tree-scalar-evolution.c revision 256281
1263936Sbr/* Scalar evolution detector. 2263936Sbr Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc. 3263936Sbr Contributed by Sebastian Pop <s.pop@laposte.net> 4263936Sbr 5263936SbrThis file is part of GCC. 6263936Sbr 7263936SbrGCC is free software; you can redistribute it and/or modify it under 8263936Sbrthe terms of the GNU General Public License as published by the Free 9263936SbrSoftware Foundation; either version 2, or (at your option) any later 10263936Sbrversion. 11263936Sbr 12263936SbrGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13263936SbrWARRANTY; without even the implied warranty of MERCHANTABILITY or 14263936SbrFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15263936Sbrfor more details. 16263936Sbr 17263936SbrYou should have received a copy of the GNU General Public License 18263936Sbralong with GCC; see the file COPYING. If not, write to the Free 19263936SbrSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20263936Sbr02110-1301, USA. */ 21263936Sbr 22263936Sbr/* 23263936Sbr Description: 24263936Sbr 25263936Sbr This pass analyzes the evolution of scalar variables in loop 26263936Sbr structures. The algorithm is based on the SSA representation, 27263936Sbr and on the loop hierarchy tree. This algorithm is not based on 28263936Sbr the notion of versions of a variable, as it was the case for the 29263936Sbr previous implementations of the scalar evolution algorithm, but 30263936Sbr it assumes that each defined name is unique. 31263936Sbr 32263936Sbr The notation used in this file is called "chains of recurrences", 33263936Sbr and has been proposed by Eugene Zima, Robert Van Engelen, and 34263936Sbr others for describing induction variables in programs. For example 35263936Sbr "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0 36263936Sbr when entering in the loop_1 and has a step 2 in this loop, in other 37263936Sbr words "for (b = 0; b < N; b+=2);". Note that the coefficients of 38263936Sbr this chain of recurrence (or chrec [shrek]) can contain the name of 39263936Sbr other variables, in which case they are called parametric chrecs. 40263936Sbr For example, "b -> {a, +, 2}_1" means that the initial value of "b" 41263936Sbr is the value of "a". In most of the cases these parametric chrecs 42263936Sbr are fully instantiated before their use because symbolic names can 43263936Sbr hide some difficult cases such as self-references described later 44263936Sbr (see the Fibonacci example). 45263936Sbr 46263936Sbr A short sketch of the algorithm is: 47263936Sbr 48263936Sbr Given a scalar variable to be analyzed, follow the SSA edge to 49263936Sbr its definition: 50263936Sbr 51263936Sbr - When the definition is a MODIFY_EXPR: if the right hand side 52263936Sbr (RHS) of the definition cannot be statically analyzed, the answer 53263936Sbr of the analyzer is: "don't know". 54263936Sbr Otherwise, for all the variables that are not yet analyzed in the 55263936Sbr RHS, try to determine their evolution, and finally try to 56263936Sbr evaluate the operation of the RHS that gives the evolution 57263936Sbr function of the analyzed variable. 58263936Sbr 59263936Sbr - When the definition is a condition-phi-node: determine the 60263936Sbr evolution function for all the branches of the phi node, and 61263936Sbr finally merge these evolutions (see chrec_merge). 62263936Sbr 63263936Sbr - When the definition is a loop-phi-node: determine its initial 64263936Sbr condition, that is the SSA edge defined in an outer loop, and 65263936Sbr keep it symbolic. Then determine the SSA edges that are defined 66263936Sbr in the body of the loop. Follow the inner edges until ending on 67263936Sbr another loop-phi-node of the same analyzed loop. If the reached 68263936Sbr loop-phi-node is not the starting loop-phi-node, then we keep 69263936Sbr this definition under a symbolic form. If the reached 70263936Sbr loop-phi-node is the same as the starting one, then we compute a 71263936Sbr symbolic stride on the return path. The result is then the 72263936Sbr symbolic chrec {initial_condition, +, symbolic_stride}_loop. 73263936Sbr 74263936Sbr Examples: 75263936Sbr 76263936Sbr Example 1: Illustration of the basic algorithm. 77263936Sbr 78263936Sbr | a = 3 79263936Sbr | loop_1 80263936Sbr | b = phi (a, c) 81263936Sbr | c = b + 1 82263936Sbr | if (c > 10) exit_loop 83263936Sbr | endloop 84263936Sbr 85263936Sbr Suppose that we want to know the number of iterations of the 86263936Sbr loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We 87263936Sbr ask the scalar evolution analyzer two questions: what's the 88263936Sbr scalar evolution (scev) of "c", and what's the scev of "10". For 89263936Sbr "10" the answer is "10" since it is a scalar constant. For the 90263936Sbr scalar variable "c", it follows the SSA edge to its definition, 91263936Sbr "c = b + 1", and then asks again what's the scev of "b". 92263936Sbr Following the SSA edge, we end on a loop-phi-node "b = phi (a, 93263936Sbr c)", where the initial condition is "a", and the inner loop edge 94263936Sbr is "c". The initial condition is kept under a symbolic form (it 95263936Sbr may be the case that the copy constant propagation has done its 96263936Sbr work and we end with the constant "3" as one of the edges of the 97263936Sbr loop-phi-node). The update edge is followed to the end of the 98263936Sbr loop, and until reaching again the starting loop-phi-node: b -> c 99263936Sbr -> b. At this point we have drawn a path from "b" to "b" from 100263936Sbr which we compute the stride in the loop: in this example it is 101263936Sbr "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now 102263936Sbr that the scev for "b" is known, it is possible to compute the 103263936Sbr scev for "c", that is "c -> {a + 1, +, 1}_1". In order to 104263936Sbr determine the number of iterations in the loop_1, we have to 105263936Sbr instantiate_parameters ({a + 1, +, 1}_1), that gives after some 106263936Sbr more analysis the scev {4, +, 1}_1, or in other words, this is 107263936Sbr the function "f (x) = x + 4", where x is the iteration count of 108263936Sbr the loop_1. Now we have to solve the inequality "x + 4 > 10", 109263936Sbr and take the smallest iteration number for which the loop is 110263936Sbr exited: x = 7. This loop runs from x = 0 to x = 7, and in total 111263936Sbr there are 8 iterations. In terms of loop normalization, we have 112263936Sbr created a variable that is implicitly defined, "x" or just "_1", 113263936Sbr and all the other analyzed scalars of the loop are defined in 114263936Sbr function of this variable: 115263936Sbr 116263936Sbr a -> 3 117263936Sbr b -> {3, +, 1}_1 118263936Sbr c -> {4, +, 1}_1 119263936Sbr 120263936Sbr or in terms of a C program: 121263936Sbr 122263936Sbr | a = 3 123263936Sbr | for (x = 0; x <= 7; x++) 124263936Sbr | { 125263936Sbr | b = x + 3 126263936Sbr | c = x + 4 127263936Sbr | } 128263936Sbr 129263936Sbr Example 2: Illustration of the algorithm on nested loops. 130263936Sbr 131263936Sbr | loop_1 132263936Sbr | a = phi (1, b) 133263936Sbr | c = a + 2 134263936Sbr | loop_2 10 times 135263936Sbr | b = phi (c, d) 136263936Sbr | d = b + 3 137263936Sbr | endloop 138263936Sbr | endloop 139263936Sbr 140263936Sbr For analyzing the scalar evolution of "a", the algorithm follows 141263936Sbr the SSA edge into the loop's body: "a -> b". "b" is an inner 142263936Sbr loop-phi-node, and its analysis as in Example 1, gives: 143263936Sbr 144263936Sbr b -> {c, +, 3}_2 145263936Sbr d -> {c + 3, +, 3}_2 146263936Sbr 147263936Sbr Following the SSA edge for the initial condition, we end on "c = a 148263936Sbr + 2", and then on the starting loop-phi-node "a". From this point, 149263936Sbr the loop stride is computed: back on "c = a + 2" we get a "+2" in 150263936Sbr the loop_1, then on the loop-phi-node "b" we compute the overall 151263936Sbr effect of the inner loop that is "b = c + 30", and we get a "+30" 152263936Sbr in the loop_1. That means that the overall stride in loop_1 is 153263936Sbr equal to "+32", and the result is: 154263936Sbr 155263936Sbr a -> {1, +, 32}_1 156263936Sbr c -> {3, +, 32}_1 157263936Sbr 158263936Sbr Example 3: Higher degree polynomials. 159263936Sbr 160263936Sbr | loop_1 161263936Sbr | a = phi (2, b) 162263936Sbr | c = phi (5, d) 163263936Sbr | b = a + 1 164263936Sbr | d = c + a 165263936Sbr | endloop 166263936Sbr 167263936Sbr a -> {2, +, 1}_1 168263936Sbr b -> {3, +, 1}_1 169263936Sbr c -> {5, +, a}_1 170263936Sbr d -> {5 + a, +, a}_1 171263936Sbr 172263936Sbr instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1 173263936Sbr instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1 174263936Sbr 175263936Sbr Example 4: Lucas, Fibonacci, or mixers in general. 176263936Sbr 177263936Sbr | loop_1 178263936Sbr | a = phi (1, b) 179263936Sbr | c = phi (3, d) 180263936Sbr | b = c 181263936Sbr | d = c + a 182263936Sbr | endloop 183263936Sbr 184263936Sbr a -> (1, c)_1 185263936Sbr c -> {3, +, a}_1 186263936Sbr 187263936Sbr The syntax "(1, c)_1" stands for a PEELED_CHREC that has the 188263936Sbr following semantics: during the first iteration of the loop_1, the 189263936Sbr variable contains the value 1, and then it contains the value "c". 190263936Sbr Note that this syntax is close to the syntax of the loop-phi-node: 191263936Sbr "a -> (1, c)_1" vs. "a = phi (1, c)". 192263936Sbr 193263936Sbr The symbolic chrec representation contains all the semantics of the 194263936Sbr original code. What is more difficult is to use this information. 195263936Sbr 196263936Sbr Example 5: Flip-flops, or exchangers. 197263936Sbr 198263936Sbr | loop_1 199263936Sbr | a = phi (1, b) 200263936Sbr | c = phi (3, d) 201263936Sbr | b = c 202263936Sbr | d = a 203263936Sbr | endloop 204263936Sbr 205263936Sbr a -> (1, c)_1 206263936Sbr c -> (3, a)_1 207263936Sbr 208263936Sbr Based on these symbolic chrecs, it is possible to refine this 209263936Sbr information into the more precise PERIODIC_CHRECs: 210263936Sbr 211263936Sbr a -> |1, 3|_1 212263936Sbr c -> |3, 1|_1 213263936Sbr 214263936Sbr This transformation is not yet implemented. 215263936Sbr 216263936Sbr Further readings: 217263936Sbr 218263936Sbr You can find a more detailed description of the algorithm in: 219263936Sbr http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf 220263936Sbr http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that 221263936Sbr this is a preliminary report and some of the details of the 222263936Sbr algorithm have changed. I'm working on a research report that 223263936Sbr updates the description of the algorithms to reflect the design 224263936Sbr choices used in this implementation. 225263936Sbr 226263936Sbr A set of slides show a high level overview of the algorithm and run 227263936Sbr an example through the scalar evolution analyzer: 228263936Sbr http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf 229263936Sbr 230263936Sbr The slides that I have presented at the GCC Summit'04 are available 231263936Sbr at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf 232263936Sbr*/ 233263936Sbr 234263936Sbr#include "config.h" 235263936Sbr#include "system.h" 236263936Sbr#include "coretypes.h" 237263936Sbr#include "tm.h" 238263936Sbr#include "ggc.h" 239263936Sbr#include "tree.h" 240263936Sbr#include "real.h" 241263936Sbr 242263936Sbr/* These RTL headers are needed for basic-block.h. */ 243263936Sbr#include "rtl.h" 244263936Sbr#include "basic-block.h" 245263936Sbr#include "diagnostic.h" 246263936Sbr#include "tree-flow.h" 247263936Sbr#include "tree-dump.h" 248263936Sbr#include "timevar.h" 249263936Sbr#include "cfgloop.h" 250263936Sbr#include "tree-chrec.h" 251263936Sbr#include "tree-scalar-evolution.h" 252263936Sbr#include "tree-pass.h" 253263936Sbr#include "flags.h" 254263936Sbr#include "params.h" 255263936Sbr 256263936Sbrstatic tree analyze_scalar_evolution_1 (struct loop *, tree, tree); 257263936Sbrstatic tree resolve_mixers (struct loop *, tree); 258263936Sbr 259263936Sbr/* The cached information about a ssa name VAR, claiming that inside LOOP, 260263936Sbr the value of VAR can be expressed as CHREC. */ 261263936Sbr 262263936Sbrstruct scev_info_str 263263936Sbr{ 264263936Sbr tree var; 265263936Sbr tree chrec; 266263936Sbr}; 267263936Sbr 268263936Sbr/* Counters for the scev database. */ 269263936Sbrstatic unsigned nb_set_scev = 0; 270263936Sbrstatic unsigned nb_get_scev = 0; 271263936Sbr 272263936Sbr/* The following trees are unique elements. Thus the comparison of 273263936Sbr another element to these elements should be done on the pointer to 274263936Sbr these trees, and not on their value. */ 275263936Sbr 276263936Sbr/* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */ 277263936Sbrtree chrec_not_analyzed_yet; 278263936Sbr 279263936Sbr/* Reserved to the cases where the analyzer has detected an 280263936Sbr undecidable property at compile time. */ 281263936Sbrtree chrec_dont_know; 282263936Sbr 283263936Sbr/* When the analyzer has detected that a property will never 284263936Sbr happen, then it qualifies it with chrec_known. */ 285263936Sbrtree chrec_known; 286263936Sbr 287263936Sbrstatic bitmap already_instantiated; 288263936Sbr 289263936Sbrstatic htab_t scalar_evolution_info; 290263936Sbr 291263936Sbr 292263936Sbr/* Constructs a new SCEV_INFO_STR structure. */ 293263936Sbr 294263936Sbrstatic inline struct scev_info_str * 295263936Sbrnew_scev_info_str (tree var) 296263936Sbr{ 297263936Sbr struct scev_info_str *res; 298263936Sbr 299263936Sbr res = XNEW (struct scev_info_str); 300263936Sbr res->var = var; 301263936Sbr res->chrec = chrec_not_analyzed_yet; 302263936Sbr 303263936Sbr return res; 304263936Sbr} 305263936Sbr 306263936Sbr/* Computes a hash function for database element ELT. */ 307263936Sbr 308263936Sbrstatic hashval_t 309263936Sbrhash_scev_info (const void *elt) 310263936Sbr{ 311263936Sbr return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var); 312263936Sbr} 313263936Sbr 314263936Sbr/* Compares database elements E1 and E2. */ 315263936Sbr 316263936Sbrstatic int 317263936Sbreq_scev_info (const void *e1, const void *e2) 318263936Sbr{ 319263936Sbr const struct scev_info_str *elt1 = (const struct scev_info_str *) e1; 320263936Sbr const struct scev_info_str *elt2 = (const struct scev_info_str *) e2; 321263936Sbr 322263936Sbr return elt1->var == elt2->var; 323263936Sbr} 324263936Sbr 325263936Sbr/* Deletes database element E. */ 326263936Sbr 327263936Sbrstatic void 328263936Sbrdel_scev_info (void *e) 329263936Sbr{ 330263936Sbr free (e); 331263936Sbr} 332263936Sbr 333263936Sbr/* Get the index corresponding to VAR in the current LOOP. If 334263936Sbr it's the first time we ask for this VAR, then we return 335263936Sbr chrec_not_analyzed_yet for this VAR and return its index. */ 336263936Sbr 337263936Sbrstatic tree * 338263936Sbrfind_var_scev_info (tree var) 339263936Sbr{ 340263936Sbr struct scev_info_str *res; 341263936Sbr struct scev_info_str tmp; 342263936Sbr PTR *slot; 343263936Sbr 344263936Sbr tmp.var = var; 345263936Sbr slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT); 346263936Sbr 347263936Sbr if (!*slot) 348263936Sbr *slot = new_scev_info_str (var); 349263936Sbr res = (struct scev_info_str *) *slot; 350263936Sbr 351263936Sbr return &res->chrec; 352263936Sbr} 353263936Sbr 354263936Sbr/* Return true when CHREC contains symbolic names defined in 355263936Sbr LOOP_NB. */ 356263936Sbr 357263936Sbrbool 358263936Sbrchrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb) 359263936Sbr{ 360263936Sbr if (chrec == NULL_TREE) 361263936Sbr return false; 362263936Sbr 363263936Sbr if (TREE_INVARIANT (chrec)) 364263936Sbr return false; 365263936Sbr 366263936Sbr if (TREE_CODE (chrec) == VAR_DECL 367263936Sbr || TREE_CODE (chrec) == PARM_DECL 368263936Sbr || TREE_CODE (chrec) == FUNCTION_DECL 369263936Sbr || TREE_CODE (chrec) == LABEL_DECL 370263936Sbr || TREE_CODE (chrec) == RESULT_DECL 371263936Sbr || TREE_CODE (chrec) == FIELD_DECL) 372263936Sbr return true; 373263936Sbr 374263936Sbr if (TREE_CODE (chrec) == SSA_NAME) 375263936Sbr { 376263936Sbr tree def = SSA_NAME_DEF_STMT (chrec); 377263936Sbr struct loop *def_loop = loop_containing_stmt (def); 378263936Sbr struct loop *loop = current_loops->parray[loop_nb]; 379263936Sbr 380263936Sbr if (def_loop == NULL) 381263936Sbr return false; 382263936Sbr 383263936Sbr if (loop == def_loop || flow_loop_nested_p (loop, def_loop)) 384263936Sbr return true; 385263936Sbr 386263936Sbr return false; 387263936Sbr } 388263936Sbr 389263936Sbr switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 390263936Sbr { 391263936Sbr case 3: 392263936Sbr if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2), 393263936Sbr loop_nb)) 394263936Sbr return true; 395263936Sbr 396263936Sbr case 2: 397263936Sbr if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1), 398263936Sbr loop_nb)) 399263936Sbr return true; 400263936Sbr 401263936Sbr case 1: 402263936Sbr if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0), 403263936Sbr loop_nb)) 404263936Sbr return true; 405263936Sbr 406263936Sbr default: 407263936Sbr return false; 408263936Sbr } 409263936Sbr} 410263936Sbr 411263936Sbr/* Return true when PHI is a loop-phi-node. */ 412263936Sbr 413263936Sbrstatic bool 414263936Sbrloop_phi_node_p (tree phi) 415263936Sbr{ 416263936Sbr /* The implementation of this function is based on the following 417263936Sbr property: "all the loop-phi-nodes of a loop are contained in the 418263936Sbr loop's header basic block". */ 419263936Sbr 420263936Sbr return loop_containing_stmt (phi)->header == bb_for_stmt (phi); 421263936Sbr} 422263936Sbr 423263936Sbr/* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP. 424263936Sbr In general, in the case of multivariate evolutions we want to get 425263936Sbr the evolution in different loops. LOOP specifies the level for 426263936Sbr which to get the evolution. 427263936Sbr 428263936Sbr Example: 429263936Sbr 430263936Sbr | for (j = 0; j < 100; j++) 431263936Sbr | { 432263936Sbr | for (k = 0; k < 100; k++) 433263936Sbr | { 434263936Sbr | i = k + j; - Here the value of i is a function of j, k. 435263936Sbr | } 436263936Sbr | ... = i - Here the value of i is a function of j. 437263936Sbr | } 438263936Sbr | ... = i - Here the value of i is a scalar. 439263936Sbr 440263936Sbr Example: 441263936Sbr 442263936Sbr | i_0 = ... 443263936Sbr | loop_1 10 times 444263936Sbr | i_1 = phi (i_0, i_2) 445263936Sbr | i_2 = i_1 + 2 446263936Sbr | endloop 447263936Sbr 448263936Sbr This loop has the same effect as: 449263936Sbr LOOP_1 has the same effect as: 450263936Sbr 451263936Sbr | i_1 = i_0 + 20 452263936Sbr 453263936Sbr The overall effect of the loop, "i_0 + 20" in the previous example, 454263936Sbr is obtained by passing in the parameters: LOOP = 1, 455263936Sbr EVOLUTION_FN = {i_0, +, 2}_1. 456263936Sbr*/ 457263936Sbr 458263936Sbrstatic tree 459263936Sbrcompute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) 460263936Sbr{ 461263936Sbr bool val = false; 462263936Sbr 463263936Sbr if (evolution_fn == chrec_dont_know) 464263936Sbr return chrec_dont_know; 465263936Sbr 466263936Sbr else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC) 467263936Sbr { 468263936Sbr if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num) 469263936Sbr { 470263936Sbr struct loop *inner_loop = 471263936Sbr current_loops->parray[CHREC_VARIABLE (evolution_fn)]; 472263936Sbr tree nb_iter = number_of_iterations_in_loop (inner_loop); 473263936Sbr 474263936Sbr if (nb_iter == chrec_dont_know) 475263936Sbr return chrec_dont_know; 476263936Sbr else 477263936Sbr { 478263936Sbr tree res; 479263936Sbr tree type = chrec_type (nb_iter); 480263936Sbr 481263936Sbr /* Number of iterations is off by one (the ssa name we 482263936Sbr analyze must be defined before the exit). */ 483263936Sbr nb_iter = chrec_fold_minus (type, nb_iter, 484263936Sbr build_int_cst (type, 1)); 485263936Sbr 486263936Sbr /* evolution_fn is the evolution function in LOOP. Get 487263936Sbr its value in the nb_iter-th iteration. */ 488263936Sbr res = chrec_apply (inner_loop->num, evolution_fn, nb_iter); 489263936Sbr 490263936Sbr /* Continue the computation until ending on a parent of LOOP. */ 491263936Sbr return compute_overall_effect_of_inner_loop (loop, res); 492263936Sbr } 493263936Sbr } 494263936Sbr else 495263936Sbr return evolution_fn; 496263936Sbr } 497263936Sbr 498263936Sbr /* If the evolution function is an invariant, there is nothing to do. */ 499263936Sbr else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val) 500263936Sbr return evolution_fn; 501263936Sbr 502263936Sbr else 503263936Sbr return chrec_dont_know; 504263936Sbr} 505263936Sbr 506263936Sbr/* Determine whether the CHREC is always positive/negative. If the expression 507263936Sbr cannot be statically analyzed, return false, otherwise set the answer into 508263936Sbr VALUE. */ 509263936Sbr 510263936Sbrbool 511263936Sbrchrec_is_positive (tree chrec, bool *value) 512263936Sbr{ 513263936Sbr bool value0, value1, value2; 514263936Sbr tree type, end_value, nb_iter; 515263936Sbr 516263936Sbr switch (TREE_CODE (chrec)) 517263936Sbr { 518263936Sbr case POLYNOMIAL_CHREC: 519263936Sbr if (!chrec_is_positive (CHREC_LEFT (chrec), &value0) 520263936Sbr || !chrec_is_positive (CHREC_RIGHT (chrec), &value1)) 521263936Sbr return false; 522263936Sbr 523263936Sbr /* FIXME -- overflows. */ 524263936Sbr if (value0 == value1) 525263936Sbr { 526263936Sbr *value = value0; 527263936Sbr return true; 528263936Sbr } 529263936Sbr 530263936Sbr /* Otherwise the chrec is under the form: "{-197, +, 2}_1", 531263936Sbr and the proof consists in showing that the sign never 532263936Sbr changes during the execution of the loop, from 0 to 533263936Sbr loop->nb_iterations. */ 534263936Sbr if (!evolution_function_is_affine_p (chrec)) 535263936Sbr return false; 536263936Sbr 537263936Sbr nb_iter = number_of_iterations_in_loop 538263936Sbr (current_loops->parray[CHREC_VARIABLE (chrec)]); 539263936Sbr 540263936Sbr if (chrec_contains_undetermined (nb_iter)) 541263936Sbr return false; 542263936Sbr 543263936Sbr type = chrec_type (nb_iter); 544263936Sbr nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1)); 545263936Sbr 546263936Sbr#if 0 547263936Sbr /* TODO -- If the test is after the exit, we may decrease the number of 548263936Sbr iterations by one. */ 549263936Sbr if (after_exit) 550263936Sbr nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1)); 551263936Sbr#endif 552263936Sbr 553263936Sbr end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter); 554263936Sbr 555263936Sbr if (!chrec_is_positive (end_value, &value2)) 556263936Sbr return false; 557263936Sbr 558263936Sbr *value = value0; 559263936Sbr return value0 == value1; 560263936Sbr 561263936Sbr case INTEGER_CST: 562263936Sbr *value = (tree_int_cst_sgn (chrec) == 1); 563263936Sbr return true; 564263936Sbr 565263936Sbr default: 566263936Sbr return false; 567263936Sbr } 568263936Sbr} 569263936Sbr 570263936Sbr/* Associate CHREC to SCALAR. */ 571263936Sbr 572263936Sbrstatic void 573263936Sbrset_scalar_evolution (tree scalar, tree chrec) 574263936Sbr{ 575263936Sbr tree *scalar_info; 576263936Sbr 577263936Sbr if (TREE_CODE (scalar) != SSA_NAME) 578263936Sbr return; 579263936Sbr 580263936Sbr scalar_info = find_var_scev_info (scalar); 581263936Sbr 582263936Sbr if (dump_file) 583263936Sbr { 584263936Sbr if (dump_flags & TDF_DETAILS) 585263936Sbr { 586263936Sbr fprintf (dump_file, "(set_scalar_evolution \n"); 587263936Sbr fprintf (dump_file, " (scalar = "); 588263936Sbr print_generic_expr (dump_file, scalar, 0); 589263936Sbr fprintf (dump_file, ")\n (scalar_evolution = "); 590263936Sbr print_generic_expr (dump_file, chrec, 0); 591263936Sbr fprintf (dump_file, "))\n"); 592263936Sbr } 593263936Sbr if (dump_flags & TDF_STATS) 594263936Sbr nb_set_scev++; 595263936Sbr } 596263936Sbr 597263936Sbr *scalar_info = chrec; 598263936Sbr} 599263936Sbr 600263936Sbr/* Retrieve the chrec associated to SCALAR in the LOOP. */ 601263936Sbr 602263936Sbrstatic tree 603263936Sbrget_scalar_evolution (tree scalar) 604263936Sbr{ 605263936Sbr tree res; 606263936Sbr 607263936Sbr if (dump_file) 608263936Sbr { 609263936Sbr if (dump_flags & TDF_DETAILS) 610263936Sbr { 611263936Sbr fprintf (dump_file, "(get_scalar_evolution \n"); 612263936Sbr fprintf (dump_file, " (scalar = "); 613263936Sbr print_generic_expr (dump_file, scalar, 0); 614263936Sbr fprintf (dump_file, ")\n"); 615263936Sbr } 616263936Sbr if (dump_flags & TDF_STATS) 617263936Sbr nb_get_scev++; 618263936Sbr } 619263936Sbr 620263936Sbr switch (TREE_CODE (scalar)) 621263936Sbr { 622263936Sbr case SSA_NAME: 623263936Sbr res = *find_var_scev_info (scalar); 624263936Sbr break; 625263936Sbr 626263936Sbr case REAL_CST: 627263936Sbr case INTEGER_CST: 628263936Sbr res = scalar; 629263936Sbr break; 630263936Sbr 631263936Sbr default: 632263936Sbr res = chrec_not_analyzed_yet; 633263936Sbr break; 634263936Sbr } 635263936Sbr 636263936Sbr if (dump_file && (dump_flags & TDF_DETAILS)) 637263936Sbr { 638263936Sbr fprintf (dump_file, " (scalar_evolution = "); 639263936Sbr print_generic_expr (dump_file, res, 0); 640263936Sbr fprintf (dump_file, "))\n"); 641263936Sbr } 642263936Sbr 643263936Sbr return res; 644263936Sbr} 645263936Sbr 646263936Sbr/* Helper function for add_to_evolution. Returns the evolution 647263936Sbr function for an assignment of the form "a = b + c", where "a" and 648263936Sbr "b" are on the strongly connected component. CHREC_BEFORE is the 649263936Sbr information that we already have collected up to this point. 650263936Sbr TO_ADD is the evolution of "c". 651263936Sbr 652263936Sbr When CHREC_BEFORE has an evolution part in LOOP_NB, add to this 653263936Sbr evolution the expression TO_ADD, otherwise construct an evolution 654263936Sbr part for this loop. */ 655263936Sbr 656263936Sbrstatic tree 657263936Sbradd_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, 658263936Sbr tree at_stmt) 659263936Sbr{ 660263936Sbr tree type, left, right; 661263936Sbr 662263936Sbr switch (TREE_CODE (chrec_before)) 663263936Sbr { 664263936Sbr case POLYNOMIAL_CHREC: 665263936Sbr if (CHREC_VARIABLE (chrec_before) <= loop_nb) 666263936Sbr { 667263936Sbr unsigned var; 668263936Sbr 669263936Sbr type = chrec_type (chrec_before); 670263936Sbr 671263936Sbr /* When there is no evolution part in this loop, build it. */ 672263936Sbr if (CHREC_VARIABLE (chrec_before) < loop_nb) 673263936Sbr { 674263936Sbr var = loop_nb; 675263936Sbr left = chrec_before; 676263936Sbr right = SCALAR_FLOAT_TYPE_P (type) 677263936Sbr ? build_real (type, dconst0) 678263936Sbr : build_int_cst (type, 0); 679263936Sbr } 680263936Sbr else 681263936Sbr { 682263936Sbr var = CHREC_VARIABLE (chrec_before); 683263936Sbr left = CHREC_LEFT (chrec_before); 684263936Sbr right = CHREC_RIGHT (chrec_before); 685263936Sbr } 686263936Sbr 687263936Sbr to_add = chrec_convert (type, to_add, at_stmt); 688263936Sbr right = chrec_convert (type, right, at_stmt); 689263936Sbr right = chrec_fold_plus (type, right, to_add); 690263936Sbr return build_polynomial_chrec (var, left, right); 691263936Sbr } 692263936Sbr else 693263936Sbr { 694263936Sbr /* Search the evolution in LOOP_NB. */ 695263936Sbr left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), 696263936Sbr to_add, at_stmt); 697263936Sbr right = CHREC_RIGHT (chrec_before); 698263936Sbr right = chrec_convert (chrec_type (left), right, at_stmt); 699263936Sbr return build_polynomial_chrec (CHREC_VARIABLE (chrec_before), 700263936Sbr left, right); 701263936Sbr } 702263936Sbr 703263936Sbr default: 704263936Sbr /* These nodes do not depend on a loop. */ 705263936Sbr if (chrec_before == chrec_dont_know) 706263936Sbr return chrec_dont_know; 707263936Sbr 708263936Sbr left = chrec_before; 709263936Sbr right = chrec_convert (chrec_type (left), to_add, at_stmt); 710263936Sbr return build_polynomial_chrec (loop_nb, left, right); 711263936Sbr } 712263936Sbr} 713263936Sbr 714263936Sbr/* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension 715263936Sbr of LOOP_NB. 716263936Sbr 717263936Sbr Description (provided for completeness, for those who read code in 718263936Sbr a plane, and for my poor 62 bytes brain that would have forgotten 719263936Sbr all this in the next two or three months): 720263936Sbr 721263936Sbr The algorithm of translation of programs from the SSA representation 722263936Sbr into the chrecs syntax is based on a pattern matching. After having 723263936Sbr reconstructed the overall tree expression for a loop, there are only 724263936Sbr two cases that can arise: 725263936Sbr 726263936Sbr 1. a = loop-phi (init, a + expr) 727263936Sbr 2. a = loop-phi (init, expr) 728263936Sbr 729263936Sbr where EXPR is either a scalar constant with respect to the analyzed 730263936Sbr loop (this is a degree 0 polynomial), or an expression containing 731263936Sbr other loop-phi definitions (these are higher degree polynomials). 732263936Sbr 733263936Sbr Examples: 734263936Sbr 735263936Sbr 1. 736263936Sbr | init = ... 737263936Sbr | loop_1 738263936Sbr | a = phi (init, a + 5) 739263936Sbr | endloop 740263936Sbr 741263936Sbr 2. 742263936Sbr | inita = ... 743263936Sbr | initb = ... 744263936Sbr | loop_1 745263936Sbr | a = phi (inita, 2 * b + 3) 746263936Sbr | b = phi (initb, b + 1) 747263936Sbr | endloop 748263936Sbr 749263936Sbr For the first case, the semantics of the SSA representation is: 750263936Sbr 751263936Sbr | a (x) = init + \sum_{j = 0}^{x - 1} expr (j) 752263936Sbr 753263936Sbr that is, there is a loop index "x" that determines the scalar value 754263936Sbr of the variable during the loop execution. During the first 755263936Sbr iteration, the value is that of the initial condition INIT, while 756263936Sbr during the subsequent iterations, it is the sum of the initial 757263936Sbr condition with the sum of all the values of EXPR from the initial 758263936Sbr iteration to the before last considered iteration. 759263936Sbr 760263936Sbr For the second case, the semantics of the SSA program is: 761263936Sbr 762263936Sbr | a (x) = init, if x = 0; 763263936Sbr | expr (x - 1), otherwise. 764263936Sbr 765263936Sbr The second case corresponds to the PEELED_CHREC, whose syntax is 766263936Sbr close to the syntax of a loop-phi-node: 767263936Sbr 768263936Sbr | phi (init, expr) vs. (init, expr)_x 769263936Sbr 770263936Sbr The proof of the translation algorithm for the first case is a 771263936Sbr proof by structural induction based on the degree of EXPR. 772263936Sbr 773263936Sbr Degree 0: 774263936Sbr When EXPR is a constant with respect to the analyzed loop, or in 775263936Sbr other words when EXPR is a polynomial of degree 0, the evolution of 776263936Sbr the variable A in the loop is an affine function with an initial 777263936Sbr condition INIT, and a step EXPR. In order to show this, we start 778263936Sbr from the semantics of the SSA representation: 779263936Sbr 780263936Sbr f (x) = init + \sum_{j = 0}^{x - 1} expr (j) 781263936Sbr 782263936Sbr and since "expr (j)" is a constant with respect to "j", 783263936Sbr 784263936Sbr f (x) = init + x * expr 785263936Sbr 786263936Sbr Finally, based on the semantics of the pure sum chrecs, by 787263936Sbr identification we get the corresponding chrecs syntax: 788263936Sbr 789263936Sbr f (x) = init * \binom{x}{0} + expr * \binom{x}{1} 790263936Sbr f (x) -> {init, +, expr}_x 791263936Sbr 792 Higher degree: 793 Suppose that EXPR is a polynomial of degree N with respect to the 794 analyzed loop_x for which we have already determined that it is 795 written under the chrecs syntax: 796 797 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x) 798 799 We start from the semantics of the SSA program: 800 801 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j) 802 | 803 | f (x) = init + \sum_{j = 0}^{x - 1} 804 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1}) 805 | 806 | f (x) = init + \sum_{j = 0}^{x - 1} 807 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k}) 808 | 809 | f (x) = init + \sum_{k = 0}^{n - 1} 810 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k}) 811 | 812 | f (x) = init + \sum_{k = 0}^{n - 1} 813 | (b_k * \binom{x}{k + 1}) 814 | 815 | f (x) = init + b_0 * \binom{x}{1} + ... 816 | + b_{n-1} * \binom{x}{n} 817 | 818 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ... 819 | + b_{n-1} * \binom{x}{n} 820 | 821 822 And finally from the definition of the chrecs syntax, we identify: 823 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x 824 825 This shows the mechanism that stands behind the add_to_evolution 826 function. An important point is that the use of symbolic 827 parameters avoids the need of an analysis schedule. 828 829 Example: 830 831 | inita = ... 832 | initb = ... 833 | loop_1 834 | a = phi (inita, a + 2 + b) 835 | b = phi (initb, b + 1) 836 | endloop 837 838 When analyzing "a", the algorithm keeps "b" symbolically: 839 840 | a -> {inita, +, 2 + b}_1 841 842 Then, after instantiation, the analyzer ends on the evolution: 843 844 | a -> {inita, +, 2 + initb, +, 1}_1 845 846*/ 847 848static tree 849add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, 850 tree to_add, tree at_stmt) 851{ 852 tree type = chrec_type (to_add); 853 tree res = NULL_TREE; 854 855 if (to_add == NULL_TREE) 856 return chrec_before; 857 858 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not 859 instantiated at this point. */ 860 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC) 861 /* This should not happen. */ 862 return chrec_dont_know; 863 864 if (dump_file && (dump_flags & TDF_DETAILS)) 865 { 866 fprintf (dump_file, "(add_to_evolution \n"); 867 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb); 868 fprintf (dump_file, " (chrec_before = "); 869 print_generic_expr (dump_file, chrec_before, 0); 870 fprintf (dump_file, ")\n (to_add = "); 871 print_generic_expr (dump_file, to_add, 0); 872 fprintf (dump_file, ")\n"); 873 } 874 875 if (code == MINUS_EXPR) 876 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type) 877 ? build_real (type, dconstm1) 878 : build_int_cst_type (type, -1)); 879 880 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt); 881 882 if (dump_file && (dump_flags & TDF_DETAILS)) 883 { 884 fprintf (dump_file, " (res = "); 885 print_generic_expr (dump_file, res, 0); 886 fprintf (dump_file, "))\n"); 887 } 888 889 return res; 890} 891 892/* Helper function. */ 893 894static inline tree 895set_nb_iterations_in_loop (struct loop *loop, 896 tree res) 897{ 898 tree type = chrec_type (res); 899 900 res = chrec_fold_plus (type, res, build_int_cst (type, 1)); 901 902 /* FIXME HWI: However we want to store one iteration less than the 903 count of the loop in order to be compatible with the other 904 nb_iter computations in loop-iv. This also allows the 905 representation of nb_iters that are equal to MAX_INT. */ 906 if (TREE_CODE (res) == INTEGER_CST 907 && (TREE_INT_CST_LOW (res) == 0 908 || TREE_OVERFLOW (res))) 909 res = chrec_dont_know; 910 911 if (dump_file && (dump_flags & TDF_DETAILS)) 912 { 913 fprintf (dump_file, " (set_nb_iterations_in_loop = "); 914 print_generic_expr (dump_file, res, 0); 915 fprintf (dump_file, "))\n"); 916 } 917 918 loop->nb_iterations = res; 919 return res; 920} 921 922 923 924/* This section selects the loops that will be good candidates for the 925 scalar evolution analysis. For the moment, greedily select all the 926 loop nests we could analyze. */ 927 928/* Return true when it is possible to analyze the condition expression 929 EXPR. */ 930 931static bool 932analyzable_condition (tree expr) 933{ 934 tree condition; 935 936 if (TREE_CODE (expr) != COND_EXPR) 937 return false; 938 939 condition = TREE_OPERAND (expr, 0); 940 941 switch (TREE_CODE (condition)) 942 { 943 case SSA_NAME: 944 return true; 945 946 case LT_EXPR: 947 case LE_EXPR: 948 case GT_EXPR: 949 case GE_EXPR: 950 case EQ_EXPR: 951 case NE_EXPR: 952 return true; 953 954 default: 955 return false; 956 } 957 958 return false; 959} 960 961/* For a loop with a single exit edge, return the COND_EXPR that 962 guards the exit edge. If the expression is too difficult to 963 analyze, then give up. */ 964 965tree 966get_loop_exit_condition (struct loop *loop) 967{ 968 tree res = NULL_TREE; 969 edge exit_edge = loop->single_exit; 970 971 972 if (dump_file && (dump_flags & TDF_DETAILS)) 973 fprintf (dump_file, "(get_loop_exit_condition \n "); 974 975 if (exit_edge) 976 { 977 tree expr; 978 979 expr = last_stmt (exit_edge->src); 980 if (analyzable_condition (expr)) 981 res = expr; 982 } 983 984 if (dump_file && (dump_flags & TDF_DETAILS)) 985 { 986 print_generic_expr (dump_file, res, 0); 987 fprintf (dump_file, ")\n"); 988 } 989 990 return res; 991} 992 993/* Recursively determine and enqueue the exit conditions for a loop. */ 994 995static void 996get_exit_conditions_rec (struct loop *loop, 997 VEC(tree,heap) **exit_conditions) 998{ 999 if (!loop) 1000 return; 1001 1002 /* Recurse on the inner loops, then on the next (sibling) loops. */ 1003 get_exit_conditions_rec (loop->inner, exit_conditions); 1004 get_exit_conditions_rec (loop->next, exit_conditions); 1005 1006 if (loop->single_exit) 1007 { 1008 tree loop_condition = get_loop_exit_condition (loop); 1009 1010 if (loop_condition) 1011 VEC_safe_push (tree, heap, *exit_conditions, loop_condition); 1012 } 1013} 1014 1015/* Select the candidate loop nests for the analysis. This function 1016 initializes the EXIT_CONDITIONS array. */ 1017 1018static void 1019select_loops_exit_conditions (struct loops *loops, 1020 VEC(tree,heap) **exit_conditions) 1021{ 1022 struct loop *function_body = loops->parray[0]; 1023 1024 get_exit_conditions_rec (function_body->inner, exit_conditions); 1025} 1026 1027 1028/* Depth first search algorithm. */ 1029 1030typedef enum t_bool { 1031 t_false, 1032 t_true, 1033 t_dont_know 1034} t_bool; 1035 1036 1037static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int); 1038 1039/* Follow the ssa edge into the right hand side RHS of an assignment. 1040 Return true if the strongly connected component has been found. */ 1041 1042static t_bool 1043follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs, 1044 tree halting_phi, tree *evolution_of_loop, int limit) 1045{ 1046 t_bool res = t_false; 1047 tree rhs0, rhs1; 1048 tree type_rhs = TREE_TYPE (rhs); 1049 tree evol; 1050 1051 /* The RHS is one of the following cases: 1052 - an SSA_NAME, 1053 - an INTEGER_CST, 1054 - a PLUS_EXPR, 1055 - a MINUS_EXPR, 1056 - an ASSERT_EXPR, 1057 - other cases are not yet handled. */ 1058 switch (TREE_CODE (rhs)) 1059 { 1060 case NOP_EXPR: 1061 /* This assignment is under the form "a_1 = (cast) rhs. */ 1062 res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0), 1063 halting_phi, evolution_of_loop, limit); 1064 *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), 1065 *evolution_of_loop, at_stmt); 1066 break; 1067 1068 case INTEGER_CST: 1069 /* This assignment is under the form "a_1 = 7". */ 1070 res = t_false; 1071 break; 1072 1073 case SSA_NAME: 1074 /* This assignment is under the form: "a_1 = b_2". */ 1075 res = follow_ssa_edge 1076 (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit); 1077 break; 1078 1079 case PLUS_EXPR: 1080 /* This case is under the form "rhs0 + rhs1". */ 1081 rhs0 = TREE_OPERAND (rhs, 0); 1082 rhs1 = TREE_OPERAND (rhs, 1); 1083 STRIP_TYPE_NOPS (rhs0); 1084 STRIP_TYPE_NOPS (rhs1); 1085 1086 if (TREE_CODE (rhs0) == SSA_NAME) 1087 { 1088 if (TREE_CODE (rhs1) == SSA_NAME) 1089 { 1090 /* Match an assignment under the form: 1091 "a = b + c". */ 1092 evol = *evolution_of_loop; 1093 res = follow_ssa_edge 1094 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 1095 &evol, limit); 1096 1097 if (res == t_true) 1098 *evolution_of_loop = add_to_evolution 1099 (loop->num, 1100 chrec_convert (type_rhs, evol, at_stmt), 1101 PLUS_EXPR, rhs1, at_stmt); 1102 1103 else if (res == t_false) 1104 { 1105 res = follow_ssa_edge 1106 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 1107 evolution_of_loop, limit); 1108 1109 if (res == t_true) 1110 *evolution_of_loop = add_to_evolution 1111 (loop->num, 1112 chrec_convert (type_rhs, *evolution_of_loop, at_stmt), 1113 PLUS_EXPR, rhs0, at_stmt); 1114 1115 else if (res == t_dont_know) 1116 *evolution_of_loop = chrec_dont_know; 1117 } 1118 1119 else if (res == t_dont_know) 1120 *evolution_of_loop = chrec_dont_know; 1121 } 1122 1123 else 1124 { 1125 /* Match an assignment under the form: 1126 "a = b + ...". */ 1127 res = follow_ssa_edge 1128 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 1129 evolution_of_loop, limit); 1130 if (res == t_true) 1131 *evolution_of_loop = add_to_evolution 1132 (loop->num, chrec_convert (type_rhs, *evolution_of_loop, 1133 at_stmt), 1134 PLUS_EXPR, rhs1, at_stmt); 1135 1136 else if (res == t_dont_know) 1137 *evolution_of_loop = chrec_dont_know; 1138 } 1139 } 1140 1141 else if (TREE_CODE (rhs1) == SSA_NAME) 1142 { 1143 /* Match an assignment under the form: 1144 "a = ... + c". */ 1145 res = follow_ssa_edge 1146 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 1147 evolution_of_loop, limit); 1148 if (res == t_true) 1149 *evolution_of_loop = add_to_evolution 1150 (loop->num, chrec_convert (type_rhs, *evolution_of_loop, 1151 at_stmt), 1152 PLUS_EXPR, rhs0, at_stmt); 1153 1154 else if (res == t_dont_know) 1155 *evolution_of_loop = chrec_dont_know; 1156 } 1157 1158 else 1159 /* Otherwise, match an assignment under the form: 1160 "a = ... + ...". */ 1161 /* And there is nothing to do. */ 1162 res = t_false; 1163 1164 break; 1165 1166 case MINUS_EXPR: 1167 /* This case is under the form "opnd0 = rhs0 - rhs1". */ 1168 rhs0 = TREE_OPERAND (rhs, 0); 1169 rhs1 = TREE_OPERAND (rhs, 1); 1170 STRIP_TYPE_NOPS (rhs0); 1171 STRIP_TYPE_NOPS (rhs1); 1172 1173 if (TREE_CODE (rhs0) == SSA_NAME) 1174 { 1175 /* Match an assignment under the form: 1176 "a = b - ...". */ 1177 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 1178 evolution_of_loop, limit); 1179 if (res == t_true) 1180 *evolution_of_loop = add_to_evolution 1181 (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt), 1182 MINUS_EXPR, rhs1, at_stmt); 1183 1184 else if (res == t_dont_know) 1185 *evolution_of_loop = chrec_dont_know; 1186 } 1187 else 1188 /* Otherwise, match an assignment under the form: 1189 "a = ... - ...". */ 1190 /* And there is nothing to do. */ 1191 res = t_false; 1192 1193 break; 1194 1195 case ASSERT_EXPR: 1196 { 1197 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>" 1198 It must be handled as a copy assignment of the form a_1 = a_2. */ 1199 tree op0 = ASSERT_EXPR_VAR (rhs); 1200 if (TREE_CODE (op0) == SSA_NAME) 1201 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0), 1202 halting_phi, evolution_of_loop, limit); 1203 else 1204 res = t_false; 1205 break; 1206 } 1207 1208 1209 default: 1210 res = t_false; 1211 break; 1212 } 1213 1214 return res; 1215} 1216 1217/* Checks whether the I-th argument of a PHI comes from a backedge. */ 1218 1219static bool 1220backedge_phi_arg_p (tree phi, int i) 1221{ 1222 edge e = PHI_ARG_EDGE (phi, i); 1223 1224 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care 1225 about updating it anywhere, and this should work as well most of the 1226 time. */ 1227 if (e->flags & EDGE_IRREDUCIBLE_LOOP) 1228 return true; 1229 1230 return false; 1231} 1232 1233/* Helper function for one branch of the condition-phi-node. Return 1234 true if the strongly connected component has been found following 1235 this path. */ 1236 1237static inline t_bool 1238follow_ssa_edge_in_condition_phi_branch (int i, 1239 struct loop *loop, 1240 tree condition_phi, 1241 tree halting_phi, 1242 tree *evolution_of_branch, 1243 tree init_cond, int limit) 1244{ 1245 tree branch = PHI_ARG_DEF (condition_phi, i); 1246 *evolution_of_branch = chrec_dont_know; 1247 1248 /* Do not follow back edges (they must belong to an irreducible loop, which 1249 we really do not want to worry about). */ 1250 if (backedge_phi_arg_p (condition_phi, i)) 1251 return t_false; 1252 1253 if (TREE_CODE (branch) == SSA_NAME) 1254 { 1255 *evolution_of_branch = init_cond; 1256 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, 1257 evolution_of_branch, limit); 1258 } 1259 1260 /* This case occurs when one of the condition branches sets 1261 the variable to a constant: i.e. a phi-node like 1262 "a_2 = PHI <a_7(5), 2(6)>;". 1263 1264 FIXME: This case have to be refined correctly: 1265 in some cases it is possible to say something better than 1266 chrec_dont_know, for example using a wrap-around notation. */ 1267 return t_false; 1268} 1269 1270/* This function merges the branches of a condition-phi-node in a 1271 loop. */ 1272 1273static t_bool 1274follow_ssa_edge_in_condition_phi (struct loop *loop, 1275 tree condition_phi, 1276 tree halting_phi, 1277 tree *evolution_of_loop, int limit) 1278{ 1279 int i; 1280 tree init = *evolution_of_loop; 1281 tree evolution_of_branch; 1282 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi, 1283 halting_phi, 1284 &evolution_of_branch, 1285 init, limit); 1286 if (res == t_false || res == t_dont_know) 1287 return res; 1288 1289 *evolution_of_loop = evolution_of_branch; 1290 1291 for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++) 1292 { 1293 /* Quickly give up when the evolution of one of the branches is 1294 not known. */ 1295 if (*evolution_of_loop == chrec_dont_know) 1296 return t_true; 1297 1298 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi, 1299 halting_phi, 1300 &evolution_of_branch, 1301 init, limit); 1302 if (res == t_false || res == t_dont_know) 1303 return res; 1304 1305 *evolution_of_loop = chrec_merge (*evolution_of_loop, 1306 evolution_of_branch); 1307 } 1308 1309 return t_true; 1310} 1311 1312/* Follow an SSA edge in an inner loop. It computes the overall 1313 effect of the loop, and following the symbolic initial conditions, 1314 it follows the edges in the parent loop. The inner loop is 1315 considered as a single statement. */ 1316 1317static t_bool 1318follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, 1319 tree loop_phi_node, 1320 tree halting_phi, 1321 tree *evolution_of_loop, int limit) 1322{ 1323 struct loop *loop = loop_containing_stmt (loop_phi_node); 1324 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node)); 1325 1326 /* Sometimes, the inner loop is too difficult to analyze, and the 1327 result of the analysis is a symbolic parameter. */ 1328 if (ev == PHI_RESULT (loop_phi_node)) 1329 { 1330 t_bool res = t_false; 1331 int i; 1332 1333 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) 1334 { 1335 tree arg = PHI_ARG_DEF (loop_phi_node, i); 1336 basic_block bb; 1337 1338 /* Follow the edges that exit the inner loop. */ 1339 bb = PHI_ARG_EDGE (loop_phi_node, i)->src; 1340 if (!flow_bb_inside_loop_p (loop, bb)) 1341 res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, 1342 arg, halting_phi, 1343 evolution_of_loop, limit); 1344 if (res == t_true) 1345 break; 1346 } 1347 1348 /* If the path crosses this loop-phi, give up. */ 1349 if (res == t_true) 1350 *evolution_of_loop = chrec_dont_know; 1351 1352 return res; 1353 } 1354 1355 /* Otherwise, compute the overall effect of the inner loop. */ 1356 ev = compute_overall_effect_of_inner_loop (loop, ev); 1357 return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi, 1358 evolution_of_loop, limit); 1359} 1360 1361/* Follow an SSA edge from a loop-phi-node to itself, constructing a 1362 path that is analyzed on the return walk. */ 1363 1364static t_bool 1365follow_ssa_edge (struct loop *loop, tree def, tree halting_phi, 1366 tree *evolution_of_loop, int limit) 1367{ 1368 struct loop *def_loop; 1369 1370 if (TREE_CODE (def) == NOP_EXPR) 1371 return t_false; 1372 1373 /* Give up if the path is longer than the MAX that we allow. */ 1374 if (limit++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 1375 return t_dont_know; 1376 1377 def_loop = loop_containing_stmt (def); 1378 1379 switch (TREE_CODE (def)) 1380 { 1381 case PHI_NODE: 1382 if (!loop_phi_node_p (def)) 1383 /* DEF is a condition-phi-node. Follow the branches, and 1384 record their evolutions. Finally, merge the collected 1385 information and set the approximation to the main 1386 variable. */ 1387 return follow_ssa_edge_in_condition_phi 1388 (loop, def, halting_phi, evolution_of_loop, limit); 1389 1390 /* When the analyzed phi is the halting_phi, the 1391 depth-first search is over: we have found a path from 1392 the halting_phi to itself in the loop. */ 1393 if (def == halting_phi) 1394 return t_true; 1395 1396 /* Otherwise, the evolution of the HALTING_PHI depends 1397 on the evolution of another loop-phi-node, i.e. the 1398 evolution function is a higher degree polynomial. */ 1399 if (def_loop == loop) 1400 return t_false; 1401 1402 /* Inner loop. */ 1403 if (flow_loop_nested_p (loop, def_loop)) 1404 return follow_ssa_edge_inner_loop_phi 1405 (loop, def, halting_phi, evolution_of_loop, limit); 1406 1407 /* Outer loop. */ 1408 return t_false; 1409 1410 case MODIFY_EXPR: 1411 return follow_ssa_edge_in_rhs (loop, def, 1412 TREE_OPERAND (def, 1), 1413 halting_phi, 1414 evolution_of_loop, limit); 1415 1416 default: 1417 /* At this level of abstraction, the program is just a set 1418 of MODIFY_EXPRs and PHI_NODEs. In principle there is no 1419 other node to be handled. */ 1420 return t_false; 1421 } 1422} 1423 1424 1425 1426/* Given a LOOP_PHI_NODE, this function determines the evolution 1427 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */ 1428 1429static tree 1430analyze_evolution_in_loop (tree loop_phi_node, 1431 tree init_cond) 1432{ 1433 int i; 1434 tree evolution_function = chrec_not_analyzed_yet; 1435 struct loop *loop = loop_containing_stmt (loop_phi_node); 1436 basic_block bb; 1437 1438 if (dump_file && (dump_flags & TDF_DETAILS)) 1439 { 1440 fprintf (dump_file, "(analyze_evolution_in_loop \n"); 1441 fprintf (dump_file, " (loop_phi_node = "); 1442 print_generic_expr (dump_file, loop_phi_node, 0); 1443 fprintf (dump_file, ")\n"); 1444 } 1445 1446 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) 1447 { 1448 tree arg = PHI_ARG_DEF (loop_phi_node, i); 1449 tree ssa_chain, ev_fn; 1450 t_bool res; 1451 1452 /* Select the edges that enter the loop body. */ 1453 bb = PHI_ARG_EDGE (loop_phi_node, i)->src; 1454 if (!flow_bb_inside_loop_p (loop, bb)) 1455 continue; 1456 1457 if (TREE_CODE (arg) == SSA_NAME) 1458 { 1459 ssa_chain = SSA_NAME_DEF_STMT (arg); 1460 1461 /* Pass in the initial condition to the follow edge function. */ 1462 ev_fn = init_cond; 1463 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0); 1464 } 1465 else 1466 res = t_false; 1467 1468 /* When it is impossible to go back on the same 1469 loop_phi_node by following the ssa edges, the 1470 evolution is represented by a peeled chrec, i.e. the 1471 first iteration, EV_FN has the value INIT_COND, then 1472 all the other iterations it has the value of ARG. 1473 For the moment, PEELED_CHREC nodes are not built. */ 1474 if (res != t_true) 1475 ev_fn = chrec_dont_know; 1476 1477 /* When there are multiple back edges of the loop (which in fact never 1478 happens currently, but nevertheless), merge their evolutions. */ 1479 evolution_function = chrec_merge (evolution_function, ev_fn); 1480 } 1481 1482 if (dump_file && (dump_flags & TDF_DETAILS)) 1483 { 1484 fprintf (dump_file, " (evolution_function = "); 1485 print_generic_expr (dump_file, evolution_function, 0); 1486 fprintf (dump_file, "))\n"); 1487 } 1488 1489 return evolution_function; 1490} 1491 1492/* Given a loop-phi-node, return the initial conditions of the 1493 variable on entry of the loop. When the CCP has propagated 1494 constants into the loop-phi-node, the initial condition is 1495 instantiated, otherwise the initial condition is kept symbolic. 1496 This analyzer does not analyze the evolution outside the current 1497 loop, and leaves this task to the on-demand tree reconstructor. */ 1498 1499static tree 1500analyze_initial_condition (tree loop_phi_node) 1501{ 1502 int i; 1503 tree init_cond = chrec_not_analyzed_yet; 1504 struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father; 1505 1506 if (dump_file && (dump_flags & TDF_DETAILS)) 1507 { 1508 fprintf (dump_file, "(analyze_initial_condition \n"); 1509 fprintf (dump_file, " (loop_phi_node = \n"); 1510 print_generic_expr (dump_file, loop_phi_node, 0); 1511 fprintf (dump_file, ")\n"); 1512 } 1513 1514 for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) 1515 { 1516 tree branch = PHI_ARG_DEF (loop_phi_node, i); 1517 basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src; 1518 1519 /* When the branch is oriented to the loop's body, it does 1520 not contribute to the initial condition. */ 1521 if (flow_bb_inside_loop_p (loop, bb)) 1522 continue; 1523 1524 if (init_cond == chrec_not_analyzed_yet) 1525 { 1526 init_cond = branch; 1527 continue; 1528 } 1529 1530 if (TREE_CODE (branch) == SSA_NAME) 1531 { 1532 init_cond = chrec_dont_know; 1533 break; 1534 } 1535 1536 init_cond = chrec_merge (init_cond, branch); 1537 } 1538 1539 /* Ooops -- a loop without an entry??? */ 1540 if (init_cond == chrec_not_analyzed_yet) 1541 init_cond = chrec_dont_know; 1542 1543 if (dump_file && (dump_flags & TDF_DETAILS)) 1544 { 1545 fprintf (dump_file, " (init_cond = "); 1546 print_generic_expr (dump_file, init_cond, 0); 1547 fprintf (dump_file, "))\n"); 1548 } 1549 1550 return init_cond; 1551} 1552 1553/* Analyze the scalar evolution for LOOP_PHI_NODE. */ 1554 1555static tree 1556interpret_loop_phi (struct loop *loop, tree loop_phi_node) 1557{ 1558 tree res; 1559 struct loop *phi_loop = loop_containing_stmt (loop_phi_node); 1560 tree init_cond; 1561 1562 if (phi_loop != loop) 1563 { 1564 struct loop *subloop; 1565 tree evolution_fn = analyze_scalar_evolution 1566 (phi_loop, PHI_RESULT (loop_phi_node)); 1567 1568 /* Dive one level deeper. */ 1569 subloop = superloop_at_depth (phi_loop, loop->depth + 1); 1570 1571 /* Interpret the subloop. */ 1572 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn); 1573 return res; 1574 } 1575 1576 /* Otherwise really interpret the loop phi. */ 1577 init_cond = analyze_initial_condition (loop_phi_node); 1578 res = analyze_evolution_in_loop (loop_phi_node, init_cond); 1579 1580 return res; 1581} 1582 1583/* This function merges the branches of a condition-phi-node, 1584 contained in the outermost loop, and whose arguments are already 1585 analyzed. */ 1586 1587static tree 1588interpret_condition_phi (struct loop *loop, tree condition_phi) 1589{ 1590 int i; 1591 tree res = chrec_not_analyzed_yet; 1592 1593 for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++) 1594 { 1595 tree branch_chrec; 1596 1597 if (backedge_phi_arg_p (condition_phi, i)) 1598 { 1599 res = chrec_dont_know; 1600 break; 1601 } 1602 1603 branch_chrec = analyze_scalar_evolution 1604 (loop, PHI_ARG_DEF (condition_phi, i)); 1605 1606 res = chrec_merge (res, branch_chrec); 1607 } 1608 1609 return res; 1610} 1611 1612/* Interpret the right hand side of a modify_expr OPND1. If we didn't 1613 analyze this node before, follow the definitions until ending 1614 either on an analyzed modify_expr, or on a loop-phi-node. On the 1615 return path, this function propagates evolutions (ala constant copy 1616 propagation). OPND1 is not a GIMPLE expression because we could 1617 analyze the effect of an inner loop: see interpret_loop_phi. */ 1618 1619static tree 1620interpret_rhs_modify_expr (struct loop *loop, tree at_stmt, 1621 tree opnd1, tree type) 1622{ 1623 tree res, opnd10, opnd11, chrec10, chrec11; 1624 1625 if (is_gimple_min_invariant (opnd1)) 1626 return chrec_convert (type, opnd1, at_stmt); 1627 1628 switch (TREE_CODE (opnd1)) 1629 { 1630 case PLUS_EXPR: 1631 opnd10 = TREE_OPERAND (opnd1, 0); 1632 opnd11 = TREE_OPERAND (opnd1, 1); 1633 chrec10 = analyze_scalar_evolution (loop, opnd10); 1634 chrec11 = analyze_scalar_evolution (loop, opnd11); 1635 chrec10 = chrec_convert (type, chrec10, at_stmt); 1636 chrec11 = chrec_convert (type, chrec11, at_stmt); 1637 res = chrec_fold_plus (type, chrec10, chrec11); 1638 break; 1639 1640 case MINUS_EXPR: 1641 opnd10 = TREE_OPERAND (opnd1, 0); 1642 opnd11 = TREE_OPERAND (opnd1, 1); 1643 chrec10 = analyze_scalar_evolution (loop, opnd10); 1644 chrec11 = analyze_scalar_evolution (loop, opnd11); 1645 chrec10 = chrec_convert (type, chrec10, at_stmt); 1646 chrec11 = chrec_convert (type, chrec11, at_stmt); 1647 res = chrec_fold_minus (type, chrec10, chrec11); 1648 break; 1649 1650 case NEGATE_EXPR: 1651 opnd10 = TREE_OPERAND (opnd1, 0); 1652 chrec10 = analyze_scalar_evolution (loop, opnd10); 1653 chrec10 = chrec_convert (type, chrec10, at_stmt); 1654 /* TYPE may be integer, real or complex, so use fold_convert. */ 1655 res = chrec_fold_multiply (type, chrec10, 1656 fold_convert (type, integer_minus_one_node)); 1657 break; 1658 1659 case MULT_EXPR: 1660 opnd10 = TREE_OPERAND (opnd1, 0); 1661 opnd11 = TREE_OPERAND (opnd1, 1); 1662 chrec10 = analyze_scalar_evolution (loop, opnd10); 1663 chrec11 = analyze_scalar_evolution (loop, opnd11); 1664 chrec10 = chrec_convert (type, chrec10, at_stmt); 1665 chrec11 = chrec_convert (type, chrec11, at_stmt); 1666 res = chrec_fold_multiply (type, chrec10, chrec11); 1667 break; 1668 1669 case SSA_NAME: 1670 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1), 1671 at_stmt); 1672 break; 1673 1674 case ASSERT_EXPR: 1675 opnd10 = ASSERT_EXPR_VAR (opnd1); 1676 res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10), 1677 at_stmt); 1678 break; 1679 1680 case NOP_EXPR: 1681 case CONVERT_EXPR: 1682 opnd10 = TREE_OPERAND (opnd1, 0); 1683 chrec10 = analyze_scalar_evolution (loop, opnd10); 1684 res = chrec_convert (type, chrec10, at_stmt); 1685 break; 1686 1687 default: 1688 res = chrec_dont_know; 1689 break; 1690 } 1691 1692 return res; 1693} 1694 1695 1696 1697/* This section contains all the entry points: 1698 - number_of_iterations_in_loop, 1699 - analyze_scalar_evolution, 1700 - instantiate_parameters. 1701*/ 1702 1703/* Compute and return the evolution function in WRTO_LOOP, the nearest 1704 common ancestor of DEF_LOOP and USE_LOOP. */ 1705 1706static tree 1707compute_scalar_evolution_in_loop (struct loop *wrto_loop, 1708 struct loop *def_loop, 1709 tree ev) 1710{ 1711 tree res; 1712 if (def_loop == wrto_loop) 1713 return ev; 1714 1715 def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1); 1716 res = compute_overall_effect_of_inner_loop (def_loop, ev); 1717 1718 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet); 1719} 1720 1721/* Folds EXPR, if it is a cast to pointer, assuming that the created 1722 polynomial_chrec does not wrap. */ 1723 1724static tree 1725fold_used_pointer_cast (tree expr) 1726{ 1727 tree op; 1728 tree type, inner_type; 1729 1730 if (TREE_CODE (expr) != NOP_EXPR && TREE_CODE (expr) != CONVERT_EXPR) 1731 return expr; 1732 1733 op = TREE_OPERAND (expr, 0); 1734 if (TREE_CODE (op) != POLYNOMIAL_CHREC) 1735 return expr; 1736 1737 type = TREE_TYPE (expr); 1738 inner_type = TREE_TYPE (op); 1739 1740 if (!INTEGRAL_TYPE_P (inner_type) 1741 || TYPE_PRECISION (inner_type) != TYPE_PRECISION (type)) 1742 return expr; 1743 1744 return build_polynomial_chrec (CHREC_VARIABLE (op), 1745 chrec_convert (type, CHREC_LEFT (op), NULL_TREE), 1746 chrec_convert (type, CHREC_RIGHT (op), NULL_TREE)); 1747} 1748 1749/* Returns true if EXPR is an expression corresponding to offset of pointer 1750 in p + offset. */ 1751 1752static bool 1753pointer_offset_p (tree expr) 1754{ 1755 if (TREE_CODE (expr) == INTEGER_CST) 1756 return true; 1757 1758 if ((TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR) 1759 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))) 1760 return true; 1761 1762 return false; 1763} 1764 1765/* EXPR is a scalar evolution of a pointer that is dereferenced or used in 1766 comparison. This means that it must point to a part of some object in 1767 memory, which enables us to argue about overflows and possibly simplify 1768 the EXPR. AT_STMT is the statement in which this conversion has to be 1769 performed. Returns the simplified value. 1770 1771 Currently, for 1772 1773 int i, n; 1774 int *p; 1775 1776 for (i = -n; i < n; i++) 1777 *(p + i) = ...; 1778 1779 We generate the following code (assuming that size of int and size_t is 1780 4 bytes): 1781 1782 for (i = -n; i < n; i++) 1783 { 1784 size_t tmp1, tmp2; 1785 int *tmp3, *tmp4; 1786 1787 tmp1 = (size_t) i; (1) 1788 tmp2 = 4 * tmp1; (2) 1789 tmp3 = (int *) tmp2; (3) 1790 tmp4 = p + tmp3; (4) 1791 1792 *tmp4 = ...; 1793 } 1794 1795 We in general assume that pointer arithmetics does not overflow (since its 1796 behavior is undefined in that case). One of the problems is that our 1797 translation does not capture this property very well -- (int *) is 1798 considered unsigned, hence the computation in (4) does overflow if i is 1799 negative. 1800 1801 This impreciseness creates complications in scev analysis. The scalar 1802 evolution of i is [-n, +, 1]. Since int and size_t have the same precision 1803 (in this example), and size_t is unsigned (so we do not care about 1804 overflows), we succeed to derive that scev of tmp1 is [(size_t) -n, +, 1] 1805 and scev of tmp2 is [4 * (size_t) -n, +, 4]. With tmp3, we run into 1806 problem -- [(int *) (4 * (size_t) -n), +, 4] wraps, and since we on several 1807 places assume that this is not the case for scevs with pointer type, we 1808 cannot use this scev for tmp3; hence, its scev is 1809 (int *) [(4 * (size_t) -n), +, 4], and scev of tmp4 is 1810 p + (int *) [(4 * (size_t) -n), +, 4]. Most of the optimizers are unable to 1811 work with scevs of this shape. 1812 1813 However, since tmp4 is dereferenced, all its values must belong to a single 1814 object, and taking into account that the precision of int * and size_t is 1815 the same, it is impossible for its scev to wrap. Hence, we can derive that 1816 its evolution is [p + (int *) (4 * (size_t) -n), +, 4], which the optimizers 1817 can work with. 1818 1819 ??? Maybe we should use different representation for pointer arithmetics, 1820 however that is a long-term project with a lot of potential for creating 1821 bugs. */ 1822 1823static tree 1824fold_used_pointer (tree expr, tree at_stmt) 1825{ 1826 tree op0, op1, new0, new1; 1827 enum tree_code code = TREE_CODE (expr); 1828 1829 if (code == PLUS_EXPR 1830 || code == MINUS_EXPR) 1831 { 1832 op0 = TREE_OPERAND (expr, 0); 1833 op1 = TREE_OPERAND (expr, 1); 1834 1835 if (pointer_offset_p (op1)) 1836 { 1837 new0 = fold_used_pointer (op0, at_stmt); 1838 new1 = fold_used_pointer_cast (op1); 1839 } 1840 else if (code == PLUS_EXPR && pointer_offset_p (op0)) 1841 { 1842 new0 = fold_used_pointer_cast (op0); 1843 new1 = fold_used_pointer (op1, at_stmt); 1844 } 1845 else 1846 return expr; 1847 1848 if (new0 == op0 && new1 == op1) 1849 return expr; 1850 1851 new0 = chrec_convert (TREE_TYPE (expr), new0, at_stmt); 1852 new1 = chrec_convert (TREE_TYPE (expr), new1, at_stmt); 1853 1854 if (code == PLUS_EXPR) 1855 expr = chrec_fold_plus (TREE_TYPE (expr), new0, new1); 1856 else 1857 expr = chrec_fold_minus (TREE_TYPE (expr), new0, new1); 1858 1859 return expr; 1860 } 1861 else 1862 return fold_used_pointer_cast (expr); 1863} 1864 1865/* Returns true if PTR is dereferenced, or used in comparison. */ 1866 1867static bool 1868pointer_used_p (tree ptr) 1869{ 1870 use_operand_p use_p; 1871 imm_use_iterator imm_iter; 1872 tree stmt, rhs; 1873 struct ptr_info_def *pi = get_ptr_info (ptr); 1874 var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr)); 1875 1876 /* Check whether the pointer has a memory tag; if it does, it is 1877 (or at least used to be) dereferenced. */ 1878 if ((pi != NULL && pi->name_mem_tag != NULL) 1879 || v_ann->symbol_mem_tag) 1880 return true; 1881 1882 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, ptr) 1883 { 1884 stmt = USE_STMT (use_p); 1885 if (TREE_CODE (stmt) == COND_EXPR) 1886 return true; 1887 1888 if (TREE_CODE (stmt) != MODIFY_EXPR) 1889 continue; 1890 1891 rhs = TREE_OPERAND (stmt, 1); 1892 if (!COMPARISON_CLASS_P (rhs)) 1893 continue; 1894 1895 if (TREE_OPERAND (stmt, 0) == ptr 1896 || TREE_OPERAND (stmt, 1) == ptr) 1897 return true; 1898 } 1899 1900 return false; 1901} 1902 1903/* Helper recursive function. */ 1904 1905static tree 1906analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) 1907{ 1908 tree def, type = TREE_TYPE (var); 1909 basic_block bb; 1910 struct loop *def_loop; 1911 1912 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE) 1913 return chrec_dont_know; 1914 1915 if (TREE_CODE (var) != SSA_NAME) 1916 return interpret_rhs_modify_expr (loop, NULL_TREE, var, type); 1917 1918 def = SSA_NAME_DEF_STMT (var); 1919 bb = bb_for_stmt (def); 1920 def_loop = bb ? bb->loop_father : NULL; 1921 1922 if (bb == NULL 1923 || !flow_bb_inside_loop_p (loop, bb)) 1924 { 1925 /* Keep the symbolic form. */ 1926 res = var; 1927 goto set_and_end; 1928 } 1929 1930 if (res != chrec_not_analyzed_yet) 1931 { 1932 if (loop != bb->loop_father) 1933 res = compute_scalar_evolution_in_loop 1934 (find_common_loop (loop, bb->loop_father), bb->loop_father, res); 1935 1936 goto set_and_end; 1937 } 1938 1939 if (loop != def_loop) 1940 { 1941 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet); 1942 res = compute_scalar_evolution_in_loop (loop, def_loop, res); 1943 1944 goto set_and_end; 1945 } 1946 1947 switch (TREE_CODE (def)) 1948 { 1949 case MODIFY_EXPR: 1950 res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type); 1951 1952 if (POINTER_TYPE_P (type) 1953 && !automatically_generated_chrec_p (res) 1954 && pointer_used_p (var)) 1955 res = fold_used_pointer (res, def); 1956 break; 1957 1958 case PHI_NODE: 1959 if (loop_phi_node_p (def)) 1960 res = interpret_loop_phi (loop, def); 1961 else 1962 res = interpret_condition_phi (loop, def); 1963 break; 1964 1965 default: 1966 res = chrec_dont_know; 1967 break; 1968 } 1969 1970 set_and_end: 1971 1972 /* Keep the symbolic form. */ 1973 if (res == chrec_dont_know) 1974 res = var; 1975 1976 if (loop == def_loop) 1977 set_scalar_evolution (var, res); 1978 1979 return res; 1980} 1981 1982/* Entry point for the scalar evolution analyzer. 1983 Analyzes and returns the scalar evolution of the ssa_name VAR. 1984 LOOP_NB is the identifier number of the loop in which the variable 1985 is used. 1986 1987 Example of use: having a pointer VAR to a SSA_NAME node, STMT a 1988 pointer to the statement that uses this variable, in order to 1989 determine the evolution function of the variable, use the following 1990 calls: 1991 1992 unsigned loop_nb = loop_containing_stmt (stmt)->num; 1993 tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var); 1994 tree chrec_instantiated = instantiate_parameters 1995 (loop_nb, chrec_with_symbols); 1996*/ 1997 1998tree 1999analyze_scalar_evolution (struct loop *loop, tree var) 2000{ 2001 tree res; 2002 2003 if (dump_file && (dump_flags & TDF_DETAILS)) 2004 { 2005 fprintf (dump_file, "(analyze_scalar_evolution \n"); 2006 fprintf (dump_file, " (loop_nb = %d)\n", loop->num); 2007 fprintf (dump_file, " (scalar = "); 2008 print_generic_expr (dump_file, var, 0); 2009 fprintf (dump_file, ")\n"); 2010 } 2011 2012 res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var)); 2013 2014 if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know) 2015 res = var; 2016 2017 if (dump_file && (dump_flags & TDF_DETAILS)) 2018 fprintf (dump_file, ")\n"); 2019 2020 return res; 2021} 2022 2023/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to 2024 WRTO_LOOP (which should be a superloop of both USE_LOOP and definition 2025 of VERSION). 2026 2027 FOLDED_CASTS is set to true if resolve_mixers used 2028 chrec_convert_aggressive (TODO -- not really, we are way too conservative 2029 at the moment in order to keep things simple). */ 2030 2031static tree 2032analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop, 2033 tree version, bool *folded_casts) 2034{ 2035 bool val = false; 2036 tree ev = version, tmp; 2037 2038 if (folded_casts) 2039 *folded_casts = false; 2040 while (1) 2041 { 2042 tmp = analyze_scalar_evolution (use_loop, ev); 2043 ev = resolve_mixers (use_loop, tmp); 2044 2045 if (folded_casts && tmp != ev) 2046 *folded_casts = true; 2047 2048 if (use_loop == wrto_loop) 2049 return ev; 2050 2051 /* If the value of the use changes in the inner loop, we cannot express 2052 its value in the outer loop (we might try to return interval chrec, 2053 but we do not have a user for it anyway) */ 2054 if (!no_evolution_in_loop_p (ev, use_loop->num, &val) 2055 || !val) 2056 return chrec_dont_know; 2057 2058 use_loop = use_loop->outer; 2059 } 2060} 2061 2062/* Returns instantiated value for VERSION in CACHE. */ 2063 2064static tree 2065get_instantiated_value (htab_t cache, tree version) 2066{ 2067 struct scev_info_str *info, pattern; 2068 2069 pattern.var = version; 2070 info = (struct scev_info_str *) htab_find (cache, &pattern); 2071 2072 if (info) 2073 return info->chrec; 2074 else 2075 return NULL_TREE; 2076} 2077 2078/* Sets instantiated value for VERSION to VAL in CACHE. */ 2079 2080static void 2081set_instantiated_value (htab_t cache, tree version, tree val) 2082{ 2083 struct scev_info_str *info, pattern; 2084 PTR *slot; 2085 2086 pattern.var = version; 2087 slot = htab_find_slot (cache, &pattern, INSERT); 2088 2089 if (!*slot) 2090 *slot = new_scev_info_str (version); 2091 info = (struct scev_info_str *) *slot; 2092 info->chrec = val; 2093} 2094 2095/* Return the closed_loop_phi node for VAR. If there is none, return 2096 NULL_TREE. */ 2097 2098static tree 2099loop_closed_phi_def (tree var) 2100{ 2101 struct loop *loop; 2102 edge exit; 2103 tree phi; 2104 2105 if (var == NULL_TREE 2106 || TREE_CODE (var) != SSA_NAME) 2107 return NULL_TREE; 2108 2109 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var)); 2110 exit = loop->single_exit; 2111 if (!exit) 2112 return NULL_TREE; 2113 2114 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) 2115 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var) 2116 return PHI_RESULT (phi); 2117 2118 return NULL_TREE; 2119} 2120 2121/* Analyze all the parameters of the chrec that were left under a symbolic form, 2122 with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache 2123 of already instantiated values. FLAGS modify the way chrecs are 2124 instantiated. SIZE_EXPR is used for computing the size of the expression to 2125 be instantiated, and to stop if it exceeds some limit. */ 2126 2127/* Values for FLAGS. */ 2128enum 2129{ 2130 INSERT_SUPERLOOP_CHRECS = 1, /* Loop invariants are replaced with chrecs 2131 in outer loops. */ 2132 FOLD_CONVERSIONS = 2 /* The conversions that may wrap in 2133 signed/pointer type are folded, as long as the 2134 value of the chrec is preserved. */ 2135}; 2136 2137static tree 2138instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache, 2139 int size_expr) 2140{ 2141 tree res, op0, op1, op2; 2142 basic_block def_bb; 2143 struct loop *def_loop; 2144 tree type = chrec_type (chrec); 2145 2146 /* Give up if the expression is larger than the MAX that we allow. */ 2147 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 2148 return chrec_dont_know; 2149 2150 if (automatically_generated_chrec_p (chrec) 2151 || is_gimple_min_invariant (chrec)) 2152 return chrec; 2153 2154 switch (TREE_CODE (chrec)) 2155 { 2156 case SSA_NAME: 2157 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec)); 2158 2159 /* A parameter (or loop invariant and we do not want to include 2160 evolutions in outer loops), nothing to do. */ 2161 if (!def_bb 2162 || (!(flags & INSERT_SUPERLOOP_CHRECS) 2163 && !flow_bb_inside_loop_p (loop, def_bb))) 2164 return chrec; 2165 2166 /* We cache the value of instantiated variable to avoid exponential 2167 time complexity due to reevaluations. We also store the convenient 2168 value in the cache in order to prevent infinite recursion -- we do 2169 not want to instantiate the SSA_NAME if it is in a mixer 2170 structure. This is used for avoiding the instantiation of 2171 recursively defined functions, such as: 2172 2173 | a_2 -> {0, +, 1, +, a_2}_1 */ 2174 2175 res = get_instantiated_value (cache, chrec); 2176 if (res) 2177 return res; 2178 2179 /* Store the convenient value for chrec in the structure. If it 2180 is defined outside of the loop, we may just leave it in symbolic 2181 form, otherwise we need to admit that we do not know its behavior 2182 inside the loop. */ 2183 res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know; 2184 set_instantiated_value (cache, chrec, res); 2185 2186 /* To make things even more complicated, instantiate_parameters_1 2187 calls analyze_scalar_evolution that may call # of iterations 2188 analysis that may in turn call instantiate_parameters_1 again. 2189 To prevent the infinite recursion, keep also the bitmap of 2190 ssa names that are being instantiated globally. */ 2191 if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec))) 2192 return res; 2193 2194 def_loop = find_common_loop (loop, def_bb->loop_father); 2195 2196 /* If the analysis yields a parametric chrec, instantiate the 2197 result again. */ 2198 bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); 2199 res = analyze_scalar_evolution (def_loop, chrec); 2200 2201 /* Don't instantiate loop-closed-ssa phi nodes. */ 2202 if (TREE_CODE (res) == SSA_NAME 2203 && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL 2204 || (loop_containing_stmt (SSA_NAME_DEF_STMT (res))->depth 2205 > def_loop->depth))) 2206 { 2207 if (res == chrec) 2208 res = loop_closed_phi_def (chrec); 2209 else 2210 res = chrec; 2211 2212 if (res == NULL_TREE) 2213 res = chrec_dont_know; 2214 } 2215 2216 else if (res != chrec_dont_know) 2217 res = instantiate_parameters_1 (loop, res, flags, cache, size_expr); 2218 2219 bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); 2220 2221 /* Store the correct value to the cache. */ 2222 set_instantiated_value (cache, chrec, res); 2223 return res; 2224 2225 case POLYNOMIAL_CHREC: 2226 op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), 2227 flags, cache, size_expr); 2228 if (op0 == chrec_dont_know) 2229 return chrec_dont_know; 2230 2231 op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), 2232 flags, cache, size_expr); 2233 if (op1 == chrec_dont_know) 2234 return chrec_dont_know; 2235 2236 if (CHREC_LEFT (chrec) != op0 2237 || CHREC_RIGHT (chrec) != op1) 2238 { 2239 op1 = chrec_convert (chrec_type (op0), op1, NULL_TREE); 2240 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); 2241 } 2242 return chrec; 2243 2244 case PLUS_EXPR: 2245 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2246 flags, cache, size_expr); 2247 if (op0 == chrec_dont_know) 2248 return chrec_dont_know; 2249 2250 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2251 flags, cache, size_expr); 2252 if (op1 == chrec_dont_know) 2253 return chrec_dont_know; 2254 2255 if (TREE_OPERAND (chrec, 0) != op0 2256 || TREE_OPERAND (chrec, 1) != op1) 2257 { 2258 op0 = chrec_convert (type, op0, NULL_TREE); 2259 op1 = chrec_convert (type, op1, NULL_TREE); 2260 chrec = chrec_fold_plus (type, op0, op1); 2261 } 2262 return chrec; 2263 2264 case MINUS_EXPR: 2265 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2266 flags, cache, size_expr); 2267 if (op0 == chrec_dont_know) 2268 return chrec_dont_know; 2269 2270 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2271 flags, cache, size_expr); 2272 if (op1 == chrec_dont_know) 2273 return chrec_dont_know; 2274 2275 if (TREE_OPERAND (chrec, 0) != op0 2276 || TREE_OPERAND (chrec, 1) != op1) 2277 { 2278 op0 = chrec_convert (type, op0, NULL_TREE); 2279 op1 = chrec_convert (type, op1, NULL_TREE); 2280 chrec = chrec_fold_minus (type, op0, op1); 2281 } 2282 return chrec; 2283 2284 case MULT_EXPR: 2285 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2286 flags, cache, size_expr); 2287 if (op0 == chrec_dont_know) 2288 return chrec_dont_know; 2289 2290 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2291 flags, cache, size_expr); 2292 if (op1 == chrec_dont_know) 2293 return chrec_dont_know; 2294 2295 if (TREE_OPERAND (chrec, 0) != op0 2296 || TREE_OPERAND (chrec, 1) != op1) 2297 { 2298 op0 = chrec_convert (type, op0, NULL_TREE); 2299 op1 = chrec_convert (type, op1, NULL_TREE); 2300 chrec = chrec_fold_multiply (type, op0, op1); 2301 } 2302 return chrec; 2303 2304 case NOP_EXPR: 2305 case CONVERT_EXPR: 2306 case NON_LVALUE_EXPR: 2307 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2308 flags, cache, size_expr); 2309 if (op0 == chrec_dont_know) 2310 return chrec_dont_know; 2311 2312 if (flags & FOLD_CONVERSIONS) 2313 { 2314 tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0); 2315 if (tmp) 2316 return tmp; 2317 } 2318 2319 if (op0 == TREE_OPERAND (chrec, 0)) 2320 return chrec; 2321 2322 /* If we used chrec_convert_aggressive, we can no longer assume that 2323 signed chrecs do not overflow, as chrec_convert does, so avoid 2324 calling it in that case. */ 2325 if (flags & FOLD_CONVERSIONS) 2326 return fold_convert (TREE_TYPE (chrec), op0); 2327 2328 return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE); 2329 2330 case SCEV_NOT_KNOWN: 2331 return chrec_dont_know; 2332 2333 case SCEV_KNOWN: 2334 return chrec_known; 2335 2336 default: 2337 break; 2338 } 2339 2340 switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 2341 { 2342 case 3: 2343 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2344 flags, cache, size_expr); 2345 if (op0 == chrec_dont_know) 2346 return chrec_dont_know; 2347 2348 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2349 flags, cache, size_expr); 2350 if (op1 == chrec_dont_know) 2351 return chrec_dont_know; 2352 2353 op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2), 2354 flags, cache, size_expr); 2355 if (op2 == chrec_dont_know) 2356 return chrec_dont_know; 2357 2358 if (op0 == TREE_OPERAND (chrec, 0) 2359 && op1 == TREE_OPERAND (chrec, 1) 2360 && op2 == TREE_OPERAND (chrec, 2)) 2361 return chrec; 2362 2363 return fold_build3 (TREE_CODE (chrec), 2364 TREE_TYPE (chrec), op0, op1, op2); 2365 2366 case 2: 2367 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2368 flags, cache, size_expr); 2369 if (op0 == chrec_dont_know) 2370 return chrec_dont_know; 2371 2372 op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2373 flags, cache, size_expr); 2374 if (op1 == chrec_dont_know) 2375 return chrec_dont_know; 2376 2377 if (op0 == TREE_OPERAND (chrec, 0) 2378 && op1 == TREE_OPERAND (chrec, 1)) 2379 return chrec; 2380 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); 2381 2382 case 1: 2383 op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2384 flags, cache, size_expr); 2385 if (op0 == chrec_dont_know) 2386 return chrec_dont_know; 2387 if (op0 == TREE_OPERAND (chrec, 0)) 2388 return chrec; 2389 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0); 2390 2391 case 0: 2392 return chrec; 2393 2394 default: 2395 break; 2396 } 2397 2398 /* Too complicated to handle. */ 2399 return chrec_dont_know; 2400} 2401 2402/* Analyze all the parameters of the chrec that were left under a 2403 symbolic form. LOOP is the loop in which symbolic names have to 2404 be analyzed and instantiated. */ 2405 2406tree 2407instantiate_parameters (struct loop *loop, 2408 tree chrec) 2409{ 2410 tree res; 2411 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); 2412 2413 if (dump_file && (dump_flags & TDF_DETAILS)) 2414 { 2415 fprintf (dump_file, "(instantiate_parameters \n"); 2416 fprintf (dump_file, " (loop_nb = %d)\n", loop->num); 2417 fprintf (dump_file, " (chrec = "); 2418 print_generic_expr (dump_file, chrec, 0); 2419 fprintf (dump_file, ")\n"); 2420 } 2421 2422 res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache, 2423 0); 2424 2425 if (dump_file && (dump_flags & TDF_DETAILS)) 2426 { 2427 fprintf (dump_file, " (res = "); 2428 print_generic_expr (dump_file, res, 0); 2429 fprintf (dump_file, "))\n"); 2430 } 2431 2432 htab_delete (cache); 2433 2434 return res; 2435} 2436 2437/* Similar to instantiate_parameters, but does not introduce the 2438 evolutions in outer loops for LOOP invariants in CHREC, and does not 2439 care about causing overflows, as long as they do not affect value 2440 of an expression. */ 2441 2442static tree 2443resolve_mixers (struct loop *loop, tree chrec) 2444{ 2445 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); 2446 tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0); 2447 htab_delete (cache); 2448 return ret; 2449} 2450 2451/* Entry point for the analysis of the number of iterations pass. 2452 This function tries to safely approximate the number of iterations 2453 the loop will run. When this property is not decidable at compile 2454 time, the result is chrec_dont_know. Otherwise the result is 2455 a scalar or a symbolic parameter. 2456 2457 Example of analysis: suppose that the loop has an exit condition: 2458 2459 "if (b > 49) goto end_loop;" 2460 2461 and that in a previous analysis we have determined that the 2462 variable 'b' has an evolution function: 2463 2464 "EF = {23, +, 5}_2". 2465 2466 When we evaluate the function at the point 5, i.e. the value of the 2467 variable 'b' after 5 iterations in the loop, we have EF (5) = 48, 2468 and EF (6) = 53. In this case the value of 'b' on exit is '53' and 2469 the loop body has been executed 6 times. */ 2470 2471tree 2472number_of_iterations_in_loop (struct loop *loop) 2473{ 2474 tree res, type; 2475 edge exit; 2476 struct tree_niter_desc niter_desc; 2477 2478 /* Determine whether the number_of_iterations_in_loop has already 2479 been computed. */ 2480 res = loop->nb_iterations; 2481 if (res) 2482 return res; 2483 res = chrec_dont_know; 2484 2485 if (dump_file && (dump_flags & TDF_DETAILS)) 2486 fprintf (dump_file, "(number_of_iterations_in_loop\n"); 2487 2488 exit = loop->single_exit; 2489 if (!exit) 2490 goto end; 2491 2492 if (!number_of_iterations_exit (loop, exit, &niter_desc, false)) 2493 goto end; 2494 2495 type = TREE_TYPE (niter_desc.niter); 2496 if (integer_nonzerop (niter_desc.may_be_zero)) 2497 res = build_int_cst (type, 0); 2498 else if (integer_zerop (niter_desc.may_be_zero)) 2499 res = niter_desc.niter; 2500 else 2501 res = chrec_dont_know; 2502 2503end: 2504 return set_nb_iterations_in_loop (loop, res); 2505} 2506 2507/* One of the drivers for testing the scalar evolutions analysis. 2508 This function computes the number of iterations for all the loops 2509 from the EXIT_CONDITIONS array. */ 2510 2511static void 2512number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions) 2513{ 2514 unsigned int i; 2515 unsigned nb_chrec_dont_know_loops = 0; 2516 unsigned nb_static_loops = 0; 2517 tree cond; 2518 2519 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) 2520 { 2521 tree res = number_of_iterations_in_loop (loop_containing_stmt (cond)); 2522 if (chrec_contains_undetermined (res)) 2523 nb_chrec_dont_know_loops++; 2524 else 2525 nb_static_loops++; 2526 } 2527 2528 if (dump_file) 2529 { 2530 fprintf (dump_file, "\n(\n"); 2531 fprintf (dump_file, "-----------------------------------------\n"); 2532 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops); 2533 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops); 2534 fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num); 2535 fprintf (dump_file, "-----------------------------------------\n"); 2536 fprintf (dump_file, ")\n\n"); 2537 2538 print_loop_ir (dump_file); 2539 } 2540} 2541 2542 2543 2544/* Counters for the stats. */ 2545 2546struct chrec_stats 2547{ 2548 unsigned nb_chrecs; 2549 unsigned nb_affine; 2550 unsigned nb_affine_multivar; 2551 unsigned nb_higher_poly; 2552 unsigned nb_chrec_dont_know; 2553 unsigned nb_undetermined; 2554}; 2555 2556/* Reset the counters. */ 2557 2558static inline void 2559reset_chrecs_counters (struct chrec_stats *stats) 2560{ 2561 stats->nb_chrecs = 0; 2562 stats->nb_affine = 0; 2563 stats->nb_affine_multivar = 0; 2564 stats->nb_higher_poly = 0; 2565 stats->nb_chrec_dont_know = 0; 2566 stats->nb_undetermined = 0; 2567} 2568 2569/* Dump the contents of a CHREC_STATS structure. */ 2570 2571static void 2572dump_chrecs_stats (FILE *file, struct chrec_stats *stats) 2573{ 2574 fprintf (file, "\n(\n"); 2575 fprintf (file, "-----------------------------------------\n"); 2576 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine); 2577 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar); 2578 fprintf (file, "%d\tdegree greater than 2 polynomials\n", 2579 stats->nb_higher_poly); 2580 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know); 2581 fprintf (file, "-----------------------------------------\n"); 2582 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs); 2583 fprintf (file, "%d\twith undetermined coefficients\n", 2584 stats->nb_undetermined); 2585 fprintf (file, "-----------------------------------------\n"); 2586 fprintf (file, "%d\tchrecs in the scev database\n", 2587 (int) htab_elements (scalar_evolution_info)); 2588 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev); 2589 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev); 2590 fprintf (file, "-----------------------------------------\n"); 2591 fprintf (file, ")\n\n"); 2592} 2593 2594/* Gather statistics about CHREC. */ 2595 2596static void 2597gather_chrec_stats (tree chrec, struct chrec_stats *stats) 2598{ 2599 if (dump_file && (dump_flags & TDF_STATS)) 2600 { 2601 fprintf (dump_file, "(classify_chrec "); 2602 print_generic_expr (dump_file, chrec, 0); 2603 fprintf (dump_file, "\n"); 2604 } 2605 2606 stats->nb_chrecs++; 2607 2608 if (chrec == NULL_TREE) 2609 { 2610 stats->nb_undetermined++; 2611 return; 2612 } 2613 2614 switch (TREE_CODE (chrec)) 2615 { 2616 case POLYNOMIAL_CHREC: 2617 if (evolution_function_is_affine_p (chrec)) 2618 { 2619 if (dump_file && (dump_flags & TDF_STATS)) 2620 fprintf (dump_file, " affine_univariate\n"); 2621 stats->nb_affine++; 2622 } 2623 else if (evolution_function_is_affine_multivariate_p (chrec)) 2624 { 2625 if (dump_file && (dump_flags & TDF_STATS)) 2626 fprintf (dump_file, " affine_multivariate\n"); 2627 stats->nb_affine_multivar++; 2628 } 2629 else 2630 { 2631 if (dump_file && (dump_flags & TDF_STATS)) 2632 fprintf (dump_file, " higher_degree_polynomial\n"); 2633 stats->nb_higher_poly++; 2634 } 2635 2636 break; 2637 2638 default: 2639 break; 2640 } 2641 2642 if (chrec_contains_undetermined (chrec)) 2643 { 2644 if (dump_file && (dump_flags & TDF_STATS)) 2645 fprintf (dump_file, " undetermined\n"); 2646 stats->nb_undetermined++; 2647 } 2648 2649 if (dump_file && (dump_flags & TDF_STATS)) 2650 fprintf (dump_file, ")\n"); 2651} 2652 2653/* One of the drivers for testing the scalar evolutions analysis. 2654 This function analyzes the scalar evolution of all the scalars 2655 defined as loop phi nodes in one of the loops from the 2656 EXIT_CONDITIONS array. 2657 2658 TODO Optimization: A loop is in canonical form if it contains only 2659 a single scalar loop phi node. All the other scalars that have an 2660 evolution in the loop are rewritten in function of this single 2661 index. This allows the parallelization of the loop. */ 2662 2663static void 2664analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions) 2665{ 2666 unsigned int i; 2667 struct chrec_stats stats; 2668 tree cond; 2669 2670 reset_chrecs_counters (&stats); 2671 2672 for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) 2673 { 2674 struct loop *loop; 2675 basic_block bb; 2676 tree phi, chrec; 2677 2678 loop = loop_containing_stmt (cond); 2679 bb = loop->header; 2680 2681 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2682 if (is_gimple_reg (PHI_RESULT (phi))) 2683 { 2684 chrec = instantiate_parameters 2685 (loop, 2686 analyze_scalar_evolution (loop, PHI_RESULT (phi))); 2687 2688 if (dump_file && (dump_flags & TDF_STATS)) 2689 gather_chrec_stats (chrec, &stats); 2690 } 2691 } 2692 2693 if (dump_file && (dump_flags & TDF_STATS)) 2694 dump_chrecs_stats (dump_file, &stats); 2695} 2696 2697/* Callback for htab_traverse, gathers information on chrecs in the 2698 hashtable. */ 2699 2700static int 2701gather_stats_on_scev_database_1 (void **slot, void *stats) 2702{ 2703 struct scev_info_str *entry = (struct scev_info_str *) *slot; 2704 2705 gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats); 2706 2707 return 1; 2708} 2709 2710/* Classify the chrecs of the whole database. */ 2711 2712void 2713gather_stats_on_scev_database (void) 2714{ 2715 struct chrec_stats stats; 2716 2717 if (!dump_file) 2718 return; 2719 2720 reset_chrecs_counters (&stats); 2721 2722 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1, 2723 &stats); 2724 2725 dump_chrecs_stats (dump_file, &stats); 2726} 2727 2728 2729 2730/* Initializer. */ 2731 2732static void 2733initialize_scalar_evolutions_analyzer (void) 2734{ 2735 /* The elements below are unique. */ 2736 if (chrec_dont_know == NULL_TREE) 2737 { 2738 chrec_not_analyzed_yet = NULL_TREE; 2739 chrec_dont_know = make_node (SCEV_NOT_KNOWN); 2740 chrec_known = make_node (SCEV_KNOWN); 2741 TREE_TYPE (chrec_dont_know) = void_type_node; 2742 TREE_TYPE (chrec_known) = void_type_node; 2743 } 2744} 2745 2746/* Initialize the analysis of scalar evolutions for LOOPS. */ 2747 2748void 2749scev_initialize (struct loops *loops) 2750{ 2751 unsigned i; 2752 current_loops = loops; 2753 2754 scalar_evolution_info = htab_create (100, hash_scev_info, 2755 eq_scev_info, del_scev_info); 2756 already_instantiated = BITMAP_ALLOC (NULL); 2757 2758 initialize_scalar_evolutions_analyzer (); 2759 2760 for (i = 1; i < loops->num; i++) 2761 if (loops->parray[i]) 2762 loops->parray[i]->nb_iterations = NULL_TREE; 2763} 2764 2765/* Cleans up the information cached by the scalar evolutions analysis. */ 2766 2767void 2768scev_reset (void) 2769{ 2770 unsigned i; 2771 struct loop *loop; 2772 2773 if (!scalar_evolution_info || !current_loops) 2774 return; 2775 2776 htab_empty (scalar_evolution_info); 2777 for (i = 1; i < current_loops->num; i++) 2778 { 2779 loop = current_loops->parray[i]; 2780 if (loop) 2781 loop->nb_iterations = NULL_TREE; 2782 } 2783} 2784 2785/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns 2786 its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we 2787 want step to be invariant in LOOP. Otherwise we require it to be an 2788 integer constant. IV->no_overflow is set to true if we are sure the iv cannot 2789 overflow (e.g. because it is computed in signed arithmetics). */ 2790 2791bool 2792simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv, 2793 bool allow_nonconstant_step) 2794{ 2795 basic_block bb = bb_for_stmt (stmt); 2796 tree type, ev; 2797 bool folded_casts; 2798 2799 iv->base = NULL_TREE; 2800 iv->step = NULL_TREE; 2801 iv->no_overflow = false; 2802 2803 type = TREE_TYPE (op); 2804 if (TREE_CODE (type) != INTEGER_TYPE 2805 && TREE_CODE (type) != POINTER_TYPE) 2806 return false; 2807 2808 ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op, 2809 &folded_casts); 2810 if (chrec_contains_undetermined (ev)) 2811 return false; 2812 2813 if (tree_does_not_contain_chrecs (ev) 2814 && !chrec_contains_symbols_defined_in_loop (ev, loop->num)) 2815 { 2816 iv->base = ev; 2817 iv->no_overflow = true; 2818 return true; 2819 } 2820 2821 if (TREE_CODE (ev) != POLYNOMIAL_CHREC 2822 || CHREC_VARIABLE (ev) != (unsigned) loop->num) 2823 return false; 2824 2825 iv->step = CHREC_RIGHT (ev); 2826 if (allow_nonconstant_step) 2827 { 2828 if (tree_contains_chrecs (iv->step, NULL) 2829 || chrec_contains_symbols_defined_in_loop (iv->step, loop->num)) 2830 return false; 2831 } 2832 else if (TREE_CODE (iv->step) != INTEGER_CST) 2833 return false; 2834 2835 iv->base = CHREC_LEFT (ev); 2836 if (tree_contains_chrecs (iv->base, NULL) 2837 || chrec_contains_symbols_defined_in_loop (iv->base, loop->num)) 2838 return false; 2839 2840 iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type); 2841 2842 return true; 2843} 2844 2845/* Runs the analysis of scalar evolutions. */ 2846 2847void 2848scev_analysis (void) 2849{ 2850 VEC(tree,heap) *exit_conditions; 2851 2852 exit_conditions = VEC_alloc (tree, heap, 37); 2853 select_loops_exit_conditions (current_loops, &exit_conditions); 2854 2855 if (dump_file && (dump_flags & TDF_STATS)) 2856 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions); 2857 2858 number_of_iterations_for_all_loops (&exit_conditions); 2859 VEC_free (tree, heap, exit_conditions); 2860} 2861 2862/* Finalize the scalar evolution analysis. */ 2863 2864void 2865scev_finalize (void) 2866{ 2867 htab_delete (scalar_evolution_info); 2868 BITMAP_FREE (already_instantiated); 2869} 2870 2871/* Returns true if EXPR looks expensive. */ 2872 2873static bool 2874expression_expensive_p (tree expr) 2875{ 2876 return force_expr_to_var_cost (expr) >= target_spill_cost; 2877} 2878 2879/* Replace ssa names for that scev can prove they are constant by the 2880 appropriate constants. Also perform final value replacement in loops, 2881 in case the replacement expressions are cheap. 2882 2883 We only consider SSA names defined by phi nodes; rest is left to the 2884 ordinary constant propagation pass. */ 2885 2886unsigned int 2887scev_const_prop (void) 2888{ 2889 basic_block bb; 2890 tree name, phi, next_phi, type, ev; 2891 struct loop *loop, *ex_loop; 2892 bitmap ssa_names_to_remove = NULL; 2893 unsigned i; 2894 2895 if (!current_loops) 2896 return 0; 2897 2898 FOR_EACH_BB (bb) 2899 { 2900 loop = bb->loop_father; 2901 2902 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2903 { 2904 name = PHI_RESULT (phi); 2905 2906 if (!is_gimple_reg (name)) 2907 continue; 2908 2909 type = TREE_TYPE (name); 2910 2911 if (!POINTER_TYPE_P (type) 2912 && !INTEGRAL_TYPE_P (type)) 2913 continue; 2914 2915 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name)); 2916 if (!is_gimple_min_invariant (ev) 2917 || !may_propagate_copy (name, ev)) 2918 continue; 2919 2920 /* Replace the uses of the name. */ 2921 if (name != ev) 2922 replace_uses_by (name, ev); 2923 2924 if (!ssa_names_to_remove) 2925 ssa_names_to_remove = BITMAP_ALLOC (NULL); 2926 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name)); 2927 } 2928 } 2929 2930 /* Remove the ssa names that were replaced by constants. We do not remove them 2931 directly in the previous cycle, since this invalidates scev cache. */ 2932 if (ssa_names_to_remove) 2933 { 2934 bitmap_iterator bi; 2935 unsigned i; 2936 2937 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi) 2938 { 2939 name = ssa_name (i); 2940 phi = SSA_NAME_DEF_STMT (name); 2941 2942 gcc_assert (TREE_CODE (phi) == PHI_NODE); 2943 remove_phi_node (phi, NULL); 2944 } 2945 2946 BITMAP_FREE (ssa_names_to_remove); 2947 scev_reset (); 2948 } 2949 2950 /* Now the regular final value replacement. */ 2951 for (i = current_loops->num - 1; i > 0; i--) 2952 { 2953 edge exit; 2954 tree def, rslt, ass, niter; 2955 block_stmt_iterator bsi; 2956 2957 loop = current_loops->parray[i]; 2958 if (!loop) 2959 continue; 2960 2961 /* If we do not know exact number of iterations of the loop, we cannot 2962 replace the final value. */ 2963 exit = loop->single_exit; 2964 if (!exit) 2965 continue; 2966 2967 niter = number_of_iterations_in_loop (loop); 2968 if (niter == chrec_dont_know 2969 /* If computing the number of iterations is expensive, it may be 2970 better not to introduce computations involving it. */ 2971 || expression_expensive_p (niter)) 2972 continue; 2973 2974 /* Ensure that it is possible to insert new statements somewhere. */ 2975 if (!single_pred_p (exit->dest)) 2976 split_loop_exit_edge (exit); 2977 tree_block_label (exit->dest); 2978 bsi = bsi_after_labels (exit->dest); 2979 2980 ex_loop = superloop_at_depth (loop, exit->dest->loop_father->depth + 1); 2981 2982 for (phi = phi_nodes (exit->dest); phi; phi = next_phi) 2983 { 2984 next_phi = PHI_CHAIN (phi); 2985 rslt = PHI_RESULT (phi); 2986 def = PHI_ARG_DEF_FROM_EDGE (phi, exit); 2987 if (!is_gimple_reg (def)) 2988 continue; 2989 2990 if (!POINTER_TYPE_P (TREE_TYPE (def)) 2991 && !INTEGRAL_TYPE_P (TREE_TYPE (def))) 2992 continue; 2993 2994 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL); 2995 def = compute_overall_effect_of_inner_loop (ex_loop, def); 2996 if (!tree_does_not_contain_chrecs (def) 2997 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num) 2998 /* Moving the computation from the loop may prolong life range 2999 of some ssa names, which may cause problems if they appear 3000 on abnormal edges. */ 3001 || contains_abnormal_ssa_name_p (def)) 3002 continue; 3003 3004 /* Eliminate the phi node and replace it by a computation outside 3005 the loop. */ 3006 def = unshare_expr (def); 3007 SET_PHI_RESULT (phi, NULL_TREE); 3008 remove_phi_node (phi, NULL_TREE); 3009 3010 ass = build2 (MODIFY_EXPR, void_type_node, rslt, NULL_TREE); 3011 SSA_NAME_DEF_STMT (rslt) = ass; 3012 { 3013 block_stmt_iterator dest = bsi; 3014 bsi_insert_before (&dest, ass, BSI_NEW_STMT); 3015 def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE); 3016 } 3017 TREE_OPERAND (ass, 1) = def; 3018 update_stmt (ass); 3019 } 3020 } 3021 return 0; 3022} 3023