1 /* Scalar evolution detector.
2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3    Contributed by Sebastian Pop <s.pop@laposte.net>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
22 /*
23    Description:
25    This pass analyzes the evolution of scalar variables in loop
26    structures.  The algorithm is based on the SSA representation,
27    and on the loop hierarchy tree.  This algorithm is not based on
28    the notion of versions of a variable, as it was the case for the
29    previous implementations of the scalar evolution algorithm, but
30    it assumes that each defined name is unique.
32    The notation used in this file is called "chains of recurrences",
33    and has been proposed by Eugene Zima, Robert Van Engelen, and
34    others for describing induction variables in programs.  For example
35    "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
36    when entering in the loop_1 and has a step 2 in this loop, in other
37    words "for (b = 0; b < N; b+=2);".  Note that the coefficients of
38    this chain of recurrence (or chrec [shrek]) can contain the name of
39    other variables, in which case they are called parametric chrecs.
40    For example, "b -> {a, +, 2}_1" means that the initial value of "b"
41    is the value of "a".  In most of the cases these parametric chrecs
42    are fully instantiated before their use because symbolic names can
43    hide some difficult cases such as self-references described later
44    (see the Fibonacci example).
46    A short sketch of the algorithm is:
48    Given a scalar variable to be analyzed, follow the SSA edge to
49    its definition:
51    - When the definition is a MODIFY_EXPR: if the right hand side
52    (RHS) of the definition cannot be statically analyzed, the answer
53    of the analyzer is: "don't know".
54    Otherwise, for all the variables that are not yet analyzed in the
55    RHS, try to determine their evolution, and finally try to
56    evaluate the operation of the RHS that gives the evolution
57    function of the analyzed variable.
59    - When the definition is a condition-phi-node: determine the
60    evolution function for all the branches of the phi node, and
61    finally merge these evolutions (see chrec_merge).
63    - When the definition is a loop-phi-node: determine its initial
64    condition, that is the SSA edge defined in an outer loop, and
65    keep it symbolic.  Then determine the SSA edges that are defined
66    in the body of the loop.  Follow the inner edges until ending on
67    another loop-phi-node of the same analyzed loop.  If the reached
68    loop-phi-node is not the starting loop-phi-node, then we keep
69    this definition under a symbolic form.  If the reached
70    loop-phi-node is the same as the starting one, then we compute a
71    symbolic stride on the return path.  The result is then the
72    symbolic chrec {initial_condition, +, symbolic_stride}_loop.
74    Examples:
76    Example 1: Illustration of the basic algorithm.
78    | a = 3
79    | loop_1
80    |   b = phi (a, c)
81    |   c = b + 1
82    |   if (c > 10) exit_loop
83    | endloop
85    Suppose that we want to know the number of iterations of the
86    loop_1.  The exit_loop is controlled by a COND_EXPR (c > 10).  We
87    ask the scalar evolution analyzer two questions: what's the
88    scalar evolution (scev) of "c", and what's the scev of "10".  For
89    "10" the answer is "10" since it is a scalar constant.  For the
90    scalar variable "c", it follows the SSA edge to its definition,
91    "c = b + 1", and then asks again what's the scev of "b".
92    Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93    c)", where the initial condition is "a", and the inner loop edge
94    is "c".  The initial condition is kept under a symbolic form (it
95    may be the case that the copy constant propagation has done its
96    work and we end with the constant "3" as one of the edges of the
97    loop-phi-node).  The update edge is followed to the end of the
98    loop, and until reaching again the starting loop-phi-node: b -> c
99    -> b.  At this point we have drawn a path from "b" to "b" from
100    which we compute the stride in the loop: in this example it is
101    "+1".  The resulting scev for "b" is "b -> {a, +, 1}_1".  Now
102    that the scev for "b" is known, it is possible to compute the
103    scev for "c", that is "c -> {a + 1, +, 1}_1".  In order to
104    determine the number of iterations in the loop_1, we have to
105    instantiate_parameters ({a + 1, +, 1}_1), that gives after some
106    more analysis the scev {4, +, 1}_1, or in other words, this is
107    the function "f (x) = x + 4", where x is the iteration count of
108    the loop_1.  Now we have to solve the inequality "x + 4 > 10",
109    and take the smallest iteration number for which the loop is
110    exited: x = 7.  This loop runs from x = 0 to x = 7, and in total
111    there are 8 iterations.  In terms of loop normalization, we have
112    created a variable that is implicitly defined, "x" or just "_1",
113    and all the other analyzed scalars of the loop are defined in
114    function of this variable:
116    a -> 3
117    b -> {3, +, 1}_1
118    c -> {4, +, 1}_1
120    or in terms of a C program:
122    | a = 3
123    | for (x = 0; x <= 7; x++)
124    |   {
125    |     b = x + 3
126    |     c = x + 4
127    |   }
129    Example 2: Illustration of the algorithm on nested loops.
131    | loop_1
132    |   a = phi (1, b)
133    |   c = a + 2
134    |   loop_2  10 times
135    |     b = phi (c, d)
136    |     d = b + 3
137    |   endloop
138    | endloop
140    For analyzing the scalar evolution of "a", the algorithm follows
141    the SSA edge into the loop's body: "a -> b".  "b" is an inner
142    loop-phi-node, and its analysis as in Example 1, gives:
144    b -> {c, +, 3}_2
145    d -> {c + 3, +, 3}_2
147    Following the SSA edge for the initial condition, we end on "c = a
148    + 2", and then on the starting loop-phi-node "a".  From this point,
149    the loop stride is computed: back on "c = a + 2" we get a "+2" in
150    the loop_1, then on the loop-phi-node "b" we compute the overall
151    effect of the inner loop that is "b = c + 30", and we get a "+30"
152    in the loop_1.  That means that the overall stride in loop_1 is
153    equal to "+32", and the result is:
155    a -> {1, +, 32}_1
156    c -> {3, +, 32}_1
158    Example 3: Higher degree polynomials.
160    | loop_1
161    |   a = phi (2, b)
162    |   c = phi (5, d)
163    |   b = a + 1
164    |   d = c + a
165    | endloop
167    a -> {2, +, 1}_1
168    b -> {3, +, 1}_1
169    c -> {5, +, a}_1
170    d -> {5 + a, +, a}_1
172    instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
173    instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
175    Example 4: Lucas, Fibonacci, or mixers in general.
177    | loop_1
178    |   a = phi (1, b)
179    |   c = phi (3, d)
180    |   b = c
181    |   d = c + a
182    | endloop
184    a -> (1, c)_1
185    c -> {3, +, a}_1
187    The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
188    following semantics: during the first iteration of the loop_1, the
189    variable contains the value 1, and then it contains the value "c".
190    Note that this syntax is close to the syntax of the loop-phi-node:
191    "a -> (1, c)_1" vs. "a = phi (1, c)".
193    The symbolic chrec representation contains all the semantics of the
194    original code.  What is more difficult is to use this information.
196    Example 5: Flip-flops, or exchangers.
198    | loop_1
199    |   a = phi (1, b)
200    |   c = phi (3, d)
201    |   b = c
202    |   d = a
203    | endloop
205    a -> (1, c)_1
206    c -> (3, a)_1
208    Based on these symbolic chrecs, it is possible to refine this
209    information into the more precise PERIODIC_CHRECs:
211    a -> |1, 3|_1
212    c -> |3, 1|_1
214    This transformation is not yet implemented.
216    Further readings:
218    You can find a more detailed description of the algorithm in:
219    http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
220    http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz.  But note that
221    this is a preliminary report and some of the details of the
222    algorithm have changed.  I'm working on a research report that
223    updates the description of the algorithms to reflect the design
224    choices used in this implementation.
226    A set of slides show a high level overview of the algorithm and run
227    an example through the scalar evolution analyzer:
228    http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
230    The slides that I have presented at the GCC Summit'04 are available
231    at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
232 */
234 #include "config.h"
235 #include "system.h"
236 #include "coretypes.h"
237 #include "tm.h"
238 #include "ggc.h"
239 #include "tree.h"
240 #include "real.h"
242 /* These RTL headers are needed for basic-block.h.  */
243 #include "rtl.h"
244 #include "basic-block.h"
245 #include "diagnostic.h"
246 #include "tree-flow.h"
247 #include "tree-dump.h"
248 #include "timevar.h"
249 #include "cfgloop.h"
250 #include "tree-chrec.h"
251 #include "tree-scalar-evolution.h"
252 #include "tree-pass.h"
253 #include "flags.h"
254 #include "params.h"
256 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
257 static tree resolve_mixers (struct loop *, tree);
259 /* The cached information about a ssa name VAR, claiming that inside LOOP,
260    the value of VAR can be expressed as CHREC.  */
262 struct scev_info_str
263 {
264   tree var;
265   tree chrec;
266 };
268 /* Counters for the scev database.  */
269 static unsigned nb_set_scev = 0;
270 static unsigned nb_get_scev = 0;
272 /* The following trees are unique elements.  Thus the comparison of
273    another element to these elements should be done on the pointer to
274    these trees, and not on their value.  */
276 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE.  */
277 tree chrec_not_analyzed_yet;
279 /* Reserved to the cases where the analyzer has detected an
280    undecidable property at compile time.  */
281 tree chrec_dont_know;
283 /* When the analyzer has detected that a property will never
284    happen, then it qualifies it with chrec_known.  */
285 tree chrec_known;
287 static bitmap already_instantiated;
289 static htab_t scalar_evolution_info;
291 \f
292 /* Constructs a new SCEV_INFO_STR structure.  */
294 static inline struct scev_info_str *
295 new_scev_info_str (tree var)
296 {
297   struct scev_info_str *res;
299   res = XNEW (struct scev_info_str);
300   res->var = var;
301   res->chrec = chrec_not_analyzed_yet;
303   return res;
304 }
306 /* Computes a hash function for database element ELT.  */
308 static hashval_t
309 hash_scev_info (const void *elt)
310 {
311   return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var);
312 }
314 /* Compares database elements E1 and E2.  */
316 static int
317 eq_scev_info (const void *e1, const void *e2)
318 {
319   const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
320   const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
322   return elt1->var == elt2->var;
323 }
325 /* Deletes database element E.  */
327 static void
328 del_scev_info (void *e)
329 {
330   free (e);
331 }
333 /* Get the index corresponding to VAR in the current LOOP.  If
334    it's the first time we ask for this VAR, then we return
335    chrec_not_analyzed_yet for this VAR and return its index.  */
337 static tree *
338 find_var_scev_info (tree var)
339 {
340   struct scev_info_str *res;
341   struct scev_info_str tmp;
342   PTR *slot;
344   tmp.var = var;
345   slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
347   if (!*slot)
348     *slot = new_scev_info_str (var);
349   res = (struct scev_info_str *) *slot;
351   return &res->chrec;
352 }
354 /* Return true when CHREC contains symbolic names defined in
355    LOOP_NB.  */
357 bool
358 chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb)
359 {
360   if (chrec == NULL_TREE)
361     return false;
363   if (TREE_INVARIANT (chrec))
364     return false;
366   if (TREE_CODE (chrec) == VAR_DECL
367       || TREE_CODE (chrec) == PARM_DECL
368       || TREE_CODE (chrec) == FUNCTION_DECL
369       || TREE_CODE (chrec) == LABEL_DECL
370       || TREE_CODE (chrec) == RESULT_DECL
371       || TREE_CODE (chrec) == FIELD_DECL)
372     return true;
374   if (TREE_CODE (chrec) == SSA_NAME)
375     {
376       tree def = SSA_NAME_DEF_STMT (chrec);
377       struct loop *def_loop = loop_containing_stmt (def);
378       struct loop *loop = current_loops->parray[loop_nb];
380       if (def_loop == NULL)
381         return false;
383       if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
384         return true;
386       return false;
387     }
389   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
390     {
391     case 3:
392       if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2),
393                                                   loop_nb))
394         return true;
396     case 2:
397       if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1),
398                                                   loop_nb))
399         return true;
401     case 1:
402       if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0),
403                                                   loop_nb))
404         return true;
406     default:
407       return false;
408     }
409 }
411 /* Return true when PHI is a loop-phi-node.  */
413 static bool
414 loop_phi_node_p (tree phi)
415 {
416   /* The implementation of this function is based on the following
417      property: "all the loop-phi-nodes of a loop are contained in the
418      loop's header basic block".  */
420   return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
421 }
423 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
424    In general, in the case of multivariate evolutions we want to get
425    the evolution in different loops.  LOOP specifies the level for
426    which to get the evolution.
428    Example:
430    | for (j = 0; j < 100; j++)
431    |   {
432    |     for (k = 0; k < 100; k++)
433    |       {
434    |         i = k + j;   - Here the value of i is a function of j, k.
435    |       }
436    |      ... = i         - Here the value of i is a function of j.
437    |   }
438    | ... = i              - Here the value of i is a scalar.
440    Example:
442    | i_0 = ...
443    | loop_1 10 times
444    |   i_1 = phi (i_0, i_2)
445    |   i_2 = i_1 + 2
446    | endloop
448    This loop has the same effect as:
449    LOOP_1 has the same effect as:
451    | i_1 = i_0 + 20
453    The overall effect of the loop, "i_0 + 20" in the previous example,
454    is obtained by passing in the parameters: LOOP = 1,
455    EVOLUTION_FN = {i_0, +, 2}_1.
456 */
458 static tree
459 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
460 {
461   bool val = false;
463   if (evolution_fn == chrec_dont_know)
464     return chrec_dont_know;
466   else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
467     {
468       if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num)
469         {
470           struct loop *inner_loop =
471             current_loops->parray[CHREC_VARIABLE (evolution_fn)];
472           tree nb_iter = number_of_iterations_in_loop (inner_loop);
474           if (nb_iter == chrec_dont_know)
475             return chrec_dont_know;
476           else
477             {
478               tree res;
480               /* Number of iterations is off by one (the ssa name we
481                  analyze must be defined before the exit).  */
482               nb_iter = chrec_fold_minus (chrec_type (nb_iter),
483                                 nb_iter,
484                                 build_int_cst_type (chrec_type (nb_iter), 1));
486               /* evolution_fn is the evolution function in LOOP.  Get
487                  its value in the nb_iter-th iteration.  */
488               res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
490               /* Continue the computation until ending on a parent of LOOP.  */
491               return compute_overall_effect_of_inner_loop (loop, res);
492             }
493         }
494       else
495         return evolution_fn;
496      }
498   /* If the evolution function is an invariant, there is nothing to do.  */
499   else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
500     return evolution_fn;
502   else
503     return chrec_dont_know;
504 }
506 /* Determine whether the CHREC is always positive/negative.  If the expression
507    cannot be statically analyzed, return false, otherwise set the answer into
508    VALUE.  */
510 bool
511 chrec_is_positive (tree chrec, bool *value)
512 {
513   bool value0, value1;
514   bool value2;
515   tree end_value;
516   tree nb_iter;
518   switch (TREE_CODE (chrec))
519     {
520     case POLYNOMIAL_CHREC:
521       if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
522           || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
523         return false;
525       /* FIXME -- overflows.  */
526       if (value0 == value1)
527         {
528           *value = value0;
529           return true;
530         }
532       /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
533          and the proof consists in showing that the sign never
534          changes during the execution of the loop, from 0 to
535          loop->nb_iterations.  */
536       if (!evolution_function_is_affine_p (chrec))
537         return false;
539       nb_iter = number_of_iterations_in_loop
540         (current_loops->parray[CHREC_VARIABLE (chrec)]);
542       if (chrec_contains_undetermined (nb_iter))
543         return false;
545       nb_iter = chrec_fold_minus
546         (chrec_type (nb_iter), nb_iter,
547          build_int_cst (chrec_type (nb_iter), 1));
549 #if 0
550       /* TODO -- If the test is after the exit, we may decrease the number of
551          iterations by one.  */
552       if (after_exit)
553         nb_iter = chrec_fold_minus
554                 (chrec_type (nb_iter), nb_iter,
555                  build_int_cst (chrec_type (nb_iter), 1));
556 #endif
558       end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
560       if (!chrec_is_positive (end_value, &value2))
561         return false;
563       *value = value0;
564       return value0 == value1;
566     case INTEGER_CST:
567       *value = (tree_int_cst_sgn (chrec) == 1);
568       return true;
570     default:
571       return false;
572     }
573 }
575 /* Associate CHREC to SCALAR.  */
577 static void
578 set_scalar_evolution (tree scalar, tree chrec)
579 {
580   tree *scalar_info;
582   if (TREE_CODE (scalar) != SSA_NAME)
583     return;
585   scalar_info = find_var_scev_info (scalar);
587   if (dump_file)
588     {
589       if (dump_flags & TDF_DETAILS)
590         {
591           fprintf (dump_file, "(set_scalar_evolution \n");
592           fprintf (dump_file, "  (scalar = ");
593           print_generic_expr (dump_file, scalar, 0);
594           fprintf (dump_file, ")\n  (scalar_evolution = ");
595           print_generic_expr (dump_file, chrec, 0);
596           fprintf (dump_file, "))\n");
597         }
598       if (dump_flags & TDF_STATS)
599         nb_set_scev++;
600     }
602   *scalar_info = chrec;
603 }
605 /* Retrieve the chrec associated to SCALAR in the LOOP.  */
607 static tree
608 get_scalar_evolution (tree scalar)
609 {
610   tree res;
612   if (dump_file)
613     {
614       if (dump_flags & TDF_DETAILS)
615         {
616           fprintf (dump_file, "(get_scalar_evolution \n");
617           fprintf (dump_file, "  (scalar = ");
618           print_generic_expr (dump_file, scalar, 0);
619           fprintf (dump_file, ")\n");
620         }
621       if (dump_flags & TDF_STATS)
622         nb_get_scev++;
623     }
625   switch (TREE_CODE (scalar))
626     {
627     case SSA_NAME:
628       res = *find_var_scev_info (scalar);
629       break;
631     case REAL_CST:
632     case INTEGER_CST:
633       res = scalar;
634       break;
636     default:
637       res = chrec_not_analyzed_yet;
638       break;
639     }
641   if (dump_file && (dump_flags & TDF_DETAILS))
642     {
643       fprintf (dump_file, "  (scalar_evolution = ");
644       print_generic_expr (dump_file, res, 0);
645       fprintf (dump_file, "))\n");
646     }
648   return res;
649 }
651 /* Helper function for add_to_evolution.  Returns the evolution
652    function for an assignment of the form "a = b + c", where "a" and
653    "b" are on the strongly connected component.  CHREC_BEFORE is the
654    information that we already have collected up to this point.
655    TO_ADD is the evolution of "c".
657    When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
658    evolution the expression TO_ADD, otherwise construct an evolution
659    part for this loop.  */
661 static tree
662 add_to_evolution_1 (unsigned loop_nb,
663                     tree chrec_before,
664                     tree to_add)
665 {
666   switch (TREE_CODE (chrec_before))
667     {
668     case POLYNOMIAL_CHREC:
669       if (CHREC_VARIABLE (chrec_before) <= loop_nb)
670         {
671           unsigned var;
672           tree left, right;
673           tree type = chrec_type (chrec_before);
675           /* When there is no evolution part in this loop, build it.  */
676           if (CHREC_VARIABLE (chrec_before) < loop_nb)
677             {
678               var = loop_nb;
679               left = chrec_before;
680               right = SCALAR_FLOAT_TYPE_P (type)
681                 ? build_real (type, dconst0)
682                 : build_int_cst (type, 0);
683             }
684           else
685             {
686               var = CHREC_VARIABLE (chrec_before);
687               left = CHREC_LEFT (chrec_before);
688               right = CHREC_RIGHT (chrec_before);
689             }
691           return build_polynomial_chrec
692             (var, left, chrec_fold_plus (type, right, to_add));
693         }
694       else
695         /* Search the evolution in LOOP_NB.  */
696         return build_polynomial_chrec
697           (CHREC_VARIABLE (chrec_before),
698            add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add),
699            CHREC_RIGHT (chrec_before));
701     default:
702       /* These nodes do not depend on a loop.  */
703       if (chrec_before == chrec_dont_know)
704         return chrec_dont_know;
705       return build_polynomial_chrec (loop_nb, chrec_before, to_add);
706     }
707 }
709 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
710    of LOOP_NB.
712    Description (provided for completeness, for those who read code in
713    a plane, and for my poor 62 bytes brain that would have forgotten
714    all this in the next two or three months):
716    The algorithm of translation of programs from the SSA representation
717    into the chrecs syntax is based on a pattern matching.  After having
718    reconstructed the overall tree expression for a loop, there are only
719    two cases that can arise:
721    1. a = loop-phi (init, a + expr)
722    2. a = loop-phi (init, expr)
724    where EXPR is either a scalar constant with respect to the analyzed
725    loop (this is a degree 0 polynomial), or an expression containing
726    other loop-phi definitions (these are higher degree polynomials).
728    Examples:
730    1.
731    | init = ...
732    | loop_1
733    |   a = phi (init, a + 5)
734    | endloop
736    2.
737    | inita = ...
738    | initb = ...
739    | loop_1
740    |   a = phi (inita, 2 * b + 3)
741    |   b = phi (initb, b + 1)
742    | endloop
744    For the first case, the semantics of the SSA representation is:
746    | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
748    that is, there is a loop index "x" that determines the scalar value
749    of the variable during the loop execution.  During the first
750    iteration, the value is that of the initial condition INIT, while
751    during the subsequent iterations, it is the sum of the initial
752    condition with the sum of all the values of EXPR from the initial
753    iteration to the before last considered iteration.
755    For the second case, the semantics of the SSA program is:
757    | a (x) = init, if x = 0;
758    |         expr (x - 1), otherwise.
760    The second case corresponds to the PEELED_CHREC, whose syntax is
761    close to the syntax of a loop-phi-node:
763    | phi (init, expr)  vs.  (init, expr)_x
765    The proof of the translation algorithm for the first case is a
766    proof by structural induction based on the degree of EXPR.
768    Degree 0:
769    When EXPR is a constant with respect to the analyzed loop, or in
770    other words when EXPR is a polynomial of degree 0, the evolution of
771    the variable A in the loop is an affine function with an initial
772    condition INIT, and a step EXPR.  In order to show this, we start
773    from the semantics of the SSA representation:
775    f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
777    and since "expr (j)" is a constant with respect to "j",
779    f (x) = init + x * expr
781    Finally, based on the semantics of the pure sum chrecs, by
782    identification we get the corresponding chrecs syntax:
784    f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
785    f (x) -> {init, +, expr}_x
787    Higher degree:
788    Suppose that EXPR is a polynomial of degree N with respect to the
789    analyzed loop_x for which we have already determined that it is
790    written under the chrecs syntax:
792    | expr (x)  ->  {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
794    We start from the semantics of the SSA program:
796    | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
797    |
798    | f (x) = init + \sum_{j = 0}^{x - 1}
799    |                (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
800    |
801    | f (x) = init + \sum_{j = 0}^{x - 1}
802    |                \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
803    |
804    | f (x) = init + \sum_{k = 0}^{n - 1}
805    |                (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
806    |
807    | f (x) = init + \sum_{k = 0}^{n - 1}
808    |                (b_k * \binom{x}{k + 1})
809    |
810    | f (x) = init + b_0 * \binom{x}{1} + ...
811    |              + b_{n-1} * \binom{x}{n}
812    |
813    | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
814    |                             + b_{n-1} * \binom{x}{n}
815    |
817    And finally from the definition of the chrecs syntax, we identify:
818    | f (x)  ->  {init, +, b_0, +, ..., +, b_{n-1}}_x
820    This shows the mechanism that stands behind the add_to_evolution
821    function.  An important point is that the use of symbolic
822    parameters avoids the need of an analysis schedule.
824    Example:
826    | inita = ...
827    | initb = ...
828    | loop_1
829    |   a = phi (inita, a + 2 + b)
830    |   b = phi (initb, b + 1)
831    | endloop
833    When analyzing "a", the algorithm keeps "b" symbolically:
835    | a  ->  {inita, +, 2 + b}_1
837    Then, after instantiation, the analyzer ends on the evolution:
839    | a  ->  {inita, +, 2 + initb, +, 1}_1
841 */
843 static tree
844 add_to_evolution (unsigned loop_nb,
845                   tree chrec_before,
846                   enum tree_code code,
847                   tree to_add)
848 {
849   tree type = chrec_type (to_add);
850   tree res = NULL_TREE;
852   if (to_add == NULL_TREE)
853     return chrec_before;
855   /* TO_ADD is either a scalar, or a parameter.  TO_ADD is not
856      instantiated at this point.  */
857   if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
858     /* This should not happen.  */
859     return chrec_dont_know;
861   if (dump_file && (dump_flags & TDF_DETAILS))
862     {
863       fprintf (dump_file, "(add_to_evolution \n");
864       fprintf (dump_file, "  (loop_nb = %d)\n", loop_nb);
865       fprintf (dump_file, "  (chrec_before = ");
866       print_generic_expr (dump_file, chrec_before, 0);
867       fprintf (dump_file, ")\n  (to_add = ");
868       print_generic_expr (dump_file, to_add, 0);
869       fprintf (dump_file, ")\n");
870     }
872   if (code == MINUS_EXPR)
873     to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
874                                   ? build_real (type, dconstm1)
875                                   : build_int_cst_type (type, -1));
877   res = add_to_evolution_1 (loop_nb, chrec_before, to_add);
879   if (dump_file && (dump_flags & TDF_DETAILS))
880     {
881       fprintf (dump_file, "  (res = ");
882       print_generic_expr (dump_file, res, 0);
883       fprintf (dump_file, "))\n");
884     }
886   return res;
887 }
889 /* Helper function.  */
891 static inline tree
892 set_nb_iterations_in_loop (struct loop *loop,
893                            tree res)
894 {
895   res = chrec_fold_plus (chrec_type (res), res,
896                          build_int_cst_type (chrec_type (res), 1));
898   /* FIXME HWI: However we want to store one iteration less than the
899      count of the loop in order to be compatible with the other
900      nb_iter computations in loop-iv.  This also allows the
901      representation of nb_iters that are equal to MAX_INT.  */
902   if (TREE_CODE (res) == INTEGER_CST
903       && (TREE_INT_CST_LOW (res) == 0
904           || TREE_OVERFLOW (res)))
905     res = chrec_dont_know;
907   if (dump_file && (dump_flags & TDF_DETAILS))
908     {
909       fprintf (dump_file, "  (set_nb_iterations_in_loop = ");
910       print_generic_expr (dump_file, res, 0);
911       fprintf (dump_file, "))\n");
912     }
914   loop->nb_iterations = res;
915   return res;
916 }
918 \f
920 /* This section selects the loops that will be good candidates for the
921    scalar evolution analysis.  For the moment, greedily select all the
922    loop nests we could analyze.  */
924 /* Return true when it is possible to analyze the condition expression
925    EXPR.  */
927 static bool
928 analyzable_condition (tree expr)
929 {
930   tree condition;
932   if (TREE_CODE (expr) != COND_EXPR)
933     return false;
935   condition = TREE_OPERAND (expr, 0);
937   switch (TREE_CODE (condition))
938     {
939     case SSA_NAME:
940       return true;
942     case LT_EXPR:
943     case LE_EXPR:
944     case GT_EXPR:
945     case GE_EXPR:
946     case EQ_EXPR:
947     case NE_EXPR:
948       return true;
950     default:
951       return false;
952     }
954   return false;
955 }
957 /* For a loop with a single exit edge, return the COND_EXPR that
958    guards the exit edge.  If the expression is too difficult to
959    analyze, then give up.  */
961 tree
962 get_loop_exit_condition (struct loop *loop)
963 {
964   tree res = NULL_TREE;
965   edge exit_edge = loop->single_exit;
968   if (dump_file && (dump_flags & TDF_DETAILS))
969     fprintf (dump_file, "(get_loop_exit_condition \n  ");
971   if (exit_edge)
972     {
973       tree expr;
975       expr = last_stmt (exit_edge->src);
976       if (analyzable_condition (expr))
977         res = expr;
978     }
980   if (dump_file && (dump_flags & TDF_DETAILS))
981     {
982       print_generic_expr (dump_file, res, 0);
983       fprintf (dump_file, ")\n");
984     }
986   return res;
987 }
989 /* Recursively determine and enqueue the exit conditions for a loop.  */
991 static void
992 get_exit_conditions_rec (struct loop *loop,
993                          VEC(tree,heap) **exit_conditions)
994 {
995   if (!loop)
996     return;
998   /* Recurse on the inner loops, then on the next (sibling) loops.  */
999   get_exit_conditions_rec (loop->inner, exit_conditions);
1000   get_exit_conditions_rec (loop->next, exit_conditions);
1002   if (loop->single_exit)
1003     {
1004       tree loop_condition = get_loop_exit_condition (loop);
1006       if (loop_condition)
1007         VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
1008     }
1009 }
1011 /* Select the candidate loop nests for the analysis.  This function
1012    initializes the EXIT_CONDITIONS array.  */
1014 static void
1015 select_loops_exit_conditions (struct loops *loops,
1016                               VEC(tree,heap) **exit_conditions)
1017 {
1018   struct loop *function_body = loops->parray;
1020   get_exit_conditions_rec (function_body->inner, exit_conditions);
1021 }
1023 \f
1024 /* Depth first search algorithm.  */
1026 typedef enum t_bool {
1027   t_false,
1028   t_true,
1029   t_dont_know
1030 } t_bool;
1033 static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
1035 /* Follow the ssa edge into the right hand side RHS of an assignment.
1036    Return true if the strongly connected component has been found.  */
1038 static t_bool
1039 follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs,
1040                         tree halting_phi, tree *evolution_of_loop, int limit)
1041 {
1042   t_bool res = t_false;
1043   tree rhs0, rhs1;
1044   tree type_rhs = TREE_TYPE (rhs);
1045   tree evol;
1047   /* The RHS is one of the following cases:
1048      - an SSA_NAME,
1049      - an INTEGER_CST,
1050      - a PLUS_EXPR,
1051      - a MINUS_EXPR,
1052      - an ASSERT_EXPR,
1053      - other cases are not yet handled.  */
1054   switch (TREE_CODE (rhs))
1055     {
1056     case NOP_EXPR:
1057       /* This assignment is under the form "a_1 = (cast) rhs.  */
1058       res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
1059                                     halting_phi, evolution_of_loop, limit);
1060       *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
1061                                           *evolution_of_loop, at_stmt);
1062       break;
1064     case INTEGER_CST:
1065       /* This assignment is under the form "a_1 = 7".  */
1066       res = t_false;
1067       break;
1069     case SSA_NAME:
1070       /* This assignment is under the form: "a_1 = b_2".  */
1071       res = follow_ssa_edge
1072         (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
1073       break;
1075     case PLUS_EXPR:
1076       /* This case is under the form "rhs0 + rhs1".  */
1077       rhs0 = TREE_OPERAND (rhs, 0);
1078       rhs1 = TREE_OPERAND (rhs, 1);
1079       STRIP_TYPE_NOPS (rhs0);
1080       STRIP_TYPE_NOPS (rhs1);
1082       if (TREE_CODE (rhs0) == SSA_NAME)
1083         {
1084           if (TREE_CODE (rhs1) == SSA_NAME)
1085             {
1086               /* Match an assignment under the form:
1087                  "a = b + c".  */
1088               evol = *evolution_of_loop;
1089               res = follow_ssa_edge
1090                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1091                  &evol, limit);
1093               if (res == t_true)
1094                 *evolution_of_loop = add_to_evolution
1095                   (loop->num,
1096                    chrec_convert (type_rhs, evol, at_stmt),
1097                    PLUS_EXPR, rhs1);
1099               else if (res == t_false)
1100                 {
1101                   res = follow_ssa_edge
1102                     (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1103                      evolution_of_loop, limit);
1105                   if (res == t_true)
1106                     *evolution_of_loop = add_to_evolution
1107                       (loop->num,
1108                        chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1109                        PLUS_EXPR, rhs0);
1111                   else if (res == t_dont_know)
1112                     *evolution_of_loop = chrec_dont_know;
1113                 }
1115               else if (res == t_dont_know)
1116                 *evolution_of_loop = chrec_dont_know;
1117             }
1119           else
1120             {
1121               /* Match an assignment under the form:
1122                  "a = b + ...".  */
1123               res = follow_ssa_edge
1124                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1125                  evolution_of_loop, limit);
1126               if (res == t_true)
1127                 *evolution_of_loop = add_to_evolution
1128                   (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1129                                              at_stmt),
1130                    PLUS_EXPR, rhs1);
1132               else if (res == t_dont_know)
1133                 *evolution_of_loop = chrec_dont_know;
1134             }
1135         }
1137       else if (TREE_CODE (rhs1) == SSA_NAME)
1138         {
1139           /* Match an assignment under the form:
1140              "a = ... + c".  */
1141           res = follow_ssa_edge
1142             (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1143              evolution_of_loop, limit);
1144           if (res == t_true)
1145             *evolution_of_loop = add_to_evolution
1146               (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1147                                          at_stmt),
1148                PLUS_EXPR, rhs0);
1150           else if (res == t_dont_know)
1151             *evolution_of_loop = chrec_dont_know;
1152         }
1154       else
1155         /* Otherwise, match an assignment under the form:
1156            "a = ... + ...".  */
1157         /* And there is nothing to do.  */
1158         res = t_false;
1160       break;
1162     case MINUS_EXPR:
1163       /* This case is under the form "opnd0 = rhs0 - rhs1".  */
1164       rhs0 = TREE_OPERAND (rhs, 0);
1165       rhs1 = TREE_OPERAND (rhs, 1);
1166       STRIP_TYPE_NOPS (rhs0);
1167       STRIP_TYPE_NOPS (rhs1);
1169       if (TREE_CODE (rhs0) == SSA_NAME)
1170         {
1171           /* Match an assignment under the form:
1172              "a = b - ...".  */
1173           res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1174                                  evolution_of_loop, limit);
1175           if (res == t_true)
1176             *evolution_of_loop = add_to_evolution
1177               (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1178                MINUS_EXPR, rhs1);
1180           else if (res == t_dont_know)
1181             *evolution_of_loop = chrec_dont_know;
1182         }
1183       else
1184         /* Otherwise, match an assignment under the form:
1185            "a = ... - ...".  */
1186         /* And there is nothing to do.  */
1187         res = t_false;
1189       break;
1191     case ASSERT_EXPR:
1192       {
1193         /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1194            It must be handled as a copy assignment of the form a_1 = a_2.  */
1195         tree op0 = ASSERT_EXPR_VAR (rhs);
1196         if (TREE_CODE (op0) == SSA_NAME)
1197           res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1198                                  halting_phi, evolution_of_loop, limit);
1199         else
1200           res = t_false;
1201         break;
1202       }
1205     default:
1206       res = t_false;
1207       break;
1208     }
1210   return res;
1211 }
1213 /* Checks whether the I-th argument of a PHI comes from a backedge.  */
1215 static bool
1216 backedge_phi_arg_p (tree phi, int i)
1217 {
1218   edge e = PHI_ARG_EDGE (phi, i);
1220   /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1221      about updating it anywhere, and this should work as well most of the
1222      time.  */
1223   if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1224     return true;
1226   return false;
1227 }
1229 /* Helper function for one branch of the condition-phi-node.  Return
1230    true if the strongly connected component has been found following
1231    this path.  */
1233 static inline t_bool
1234 follow_ssa_edge_in_condition_phi_branch (int i,
1235                                          struct loop *loop,
1236                                          tree condition_phi,
1237                                          tree halting_phi,
1238                                          tree *evolution_of_branch,
1239                                          tree init_cond, int limit)
1240 {
1241   tree branch = PHI_ARG_DEF (condition_phi, i);
1242   *evolution_of_branch = chrec_dont_know;
1244   /* Do not follow back edges (they must belong to an irreducible loop, which
1245      we really do not want to worry about).  */
1246   if (backedge_phi_arg_p (condition_phi, i))
1247     return t_false;
1249   if (TREE_CODE (branch) == SSA_NAME)
1250     {
1251       *evolution_of_branch = init_cond;
1252       return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1253                               evolution_of_branch, limit);
1254     }
1256   /* This case occurs when one of the condition branches sets
1257      the variable to a constant: i.e. a phi-node like
1258      "a_2 = PHI <a_7(5), 2(6)>;".
1260      FIXME:  This case have to be refined correctly:
1261      in some cases it is possible to say something better than
1262      chrec_dont_know, for example using a wrap-around notation.  */
1263   return t_false;
1264 }
1266 /* This function merges the branches of a condition-phi-node in a
1267    loop.  */
1269 static t_bool
1270 follow_ssa_edge_in_condition_phi (struct loop *loop,
1271                                   tree condition_phi,
1272                                   tree halting_phi,
1273                                   tree *evolution_of_loop, int limit)
1274 {
1275   int i;
1276   tree init = *evolution_of_loop;
1277   tree evolution_of_branch;
1278   t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1279                                                         halting_phi,
1280                                                         &evolution_of_branch,
1281                                                         init, limit);
1282   if (res == t_false || res == t_dont_know)
1283     return res;
1285   *evolution_of_loop = evolution_of_branch;
1287   for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1288     {
1289       /* Quickly give up when the evolution of one of the branches is
1290          not known.  */
1291       if (*evolution_of_loop == chrec_dont_know)
1292         return t_true;
1294       res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1295                                                      halting_phi,
1296                                                      &evolution_of_branch,
1297                                                      init, limit);
1298       if (res == t_false || res == t_dont_know)
1299         return res;
1301       *evolution_of_loop = chrec_merge (*evolution_of_loop,
1302                                         evolution_of_branch);
1303     }
1305   return t_true;
1306 }
1308 /* Follow an SSA edge in an inner loop.  It computes the overall
1309    effect of the loop, and following the symbolic initial conditions,
1310    it follows the edges in the parent loop.  The inner loop is
1311    considered as a single statement.  */
1313 static t_bool
1314 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1315                                 tree loop_phi_node,
1316                                 tree halting_phi,
1317                                 tree *evolution_of_loop, int limit)
1318 {
1319   struct loop *loop = loop_containing_stmt (loop_phi_node);
1320   tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1322   /* Sometimes, the inner loop is too difficult to analyze, and the
1323      result of the analysis is a symbolic parameter.  */
1324   if (ev == PHI_RESULT (loop_phi_node))
1325     {
1326       t_bool res = t_false;
1327       int i;
1329       for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1330         {
1331           tree arg = PHI_ARG_DEF (loop_phi_node, i);
1332           basic_block bb;
1334           /* Follow the edges that exit the inner loop.  */
1335           bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1336           if (!flow_bb_inside_loop_p (loop, bb))
1337             res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
1338                                           arg, halting_phi,
1339                                           evolution_of_loop, limit);
1340           if (res == t_true)
1341             break;
1342         }
1344       /* If the path crosses this loop-phi, give up.  */
1345       if (res == t_true)
1346         *evolution_of_loop = chrec_dont_know;
1348       return res;
1349     }
1351   /* Otherwise, compute the overall effect of the inner loop.  */
1352   ev = compute_overall_effect_of_inner_loop (loop, ev);
1353   return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
1354                                  evolution_of_loop, limit);
1355 }
1357 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1358    path that is analyzed on the return walk.  */
1360 static t_bool
1361 follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
1362                  tree *evolution_of_loop, int limit)
1363 {
1364   struct loop *def_loop;
1366   if (TREE_CODE (def) == NOP_EXPR)
1367     return t_false;
1369   /* Give up if the path is longer than the MAX that we allow.  */
1370   if (limit++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1371     return t_dont_know;
1373   def_loop = loop_containing_stmt (def);
1375   switch (TREE_CODE (def))
1376     {
1377     case PHI_NODE:
1378       if (!loop_phi_node_p (def))
1379         /* DEF is a condition-phi-node.  Follow the branches, and
1380            record their evolutions.  Finally, merge the collected
1381            information and set the approximation to the main
1382            variable.  */
1383         return follow_ssa_edge_in_condition_phi
1384           (loop, def, halting_phi, evolution_of_loop, limit);
1386       /* When the analyzed phi is the halting_phi, the
1387          depth-first search is over: we have found a path from
1388          the halting_phi to itself in the loop.  */
1389       if (def == halting_phi)
1390         return t_true;
1392       /* Otherwise, the evolution of the HALTING_PHI depends
1393          on the evolution of another loop-phi-node, i.e. the
1394          evolution function is a higher degree polynomial.  */
1395       if (def_loop == loop)
1396         return t_false;
1398       /* Inner loop.  */
1399       if (flow_loop_nested_p (loop, def_loop))
1400         return follow_ssa_edge_inner_loop_phi
1401           (loop, def, halting_phi, evolution_of_loop, limit);
1403       /* Outer loop.  */
1404       return t_false;
1406     case MODIFY_EXPR:
1407       return follow_ssa_edge_in_rhs (loop, def,
1408                                      TREE_OPERAND (def, 1),
1409                                      halting_phi,
1410                                      evolution_of_loop, limit);
1412     default:
1413       /* At this level of abstraction, the program is just a set
1414          of MODIFY_EXPRs and PHI_NODEs.  In principle there is no
1415          other node to be handled.  */
1416       return t_false;
1417     }
1418 }
1420 \f
1422 /* Given a LOOP_PHI_NODE, this function determines the evolution
1423    function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.  */
1425 static tree
1426 analyze_evolution_in_loop (tree loop_phi_node,
1427                            tree init_cond)
1428 {
1429   int i;
1430   tree evolution_function = chrec_not_analyzed_yet;
1431   struct loop *loop = loop_containing_stmt (loop_phi_node);
1432   basic_block bb;
1434   if (dump_file && (dump_flags & TDF_DETAILS))
1435     {
1436       fprintf (dump_file, "(analyze_evolution_in_loop \n");
1437       fprintf (dump_file, "  (loop_phi_node = ");
1438       print_generic_expr (dump_file, loop_phi_node, 0);
1439       fprintf (dump_file, ")\n");
1440     }
1442   for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1443     {
1444       tree arg = PHI_ARG_DEF (loop_phi_node, i);
1445       tree ssa_chain, ev_fn;
1446       t_bool res;
1448       /* Select the edges that enter the loop body.  */
1449       bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1450       if (!flow_bb_inside_loop_p (loop, bb))
1451         continue;
1453       if (TREE_CODE (arg) == SSA_NAME)
1454         {
1455           ssa_chain = SSA_NAME_DEF_STMT (arg);
1457           /* Pass in the initial condition to the follow edge function.  */
1458           ev_fn = init_cond;
1459           res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1460         }
1461       else
1462         res = t_false;
1464       /* When it is impossible to go back on the same
1465          loop_phi_node by following the ssa edges, the
1466          evolution is represented by a peeled chrec, i.e. the
1467          first iteration, EV_FN has the value INIT_COND, then
1468          all the other iterations it has the value of ARG.
1469          For the moment, PEELED_CHREC nodes are not built.  */
1470       if (res != t_true)
1471         ev_fn = chrec_dont_know;
1473       /* When there are multiple back edges of the loop (which in fact never
1474          happens currently, but nevertheless), merge their evolutions.  */
1475       evolution_function = chrec_merge (evolution_function, ev_fn);
1476     }
1478   if (dump_file && (dump_flags & TDF_DETAILS))
1479     {
1480       fprintf (dump_file, "  (evolution_function = ");
1481       print_generic_expr (dump_file, evolution_function, 0);
1482       fprintf (dump_file, "))\n");
1483     }
1485   return evolution_function;
1486 }
1488 /* Given a loop-phi-node, return the initial conditions of the
1489    variable on entry of the loop.  When the CCP has propagated
1490    constants into the loop-phi-node, the initial condition is
1491    instantiated, otherwise the initial condition is kept symbolic.
1492    This analyzer does not analyze the evolution outside the current
1493    loop, and leaves this task to the on-demand tree reconstructor.  */
1495 static tree
1496 analyze_initial_condition (tree loop_phi_node)
1497 {
1498   int i;
1499   tree init_cond = chrec_not_analyzed_yet;
1500   struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1502   if (dump_file && (dump_flags & TDF_DETAILS))
1503     {
1504       fprintf (dump_file, "(analyze_initial_condition \n");
1505       fprintf (dump_file, "  (loop_phi_node = \n");
1506       print_generic_expr (dump_file, loop_phi_node, 0);
1507       fprintf (dump_file, ")\n");
1508     }
1510   for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1511     {
1512       tree branch = PHI_ARG_DEF (loop_phi_node, i);
1513       basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1515       /* When the branch is oriented to the loop's body, it does
1516          not contribute to the initial condition.  */
1517       if (flow_bb_inside_loop_p (loop, bb))
1518         continue;
1520       if (init_cond == chrec_not_analyzed_yet)
1521         {
1522           init_cond = branch;
1523           continue;
1524         }
1526       if (TREE_CODE (branch) == SSA_NAME)
1527         {
1528           init_cond = chrec_dont_know;
1529           break;
1530         }
1532       init_cond = chrec_merge (init_cond, branch);
1533     }
1535   /* Ooops -- a loop without an entry???  */
1536   if (init_cond == chrec_not_analyzed_yet)
1537     init_cond = chrec_dont_know;
1539   if (dump_file && (dump_flags & TDF_DETAILS))
1540     {
1541       fprintf (dump_file, "  (init_cond = ");
1542       print_generic_expr (dump_file, init_cond, 0);
1543       fprintf (dump_file, "))\n");
1544     }
1546   return init_cond;
1547 }
1549 /* Analyze the scalar evolution for LOOP_PHI_NODE.  */
1551 static tree
1552 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1553 {
1554   tree res;
1555   struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1556   tree init_cond;
1558   if (phi_loop != loop)
1559     {
1560       struct loop *subloop;
1561       tree evolution_fn = analyze_scalar_evolution
1562         (phi_loop, PHI_RESULT (loop_phi_node));
1564       /* Dive one level deeper.  */
1565       subloop = superloop_at_depth (phi_loop, loop->depth + 1);
1567       /* Interpret the subloop.  */
1568       res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1569       return res;
1570     }
1572   /* Otherwise really interpret the loop phi.  */
1573   init_cond = analyze_initial_condition (loop_phi_node);
1574   res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1576   return res;
1577 }
1579 /* This function merges the branches of a condition-phi-node,
1580    contained in the outermost loop, and whose arguments are already
1581    analyzed.  */
1583 static tree
1584 interpret_condition_phi (struct loop *loop, tree condition_phi)
1585 {
1586   int i;
1587   tree res = chrec_not_analyzed_yet;
1589   for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1590     {
1591       tree branch_chrec;
1593       if (backedge_phi_arg_p (condition_phi, i))
1594         {
1595           res = chrec_dont_know;
1596           break;
1597         }
1599       branch_chrec = analyze_scalar_evolution
1600         (loop, PHI_ARG_DEF (condition_phi, i));
1602       res = chrec_merge (res, branch_chrec);
1603     }
1605   return res;
1606 }
1608 /* Interpret the right hand side of a modify_expr OPND1.  If we didn't
1609    analyze this node before, follow the definitions until ending
1610    either on an analyzed modify_expr, or on a loop-phi-node.  On the
1611    return path, this function propagates evolutions (ala constant copy
1612    propagation).  OPND1 is not a GIMPLE expression because we could
1613    analyze the effect of an inner loop: see interpret_loop_phi.  */
1615 static tree
1616 interpret_rhs_modify_expr (struct loop *loop, tree at_stmt,
1617                            tree opnd1, tree type)
1618 {
1619   tree res, opnd10, opnd11, chrec10, chrec11;
1621   if (is_gimple_min_invariant (opnd1))
1622     return chrec_convert (type, opnd1, at_stmt);
1624   switch (TREE_CODE (opnd1))
1625     {
1626     case PLUS_EXPR:
1627       opnd10 = TREE_OPERAND (opnd1, 0);
1628       opnd11 = TREE_OPERAND (opnd1, 1);
1629       chrec10 = analyze_scalar_evolution (loop, opnd10);
1630       chrec11 = analyze_scalar_evolution (loop, opnd11);
1631       chrec10 = chrec_convert (type, chrec10, at_stmt);
1632       chrec11 = chrec_convert (type, chrec11, at_stmt);
1633       res = chrec_fold_plus (type, chrec10, chrec11);
1634       break;
1636     case MINUS_EXPR:
1637       opnd10 = TREE_OPERAND (opnd1, 0);
1638       opnd11 = TREE_OPERAND (opnd1, 1);
1639       chrec10 = analyze_scalar_evolution (loop, opnd10);
1640       chrec11 = analyze_scalar_evolution (loop, opnd11);
1641       chrec10 = chrec_convert (type, chrec10, at_stmt);
1642       chrec11 = chrec_convert (type, chrec11, at_stmt);
1643       res = chrec_fold_minus (type, chrec10, chrec11);
1644       break;
1646     case NEGATE_EXPR:
1647       opnd10 = TREE_OPERAND (opnd1, 0);
1648       chrec10 = analyze_scalar_evolution (loop, opnd10);
1649       chrec10 = chrec_convert (type, chrec10, at_stmt);
1650       res = chrec_fold_multiply (type, chrec10, SCALAR_FLOAT_TYPE_P (type)
1651                                   ? build_real (type, dconstm1)
1652                                   : build_int_cst_type (type, -1));
1653       break;
1655     case MULT_EXPR:
1656       opnd10 = TREE_OPERAND (opnd1, 0);
1657       opnd11 = TREE_OPERAND (opnd1, 1);
1658       chrec10 = analyze_scalar_evolution (loop, opnd10);
1659       chrec11 = analyze_scalar_evolution (loop, opnd11);
1660       chrec10 = chrec_convert (type, chrec10, at_stmt);
1661       chrec11 = chrec_convert (type, chrec11, at_stmt);
1662       res = chrec_fold_multiply (type, chrec10, chrec11);
1663       break;
1665     case SSA_NAME:
1666       res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
1667                            at_stmt);
1668       break;
1670     case ASSERT_EXPR:
1671       opnd10 = ASSERT_EXPR_VAR (opnd1);
1672       res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
1673                            at_stmt);
1674       break;
1676     case NOP_EXPR:
1677     case CONVERT_EXPR:
1678       opnd10 = TREE_OPERAND (opnd1, 0);
1679       chrec10 = analyze_scalar_evolution (loop, opnd10);
1680       res = chrec_convert (type, chrec10, at_stmt);
1681       break;
1683     default:
1684       res = chrec_dont_know;
1685       break;
1686     }
1688   return res;
1689 }
1691 \f
1693 /* This section contains all the entry points:
1694    - number_of_iterations_in_loop,
1695    - analyze_scalar_evolution,
1696    - instantiate_parameters.
1697 */
1699 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1700    common ancestor of DEF_LOOP and USE_LOOP.  */
1702 static tree
1703 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1704                                   struct loop *def_loop,
1705                                   tree ev)
1706 {
1707   tree res;
1708   if (def_loop == wrto_loop)
1709     return ev;
1711   def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
1712   res = compute_overall_effect_of_inner_loop (def_loop, ev);
1714   return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1715 }
1717 /* Helper recursive function.  */
1719 static tree
1720 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1721 {
1722   tree def, type = TREE_TYPE (var);
1723   basic_block bb;
1724   struct loop *def_loop;
1726   if (loop == NULL)
1727     return chrec_dont_know;
1729   if (TREE_CODE (var) != SSA_NAME)
1730     return interpret_rhs_modify_expr (loop, NULL_TREE, var, type);
1732   def = SSA_NAME_DEF_STMT (var);
1733   bb = bb_for_stmt (def);
1734   def_loop = bb ? bb->loop_father : NULL;
1736   if (bb == NULL
1737       || !flow_bb_inside_loop_p (loop, bb))
1738     {
1739       /* Keep the symbolic form.  */
1740       res = var;
1741       goto set_and_end;
1742     }
1744   if (res != chrec_not_analyzed_yet)
1745     {
1746       if (loop != bb->loop_father)
1747         res = compute_scalar_evolution_in_loop
1748             (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1750       goto set_and_end;
1751     }
1753   if (loop != def_loop)
1754     {
1755       res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1756       res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1758       goto set_and_end;
1759     }
1761   switch (TREE_CODE (def))
1762     {
1763     case MODIFY_EXPR:
1764       res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type);
1765       break;
1767     case PHI_NODE:
1768       if (loop_phi_node_p (def))
1769         res = interpret_loop_phi (loop, def);
1770       else
1771         res = interpret_condition_phi (loop, def);
1772       break;
1774     default:
1775       res = chrec_dont_know;
1776       break;
1777     }
1779  set_and_end:
1781   /* Keep the symbolic form.  */
1782   if (res == chrec_dont_know)
1783     res = var;
1785   if (loop == def_loop)
1786     set_scalar_evolution (var, res);
1788   return res;
1789 }
1791 /* Entry point for the scalar evolution analyzer.
1792    Analyzes and returns the scalar evolution of the ssa_name VAR.
1793    LOOP_NB is the identifier number of the loop in which the variable
1794    is used.
1796    Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1797    pointer to the statement that uses this variable, in order to
1798    determine the evolution function of the variable, use the following
1799    calls:
1801    unsigned loop_nb = loop_containing_stmt (stmt)->num;
1802    tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1803    tree chrec_instantiated = instantiate_parameters
1804    (loop_nb, chrec_with_symbols);
1805 */
1807 tree
1808 analyze_scalar_evolution (struct loop *loop, tree var)
1809 {
1810   tree res;
1812   if (dump_file && (dump_flags & TDF_DETAILS))
1813     {
1814       fprintf (dump_file, "(analyze_scalar_evolution \n");
1815       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
1816       fprintf (dump_file, "  (scalar = ");
1817       print_generic_expr (dump_file, var, 0);
1818       fprintf (dump_file, ")\n");
1819     }
1821   res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
1823   if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
1824     res = var;
1826   if (dump_file && (dump_flags & TDF_DETAILS))
1827     fprintf (dump_file, ")\n");
1829   return res;
1830 }
1832 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1833    WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1834    of VERSION).
1836    FOLDED_CASTS is set to true if resolve_mixers used
1837    chrec_convert_aggressive (TODO -- not really, we are way too conservative
1838    at the moment in order to keep things simple).  */
1840 static tree
1841 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1842                                   tree version, bool *folded_casts)
1843 {
1844   bool val = false;
1845   tree ev = version, tmp;
1847   if (folded_casts)
1848     *folded_casts = false;
1849   while (1)
1850     {
1851       tmp = analyze_scalar_evolution (use_loop, ev);
1852       ev = resolve_mixers (use_loop, tmp);
1854       if (folded_casts && tmp != ev)
1855         *folded_casts = true;
1857       if (use_loop == wrto_loop)
1858         return ev;
1860       /* If the value of the use changes in the inner loop, we cannot express
1861          its value in the outer loop (we might try to return interval chrec,
1862          but we do not have a user for it anyway)  */
1863       if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1864           || !val)
1865         return chrec_dont_know;
1867       use_loop = use_loop->outer;
1868     }
1869 }
1871 /* Returns instantiated value for VERSION in CACHE.  */
1873 static tree
1874 get_instantiated_value (htab_t cache, tree version)
1875 {
1876   struct scev_info_str *info, pattern;
1878   pattern.var = version;
1879   info = (struct scev_info_str *) htab_find (cache, &pattern);
1881   if (info)
1882     return info->chrec;
1883   else
1884     return NULL_TREE;
1885 }
1887 /* Sets instantiated value for VERSION to VAL in CACHE.  */
1889 static void
1890 set_instantiated_value (htab_t cache, tree version, tree val)
1891 {
1892   struct scev_info_str *info, pattern;
1893   PTR *slot;
1895   pattern.var = version;
1896   slot = htab_find_slot (cache, &pattern, INSERT);
1898   if (!*slot)
1899     *slot = new_scev_info_str (version);
1900   info = (struct scev_info_str *) *slot;
1901   info->chrec = val;
1902 }
1904 /* Return the closed_loop_phi node for VAR.  If there is none, return
1905    NULL_TREE.  */
1907 static tree
1908 loop_closed_phi_def (tree var)
1909 {
1910   struct loop *loop;
1911   edge exit;
1912   tree phi;
1914   if (var == NULL_TREE
1915       || TREE_CODE (var) != SSA_NAME)
1916     return NULL_TREE;
1918   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
1919   exit = loop->single_exit;
1920   if (!exit)
1921     return NULL_TREE;
1923   for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1924     if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
1925       return PHI_RESULT (phi);
1927   return NULL_TREE;
1928 }
1930 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1931    with respect to LOOP.  CHREC is the chrec to instantiate.  CACHE is the cache
1932    of already instantiated values.  FLAGS modify the way chrecs are
1933    instantiated.  SIZE_EXPR is used for computing the size of the expression to
1934    be instantiated, and to stop if it exceeds some limit.  */
1936 /* Values for FLAGS.  */
1937 enum
1938 {
1939   INSERT_SUPERLOOP_CHRECS = 1,  /* Loop invariants are replaced with chrecs
1940                                    in outer loops.  */
1941   FOLD_CONVERSIONS = 2          /* The conversions that may wrap in
1942                                    signed/pointer type are folded, as long as the
1943                                    value of the chrec is preserved.  */
1944 };
1946 static tree
1947 instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache,
1948                           int size_expr)
1949 {
1950   tree res, op0, op1, op2;
1951   basic_block def_bb;
1952   struct loop *def_loop;
1954   /* Give up if the expression is larger than the MAX that we allow.  */
1955   if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1956     return chrec_dont_know;
1958   if (automatically_generated_chrec_p (chrec)
1959       || is_gimple_min_invariant (chrec))
1960     return chrec;
1962   switch (TREE_CODE (chrec))
1963     {
1964     case SSA_NAME:
1965       def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
1967       /* A parameter (or loop invariant and we do not want to include
1968          evolutions in outer loops), nothing to do.  */
1969       if (!def_bb
1970           || (!(flags & INSERT_SUPERLOOP_CHRECS)
1971               && !flow_bb_inside_loop_p (loop, def_bb)))
1972         return chrec;
1974       /* We cache the value of instantiated variable to avoid exponential
1975          time complexity due to reevaluations.  We also store the convenient
1976          value in the cache in order to prevent infinite recursion -- we do
1977          not want to instantiate the SSA_NAME if it is in a mixer
1978          structure.  This is used for avoiding the instantiation of
1979          recursively defined functions, such as:
1981          | a_2 -> {0, +, 1, +, a_2}_1  */
1983       res = get_instantiated_value (cache, chrec);
1984       if (res)
1985         return res;
1987       /* Store the convenient value for chrec in the structure.  If it
1988          is defined outside of the loop, we may just leave it in symbolic
1989          form, otherwise we need to admit that we do not know its behavior
1990          inside the loop.  */
1991       res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
1992       set_instantiated_value (cache, chrec, res);
1994       /* To make things even more complicated, instantiate_parameters_1
1995          calls analyze_scalar_evolution that may call # of iterations
1996          analysis that may in turn call instantiate_parameters_1 again.
1997          To prevent the infinite recursion, keep also the bitmap of
1998          ssa names that are being instantiated globally.  */
1999       if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
2000         return res;
2002       def_loop = find_common_loop (loop, def_bb->loop_father);
2004       /* If the analysis yields a parametric chrec, instantiate the
2005          result again.  */
2006       bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2007       res = analyze_scalar_evolution (def_loop, chrec);
2009       /* Don't instantiate loop-closed-ssa phi nodes.  */
2010       if (TREE_CODE (res) == SSA_NAME
2011           && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2012               || (loop_containing_stmt (SSA_NAME_DEF_STMT (res))->depth
2013                   > def_loop->depth)))
2014         {
2015           if (res == chrec)
2016             res = loop_closed_phi_def (chrec);
2017           else
2018             res = chrec;
2020           if (res == NULL_TREE)
2021             res = chrec_dont_know;
2022         }
2024       else if (res != chrec_dont_know)
2025         res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
2027       bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2029       /* Store the correct value to the cache.  */
2030       set_instantiated_value (cache, chrec, res);
2031       return res;
2033     case POLYNOMIAL_CHREC:
2034       op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2035                                       flags, cache, size_expr);
2036       if (op0 == chrec_dont_know)
2037         return chrec_dont_know;
2039       op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2040                                       flags, cache, size_expr);
2041       if (op1 == chrec_dont_know)
2042         return chrec_dont_know;
2044       if (CHREC_LEFT (chrec) != op0
2045           || CHREC_RIGHT (chrec) != op1)
2046         chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2047       return chrec;
2049     case PLUS_EXPR:
2050       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2051                                       flags, cache, size_expr);
2052       if (op0 == chrec_dont_know)
2053         return chrec_dont_know;
2055       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2056                                       flags, cache, size_expr);
2057       if (op1 == chrec_dont_know)
2058         return chrec_dont_know;
2060       if (TREE_OPERAND (chrec, 0) != op0
2061           || TREE_OPERAND (chrec, 1) != op1)
2062         chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
2063       return chrec;
2065     case MINUS_EXPR:
2066       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2067                                       flags, cache, size_expr);
2068       if (op0 == chrec_dont_know)
2069         return chrec_dont_know;
2071       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2072                                       flags, cache, size_expr);
2073       if (op1 == chrec_dont_know)
2074         return chrec_dont_know;
2076       if (TREE_OPERAND (chrec, 0) != op0
2077           || TREE_OPERAND (chrec, 1) != op1)
2078         chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
2079       return chrec;
2081     case MULT_EXPR:
2082       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2083                                       flags, cache, size_expr);
2084       if (op0 == chrec_dont_know)
2085         return chrec_dont_know;
2087       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2088                                       flags, cache, size_expr);
2089       if (op1 == chrec_dont_know)
2090         return chrec_dont_know;
2092       if (TREE_OPERAND (chrec, 0) != op0
2093           || TREE_OPERAND (chrec, 1) != op1)
2094         chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
2095       return chrec;
2097     case NOP_EXPR:
2098     case CONVERT_EXPR:
2099     case NON_LVALUE_EXPR:
2100       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2101                                       flags, cache, size_expr);
2102       if (op0 == chrec_dont_know)
2103         return chrec_dont_know;
2105       if (flags & FOLD_CONVERSIONS)
2106         {
2107           tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
2108           if (tmp)
2109             return tmp;
2110         }
2112       if (op0 == TREE_OPERAND (chrec, 0))
2113         return chrec;
2115       return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
2117     case SCEV_NOT_KNOWN:
2118       return chrec_dont_know;
2120     case SCEV_KNOWN:
2121       return chrec_known;
2123     default:
2124       break;
2125     }
2127   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2128     {
2129     case 3:
2130       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2131                                       flags, cache, size_expr);
2132       if (op0 == chrec_dont_know)
2133         return chrec_dont_know;
2135       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2136                                       flags, cache, size_expr);
2137       if (op1 == chrec_dont_know)
2138         return chrec_dont_know;
2140       op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2141                                       flags, cache, size_expr);
2142       if (op2 == chrec_dont_know)
2143         return chrec_dont_know;
2145       if (op0 == TREE_OPERAND (chrec, 0)
2146           && op1 == TREE_OPERAND (chrec, 1)
2147           && op2 == TREE_OPERAND (chrec, 2))
2148         return chrec;
2150       return fold_build3 (TREE_CODE (chrec),
2151                           TREE_TYPE (chrec), op0, op1, op2);
2153     case 2:
2154       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2155                                       flags, cache, size_expr);
2156       if (op0 == chrec_dont_know)
2157         return chrec_dont_know;
2159       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2160                                       flags, cache, size_expr);
2161       if (op1 == chrec_dont_know)
2162         return chrec_dont_know;
2164       if (op0 == TREE_OPERAND (chrec, 0)
2165           && op1 == TREE_OPERAND (chrec, 1))
2166         return chrec;
2167       return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2169     case 1:
2170       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2171                                       flags, cache, size_expr);
2172       if (op0 == chrec_dont_know)
2173         return chrec_dont_know;
2174       if (op0 == TREE_OPERAND (chrec, 0))
2175         return chrec;
2176       return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2178     case 0:
2179       return chrec;
2181     default:
2182       break;
2183     }
2185   /* Too complicated to handle.  */
2186   return chrec_dont_know;
2187 }
2189 /* Analyze all the parameters of the chrec that were left under a
2190    symbolic form.  LOOP is the loop in which symbolic names have to
2191    be analyzed and instantiated.  */
2193 tree
2194 instantiate_parameters (struct loop *loop,
2195                         tree chrec)
2196 {
2197   tree res;
2198   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2200   if (dump_file && (dump_flags & TDF_DETAILS))
2201     {
2202       fprintf (dump_file, "(instantiate_parameters \n");
2203       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
2204       fprintf (dump_file, "  (chrec = ");
2205       print_generic_expr (dump_file, chrec, 0);
2206       fprintf (dump_file, ")\n");
2207     }
2209   res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
2210                                   0);
2212   if (dump_file && (dump_flags & TDF_DETAILS))
2213     {
2214       fprintf (dump_file, "  (res = ");
2215       print_generic_expr (dump_file, res, 0);
2216       fprintf (dump_file, "))\n");
2217     }
2219   htab_delete (cache);
2221   return res;
2222 }
2224 /* Similar to instantiate_parameters, but does not introduce the
2225    evolutions in outer loops for LOOP invariants in CHREC, and does not
2226    care about causing overflows, as long as they do not affect value
2227    of an expression.  */
2229 static tree
2230 resolve_mixers (struct loop *loop, tree chrec)
2231 {
2232   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2233   tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0);
2234   htab_delete (cache);
2235   return ret;
2236 }
2238 /* Entry point for the analysis of the number of iterations pass.
2239    This function tries to safely approximate the number of iterations
2240    the loop will run.  When this property is not decidable at compile
2241    time, the result is chrec_dont_know.  Otherwise the result is
2242    a scalar or a symbolic parameter.
2244    Example of analysis: suppose that the loop has an exit condition:
2246    "if (b > 49) goto end_loop;"
2248    and that in a previous analysis we have determined that the
2249    variable 'b' has an evolution function:
2251    "EF = {23, +, 5}_2".
2253    When we evaluate the function at the point 5, i.e. the value of the
2254    variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2255    and EF (6) = 53.  In this case the value of 'b' on exit is '53' and
2256    the loop body has been executed 6 times.  */
2258 tree
2259 number_of_iterations_in_loop (struct loop *loop)
2260 {
2261   tree res, type;
2262   edge exit;
2263   struct tree_niter_desc niter_desc;
2265   /* Determine whether the number_of_iterations_in_loop has already
2266      been computed.  */
2267   res = loop->nb_iterations;
2268   if (res)
2269     return res;
2270   res = chrec_dont_know;
2272   if (dump_file && (dump_flags & TDF_DETAILS))
2273     fprintf (dump_file, "(number_of_iterations_in_loop\n");
2275   exit = loop->single_exit;
2276   if (!exit)
2277     goto end;
2279   if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2280     goto end;
2282   type = TREE_TYPE (niter_desc.niter);
2283   if (integer_nonzerop (niter_desc.may_be_zero))
2284     res = build_int_cst (type, 0);
2285   else if (integer_zerop (niter_desc.may_be_zero))
2286     res = niter_desc.niter;
2287   else
2288     res = chrec_dont_know;
2290 end:
2291   return set_nb_iterations_in_loop (loop, res);
2292 }
2294 /* One of the drivers for testing the scalar evolutions analysis.
2295    This function computes the number of iterations for all the loops
2296    from the EXIT_CONDITIONS array.  */
2298 static void
2299 number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2300 {
2301   unsigned int i;
2302   unsigned nb_chrec_dont_know_loops = 0;
2303   unsigned nb_static_loops = 0;
2304   tree cond;
2306   for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2307     {
2308       tree res = number_of_iterations_in_loop (loop_containing_stmt (cond));
2309       if (chrec_contains_undetermined (res))
2310         nb_chrec_dont_know_loops++;
2311       else
2312         nb_static_loops++;
2313     }
2315   if (dump_file)
2316     {
2317       fprintf (dump_file, "\n(\n");
2318       fprintf (dump_file, "-----------------------------------------\n");
2319       fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2320       fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2321       fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
2322       fprintf (dump_file, "-----------------------------------------\n");
2323       fprintf (dump_file, ")\n\n");
2325       print_loop_ir (dump_file);
2326     }
2327 }
2329 \f
2331 /* Counters for the stats.  */
2333 struct chrec_stats
2334 {
2335   unsigned nb_chrecs;
2336   unsigned nb_affine;
2337   unsigned nb_affine_multivar;
2338   unsigned nb_higher_poly;
2339   unsigned nb_chrec_dont_know;
2340   unsigned nb_undetermined;
2341 };
2343 /* Reset the counters.  */
2345 static inline void
2346 reset_chrecs_counters (struct chrec_stats *stats)
2347 {
2348   stats->nb_chrecs = 0;
2349   stats->nb_affine = 0;
2350   stats->nb_affine_multivar = 0;
2351   stats->nb_higher_poly = 0;
2352   stats->nb_chrec_dont_know = 0;
2353   stats->nb_undetermined = 0;
2354 }
2356 /* Dump the contents of a CHREC_STATS structure.  */
2358 static void
2359 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2360 {
2361   fprintf (file, "\n(\n");
2362   fprintf (file, "-----------------------------------------\n");
2363   fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2364   fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2365   fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2366            stats->nb_higher_poly);
2367   fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2368   fprintf (file, "-----------------------------------------\n");
2369   fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2370   fprintf (file, "%d\twith undetermined coefficients\n",
2371            stats->nb_undetermined);
2372   fprintf (file, "-----------------------------------------\n");
2373   fprintf (file, "%d\tchrecs in the scev database\n",
2374            (int) htab_elements (scalar_evolution_info));
2375   fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2376   fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2377   fprintf (file, "-----------------------------------------\n");
2378   fprintf (file, ")\n\n");
2379 }
2381 /* Gather statistics about CHREC.  */
2383 static void
2384 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2385 {
2386   if (dump_file && (dump_flags & TDF_STATS))
2387     {
2388       fprintf (dump_file, "(classify_chrec ");
2389       print_generic_expr (dump_file, chrec, 0);
2390       fprintf (dump_file, "\n");
2391     }
2393   stats->nb_chrecs++;
2395   if (chrec == NULL_TREE)
2396     {
2397       stats->nb_undetermined++;
2398       return;
2399     }
2401   switch (TREE_CODE (chrec))
2402     {
2403     case POLYNOMIAL_CHREC:
2404       if (evolution_function_is_affine_p (chrec))
2405         {
2406           if (dump_file && (dump_flags & TDF_STATS))
2407             fprintf (dump_file, "  affine_univariate\n");
2408           stats->nb_affine++;
2409         }
2410       else if (evolution_function_is_affine_multivariate_p (chrec))
2411         {
2412           if (dump_file && (dump_flags & TDF_STATS))
2413             fprintf (dump_file, "  affine_multivariate\n");
2414           stats->nb_affine_multivar++;
2415         }
2416       else
2417         {
2418           if (dump_file && (dump_flags & TDF_STATS))
2419             fprintf (dump_file, "  higher_degree_polynomial\n");
2420           stats->nb_higher_poly++;
2421         }
2423       break;
2425     default:
2426       break;
2427     }
2429   if (chrec_contains_undetermined (chrec))
2430     {
2431       if (dump_file && (dump_flags & TDF_STATS))
2432         fprintf (dump_file, "  undetermined\n");
2433       stats->nb_undetermined++;
2434     }
2436   if (dump_file && (dump_flags & TDF_STATS))
2437     fprintf (dump_file, ")\n");
2438 }
2440 /* One of the drivers for testing the scalar evolutions analysis.
2441    This function analyzes the scalar evolution of all the scalars
2442    defined as loop phi nodes in one of the loops from the
2443    EXIT_CONDITIONS array.
2445    TODO Optimization: A loop is in canonical form if it contains only
2446    a single scalar loop phi node.  All the other scalars that have an
2447    evolution in the loop are rewritten in function of this single
2448    index.  This allows the parallelization of the loop.  */
2450 static void
2451 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2452 {
2453   unsigned int i;
2454   struct chrec_stats stats;
2455   tree cond;
2457   reset_chrecs_counters (&stats);
2459   for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2460     {
2461       struct loop *loop;
2462       basic_block bb;
2463       tree phi, chrec;
2465       loop = loop_containing_stmt (cond);
2466       bb = loop->header;
2468       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2469         if (is_gimple_reg (PHI_RESULT (phi)))
2470           {
2471             chrec = instantiate_parameters
2472               (loop,
2473                analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2475             if (dump_file && (dump_flags & TDF_STATS))
2476               gather_chrec_stats (chrec, &stats);
2477           }
2478     }
2480   if (dump_file && (dump_flags & TDF_STATS))
2481     dump_chrecs_stats (dump_file, &stats);
2482 }
2484 /* Callback for htab_traverse, gathers information on chrecs in the
2485    hashtable.  */
2487 static int
2488 gather_stats_on_scev_database_1 (void **slot, void *stats)
2489 {
2490   struct scev_info_str *entry = (struct scev_info_str *) *slot;
2492   gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2494   return 1;
2495 }
2497 /* Classify the chrecs of the whole database.  */
2499 void
2500 gather_stats_on_scev_database (void)
2501 {
2502   struct chrec_stats stats;
2504   if (!dump_file)
2505     return;
2507   reset_chrecs_counters (&stats);
2509   htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2510                  &stats);
2512   dump_chrecs_stats (dump_file, &stats);
2513 }
2515 \f
2517 /* Initializer.  */
2519 static void
2520 initialize_scalar_evolutions_analyzer (void)
2521 {
2522   /* The elements below are unique.  */
2523   if (chrec_dont_know == NULL_TREE)
2524     {
2525       chrec_not_analyzed_yet = NULL_TREE;
2526       chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2527       chrec_known = make_node (SCEV_KNOWN);
2528       TREE_TYPE (chrec_dont_know) = void_type_node;
2529       TREE_TYPE (chrec_known) = void_type_node;
2530     }
2531 }
2533 /* Initialize the analysis of scalar evolutions for LOOPS.  */
2535 void
2536 scev_initialize (struct loops *loops)
2537 {
2538   unsigned i;
2539   current_loops = loops;
2541   scalar_evolution_info = htab_create (100, hash_scev_info,
2542                                        eq_scev_info, del_scev_info);
2543   already_instantiated = BITMAP_ALLOC (NULL);
2545   initialize_scalar_evolutions_analyzer ();
2547   for (i = 1; i < loops->num; i++)
2548     if (loops->parray[i])
2549       loops->parray[i]->nb_iterations = NULL_TREE;
2550 }
2552 /* Cleans up the information cached by the scalar evolutions analysis.  */
2554 void
2555 scev_reset (void)
2556 {
2557   unsigned i;
2558   struct loop *loop;
2560   if (!scalar_evolution_info || !current_loops)
2561     return;
2563   htab_empty (scalar_evolution_info);
2564   for (i = 1; i < current_loops->num; i++)
2565     {
2566       loop = current_loops->parray[i];
2567       if (loop)
2568         loop->nb_iterations = NULL_TREE;
2569     }
2570 }
2572 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2573    its base and step in IV if possible.  If ALLOW_NONCONSTANT_STEP is true, we
2574    want step to be invariant in LOOP.  Otherwise we require it to be an
2575    integer constant.  IV->no_overflow is set to true if we are sure the iv cannot
2576    overflow (e.g.  because it is computed in signed arithmetics).  */
2578 bool
2579 simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
2580            bool allow_nonconstant_step)
2581 {
2582   basic_block bb = bb_for_stmt (stmt);
2583   tree type, ev;
2584   bool folded_casts;
2586   iv->base = NULL_TREE;
2587   iv->step = NULL_TREE;
2588   iv->no_overflow = false;
2590   type = TREE_TYPE (op);
2591   if (TREE_CODE (type) != INTEGER_TYPE
2592       && TREE_CODE (type) != POINTER_TYPE)
2593     return false;
2595   ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
2596                                          &folded_casts);
2597   if (chrec_contains_undetermined (ev))
2598     return false;
2600   if (tree_does_not_contain_chrecs (ev)
2601       && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2602     {
2603       iv->base = ev;
2604       iv->no_overflow = true;
2605       return true;
2606     }
2608   if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2609       || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2610     return false;
2612   iv->step = CHREC_RIGHT (ev);
2613   if (allow_nonconstant_step)
2614     {
2615       if (tree_contains_chrecs (iv->step, NULL)
2616           || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
2617         return false;
2618     }
2619   else if (TREE_CODE (iv->step) != INTEGER_CST)
2620     return false;
2622   iv->base = CHREC_LEFT (ev);
2623   if (tree_contains_chrecs (iv->base, NULL)
2624       || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
2625     return false;
2627   iv->no_overflow = (!folded_casts
2628                      && !flag_wrapv
2629                      && !TYPE_UNSIGNED (type));
2630   return true;
2631 }
2633 /* Runs the analysis of scalar evolutions.  */
2635 void
2636 scev_analysis (void)
2637 {
2638   VEC(tree,heap) *exit_conditions;
2640   exit_conditions = VEC_alloc (tree, heap, 37);
2641   select_loops_exit_conditions (current_loops, &exit_conditions);
2643   if (dump_file && (dump_flags & TDF_STATS))
2644     analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2646   number_of_iterations_for_all_loops (&exit_conditions);
2647   VEC_free (tree, heap, exit_conditions);
2648 }
2650 /* Finalize the scalar evolution analysis.  */
2652 void
2653 scev_finalize (void)
2654 {
2655   htab_delete (scalar_evolution_info);
2656   BITMAP_FREE (already_instantiated);
2657 }
2659 /* Returns true if EXPR looks expensive.  */
2661 static bool
2662 expression_expensive_p (tree expr)
2663 {
2664   return force_expr_to_var_cost (expr) >= target_spill_cost;
2665 }
2667 /* Replace ssa names for that scev can prove they are constant by the
2668    appropriate constants.  Also perform final value replacement in loops,
2669    in case the replacement expressions are cheap.
2671    We only consider SSA names defined by phi nodes; rest is left to the
2672    ordinary constant propagation pass.  */
2674 void
2675 scev_const_prop (void)
2676 {
2677   basic_block bb;
2678   tree name, phi, next_phi, type, ev;
2679   struct loop *loop, *ex_loop;
2680   bitmap ssa_names_to_remove = NULL;
2681   unsigned i;
2683   if (!current_loops)
2684     return;
2686   FOR_EACH_BB (bb)
2687     {
2688       loop = bb->loop_father;
2690       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2691         {
2692           name = PHI_RESULT (phi);
2694           if (!is_gimple_reg (name))
2695             continue;
2697           type = TREE_TYPE (name);
2699           if (!POINTER_TYPE_P (type)
2700               && !INTEGRAL_TYPE_P (type))
2701             continue;
2703           ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2704           if (!is_gimple_min_invariant (ev)
2705               || !may_propagate_copy (name, ev))
2706             continue;
2708           /* Replace the uses of the name.  */
2709           if (name != ev)
2710             replace_uses_by (name, ev);
2712           if (!ssa_names_to_remove)
2713             ssa_names_to_remove = BITMAP_ALLOC (NULL);
2714           bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
2715         }
2716     }
2718   /* Remove the ssa names that were replaced by constants.  We do not remove them
2719      directly in the previous cycle, since this invalidates scev cache.  */
2720   if (ssa_names_to_remove)
2721     {
2722       bitmap_iterator bi;
2723       unsigned i;
2725       EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
2726         {
2727           name = ssa_name (i);
2728           phi = SSA_NAME_DEF_STMT (name);
2730           gcc_assert (TREE_CODE (phi) == PHI_NODE);
2731           remove_phi_node (phi, NULL);
2732         }
2734       BITMAP_FREE (ssa_names_to_remove);
2735       scev_reset ();
2736     }
2738   /* Now the regular final value replacement.  */
2739   for (i = current_loops->num - 1; i > 0; i--)
2740     {
2741       edge exit;
2742       tree def, rslt, ass, niter;
2743       block_stmt_iterator bsi;
2745       loop = current_loops->parray[i];
2746       if (!loop)
2747         continue;
2749       /* If we do not know exact number of iterations of the loop, we cannot
2750          replace the final value.  */
2751       exit = loop->single_exit;
2752       if (!exit)
2753         continue;
2755       niter = number_of_iterations_in_loop (loop);
2756       if (niter == chrec_dont_know
2757           /* If computing the number of iterations is expensive, it may be
2758              better not to introduce computations involving it.  */
2759           || expression_expensive_p (niter))
2760         continue;
2762       /* Ensure that it is possible to insert new statements somewhere.  */
2763       if (!single_pred_p (exit->dest))
2764         split_loop_exit_edge (exit);
2765       tree_block_label (exit->dest);
2766       bsi = bsi_after_labels (exit->dest);
2768       ex_loop = superloop_at_depth (loop, exit->dest->loop_father->depth + 1);
2770       for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
2771         {
2772           next_phi = PHI_CHAIN (phi);
2773           rslt = PHI_RESULT (phi);
2774           def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2775           if (!is_gimple_reg (def))
2776             continue;
2778           if (!POINTER_TYPE_P (TREE_TYPE (def))
2779               && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
2780             continue;
2782           def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
2783           def = compute_overall_effect_of_inner_loop (ex_loop, def);
2784           if (!tree_does_not_contain_chrecs (def)
2785               || chrec_contains_symbols_defined_in_loop (def, ex_loop->num))
2786             continue;
2788           /* Eliminate the phi node and replace it by a computation outside
2789              the loop.  */
2790           def = unshare_expr (def);
2791           SET_PHI_RESULT (phi, NULL_TREE);
2792           remove_phi_node (phi, NULL_TREE);
2794           ass = build2 (MODIFY_EXPR, void_type_node, rslt, NULL_TREE);
2795           SSA_NAME_DEF_STMT (rslt) = ass;
2796           bsi_insert_after (&bsi, ass, BSI_NEW_STMT);
2797           def = force_gimple_operand_bsi (&bsi, def, false, NULL_TREE);
2798           TREE_OPERAND (ass, 1) = def;
2799           update_stmt (ass);
2800         }
2801     }
2802 }
About OSDN
Find Software
Develop Software