1169689Skan/* Scalar evolution detector. 2169689Skan Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc. 3169689Skan Contributed by Sebastian Pop <s.pop@laposte.net> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan/* 23169689Skan Description: 24169689Skan 25169689Skan This pass analyzes the evolution of scalar variables in loop 26169689Skan structures. The algorithm is based on the SSA representation, 27169689Skan and on the loop hierarchy tree. This algorithm is not based on 28169689Skan the notion of versions of a variable, as it was the case for the 29169689Skan previous implementations of the scalar evolution algorithm, but 30169689Skan it assumes that each defined name is unique. 31169689Skan 32169689Skan The notation used in this file is called "chains of recurrences", 33169689Skan and has been proposed by Eugene Zima, Robert Van Engelen, and 34169689Skan others for describing induction variables in programs. For example 35169689Skan "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0 36169689Skan when entering in the loop_1 and has a step 2 in this loop, in other 37169689Skan words "for (b = 0; b < N; b+=2);". Note that the coefficients of 38169689Skan this chain of recurrence (or chrec [shrek]) can contain the name of 39169689Skan other variables, in which case they are called parametric chrecs. 40169689Skan For example, "b -> {a, +, 2}_1" means that the initial value of "b" 41169689Skan is the value of "a". In most of the cases these parametric chrecs 42169689Skan are fully instantiated before their use because symbolic names can 43169689Skan hide some difficult cases such as self-references described later 44169689Skan (see the Fibonacci example). 45169689Skan 46169689Skan A short sketch of the algorithm is: 47169689Skan 48169689Skan Given a scalar variable to be analyzed, follow the SSA edge to 49169689Skan its definition: 50169689Skan 51169689Skan - When the definition is a MODIFY_EXPR: if the right hand side 52169689Skan (RHS) of the definition cannot be statically analyzed, the answer 53169689Skan of the analyzer is: "don't know". 54169689Skan Otherwise, for all the variables that are not yet analyzed in the 55169689Skan RHS, try to determine their evolution, and finally try to 56169689Skan evaluate the operation of the RHS that gives the evolution 57169689Skan function of the analyzed variable. 58169689Skan 59169689Skan - When the definition is a condition-phi-node: determine the 60169689Skan evolution function for all the branches of the phi node, and 61169689Skan finally merge these evolutions (see chrec_merge). 62169689Skan 63169689Skan - When the definition is a loop-phi-node: determine its initial 64169689Skan condition, that is the SSA edge defined in an outer loop, and 65169689Skan keep it symbolic. Then determine the SSA edges that are defined 66169689Skan in the body of the loop. Follow the inner edges until ending on 67169689Skan another loop-phi-node of the same analyzed loop. If the reached 68169689Skan loop-phi-node is not the starting loop-phi-node, then we keep 69169689Skan this definition under a symbolic form. If the reached 70169689Skan loop-phi-node is the same as the starting one, then we compute a 71169689Skan symbolic stride on the return path. The result is then the 72169689Skan symbolic chrec {initial_condition, +, symbolic_stride}_loop. 73169689Skan 74169689Skan Examples: 75169689Skan 76169689Skan Example 1: Illustration of the basic algorithm. 77169689Skan 78169689Skan | a = 3 79169689Skan | loop_1 80169689Skan | b = phi (a, c) 81169689Skan | c = b + 1 82169689Skan | if (c > 10) exit_loop 83169689Skan | endloop 84169689Skan 85169689Skan Suppose that we want to know the number of iterations of the 86169689Skan loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We 87169689Skan ask the scalar evolution analyzer two questions: what's the 88169689Skan scalar evolution (scev) of "c", and what's the scev of "10". For 89169689Skan "10" the answer is "10" since it is a scalar constant. For the 90169689Skan scalar variable "c", it follows the SSA edge to its definition, 91169689Skan "c = b + 1", and then asks again what's the scev of "b". 92169689Skan Following the SSA edge, we end on a loop-phi-node "b = phi (a, 93169689Skan c)", where the initial condition is "a", and the inner loop edge 94169689Skan is "c". The initial condition is kept under a symbolic form (it 95169689Skan may be the case that the copy constant propagation has done its 96169689Skan work and we end with the constant "3" as one of the edges of the 97169689Skan loop-phi-node). The update edge is followed to the end of the 98169689Skan loop, and until reaching again the starting loop-phi-node: b -> c 99169689Skan -> b. At this point we have drawn a path from "b" to "b" from 100169689Skan which we compute the stride in the loop: in this example it is 101169689Skan "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now 102169689Skan that the scev for "b" is known, it is possible to compute the 103169689Skan scev for "c", that is "c -> {a + 1, +, 1}_1". In order to 104169689Skan determine the number of iterations in the loop_1, we have to 105169689Skan instantiate_parameters ({a + 1, +, 1}_1), that gives after some 106169689Skan more analysis the scev {4, +, 1}_1, or in other words, this is 107169689Skan the function "f (x) = x + 4", where x is the iteration count of 108169689Skan the loop_1. Now we have to solve the inequality "x + 4 > 10", 109169689Skan and take the smallest iteration number for which the loop is 110169689Skan exited: x = 7. This loop runs from x = 0 to x = 7, and in total 111169689Skan there are 8 iterations. In terms of loop normalization, we have 112169689Skan created a variable that is implicitly defined, "x" or just "_1", 113169689Skan and all the other analyzed scalars of the loop are defined in 114169689Skan function of this variable: 115169689Skan 116169689Skan a -> 3 117169689Skan b -> {3, +, 1}_1 118169689Skan c -> {4, +, 1}_1 119169689Skan 120169689Skan or in terms of a C program: 121169689Skan 122169689Skan | a = 3 123169689Skan | for (x = 0; x <= 7; x++) 124169689Skan | { 125169689Skan | b = x + 3 126169689Skan | c = x + 4 127169689Skan | } 128169689Skan 129169689Skan Example 2: Illustration of the algorithm on nested loops. 130169689Skan 131169689Skan | loop_1 132169689Skan | a = phi (1, b) 133169689Skan | c = a + 2 134169689Skan | loop_2 10 times 135169689Skan | b = phi (c, d) 136169689Skan | d = b + 3 137169689Skan | endloop 138169689Skan | endloop 139169689Skan 140169689Skan For analyzing the scalar evolution of "a", the algorithm follows 141169689Skan the SSA edge into the loop's body: "a -> b". "b" is an inner 142169689Skan loop-phi-node, and its analysis as in Example 1, gives: 143169689Skan 144169689Skan b -> {c, +, 3}_2 145169689Skan d -> {c + 3, +, 3}_2 146169689Skan 147169689Skan Following the SSA edge for the initial condition, we end on "c = a 148169689Skan + 2", and then on the starting loop-phi-node "a". From this point, 149169689Skan the loop stride is computed: back on "c = a + 2" we get a "+2" in 150169689Skan the loop_1, then on the loop-phi-node "b" we compute the overall 151169689Skan effect of the inner loop that is "b = c + 30", and we get a "+30" 152169689Skan in the loop_1. That means that the overall stride in loop_1 is 153169689Skan equal to "+32", and the result is: 154169689Skan 155169689Skan a -> {1, +, 32}_1 156169689Skan c -> {3, +, 32}_1 157169689Skan 158169689Skan Example 3: Higher degree polynomials. 159169689Skan 160169689Skan | loop_1 161169689Skan | a = phi (2, b) 162169689Skan | c = phi (5, d) 163169689Skan | b = a + 1 164169689Skan | d = c + a 165169689Skan | endloop 166169689Skan 167169689Skan a -> {2, +, 1}_1 168169689Skan b -> {3, +, 1}_1 169169689Skan c -> {5, +, a}_1 170169689Skan d -> {5 + a, +, a}_1 171169689Skan 172169689Skan instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1 173169689Skan instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1 174169689Skan 175169689Skan Example 4: Lucas, Fibonacci, or mixers in general. 176169689Skan 177169689Skan | loop_1 178169689Skan | a = phi (1, b) 179169689Skan | c = phi (3, d) 180169689Skan | b = c 181169689Skan | d = c + a 182169689Skan | endloop 183169689Skan 184169689Skan a -> (1, c)_1 185169689Skan c -> {3, +, a}_1 186169689Skan 187169689Skan The syntax "(1, c)_1" stands for a PEELED_CHREC that has the 188169689Skan following semantics: during the first iteration of the loop_1, the 189169689Skan variable contains the value 1, and then it contains the value "c". 190169689Skan Note that this syntax is close to the syntax of the loop-phi-node: 191169689Skan "a -> (1, c)_1" vs. "a = phi (1, c)". 192169689Skan 193169689Skan The symbolic chrec representation contains all the semantics of the 194169689Skan original code. What is more difficult is to use this information. 195169689Skan 196169689Skan Example 5: Flip-flops, or exchangers. 197169689Skan 198169689Skan | loop_1 199169689Skan | a = phi (1, b) 200169689Skan | c = phi (3, d) 201169689Skan | b = c 202169689Skan | d = a 203169689Skan | endloop 204169689Skan 205169689Skan a -> (1, c)_1 206169689Skan c -> (3, a)_1 207169689Skan 208169689Skan Based on these symbolic chrecs, it is possible to refine this 209169689Skan information into the more precise PERIODIC_CHRECs: 210169689Skan 211169689Skan a -> |1, 3|_1 212169689Skan c -> |3, 1|_1 213169689Skan 214169689Skan This transformation is not yet implemented. 215169689Skan 216169689Skan Further readings: 217169689Skan 218169689Skan You can find a more detailed description of the algorithm in: 219169689Skan http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf 220169689Skan http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that 221169689Skan this is a preliminary report and some of the details of the 222169689Skan algorithm have changed. I'm working on a research report that 223169689Skan updates the description of the algorithms to reflect the design 224169689Skan choices used in this implementation. 225169689Skan 226169689Skan A set of slides show a high level overview of the algorithm and run 227169689Skan an example through the scalar evolution analyzer: 228169689Skan http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf 229169689Skan 230169689Skan The slides that I have presented at the GCC Summit'04 are available 231169689Skan at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf 232169689Skan*/ 233169689Skan 234169689Skan#include "config.h" 235169689Skan#include "system.h" 236169689Skan#include "coretypes.h" 237169689Skan#include "tm.h" 238169689Skan#include "ggc.h" 239169689Skan#include "tree.h" 240169689Skan#include "real.h" 241169689Skan 242169689Skan/* These RTL headers are needed for basic-block.h. */ 243169689Skan#include "rtl.h" 244169689Skan#include "basic-block.h" 245169689Skan#include "diagnostic.h" 246169689Skan#include "tree-flow.h" 247169689Skan#include "tree-dump.h" 248169689Skan#include "timevar.h" 249169689Skan#include "cfgloop.h" 250169689Skan#include "tree-chrec.h" 251169689Skan#include "tree-scalar-evolution.h" 252169689Skan#include "tree-pass.h" 253169689Skan#include "flags.h" 254169689Skan#include "params.h" 255169689Skan 256169689Skanstatic tree analyze_scalar_evolution_1 (struct loop *, tree, tree); 257169689Skanstatic tree resolve_mixers (struct loop *, tree); 258169689Skan 259169689Skan/* The cached information about a ssa name VAR, claiming that inside LOOP, 260169689Skan the value of VAR can be expressed as CHREC. */ 261169689Skan 262169689Skanstruct scev_info_str 263169689Skan{ 264169689Skan tree var; 265169689Skan tree chrec; 266169689Skan}; 267169689Skan 268169689Skan/* Counters for the scev database. */ 269169689Skanstatic unsigned nb_set_scev = 0; 270169689Skanstatic unsigned nb_get_scev = 0; 271169689Skan 272169689Skan/* The following trees are unique elements. Thus the comparison of 273169689Skan another element to these elements should be done on the pointer to 274169689Skan these trees, and not on their value. */ 275169689Skan 276169689Skan/* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */ 277169689Skantree chrec_not_analyzed_yet; 278169689Skan 279169689Skan/* Reserved to the cases where the analyzer has detected an 280169689Skan undecidable property at compile time. */ 281169689Skantree chrec_dont_know; 282169689Skan 283169689Skan/* When the analyzer has detected that a property will never 284169689Skan happen, then it qualifies it with chrec_known. */ 285169689Skantree chrec_known; 286169689Skan 287169689Skanstatic bitmap already_instantiated; 288169689Skan 289169689Skanstatic htab_t scalar_evolution_info; 290169689Skan 291169689Skan 292169689Skan/* Constructs a new SCEV_INFO_STR structure. */ 293169689Skan 294169689Skanstatic inline struct scev_info_str * 295169689Skannew_scev_info_str (tree var) 296169689Skan{ 297169689Skan struct scev_info_str *res; 298169689Skan 299169689Skan res = XNEW (struct scev_info_str); 300169689Skan res->var = var; 301169689Skan res->chrec = chrec_not_analyzed_yet; 302169689Skan 303169689Skan return res; 304169689Skan} 305169689Skan 306169689Skan/* Computes a hash function for database element ELT. */ 307169689Skan 308169689Skanstatic hashval_t 309169689Skanhash_scev_info (const void *elt) 310169689Skan{ 311169689Skan return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var); 312169689Skan} 313169689Skan 314169689Skan/* Compares database elements E1 and E2. */ 315169689Skan 316169689Skanstatic int 317169689Skaneq_scev_info (const void *e1, const void *e2) 318169689Skan{ 319169689Skan const struct scev_info_str *elt1 = (const struct scev_info_str *) e1; 320169689Skan const struct scev_info_str *elt2 = (const struct scev_info_str *) e2; 321169689Skan 322169689Skan return elt1->var == elt2->var; 323169689Skan} 324169689Skan 325169689Skan/* Deletes database element E. */ 326169689Skan 327169689Skanstatic void 328169689Skandel_scev_info (void *e) 329169689Skan{ 330169689Skan free (e); 331169689Skan} 332169689Skan 333169689Skan/* Get the index corresponding to VAR in the current LOOP. If 334169689Skan it's the first time we ask for this VAR, then we return 335169689Skan chrec_not_analyzed_yet for this VAR and return its index. */ 336169689Skan 337169689Skanstatic tree * 338169689Skanfind_var_scev_info (tree var) 339169689Skan{ 340169689Skan struct scev_info_str *res; 341169689Skan struct scev_info_str tmp; 342169689Skan PTR *slot; 343169689Skan 344169689Skan tmp.var = var; 345169689Skan slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT); 346169689Skan 347169689Skan if (!*slot) 348169689Skan *slot = new_scev_info_str (var); 349169689Skan res = (struct scev_info_str *) *slot; 350169689Skan 351169689Skan return &res->chrec; 352169689Skan} 353169689Skan 354169689Skan/* Return true when CHREC contains symbolic names defined in 355169689Skan LOOP_NB. */ 356169689Skan 357169689Skanbool 358169689Skanchrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb) 359169689Skan{ 360169689Skan if (chrec == NULL_TREE) 361169689Skan return false; 362169689Skan 363169689Skan if (TREE_INVARIANT (chrec)) 364169689Skan return false; 365169689Skan 366169689Skan if (TREE_CODE (chrec) == VAR_DECL 367169689Skan || TREE_CODE (chrec) == PARM_DECL 368169689Skan || TREE_CODE (chrec) == FUNCTION_DECL 369169689Skan || TREE_CODE (chrec) == LABEL_DECL 370169689Skan || TREE_CODE (chrec) == RESULT_DECL 371169689Skan || TREE_CODE (chrec) == FIELD_DECL) 372169689Skan return true; 373169689Skan 374169689Skan if (TREE_CODE (chrec) == SSA_NAME) 375169689Skan { 376169689Skan tree def = SSA_NAME_DEF_STMT (chrec); 377169689Skan struct loop *def_loop = loop_containing_stmt (def); 378169689Skan struct loop *loop = current_loops->parray[loop_nb]; 379169689Skan 380169689Skan if (def_loop == NULL) 381169689Skan return false; 382169689Skan 383169689Skan if (loop == def_loop || flow_loop_nested_p (loop, def_loop)) 384169689Skan return true; 385169689Skan 386169689Skan return false; 387169689Skan } 388169689Skan 389169689Skan switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 390169689Skan { 391169689Skan case 3: 392169689Skan if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2), 393169689Skan loop_nb)) 394169689Skan return true; 395169689Skan 396169689Skan case 2: 397169689Skan if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1), 398169689Skan loop_nb)) 399169689Skan return true; 400169689Skan 401169689Skan case 1: 402169689Skan if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0), 403169689Skan loop_nb)) 404169689Skan return true; 405169689Skan 406169689Skan default: 407169689Skan return false; 408169689Skan } 409169689Skan} 410169689Skan 411169689Skan/* Return true when PHI is a loop-phi-node. */ 412169689Skan 413169689Skanstatic bool 414169689Skanloop_phi_node_p (tree phi) 415169689Skan{ 416169689Skan /* The implementation of this function is based on the following 417169689Skan property: "all the loop-phi-nodes of a loop are contained in the 418169689Skan loop's header basic block". */ 419169689Skan 420169689Skan return loop_containing_stmt (phi)->header == bb_for_stmt (phi); 421169689Skan} 422169689Skan 423169689Skan/* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP. 424169689Skan In general, in the case of multivariate evolutions we want to get 425169689Skan the evolution in different loops. LOOP specifies the level for 426169689Skan which to get the evolution. 427169689Skan 428169689Skan Example: 429169689Skan 430169689Skan | for (j = 0; j < 100; j++) 431169689Skan | { 432169689Skan | for (k = 0; k < 100; k++) 433169689Skan | { 434169689Skan | i = k + j; - Here the value of i is a function of j, k. 435169689Skan | } 436169689Skan | ... = i - Here the value of i is a function of j. 437169689Skan | } 438169689Skan | ... = i - Here the value of i is a scalar. 439169689Skan 440169689Skan Example: 441169689Skan 442169689Skan | i_0 = ... 443169689Skan | loop_1 10 times 444169689Skan | i_1 = phi (i_0, i_2) 445169689Skan | i_2 = i_1 + 2 446169689Skan | endloop 447169689Skan 448169689Skan This loop has the same effect as: 449169689Skan LOOP_1 has the same effect as: 450169689Skan 451169689Skan | i_1 = i_0 + 20 452169689Skan 453169689Skan The overall effect of the loop, "i_0 + 20" in the previous example, 454169689Skan is obtained by passing in the parameters: LOOP = 1, 455169689Skan EVOLUTION_FN = {i_0, +, 2}_1. 456169689Skan*/ 457169689Skan 458169689Skanstatic tree 459169689Skancompute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) 460169689Skan{ 461169689Skan bool val = false; 462169689Skan 463169689Skan if (evolution_fn == chrec_dont_know) 464169689Skan return chrec_dont_know; 465169689Skan 466169689Skan else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC) 467169689Skan { 468169689Skan if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num) 469169689Skan { 470169689Skan struct loop *inner_loop = 471169689Skan current_loops->parray[CHREC_VARIABLE (evolution_fn)]; 472169689Skan tree nb_iter = number_of_iterations_in_loop (inner_loop); 473169689Skan 474169689Skan if (nb_iter == chrec_dont_know) 475169689Skan return chrec_dont_know; 476169689Skan else 477169689Skan { 478169689Skan tree res; 479169689Skan tree type = chrec_type (nb_iter); 480169689Skan 481169689Skan /* Number of iterations is off by one (the ssa name we 482169689Skan analyze must be defined before the exit). */ 483169689Skan nb_iter = chrec_fold_minus (type, nb_iter, 484169689Skan build_int_cst (type, 1)); 485169689Skan 486169689Skan /* evolution_fn is the evolution function in LOOP. Get 487169689Skan its value in the nb_iter-th iteration. */ 488169689Skan res = chrec_apply (inner_loop->num, evolution_fn, nb_iter); 489169689Skan 490169689Skan /* Continue the computation until ending on a parent of LOOP. */ 491169689Skan return compute_overall_effect_of_inner_loop (loop, res); 492169689Skan } 493169689Skan } 494169689Skan else 495169689Skan return evolution_fn; 496169689Skan } 497169689Skan 498169689Skan /* If the evolution function is an invariant, there is nothing to do. */ 499169689Skan else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val) 500169689Skan return evolution_fn; 501169689Skan 502169689Skan else 503169689Skan return chrec_dont_know; 504169689Skan} 505169689Skan 506169689Skan/* Determine whether the CHREC is always positive/negative. If the expression 507169689Skan cannot be statically analyzed, return false, otherwise set the answer into 508169689Skan VALUE. */ 509169689Skan 510169689Skanbool 511169689Skanchrec_is_positive (tree chrec, bool *value) 512169689Skan{ 513169689Skan bool value0, value1, value2; 514169689Skan tree type, end_value, nb_iter; 515169689Skan 516169689Skan switch (TREE_CODE (chrec)) 517169689Skan { 518169689Skan case POLYNOMIAL_CHREC: 519169689Skan if (!chrec_is_positive (CHREC_LEFT (chrec), &value0) 520169689Skan || !chrec_is_positive (CHREC_RIGHT (chrec), &value1)) 521169689Skan return false; 522169689Skan 523169689Skan /* FIXME -- overflows. */ 524169689Skan if (value0 == value1) 525169689Skan { 526169689Skan *value = value0; 527169689Skan return true; 528169689Skan } 529169689Skan 530169689Skan /* Otherwise the chrec is under the form: "{-197, +, 2}_1", 531169689Skan and the proof consists in showing that the sign never 532169689Skan changes during the execution of the loop, from 0 to 533169689Skan loop->nb_iterations. */ 534169689Skan if (!evolution_function_is_affine_p (chrec)) 535169689Skan return false; 536169689Skan 537169689Skan nb_iter = number_of_iterations_in_loop 538169689Skan (current_loops->parray[CHREC_VARIABLE (chrec)]); 539169689Skan 540169689Skan if (chrec_contains_undetermined (nb_iter)) 541169689Skan return false; 542169689Skan 543169689Skan type = chrec_type (nb_iter); 544169689Skan nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1)); 545169689Skan 546169689Skan#if 0 547169689Skan /* TODO -- If the test is after the exit, we may decrease the number of 548169689Skan iterations by one. */ 549169689Skan if (after_exit) 550169689Skan nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1)); 551169689Skan#endif 552169689Skan 553169689Skan end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter); 554169689Skan 555169689Skan if (!chrec_is_positive (end_value, &value2)) 556169689Skan return false; 557169689Skan 558169689Skan *value = value0; 559169689Skan return value0 == value1; 560169689Skan 561169689Skan case INTEGER_CST: 562169689Skan *value = (tree_int_cst_sgn (chrec) == 1); 563169689Skan return true; 564169689Skan 565169689Skan default: 566169689Skan return false; 567169689Skan } 568169689Skan} 569169689Skan 570169689Skan/* Associate CHREC to SCALAR. */ 571169689Skan 572169689Skanstatic void 573169689Skanset_scalar_evolution (tree scalar, tree chrec) 574169689Skan{ 575169689Skan tree *scalar_info; 576169689Skan 577169689Skan if (TREE_CODE (scalar) != SSA_NAME) 578169689Skan return; 579169689Skan 580169689Skan scalar_info = find_var_scev_info (scalar); 581169689Skan 582169689Skan if (dump_file) 583169689Skan { 584169689Skan if (dump_flags & TDF_DETAILS) 585169689Skan { 586169689Skan fprintf (dump_file, "(set_scalar_evolution \n"); 587169689Skan fprintf (dump_file, " (scalar = "); 588169689Skan print_generic_expr (dump_file, scalar, 0); 589169689Skan fprintf (dump_file, ")\n (scalar_evolution = "); 590169689Skan print_generic_expr (dump_file, chrec, 0); 591169689Skan fprintf (dump_file, "))\n"); 592169689Skan } 593169689Skan if (dump_flags & TDF_STATS) 594169689Skan nb_set_scev++; 595169689Skan } 596169689Skan 597169689Skan *scalar_info = chrec; 598169689Skan} 599169689Skan 600169689Skan/* Retrieve the chrec associated to SCALAR in the LOOP. */ 601169689Skan 602169689Skanstatic tree 603169689Skanget_scalar_evolution (tree scalar) 604169689Skan{ 605169689Skan tree res; 606169689Skan 607169689Skan if (dump_file) 608169689Skan { 609169689Skan if (dump_flags & TDF_DETAILS) 610169689Skan { 611169689Skan fprintf (dump_file, "(get_scalar_evolution \n"); 612169689Skan fprintf (dump_file, " (scalar = "); 613169689Skan print_generic_expr (dump_file, scalar, 0); 614169689Skan fprintf (dump_file, ")\n"); 615169689Skan } 616169689Skan if (dump_flags & TDF_STATS) 617169689Skan nb_get_scev++; 618169689Skan } 619169689Skan 620169689Skan switch (TREE_CODE (scalar)) 621169689Skan { 622169689Skan case SSA_NAME: 623169689Skan res = *find_var_scev_info (scalar); 624169689Skan break; 625169689Skan 626169689Skan case REAL_CST: 627169689Skan case INTEGER_CST: 628169689Skan res = scalar; 629169689Skan break; 630169689Skan 631169689Skan default: 632169689Skan res = chrec_not_analyzed_yet; 633169689Skan break; 634169689Skan } 635169689Skan 636169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 637169689Skan { 638169689Skan fprintf (dump_file, " (scalar_evolution = "); 639169689Skan print_generic_expr (dump_file, res, 0); 640169689Skan fprintf (dump_file, "))\n"); 641169689Skan } 642169689Skan 643169689Skan return res; 644169689Skan} 645169689Skan 646169689Skan/* Helper function for add_to_evolution. Returns the evolution 647169689Skan function for an assignment of the form "a = b + c", where "a" and 648169689Skan "b" are on the strongly connected component. CHREC_BEFORE is the 649169689Skan information that we already have collected up to this point. 650169689Skan TO_ADD is the evolution of "c". 651169689Skan 652169689Skan When CHREC_BEFORE has an evolution part in LOOP_NB, add to this 653169689Skan evolution the expression TO_ADD, otherwise construct an evolution 654169689Skan part for this loop. */ 655169689Skan 656169689Skanstatic tree 657169689Skanadd_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, 658169689Skan tree at_stmt) 659169689Skan{ 660169689Skan tree type, left, right; 661169689Skan 662169689Skan switch (TREE_CODE (chrec_before)) 663169689Skan { 664169689Skan case POLYNOMIAL_CHREC: 665169689Skan if (CHREC_VARIABLE (chrec_before) <= loop_nb) 666169689Skan { 667169689Skan unsigned var; 668169689Skan 669169689Skan type = chrec_type (chrec_before); 670169689Skan 671169689Skan /* When there is no evolution part in this loop, build it. */ 672169689Skan if (CHREC_VARIABLE (chrec_before) < loop_nb) 673169689Skan { 674169689Skan var = loop_nb; 675169689Skan left = chrec_before; 676169689Skan right = SCALAR_FLOAT_TYPE_P (type) 677169689Skan ? build_real (type, dconst0) 678169689Skan : build_int_cst (type, 0); 679169689Skan } 680169689Skan else 681169689Skan { 682169689Skan var = CHREC_VARIABLE (chrec_before); 683169689Skan left = CHREC_LEFT (chrec_before); 684169689Skan right = CHREC_RIGHT (chrec_before); 685169689Skan } 686169689Skan 687169689Skan to_add = chrec_convert (type, to_add, at_stmt); 688169689Skan right = chrec_convert (type, right, at_stmt); 689169689Skan right = chrec_fold_plus (type, right, to_add); 690169689Skan return build_polynomial_chrec (var, left, right); 691169689Skan } 692169689Skan else 693169689Skan { 694169689Skan /* Search the evolution in LOOP_NB. */ 695169689Skan left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), 696169689Skan to_add, at_stmt); 697169689Skan right = CHREC_RIGHT (chrec_before); 698169689Skan right = chrec_convert (chrec_type (left), right, at_stmt); 699169689Skan return build_polynomial_chrec (CHREC_VARIABLE (chrec_before), 700169689Skan left, right); 701169689Skan } 702169689Skan 703169689Skan default: 704169689Skan /* These nodes do not depend on a loop. */ 705169689Skan if (chrec_before == chrec_dont_know) 706169689Skan return chrec_dont_know; 707169689Skan 708169689Skan left = chrec_before; 709169689Skan right = chrec_convert (chrec_type (left), to_add, at_stmt); 710169689Skan return build_polynomial_chrec (loop_nb, left, right); 711169689Skan } 712169689Skan} 713169689Skan 714169689Skan/* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension 715169689Skan of LOOP_NB. 716169689Skan 717169689Skan Description (provided for completeness, for those who read code in 718169689Skan a plane, and for my poor 62 bytes brain that would have forgotten 719169689Skan all this in the next two or three months): 720169689Skan 721169689Skan The algorithm of translation of programs from the SSA representation 722169689Skan into the chrecs syntax is based on a pattern matching. After having 723169689Skan reconstructed the overall tree expression for a loop, there are only 724169689Skan two cases that can arise: 725169689Skan 726169689Skan 1. a = loop-phi (init, a + expr) 727169689Skan 2. a = loop-phi (init, expr) 728169689Skan 729169689Skan where EXPR is either a scalar constant with respect to the analyzed 730169689Skan loop (this is a degree 0 polynomial), or an expression containing 731169689Skan other loop-phi definitions (these are higher degree polynomials). 732169689Skan 733169689Skan Examples: 734169689Skan 735169689Skan 1. 736169689Skan | init = ... 737169689Skan | loop_1 738169689Skan | a = phi (init, a + 5) 739169689Skan | endloop 740169689Skan 741169689Skan 2. 742169689Skan | inita = ... 743169689Skan | initb = ... 744169689Skan | loop_1 745169689Skan | a = phi (inita, 2 * b + 3) 746169689Skan | b = phi (initb, b + 1) 747169689Skan | endloop 748169689Skan 749169689Skan For the first case, the semantics of the SSA representation is: 750169689Skan 751169689Skan | a (x) = init + \sum_{j = 0}^{x - 1} expr (j) 752169689Skan 753169689Skan that is, there is a loop index "x" that determines the scalar value 754169689Skan of the variable during the loop execution. During the first 755169689Skan iteration, the value is that of the initial condition INIT, while 756169689Skan during the subsequent iterations, it is the sum of the initial 757169689Skan condition with the sum of all the values of EXPR from the initial 758169689Skan iteration to the before last considered iteration. 759169689Skan 760169689Skan For the second case, the semantics of the SSA program is: 761169689Skan 762169689Skan | a (x) = init, if x = 0; 763169689Skan | expr (x - 1), otherwise. 764169689Skan 765169689Skan The second case corresponds to the PEELED_CHREC, whose syntax is 766169689Skan close to the syntax of a loop-phi-node: 767169689Skan 768169689Skan | phi (init, expr) vs. (init, expr)_x 769169689Skan 770169689Skan The proof of the translation algorithm for the first case is a 771169689Skan proof by structural induction based on the degree of EXPR. 772169689Skan 773169689Skan Degree 0: 774169689Skan When EXPR is a constant with respect to the analyzed loop, or in 775169689Skan other words when EXPR is a polynomial of degree 0, the evolution of 776169689Skan the variable A in the loop is an affine function with an initial 777169689Skan condition INIT, and a step EXPR. In order to show this, we start 778169689Skan from the semantics of the SSA representation: 779169689Skan 780169689Skan f (x) = init + \sum_{j = 0}^{x - 1} expr (j) 781169689Skan 782169689Skan and since "expr (j)" is a constant with respect to "j", 783169689Skan 784169689Skan f (x) = init + x * expr 785169689Skan 786169689Skan Finally, based on the semantics of the pure sum chrecs, by 787169689Skan identification we get the corresponding chrecs syntax: 788169689Skan 789169689Skan f (x) = init * \binom{x}{0} + expr * \binom{x}{1} 790169689Skan f (x) -> {init, +, expr}_x 791169689Skan 792169689Skan Higher degree: 793169689Skan Suppose that EXPR is a polynomial of degree N with respect to the 794169689Skan analyzed loop_x for which we have already determined that it is 795169689Skan written under the chrecs syntax: 796169689Skan 797169689Skan | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x) 798169689Skan 799169689Skan We start from the semantics of the SSA program: 800169689Skan 801169689Skan | f (x) = init + \sum_{j = 0}^{x - 1} expr (j) 802169689Skan | 803169689Skan | f (x) = init + \sum_{j = 0}^{x - 1} 804169689Skan | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1}) 805169689Skan | 806169689Skan | f (x) = init + \sum_{j = 0}^{x - 1} 807169689Skan | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k}) 808169689Skan | 809169689Skan | f (x) = init + \sum_{k = 0}^{n - 1} 810169689Skan | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k}) 811169689Skan | 812169689Skan | f (x) = init + \sum_{k = 0}^{n - 1} 813169689Skan | (b_k * \binom{x}{k + 1}) 814169689Skan | 815169689Skan | f (x) = init + b_0 * \binom{x}{1} + ... 816169689Skan | + b_{n-1} * \binom{x}{n} 817169689Skan | 818169689Skan | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ... 819169689Skan | + b_{n-1} * \binom{x}{n} 820169689Skan | 821169689Skan 822169689Skan And finally from the definition of the chrecs syntax, we identify: 823169689Skan | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x 824169689Skan 825169689Skan This shows the mechanism that stands behind the add_to_evolution 826169689Skan function. An important point is that the use of symbolic 827169689Skan parameters avoids the need of an analysis schedule. 828169689Skan 829169689Skan Example: 830169689Skan 831169689Skan | inita = ... 832169689Skan | initb = ... 833169689Skan | loop_1 834169689Skan | a = phi (inita, a + 2 + b) 835169689Skan | b = phi (initb, b + 1) 836169689Skan | endloop 837169689Skan 838169689Skan When analyzing "a", the algorithm keeps "b" symbolically: 839169689Skan 840169689Skan | a -> {inita, +, 2 + b}_1 841169689Skan 842169689Skan Then, after instantiation, the analyzer ends on the evolution: 843169689Skan 844169689Skan | a -> {inita, +, 2 + initb, +, 1}_1 845169689Skan 846169689Skan*/ 847169689Skan 848169689Skanstatic tree 849169689Skanadd_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, 850169689Skan tree to_add, tree at_stmt) 851169689Skan{ 852169689Skan tree type = chrec_type (to_add); 853169689Skan tree res = NULL_TREE; 854169689Skan 855169689Skan if (to_add == NULL_TREE) 856169689Skan return chrec_before; 857169689Skan 858169689Skan /* TO_ADD is either a scalar, or a parameter. TO_ADD is not 859169689Skan instantiated at this point. */ 860169689Skan if (TREE_CODE (to_add) == POLYNOMIAL_CHREC) 861169689Skan /* This should not happen. */ 862169689Skan return chrec_dont_know; 863169689Skan 864169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 865169689Skan { 866169689Skan fprintf (dump_file, "(add_to_evolution \n"); 867169689Skan fprintf (dump_file, " (loop_nb = %d)\n", loop_nb); 868169689Skan fprintf (dump_file, " (chrec_before = "); 869169689Skan print_generic_expr (dump_file, chrec_before, 0); 870169689Skan fprintf (dump_file, ")\n (to_add = "); 871169689Skan print_generic_expr (dump_file, to_add, 0); 872169689Skan fprintf (dump_file, ")\n"); 873169689Skan } 874169689Skan 875169689Skan if (code == MINUS_EXPR) 876169689Skan to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type) 877169689Skan ? build_real (type, dconstm1) 878169689Skan : build_int_cst_type (type, -1)); 879169689Skan 880169689Skan res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt); 881169689Skan 882169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 883169689Skan { 884169689Skan fprintf (dump_file, " (res = "); 885169689Skan print_generic_expr (dump_file, res, 0); 886169689Skan fprintf (dump_file, "))\n"); 887169689Skan } 888169689Skan 889169689Skan return res; 890169689Skan} 891169689Skan 892169689Skan/* Helper function. */ 893169689Skan 894169689Skanstatic inline tree 895169689Skanset_nb_iterations_in_loop (struct loop *loop, 896169689Skan tree res) 897169689Skan{ 898169689Skan tree type = chrec_type (res); 899169689Skan 900169689Skan res = chrec_fold_plus (type, res, build_int_cst (type, 1)); 901169689Skan 902169689Skan /* FIXME HWI: However we want to store one iteration less than the 903169689Skan count of the loop in order to be compatible with the other 904169689Skan nb_iter computations in loop-iv. This also allows the 905169689Skan representation of nb_iters that are equal to MAX_INT. */ 906169689Skan if (TREE_CODE (res) == INTEGER_CST 907169689Skan && (TREE_INT_CST_LOW (res) == 0 908169689Skan || TREE_OVERFLOW (res))) 909169689Skan res = chrec_dont_know; 910169689Skan 911169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 912169689Skan { 913169689Skan fprintf (dump_file, " (set_nb_iterations_in_loop = "); 914169689Skan print_generic_expr (dump_file, res, 0); 915169689Skan fprintf (dump_file, "))\n"); 916169689Skan } 917169689Skan 918169689Skan loop->nb_iterations = res; 919169689Skan return res; 920169689Skan} 921169689Skan 922169689Skan 923169689Skan 924169689Skan/* This section selects the loops that will be good candidates for the 925169689Skan scalar evolution analysis. For the moment, greedily select all the 926169689Skan loop nests we could analyze. */ 927169689Skan 928169689Skan/* Return true when it is possible to analyze the condition expression 929169689Skan EXPR. */ 930169689Skan 931169689Skanstatic bool 932169689Skananalyzable_condition (tree expr) 933169689Skan{ 934169689Skan tree condition; 935169689Skan 936169689Skan if (TREE_CODE (expr) != COND_EXPR) 937169689Skan return false; 938169689Skan 939169689Skan condition = TREE_OPERAND (expr, 0); 940169689Skan 941169689Skan switch (TREE_CODE (condition)) 942169689Skan { 943169689Skan case SSA_NAME: 944169689Skan return true; 945169689Skan 946169689Skan case LT_EXPR: 947169689Skan case LE_EXPR: 948169689Skan case GT_EXPR: 949169689Skan case GE_EXPR: 950169689Skan case EQ_EXPR: 951169689Skan case NE_EXPR: 952169689Skan return true; 953169689Skan 954169689Skan default: 955169689Skan return false; 956169689Skan } 957169689Skan 958169689Skan return false; 959169689Skan} 960169689Skan 961169689Skan/* For a loop with a single exit edge, return the COND_EXPR that 962169689Skan guards the exit edge. If the expression is too difficult to 963169689Skan analyze, then give up. */ 964169689Skan 965169689Skantree 966169689Skanget_loop_exit_condition (struct loop *loop) 967169689Skan{ 968169689Skan tree res = NULL_TREE; 969169689Skan edge exit_edge = loop->single_exit; 970169689Skan 971169689Skan 972169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 973169689Skan fprintf (dump_file, "(get_loop_exit_condition \n "); 974169689Skan 975169689Skan if (exit_edge) 976169689Skan { 977169689Skan tree expr; 978169689Skan 979169689Skan expr = last_stmt (exit_edge->src); 980169689Skan if (analyzable_condition (expr)) 981169689Skan res = expr; 982169689Skan } 983169689Skan 984169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 985169689Skan { 986169689Skan print_generic_expr (dump_file, res, 0); 987169689Skan fprintf (dump_file, ")\n"); 988169689Skan } 989169689Skan 990169689Skan return res; 991169689Skan} 992169689Skan 993169689Skan/* Recursively determine and enqueue the exit conditions for a loop. */ 994169689Skan 995169689Skanstatic void 996169689Skanget_exit_conditions_rec (struct loop *loop, 997169689Skan VEC(tree,heap) **exit_conditions) 998169689Skan{ 999169689Skan if (!loop) 1000169689Skan return; 1001169689Skan 1002169689Skan /* Recurse on the inner loops, then on the next (sibling) loops. */ 1003169689Skan get_exit_conditions_rec (loop->inner, exit_conditions); 1004169689Skan get_exit_conditions_rec (loop->next, exit_conditions); 1005169689Skan 1006169689Skan if (loop->single_exit) 1007169689Skan { 1008169689Skan tree loop_condition = get_loop_exit_condition (loop); 1009169689Skan 1010169689Skan if (loop_condition) 1011169689Skan VEC_safe_push (tree, heap, *exit_conditions, loop_condition); 1012169689Skan } 1013169689Skan} 1014169689Skan 1015169689Skan/* Select the candidate loop nests for the analysis. This function 1016169689Skan initializes the EXIT_CONDITIONS array. */ 1017169689Skan 1018169689Skanstatic void 1019169689Skanselect_loops_exit_conditions (struct loops *loops, 1020169689Skan VEC(tree,heap) **exit_conditions) 1021169689Skan{ 1022169689Skan struct loop *function_body = loops->parray[0]; 1023169689Skan 1024169689Skan get_exit_conditions_rec (function_body->inner, exit_conditions); 1025169689Skan} 1026169689Skan 1027169689Skan 1028169689Skan/* Depth first search algorithm. */ 1029169689Skan 1030169689Skantypedef enum t_bool { 1031169689Skan t_false, 1032169689Skan t_true, 1033169689Skan t_dont_know 1034169689Skan} t_bool; 1035169689Skan 1036169689Skan 1037169689Skanstatic t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int); 1038169689Skan 1039169689Skan/* Follow the ssa edge into the right hand side RHS of an assignment. 1040169689Skan Return true if the strongly connected component has been found. */ 1041169689Skan 1042169689Skanstatic t_bool 1043169689Skanfollow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs, 1044169689Skan tree halting_phi, tree *evolution_of_loop, int limit) 1045169689Skan{ 1046169689Skan t_bool res = t_false; 1047169689Skan tree rhs0, rhs1; 1048169689Skan tree type_rhs = TREE_TYPE (rhs); 1049169689Skan tree evol; 1050169689Skan 1051169689Skan /* The RHS is one of the following cases: 1052169689Skan - an SSA_NAME, 1053169689Skan - an INTEGER_CST, 1054169689Skan - a PLUS_EXPR, 1055169689Skan - a MINUS_EXPR, 1056169689Skan - an ASSERT_EXPR, 1057169689Skan - other cases are not yet handled. */ 1058169689Skan switch (TREE_CODE (rhs)) 1059169689Skan { 1060169689Skan case NOP_EXPR: 1061169689Skan /* This assignment is under the form "a_1 = (cast) rhs. */ 1062169689Skan res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0), 1063169689Skan halting_phi, evolution_of_loop, limit); 1064169689Skan *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), 1065169689Skan *evolution_of_loop, at_stmt); 1066169689Skan break; 1067169689Skan 1068169689Skan case INTEGER_CST: 1069169689Skan /* This assignment is under the form "a_1 = 7". */ 1070169689Skan res = t_false; 1071169689Skan break; 1072169689Skan 1073169689Skan case SSA_NAME: 1074169689Skan /* This assignment is under the form: "a_1 = b_2". */ 1075169689Skan res = follow_ssa_edge 1076169689Skan (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit); 1077169689Skan break; 1078169689Skan 1079169689Skan case PLUS_EXPR: 1080169689Skan /* This case is under the form "rhs0 + rhs1". */ 1081169689Skan rhs0 = TREE_OPERAND (rhs, 0); 1082169689Skan rhs1 = TREE_OPERAND (rhs, 1); 1083169689Skan STRIP_TYPE_NOPS (rhs0); 1084169689Skan STRIP_TYPE_NOPS (rhs1); 1085169689Skan 1086169689Skan if (TREE_CODE (rhs0) == SSA_NAME) 1087169689Skan { 1088169689Skan if (TREE_CODE (rhs1) == SSA_NAME) 1089169689Skan { 1090169689Skan /* Match an assignment under the form: 1091169689Skan "a = b + c". */ 1092169689Skan evol = *evolution_of_loop; 1093169689Skan res = follow_ssa_edge 1094169689Skan (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 1095169689Skan &evol, limit); 1096169689Skan 1097169689Skan if (res == t_true) 1098169689Skan *evolution_of_loop = add_to_evolution 1099169689Skan (loop->num, 1100169689Skan chrec_convert (type_rhs, evol, at_stmt), 1101169689Skan PLUS_EXPR, rhs1, at_stmt); 1102169689Skan 1103169689Skan else if (res == t_false) 1104169689Skan { 1105169689Skan res = follow_ssa_edge 1106169689Skan (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 1107169689Skan evolution_of_loop, limit); 1108169689Skan 1109169689Skan if (res == t_true) 1110169689Skan *evolution_of_loop = add_to_evolution 1111169689Skan (loop->num, 1112169689Skan chrec_convert (type_rhs, *evolution_of_loop, at_stmt), 1113169689Skan PLUS_EXPR, rhs0, at_stmt); 1114169689Skan 1115169689Skan else if (res == t_dont_know) 1116169689Skan *evolution_of_loop = chrec_dont_know; 1117169689Skan } 1118169689Skan 1119169689Skan else if (res == t_dont_know) 1120169689Skan *evolution_of_loop = chrec_dont_know; 1121169689Skan } 1122169689Skan 1123169689Skan else 1124169689Skan { 1125169689Skan /* Match an assignment under the form: 1126169689Skan "a = b + ...". */ 1127169689Skan res = follow_ssa_edge 1128169689Skan (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 1129169689Skan evolution_of_loop, limit); 1130169689Skan if (res == t_true) 1131169689Skan *evolution_of_loop = add_to_evolution 1132169689Skan (loop->num, chrec_convert (type_rhs, *evolution_of_loop, 1133169689Skan at_stmt), 1134169689Skan PLUS_EXPR, rhs1, at_stmt); 1135169689Skan 1136169689Skan else if (res == t_dont_know) 1137169689Skan *evolution_of_loop = chrec_dont_know; 1138169689Skan } 1139169689Skan } 1140169689Skan 1141169689Skan else if (TREE_CODE (rhs1) == SSA_NAME) 1142169689Skan { 1143169689Skan /* Match an assignment under the form: 1144169689Skan "a = ... + c". */ 1145169689Skan res = follow_ssa_edge 1146169689Skan (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 1147169689Skan evolution_of_loop, limit); 1148169689Skan if (res == t_true) 1149169689Skan *evolution_of_loop = add_to_evolution 1150169689Skan (loop->num, chrec_convert (type_rhs, *evolution_of_loop, 1151169689Skan at_stmt), 1152169689Skan PLUS_EXPR, rhs0, at_stmt); 1153169689Skan 1154169689Skan else if (res == t_dont_know) 1155169689Skan *evolution_of_loop = chrec_dont_know; 1156169689Skan } 1157169689Skan 1158169689Skan else 1159169689Skan /* Otherwise, match an assignment under the form: 1160169689Skan "a = ... + ...". */ 1161169689Skan /* And there is nothing to do. */ 1162169689Skan res = t_false; 1163169689Skan 1164169689Skan break; 1165169689Skan 1166169689Skan case MINUS_EXPR: 1167169689Skan /* This case is under the form "opnd0 = rhs0 - rhs1". */ 1168169689Skan rhs0 = TREE_OPERAND (rhs, 0); 1169169689Skan rhs1 = TREE_OPERAND (rhs, 1); 1170169689Skan STRIP_TYPE_NOPS (rhs0); 1171169689Skan STRIP_TYPE_NOPS (rhs1); 1172169689Skan 1173169689Skan if (TREE_CODE (rhs0) == SSA_NAME) 1174169689Skan { 1175169689Skan /* Match an assignment under the form: 1176169689Skan "a = b - ...". */ 1177169689Skan res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 1178169689Skan evolution_of_loop, limit); 1179169689Skan if (res == t_true) 1180169689Skan *evolution_of_loop = add_to_evolution 1181169689Skan (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt), 1182169689Skan MINUS_EXPR, rhs1, at_stmt); 1183169689Skan 1184169689Skan else if (res == t_dont_know) 1185169689Skan *evolution_of_loop = chrec_dont_know; 1186169689Skan } 1187169689Skan else 1188169689Skan /* Otherwise, match an assignment under the form: 1189169689Skan "a = ... - ...". */ 1190169689Skan /* And there is nothing to do. */ 1191169689Skan res = t_false; 1192169689Skan 1193169689Skan break; 1194169689Skan 1195169689Skan case ASSERT_EXPR: 1196169689Skan { 1197169689Skan /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>" 1198169689Skan It must be handled as a copy assignment of the form a_1 = a_2. */ 1199169689Skan tree op0 = ASSERT_EXPR_VAR (rhs); 1200169689Skan if (TREE_CODE (op0) == SSA_NAME) 1201169689Skan res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0), 1202169689Skan halting_phi, evolution_of_loop, limit); 1203169689Skan else 1204169689Skan res = t_false; 1205169689Skan break; 1206169689Skan } 1207169689Skan 1208169689Skan 1209169689Skan default: 1210169689Skan res = t_false; 1211169689Skan break; 1212169689Skan } 1213169689Skan 1214169689Skan return res; 1215169689Skan} 1216169689Skan 1217169689Skan/* Checks whether the I-th argument of a PHI comes from a backedge. */ 1218169689Skan 1219169689Skanstatic bool 1220169689Skanbackedge_phi_arg_p (tree phi, int i) 1221169689Skan{ 1222169689Skan edge e = PHI_ARG_EDGE (phi, i); 1223169689Skan 1224169689Skan /* We would in fact like to test EDGE_DFS_BACK here, but we do not care 1225169689Skan about updating it anywhere, and this should work as well most of the 1226169689Skan time. */ 1227169689Skan if (e->flags & EDGE_IRREDUCIBLE_LOOP) 1228169689Skan return true; 1229169689Skan 1230169689Skan return false; 1231169689Skan} 1232169689Skan 1233169689Skan/* Helper function for one branch of the condition-phi-node. Return 1234169689Skan true if the strongly connected component has been found following 1235169689Skan this path. */ 1236169689Skan 1237169689Skanstatic inline t_bool 1238169689Skanfollow_ssa_edge_in_condition_phi_branch (int i, 1239169689Skan struct loop *loop, 1240169689Skan tree condition_phi, 1241169689Skan tree halting_phi, 1242169689Skan tree *evolution_of_branch, 1243169689Skan tree init_cond, int limit) 1244169689Skan{ 1245169689Skan tree branch = PHI_ARG_DEF (condition_phi, i); 1246169689Skan *evolution_of_branch = chrec_dont_know; 1247169689Skan 1248169689Skan /* Do not follow back edges (they must belong to an irreducible loop, which 1249169689Skan we really do not want to worry about). */ 1250169689Skan if (backedge_phi_arg_p (condition_phi, i)) 1251169689Skan return t_false; 1252169689Skan 1253169689Skan if (TREE_CODE (branch) == SSA_NAME) 1254169689Skan { 1255169689Skan *evolution_of_branch = init_cond; 1256169689Skan return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, 1257169689Skan evolution_of_branch, limit); 1258169689Skan } 1259169689Skan 1260169689Skan /* This case occurs when one of the condition branches sets 1261169689Skan the variable to a constant: i.e. a phi-node like 1262169689Skan "a_2 = PHI <a_7(5), 2(6)>;". 1263169689Skan 1264169689Skan FIXME: This case have to be refined correctly: 1265169689Skan in some cases it is possible to say something better than 1266169689Skan chrec_dont_know, for example using a wrap-around notation. */ 1267169689Skan return t_false; 1268169689Skan} 1269169689Skan 1270169689Skan/* This function merges the branches of a condition-phi-node in a 1271169689Skan loop. */ 1272169689Skan 1273169689Skanstatic t_bool 1274169689Skanfollow_ssa_edge_in_condition_phi (struct loop *loop, 1275169689Skan tree condition_phi, 1276169689Skan tree halting_phi, 1277169689Skan tree *evolution_of_loop, int limit) 1278169689Skan{ 1279169689Skan int i; 1280169689Skan tree init = *evolution_of_loop; 1281169689Skan tree evolution_of_branch; 1282169689Skan t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi, 1283169689Skan halting_phi, 1284169689Skan &evolution_of_branch, 1285169689Skan init, limit); 1286169689Skan if (res == t_false || res == t_dont_know) 1287169689Skan return res; 1288169689Skan 1289169689Skan *evolution_of_loop = evolution_of_branch; 1290169689Skan 1291169689Skan for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++) 1292169689Skan { 1293169689Skan /* Quickly give up when the evolution of one of the branches is 1294169689Skan not known. */ 1295169689Skan if (*evolution_of_loop == chrec_dont_know) 1296169689Skan return t_true; 1297169689Skan 1298169689Skan res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi, 1299169689Skan halting_phi, 1300169689Skan &evolution_of_branch, 1301169689Skan init, limit); 1302169689Skan if (res == t_false || res == t_dont_know) 1303169689Skan return res; 1304169689Skan 1305169689Skan *evolution_of_loop = chrec_merge (*evolution_of_loop, 1306169689Skan evolution_of_branch); 1307169689Skan } 1308169689Skan 1309169689Skan return t_true; 1310169689Skan} 1311169689Skan 1312169689Skan/* Follow an SSA edge in an inner loop. It computes the overall 1313169689Skan effect of the loop, and following the symbolic initial conditions, 1314169689Skan it follows the edges in the parent loop. The inner loop is 1315169689Skan considered as a single statement. */ 1316169689Skan 1317169689Skanstatic t_bool 1318169689Skanfollow_ssa_edge_inner_loop_phi (struct loop *outer_loop, 1319169689Skan tree loop_phi_node, 1320169689Skan tree halting_phi, 1321169689Skan tree *evolution_of_loop, int limit) 1322169689Skan{ 1323169689Skan struct loop *loop = loop_containing_stmt (loop_phi_node); 1324169689Skan tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node)); 1325169689Skan 1326169689Skan /* Sometimes, the inner loop is too difficult to analyze, and the 1327169689Skan result of the analysis is a symbolic parameter. */ 1328169689Skan if (ev == PHI_RESULT (loop_phi_node)) 1329169689Skan { 1330169689Skan t_bool res = t_false; 1331169689Skan int i; 1332169689Skan 1333169689Skan for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) 1334169689Skan { 1335169689Skan tree arg = PHI_ARG_DEF (loop_phi_node, i); 1336169689Skan basic_block bb; 1337169689Skan 1338169689Skan /* Follow the edges that exit the inner loop. */ 1339169689Skan bb = PHI_ARG_EDGE (loop_phi_node, i)->src; 1340169689Skan if (!flow_bb_inside_loop_p (loop, bb)) 1341169689Skan res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, 1342169689Skan arg, halting_phi, 1343169689Skan evolution_of_loop, limit); 1344169689Skan if (res == t_true) 1345169689Skan break; 1346169689Skan } 1347169689Skan 1348169689Skan /* If the path crosses this loop-phi, give up. */ 1349169689Skan if (res == t_true) 1350169689Skan *evolution_of_loop = chrec_dont_know; 1351169689Skan 1352169689Skan return res; 1353169689Skan } 1354169689Skan 1355169689Skan /* Otherwise, compute the overall effect of the inner loop. */ 1356169689Skan ev = compute_overall_effect_of_inner_loop (loop, ev); 1357169689Skan return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi, 1358169689Skan evolution_of_loop, limit); 1359169689Skan} 1360169689Skan 1361169689Skan/* Follow an SSA edge from a loop-phi-node to itself, constructing a 1362169689Skan path that is analyzed on the return walk. */ 1363169689Skan 1364169689Skanstatic t_bool 1365169689Skanfollow_ssa_edge (struct loop *loop, tree def, tree halting_phi, 1366169689Skan tree *evolution_of_loop, int limit) 1367169689Skan{ 1368169689Skan struct loop *def_loop; 1369169689Skan 1370169689Skan if (TREE_CODE (def) == NOP_EXPR) 1371169689Skan return t_false; 1372169689Skan 1373169689Skan /* Give up if the path is longer than the MAX that we allow. */ 1374169689Skan if (limit++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 1375169689Skan return t_dont_know; 1376169689Skan 1377169689Skan def_loop = loop_containing_stmt (def); 1378169689Skan 1379169689Skan switch (TREE_CODE (def)) 1380169689Skan { 1381169689Skan case PHI_NODE: 1382169689Skan if (!loop_phi_node_p (def)) 1383169689Skan /* DEF is a condition-phi-node. Follow the branches, and 1384169689Skan record their evolutions. Finally, merge the collected 1385169689Skan information and set the approximation to the main 1386169689Skan variable. */ 1387169689Skan return follow_ssa_edge_in_condition_phi 1388169689Skan (loop, def, halting_phi, evolution_of_loop, limit); 1389169689Skan 1390169689Skan /* When the analyzed phi is the halting_phi, the 1391169689Skan depth-first search is over: we have found a path from 1392169689Skan the halting_phi to itself in the loop. */ 1393169689Skan if (def == halting_phi) 1394169689Skan return t_true; 1395169689Skan 1396169689Skan /* Otherwise, the evolution of the HALTING_PHI depends 1397169689Skan on the evolution of another loop-phi-node, i.e. the 1398169689Skan evolution function is a higher degree polynomial. */ 1399169689Skan if (def_loop == loop) 1400169689Skan return t_false; 1401169689Skan 1402169689Skan /* Inner loop. */ 1403169689Skan if (flow_loop_nested_p (loop, def_loop)) 1404169689Skan return follow_ssa_edge_inner_loop_phi 1405169689Skan (loop, def, halting_phi, evolution_of_loop, limit); 1406169689Skan 1407169689Skan /* Outer loop. */ 1408169689Skan return t_false; 1409169689Skan 1410169689Skan case MODIFY_EXPR: 1411169689Skan return follow_ssa_edge_in_rhs (loop, def, 1412169689Skan TREE_OPERAND (def, 1), 1413169689Skan halting_phi, 1414169689Skan evolution_of_loop, limit); 1415169689Skan 1416169689Skan default: 1417169689Skan /* At this level of abstraction, the program is just a set 1418169689Skan of MODIFY_EXPRs and PHI_NODEs. In principle there is no 1419169689Skan other node to be handled. */ 1420169689Skan return t_false; 1421169689Skan } 1422169689Skan} 1423169689Skan 1424169689Skan 1425169689Skan 1426169689Skan/* Given a LOOP_PHI_NODE, this function determines the evolution 1427169689Skan function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */ 1428169689Skan 1429169689Skanstatic tree 1430169689Skananalyze_evolution_in_loop (tree loop_phi_node, 1431169689Skan tree init_cond) 1432169689Skan{ 1433169689Skan int i; 1434169689Skan tree evolution_function = chrec_not_analyzed_yet; 1435169689Skan struct loop *loop = loop_containing_stmt (loop_phi_node); 1436169689Skan basic_block bb; 1437169689Skan 1438169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1439169689Skan { 1440169689Skan fprintf (dump_file, "(analyze_evolution_in_loop \n"); 1441169689Skan fprintf (dump_file, " (loop_phi_node = "); 1442169689Skan print_generic_expr (dump_file, loop_phi_node, 0); 1443169689Skan fprintf (dump_file, ")\n"); 1444169689Skan } 1445169689Skan 1446169689Skan for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) 1447169689Skan { 1448169689Skan tree arg = PHI_ARG_DEF (loop_phi_node, i); 1449169689Skan tree ssa_chain, ev_fn; 1450169689Skan t_bool res; 1451169689Skan 1452169689Skan /* Select the edges that enter the loop body. */ 1453169689Skan bb = PHI_ARG_EDGE (loop_phi_node, i)->src; 1454169689Skan if (!flow_bb_inside_loop_p (loop, bb)) 1455169689Skan continue; 1456169689Skan 1457169689Skan if (TREE_CODE (arg) == SSA_NAME) 1458169689Skan { 1459169689Skan ssa_chain = SSA_NAME_DEF_STMT (arg); 1460169689Skan 1461169689Skan /* Pass in the initial condition to the follow edge function. */ 1462169689Skan ev_fn = init_cond; 1463169689Skan res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0); 1464169689Skan } 1465169689Skan else 1466169689Skan res = t_false; 1467169689Skan 1468169689Skan /* When it is impossible to go back on the same 1469169689Skan loop_phi_node by following the ssa edges, the 1470169689Skan evolution is represented by a peeled chrec, i.e. the 1471169689Skan first iteration, EV_FN has the value INIT_COND, then 1472169689Skan all the other iterations it has the value of ARG. 1473169689Skan For the moment, PEELED_CHREC nodes are not built. */ 1474169689Skan if (res != t_true) 1475169689Skan ev_fn = chrec_dont_know; 1476169689Skan 1477169689Skan /* When there are multiple back edges of the loop (which in fact never 1478169689Skan happens currently, but nevertheless), merge their evolutions. */ 1479169689Skan evolution_function = chrec_merge (evolution_function, ev_fn); 1480169689Skan } 1481169689Skan 1482169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1483169689Skan { 1484169689Skan fprintf (dump_file, " (evolution_function = "); 1485169689Skan print_generic_expr (dump_file, evolution_function, 0); 1486169689Skan fprintf (dump_file, "))\n"); 1487169689Skan } 1488169689Skan 1489169689Skan return evolution_function; 1490169689Skan} 1491169689Skan 1492169689Skan/* Given a loop-phi-node, return the initial conditions of the 1493169689Skan variable on entry of the loop. When the CCP has propagated 1494169689Skan constants into the loop-phi-node, the initial condition is 1495169689Skan instantiated, otherwise the initial condition is kept symbolic. 1496169689Skan This analyzer does not analyze the evolution outside the current 1497169689Skan loop, and leaves this task to the on-demand tree reconstructor. */ 1498169689Skan 1499169689Skanstatic tree 1500169689Skananalyze_initial_condition (tree loop_phi_node) 1501169689Skan{ 1502169689Skan int i; 1503169689Skan tree init_cond = chrec_not_analyzed_yet; 1504169689Skan struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father; 1505169689Skan 1506169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1507169689Skan { 1508169689Skan fprintf (dump_file, "(analyze_initial_condition \n"); 1509169689Skan fprintf (dump_file, " (loop_phi_node = \n"); 1510169689Skan print_generic_expr (dump_file, loop_phi_node, 0); 1511169689Skan fprintf (dump_file, ")\n"); 1512169689Skan } 1513169689Skan 1514169689Skan for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) 1515169689Skan { 1516169689Skan tree branch = PHI_ARG_DEF (loop_phi_node, i); 1517169689Skan basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src; 1518169689Skan 1519169689Skan /* When the branch is oriented to the loop's body, it does 1520169689Skan not contribute to the initial condition. */ 1521169689Skan if (flow_bb_inside_loop_p (loop, bb)) 1522169689Skan continue; 1523169689Skan 1524169689Skan if (init_cond == chrec_not_analyzed_yet) 1525169689Skan { 1526169689Skan init_cond = branch; 1527169689Skan continue; 1528169689Skan } 1529169689Skan 1530169689Skan if (TREE_CODE (branch) == SSA_NAME) 1531169689Skan { 1532169689Skan init_cond = chrec_dont_know; 1533169689Skan break; 1534169689Skan } 1535169689Skan 1536169689Skan init_cond = chrec_merge (init_cond, branch); 1537169689Skan } 1538169689Skan 1539169689Skan /* Ooops -- a loop without an entry??? */ 1540169689Skan if (init_cond == chrec_not_analyzed_yet) 1541169689Skan init_cond = chrec_dont_know; 1542169689Skan 1543169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1544169689Skan { 1545169689Skan fprintf (dump_file, " (init_cond = "); 1546169689Skan print_generic_expr (dump_file, init_cond, 0); 1547169689Skan fprintf (dump_file, "))\n"); 1548169689Skan } 1549169689Skan 1550169689Skan return init_cond; 1551169689Skan} 1552169689Skan 1553169689Skan/* Analyze the scalar evolution for LOOP_PHI_NODE. */ 1554169689Skan 1555169689Skanstatic tree 1556169689Skaninterpret_loop_phi (struct loop *loop, tree loop_phi_node) 1557169689Skan{ 1558169689Skan tree res; 1559169689Skan struct loop *phi_loop = loop_containing_stmt (loop_phi_node); 1560169689Skan tree init_cond; 1561169689Skan 1562169689Skan if (phi_loop != loop) 1563169689Skan { 1564169689Skan struct loop *subloop; 1565169689Skan tree evolution_fn = analyze_scalar_evolution 1566169689Skan (phi_loop, PHI_RESULT (loop_phi_node)); 1567169689Skan 1568169689Skan /* Dive one level deeper. */ 1569169689Skan subloop = superloop_at_depth (phi_loop, loop->depth + 1); 1570169689Skan 1571169689Skan /* Interpret the subloop. */ 1572169689Skan res = compute_overall_effect_of_inner_loop (subloop, evolution_fn); 1573169689Skan return res; 1574169689Skan } 1575169689Skan 1576169689Skan /* Otherwise really interpret the loop phi. */ 1577169689Skan init_cond = analyze_initial_condition (loop_phi_node); 1578169689Skan res = analyze_evolution_in_loop (loop_phi_node, init_cond); 1579169689Skan 1580169689Skan return res; 1581169689Skan} 1582169689Skan 1583169689Skan/* This function merges the branches of a condition-phi-node, 1584169689Skan contained in the outermost loop, and whose arguments are already 1585169689Skan analyzed. */ 1586169689Skan 1587169689Skanstatic tree 1588169689Skaninterpret_condition_phi (struct loop *loop, tree condition_phi) 1589169689Skan{ 1590169689Skan int i; 1591169689Skan tree res = chrec_not_analyzed_yet; 1592169689Skan 1593169689Skan for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++) 1594169689Skan { 1595169689Skan tree branch_chrec; 1596169689Skan 1597169689Skan if (backedge_phi_arg_p (condition_phi, i)) 1598169689Skan { 1599169689Skan res = chrec_dont_know; 1600169689Skan break; 1601169689Skan } 1602169689Skan 1603169689Skan branch_chrec = analyze_scalar_evolution 1604169689Skan (loop, PHI_ARG_DEF (condition_phi, i)); 1605169689Skan 1606169689Skan res = chrec_merge (res, branch_chrec); 1607169689Skan } 1608169689Skan 1609169689Skan return res; 1610169689Skan} 1611169689Skan 1612169689Skan/* Interpret the right hand side of a modify_expr OPND1. If we didn't 1613169689Skan analyze this node before, follow the definitions until ending 1614169689Skan either on an analyzed modify_expr, or on a loop-phi-node. On the 1615169689Skan return path, this function propagates evolutions (ala constant copy 1616169689Skan propagation). OPND1 is not a GIMPLE expression because we could 1617169689Skan analyze the effect of an inner loop: see interpret_loop_phi. */ 1618169689Skan 1619169689Skanstatic tree 1620169689Skaninterpret_rhs_modify_expr (struct loop *loop, tree at_stmt, 1621169689Skan tree opnd1, tree type) 1622169689Skan{ 1623169689Skan tree res, opnd10, opnd11, chrec10, chrec11; 1624169689Skan 1625169689Skan if (is_gimple_min_invariant (opnd1)) 1626169689Skan return chrec_convert (type, opnd1, at_stmt); 1627169689Skan 1628169689Skan switch (TREE_CODE (opnd1)) 1629169689Skan { 1630169689Skan case PLUS_EXPR: 1631169689Skan opnd10 = TREE_OPERAND (opnd1, 0); 1632169689Skan opnd11 = TREE_OPERAND (opnd1, 1); 1633169689Skan chrec10 = analyze_scalar_evolution (loop, opnd10); 1634169689Skan chrec11 = analyze_scalar_evolution (loop, opnd11); 1635169689Skan chrec10 = chrec_convert (type, chrec10, at_stmt); 1636169689Skan chrec11 = chrec_convert (type, chrec11, at_stmt); 1637169689Skan res = chrec_fold_plus (type, chrec10, chrec11); 1638169689Skan break; 1639169689Skan 1640169689Skan case MINUS_EXPR: 1641169689Skan opnd10 = TREE_OPERAND (opnd1, 0); 1642169689Skan opnd11 = TREE_OPERAND (opnd1, 1); 1643169689Skan chrec10 = analyze_scalar_evolution (loop, opnd10); 1644169689Skan chrec11 = analyze_scalar_evolution (loop, opnd11); 1645169689Skan chrec10 = chrec_convert (type, chrec10, at_stmt); 1646169689Skan chrec11 = chrec_convert (type, chrec11, at_stmt); 1647169689Skan res = chrec_fold_minus (type, chrec10, chrec11); 1648169689Skan break; 1649169689Skan 1650169689Skan case NEGATE_EXPR: 1651169689Skan opnd10 = TREE_OPERAND (opnd1, 0); 1652169689Skan chrec10 = analyze_scalar_evolution (loop, opnd10); 1653169689Skan chrec10 = chrec_convert (type, chrec10, at_stmt); 1654169689Skan /* TYPE may be integer, real or complex, so use fold_convert. */ 1655169689Skan res = chrec_fold_multiply (type, chrec10, 1656169689Skan fold_convert (type, integer_minus_one_node)); 1657169689Skan break; 1658169689Skan 1659169689Skan case MULT_EXPR: 1660169689Skan opnd10 = TREE_OPERAND (opnd1, 0); 1661169689Skan opnd11 = TREE_OPERAND (opnd1, 1); 1662169689Skan chrec10 = analyze_scalar_evolution (loop, opnd10); 1663169689Skan chrec11 = analyze_scalar_evolution (loop, opnd11); 1664169689Skan chrec10 = chrec_convert (type, chrec10, at_stmt); 1665169689Skan chrec11 = chrec_convert (type, chrec11, at_stmt); 1666169689Skan res = chrec_fold_multiply (type, chrec10, chrec11); 1667169689Skan break; 1668169689Skan 1669169689Skan case SSA_NAME: 1670169689Skan res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1), 1671169689Skan at_stmt); 1672169689Skan break; 1673169689Skan 1674169689Skan case ASSERT_EXPR: 1675169689Skan opnd10 = ASSERT_EXPR_VAR (opnd1); 1676169689Skan res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10), 1677169689Skan at_stmt); 1678169689Skan break; 1679169689Skan 1680169689Skan case NOP_EXPR: 1681169689Skan case CONVERT_EXPR: 1682169689Skan opnd10 = TREE_OPERAND (opnd1, 0); 1683169689Skan chrec10 = analyze_scalar_evolution (loop, opnd10); 1684169689Skan res = chrec_convert (type, chrec10, at_stmt); 1685169689Skan break; 1686169689Skan 1687169689Skan default: 1688169689Skan res = chrec_dont_know; 1689169689Skan break; 1690169689Skan } 1691169689Skan 1692169689Skan return res; 1693169689Skan} 1694169689Skan 1695169689Skan 1696169689Skan 1697169689Skan/* This section contains all the entry points: 1698169689Skan - number_of_iterations_in_loop, 1699169689Skan - analyze_scalar_evolution, 1700169689Skan - instantiate_parameters. 1701169689Skan*/ 1702169689Skan 1703169689Skan/* Compute and return the evolution function in WRTO_LOOP, the nearest 1704169689Skan common ancestor of DEF_LOOP and USE_LOOP. */ 1705169689Skan 1706169689Skanstatic tree 1707169689Skancompute_scalar_evolution_in_loop (struct loop *wrto_loop, 1708169689Skan struct loop *def_loop, 1709169689Skan tree ev) 1710169689Skan{ 1711169689Skan tree res; 1712169689Skan if (def_loop == wrto_loop) 1713169689Skan return ev; 1714169689Skan 1715169689Skan def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1); 1716169689Skan res = compute_overall_effect_of_inner_loop (def_loop, ev); 1717169689Skan 1718169689Skan return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet); 1719169689Skan} 1720169689Skan 1721169689Skan/* Folds EXPR, if it is a cast to pointer, assuming that the created 1722169689Skan polynomial_chrec does not wrap. */ 1723169689Skan 1724169689Skanstatic tree 1725169689Skanfold_used_pointer_cast (tree expr) 1726169689Skan{ 1727169689Skan tree op; 1728169689Skan tree type, inner_type; 1729169689Skan 1730169689Skan if (TREE_CODE (expr) != NOP_EXPR && TREE_CODE (expr) != CONVERT_EXPR) 1731169689Skan return expr; 1732169689Skan 1733169689Skan op = TREE_OPERAND (expr, 0); 1734169689Skan if (TREE_CODE (op) != POLYNOMIAL_CHREC) 1735169689Skan return expr; 1736169689Skan 1737169689Skan type = TREE_TYPE (expr); 1738169689Skan inner_type = TREE_TYPE (op); 1739169689Skan 1740169689Skan if (!INTEGRAL_TYPE_P (inner_type) 1741169689Skan || TYPE_PRECISION (inner_type) != TYPE_PRECISION (type)) 1742169689Skan return expr; 1743169689Skan 1744169689Skan return build_polynomial_chrec (CHREC_VARIABLE (op), 1745169689Skan chrec_convert (type, CHREC_LEFT (op), NULL_TREE), 1746169689Skan chrec_convert (type, CHREC_RIGHT (op), NULL_TREE)); 1747169689Skan} 1748169689Skan 1749169689Skan/* Returns true if EXPR is an expression corresponding to offset of pointer 1750169689Skan in p + offset. */ 1751169689Skan 1752169689Skanstatic bool 1753169689Skanpointer_offset_p (tree expr) 1754169689Skan{ 1755169689Skan if (TREE_CODE (expr) == INTEGER_CST) 1756169689Skan return true; 1757169689Skan 1758169689Skan if ((TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR) 1759169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))) 1760169689Skan return true; 1761169689Skan 1762169689Skan return false; 1763169689Skan} 1764169689Skan 1765169689Skan/* EXPR is a scalar evolution of a pointer that is dereferenced or used in 1766169689Skan comparison. This means that it must point to a part of some object in 1767169689Skan memory, which enables us to argue about overflows and possibly simplify 1768169689Skan the EXPR. AT_STMT is the statement in which this conversion has to be 1769169689Skan performed. Returns the simplified value. 1770169689Skan 1771169689Skan Currently, for 1772169689Skan 1773169689Skan int i, n; 1774169689Skan int *p; 1775169689Skan 1776169689Skan for (i = -n; i < n; i++) 1777169689Skan *(p + i) = ...; 1778169689Skan 1779169689Skan We generate the following code (assuming that size of int and size_t is 1780169689Skan 4 bytes): 1781169689Skan 1782169689Skan for (i = -n; i < n; i++) 1783169689Skan { 1784169689Skan size_t tmp1, tmp2; 1785169689Skan int *tmp3, *tmp4; 1786169689Skan 1787169689Skan tmp1 = (size_t) i; (1) 1788169689Skan tmp2 = 4 * tmp1; (2) 1789169689Skan tmp3 = (int *) tmp2; (3) 1790169689Skan tmp4 = p + tmp3; (4) 1791169689Skan 1792169689Skan *tmp4 = ...; 1793169689Skan } 1794169689Skan 1795169689Skan We in general assume that pointer arithmetics does not overflow (since its 1796169689Skan behavior is undefined in that case). One of the problems is that our 1797169689Skan translation does not capture this property very well -- (int *) is 1798169689Skan considered unsigned, hence the computation in (4) does overflow if i is 1799169689Skan negative. 1800169689Skan 1801169689Skan This impreciseness creates complications in scev analysis. The scalar 1802169689Skan evolution of i is [-n, +, 1]. Since int and size_t have the same precision 1803169689Skan (in this example), and size_t is unsigned (so we do not care about 1804169689Skan overflows), we succeed to derive that scev of tmp1 is [(size_t) -n, +, 1] 1805169689Skan and scev of tmp2 is [4 * (size_t) -n, +, 4]. With tmp3, we run into 1806169689Skan problem -- [(int *) (4 * (size_t) -n), +, 4] wraps, and since we on several 1807169689Skan places assume that this is not the case for scevs with pointer type, we 1808169689Skan cannot use this scev for tmp3; hence, its scev is 1809169689Skan (int *) [(4 * (size_t) -n), +, 4], and scev of tmp4 is 1810169689Skan p + (int *) [(4 * (size_t) -n), +, 4]. Most of the optimizers are unable to 1811169689Skan work with scevs of this shape. 1812169689Skan 1813169689Skan However, since tmp4 is dereferenced, all its values must belong to a single 1814169689Skan object, and taking into account that the precision of int * and size_t is 1815169689Skan the same, it is impossible for its scev to wrap. Hence, we can derive that 1816169689Skan its evolution is [p + (int *) (4 * (size_t) -n), +, 4], which the optimizers 1817169689Skan can work with. 1818169689Skan 1819169689Skan ??? Maybe we should use different representation for pointer arithmetics, 1820169689Skan however that is a long-term project with a lot of potential for creating 1821169689Skan bugs. */ 1822169689Skan 1823169689Skanstatic tree 1824169689Skanfold_used_pointer (tree expr, tree at_stmt) 1825169689Skan{ 1826169689Skan tree op0, op1, new0, new1; 1827169689Skan enum tree_code code = TREE_CODE (expr); 1828169689Skan 1829169689Skan if (code == PLUS_EXPR 1830169689Skan || code == MINUS_EXPR) 1831169689Skan { 1832169689Skan op0 = TREE_OPERAND (expr, 0); 1833169689Skan op1 = TREE_OPERAND (expr, 1); 1834169689Skan 1835169689Skan if (pointer_offset_p (op1)) 1836169689Skan { 1837169689Skan new0 = fold_used_pointer (op0, at_stmt); 1838169689Skan new1 = fold_used_pointer_cast (op1); 1839169689Skan } 1840169689Skan else if (code == PLUS_EXPR && pointer_offset_p (op0)) 1841169689Skan { 1842169689Skan new0 = fold_used_pointer_cast (op0); 1843169689Skan new1 = fold_used_pointer (op1, at_stmt); 1844169689Skan } 1845169689Skan else 1846169689Skan return expr; 1847169689Skan 1848169689Skan if (new0 == op0 && new1 == op1) 1849169689Skan return expr; 1850169689Skan 1851169689Skan new0 = chrec_convert (TREE_TYPE (expr), new0, at_stmt); 1852169689Skan new1 = chrec_convert (TREE_TYPE (expr), new1, at_stmt); 1853169689Skan 1854169689Skan if (code == PLUS_EXPR) 1855169689Skan expr = chrec_fold_plus (TREE_TYPE (expr), new0, new1); 1856169689Skan else 1857169689Skan expr = chrec_fold_minus (TREE_TYPE (expr), new0, new1); 1858169689Skan 1859169689Skan return expr; 1860169689Skan } 1861169689Skan else 1862169689Skan return fold_used_pointer_cast (expr); 1863169689Skan} 1864169689Skan 1865169689Skan/* Returns true if PTR is dereferenced, or used in comparison. */ 1866169689Skan 1867169689Skanstatic bool 1868169689Skanpointer_used_p (tree ptr) 1869169689Skan{ 1870169689Skan use_operand_p use_p; 1871169689Skan imm_use_iterator imm_iter; 1872169689Skan tree stmt, rhs; 1873169689Skan struct ptr_info_def *pi = get_ptr_info (ptr); 1874169689Skan var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr)); 1875169689Skan 1876169689Skan /* Check whether the pointer has a memory tag; if it does, it is 1877169689Skan (or at least used to be) dereferenced. */ 1878169689Skan if ((pi != NULL && pi->name_mem_tag != NULL) 1879169689Skan || v_ann->symbol_mem_tag) 1880169689Skan return true; 1881169689Skan 1882169689Skan FOR_EACH_IMM_USE_FAST (use_p, imm_iter, ptr) 1883169689Skan { 1884169689Skan stmt = USE_STMT (use_p); 1885169689Skan if (TREE_CODE (stmt) == COND_EXPR) 1886169689Skan return true; 1887169689Skan 1888169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 1889169689Skan continue; 1890169689Skan 1891169689Skan rhs = TREE_OPERAND (stmt, 1); 1892169689Skan if (!COMPARISON_CLASS_P (rhs)) 1893169689Skan continue; 1894169689Skan 1895169689Skan if (TREE_OPERAND (stmt, 0) == ptr 1896169689Skan || TREE_OPERAND (stmt, 1) == ptr) 1897169689Skan return true; 1898169689Skan } 1899169689Skan 1900169689Skan return false; 1901169689Skan} 1902169689Skan 1903169689Skan/* Helper recursive function. */ 1904169689Skan 1905169689Skanstatic tree 1906169689Skananalyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) 1907169689Skan{ 1908169689Skan tree def, type = TREE_TYPE (var); 1909169689Skan basic_block bb; 1910169689Skan struct loop *def_loop; 1911169689Skan 1912169689Skan if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE) 1913169689Skan return chrec_dont_know; 1914169689Skan 1915169689Skan if (TREE_CODE (var) != SSA_NAME) 1916169689Skan return interpret_rhs_modify_expr (loop, NULL_TREE, var, type); 1917169689Skan 1918169689Skan def = SSA_NAME_DEF_STMT (var); 1919169689Skan bb = bb_for_stmt (def); 1920169689Skan def_loop = bb ? bb->loop_father : NULL; 1921169689Skan 1922169689Skan if (bb == NULL 1923169689Skan || !flow_bb_inside_loop_p (loop, bb)) 1924169689Skan { 1925169689Skan /* Keep the symbolic form. */ 1926169689Skan res = var; 1927169689Skan goto set_and_end; 1928169689Skan } 1929169689Skan 1930169689Skan if (res != chrec_not_analyzed_yet) 1931169689Skan { 1932169689Skan if (loop != bb->loop_father) 1933169689Skan res = compute_scalar_evolution_in_loop 1934169689Skan (find_common_loop (loop, bb->loop_father), bb->loop_father, res); 1935169689Skan 1936169689Skan goto set_and_end; 1937169689Skan } 1938169689Skan 1939169689Skan if (loop != def_loop) 1940169689Skan { 1941169689Skan res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet); 1942169689Skan res = compute_scalar_evolution_in_loop (loop, def_loop, res); 1943169689Skan 1944169689Skan goto set_and_end; 1945169689Skan } 1946169689Skan 1947169689Skan switch (TREE_CODE (def)) 1948169689Skan { 1949169689Skan case MODIFY_EXPR: 1950169689Skan res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type); 1951169689Skan 1952169689Skan if (POINTER_TYPE_P (type) 1953169689Skan && !automatically_generated_chrec_p (res) 1954169689Skan && pointer_used_p (var)) 1955169689Skan res = fold_used_pointer (res, def); 1956169689Skan break; 1957169689Skan 1958169689Skan case PHI_NODE: 1959169689Skan if (loop_phi_node_p (def)) 1960169689Skan res = interpret_loop_phi (loop, def); 1961169689Skan else 1962169689Skan res = interpret_condition_phi (loop, def); 1963169689Skan break; 1964169689Skan 1965169689Skan default: 1966169689Skan res = chrec_dont_know; 1967169689Skan break; 1968169689Skan } 1969169689Skan 1970169689Skan set_and_end: 1971169689Skan 1972169689Skan /* Keep the symbolic form. */ 1973169689Skan if (res == chrec_dont_know) 1974169689Skan res = var; 1975169689Skan 1976169689Skan if (loop == def_loop) 1977169689Skan set_scalar_evolution (var, res); 1978169689Skan 1979169689Skan return res; 1980169689Skan} 1981169689Skan 1982169689Skan/* Entry point for the scalar evolution analyzer. 1983169689Skan Analyzes and returns the scalar evolution of the ssa_name VAR. 1984169689Skan LOOP_NB is the identifier number of the loop in which the variable 1985169689Skan is used. 1986169689Skan 1987169689Skan Example of use: having a pointer VAR to a SSA_NAME node, STMT a 1988169689Skan pointer to the statement that uses this variable, in order to 1989169689Skan determine the evolution function of the variable, use the following 1990169689Skan calls: 1991169689Skan 1992169689Skan unsigned loop_nb = loop_containing_stmt (stmt)->num; 1993169689Skan tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var); 1994169689Skan tree chrec_instantiated = instantiate_parameters 1995169689Skan (loop_nb, chrec_with_symbols); 1996169689Skan*/ 1997169689Skan 1998169689Skantree 1999169689Skananalyze_scalar_evolution (struct loop *loop, tree var) 2000169689Skan{ 2001169689Skan tree res; 2002169689Skan 2003169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2004169689Skan { 2005169689Skan fprintf (dump_file, "(analyze_scalar_evolution \n"); 2006169689Skan fprintf (dump_file, " (loop_nb = %d)\n", loop->num); 2007169689Skan fprintf (dump_file, " (scalar = "); 2008169689Skan print_generic_expr (dump_file, var, 0); 2009169689Skan fprintf (dump_file, ")\n"); 2010169689Skan } 2011169689Skan 2012169689Skan res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var)); 2013169689Skan 2014169689Skan if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know) 2015169689Skan res = var; 2016169689Skan 2017169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2018169689Skan fprintf (dump_file, ")\n"); 2019169689Skan 2020169689Skan return res; 2021169689Skan} 2022169689Skan 2023169689Skan/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to 2024169689Skan WRTO_LOOP (which should be a superloop of both USE_LOOP and definition 2025169689Skan of VERSION). 2026169689Skan 2027169689Skan FOLDED_CASTS is set to true if resolve_mixers used 2028169689Skan chrec_convert_aggressive (TODO -- not really, we are way too conservative 2029169689Skan at the moment in order to keep things simple). */ 2030169689Skan 2031169689Skanstatic tree 2032169689Skananalyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop, 2033169689Skan tree version, bool *folded_casts) 2034169689Skan{ 2035169689Skan bool val = false; 2036169689Skan tree ev = version, tmp; 2037169689Skan 2038169689Skan if (folded_casts) 2039169689Skan *folded_casts = false; 2040169689Skan while (1) 2041169689Skan { 2042169689Skan tmp = analyze_scalar_evolution (use_loop, ev); 2043169689Skan ev = resolve_mixers (use_loop, tmp); 2044169689Skan 2045169689Skan if (folded_casts && tmp != ev) 2046169689Skan *folded_casts = true; 2047169689Skan 2048169689Skan if (use_loop == wrto_loop) 2049169689Skan return ev; 2050169689Skan 2051169689Skan /* If the value of the use changes in the inner loop, we cannot express 2052169689Skan its value in the outer loop (we might try to return interval chrec, 2053169689Skan but we do not have a user for it anyway) */ 2054169689Skan if (!no_evolution_in_loop_p (ev, use_loop->num, &val) 2055169689Skan || !val) 2056169689Skan return chrec_dont_know; 2057169689Skan 2058169689Skan use_loop = use_loop->outer; 2059169689Skan } 2060169689Skan} 2061169689Skan 2062169689Skan/* Returns instantiated value for VERSION in CACHE. */ 2063169689Skan 2064169689Skanstatic tree 2065169689Skanget_instantiated_value (htab_t cache, tree version) 2066169689Skan{ 2067169689Skan struct scev_info_str *info, pattern; 2068169689Skan 2069169689Skan pattern.var = version; 2070169689Skan info = (struct scev_info_str *) htab_find (cache, &pattern); 2071169689Skan 2072169689Skan if (info) 2073169689Skan return info->chrec; 2074169689Skan else 2075169689Skan return NULL_TREE; 2076169689Skan} 2077169689Skan 2078169689Skan/* Sets instantiated value for VERSION to VAL in CACHE. */ 2079169689Skan 2080169689Skanstatic void 2081169689Skanset_instantiated_value (htab_t cache, tree version, tree val) 2082169689Skan{ 2083169689Skan struct scev_info_str *info, pattern; 2084169689Skan PTR *slot; 2085169689Skan 2086169689Skan pattern.var = version; 2087169689Skan slot = htab_find_slot (cache, &pattern, INSERT); 2088169689Skan 2089169689Skan if (!*slot) 2090169689Skan *slot = new_scev_info_str (version); 2091169689Skan info = (struct scev_info_str *) *slot; 2092169689Skan info->chrec = val; 2093169689Skan} 2094169689Skan 2095169689Skan/* Return the closed_loop_phi node for VAR. If there is none, return 2096169689Skan NULL_TREE. */ 2097169689Skan 2098169689Skanstatic tree 2099169689Skanloop_closed_phi_def (tree var) 2100169689Skan{ 2101169689Skan struct loop *loop; 2102169689Skan edge exit; 2103169689Skan tree phi; 2104169689Skan 2105169689Skan if (var == NULL_TREE 2106169689Skan || TREE_CODE (var) != SSA_NAME) 2107169689Skan return NULL_TREE; 2108169689Skan 2109169689Skan loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var)); 2110169689Skan exit = loop->single_exit; 2111169689Skan if (!exit) 2112169689Skan return NULL_TREE; 2113169689Skan 2114169689Skan for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) 2115169689Skan if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var) 2116169689Skan return PHI_RESULT (phi); 2117169689Skan 2118169689Skan return NULL_TREE; 2119169689Skan} 2120169689Skan 2121169689Skan/* Analyze all the parameters of the chrec that were left under a symbolic form, 2122169689Skan with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache 2123169689Skan of already instantiated values. FLAGS modify the way chrecs are 2124169689Skan instantiated. SIZE_EXPR is used for computing the size of the expression to 2125169689Skan be instantiated, and to stop if it exceeds some limit. */ 2126169689Skan 2127169689Skan/* Values for FLAGS. */ 2128169689Skanenum 2129169689Skan{ 2130169689Skan INSERT_SUPERLOOP_CHRECS = 1, /* Loop invariants are replaced with chrecs 2131169689Skan in outer loops. */ 2132169689Skan FOLD_CONVERSIONS = 2 /* The conversions that may wrap in 2133169689Skan signed/pointer type are folded, as long as the 2134169689Skan value of the chrec is preserved. */ 2135169689Skan}; 2136169689Skan 2137169689Skanstatic tree 2138169689Skaninstantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache, 2139169689Skan int size_expr) 2140169689Skan{ 2141169689Skan tree res, op0, op1, op2; 2142169689Skan basic_block def_bb; 2143169689Skan struct loop *def_loop; 2144169689Skan tree type = chrec_type (chrec); 2145169689Skan 2146169689Skan /* Give up if the expression is larger than the MAX that we allow. */ 2147169689Skan if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 2148169689Skan return chrec_dont_know; 2149169689Skan 2150169689Skan if (automatically_generated_chrec_p (chrec) 2151169689Skan || is_gimple_min_invariant (chrec)) 2152169689Skan return chrec; 2153169689Skan 2154169689Skan switch (TREE_CODE (chrec)) 2155169689Skan { 2156169689Skan case SSA_NAME: 2157169689Skan def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec)); 2158169689Skan 2159169689Skan /* A parameter (or loop invariant and we do not want to include 2160169689Skan evolutions in outer loops), nothing to do. */ 2161169689Skan if (!def_bb 2162169689Skan || (!(flags & INSERT_SUPERLOOP_CHRECS) 2163169689Skan && !flow_bb_inside_loop_p (loop, def_bb))) 2164169689Skan return chrec; 2165169689Skan 2166169689Skan /* We cache the value of instantiated variable to avoid exponential 2167169689Skan time complexity due to reevaluations. We also store the convenient 2168169689Skan value in the cache in order to prevent infinite recursion -- we do 2169169689Skan not want to instantiate the SSA_NAME if it is in a mixer 2170169689Skan structure. This is used for avoiding the instantiation of 2171169689Skan recursively defined functions, such as: 2172169689Skan 2173169689Skan | a_2 -> {0, +, 1, +, a_2}_1 */ 2174169689Skan 2175169689Skan res = get_instantiated_value (cache, chrec); 2176169689Skan if (res) 2177169689Skan return res; 2178169689Skan 2179169689Skan /* Store the convenient value for chrec in the structure. If it 2180169689Skan is defined outside of the loop, we may just leave it in symbolic 2181169689Skan form, otherwise we need to admit that we do not know its behavior 2182169689Skan inside the loop. */ 2183169689Skan res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know; 2184169689Skan set_instantiated_value (cache, chrec, res); 2185169689Skan 2186169689Skan /* To make things even more complicated, instantiate_parameters_1 2187169689Skan calls analyze_scalar_evolution that may call # of iterations 2188169689Skan analysis that may in turn call instantiate_parameters_1 again. 2189169689Skan To prevent the infinite recursion, keep also the bitmap of 2190169689Skan ssa names that are being instantiated globally. */ 2191169689Skan if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec))) 2192169689Skan return res; 2193169689Skan 2194169689Skan def_loop = find_common_loop (loop, def_bb->loop_father); 2195169689Skan 2196169689Skan /* If the analysis yields a parametric chrec, instantiate the 2197169689Skan result again. */ 2198169689Skan bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); 2199169689Skan res = analyze_scalar_evolution (def_loop, chrec); 2200169689Skan 2201169689Skan /* Don't instantiate loop-closed-ssa phi nodes. */ 2202169689Skan if (TREE_CODE (res) == SSA_NAME 2203169689Skan && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL 2204169689Skan || (loop_containing_stmt (SSA_NAME_DEF_STMT (res))->depth 2205169689Skan > def_loop->depth))) 2206169689Skan { 2207169689Skan if (res == chrec) 2208169689Skan res = loop_closed_phi_def (chrec); 2209169689Skan else 2210169689Skan res = chrec; 2211169689Skan 2212169689Skan if (res == NULL_TREE) 2213169689Skan res = chrec_dont_know; 2214169689Skan } 2215169689Skan 2216169689Skan else if (res != chrec_dont_know) 2217169689Skan res = instantiate_parameters_1 (loop, res, flags, cache, size_expr); 2218169689Skan 2219169689Skan bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); 2220169689Skan 2221169689Skan /* Store the correct value to the cache. */ 2222169689Skan set_instantiated_value (cache, chrec, res); 2223169689Skan return res; 2224169689Skan 2225169689Skan case POLYNOMIAL_CHREC: 2226169689Skan op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), 2227169689Skan flags, cache, size_expr); 2228169689Skan if (op0 == chrec_dont_know) 2229169689Skan return chrec_dont_know; 2230169689Skan 2231169689Skan op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), 2232169689Skan flags, cache, size_expr); 2233169689Skan if (op1 == chrec_dont_know) 2234169689Skan return chrec_dont_know; 2235169689Skan 2236169689Skan if (CHREC_LEFT (chrec) != op0 2237169689Skan || CHREC_RIGHT (chrec) != op1) 2238169689Skan { 2239169689Skan op1 = chrec_convert (chrec_type (op0), op1, NULL_TREE); 2240169689Skan chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); 2241169689Skan } 2242169689Skan return chrec; 2243169689Skan 2244169689Skan case PLUS_EXPR: 2245169689Skan op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2246169689Skan flags, cache, size_expr); 2247169689Skan if (op0 == chrec_dont_know) 2248169689Skan return chrec_dont_know; 2249169689Skan 2250169689Skan op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2251169689Skan flags, cache, size_expr); 2252169689Skan if (op1 == chrec_dont_know) 2253169689Skan return chrec_dont_know; 2254169689Skan 2255169689Skan if (TREE_OPERAND (chrec, 0) != op0 2256169689Skan || TREE_OPERAND (chrec, 1) != op1) 2257169689Skan { 2258169689Skan op0 = chrec_convert (type, op0, NULL_TREE); 2259169689Skan op1 = chrec_convert (type, op1, NULL_TREE); 2260169689Skan chrec = chrec_fold_plus (type, op0, op1); 2261169689Skan } 2262169689Skan return chrec; 2263169689Skan 2264169689Skan case MINUS_EXPR: 2265169689Skan op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2266169689Skan flags, cache, size_expr); 2267169689Skan if (op0 == chrec_dont_know) 2268169689Skan return chrec_dont_know; 2269169689Skan 2270169689Skan op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2271169689Skan flags, cache, size_expr); 2272169689Skan if (op1 == chrec_dont_know) 2273169689Skan return chrec_dont_know; 2274169689Skan 2275169689Skan if (TREE_OPERAND (chrec, 0) != op0 2276169689Skan || TREE_OPERAND (chrec, 1) != op1) 2277169689Skan { 2278169689Skan op0 = chrec_convert (type, op0, NULL_TREE); 2279169689Skan op1 = chrec_convert (type, op1, NULL_TREE); 2280169689Skan chrec = chrec_fold_minus (type, op0, op1); 2281169689Skan } 2282169689Skan return chrec; 2283169689Skan 2284169689Skan case MULT_EXPR: 2285169689Skan op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2286169689Skan flags, cache, size_expr); 2287169689Skan if (op0 == chrec_dont_know) 2288169689Skan return chrec_dont_know; 2289169689Skan 2290169689Skan op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2291169689Skan flags, cache, size_expr); 2292169689Skan if (op1 == chrec_dont_know) 2293169689Skan return chrec_dont_know; 2294169689Skan 2295169689Skan if (TREE_OPERAND (chrec, 0) != op0 2296169689Skan || TREE_OPERAND (chrec, 1) != op1) 2297169689Skan { 2298169689Skan op0 = chrec_convert (type, op0, NULL_TREE); 2299169689Skan op1 = chrec_convert (type, op1, NULL_TREE); 2300169689Skan chrec = chrec_fold_multiply (type, op0, op1); 2301169689Skan } 2302169689Skan return chrec; 2303169689Skan 2304169689Skan case NOP_EXPR: 2305169689Skan case CONVERT_EXPR: 2306169689Skan case NON_LVALUE_EXPR: 2307169689Skan op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2308169689Skan flags, cache, size_expr); 2309169689Skan if (op0 == chrec_dont_know) 2310169689Skan return chrec_dont_know; 2311169689Skan 2312169689Skan if (flags & FOLD_CONVERSIONS) 2313169689Skan { 2314169689Skan tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0); 2315169689Skan if (tmp) 2316169689Skan return tmp; 2317169689Skan } 2318169689Skan 2319169689Skan if (op0 == TREE_OPERAND (chrec, 0)) 2320169689Skan return chrec; 2321169689Skan 2322169689Skan /* If we used chrec_convert_aggressive, we can no longer assume that 2323169689Skan signed chrecs do not overflow, as chrec_convert does, so avoid 2324169689Skan calling it in that case. */ 2325169689Skan if (flags & FOLD_CONVERSIONS) 2326169689Skan return fold_convert (TREE_TYPE (chrec), op0); 2327169689Skan 2328169689Skan return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE); 2329169689Skan 2330169689Skan case SCEV_NOT_KNOWN: 2331169689Skan return chrec_dont_know; 2332169689Skan 2333169689Skan case SCEV_KNOWN: 2334169689Skan return chrec_known; 2335169689Skan 2336169689Skan default: 2337169689Skan break; 2338169689Skan } 2339169689Skan 2340169689Skan switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 2341169689Skan { 2342169689Skan case 3: 2343169689Skan op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2344169689Skan flags, cache, size_expr); 2345169689Skan if (op0 == chrec_dont_know) 2346169689Skan return chrec_dont_know; 2347169689Skan 2348169689Skan op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2349169689Skan flags, cache, size_expr); 2350169689Skan if (op1 == chrec_dont_know) 2351169689Skan return chrec_dont_know; 2352169689Skan 2353169689Skan op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2), 2354169689Skan flags, cache, size_expr); 2355169689Skan if (op2 == chrec_dont_know) 2356169689Skan return chrec_dont_know; 2357169689Skan 2358169689Skan if (op0 == TREE_OPERAND (chrec, 0) 2359169689Skan && op1 == TREE_OPERAND (chrec, 1) 2360169689Skan && op2 == TREE_OPERAND (chrec, 2)) 2361169689Skan return chrec; 2362169689Skan 2363169689Skan return fold_build3 (TREE_CODE (chrec), 2364169689Skan TREE_TYPE (chrec), op0, op1, op2); 2365169689Skan 2366169689Skan case 2: 2367169689Skan op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2368169689Skan flags, cache, size_expr); 2369169689Skan if (op0 == chrec_dont_know) 2370169689Skan return chrec_dont_know; 2371169689Skan 2372169689Skan op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), 2373169689Skan flags, cache, size_expr); 2374169689Skan if (op1 == chrec_dont_know) 2375169689Skan return chrec_dont_know; 2376169689Skan 2377169689Skan if (op0 == TREE_OPERAND (chrec, 0) 2378169689Skan && op1 == TREE_OPERAND (chrec, 1)) 2379169689Skan return chrec; 2380169689Skan return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); 2381169689Skan 2382169689Skan case 1: 2383169689Skan op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), 2384169689Skan flags, cache, size_expr); 2385169689Skan if (op0 == chrec_dont_know) 2386169689Skan return chrec_dont_know; 2387169689Skan if (op0 == TREE_OPERAND (chrec, 0)) 2388169689Skan return chrec; 2389169689Skan return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0); 2390169689Skan 2391169689Skan case 0: 2392169689Skan return chrec; 2393169689Skan 2394169689Skan default: 2395169689Skan break; 2396169689Skan } 2397169689Skan 2398169689Skan /* Too complicated to handle. */ 2399169689Skan return chrec_dont_know; 2400169689Skan} 2401169689Skan 2402169689Skan/* Analyze all the parameters of the chrec that were left under a 2403169689Skan symbolic form. LOOP is the loop in which symbolic names have to 2404169689Skan be analyzed and instantiated. */ 2405169689Skan 2406169689Skantree 2407169689Skaninstantiate_parameters (struct loop *loop, 2408169689Skan tree chrec) 2409169689Skan{ 2410169689Skan tree res; 2411169689Skan htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); 2412169689Skan 2413169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2414169689Skan { 2415169689Skan fprintf (dump_file, "(instantiate_parameters \n"); 2416169689Skan fprintf (dump_file, " (loop_nb = %d)\n", loop->num); 2417169689Skan fprintf (dump_file, " (chrec = "); 2418169689Skan print_generic_expr (dump_file, chrec, 0); 2419169689Skan fprintf (dump_file, ")\n"); 2420169689Skan } 2421169689Skan 2422169689Skan res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache, 2423169689Skan 0); 2424169689Skan 2425169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2426169689Skan { 2427169689Skan fprintf (dump_file, " (res = "); 2428169689Skan print_generic_expr (dump_file, res, 0); 2429169689Skan fprintf (dump_file, "))\n"); 2430169689Skan } 2431169689Skan 2432169689Skan htab_delete (cache); 2433169689Skan 2434169689Skan return res; 2435169689Skan} 2436169689Skan 2437169689Skan/* Similar to instantiate_parameters, but does not introduce the 2438169689Skan evolutions in outer loops for LOOP invariants in CHREC, and does not 2439169689Skan care about causing overflows, as long as they do not affect value 2440169689Skan of an expression. */ 2441169689Skan 2442169689Skanstatic tree 2443169689Skanresolve_mixers (struct loop *loop, tree chrec) 2444169689Skan{ 2445169689Skan htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); 2446169689Skan tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0); 2447169689Skan htab_delete (cache); 2448169689Skan return ret; 2449169689Skan} 2450169689Skan 2451169689Skan/* Entry point for the analysis of the number of iterations pass. 2452169689Skan This function tries to safely approximate the number of iterations 2453169689Skan the loop will run. When this property is not decidable at compile 2454169689Skan time, the result is chrec_dont_know. Otherwise the result is 2455169689Skan a scalar or a symbolic parameter. 2456169689Skan 2457169689Skan Example of analysis: suppose that the loop has an exit condition: 2458169689Skan 2459169689Skan "if (b > 49) goto end_loop;" 2460169689Skan 2461169689Skan and that in a previous analysis we have determined that the 2462169689Skan variable 'b' has an evolution function: 2463169689Skan 2464169689Skan "EF = {23, +, 5}_2". 2465169689Skan 2466169689Skan When we evaluate the function at the point 5, i.e. the value of the 2467169689Skan variable 'b' after 5 iterations in the loop, we have EF (5) = 48, 2468169689Skan and EF (6) = 53. In this case the value of 'b' on exit is '53' and 2469169689Skan the loop body has been executed 6 times. */ 2470169689Skan 2471169689Skantree 2472169689Skannumber_of_iterations_in_loop (struct loop *loop) 2473169689Skan{ 2474169689Skan tree res, type; 2475169689Skan edge exit; 2476169689Skan struct tree_niter_desc niter_desc; 2477169689Skan 2478169689Skan /* Determine whether the number_of_iterations_in_loop has already 2479169689Skan been computed. */ 2480169689Skan res = loop->nb_iterations; 2481169689Skan if (res) 2482169689Skan return res; 2483169689Skan res = chrec_dont_know; 2484169689Skan 2485169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2486169689Skan fprintf (dump_file, "(number_of_iterations_in_loop\n"); 2487169689Skan 2488169689Skan exit = loop->single_exit; 2489169689Skan if (!exit) 2490169689Skan goto end; 2491169689Skan 2492169689Skan if (!number_of_iterations_exit (loop, exit, &niter_desc, false)) 2493169689Skan goto end; 2494169689Skan 2495169689Skan type = TREE_TYPE (niter_desc.niter); 2496169689Skan if (integer_nonzerop (niter_desc.may_be_zero)) 2497169689Skan res = build_int_cst (type, 0); 2498169689Skan else if (integer_zerop (niter_desc.may_be_zero)) 2499169689Skan res = niter_desc.niter; 2500169689Skan else 2501169689Skan res = chrec_dont_know; 2502169689Skan 2503169689Skanend: 2504169689Skan return set_nb_iterations_in_loop (loop, res); 2505169689Skan} 2506169689Skan 2507169689Skan/* One of the drivers for testing the scalar evolutions analysis. 2508169689Skan This function computes the number of iterations for all the loops 2509169689Skan from the EXIT_CONDITIONS array. */ 2510169689Skan 2511169689Skanstatic void 2512169689Skannumber_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions) 2513169689Skan{ 2514169689Skan unsigned int i; 2515169689Skan unsigned nb_chrec_dont_know_loops = 0; 2516169689Skan unsigned nb_static_loops = 0; 2517169689Skan tree cond; 2518169689Skan 2519169689Skan for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) 2520169689Skan { 2521169689Skan tree res = number_of_iterations_in_loop (loop_containing_stmt (cond)); 2522169689Skan if (chrec_contains_undetermined (res)) 2523169689Skan nb_chrec_dont_know_loops++; 2524169689Skan else 2525169689Skan nb_static_loops++; 2526169689Skan } 2527169689Skan 2528169689Skan if (dump_file) 2529169689Skan { 2530169689Skan fprintf (dump_file, "\n(\n"); 2531169689Skan fprintf (dump_file, "-----------------------------------------\n"); 2532169689Skan fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops); 2533169689Skan fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops); 2534169689Skan fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num); 2535169689Skan fprintf (dump_file, "-----------------------------------------\n"); 2536169689Skan fprintf (dump_file, ")\n\n"); 2537169689Skan 2538169689Skan print_loop_ir (dump_file); 2539169689Skan } 2540169689Skan} 2541169689Skan 2542169689Skan 2543169689Skan 2544169689Skan/* Counters for the stats. */ 2545169689Skan 2546169689Skanstruct chrec_stats 2547169689Skan{ 2548169689Skan unsigned nb_chrecs; 2549169689Skan unsigned nb_affine; 2550169689Skan unsigned nb_affine_multivar; 2551169689Skan unsigned nb_higher_poly; 2552169689Skan unsigned nb_chrec_dont_know; 2553169689Skan unsigned nb_undetermined; 2554169689Skan}; 2555169689Skan 2556169689Skan/* Reset the counters. */ 2557169689Skan 2558169689Skanstatic inline void 2559169689Skanreset_chrecs_counters (struct chrec_stats *stats) 2560169689Skan{ 2561169689Skan stats->nb_chrecs = 0; 2562169689Skan stats->nb_affine = 0; 2563169689Skan stats->nb_affine_multivar = 0; 2564169689Skan stats->nb_higher_poly = 0; 2565169689Skan stats->nb_chrec_dont_know = 0; 2566169689Skan stats->nb_undetermined = 0; 2567169689Skan} 2568169689Skan 2569169689Skan/* Dump the contents of a CHREC_STATS structure. */ 2570169689Skan 2571169689Skanstatic void 2572169689Skandump_chrecs_stats (FILE *file, struct chrec_stats *stats) 2573169689Skan{ 2574169689Skan fprintf (file, "\n(\n"); 2575169689Skan fprintf (file, "-----------------------------------------\n"); 2576169689Skan fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine); 2577169689Skan fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar); 2578169689Skan fprintf (file, "%d\tdegree greater than 2 polynomials\n", 2579169689Skan stats->nb_higher_poly); 2580169689Skan fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know); 2581169689Skan fprintf (file, "-----------------------------------------\n"); 2582169689Skan fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs); 2583169689Skan fprintf (file, "%d\twith undetermined coefficients\n", 2584169689Skan stats->nb_undetermined); 2585169689Skan fprintf (file, "-----------------------------------------\n"); 2586169689Skan fprintf (file, "%d\tchrecs in the scev database\n", 2587169689Skan (int) htab_elements (scalar_evolution_info)); 2588169689Skan fprintf (file, "%d\tsets in the scev database\n", nb_set_scev); 2589169689Skan fprintf (file, "%d\tgets in the scev database\n", nb_get_scev); 2590169689Skan fprintf (file, "-----------------------------------------\n"); 2591169689Skan fprintf (file, ")\n\n"); 2592169689Skan} 2593169689Skan 2594169689Skan/* Gather statistics about CHREC. */ 2595169689Skan 2596169689Skanstatic void 2597169689Skangather_chrec_stats (tree chrec, struct chrec_stats *stats) 2598169689Skan{ 2599169689Skan if (dump_file && (dump_flags & TDF_STATS)) 2600169689Skan { 2601169689Skan fprintf (dump_file, "(classify_chrec "); 2602169689Skan print_generic_expr (dump_file, chrec, 0); 2603169689Skan fprintf (dump_file, "\n"); 2604169689Skan } 2605169689Skan 2606169689Skan stats->nb_chrecs++; 2607169689Skan 2608169689Skan if (chrec == NULL_TREE) 2609169689Skan { 2610169689Skan stats->nb_undetermined++; 2611169689Skan return; 2612169689Skan } 2613169689Skan 2614169689Skan switch (TREE_CODE (chrec)) 2615169689Skan { 2616169689Skan case POLYNOMIAL_CHREC: 2617169689Skan if (evolution_function_is_affine_p (chrec)) 2618169689Skan { 2619169689Skan if (dump_file && (dump_flags & TDF_STATS)) 2620169689Skan fprintf (dump_file, " affine_univariate\n"); 2621169689Skan stats->nb_affine++; 2622169689Skan } 2623169689Skan else if (evolution_function_is_affine_multivariate_p (chrec)) 2624169689Skan { 2625169689Skan if (dump_file && (dump_flags & TDF_STATS)) 2626169689Skan fprintf (dump_file, " affine_multivariate\n"); 2627169689Skan stats->nb_affine_multivar++; 2628169689Skan } 2629169689Skan else 2630169689Skan { 2631169689Skan if (dump_file && (dump_flags & TDF_STATS)) 2632169689Skan fprintf (dump_file, " higher_degree_polynomial\n"); 2633169689Skan stats->nb_higher_poly++; 2634169689Skan } 2635169689Skan 2636169689Skan break; 2637169689Skan 2638169689Skan default: 2639169689Skan break; 2640169689Skan } 2641169689Skan 2642169689Skan if (chrec_contains_undetermined (chrec)) 2643169689Skan { 2644169689Skan if (dump_file && (dump_flags & TDF_STATS)) 2645169689Skan fprintf (dump_file, " undetermined\n"); 2646169689Skan stats->nb_undetermined++; 2647169689Skan } 2648169689Skan 2649169689Skan if (dump_file && (dump_flags & TDF_STATS)) 2650169689Skan fprintf (dump_file, ")\n"); 2651169689Skan} 2652169689Skan 2653169689Skan/* One of the drivers for testing the scalar evolutions analysis. 2654169689Skan This function analyzes the scalar evolution of all the scalars 2655169689Skan defined as loop phi nodes in one of the loops from the 2656169689Skan EXIT_CONDITIONS array. 2657169689Skan 2658169689Skan TODO Optimization: A loop is in canonical form if it contains only 2659169689Skan a single scalar loop phi node. All the other scalars that have an 2660169689Skan evolution in the loop are rewritten in function of this single 2661169689Skan index. This allows the parallelization of the loop. */ 2662169689Skan 2663169689Skanstatic void 2664169689Skananalyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions) 2665169689Skan{ 2666169689Skan unsigned int i; 2667169689Skan struct chrec_stats stats; 2668169689Skan tree cond; 2669169689Skan 2670169689Skan reset_chrecs_counters (&stats); 2671169689Skan 2672169689Skan for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) 2673169689Skan { 2674169689Skan struct loop *loop; 2675169689Skan basic_block bb; 2676169689Skan tree phi, chrec; 2677169689Skan 2678169689Skan loop = loop_containing_stmt (cond); 2679169689Skan bb = loop->header; 2680169689Skan 2681169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2682169689Skan if (is_gimple_reg (PHI_RESULT (phi))) 2683169689Skan { 2684169689Skan chrec = instantiate_parameters 2685169689Skan (loop, 2686169689Skan analyze_scalar_evolution (loop, PHI_RESULT (phi))); 2687169689Skan 2688169689Skan if (dump_file && (dump_flags & TDF_STATS)) 2689169689Skan gather_chrec_stats (chrec, &stats); 2690169689Skan } 2691169689Skan } 2692169689Skan 2693169689Skan if (dump_file && (dump_flags & TDF_STATS)) 2694169689Skan dump_chrecs_stats (dump_file, &stats); 2695169689Skan} 2696169689Skan 2697169689Skan/* Callback for htab_traverse, gathers information on chrecs in the 2698169689Skan hashtable. */ 2699169689Skan 2700169689Skanstatic int 2701169689Skangather_stats_on_scev_database_1 (void **slot, void *stats) 2702169689Skan{ 2703169689Skan struct scev_info_str *entry = (struct scev_info_str *) *slot; 2704169689Skan 2705169689Skan gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats); 2706169689Skan 2707169689Skan return 1; 2708169689Skan} 2709169689Skan 2710169689Skan/* Classify the chrecs of the whole database. */ 2711169689Skan 2712169689Skanvoid 2713169689Skangather_stats_on_scev_database (void) 2714169689Skan{ 2715169689Skan struct chrec_stats stats; 2716169689Skan 2717169689Skan if (!dump_file) 2718169689Skan return; 2719169689Skan 2720169689Skan reset_chrecs_counters (&stats); 2721169689Skan 2722169689Skan htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1, 2723169689Skan &stats); 2724169689Skan 2725169689Skan dump_chrecs_stats (dump_file, &stats); 2726169689Skan} 2727169689Skan 2728169689Skan 2729169689Skan 2730169689Skan/* Initializer. */ 2731169689Skan 2732169689Skanstatic void 2733169689Skaninitialize_scalar_evolutions_analyzer (void) 2734169689Skan{ 2735169689Skan /* The elements below are unique. */ 2736169689Skan if (chrec_dont_know == NULL_TREE) 2737169689Skan { 2738169689Skan chrec_not_analyzed_yet = NULL_TREE; 2739169689Skan chrec_dont_know = make_node (SCEV_NOT_KNOWN); 2740169689Skan chrec_known = make_node (SCEV_KNOWN); 2741169689Skan TREE_TYPE (chrec_dont_know) = void_type_node; 2742169689Skan TREE_TYPE (chrec_known) = void_type_node; 2743169689Skan } 2744169689Skan} 2745169689Skan 2746169689Skan/* Initialize the analysis of scalar evolutions for LOOPS. */ 2747169689Skan 2748169689Skanvoid 2749169689Skanscev_initialize (struct loops *loops) 2750169689Skan{ 2751169689Skan unsigned i; 2752169689Skan current_loops = loops; 2753169689Skan 2754169689Skan scalar_evolution_info = htab_create (100, hash_scev_info, 2755169689Skan eq_scev_info, del_scev_info); 2756169689Skan already_instantiated = BITMAP_ALLOC (NULL); 2757169689Skan 2758169689Skan initialize_scalar_evolutions_analyzer (); 2759169689Skan 2760169689Skan for (i = 1; i < loops->num; i++) 2761169689Skan if (loops->parray[i]) 2762169689Skan loops->parray[i]->nb_iterations = NULL_TREE; 2763169689Skan} 2764169689Skan 2765169689Skan/* Cleans up the information cached by the scalar evolutions analysis. */ 2766169689Skan 2767169689Skanvoid 2768169689Skanscev_reset (void) 2769169689Skan{ 2770169689Skan unsigned i; 2771169689Skan struct loop *loop; 2772169689Skan 2773169689Skan if (!scalar_evolution_info || !current_loops) 2774169689Skan return; 2775169689Skan 2776169689Skan htab_empty (scalar_evolution_info); 2777169689Skan for (i = 1; i < current_loops->num; i++) 2778169689Skan { 2779169689Skan loop = current_loops->parray[i]; 2780169689Skan if (loop) 2781169689Skan loop->nb_iterations = NULL_TREE; 2782169689Skan } 2783169689Skan} 2784169689Skan 2785169689Skan/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns 2786169689Skan its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we 2787169689Skan want step to be invariant in LOOP. Otherwise we require it to be an 2788169689Skan integer constant. IV->no_overflow is set to true if we are sure the iv cannot 2789169689Skan overflow (e.g. because it is computed in signed arithmetics). */ 2790169689Skan 2791169689Skanbool 2792169689Skansimple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv, 2793169689Skan bool allow_nonconstant_step) 2794169689Skan{ 2795169689Skan basic_block bb = bb_for_stmt (stmt); 2796169689Skan tree type, ev; 2797169689Skan bool folded_casts; 2798169689Skan 2799169689Skan iv->base = NULL_TREE; 2800169689Skan iv->step = NULL_TREE; 2801169689Skan iv->no_overflow = false; 2802169689Skan 2803169689Skan type = TREE_TYPE (op); 2804169689Skan if (TREE_CODE (type) != INTEGER_TYPE 2805169689Skan && TREE_CODE (type) != POINTER_TYPE) 2806169689Skan return false; 2807169689Skan 2808169689Skan ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op, 2809169689Skan &folded_casts); 2810169689Skan if (chrec_contains_undetermined (ev)) 2811169689Skan return false; 2812169689Skan 2813169689Skan if (tree_does_not_contain_chrecs (ev) 2814169689Skan && !chrec_contains_symbols_defined_in_loop (ev, loop->num)) 2815169689Skan { 2816169689Skan iv->base = ev; 2817169689Skan iv->no_overflow = true; 2818169689Skan return true; 2819169689Skan } 2820169689Skan 2821169689Skan if (TREE_CODE (ev) != POLYNOMIAL_CHREC 2822169689Skan || CHREC_VARIABLE (ev) != (unsigned) loop->num) 2823169689Skan return false; 2824169689Skan 2825169689Skan iv->step = CHREC_RIGHT (ev); 2826169689Skan if (allow_nonconstant_step) 2827169689Skan { 2828169689Skan if (tree_contains_chrecs (iv->step, NULL) 2829169689Skan || chrec_contains_symbols_defined_in_loop (iv->step, loop->num)) 2830169689Skan return false; 2831169689Skan } 2832169689Skan else if (TREE_CODE (iv->step) != INTEGER_CST) 2833169689Skan return false; 2834169689Skan 2835169689Skan iv->base = CHREC_LEFT (ev); 2836169689Skan if (tree_contains_chrecs (iv->base, NULL) 2837169689Skan || chrec_contains_symbols_defined_in_loop (iv->base, loop->num)) 2838169689Skan return false; 2839169689Skan 2840169689Skan iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type); 2841169689Skan 2842169689Skan return true; 2843169689Skan} 2844169689Skan 2845169689Skan/* Runs the analysis of scalar evolutions. */ 2846169689Skan 2847169689Skanvoid 2848169689Skanscev_analysis (void) 2849169689Skan{ 2850169689Skan VEC(tree,heap) *exit_conditions; 2851169689Skan 2852169689Skan exit_conditions = VEC_alloc (tree, heap, 37); 2853169689Skan select_loops_exit_conditions (current_loops, &exit_conditions); 2854169689Skan 2855169689Skan if (dump_file && (dump_flags & TDF_STATS)) 2856169689Skan analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions); 2857169689Skan 2858169689Skan number_of_iterations_for_all_loops (&exit_conditions); 2859169689Skan VEC_free (tree, heap, exit_conditions); 2860169689Skan} 2861169689Skan 2862169689Skan/* Finalize the scalar evolution analysis. */ 2863169689Skan 2864169689Skanvoid 2865169689Skanscev_finalize (void) 2866169689Skan{ 2867169689Skan htab_delete (scalar_evolution_info); 2868169689Skan BITMAP_FREE (already_instantiated); 2869169689Skan} 2870169689Skan 2871169689Skan/* Returns true if EXPR looks expensive. */ 2872169689Skan 2873169689Skanstatic bool 2874169689Skanexpression_expensive_p (tree expr) 2875169689Skan{ 2876169689Skan return force_expr_to_var_cost (expr) >= target_spill_cost; 2877169689Skan} 2878169689Skan 2879169689Skan/* Replace ssa names for that scev can prove they are constant by the 2880169689Skan appropriate constants. Also perform final value replacement in loops, 2881169689Skan in case the replacement expressions are cheap. 2882169689Skan 2883169689Skan We only consider SSA names defined by phi nodes; rest is left to the 2884169689Skan ordinary constant propagation pass. */ 2885169689Skan 2886169689Skanunsigned int 2887169689Skanscev_const_prop (void) 2888169689Skan{ 2889169689Skan basic_block bb; 2890169689Skan tree name, phi, next_phi, type, ev; 2891169689Skan struct loop *loop, *ex_loop; 2892169689Skan bitmap ssa_names_to_remove = NULL; 2893169689Skan unsigned i; 2894169689Skan 2895169689Skan if (!current_loops) 2896169689Skan return 0; 2897169689Skan 2898169689Skan FOR_EACH_BB (bb) 2899169689Skan { 2900169689Skan loop = bb->loop_father; 2901169689Skan 2902169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2903169689Skan { 2904169689Skan name = PHI_RESULT (phi); 2905169689Skan 2906169689Skan if (!is_gimple_reg (name)) 2907169689Skan continue; 2908169689Skan 2909169689Skan type = TREE_TYPE (name); 2910169689Skan 2911169689Skan if (!POINTER_TYPE_P (type) 2912169689Skan && !INTEGRAL_TYPE_P (type)) 2913169689Skan continue; 2914169689Skan 2915169689Skan ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name)); 2916169689Skan if (!is_gimple_min_invariant (ev) 2917169689Skan || !may_propagate_copy (name, ev)) 2918169689Skan continue; 2919169689Skan 2920169689Skan /* Replace the uses of the name. */ 2921169689Skan if (name != ev) 2922169689Skan replace_uses_by (name, ev); 2923169689Skan 2924169689Skan if (!ssa_names_to_remove) 2925169689Skan ssa_names_to_remove = BITMAP_ALLOC (NULL); 2926169689Skan bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name)); 2927169689Skan } 2928169689Skan } 2929169689Skan 2930169689Skan /* Remove the ssa names that were replaced by constants. We do not remove them 2931169689Skan directly in the previous cycle, since this invalidates scev cache. */ 2932169689Skan if (ssa_names_to_remove) 2933169689Skan { 2934169689Skan bitmap_iterator bi; 2935169689Skan unsigned i; 2936169689Skan 2937169689Skan EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi) 2938169689Skan { 2939169689Skan name = ssa_name (i); 2940169689Skan phi = SSA_NAME_DEF_STMT (name); 2941169689Skan 2942169689Skan gcc_assert (TREE_CODE (phi) == PHI_NODE); 2943169689Skan remove_phi_node (phi, NULL); 2944169689Skan } 2945169689Skan 2946169689Skan BITMAP_FREE (ssa_names_to_remove); 2947169689Skan scev_reset (); 2948169689Skan } 2949169689Skan 2950169689Skan /* Now the regular final value replacement. */ 2951169689Skan for (i = current_loops->num - 1; i > 0; i--) 2952169689Skan { 2953169689Skan edge exit; 2954169689Skan tree def, rslt, ass, niter; 2955169689Skan block_stmt_iterator bsi; 2956169689Skan 2957169689Skan loop = current_loops->parray[i]; 2958169689Skan if (!loop) 2959169689Skan continue; 2960169689Skan 2961169689Skan /* If we do not know exact number of iterations of the loop, we cannot 2962169689Skan replace the final value. */ 2963169689Skan exit = loop->single_exit; 2964169689Skan if (!exit) 2965169689Skan continue; 2966169689Skan 2967169689Skan niter = number_of_iterations_in_loop (loop); 2968169689Skan if (niter == chrec_dont_know 2969169689Skan /* If computing the number of iterations is expensive, it may be 2970169689Skan better not to introduce computations involving it. */ 2971169689Skan || expression_expensive_p (niter)) 2972169689Skan continue; 2973169689Skan 2974169689Skan /* Ensure that it is possible to insert new statements somewhere. */ 2975169689Skan if (!single_pred_p (exit->dest)) 2976169689Skan split_loop_exit_edge (exit); 2977169689Skan tree_block_label (exit->dest); 2978169689Skan bsi = bsi_after_labels (exit->dest); 2979169689Skan 2980169689Skan ex_loop = superloop_at_depth (loop, exit->dest->loop_father->depth + 1); 2981169689Skan 2982169689Skan for (phi = phi_nodes (exit->dest); phi; phi = next_phi) 2983169689Skan { 2984169689Skan next_phi = PHI_CHAIN (phi); 2985169689Skan rslt = PHI_RESULT (phi); 2986169689Skan def = PHI_ARG_DEF_FROM_EDGE (phi, exit); 2987169689Skan if (!is_gimple_reg (def)) 2988169689Skan continue; 2989169689Skan 2990169689Skan if (!POINTER_TYPE_P (TREE_TYPE (def)) 2991169689Skan && !INTEGRAL_TYPE_P (TREE_TYPE (def))) 2992169689Skan continue; 2993169689Skan 2994169689Skan def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL); 2995169689Skan def = compute_overall_effect_of_inner_loop (ex_loop, def); 2996169689Skan if (!tree_does_not_contain_chrecs (def) 2997169689Skan || chrec_contains_symbols_defined_in_loop (def, ex_loop->num) 2998169689Skan /* Moving the computation from the loop may prolong life range 2999169689Skan of some ssa names, which may cause problems if they appear 3000169689Skan on abnormal edges. */ 3001169689Skan || contains_abnormal_ssa_name_p (def)) 3002169689Skan continue; 3003169689Skan 3004169689Skan /* Eliminate the phi node and replace it by a computation outside 3005169689Skan the loop. */ 3006169689Skan def = unshare_expr (def); 3007169689Skan SET_PHI_RESULT (phi, NULL_TREE); 3008169689Skan remove_phi_node (phi, NULL_TREE); 3009169689Skan 3010169689Skan ass = build2 (MODIFY_EXPR, void_type_node, rslt, NULL_TREE); 3011169689Skan SSA_NAME_DEF_STMT (rslt) = ass; 3012169689Skan { 3013169689Skan block_stmt_iterator dest = bsi; 3014169689Skan bsi_insert_before (&dest, ass, BSI_NEW_STMT); 3015169689Skan def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE); 3016169689Skan } 3017169689Skan TREE_OPERAND (ass, 1) = def; 3018169689Skan update_stmt (ass); 3019169689Skan } 3020169689Skan } 3021169689Skan return 0; 3022169689Skan} 3023