diff options
Diffstat (limited to 'gcc/tree-scalar-evolution.c')
| -rw-r--r-- | gcc/tree-scalar-evolution.c | 3768 |
1 files changed, 3768 insertions, 0 deletions
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c new file mode 100644 index 00000000000..1daeb42aa16 --- /dev/null +++ b/gcc/tree-scalar-evolution.c @@ -0,0 +1,3768 @@ +/* Scalar evolution detector. + Copyright (C) 2003, 2004 Free Software Foundation, Inc. + Contributed by Sebastian Pop <s.pop@laposte.net> + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +/* + Description: + + This pass analyzes the evolution of scalar variables in loop + structures. The algorithm is based on the SSA representation, + and on the loop hierarchy tree. This algorithm is not based on + the notion of versions of a variable, as it was the case for the + previous implementations of the scalar evolution algorithm, but + it assumes that each defined name is unique. + + A short sketch of the algorithm is: + + Given a scalar variable to be analyzed, follow the SSA edge to + its definition: + + - When the definition is a MODIFY_EXPR: if the right hand side + (RHS) of the definition cannot be statically analyzed, the answer + of the analyzer is: "don't know", that corresponds to the + conservative [-oo, +oo] element of the lattice of intervals. + Otherwise, for all the variables that are not yet analyzed in the + RHS, try to determine their evolution, and finally try to + evaluate the operation of the RHS that gives the evolution + function of the analyzed variable. + + - When the definition is a condition-phi-node: determine the + evolution function for all the branches of the phi node, and + finally merge these evolutions (see chrec_merge). + + - When the definition is a loop-phi-node: determine its initial + condition, that is the SSA edge defined in an outer loop, and + keep it symbolic. Then determine the SSA edges that are defined + in the body of the loop. Follow the inner edges until ending on + another loop-phi-node of the same analyzed loop. If the reached + loop-phi-node is not the starting loop-phi-node, then we keep + this definition under a symbolic form. If the reached + loop-phi-node is the same as the starting one, then we compute a + symbolic stride on the return path. The result is then the + symbolic chrec {initial_condition, +, symbolic_stride}_loop. + + Examples: + + Example 1: Illustration of the basic algorithm. + + | a = 3 + | loop_1 + | b = phi (a, c) + | c = b + 1 + | if (c > 10) exit_loop + | endloop + + Suppose that we want to know the number of iterations of the + loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We + ask the scalar evolution analyzer two questions: what's the + scalar evolution (scev) of "c", and what's the scev of "10". For + "10" the answer is "10" since it is a scalar constant. For the + scalar variable "c", it follows the SSA edge to its definition, + "c = b + 1", and then asks again what's the scev of "b". + Following the SSA edge, we end on a loop-phi-node "b = phi (a, + c)", where the initial condition is "a", and the inner loop edge + is "c". The initial condition is kept under a symbolic form (it + may be the case that the copy constant propagation has done its + work and we end with the constant "3" as one of the edges of the + loop-phi-node). The update edge is followed to the end of the + loop, and until reaching again the starting loop-phi-node: b -> c + -> b. At this point we have drawn a path from "b" to "b" from + which we compute the stride in the loop: in this example it is + "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now + that the scev for "b" is known, it is possible to compute the + scev for "c", that is "c -> {a + 1, +, 1}_1". In order to + determine the number of iterations in the loop_1, we have to + instantiate_parameters ({a + 1, +, 1}_1), that gives after some + more analysis the scev {4, +, 1}_1, or in other words, this is + the function "f (x) = x + 4", where x is the iteration count of + the loop_1. Now we have to solve the inequality "x + 4 > 10", + and take the smallest iteration number for which the loop is + exited: x = 7. This loop runs from x = 0 to x = 7, and in total + there are 8 iterations. In terms of loop normalization, we have + created a variable that is implicitly defined, "x" or just "_1", + and all the other analyzed scalars of the loop are defined in + function of this variable: + + a -> 3 + b -> {3, +, 1}_1 + c -> {4, +, 1}_1 + + or in terms of a C program: + + | a = 3 + | for (x = 0; x <= 7; x++) + | { + | b = x + 3 + | c = x + 4 + | } + + Example 2: Illustration of the algorithm on nested loops. + + | loop_1 + | a = phi (1, b) + | c = a + 2 + | loop_2 10 times + | b = phi (c, d) + | d = b + 3 + | endloop + | endloop + + For analyzing the scalar evolution of "a", the algorithm follows + the SSA edge into the loop's body: "a -> b". "b" is an inner + loop-phi-node, and its analysis as in Example 1, gives: + + b -> {c, +, 3}_2 + d -> {c + 3, +, 3}_2 + + Following the SSA edge for the initial condition, we end on "c = a + + 2", and then on the starting loop-phi-node "a". From this point, + the loop stride is computed: back on "c = a + 2" we get a "+2" in + the loop_1, then on the loop-phi-node "b" we compute the overall + effect of the inner loop that is "b = c + 30", and we get a "+30" + in the loop_1. That means that the overall stride in loop_1 is + equal to "+32", and the result is: + + a -> {1, +, 32}_1 + c -> {3, +, 32}_1 + + Example 3: Higher degree polynomials. + + | loop_1 + | a = phi (2, b) + | c = phi (5, d) + | b = a + 1 + | d = c + a + | endloop + + a -> {2, +, 1}_1 + b -> {3, +, 1}_1 + c -> {5, +, a}_1 + d -> {5 + a, +, a}_1 + + instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1 + instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1 + + Example 4: Lucas, Fibonacci, or mixers in general. + + | loop_1 + | a = phi (1, b) + | c = phi (3, d) + | b = c + | d = c + a + | endloop + + a -> (1, c)_1 + c -> {3, +, a}_1 + + The syntax "(1, c)_1" stands for a PEELED_CHREC that has the + following semantics: during the first iteration of the loop_1, the + variable contains the value 1, and then it contains the value "c". + Note that this syntax is close to the syntax of the loop-phi-node: + "a -> (1, c)_1" vs. "a = phi (1, c)". + + The symbolic chrec representation contains all the semantics of the + original code. What is more difficult is to use this information. + + Example 5: Flip-flops, or exchangers. + + | loop_1 + | a = phi (1, b) + | c = phi (3, d) + | b = c + | d = a + | endloop + + a -> (1, c)_1 + c -> (3, a)_1 + + Based on these symbolic chrecs, it is possible to refine this + information into the more precise PERIODIC_CHRECs: + + a -> |1, 3|_1 + c -> |3, 1|_1 + + This transformation is not yet implemented. + + Further readings: + + You can find a more detailed description of the algorithm in: + http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf + http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that + this is a preliminary report and some of the details of the + algorithm have changed. I'm working on a research report that + updates the description of the algorithms to reflect the design + choices used in this implementation. + + A set of slides show a high level overview of the algorithm and + run an example through the scalar evolution analyzer: + http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf + + Fixmes: + + FIXME taylor: This FIXME concerns all the cases where we have to + deal with additions of exponential functions: "exp + exp" or + "poly + exp" or "cst + exp". This could be handled by a Taylor + decomposition of the exponential function, but this is still + under construction (not implemented yet, or chrec_top). + + The idea is to represent the exponential evolution functions + using infinite degree polynomials: + + | a -> {1, *, 2}_1 = {1, +, 1, +, 1, +, ...}_1 = {1, +, a}_1 + + Proof: + \begin{eqnarray*} + \{1, *, t+1\} (x) &=& exp \left(log (1) + log (t+1) \binom{x}{1} \right) \\ + &=& (t+1)^x \\ + &=& \binom{x}{0} + \binom{x}{1}t + \binom{x}{2}t^2 + + \ldots + \binom{x}{x}t^x \\ + &=& \{1, +, t, +, t^2, +, \ldots, +, t^x\} \\ + \end{eqnarray*} + + While this equality is simple to prove for exponentials of degree + 1, it is still work in progress for higher degree exponentials. +*/ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "errors.h" +#include "ggc.h" +#include "tree.h" + +/* These RTL headers are needed for basic-block.h. */ +#include "rtl.h" +#include "basic-block.h" +#include "diagnostic.h" +#include "tree-flow.h" +#include "tree-dump.h" +#include "timevar.h" +#include "cfgloop.h" +#include "tree-fold-const.h" +#include "tree-chrec.h" +#include "tree-data-ref.h" +#include "tree-scalar-evolution.h" +#include "tree-pass.h" +#include "tree-vectorizer.h" +#include "flags.h" + +static tree analyze_scalar_evolution_1 (struct loop *, tree, tree); + +/* The cached information about a ssa name VAR, claiming that inside LOOP, + the value of VAR can be expressed as CHREC. */ + +struct scev_info_str +{ + tree var; + tree chrec; +}; + +/* Counters for the scev database. */ +static unsigned nb_set_scev = 0; +static unsigned nb_get_scev = 0; + +/* The following trees are unique elements. Thus the comparison of + another element to these elements should be done on the pointer to + these trees, and not on their value. */ + +/* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */ +tree chrec_not_analyzed_yet; + +/* Reserved to the cases where the analyzer has detected an + undecidable property at compile time. */ +tree chrec_top; + +/* When the analyzer has detected that a property will never + happen, then it qualifies it with chrec_bot. */ +tree chrec_bot; + +static struct loops *current_loops; +static varray_type already_instantiated; + +static htab_t scalar_evolution_info; + +/* Flag to indicate availability of dependency info. */ +static bool dd_info_available; + + +/* Constructs a new SCEV_INFO_STR structure. */ + +static inline struct scev_info_str * +new_scev_info_str (tree var) +{ + struct scev_info_str *res; + + res = xmalloc (sizeof (struct scev_info_str)); + res->var = var; + res->chrec = chrec_not_analyzed_yet; + + return res; +} + +/* Computes a hash function for database element ELT. */ + +static hashval_t +hash_scev_info (const void *elt) +{ + return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var); +} + +/* Compares database elements E1 and E2. */ + +static int +eq_scev_info (const void *e1, const void *e2) +{ + const struct scev_info_str *elt1 = e1; + const struct scev_info_str *elt2 = e2; + + return elt1->var == elt2->var; +} + +/* Deletes database element E. */ + +static void +del_scev_info (void *e) +{ + free (e); +} + +/* Get the index corresponding to VAR in the current LOOP. If + it's the first time we ask for this VAR, then we return + chrec_not_analysed_yet for this VAR and return its index. */ + +static tree * +find_var_scev_info (tree var) +{ + struct scev_info_str *res; + struct scev_info_str tmp; + PTR *slot; + + tmp.var = var; + slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT); + + if (!*slot) + *slot = new_scev_info_str (var); + res = *slot; + + return &res->chrec; +} + +/* Determines whether the chrec contains symbolic names defined in + LOOP_NB. */ + +bool +chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb) +{ + if (chrec == NULL_TREE) + return false; + + if (TREE_CODE (chrec) == VAR_DECL + || TREE_CODE (chrec) == PARM_DECL + || TREE_CODE (chrec) == FUNCTION_DECL + || TREE_CODE (chrec) == LABEL_DECL + || TREE_CODE (chrec) == RESULT_DECL + || TREE_CODE (chrec) == FIELD_DECL) + return true; + + if (TREE_CODE (chrec) == SSA_NAME) + { + tree def = SSA_NAME_DEF_STMT (chrec); + struct loop *def_loop = loop_of_stmt (def); + struct loop *loop = loop_from_num (current_loops, loop_nb); + + if (def_loop == NULL) + return false; + + if (loop == def_loop || flow_loop_nested_p (loop, def_loop)) + return true; + + return false; + } + + switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) + { + case 3: + if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2), + loop_nb)) + return true; + + case 2: + if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1), + loop_nb)) + return true; + + case 1: + if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0), + loop_nb)) + return true; + + default: + return false; + } +} + + + +/* This section contains the interface to the SSA IR. */ + +/* This function determines whether PHI is a loop-phi-node. Otherwise + it is a condition-phi-node. */ + +static bool +loop_phi_node_p (tree phi) +{ + /* The implementation of this function is based on the following + property: "all the loop-phi-nodes of a loop are contained in the + loop's header basic block". */ + + return loop_of_stmt (phi)->header == bb_for_stmt (phi); +} + +/* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP. + In general, in the case of multivariate evolutions we want to get + the evolution in different loops. LOOP specifies the level for + which to get the evolution. + + Example: + + | for (j = 0; j < 100; j++) + | { + | for (k = 0; k < 100; k++) + | { + | i = k + j; - Here the value of i is a function of j, k. + | } + | ... = i - Here the value of i is a function of j. + | } + | ... = i - Here the value of i is a scalar. + + Example: + + | i_0 = ... + | loop_1 10 times + | i_1 = phi (i_0, i_2) + | i_2 = i_1 + 2 + | endloop + + This loop has the same effect as: + LOOP_1 has the same effect as: + + | i_1 = i_0 + 20 + + This overall effect of the loop is obtained by passing in the + parameters: LOOP = 1, EVOLUTION_FN {i_0, +, 2}_1. +*/ + +static tree +compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) +{ + bool val = false; + + if (evolution_fn == chrec_top) + return chrec_top; + + else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC) + { + if (CHREC_VARIABLE (evolution_fn) >= loop_num (loop)) + { + struct loop *inner_loop = + loop_from_num (current_loops, CHREC_VARIABLE (evolution_fn)); + tree nb_iter = number_of_iterations_in_loop (inner_loop); + + if (nb_iter == chrec_top) + return chrec_top; + else + { + tree res; + + /* Number of iterations is off by one (the ssa name we + analyze must be defined before the exit). */ + nb_iter = chrec_fold_minus (chrec_type (nb_iter), + nb_iter, + convert (chrec_type (nb_iter), + integer_one_node)); + + /* evolution_fn is the evolution function in LOOP. Get + its value in the nb_iter-th iteration. */ + res = chrec_apply (inner_loop->num, evolution_fn, nb_iter); + + /* Continue the computation until ending on a parent of LOOP. */ + return compute_overall_effect_of_inner_loop (loop, res); + } + } + else + return evolution_fn; + } + + /* If the evolution function is an invariant, there is nothing to do. */ + else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val) + return evolution_fn; + + else + return chrec_top; +} + + + +/* The following section constitutes the interface with the chrecs. */ + +/* Determine whether the CHREC is always positive/negative. If the expression + cannot be statically analyzed, return false, otherwise set the answer into + VALUE. */ + +bool +chrec_is_positive (tree chrec, bool *value) +{ + bool value0, value1; + bool value2; + tree end_value; + tree nb_iter; + + switch (TREE_CODE (chrec)) + { + case INTERVAL_CHREC: + if (!chrec_is_positive (CHREC_LOW (chrec), &value0) + || !chrec_is_positive (CHREC_UP (chrec), &value1)) + return false; + + *value = value0; + return value0 == value1; + + case POLYNOMIAL_CHREC: + case EXPONENTIAL_CHREC: + if (!chrec_is_positive (CHREC_LEFT (chrec), &value0) + || !chrec_is_positive (CHREC_RIGHT (chrec), &value1)) + return false; + + /* FIXME -- overflows. */ + if (value0 == value1) + { + *value = value0; + return true; + } + + /* Otherwise the chrec is under the form: "{-197, +, 2}_1", + and the proof consists in showing that the sign never + changes during the execution of the loop, from 0 to + loop_nb_iterations (). */ + if (!evolution_function_is_affine_p (chrec)) + return false; + + nb_iter = number_of_iterations_in_loop + (loop_from_num (current_loops, CHREC_VARIABLE (chrec))); + nb_iter = chrec_fold_minus + (chrec_type (nb_iter), nb_iter, + convert (chrec_type (nb_iter), integer_one_node)); + +#if 0 + /* TODO -- If the test is after the exit, we may decrease the number of + iterations by one. */ + if (after_exit) + nb_iter = chrec_fold_minus + (chrec_type (nb_iter), nb_iter, + convert (chrec_type (nb_iter), integer_one_node)); +#endif + + end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter); + + if (!chrec_is_positive (end_value, &value2)) + return false; + + *value = value0; + return value0 == value1; + + case INTEGER_CST: + *value = (tree_int_cst_sgn (chrec) == 1); + return true; + + default: + return false; + } +} + +/* Associate CHREC to SCALAR. */ + +static void +set_scalar_evolution (tree scalar, tree chrec) +{ + tree *scalar_info; + + if (TREE_CODE (scalar) != SSA_NAME) + return; + + scalar_info = find_var_scev_info (scalar); + + if (dump_file) + { + if (dump_flags & TDF_DETAILS) + { + fprintf (dump_file, "(set_scalar_evolution \n"); + fprintf (dump_file, " (scalar = "); + print_generic_expr (dump_file, scalar, 0); + fprintf (dump_file, ")\n (scalar_evolution = "); + print_generic_expr (dump_file, chrec, 0); + fprintf (dump_file, "))\n"); + } + if (dump_flags & TDF_STATS) + nb_set_scev++; + } + + *scalar_info = chrec; +} + +/* Retrieve the chrec associated to SCALAR in the LOOP. */ + +static tree +get_scalar_evolution (tree scalar) +{ + tree res; + + if (dump_file) + { + if (dump_flags & TDF_DETAILS) + { + fprintf (dump_file, "(get_scalar_evolution \n"); + fprintf (dump_file, " (scalar = "); + print_generic_expr (dump_file, scalar, 0); + fprintf (dump_file, ")\n"); + } + if (dump_flags & TDF_STATS) + nb_get_scev++; + } + + switch (TREE_CODE (scalar)) + { + case SSA_NAME: + res = *find_var_scev_info (scalar); + break; + + case REAL_CST: + case INTEGER_CST: + res = scalar; + break; + + default: + res = chrec_not_analyzed_yet; + break; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (scalar_evolution = "); + print_generic_expr (dump_file, res, 0); + fprintf (dump_file, "))\n"); + } + + return res; +} + +/* When CHREC_BEFORE has an evolution part in LOOP_NB, add to this + evolution the expression TO_ADD, otherwise construct an evolution + part for this loop. */ + +static tree +add_to_evolution_1 (unsigned loop_nb, + tree chrec_before, + tree to_add) +{ + switch (TREE_CODE (chrec_before)) + { + case POLYNOMIAL_CHREC: + if (CHREC_VARIABLE (chrec_before) <= loop_nb) + { + unsigned var; + tree left, right; + tree type = chrec_type (chrec_before); + + /* When there is no evolution part in this loop, build it. */ + if (CHREC_VARIABLE (chrec_before) < loop_nb) + { + var = loop_nb; + left = chrec_before; + right = convert (type, integer_zero_node); + } + else + { + var = CHREC_VARIABLE (chrec_before); + left = CHREC_LEFT (chrec_before); + right = CHREC_RIGHT (chrec_before); + } + + return build_polynomial_chrec + (var, left, chrec_fold_plus (type, right, to_add)); + } + else + /* Search the evolution in LOOP_NB. */ + return build_polynomial_chrec + (CHREC_VARIABLE (chrec_before), + add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add), + CHREC_RIGHT (chrec_before)); + + case EXPONENTIAL_CHREC: + if (CHREC_VARIABLE (chrec_before) == loop_nb) + /* We still don't know how to fold these operations that mix + polynomial and exponential functions. For the moment, give + a rough approximation: [-oo, +oo]. */ + return build_exponential_chrec (loop_nb, CHREC_LEFT (chrec_before), + chrec_top); + + /* When there is no evolution part in this loop, build it. */ + else if (CHREC_VARIABLE (chrec_before) < loop_nb) + return build_polynomial_chrec (loop_nb, chrec_before, to_add); + + else + return build_exponential_chrec + (CHREC_VARIABLE (chrec_before), + add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add), + CHREC_RIGHT (chrec_before)); + + default: + /* These nodes do not depend on a loop. */ + if (chrec_before == chrec_top) + return chrec_top; + return build_polynomial_chrec (loop_nb, chrec_before, to_add); + } +} + +/* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension + of LOOP_NB. + + Description (provided for completeness, for those who read code in + a plane, and for my poor 62 bytes brain that would have forgotten + all this in the next two or three months): + + The algorithm of translation of programs from the SSA representation + into the chrecs syntax is based on a pattern matching. After having + reconstructed the overall tree expression for a loop, there are only + two cases that can arise: + + 1. a = loop-phi (init, a + expr) + 2. a = loop-phi (init, expr) + + where EXPR is either a scalar constant with respect to the analyzed + loop (this is a degree 0 polynomial), or an expression containing + other loop-phi definitions (these are higher degree polynomials). + + Examples: + + 1. + | init = ... + | loop_1 + | a = phi (init, a + 5) + | endloop + + 2. + | inita = ... + | initb = ... + | loop_1 + | a = phi (inita, 2 * b + 3) + | b = phi (initb, b + 1) + | endloop + + For the first case, the semantics of the SSA representation is: + + | a (x) = init + \sum_{j = 0}^{x - 1} expr (j) + + that is, there is a loop index "x" that determines the scalar value + of the variable during the loop execution. During the first + iteration, the value is that of the initial condition INIT, while + during the subsequent iterations, it is the sum of the initial + condition with the sum of all the values of EXPR from the initial + iteration to the before last considered iteration. + + For the second case, the semantics of the SSA program is: + + | a (x) = init, if x = 0; + | expr (x - 1), otherwise. + + The second case corresponds to the PEELED_CHREC, whose syntax is + close to the syntax of a loop-phi-node: + + | phi (init, expr) vs. (init, expr)_x + + The proof of the translation algorithm for the first case is a + proof by structural induction based on the degree of EXPR. + + Degree 0: + When EXPR is a constant with respect to the analyzed loop, or in + other words when EXPR is a polynomial of degree 0, the evolution of + the variable A in the loop is an affine function with an initial + condition INIT, and a step EXPR. In order to show this, we start + from the semantics of the SSA representation: + + f (x) = init + \sum_{j = 0}^{x - 1} expr (j) + + and since "expr (j)" is a constant with respect to "j", + + f (x) = init + x * expr + + Finally, based on the semantics of the pure sum chrecs, by + identification we get the corresponding chrecs syntax: + + f (x) = init * \binom{x}{0} + expr * \binom{x}{1} + f (x) -> {init, +, expr}_x + + Higher degree: + Suppose that EXPR is a polynomial of degree N with respect to the + analyzed loop_x for which we have already determined that it is + written under the chrecs syntax: + + | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x) + + We start from the semantics of the SSA program: + + | f (x) = init + \sum_{j = 0}^{x - 1} expr (j) + | + | f (x) = init + \sum_{j = 0}^{x - 1} + | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1}) + | + | f (x) = init + \sum_{j = 0}^{x - 1} + | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k}) + | + | f (x) = init + \sum_{k = 0}^{n - 1} + | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k}) + | + | f (x) = init + \sum_{k = 0}^{n - 1} + | (b_k * \binom{x}{k + 1}) + | + | f (x) = init + b_0 * \binom{x}{1} + ... + | + b_{n-1} * \binom{x}{n} + | + | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ... + | + b_{n-1} * \binom{x}{n} + | + + And finally from the definition of the chrecs syntax, we identify: + | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x + + This shows the mechanism that stands behind the add_to_evolution + function. An important point is that the use of symbolic + parameters avoids the need of an analysis schedule. + + Example: + + | inita = ... + | initb = ... + | loop_1 + | a = phi (inita, a + 2 + b) + | b = phi (initb, b + 1) + | endloop + + When analyzing "a", the algorithm keeps "b" symbolically: + + | a -> {inita, +, 2 + b}_1 + + Then, after instantiation, the analyzer ends on the evolution: + + | a -> {inita, +, 2 + initb, +, 1}_1 + +*/ + +static tree +add_to_evolution (unsigned loop_nb, + tree chrec_before, + enum tree_code code, + tree to_add) +{ + tree type = chrec_type (to_add); + tree res = NULL_TREE; + + if (to_add == NULL_TREE) + return chrec_before; + + /* TO_ADD is either a scalar, or a parameter. TO_ADD is not + instantiated at this point. */ + if (TREE_CODE (to_add) == POLYNOMIAL_CHREC + || TREE_CODE (to_add) == EXPONENTIAL_CHREC) + /* This should not happen. */ + return chrec_top; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(add_to_evolution \n"); + fprintf (dump_file, " (loop_nb = %d)\n", loop_nb); + fprintf (dump_file, " (chrec_before = "); + print_generic_expr (dump_file, chrec_before, 0); + fprintf (dump_file, ")\n (to_add = "); + print_generic_expr (dump_file, to_add, 0); + fprintf (dump_file, ")\n"); + } + + if (code == MINUS_EXPR) + to_add = chrec_fold_multiply (type, to_add, + convert (type, integer_minus_one_node)); + + res = add_to_evolution_1 (loop_nb, chrec_before, to_add); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (res = "); + print_generic_expr (dump_file, res, 0); + fprintf (dump_file, "))\n"); + } + + return res; +} + +/* When CHREC_BEFORE has an evolution part in LOOP_NB, multiply its + evolution by the expression TO_MULT, otherwise construct an + evolution part for this loop. */ + +static tree +multiply_evolution_1 (unsigned loop_nb, + tree chrec_before, + tree to_mult) +{ + if (chrec_before == chrec_not_analyzed_yet) + return chrec_not_analyzed_yet; + + switch (TREE_CODE (chrec_before)) + { + case POLYNOMIAL_CHREC: + if (CHREC_VARIABLE (chrec_before) == loop_nb) + /* We still don't know how to fold these operations that mix + polynomial and exponential functions. For the moment, give + a rough approximation: [-oo, +oo]. */ + return build_polynomial_chrec (loop_nb, CHREC_LEFT (chrec_before), + chrec_top); + + /* When there is no evolution part in this loop, build it. */ + else if (CHREC_VARIABLE (chrec_before) < loop_nb) + return build_exponential_chrec (loop_nb, chrec_before, to_mult); + + else + return build_polynomial_chrec + (CHREC_VARIABLE (chrec_before), + multiply_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_mult), + CHREC_RIGHT (chrec_before)); + + case EXPONENTIAL_CHREC: + if (CHREC_VARIABLE (chrec_before) == loop_nb + /* The evolution has to be multiplied on the leftmost position for + loop_nb. */ + && ((TREE_CODE (CHREC_LEFT (chrec_before)) != POLYNOMIAL_CHREC + && TREE_CODE (CHREC_LEFT (chrec_before)) != EXPONENTIAL_CHREC) + || (CHREC_VARIABLE (CHREC_LEFT (chrec_before)) != loop_nb))) + return build_exponential_chrec + (loop_nb, + CHREC_LEFT (chrec_before), + chrec_fold_multiply (chrec_type (to_mult), + CHREC_RIGHT (chrec_before), to_mult)); + + else if (CHREC_VARIABLE (chrec_before) < loop_nb) + return build_exponential_chrec (loop_nb, chrec_before, to_mult); + + else + return build_exponential_chrec + (CHREC_VARIABLE (chrec_before), + multiply_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_mult), + CHREC_RIGHT (chrec_before)); + + default: + /* These nodes do not depend on a loop. */ + return build_exponential_chrec (loop_nb, chrec_before, to_mult); + } +} + +/* Add TO_MULT to the evolution part of CHREC_BEFORE in the dimension + of LOOP_NB. */ + +static tree +multiply_evolution (unsigned loop_nb, + tree chrec_before, + tree to_mult) +{ + tree res = NULL_TREE; + + if (to_mult == chrec_not_analyzed_yet) + return chrec_before; + + /* TO_MULT is either a scalar, or a parameter. TO_MULT is not + instantiated at this point. */ + if (TREE_CODE (to_mult) == POLYNOMIAL_CHREC + || TREE_CODE (to_mult) == EXPONENTIAL_CHREC) + /* This should not happen. */ + return chrec_top; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(multiply_evolution \n"); + fprintf (dump_file, " (loop_nb = %d)\n", loop_nb); + fprintf (dump_file, " (chrec_before = "); + print_generic_expr (dump_file, chrec_before, 0); + fprintf (dump_file, ")\n (to_mult = "); + print_generic_expr (dump_file, to_mult, 0); + fprintf (dump_file, ")\n"); + } + + res = multiply_evolution_1 (loop_nb, chrec_before, to_mult); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (res = "); + print_generic_expr (dump_file, res, 0); + fprintf (dump_file, "))\n"); + } + + return res; +} + + + +/* This section deals with the approximation of the number of + iterations a loop will run. */ + +/* Helper function that determines whether the considered types are + compatible for finding a solution. */ +#if 0 +static bool +types_forbid_solutions_p (enum tree_code code, + tree type0, + tree type1) +{ + switch (code) + { + case LE_EXPR: + return tree_is_le (TYPE_MAX_VALUE (type0), + TYPE_MIN_VALUE (type1)); + + case LT_EXPR: + return tree_is_lt (TYPE_MAX_VALUE (type0), + TYPE_MIN_VALUE (type1)); + + case EQ_EXPR: + return false; + + case NE_EXPR: + return (tree_is_lt (TYPE_MAX_VALUE (type0), + TYPE_MIN_VALUE (type1)) + || tree_is_lt (TYPE_MAX_VALUE (type1), + TYPE_MIN_VALUE (type0))); + + default: + abort (); + return false; + } +} +#endif + +/* Helper function for the case when both evolution functions don't + have an evolution in the considered loop. */ + +static tree +first_iteration_non_satisfying_noev_noev (enum tree_code code, + unsigned loop_nb ATTRIBUTE_UNUSED, + tree chrec0, + tree chrec1) +{ + tree init0 = initial_condition (chrec0); + tree init1 = initial_condition (chrec1); + + if (TREE_CODE (init0) != INTEGER_CST + || TREE_CODE (init1) != INTEGER_CST) + return chrec_top; + + if (!evolution_function_is_constant_p (chrec0) + || !evolution_function_is_constant_p (chrec1)) + return chrec_top; + + switch (code) + { + case LE_EXPR: + if (tree_is_gt (init0, init1)) + return integer_zero_node; + else + return chrec_bot; + + case LT_EXPR: + if (tree_is_ge (init0, init1)) + return integer_zero_node; + else + return chrec_bot; + + case EQ_EXPR: + if (tree_is_eq (init0, init1)) + return integer_zero_node; + else + return chrec_bot; + + case NE_EXPR: + if (tree_is_ne (init0, init1)) + return integer_zero_node; + else + return chrec_bot; + + default: + return chrec_top; + } +} + +/* Helper function for the case when CHREC0 has no evolution and + CHREC1 has an evolution in the considered loop. */ + +static tree +first_iteration_non_satisfying_noev_ev (enum tree_code code, + unsigned loop_nb, + tree chrec0, + tree chrec1) +{ + tree type1 = chrec_type (chrec1); + /* tree tmax = TYPE_MAX_VALUE (type1); */ + tree ev_in_this_loop; + tree init0, init1, step1; + tree nb_iters; + + ev_in_this_loop = hide_evolution_in_other_loops_than_loop (chrec1, loop_nb); + if (!evolution_function_is_affine_p (ev_in_this_loop)) + /* For the moment handle only polynomials of degree 1. */ + return chrec_top; + + init1 = CHREC_LEFT (ev_in_this_loop); + step1 = CHREC_RIGHT (ev_in_this_loop); + init0 = initial_condition (chrec0); + if (TREE_CODE (init0) != INTEGER_CST + || TREE_CODE (init1) != INTEGER_CST + || TREE_CODE (step1) != INTEGER_CST) + /* For the moment we deal only with INTEGER_CSTs. */ + return chrec_top; + + switch (code) + { + case LE_EXPR: + { + if (tree_is_gt (init0, init1)) + { + if (evolution_function_is_constant_p (chrec0)) + /* Example: "while (2 <= {0, +, 1}_2)". */ + return integer_zero_node; + else + /* Example: "while ({2, +, -1}_1 <= {0, +, 1}_2)". The + number of iterations in loop_2 during the first two + iterations of loop_1 is equal to 0. */ + return chrec_top; + } + + if (tree_int_cst_sgn (step1) > 0) + { + if (evolution_function_is_constant_p (chrec0)) + /* Example: "while (2 <= {3, +, 1}_2)". */ + return chrec_top; + /* nb_iters = tree_fold_plus + (integer_type_node, + tree_fold_floor_div (integer_type_node, + tree_fold_minus (integer_type_node, + tmax, init1), + step1), + integer_one_node); + */ + else + /* Example: "while ({2, +, 1}_1 <= {3, +, 1}_2)". */ + return chrec_top; + } + + else + { + if (evolution_function_is_constant_p (chrec0)) + /* Example: "while (2 <= {3, +, -1}_2)". */ + nb_iters = tree_fold_plus + (integer_type_node, + tree_fold_floor_div (integer_type_node, + tree_fold_minus (integer_type_node, + init1, init0), + tree_fold_abs (integer_type_node, + step1)), + integer_one_node); + else + /* Example: "while ({2, +, 1}_1 <= {3, +, -1}_2)". */ + return chrec_top; + } + + /* Verify the result. */ + if (evolution_function_is_constant_p (chrec0) + && tree_is_gt (init0, + tree_fold_plus (type1, init1, + tree_fold_multiply + (integer_type_node, + nb_iters, step1)))) + return nb_iters; + + else + /* Difficult cases fall down there. Example: When the + evolution step is big enough the wrapped value can be + bigger than init0. In these cases the loop may end after + several wraps, or never end. */ + return chrec_top; + } + + case LT_EXPR: + { + if (tree_is_ge (init0, init1)) + { + if (evolution_function_is_constant_p (chrec0)) + /* Example: "while (2 < {0, +, 1}_2)". */ + return integer_zero_node; + else + /* Example: "while ({2, +, 1}_1 < {0, +, 1}_2)". */ + return chrec_top; + } + + if (tree_int_cst_sgn (step1) > 0) + { + if (evolution_function_is_constant_p (chrec0)) + /* Example: "while (2 < {3, +, 1}_2)". */ + return chrec_top; + /* nb_iters = tree_fold_ceil_div + (integer_type_node, + tree_fold_minus (integer_type_node, tmax, init1), + step1); + */ + else + /* Example: "while ({2, +, 1}_1 < {3, +, 1}_2)". */ + return chrec_top; + } + else + { + if (evolution_function_is_constant_p (chrec0)) + /* Example: "while (2 < {3, +, -1}_2)". */ + nb_iters = tree_fold_ceil_div + (integer_type_node, + tree_fold_minus (type1, init1, init0), + tree_fold_abs (type1, step1)); + else + /* Example: "while ({2, +, 1}_1 < {3, +, -1}_2)". */ + return chrec_top; + } + + /* Verify the result. */ + if (evolution_function_is_constant_p (chrec0) + && tree_is_ge (init0, + tree_fold_plus (type1, init1, + tree_fold_multiply + (integer_type_node, + nb_iters, step1)))) + return nb_iters; + + else + /* Difficult cases fall down there. */ + return chrec_top; + } + + case EQ_EXPR: + { + if (tree_is_ne (init0, init1)) + { + if (evolution_function_is_constant_p (chrec0)) + /* Example: "while (2 == {0, +, 1}_2)". */ + return integer_zero_node; + else + /* Example: "while ({2, +, -1}_1 == {0, +, 1}_2)". */ + return chrec_top; + } + + if (evolution_function_is_constant_p (chrec0)) + { + if (integer_zerop (step1)) + /* Example: "while (2 == {2, +, 0}_2)". */ + return chrec_bot; + else + return integer_one_node; + } + else + return chrec_top; + } + + case NE_EXPR: + { + if (tree_is_eq (init0, init1)) + { + if (evolution_function_is_constant_p (chrec0)) + /* Example: "while (0 != {0, +, 1}_2)". */ + return integer_zero_node; + else + /* Example: "while ({0, +, -1}_1 != {0, +, 1}_2)". */ + return chrec_top; + } + + if (tree_int_cst_sgn (step1) > 0) + { + if (evolution_function_is_constant_p (chrec0)) + { + if (tree_is_gt (init0, init1)) + { + tree diff = tree_fold_minus (integer_type_node, + init0, init1); + if (tree_fold_divides_p (integer_type_node, step1, diff)) + /* Example: "while (3 != {2, +, 1}_2)". */ + nb_iters = tree_fold_exact_div + (integer_type_node, diff, step1); + else + /* Example: "while (3 != {2, +, 2}_2)". */ + return chrec_top; + } + else + /* Example: "while (2 != {3, +, 1}_2)". */ + return chrec_top; + } + else + /* Example: "while ({2, +, 1}_1 != {3, +, 1}_2)". */ + return chrec_top; + } + + else + { + if (evolution_function_is_constant_p (chrec0)) + { + if (tree_is_lt (init0, init1)) + { + tree diff = tree_fold_minus (integer_type_node, + init1, init0); + if (tree_fold_divides_p (integer_type_node, step1, diff)) + /* Example: "while (2 != {3, +, -1}_2)". */ + nb_iters = tree_fold_exact_div + (integer_type_node, diff, + tree_fold_abs (integer_type_node, step1)); + else + /* Example: "while (2 != {3, +, -2}_2)". */ + return chrec_top; + } + else + /* Example: "while (3 != {2, +, -1}_2)". */ + return chrec_top; + } + else + /* Example: "while ({2, +, 1}_1 != {3, +, -1}_2)". */ + return chrec_top; + } + + /* Verify the result. */ + if (evolution_function_is_constant_p (chrec0) + && tree_is_eq (init0, + tree_fold_plus (type1, init1, + tree_fold_multiply + (integer_type_node, + nb_iters, step1)))) + return nb_iters; + + else + /* Difficult cases fall down there. */ + return chrec_top; + } + + default: + return chrec_top; + } + return chrec_top; +} + +/* Helper function for the case when CHREC1 has no evolution and + CHREC0 has an evolution in the considered loop. */ + +static tree +first_iteration_non_satisfying_ev_noev (enum tree_code code, + unsigned loop_nb, + tree chrec0, + tree chrec1) +{ + tree type0 = chrec_type (chrec0); + /* tree tmin = TYPE_MIN_VALUE (type0); */ + tree ev_in_this_loop; + tree init0, init1, step0; + tree nb_iters; + + ev_in_this_loop = hide_evolution_in_other_loops_than_loop (chrec0, loop_nb); + if (!evolution_function_is_affine_p (ev_in_this_loop)) + /* For the moment handle only polynomials of degree 1. */ + return chrec_top; + + init0 = CHREC_LEFT (ev_in_this_loop); + step0 = CHREC_RIGHT (ev_in_this_loop); + init1 = initial_condition (chrec1); + if (TREE_CODE (init1) != INTEGER_CST + || TREE_CODE (init0) != INTEGER_CST + || TREE_CODE (step0) != INTEGER_CST) + /* For the moment we deal only with INTEGER_CSTs. */ + return chrec_top; + + switch (code) + { + case LE_EXPR: + { + if (tree_is_gt (init0, init1)) + { + if (evolution_function_is_constant_p (chrec1)) + /* Example: "while ({2, +, 1}_2 <= 0)". */ + return integer_zero_node; + + else + /* Example: "while ({2, +, 1}_2 <= {0, +, 1}_1)". */ + return chrec_top; + } + + if (tree_int_cst_sgn (step0) < 0) + { + if (evolution_function_is_constant_p (chrec1)) + /* Example: "while ({2, +, -1}_2 <= 3)". */ + return chrec_top; + /* nb_iters = tree_fold_plus + (integer_type_node, + tree_fold_floor_div (integer_type_node, + tree_fold_minus (integer_type_node, + init0, tmin), + tree_fold_abs (integer_type_node, + step0)), + integer_one_node); + */ + else + /* Example: "while ({2, +, -1}_2 <= {3, +, 1}_1)". */ + return chrec_top; + } + else + { + if (evolution_function_is_constant_p (chrec1)) + /* Example: "while ({2, +, 1}_2 <= 3)". */ + nb_iters = tree_fold_plus + (integer_type_node, + tree_fold_floor_div (integer_type_node, + tree_fold_minus (integer_type_node, + init1, init0), + step0), + integer_one_node); + else + /* Example: "while ({2, +, 1}_2 <= {3, +, 1}_1)". */ + return chrec_top; + } + + /* Verify the result. */ + if (evolution_function_is_constant_p (chrec1) + && tree_is_gt (tree_fold_plus (type0, init0, + tree_fold_multiply + (integer_type_node, + nb_iters, step0)), + init1)) + return nb_iters; + + else + /* Difficult cases fall down there. */ + return chrec_top; + } + + case LT_EXPR: + { + if (tree_is_ge (init0, init1)) + { + if (evolution_function_is_constant_p (chrec1)) + /* Example: "while ({2, +, 1}_2 < 0)". */ + return integer_zero_node; + + else + /* Example: "while ({2, +, 1}_2 < {0, +, 1}_1)". */ + return chrec_top; + } + + if (tree_int_cst_sgn (step0) < 0) + { + if (evolution_function_is_constant_p (chrec1)) + /* Example: "while ({2, +, -1}_2 < 3)". */ + return chrec_top; + /* nb_iters = tree_fold_ceil_div + (integer_type_node, + tree_fold_minus (integer_type_node, init0, tmin), + tree_fold_abs (integer_type_node, step0)); + */ + else + /* Example: "while ({2, +, -1}_2 < {3, +, 1}_1)". */ + return chrec_top; + } + else + { + if (evolution_function_is_constant_p (chrec1)) + /* Example: "while ({2, +, 1}_2 < 3)". */ + nb_iters = tree_fold_ceil_div + (integer_type_node, + tree_fold_minus (integer_type_node, init1, init0), + step0); + else + /* Example: "while ({2, +, 1}_2 < {3, +, 1}_1)". */ + return chrec_top; + } + + /* Verify the result. */ + if (evolution_function_is_constant_p (chrec1) + && tree_is_ge (tree_fold_plus (type0, init0, + tree_fold_multiply + (integer_type_node, + nb_iters, step0)), + init1)) + return nb_iters; + + else + /* Difficult cases fall down there. */ + return chrec_top; + } + + case EQ_EXPR: + { + if (tree_is_ne (init0, init1)) + { + if (evolution_function_is_constant_p (chrec1)) + /* Example: "while ({2, +, 1}_2 == 0)". */ + return integer_zero_node; + else + /* Example: "while ({2, +, -1}_2 == {0, +, 1}_1)". */ + return chrec_top; + } + + if (evolution_function_is_constant_p (chrec1)) + { + if (integer_zerop (step0)) + /* Example: "while ({2, +, 0}_2 == 2)". */ + return chrec_bot; + else + return integer_one_node; + } + else + return chrec_top; + } + + case NE_EXPR: + { + if (tree_is_eq (init0, init1)) + { + if (evolution_function_is_constant_p (chrec1)) + /* Example: "while ({0, +, 1}_2 != 0)". */ + return integer_zero_node; + else + /* Example: "while ({0, +, -1}_2 != {0, +, 1}_1)". */ + return chrec_top; + } + + if (tree_int_cst_sgn (step0) > 0) + { + if (evolution_function_is_constant_p (chrec1)) + { + if (tree_is_lt (init0, init1)) + { + tree diff = tree_fold_minus (integer_type_node, + init1, init0); + if (tree_fold_divides_p (integer_type_node, step0, diff)) + /* Example: "while ({2, +, 1}_2 != 3)". */ + nb_iters = tree_fold_exact_div + (integer_type_node, diff, step0); + else + /* Example: "while ({2, +, 2}_2 != 3)". */ + return chrec_top; + } + else + /* Example: "while ({3, +, 1}_2 != 2)". */ + return chrec_top; + } + else + /* Example: "while ({2, +, 1}_2 != {3, +, 1}_1)". */ + return chrec_top; + } + + else + { + if (evolution_function_is_constant_p (chrec1)) + { + if (tree_is_gt (init0, init1)) + { + tree diff = tree_fold_minus (integer_type_node, + init0, init1); + if (tree_fold_divides_p (integer_type_node, step0, diff)) + /* Example: "while ({3, +, -1}_2 != 2)". */ + nb_iters = tree_fold_exact_div + (integer_type_node, diff, + tree_fold_abs (integer_type_node, step0)); + else + /* Example: "while ({3, +, -2}_2 != 2)". */ + return chrec_top; + } + else + /* Example: "while ({2, +, -1}_2 != 3)". */ + return chrec_top; + } + else + /* Example: "while ({2, +, -1}_2 != {3, +, -1}_1)". */ + return chrec_top; + } + + /* Verify the result. */ + if (evolution_function_is_constant_p (chrec1) + && tree_is_eq (tree_fold_plus (type0, init0, + tree_fold_multiply + (integer_type_node, + nb_iters, step0)), + init1)) + return nb_iters; + else + /* Difficult cases fall down there. */ + return chrec_top; + } + + default: + return chrec_top; + } + + return chrec_top; +} + +/* Helper function for the case when both CHREC0 and CHREC1 has an + evolution in the considered loop. */ + +static tree +first_iteration_non_satisfying_ev_ev (enum tree_code code, + unsigned loop_nb ATTRIBUTE_UNUSED, + tree chrec0 ATTRIBUTE_UNUSED, + tree chrec1 ATTRIBUTE_UNUSED) +{ + switch (code) + { + case LE_EXPR: + + case LT_EXPR: + + case EQ_EXPR: + + case NE_EXPR: + + default: + return chrec_top; + } + + return chrec_top; +} + +/* Helper function. */ + +static tree +first_iteration_non_satisfying_1 (enum tree_code code, + unsigned loop_nb, + tree chrec0, + tree chrec1) +{ + bool val = false; + tree res, other_evs; + + if (automatically_generated_chrec_p (chrec0) + || automatically_generated_chrec_p (chrec1)) + return chrec_top; + + if (!no_evolution_in_loop_p (chrec0, loop_nb, &val)) + return chrec_top; + + else if (val) + { + if (!no_evolution_in_loop_p (chrec1, loop_nb, &val)) + return chrec_top; + + else if (val) + return first_iteration_non_satisfying_noev_noev (code, loop_nb, + chrec0, chrec1); + else + { + res = first_iteration_non_satisfying_noev_ev (code, loop_nb, + chrec0, chrec1); + if (res == chrec_top) + return res; + + other_evs = hide_evolution_in_loop (chrec1, loop_nb); + other_evs = chrec_replace_initial_condition + (other_evs, convert (chrec_type (other_evs), integer_zero_node)); + } + } + + else + { + if (!no_evolution_in_loop_p (chrec1, loop_nb, &val)) + return chrec_top; + + else if (val) + { + res = first_iteration_non_satisfying_ev_noev (code, loop_nb, + chrec0, chrec1); + if (res == chrec_top) + return res; + + other_evs = hide_evolution_in_loop (chrec0, loop_nb); + other_evs = chrec_replace_initial_condition + (other_evs, convert (chrec_type (other_evs), integer_zero_node)); + } + else + return first_iteration_non_satisfying_ev_ev (code, loop_nb, + chrec0, chrec1); + } + + res = chrec_fold_minus (chrec_type (res), res, other_evs); + return res; +} + +/* Try to compute the first iteration I of LOOP_NB that does not satisfy + CODE: in the context of the computation of the number of iterations: + - if (CODE is LE_EXPR) the loop exits when CHREC0 (I) > CHREC1 (I), + - if (CODE is LT_EXPR) the loop exits when CHREC0 (I) >= CHREC1 (I), + - if (CODE is EQ_EXPR) the loop exits when CHREC0 (I) != CHREC1 (I), + ... + + The result is one of the following: + - CHREC_TOP when the analyzer cannot determine the property, + - CHREC_BOT when the property is always true, + - an INTEGER_CST tree node, + - a CHREC, + - an expression containing SSA_NAMEs. +*/ + +tree +first_iteration_non_satisfying (enum tree_code code, + unsigned loop_nb, + tree chrec0, + tree chrec1) +{ + switch (code) + { + case LT_EXPR: + return first_iteration_non_satisfying_1 (LT_EXPR, loop_nb, + chrec0, chrec1); + + case LE_EXPR: + return first_iteration_non_satisfying_1 (LE_EXPR, loop_nb, + chrec0, chrec1); + + case GT_EXPR: + return first_iteration_non_satisfying_1 (LT_EXPR, loop_nb, + chrec1, chrec0); + + case GE_EXPR: + return first_iteration_non_satisfying_1 (LE_EXPR, loop_nb, + chrec1, chrec0); + + case EQ_EXPR: + return first_iteration_non_satisfying_1 (EQ_EXPR, loop_nb, + chrec0, chrec1); + + case NE_EXPR: + return first_iteration_non_satisfying_1 (NE_EXPR, loop_nb, + chrec0, chrec1); + + default: + return chrec_top; + } +} + +/* Helper function. */ + +static inline tree +set_nb_iterations_in_loop (struct loop *loop, + tree res) +{ + /* After the loop copy headers has transformed the code, each loop + runs at least once. */ + res = chrec_fold_plus (chrec_type (res), res, integer_one_node); + /* FIXME HWI: However we want to store one iteration less than the + count of the loop in order to be compatible with the other + nb_iter computations in loop-iv. This also allows the + representation of nb_iters that are equal to MAX_INT. */ + if (TREE_CODE (res) == INTEGER_CST + && TREE_INT_CST_LOW (res) == 0) + res = chrec_top; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (set_nb_iterations_in_loop = "); + print_generic_expr (dump_file, res, 0); + fprintf (dump_file, "))\n"); + } + + loop->nb_iterations = res; + return res; +} + + + +/* This section selects the loops that will be good candidates for the + scalar evolution analysis. + + Note: This section will be rewritten to expose a better interface + to other client passes. For the moment, greedily select all the + loop nests we could analyze. */ + +/* Determine whether it is possible to analyze this condition + expression. */ + +static bool +analyzable_condition (tree expr) +{ + tree condition; + + if (TREE_CODE (expr) != COND_EXPR) + return false; + + condition = TREE_OPERAND (expr, 0); + + switch (TREE_CODE (condition)) + { + case SSA_NAME: + /* Volatile expressions are not analyzable. */ + if (TREE_THIS_VOLATILE (SSA_NAME_VAR (condition))) + return false; + return true; + + case LT_EXPR: + case LE_EXPR: + case GT_EXPR: + case GE_EXPR: + case EQ_EXPR: + case NE_EXPR: + { + tree opnd0, opnd1; + + opnd0 = TREE_OPERAND (condition, 0); + opnd1 = TREE_OPERAND (condition, 1); + + if (TREE_CODE (opnd0) == SSA_NAME + && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd0))) + return false; + + if (TREE_CODE (opnd1) == SSA_NAME + && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd1))) + return false; + + return true; + } + + default: + return false; + } + + return false; +} + +/* For a loop with a single exit edge, determine the COND_EXPR that + guards the exit edge. If the expression is too difficult to + analyze, then give up. */ + +tree +get_loop_exit_condition (struct loop *loop) +{ + tree res = NULL_TREE; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(get_loop_exit_condition \n "); + + if (loop_exit_edges (loop)) + { + edge exit_edge; + tree expr; + + exit_edge = loop_exit_edge (loop, 0); + expr = last_stmt (edge_source (exit_edge)); + + if (analyzable_condition (expr)) + res = expr; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + print_generic_expr (dump_file, res, 0); + fprintf (dump_file, ")\n"); + } + + return res; +} + +/* Recursively determine and enqueue the exit conditions for a loop. */ + +static void +get_exit_conditions_rec (struct loop *loop, + varray_type *exit_conditions) +{ + if (!loop) + return; + + /* Recurse on the inner loops, then on the next (sibling) loops. */ + get_exit_conditions_rec (inner_loop (loop), exit_conditions); + get_exit_conditions_rec (next_loop (loop), exit_conditions); + + flow_loop_scan (loop, LOOP_EXIT_EDGES); + if (loop_num_exits (loop) == 1) + { + tree loop_condition = get_loop_exit_condition (loop); + + if (loop_condition) + VARRAY_PUSH_TREE (*exit_conditions, loop_condition); + } +} + +/* Select the candidate loop nests for the analysis. This function + initializes the EXIT_CONDITIONS array. The vector EXIT_CONDITIONS is + initialized in a loop-depth-first order, ie. the inner loops + conditions appear before the outer. This property of the + EXIT_CONDITIONS list is exploited by the evolution analyzer. */ + +static void +select_loops_exit_conditions (struct loops *loops, + varray_type *exit_conditions) +{ + struct loop *function_body = loops->parray[0]; + + get_exit_conditions_rec (inner_loop (function_body), exit_conditions); +} + + + +/* Debugging functions section. */ + +extern void draw_tree_cfg (void); + +/* Draw the flow graph. */ + +void +draw_tree_cfg (void) +{ + FILE *dump_file; + if (n_basic_blocks > 0) + { + dump_file = fopen ("tree_cfg.dot", "w"); + if (dump_file) + { + tree_cfg2dot (dump_file); + fclose (dump_file); + system ("dotty tree_cfg.dot"); + } + } +} + + +/* Depth first search algorithm. */ + +static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *); + +/* Follow the ssa edge into the right hand side of an assignment. */ + +static bool +follow_ssa_edge_in_rhs (struct loop *loop, + tree rhs, + tree halting_phi, + tree *evolution_of_loop) +{ + bool res = false; + tree rhs0, rhs1; + tree type_rhs = TREE_TYPE (rhs); + + /* The RHS is one of the following cases: + - an SSA_NAME, + - an INTEGER_CST, + - a PLUS_EXPR, + - a MINUS_EXPR, + - other cases are not yet handled. + */ + switch (TREE_CODE (rhs)) + { + case INTEGER_CST: + /* This assignment is under the form "a_1 = 7". */ + res = false; + break; + + case SSA_NAME: + /* This assignment is under the form: "a_1 = b_2". */ + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop); + break; + + case PLUS_EXPR: + /* This case is under the form "rhs0 + rhs1". */ + rhs0 = TREE_OPERAND (rhs, 0); + rhs1 = TREE_OPERAND (rhs, 1); + + if (TREE_CODE (rhs0) == SSA_NAME) + { + if (TREE_CODE (rhs1) == SSA_NAME) + { + /* Match an assignment under the form: + "a = b + c". */ + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, + evolution_of_loop); + + if (res) + *evolution_of_loop = add_to_evolution + (loop->num, + chrec_convert (type_rhs, *evolution_of_loop), + PLUS_EXPR, rhs1); + + else + { + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, + evolution_of_loop); + + if (res) + *evolution_of_loop = add_to_evolution + (loop->num, + chrec_convert (type_rhs, *evolution_of_loop), + PLUS_EXPR, rhs0); + } + } + + else + { + /* Match an assignment under the form: + "a = b + ...". */ + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, + evolution_of_loop); + if (res) + *evolution_of_loop = add_to_evolution + (loop->num, chrec_convert (type_rhs, *evolution_of_loop), + PLUS_EXPR, rhs1); + } + } + + else if (TREE_CODE (rhs1) == SSA_NAME) + { + /* Match an assignment under the form: + "a = ... + c". */ + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, + evolution_of_loop); + if (res) + *evolution_of_loop = add_to_evolution + (loop->num, chrec_convert (type_rhs, *evolution_of_loop), + PLUS_EXPR, rhs0); + } + + else + /* Otherwise, match an assignment under the form: + "a = ... + ...". */ + /* And there is nothing to do. */ + res = false; + + break; + + case MINUS_EXPR: + /* This case is under the form "opnd0 = rhs0 - rhs1". */ + rhs0 = TREE_OPERAND (rhs, 0); + rhs1 = TREE_OPERAND (rhs, 1); + if (TREE_CODE (rhs0) == SSA_NAME) + { + if (TREE_CODE (rhs1) == SSA_NAME) + { + /* Match an assignment under the form: + "a = b - c". */ + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, + evolution_of_loop); + + if (res) + *evolution_of_loop = add_to_evolution + (loop->num, chrec_convert (type_rhs, *evolution_of_loop), + MINUS_EXPR, rhs1); + + else + { + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, + evolution_of_loop); + + if (res) + *evolution_of_loop = add_to_evolution + (loop->num, + chrec_fold_multiply (type_rhs, + *evolution_of_loop, + convert (type_rhs, + integer_minus_one_node)), + PLUS_EXPR, rhs0); + } + } + + else + { + /* Match an assignment under the form: + "a = b - ...". */ + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, + evolution_of_loop); + if (res) + *evolution_of_loop = add_to_evolution + (loop->num, chrec_convert (type_rhs, *evolution_of_loop), + MINUS_EXPR, rhs1); + } + } + + else if (TREE_CODE (rhs1) == SSA_NAME) + { + /* Match an assignment under the form: + "a = ... - c". */ + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, + evolution_of_loop); + if (res) + *evolution_of_loop = add_to_evolution + (loop->num, + chrec_fold_multiply (type_rhs, + *evolution_of_loop, + convert (type_rhs, integer_minus_one_node)), + PLUS_EXPR, rhs0); + } + + else + /* Otherwise, match an assignment under the form: + "a = ... - ...". */ + /* And there is nothing to do. */ + res = false; + + break; + + case MULT_EXPR: + /* This case is under the form "opnd0 = rhs0 * rhs1". */ + rhs0 = TREE_OPERAND (rhs, 0); + rhs1 = TREE_OPERAND (rhs, 1); + if (TREE_CODE (rhs0) == SSA_NAME) + { + if (TREE_CODE (rhs1) == SSA_NAME) + { + /* Match an assignment under the form: + "a = b * c". */ + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, + evolution_of_loop); + + if (res) + *evolution_of_loop = multiply_evolution + (loop->num, *evolution_of_loop, rhs1); + + else + { + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, + evolution_of_loop); + + if (res) + *evolution_of_loop = multiply_evolution + (loop->num, *evolution_of_loop, rhs0); + } + } + + else + { + /* Match an assignment under the form: + "a = b * ...". */ + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, + evolution_of_loop); + if (res) + *evolution_of_loop = multiply_evolution + (loop->num, *evolution_of_loop, rhs1); + } + } + + else if (TREE_CODE (rhs1) == SSA_NAME) + { + /* Match an assignment under the form: + "a = ... * c". */ + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, + evolution_of_loop); + if (res) + *evolution_of_loop = multiply_evolution + (loop->num, *evolution_of_loop, rhs0); + } + + else + /* Otherwise, match an assignment under the form: + "a = ... * ...". */ + /* And there is nothing to do. */ + res = false; + + break; + + default: + res = false; + break; + } + + return res; +} + +/* Checks whether the I-th argument of a PHI comes from a backedge. */ + +static bool +backedge_phi_arg_p (tree phi, int i) +{ + edge e = PHI_ARG_EDGE (phi, i); + + /* We would in fact like to test EDGE_DFS_BACK here, but we do not care + about updating it anywhere, and this should work as well most of the + time. */ + if (e->flags & EDGE_IRREDUCIBLE_LOOP) + return true; + + return false; +} + +/* Helper function for one branch of the condition-phi-node. */ + +static inline bool +follow_ssa_edge_in_condition_phi_branch (int i, + struct loop *loop, + tree condition_phi, + tree halting_phi, + tree *evolution_of_branch, + tree init_cond) +{ + tree branch = PHI_ARG_DEF (condition_phi, i); + *evolution_of_branch = chrec_top; + + /* Do not follow back edges (they must belong to an irreducible loop, which + we really do not want to worry about). */ + if (backedge_phi_arg_p (condition_phi, i)) + return false; + + if (TREE_CODE (branch) == SSA_NAME) + { + *evolution_of_branch = init_cond; + return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, + evolution_of_branch); + } + + /* This case occurs when one of the condition branches sets + the variable to a constant: ie. a phi-node like + "a_2 = PHI <a_7(5), 2(6)>;". + The testsuite/.../ssa-chrec-17.c exercises this code. + + FIXME: This case have to be refined correctly: + in some cases it is possible to say something better than + chrec_top, for example using a wrap-around notation. */ + return false; +} + +/* This function merges the branches of a condition-phi-node in a + loop. */ + +static bool +follow_ssa_edge_in_condition_phi (struct loop *loop, + tree condition_phi, + tree halting_phi, + tree *evolution_of_loop) +{ + int i; + tree init = *evolution_of_loop; + tree evolution_of_branch; + + if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi, + halting_phi, + &evolution_of_branch, + init)) + return false; + *evolution_of_loop = evolution_of_branch; + + for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++) + { + if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi, + halting_phi, + &evolution_of_branch, + init)) + return false; + + *evolution_of_loop = chrec_merge (*evolution_of_loop, + evolution_of_branch); + } + + return true; +} + +/* Follow an SSA edge in an inner loop. It computes the overall + effect of the loop, and following the symbolic initial conditions, + it follows the edges in the parent loop. The inner loop is + considered as a single statement. */ + +static bool +follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, + tree loop_phi_node, + tree halting_phi, + tree *evolution_of_loop) +{ + struct loop *loop = loop_of_stmt (loop_phi_node); + tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node)); + + /* Sometimes, the inner loop is too difficult to analyze, and the + result of the analysis is a symbolic parameter. */ + if (ev == PHI_RESULT (loop_phi_node)) + { + bool res = false; + int i; + + for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) + { + tree arg = PHI_ARG_DEF (loop_phi_node, i); + basic_block bb; + + /* Follow the edges that exit the inner loop. */ + bb = PHI_ARG_EDGE (loop_phi_node, i)->src; + if (!flow_bb_inside_loop_p (loop, bb)) + res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi, + evolution_of_loop); + } + + /* If the path crosses this loop-phi, give up. */ + if (res == true) + *evolution_of_loop = chrec_top; + + return res; + } + + /* Otherwise, compute the overall effect of the inner loop. */ + ev = compute_overall_effect_of_inner_loop (loop, ev); + return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi, + evolution_of_loop); +} + +/* Follow an SSA edge from a loop-phi-node to itself, constructing a + path that is analyzed on the return walk. */ + +static bool +follow_ssa_edge (struct loop *loop, + tree def, + tree halting_phi, + tree *evolution_of_loop) +{ + struct loop *def_loop; + + if (TREE_CODE (def) == NOP_EXPR) + return false; + + def_loop = loop_of_stmt (def); + + switch (TREE_CODE (def)) + { + case PHI_NODE: + if (!loop_phi_node_p (def)) + /* DEF is a condition-phi-node. Follow the branches, and + record their evolutions. Finally, merge the collected + information and set the approximation to the main + variable. */ + return follow_ssa_edge_in_condition_phi + (loop, def, halting_phi, evolution_of_loop); + + /* When the analyzed phi is the halting_phi, the + depth-first search is over: we have found a path from + the halting_phi to itself in the loop. */ + if (def == halting_phi) + return true; + + /* Otherwise, the evolution of the HALTING_PHI depends + on the evolution of another loop-phi-node, ie. the + evolution function is a higher degree polynomial. */ + if (def_loop == loop) + return false; + + /* Inner loop. */ + if (flow_loop_nested_p (loop, def_loop)) + return follow_ssa_edge_inner_loop_phi + (loop, def, halting_phi, evolution_of_loop); + + /* Outer loop. */ + return false; + + case MODIFY_EXPR: + return follow_ssa_edge_in_rhs (loop, + TREE_OPERAND (def, 1), + halting_phi, + evolution_of_loop); + + default: + /* At this level of abstraction, the program is just a set + of MODIFY_EXPRs and PHI_NODEs. In principle there is no + other node to be handled. */ + return false; + } +} + + + +/* Given a LOOP_PHI_NODE, this function determines the evolution + function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */ + +static tree +analyze_evolution_in_loop (tree loop_phi_node, + tree init_cond) +{ + int i; + tree evolution_function = chrec_not_analyzed_yet; + struct loop *loop = loop_of_stmt (loop_phi_node); + basic_block bb; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(analyze_evolution_in_loop \n"); + fprintf (dump_file, " (loop_phi_node = "); + print_generic_expr (dump_file, loop_phi_node, 0); + fprintf (dump_file, ")\n"); + } + + for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) + { + tree arg = PHI_ARG_DEF (loop_phi_node, i); + tree ssa_chain, ev_fn; + bool res; + + /* Select the edges that enter the loop body. */ + bb = PHI_ARG_EDGE (loop_phi_node, i)->src; + if (!flow_bb_inside_loop_p (loop, bb)) + continue; + + if (TREE_CODE (arg) == SSA_NAME) + { + ssa_chain = SSA_NAME_DEF_STMT (arg); + + /* Pass in the initial condition to the follow edge function. */ + ev_fn = init_cond; + res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn); + } + else + res = false; + + /* When it is impossible to go back on the same + loop_phi_node by following the ssa edges, the + evolution is represented by a peeled chrec, ie. the + first iteration, EV_FN has the value INIT_COND, then + all the other iterations it has the value of ARG. */ + if (!res) + { + /* FIXME: when dealing with periodic scalars, the + analysis of the scalar evolution of ARG would + create an infinite recurrence. Solution: don't + try to simplify the peeled chrec at this time, + but wait until having more information. */ + ev_fn = build_peeled_chrec (loop->num, init_cond, arg); + + /* Try to simplify the peeled chrec. */ + ev_fn = simplify_peeled_chrec (ev_fn); + } + + /* When there are multiple back edges of the loop (which in fact never + happens currently, but nevertheless), merge their evolutions. */ + evolution_function = chrec_merge (evolution_function, ev_fn); + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (evolution_function = "); + print_generic_expr (dump_file, evolution_function, 0); + fprintf (dump_file, "))\n"); + } + + return evolution_function; +} + +/* Given a loop-phi-node, this function determines the initial + conditions of the variable on entry of the loop. When the CCP has + propagated constants into the loop-phi-node, the initial condition + is instantiated, otherwise the initial condition is kept symbolic. + This analyzer does not analyze the evolution outside the current + loop, and leaves this task to the on-demand tree reconstructor. */ + +static tree +analyze_initial_condition (tree loop_phi_node) +{ + int i; + tree init_cond = chrec_not_analyzed_yet; + struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(analyze_initial_condition \n"); + fprintf (dump_file, " (loop_phi_node = \n"); + print_generic_expr (dump_file, loop_phi_node, 0); + fprintf (dump_file, ")\n"); + } + + for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) + { + tree branch = PHI_ARG_DEF (loop_phi_node, i); + basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src; + + /* When the branch is oriented to the loop's body, it does + not contribute to the initial condition. */ + if (flow_bb_inside_loop_p (loop, bb)) + continue; + + if (init_cond == chrec_not_analyzed_yet) + { + init_cond = branch; + continue; + } + + if (TREE_CODE (branch) == SSA_NAME) + { + init_cond = chrec_top; + break; + } + + init_cond = chrec_merge (init_cond, branch); + } + + /* Ooops -- a loop without an entry??? */ + if (init_cond == chrec_not_analyzed_yet) + init_cond = chrec_top; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (init_cond = "); + print_generic_expr (dump_file, init_cond, 0); + fprintf (dump_file, "))\n"); + } + + return init_cond; +} + +/* Analyze the scalar evolution for LOOP_PHI_NODE. */ + +static tree +interpret_loop_phi (struct loop *loop, tree loop_phi_node) +{ + tree res; + struct loop *phi_loop = loop_of_stmt (loop_phi_node); + tree init_cond; + + if (phi_loop != loop) + { + struct loop *subloop; + tree evolution_fn = analyze_scalar_evolution + (phi_loop, PHI_RESULT (loop_phi_node)); + + /* Dive one level deeper. */ + subloop = superloop_at_depth (phi_loop, loop->depth + 1); + + /* Interpret the subloop. */ + res = compute_overall_effect_of_inner_loop (subloop, evolution_fn); + return res; + } + + /* Otherwise really interpret the loop phi. */ + init_cond = analyze_initial_condition (loop_phi_node); + res = analyze_evolution_in_loop (loop_phi_node, init_cond); + + return res; +} + +/* This function merges the branches of a condition-phi-node, + contained in the outermost loop, and whose arguments are already + analyzed. */ + +static tree +interpret_condition_phi (struct loop *loop, tree condition_phi) +{ + int i; + tree res = chrec_not_analyzed_yet; + + for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++) + { + tree branch_chrec; + + if (backedge_phi_arg_p (condition_phi, i)) + { + res = chrec_top; + break; + } + + branch_chrec = analyze_scalar_evolution + (loop, PHI_ARG_DEF (condition_phi, i)); + + res = chrec_merge (res, branch_chrec); + } + + return res; +} + +/* Interpret the right hand side of a modify_expr OPND1. If we didn't + analyzed this node before, follow the definitions until ending + either on an analyzed modify_expr, or on a loop-phi-node. On the + return path, this function propagates evolutions (ala constant copy + propagation). OPND1 is not a GIMPLE expression because we could + analyze the effect of an inner loop: see interpret_loop_phi. */ + +static tree +interpret_rhs_modify_expr (struct loop *loop, + tree opnd1, tree type) +{ + tree res, opnd10, opnd11, chrec10, chrec11; + + if (is_gimple_min_invariant (opnd1)) + return chrec_convert (type, opnd1); + + switch (TREE_CODE (opnd1)) + { + case PLUS_EXPR: + opnd10 = TREE_OPERAND (opnd1, 0); + opnd11 = TREE_OPERAND (opnd1, 1); + chrec10 = analyze_scalar_evolution (loop, opnd10); + chrec11 = analyze_scalar_evolution (loop, opnd11); + chrec10 = chrec_convert (type, chrec10); + chrec11 = chrec_convert (type, chrec11); + res = chrec_fold_plus (type, chrec10, chrec11); + break; + + case MINUS_EXPR: + opnd10 = TREE_OPERAND (opnd1, 0); + opnd11 = TREE_OPERAND (opnd1, 1); + chrec10 = analyze_scalar_evolution (loop, opnd10); + chrec11 = analyze_scalar_evolution (loop, opnd11); + chrec10 = chrec_convert (type, chrec10); + chrec11 = chrec_convert (type, chrec11); + res = chrec_fold_minus (type, chrec10, chrec11); + break; + + case NEGATE_EXPR: + opnd10 = TREE_OPERAND (opnd1, 0); + chrec10 = analyze_scalar_evolution (loop, opnd10); + chrec10 = chrec_convert (type, chrec10); + res = chrec_fold_minus (type, convert (type, integer_zero_node), + chrec10); + break; + + case MULT_EXPR: + opnd10 = TREE_OPERAND (opnd1, 0); + opnd11 = TREE_OPERAND (opnd1, 1); + chrec10 = analyze_scalar_evolution (loop, opnd10); + chrec11 = analyze_scalar_evolution (loop, opnd11); + chrec10 = chrec_convert (type, chrec10); + chrec11 = chrec_convert (type, chrec11); + res = chrec_fold_multiply (type, chrec10, chrec11); + break; + + case SSA_NAME: + res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1)); + break; + + case NOP_EXPR: + case CONVERT_EXPR: + opnd10 = TREE_OPERAND (opnd1, 0); + chrec10 = analyze_scalar_evolution (loop, opnd10); + res = chrec_convert (type, chrec10); + break; + + default: + res = chrec_top; + break; + } + + return res; +} + + + +/* This section contains all the entry points: + - number_of_iterations_in_loop, + - analyze_scalar_evolution, + - instantiate_parameters. +*/ + +/* Compute the evolution function in WRTO_LOOP, the nearest common + ancestor of DEF_LOOP and USE_LOOP. */ + +static tree +compute_scalar_evolution_in_loop (struct loop *wrto_loop, + struct loop *def_loop, + tree ev) +{ + tree res; + if (def_loop == wrto_loop) + return ev; + + def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1); + res = compute_overall_effect_of_inner_loop (def_loop, ev); + + return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet); +} + +/* Helper recursive function. */ + +static tree +analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) +{ + tree def, type = TREE_TYPE (var); + basic_block bb; + struct loop *def_loop; + + if (loop == NULL) + return chrec_top; + + if (TREE_CODE (var) != SSA_NAME) + return interpret_rhs_modify_expr (loop, var, type); + + def = SSA_NAME_DEF_STMT (var); + bb = bb_for_stmt (def); + def_loop = bb ? bb->loop_father : NULL; + + if (bb == NULL + || !flow_bb_inside_loop_p (loop, bb)) + { + /* Keep the symbolic form. */ + res = var; + goto set_and_end; + } + + if (res != chrec_not_analyzed_yet) + { + if (loop != bb->loop_father) + res = compute_scalar_evolution_in_loop + (find_common_loop (loop, bb->loop_father), bb->loop_father, res); + + goto set_and_end; + } + + if (loop != def_loop) + { + res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet); + res = compute_scalar_evolution_in_loop (loop, def_loop, res); + + goto set_and_end; + } + + switch (TREE_CODE (def)) + { + case MODIFY_EXPR: + res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type); + break; + + case PHI_NODE: + if (loop_phi_node_p (def)) + res = interpret_loop_phi (loop, def); + else + res = interpret_condition_phi (loop, def); + break; + + default: + res = chrec_top; + break; + } + + set_and_end: + + /* Keep the symbolic form. */ + if (res == chrec_top) + res = var; + + if (loop == def_loop) + set_scalar_evolution (var, res); + + return res; +} + +/* Entry point for the scalar evolution analyzer. + Analyzes and returns the scalar evolution of the ssa_name VAR. + LOOP_NB is the identifier number of the loop in which the variable + is used. + + Example of use: having a pointer VAR to a SSA_NAME node, STMT a + pointer to the statement that uses this variable, in order to + determine the evolution function of the variable, use the following + calls: + + unsigned loop_nb = loop_num (loop_of_stmt (stmt)); + tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var); + tree chrec_instantiated = instantiate_parameters + (loop_nb, chrec_with_symbols); +*/ + +tree +analyze_scalar_evolution (struct loop *loop, tree var) +{ + tree res; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(analyze_scalar_evolution \n"); + fprintf (dump_file, " (loop_nb = %d)\n", loop->num); + fprintf (dump_file, " (scalar = "); + print_generic_expr (dump_file, var, 0); + fprintf (dump_file, ")\n"); + } + + res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var)); + + if (TREE_CODE (var) == SSA_NAME && res == chrec_top) + res = var; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); + + return res; +} + +/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to + WRTO_LOOP (which should be a superloop of both USE_LOOP and definition + of VERSION). */ + +tree +analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop, + tree version) +{ + bool val = false; + tree ev = version; + + while (1) + { + ev = analyze_scalar_evolution (use_loop, ev); + + if (use_loop == wrto_loop) + return ev; + + /* If the value of the use changes in the inner loop, we cannot express + its value in the outer loop (we might try to return interval chrec, + but we do not have a user for it anyway) */ + if (!no_evolution_in_loop_p (ev, use_loop->num, &val) + || !val) + return chrec_top; + + use_loop = use_loop->outer; + } +} + +/* Analyze all the parameters of the chrec that were left under a symbolic form, + with respect to LOOP. CHREC is the chrec to instantiate. */ + +static tree +instantiate_parameters_1 (struct loop *loop, tree chrec) +{ + tree res, op0, op1, op2; + basic_block def_bb; + struct loop *def_loop; + + if (chrec == NULL_TREE + || automatically_generated_chrec_p (chrec)) + return chrec; + + if (is_gimple_min_invariant (chrec)) + return chrec; + + switch (TREE_CODE (chrec)) + { + case SSA_NAME: + def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec)); + + /* A parameter, nothing to do. */ + if (!def_bb) + return chrec; + + /* Don't instantiate the SSA_NAME if it is in a mixer + structure. This is used for avoiding the instantiation of + recursively defined functions, such as: + + | a_2 -> {0, +, 1, +, a_2}_1 + + Note: the size of already_instantiated is proportional to + the degree of the evolution function. This is the number + of parameters that have to be instantiated, and is almost + all the time less than 2. */ + if (tree_is_in_varray_tree_p (chrec, already_instantiated)) + { + if (!flow_bb_inside_loop_p (loop, def_bb)) + { + /* It is an invariant in LOOP, so we may keep the symbolic + form. */ + return chrec; + } + else + { + /* Something with unknown behavior in LOOP. */ + return chrec_top; + } + } + + def_loop = find_common_loop (loop, def_bb->loop_father); + + /* If the analysis yields a parametric chrec, instantiate + the result again. Enqueue the SSA_NAME such that it will + never be instantiated twice, avoiding the cyclic + instantiation in mixers. */ + VARRAY_PUSH_TREE (already_instantiated, chrec); + res = analyze_scalar_evolution (def_loop, chrec); + res = instantiate_parameters (loop, res); + VARRAY_POP (already_instantiated); + return res; + + case POLYNOMIAL_CHREC: + op0 = instantiate_parameters (loop, CHREC_LEFT (chrec)); + op1 = instantiate_parameters (loop, CHREC_RIGHT (chrec)); + return build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); + + case EXPONENTIAL_CHREC: + op0 = instantiate_parameters (loop, CHREC_LEFT (chrec)); + op1 = instantiate_parameters (loop, CHREC_RIGHT (chrec)); + return build_exponential_chrec (CHREC_VARIABLE (chrec), op0, op1); + + case PEELED_CHREC: + op0 = instantiate_parameters (loop, CHREC_LEFT (chrec)); + op1 = instantiate_parameters (loop, CHREC_RIGHT (chrec)); + return build_peeled_chrec (CHREC_VARIABLE (chrec), op0, op1); + + case INTERVAL_CHREC: + op0 = instantiate_parameters (loop, CHREC_LOW (chrec)); + op1 = instantiate_parameters (loop, CHREC_UP (chrec)); + return build_interval_chrec (op0, op1); + + case PLUS_EXPR: + op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0)); + op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1)); + return chrec_fold_plus (TREE_TYPE (chrec), op0, op1); + + case MINUS_EXPR: + op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0)); + op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1)); + return chrec_fold_minus (TREE_TYPE (chrec), op0, op1); + + case MULT_EXPR: + op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0)); + op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1)); + return chrec_fold_multiply (TREE_TYPE (chrec), op0, op1); + + case NOP_EXPR: + op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0)); + return chrec_convert (TREE_TYPE (chrec), op0); + + default: + break; + } + + switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) + { + case 3: + op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0)); + op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1)); + op2 = instantiate_parameters (loop, TREE_OPERAND (chrec, 2)); + return build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1, op2); + + case 2: + op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0)); + op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1)); + return build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); + + case 1: + op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0)); + return build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0); + + case 0: + return chrec; + + default: + break; + } + + /* Too complicated to handle. */ + return chrec_top; +} + +/* Analyze all the parameters of the chrec that were left under a + symbolic form. LOOP is the loop in which symbolic names have to + be analyzed and instantiated. */ + +tree +instantiate_parameters (struct loop *loop, + tree chrec) +{ + tree res; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(instantiate_parameters \n"); + fprintf (dump_file, " (loop_nb = %d)\n", loop->num); + fprintf (dump_file, " (chrec = "); + print_generic_expr (dump_file, chrec, 0); + fprintf (dump_file, ")\n"); + } + + res = instantiate_parameters_1 (loop, chrec); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (res = "); + print_generic_expr (dump_file, res, 0); + fprintf (dump_file, "))\n"); + } + + return res; +} + +/* Entry point for the analysis of the number of iterations pass. + This function tries to safely approximate the number of iterations + the loop will run. When this property is not decidable at compile + time, the result is chrec_top: [-oo, +oo]. Otherwise the result is + a scalar, an interval, or a symbolic parameter. + + Example of analysis: suppose that the loop has an exit condition: + + "if (b > 49) goto end_loop;" + + and that in a previous analysis we have determined that the + variable 'b' has an evolution function: + + "EF = {23, +, 5}_2". + + When we evaluate the function at the point 5, i.e. the value of the + variable 'b' after 5 iterations in the loop, we have EF (5) = 48, + and EF (6) = 53. In this case the value of 'b' on exit is '53' and + the loop body has been executed 6 times. */ + +tree +number_of_iterations_in_loop (struct loop *loop) +{ + enum tree_code code; + tree res; + tree cond, test, opnd0, opnd1; + tree chrec0, chrec1; + edge exit; + + /* Determine whether the number_of_iterations_in_loop has already + been computed. */ + res = loop_nb_iterations (loop); + if (res) + return res; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(number_of_iterations_in_loop \n"); + + cond = get_loop_exit_condition (loop); + if (cond == NULL_TREE) + return set_nb_iterations_in_loop (loop, chrec_top); + + test = TREE_OPERAND (cond, 0); + exit = loop_exit_edge (loop, 0); + if (exit->flags & EDGE_TRUE_VALUE) + test = invert_truthvalue (test); + + code = TREE_CODE (test); + switch (code) + { + case SSA_NAME: + /* "while (opnd0 != 0)". */ + code = NE_EXPR; + chrec0 = analyze_scalar_evolution (loop, test); + chrec1 = integer_zero_node; + + if (chrec0 == chrec_top) + /* KEEP_IT_SYMBOLIC. */ + chrec0 = test; + + goto end; + + case LT_EXPR: + case LE_EXPR: + case GT_EXPR: + case GE_EXPR: + case EQ_EXPR: + case NE_EXPR: + opnd0 = TREE_OPERAND (test, 0); + opnd1 = TREE_OPERAND (test, 1); + chrec0 = analyze_scalar_evolution (loop, opnd0); + chrec1 = analyze_scalar_evolution (loop, opnd1); + + chrec0 = instantiate_parameters (loop, chrec0); + chrec1 = instantiate_parameters (loop, chrec1); + + if (chrec0 == chrec_top) + /* KEEP_IT_SYMBOLIC. */ + chrec0 = opnd0; + + if (chrec1 == chrec_top) + /* KEEP_IT_SYMBOLIC. */ + chrec1 = opnd1; + + goto end; + + default: + return set_nb_iterations_in_loop (loop, chrec_top); + } + + end: + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (loop_nb = %d)\n", loop->num); + fprintf (dump_file, " (loop_while_expr_is_true: "); + print_generic_expr (dump_file, test, 0); + fprintf (dump_file, ")\n (chrec0 = "); + print_generic_expr (dump_file, chrec0, 0); + fprintf (dump_file, ")\n (chrec1 = "); + print_generic_expr (dump_file, chrec1, 0); + fprintf (dump_file, ")\n"); + } + + if (chrec_contains_undetermined (chrec0) + || chrec_contains_undetermined (chrec1)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " (nb_iterations cannot be determined))\n"); + + /* Do not update the loop->nb_iterations. */ + return chrec_top; + } + + res = first_iteration_non_satisfying (code, loop->num, chrec0, chrec1); + + return set_nb_iterations_in_loop (loop, res); +} + +/* One of the drivers for testing the scalar evolutions analysis. + This function computes the number of iterations for all the loops + from the EXIT_CONDITIONS array. */ + +static void +number_of_iterations_for_all_loops (varray_type exit_conditions) +{ + unsigned int i; + unsigned nb_chrec_top_loops = 0; + unsigned nb_static_loops = 0; + + for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++) + { + tree res = number_of_iterations_in_loop + (loop_of_stmt (VARRAY_TREE (exit_conditions, i))); + if (res == chrec_top) + nb_chrec_top_loops++; + else + nb_static_loops++; + } + + if (dump_file) + { + fprintf (dump_file, "\n(\n"); + fprintf (dump_file, "-----------------------------------------\n"); + fprintf (dump_file, "%d\tnb_chrec_top_loops\n", nb_chrec_top_loops); + fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops); + fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num); + fprintf (dump_file, "-----------------------------------------\n"); + fprintf (dump_file, ")\n\n"); + + print_loop_ir (dump_file); + } +} + + + +/* Counters for the stats. */ + +struct chrec_stats +{ + unsigned nb_chrecs; + unsigned nb_peeled; + unsigned nb_affine; + unsigned nb_affine_multivar; + unsigned nb_higher_poly; + unsigned nb_expo; + unsigned nb_chrec_top; + unsigned nb_interval_chrec; + unsigned nb_undetermined; +}; + +/* Reset the counters. */ + +static inline void +reset_chrecs_counters (struct chrec_stats *stats) +{ + stats->nb_chrecs = 0; + stats->nb_peeled = 0; + stats->nb_affine = 0; + stats->nb_affine_multivar = 0; + stats->nb_higher_poly = 0; + stats->nb_expo = 0; + stats->nb_chrec_top = 0; + stats->nb_interval_chrec = 0; + stats->nb_undetermined = 0; +} + +/* Dump the contents of a CHREC_STATS structure. */ + +static void +dump_chrecs_stats (FILE *file, struct chrec_stats *stats) +{ + fprintf (file, "\n(\n"); + fprintf (file, "-----------------------------------------\n"); + fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine); + fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar); + fprintf (file, "%d\tdegree greater than 2 polynomials\n", + stats->nb_higher_poly); + fprintf (file, "%d\taffine peeled chrecs\n", stats->nb_peeled); + fprintf (file, "%d\texponential chrecs\n", stats->nb_expo); + fprintf (file, "%d\tchrec_top chrecs\n", stats->nb_chrec_top); + fprintf (file, "%d\tinterval chrecs\n", stats->nb_chrec_top); + fprintf (file, "-----------------------------------------\n"); + fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs); + fprintf (file, "%d\twith undetermined coefficients\n", + stats->nb_undetermined); + fprintf (file, "-----------------------------------------\n"); + fprintf (file, "%d\tchrecs in the scev database\n", + (int) htab_elements (scalar_evolution_info)); + fprintf (file, "%d\tsets in the scev database\n", nb_set_scev); + fprintf (file, "%d\tgets in the scev database\n", nb_get_scev); + fprintf (file, "-----------------------------------------\n"); + fprintf (file, ")\n\n"); +} + +/* Gather statistics about CHREC. */ + +static void +gather_chrec_stats (tree chrec, struct chrec_stats *stats) +{ + if (dump_file && (dump_flags & TDF_STATS)) + { + fprintf (dump_file, "(classify_chrec "); + print_generic_expr (dump_file, chrec, 0); + fprintf (dump_file, "\n"); + } + + stats->nb_chrecs++; + + if (chrec == NULL_TREE) + { + stats->nb_undetermined++; + return; + } + + switch (TREE_CODE (chrec)) + { + case POLYNOMIAL_CHREC: + if (evolution_function_is_affine_p (chrec)) + { + if (dump_file && (dump_flags & TDF_STATS)) + fprintf (dump_file, " affine_univariate\n"); + stats->nb_affine++; + } + else if (evolution_function_is_affine_multivariate_p (chrec)) + { + if (dump_file && (dump_flags & TDF_STATS)) + fprintf (dump_file, " affine_multivariate\n"); + stats->nb_affine_multivar++; + } + else + { + if (dump_file && (dump_flags & TDF_STATS)) + fprintf (dump_file, " higher_degree_polynomial\n"); + stats->nb_higher_poly++; + } + + break; + + case EXPONENTIAL_CHREC: + if (dump_file && (dump_flags & TDF_STATS)) + fprintf (dump_file, " exponential\n"); + stats->nb_expo++; + break; + + case INTERVAL_CHREC: + if (chrec == chrec_top) + { + if (dump_file && (dump_flags & TDF_STATS)) + fprintf (dump_file, " chrec_top\n"); + stats->nb_chrec_top++; + } + else + { + if (dump_file && (dump_flags & TDF_STATS)) + fprintf (dump_file, " interval chrec\n"); + stats->nb_interval_chrec++; + } + break; + + case PEELED_CHREC: + if (dump_file && (dump_flags & TDF_STATS)) + fprintf (dump_file, " peeled chrec\n"); + stats->nb_peeled++; + break; + + default: + break; + } + + if (chrec_contains_undetermined (chrec)) + { + if (dump_file && (dump_flags & TDF_STATS)) + fprintf (dump_file, " undetermined\n"); + stats->nb_undetermined++; + } + + if (dump_file && (dump_flags & TDF_STATS)) + fprintf (dump_file, ")\n"); +} + +/* One of the drivers for testing the scalar evolutions analysis. + This function analyzes the scalar evolution of all the scalars + defined as loop phi nodes in one of the loops from the + EXIT_CONDITIONS array. + + TODO Optimization: A loop is in canonical form if it contains only + a single scalar loop phi node. All the other scalars that have an + evolution in the loop are rewritten in function of this single + index. This allows the parallelization of the loop. */ + +static void +analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions) +{ + unsigned int i; + struct chrec_stats stats; + + reset_chrecs_counters (&stats); + + for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++) + { + struct loop *loop; + basic_block bb; + tree phi, chrec; + + loop = loop_of_stmt (VARRAY_TREE (exit_conditions, i)); + bb = loop_header (loop); + + for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + if (is_gimple_reg (PHI_RESULT (phi))) + { + chrec = instantiate_parameters + (loop, + analyze_scalar_evolution (loop, PHI_RESULT (phi))); + + if (dump_file && (dump_flags & TDF_STATS)) + gather_chrec_stats (chrec, &stats); + } + } + + if (dump_file && (dump_flags & TDF_STATS)) + dump_chrecs_stats (dump_file, &stats); +} + +/* Callback for htab_traverse, gathers information on chrecs in the + hashtable. */ + +static int +gather_stats_on_scev_database_1 (void **slot, void *stats) +{ + struct scev_info_str *entry = *slot; + + gather_chrec_stats (entry->chrec, stats); + + return 1; +} + +/* Classify the chrecs of the whole database. */ + +void +gather_stats_on_scev_database (void) +{ + struct chrec_stats stats; + + if (!dump_file) + return; + + reset_chrecs_counters (&stats); + + htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1, + &stats); + + dump_chrecs_stats (dump_file, &stats); +} + + + +static void initialize_scalar_evolutions_analyzer (void); +static void scev_init (void); +static void scev_analysis (void); +static void scev_depend (void); +static void scev_elim_checks (void); +static void scev_vectorize (void); +static void scev_done (void); +static bool gate_scev (void); +static bool gate_scev_analysis (void); +static bool gate_scev_depend (void); +static bool gate_scev_elim_checks (void); +static bool gate_scev_vectorize (void); + +/* Initializer. */ + +static void +initialize_scalar_evolutions_analyzer (void) +{ + /* The elements below are unique. The values contained in these + intervals are not used. */ + chrec_not_analyzed_yet = NULL_TREE; + chrec_top = build_interval_chrec + (build_int_2 (2222, 0), build_int_2 (3222, 0)); + chrec_bot = build_interval_chrec + (build_int_2 (3333, 0), build_int_2 (4333, 0)); +} + +/* Initialize the analysis of scalar evolutions for LOOPS. */ + +void +scev_initialize (struct loops *loops) +{ + unsigned i; + current_loops = loops; + + scalar_evolution_info = htab_create (100, hash_scev_info, + eq_scev_info, del_scev_info); + VARRAY_TREE_INIT (already_instantiated, 3, + "already_instantiated"); + + initialize_scalar_evolutions_analyzer (); + + for (i = 1; i < loops->num; i++) + if (loops->parray[i]) + flow_loop_scan (loops->parray[i], LOOP_EXIT_EDGES); +} + +/* Initialize the analysis of scalar evolutions. */ + +static void +scev_init (void) +{ + current_loops = tree_loop_optimizer_init (NULL, flag_tree_loop != 0); + if (!current_loops) + return; + scev_initialize (current_loops); +} + +/* Runs the analysis of scalar evolutions. */ + +static void +scev_analysis (void) +{ + varray_type exit_conditions; + + VARRAY_GENERIC_PTR_INIT (exit_conditions, 37, "exit_conditions"); + select_loops_exit_conditions (current_loops, &exit_conditions); + +#if 0 + dump_file = stderr; + dump_flags = 31; +#endif + + if (dump_file && (dump_flags & TDF_STATS)) + analyze_scalar_evolution_for_all_loop_phi_nodes (exit_conditions); + + number_of_iterations_for_all_loops (exit_conditions); + VARRAY_CLEAR (exit_conditions); +} + +/* Runs the analysis of all the data dependences. */ + +static void +scev_depend (void) +{ + analyze_all_data_dependences (current_loops); + dd_info_available = true; +} + +static void +scev_elim_checks (void) +{ + eliminate_redundant_checks (); +} + +/* Runs the linear loop transformations. */ + +static void +scev_linear_transform (void) +{ + linear_transform_loops (current_loops); +} + +/* Runs the canonical iv creation pass. */ + +static void +scev_iv_canon (void) +{ + canonicalize_induction_variables (current_loops); +} + +/* Runs the vectorization pass. */ + +static void +scev_vectorize (void) +{ + bitmap_clear (vars_to_rename); + + vectorize_loops (current_loops); +} + +/* Finalize the scalar evolution analysis. */ + +void +scev_finalize (void) +{ + htab_delete (scalar_evolution_info); + already_instantiated = NULL; + current_loops = NULL; +} + +/* Finalize the scalar evolution passes. */ + +static void +scev_done (void) +{ + if (current_loops) + { + loop_optimizer_finalize (current_loops, NULL); + scev_finalize (); + cleanup_tree_cfg (); + } + + dd_info_available = false; +} + +static bool +gate_scev (void) +{ + return (flag_scalar_evolutions != 0 + || flag_tree_vectorize != 0 + || flag_all_data_deps != 0 + || flag_tree_elim_checks != 0 + || flag_tree_loop_linear != 0); +} + +static bool +gate_scev_analysis (void) +{ + return current_loops && flag_scalar_evolutions != 0; +} + +static bool +gate_scev_depend (void) +{ + return current_loops && flag_all_data_deps != 0; +} + +static bool +gate_scev_elim_checks (void) +{ + return current_loops && flag_tree_elim_checks != 0; +} + +static bool +gate_scev_linear_transform (void) +{ + return current_loops && flag_tree_loop_linear != 0; +} + +static bool +gate_scev_iv_canon (void) +{ + return (current_loops + /* Only run this pass if we will be able to eliminate the + superfluous ivs we create. */ + && flag_tree_loop); +} + +static bool +gate_scev_vectorize (void) +{ + return current_loops && flag_tree_vectorize != 0; +} + +static bool +gate_ddg (void) +{ + return dd_info_available && flag_ddg && flag_scalar_evolutions != 0; +} + +static bool +gate_delete_ddg (void) +{ + return flag_ddg && flag_scalar_evolutions != 0; +} + +static void +create_dg_graph (void) +{ + dg_create_graph (current_loops); +} + +struct tree_opt_pass pass_scev = +{ + NULL, /* name */ + gate_scev, /* gate */ + NULL, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func /* todo_flags_finish */ +}; + +struct tree_opt_pass pass_scev_init = +{ + NULL, /* name */ + NULL, /* gate */ + scev_init, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0 /* todo_flags_finish */ +}; + +struct tree_opt_pass pass_scev_anal = +{ + "scev", /* name */ + gate_scev_analysis, /* gate */ + scev_analysis, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_SCALAR_EVOLUTIONS, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0 /* todo_flags_finish */ +}; + +struct tree_opt_pass pass_scev_depend = +{ + "ddall", /* name */ + gate_scev_depend, /* gate */ + scev_depend, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_ALL_DATA_DEPS, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + PROP_scev, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0 /* todo_flags_finish */ +}; + +struct tree_opt_pass pass_scev_vectorize = +{ + "vect", /* name */ + gate_scev_vectorize, /* gate */ + scev_vectorize, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_VECTORIZATION, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_rename_vars /* todo_flags_finish */ +}; + +struct tree_opt_pass pass_scev_linear_transform = +{ + "ltrans", /* name */ + gate_scev_linear_transform, /* gate */ + scev_linear_transform, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_LINEAR_TRANSFORM, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func /* todo_flags_finish */ +}; + +struct tree_opt_pass pass_scev_iv_canon = +{ + "ivcan", /* name */ + gate_scev_iv_canon, /* gate */ + scev_iv_canon, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_LOOP_IVCANON, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func /* todo_flags_finish */ +}; + +struct tree_opt_pass pass_scev_elim_checks = +{ + "elck", /* name */ + gate_scev_elim_checks, /* gate */ + scev_elim_checks, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_ELIM_CHECKS, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func /* todo_flags_finish */ +}; + +struct tree_opt_pass pass_scev_done = +{ + NULL, /* name */ + NULL, /* gate */ + scev_done, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0 /* todo_flags_finish */ +}; + +struct tree_opt_pass pass_ddg = +{ + "ddg", /* name */ + gate_ddg, /* gate */ + create_dg_graph, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_DEP_GRAPH, /* tv_id */ + PROP_scev, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0 /* todo_flags_finish */ +}; + +struct tree_opt_pass pass_delete_ddg = +{ + "delete ddg", /* name */ + gate_delete_ddg, /* gate */ + dg_delete_graph, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_DEP_GRAPH, /* tv_id */ + 0, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0 /* todo_flags_finish */ +}; |