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