7d97d92dce2ccf0b8a21ba4ffe2f4903a8951183
1 /* Scalar evolution detector.
2    Copyright (C) 2003, 2004 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, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, 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.
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 "errors.h"
239 #include "ggc.h"
240 #include "tree.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"
255 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
256 static tree resolve_mixers (struct loop *, tree);
258 /* The cached information about a ssa name VAR, claiming that inside LOOP,
259    the value of VAR can be expressed as CHREC.  */
261 struct scev_info_str
262 {
263   tree var;
264   tree chrec;
265 };
267 /* Counters for the scev database.  */
268 static unsigned nb_set_scev = 0;
269 static unsigned nb_get_scev = 0;
271 /* The following trees are unique elements.  Thus the comparison of
272    another element to these elements should be done on the pointer to
273    these trees, and not on their value.  */
275 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE.  */
276 tree chrec_not_analyzed_yet;
278 /* Reserved to the cases where the analyzer has detected an
279    undecidable property at compile time.  */
280 tree chrec_dont_know;
282 /* When the analyzer has detected that a property will never
283    happen, then it qualifies it with chrec_known.  */
284 tree chrec_known;
288 static htab_t scalar_evolution_info;
290 \f
291 /* Constructs a new SCEV_INFO_STR structure.  */
293 static inline struct scev_info_str *
294 new_scev_info_str (tree var)
295 {
296   struct scev_info_str *res;
298   res = xmalloc (sizeof (struct scev_info_str));
299   res->var = var;
300   res->chrec = chrec_not_analyzed_yet;
302   return res;
303 }
305 /* Computes a hash function for database element ELT.  */
307 static hashval_t
308 hash_scev_info (const void *elt)
309 {
310   return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var);
311 }
313 /* Compares database elements E1 and E2.  */
315 static int
316 eq_scev_info (const void *e1, const void *e2)
317 {
318   const struct scev_info_str *elt1 = e1;
319   const struct scev_info_str *elt2 = e2;
321   return elt1->var == elt2->var;
322 }
324 /* Deletes database element E.  */
326 static void
327 del_scev_info (void *e)
328 {
329   free (e);
330 }
332 /* Get the index corresponding to VAR in the current LOOP.  If
333    it's the first time we ask for this VAR, then we return
334    chrec_not_analyzed_yet for this VAR and return its index.  */
336 static tree *
337 find_var_scev_info (tree var)
338 {
339   struct scev_info_str *res;
340   struct scev_info_str tmp;
341   PTR *slot;
343   tmp.var = var;
344   slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
346   if (!*slot)
347     *slot = new_scev_info_str (var);
348   res = *slot;
350   return &res->chrec;
351 }
353 /* Tries to express CHREC in wider type TYPE.  */
355 tree
356 count_ev_in_wider_type (tree type, tree chrec)
357 {
358   tree base, step;
359   struct loop *loop;
361   if (!evolution_function_is_affine_p (chrec))
362     return fold_convert (type, chrec);
364   base = CHREC_LEFT (chrec);
365   step = CHREC_RIGHT (chrec);
366   loop = current_loops->parray[CHREC_VARIABLE (chrec)];
368   /* TODO -- if we knew the statement at that the conversion occurs,
369      we could pass it to can_count_iv_in_wider_type and get a better
370      result.  */
371   step = can_count_iv_in_wider_type (loop, type, base, step, NULL_TREE);
372   if (!step)
373     return fold_convert (type, chrec);
374   base = chrec_convert (type, base);
376   return build_polynomial_chrec (CHREC_VARIABLE (chrec),
377                                  base, step);
378 }
380 /* Return true when CHREC contains symbolic names defined in
381    LOOP_NB.  */
383 bool
384 chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb)
385 {
386   if (chrec == NULL_TREE)
387     return false;
389   if (TREE_INVARIANT (chrec))
390     return false;
392   if (TREE_CODE (chrec) == VAR_DECL
393       || TREE_CODE (chrec) == PARM_DECL
394       || TREE_CODE (chrec) == FUNCTION_DECL
395       || TREE_CODE (chrec) == LABEL_DECL
396       || TREE_CODE (chrec) == RESULT_DECL
397       || TREE_CODE (chrec) == FIELD_DECL)
398     return true;
400   if (TREE_CODE (chrec) == SSA_NAME)
401     {
402       tree def = SSA_NAME_DEF_STMT (chrec);
403       struct loop *def_loop = loop_containing_stmt (def);
404       struct loop *loop = current_loops->parray[loop_nb];
406       if (def_loop == NULL)
407         return false;
409       if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
410         return true;
412       return false;
413     }
415   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
416     {
417     case 3:
418       if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2),
419                                                   loop_nb))
420         return true;
422     case 2:
423       if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1),
424                                                   loop_nb))
425         return true;
427     case 1:
428       if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0),
429                                                   loop_nb))
430         return true;
432     default:
433       return false;
434     }
435 }
437 /* Return true when PHI is a loop-phi-node.  */
439 static bool
440 loop_phi_node_p (tree phi)
441 {
442   /* The implementation of this function is based on the following
443      property: "all the loop-phi-nodes of a loop are contained in the
444      loop's header basic block".  */
446   return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
447 }
449 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
450    In general, in the case of multivariate evolutions we want to get
451    the evolution in different loops.  LOOP specifies the level for
452    which to get the evolution.
454    Example:
456    | for (j = 0; j < 100; j++)
457    |   {
458    |     for (k = 0; k < 100; k++)
459    |       {
460    |         i = k + j;   - Here the value of i is a function of j, k.
461    |       }
462    |      ... = i         - Here the value of i is a function of j.
463    |   }
464    | ... = i              - Here the value of i is a scalar.
466    Example:
468    | i_0 = ...
469    | loop_1 10 times
470    |   i_1 = phi (i_0, i_2)
471    |   i_2 = i_1 + 2
472    | endloop
474    This loop has the same effect as:
475    LOOP_1 has the same effect as:
477    | i_1 = i_0 + 20
479    The overall effect of the loop, "i_0 + 20" in the previous example,
480    is obtained by passing in the parameters: LOOP = 1,
481    EVOLUTION_FN = {i_0, +, 2}_1.
482 */
484 static tree
485 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
486 {
487   bool val = false;
489   if (evolution_fn == chrec_dont_know)
490     return chrec_dont_know;
492   else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
493     {
494       if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num)
495         {
496           struct loop *inner_loop =
497             current_loops->parray[CHREC_VARIABLE (evolution_fn)];
498           tree nb_iter = number_of_iterations_in_loop (inner_loop);
500           if (nb_iter == chrec_dont_know)
501             return chrec_dont_know;
502           else
503             {
504               tree res;
506               /* Number of iterations is off by one (the ssa name we
507                  analyze must be defined before the exit).  */
508               nb_iter = chrec_fold_minus (chrec_type (nb_iter),
509                                 nb_iter,
510                                 build_int_cst_type (chrec_type (nb_iter), 1));
512               /* evolution_fn is the evolution function in LOOP.  Get
513                  its value in the nb_iter-th iteration.  */
514               res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
516               /* Continue the computation until ending on a parent of LOOP.  */
517               return compute_overall_effect_of_inner_loop (loop, res);
518             }
519         }
520       else
521         return evolution_fn;
522      }
524   /* If the evolution function is an invariant, there is nothing to do.  */
525   else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
526     return evolution_fn;
528   else
529     return chrec_dont_know;
530 }
532 /* Determine whether the CHREC is always positive/negative.  If the expression
533    cannot be statically analyzed, return false, otherwise set the answer into
534    VALUE.  */
536 bool
537 chrec_is_positive (tree chrec, bool *value)
538 {
539   bool value0, value1;
540   bool value2;
541   tree end_value;
542   tree nb_iter;
544   switch (TREE_CODE (chrec))
545     {
546     case POLYNOMIAL_CHREC:
547       if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
548           || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
549         return false;
551       /* FIXME -- overflows.  */
552       if (value0 == value1)
553         {
554           *value = value0;
555           return true;
556         }
558       /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
559          and the proof consists in showing that the sign never
560          changes during the execution of the loop, from 0 to
561          loop->nb_iterations.  */
562       if (!evolution_function_is_affine_p (chrec))
563         return false;
565       nb_iter = number_of_iterations_in_loop
566         (current_loops->parray[CHREC_VARIABLE (chrec)]);
568       if (chrec_contains_undetermined (nb_iter))
569         return false;
571       nb_iter = chrec_fold_minus
572         (chrec_type (nb_iter), nb_iter,
573          build_int_cst (chrec_type (nb_iter), 1));
575 #if 0
576       /* TODO -- If the test is after the exit, we may decrease the number of
577          iterations by one.  */
578       if (after_exit)
579         nb_iter = chrec_fold_minus
580                 (chrec_type (nb_iter), nb_iter,
581                  build_int_cst (chrec_type (nb_iter), 1));
582 #endif
584       end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
586       if (!chrec_is_positive (end_value, &value2))
587         return false;
589       *value = value0;
590       return value0 == value1;
592     case INTEGER_CST:
593       *value = (tree_int_cst_sgn (chrec) == 1);
594       return true;
596     default:
597       return false;
598     }
599 }
601 /* Associate CHREC to SCALAR.  */
603 static void
604 set_scalar_evolution (tree scalar, tree chrec)
605 {
606   tree *scalar_info;
608   if (TREE_CODE (scalar) != SSA_NAME)
609     return;
611   scalar_info = find_var_scev_info (scalar);
613   if (dump_file)
614     {
615       if (dump_flags & TDF_DETAILS)
616         {
617           fprintf (dump_file, "(set_scalar_evolution \n");
618           fprintf (dump_file, "  (scalar = ");
619           print_generic_expr (dump_file, scalar, 0);
620           fprintf (dump_file, ")\n  (scalar_evolution = ");
621           print_generic_expr (dump_file, chrec, 0);
622           fprintf (dump_file, "))\n");
623         }
624       if (dump_flags & TDF_STATS)
625         nb_set_scev++;
626     }
628   *scalar_info = chrec;
629 }
631 /* Retrieve the chrec associated to SCALAR in the LOOP.  */
633 static tree
634 get_scalar_evolution (tree scalar)
635 {
636   tree res;
638   if (dump_file)
639     {
640       if (dump_flags & TDF_DETAILS)
641         {
642           fprintf (dump_file, "(get_scalar_evolution \n");
643           fprintf (dump_file, "  (scalar = ");
644           print_generic_expr (dump_file, scalar, 0);
645           fprintf (dump_file, ")\n");
646         }
647       if (dump_flags & TDF_STATS)
648         nb_get_scev++;
649     }
651   switch (TREE_CODE (scalar))
652     {
653     case SSA_NAME:
654       res = *find_var_scev_info (scalar);
655       break;
657     case REAL_CST:
658     case INTEGER_CST:
659       res = scalar;
660       break;
662     default:
663       res = chrec_not_analyzed_yet;
664       break;
665     }
667   if (dump_file && (dump_flags & TDF_DETAILS))
668     {
669       fprintf (dump_file, "  (scalar_evolution = ");
670       print_generic_expr (dump_file, res, 0);
671       fprintf (dump_file, "))\n");
672     }
674   return res;
675 }
677 /* Helper function for add_to_evolution.  Returns the evolution
678    function for an assignment of the form "a = b + c", where "a" and
679    "b" are on the strongly connected component.  CHREC_BEFORE is the
680    information that we already have collected up to this point.
681    TO_ADD is the evolution of "c".
683    When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
684    evolution the expression TO_ADD, otherwise construct an evolution
685    part for this loop.  */
687 static tree
689                     tree chrec_before,
691 {
692   switch (TREE_CODE (chrec_before))
693     {
694     case POLYNOMIAL_CHREC:
695       if (CHREC_VARIABLE (chrec_before) <= loop_nb)
696         {
697           unsigned var;
698           tree left, right;
699           tree type = chrec_type (chrec_before);
701           /* When there is no evolution part in this loop, build it.  */
702           if (CHREC_VARIABLE (chrec_before) < loop_nb)
703             {
704               var = loop_nb;
705               left = chrec_before;
706               right = build_int_cst (type, 0);
707             }
708           else
709             {
710               var = CHREC_VARIABLE (chrec_before);
711               left = CHREC_LEFT (chrec_before);
712               right = CHREC_RIGHT (chrec_before);
713             }
715           return build_polynomial_chrec
716             (var, left, chrec_fold_plus (type, right, to_add));
717         }
718       else
719         /* Search the evolution in LOOP_NB.  */
720         return build_polynomial_chrec
721           (CHREC_VARIABLE (chrec_before),
723            CHREC_RIGHT (chrec_before));
725     default:
726       /* These nodes do not depend on a loop.  */
727       if (chrec_before == chrec_dont_know)
728         return chrec_dont_know;
729       return build_polynomial_chrec (loop_nb, chrec_before, to_add);
730     }
731 }
733 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
734    of LOOP_NB.
736    Description (provided for completeness, for those who read code in
737    a plane, and for my poor 62 bytes brain that would have forgotten
738    all this in the next two or three months):
740    The algorithm of translation of programs from the SSA representation
741    into the chrecs syntax is based on a pattern matching.  After having
742    reconstructed the overall tree expression for a loop, there are only
743    two cases that can arise:
745    1. a = loop-phi (init, a + expr)
746    2. a = loop-phi (init, expr)
748    where EXPR is either a scalar constant with respect to the analyzed
749    loop (this is a degree 0 polynomial), or an expression containing
750    other loop-phi definitions (these are higher degree polynomials).
752    Examples:
754    1.
755    | init = ...
756    | loop_1
757    |   a = phi (init, a + 5)
758    | endloop
760    2.
761    | inita = ...
762    | initb = ...
763    | loop_1
764    |   a = phi (inita, 2 * b + 3)
765    |   b = phi (initb, b + 1)
766    | endloop
768    For the first case, the semantics of the SSA representation is:
770    | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
772    that is, there is a loop index "x" that determines the scalar value
773    of the variable during the loop execution.  During the first
774    iteration, the value is that of the initial condition INIT, while
775    during the subsequent iterations, it is the sum of the initial
776    condition with the sum of all the values of EXPR from the initial
777    iteration to the before last considered iteration.
779    For the second case, the semantics of the SSA program is:
781    | a (x) = init, if x = 0;
782    |         expr (x - 1), otherwise.
784    The second case corresponds to the PEELED_CHREC, whose syntax is
785    close to the syntax of a loop-phi-node:
787    | phi (init, expr)  vs.  (init, expr)_x
789    The proof of the translation algorithm for the first case is a
790    proof by structural induction based on the degree of EXPR.
792    Degree 0:
793    When EXPR is a constant with respect to the analyzed loop, or in
794    other words when EXPR is a polynomial of degree 0, the evolution of
795    the variable A in the loop is an affine function with an initial
796    condition INIT, and a step EXPR.  In order to show this, we start
797    from the semantics of the SSA representation:
799    f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
801    and since "expr (j)" is a constant with respect to "j",
803    f (x) = init + x * expr
805    Finally, based on the semantics of the pure sum chrecs, by
806    identification we get the corresponding chrecs syntax:
808    f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
809    f (x) -> {init, +, expr}_x
811    Higher degree:
812    Suppose that EXPR is a polynomial of degree N with respect to the
813    analyzed loop_x for which we have already determined that it is
814    written under the chrecs syntax:
816    | expr (x)  ->  {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
818    We start from the semantics of the SSA program:
820    | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
821    |
822    | f (x) = init + \sum_{j = 0}^{x - 1}
823    |                (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
824    |
825    | f (x) = init + \sum_{j = 0}^{x - 1}
826    |                \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
827    |
828    | f (x) = init + \sum_{k = 0}^{n - 1}
829    |                (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
830    |
831    | f (x) = init + \sum_{k = 0}^{n - 1}
832    |                (b_k * \binom{x}{k + 1})
833    |
834    | f (x) = init + b_0 * \binom{x}{1} + ...
835    |              + b_{n-1} * \binom{x}{n}
836    |
837    | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
838    |                             + b_{n-1} * \binom{x}{n}
839    |
841    And finally from the definition of the chrecs syntax, we identify:
842    | f (x)  ->  {init, +, b_0, +, ..., +, b_{n-1}}_x
844    This shows the mechanism that stands behind the add_to_evolution
845    function.  An important point is that the use of symbolic
846    parameters avoids the need of an analysis schedule.
848    Example:
850    | inita = ...
851    | initb = ...
852    | loop_1
853    |   a = phi (inita, a + 2 + b)
854    |   b = phi (initb, b + 1)
855    | endloop
857    When analyzing "a", the algorithm keeps "b" symbolically:
859    | a  ->  {inita, +, 2 + b}_1
861    Then, after instantiation, the analyzer ends on the evolution:
863    | a  ->  {inita, +, 2 + initb, +, 1}_1
865 */
867 static tree
869                   tree chrec_before,
870                   enum tree_code code,
872 {
873   tree type = chrec_type (to_add);
874   tree res = NULL_TREE;
877     return chrec_before;
879   /* TO_ADD is either a scalar, or a parameter.  TO_ADD is not
880      instantiated at this point.  */
881   if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
882     /* This should not happen.  */
883     return chrec_dont_know;
885   if (dump_file && (dump_flags & TDF_DETAILS))
886     {
888       fprintf (dump_file, "  (loop_nb = %d)\n", loop_nb);
889       fprintf (dump_file, "  (chrec_before = ");
890       print_generic_expr (dump_file, chrec_before, 0);
891       fprintf (dump_file, ")\n  (to_add = ");
893       fprintf (dump_file, ")\n");
894     }
896   if (code == MINUS_EXPR)
898                                   build_int_cst_type (type, -1));
902   if (dump_file && (dump_flags & TDF_DETAILS))
903     {
904       fprintf (dump_file, "  (res = ");
905       print_generic_expr (dump_file, res, 0);
906       fprintf (dump_file, "))\n");
907     }
909   return res;
910 }
912 /* Helper function.  */
914 static inline tree
915 set_nb_iterations_in_loop (struct loop *loop,
916                            tree res)
917 {
918   res = chrec_fold_plus (chrec_type (res), res,
919                          build_int_cst_type (chrec_type (res), 1));
921   /* FIXME HWI: However we want to store one iteration less than the
922      count of the loop in order to be compatible with the other
923      nb_iter computations in loop-iv.  This also allows the
924      representation of nb_iters that are equal to MAX_INT.  */
925   if ((TREE_CODE (res) == INTEGER_CST && TREE_INT_CST_LOW (res) == 0)
926       || TREE_OVERFLOW (res))
927     res = chrec_dont_know;
929   if (dump_file && (dump_flags & TDF_DETAILS))
930     {
931       fprintf (dump_file, "  (set_nb_iterations_in_loop = ");
932       print_generic_expr (dump_file, res, 0);
933       fprintf (dump_file, "))\n");
934     }
936   loop->nb_iterations = res;
937   return res;
938 }
940 \f
942 /* This section selects the loops that will be good candidates for the
943    scalar evolution analysis.  For the moment, greedily select all the
944    loop nests we could analyze.  */
946 /* Return true when it is possible to analyze the condition expression
947    EXPR.  */
949 static bool
950 analyzable_condition (tree expr)
951 {
952   tree condition;
954   if (TREE_CODE (expr) != COND_EXPR)
955     return false;
957   condition = TREE_OPERAND (expr, 0);
959   switch (TREE_CODE (condition))
960     {
961     case SSA_NAME:
962       /* Volatile expressions are not analyzable.  */
963       if (TREE_THIS_VOLATILE (SSA_NAME_VAR (condition)))
964         return false;
965       return true;
967     case LT_EXPR:
968     case LE_EXPR:
969     case GT_EXPR:
970     case GE_EXPR:
971     case EQ_EXPR:
972     case NE_EXPR:
973       {
974         tree opnd0, opnd1;
976         opnd0 = TREE_OPERAND (condition, 0);
977         opnd1 = TREE_OPERAND (condition, 1);
979         if (TREE_CODE (opnd0) == SSA_NAME
980             && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd0)))
981           return false;
983         if (TREE_CODE (opnd1) == SSA_NAME
984             && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd1)))
985           return false;
987         return true;
988       }
990     default:
991       return false;
992     }
994   return false;
995 }
997 /* For a loop with a single exit edge, return the COND_EXPR that
998    guards the exit edge.  If the expression is too difficult to
999    analyze, then give up.  */
1001 tree
1002 get_loop_exit_condition (struct loop *loop)
1003 {
1004   tree res = NULL_TREE;
1005   edge exit_edge = loop->single_exit;
1008   if (dump_file && (dump_flags & TDF_DETAILS))
1009     fprintf (dump_file, "(get_loop_exit_condition \n  ");
1011   if (exit_edge)
1012     {
1013       tree expr;
1015       expr = last_stmt (exit_edge->src);
1016       if (analyzable_condition (expr))
1017         res = expr;
1018     }
1020   if (dump_file && (dump_flags & TDF_DETAILS))
1021     {
1022       print_generic_expr (dump_file, res, 0);
1023       fprintf (dump_file, ")\n");
1024     }
1026   return res;
1027 }
1029 /* Recursively determine and enqueue the exit conditions for a loop.  */
1031 static void
1032 get_exit_conditions_rec (struct loop *loop,
1033                          varray_type *exit_conditions)
1034 {
1035   if (!loop)
1036     return;
1038   /* Recurse on the inner loops, then on the next (sibling) loops.  */
1039   get_exit_conditions_rec (loop->inner, exit_conditions);
1040   get_exit_conditions_rec (loop->next, exit_conditions);
1042   if (loop->single_exit)
1043     {
1044       tree loop_condition = get_loop_exit_condition (loop);
1046       if (loop_condition)
1047         VARRAY_PUSH_TREE (*exit_conditions, loop_condition);
1048     }
1049 }
1051 /* Select the candidate loop nests for the analysis.  This function
1052    initializes the EXIT_CONDITIONS array.  */
1054 static void
1055 select_loops_exit_conditions (struct loops *loops,
1056                               varray_type *exit_conditions)
1057 {
1058   struct loop *function_body = loops->parray;
1060   get_exit_conditions_rec (function_body->inner, exit_conditions);
1061 }
1063 \f
1064 /* Depth first search algorithm.  */
1066 static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
1068 /* Follow the ssa edge into the right hand side RHS of an assignment.
1069    Return true if the strongly connected component has been found.  */
1071 static bool
1072 follow_ssa_edge_in_rhs (struct loop *loop,
1073                         tree rhs,
1074                         tree halting_phi,
1075                         tree *evolution_of_loop)
1076 {
1077   bool res = false;
1078   tree rhs0, rhs1;
1079   tree type_rhs = TREE_TYPE (rhs);
1081   /* The RHS is one of the following cases:
1082      - an SSA_NAME,
1083      - an INTEGER_CST,
1084      - a PLUS_EXPR,
1085      - a MINUS_EXPR,
1086      - other cases are not yet handled.
1087   */
1088   switch (TREE_CODE (rhs))
1089     {
1090     case NOP_EXPR:
1091       /* This assignment is under the form "a_1 = (cast) rhs.  */
1092       res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi,
1093                                     evolution_of_loop);
1094       *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop);
1095       break;
1097     case INTEGER_CST:
1098       /* This assignment is under the form "a_1 = 7".  */
1099       res = false;
1100       break;
1102     case SSA_NAME:
1103       /* This assignment is under the form: "a_1 = b_2".  */
1104       res = follow_ssa_edge
1105         (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop);
1106       break;
1108     case PLUS_EXPR:
1109       /* This case is under the form "rhs0 + rhs1".  */
1110       rhs0 = TREE_OPERAND (rhs, 0);
1111       rhs1 = TREE_OPERAND (rhs, 1);
1112       STRIP_TYPE_NOPS (rhs0);
1113       STRIP_TYPE_NOPS (rhs1);
1115       if (TREE_CODE (rhs0) == SSA_NAME)
1116         {
1117           if (TREE_CODE (rhs1) == SSA_NAME)
1118             {
1119               /* Match an assignment under the form:
1120                  "a = b + c".  */
1121               res = follow_ssa_edge
1122                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1123                  evolution_of_loop);
1125               if (res)
1127                   (loop->num,
1128                    chrec_convert (type_rhs, *evolution_of_loop),
1129                    PLUS_EXPR, rhs1);
1131               else
1132                 {
1133                   res = follow_ssa_edge
1134                     (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1135                      evolution_of_loop);
1137                   if (res)
1139                       (loop->num,
1140                        chrec_convert (type_rhs, *evolution_of_loop),
1141                        PLUS_EXPR, rhs0);
1142                 }
1143             }
1145           else
1146             {
1147               /* Match an assignment under the form:
1148                  "a = b + ...".  */
1149               res = follow_ssa_edge
1150                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1151                  evolution_of_loop);
1152               if (res)
1154                   (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
1155                    PLUS_EXPR, rhs1);
1156             }
1157         }
1159       else if (TREE_CODE (rhs1) == SSA_NAME)
1160         {
1161           /* Match an assignment under the form:
1162              "a = ... + c".  */
1163           res = follow_ssa_edge
1164             (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1165              evolution_of_loop);
1166           if (res)
1168               (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
1169                PLUS_EXPR, rhs0);
1170         }
1172       else
1173         /* Otherwise, match an assignment under the form:
1174            "a = ... + ...".  */
1175         /* And there is nothing to do.  */
1176         res = false;
1178       break;
1180     case MINUS_EXPR:
1181       /* This case is under the form "opnd0 = rhs0 - rhs1".  */
1182       rhs0 = TREE_OPERAND (rhs, 0);
1183       rhs1 = TREE_OPERAND (rhs, 1);
1184       STRIP_TYPE_NOPS (rhs0);
1185       STRIP_TYPE_NOPS (rhs1);
1187       if (TREE_CODE (rhs0) == SSA_NAME)
1188         {
1189           if (TREE_CODE (rhs1) == SSA_NAME)
1190             {
1191               /* Match an assignment under the form:
1192                  "a = b - c".  */
1193               res = follow_ssa_edge
1194                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1195                  evolution_of_loop);
1197               if (res)
1199                   (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
1200                    MINUS_EXPR, rhs1);
1202               else
1203                 {
1204                   res = follow_ssa_edge
1205                     (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1206                      evolution_of_loop);
1208                   if (res)
1210                       (loop->num,
1211                        chrec_fold_multiply (type_rhs,
1212                                             *evolution_of_loop,
1213                                             build_int_cst_type (type_rhs, -1)),
1214                        PLUS_EXPR, rhs0);
1215                 }
1216             }
1218           else
1219             {
1220               /* Match an assignment under the form:
1221                  "a = b - ...".  */
1222               res = follow_ssa_edge
1223                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1224                  evolution_of_loop);
1225               if (res)
1227                   (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
1228                    MINUS_EXPR, rhs1);
1229             }
1230         }
1232       else if (TREE_CODE (rhs1) == SSA_NAME)
1233         {
1234           /* Match an assignment under the form:
1235              "a = ... - c".  */
1236           res = follow_ssa_edge
1237             (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1238              evolution_of_loop);
1239           if (res)
1241               (loop->num,
1242                chrec_fold_multiply (type_rhs,
1243                                     *evolution_of_loop,
1244                                     build_int_cst_type (type_rhs, -1)),
1245                PLUS_EXPR, rhs0);
1246         }
1248       else
1249         /* Otherwise, match an assignment under the form:
1250            "a = ... - ...".  */
1251         /* And there is nothing to do.  */
1252         res = false;
1254       break;
1256     case MULT_EXPR:
1257       /* This case is under the form "opnd0 = rhs0 * rhs1".  */
1258       rhs0 = TREE_OPERAND (rhs, 0);
1259       rhs1 = TREE_OPERAND (rhs, 1);
1260       STRIP_TYPE_NOPS (rhs0);
1261       STRIP_TYPE_NOPS (rhs1);
1263       if (TREE_CODE (rhs0) == SSA_NAME)
1264         {
1265           if (TREE_CODE (rhs1) == SSA_NAME)
1266             {
1267               /* Match an assignment under the form:
1268                  "a = b * c".  */
1269               res = follow_ssa_edge
1270                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1271                  evolution_of_loop);
1273               if (res)
1274                 *evolution_of_loop = chrec_dont_know;
1276               else
1277                 {
1278                   res = follow_ssa_edge
1279                     (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1280                      evolution_of_loop);
1282                   if (res)
1283                     *evolution_of_loop = chrec_dont_know;
1284                 }
1285             }
1287           else
1288             {
1289               /* Match an assignment under the form:
1290                  "a = b * ...".  */
1291               res = follow_ssa_edge
1292                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1293                  evolution_of_loop);
1294               if (res)
1295                 *evolution_of_loop = chrec_dont_know;
1296             }
1297         }
1299       else if (TREE_CODE (rhs1) == SSA_NAME)
1300         {
1301           /* Match an assignment under the form:
1302              "a = ... * c".  */
1303           res = follow_ssa_edge
1304             (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1305              evolution_of_loop);
1306           if (res)
1307             *evolution_of_loop = chrec_dont_know;
1308         }
1310       else
1311         /* Otherwise, match an assignment under the form:
1312            "a = ... * ...".  */
1313         /* And there is nothing to do.  */
1314         res = false;
1316       break;
1318     default:
1319       res = false;
1320       break;
1321     }
1323   return res;
1324 }
1326 /* Checks whether the I-th argument of a PHI comes from a backedge.  */
1328 static bool
1329 backedge_phi_arg_p (tree phi, int i)
1330 {
1331   edge e = PHI_ARG_EDGE (phi, i);
1333   /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1334      about updating it anywhere, and this should work as well most of the
1335      time.  */
1336   if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1337     return true;
1339   return false;
1340 }
1342 /* Helper function for one branch of the condition-phi-node.  Return
1343    true if the strongly connected component has been found following
1344    this path.  */
1346 static inline bool
1347 follow_ssa_edge_in_condition_phi_branch (int i,
1348                                          struct loop *loop,
1349                                          tree condition_phi,
1350                                          tree halting_phi,
1351                                          tree *evolution_of_branch,
1352                                          tree init_cond)
1353 {
1354   tree branch = PHI_ARG_DEF (condition_phi, i);
1355   *evolution_of_branch = chrec_dont_know;
1357   /* Do not follow back edges (they must belong to an irreducible loop, which
1358      we really do not want to worry about).  */
1359   if (backedge_phi_arg_p (condition_phi, i))
1360     return false;
1362   if (TREE_CODE (branch) == SSA_NAME)
1363     {
1364       *evolution_of_branch = init_cond;
1365       return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1366                               evolution_of_branch);
1367     }
1369   /* This case occurs when one of the condition branches sets
1370      the variable to a constant: i.e. a phi-node like
1371      "a_2 = PHI <a_7(5), 2(6)>;".
1373      FIXME:  This case have to be refined correctly:
1374      in some cases it is possible to say something better than
1375      chrec_dont_know, for example using a wrap-around notation.  */
1376   return false;
1377 }
1379 /* This function merges the branches of a condition-phi-node in a
1380    loop.  */
1382 static bool
1383 follow_ssa_edge_in_condition_phi (struct loop *loop,
1384                                   tree condition_phi,
1385                                   tree halting_phi,
1386                                   tree *evolution_of_loop)
1387 {
1388   int i;
1389   tree init = *evolution_of_loop;
1390   tree evolution_of_branch;
1392   if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1393                                                 halting_phi,
1394                                                 &evolution_of_branch,
1395                                                 init))
1396     return false;
1397   *evolution_of_loop = evolution_of_branch;
1399   for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1400     {
1401       if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1402                                                     halting_phi,
1403                                                     &evolution_of_branch,
1404                                                     init))
1405         return false;
1407       *evolution_of_loop = chrec_merge (*evolution_of_loop,
1408                                         evolution_of_branch);
1409     }
1411   return true;
1412 }
1414 /* Follow an SSA edge in an inner loop.  It computes the overall
1415    effect of the loop, and following the symbolic initial conditions,
1416    it follows the edges in the parent loop.  The inner loop is
1417    considered as a single statement.  */
1419 static bool
1420 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1421                                 tree loop_phi_node,
1422                                 tree halting_phi,
1423                                 tree *evolution_of_loop)
1424 {
1425   struct loop *loop = loop_containing_stmt (loop_phi_node);
1426   tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1428   /* Sometimes, the inner loop is too difficult to analyze, and the
1429      result of the analysis is a symbolic parameter.  */
1430   if (ev == PHI_RESULT (loop_phi_node))
1431     {
1432       bool res = false;
1433       int i;
1435       for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1436         {
1437           tree arg = PHI_ARG_DEF (loop_phi_node, i);
1438           basic_block bb;
1440           /* Follow the edges that exit the inner loop.  */
1441           bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1442           if (!flow_bb_inside_loop_p (loop, bb))
1443             res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi,
1444                                                  evolution_of_loop);
1445         }
1447       /* If the path crosses this loop-phi, give up.  */
1448       if (res == true)
1449         *evolution_of_loop = chrec_dont_know;
1451       return res;
1452     }
1454   /* Otherwise, compute the overall effect of the inner loop.  */
1455   ev = compute_overall_effect_of_inner_loop (loop, ev);
1456   return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi,
1457                                  evolution_of_loop);
1458 }
1460 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1461    path that is analyzed on the return walk.  */
1463 static bool
1464 follow_ssa_edge (struct loop *loop,
1465                  tree def,
1466                  tree halting_phi,
1467                  tree *evolution_of_loop)
1468 {
1469   struct loop *def_loop;
1471   if (TREE_CODE (def) == NOP_EXPR)
1472     return false;
1474   def_loop = loop_containing_stmt (def);
1476   switch (TREE_CODE (def))
1477     {
1478     case PHI_NODE:
1479       if (!loop_phi_node_p (def))
1480         /* DEF is a condition-phi-node.  Follow the branches, and
1481            record their evolutions.  Finally, merge the collected
1482            information and set the approximation to the main
1483            variable.  */
1484         return follow_ssa_edge_in_condition_phi
1485           (loop, def, halting_phi, evolution_of_loop);
1487       /* When the analyzed phi is the halting_phi, the
1488          depth-first search is over: we have found a path from
1489          the halting_phi to itself in the loop.  */
1490       if (def == halting_phi)
1491         return true;
1493       /* Otherwise, the evolution of the HALTING_PHI depends
1494          on the evolution of another loop-phi-node, i.e. the
1495          evolution function is a higher degree polynomial.  */
1496       if (def_loop == loop)
1497         return false;
1499       /* Inner loop.  */
1500       if (flow_loop_nested_p (loop, def_loop))
1501         return follow_ssa_edge_inner_loop_phi
1502           (loop, def, halting_phi, evolution_of_loop);
1504       /* Outer loop.  */
1505       return false;
1507     case MODIFY_EXPR:
1508       return follow_ssa_edge_in_rhs (loop,
1509                                      TREE_OPERAND (def, 1),
1510                                      halting_phi,
1511                                      evolution_of_loop);
1513     default:
1514       /* At this level of abstraction, the program is just a set
1515          of MODIFY_EXPRs and PHI_NODEs.  In principle there is no
1516          other node to be handled.  */
1517       return false;
1518     }
1519 }
1521 \f
1523 /* Given a LOOP_PHI_NODE, this function determines the evolution
1524    function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.  */
1526 static tree
1527 analyze_evolution_in_loop (tree loop_phi_node,
1528                            tree init_cond)
1529 {
1530   int i;
1531   tree evolution_function = chrec_not_analyzed_yet;
1532   struct loop *loop = loop_containing_stmt (loop_phi_node);
1533   basic_block bb;
1535   if (dump_file && (dump_flags & TDF_DETAILS))
1536     {
1537       fprintf (dump_file, "(analyze_evolution_in_loop \n");
1538       fprintf (dump_file, "  (loop_phi_node = ");
1539       print_generic_expr (dump_file, loop_phi_node, 0);
1540       fprintf (dump_file, ")\n");
1541     }
1543   for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1544     {
1545       tree arg = PHI_ARG_DEF (loop_phi_node, i);
1546       tree ssa_chain, ev_fn;
1547       bool res;
1549       /* Select the edges that enter the loop body.  */
1550       bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1551       if (!flow_bb_inside_loop_p (loop, bb))
1552         continue;
1554       if (TREE_CODE (arg) == SSA_NAME)
1555         {
1556           ssa_chain = SSA_NAME_DEF_STMT (arg);
1558           /* Pass in the initial condition to the follow edge function.  */
1559           ev_fn = init_cond;
1560           res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn);
1561         }
1562       else
1563         res = false;
1565       /* When it is impossible to go back on the same
1566          loop_phi_node by following the ssa edges, the
1567          evolution is represented by a peeled chrec, i.e. the
1568          first iteration, EV_FN has the value INIT_COND, then
1569          all the other iterations it has the value of ARG.
1570          For the moment, PEELED_CHREC nodes are not built.  */
1571       if (!res)
1572         ev_fn = chrec_dont_know;
1574       /* When there are multiple back edges of the loop (which in fact never
1575          happens currently, but nevertheless), merge their evolutions.  */
1576       evolution_function = chrec_merge (evolution_function, ev_fn);
1577     }
1579   if (dump_file && (dump_flags & TDF_DETAILS))
1580     {
1581       fprintf (dump_file, "  (evolution_function = ");
1582       print_generic_expr (dump_file, evolution_function, 0);
1583       fprintf (dump_file, "))\n");
1584     }
1586   return evolution_function;
1587 }
1589 /* Given a loop-phi-node, return the initial conditions of the
1590    variable on entry of the loop.  When the CCP has propagated
1591    constants into the loop-phi-node, the initial condition is
1592    instantiated, otherwise the initial condition is kept symbolic.
1593    This analyzer does not analyze the evolution outside the current
1594    loop, and leaves this task to the on-demand tree reconstructor.  */
1596 static tree
1597 analyze_initial_condition (tree loop_phi_node)
1598 {
1599   int i;
1600   tree init_cond = chrec_not_analyzed_yet;
1601   struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1603   if (dump_file && (dump_flags & TDF_DETAILS))
1604     {
1605       fprintf (dump_file, "(analyze_initial_condition \n");
1606       fprintf (dump_file, "  (loop_phi_node = \n");
1607       print_generic_expr (dump_file, loop_phi_node, 0);
1608       fprintf (dump_file, ")\n");
1609     }
1611   for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1612     {
1613       tree branch = PHI_ARG_DEF (loop_phi_node, i);
1614       basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1616       /* When the branch is oriented to the loop's body, it does
1617          not contribute to the initial condition.  */
1618       if (flow_bb_inside_loop_p (loop, bb))
1619         continue;
1621       if (init_cond == chrec_not_analyzed_yet)
1622         {
1623           init_cond = branch;
1624           continue;
1625         }
1627       if (TREE_CODE (branch) == SSA_NAME)
1628         {
1629           init_cond = chrec_dont_know;
1630           break;
1631         }
1633       init_cond = chrec_merge (init_cond, branch);
1634     }
1636   /* Ooops -- a loop without an entry???  */
1637   if (init_cond == chrec_not_analyzed_yet)
1638     init_cond = chrec_dont_know;
1640   if (dump_file && (dump_flags & TDF_DETAILS))
1641     {
1642       fprintf (dump_file, "  (init_cond = ");
1643       print_generic_expr (dump_file, init_cond, 0);
1644       fprintf (dump_file, "))\n");
1645     }
1647   return init_cond;
1648 }
1650 /* Analyze the scalar evolution for LOOP_PHI_NODE.  */
1652 static tree
1653 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1654 {
1655   tree res;
1656   struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1657   tree init_cond;
1659   if (phi_loop != loop)
1660     {
1661       struct loop *subloop;
1662       tree evolution_fn = analyze_scalar_evolution
1663         (phi_loop, PHI_RESULT (loop_phi_node));
1665       /* Dive one level deeper.  */
1666       subloop = superloop_at_depth (phi_loop, loop->depth + 1);
1668       /* Interpret the subloop.  */
1669       res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1670       return res;
1671     }
1673   /* Otherwise really interpret the loop phi.  */
1674   init_cond = analyze_initial_condition (loop_phi_node);
1675   res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1677   return res;
1678 }
1680 /* This function merges the branches of a condition-phi-node,
1681    contained in the outermost loop, and whose arguments are already
1682    analyzed.  */
1684 static tree
1685 interpret_condition_phi (struct loop *loop, tree condition_phi)
1686 {
1687   int i;
1688   tree res = chrec_not_analyzed_yet;
1690   for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1691     {
1692       tree branch_chrec;
1694       if (backedge_phi_arg_p (condition_phi, i))
1695         {
1696           res = chrec_dont_know;
1697           break;
1698         }
1700       branch_chrec = analyze_scalar_evolution
1701         (loop, PHI_ARG_DEF (condition_phi, i));
1703       res = chrec_merge (res, branch_chrec);
1704     }
1706   return res;
1707 }
1709 /* Interpret the right hand side of a modify_expr OPND1.  If we didn't
1710    analyzed this node before, follow the definitions until ending
1711    either on an analyzed modify_expr, or on a loop-phi-node.  On the
1712    return path, this function propagates evolutions (ala constant copy
1713    propagation).  OPND1 is not a GIMPLE expression because we could
1714    analyze the effect of an inner loop: see interpret_loop_phi.  */
1716 static tree
1717 interpret_rhs_modify_expr (struct loop *loop,
1718                            tree opnd1, tree type)
1719 {
1720   tree res, opnd10, opnd11, chrec10, chrec11;
1722   if (is_gimple_min_invariant (opnd1))
1723     return chrec_convert (type, opnd1);
1725   switch (TREE_CODE (opnd1))
1726     {
1727     case PLUS_EXPR:
1728       opnd10 = TREE_OPERAND (opnd1, 0);
1729       opnd11 = TREE_OPERAND (opnd1, 1);
1730       chrec10 = analyze_scalar_evolution (loop, opnd10);
1731       chrec11 = analyze_scalar_evolution (loop, opnd11);
1732       chrec10 = chrec_convert (type, chrec10);
1733       chrec11 = chrec_convert (type, chrec11);
1734       res = chrec_fold_plus (type, chrec10, chrec11);
1735       break;
1737     case MINUS_EXPR:
1738       opnd10 = TREE_OPERAND (opnd1, 0);
1739       opnd11 = TREE_OPERAND (opnd1, 1);
1740       chrec10 = analyze_scalar_evolution (loop, opnd10);
1741       chrec11 = analyze_scalar_evolution (loop, opnd11);
1742       chrec10 = chrec_convert (type, chrec10);
1743       chrec11 = chrec_convert (type, chrec11);
1744       res = chrec_fold_minus (type, chrec10, chrec11);
1745       break;
1747     case NEGATE_EXPR:
1748       opnd10 = TREE_OPERAND (opnd1, 0);
1749       chrec10 = analyze_scalar_evolution (loop, opnd10);
1750       chrec10 = chrec_convert (type, chrec10);
1751       res = chrec_fold_minus (type, build_int_cst (type, 0), chrec10);
1752       break;
1754     case MULT_EXPR:
1755       opnd10 = TREE_OPERAND (opnd1, 0);
1756       opnd11 = TREE_OPERAND (opnd1, 1);
1757       chrec10 = analyze_scalar_evolution (loop, opnd10);
1758       chrec11 = analyze_scalar_evolution (loop, opnd11);
1759       chrec10 = chrec_convert (type, chrec10);
1760       chrec11 = chrec_convert (type, chrec11);
1761       res = chrec_fold_multiply (type, chrec10, chrec11);
1762       break;
1764     case SSA_NAME:
1765       res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1));
1766       break;
1768     case NOP_EXPR:
1769     case CONVERT_EXPR:
1770       opnd10 = TREE_OPERAND (opnd1, 0);
1771       chrec10 = analyze_scalar_evolution (loop, opnd10);
1772       res = chrec_convert (type, chrec10);
1773       break;
1775     default:
1776       res = chrec_dont_know;
1777       break;
1778     }
1780   return res;
1781 }
1783 \f
1785 /* This section contains all the entry points:
1786    - number_of_iterations_in_loop,
1787    - analyze_scalar_evolution,
1788    - instantiate_parameters.
1789 */
1791 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1792    common ancestor of DEF_LOOP and USE_LOOP.  */
1794 static tree
1795 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1796                                   struct loop *def_loop,
1797                                   tree ev)
1798 {
1799   tree res;
1800   if (def_loop == wrto_loop)
1801     return ev;
1803   def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
1804   res = compute_overall_effect_of_inner_loop (def_loop, ev);
1806   return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1807 }
1809 /* Helper recursive function.  */
1811 static tree
1812 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1813 {
1814   tree def, type = TREE_TYPE (var);
1815   basic_block bb;
1816   struct loop *def_loop;
1818   if (loop == NULL)
1819     return chrec_dont_know;
1821   if (TREE_CODE (var) != SSA_NAME)
1822     return interpret_rhs_modify_expr (loop, var, type);
1824   def = SSA_NAME_DEF_STMT (var);
1825   bb = bb_for_stmt (def);
1826   def_loop = bb ? bb->loop_father : NULL;
1828   if (bb == NULL
1829       || !flow_bb_inside_loop_p (loop, bb))
1830     {
1831       /* Keep the symbolic form.  */
1832       res = var;
1833       goto set_and_end;
1834     }
1836   if (res != chrec_not_analyzed_yet)
1837     {
1838       if (loop != bb->loop_father)
1839         res = compute_scalar_evolution_in_loop
1840             (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1842       goto set_and_end;
1843     }
1845   if (loop != def_loop)
1846     {
1847       res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1848       res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1850       goto set_and_end;
1851     }
1853   switch (TREE_CODE (def))
1854     {
1855     case MODIFY_EXPR:
1856       res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type);
1857       break;
1859     case PHI_NODE:
1860       if (loop_phi_node_p (def))
1861         res = interpret_loop_phi (loop, def);
1862       else
1863         res = interpret_condition_phi (loop, def);
1864       break;
1866     default:
1867       res = chrec_dont_know;
1868       break;
1869     }
1871  set_and_end:
1873   /* Keep the symbolic form.  */
1874   if (res == chrec_dont_know)
1875     res = var;
1877   if (loop == def_loop)
1878     set_scalar_evolution (var, res);
1880   return res;
1881 }
1883 /* Entry point for the scalar evolution analyzer.
1884    Analyzes and returns the scalar evolution of the ssa_name VAR.
1885    LOOP_NB is the identifier number of the loop in which the variable
1886    is used.
1888    Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1889    pointer to the statement that uses this variable, in order to
1890    determine the evolution function of the variable, use the following
1891    calls:
1893    unsigned loop_nb = loop_containing_stmt (stmt)->num;
1894    tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1895    tree chrec_instantiated = instantiate_parameters
1896    (loop_nb, chrec_with_symbols);
1897 */
1899 tree
1900 analyze_scalar_evolution (struct loop *loop, tree var)
1901 {
1902   tree res;
1904   if (dump_file && (dump_flags & TDF_DETAILS))
1905     {
1906       fprintf (dump_file, "(analyze_scalar_evolution \n");
1907       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
1908       fprintf (dump_file, "  (scalar = ");
1909       print_generic_expr (dump_file, var, 0);
1910       fprintf (dump_file, ")\n");
1911     }
1913   res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
1915   if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
1916     res = var;
1918   if (dump_file && (dump_flags & TDF_DETAILS))
1919     fprintf (dump_file, ")\n");
1921   return res;
1922 }
1924 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1925    WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1926    of VERSION).  */
1928 static tree
1929 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1930                                   tree version)
1931 {
1932   bool val = false;
1933   tree ev = version;
1935   while (1)
1936     {
1937       ev = analyze_scalar_evolution (use_loop, ev);
1938       ev = resolve_mixers (use_loop, ev);
1940       if (use_loop == wrto_loop)
1941         return ev;
1943       /* If the value of the use changes in the inner loop, we cannot express
1944          its value in the outer loop (we might try to return interval chrec,
1945          but we do not have a user for it anyway)  */
1946       if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1947           || !val)
1948         return chrec_dont_know;
1950       use_loop = use_loop->outer;
1951     }
1952 }
1954 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1955    with respect to LOOP.  CHREC is the chrec to instantiate.  If
1956    ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
1957    outer loop chrecs is done.  */
1959 static tree
1960 instantiate_parameters_1 (struct loop *loop, tree chrec,
1961                           bool allow_superloop_chrecs)
1962 {
1963   tree res, op0, op1, op2;
1964   basic_block def_bb;
1965   struct loop *def_loop;
1967   if (chrec == NULL_TREE
1968       || automatically_generated_chrec_p (chrec))
1969     return chrec;
1971   if (is_gimple_min_invariant (chrec))
1972     return chrec;
1974   switch (TREE_CODE (chrec))
1975     {
1976     case SSA_NAME:
1977       def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
1979       /* A parameter (or loop invariant and we do not want to include
1980          evolutions in outer loops), nothing to do.  */
1981       if (!def_bb
1982           || (!allow_superloop_chrecs
1983               && !flow_bb_inside_loop_p (loop, def_bb)))
1984         return chrec;
1986       /* Don't instantiate the SSA_NAME if it is in a mixer
1987          structure.  This is used for avoiding the instantiation of
1988          recursively defined functions, such as:
1990          | a_2 -> {0, +, 1, +, a_2}_1  */
1992       if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
1993         {
1994           if (!flow_bb_inside_loop_p (loop, def_bb))
1995             {
1996               /* We may keep the loop invariant in symbolic form.  */
1997               return chrec;
1998             }
1999           else
2000             {
2001               /* Something with unknown behavior in LOOP.  */
2002               return chrec_dont_know;
2003             }
2004         }
2006       def_loop = find_common_loop (loop, def_bb->loop_father);
2008       /* If the analysis yields a parametric chrec, instantiate the
2009          result again.  Avoid the cyclic instantiation in mixers.  */
2011       res = analyze_scalar_evolution (def_loop, chrec);
2012       res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs);
2014       return res;
2016     case POLYNOMIAL_CHREC:
2017       op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2018                                       allow_superloop_chrecs);
2019       op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2020                                       allow_superloop_chrecs);
2021       return build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2023     case PLUS_EXPR:
2024       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2025                                       allow_superloop_chrecs);
2026       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2027                                       allow_superloop_chrecs);
2028       return chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
2030     case MINUS_EXPR:
2031       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2032                                       allow_superloop_chrecs);
2033       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2034                                       allow_superloop_chrecs);
2035       return chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
2037     case MULT_EXPR:
2038       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2039                                       allow_superloop_chrecs);
2040       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2041                                       allow_superloop_chrecs);
2042       return chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
2044     case NOP_EXPR:
2045     case CONVERT_EXPR:
2046     case NON_LVALUE_EXPR:
2047       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2048                                       allow_superloop_chrecs);
2049       if (op0 == chrec_dont_know)
2050         return chrec_dont_know;
2052       return chrec_convert (TREE_TYPE (chrec), op0);
2054     case SCEV_NOT_KNOWN:
2055       return chrec_dont_know;
2057     case SCEV_KNOWN:
2058       return chrec_known;
2060     default:
2061       break;
2062     }
2064   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2065     {
2066     case 3:
2067       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2068                                       allow_superloop_chrecs);
2069       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2070                                       allow_superloop_chrecs);
2071       op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2072                                       allow_superloop_chrecs);
2073       if (op0 == chrec_dont_know
2074           || op1 == chrec_dont_know
2075           || op2 == chrec_dont_know)
2076         return chrec_dont_know;
2077       return fold (build (TREE_CODE (chrec),
2078                           TREE_TYPE (chrec), op0, op1, op2));
2080     case 2:
2081       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2082                                       allow_superloop_chrecs);
2083       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2084                                       allow_superloop_chrecs);
2085       if (op0 == chrec_dont_know
2086           || op1 == chrec_dont_know)
2087         return chrec_dont_know;
2088       return fold (build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1));
2090     case 1:
2091       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2092                                       allow_superloop_chrecs);
2093       if (op0 == chrec_dont_know)
2094         return chrec_dont_know;
2095       return fold (build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0));
2097     case 0:
2098       return chrec;
2100     default:
2101       break;
2102     }
2104   /* Too complicated to handle.  */
2105   return chrec_dont_know;
2106 }
2108 /* Analyze all the parameters of the chrec that were left under a
2109    symbolic form.  LOOP is the loop in which symbolic names have to
2110    be analyzed and instantiated.  */
2112 tree
2113 instantiate_parameters (struct loop *loop,
2114                         tree chrec)
2115 {
2116   tree res;
2118   if (dump_file && (dump_flags & TDF_DETAILS))
2119     {
2120       fprintf (dump_file, "(instantiate_parameters \n");
2121       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
2122       fprintf (dump_file, "  (chrec = ");
2123       print_generic_expr (dump_file, chrec, 0);
2124       fprintf (dump_file, ")\n");
2125     }
2127   res = instantiate_parameters_1 (loop, chrec, true);
2129   if (dump_file && (dump_flags & TDF_DETAILS))
2130     {
2131       fprintf (dump_file, "  (res = ");
2132       print_generic_expr (dump_file, res, 0);
2133       fprintf (dump_file, "))\n");
2134     }
2136   return res;
2137 }
2139 /* Similar to instantiate_parameters, but does not introduce the
2140    evolutions in outer loops for LOOP invariants in CHREC.  */
2142 static tree
2143 resolve_mixers (struct loop *loop, tree chrec)
2144 {
2145   return instantiate_parameters_1 (loop, chrec, false);
2146 }
2148 /* Entry point for the analysis of the number of iterations pass.
2149    This function tries to safely approximate the number of iterations
2150    the loop will run.  When this property is not decidable at compile
2151    time, the result is chrec_dont_know.  Otherwise the result is
2152    a scalar or a symbolic parameter.
2154    Example of analysis: suppose that the loop has an exit condition:
2156    "if (b > 49) goto end_loop;"
2158    and that in a previous analysis we have determined that the
2159    variable 'b' has an evolution function:
2161    "EF = {23, +, 5}_2".
2163    When we evaluate the function at the point 5, i.e. the value of the
2164    variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2165    and EF (6) = 53.  In this case the value of 'b' on exit is '53' and
2166    the loop body has been executed 6 times.  */
2168 tree
2169 number_of_iterations_in_loop (struct loop *loop)
2170 {
2171   tree res, type;
2172   edge exit;
2173   struct tree_niter_desc niter_desc;
2175   /* Determine whether the number_of_iterations_in_loop has already
2176      been computed.  */
2177   res = loop->nb_iterations;
2178   if (res)
2179     return res;
2180   res = chrec_dont_know;
2182   if (dump_file && (dump_flags & TDF_DETAILS))
2183     fprintf (dump_file, "(number_of_iterations_in_loop\n");
2185   exit = loop->single_exit;
2186   if (!exit)
2187     goto end;
2189   if (!number_of_iterations_exit (loop, exit, &niter_desc))
2190     goto end;
2192   type = TREE_TYPE (niter_desc.niter);
2193   if (integer_nonzerop (niter_desc.may_be_zero))
2194     res = build_int_cst (type, 0);
2195   else if (integer_zerop (niter_desc.may_be_zero))
2196     res = niter_desc.niter;
2197   else
2198     res = chrec_dont_know;
2200 end:
2201   return set_nb_iterations_in_loop (loop, res);
2202 }
2204 /* One of the drivers for testing the scalar evolutions analysis.
2205    This function computes the number of iterations for all the loops
2206    from the EXIT_CONDITIONS array.  */
2208 static void
2209 number_of_iterations_for_all_loops (varray_type exit_conditions)
2210 {
2211   unsigned int i;
2212   unsigned nb_chrec_dont_know_loops = 0;
2213   unsigned nb_static_loops = 0;
2215   for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
2216     {
2217       tree res = number_of_iterations_in_loop
2218         (loop_containing_stmt (VARRAY_TREE (exit_conditions, i)));
2219       if (chrec_contains_undetermined (res))
2220         nb_chrec_dont_know_loops++;
2221       else
2222         nb_static_loops++;
2223     }
2225   if (dump_file)
2226     {
2227       fprintf (dump_file, "\n(\n");
2228       fprintf (dump_file, "-----------------------------------------\n");
2229       fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2230       fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2231       fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
2232       fprintf (dump_file, "-----------------------------------------\n");
2233       fprintf (dump_file, ")\n\n");
2235       print_loop_ir (dump_file);
2236     }
2237 }
2239 \f
2241 /* Counters for the stats.  */
2243 struct chrec_stats
2244 {
2245   unsigned nb_chrecs;
2246   unsigned nb_affine;
2247   unsigned nb_affine_multivar;
2248   unsigned nb_higher_poly;
2249   unsigned nb_chrec_dont_know;
2250   unsigned nb_undetermined;
2251 };
2253 /* Reset the counters.  */
2255 static inline void
2256 reset_chrecs_counters (struct chrec_stats *stats)
2257 {
2258   stats->nb_chrecs = 0;
2259   stats->nb_affine = 0;
2260   stats->nb_affine_multivar = 0;
2261   stats->nb_higher_poly = 0;
2262   stats->nb_chrec_dont_know = 0;
2263   stats->nb_undetermined = 0;
2264 }
2266 /* Dump the contents of a CHREC_STATS structure.  */
2268 static void
2269 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2270 {
2271   fprintf (file, "\n(\n");
2272   fprintf (file, "-----------------------------------------\n");
2273   fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2274   fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2275   fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2276            stats->nb_higher_poly);
2277   fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2278   fprintf (file, "-----------------------------------------\n");
2279   fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2280   fprintf (file, "%d\twith undetermined coefficients\n",
2281            stats->nb_undetermined);
2282   fprintf (file, "-----------------------------------------\n");
2283   fprintf (file, "%d\tchrecs in the scev database\n",
2284            (int) htab_elements (scalar_evolution_info));
2285   fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2286   fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2287   fprintf (file, "-----------------------------------------\n");
2288   fprintf (file, ")\n\n");
2289 }
2291 /* Gather statistics about CHREC.  */
2293 static void
2294 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2295 {
2296   if (dump_file && (dump_flags & TDF_STATS))
2297     {
2298       fprintf (dump_file, "(classify_chrec ");
2299       print_generic_expr (dump_file, chrec, 0);
2300       fprintf (dump_file, "\n");
2301     }
2303   stats->nb_chrecs++;
2305   if (chrec == NULL_TREE)
2306     {
2307       stats->nb_undetermined++;
2308       return;
2309     }
2311   switch (TREE_CODE (chrec))
2312     {
2313     case POLYNOMIAL_CHREC:
2314       if (evolution_function_is_affine_p (chrec))
2315         {
2316           if (dump_file && (dump_flags & TDF_STATS))
2317             fprintf (dump_file, "  affine_univariate\n");
2318           stats->nb_affine++;
2319         }
2320       else if (evolution_function_is_affine_multivariate_p (chrec))
2321         {
2322           if (dump_file && (dump_flags & TDF_STATS))
2323             fprintf (dump_file, "  affine_multivariate\n");
2324           stats->nb_affine_multivar++;
2325         }
2326       else
2327         {
2328           if (dump_file && (dump_flags & TDF_STATS))
2329             fprintf (dump_file, "  higher_degree_polynomial\n");
2330           stats->nb_higher_poly++;
2331         }
2333       break;
2335     default:
2336       break;
2337     }
2339   if (chrec_contains_undetermined (chrec))
2340     {
2341       if (dump_file && (dump_flags & TDF_STATS))
2342         fprintf (dump_file, "  undetermined\n");
2343       stats->nb_undetermined++;
2344     }
2346   if (dump_file && (dump_flags & TDF_STATS))
2347     fprintf (dump_file, ")\n");
2348 }
2350 /* One of the drivers for testing the scalar evolutions analysis.
2351    This function analyzes the scalar evolution of all the scalars
2352    defined as loop phi nodes in one of the loops from the
2353    EXIT_CONDITIONS array.
2355    TODO Optimization: A loop is in canonical form if it contains only
2356    a single scalar loop phi node.  All the other scalars that have an
2357    evolution in the loop are rewritten in function of this single
2358    index.  This allows the parallelization of the loop.  */
2360 static void
2361 analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions)
2362 {
2363   unsigned int i;
2364   struct chrec_stats stats;
2366   reset_chrecs_counters (&stats);
2368   for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
2369     {
2370       struct loop *loop;
2371       basic_block bb;
2372       tree phi, chrec;
2374       loop = loop_containing_stmt (VARRAY_TREE (exit_conditions, i));
2377       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2378         if (is_gimple_reg (PHI_RESULT (phi)))
2379           {
2380             chrec = instantiate_parameters
2381               (loop,
2382                analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2384             if (dump_file && (dump_flags & TDF_STATS))
2385               gather_chrec_stats (chrec, &stats);
2386           }
2387     }
2389   if (dump_file && (dump_flags & TDF_STATS))
2390     dump_chrecs_stats (dump_file, &stats);
2391 }
2393 /* Callback for htab_traverse, gathers information on chrecs in the
2394    hashtable.  */
2396 static int
2397 gather_stats_on_scev_database_1 (void **slot, void *stats)
2398 {
2399   struct scev_info_str *entry = *slot;
2401   gather_chrec_stats (entry->chrec, stats);
2403   return 1;
2404 }
2406 /* Classify the chrecs of the whole database.  */
2408 void
2409 gather_stats_on_scev_database (void)
2410 {
2411   struct chrec_stats stats;
2413   if (!dump_file)
2414     return;
2416   reset_chrecs_counters (&stats);
2418   htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2419                  &stats);
2421   dump_chrecs_stats (dump_file, &stats);
2422 }
2424 \f
2426 /* Initializer.  */
2428 static void
2429 initialize_scalar_evolutions_analyzer (void)
2430 {
2431   /* The elements below are unique.  */
2432   if (chrec_dont_know == NULL_TREE)
2433     {
2434       chrec_not_analyzed_yet = NULL_TREE;
2435       chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2436       chrec_known = make_node (SCEV_KNOWN);
2437       TREE_TYPE (chrec_dont_know) = NULL_TREE;
2438       TREE_TYPE (chrec_known) = NULL_TREE;
2439     }
2440 }
2442 /* Initialize the analysis of scalar evolutions for LOOPS.  */
2444 void
2445 scev_initialize (struct loops *loops)
2446 {
2447   unsigned i;
2448   current_loops = loops;
2450   scalar_evolution_info = htab_create (100, hash_scev_info,
2451                                        eq_scev_info, del_scev_info);
2454   initialize_scalar_evolutions_analyzer ();
2456   for (i = 1; i < loops->num; i++)
2457     if (loops->parray[i])
2458       loops->parray[i]->nb_iterations = NULL_TREE;
2459 }
2461 /* Cleans up the information cached by the scalar evolutions analysis.  */
2463 void
2464 scev_reset (void)
2465 {
2466   unsigned i;
2467   struct loop *loop;
2469   if (!scalar_evolution_info || !current_loops)
2470     return;
2472   htab_empty (scalar_evolution_info);
2473   for (i = 1; i < current_loops->num; i++)
2474     {
2475       loop = current_loops->parray[i];
2476       if (loop)
2477         loop->nb_iterations = NULL_TREE;
2478     }
2479 }
2481 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2482    its BASE and STEP if possible.  */
2484 bool
2485 simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step)
2486 {
2487   basic_block bb = bb_for_stmt (stmt);
2488   tree type, ev;
2490   *base = NULL_TREE;
2491   *step = NULL_TREE;
2493   type = TREE_TYPE (op);
2494   if (TREE_CODE (type) != INTEGER_TYPE
2495       && TREE_CODE (type) != POINTER_TYPE)
2496     return false;
2498   ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op);
2499   if (chrec_contains_undetermined (ev))
2500     return false;
2502   if (tree_does_not_contain_chrecs (ev)
2503       && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2504     {
2505       *base = ev;
2506       return true;
2507     }
2509   if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2510       || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2511     return false;
2513   *step = CHREC_RIGHT (ev);
2514   if (TREE_CODE (*step) != INTEGER_CST)
2515     return false;
2516   *base = CHREC_LEFT (ev);
2517   if (tree_contains_chrecs (*base)
2518       || chrec_contains_symbols_defined_in_loop (*base, loop->num))
2519     return false;
2521   return true;
2522 }
2524 /* Runs the analysis of scalar evolutions.  */
2526 void
2527 scev_analysis (void)
2528 {
2529   varray_type exit_conditions;
2531   VARRAY_GENERIC_PTR_INIT (exit_conditions, 37, "exit_conditions");
2532   select_loops_exit_conditions (current_loops, &exit_conditions);
2534   if (dump_file && (dump_flags & TDF_STATS))
2535     analyze_scalar_evolution_for_all_loop_phi_nodes (exit_conditions);
2537   number_of_iterations_for_all_loops (exit_conditions);
2538   VARRAY_CLEAR (exit_conditions);
2539 }
2541 /* Finalize the scalar evolution analysis.  */
2543 void
2544 scev_finalize (void)
2545 {
2546   htab_delete (scalar_evolution_info);