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