1/* Scalar evolution detector. 2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <s.pop@laposte.net> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 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 MODIFY_EXPR: 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 ({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 2: 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 3: Higher degree polynomials. 159 160 | loop_1 161 | a = phi (2, b) 162 | c = phi (5, d) 163 | b = a + 1 164 | d = c + a 165 | endloop 166 167 a -> {2, +, 1}_1 168 b -> {3, +, 1}_1 169 c -> {5, +, a}_1 170 d -> {5 + a, +, a}_1 171 172 instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1 173 instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1 174 175 Example 4: Lucas, Fibonacci, or mixers in general. 176 177 | loop_1 178 | a = phi (1, b) 179 | c = phi (3, d) 180 | b = c 181 | d = c + a 182 | endloop 183 184 a -> (1, c)_1 185 c -> {3, +, a}_1 186 187 The syntax "(1, c)_1" stands for a PEELED_CHREC that has the 188 following semantics: during the first iteration of the loop_1, the 189 variable contains the value 1, and then it contains the value "c". 190 Note that this syntax is close to the syntax of the loop-phi-node: 191 "a -> (1, c)_1" vs. "a = phi (1, c)". 192 193 The symbolic chrec representation contains all the semantics of the 194 original code. What is more difficult is to use this information. 195 196 Example 5: Flip-flops, or exchangers. 197 198 | loop_1 199 | a = phi (1, b) 200 | c = phi (3, d) 201 | b = c 202 | d = a 203 | endloop 204 205 a -> (1, c)_1 206 c -> (3, a)_1 207 208 Based on these symbolic chrecs, it is possible to refine this 209 information into the more precise PERIODIC_CHRECs: 210 211 a -> |1, 3|_1 212 c -> |3, 1|_1 213 214 This transformation is not yet implemented. 215 216 Further readings: 217 218 You can find a more detailed description of the algorithm in: 219 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf 220 http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that 221 this is a preliminary report and some of the details of the 222 algorithm have changed. I'm working on a research report that 223 updates the description of the algorithms to reflect the design 224 choices used in this implementation. 225 226 A set of slides show a high level overview of the algorithm and run 227 an example through the scalar evolution analyzer: 228 http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf 229 230 The slides that I have presented at the GCC Summit'04 are available 231 at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf 232*/ 233 234#include "config.h" 235#include "system.h" 236#include "coretypes.h" 237#include "tm.h" 238#include "ggc.h" 239#include "tree.h" 240#include "real.h" 241 242/* These RTL headers are needed for basic-block.h. */ 243#include "rtl.h" 244#include "basic-block.h" 245#include "diagnostic.h" 246#include "tree-flow.h" 247#include "tree-dump.h" 248#include "timevar.h" 249#include "cfgloop.h" 250#include "tree-chrec.h" 251#include "tree-scalar-evolution.h" 252#include "tree-pass.h" 253#include "flags.h" 254#include "params.h" 255 256static tree analyze_scalar_evolution_1 (struct loop *, tree, tree); 257static tree resolve_mixers (struct loop *, tree); 258 259/* The cached information about a ssa name VAR, claiming that inside LOOP, 260 the value of VAR can be expressed as CHREC. */ 261 262struct scev_info_str 263{ 264 tree var; 265 tree chrec; 266}; 267 268/* Counters for the scev database. */ 269static unsigned nb_set_scev = 0; 270static unsigned nb_get_scev = 0; 271 272/* The following trees are unique elements. Thus the comparison of 273 another element to these elements should be done on the pointer to 274 these trees, and not on their value. */ 275 276/* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */ 277tree chrec_not_analyzed_yet; 278 279/* Reserved to the cases where the analyzer has detected an 280 undecidable property at compile time. */ 281tree chrec_dont_know; 282 283/* When the analyzer has detected that a property will never 284 happen, then it qualifies it with chrec_known. */ 285tree chrec_known; 286 287static bitmap already_instantiated; 288 289static htab_t scalar_evolution_info; 290 291 292/* Constructs a new SCEV_INFO_STR structure. */ 293 294static inline struct scev_info_str * 295new_scev_info_str (tree var) 296{ 297 struct scev_info_str *res; 298 299 res = xmalloc (sizeof (struct scev_info_str)); 300 res->var = var; 301 res->chrec = chrec_not_analyzed_yet; 302 303 return res; 304} 305 306/* Computes a hash function for database element ELT. */ 307 308static hashval_t 309hash_scev_info (const void *elt) 310{ 311 return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var); 312} 313 314/* Compares database elements E1 and E2. */ 315 316static int 317eq_scev_info (const void *e1, const void *e2) 318{ 319 const struct scev_info_str *elt1 = e1; 320 const struct scev_info_str *elt2 = e2; 321 322 return elt1->var == elt2->var; 323} 324 325/* Deletes database element E. */ 326 327static void 328del_scev_info (void *e) 329{ 330 free (e); 331} 332 333/* Get the index corresponding to VAR in the current LOOP. If 334 it's the first time we ask for this VAR, then we return 335 chrec_not_analyzed_yet for this VAR and return its index. */ 336 337static tree * 338find_var_scev_info (tree var) 339{ 340 struct scev_info_str *res; 341 struct scev_info_str tmp; 342 PTR *slot; 343 344 tmp.var = var; 345 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT); 346 347 if (!*slot) 348 *slot = new_scev_info_str (var); 349 res = *slot; 350 351 return &res->chrec; 352} 353 354/* Return true when CHREC contains symbolic names defined in 355 LOOP_NB. */ 356 357bool 358chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb) 359{ 360 if (chrec == NULL_TREE) 361 return false; 362 363 if (TREE_INVARIANT (chrec)) 364 return false; 365 366 if (TREE_CODE (chrec) == VAR_DECL 367 || TREE_CODE (chrec) == PARM_DECL 368 || TREE_CODE (chrec) == FUNCTION_DECL 369 || TREE_CODE (chrec) == LABEL_DECL 370 || TREE_CODE (chrec) == RESULT_DECL 371 || TREE_CODE (chrec) == FIELD_DECL) 372 return true; 373 374 if (TREE_CODE (chrec) == SSA_NAME) 375 { 376 tree def = SSA_NAME_DEF_STMT (chrec); 377 struct loop *def_loop = loop_containing_stmt (def); 378 struct loop *loop = current_loops->parray[loop_nb]; 379 380 if (def_loop == NULL) 381 return false; 382 383 if (loop == def_loop || flow_loop_nested_p (loop, def_loop)) 384 return true; 385 386 return false; 387 } 388 389 switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 390 { 391 case 3: 392 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2), 393 loop_nb)) 394 return true; 395 396 case 2: 397 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1), 398 loop_nb)) 399 return true; 400 401 case 1: 402 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0), 403 loop_nb)) 404 return true; 405 406 default: 407 return false; 408 } 409} 410 411/* Return true when PHI is a loop-phi-node. */ 412 413static bool 414loop_phi_node_p (tree phi) 415{ 416 /* The implementation of this function is based on the following 417 property: "all the loop-phi-nodes of a loop are contained in the 418 loop's header basic block". */ 419 420 return loop_containing_stmt (phi)->header == bb_for_stmt (phi); 421} 422 423/* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP. 424 In general, in the case of multivariate evolutions we want to get 425 the evolution in different loops. LOOP specifies the level for 426 which to get the evolution. 427 428 Example: 429 430 | for (j = 0; j < 100; j++) 431 | { 432 | for (k = 0; k < 100; k++) 433 | { 434 | i = k + j; - Here the value of i is a function of j, k. 435 | } 436 | ... = i - Here the value of i is a function of j. 437 | } 438 | ... = i - Here the value of i is a scalar. 439 440 Example: 441 442 | i_0 = ... 443 | loop_1 10 times 444 | i_1 = phi (i_0, i_2) 445 | i_2 = i_1 + 2 446 | endloop 447 448 This loop has the same effect as: 449 LOOP_1 has the same effect as: 450 451 | i_1 = i_0 + 20 452 453 The overall effect of the loop, "i_0 + 20" in the previous example, 454 is obtained by passing in the parameters: LOOP = 1, 455 EVOLUTION_FN = {i_0, +, 2}_1. 456*/ 457 458static tree 459compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) 460{ 461 bool val = false; 462 463 if (evolution_fn == chrec_dont_know) 464 return chrec_dont_know; 465 466 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC) 467 { 468 if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num) 469 { 470 struct loop *inner_loop = 471 current_loops->parray[CHREC_VARIABLE (evolution_fn)]; 472 tree nb_iter = number_of_iterations_in_loop (inner_loop); 473 474 if (nb_iter == chrec_dont_know) 475 return chrec_dont_know; 476 else 477 { 478 tree res; 479 480 /* Number of iterations is off by one (the ssa name we 481 analyze must be defined before the exit). */ 482 nb_iter = chrec_fold_minus (chrec_type (nb_iter), 483 nb_iter, 484 build_int_cst_type (chrec_type (nb_iter), 1)); 485 486 /* evolution_fn is the evolution function in LOOP. Get 487 its value in the nb_iter-th iteration. */ 488 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter); 489 490 /* Continue the computation until ending on a parent of LOOP. */ 491 return compute_overall_effect_of_inner_loop (loop, res); 492 } 493 } 494 else 495 return evolution_fn; 496 } 497 498 /* If the evolution function is an invariant, there is nothing to do. */ 499 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val) 500 return evolution_fn; 501 502 else 503 return chrec_dont_know; 504} 505 506/* Determine whether the CHREC is always positive/negative. If the expression 507 cannot be statically analyzed, return false, otherwise set the answer into 508 VALUE. */ 509 510bool 511chrec_is_positive (tree chrec, bool *value) 512{ 513 bool value0, value1; 514 bool value2; 515 tree end_value; 516 tree nb_iter; 517 518 switch (TREE_CODE (chrec)) 519 { 520 case POLYNOMIAL_CHREC: 521 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0) 522 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1)) 523 return false; 524 525 /* FIXME -- overflows. */ 526 if (value0 == value1) 527 { 528 *value = value0; 529 return true; 530 } 531 532 /* Otherwise the chrec is under the form: "{-197, +, 2}_1", 533 and the proof consists in showing that the sign never 534 changes during the execution of the loop, from 0 to 535 loop->nb_iterations. */ 536 if (!evolution_function_is_affine_p (chrec)) 537 return false; 538 539 nb_iter = number_of_iterations_in_loop 540 (current_loops->parray[CHREC_VARIABLE (chrec)]); 541 542 if (chrec_contains_undetermined (nb_iter)) 543 return false; 544 545 nb_iter = chrec_fold_minus 546 (chrec_type (nb_iter), nb_iter, 547 build_int_cst (chrec_type (nb_iter), 1)); 548 549#if 0 550 /* TODO -- If the test is after the exit, we may decrease the number of 551 iterations by one. */ 552 if (after_exit) 553 nb_iter = chrec_fold_minus 554 (chrec_type (nb_iter), nb_iter, 555 build_int_cst (chrec_type (nb_iter), 1)); 556#endif 557 558 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter); 559 560 if (!chrec_is_positive (end_value, &value2)) 561 return false; 562 563 *value = value0; 564 return value0 == value1; 565 566 case INTEGER_CST: 567 *value = (tree_int_cst_sgn (chrec) == 1); 568 return true; 569 570 default: 571 return false; 572 } 573} 574 575/* Associate CHREC to SCALAR. */ 576 577static void 578set_scalar_evolution (tree scalar, tree chrec) 579{ 580 tree *scalar_info; 581 582 if (TREE_CODE (scalar) != SSA_NAME) 583 return; 584 585 scalar_info = find_var_scev_info (scalar); 586 587 if (dump_file) 588 { 589 if (dump_flags & TDF_DETAILS) 590 { 591 fprintf (dump_file, "(set_scalar_evolution \n"); 592 fprintf (dump_file, " (scalar = "); 593 print_generic_expr (dump_file, scalar, 0); 594 fprintf (dump_file, ")\n (scalar_evolution = "); 595 print_generic_expr (dump_file, chrec, 0); 596 fprintf (dump_file, "))\n"); 597 } 598 if (dump_flags & TDF_STATS) 599 nb_set_scev++; 600 } 601 602 *scalar_info = chrec; 603} 604 605/* Retrieve the chrec associated to SCALAR in the LOOP. */ 606 607static tree 608get_scalar_evolution (tree scalar) 609{ 610 tree res; 611 612 if (dump_file) 613 { 614 if (dump_flags & TDF_DETAILS) 615 { 616 fprintf (dump_file, "(get_scalar_evolution \n"); 617 fprintf (dump_file, " (scalar = "); 618 print_generic_expr (dump_file, scalar, 0); 619 fprintf (dump_file, ")\n"); 620 } 621 if (dump_flags & TDF_STATS) 622 nb_get_scev++; 623 } 624 625 switch (TREE_CODE (scalar)) 626 { 627 case SSA_NAME: 628 res = *find_var_scev_info (scalar); 629 break; 630 631 case REAL_CST: 632 case INTEGER_CST: 633 res = scalar; 634 break; 635 636 default: 637 res = chrec_not_analyzed_yet; 638 break; 639 } 640 641 if (dump_file && (dump_flags & TDF_DETAILS)) 642 { 643 fprintf (dump_file, " (scalar_evolution = "); 644 print_generic_expr (dump_file, res, 0); 645 fprintf (dump_file, "))\n"); 646 } 647 648 return res; 649} 650 651/* Helper function for add_to_evolution. Returns the evolution 652 function for an assignment of the form "a = b + c", where "a" and 653 "b" are on the strongly connected component. CHREC_BEFORE is the 654 information that we already have collected up to this point. 655 TO_ADD is the evolution of "c". 656 657 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this 658 evolution the expression TO_ADD, otherwise construct an evolution 659 part for this loop. */ 660 661static tree 662add_to_evolution_1 (unsigned loop_nb, 663 tree chrec_before, 664 tree to_add) 665{ 666 switch (TREE_CODE (chrec_before)) 667 { 668 case POLYNOMIAL_CHREC: 669 if (CHREC_VARIABLE (chrec_before) <= loop_nb) 670 { 671 unsigned var; 672 tree left, right; 673 tree type = chrec_type (chrec_before); 674 675 /* When there is no evolution part in this loop, build it. */ 676 if (CHREC_VARIABLE (chrec_before) < loop_nb) 677 { 678 var = loop_nb; 679 left = chrec_before; 680 right = SCALAR_FLOAT_TYPE_P (type) 681 ? build_real (type, dconst0) 682 : build_int_cst (type, 0); 683 } 684 else 685 { 686 var = CHREC_VARIABLE (chrec_before); 687 left = CHREC_LEFT (chrec_before); 688 right = CHREC_RIGHT (chrec_before); 689 } 690 691 return build_polynomial_chrec 692 (var, left, chrec_fold_plus (type, right, to_add)); 693 } 694 else 695 /* Search the evolution in LOOP_NB. */ 696 return build_polynomial_chrec 697 (CHREC_VARIABLE (chrec_before), 698 add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add), 699 CHREC_RIGHT (chrec_before)); 700 701 default: 702 /* These nodes do not depend on a loop. */ 703 if (chrec_before == chrec_dont_know) 704 return chrec_dont_know; 705 return build_polynomial_chrec (loop_nb, chrec_before, to_add); 706 } 707} 708 709/* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension 710 of LOOP_NB. 711 712 Description (provided for completeness, for those who read code in 713 a plane, and for my poor 62 bytes brain that would have forgotten 714 all this in the next two or three months): 715 716 The algorithm of translation of programs from the SSA representation 717 into the chrecs syntax is based on a pattern matching. After having 718 reconstructed the overall tree expression for a loop, there are only 719 two cases that can arise: 720 721 1. a = loop-phi (init, a + expr) 722 2. a = loop-phi (init, expr) 723 724 where EXPR is either a scalar constant with respect to the analyzed 725 loop (this is a degree 0 polynomial), or an expression containing 726 other loop-phi definitions (these are higher degree polynomials). 727 728 Examples: 729 730 1. 731 | init = ... 732 | loop_1 733 | a = phi (init, a + 5) 734 | endloop 735 736 2. 737 | inita = ... 738 | initb = ... 739 | loop_1 740 | a = phi (inita, 2 * b + 3) 741 | b = phi (initb, b + 1) 742 | endloop 743 744 For the first case, the semantics of the SSA representation is: 745 746 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j) 747 748 that is, there is a loop index "x" that determines the scalar value 749 of the variable during the loop execution. During the first 750 iteration, the value is that of the initial condition INIT, while 751 during the subsequent iterations, it is the sum of the initial 752 condition with the sum of all the values of EXPR from the initial 753 iteration to the before last considered iteration. 754 755 For the second case, the semantics of the SSA program is: 756 757 | a (x) = init, if x = 0; 758 | expr (x - 1), otherwise. 759 760 The second case corresponds to the PEELED_CHREC, whose syntax is 761 close to the syntax of a loop-phi-node: 762 763 | phi (init, expr) vs. (init, expr)_x 764 765 The proof of the translation algorithm for the first case is a 766 proof by structural induction based on the degree of EXPR. 767 768 Degree 0: 769 When EXPR is a constant with respect to the analyzed loop, or in 770 other words when EXPR is a polynomial of degree 0, the evolution of 771 the variable A in the loop is an affine function with an initial 772 condition INIT, and a step EXPR. In order to show this, we start 773 from the semantics of the SSA representation: 774 775 f (x) = init + \sum_{j = 0}^{x - 1} expr (j) 776 777 and since "expr (j)" is a constant with respect to "j", 778 779 f (x) = init + x * expr 780 781 Finally, based on the semantics of the pure sum chrecs, by 782 identification we get the corresponding chrecs syntax: 783 784 f (x) = init * \binom{x}{0} + expr * \binom{x}{1} 785 f (x) -> {init, +, expr}_x 786 787 Higher degree: 788 Suppose that EXPR is a polynomial of degree N with respect to the 789 analyzed loop_x for which we have already determined that it is 790 written under the chrecs syntax: 791 792 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x) 793 794 We start from the semantics of the SSA program: 795 796 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j) 797 | 798 | f (x) = init + \sum_{j = 0}^{x - 1} 799 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1}) 800 | 801 | f (x) = init + \sum_{j = 0}^{x - 1} 802 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k}) 803 | 804 | f (x) = init + \sum_{k = 0}^{n - 1} 805 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k}) 806 | 807 | f (x) = init + \sum_{k = 0}^{n - 1} 808 | (b_k * \binom{x}{k + 1}) 809 | 810 | f (x) = init + b_0 * \binom{x}{1} + ... 811 | + b_{n-1} * \binom{x}{n} 812 | 813 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ... 814 | + b_{n-1} * \binom{x}{n} 815 | 816 817 And finally from the definition of the chrecs syntax, we identify: 818 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x 819 820 This shows the mechanism that stands behind the add_to_evolution 821 function. An important point is that the use of symbolic 822 parameters avoids the need of an analysis schedule. 823 824 Example: 825 826 | inita = ... 827 | initb = ... 828 | loop_1 829 | a = phi (inita, a + 2 + b) 830 | b = phi (initb, b + 1) 831 | endloop 832 833 When analyzing "a", the algorithm keeps "b" symbolically: 834 835 | a -> {inita, +, 2 + b}_1 836 837 Then, after instantiation, the analyzer ends on the evolution: 838 839 | a -> {inita, +, 2 + initb, +, 1}_1 840 841*/ 842 843static tree 844add_to_evolution (unsigned loop_nb, 845 tree chrec_before, 846 enum tree_code code, 847 tree to_add) 848{ 849 tree type = chrec_type (to_add); 850 tree res = NULL_TREE; 851 852 if (to_add == NULL_TREE) 853 return chrec_before; 854 855 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not 856 instantiated at this point. */ 857 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC) 858 /* This should not happen. */ 859 return chrec_dont_know; 860 861 if (dump_file && (dump_flags & TDF_DETAILS)) 862 { 863 fprintf (dump_file, "(add_to_evolution \n"); 864 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb); 865 fprintf (dump_file, " (chrec_before = "); 866 print_generic_expr (dump_file, chrec_before, 0); 867 fprintf (dump_file, ")\n (to_add = "); 868 print_generic_expr (dump_file, to_add, 0); 869 fprintf (dump_file, ")\n"); 870 } 871 872 if (code == MINUS_EXPR) 873 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type) 874 ? build_real (type, dconstm1) 875 : build_int_cst_type (type, -1)); 876 877 res = add_to_evolution_1 (loop_nb, chrec_before, to_add); 878 879 if (dump_file && (dump_flags & TDF_DETAILS)) 880 { 881 fprintf (dump_file, " (res = "); 882 print_generic_expr (dump_file, res, 0); 883 fprintf (dump_file, "))\n"); 884 } 885 886 return res; 887} 888 889/* Helper function. */ 890 891static inline tree 892set_nb_iterations_in_loop (struct loop *loop, 893 tree res) 894{ 895 res = chrec_fold_plus (chrec_type (res), res, 896 build_int_cst_type (chrec_type (res), 1)); 897 898 /* FIXME HWI: However we want to store one iteration less than the 899 count of the loop in order to be compatible with the other 900 nb_iter computations in loop-iv. This also allows the 901 representation of nb_iters that are equal to MAX_INT. */ 902 if (TREE_CODE (res) == INTEGER_CST 903 && (TREE_INT_CST_LOW (res) == 0 904 || TREE_OVERFLOW (res))) 905 res = chrec_dont_know; 906 907 if (dump_file && (dump_flags & TDF_DETAILS)) 908 { 909 fprintf (dump_file, " (set_nb_iterations_in_loop = "); 910 print_generic_expr (dump_file, res, 0); 911 fprintf (dump_file, "))\n"); 912 } 913 914 loop->nb_iterations = res; 915 return res; 916} 917 918 919 920/* This section selects the loops that will be good candidates for the 921 scalar evolution analysis. For the moment, greedily select all the 922 loop nests we could analyze. */ 923 924/* Return true when it is possible to analyze the condition expression 925 EXPR. */ 926 927static bool 928analyzable_condition (tree expr) 929{ 930 tree condition; 931 932 if (TREE_CODE (expr) != COND_EXPR) 933 return false; 934 935 condition = TREE_OPERAND (expr, 0); 936 937 switch (TREE_CODE (condition)) 938 { 939 case SSA_NAME: 940 return true; 941 942 case LT_EXPR: 943 case LE_EXPR: 944 case GT_EXPR: 945 case GE_EXPR: 946 case EQ_EXPR: 947 case NE_EXPR: 948 return true; 949 950 default: 951 return false; 952 } 953 954 return false; 955} 956 957/* For a loop with a single exit edge, return the COND_EXPR that 958 guards the exit edge. If the expression is too difficult to 959 analyze, then give up. */ 960 961tree 962get_loop_exit_condition (struct loop *loop) 963{ 964 tree res = NULL_TREE; 965 edge exit_edge = loop->single_exit; 966 967 968 if (dump_file && (dump_flags & TDF_DETAILS)) 969 fprintf (dump_file, "(get_loop_exit_condition \n "); 970 971 if (exit_edge) 972 { 973 tree expr; 974 975 expr = last_stmt (exit_edge->src); 976 if (analyzable_condition (expr)) 977 res = expr; 978 } 979 980 if (dump_file && (dump_flags & TDF_DETAILS)) 981 { 982 print_generic_expr (dump_file, res, 0); 983 fprintf (dump_file, ")\n"); 984 } 985 986 return res; 987} 988 989/* Recursively determine and enqueue the exit conditions for a loop. */ 990 991static void 992get_exit_conditions_rec (struct loop *loop, 993 VEC(tree,heap) **exit_conditions) 994{ 995 if (!loop) 996 return; 997 998 /* Recurse on the inner loops, then on the next (sibling) loops. */ 999 get_exit_conditions_rec (loop->inner, exit_conditions); 1000 get_exit_conditions_rec (loop->next, exit_conditions); 1001 1002 if (loop->single_exit) 1003 { 1004 tree loop_condition = get_loop_exit_condition (loop); 1005 1006 if (loop_condition) 1007 VEC_safe_push (tree, heap, *exit_conditions, loop_condition); 1008 } 1009} 1010 1011/* Select the candidate loop nests for the analysis. This function 1012 initializes the EXIT_CONDITIONS array. */ 1013 1014static void 1015select_loops_exit_conditions (struct loops *loops, 1016 VEC(tree,heap) **exit_conditions) 1017{ 1018 struct loop *function_body = loops->parray[0]; 1019 1020 get_exit_conditions_rec (function_body->inner, exit_conditions); 1021} 1022 1023 1024/* Depth first search algorithm. */ 1025 1026typedef enum t_bool { 1027 t_false, 1028 t_true, 1029 t_dont_know 1030} t_bool; 1031 1032 1033static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int); 1034 1035/* Follow the ssa edge into the right hand side RHS of an assignment. 1036 Return true if the strongly connected component has been found. */ 1037 1038static t_bool 1039follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs, 1040 tree halting_phi, tree *evolution_of_loop, int limit) 1041{ 1042 t_bool res = t_false; 1043 tree rhs0, rhs1; 1044 tree type_rhs = TREE_TYPE (rhs); 1045 tree evol; 1046 1047 /* The RHS is one of the following cases: 1048 - an SSA_NAME, 1049 - an INTEGER_CST, 1050 - a PLUS_EXPR, 1051 - a MINUS_EXPR, 1052 - an ASSERT_EXPR, 1053 - other cases are not yet handled. */ 1054 switch (TREE_CODE (rhs)) 1055 { 1056 case NOP_EXPR: 1057 /* This assignment is under the form "a_1 = (cast) rhs. */ 1058 res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0), 1059 halting_phi, evolution_of_loop, limit); 1060 *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), 1061 *evolution_of_loop, at_stmt); 1062 break; 1063 1064 case INTEGER_CST: 1065 /* This assignment is under the form "a_1 = 7". */ 1066 res = t_false; 1067 break; 1068 1069 case SSA_NAME: 1070 /* This assignment is under the form: "a_1 = b_2". */ 1071 res = follow_ssa_edge 1072 (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit); 1073 break; 1074 1075 case PLUS_EXPR: 1076 /* This case is under the form "rhs0 + rhs1". */ 1077 rhs0 = TREE_OPERAND (rhs, 0); 1078 rhs1 = TREE_OPERAND (rhs, 1); 1079 STRIP_TYPE_NOPS (rhs0); 1080 STRIP_TYPE_NOPS (rhs1); 1081 1082 if (TREE_CODE (rhs0) == SSA_NAME) 1083 { 1084 if (TREE_CODE (rhs1) == SSA_NAME) 1085 { 1086 /* Match an assignment under the form: 1087 "a = b + c". */ 1088 evol = *evolution_of_loop; 1089 res = follow_ssa_edge 1090 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 1091 &evol, limit); 1092 1093 if (res == t_true) 1094 *evolution_of_loop = add_to_evolution 1095 (loop->num, 1096 chrec_convert (type_rhs, evol, at_stmt), 1097 PLUS_EXPR, rhs1); 1098 1099 else if (res == t_false) 1100 { 1101 res = follow_ssa_edge 1102 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 1103 evolution_of_loop, limit); 1104 1105 if (res == t_true) 1106 *evolution_of_loop = add_to_evolution 1107 (loop->num, 1108 chrec_convert (type_rhs, *evolution_of_loop, at_stmt), 1109 PLUS_EXPR, rhs0); 1110 1111 else if (res == t_dont_know) 1112 *evolution_of_loop = chrec_dont_know; 1113 } 1114 1115 else if (res == t_dont_know) 1116 *evolution_of_loop = chrec_dont_know; 1117 } 1118 1119 else 1120 { 1121 /* Match an assignment under the form: 1122 "a = b + ...". */ 1123 res = follow_ssa_edge 1124 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 1125 evolution_of_loop, limit); 1126 if (res == t_true) 1127 *evolution_of_loop = add_to_evolution 1128 (loop->num, chrec_convert (type_rhs, *evolution_of_loop, 1129 at_stmt), 1130 PLUS_EXPR, rhs1); 1131 1132 else if (res == t_dont_know) 1133 *evolution_of_loop = chrec_dont_know; 1134 } 1135 } 1136 1137 else if (TREE_CODE (rhs1) == SSA_NAME) 1138 { 1139 /* Match an assignment under the form: 1140 "a = ... + c". */ 1141 res = follow_ssa_edge 1142 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 1143 evolution_of_loop, limit); 1144 if (res == t_true) 1145 *evolution_of_loop = add_to_evolution 1146 (loop->num, chrec_convert (type_rhs, *evolution_of_loop, 1147 at_stmt), 1148 PLUS_EXPR, rhs0); 1149 1150 else if (res == t_dont_know) 1151 *evolution_of_loop = chrec_dont_know; 1152 } 1153 1154 else 1155 /* Otherwise, match an assignment under the form: 1156 "a = ... + ...". */ 1157 /* And there is nothing to do. */ 1158 res = t_false; 1159 1160 break; 1161 1162 case MINUS_EXPR: 1163 /* This case is under the form "opnd0 = rhs0 - rhs1". */ 1164 rhs0 = TREE_OPERAND (rhs, 0); 1165 rhs1 = TREE_OPERAND (rhs, 1); 1166 STRIP_TYPE_NOPS (rhs0); 1167 STRIP_TYPE_NOPS (rhs1); 1168 1169 if (TREE_CODE (rhs0) == SSA_NAME) 1170 { 1171 /* Match an assignment under the form: 1172 "a = b - ...". */ 1173 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 1174 evolution_of_loop, limit); 1175 if (res == t_true) 1176 *evolution_of_loop = add_to_evolution 1177 (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt), 1178 MINUS_EXPR, rhs1); 1179 1180 else if (res == t_dont_know) 1181 *evolution_of_loop = chrec_dont_know; 1182 } 1183 else 1184 /* Otherwise, match an assignment under the form: 1185 "a = ... - ...". */ 1186 /* And there is nothing to do. */ 1187 res = t_false; 1188 1189 break; 1190 1191 case ASSERT_EXPR: 1192 { 1193 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>" 1194 It must be handled as a copy assignment of the form a_1 = a_2. */ 1195 tree op0 = ASSERT_EXPR_VAR (rhs); 1196 if (TREE_CODE (op0) == SSA_NAME) 1197 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0), 1198 halting_phi, evolution_of_loop, limit); 1199 else 1200 res = t_false; 1201 break; 1202 } 1203 1204 1205 default: 1206 res = t_false; 1207 break; 1208 } 1209 1210 return res; 1211} 1212 1213/* Checks whether the I-th argument of a PHI comes from a backedge. */ 1214 1215static bool 1216backedge_phi_arg_p (tree phi, int i) 1217{ 1218 edge e = PHI_ARG_EDGE (phi, i); 1219 1220 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care 1221 about updating it anywhere, and this should work as well most of the 1222 time. */ 1223 if (e->flags & EDGE_IRREDUCIBLE_LOOP) 1224 return true; 1225 1226 return false; 1227} 1228 1229/* Helper function for one branch of the condition-phi-node. Return 1230 true if the strongly connected component has been found following 1231 this path. */ 1232 1233static inline t_bool 1234follow_ssa_edge_in_condition_phi_branch (int i, 1235 struct loop *loop, 1236 tree condition_phi, 1237 tree halting_phi, 1238 tree *evolution_of_branch, 1239 tree init_cond, int limit) 1240{ 1241 tree branch = PHI_ARG_DEF (condition_phi, i); 1242 *evolution_of_branch = chrec_dont_know; 1243 1244 /* Do not follow back edges (they must belong to an irreducible loop, which 1245 we really do not want to worry about). */ 1246 if (backedge_phi_arg_p (condition_phi, i)) 1247 return t_false; 1248 1249 if (TREE_CODE (branch) == SSA_NAME) 1250 { 1251 *evolution_of_branch = init_cond; 1252 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, 1253 evolution_of_branch, limit); 1254 } 1255 1256 /* This case occurs when one of the condition branches sets 1257 the variable to a constant: i.e. a phi-node like 1258 "a_2 = PHI <a_7(5), 2(6)>;". 1259 1260 FIXME: This case have to be refined correctly: 1261 in some cases it is possible to say something better than 1262 chrec_dont_know, for example using a wrap-around notation. */ 1263 return t_false; 1264} 1265 1266/* This function merges the branches of a condition-phi-node in a 1267 loop. */ 1268 1269static t_bool 1270follow_ssa_edge_in_condition_phi (struct loop *loop, 1271 tree condition_phi, 1272 tree halting_phi, 1273 tree *evolution_of_loop, int limit) 1274{ 1275 int i; 1276 tree init = *evolution_of_loop; 1277 tree evolution_of_branch; 1278 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi, 1279 halting_phi, 1280 &evolution_of_branch, 1281 init, limit); 1282 if (res == t_false || res == t_dont_know) 1283 return res; 1284 1285 *evolution_of_loop = evolution_of_branch; 1286 1287 for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++) 1288 { 1289 /* Quickly give up when the evolution of one of the branches is 1290 not known. */ 1291 if (*evolution_of_loop == chrec_dont_know) 1292 return t_true; 1293 1294 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi, 1295 halting_phi, 1296 &evolution_of_branch, 1297 init, limit); 1298 if (res == t_false || res == t_dont_know) 1299 return res; 1300 1301 *evolution_of_loop = chrec_merge (*evolution_of_loop, 1302 evolution_of_branch); 1303 } 1304 1305 return t_true; 1306} 1307 1308/* Follow an SSA edge in an inner loop. It computes the overall 1309 effect of the loop, and following the symbolic initial conditions, 1310 it follows the edges in the parent loop. The inner loop is 1311 considered as a single statement. */ 1312 1313static t_bool 1314follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, 1315 tree loop_phi_node, 1316 tree halting_phi, 1317 tree *evolution_of_loop, int limit) 1318{ 1319 struct loop *loop = loop_containing_stmt (loop_phi_node); 1320 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node)); 1321 1322 /* Sometimes, the inner loop is too difficult to analyze, and the 1323 result of the analysis is a symbolic parameter. */ 1324 if (ev == PHI_RESULT (loop_phi_node)) 1325 { 1326 t_bool res = t_false; 1327 int i; 1328 1329 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) 1330 { 1331 tree arg = PHI_ARG_DEF (loop_phi_node, i); 1332 basic_block bb; 1333 1334 /* Follow the edges that exit the inner loop. */ 1335 bb = PHI_ARG_EDGE (loop_phi_node, i)->src; 1336 if (!flow_bb_inside_loop_p (loop, bb)) 1337 res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, 1338 arg, halting_phi, 1339 evolution_of_loop, limit); 1340 if (res == t_true) 1341 break; 1342 } 1343 1344 /* If the path crosses this loop-phi, give up. */ 1345 if (res == t_true) 1346 *evolution_of_loop = chrec_dont_know; 1347 1348 return res; 1349 } 1350 1351 /* Otherwise, compute the overall effect of the inner loop. */ 1352 ev = compute_overall_effect_of_inner_loop (loop, ev); 1353 return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi, 1354 evolution_of_loop, limit); 1355} 1356 1357/* Follow an SSA edge from a loop-phi-node to itself, constructing a 1358 path that is analyzed on the return walk. */ 1359 1360static t_bool 1361follow_ssa_edge (struct loop *loop, tree def, tree halting_phi, 1362 tree *evolution_of_loop, int limit) 1363{ 1364 struct loop *def_loop; 1365 1366 if (TREE_CODE (def) == NOP_EXPR) 1367 return t_false; 1368 1369 /* Give up if the path is longer than the MAX that we allow. */ 1370 if (limit++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 1371 return t_dont_know; 1372 1373 def_loop = loop_containing_stmt (def); 1374 1375 switch (TREE_CODE (def)) 1376 { 1377 case PHI_NODE: 1378 if (!loop_phi_node_p (def)) 1379 /* DEF is a condition-phi-node. Follow the branches, and 1380 record their evolutions. Finally, merge the collected 1381 information and set the approximation to the main 1382 variable. */ 1383 return follow_ssa_edge_in_condition_phi 1384 (loop, def, halting_phi, evolution_of_loop, limit); 1385 1386 /* When the analyzed phi is the halting_phi, the 1387 depth-first search is over: we have found a path from 1388 the halting_phi to itself in the loop. */ 1389 if (def == halting_phi) 1390 return t_true; 1391 1392 /* Otherwise, the evolution of the HALTING_PHI depends 1393 on the evolution of another loop-phi-node, i.e. the 1394 evolution function is a higher degree polynomial. */ 1395 if (def_loop == loop) 1396 return t_false; 1397 1398 /* Inner loop. */ 1399 if (flow_loop_nested_p (loop, def_loop)) 1400 return follow_ssa_edge_inner_loop_phi 1401 (loop, def, halting_phi, evolution_of_loop, limit); 1402 1403 /* Outer loop. */ 1404 return t_false; 1405 1406 case MODIFY_EXPR: 1407 return follow_ssa_edge_in_rhs (loop, def, 1408 TREE_OPERAND (def, 1), 1409 halting_phi, 1410 evolution_of_loop, limit); 1411 1412 default: 1413 /* At this level of abstraction, the program is just a set 1414 of MODIFY_EXPRs and PHI_NODEs. In principle there is no 1415 other node to be handled. */ 1416 return t_false; 1417 } 1418} 1419 1420 1421 1422/* Given a LOOP_PHI_NODE, this function determines the evolution 1423 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */ 1424 1425static tree 1426analyze_evolution_in_loop (tree loop_phi_node, 1427 tree init_cond) 1428{ 1429 int i; 1430 tree evolution_function = chrec_not_analyzed_yet; 1431 struct loop *loop = loop_containing_stmt (loop_phi_node); 1432 basic_block bb; 1433 1434 if (dump_file && (dump_flags & TDF_DETAILS)) 1435 { 1436 fprintf (dump_file, "(analyze_evolution_in_loop \n"); 1437 fprintf (dump_file, " (loop_phi_node = "); 1438 print_generic_expr (dump_file, loop_phi_node, 0); 1439 fprintf (dump_file, ")\n"); 1440 } 1441 1442 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) 1443 { 1444 tree arg = PHI_ARG_DEF (loop_phi_node, i); 1445 tree ssa_chain, ev_fn; 1446 t_bool res; 1447 1448 /* Select the edges that enter the loop body. */ 1449 bb = PHI_ARG_EDGE (loop_phi_node, i)->src; 1450 if (!flow_bb_inside_loop_p (loop, bb)) 1451 continue; 1452 1453 if (TREE_CODE (arg) == SSA_NAME) 1454 { 1455 ssa_chain = SSA_NAME_DEF_STMT (arg); 1456 1457 /* Pass in the initial condition to the follow edge function. */ 1458 ev_fn = init_cond; 1459 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0); 1460 } 1461 else 1462 res = t_false; 1463 1464 /* When it is impossible to go back on the same 1465 loop_phi_node by following the ssa edges, the 1466 evolution is represented by a peeled chrec, i.e. the 1467 first iteration, EV_FN has the value INIT_COND, then 1468 all the other iterations it has the value of ARG. 1469 For the moment, PEELED_CHREC nodes are not built. */ 1470 if (res != t_true) 1471 ev_fn = chrec_dont_know; 1472 1473 /* When there are multiple back edges of the loop (which in fact never 1474 happens currently, but nevertheless), merge their evolutions. */ 1475 evolution_function = chrec_merge (evolution_function, ev_fn); 1476 } 1477 1478 if (dump_file && (dump_flags & TDF_DETAILS)) 1479 { 1480 fprintf (dump_file, " (evolution_function = "); 1481 print_generic_expr (dump_file, evolution_function, 0); 1482 fprintf (dump_file, "))\n"); 1483 } 1484 1485 return evolution_function; 1486} 1487 1488/* Given a loop-phi-node, return the initial conditions of the 1489 variable on entry of the loop. When the CCP has propagated 1490 constants into the loop-phi-node, the initial condition is 1491 instantiated, otherwise the initial condition is kept symbolic. 1492 This analyzer does not analyze the evolution outside the current 1493 loop, and leaves this task to the on-demand tree reconstructor. */ 1494 1495static tree 1496analyze_initial_condition (tree loop_phi_node) 1497{ 1498 int i; 1499 tree init_cond = chrec_not_analyzed_yet; 1500 struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father; 1501 1502 if (dump_file && (dump_flags & TDF_DETAILS)) 1503 { 1504 fprintf (dump_file, "(analyze_initial_condition \n"); 1505 fprintf (dump_file, " (loop_phi_node = \n"); 1506 print_generic_expr (dump_file, loop_phi_node, 0); 1507 fprintf (dump_file, ")\n"); 1508 } 1509 1510 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) 1511 { 1512 tree branch = PHI_ARG_DEF (loop_phi_node, i); 1513 basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src; 1514 1515 /* When the branch is oriented to the loop's body, it does 1516 not contribute to the initial condition. */ 1517 if (flow_bb_inside_loop_p (loop, bb)) 1518 continue; 1519 1520 if (init_cond == chrec_not_analyzed_yet) 1521 { 1522 init_cond = branch; 1523 continue; 1524 } 1525 1526 if (TREE_CODE (branch) == SSA_NAME) 1527 { 1528 init_cond = chrec_dont_know; 1529 break; 1530 } 1531 1532 init_cond = chrec_merge (init_cond, branch); 1533 } 1534 1535 /* Ooops -- a loop without an entry??? */ 1536 if (init_cond == chrec_not_analyzed_yet) 1537 init_cond = chrec_dont_know; 1538 1539 if (dump_file && (dump_flags & TDF_DETAILS)) 1540 { 1541 fprintf (dump_file, " (init_cond = "); 1542 print_generic_expr (dump_file, init_cond, 0); 1543 fprintf (dump_file, "))\n"); 1544 } 1545 1546 return init_cond; 1547} 1548 1549/* Analyze the scalar evolution for LOOP_PHI_NODE. */ 1550 1551static tree 1552interpret_loop_phi (struct loop *loop, tree loop_phi_node) 1553{ 1554 tree res; 1555 struct loop *phi_loop = loop_containing_stmt (loop_phi_node); 1556 tree init_cond; 1557 1558 if (phi_loop != loop) 1559 { 1560 struct loop *subloop; 1561 tree evolution_fn = analyze_scalar_evolution 1562 (phi_loop, PHI_RESULT (loop_phi_node)); 1563 1564 /* Dive one level deeper. */ 1565 subloop = superloop_at_depth (phi_loop, loop->depth + 1); 1566 1567 /* Interpret the subloop. */ 1568 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn); 1569 return res; 1570 } 1571 1572 /* Otherwise really interpret the loop phi. */ 1573 init_cond = analyze_initial_condition (loop_phi_node); 1574 res = analyze_evolution_in_loop (loop_phi_node, init_cond); 1575 1576 return res; 1577} 1578 1579/* This function merges the branches of a condition-phi-node, 1580 contained in the outermost loop, and whose arguments are already 1581 analyzed. */ 1582 1583static tree 1584interpret_condition_phi (struct loop *loop, tree condition_phi) 1585{ 1586 int i; 1587 tree res = chrec_not_analyzed_yet; 1588 1589 for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++) 1590 { 1591 tree branch_chrec; 1592 1593 if (backedge_phi_arg_p (condition_phi, i)) 1594 { 1595 res = chrec_dont_know; 1596 break; 1597 } 1598 1599 branch_chrec = analyze_scalar_evolution 1600 (loop, PHI_ARG_DEF (condition_phi, i)); 1601 1602 res = chrec_merge (res, branch_chrec); 1603 } 1604 1605 return res; 1606} 1607 1608/* Interpret the right hand side of a modify_expr OPND1. If we didn't 1609 analyze this node before, follow the definitions until ending 1610 either on an analyzed modify_expr, or on a loop-phi-node. On the 1611 return path, this function propagates evolutions (ala constant copy 1612 propagation). OPND1 is not a GIMPLE expression because we could 1613 analyze the effect of an inner loop: see interpret_loop_phi. */ 1614 1615static tree 1616interpret_rhs_modify_expr (struct loop *loop, tree at_stmt, 1617 tree opnd1, tree type) 1618{ 1619 tree res, opnd10, opnd11, chrec10, chrec11; 1620 1621 if (is_gimple_min_invariant (opnd1)) 1622 return chrec_convert (type, opnd1, at_stmt); 1623 1624 switch (TREE_CODE (opnd1)) 1625 { 1626 case PLUS_EXPR: 1627 opnd10 = TREE_OPERAND (opnd1, 0); 1628 opnd11 = TREE_OPERAND (opnd1, 1); 1629 chrec10 = analyze_scalar_evolution (loop, opnd10); 1630 chrec11 = analyze_scalar_evolution (loop, opnd11); 1631 chrec10 = chrec_convert (type, chrec10, at_stmt); 1632 chrec11 = chrec_convert (type, chrec11, at_stmt); 1633 res = chrec_fold_plus (type, chrec10, chrec11); 1634 break; 1635 1636 case MINUS_EXPR: 1637 opnd10 = TREE_OPERAND (opnd1, 0); 1638 opnd11 = TREE_OPERAND (opnd1, 1); 1639 chrec10 = analyze_scalar_evolution (loop, opnd10); 1640 chrec11 = analyze_scalar_evolution (loop, opnd11); 1641 chrec10 = chrec_convert (type, chrec10, at_stmt); 1642 chrec11 = chrec_convert (type, chrec11, at_stmt); 1643 res = chrec_fold_minus (type, chrec10, chrec11); 1644 break; 1645 1646 case NEGATE_EXPR: 1647 opnd10 = TREE_OPERAND (opnd1, 0); 1648 chrec10 = analyze_scalar_evolution (loop, opnd10); 1649 chrec10 = chrec_convert (type, chrec10, at_stmt); 1650 /* TYPE may be integer, real or complex, so use fold_convert. */ 1651 res = chrec_fold_multiply (type, chrec10, 1652 fold_convert (type, integer_minus_one_node)); 1653 break; 1654 1655 case MULT_EXPR: 1656 opnd10 = TREE_OPERAND (opnd1, 0); 1657 opnd11 = TREE_OPERAND (opnd1, 1); 1658 chrec10 = analyze_scalar_evolution (loop, opnd10); 1659 chrec11 = analyze_scalar_evolution (loop, opnd11); 1660 chrec10 = chrec_convert (type, chrec10, at_stmt); 1661 chrec11 = chrec_convert (type, chrec11, at_stmt); 1662 res = chrec_fold_multiply (type, chrec10, chrec11); 1663 break; 1664 1665 case SSA_NAME: 1666 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1), 1667 at_stmt); 1668 break; 1669 1670 case ASSERT_EXPR: 1671 opnd10 = ASSERT_EXPR_VAR (opnd1); 1672 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10), 1673 at_stmt); 1674 break; 1675 1676 case NOP_EXPR: 1677 case CONVERT_EXPR: 1678 opnd10 = TREE_OPERAND (opnd1, 0); 1679 chrec10 = analyze_scalar_evolution (loop, opnd10); 1680 res = chrec_convert (type, chrec10, at_stmt); 1681 break; 1682 1683 default: 1684 res = chrec_dont_know; 1685 break; 1686 } 1687 1688 return res; 1689} 1690 1691 1692 1693/* This section contains all the entry points: 1694 - number_of_iterations_in_loop, 1695 - analyze_scalar_evolution, 1696 - instantiate_parameters. 1697*/ 1698 1699/* Compute and return the evolution function in WRTO_LOOP, the nearest 1700 common ancestor of DEF_LOOP and USE_LOOP. */ 1701 1702static tree 1703compute_scalar_evolution_in_loop (struct loop *wrto_loop, 1704 struct loop *def_loop, 1705 tree ev) 1706{ 1707 tree res; 1708 if (def_loop == wrto_loop) 1709 return ev; 1710 1711 def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1); 1712 res = compute_overall_effect_of_inner_loop (def_loop, ev); 1713 1714 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet); 1715} 1716 1717/* Helper recursive function. */ 1718 1719static tree 1720analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) 1721{ 1722 tree def, type = TREE_TYPE (var); 1723 basic_block bb; 1724 struct loop *def_loop; 1725 1726 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE) 1727 return chrec_dont_know; 1728 1729 if (TREE_CODE (var) != SSA_NAME) 1730 return interpret_rhs_modify_expr (loop, NULL_TREE, var, type); 1731 1732 def = SSA_NAME_DEF_STMT (var); 1733 bb = bb_for_stmt (def); 1734 def_loop = bb ? bb->loop_father : NULL; 1735 1736 if (bb == NULL 1737 || !flow_bb_inside_loop_p (loop, bb)) 1738 { 1739 /* Keep the symbolic form. */ 1740 res = var; 1741 goto set_and_end; 1742 } 1743 1744 if (res != chrec_not_analyzed_yet) 1745 { 1746 if (loop != bb->loop_father) 1747 res = compute_scalar_evolution_in_loop 1748 (find_common_loop (loop, bb->loop_father), bb->loop_father, res); 1749 1750 goto set_and_end; 1751 } 1752 1753 if (loop != def_loop) 1754 { 1755 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet); 1756 res = compute_scalar_evolution_in_loop (loop, def_loop, res); 1757 1758 goto set_and_end; 1759 } 1760 1761 switch (TREE_CODE (def)) 1762 { 1763 case MODIFY_EXPR: 1764 res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type); 1765 break; 1766 1767 case PHI_NODE: 1768 if (loop_phi_node_p (def)) 1769 res = interpret_loop_phi (loop, def); 1770 else 1771 res = interpret_condition_phi (loop, def); 1772 break; 1773 1774 default: 1775 res = chrec_dont_know; 1776 break; 1777 } 1778 1779 set_and_end: 1780 1781 /* Keep the symbolic form. */ 1782 if (res == chrec_dont_know) 1783 res = var; 1784 1785 if (loop == def_loop) 1786 set_scalar_evolution (var, res); 1787 1788 return res; 1789} 1790 1791/* Entry point for the scalar evolution analyzer. 1792 Analyzes and returns the scalar evolution of the ssa_name VAR. 1793 LOOP_NB is the identifier number of the loop in which the variable 1794 is used. 1795 1796 Example of use: having a pointer VAR to a SSA_NAME node, STMT a 1797 pointer to the statement that uses this variable, in order to 1798 determine the evolution function of the variable, use the following 1799 calls: 1800 1801 unsigned loop_nb = loop_containing_stmt (stmt)->num; 1802 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var); 1803 tree chrec_instantiated = instantiate_parameters 1804 (loop_nb, chrec_with_symbols); 1805*/ 1806 1807tree 1808analyze_scalar_evolution (struct loop *loop, tree var) 1809{ 1810 tree res; 1811 1812 if (dump_file && (dump_flags & TDF_DETAILS)) 1813 { 1814 fprintf (dump_file, "(analyze_scalar_evolution \n"); 1815 fprintf (dump_file, " (loop_nb = %d)\n", loop->num); 1816 fprintf (dump_file, " (scalar = "); 1817 print_generic_expr (dump_file, var, 0); 1818 fprintf (dump_file, ")\n"); 1819 } 1820 1821 res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var)); 1822 1823 if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know) 1824 res = var; 1825 1826 if (dump_file && (dump_flags & TDF_DETAILS)) 1827 fprintf (dump_file, ")\n"); 1828 1829 return res; 1830} 1831 1832/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to 1833 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition 1834 of VERSION). 1835 1836 FOLDED_CASTS is set to true if resolve_mixers used 1837 chrec_convert_aggressive (TODO -- not really, we are way too conservative 1838 at the moment in order to keep things simple). */ 1839 1840static tree 1841analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop, 1842 tree version, bool *folded_casts) 1843{ 1844 bool val = false; 1845 tree ev = version, tmp; 1846 1847 if (folded_casts) 1848 *folded_casts = false; 1849 while (1) 1850 { 1851 tmp = analyze_scalar_evolution (use_loop, ev); 1852 ev = resolve_mixers (use_loop, tmp); 1853 1854 if (folded_casts && tmp != ev) 1855 *folded_casts = true; 1856 1857 if (use_loop == wrto_loop) 1858 return ev; 1859 1860 /* If the value of the use changes in the inner loop, we cannot express 1861 its value in the outer loop (we might try to return interval chrec, 1862 but we do not have a user for it anyway) */ 1863 if (!no_evolution_in_loop_p (ev, use_loop->num, &val) 1864 || !val) 1865 return chrec_dont_know; 1866 1867 use_loop = use_loop->outer; 1868 } 1869} 1870 1871/* Returns instantiated value for VERSION in CACHE. */ 1872 1873static tree 1874get_instantiated_value (htab_t cache, tree version) 1875{ 1876 struct scev_info_str *info, pattern; 1877 1878 pattern.var = version; 1879 info = htab_find (cache, &pattern); 1880 1881 if (info) 1882 return info->chrec; 1883 else 1884 return NULL_TREE; 1885} 1886 1887/* Sets instantiated value for VERSION to VAL in CACHE. */ 1888 1889static void 1890set_instantiated_value (htab_t cache, tree version, tree val) 1891{ 1892 struct scev_info_str *info, pattern; 1893 PTR *slot; 1894 1895 pattern.var = version; 1896 slot = htab_find_slot (cache, &pattern, INSERT); 1897 1898 if (*slot) 1899 info = *slot; 1900 else 1901 info = *slot = new_scev_info_str (version); 1902 info->chrec = val; 1903} 1904 1905/* Return the closed_loop_phi node for VAR. If there is none, return 1906 NULL_TREE. */ 1907 1908static tree 1909loop_closed_phi_def (tree var) 1910{ 1911 struct loop *loop; 1912 edge exit; 1913 tree phi; 1914 1915 if (var == NULL_TREE 1916 || TREE_CODE (var) != SSA_NAME) 1917 return NULL_TREE; 1918 1919 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var)); 1920 exit = loop->single_exit; 1921 if (!exit) 1922 return NULL_TREE; 1923 1924 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) 1925 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var) 1926 return PHI_RESULT (phi); 1927 1928 return NULL_TREE; 1929} 1930 1931/* Analyze all the parameters of the chrec that were left under a symbolic form, 1932 with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache 1933 of already instantiated values. FLAGS modify the way chrecs are 1934 instantiated. SIZE_EXPR is used for computing the size of the expression to 1935 be instantiated, and to stop if it exceeds some limit. */ 1936 1937/* Values for FLAGS. */ 1938enum 1939{ 1940 INSERT_SUPERLOOP_CHRECS = 1, /* Loop invariants are replaced with chrecs 1941 in outer loops. */ 1942 FOLD_CONVERSIONS = 2 /* The conversions that may wrap in 1943 signed/pointer type are folded, as long as the 1944 value of the chrec is preserved. */ 1945}; 1946 1947static tree 1948instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache, 1949 int size_expr) 1950{ 1951 tree res, op0, op1, op2; 1952 basic_block def_bb; 1953 struct loop *def_loop; 1954 1955 /* Give up if the expression is larger than the MAX that we allow. */ 1956 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 1957 return chrec_dont_know; 1958 1959 if (automatically_generated_chrec_p (chrec) 1960 || is_gimple_min_invariant (chrec)) 1961 return chrec; 1962 1963 switch (TREE_CODE (chrec)) 1964 { 1965 case SSA_NAME: 1966 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec)); 1967 1968 /* A parameter (or loop invariant and we do not want to include 1969 evolutions in outer loops), nothing to do. */ 1970 if (!def_bb 1971 || (!(flags & INSERT_SUPERLOOP_CHRECS) 1972 && !flow_bb_inside_loop_p (loop, def_bb))) 1973 return chrec; 1974 1975 /* We cache the value of instantiated variable to avoid exponential 1976 time complexity due to reevaluations. We also store the convenient 1977 value in the cache in order to prevent infinite recursion -- we do 1978 not want to instantiate the SSA_NAME if it is in a mixer 1979 structure. This is used for avoiding the instantiation of 1980 recursively defined functions, such as: 1981 1982 | a_2 -> {0, +, 1, +, a_2}_1 */ 1983 1984 res = get_instantiated_value (cache, chrec); 1985 if (res) 1986 return res; 1987 1988 /* Store the convenient value for chrec in the structure. If it 1989 is defined outside of the loop, we may just leave it in symbolic 1990 form, otherwise we need to admit that we do not know its behavior 1991 inside the loop. */ 1992 res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know; 1993 set_instantiated_value (cache, chrec, res); 1994 1995 /* To make things even more complicated, instantiate_parameters_1 1996 calls analyze_scalar_evolution that may call # of iterations 1997 analysis that may in turn call instantiate_parameters_1 again. 1998 To prevent the infinite recursion, keep also the bitmap of 1999 ssa names that are being instantiated globally. */ 2000 if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec))) 2001 return res; 2002 2003 def_loop = find_common_loop (loop, def_bb->loop_father); 2004 2005 /* If the analysis yields a parametric chrec, instantiate the 2006 result again. */ 2007 bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); 2008 res = analyze_scalar_evolution (def_loop, chrec); 2009 2010 /* Don't instantiate loop-closed-ssa phi nodes. */ 2011 if (TREE_CODE (res) == SSA_NAME 2012 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL 2013 || (loop_containing_stmt (SSA_NAME_DEF_STMT (res))->depth 2014 > def_loop->depth))) 2015 { 2016 if (res == chrec) 2017 res = loop_closed_phi_def (chrec); 2018 else 2019 res = chrec; 2020 2021 if (res == NULL_TREE) 2022 res = chrec_dont_know; 2023 } 2024 2025 else if (res != chrec_dont_know) 2026 res = instantiate_parameters_1 (loop, res, flags, cache, size_expr); 2027 2028 bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); 2029 2030 /* Store the correct value to the cache. */ 2031 set_instantiated_value (cache, chrec, res); 2032 return res; 2033 2034 case POLYNOMIAL_CHREC: 2035 op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), 2036 flags, cache, size_expr); 2037 if (op0 == chrec_dont_know) 2038 return chrec_dont_know; 2039 2040 op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), 2041 flags, cache, size_expr); 2042 if (op1 == chrec_dont_know) 2043 return chrec_dont_know; 2044 2045 if (CHREC_LEFT (chrec) != op0 2046 || CHREC_RIGHT (chrec) != op1) 2047 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); 2048 return chrec; 2049 2050 case PLUS_EXPR: 2051 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2052 flags, cache, size_expr); 2053 if (op0 == chrec_dont_know) 2054 return chrec_dont_know; 2055 2056 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2057 flags, cache, size_expr); 2058 if (op1 == chrec_dont_know) 2059 return chrec_dont_know; 2060 2061 if (TREE_OPERAND (chrec, 0) != op0 2062 || TREE_OPERAND (chrec, 1) != op1) 2063 chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1); 2064 return chrec; 2065 2066 case MINUS_EXPR: 2067 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2068 flags, cache, size_expr); 2069 if (op0 == chrec_dont_know) 2070 return chrec_dont_know; 2071 2072 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2073 flags, cache, size_expr); 2074 if (op1 == chrec_dont_know) 2075 return chrec_dont_know; 2076 2077 if (TREE_OPERAND (chrec, 0) != op0 2078 || TREE_OPERAND (chrec, 1) != op1) 2079 chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1); 2080 return chrec; 2081 2082 case MULT_EXPR: 2083 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2084 flags, cache, size_expr); 2085 if (op0 == chrec_dont_know) 2086 return chrec_dont_know; 2087 2088 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2089 flags, cache, size_expr); 2090 if (op1 == chrec_dont_know) 2091 return chrec_dont_know; 2092 2093 if (TREE_OPERAND (chrec, 0) != op0 2094 || TREE_OPERAND (chrec, 1) != op1) 2095 chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1); 2096 return chrec; 2097 2098 case NOP_EXPR: 2099 case CONVERT_EXPR: 2100 case NON_LVALUE_EXPR: 2101 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2102 flags, cache, size_expr); 2103 if (op0 == chrec_dont_know) 2104 return chrec_dont_know; 2105 2106 if (flags & FOLD_CONVERSIONS) 2107 { 2108 tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0); 2109 if (tmp) 2110 return tmp; 2111 } 2112 2113 if (op0 == TREE_OPERAND (chrec, 0)) 2114 return chrec; 2115 2116 /* If we used chrec_convert_aggressive, we can no longer assume that 2117 signed chrecs do not overflow, as chrec_convert does, so avoid 2118 calling it in that case. */ 2119 if (flags & FOLD_CONVERSIONS) 2120 return fold_convert (TREE_TYPE (chrec), op0); 2121 2122 return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE); 2123 2124 case SCEV_NOT_KNOWN: 2125 return chrec_dont_know; 2126 2127 case SCEV_KNOWN: 2128 return chrec_known; 2129 2130 default: 2131 break; 2132 } 2133 2134 switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 2135 { 2136 case 3: 2137 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2138 flags, cache, size_expr); 2139 if (op0 == chrec_dont_know) 2140 return chrec_dont_know; 2141 2142 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2143 flags, cache, size_expr); 2144 if (op1 == chrec_dont_know) 2145 return chrec_dont_know; 2146 2147 op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2), 2148 flags, cache, size_expr); 2149 if (op2 == chrec_dont_know) 2150 return chrec_dont_know; 2151 2152 if (op0 == TREE_OPERAND (chrec, 0) 2153 && op1 == TREE_OPERAND (chrec, 1) 2154 && op2 == TREE_OPERAND (chrec, 2)) 2155 return chrec; 2156 2157 return fold_build3 (TREE_CODE (chrec), 2158 TREE_TYPE (chrec), op0, op1, op2); 2159 2160 case 2: 2161 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2162 flags, cache, size_expr); 2163 if (op0 == chrec_dont_know) 2164 return chrec_dont_know; 2165 2166 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2167 flags, cache, size_expr); 2168 if (op1 == chrec_dont_know) 2169 return chrec_dont_know; 2170 2171 if (op0 == TREE_OPERAND (chrec, 0) 2172 && op1 == TREE_OPERAND (chrec, 1)) 2173 return chrec; 2174 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); 2175 2176 case 1: 2177 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2178 flags, cache, size_expr); 2179 if (op0 == chrec_dont_know) 2180 return chrec_dont_know; 2181 if (op0 == TREE_OPERAND (chrec, 0)) 2182 return chrec; 2183 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0); 2184 2185 case 0: 2186 return chrec; 2187 2188 default: 2189 break; 2190 } 2191 2192 /* Too complicated to handle. */ 2193 return chrec_dont_know; 2194} 2195 2196/* Analyze all the parameters of the chrec that were left under a 2197 symbolic form. LOOP is the loop in which symbolic names have to 2198 be analyzed and instantiated. */ 2199 2200tree 2201instantiate_parameters (struct loop *loop, 2202 tree chrec) 2203{ 2204 tree res; 2205 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); 2206 2207 if (dump_file && (dump_flags & TDF_DETAILS)) 2208 { 2209 fprintf (dump_file, "(instantiate_parameters \n"); 2210 fprintf (dump_file, " (loop_nb = %d)\n", loop->num); 2211 fprintf (dump_file, " (chrec = "); 2212 print_generic_expr (dump_file, chrec, 0); 2213 fprintf (dump_file, ")\n"); 2214 } 2215 2216 res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache, 2217 0); 2218 2219 if (dump_file && (dump_flags & TDF_DETAILS)) 2220 { 2221 fprintf (dump_file, " (res = "); 2222 print_generic_expr (dump_file, res, 0); 2223 fprintf (dump_file, "))\n"); 2224 } 2225 2226 htab_delete (cache); 2227 2228 return res; 2229} 2230 2231/* Similar to instantiate_parameters, but does not introduce the 2232 evolutions in outer loops for LOOP invariants in CHREC, and does not 2233 care about causing overflows, as long as they do not affect value 2234 of an expression. */ 2235 2236static tree 2237resolve_mixers (struct loop *loop, tree chrec) 2238{ 2239 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); 2240 tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0); 2241 htab_delete (cache); 2242 return ret; 2243} 2244 2245/* Entry point for the analysis of the number of iterations pass. 2246 This function tries to safely approximate the number of iterations 2247 the loop will run. When this property is not decidable at compile 2248 time, the result is chrec_dont_know. Otherwise the result is 2249 a scalar or a symbolic parameter. 2250 2251 Example of analysis: suppose that the loop has an exit condition: 2252 2253 "if (b > 49) goto end_loop;" 2254 2255 and that in a previous analysis we have determined that the 2256 variable 'b' has an evolution function: 2257 2258 "EF = {23, +, 5}_2". 2259 2260 When we evaluate the function at the point 5, i.e. the value of the 2261 variable 'b' after 5 iterations in the loop, we have EF (5) = 48, 2262 and EF (6) = 53. In this case the value of 'b' on exit is '53' and 2263 the loop body has been executed 6 times. */ 2264 2265tree 2266number_of_iterations_in_loop (struct loop *loop) 2267{ 2268 tree res, type; 2269 edge exit; 2270 struct tree_niter_desc niter_desc; 2271 2272 /* Determine whether the number_of_iterations_in_loop has already 2273 been computed. */ 2274 res = loop->nb_iterations; 2275 if (res) 2276 return res; 2277 res = chrec_dont_know; 2278 2279 if (dump_file && (dump_flags & TDF_DETAILS)) 2280 fprintf (dump_file, "(number_of_iterations_in_loop\n"); 2281 2282 exit = loop->single_exit; 2283 if (!exit) 2284 goto end; 2285 2286 if (!number_of_iterations_exit (loop, exit, &niter_desc, false)) 2287 goto end; 2288 2289 type = TREE_TYPE (niter_desc.niter); 2290 if (integer_nonzerop (niter_desc.may_be_zero)) 2291 res = build_int_cst (type, 0); 2292 else if (integer_zerop (niter_desc.may_be_zero)) 2293 res = niter_desc.niter; 2294 else 2295 res = chrec_dont_know; 2296 2297end: 2298 return set_nb_iterations_in_loop (loop, res); 2299} 2300 2301/* One of the drivers for testing the scalar evolutions analysis. 2302 This function computes the number of iterations for all the loops 2303 from the EXIT_CONDITIONS array. */ 2304 2305static void 2306number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions) 2307{ 2308 unsigned int i; 2309 unsigned nb_chrec_dont_know_loops = 0; 2310 unsigned nb_static_loops = 0; 2311 tree cond; 2312 2313 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) 2314 { 2315 tree res = number_of_iterations_in_loop (loop_containing_stmt (cond)); 2316 if (chrec_contains_undetermined (res)) 2317 nb_chrec_dont_know_loops++; 2318 else 2319 nb_static_loops++; 2320 } 2321 2322 if (dump_file) 2323 { 2324 fprintf (dump_file, "\n(\n"); 2325 fprintf (dump_file, "-----------------------------------------\n"); 2326 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops); 2327 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops); 2328 fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num); 2329 fprintf (dump_file, "-----------------------------------------\n"); 2330 fprintf (dump_file, ")\n\n"); 2331 2332 print_loop_ir (dump_file); 2333 } 2334} 2335 2336 2337 2338/* Counters for the stats. */ 2339 2340struct chrec_stats 2341{ 2342 unsigned nb_chrecs; 2343 unsigned nb_affine; 2344 unsigned nb_affine_multivar; 2345 unsigned nb_higher_poly; 2346 unsigned nb_chrec_dont_know; 2347 unsigned nb_undetermined; 2348}; 2349 2350/* Reset the counters. */ 2351 2352static inline void 2353reset_chrecs_counters (struct chrec_stats *stats) 2354{ 2355 stats->nb_chrecs = 0; 2356 stats->nb_affine = 0; 2357 stats->nb_affine_multivar = 0; 2358 stats->nb_higher_poly = 0; 2359 stats->nb_chrec_dont_know = 0; 2360 stats->nb_undetermined = 0; 2361} 2362 2363/* Dump the contents of a CHREC_STATS structure. */ 2364 2365static void 2366dump_chrecs_stats (FILE *file, struct chrec_stats *stats) 2367{ 2368 fprintf (file, "\n(\n"); 2369 fprintf (file, "-----------------------------------------\n"); 2370 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine); 2371 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar); 2372 fprintf (file, "%d\tdegree greater than 2 polynomials\n", 2373 stats->nb_higher_poly); 2374 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know); 2375 fprintf (file, "-----------------------------------------\n"); 2376 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs); 2377 fprintf (file, "%d\twith undetermined coefficients\n", 2378 stats->nb_undetermined); 2379 fprintf (file, "-----------------------------------------\n"); 2380 fprintf (file, "%d\tchrecs in the scev database\n", 2381 (int) htab_elements (scalar_evolution_info)); 2382 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev); 2383 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev); 2384 fprintf (file, "-----------------------------------------\n"); 2385 fprintf (file, ")\n\n"); 2386} 2387 2388/* Gather statistics about CHREC. */ 2389 2390static void 2391gather_chrec_stats (tree chrec, struct chrec_stats *stats) 2392{ 2393 if (dump_file && (dump_flags & TDF_STATS)) 2394 { 2395 fprintf (dump_file, "(classify_chrec "); 2396 print_generic_expr (dump_file, chrec, 0); 2397 fprintf (dump_file, "\n"); 2398 } 2399 2400 stats->nb_chrecs++; 2401 2402 if (chrec == NULL_TREE) 2403 { 2404 stats->nb_undetermined++; 2405 return; 2406 } 2407 2408 switch (TREE_CODE (chrec)) 2409 { 2410 case POLYNOMIAL_CHREC: 2411 if (evolution_function_is_affine_p (chrec)) 2412 { 2413 if (dump_file && (dump_flags & TDF_STATS)) 2414 fprintf (dump_file, " affine_univariate\n"); 2415 stats->nb_affine++; 2416 } 2417 else if (evolution_function_is_affine_multivariate_p (chrec)) 2418 { 2419 if (dump_file && (dump_flags & TDF_STATS)) 2420 fprintf (dump_file, " affine_multivariate\n"); 2421 stats->nb_affine_multivar++; 2422 } 2423 else 2424 { 2425 if (dump_file && (dump_flags & TDF_STATS)) 2426 fprintf (dump_file, " higher_degree_polynomial\n"); 2427 stats->nb_higher_poly++; 2428 } 2429 2430 break; 2431 2432 default: 2433 break; 2434 } 2435 2436 if (chrec_contains_undetermined (chrec)) 2437 { 2438 if (dump_file && (dump_flags & TDF_STATS)) 2439 fprintf (dump_file, " undetermined\n"); 2440 stats->nb_undetermined++; 2441 } 2442 2443 if (dump_file && (dump_flags & TDF_STATS)) 2444 fprintf (dump_file, ")\n"); 2445} 2446 2447/* One of the drivers for testing the scalar evolutions analysis. 2448 This function analyzes the scalar evolution of all the scalars 2449 defined as loop phi nodes in one of the loops from the 2450 EXIT_CONDITIONS array. 2451 2452 TODO Optimization: A loop is in canonical form if it contains only 2453 a single scalar loop phi node. All the other scalars that have an 2454 evolution in the loop are rewritten in function of this single 2455 index. This allows the parallelization of the loop. */ 2456 2457static void 2458analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions) 2459{ 2460 unsigned int i; 2461 struct chrec_stats stats; 2462 tree cond; 2463 2464 reset_chrecs_counters (&stats); 2465 2466 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) 2467 { 2468 struct loop *loop; 2469 basic_block bb; 2470 tree phi, chrec; 2471 2472 loop = loop_containing_stmt (cond); 2473 bb = loop->header; 2474 2475 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2476 if (is_gimple_reg (PHI_RESULT (phi))) 2477 { 2478 chrec = instantiate_parameters 2479 (loop, 2480 analyze_scalar_evolution (loop, PHI_RESULT (phi))); 2481 2482 if (dump_file && (dump_flags & TDF_STATS)) 2483 gather_chrec_stats (chrec, &stats); 2484 } 2485 } 2486 2487 if (dump_file && (dump_flags & TDF_STATS)) 2488 dump_chrecs_stats (dump_file, &stats); 2489} 2490 2491/* Callback for htab_traverse, gathers information on chrecs in the 2492 hashtable. */ 2493 2494static int 2495gather_stats_on_scev_database_1 (void **slot, void *stats) 2496{ 2497 struct scev_info_str *entry = *slot; 2498 2499 gather_chrec_stats (entry->chrec, stats); 2500 2501 return 1; 2502} 2503 2504/* Classify the chrecs of the whole database. */ 2505 2506void 2507gather_stats_on_scev_database (void) 2508{ 2509 struct chrec_stats stats; 2510 2511 if (!dump_file) 2512 return; 2513 2514 reset_chrecs_counters (&stats); 2515 2516 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1, 2517 &stats); 2518 2519 dump_chrecs_stats (dump_file, &stats); 2520} 2521 2522 2523 2524/* Initializer. */ 2525 2526static void 2527initialize_scalar_evolutions_analyzer (void) 2528{ 2529 /* The elements below are unique. */ 2530 if (chrec_dont_know == NULL_TREE) 2531 { 2532 chrec_not_analyzed_yet = NULL_TREE; 2533 chrec_dont_know = make_node (SCEV_NOT_KNOWN); 2534 chrec_known = make_node (SCEV_KNOWN); 2535 TREE_TYPE (chrec_dont_know) = void_type_node; 2536 TREE_TYPE (chrec_known) = void_type_node; 2537 } 2538} 2539 2540/* Initialize the analysis of scalar evolutions for LOOPS. */ 2541 2542void 2543scev_initialize (struct loops *loops) 2544{ 2545 unsigned i; 2546 current_loops = loops; 2547 2548 scalar_evolution_info = htab_create (100, hash_scev_info, 2549 eq_scev_info, del_scev_info); 2550 already_instantiated = BITMAP_ALLOC (NULL); 2551 2552 initialize_scalar_evolutions_analyzer (); 2553 2554 for (i = 1; i < loops->num; i++) 2555 if (loops->parray[i]) 2556 loops->parray[i]->nb_iterations = NULL_TREE; 2557} 2558 2559/* Cleans up the information cached by the scalar evolutions analysis. */ 2560 2561void 2562scev_reset (void) 2563{ 2564 unsigned i; 2565 struct loop *loop; 2566 2567 if (!scalar_evolution_info || !current_loops) 2568 return; 2569 2570 htab_empty (scalar_evolution_info); 2571 for (i = 1; i < current_loops->num; i++) 2572 { 2573 loop = current_loops->parray[i]; 2574 if (loop) 2575 loop->nb_iterations = NULL_TREE; 2576 } 2577} 2578 2579/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns 2580 its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we 2581 want step to be invariant in LOOP. Otherwise we require it to be an 2582 integer constant. IV->no_overflow is set to true if we are sure the iv cannot 2583 overflow (e.g. because it is computed in signed arithmetics). */ 2584 2585bool 2586simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv, 2587 bool allow_nonconstant_step) 2588{ 2589 basic_block bb = bb_for_stmt (stmt); 2590 tree type, ev; 2591 bool folded_casts; 2592 2593 iv->base = NULL_TREE; 2594 iv->step = NULL_TREE; 2595 iv->no_overflow = false; 2596 2597 type = TREE_TYPE (op); 2598 if (TREE_CODE (type) != INTEGER_TYPE 2599 && TREE_CODE (type) != POINTER_TYPE) 2600 return false; 2601 2602 ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op, 2603 &folded_casts); 2604 if (chrec_contains_undetermined (ev)) 2605 return false; 2606 2607 if (tree_does_not_contain_chrecs (ev) 2608 && !chrec_contains_symbols_defined_in_loop (ev, loop->num)) 2609 { 2610 iv->base = ev; 2611 iv->no_overflow = true; 2612 return true; 2613 } 2614 2615 if (TREE_CODE (ev) != POLYNOMIAL_CHREC 2616 || CHREC_VARIABLE (ev) != (unsigned) loop->num) 2617 return false; 2618 2619 iv->step = CHREC_RIGHT (ev); 2620 if (allow_nonconstant_step) 2621 { 2622 if (tree_contains_chrecs (iv->step, NULL) 2623 || chrec_contains_symbols_defined_in_loop (iv->step, loop->num)) 2624 return false; 2625 } 2626 else if (TREE_CODE (iv->step) != INTEGER_CST) 2627 return false; 2628 2629 iv->base = CHREC_LEFT (ev); 2630 if (tree_contains_chrecs (iv->base, NULL) 2631 || chrec_contains_symbols_defined_in_loop (iv->base, loop->num)) 2632 return false; 2633 2634 iv->no_overflow = (!folded_casts 2635 && !flag_wrapv 2636 && !TYPE_UNSIGNED (type)); 2637 return true; 2638} 2639 2640/* Runs the analysis of scalar evolutions. */ 2641 2642void 2643scev_analysis (void) 2644{ 2645 VEC(tree,heap) *exit_conditions; 2646 2647 exit_conditions = VEC_alloc (tree, heap, 37); 2648 select_loops_exit_conditions (current_loops, &exit_conditions); 2649 2650 if (dump_file && (dump_flags & TDF_STATS)) 2651 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions); 2652 2653 number_of_iterations_for_all_loops (&exit_conditions); 2654 VEC_free (tree, heap, exit_conditions); 2655} 2656 2657/* Finalize the scalar evolution analysis. */ 2658 2659void 2660scev_finalize (void) 2661{ 2662 htab_delete (scalar_evolution_info); 2663 BITMAP_FREE (already_instantiated); 2664} 2665 2666/* Returns true if EXPR looks expensive. */ 2667 2668static bool 2669expression_expensive_p (tree expr) 2670{ 2671 return force_expr_to_var_cost (expr) >= target_spill_cost; 2672} 2673 2674/* Replace ssa names for that scev can prove they are constant by the 2675 appropriate constants. Also perform final value replacement in loops, 2676 in case the replacement expressions are cheap. 2677 2678 We only consider SSA names defined by phi nodes; rest is left to the 2679 ordinary constant propagation pass. */ 2680 2681void 2682scev_const_prop (void) 2683{ 2684 basic_block bb; 2685 tree name, phi, next_phi, type, ev; 2686 struct loop *loop, *ex_loop; 2687 bitmap ssa_names_to_remove = NULL; 2688 unsigned i; 2689 2690 if (!current_loops) 2691 return; 2692 2693 FOR_EACH_BB (bb) 2694 { 2695 loop = bb->loop_father; 2696 2697 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2698 { 2699 name = PHI_RESULT (phi); 2700 2701 if (!is_gimple_reg (name)) 2702 continue; 2703 2704 type = TREE_TYPE (name); 2705 2706 if (!POINTER_TYPE_P (type) 2707 && !INTEGRAL_TYPE_P (type)) 2708 continue; 2709 2710 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name)); 2711 if (!is_gimple_min_invariant (ev) 2712 || !may_propagate_copy (name, ev)) 2713 continue; 2714 2715 /* Replace the uses of the name. */ 2716 if (name != ev) 2717 replace_uses_by (name, ev); 2718 2719 if (!ssa_names_to_remove) 2720 ssa_names_to_remove = BITMAP_ALLOC (NULL); 2721 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name)); 2722 } 2723 } 2724 2725 /* Remove the ssa names that were replaced by constants. We do not remove them 2726 directly in the previous cycle, since this invalidates scev cache. */ 2727 if (ssa_names_to_remove) 2728 { 2729 bitmap_iterator bi; 2730 unsigned i; 2731 2732 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi) 2733 { 2734 name = ssa_name (i); 2735 phi = SSA_NAME_DEF_STMT (name); 2736 2737 gcc_assert (TREE_CODE (phi) == PHI_NODE); 2738 remove_phi_node (phi, NULL); 2739 } 2740 2741 BITMAP_FREE (ssa_names_to_remove); 2742 scev_reset (); 2743 } 2744 2745 /* Now the regular final value replacement. */ 2746 for (i = current_loops->num - 1; i > 0; i--) 2747 { 2748 edge exit; 2749 tree def, rslt, ass, niter; 2750 block_stmt_iterator bsi; 2751 2752 loop = current_loops->parray[i]; 2753 if (!loop) 2754 continue; 2755 2756 /* If we do not know exact number of iterations of the loop, we cannot 2757 replace the final value. */ 2758 exit = loop->single_exit; 2759 if (!exit) 2760 continue; 2761 2762 niter = number_of_iterations_in_loop (loop); 2763 if (niter == chrec_dont_know 2764 /* If computing the number of iterations is expensive, it may be 2765 better not to introduce computations involving it. */ 2766 || expression_expensive_p (niter)) 2767 continue; 2768 2769 /* Ensure that it is possible to insert new statements somewhere. */ 2770 if (!single_pred_p (exit->dest)) 2771 split_loop_exit_edge (exit); 2772 tree_block_label (exit->dest); 2773 bsi = bsi_after_labels (exit->dest); 2774 2775 ex_loop = superloop_at_depth (loop, exit->dest->loop_father->depth + 1); 2776 2777 for (phi = phi_nodes (exit->dest); phi; phi = next_phi) 2778 { 2779 next_phi = PHI_CHAIN (phi); 2780 rslt = PHI_RESULT (phi); 2781 def = PHI_ARG_DEF_FROM_EDGE (phi, exit); 2782 if (!is_gimple_reg (def)) 2783 continue; 2784 2785 if (!POINTER_TYPE_P (TREE_TYPE (def)) 2786 && !INTEGRAL_TYPE_P (TREE_TYPE (def))) 2787 continue; 2788 2789 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL); 2790 def = compute_overall_effect_of_inner_loop (ex_loop, def); 2791 if (!tree_does_not_contain_chrecs (def) 2792 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num) 2793 /* Moving the computation from the loop may prolong life range 2794 of some ssa names, which may cause problems if they appear 2795 on abnormal edges. */ 2796 || contains_abnormal_ssa_name_p (def)) 2797 continue; 2798 2799 /* Eliminate the phi node and replace it by a computation outside 2800 the loop. */ 2801 def = unshare_expr (def); 2802 SET_PHI_RESULT (phi, NULL_TREE); 2803 remove_phi_node (phi, NULL_TREE); 2804 2805 ass = build2 (MODIFY_EXPR, void_type_node, rslt, NULL_TREE); 2806 SSA_NAME_DEF_STMT (rslt) = ass; 2807 { 2808 block_stmt_iterator dest = bsi; 2809 bsi_insert_before (&dest, ass, BSI_NEW_STMT); 2810 def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE); 2811 } 2812 TREE_OPERAND (ass, 1) = def; 2813 update_stmt (ass); 2814 } 2815 } 2816} 2817