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