1 /* Scalar evolution detector. 2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 3 Free Software Foundation, Inc. 4 Contributed by Sebastian Pop <s.pop@laposte.net> 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free 10 Software Foundation; either version 3, or (at your option) any later 11 version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 /* 23 Description: 24 25 This pass analyzes the evolution of scalar variables in loop 26 structures. The algorithm is based on the SSA representation, 27 and on the loop hierarchy tree. This algorithm is not based on 28 the notion of versions of a variable, as it was the case for the 29 previous implementations of the scalar evolution algorithm, but 30 it assumes that each defined name is unique. 31 32 The notation used in this file is called "chains of recurrences", 33 and has been proposed by Eugene Zima, Robert Van Engelen, and 34 others for describing induction variables in programs. For example 35 "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0 36 when entering in the loop_1 and has a step 2 in this loop, in other 37 words "for (b = 0; b < N; b+=2);". Note that the coefficients of 38 this chain of recurrence (or chrec [shrek]) can contain the name of 39 other variables, in which case they are called parametric chrecs. 40 For example, "b -> {a, +, 2}_1" means that the initial value of "b" 41 is the value of "a". In most of the cases these parametric chrecs 42 are fully instantiated before their use because symbolic names can 43 hide some difficult cases such as self-references described later 44 (see the Fibonacci example). 45 46 A short sketch of the algorithm is: 47 48 Given a scalar variable to be analyzed, follow the SSA edge to 49 its definition: 50 51 - When the definition is a GIMPLE_ASSIGN: if the right hand side 52 (RHS) of the definition cannot be statically analyzed, the answer 53 of the analyzer is: "don't know". 54 Otherwise, for all the variables that are not yet analyzed in the 55 RHS, try to determine their evolution, and finally try to 56 evaluate the operation of the RHS that gives the evolution 57 function of the analyzed variable. 58 59 - When the definition is a condition-phi-node: determine the 60 evolution function for all the branches of the phi node, and 61 finally merge these evolutions (see chrec_merge). 62 63 - When the definition is a loop-phi-node: determine its initial 64 condition, that is the SSA edge defined in an outer loop, and 65 keep it symbolic. Then determine the SSA edges that are defined 66 in the body of the loop. Follow the inner edges until ending on 67 another loop-phi-node of the same analyzed loop. If the reached 68 loop-phi-node is not the starting loop-phi-node, then we keep 69 this definition under a symbolic form. If the reached 70 loop-phi-node is the same as the starting one, then we compute a 71 symbolic stride on the return path. The result is then the 72 symbolic chrec {initial_condition, +, symbolic_stride}_loop. 73 74 Examples: 75 76 Example 1: Illustration of the basic algorithm. 77 78 | a = 3 79 | loop_1 80 | b = phi (a, c) 81 | c = b + 1 82 | if (c > 10) exit_loop 83 | endloop 84 85 Suppose that we want to know the number of iterations of the 86 loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We 87 ask the scalar evolution analyzer two questions: what's the 88 scalar evolution (scev) of "c", and what's the scev of "10". For 89 "10" the answer is "10" since it is a scalar constant. For the 90 scalar variable "c", it follows the SSA edge to its definition, 91 "c = b + 1", and then asks again what's the scev of "b". 92 Following the SSA edge, we end on a loop-phi-node "b = phi (a, 93 c)", where the initial condition is "a", and the inner loop edge 94 is "c". The initial condition is kept under a symbolic form (it 95 may be the case that the copy constant propagation has done its 96 work and we end with the constant "3" as one of the edges of the 97 loop-phi-node). The update edge is followed to the end of the 98 loop, and until reaching again the starting loop-phi-node: b -> c 99 -> b. At this point we have drawn a path from "b" to "b" from 100 which we compute the stride in the loop: in this example it is 101 "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now 102 that the scev for "b" is known, it is possible to compute the 103 scev for "c", that is "c -> {a + 1, +, 1}_1". In order to 104 determine the number of iterations in the loop_1, we have to 105 instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some 106 more analysis the scev {4, +, 1}_1, or in other words, this is 107 the function "f (x) = x + 4", where x is the iteration count of 108 the loop_1. Now we have to solve the inequality "x + 4 > 10", 109 and take the smallest iteration number for which the loop is 110 exited: x = 7. This loop runs from x = 0 to x = 7, and in total 111 there are 8 iterations. In terms of loop normalization, we have 112 created a variable that is implicitly defined, "x" or just "_1", 113 and all the other analyzed scalars of the loop are defined in 114 function of this variable: 115 116 a -> 3 117 b -> {3, +, 1}_1 118 c -> {4, +, 1}_1 119 120 or in terms of a C program: 121 122 | a = 3 123 | for (x = 0; x <= 7; x++) 124 | { 125 | b = x + 3 126 | c = x + 4 127 | } 128 129 Example 2a: Illustration of the algorithm on nested loops. 130 131 | loop_1 132 | a = phi (1, b) 133 | c = a + 2 134 | loop_2 10 times 135 | b = phi (c, d) 136 | d = b + 3 137 | endloop 138 | endloop 139 140 For analyzing the scalar evolution of "a", the algorithm follows 141 the SSA edge into the loop's body: "a -> b". "b" is an inner 142 loop-phi-node, and its analysis as in Example 1, gives: 143 144 b -> {c, +, 3}_2 145 d -> {c + 3, +, 3}_2 146 147 Following the SSA edge for the initial condition, we end on "c = a 148 + 2", and then on the starting loop-phi-node "a". From this point, 149 the loop stride is computed: back on "c = a + 2" we get a "+2" in 150 the loop_1, then on the loop-phi-node "b" we compute the overall 151 effect of the inner loop that is "b = c + 30", and we get a "+30" 152 in the loop_1. That means that the overall stride in loop_1 is 153 equal to "+32", and the result is: 154 155 a -> {1, +, 32}_1 156 c -> {3, +, 32}_1 157 158 Example 2b: Multivariate chains of recurrences. 159 160 | loop_1 161 | k = phi (0, k + 1) 162 | loop_2 4 times 163 | j = phi (0, j + 1) 164 | loop_3 4 times 165 | i = phi (0, i + 1) 166 | A[j + k] = ... 167 | endloop 168 | endloop 169 | endloop 170 171 Analyzing the access function of array A with 172 instantiate_parameters (loop_1, "j + k"), we obtain the 173 instantiation and the analysis of the scalar variables "j" and "k" 174 in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end 175 value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is 176 {0, +, 1}_1. To obtain the evolution function in loop_3 and 177 instantiate the scalar variables up to loop_1, one has to use: 178 instantiate_scev (block_before_loop (loop_1), loop_3, "j + k"). 179 The result of this call is {{0, +, 1}_1, +, 1}_2. 180 181 Example 3: Higher degree polynomials. 182 183 | loop_1 184 | a = phi (2, b) 185 | c = phi (5, d) 186 | b = a + 1 187 | d = c + a 188 | endloop 189 190 a -> {2, +, 1}_1 191 b -> {3, +, 1}_1 192 c -> {5, +, a}_1 193 d -> {5 + a, +, a}_1 194 195 instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1 196 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1 197 198 Example 4: Lucas, Fibonacci, or mixers in general. 199 200 | loop_1 201 | a = phi (1, b) 202 | c = phi (3, d) 203 | b = c 204 | d = c + a 205 | endloop 206 207 a -> (1, c)_1 208 c -> {3, +, a}_1 209 210 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the 211 following semantics: during the first iteration of the loop_1, the 212 variable contains the value 1, and then it contains the value "c". 213 Note that this syntax is close to the syntax of the loop-phi-node: 214 "a -> (1, c)_1" vs. "a = phi (1, c)". 215 216 The symbolic chrec representation contains all the semantics of the 217 original code. What is more difficult is to use this information. 218 219 Example 5: Flip-flops, or exchangers. 220 221 | loop_1 222 | a = phi (1, b) 223 | c = phi (3, d) 224 | b = c 225 | d = a 226 | endloop 227 228 a -> (1, c)_1 229 c -> (3, a)_1 230 231 Based on these symbolic chrecs, it is possible to refine this 232 information into the more precise PERIODIC_CHRECs: 233 234 a -> |1, 3|_1 235 c -> |3, 1|_1 236 237 This transformation is not yet implemented. 238 239 Further readings: 240 241 You can find a more detailed description of the algorithm in: 242 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf 243 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that 244 this is a preliminary report and some of the details of the 245 algorithm have changed. I'm working on a research report that 246 updates the description of the algorithms to reflect the design 247 choices used in this implementation. 248 249 A set of slides show a high level overview of the algorithm and run 250 an example through the scalar evolution analyzer: 251 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf 252 253 The slides that I have presented at the GCC Summit'04 are available 254 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf 255 */ 256 257 #include "config.h" 258 #include "system.h" 259 #include "coretypes.h" 260 #include "tm.h" 261 #include "ggc.h" 262 #include "tree.h" 263 #include "real.h" 264 265 /* These RTL headers are needed for basic-block.h. */ 266 #include "rtl.h" 267 #include "basic-block.h" 268 #include "diagnostic.h" 269 #include "tree-flow.h" 270 #include "tree-dump.h" 271 #include "timevar.h" 272 #include "cfgloop.h" 273 #include "tree-chrec.h" 274 #include "tree-scalar-evolution.h" 275 #include "tree-pass.h" 276 #include "flags.h" 277 #include "params.h" 278 279 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree); 280 281 /* The cached information about an SSA name VAR, claiming that below 282 basic block INSTANTIATED_BELOW, the value of VAR can be expressed 283 as CHREC. */ 284 285 struct GTY(()) scev_info_str { 286 basic_block instantiated_below; 287 tree var; 288 tree chrec; 289 }; 290 291 /* Counters for the scev database. */ 292 static unsigned nb_set_scev = 0; 293 static unsigned nb_get_scev = 0; 294 295 /* The following trees are unique elements. Thus the comparison of 296 another element to these elements should be done on the pointer to 297 these trees, and not on their value. */ 298 299 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */ 300 tree chrec_not_analyzed_yet; 301 302 /* Reserved to the cases where the analyzer has detected an 303 undecidable property at compile time. */ 304 tree chrec_dont_know; 305 306 /* When the analyzer has detected that a property will never 307 happen, then it qualifies it with chrec_known. */ 308 tree chrec_known; 309 310 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info; 311 312 313 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ 314 315 static inline struct scev_info_str * 316 new_scev_info_str (basic_block instantiated_below, tree var) 317 { 318 struct scev_info_str *res; 319 320 res = GGC_NEW (struct scev_info_str); 321 res->var = var; 322 res->chrec = chrec_not_analyzed_yet; 323 res->instantiated_below = instantiated_below; 324 325 return res; 326 } 327 328 /* Computes a hash function for database element ELT. */ 329 330 static hashval_t 331 hash_scev_info (const void *elt) 332 { 333 return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var); 334 } 335 336 /* Compares database elements E1 and E2. */ 337 338 static int 339 eq_scev_info (const void *e1, const void *e2) 340 { 341 const struct scev_info_str *elt1 = (const struct scev_info_str *) e1; 342 const struct scev_info_str *elt2 = (const struct scev_info_str *) e2; 343 344 return (elt1->var == elt2->var 345 && elt1->instantiated_below == elt2->instantiated_below); 346 } 347 348 /* Deletes database element E. */ 349 350 static void 351 del_scev_info (void *e) 352 { 353 ggc_free (e); 354 } 355 356 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block. 357 A first query on VAR returns chrec_not_analyzed_yet. */ 358 359 static tree * 360 find_var_scev_info (basic_block instantiated_below, tree var) 361 { 362 struct scev_info_str *res; 363 struct scev_info_str tmp; 364 PTR *slot; 365 366 tmp.var = var; 367 tmp.instantiated_below = instantiated_below; 368 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT); 369 370 if (!*slot) 371 *slot = new_scev_info_str (instantiated_below, var); 372 res = (struct scev_info_str *) *slot; 373 374 return &res->chrec; 375 } 376 377 /* Return true when CHREC contains symbolic names defined in 378 LOOP_NB. */ 379 380 bool 381 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb) 382 { 383 int i, n; 384 385 if (chrec == NULL_TREE) 386 return false; 387 388 if (is_gimple_min_invariant (chrec)) 389 return false; 390 391 if (TREE_CODE (chrec) == VAR_DECL 392 || TREE_CODE (chrec) == PARM_DECL 393 || TREE_CODE (chrec) == FUNCTION_DECL 394 || TREE_CODE (chrec) == LABEL_DECL 395 || TREE_CODE (chrec) == RESULT_DECL 396 || TREE_CODE (chrec) == FIELD_DECL) 397 return true; 398 399 if (TREE_CODE (chrec) == SSA_NAME) 400 { 401 gimple def = SSA_NAME_DEF_STMT (chrec); 402 struct loop *def_loop = loop_containing_stmt (def); 403 struct loop *loop = get_loop (loop_nb); 404 405 if (def_loop == NULL) 406 return false; 407 408 if (loop == def_loop || flow_loop_nested_p (loop, def_loop)) 409 return true; 410 411 return false; 412 } 413 414 n = TREE_OPERAND_LENGTH (chrec); 415 for (i = 0; i < n; i++) 416 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i), 417 loop_nb)) 418 return true; 419 return false; 420 } 421 422 /* Return true when PHI is a loop-phi-node. */ 423 424 static bool 425 loop_phi_node_p (gimple phi) 426 { 427 /* The implementation of this function is based on the following 428 property: "all the loop-phi-nodes of a loop are contained in the 429 loop's header basic block". */ 430 431 return loop_containing_stmt (phi)->header == gimple_bb (phi); 432 } 433 434 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP. 435 In general, in the case of multivariate evolutions we want to get 436 the evolution in different loops. LOOP specifies the level for 437 which to get the evolution. 438 439 Example: 440 441 | for (j = 0; j < 100; j++) 442 | { 443 | for (k = 0; k < 100; k++) 444 | { 445 | i = k + j; - Here the value of i is a function of j, k. 446 | } 447 | ... = i - Here the value of i is a function of j. 448 | } 449 | ... = i - Here the value of i is a scalar. 450 451 Example: 452 453 | i_0 = ... 454 | loop_1 10 times 455 | i_1 = phi (i_0, i_2) 456 | i_2 = i_1 + 2 457 | endloop 458 459 This loop has the same effect as: 460 LOOP_1 has the same effect as: 461 462 | i_1 = i_0 + 20 463 464 The overall effect of the loop, "i_0 + 20" in the previous example, 465 is obtained by passing in the parameters: LOOP = 1, 466 EVOLUTION_FN = {i_0, +, 2}_1. 467 */ 468 469 tree 470 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) 471 { 472 bool val = false; 473 474 if (evolution_fn == chrec_dont_know) 475 return chrec_dont_know; 476 477 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC) 478 { 479 struct loop *inner_loop = get_chrec_loop (evolution_fn); 480 481 if (inner_loop == loop 482 || flow_loop_nested_p (loop, inner_loop)) 483 { 484 tree nb_iter = number_of_latch_executions (inner_loop); 485 486 if (nb_iter == chrec_dont_know) 487 return chrec_dont_know; 488 else 489 { 490 tree res; 491 492 /* evolution_fn is the evolution function in LOOP. Get 493 its value in the nb_iter-th iteration. */ 494 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter); 495 496 if (chrec_contains_symbols_defined_in_loop (res, loop->num)) 497 res = instantiate_parameters (loop, res); 498 499 /* Continue the computation until ending on a parent of LOOP. */ 500 return compute_overall_effect_of_inner_loop (loop, res); 501 } 502 } 503 else 504 return evolution_fn; 505 } 506 507 /* If the evolution function is an invariant, there is nothing to do. */ 508 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val) 509 return evolution_fn; 510 511 else 512 return chrec_dont_know; 513 } 514 515 /* Determine whether the CHREC is always positive/negative. If the expression 516 cannot be statically analyzed, return false, otherwise set the answer into 517 VALUE. */ 518 519 bool 520 chrec_is_positive (tree chrec, bool *value) 521 { 522 bool value0, value1, value2; 523 tree end_value, nb_iter; 524 525 switch (TREE_CODE (chrec)) 526 { 527 case POLYNOMIAL_CHREC: 528 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0) 529 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1)) 530 return false; 531 532 /* FIXME -- overflows. */ 533 if (value0 == value1) 534 { 535 *value = value0; 536 return true; 537 } 538 539 /* Otherwise the chrec is under the form: "{-197, +, 2}_1", 540 and the proof consists in showing that the sign never 541 changes during the execution of the loop, from 0 to 542 loop->nb_iterations. */ 543 if (!evolution_function_is_affine_p (chrec)) 544 return false; 545 546 nb_iter = number_of_latch_executions (get_chrec_loop (chrec)); 547 if (chrec_contains_undetermined (nb_iter)) 548 return false; 549 550 #if 0 551 /* TODO -- If the test is after the exit, we may decrease the number of 552 iterations by one. */ 553 if (after_exit) 554 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1)); 555 #endif 556 557 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter); 558 559 if (!chrec_is_positive (end_value, &value2)) 560 return false; 561 562 *value = value0; 563 return value0 == value1; 564 565 case INTEGER_CST: 566 *value = (tree_int_cst_sgn (chrec) == 1); 567 return true; 568 569 default: 570 return false; 571 } 572 } 573 574 /* Associate CHREC to SCALAR. */ 575 576 static void 577 set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec) 578 { 579 tree *scalar_info; 580 581 if (TREE_CODE (scalar) != SSA_NAME) 582 return; 583 584 scalar_info = find_var_scev_info (instantiated_below, scalar); 585 586 if (dump_file) 587 { 588 if (dump_flags & TDF_DETAILS) 589 { 590 fprintf (dump_file, "(set_scalar_evolution \n"); 591 fprintf (dump_file, " instantiated_below = %d \n", 592 instantiated_below->index); 593 fprintf (dump_file, " (scalar = "); 594 print_generic_expr (dump_file, scalar, 0); 595 fprintf (dump_file, ")\n (scalar_evolution = "); 596 print_generic_expr (dump_file, chrec, 0); 597 fprintf (dump_file, "))\n"); 598 } 599 if (dump_flags & TDF_STATS) 600 nb_set_scev++; 601 } 602 603 *scalar_info = chrec; 604 } 605 606 /* Retrieve the chrec associated to SCALAR instantiated below 607 INSTANTIATED_BELOW block. */ 608 609 static tree 610 get_scalar_evolution (basic_block instantiated_below, tree scalar) 611 { 612 tree res; 613 614 if (dump_file) 615 { 616 if (dump_flags & TDF_DETAILS) 617 { 618 fprintf (dump_file, "(get_scalar_evolution \n"); 619 fprintf (dump_file, " (scalar = "); 620 print_generic_expr (dump_file, scalar, 0); 621 fprintf (dump_file, ")\n"); 622 } 623 if (dump_flags & TDF_STATS) 624 nb_get_scev++; 625 } 626 627 switch (TREE_CODE (scalar)) 628 { 629 case SSA_NAME: 630 res = *find_var_scev_info (instantiated_below, scalar); 631 break; 632 633 case REAL_CST: 634 case FIXED_CST: 635 case INTEGER_CST: 636 res = scalar; 637 break; 638 639 default: 640 res = chrec_not_analyzed_yet; 641 break; 642 } 643 644 if (dump_file && (dump_flags & TDF_DETAILS)) 645 { 646 fprintf (dump_file, " (scalar_evolution = "); 647 print_generic_expr (dump_file, res, 0); 648 fprintf (dump_file, "))\n"); 649 } 650 651 return res; 652 } 653 654 /* Helper function for add_to_evolution. Returns the evolution 655 function for an assignment of the form "a = b + c", where "a" and 656 "b" are on the strongly connected component. CHREC_BEFORE is the 657 information that we already have collected up to this point. 658 TO_ADD is the evolution of "c". 659 660 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this 661 evolution the expression TO_ADD, otherwise construct an evolution 662 part for this loop. */ 663 664 static tree 665 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, 666 gimple at_stmt) 667 { 668 tree type, left, right; 669 struct loop *loop = get_loop (loop_nb), *chloop; 670 671 switch (TREE_CODE (chrec_before)) 672 { 673 case POLYNOMIAL_CHREC: 674 chloop = get_chrec_loop (chrec_before); 675 if (chloop == loop 676 || flow_loop_nested_p (chloop, loop)) 677 { 678 unsigned var; 679 680 type = chrec_type (chrec_before); 681 682 /* When there is no evolution part in this loop, build it. */ 683 if (chloop != loop) 684 { 685 var = loop_nb; 686 left = chrec_before; 687 right = SCALAR_FLOAT_TYPE_P (type) 688 ? build_real (type, dconst0) 689 : build_int_cst (type, 0); 690 } 691 else 692 { 693 var = CHREC_VARIABLE (chrec_before); 694 left = CHREC_LEFT (chrec_before); 695 right = CHREC_RIGHT (chrec_before); 696 } 697 698 to_add = chrec_convert (type, to_add, at_stmt); 699 right = chrec_convert_rhs (type, right, at_stmt); 700 right = chrec_fold_plus (chrec_type (right), right, to_add); 701 return build_polynomial_chrec (var, left, right); 702 } 703 else 704 { 705 gcc_assert (flow_loop_nested_p (loop, chloop)); 706 707 /* Search the evolution in LOOP_NB. */ 708 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), 709 to_add, at_stmt); 710 right = CHREC_RIGHT (chrec_before); 711 right = chrec_convert_rhs (chrec_type (left), right, at_stmt); 712 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before), 713 left, right); 714 } 715 716 default: 717 /* These nodes do not depend on a loop. */ 718 if (chrec_before == chrec_dont_know) 719 return chrec_dont_know; 720 721 left = chrec_before; 722 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt); 723 return build_polynomial_chrec (loop_nb, left, right); 724 } 725 } 726 727 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension 728 of LOOP_NB. 729 730 Description (provided for completeness, for those who read code in 731 a plane, and for my poor 62 bytes brain that would have forgotten 732 all this in the next two or three months): 733 734 The algorithm of translation of programs from the SSA representation 735 into the chrecs syntax is based on a pattern matching. After having 736 reconstructed the overall tree expression for a loop, there are only 737 two cases that can arise: 738 739 1. a = loop-phi (init, a + expr) 740 2. a = loop-phi (init, expr) 741 742 where EXPR is either a scalar constant with respect to the analyzed 743 loop (this is a degree 0 polynomial), or an expression containing 744 other loop-phi definitions (these are higher degree polynomials). 745 746 Examples: 747 748 1. 749 | init = ... 750 | loop_1 751 | a = phi (init, a + 5) 752 | endloop 753 754 2. 755 | inita = ... 756 | initb = ... 757 | loop_1 758 | a = phi (inita, 2 * b + 3) 759 | b = phi (initb, b + 1) 760 | endloop 761 762 For the first case, the semantics of the SSA representation is: 763 764 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j) 765 766 that is, there is a loop index "x" that determines the scalar value 767 of the variable during the loop execution. During the first 768 iteration, the value is that of the initial condition INIT, while 769 during the subsequent iterations, it is the sum of the initial 770 condition with the sum of all the values of EXPR from the initial 771 iteration to the before last considered iteration. 772 773 For the second case, the semantics of the SSA program is: 774 775 | a (x) = init, if x = 0; 776 | expr (x - 1), otherwise. 777 778 The second case corresponds to the PEELED_CHREC, whose syntax is 779 close to the syntax of a loop-phi-node: 780 781 | phi (init, expr) vs. (init, expr)_x 782 783 The proof of the translation algorithm for the first case is a 784 proof by structural induction based on the degree of EXPR. 785 786 Degree 0: 787 When EXPR is a constant with respect to the analyzed loop, or in 788 other words when EXPR is a polynomial of degree 0, the evolution of 789 the variable A in the loop is an affine function with an initial 790 condition INIT, and a step EXPR. In order to show this, we start 791 from the semantics of the SSA representation: 792 793 f (x) = init + \sum_{j = 0}^{x - 1} expr (j) 794 795 and since "expr (j)" is a constant with respect to "j", 796 797 f (x) = init + x * expr 798 799 Finally, based on the semantics of the pure sum chrecs, by 800 identification we get the corresponding chrecs syntax: 801 802 f (x) = init * \binom{x}{0} + expr * \binom{x}{1} 803 f (x) -> {init, +, expr}_x 804 805 Higher degree: 806 Suppose that EXPR is a polynomial of degree N with respect to the 807 analyzed loop_x for which we have already determined that it is 808 written under the chrecs syntax: 809 810 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x) 811 812 We start from the semantics of the SSA program: 813 814 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j) 815 | 816 | f (x) = init + \sum_{j = 0}^{x - 1} 817 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1}) 818 | 819 | f (x) = init + \sum_{j = 0}^{x - 1} 820 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k}) 821 | 822 | f (x) = init + \sum_{k = 0}^{n - 1} 823 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k}) 824 | 825 | f (x) = init + \sum_{k = 0}^{n - 1} 826 | (b_k * \binom{x}{k + 1}) 827 | 828 | f (x) = init + b_0 * \binom{x}{1} + ... 829 | + b_{n-1} * \binom{x}{n} 830 | 831 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ... 832 | + b_{n-1} * \binom{x}{n} 833 | 834 835 And finally from the definition of the chrecs syntax, we identify: 836 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x 837 838 This shows the mechanism that stands behind the add_to_evolution 839 function. An important point is that the use of symbolic 840 parameters avoids the need of an analysis schedule. 841 842 Example: 843 844 | inita = ... 845 | initb = ... 846 | loop_1 847 | a = phi (inita, a + 2 + b) 848 | b = phi (initb, b + 1) 849 | endloop 850 851 When analyzing "a", the algorithm keeps "b" symbolically: 852 853 | a -> {inita, +, 2 + b}_1 854 855 Then, after instantiation, the analyzer ends on the evolution: 856 857 | a -> {inita, +, 2 + initb, +, 1}_1 858 859 */ 860 861 static tree 862 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, 863 tree to_add, gimple at_stmt) 864 { 865 tree type = chrec_type (to_add); 866 tree res = NULL_TREE; 867 868 if (to_add == NULL_TREE) 869 return chrec_before; 870 871 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not 872 instantiated at this point. */ 873 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC) 874 /* This should not happen. */ 875 return chrec_dont_know; 876 877 if (dump_file && (dump_flags & TDF_DETAILS)) 878 { 879 fprintf (dump_file, "(add_to_evolution \n"); 880 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb); 881 fprintf (dump_file, " (chrec_before = "); 882 print_generic_expr (dump_file, chrec_before, 0); 883 fprintf (dump_file, ")\n (to_add = "); 884 print_generic_expr (dump_file, to_add, 0); 885 fprintf (dump_file, ")\n"); 886 } 887 888 if (code == MINUS_EXPR) 889 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type) 890 ? build_real (type, dconstm1) 891 : build_int_cst_type (type, -1)); 892 893 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt); 894 895 if (dump_file && (dump_flags & TDF_DETAILS)) 896 { 897 fprintf (dump_file, " (res = "); 898 print_generic_expr (dump_file, res, 0); 899 fprintf (dump_file, "))\n"); 900 } 901 902 return res; 903 } 904 905 /* Helper function. */ 906 907 static inline tree 908 set_nb_iterations_in_loop (struct loop *loop, 909 tree res) 910 { 911 if (dump_file && (dump_flags & TDF_DETAILS)) 912 { 913 fprintf (dump_file, " (set_nb_iterations_in_loop = "); 914 print_generic_expr (dump_file, res, 0); 915 fprintf (dump_file, "))\n"); 916 } 917 918 loop->nb_iterations = res; 919 return res; 920 } 921 922 923 924 /* This section selects the loops that will be good candidates for the 925 scalar evolution analysis. For the moment, greedily select all the 926 loop nests we could analyze. */ 927 928 /* For a loop with a single exit edge, return the COND_EXPR that 929 guards the exit edge. If the expression is too difficult to 930 analyze, then give up. */ 931 932 gimple 933 get_loop_exit_condition (const struct loop *loop) 934 { 935 gimple res = NULL; 936 edge exit_edge = single_exit (loop); 937 938 if (dump_file && (dump_flags & TDF_DETAILS)) 939 fprintf (dump_file, "(get_loop_exit_condition \n "); 940 941 if (exit_edge) 942 { 943 gimple stmt; 944 945 stmt = last_stmt (exit_edge->src); 946 if (gimple_code (stmt) == GIMPLE_COND) 947 res = stmt; 948 } 949 950 if (dump_file && (dump_flags & TDF_DETAILS)) 951 { 952 print_gimple_stmt (dump_file, res, 0, 0); 953 fprintf (dump_file, ")\n"); 954 } 955 956 return res; 957 } 958 959 /* Recursively determine and enqueue the exit conditions for a loop. */ 960 961 static void 962 get_exit_conditions_rec (struct loop *loop, 963 VEC(gimple,heap) **exit_conditions) 964 { 965 if (!loop) 966 return; 967 968 /* Recurse on the inner loops, then on the next (sibling) loops. */ 969 get_exit_conditions_rec (loop->inner, exit_conditions); 970 get_exit_conditions_rec (loop->next, exit_conditions); 971 972 if (single_exit (loop)) 973 { 974 gimple loop_condition = get_loop_exit_condition (loop); 975 976 if (loop_condition) 977 VEC_safe_push (gimple, heap, *exit_conditions, loop_condition); 978 } 979 } 980 981 /* Select the candidate loop nests for the analysis. This function 982 initializes the EXIT_CONDITIONS array. */ 983 984 static void 985 select_loops_exit_conditions (VEC(gimple,heap) **exit_conditions) 986 { 987 struct loop *function_body = current_loops->tree_root; 988 989 get_exit_conditions_rec (function_body->inner, exit_conditions); 990 } 991 992 993 /* Depth first search algorithm. */ 994 995 typedef enum t_bool { 996 t_false, 997 t_true, 998 t_dont_know 999 } t_bool; 1000 1001 1002 static t_bool follow_ssa_edge (struct loop *loop, gimple, gimple, tree *, int); 1003 1004 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1. 1005 Return true if the strongly connected component has been found. */ 1006 1007 static t_bool 1008 follow_ssa_edge_binary (struct loop *loop, gimple at_stmt, 1009 tree type, tree rhs0, enum tree_code code, tree rhs1, 1010 gimple halting_phi, tree *evolution_of_loop, int limit) 1011 { 1012 t_bool res = t_false; 1013 tree evol; 1014 1015 switch (code) 1016 { 1017 case POINTER_PLUS_EXPR: 1018 case PLUS_EXPR: 1019 if (TREE_CODE (rhs0) == SSA_NAME) 1020 { 1021 if (TREE_CODE (rhs1) == SSA_NAME) 1022 { 1023 /* Match an assignment under the form: 1024 "a = b + c". */ 1025 1026 /* We want only assignments of form "name + name" contribute to 1027 LIMIT, as the other cases do not necessarily contribute to 1028 the complexity of the expression. */ 1029 limit++; 1030 1031 evol = *evolution_of_loop; 1032 res = follow_ssa_edge 1033 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit); 1034 1035 if (res == t_true) 1036 *evolution_of_loop = add_to_evolution 1037 (loop->num, 1038 chrec_convert (type, evol, at_stmt), 1039 code, rhs1, at_stmt); 1040 1041 else if (res == t_false) 1042 { 1043 res = follow_ssa_edge 1044 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 1045 evolution_of_loop, limit); 1046 1047 if (res == t_true) 1048 *evolution_of_loop = add_to_evolution 1049 (loop->num, 1050 chrec_convert (type, *evolution_of_loop, at_stmt), 1051 code, rhs0, at_stmt); 1052 1053 else if (res == t_dont_know) 1054 *evolution_of_loop = chrec_dont_know; 1055 } 1056 1057 else if (res == t_dont_know) 1058 *evolution_of_loop = chrec_dont_know; 1059 } 1060 1061 else 1062 { 1063 /* Match an assignment under the form: 1064 "a = b + ...". */ 1065 res = follow_ssa_edge 1066 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 1067 evolution_of_loop, limit); 1068 if (res == t_true) 1069 *evolution_of_loop = add_to_evolution 1070 (loop->num, chrec_convert (type, *evolution_of_loop, 1071 at_stmt), 1072 code, rhs1, at_stmt); 1073 1074 else if (res == t_dont_know) 1075 *evolution_of_loop = chrec_dont_know; 1076 } 1077 } 1078 1079 else if (TREE_CODE (rhs1) == SSA_NAME) 1080 { 1081 /* Match an assignment under the form: 1082 "a = ... + c". */ 1083 res = follow_ssa_edge 1084 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 1085 evolution_of_loop, limit); 1086 if (res == t_true) 1087 *evolution_of_loop = add_to_evolution 1088 (loop->num, chrec_convert (type, *evolution_of_loop, 1089 at_stmt), 1090 code, rhs0, at_stmt); 1091 1092 else if (res == t_dont_know) 1093 *evolution_of_loop = chrec_dont_know; 1094 } 1095 1096 else 1097 /* Otherwise, match an assignment under the form: 1098 "a = ... + ...". */ 1099 /* And there is nothing to do. */ 1100 res = t_false; 1101 break; 1102 1103 case MINUS_EXPR: 1104 /* This case is under the form "opnd0 = rhs0 - rhs1". */ 1105 if (TREE_CODE (rhs0) == SSA_NAME) 1106 { 1107 /* Match an assignment under the form: 1108 "a = b - ...". */ 1109 1110 /* We want only assignments of form "name - name" contribute to 1111 LIMIT, as the other cases do not necessarily contribute to 1112 the complexity of the expression. */ 1113 if (TREE_CODE (rhs1) == SSA_NAME) 1114 limit++; 1115 1116 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 1117 evolution_of_loop, limit); 1118 if (res == t_true) 1119 *evolution_of_loop = add_to_evolution 1120 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt), 1121 MINUS_EXPR, rhs1, at_stmt); 1122 1123 else if (res == t_dont_know) 1124 *evolution_of_loop = chrec_dont_know; 1125 } 1126 else 1127 /* Otherwise, match an assignment under the form: 1128 "a = ... - ...". */ 1129 /* And there is nothing to do. */ 1130 res = t_false; 1131 break; 1132 1133 default: 1134 res = t_false; 1135 } 1136 1137 return res; 1138 } 1139 1140 /* Follow the ssa edge into the expression EXPR. 1141 Return true if the strongly connected component has been found. */ 1142 1143 static t_bool 1144 follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr, 1145 gimple halting_phi, tree *evolution_of_loop, int limit) 1146 { 1147 enum tree_code code = TREE_CODE (expr); 1148 tree type = TREE_TYPE (expr), rhs0, rhs1; 1149 t_bool res; 1150 1151 /* The EXPR is one of the following cases: 1152 - an SSA_NAME, 1153 - an INTEGER_CST, 1154 - a PLUS_EXPR, 1155 - a POINTER_PLUS_EXPR, 1156 - a MINUS_EXPR, 1157 - an ASSERT_EXPR, 1158 - other cases are not yet handled. */ 1159 1160 switch (code) 1161 { 1162 CASE_CONVERT: 1163 /* This assignment is under the form "a_1 = (cast) rhs. */ 1164 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0), 1165 halting_phi, evolution_of_loop, limit); 1166 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt); 1167 break; 1168 1169 case INTEGER_CST: 1170 /* This assignment is under the form "a_1 = 7". */ 1171 res = t_false; 1172 break; 1173 1174 case SSA_NAME: 1175 /* This assignment is under the form: "a_1 = b_2". */ 1176 res = follow_ssa_edge 1177 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit); 1178 break; 1179 1180 case POINTER_PLUS_EXPR: 1181 case PLUS_EXPR: 1182 case MINUS_EXPR: 1183 /* This case is under the form "rhs0 +- rhs1". */ 1184 rhs0 = TREE_OPERAND (expr, 0); 1185 rhs1 = TREE_OPERAND (expr, 1); 1186 type = TREE_TYPE (rhs0); 1187 STRIP_USELESS_TYPE_CONVERSION (rhs0); 1188 STRIP_USELESS_TYPE_CONVERSION (rhs1); 1189 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1, 1190 halting_phi, evolution_of_loop, limit); 1191 break; 1192 1193 case ASSERT_EXPR: 1194 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>" 1195 It must be handled as a copy assignment of the form a_1 = a_2. */ 1196 rhs0 = ASSERT_EXPR_VAR (expr); 1197 if (TREE_CODE (rhs0) == SSA_NAME) 1198 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), 1199 halting_phi, evolution_of_loop, limit); 1200 else 1201 res = t_false; 1202 break; 1203 1204 default: 1205 res = t_false; 1206 break; 1207 } 1208 1209 return res; 1210 } 1211 1212 /* Follow the ssa edge into the right hand side of an assignment STMT. 1213 Return true if the strongly connected component has been found. */ 1214 1215 static t_bool 1216 follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt, 1217 gimple halting_phi, tree *evolution_of_loop, int limit) 1218 { 1219 enum tree_code code = gimple_assign_rhs_code (stmt); 1220 tree type = gimple_expr_type (stmt), rhs1, rhs2; 1221 t_bool res; 1222 1223 switch (code) 1224 { 1225 CASE_CONVERT: 1226 /* This assignment is under the form "a_1 = (cast) rhs. */ 1227 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt), 1228 halting_phi, evolution_of_loop, limit); 1229 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt); 1230 break; 1231 1232 case POINTER_PLUS_EXPR: 1233 case PLUS_EXPR: 1234 case MINUS_EXPR: 1235 rhs1 = gimple_assign_rhs1 (stmt); 1236 rhs2 = gimple_assign_rhs2 (stmt); 1237 type = TREE_TYPE (rhs1); 1238 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2, 1239 halting_phi, evolution_of_loop, limit); 1240 break; 1241 1242 default: 1243 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) 1244 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt), 1245 halting_phi, evolution_of_loop, limit); 1246 else 1247 res = t_false; 1248 break; 1249 } 1250 1251 return res; 1252 } 1253 1254 /* Checks whether the I-th argument of a PHI comes from a backedge. */ 1255 1256 static bool 1257 backedge_phi_arg_p (gimple phi, int i) 1258 { 1259 const_edge e = gimple_phi_arg_edge (phi, i); 1260 1261 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care 1262 about updating it anywhere, and this should work as well most of the 1263 time. */ 1264 if (e->flags & EDGE_IRREDUCIBLE_LOOP) 1265 return true; 1266 1267 return false; 1268 } 1269 1270 /* Helper function for one branch of the condition-phi-node. Return 1271 true if the strongly connected component has been found following 1272 this path. */ 1273 1274 static inline t_bool 1275 follow_ssa_edge_in_condition_phi_branch (int i, 1276 struct loop *loop, 1277 gimple condition_phi, 1278 gimple halting_phi, 1279 tree *evolution_of_branch, 1280 tree init_cond, int limit) 1281 { 1282 tree branch = PHI_ARG_DEF (condition_phi, i); 1283 *evolution_of_branch = chrec_dont_know; 1284 1285 /* Do not follow back edges (they must belong to an irreducible loop, which 1286 we really do not want to worry about). */ 1287 if (backedge_phi_arg_p (condition_phi, i)) 1288 return t_false; 1289 1290 if (TREE_CODE (branch) == SSA_NAME) 1291 { 1292 *evolution_of_branch = init_cond; 1293 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, 1294 evolution_of_branch, limit); 1295 } 1296 1297 /* This case occurs when one of the condition branches sets 1298 the variable to a constant: i.e. a phi-node like 1299 "a_2 = PHI <a_7(5), 2(6)>;". 1300 1301 FIXME: This case have to be refined correctly: 1302 in some cases it is possible to say something better than 1303 chrec_dont_know, for example using a wrap-around notation. */ 1304 return t_false; 1305 } 1306 1307 /* This function merges the branches of a condition-phi-node in a 1308 loop. */ 1309 1310 static t_bool 1311 follow_ssa_edge_in_condition_phi (struct loop *loop, 1312 gimple condition_phi, 1313 gimple halting_phi, 1314 tree *evolution_of_loop, int limit) 1315 { 1316 int i, n; 1317 tree init = *evolution_of_loop; 1318 tree evolution_of_branch; 1319 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi, 1320 halting_phi, 1321 &evolution_of_branch, 1322 init, limit); 1323 if (res == t_false || res == t_dont_know) 1324 return res; 1325 1326 *evolution_of_loop = evolution_of_branch; 1327 1328 n = gimple_phi_num_args (condition_phi); 1329 for (i = 1; i < n; i++) 1330 { 1331 /* Quickly give up when the evolution of one of the branches is 1332 not known. */ 1333 if (*evolution_of_loop == chrec_dont_know) 1334 return t_true; 1335 1336 /* Increase the limit by the PHI argument number to avoid exponential 1337 time and memory complexity. */ 1338 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi, 1339 halting_phi, 1340 &evolution_of_branch, 1341 init, limit + i); 1342 if (res == t_false || res == t_dont_know) 1343 return res; 1344 1345 *evolution_of_loop = chrec_merge (*evolution_of_loop, 1346 evolution_of_branch); 1347 } 1348 1349 return t_true; 1350 } 1351 1352 /* Follow an SSA edge in an inner loop. It computes the overall 1353 effect of the loop, and following the symbolic initial conditions, 1354 it follows the edges in the parent loop. The inner loop is 1355 considered as a single statement. */ 1356 1357 static t_bool 1358 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, 1359 gimple loop_phi_node, 1360 gimple halting_phi, 1361 tree *evolution_of_loop, int limit) 1362 { 1363 struct loop *loop = loop_containing_stmt (loop_phi_node); 1364 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node)); 1365 1366 /* Sometimes, the inner loop is too difficult to analyze, and the 1367 result of the analysis is a symbolic parameter. */ 1368 if (ev == PHI_RESULT (loop_phi_node)) 1369 { 1370 t_bool res = t_false; 1371 int i, n = gimple_phi_num_args (loop_phi_node); 1372 1373 for (i = 0; i < n; i++) 1374 { 1375 tree arg = PHI_ARG_DEF (loop_phi_node, i); 1376 basic_block bb; 1377 1378 /* Follow the edges that exit the inner loop. */ 1379 bb = gimple_phi_arg_edge (loop_phi_node, i)->src; 1380 if (!flow_bb_inside_loop_p (loop, bb)) 1381 res = follow_ssa_edge_expr (outer_loop, loop_phi_node, 1382 arg, halting_phi, 1383 evolution_of_loop, limit); 1384 if (res == t_true) 1385 break; 1386 } 1387 1388 /* If the path crosses this loop-phi, give up. */ 1389 if (res == t_true) 1390 *evolution_of_loop = chrec_dont_know; 1391 1392 return res; 1393 } 1394 1395 /* Otherwise, compute the overall effect of the inner loop. */ 1396 ev = compute_overall_effect_of_inner_loop (loop, ev); 1397 return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi, 1398 evolution_of_loop, limit); 1399 } 1400 1401 /* Follow an SSA edge from a loop-phi-node to itself, constructing a 1402 path that is analyzed on the return walk. */ 1403 1404 static t_bool 1405 follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi, 1406 tree *evolution_of_loop, int limit) 1407 { 1408 struct loop *def_loop; 1409 1410 if (gimple_nop_p (def)) 1411 return t_false; 1412 1413 /* Give up if the path is longer than the MAX that we allow. */ 1414 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 1415 return t_dont_know; 1416 1417 def_loop = loop_containing_stmt (def); 1418 1419 switch (gimple_code (def)) 1420 { 1421 case GIMPLE_PHI: 1422 if (!loop_phi_node_p (def)) 1423 /* DEF is a condition-phi-node. Follow the branches, and 1424 record their evolutions. Finally, merge the collected 1425 information and set the approximation to the main 1426 variable. */ 1427 return follow_ssa_edge_in_condition_phi 1428 (loop, def, halting_phi, evolution_of_loop, limit); 1429 1430 /* When the analyzed phi is the halting_phi, the 1431 depth-first search is over: we have found a path from 1432 the halting_phi to itself in the loop. */ 1433 if (def == halting_phi) 1434 return t_true; 1435 1436 /* Otherwise, the evolution of the HALTING_PHI depends 1437 on the evolution of another loop-phi-node, i.e. the 1438 evolution function is a higher degree polynomial. */ 1439 if (def_loop == loop) 1440 return t_false; 1441 1442 /* Inner loop. */ 1443 if (flow_loop_nested_p (loop, def_loop)) 1444 return follow_ssa_edge_inner_loop_phi 1445 (loop, def, halting_phi, evolution_of_loop, limit + 1); 1446 1447 /* Outer loop. */ 1448 return t_false; 1449 1450 case GIMPLE_ASSIGN: 1451 return follow_ssa_edge_in_rhs (loop, def, halting_phi, 1452 evolution_of_loop, limit); 1453 1454 default: 1455 /* At this level of abstraction, the program is just a set 1456 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no 1457 other node to be handled. */ 1458 return t_false; 1459 } 1460 } 1461 1462 1463 1464 /* Given a LOOP_PHI_NODE, this function determines the evolution 1465 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */ 1466 1467 static tree 1468 analyze_evolution_in_loop (gimple loop_phi_node, 1469 tree init_cond) 1470 { 1471 int i, n = gimple_phi_num_args (loop_phi_node); 1472 tree evolution_function = chrec_not_analyzed_yet; 1473 struct loop *loop = loop_containing_stmt (loop_phi_node); 1474 basic_block bb; 1475 1476 if (dump_file && (dump_flags & TDF_DETAILS)) 1477 { 1478 fprintf (dump_file, "(analyze_evolution_in_loop \n"); 1479 fprintf (dump_file, " (loop_phi_node = "); 1480 print_gimple_stmt (dump_file, loop_phi_node, 0, 0); 1481 fprintf (dump_file, ")\n"); 1482 } 1483 1484 for (i = 0; i < n; i++) 1485 { 1486 tree arg = PHI_ARG_DEF (loop_phi_node, i); 1487 gimple ssa_chain; 1488 tree ev_fn; 1489 t_bool res; 1490 1491 /* Select the edges that enter the loop body. */ 1492 bb = gimple_phi_arg_edge (loop_phi_node, i)->src; 1493 if (!flow_bb_inside_loop_p (loop, bb)) 1494 continue; 1495 1496 if (TREE_CODE (arg) == SSA_NAME) 1497 { 1498 bool val = false; 1499 1500 ssa_chain = SSA_NAME_DEF_STMT (arg); 1501 1502 /* Pass in the initial condition to the follow edge function. */ 1503 ev_fn = init_cond; 1504 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0); 1505 1506 /* If ev_fn has no evolution in the inner loop, and the 1507 init_cond is not equal to ev_fn, then we have an 1508 ambiguity between two possible values, as we cannot know 1509 the number of iterations at this point. */ 1510 if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC 1511 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val 1512 && !operand_equal_p (init_cond, ev_fn, 0)) 1513 ev_fn = chrec_dont_know; 1514 } 1515 else 1516 res = t_false; 1517 1518 /* When it is impossible to go back on the same 1519 loop_phi_node by following the ssa edges, the 1520 evolution is represented by a peeled chrec, i.e. the 1521 first iteration, EV_FN has the value INIT_COND, then 1522 all the other iterations it has the value of ARG. 1523 For the moment, PEELED_CHREC nodes are not built. */ 1524 if (res != t_true) 1525 ev_fn = chrec_dont_know; 1526 1527 /* When there are multiple back edges of the loop (which in fact never 1528 happens currently, but nevertheless), merge their evolutions. */ 1529 evolution_function = chrec_merge (evolution_function, ev_fn); 1530 } 1531 1532 if (dump_file && (dump_flags & TDF_DETAILS)) 1533 { 1534 fprintf (dump_file, " (evolution_function = "); 1535 print_generic_expr (dump_file, evolution_function, 0); 1536 fprintf (dump_file, "))\n"); 1537 } 1538 1539 return evolution_function; 1540 } 1541 1542 /* Given a loop-phi-node, return the initial conditions of the 1543 variable on entry of the loop. When the CCP has propagated 1544 constants into the loop-phi-node, the initial condition is 1545 instantiated, otherwise the initial condition is kept symbolic. 1546 This analyzer does not analyze the evolution outside the current 1547 loop, and leaves this task to the on-demand tree reconstructor. */ 1548 1549 static tree 1550 analyze_initial_condition (gimple loop_phi_node) 1551 { 1552 int i, n; 1553 tree init_cond = chrec_not_analyzed_yet; 1554 struct loop *loop = loop_containing_stmt (loop_phi_node); 1555 1556 if (dump_file && (dump_flags & TDF_DETAILS)) 1557 { 1558 fprintf (dump_file, "(analyze_initial_condition \n"); 1559 fprintf (dump_file, " (loop_phi_node = \n"); 1560 print_gimple_stmt (dump_file, loop_phi_node, 0, 0); 1561 fprintf (dump_file, ")\n"); 1562 } 1563 1564 n = gimple_phi_num_args (loop_phi_node); 1565 for (i = 0; i < n; i++) 1566 { 1567 tree branch = PHI_ARG_DEF (loop_phi_node, i); 1568 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src; 1569 1570 /* When the branch is oriented to the loop's body, it does 1571 not contribute to the initial condition. */ 1572 if (flow_bb_inside_loop_p (loop, bb)) 1573 continue; 1574 1575 if (init_cond == chrec_not_analyzed_yet) 1576 { 1577 init_cond = branch; 1578 continue; 1579 } 1580 1581 if (TREE_CODE (branch) == SSA_NAME) 1582 { 1583 init_cond = chrec_dont_know; 1584 break; 1585 } 1586 1587 init_cond = chrec_merge (init_cond, branch); 1588 } 1589 1590 /* Ooops -- a loop without an entry??? */ 1591 if (init_cond == chrec_not_analyzed_yet) 1592 init_cond = chrec_dont_know; 1593 1594 /* During early loop unrolling we do not have fully constant propagated IL. 1595 Handle degenerate PHIs here to not miss important unrollings. */ 1596 if (TREE_CODE (init_cond) == SSA_NAME) 1597 { 1598 gimple def = SSA_NAME_DEF_STMT (init_cond); 1599 tree res; 1600 if (gimple_code (def) == GIMPLE_PHI 1601 && (res = degenerate_phi_result (def)) != NULL_TREE 1602 /* Only allow invariants here, otherwise we may break 1603 loop-closed SSA form. */ 1604 && is_gimple_min_invariant (res)) 1605 init_cond = res; 1606 } 1607 1608 if (dump_file && (dump_flags & TDF_DETAILS)) 1609 { 1610 fprintf (dump_file, " (init_cond = "); 1611 print_generic_expr (dump_file, init_cond, 0); 1612 fprintf (dump_file, "))\n"); 1613 } 1614 1615 return init_cond; 1616 } 1617 1618 /* Analyze the scalar evolution for LOOP_PHI_NODE. */ 1619 1620 static tree 1621 interpret_loop_phi (struct loop *loop, gimple loop_phi_node) 1622 { 1623 tree res; 1624 struct loop *phi_loop = loop_containing_stmt (loop_phi_node); 1625 tree init_cond; 1626 1627 if (phi_loop != loop) 1628 { 1629 struct loop *subloop; 1630 tree evolution_fn = analyze_scalar_evolution 1631 (phi_loop, PHI_RESULT (loop_phi_node)); 1632 1633 /* Dive one level deeper. */ 1634 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1); 1635 1636 /* Interpret the subloop. */ 1637 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn); 1638 return res; 1639 } 1640 1641 /* Otherwise really interpret the loop phi. */ 1642 init_cond = analyze_initial_condition (loop_phi_node); 1643 res = analyze_evolution_in_loop (loop_phi_node, init_cond); 1644 1645 /* Verify we maintained the correct initial condition throughout 1646 possible conversions in the SSA chain. */ 1647 if (res != chrec_dont_know) 1648 { 1649 tree new_init = res; 1650 if (CONVERT_EXPR_P (res) 1651 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC) 1652 new_init = fold_convert (TREE_TYPE (res), 1653 CHREC_LEFT (TREE_OPERAND (res, 0))); 1654 else if (TREE_CODE (res) == POLYNOMIAL_CHREC) 1655 new_init = CHREC_LEFT (res); 1656 STRIP_USELESS_TYPE_CONVERSION (new_init); 1657 gcc_assert (TREE_CODE (new_init) != POLYNOMIAL_CHREC); 1658 if (!operand_equal_p (init_cond, new_init, 0)) 1659 return chrec_dont_know; 1660 } 1661 1662 return res; 1663 } 1664 1665 /* This function merges the branches of a condition-phi-node, 1666 contained in the outermost loop, and whose arguments are already 1667 analyzed. */ 1668 1669 static tree 1670 interpret_condition_phi (struct loop *loop, gimple condition_phi) 1671 { 1672 int i, n = gimple_phi_num_args (condition_phi); 1673 tree res = chrec_not_analyzed_yet; 1674 1675 for (i = 0; i < n; i++) 1676 { 1677 tree branch_chrec; 1678 1679 if (backedge_phi_arg_p (condition_phi, i)) 1680 { 1681 res = chrec_dont_know; 1682 break; 1683 } 1684 1685 branch_chrec = analyze_scalar_evolution 1686 (loop, PHI_ARG_DEF (condition_phi, i)); 1687 1688 res = chrec_merge (res, branch_chrec); 1689 } 1690 1691 return res; 1692 } 1693 1694 /* Interpret the operation RHS1 OP RHS2. If we didn't 1695 analyze this node before, follow the definitions until ending 1696 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the 1697 return path, this function propagates evolutions (ala constant copy 1698 propagation). OPND1 is not a GIMPLE expression because we could 1699 analyze the effect of an inner loop: see interpret_loop_phi. */ 1700 1701 static tree 1702 interpret_rhs_expr (struct loop *loop, gimple at_stmt, 1703 tree type, tree rhs1, enum tree_code code, tree rhs2) 1704 { 1705 tree res, chrec1, chrec2; 1706 1707 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) 1708 { 1709 if (is_gimple_min_invariant (rhs1)) 1710 return chrec_convert (type, rhs1, at_stmt); 1711 1712 if (code == SSA_NAME) 1713 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1), 1714 at_stmt); 1715 1716 if (code == ASSERT_EXPR) 1717 { 1718 rhs1 = ASSERT_EXPR_VAR (rhs1); 1719 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1), 1720 at_stmt); 1721 } 1722 1723 return chrec_dont_know; 1724 } 1725 1726 switch (code) 1727 { 1728 case POINTER_PLUS_EXPR: 1729 chrec1 = analyze_scalar_evolution (loop, rhs1); 1730 chrec2 = analyze_scalar_evolution (loop, rhs2); 1731 chrec1 = chrec_convert (type, chrec1, at_stmt); 1732 chrec2 = chrec_convert (sizetype, chrec2, at_stmt); 1733 res = chrec_fold_plus (type, chrec1, chrec2); 1734 break; 1735 1736 case PLUS_EXPR: 1737 chrec1 = analyze_scalar_evolution (loop, rhs1); 1738 chrec2 = analyze_scalar_evolution (loop, rhs2); 1739 chrec1 = chrec_convert (type, chrec1, at_stmt); 1740 chrec2 = chrec_convert (type, chrec2, at_stmt); 1741 res = chrec_fold_plus (type, chrec1, chrec2); 1742 break; 1743 1744 case MINUS_EXPR: 1745 chrec1 = analyze_scalar_evolution (loop, rhs1); 1746 chrec2 = analyze_scalar_evolution (loop, rhs2); 1747 chrec1 = chrec_convert (type, chrec1, at_stmt); 1748 chrec2 = chrec_convert (type, chrec2, at_stmt); 1749 res = chrec_fold_minus (type, chrec1, chrec2); 1750 break; 1751 1752 case NEGATE_EXPR: 1753 chrec1 = analyze_scalar_evolution (loop, rhs1); 1754 chrec1 = chrec_convert (type, chrec1, at_stmt); 1755 /* TYPE may be integer, real or complex, so use fold_convert. */ 1756 res = chrec_fold_multiply (type, chrec1, 1757 fold_convert (type, integer_minus_one_node)); 1758 break; 1759 1760 case BIT_NOT_EXPR: 1761 /* Handle ~X as -1 - X. */ 1762 chrec1 = analyze_scalar_evolution (loop, rhs1); 1763 chrec1 = chrec_convert (type, chrec1, at_stmt); 1764 res = chrec_fold_minus (type, 1765 fold_convert (type, integer_minus_one_node), 1766 chrec1); 1767 break; 1768 1769 case MULT_EXPR: 1770 chrec1 = analyze_scalar_evolution (loop, rhs1); 1771 chrec2 = analyze_scalar_evolution (loop, rhs2); 1772 chrec1 = chrec_convert (type, chrec1, at_stmt); 1773 chrec2 = chrec_convert (type, chrec2, at_stmt); 1774 res = chrec_fold_multiply (type, chrec1, chrec2); 1775 break; 1776 1777 CASE_CONVERT: 1778 chrec1 = analyze_scalar_evolution (loop, rhs1); 1779 res = chrec_convert (type, chrec1, at_stmt); 1780 break; 1781 1782 default: 1783 res = chrec_dont_know; 1784 break; 1785 } 1786 1787 return res; 1788 } 1789 1790 /* Interpret the expression EXPR. */ 1791 1792 static tree 1793 interpret_expr (struct loop *loop, gimple at_stmt, tree expr) 1794 { 1795 enum tree_code code; 1796 tree type = TREE_TYPE (expr), op0, op1; 1797 1798 if (automatically_generated_chrec_p (expr)) 1799 return expr; 1800 1801 if (TREE_CODE (expr) == POLYNOMIAL_CHREC) 1802 return chrec_dont_know; 1803 1804 extract_ops_from_tree (expr, &code, &op0, &op1); 1805 1806 return interpret_rhs_expr (loop, at_stmt, type, 1807 op0, code, op1); 1808 } 1809 1810 /* Interpret the rhs of the assignment STMT. */ 1811 1812 static tree 1813 interpret_gimple_assign (struct loop *loop, gimple stmt) 1814 { 1815 tree type = TREE_TYPE (gimple_assign_lhs (stmt)); 1816 enum tree_code code = gimple_assign_rhs_code (stmt); 1817 1818 return interpret_rhs_expr (loop, stmt, type, 1819 gimple_assign_rhs1 (stmt), code, 1820 gimple_assign_rhs2 (stmt)); 1821 } 1822 1823 1824 1825 /* This section contains all the entry points: 1826 - number_of_iterations_in_loop, 1827 - analyze_scalar_evolution, 1828 - instantiate_parameters. 1829 */ 1830 1831 /* Compute and return the evolution function in WRTO_LOOP, the nearest 1832 common ancestor of DEF_LOOP and USE_LOOP. */ 1833 1834 static tree 1835 compute_scalar_evolution_in_loop (struct loop *wrto_loop, 1836 struct loop *def_loop, 1837 tree ev) 1838 { 1839 tree res; 1840 if (def_loop == wrto_loop) 1841 return ev; 1842 1843 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1); 1844 res = compute_overall_effect_of_inner_loop (def_loop, ev); 1845 1846 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet); 1847 } 1848 1849 /* Helper recursive function. */ 1850 1851 static tree 1852 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) 1853 { 1854 tree type = TREE_TYPE (var); 1855 gimple def; 1856 basic_block bb; 1857 struct loop *def_loop; 1858 1859 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE) 1860 return chrec_dont_know; 1861 1862 if (TREE_CODE (var) != SSA_NAME) 1863 return interpret_expr (loop, NULL, var); 1864 1865 def = SSA_NAME_DEF_STMT (var); 1866 bb = gimple_bb (def); 1867 def_loop = bb ? bb->loop_father : NULL; 1868 1869 if (bb == NULL 1870 || !flow_bb_inside_loop_p (loop, bb)) 1871 { 1872 /* Keep the symbolic form. */ 1873 res = var; 1874 goto set_and_end; 1875 } 1876 1877 if (res != chrec_not_analyzed_yet) 1878 { 1879 if (loop != bb->loop_father) 1880 res = compute_scalar_evolution_in_loop 1881 (find_common_loop (loop, bb->loop_father), bb->loop_father, res); 1882 1883 goto set_and_end; 1884 } 1885 1886 if (loop != def_loop) 1887 { 1888 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet); 1889 res = compute_scalar_evolution_in_loop (loop, def_loop, res); 1890 1891 goto set_and_end; 1892 } 1893 1894 switch (gimple_code (def)) 1895 { 1896 case GIMPLE_ASSIGN: 1897 res = interpret_gimple_assign (loop, def); 1898 break; 1899 1900 case GIMPLE_PHI: 1901 if (loop_phi_node_p (def)) 1902 res = interpret_loop_phi (loop, def); 1903 else 1904 res = interpret_condition_phi (loop, def); 1905 break; 1906 1907 default: 1908 res = chrec_dont_know; 1909 break; 1910 } 1911 1912 set_and_end: 1913 1914 /* Keep the symbolic form. */ 1915 if (res == chrec_dont_know) 1916 res = var; 1917 1918 if (loop == def_loop) 1919 set_scalar_evolution (block_before_loop (loop), var, res); 1920 1921 return res; 1922 } 1923 1924 /* Analyzes and returns the scalar evolution of the ssa_name VAR in 1925 LOOP. LOOP is the loop in which the variable is used. 1926 1927 Example of use: having a pointer VAR to a SSA_NAME node, STMT a 1928 pointer to the statement that uses this variable, in order to 1929 determine the evolution function of the variable, use the following 1930 calls: 1931 1932 loop_p loop = loop_containing_stmt (stmt); 1933 tree chrec_with_symbols = analyze_scalar_evolution (loop, var); 1934 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols); 1935 */ 1936 1937 tree 1938 analyze_scalar_evolution (struct loop *loop, tree var) 1939 { 1940 tree res; 1941 1942 if (dump_file && (dump_flags & TDF_DETAILS)) 1943 { 1944 fprintf (dump_file, "(analyze_scalar_evolution \n"); 1945 fprintf (dump_file, " (loop_nb = %d)\n", loop->num); 1946 fprintf (dump_file, " (scalar = "); 1947 print_generic_expr (dump_file, var, 0); 1948 fprintf (dump_file, ")\n"); 1949 } 1950 1951 res = get_scalar_evolution (block_before_loop (loop), var); 1952 res = analyze_scalar_evolution_1 (loop, var, res); 1953 1954 if (dump_file && (dump_flags & TDF_DETAILS)) 1955 fprintf (dump_file, ")\n"); 1956 1957 return res; 1958 } 1959 1960 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to 1961 WRTO_LOOP (which should be a superloop of USE_LOOP) 1962 1963 FOLDED_CASTS is set to true if resolve_mixers used 1964 chrec_convert_aggressive (TODO -- not really, we are way too conservative 1965 at the moment in order to keep things simple). 1966 1967 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following 1968 example: 1969 1970 for (i = 0; i < 100; i++) -- loop 1 1971 { 1972 for (j = 0; j < 100; j++) -- loop 2 1973 { 1974 k1 = i; 1975 k2 = j; 1976 1977 use2 (k1, k2); 1978 1979 for (t = 0; t < 100; t++) -- loop 3 1980 use3 (k1, k2); 1981 1982 } 1983 use1 (k1, k2); 1984 } 1985 1986 Both k1 and k2 are invariants in loop3, thus 1987 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1 1988 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2 1989 1990 As they are invariant, it does not matter whether we consider their 1991 usage in loop 3 or loop 2, hence 1992 analyze_scalar_evolution_in_loop (loop2, loop3, k1) = 1993 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i 1994 analyze_scalar_evolution_in_loop (loop2, loop3, k2) = 1995 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2 1996 1997 Similarly for their evolutions with respect to loop 1. The values of K2 1998 in the use in loop 2 vary independently on loop 1, thus we cannot express 1999 the evolution with respect to loop 1: 2000 analyze_scalar_evolution_in_loop (loop1, loop3, k1) = 2001 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1 2002 analyze_scalar_evolution_in_loop (loop1, loop3, k2) = 2003 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know 2004 2005 The value of k2 in the use in loop 1 is known, though: 2006 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1 2007 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100 2008 */ 2009 2010 static tree 2011 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop, 2012 tree version, bool *folded_casts) 2013 { 2014 bool val = false; 2015 tree ev = version, tmp; 2016 2017 /* We cannot just do 2018 2019 tmp = analyze_scalar_evolution (use_loop, version); 2020 ev = resolve_mixers (wrto_loop, tmp); 2021 2022 as resolve_mixers would query the scalar evolution with respect to 2023 wrto_loop. For example, in the situation described in the function 2024 comment, suppose that wrto_loop = loop1, use_loop = loop3 and 2025 version = k2. Then 2026 2027 analyze_scalar_evolution (use_loop, version) = k2 2028 2029 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1 2030 is 100, which is a wrong result, since we are interested in the 2031 value in loop 3. 2032 2033 Instead, we need to proceed from use_loop to wrto_loop loop by loop, 2034 each time checking that there is no evolution in the inner loop. */ 2035 2036 if (folded_casts) 2037 *folded_casts = false; 2038 while (1) 2039 { 2040 tmp = analyze_scalar_evolution (use_loop, ev); 2041 ev = resolve_mixers (use_loop, tmp); 2042 2043 if (folded_casts && tmp != ev) 2044 *folded_casts = true; 2045 2046 if (use_loop == wrto_loop) 2047 return ev; 2048 2049 /* If the value of the use changes in the inner loop, we cannot express 2050 its value in the outer loop (we might try to return interval chrec, 2051 but we do not have a user for it anyway) */ 2052 if (!no_evolution_in_loop_p (ev, use_loop->num, &val) 2053 || !val) 2054 return chrec_dont_know; 2055 2056 use_loop = loop_outer (use_loop); 2057 } 2058 } 2059 2060 /* Returns from CACHE the value for VERSION instantiated below 2061 INSTANTIATED_BELOW block. */ 2062 2063 static tree 2064 get_instantiated_value (htab_t cache, basic_block instantiated_below, 2065 tree version) 2066 { 2067 struct scev_info_str *info, pattern; 2068 2069 pattern.var = version; 2070 pattern.instantiated_below = instantiated_below; 2071 info = (struct scev_info_str *) htab_find (cache, &pattern); 2072 2073 if (info) 2074 return info->chrec; 2075 else 2076 return NULL_TREE; 2077 } 2078 2079 /* Sets in CACHE the value of VERSION instantiated below basic block 2080 INSTANTIATED_BELOW to VAL. */ 2081 2082 static void 2083 set_instantiated_value (htab_t cache, basic_block instantiated_below, 2084 tree version, tree val) 2085 { 2086 struct scev_info_str *info, pattern; 2087 PTR *slot; 2088 2089 pattern.var = version; 2090 pattern.instantiated_below = instantiated_below; 2091 slot = htab_find_slot (cache, &pattern, INSERT); 2092 2093 if (!*slot) 2094 *slot = new_scev_info_str (instantiated_below, version); 2095 info = (struct scev_info_str *) *slot; 2096 info->chrec = val; 2097 } 2098 2099 /* Return the closed_loop_phi node for VAR. If there is none, return 2100 NULL_TREE. */ 2101 2102 static tree 2103 loop_closed_phi_def (tree var) 2104 { 2105 struct loop *loop; 2106 edge exit; 2107 gimple phi; 2108 gimple_stmt_iterator psi; 2109 2110 if (var == NULL_TREE 2111 || TREE_CODE (var) != SSA_NAME) 2112 return NULL_TREE; 2113 2114 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var)); 2115 exit = single_exit (loop); 2116 if (!exit) 2117 return NULL_TREE; 2118 2119 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi)) 2120 { 2121 phi = gsi_stmt (psi); 2122 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var) 2123 return PHI_RESULT (phi); 2124 } 2125 2126 return NULL_TREE; 2127 } 2128 2129 static tree instantiate_scev_r (basic_block, struct loop *, tree, bool, 2130 htab_t, int); 2131 2132 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW 2133 and EVOLUTION_LOOP, that were left under a symbolic form. 2134 2135 CHREC is an SSA_NAME to be instantiated. 2136 2137 CACHE is the cache of already instantiated values. 2138 2139 FOLD_CONVERSIONS should be set to true when the conversions that 2140 may wrap in signed/pointer type are folded, as long as the value of 2141 the chrec is preserved. 2142 2143 SIZE_EXPR is used for computing the size of the expression to be 2144 instantiated, and to stop if it exceeds some limit. */ 2145 2146 static tree 2147 instantiate_scev_name (basic_block instantiate_below, 2148 struct loop *evolution_loop, tree chrec, 2149 bool fold_conversions, htab_t cache, int size_expr) 2150 { 2151 tree res; 2152 struct loop *def_loop; 2153 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec)); 2154 2155 /* A parameter (or loop invariant and we do not want to include 2156 evolutions in outer loops), nothing to do. */ 2157 if (!def_bb 2158 || loop_depth (def_bb->loop_father) == 0 2159 || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb)) 2160 return chrec; 2161 2162 /* We cache the value of instantiated variable to avoid exponential 2163 time complexity due to reevaluations. We also store the convenient 2164 value in the cache in order to prevent infinite recursion -- we do 2165 not want to instantiate the SSA_NAME if it is in a mixer 2166 structure. This is used for avoiding the instantiation of 2167 recursively defined functions, such as: 2168 2169 | a_2 -> {0, +, 1, +, a_2}_1 */ 2170 2171 res = get_instantiated_value (cache, instantiate_below, chrec); 2172 if (res) 2173 return res; 2174 2175 res = chrec_dont_know; 2176 set_instantiated_value (cache, instantiate_below, chrec, res); 2177 2178 def_loop = find_common_loop (evolution_loop, def_bb->loop_father); 2179 2180 /* If the analysis yields a parametric chrec, instantiate the 2181 result again. */ 2182 res = analyze_scalar_evolution (def_loop, chrec); 2183 2184 /* Don't instantiate loop-closed-ssa phi nodes. */ 2185 if (TREE_CODE (res) == SSA_NAME 2186 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL 2187 || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res))) 2188 > loop_depth (def_loop)))) 2189 { 2190 if (res == chrec) 2191 res = loop_closed_phi_def (chrec); 2192 else 2193 res = chrec; 2194 2195 if (res == NULL_TREE 2196 || !dominated_by_p (CDI_DOMINATORS, instantiate_below, 2197 gimple_bb (SSA_NAME_DEF_STMT (res)))) 2198 res = chrec_dont_know; 2199 } 2200 2201 else if (res != chrec_dont_know) 2202 res = instantiate_scev_r (instantiate_below, evolution_loop, res, 2203 fold_conversions, cache, size_expr); 2204 2205 /* Store the correct value to the cache. */ 2206 set_instantiated_value (cache, instantiate_below, chrec, res); 2207 return res; 2208 2209 } 2210 2211 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW 2212 and EVOLUTION_LOOP, that were left under a symbolic form. 2213 2214 CHREC is a polynomial chain of recurrence to be instantiated. 2215 2216 CACHE is the cache of already instantiated values. 2217 2218 FOLD_CONVERSIONS should be set to true when the conversions that 2219 may wrap in signed/pointer type are folded, as long as the value of 2220 the chrec is preserved. 2221 2222 SIZE_EXPR is used for computing the size of the expression to be 2223 instantiated, and to stop if it exceeds some limit. */ 2224 2225 static tree 2226 instantiate_scev_poly (basic_block instantiate_below, 2227 struct loop *evolution_loop, tree chrec, 2228 bool fold_conversions, htab_t cache, int size_expr) 2229 { 2230 tree op1; 2231 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, 2232 CHREC_LEFT (chrec), fold_conversions, cache, 2233 size_expr); 2234 if (op0 == chrec_dont_know) 2235 return chrec_dont_know; 2236 2237 op1 = instantiate_scev_r (instantiate_below, evolution_loop, 2238 CHREC_RIGHT (chrec), fold_conversions, cache, 2239 size_expr); 2240 if (op1 == chrec_dont_know) 2241 return chrec_dont_know; 2242 2243 if (CHREC_LEFT (chrec) != op0 2244 || CHREC_RIGHT (chrec) != op1) 2245 { 2246 unsigned var = CHREC_VARIABLE (chrec); 2247 2248 /* When the instantiated stride or base has an evolution in an 2249 innermost loop, return chrec_dont_know, as this is not a 2250 valid SCEV representation. In the reduced testcase for 2251 PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no 2252 meaning. */ 2253 if ((tree_is_chrec (op0) && CHREC_VARIABLE (op0) > var) 2254 || (tree_is_chrec (op1) && CHREC_VARIABLE (op1) > var)) 2255 return chrec_dont_know; 2256 2257 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL); 2258 chrec = build_polynomial_chrec (var, op0, op1); 2259 } 2260 2261 return chrec; 2262 } 2263 2264 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW 2265 and EVOLUTION_LOOP, that were left under a symbolic form. 2266 2267 "C0 CODE C1" is a binary expression of type TYPE to be instantiated. 2268 2269 CACHE is the cache of already instantiated values. 2270 2271 FOLD_CONVERSIONS should be set to true when the conversions that 2272 may wrap in signed/pointer type are folded, as long as the value of 2273 the chrec is preserved. 2274 2275 SIZE_EXPR is used for computing the size of the expression to be 2276 instantiated, and to stop if it exceeds some limit. */ 2277 2278 static tree 2279 instantiate_scev_binary (basic_block instantiate_below, 2280 struct loop *evolution_loop, tree chrec, enum tree_code code, 2281 tree type, tree c0, tree c1, 2282 bool fold_conversions, htab_t cache, int size_expr) 2283 { 2284 tree op1; 2285 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, 2286 c0, fold_conversions, cache, 2287 size_expr); 2288 if (op0 == chrec_dont_know) 2289 return chrec_dont_know; 2290 2291 op1 = instantiate_scev_r (instantiate_below, evolution_loop, 2292 c1, fold_conversions, cache, 2293 size_expr); 2294 if (op1 == chrec_dont_know) 2295 return chrec_dont_know; 2296 2297 if (c0 != op0 2298 || c1 != op1) 2299 { 2300 op0 = chrec_convert (type, op0, NULL); 2301 op1 = chrec_convert_rhs (type, op1, NULL); 2302 2303 switch (code) 2304 { 2305 case POINTER_PLUS_EXPR: 2306 case PLUS_EXPR: 2307 return chrec_fold_plus (type, op0, op1); 2308 2309 case MINUS_EXPR: 2310 return chrec_fold_minus (type, op0, op1); 2311 2312 case MULT_EXPR: 2313 return chrec_fold_multiply (type, op0, op1); 2314 2315 default: 2316 gcc_unreachable (); 2317 } 2318 } 2319 2320 return chrec ? chrec : fold_build2 (code, type, c0, c1); 2321 } 2322 2323 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW 2324 and EVOLUTION_LOOP, that were left under a symbolic form. 2325 2326 "CHREC" that stands for a convert expression "(TYPE) OP" is to be 2327 instantiated. 2328 2329 CACHE is the cache of already instantiated values. 2330 2331 FOLD_CONVERSIONS should be set to true when the conversions that 2332 may wrap in signed/pointer type are folded, as long as the value of 2333 the chrec is preserved. 2334 2335 SIZE_EXPR is used for computing the size of the expression to be 2336 instantiated, and to stop if it exceeds some limit. */ 2337 2338 static tree 2339 instantiate_scev_convert (basic_block instantiate_below, 2340 struct loop *evolution_loop, tree chrec, 2341 tree type, tree op, 2342 bool fold_conversions, htab_t cache, int size_expr) 2343 { 2344 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op, 2345 fold_conversions, cache, size_expr); 2346 2347 if (op0 == chrec_dont_know) 2348 return chrec_dont_know; 2349 2350 if (fold_conversions) 2351 { 2352 tree tmp = chrec_convert_aggressive (type, op0); 2353 if (tmp) 2354 return tmp; 2355 } 2356 2357 if (chrec && op0 == op) 2358 return chrec; 2359 2360 /* If we used chrec_convert_aggressive, we can no longer assume that 2361 signed chrecs do not overflow, as chrec_convert does, so avoid 2362 calling it in that case. */ 2363 if (fold_conversions) 2364 return fold_convert (type, op0); 2365 2366 return chrec_convert (type, op0, NULL); 2367 } 2368 2369 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW 2370 and EVOLUTION_LOOP, that were left under a symbolic form. 2371 2372 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated. 2373 Handle ~X as -1 - X. 2374 Handle -X as -1 * X. 2375 2376 CACHE is the cache of already instantiated values. 2377 2378 FOLD_CONVERSIONS should be set to true when the conversions that 2379 may wrap in signed/pointer type are folded, as long as the value of 2380 the chrec is preserved. 2381 2382 SIZE_EXPR is used for computing the size of the expression to be 2383 instantiated, and to stop if it exceeds some limit. */ 2384 2385 static tree 2386 instantiate_scev_not (basic_block instantiate_below, 2387 struct loop *evolution_loop, tree chrec, 2388 enum tree_code code, tree type, tree op, 2389 bool fold_conversions, htab_t cache, int size_expr) 2390 { 2391 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op, 2392 fold_conversions, cache, size_expr); 2393 2394 if (op0 == chrec_dont_know) 2395 return chrec_dont_know; 2396 2397 if (op != op0) 2398 { 2399 op0 = chrec_convert (type, op0, NULL); 2400 2401 switch (code) 2402 { 2403 case BIT_NOT_EXPR: 2404 return chrec_fold_minus 2405 (type, fold_convert (type, integer_minus_one_node), op0); 2406 2407 case NEGATE_EXPR: 2408 return chrec_fold_multiply 2409 (type, fold_convert (type, integer_minus_one_node), op0); 2410 2411 default: 2412 gcc_unreachable (); 2413 } 2414 } 2415 2416 return chrec ? chrec : fold_build1 (code, type, op0); 2417 } 2418 2419 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW 2420 and EVOLUTION_LOOP, that were left under a symbolic form. 2421 2422 CHREC is an expression with 3 operands to be instantiated. 2423 2424 CACHE is the cache of already instantiated values. 2425 2426 FOLD_CONVERSIONS should be set to true when the conversions that 2427 may wrap in signed/pointer type are folded, as long as the value of 2428 the chrec is preserved. 2429 2430 SIZE_EXPR is used for computing the size of the expression to be 2431 instantiated, and to stop if it exceeds some limit. */ 2432 2433 static tree 2434 instantiate_scev_3 (basic_block instantiate_below, 2435 struct loop *evolution_loop, tree chrec, 2436 bool fold_conversions, htab_t cache, int size_expr) 2437 { 2438 tree op1, op2; 2439 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, 2440 TREE_OPERAND (chrec, 0), 2441 fold_conversions, cache, size_expr); 2442 if (op0 == chrec_dont_know) 2443 return chrec_dont_know; 2444 2445 op1 = instantiate_scev_r (instantiate_below, evolution_loop, 2446 TREE_OPERAND (chrec, 1), 2447 fold_conversions, cache, size_expr); 2448 if (op1 == chrec_dont_know) 2449 return chrec_dont_know; 2450 2451 op2 = instantiate_scev_r (instantiate_below, evolution_loop, 2452 TREE_OPERAND (chrec, 2), 2453 fold_conversions, cache, size_expr); 2454 if (op2 == chrec_dont_know) 2455 return chrec_dont_know; 2456 2457 if (op0 == TREE_OPERAND (chrec, 0) 2458 && op1 == TREE_OPERAND (chrec, 1) 2459 && op2 == TREE_OPERAND (chrec, 2)) 2460 return chrec; 2461 2462 return fold_build3 (TREE_CODE (chrec), 2463 TREE_TYPE (chrec), op0, op1, op2); 2464 } 2465 2466 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW 2467 and EVOLUTION_LOOP, that were left under a symbolic form. 2468 2469 CHREC is an expression with 2 operands to be instantiated. 2470 2471 CACHE is the cache of already instantiated values. 2472 2473 FOLD_CONVERSIONS should be set to true when the conversions that 2474 may wrap in signed/pointer type are folded, as long as the value of 2475 the chrec is preserved. 2476 2477 SIZE_EXPR is used for computing the size of the expression to be 2478 instantiated, and to stop if it exceeds some limit. */ 2479 2480 static tree 2481 instantiate_scev_2 (basic_block instantiate_below, 2482 struct loop *evolution_loop, tree chrec, 2483 bool fold_conversions, htab_t cache, int size_expr) 2484 { 2485 tree op1; 2486 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, 2487 TREE_OPERAND (chrec, 0), 2488 fold_conversions, cache, size_expr); 2489 if (op0 == chrec_dont_know) 2490 return chrec_dont_know; 2491 2492 op1 = instantiate_scev_r (instantiate_below, evolution_loop, 2493 TREE_OPERAND (chrec, 1), 2494 fold_conversions, cache, size_expr); 2495 if (op1 == chrec_dont_know) 2496 return chrec_dont_know; 2497 2498 if (op0 == TREE_OPERAND (chrec, 0) 2499 && op1 == TREE_OPERAND (chrec, 1)) 2500 return chrec; 2501 2502 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); 2503 } 2504 2505 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW 2506 and EVOLUTION_LOOP, that were left under a symbolic form. 2507 2508 CHREC is an expression with 2 operands to be instantiated. 2509 2510 CACHE is the cache of already instantiated values. 2511 2512 FOLD_CONVERSIONS should be set to true when the conversions that 2513 may wrap in signed/pointer type are folded, as long as the value of 2514 the chrec is preserved. 2515 2516 SIZE_EXPR is used for computing the size of the expression to be 2517 instantiated, and to stop if it exceeds some limit. */ 2518 2519 static tree 2520 instantiate_scev_1 (basic_block instantiate_below, 2521 struct loop *evolution_loop, tree chrec, 2522 bool fold_conversions, htab_t cache, int size_expr) 2523 { 2524 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, 2525 TREE_OPERAND (chrec, 0), 2526 fold_conversions, cache, size_expr); 2527 2528 if (op0 == chrec_dont_know) 2529 return chrec_dont_know; 2530 2531 if (op0 == TREE_OPERAND (chrec, 0)) 2532 return chrec; 2533 2534 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0); 2535 } 2536 2537 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW 2538 and EVOLUTION_LOOP, that were left under a symbolic form. 2539 2540 CHREC is the scalar evolution to instantiate. 2541 2542 CACHE is the cache of already instantiated values. 2543 2544 FOLD_CONVERSIONS should be set to true when the conversions that 2545 may wrap in signed/pointer type are folded, as long as the value of 2546 the chrec is preserved. 2547 2548 SIZE_EXPR is used for computing the size of the expression to be 2549 instantiated, and to stop if it exceeds some limit. */ 2550 2551 static tree 2552 instantiate_scev_r (basic_block instantiate_below, 2553 struct loop *evolution_loop, tree chrec, 2554 bool fold_conversions, htab_t cache, int size_expr) 2555 { 2556 /* Give up if the expression is larger than the MAX that we allow. */ 2557 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 2558 return chrec_dont_know; 2559 2560 if (chrec == NULL_TREE 2561 || automatically_generated_chrec_p (chrec) 2562 || is_gimple_min_invariant (chrec)) 2563 return chrec; 2564 2565 switch (TREE_CODE (chrec)) 2566 { 2567 case SSA_NAME: 2568 return instantiate_scev_name (instantiate_below, evolution_loop, chrec, 2569 fold_conversions, cache, size_expr); 2570 2571 case POLYNOMIAL_CHREC: 2572 return instantiate_scev_poly (instantiate_below, evolution_loop, chrec, 2573 fold_conversions, cache, size_expr); 2574 2575 case POINTER_PLUS_EXPR: 2576 case PLUS_EXPR: 2577 case MINUS_EXPR: 2578 case MULT_EXPR: 2579 return instantiate_scev_binary (instantiate_below, evolution_loop, chrec, 2580 TREE_CODE (chrec), chrec_type (chrec), 2581 TREE_OPERAND (chrec, 0), 2582 TREE_OPERAND (chrec, 1), 2583 fold_conversions, cache, size_expr); 2584 2585 CASE_CONVERT: 2586 return instantiate_scev_convert (instantiate_below, evolution_loop, chrec, 2587 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0), 2588 fold_conversions, cache, size_expr); 2589 2590 case NEGATE_EXPR: 2591 case BIT_NOT_EXPR: 2592 return instantiate_scev_not (instantiate_below, evolution_loop, chrec, 2593 TREE_CODE (chrec), TREE_TYPE (chrec), 2594 TREE_OPERAND (chrec, 0), 2595 fold_conversions, cache, size_expr); 2596 2597 case SCEV_NOT_KNOWN: 2598 return chrec_dont_know; 2599 2600 case SCEV_KNOWN: 2601 return chrec_known; 2602 2603 default: 2604 break; 2605 } 2606 2607 if (VL_EXP_CLASS_P (chrec)) 2608 return chrec_dont_know; 2609 2610 switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 2611 { 2612 case 3: 2613 return instantiate_scev_3 (instantiate_below, evolution_loop, chrec, 2614 fold_conversions, cache, size_expr); 2615 2616 case 2: 2617 return instantiate_scev_2 (instantiate_below, evolution_loop, chrec, 2618 fold_conversions, cache, size_expr); 2619 2620 case 1: 2621 return instantiate_scev_1 (instantiate_below, evolution_loop, chrec, 2622 fold_conversions, cache, size_expr); 2623 2624 case 0: 2625 return chrec; 2626 2627 default: 2628 break; 2629 } 2630 2631 /* Too complicated to handle. */ 2632 return chrec_dont_know; 2633 } 2634 2635 /* Analyze all the parameters of the chrec that were left under a 2636 symbolic form. INSTANTIATE_BELOW is the basic block that stops the 2637 recursive instantiation of parameters: a parameter is a variable 2638 that is defined in a basic block that dominates INSTANTIATE_BELOW or 2639 a function parameter. */ 2640 2641 tree 2642 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop, 2643 tree chrec) 2644 { 2645 tree res; 2646 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); 2647 2648 if (dump_file && (dump_flags & TDF_DETAILS)) 2649 { 2650 fprintf (dump_file, "(instantiate_scev \n"); 2651 fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index); 2652 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num); 2653 fprintf (dump_file, " (chrec = "); 2654 print_generic_expr (dump_file, chrec, 0); 2655 fprintf (dump_file, ")\n"); 2656 } 2657 2658 res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false, 2659 cache, 0); 2660 2661 if (dump_file && (dump_flags & TDF_DETAILS)) 2662 { 2663 fprintf (dump_file, " (res = "); 2664 print_generic_expr (dump_file, res, 0); 2665 fprintf (dump_file, "))\n"); 2666 } 2667 2668 htab_delete (cache); 2669 2670 return res; 2671 } 2672 2673 /* Similar to instantiate_parameters, but does not introduce the 2674 evolutions in outer loops for LOOP invariants in CHREC, and does not 2675 care about causing overflows, as long as they do not affect value 2676 of an expression. */ 2677 2678 tree 2679 resolve_mixers (struct loop *loop, tree chrec) 2680 { 2681 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); 2682 tree ret = instantiate_scev_r (block_before_loop (loop), loop, chrec, true, 2683 cache, 0); 2684 htab_delete (cache); 2685 return ret; 2686 } 2687 2688 /* Entry point for the analysis of the number of iterations pass. 2689 This function tries to safely approximate the number of iterations 2690 the loop will run. When this property is not decidable at compile 2691 time, the result is chrec_dont_know. Otherwise the result is 2692 a scalar or a symbolic parameter. 2693 2694 Example of analysis: suppose that the loop has an exit condition: 2695 2696 "if (b > 49) goto end_loop;" 2697 2698 and that in a previous analysis we have determined that the 2699 variable 'b' has an evolution function: 2700 2701 "EF = {23, +, 5}_2". 2702 2703 When we evaluate the function at the point 5, i.e. the value of the 2704 variable 'b' after 5 iterations in the loop, we have EF (5) = 48, 2705 and EF (6) = 53. In this case the value of 'b' on exit is '53' and 2706 the loop body has been executed 6 times. */ 2707 2708 tree 2709 number_of_latch_executions (struct loop *loop) 2710 { 2711 tree res, type; 2712 edge exit; 2713 struct tree_niter_desc niter_desc; 2714 2715 /* Determine whether the number_of_iterations_in_loop has already 2716 been computed. */ 2717 res = loop->nb_iterations; 2718 if (res) 2719 return res; 2720 res = chrec_dont_know; 2721 2722 if (dump_file && (dump_flags & TDF_DETAILS)) 2723 fprintf (dump_file, "(number_of_iterations_in_loop\n"); 2724 2725 exit = single_exit (loop); 2726 if (!exit) 2727 goto end; 2728 2729 if (!number_of_iterations_exit (loop, exit, &niter_desc, false)) 2730 goto end; 2731 2732 type = TREE_TYPE (niter_desc.niter); 2733 if (integer_nonzerop (niter_desc.may_be_zero)) 2734 res = build_int_cst (type, 0); 2735 else if (integer_zerop (niter_desc.may_be_zero)) 2736 res = niter_desc.niter; 2737 else 2738 res = chrec_dont_know; 2739 2740 end: 2741 return set_nb_iterations_in_loop (loop, res); 2742 } 2743 2744 /* Returns the number of executions of the exit condition of LOOP, 2745 i.e., the number by one higher than number_of_latch_executions. 2746 Note that unlike number_of_latch_executions, this number does 2747 not necessarily fit in the unsigned variant of the type of 2748 the control variable -- if the number of iterations is a constant, 2749 we return chrec_dont_know if adding one to number_of_latch_executions 2750 overflows; however, in case the number of iterations is symbolic 2751 expression, the caller is responsible for dealing with this 2752 the possible overflow. */ 2753 2754 tree 2755 number_of_exit_cond_executions (struct loop *loop) 2756 { 2757 tree ret = number_of_latch_executions (loop); 2758 tree type = chrec_type (ret); 2759 2760 if (chrec_contains_undetermined (ret)) 2761 return ret; 2762 2763 ret = chrec_fold_plus (type, ret, build_int_cst (type, 1)); 2764 if (TREE_CODE (ret) == INTEGER_CST 2765 && TREE_OVERFLOW (ret)) 2766 return chrec_dont_know; 2767 2768 return ret; 2769 } 2770 2771 /* One of the drivers for testing the scalar evolutions analysis. 2772 This function computes the number of iterations for all the loops 2773 from the EXIT_CONDITIONS array. */ 2774 2775 static void 2776 number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions) 2777 { 2778 unsigned int i; 2779 unsigned nb_chrec_dont_know_loops = 0; 2780 unsigned nb_static_loops = 0; 2781 gimple cond; 2782 2783 for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++) 2784 { 2785 tree res = number_of_latch_executions (loop_containing_stmt (cond)); 2786 if (chrec_contains_undetermined (res)) 2787 nb_chrec_dont_know_loops++; 2788 else 2789 nb_static_loops++; 2790 } 2791 2792 if (dump_file) 2793 { 2794 fprintf (dump_file, "\n(\n"); 2795 fprintf (dump_file, "-----------------------------------------\n"); 2796 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops); 2797 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops); 2798 fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ()); 2799 fprintf (dump_file, "-----------------------------------------\n"); 2800 fprintf (dump_file, ")\n\n"); 2801 2802 print_loops (dump_file, 3); 2803 } 2804 } 2805 2806 2807 2808 /* Counters for the stats. */ 2809 2810 struct chrec_stats 2811 { 2812 unsigned nb_chrecs; 2813 unsigned nb_affine; 2814 unsigned nb_affine_multivar; 2815 unsigned nb_higher_poly; 2816 unsigned nb_chrec_dont_know; 2817 unsigned nb_undetermined; 2818 }; 2819 2820 /* Reset the counters. */ 2821 2822 static inline void 2823 reset_chrecs_counters (struct chrec_stats *stats) 2824 { 2825 stats->nb_chrecs = 0; 2826 stats->nb_affine = 0; 2827 stats->nb_affine_multivar = 0; 2828 stats->nb_higher_poly = 0; 2829 stats->nb_chrec_dont_know = 0; 2830 stats->nb_undetermined = 0; 2831 } 2832 2833 /* Dump the contents of a CHREC_STATS structure. */ 2834 2835 static void 2836 dump_chrecs_stats (FILE *file, struct chrec_stats *stats) 2837 { 2838 fprintf (file, "\n(\n"); 2839 fprintf (file, "-----------------------------------------\n"); 2840 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine); 2841 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar); 2842 fprintf (file, "%d\tdegree greater than 2 polynomials\n", 2843 stats->nb_higher_poly); 2844 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know); 2845 fprintf (file, "-----------------------------------------\n"); 2846 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs); 2847 fprintf (file, "%d\twith undetermined coefficients\n", 2848 stats->nb_undetermined); 2849 fprintf (file, "-----------------------------------------\n"); 2850 fprintf (file, "%d\tchrecs in the scev database\n", 2851 (int) htab_elements (scalar_evolution_info)); 2852 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev); 2853 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev); 2854 fprintf (file, "-----------------------------------------\n"); 2855 fprintf (file, ")\n\n"); 2856 } 2857 2858 /* Gather statistics about CHREC. */ 2859 2860 static void 2861 gather_chrec_stats (tree chrec, struct chrec_stats *stats) 2862 { 2863 if (dump_file && (dump_flags & TDF_STATS)) 2864 { 2865 fprintf (dump_file, "(classify_chrec "); 2866 print_generic_expr (dump_file, chrec, 0); 2867 fprintf (dump_file, "\n"); 2868 } 2869 2870 stats->nb_chrecs++; 2871 2872 if (chrec == NULL_TREE) 2873 { 2874 stats->nb_undetermined++; 2875 return; 2876 } 2877 2878 switch (TREE_CODE (chrec)) 2879 { 2880 case POLYNOMIAL_CHREC: 2881 if (evolution_function_is_affine_p (chrec)) 2882 { 2883 if (dump_file && (dump_flags & TDF_STATS)) 2884 fprintf (dump_file, " affine_univariate\n"); 2885 stats->nb_affine++; 2886 } 2887 else if (evolution_function_is_affine_multivariate_p (chrec, 0)) 2888 { 2889 if (dump_file && (dump_flags & TDF_STATS)) 2890 fprintf (dump_file, " affine_multivariate\n"); 2891 stats->nb_affine_multivar++; 2892 } 2893 else 2894 { 2895 if (dump_file && (dump_flags & TDF_STATS)) 2896 fprintf (dump_file, " higher_degree_polynomial\n"); 2897 stats->nb_higher_poly++; 2898 } 2899 2900 break; 2901 2902 default: 2903 break; 2904 } 2905 2906 if (chrec_contains_undetermined (chrec)) 2907 { 2908 if (dump_file && (dump_flags & TDF_STATS)) 2909 fprintf (dump_file, " undetermined\n"); 2910 stats->nb_undetermined++; 2911 } 2912 2913 if (dump_file && (dump_flags & TDF_STATS)) 2914 fprintf (dump_file, ")\n"); 2915 } 2916 2917 /* One of the drivers for testing the scalar evolutions analysis. 2918 This function analyzes the scalar evolution of all the scalars 2919 defined as loop phi nodes in one of the loops from the 2920 EXIT_CONDITIONS array. 2921 2922 TODO Optimization: A loop is in canonical form if it contains only 2923 a single scalar loop phi node. All the other scalars that have an 2924 evolution in the loop are rewritten in function of this single 2925 index. This allows the parallelization of the loop. */ 2926 2927 static void 2928 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple,heap) **exit_conditions) 2929 { 2930 unsigned int i; 2931 struct chrec_stats stats; 2932 gimple cond, phi; 2933 gimple_stmt_iterator psi; 2934 2935 reset_chrecs_counters (&stats); 2936 2937 for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++) 2938 { 2939 struct loop *loop; 2940 basic_block bb; 2941 tree chrec; 2942 2943 loop = loop_containing_stmt (cond); 2944 bb = loop->header; 2945 2946 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) 2947 { 2948 phi = gsi_stmt (psi); 2949 if (is_gimple_reg (PHI_RESULT (phi))) 2950 { 2951 chrec = instantiate_parameters 2952 (loop, 2953 analyze_scalar_evolution (loop, PHI_RESULT (phi))); 2954 2955 if (dump_file && (dump_flags & TDF_STATS)) 2956 gather_chrec_stats (chrec, &stats); 2957 } 2958 } 2959 } 2960 2961 if (dump_file && (dump_flags & TDF_STATS)) 2962 dump_chrecs_stats (dump_file, &stats); 2963 } 2964 2965 /* Callback for htab_traverse, gathers information on chrecs in the 2966 hashtable. */ 2967 2968 static int 2969 gather_stats_on_scev_database_1 (void **slot, void *stats) 2970 { 2971 struct scev_info_str *entry = (struct scev_info_str *) *slot; 2972 2973 gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats); 2974 2975 return 1; 2976 } 2977 2978 /* Classify the chrecs of the whole database. */ 2979 2980 void 2981 gather_stats_on_scev_database (void) 2982 { 2983 struct chrec_stats stats; 2984 2985 if (!dump_file) 2986 return; 2987 2988 reset_chrecs_counters (&stats); 2989 2990 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1, 2991 &stats); 2992 2993 dump_chrecs_stats (dump_file, &stats); 2994 } 2995 2996 2997 2998 /* Initializer. */ 2999 3000 static void 3001 initialize_scalar_evolutions_analyzer (void) 3002 { 3003 /* The elements below are unique. */ 3004 if (chrec_dont_know == NULL_TREE) 3005 { 3006 chrec_not_analyzed_yet = NULL_TREE; 3007 chrec_dont_know = make_node (SCEV_NOT_KNOWN); 3008 chrec_known = make_node (SCEV_KNOWN); 3009 TREE_TYPE (chrec_dont_know) = void_type_node; 3010 TREE_TYPE (chrec_known) = void_type_node; 3011 } 3012 } 3013 3014 /* Initialize the analysis of scalar evolutions for LOOPS. */ 3015 3016 void 3017 scev_initialize (void) 3018 { 3019 loop_iterator li; 3020 struct loop *loop; 3021 3022 scalar_evolution_info = htab_create_alloc (100, 3023 hash_scev_info, 3024 eq_scev_info, 3025 del_scev_info, 3026 ggc_calloc, 3027 ggc_free); 3028 3029 initialize_scalar_evolutions_analyzer (); 3030 3031 FOR_EACH_LOOP (li, loop, 0) 3032 { 3033 loop->nb_iterations = NULL_TREE; 3034 } 3035 } 3036 3037 /* Cleans up the information cached by the scalar evolutions analysis 3038 in the hash table. */ 3039 3040 void 3041 scev_reset_htab (void) 3042 { 3043 if (!scalar_evolution_info) 3044 return; 3045 3046 htab_empty (scalar_evolution_info); 3047 } 3048 3049 /* Cleans up the information cached by the scalar evolutions analysis 3050 in the hash table and in the loop->nb_iterations. */ 3051 3052 void 3053 scev_reset (void) 3054 { 3055 loop_iterator li; 3056 struct loop *loop; 3057 3058 scev_reset_htab (); 3059 3060 if (!current_loops) 3061 return; 3062 3063 FOR_EACH_LOOP (li, loop, 0) 3064 { 3065 loop->nb_iterations = NULL_TREE; 3066 } 3067 } 3068 3069 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with 3070 respect to WRTO_LOOP and returns its base and step in IV if possible 3071 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP 3072 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be 3073 invariant in LOOP. Otherwise we require it to be an integer constant. 3074 3075 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g. 3076 because it is computed in signed arithmetics). Consequently, adding an 3077 induction variable 3078 3079 for (i = IV->base; ; i += IV->step) 3080 3081 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is 3082 false for the type of the induction variable, or you can prove that i does 3083 not wrap by some other argument. Otherwise, this might introduce undefined 3084 behavior, and 3085 3086 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step)) 3087 3088 must be used instead. */ 3089 3090 bool 3091 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, 3092 affine_iv *iv, bool allow_nonconstant_step) 3093 { 3094 tree type, ev; 3095 bool folded_casts; 3096 3097 iv->base = NULL_TREE; 3098 iv->step = NULL_TREE; 3099 iv->no_overflow = false; 3100 3101 type = TREE_TYPE (op); 3102 if (TREE_CODE (type) != INTEGER_TYPE 3103 && TREE_CODE (type) != POINTER_TYPE) 3104 return false; 3105 3106 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op, 3107 &folded_casts); 3108 if (chrec_contains_undetermined (ev) 3109 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num)) 3110 return false; 3111 3112 if (tree_does_not_contain_chrecs (ev)) 3113 { 3114 iv->base = ev; 3115 iv->step = build_int_cst (TREE_TYPE (ev), 0); 3116 iv->no_overflow = true; 3117 return true; 3118 } 3119 3120 if (TREE_CODE (ev) != POLYNOMIAL_CHREC 3121 || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num) 3122 return false; 3123 3124 iv->step = CHREC_RIGHT (ev); 3125 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST) 3126 || tree_contains_chrecs (iv->step, NULL)) 3127 return false; 3128 3129 iv->base = CHREC_LEFT (ev); 3130 if (tree_contains_chrecs (iv->base, NULL)) 3131 return false; 3132 3133 iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type); 3134 3135 return true; 3136 } 3137 3138 /* Runs the analysis of scalar evolutions. */ 3139 3140 void 3141 scev_analysis (void) 3142 { 3143 VEC(gimple,heap) *exit_conditions; 3144 3145 exit_conditions = VEC_alloc (gimple, heap, 37); 3146 select_loops_exit_conditions (&exit_conditions); 3147 3148 if (dump_file && (dump_flags & TDF_STATS)) 3149 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions); 3150 3151 number_of_iterations_for_all_loops (&exit_conditions); 3152 VEC_free (gimple, heap, exit_conditions); 3153 } 3154 3155 /* Finalize the scalar evolution analysis. */ 3156 3157 void 3158 scev_finalize (void) 3159 { 3160 if (!scalar_evolution_info) 3161 return; 3162 htab_delete (scalar_evolution_info); 3163 scalar_evolution_info = NULL; 3164 } 3165 3166 /* Returns true if the expression EXPR is considered to be too expensive 3167 for scev_const_prop. */ 3168 3169 bool 3170 expression_expensive_p (tree expr) 3171 { 3172 enum tree_code code; 3173 3174 if (is_gimple_val (expr)) 3175 return false; 3176 3177 code = TREE_CODE (expr); 3178 if (code == TRUNC_DIV_EXPR 3179 || code == CEIL_DIV_EXPR 3180 || code == FLOOR_DIV_EXPR 3181 || code == ROUND_DIV_EXPR 3182 || code == TRUNC_MOD_EXPR 3183 || code == CEIL_MOD_EXPR 3184 || code == FLOOR_MOD_EXPR 3185 || code == ROUND_MOD_EXPR 3186 || code == EXACT_DIV_EXPR) 3187 { 3188 /* Division by power of two is usually cheap, so we allow it. 3189 Forbid anything else. */ 3190 if (!integer_pow2p (TREE_OPERAND (expr, 1))) 3191 return true; 3192 } 3193 3194 switch (TREE_CODE_CLASS (code)) 3195 { 3196 case tcc_binary: 3197 case tcc_comparison: 3198 if (expression_expensive_p (TREE_OPERAND (expr, 1))) 3199 return true; 3200 3201 /* Fallthru. */ 3202 case tcc_unary: 3203 return expression_expensive_p (TREE_OPERAND (expr, 0)); 3204 3205 default: 3206 return true; 3207 } 3208 } 3209 3210 /* Replace ssa names for that scev can prove they are constant by the 3211 appropriate constants. Also perform final value replacement in loops, 3212 in case the replacement expressions are cheap. 3213 3214 We only consider SSA names defined by phi nodes; rest is left to the 3215 ordinary constant propagation pass. */ 3216 3217 unsigned int 3218 scev_const_prop (void) 3219 { 3220 basic_block bb; 3221 tree name, type, ev; 3222 gimple phi, ass; 3223 struct loop *loop, *ex_loop; 3224 bitmap ssa_names_to_remove = NULL; 3225 unsigned i; 3226 loop_iterator li; 3227 gimple_stmt_iterator psi; 3228 3229 if (number_of_loops () <= 1) 3230 return 0; 3231 3232 FOR_EACH_BB (bb) 3233 { 3234 loop = bb->loop_father; 3235 3236 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) 3237 { 3238 phi = gsi_stmt (psi); 3239 name = PHI_RESULT (phi); 3240 3241 if (!is_gimple_reg (name)) 3242 continue; 3243 3244 type = TREE_TYPE (name); 3245 3246 if (!POINTER_TYPE_P (type) 3247 && !INTEGRAL_TYPE_P (type)) 3248 continue; 3249 3250 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name)); 3251 if (!is_gimple_min_invariant (ev) 3252 || !may_propagate_copy (name, ev)) 3253 continue; 3254 3255 /* Replace the uses of the name. */ 3256 if (name != ev) 3257 replace_uses_by (name, ev); 3258 3259 if (!ssa_names_to_remove) 3260 ssa_names_to_remove = BITMAP_ALLOC (NULL); 3261 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name)); 3262 } 3263 } 3264 3265 /* Remove the ssa names that were replaced by constants. We do not 3266 remove them directly in the previous cycle, since this 3267 invalidates scev cache. */ 3268 if (ssa_names_to_remove) 3269 { 3270 bitmap_iterator bi; 3271 3272 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi) 3273 { 3274 gimple_stmt_iterator psi; 3275 name = ssa_name (i); 3276 phi = SSA_NAME_DEF_STMT (name); 3277 3278 gcc_assert (gimple_code (phi) == GIMPLE_PHI); 3279 psi = gsi_for_stmt (phi); 3280 remove_phi_node (&psi, true); 3281 } 3282 3283 BITMAP_FREE (ssa_names_to_remove); 3284 scev_reset (); 3285 } 3286 3287 /* Now the regular final value replacement. */ 3288 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) 3289 { 3290 edge exit; 3291 tree def, rslt, niter; 3292 gimple_stmt_iterator bsi; 3293 3294 /* If we do not know exact number of iterations of the loop, we cannot 3295 replace the final value. */ 3296 exit = single_exit (loop); 3297 if (!exit) 3298 continue; 3299 3300 niter = number_of_latch_executions (loop); 3301 if (niter == chrec_dont_know) 3302 continue; 3303 3304 /* Ensure that it is possible to insert new statements somewhere. */ 3305 if (!single_pred_p (exit->dest)) 3306 split_loop_exit_edge (exit); 3307 bsi = gsi_after_labels (exit->dest); 3308 3309 ex_loop = superloop_at_depth (loop, 3310 loop_depth (exit->dest->loop_father) + 1); 3311 3312 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); ) 3313 { 3314 phi = gsi_stmt (psi); 3315 rslt = PHI_RESULT (phi); 3316 def = PHI_ARG_DEF_FROM_EDGE (phi, exit); 3317 if (!is_gimple_reg (def)) 3318 { 3319 gsi_next (&psi); 3320 continue; 3321 } 3322 3323 if (!POINTER_TYPE_P (TREE_TYPE (def)) 3324 && !INTEGRAL_TYPE_P (TREE_TYPE (def))) 3325 { 3326 gsi_next (&psi); 3327 continue; 3328 } 3329 3330 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL); 3331 def = compute_overall_effect_of_inner_loop (ex_loop, def); 3332 if (!tree_does_not_contain_chrecs (def) 3333 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num) 3334 /* Moving the computation from the loop may prolong life range 3335 of some ssa names, which may cause problems if they appear 3336 on abnormal edges. */ 3337 || contains_abnormal_ssa_name_p (def) 3338 /* Do not emit expensive expressions. The rationale is that 3339 when someone writes a code like 3340 3341 while (n > 45) n -= 45; 3342 3343 he probably knows that n is not large, and does not want it 3344 to be turned into n %= 45. */ 3345 || expression_expensive_p (def)) 3346 { 3347 gsi_next (&psi); 3348 continue; 3349 } 3350 3351 /* Eliminate the PHI node and replace it by a computation outside 3352 the loop. */ 3353 def = unshare_expr (def); 3354 remove_phi_node (&psi, false); 3355 3356 def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE, 3357 true, GSI_SAME_STMT); 3358 ass = gimple_build_assign (rslt, def); 3359 gsi_insert_before (&bsi, ass, GSI_SAME_STMT); 3360 } 3361 } 3362 return 0; 3363 } 3364 3365 #include "gt-tree-scalar-evolution.h" 3366