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