1 /* Scalar evolution detector.
2    Copyright (C) 2003, 2004, 2005, 2006, 2007 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 3, 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 COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
21 /*
22    Description:
24    This pass analyzes the evolution of scalar variables in loop
25    structures.  The algorithm is based on the SSA representation,
26    and on the loop hierarchy tree.  This algorithm is not based on
27    the notion of versions of a variable, as it was the case for the
28    previous implementations of the scalar evolution algorithm, but
29    it assumes that each defined name is unique.
31    The notation used in this file is called "chains of recurrences",
32    and has been proposed by Eugene Zima, Robert Van Engelen, and
33    others for describing induction variables in programs.  For example
34    "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
35    when entering in the loop_1 and has a step 2 in this loop, in other
36    words "for (b = 0; b < N; b+=2);".  Note that the coefficients of
37    this chain of recurrence (or chrec [shrek]) can contain the name of
38    other variables, in which case they are called parametric chrecs.
39    For example, "b -> {a, +, 2}_1" means that the initial value of "b"
40    is the value of "a".  In most of the cases these parametric chrecs
41    are fully instantiated before their use because symbolic names can
42    hide some difficult cases such as self-references described later
43    (see the Fibonacci example).
45    A short sketch of the algorithm is:
47    Given a scalar variable to be analyzed, follow the SSA edge to
48    its definition:
50    - When the definition is a GIMPLE_MODIFY_STMT: if the right hand side
51    (RHS) of the definition cannot be statically analyzed, the answer
52    of the analyzer is: "don't know".
53    Otherwise, for all the variables that are not yet analyzed in the
54    RHS, try to determine their evolution, and finally try to
55    evaluate the operation of the RHS that gives the evolution
56    function of the analyzed variable.
58    - When the definition is a condition-phi-node: determine the
59    evolution function for all the branches of the phi node, and
60    finally merge these evolutions (see chrec_merge).
62    - When the definition is a loop-phi-node: determine its initial
63    condition, that is the SSA edge defined in an outer loop, and
64    keep it symbolic.  Then determine the SSA edges that are defined
65    in the body of the loop.  Follow the inner edges until ending on
66    another loop-phi-node of the same analyzed loop.  If the reached
67    loop-phi-node is not the starting loop-phi-node, then we keep
68    this definition under a symbolic form.  If the reached
69    loop-phi-node is the same as the starting one, then we compute a
70    symbolic stride on the return path.  The result is then the
71    symbolic chrec {initial_condition, +, symbolic_stride}_loop.
73    Examples:
75    Example 1: Illustration of the basic algorithm.
77    | a = 3
78    | loop_1
79    |   b = phi (a, c)
80    |   c = b + 1
81    |   if (c > 10) exit_loop
82    | endloop
84    Suppose that we want to know the number of iterations of the
85    loop_1.  The exit_loop is controlled by a COND_EXPR (c > 10).  We
86    ask the scalar evolution analyzer two questions: what's the
87    scalar evolution (scev) of "c", and what's the scev of "10".  For
88    "10" the answer is "10" since it is a scalar constant.  For the
89    scalar variable "c", it follows the SSA edge to its definition,
90    "c = b + 1", and then asks again what's the scev of "b".
91    Following the SSA edge, we end on a loop-phi-node "b = phi (a,
92    c)", where the initial condition is "a", and the inner loop edge
93    is "c".  The initial condition is kept under a symbolic form (it
94    may be the case that the copy constant propagation has done its
95    work and we end with the constant "3" as one of the edges of the
96    loop-phi-node).  The update edge is followed to the end of the
97    loop, and until reaching again the starting loop-phi-node: b -> c
98    -> b.  At this point we have drawn a path from "b" to "b" from
99    which we compute the stride in the loop: in this example it is
100    "+1".  The resulting scev for "b" is "b -> {a, +, 1}_1".  Now
101    that the scev for "b" is known, it is possible to compute the
102    scev for "c", that is "c -> {a + 1, +, 1}_1".  In order to
103    determine the number of iterations in the loop_1, we have to
104    instantiate_parameters ({a + 1, +, 1}_1), that gives after some
105    more analysis the scev {4, +, 1}_1, or in other words, this is
106    the function "f (x) = x + 4", where x is the iteration count of
107    the loop_1.  Now we have to solve the inequality "x + 4 > 10",
108    and take the smallest iteration number for which the loop is
109    exited: x = 7.  This loop runs from x = 0 to x = 7, and in total
110    there are 8 iterations.  In terms of loop normalization, we have
111    created a variable that is implicitly defined, "x" or just "_1",
112    and all the other analyzed scalars of the loop are defined in
113    function of this variable:
115    a -> 3
116    b -> {3, +, 1}_1
117    c -> {4, +, 1}_1
119    or in terms of a C program:
121    | a = 3
122    | for (x = 0; x <= 7; x++)
123    |   {
124    |     b = x + 3
125    |     c = x + 4
126    |   }
128    Example 2: Illustration of the algorithm on nested loops.
130    | loop_1
131    |   a = phi (1, b)
132    |   c = a + 2
133    |   loop_2  10 times
134    |     b = phi (c, d)
135    |     d = b + 3
136    |   endloop
137    | endloop
139    For analyzing the scalar evolution of "a", the algorithm follows
140    the SSA edge into the loop's body: "a -> b".  "b" is an inner
141    loop-phi-node, and its analysis as in Example 1, gives:
143    b -> {c, +, 3}_2
144    d -> {c + 3, +, 3}_2
146    Following the SSA edge for the initial condition, we end on "c = a
147    + 2", and then on the starting loop-phi-node "a".  From this point,
148    the loop stride is computed: back on "c = a + 2" we get a "+2" in
149    the loop_1, then on the loop-phi-node "b" we compute the overall
150    effect of the inner loop that is "b = c + 30", and we get a "+30"
151    in the loop_1.  That means that the overall stride in loop_1 is
152    equal to "+32", and the result is:
154    a -> {1, +, 32}_1
155    c -> {3, +, 32}_1
157    Example 3: Higher degree polynomials.
159    | loop_1
160    |   a = phi (2, b)
161    |   c = phi (5, d)
162    |   b = a + 1
163    |   d = c + a
164    | endloop
166    a -> {2, +, 1}_1
167    b -> {3, +, 1}_1
168    c -> {5, +, a}_1
169    d -> {5 + a, +, a}_1
171    instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
172    instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
174    Example 4: Lucas, Fibonacci, or mixers in general.
176    | loop_1
177    |   a = phi (1, b)
178    |   c = phi (3, d)
179    |   b = c
180    |   d = c + a
181    | endloop
183    a -> (1, c)_1
184    c -> {3, +, a}_1
186    The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
187    following semantics: during the first iteration of the loop_1, the
188    variable contains the value 1, and then it contains the value "c".
189    Note that this syntax is close to the syntax of the loop-phi-node:
190    "a -> (1, c)_1" vs. "a = phi (1, c)".
192    The symbolic chrec representation contains all the semantics of the
193    original code.  What is more difficult is to use this information.
195    Example 5: Flip-flops, or exchangers.
197    | loop_1
198    |   a = phi (1, b)
199    |   c = phi (3, d)
200    |   b = c
201    |   d = a
202    | endloop
204    a -> (1, c)_1
205    c -> (3, a)_1
207    Based on these symbolic chrecs, it is possible to refine this
208    information into the more precise PERIODIC_CHRECs:
210    a -> |1, 3|_1
211    c -> |3, 1|_1
213    This transformation is not yet implemented.
215    Further readings:
217    You can find a more detailed description of the algorithm in:
218    http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
219    http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz.  But note that
220    this is a preliminary report and some of the details of the
221    algorithm have changed.  I'm working on a research report that
222    updates the description of the algorithms to reflect the design
223    choices used in this implementation.
225    A set of slides show a high level overview of the algorithm and run
226    an example through the scalar evolution analyzer:
227    http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
229    The slides that I have presented at the GCC Summit'04 are available
230    at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
231 */
233 #include "config.h"
234 #include "system.h"
235 #include "coretypes.h"
236 #include "tm.h"
237 #include "ggc.h"
238 #include "tree.h"
239 #include "real.h"
241 /* These RTL headers are needed for basic-block.h.  */
242 #include "rtl.h"
243 #include "basic-block.h"
244 #include "diagnostic.h"
245 #include "tree-flow.h"
246 #include "tree-dump.h"
247 #include "timevar.h"
248 #include "cfgloop.h"
249 #include "tree-chrec.h"
250 #include "tree-scalar-evolution.h"
251 #include "tree-pass.h"
252 #include "flags.h"
253 #include "params.h"
255 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
257 /* The cached information about a ssa name VAR, claiming that inside LOOP,
258    the value of VAR can be expressed as CHREC.  */
260 struct scev_info_str GTY(())
261 {
262   tree var;
263   tree chrec;
264 };
266 /* Counters for the scev database.  */
267 static unsigned nb_set_scev = 0;
268 static unsigned nb_get_scev = 0;
270 /* The following trees are unique elements.  Thus the comparison of
271    another element to these elements should be done on the pointer to
272    these trees, and not on their value.  */
274 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE.  */
275 tree chrec_not_analyzed_yet;
277 /* Reserved to the cases where the analyzer has detected an
278    undecidable property at compile time.  */
279 tree chrec_dont_know;
281 /* When the analyzer has detected that a property will never
282    happen, then it qualifies it with chrec_known.  */
283 tree chrec_known;
285 static bitmap already_instantiated;
287 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
289 \f
290 /* Constructs a new SCEV_INFO_STR structure.  */
292 static inline struct scev_info_str *
293 new_scev_info_str (tree var)
294 {
295   struct scev_info_str *res;
297   res = GGC_NEW (struct scev_info_str);
298   res->var = var;
299   res->chrec = chrec_not_analyzed_yet;
301   return res;
302 }
304 /* Computes a hash function for database element ELT.  */
306 static hashval_t
307 hash_scev_info (const void *elt)
308 {
309   return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
310 }
312 /* Compares database elements E1 and E2.  */
314 static int
315 eq_scev_info (const void *e1, const void *e2)
316 {
317   const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
318   const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
320   return elt1->var == elt2->var;
321 }
323 /* Deletes database element E.  */
325 static void
326 del_scev_info (void *e)
327 {
328   ggc_free (e);
329 }
331 /* Get the index corresponding to VAR in the current LOOP.  If
332    it's the first time we ask for this VAR, then we return
333    chrec_not_analyzed_yet for this VAR and return its index.  */
335 static tree *
336 find_var_scev_info (tree var)
337 {
338   struct scev_info_str *res;
339   struct scev_info_str tmp;
340   PTR *slot;
342   tmp.var = var;
343   slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
345   if (!*slot)
346     *slot = new_scev_info_str (var);
347   res = (struct scev_info_str *) *slot;
349   return &res->chrec;
350 }
352 /* Return true when CHREC contains symbolic names defined in
353    LOOP_NB.  */
355 bool
356 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
357 {
358   int i, n;
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 = get_loop (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   n = TREE_OPERAND_LENGTH (chrec);
390   for (i = 0; i < n; i++)
391     if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
392                                                 loop_nb))
393       return true;
394   return false;
395 }
397 /* Return true when PHI is a loop-phi-node.  */
399 static bool
400 loop_phi_node_p (tree phi)
401 {
402   /* The implementation of this function is based on the following
403      property: "all the loop-phi-nodes of a loop are contained in the
404      loop's header basic block".  */
406   return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
407 }
409 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
410    In general, in the case of multivariate evolutions we want to get
411    the evolution in different loops.  LOOP specifies the level for
412    which to get the evolution.
414    Example:
416    | for (j = 0; j < 100; j++)
417    |   {
418    |     for (k = 0; k < 100; k++)
419    |       {
420    |         i = k + j;   - Here the value of i is a function of j, k.
421    |       }
422    |      ... = i         - Here the value of i is a function of j.
423    |   }
424    | ... = i              - Here the value of i is a scalar.
426    Example:
428    | i_0 = ...
429    | loop_1 10 times
430    |   i_1 = phi (i_0, i_2)
431    |   i_2 = i_1 + 2
432    | endloop
434    This loop has the same effect as:
435    LOOP_1 has the same effect as:
437    | i_1 = i_0 + 20
439    The overall effect of the loop, "i_0 + 20" in the previous example,
440    is obtained by passing in the parameters: LOOP = 1,
441    EVOLUTION_FN = {i_0, +, 2}_1.
442 */
444 static tree
445 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
446 {
447   bool val = false;
449   if (evolution_fn == chrec_dont_know)
450     return chrec_dont_know;
452   else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
453     {
454       struct loop *inner_loop = get_chrec_loop (evolution_fn);
456       if (inner_loop == loop
457           || flow_loop_nested_p (loop, inner_loop))
458         {
459           tree nb_iter = number_of_latch_executions (inner_loop);
461           if (nb_iter == chrec_dont_know)
462             return chrec_dont_know;
463           else
464             {
465               tree res;
467               /* evolution_fn is the evolution function in LOOP.  Get
468                  its value in the nb_iter-th iteration.  */
469               res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
471               /* Continue the computation until ending on a parent of LOOP.  */
472               return compute_overall_effect_of_inner_loop (loop, res);
473             }
474         }
475       else
476         return evolution_fn;
477      }
479   /* If the evolution function is an invariant, there is nothing to do.  */
480   else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
481     return evolution_fn;
483   else
484     return chrec_dont_know;
485 }
487 /* Determine whether the CHREC is always positive/negative.  If the expression
488    cannot be statically analyzed, return false, otherwise set the answer into
489    VALUE.  */
491 bool
492 chrec_is_positive (tree chrec, bool *value)
493 {
494   bool value0, value1, value2;
495   tree end_value, nb_iter;
497   switch (TREE_CODE (chrec))
498     {
499     case POLYNOMIAL_CHREC:
500       if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
501           || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
502         return false;
504       /* FIXME -- overflows.  */
505       if (value0 == value1)
506         {
507           *value = value0;
508           return true;
509         }
511       /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
512          and the proof consists in showing that the sign never
513          changes during the execution of the loop, from 0 to
514          loop->nb_iterations.  */
515       if (!evolution_function_is_affine_p (chrec))
516         return false;
518       nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
519       if (chrec_contains_undetermined (nb_iter))
520         return false;
522 #if 0
523       /* TODO -- If the test is after the exit, we may decrease the number of
524          iterations by one.  */
525       if (after_exit)
526         nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
527 #endif
529       end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
531       if (!chrec_is_positive (end_value, &value2))
532         return false;
534       *value = value0;
535       return value0 == value1;
537     case INTEGER_CST:
538       *value = (tree_int_cst_sgn (chrec) == 1);
539       return true;
541     default:
542       return false;
543     }
544 }
546 /* Associate CHREC to SCALAR.  */
548 static void
549 set_scalar_evolution (tree scalar, tree chrec)
550 {
551   tree *scalar_info;
553   if (TREE_CODE (scalar) != SSA_NAME)
554     return;
556   scalar_info = find_var_scev_info (scalar);
558   if (dump_file)
559     {
560       if (dump_flags & TDF_DETAILS)
561         {
562           fprintf (dump_file, "(set_scalar_evolution \n");
563           fprintf (dump_file, "  (scalar = ");
564           print_generic_expr (dump_file, scalar, 0);
565           fprintf (dump_file, ")\n  (scalar_evolution = ");
566           print_generic_expr (dump_file, chrec, 0);
567           fprintf (dump_file, "))\n");
568         }
569       if (dump_flags & TDF_STATS)
570         nb_set_scev++;
571     }
573   *scalar_info = chrec;
574 }
576 /* Retrieve the chrec associated to SCALAR in the LOOP.  */
578 static tree
579 get_scalar_evolution (tree scalar)
580 {
581   tree res;
583   if (dump_file)
584     {
585       if (dump_flags & TDF_DETAILS)
586         {
587           fprintf (dump_file, "(get_scalar_evolution \n");
588           fprintf (dump_file, "  (scalar = ");
589           print_generic_expr (dump_file, scalar, 0);
590           fprintf (dump_file, ")\n");
591         }
592       if (dump_flags & TDF_STATS)
593         nb_get_scev++;
594     }
596   switch (TREE_CODE (scalar))
597     {
598     case SSA_NAME:
599       res = *find_var_scev_info (scalar);
600       break;
602     case REAL_CST:
603     case FIXED_CST:
604     case INTEGER_CST:
605       res = scalar;
606       break;
608     default:
609       res = chrec_not_analyzed_yet;
610       break;
611     }
613   if (dump_file && (dump_flags & TDF_DETAILS))
614     {
615       fprintf (dump_file, "  (scalar_evolution = ");
616       print_generic_expr (dump_file, res, 0);
617       fprintf (dump_file, "))\n");
618     }
620   return res;
621 }
623 /* Helper function for add_to_evolution.  Returns the evolution
624    function for an assignment of the form "a = b + c", where "a" and
625    "b" are on the strongly connected component.  CHREC_BEFORE is the
626    information that we already have collected up to this point.
627    TO_ADD is the evolution of "c".
629    When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
630    evolution the expression TO_ADD, otherwise construct an evolution
631    part for this loop.  */
633 static tree
634 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
635                     tree at_stmt)
636 {
637   tree type, left, right;
638   struct loop *loop = get_loop (loop_nb), *chloop;
640   switch (TREE_CODE (chrec_before))
641     {
642     case POLYNOMIAL_CHREC:
643       chloop = get_chrec_loop (chrec_before);
644       if (chloop == loop
645           || flow_loop_nested_p (chloop, loop))
646         {
647           unsigned var;
649           type = chrec_type (chrec_before);
651           /* When there is no evolution part in this loop, build it.  */
652           if (chloop != loop)
653             {
654               var = loop_nb;
655               left = chrec_before;
656               right = SCALAR_FLOAT_TYPE_P (type)
657                 ? build_real (type, dconst0)
658                 : build_int_cst (type, 0);
659             }
660           else
661             {
662               var = CHREC_VARIABLE (chrec_before);
663               left = CHREC_LEFT (chrec_before);
664               right = CHREC_RIGHT (chrec_before);
665             }
667           to_add = chrec_convert (type, to_add, at_stmt);
668           right = chrec_convert_rhs (type, right, at_stmt);
669           right = chrec_fold_plus (chrec_type (right), right, to_add);
670           return build_polynomial_chrec (var, left, right);
671         }
672       else
673         {
674           gcc_assert (flow_loop_nested_p (loop, chloop));
676           /* Search the evolution in LOOP_NB.  */
677           left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
678                                      to_add, at_stmt);
679           right = CHREC_RIGHT (chrec_before);
680           right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
681           return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
682                                          left, right);
683         }
685     default:
686       /* These nodes do not depend on a loop.  */
687       if (chrec_before == chrec_dont_know)
688         return chrec_dont_know;
690       left = chrec_before;
691       right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
692       return build_polynomial_chrec (loop_nb, left, right);
693     }
694 }
696 /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
697    of LOOP_NB.
699    Description (provided for completeness, for those who read code in
700    a plane, and for my poor 62 bytes brain that would have forgotten
701    all this in the next two or three months):
703    The algorithm of translation of programs from the SSA representation
704    into the chrecs syntax is based on a pattern matching.  After having
705    reconstructed the overall tree expression for a loop, there are only
706    two cases that can arise:
708    1. a = loop-phi (init, a + expr)
709    2. a = loop-phi (init, expr)
711    where EXPR is either a scalar constant with respect to the analyzed
712    loop (this is a degree 0 polynomial), or an expression containing
713    other loop-phi definitions (these are higher degree polynomials).
715    Examples:
717    1.
718    | init = ...
719    | loop_1
720    |   a = phi (init, a + 5)
721    | endloop
723    2.
724    | inita = ...
725    | initb = ...
726    | loop_1
727    |   a = phi (inita, 2 * b + 3)
728    |   b = phi (initb, b + 1)
729    | endloop
731    For the first case, the semantics of the SSA representation is:
733    | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
735    that is, there is a loop index "x" that determines the scalar value
736    of the variable during the loop execution.  During the first
737    iteration, the value is that of the initial condition INIT, while
738    during the subsequent iterations, it is the sum of the initial
739    condition with the sum of all the values of EXPR from the initial
740    iteration to the before last considered iteration.
742    For the second case, the semantics of the SSA program is:
744    | a (x) = init, if x = 0;
745    |         expr (x - 1), otherwise.
747    The second case corresponds to the PEELED_CHREC, whose syntax is
748    close to the syntax of a loop-phi-node:
750    | phi (init, expr)  vs.  (init, expr)_x
752    The proof of the translation algorithm for the first case is a
753    proof by structural induction based on the degree of EXPR.
755    Degree 0:
756    When EXPR is a constant with respect to the analyzed loop, or in
757    other words when EXPR is a polynomial of degree 0, the evolution of
758    the variable A in the loop is an affine function with an initial
759    condition INIT, and a step EXPR.  In order to show this, we start
760    from the semantics of the SSA representation:
762    f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
764    and since "expr (j)" is a constant with respect to "j",
766    f (x) = init + x * expr
768    Finally, based on the semantics of the pure sum chrecs, by
769    identification we get the corresponding chrecs syntax:
771    f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
772    f (x) -> {init, +, expr}_x
774    Higher degree:
775    Suppose that EXPR is a polynomial of degree N with respect to the
776    analyzed loop_x for which we have already determined that it is
777    written under the chrecs syntax:
779    | expr (x)  ->  {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
781    We start from the semantics of the SSA program:
783    | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
784    |
785    | f (x) = init + \sum_{j = 0}^{x - 1}
786    |                (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
787    |
788    | f (x) = init + \sum_{j = 0}^{x - 1}
789    |                \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
790    |
791    | f (x) = init + \sum_{k = 0}^{n - 1}
792    |                (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
793    |
794    | f (x) = init + \sum_{k = 0}^{n - 1}
795    |                (b_k * \binom{x}{k + 1})
796    |
797    | f (x) = init + b_0 * \binom{x}{1} + ...
798    |              + b_{n-1} * \binom{x}{n}
799    |
800    | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
801    |                             + b_{n-1} * \binom{x}{n}
802    |
804    And finally from the definition of the chrecs syntax, we identify:
805    | f (x)  ->  {init, +, b_0, +, ..., +, b_{n-1}}_x
807    This shows the mechanism that stands behind the add_to_evolution
808    function.  An important point is that the use of symbolic
809    parameters avoids the need of an analysis schedule.
811    Example:
813    | inita = ...
814    | initb = ...
815    | loop_1
816    |   a = phi (inita, a + 2 + b)
817    |   b = phi (initb, b + 1)
818    | endloop
820    When analyzing "a", the algorithm keeps "b" symbolically:
822    | a  ->  {inita, +, 2 + b}_1
824    Then, after instantiation, the analyzer ends on the evolution:
826    | a  ->  {inita, +, 2 + initb, +, 1}_1
828 */
830 static tree
831 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
832                   tree to_add, tree at_stmt)
833 {
834   tree type = chrec_type (to_add);
835   tree res = NULL_TREE;
837   if (to_add == NULL_TREE)
838     return chrec_before;
840   /* TO_ADD is either a scalar, or a parameter.  TO_ADD is not
841      instantiated at this point.  */
842   if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
843     /* This should not happen.  */
844     return chrec_dont_know;
846   if (dump_file && (dump_flags & TDF_DETAILS))
847     {
848       fprintf (dump_file, "(add_to_evolution \n");
849       fprintf (dump_file, "  (loop_nb = %d)\n", loop_nb);
850       fprintf (dump_file, "  (chrec_before = ");
851       print_generic_expr (dump_file, chrec_before, 0);
852       fprintf (dump_file, ")\n  (to_add = ");
853       print_generic_expr (dump_file, to_add, 0);
854       fprintf (dump_file, ")\n");
855     }
857   if (code == MINUS_EXPR)
858     to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
859                                   ? build_real (type, dconstm1)
860                                   : build_int_cst_type (type, -1));
862   res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
864   if (dump_file && (dump_flags & TDF_DETAILS))
865     {
866       fprintf (dump_file, "  (res = ");
867       print_generic_expr (dump_file, res, 0);
868       fprintf (dump_file, "))\n");
869     }
871   return res;
872 }
874 /* Helper function.  */
876 static inline tree
877 set_nb_iterations_in_loop (struct loop *loop,
878                            tree res)
879 {
880   if (dump_file && (dump_flags & TDF_DETAILS))
881     {
882       fprintf (dump_file, "  (set_nb_iterations_in_loop = ");
883       print_generic_expr (dump_file, res, 0);
884       fprintf (dump_file, "))\n");
885     }
887   loop->nb_iterations = res;
888   return res;
889 }
891 \f
893 /* This section selects the loops that will be good candidates for the
894    scalar evolution analysis.  For the moment, greedily select all the
895    loop nests we could analyze.  */
897 /* Return true when it is possible to analyze the condition expression
898    EXPR.  */
900 static bool
901 analyzable_condition (const_tree expr)
902 {
903   tree condition;
905   if (TREE_CODE (expr) != COND_EXPR)
906     return false;
908   condition = TREE_OPERAND (expr, 0);
910   switch (TREE_CODE (condition))
911     {
912     case SSA_NAME:
913       return true;
915     case LT_EXPR:
916     case LE_EXPR:
917     case GT_EXPR:
918     case GE_EXPR:
919     case EQ_EXPR:
920     case NE_EXPR:
921       return true;
923     default:
924       return false;
925     }
927   return false;
928 }
930 /* For a loop with a single exit edge, return the COND_EXPR that
931    guards the exit edge.  If the expression is too difficult to
932    analyze, then give up.  */
934 tree
935 get_loop_exit_condition (const struct loop *loop)
936 {
937   tree res = NULL_TREE;
938   edge exit_edge = single_exit (loop);
940   if (dump_file && (dump_flags & TDF_DETAILS))
941     fprintf (dump_file, "(get_loop_exit_condition \n  ");
943   if (exit_edge)
944     {
945       tree expr;
947       expr = last_stmt (exit_edge->src);
948       if (analyzable_condition (expr))
949         res = expr;
950     }
952   if (dump_file && (dump_flags & TDF_DETAILS))
953     {
954       print_generic_expr (dump_file, res, 0);
955       fprintf (dump_file, ")\n");
956     }
958   return res;
959 }
961 /* Recursively determine and enqueue the exit conditions for a loop.  */
963 static void
964 get_exit_conditions_rec (struct loop *loop,
965                          VEC(tree,heap) **exit_conditions)
966 {
967   if (!loop)
968     return;
970   /* Recurse on the inner loops, then on the next (sibling) loops.  */
971   get_exit_conditions_rec (loop->inner, exit_conditions);
972   get_exit_conditions_rec (loop->next, exit_conditions);
974   if (single_exit (loop))
975     {
976       tree loop_condition = get_loop_exit_condition (loop);
978       if (loop_condition)
979         VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
980     }
981 }
983 /* Select the candidate loop nests for the analysis.  This function
984    initializes the EXIT_CONDITIONS array.  */
986 static void
987 select_loops_exit_conditions (VEC(tree,heap) **exit_conditions)
988 {
989   struct loop *function_body = current_loops->tree_root;
991   get_exit_conditions_rec (function_body->inner, exit_conditions);
992 }
994 \f
995 /* Depth first search algorithm.  */
997 typedef enum t_bool {
998   t_false,
999   t_true,
1000   t_dont_know
1001 } t_bool;
1004 static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
1006 /* Follow the ssa edge into the right hand side RHS of an assignment.
1007    Return true if the strongly connected component has been found.  */
1009 static t_bool
1010 follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs,
1011                         tree halting_phi, tree *evolution_of_loop, int limit)
1012 {
1013   t_bool res = t_false;
1014   tree rhs0, rhs1;
1015   tree type_rhs = TREE_TYPE (rhs);
1016   tree evol;
1017   enum tree_code code;
1019   /* The RHS is one of the following cases:
1020      - an SSA_NAME,
1021      - an INTEGER_CST,
1022      - a PLUS_EXPR,
1023      - a POINTER_PLUS_EXPR,
1024      - a MINUS_EXPR,
1025      - an ASSERT_EXPR,
1026      - other cases are not yet handled.  */
1027   code = TREE_CODE (rhs);
1028   switch (code)
1029     {
1030     case NOP_EXPR:
1031       /* This assignment is under the form "a_1 = (cast) rhs.  */
1032       res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
1033                                     halting_phi, evolution_of_loop, limit);
1034       *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
1035                                           *evolution_of_loop, at_stmt);
1036       break;
1038     case INTEGER_CST:
1039       /* This assignment is under the form "a_1 = 7".  */
1040       res = t_false;
1041       break;
1043     case SSA_NAME:
1044       /* This assignment is under the form: "a_1 = b_2".  */
1045       res = follow_ssa_edge
1046         (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
1047       break;
1049     case POINTER_PLUS_EXPR:
1050     case PLUS_EXPR:
1051       /* This case is under the form "rhs0 + rhs1".  */
1052       rhs0 = TREE_OPERAND (rhs, 0);
1053       rhs1 = TREE_OPERAND (rhs, 1);
1054       STRIP_TYPE_NOPS (rhs0);
1055       STRIP_TYPE_NOPS (rhs1);
1057       if (TREE_CODE (rhs0) == SSA_NAME)
1058         {
1059           if (TREE_CODE (rhs1) == SSA_NAME)
1060             {
1061               /* Match an assignment under the form:
1062                  "a = b + c".  */
1064               /* We want only assignments of form "name + name" contribute to
1065                  LIMIT, as the other cases do not necessarily contribute to
1066                  the complexity of the expression.  */
1067               limit++;
1069               evol = *evolution_of_loop;
1070               res = follow_ssa_edge
1071                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1072                  &evol, limit);
1074               if (res == t_true)
1075                 *evolution_of_loop = add_to_evolution
1076                   (loop->num,
1077                    chrec_convert (type_rhs, evol, at_stmt),
1078                    code, rhs1, at_stmt);
1080               else if (res == t_false)
1081                 {
1082                   res = follow_ssa_edge
1083                     (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1084                      evolution_of_loop, limit);
1086                   if (res == t_true)
1087                     *evolution_of_loop = add_to_evolution
1088                       (loop->num,
1089                        chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1090                        code, rhs0, at_stmt);
1092                   else if (res == t_dont_know)
1093                     *evolution_of_loop = chrec_dont_know;
1094                 }
1096               else if (res == t_dont_know)
1097                 *evolution_of_loop = chrec_dont_know;
1098             }
1100           else
1101             {
1102               /* Match an assignment under the form:
1103                  "a = b + ...".  */
1104               res = follow_ssa_edge
1105                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1106                  evolution_of_loop, limit);
1107               if (res == t_true)
1108                 *evolution_of_loop = add_to_evolution
1109                   (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1110                                              at_stmt),
1111                    code, rhs1, at_stmt);
1113               else if (res == t_dont_know)
1114                 *evolution_of_loop = chrec_dont_know;
1115             }
1116         }
1118       else if (TREE_CODE (rhs1) == SSA_NAME)
1119         {
1120           /* Match an assignment under the form:
1121              "a = ... + c".  */
1122           res = follow_ssa_edge
1123             (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1124              evolution_of_loop, limit);
1125           if (res == t_true)
1126             *evolution_of_loop = add_to_evolution
1127               (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1128                                          at_stmt),
1129                code, rhs0, at_stmt);
1131           else if (res == t_dont_know)
1132             *evolution_of_loop = chrec_dont_know;
1133         }
1135       else
1136         /* Otherwise, match an assignment under the form:
1137            "a = ... + ...".  */
1138         /* And there is nothing to do.  */
1139         res = t_false;
1141       break;
1143     case MINUS_EXPR:
1144       /* This case is under the form "opnd0 = rhs0 - rhs1".  */
1145       rhs0 = TREE_OPERAND (rhs, 0);
1146       rhs1 = TREE_OPERAND (rhs, 1);
1147       STRIP_TYPE_NOPS (rhs0);
1148       STRIP_TYPE_NOPS (rhs1);
1150       if (TREE_CODE (rhs0) == SSA_NAME)
1151         {
1152           /* Match an assignment under the form:
1153              "a = b - ...".  */
1155           /* We want only assignments of form "name - name" contribute to
1156              LIMIT, as the other cases do not necessarily contribute to
1157              the complexity of the expression.  */
1158           if (TREE_CODE (rhs1) == SSA_NAME)
1159             limit++;
1161           res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1162                                  evolution_of_loop, limit);
1163           if (res == t_true)
1164             *evolution_of_loop = add_to_evolution
1165               (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1166                MINUS_EXPR, rhs1, at_stmt);
1168           else if (res == t_dont_know)
1169             *evolution_of_loop = chrec_dont_know;
1170         }
1171       else
1172         /* Otherwise, match an assignment under the form:
1173            "a = ... - ...".  */
1174         /* And there is nothing to do.  */
1175         res = t_false;
1177       break;
1179     case ASSERT_EXPR:
1180       {
1181         /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1182            It must be handled as a copy assignment of the form a_1 = a_2.  */
1183         tree op0 = ASSERT_EXPR_VAR (rhs);
1184         if (TREE_CODE (op0) == SSA_NAME)
1185           res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1186                                  halting_phi, evolution_of_loop, limit);
1187         else
1188           res = t_false;
1189         break;
1190       }
1193     default:
1194       res = t_false;
1195       break;
1196     }
1198   return res;
1199 }
1201 /* Checks whether the I-th argument of a PHI comes from a backedge.  */
1203 static bool
1204 backedge_phi_arg_p (const_tree phi, int i)
1205 {
1206   const_edge e = PHI_ARG_EDGE (phi, i);
1208   /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1209      about updating it anywhere, and this should work as well most of the
1210      time.  */
1211   if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1212     return true;
1214   return false;
1215 }
1217 /* Helper function for one branch of the condition-phi-node.  Return
1218    true if the strongly connected component has been found following
1219    this path.  */
1221 static inline t_bool
1222 follow_ssa_edge_in_condition_phi_branch (int i,
1223                                          struct loop *loop,
1224                                          tree condition_phi,
1225                                          tree halting_phi,
1226                                          tree *evolution_of_branch,
1227                                          tree init_cond, int limit)
1228 {
1229   tree branch = PHI_ARG_DEF (condition_phi, i);
1230   *evolution_of_branch = chrec_dont_know;
1232   /* Do not follow back edges (they must belong to an irreducible loop, which
1233      we really do not want to worry about).  */
1234   if (backedge_phi_arg_p (condition_phi, i))
1235     return t_false;
1237   if (TREE_CODE (branch) == SSA_NAME)
1238     {
1239       *evolution_of_branch = init_cond;
1240       return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1241                               evolution_of_branch, limit);
1242     }
1244   /* This case occurs when one of the condition branches sets
1245      the variable to a constant: i.e. a phi-node like
1246      "a_2 = PHI <a_7(5), 2(6)>;".
1248      FIXME:  This case have to be refined correctly:
1249      in some cases it is possible to say something better than
1250      chrec_dont_know, for example using a wrap-around notation.  */
1251   return t_false;
1252 }
1254 /* This function merges the branches of a condition-phi-node in a
1255    loop.  */
1257 static t_bool
1258 follow_ssa_edge_in_condition_phi (struct loop *loop,
1259                                   tree condition_phi,
1260                                   tree halting_phi,
1261                                   tree *evolution_of_loop, int limit)
1262 {
1263   int i;
1264   tree init = *evolution_of_loop;
1265   tree evolution_of_branch;
1266   t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1267                                                         halting_phi,
1268                                                         &evolution_of_branch,
1269                                                         init, limit);
1270   if (res == t_false || res == t_dont_know)
1271     return res;
1273   *evolution_of_loop = evolution_of_branch;
1275   /* If the phi node is just a copy, do not increase the limit.  */
1276   if (PHI_NUM_ARGS (condition_phi) > 1)
1277     limit++;
1279   for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1280     {
1281       /* Quickly give up when the evolution of one of the branches is
1282          not known.  */
1283       if (*evolution_of_loop == chrec_dont_know)
1284         return t_true;
1286       res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1287                                                      halting_phi,
1288                                                      &evolution_of_branch,
1289                                                      init, limit);
1290       if (res == t_false || res == t_dont_know)
1291         return res;
1293       *evolution_of_loop = chrec_merge (*evolution_of_loop,
1294                                         evolution_of_branch);
1295     }
1297   return t_true;
1298 }
1300 /* Follow an SSA edge in an inner loop.  It computes the overall
1301    effect of the loop, and following the symbolic initial conditions,
1302    it follows the edges in the parent loop.  The inner loop is
1303    considered as a single statement.  */
1305 static t_bool
1306 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1307                                 tree loop_phi_node,
1308                                 tree halting_phi,
1309                                 tree *evolution_of_loop, int limit)
1310 {
1311   struct loop *loop = loop_containing_stmt (loop_phi_node);
1312   tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1314   /* Sometimes, the inner loop is too difficult to analyze, and the
1315      result of the analysis is a symbolic parameter.  */
1316   if (ev == PHI_RESULT (loop_phi_node))
1317     {
1318       t_bool res = t_false;
1319       int i;
1321       for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1322         {
1323           tree arg = PHI_ARG_DEF (loop_phi_node, i);
1324           basic_block bb;
1326           /* Follow the edges that exit the inner loop.  */
1327           bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1328           if (!flow_bb_inside_loop_p (loop, bb))
1329             res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
1330                                           arg, halting_phi,
1331                                           evolution_of_loop, limit);
1332           if (res == t_true)
1333             break;
1334         }
1336       /* If the path crosses this loop-phi, give up.  */
1337       if (res == t_true)
1338         *evolution_of_loop = chrec_dont_know;
1340       return res;
1341     }
1343   /* Otherwise, compute the overall effect of the inner loop.  */
1344   ev = compute_overall_effect_of_inner_loop (loop, ev);
1345   return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
1346                                  evolution_of_loop, limit);
1347 }
1349 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1350    path that is analyzed on the return walk.  */
1352 static t_bool
1353 follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
1354                  tree *evolution_of_loop, int limit)
1355 {
1356   struct loop *def_loop;
1358   if (TREE_CODE (def) == NOP_EXPR)
1359     return t_false;
1361   /* Give up if the path is longer than the MAX that we allow.  */
1362   if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1363     return t_dont_know;
1365   def_loop = loop_containing_stmt (def);
1367   switch (TREE_CODE (def))
1368     {
1369     case PHI_NODE:
1370       if (!loop_phi_node_p (def))
1371         /* DEF is a condition-phi-node.  Follow the branches, and
1372            record their evolutions.  Finally, merge the collected
1373            information and set the approximation to the main
1374            variable.  */
1375         return follow_ssa_edge_in_condition_phi
1376           (loop, def, halting_phi, evolution_of_loop, limit);
1378       /* When the analyzed phi is the halting_phi, the
1379          depth-first search is over: we have found a path from
1380          the halting_phi to itself in the loop.  */
1381       if (def == halting_phi)
1382         return t_true;
1384       /* Otherwise, the evolution of the HALTING_PHI depends
1385          on the evolution of another loop-phi-node, i.e. the
1386          evolution function is a higher degree polynomial.  */
1387       if (def_loop == loop)
1388         return t_false;
1390       /* Inner loop.  */
1391       if (flow_loop_nested_p (loop, def_loop))
1392         return follow_ssa_edge_inner_loop_phi
1393           (loop, def, halting_phi, evolution_of_loop, limit + 1);
1395       /* Outer loop.  */
1396       return t_false;
1398     case GIMPLE_MODIFY_STMT:
1399       return follow_ssa_edge_in_rhs (loop, def,
1400                                      GIMPLE_STMT_OPERAND (def, 1),
1401                                      halting_phi,
1402                                      evolution_of_loop, limit);
1404     default:
1405       /* At this level of abstraction, the program is just a set
1406          of GIMPLE_MODIFY_STMTs and PHI_NODEs.  In principle there is no
1407          other node to be handled.  */
1408       return t_false;
1409     }
1410 }
1412 \f
1414 /* Given a LOOP_PHI_NODE, this function determines the evolution
1415    function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.  */
1417 static tree
1418 analyze_evolution_in_loop (tree loop_phi_node,
1419                            tree init_cond)
1420 {
1421   int i;
1422   tree evolution_function = chrec_not_analyzed_yet;
1423   struct loop *loop = loop_containing_stmt (loop_phi_node);
1424   basic_block bb;
1426   if (dump_file && (dump_flags & TDF_DETAILS))
1427     {
1428       fprintf (dump_file, "(analyze_evolution_in_loop \n");
1429       fprintf (dump_file, "  (loop_phi_node = ");
1430       print_generic_expr (dump_file, loop_phi_node, 0);
1431       fprintf (dump_file, ")\n");
1432     }
1434   for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1435     {
1436       tree arg = PHI_ARG_DEF (loop_phi_node, i);
1437       tree ssa_chain, ev_fn;
1438       t_bool res;
1440       /* Select the edges that enter the loop body.  */
1441       bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1442       if (!flow_bb_inside_loop_p (loop, bb))
1443         continue;
1445       if (TREE_CODE (arg) == SSA_NAME)
1446         {
1447           ssa_chain = SSA_NAME_DEF_STMT (arg);
1449           /* Pass in the initial condition to the follow edge function.  */
1450           ev_fn = init_cond;
1451           res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1452         }
1453       else
1454         res = t_false;
1456       /* When it is impossible to go back on the same
1457          loop_phi_node by following the ssa edges, the
1458          evolution is represented by a peeled chrec, i.e. the
1459          first iteration, EV_FN has the value INIT_COND, then
1460          all the other iterations it has the value of ARG.
1461          For the moment, PEELED_CHREC nodes are not built.  */
1462       if (res != t_true)
1463         ev_fn = chrec_dont_know;
1465       /* When there are multiple back edges of the loop (which in fact never
1466          happens currently, but nevertheless), merge their evolutions.  */
1467       evolution_function = chrec_merge (evolution_function, ev_fn);
1468     }
1470   if (dump_file && (dump_flags & TDF_DETAILS))
1471     {
1472       fprintf (dump_file, "  (evolution_function = ");
1473       print_generic_expr (dump_file, evolution_function, 0);
1474       fprintf (dump_file, "))\n");
1475     }
1477   return evolution_function;
1478 }
1480 /* Given a loop-phi-node, return the initial conditions of the
1481    variable on entry of the loop.  When the CCP has propagated
1482    constants into the loop-phi-node, the initial condition is
1483    instantiated, otherwise the initial condition is kept symbolic.
1484    This analyzer does not analyze the evolution outside the current
1485    loop, and leaves this task to the on-demand tree reconstructor.  */
1487 static tree
1488 analyze_initial_condition (tree loop_phi_node)
1489 {
1490   int i;
1491   tree init_cond = chrec_not_analyzed_yet;
1492   struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1494   if (dump_file && (dump_flags & TDF_DETAILS))
1495     {
1496       fprintf (dump_file, "(analyze_initial_condition \n");
1497       fprintf (dump_file, "  (loop_phi_node = \n");
1498       print_generic_expr (dump_file, loop_phi_node, 0);
1499       fprintf (dump_file, ")\n");
1500     }
1502   for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1503     {
1504       tree branch = PHI_ARG_DEF (loop_phi_node, i);
1505       basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1507       /* When the branch is oriented to the loop's body, it does
1508          not contribute to the initial condition.  */
1509       if (flow_bb_inside_loop_p (loop, bb))
1510         continue;
1512       if (init_cond == chrec_not_analyzed_yet)
1513         {
1514           init_cond = branch;
1515           continue;
1516         }
1518       if (TREE_CODE (branch) == SSA_NAME)
1519         {
1520           init_cond = chrec_dont_know;
1521           break;
1522         }
1524       init_cond = chrec_merge (init_cond, branch);
1525     }
1527   /* Ooops -- a loop without an entry???  */
1528   if (init_cond == chrec_not_analyzed_yet)
1529     init_cond = chrec_dont_know;
1531   if (dump_file && (dump_flags & TDF_DETAILS))
1532     {
1533       fprintf (dump_file, "  (init_cond = ");
1534       print_generic_expr (dump_file, init_cond, 0);
1535       fprintf (dump_file, "))\n");
1536     }
1538   return init_cond;
1539 }
1541 /* Analyze the scalar evolution for LOOP_PHI_NODE.  */
1543 static tree
1544 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1545 {
1546   tree res;
1547   struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1548   tree init_cond;
1550   if (phi_loop != loop)
1551     {
1552       struct loop *subloop;
1553       tree evolution_fn = analyze_scalar_evolution
1554         (phi_loop, PHI_RESULT (loop_phi_node));
1556       /* Dive one level deeper.  */
1557       subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1559       /* Interpret the subloop.  */
1560       res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1561       return res;
1562     }
1564   /* Otherwise really interpret the loop phi.  */
1565   init_cond = analyze_initial_condition (loop_phi_node);
1566   res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1568   return res;
1569 }
1571 /* This function merges the branches of a condition-phi-node,
1572    contained in the outermost loop, and whose arguments are already
1573    analyzed.  */
1575 static tree
1576 interpret_condition_phi (struct loop *loop, tree condition_phi)
1577 {
1578   int i;
1579   tree res = chrec_not_analyzed_yet;
1581   for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1582     {
1583       tree branch_chrec;
1585       if (backedge_phi_arg_p (condition_phi, i))
1586         {
1587           res = chrec_dont_know;
1588           break;
1589         }
1591       branch_chrec = analyze_scalar_evolution
1592         (loop, PHI_ARG_DEF (condition_phi, i));
1594       res = chrec_merge (res, branch_chrec);
1595     }
1597   return res;
1598 }
1600 /* Interpret the right hand side of a GIMPLE_MODIFY_STMT OPND1.  If we didn't
1601    analyze this node before, follow the definitions until ending
1602    either on an analyzed GIMPLE_MODIFY_STMT, or on a loop-phi-node.  On the
1603    return path, this function propagates evolutions (ala constant copy
1604    propagation).  OPND1 is not a GIMPLE expression because we could
1605    analyze the effect of an inner loop: see interpret_loop_phi.  */
1607 static tree
1608 interpret_rhs_modify_stmt (struct loop *loop, tree at_stmt,
1609                                   tree opnd1, tree type)
1610 {
1611   tree res, opnd10, opnd11, chrec10, chrec11;
1613   if (is_gimple_min_invariant (opnd1))
1614     return chrec_convert (type, opnd1, at_stmt);
1616   switch (TREE_CODE (opnd1))
1617     {
1618     case POINTER_PLUS_EXPR:
1619       opnd10 = TREE_OPERAND (opnd1, 0);
1620       opnd11 = TREE_OPERAND (opnd1, 1);
1621       chrec10 = analyze_scalar_evolution (loop, opnd10);
1622       chrec11 = analyze_scalar_evolution (loop, opnd11);
1623       chrec10 = chrec_convert (type, chrec10, at_stmt);
1624       chrec11 = chrec_convert (sizetype, chrec11, at_stmt);
1625       res = chrec_fold_plus (type, chrec10, chrec11);
1626       break;
1628     case PLUS_EXPR:
1629       opnd10 = TREE_OPERAND (opnd1, 0);
1630       opnd11 = TREE_OPERAND (opnd1, 1);
1631       chrec10 = analyze_scalar_evolution (loop, opnd10);
1632       chrec11 = analyze_scalar_evolution (loop, opnd11);
1633       chrec10 = chrec_convert (type, chrec10, at_stmt);
1634       chrec11 = chrec_convert (type, chrec11, at_stmt);
1635       res = chrec_fold_plus (type, chrec10, chrec11);
1636       break;
1638     case MINUS_EXPR:
1639       opnd10 = TREE_OPERAND (opnd1, 0);
1640       opnd11 = TREE_OPERAND (opnd1, 1);
1641       chrec10 = analyze_scalar_evolution (loop, opnd10);
1642       chrec11 = analyze_scalar_evolution (loop, opnd11);
1643       chrec10 = chrec_convert (type, chrec10, at_stmt);
1644       chrec11 = chrec_convert (type, chrec11, at_stmt);
1645       res = chrec_fold_minus (type, chrec10, chrec11);
1646       break;
1648     case NEGATE_EXPR:
1649       opnd10 = TREE_OPERAND (opnd1, 0);
1650       chrec10 = analyze_scalar_evolution (loop, opnd10);
1651       chrec10 = chrec_convert (type, chrec10, at_stmt);
1652       /* TYPE may be integer, real or complex, so use fold_convert.  */
1653       res = chrec_fold_multiply (type, chrec10,
1654                                  fold_convert (type, integer_minus_one_node));
1655       break;
1657     case MULT_EXPR:
1658       opnd10 = TREE_OPERAND (opnd1, 0);
1659       opnd11 = TREE_OPERAND (opnd1, 1);
1660       chrec10 = analyze_scalar_evolution (loop, opnd10);
1661       chrec11 = analyze_scalar_evolution (loop, opnd11);
1662       chrec10 = chrec_convert (type, chrec10, at_stmt);
1663       chrec11 = chrec_convert (type, chrec11, at_stmt);
1664       res = chrec_fold_multiply (type, chrec10, chrec11);
1665       break;
1667     case SSA_NAME:
1668       res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
1669                            at_stmt);
1670       break;
1672     case ASSERT_EXPR:
1673       opnd10 = ASSERT_EXPR_VAR (opnd1);
1674       res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
1675                            at_stmt);
1676       break;
1678     case NOP_EXPR:
1679     case CONVERT_EXPR:
1680       opnd10 = TREE_OPERAND (opnd1, 0);
1681       chrec10 = analyze_scalar_evolution (loop, opnd10);
1682       res = chrec_convert (type, chrec10, at_stmt);
1683       break;
1685     default:
1686       res = chrec_dont_know;
1687       break;
1688     }
1690   return res;
1691 }
1693 \f
1695 /* This section contains all the entry points:
1696    - number_of_iterations_in_loop,
1697    - analyze_scalar_evolution,
1698    - instantiate_parameters.
1699 */
1701 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1702    common ancestor of DEF_LOOP and USE_LOOP.  */
1704 static tree
1705 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1706                                   struct loop *def_loop,
1707                                   tree ev)
1708 {
1709   tree res;
1710   if (def_loop == wrto_loop)
1711     return ev;
1713   def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1714   res = compute_overall_effect_of_inner_loop (def_loop, ev);
1716   return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1717 }
1719 /* Helper recursive function.  */
1721 static tree
1722 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1723 {
1724   tree def, type = TREE_TYPE (var);
1725   basic_block bb;
1726   struct loop *def_loop;
1728   if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1729     return chrec_dont_know;
1731   if (TREE_CODE (var) != SSA_NAME)
1732     return interpret_rhs_modify_stmt (loop, NULL_TREE, var, type);
1734   def = SSA_NAME_DEF_STMT (var);
1735   bb = bb_for_stmt (def);
1736   def_loop = bb ? bb->loop_father : NULL;
1738   if (bb == NULL
1739       || !flow_bb_inside_loop_p (loop, bb))
1740     {
1741       /* Keep the symbolic form.  */
1742       res = var;
1743       goto set_and_end;
1744     }
1746   if (res != chrec_not_analyzed_yet)
1747     {
1748       if (loop != bb->loop_father)
1749         res = compute_scalar_evolution_in_loop
1750             (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1752       goto set_and_end;
1753     }
1755   if (loop != def_loop)
1756     {
1757       res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1758       res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1760       goto set_and_end;
1761     }
1763   switch (TREE_CODE (def))
1764     {
1765     case GIMPLE_MODIFY_STMT:
1766       res = interpret_rhs_modify_stmt (loop, def,
1767                                        GIMPLE_STMT_OPERAND (def, 1), type);
1768       break;
1770     case PHI_NODE:
1771       if (loop_phi_node_p (def))
1772         res = interpret_loop_phi (loop, def);
1773       else
1774         res = interpret_condition_phi (loop, def);
1775       break;
1777     default:
1778       res = chrec_dont_know;
1779       break;
1780     }
1782  set_and_end:
1784   /* Keep the symbolic form.  */
1785   if (res == chrec_dont_know)
1786     res = var;
1788   if (loop == def_loop)
1789     set_scalar_evolution (var, res);
1791   return res;
1792 }
1794 /* Entry point for the scalar evolution analyzer.
1795    Analyzes and returns the scalar evolution of the ssa_name VAR.
1796    LOOP_NB is the identifier number of the loop in which the variable
1797    is used.
1799    Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1800    pointer to the statement that uses this variable, in order to
1801    determine the evolution function of the variable, use the following
1802    calls:
1804    unsigned loop_nb = loop_containing_stmt (stmt)->num;
1805    tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1806    tree chrec_instantiated = instantiate_parameters
1807    (loop_nb, chrec_with_symbols);
1808 */
1810 tree
1811 analyze_scalar_evolution (struct loop *loop, tree var)
1812 {
1813   tree res;
1815   if (dump_file && (dump_flags & TDF_DETAILS))
1816     {
1817       fprintf (dump_file, "(analyze_scalar_evolution \n");
1818       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
1819       fprintf (dump_file, "  (scalar = ");
1820       print_generic_expr (dump_file, var, 0);
1821       fprintf (dump_file, ")\n");
1822     }
1824   res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
1826   if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
1827     res = var;
1829   if (dump_file && (dump_flags & TDF_DETAILS))
1830     fprintf (dump_file, ")\n");
1832   return res;
1833 }
1835 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1836    WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1837    of VERSION).
1839    FOLDED_CASTS is set to true if resolve_mixers used
1840    chrec_convert_aggressive (TODO -- not really, we are way too conservative
1841    at the moment in order to keep things simple).  */
1843 static tree
1844 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1845                                   tree version, bool *folded_casts)
1846 {
1847   bool val = false;
1848   tree ev = version, tmp;
1850   if (folded_casts)
1851     *folded_casts = false;
1852   while (1)
1853     {
1854       tmp = analyze_scalar_evolution (use_loop, ev);
1855       ev = resolve_mixers (use_loop, tmp);
1857       if (folded_casts && tmp != ev)
1858         *folded_casts = true;
1860       if (use_loop == wrto_loop)
1861         return ev;
1863       /* If the value of the use changes in the inner loop, we cannot express
1864          its value in the outer loop (we might try to return interval chrec,
1865          but we do not have a user for it anyway)  */
1866       if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1867           || !val)
1868         return chrec_dont_know;
1870       use_loop = loop_outer (use_loop);
1871     }
1872 }
1874 /* Returns instantiated value for VERSION in CACHE.  */
1876 static tree
1877 get_instantiated_value (htab_t cache, tree version)
1878 {
1879   struct scev_info_str *info, pattern;
1881   pattern.var = version;
1882   info = (struct scev_info_str *) htab_find (cache, &pattern);
1884   if (info)
1885     return info->chrec;
1886   else
1887     return NULL_TREE;
1888 }
1890 /* Sets instantiated value for VERSION to VAL in CACHE.  */
1892 static void
1893 set_instantiated_value (htab_t cache, tree version, tree val)
1894 {
1895   struct scev_info_str *info, pattern;
1896   PTR *slot;
1898   pattern.var = version;
1899   slot = htab_find_slot (cache, &pattern, INSERT);
1901   if (!*slot)
1902     *slot = new_scev_info_str (version);
1903   info = (struct scev_info_str *) *slot;
1904   info->chrec = val;
1905 }
1907 /* Return the closed_loop_phi node for VAR.  If there is none, return
1908    NULL_TREE.  */
1910 static tree
1911 loop_closed_phi_def (tree var)
1912 {
1913   struct loop *loop;
1914   edge exit;
1915   tree phi;
1917   if (var == NULL_TREE
1918       || TREE_CODE (var) != SSA_NAME)
1919     return NULL_TREE;
1921   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
1922   exit = single_exit (loop);
1923   if (!exit)
1924     return NULL_TREE;
1926   for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1927     if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
1928       return PHI_RESULT (phi);
1930   return NULL_TREE;
1931 }
1933 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1934    with respect to LOOP.  CHREC is the chrec to instantiate.  CACHE is the cache
1935    of already instantiated values.  FLAGS modify the way chrecs are
1936    instantiated.  SIZE_EXPR is used for computing the size of the expression to
1937    be instantiated, and to stop if it exceeds some limit.  */
1939 /* Values for FLAGS.  */
1940 enum
1941 {
1942   INSERT_SUPERLOOP_CHRECS = 1,  /* Loop invariants are replaced with chrecs
1943                                    in outer loops.  */
1944   FOLD_CONVERSIONS = 2          /* The conversions that may wrap in
1945                                    signed/pointer type are folded, as long as the
1946                                    value of the chrec is preserved.  */
1947 };
1949 static tree
1950 instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache,
1951                           int size_expr)
1952 {
1953   tree res, op0, op1, op2;
1954   basic_block def_bb;
1955   struct loop *def_loop;
1956   tree type = chrec_type (chrec);
1958   /* Give up if the expression is larger than the MAX that we allow.  */
1959   if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1960     return chrec_dont_know;
1962   if (automatically_generated_chrec_p (chrec)
1963       || is_gimple_min_invariant (chrec))
1964     return chrec;
1966   switch (TREE_CODE (chrec))
1967     {
1968     case SSA_NAME:
1969       def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
1971       /* A parameter (or loop invariant and we do not want to include
1972          evolutions in outer loops), nothing to do.  */
1973       if (!def_bb
1974           || loop_depth (def_bb->loop_father) == 0
1975           || (!(flags & INSERT_SUPERLOOP_CHRECS)
1976               && !flow_bb_inside_loop_p (loop, def_bb)))
1977         return chrec;
1979       /* We cache the value of instantiated variable to avoid exponential
1980          time complexity due to reevaluations.  We also store the convenient
1981          value in the cache in order to prevent infinite recursion -- we do
1982          not want to instantiate the SSA_NAME if it is in a mixer
1983          structure.  This is used for avoiding the instantiation of
1984          recursively defined functions, such as:
1986          | a_2 -> {0, +, 1, +, a_2}_1  */
1988       res = get_instantiated_value (cache, chrec);
1989       if (res)
1990         return res;
1992       /* Store the convenient value for chrec in the structure.  If it
1993          is defined outside of the loop, we may just leave it in symbolic
1994          form, otherwise we need to admit that we do not know its behavior
1995          inside the loop.  */
1996       res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
1997       set_instantiated_value (cache, chrec, res);
1999       /* To make things even more complicated, instantiate_parameters_1
2000          calls analyze_scalar_evolution that may call # of iterations
2001          analysis that may in turn call instantiate_parameters_1 again.
2002          To prevent the infinite recursion, keep also the bitmap of
2003          ssa names that are being instantiated globally.  */
2004       if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
2005         return res;
2007       def_loop = find_common_loop (loop, def_bb->loop_father);
2009       /* If the analysis yields a parametric chrec, instantiate the
2010          result again.  */
2011       bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2012       res = analyze_scalar_evolution (def_loop, chrec);
2014       /* Don't instantiate loop-closed-ssa phi nodes.  */
2015       if (TREE_CODE (res) == SSA_NAME
2016           && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2017               || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2018                   > loop_depth (def_loop))))
2019         {
2020           if (res == chrec)
2021             res = loop_closed_phi_def (chrec);
2022           else
2023             res = chrec;
2025           if (res == NULL_TREE)
2026             res = chrec_dont_know;
2027         }
2029       else if (res != chrec_dont_know)
2030         res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
2032       bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2034       /* Store the correct value to the cache.  */
2035       set_instantiated_value (cache, chrec, res);
2036       return res;
2038     case POLYNOMIAL_CHREC:
2039       op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2040                                       flags, cache, size_expr);
2041       if (op0 == chrec_dont_know)
2042         return chrec_dont_know;
2044       op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2045                                       flags, cache, size_expr);
2046       if (op1 == chrec_dont_know)
2047         return chrec_dont_know;
2049       if (CHREC_LEFT (chrec) != op0
2050           || CHREC_RIGHT (chrec) != op1)
2051         {
2052           op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL_TREE);
2053           chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2054         }
2055       return chrec;
2057     case POINTER_PLUS_EXPR:
2058     case PLUS_EXPR:
2059       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2060                                       flags, cache, size_expr);
2061       if (op0 == chrec_dont_know)
2062         return chrec_dont_know;
2064       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2065                                       flags, cache, size_expr);
2066       if (op1 == chrec_dont_know)
2067         return chrec_dont_know;
2069       if (TREE_OPERAND (chrec, 0) != op0
2070           || TREE_OPERAND (chrec, 1) != op1)
2071         {
2072           op0 = chrec_convert (type, op0, NULL_TREE);
2073           op1 = chrec_convert_rhs (type, op1, NULL_TREE);
2074           chrec = chrec_fold_plus (type, op0, op1);
2075         }
2076       return chrec;
2078     case MINUS_EXPR:
2079       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2080                                       flags, cache, size_expr);
2081       if (op0 == chrec_dont_know)
2082         return chrec_dont_know;
2084       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2085                                       flags, cache, size_expr);
2086       if (op1 == chrec_dont_know)
2087         return chrec_dont_know;
2089       if (TREE_OPERAND (chrec, 0) != op0
2090           || TREE_OPERAND (chrec, 1) != op1)
2091         {
2092           op0 = chrec_convert (type, op0, NULL_TREE);
2093           op1 = chrec_convert (type, op1, NULL_TREE);
2094           chrec = chrec_fold_minus (type, op0, op1);
2095         }
2096       return chrec;
2098     case MULT_EXPR:
2099       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2100                                       flags, cache, size_expr);
2101       if (op0 == chrec_dont_know)
2102         return chrec_dont_know;
2104       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2105                                       flags, cache, size_expr);
2106       if (op1 == chrec_dont_know)
2107         return chrec_dont_know;
2109       if (TREE_OPERAND (chrec, 0) != op0
2110           || TREE_OPERAND (chrec, 1) != op1)
2111         {
2112           op0 = chrec_convert (type, op0, NULL_TREE);
2113           op1 = chrec_convert (type, op1, NULL_TREE);
2114           chrec = chrec_fold_multiply (type, op0, op1);
2115         }
2116       return chrec;
2118     case NOP_EXPR:
2119     case CONVERT_EXPR:
2120     case NON_LVALUE_EXPR:
2121       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2122                                       flags, cache, size_expr);
2123       if (op0 == chrec_dont_know)
2124         return chrec_dont_know;
2126       if (flags & FOLD_CONVERSIONS)
2127         {
2128           tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
2129           if (tmp)
2130             return tmp;
2131         }
2133       if (op0 == TREE_OPERAND (chrec, 0))
2134         return chrec;
2136       /* If we used chrec_convert_aggressive, we can no longer assume that
2137          signed chrecs do not overflow, as chrec_convert does, so avoid
2138          calling it in that case.  */
2139       if (flags & FOLD_CONVERSIONS)
2140         return fold_convert (TREE_TYPE (chrec), op0);
2142       return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
2144     case SCEV_NOT_KNOWN:
2145       return chrec_dont_know;
2147     case SCEV_KNOWN:
2148       return chrec_known;
2150     default:
2151       break;
2152     }
2154   gcc_assert (!VL_EXP_CLASS_P (chrec));
2155   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2156     {
2157     case 3:
2158       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2159                                       flags, cache, size_expr);
2160       if (op0 == chrec_dont_know)
2161         return chrec_dont_know;
2163       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2164                                       flags, cache, size_expr);
2165       if (op1 == chrec_dont_know)
2166         return chrec_dont_know;
2168       op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2169                                       flags, cache, size_expr);
2170       if (op2 == chrec_dont_know)
2171         return chrec_dont_know;
2173       if (op0 == TREE_OPERAND (chrec, 0)
2174           && op1 == TREE_OPERAND (chrec, 1)
2175           && op2 == TREE_OPERAND (chrec, 2))
2176         return chrec;
2178       return fold_build3 (TREE_CODE (chrec),
2179                           TREE_TYPE (chrec), op0, op1, op2);
2181     case 2:
2182       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2183                                       flags, cache, size_expr);
2184       if (op0 == chrec_dont_know)
2185         return chrec_dont_know;
2187       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2188                                       flags, cache, size_expr);
2189       if (op1 == chrec_dont_know)
2190         return chrec_dont_know;
2192       if (op0 == TREE_OPERAND (chrec, 0)
2193           && op1 == TREE_OPERAND (chrec, 1))
2194         return chrec;
2195       return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2197     case 1:
2198       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2199                                       flags, cache, size_expr);
2200       if (op0 == chrec_dont_know)
2201         return chrec_dont_know;
2202       if (op0 == TREE_OPERAND (chrec, 0))
2203         return chrec;
2204       return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2206     case 0:
2207       return chrec;
2209     default:
2210       break;
2211     }
2213   /* Too complicated to handle.  */
2214   return chrec_dont_know;
2215 }
2217 /* Analyze all the parameters of the chrec that were left under a
2218    symbolic form.  LOOP is the loop in which symbolic names have to
2219    be analyzed and instantiated.  */
2221 tree
2222 instantiate_parameters (struct loop *loop,
2223                         tree chrec)
2224 {
2225   tree res;
2226   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2228   if (dump_file && (dump_flags & TDF_DETAILS))
2229     {
2230       fprintf (dump_file, "(instantiate_parameters \n");
2231       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
2232       fprintf (dump_file, "  (chrec = ");
2233       print_generic_expr (dump_file, chrec, 0);
2234       fprintf (dump_file, ")\n");
2235     }
2237   res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
2238                                   0);
2240   if (dump_file && (dump_flags & TDF_DETAILS))
2241     {
2242       fprintf (dump_file, "  (res = ");
2243       print_generic_expr (dump_file, res, 0);
2244       fprintf (dump_file, "))\n");
2245     }
2247   htab_delete (cache);
2249   return res;
2250 }
2252 /* Similar to instantiate_parameters, but does not introduce the
2253    evolutions in outer loops for LOOP invariants in CHREC, and does not
2254    care about causing overflows, as long as they do not affect value
2255    of an expression.  */
2257 tree
2258 resolve_mixers (struct loop *loop, tree chrec)
2259 {
2260   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2261   tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0);
2262   htab_delete (cache);
2263   return ret;
2264 }
2266 /* Entry point for the analysis of the number of iterations pass.
2267    This function tries to safely approximate the number of iterations
2268    the loop will run.  When this property is not decidable at compile
2269    time, the result is chrec_dont_know.  Otherwise the result is
2270    a scalar or a symbolic parameter.
2272    Example of analysis: suppose that the loop has an exit condition:
2274    "if (b > 49) goto end_loop;"
2276    and that in a previous analysis we have determined that the
2277    variable 'b' has an evolution function:
2279    "EF = {23, +, 5}_2".
2281    When we evaluate the function at the point 5, i.e. the value of the
2282    variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2283    and EF (6) = 53.  In this case the value of 'b' on exit is '53' and
2284    the loop body has been executed 6 times.  */
2286 tree
2287 number_of_latch_executions (struct loop *loop)
2288 {
2289   tree res, type;
2290   edge exit;
2291   struct tree_niter_desc niter_desc;
2293   /* Determine whether the number_of_iterations_in_loop has already
2294      been computed.  */
2295   res = loop->nb_iterations;
2296   if (res)
2297     return res;
2298   res = chrec_dont_know;
2300   if (dump_file && (dump_flags & TDF_DETAILS))
2301     fprintf (dump_file, "(number_of_iterations_in_loop\n");
2303   exit = single_exit (loop);
2304   if (!exit)
2305     goto end;
2307   if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2308     goto end;
2310   type = TREE_TYPE (niter_desc.niter);
2311   if (integer_nonzerop (niter_desc.may_be_zero))
2312     res = build_int_cst (type, 0);
2313   else if (integer_zerop (niter_desc.may_be_zero))
2314     res = niter_desc.niter;
2315   else
2316     res = chrec_dont_know;
2318 end:
2319   return set_nb_iterations_in_loop (loop, res);
2320 }
2322 /* Returns the number of executions of the exit condition of LOOP,
2323    i.e., the number by one higher than number_of_latch_executions.
2324    Note that unline number_of_latch_executions, this number does
2325    not necessarily fit in the unsigned variant of the type of
2326    the control variable -- if the number of iterations is a constant,
2327    we return chrec_dont_know if adding one to number_of_latch_executions
2328    overflows; however, in case the number of iterations is symbolic
2329    expression, the caller is responsible for dealing with this
2330    the possible overflow.  */
2332 tree
2333 number_of_exit_cond_executions (struct loop *loop)
2334 {
2335   tree ret = number_of_latch_executions (loop);
2336   tree type = chrec_type (ret);
2338   if (chrec_contains_undetermined (ret))
2339     return ret;
2341   ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
2342   if (TREE_CODE (ret) == INTEGER_CST
2343       && TREE_OVERFLOW (ret))
2344     return chrec_dont_know;
2346   return ret;
2347 }
2349 /* One of the drivers for testing the scalar evolutions analysis.
2350    This function computes the number of iterations for all the loops
2351    from the EXIT_CONDITIONS array.  */
2353 static void
2354 number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2355 {
2356   unsigned int i;
2357   unsigned nb_chrec_dont_know_loops = 0;
2358   unsigned nb_static_loops = 0;
2359   tree cond;
2361   for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2362     {
2363       tree res = number_of_latch_executions (loop_containing_stmt (cond));
2364       if (chrec_contains_undetermined (res))
2365         nb_chrec_dont_know_loops++;
2366       else
2367         nb_static_loops++;
2368     }
2370   if (dump_file)
2371     {
2372       fprintf (dump_file, "\n(\n");
2373       fprintf (dump_file, "-----------------------------------------\n");
2374       fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2375       fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2376       fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2377       fprintf (dump_file, "-----------------------------------------\n");
2378       fprintf (dump_file, ")\n\n");
2380       print_loops (dump_file, 3);
2381     }
2382 }
2384 \f
2386 /* Counters for the stats.  */
2388 struct chrec_stats
2389 {
2390   unsigned nb_chrecs;
2391   unsigned nb_affine;
2392   unsigned nb_affine_multivar;
2393   unsigned nb_higher_poly;
2394   unsigned nb_chrec_dont_know;
2395   unsigned nb_undetermined;
2396 };
2398 /* Reset the counters.  */
2400 static inline void
2401 reset_chrecs_counters (struct chrec_stats *stats)
2402 {
2403   stats->nb_chrecs = 0;
2404   stats->nb_affine = 0;
2405   stats->nb_affine_multivar = 0;
2406   stats->nb_higher_poly = 0;
2407   stats->nb_chrec_dont_know = 0;
2408   stats->nb_undetermined = 0;
2409 }
2411 /* Dump the contents of a CHREC_STATS structure.  */
2413 static void
2414 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2415 {
2416   fprintf (file, "\n(\n");
2417   fprintf (file, "-----------------------------------------\n");
2418   fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2419   fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2420   fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2421            stats->nb_higher_poly);
2422   fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2423   fprintf (file, "-----------------------------------------\n");
2424   fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2425   fprintf (file, "%d\twith undetermined coefficients\n",
2426            stats->nb_undetermined);
2427   fprintf (file, "-----------------------------------------\n");
2428   fprintf (file, "%d\tchrecs in the scev database\n",
2429            (int) htab_elements (scalar_evolution_info));
2430   fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2431   fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2432   fprintf (file, "-----------------------------------------\n");
2433   fprintf (file, ")\n\n");
2434 }
2436 /* Gather statistics about CHREC.  */
2438 static void
2439 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2440 {
2441   if (dump_file && (dump_flags & TDF_STATS))
2442     {
2443       fprintf (dump_file, "(classify_chrec ");
2444       print_generic_expr (dump_file, chrec, 0);
2445       fprintf (dump_file, "\n");
2446     }
2448   stats->nb_chrecs++;
2450   if (chrec == NULL_TREE)
2451     {
2452       stats->nb_undetermined++;
2453       return;
2454     }
2456   switch (TREE_CODE (chrec))
2457     {
2458     case POLYNOMIAL_CHREC:
2459       if (evolution_function_is_affine_p (chrec))
2460         {
2461           if (dump_file && (dump_flags & TDF_STATS))
2462             fprintf (dump_file, "  affine_univariate\n");
2463           stats->nb_affine++;
2464         }
2465       else if (evolution_function_is_affine_multivariate_p (chrec, 0))
2466         {
2467           if (dump_file && (dump_flags & TDF_STATS))
2468             fprintf (dump_file, "  affine_multivariate\n");
2469           stats->nb_affine_multivar++;
2470         }
2471       else
2472         {
2473           if (dump_file && (dump_flags & TDF_STATS))
2474             fprintf (dump_file, "  higher_degree_polynomial\n");
2475           stats->nb_higher_poly++;
2476         }
2478       break;
2480     default:
2481       break;
2482     }
2484   if (chrec_contains_undetermined (chrec))
2485     {
2486       if (dump_file && (dump_flags & TDF_STATS))
2487         fprintf (dump_file, "  undetermined\n");
2488       stats->nb_undetermined++;
2489     }
2491   if (dump_file && (dump_flags & TDF_STATS))
2492     fprintf (dump_file, ")\n");
2493 }
2495 /* One of the drivers for testing the scalar evolutions analysis.
2496    This function analyzes the scalar evolution of all the scalars
2497    defined as loop phi nodes in one of the loops from the
2498    EXIT_CONDITIONS array.
2500    TODO Optimization: A loop is in canonical form if it contains only
2501    a single scalar loop phi node.  All the other scalars that have an
2502    evolution in the loop are rewritten in function of this single
2503    index.  This allows the parallelization of the loop.  */
2505 static void
2506 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2507 {
2508   unsigned int i;
2509   struct chrec_stats stats;
2510   tree cond;
2512   reset_chrecs_counters (&stats);
2514   for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2515     {
2516       struct loop *loop;
2517       basic_block bb;
2518       tree phi, chrec;
2520       loop = loop_containing_stmt (cond);
2521       bb = loop->header;
2523       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2524         if (is_gimple_reg (PHI_RESULT (phi)))
2525           {
2526             chrec = instantiate_parameters
2527               (loop,
2528                analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2530             if (dump_file && (dump_flags & TDF_STATS))
2531               gather_chrec_stats (chrec, &stats);
2532           }
2533     }
2535   if (dump_file && (dump_flags & TDF_STATS))
2536     dump_chrecs_stats (dump_file, &stats);
2537 }
2539 /* Callback for htab_traverse, gathers information on chrecs in the
2540    hashtable.  */
2542 static int
2543 gather_stats_on_scev_database_1 (void **slot, void *stats)
2544 {
2545   struct scev_info_str *entry = (struct scev_info_str *) *slot;
2547   gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2549   return 1;
2550 }
2552 /* Classify the chrecs of the whole database.  */
2554 void
2555 gather_stats_on_scev_database (void)
2556 {
2557   struct chrec_stats stats;
2559   if (!dump_file)
2560     return;
2562   reset_chrecs_counters (&stats);
2564   htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2565                  &stats);
2567   dump_chrecs_stats (dump_file, &stats);
2568 }
2570 \f
2572 /* Initializer.  */
2574 static void
2575 initialize_scalar_evolutions_analyzer (void)
2576 {
2577   /* The elements below are unique.  */
2578   if (chrec_dont_know == NULL_TREE)
2579     {
2580       chrec_not_analyzed_yet = NULL_TREE;
2581       chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2582       chrec_known = make_node (SCEV_KNOWN);
2583       TREE_TYPE (chrec_dont_know) = void_type_node;
2584       TREE_TYPE (chrec_known) = void_type_node;
2585     }
2586 }
2588 /* Initialize the analysis of scalar evolutions for LOOPS.  */
2590 void
2591 scev_initialize (void)
2592 {
2593   loop_iterator li;
2594   struct loop *loop;
2596   scalar_evolution_info = htab_create_alloc (100,
2597                                              hash_scev_info,
2598                                              eq_scev_info,
2599                                              del_scev_info,
2600                                              ggc_calloc,
2601                                              ggc_free);
2602   already_instantiated = BITMAP_ALLOC (NULL);
2604   initialize_scalar_evolutions_analyzer ();
2606   FOR_EACH_LOOP (li, loop, 0)
2607     {
2608       loop->nb_iterations = NULL_TREE;
2609     }
2610 }
2612 /* Clean the scalar evolution analysis cache, but preserve the cached
2613    numbers of iterations for the loops.  */
2615 void
2616 scev_reset_except_niters (void)
2617 {
2618   if (scalar_evolution_info)
2619     htab_empty (scalar_evolution_info);
2620 }
2622 /* Cleans up the information cached by the scalar evolutions analysis.  */
2624 void
2625 scev_reset (void)
2626 {
2627   loop_iterator li;
2628   struct loop *loop;
2630   if (!scalar_evolution_info || !current_loops)
2631     return;
2633   scev_reset_except_niters ();
2635   FOR_EACH_LOOP (li, loop, 0)
2636     {
2637       loop->nb_iterations = NULL_TREE;
2638     }
2639 }
2641 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2642    its base and step in IV if possible.  If ALLOW_NONCONSTANT_STEP is true, we
2643    want step to be invariant in LOOP.  Otherwise we require it to be an
2644    integer constant.  IV->no_overflow is set to true if we are sure the iv cannot
2645    overflow (e.g.  because it is computed in signed arithmetics).  */
2647 bool
2648 simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
2649            bool allow_nonconstant_step)
2650 {
2651   basic_block bb = bb_for_stmt (stmt);
2652   tree type, ev;
2653   bool folded_casts;
2655   iv->base = NULL_TREE;
2656   iv->step = NULL_TREE;
2657   iv->no_overflow = false;
2659   type = TREE_TYPE (op);
2660   if (TREE_CODE (type) != INTEGER_TYPE
2661       && TREE_CODE (type) != POINTER_TYPE)
2662     return false;
2664   ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
2665                                          &folded_casts);
2666   if (chrec_contains_undetermined (ev))
2667     return false;
2669   if (tree_does_not_contain_chrecs (ev)
2670       && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2671     {
2672       iv->base = ev;
2673       iv->step = build_int_cst (TREE_TYPE (ev), 0);
2674       iv->no_overflow = true;
2675       return true;
2676     }
2678   if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2679       || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2680     return false;
2682   iv->step = CHREC_RIGHT (ev);
2683   if (allow_nonconstant_step)
2684     {
2685       if (tree_contains_chrecs (iv->step, NULL)
2686           || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
2687         return false;
2688     }
2689   else if (TREE_CODE (iv->step) != INTEGER_CST)
2690     return false;
2692   iv->base = CHREC_LEFT (ev);
2693   if (tree_contains_chrecs (iv->base, NULL)
2694       || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
2695     return false;
2697   iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
2699   return true;
2700 }
2702 /* Runs the analysis of scalar evolutions.  */
2704 void
2705 scev_analysis (void)
2706 {
2707   VEC(tree,heap) *exit_conditions;
2709   exit_conditions = VEC_alloc (tree, heap, 37);
2710   select_loops_exit_conditions (&exit_conditions);
2712   if (dump_file && (dump_flags & TDF_STATS))
2713     analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2715   number_of_iterations_for_all_loops (&exit_conditions);
2716   VEC_free (tree, heap, exit_conditions);
2717 }
2719 /* Finalize the scalar evolution analysis.  */
2721 void
2722 scev_finalize (void)
2723 {
2724   if (!scalar_evolution_info)
2725     return;
2726   htab_delete (scalar_evolution_info);
2727   BITMAP_FREE (already_instantiated);
2728   scalar_evolution_info = NULL;
2729 }
2731 /* Replace ssa names for that scev can prove they are constant by the
2732    appropriate constants.  Also perform final value replacement in loops,
2733    in case the replacement expressions are cheap.
2735    We only consider SSA names defined by phi nodes; rest is left to the
2736    ordinary constant propagation pass.  */
2738 unsigned int
2739 scev_const_prop (void)
2740 {
2741   basic_block bb;
2742   tree name, phi, next_phi, type, ev;
2743   struct loop *loop, *ex_loop;
2744   bitmap ssa_names_to_remove = NULL;
2745   unsigned i;
2746   loop_iterator li;
2748   if (number_of_loops () <= 1)
2749     return 0;
2751   FOR_EACH_BB (bb)
2752     {
2753       loop = bb->loop_father;
2755       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2756         {
2757           name = PHI_RESULT (phi);
2759           if (!is_gimple_reg (name))
2760             continue;
2762           type = TREE_TYPE (name);
2764           if (!POINTER_TYPE_P (type)
2765               && !INTEGRAL_TYPE_P (type))
2766             continue;
2768           ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2769           if (!is_gimple_min_invariant (ev)
2770               || !may_propagate_copy (name, ev))
2771             continue;
2773           /* Replace the uses of the name.  */
2774           if (name != ev)
2775             replace_uses_by (name, ev);
2777           if (!ssa_names_to_remove)
2778             ssa_names_to_remove = BITMAP_ALLOC (NULL);
2779           bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
2780         }
2781     }
2783   /* Remove the ssa names that were replaced by constants.  We do not
2784      remove them directly in the previous cycle, since this
2785      invalidates scev cache.  */
2786   if (ssa_names_to_remove)
2787     {
2788       bitmap_iterator bi;
2790       EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
2791         {
2792           name = ssa_name (i);
2793           phi = SSA_NAME_DEF_STMT (name);
2795           gcc_assert (TREE_CODE (phi) == PHI_NODE);
2796           remove_phi_node (phi, NULL, true);
2797         }
2799       BITMAP_FREE (ssa_names_to_remove);
2800       scev_reset ();
2801     }
2803   /* Now the regular final value replacement.  */
2804   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
2805     {
2806       edge exit;
2807       tree def, rslt, ass, niter;
2808       block_stmt_iterator bsi;
2810       /* If we do not know exact number of iterations of the loop, we cannot
2811          replace the final value.  */
2812       exit = single_exit (loop);
2813       if (!exit)
2814         continue;
2816       niter = number_of_latch_executions (loop);
2817       /* We used to check here whether the computation of NITER is expensive,
2818          and avoided final value elimination if that is the case.  The problem
2819          is that it is hard to evaluate whether the expression is too
2820          expensive, as we do not know what optimization opportunities the
2821          the elimination of the final value may reveal.  Therefore, we now
2822          eliminate the final values of induction variables unconditionally.  */
2823       if (niter == chrec_dont_know)
2824         continue;
2826       /* Ensure that it is possible to insert new statements somewhere.  */
2827       if (!single_pred_p (exit->dest))
2828         split_loop_exit_edge (exit);
2829       bsi = bsi_after_labels (exit->dest);
2831       ex_loop = superloop_at_depth (loop,
2832                                     loop_depth (exit->dest->loop_father) + 1);
2834       for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
2835         {
2836           next_phi = PHI_CHAIN (phi);
2837           rslt = PHI_RESULT (phi);
2838           def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2839           if (!is_gimple_reg (def))
2840             continue;
2842           if (!POINTER_TYPE_P (TREE_TYPE (def))
2843               && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
2844             continue;
2846           def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
2847           def = compute_overall_effect_of_inner_loop (ex_loop, def);
2848           if (!tree_does_not_contain_chrecs (def)
2849               || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
2850               /* Moving the computation from the loop may prolong life range
2851                  of some ssa names, which may cause problems if they appear
2852                  on abnormal edges.  */
2853               || contains_abnormal_ssa_name_p (def))
2854             continue;
2856           /* Eliminate the PHI node and replace it by a computation outside
2857              the loop.  */
2858           def = unshare_expr (def);
2859           remove_phi_node (phi, NULL_TREE, false);
2861           ass = build_gimple_modify_stmt (rslt, NULL_TREE);
2862           SSA_NAME_DEF_STMT (rslt) = ass;
2863           {
2864             block_stmt_iterator dest = bsi;
2865             bsi_insert_before (&dest, ass, BSI_NEW_STMT);
2866             def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE,
2867                                             true, BSI_SAME_STMT);
2868           }
2869           GIMPLE_STMT_OPERAND (ass, 1) = def;
2870           update_stmt (ass);
2871         }
2872     }
2873   return 0;
2874 }
2876 #include "gt-tree-scalar-evolution.h"
About OSDN
Find Software
Develop Software