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