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