ad8f2f0f190b2b3f65bcea2f535a3637c4d61515
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           || (!(flags & INSERT_SUPERLOOP_CHRECS)
1975               && !flow_bb_inside_loop_p (loop, def_bb)))
1976         return chrec;
1978       /* We cache the value of instantiated variable to avoid exponential
1979          time complexity due to reevaluations.  We also store the convenient
1980          value in the cache in order to prevent infinite recursion -- we do
1981          not want to instantiate the SSA_NAME if it is in a mixer
1982          structure.  This is used for avoiding the instantiation of
1983          recursively defined functions, such as:
1985          | a_2 -> {0, +, 1, +, a_2}_1  */
1987       res = get_instantiated_value (cache, chrec);
1988       if (res)
1989         return res;
1991       /* Store the convenient value for chrec in the structure.  If it
1992          is defined outside of the loop, we may just leave it in symbolic
1993          form, otherwise we need to admit that we do not know its behavior
1994          inside the loop.  */
1995       res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
1996       set_instantiated_value (cache, chrec, res);
1998       /* To make things even more complicated, instantiate_parameters_1
1999          calls analyze_scalar_evolution that may call # of iterations
2000          analysis that may in turn call instantiate_parameters_1 again.
2001          To prevent the infinite recursion, keep also the bitmap of
2002          ssa names that are being instantiated globally.  */
2003       if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
2004         return res;
2006       def_loop = find_common_loop (loop, def_bb->loop_father);
2008       /* If the analysis yields a parametric chrec, instantiate the
2009          result again.  */
2010       bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2011       res = analyze_scalar_evolution (def_loop, chrec);
2013       /* Don't instantiate loop-closed-ssa phi nodes.  */
2014       if (TREE_CODE (res) == SSA_NAME
2015           && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2016               || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2017                   > loop_depth (def_loop))))
2018         {
2019           if (res == chrec)
2020             res = loop_closed_phi_def (chrec);
2021           else
2022             res = chrec;
2024           if (res == NULL_TREE)
2025             res = chrec_dont_know;
2026         }
2028       else if (res != chrec_dont_know)
2029         res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
2031       bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2033       /* Store the correct value to the cache.  */
2034       set_instantiated_value (cache, chrec, res);
2035       return res;
2037     case POLYNOMIAL_CHREC:
2038       op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2039                                       flags, cache, size_expr);
2040       if (op0 == chrec_dont_know)
2041         return chrec_dont_know;
2043       op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2044                                       flags, cache, size_expr);
2045       if (op1 == chrec_dont_know)
2046         return chrec_dont_know;
2048       if (CHREC_LEFT (chrec) != op0
2049           || CHREC_RIGHT (chrec) != op1)
2050         {
2051           op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL_TREE);
2052           chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2053         }
2054       return chrec;
2056     case POINTER_PLUS_EXPR:
2057     case PLUS_EXPR:
2058       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2059                                       flags, cache, size_expr);
2060       if (op0 == chrec_dont_know)
2061         return chrec_dont_know;
2063       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2064                                       flags, cache, size_expr);
2065       if (op1 == chrec_dont_know)
2066         return chrec_dont_know;
2068       if (TREE_OPERAND (chrec, 0) != op0
2069           || TREE_OPERAND (chrec, 1) != op1)
2070         {
2071           op0 = chrec_convert (type, op0, NULL_TREE);
2072           op1 = chrec_convert_rhs (type, op1, NULL_TREE);
2073           chrec = chrec_fold_plus (type, op0, op1);
2074         }
2075       return chrec;
2077     case MINUS_EXPR:
2078       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2079                                       flags, cache, size_expr);
2080       if (op0 == chrec_dont_know)
2081         return chrec_dont_know;
2083       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2084                                       flags, cache, size_expr);
2085       if (op1 == chrec_dont_know)
2086         return chrec_dont_know;
2088       if (TREE_OPERAND (chrec, 0) != op0
2089           || TREE_OPERAND (chrec, 1) != op1)
2090         {
2091           op0 = chrec_convert (type, op0, NULL_TREE);
2092           op1 = chrec_convert (type, op1, NULL_TREE);
2093           chrec = chrec_fold_minus (type, op0, op1);
2094         }
2095       return chrec;
2097     case MULT_EXPR:
2098       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2099                                       flags, cache, size_expr);
2100       if (op0 == chrec_dont_know)
2101         return chrec_dont_know;
2103       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2104                                       flags, cache, size_expr);
2105       if (op1 == chrec_dont_know)
2106         return chrec_dont_know;
2108       if (TREE_OPERAND (chrec, 0) != op0
2109           || TREE_OPERAND (chrec, 1) != op1)
2110         {
2111           op0 = chrec_convert (type, op0, NULL_TREE);
2112           op1 = chrec_convert (type, op1, NULL_TREE);
2113           chrec = chrec_fold_multiply (type, op0, op1);
2114         }
2115       return chrec;
2117     case NOP_EXPR:
2118     case CONVERT_EXPR:
2119     case NON_LVALUE_EXPR:
2120       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2121                                       flags, cache, size_expr);
2122       if (op0 == chrec_dont_know)
2123         return chrec_dont_know;
2125       if (flags & FOLD_CONVERSIONS)
2126         {
2127           tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
2128           if (tmp)
2129             return tmp;
2130         }
2132       if (op0 == TREE_OPERAND (chrec, 0))
2133         return chrec;
2135       /* If we used chrec_convert_aggressive, we can no longer assume that
2136          signed chrecs do not overflow, as chrec_convert does, so avoid
2137          calling it in that case.  */
2138       if (flags & FOLD_CONVERSIONS)
2139         return fold_convert (TREE_TYPE (chrec), op0);
2141       return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
2143     case SCEV_NOT_KNOWN:
2144       return chrec_dont_know;
2146     case SCEV_KNOWN:
2147       return chrec_known;
2149     default:
2150       break;
2151     }
2153   gcc_assert (!VL_EXP_CLASS_P (chrec));
2154   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2155     {
2156     case 3:
2157       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2158                                       flags, cache, size_expr);
2159       if (op0 == chrec_dont_know)
2160         return chrec_dont_know;
2162       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2163                                       flags, cache, size_expr);
2164       if (op1 == chrec_dont_know)
2165         return chrec_dont_know;
2167       op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2168                                       flags, cache, size_expr);
2169       if (op2 == chrec_dont_know)
2170         return chrec_dont_know;
2172       if (op0 == TREE_OPERAND (chrec, 0)
2173           && op1 == TREE_OPERAND (chrec, 1)
2174           && op2 == TREE_OPERAND (chrec, 2))
2175         return chrec;
2177       return fold_build3 (TREE_CODE (chrec),
2178                           TREE_TYPE (chrec), op0, op1, op2);
2180     case 2:
2181       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2182                                       flags, cache, size_expr);
2183       if (op0 == chrec_dont_know)
2184         return chrec_dont_know;
2186       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2187                                       flags, cache, size_expr);
2188       if (op1 == chrec_dont_know)
2189         return chrec_dont_know;
2191       if (op0 == TREE_OPERAND (chrec, 0)
2192           && op1 == TREE_OPERAND (chrec, 1))
2193         return chrec;
2194       return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2196     case 1:
2197       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2198                                       flags, cache, size_expr);
2199       if (op0 == chrec_dont_know)
2200         return chrec_dont_know;
2201       if (op0 == TREE_OPERAND (chrec, 0))
2202         return chrec;
2203       return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2205     case 0:
2206       return chrec;
2208     default:
2209       break;
2210     }
2212   /* Too complicated to handle.  */
2213   return chrec_dont_know;
2214 }
2216 /* Analyze all the parameters of the chrec that were left under a
2217    symbolic form.  LOOP is the loop in which symbolic names have to
2218    be analyzed and instantiated.  */
2220 tree
2221 instantiate_parameters (struct loop *loop,
2222                         tree chrec)
2223 {
2224   tree res;
2225   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2227   if (dump_file && (dump_flags & TDF_DETAILS))
2228     {
2229       fprintf (dump_file, "(instantiate_parameters \n");
2230       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
2231       fprintf (dump_file, "  (chrec = ");
2232       print_generic_expr (dump_file, chrec, 0);
2233       fprintf (dump_file, ")\n");
2234     }
2236   res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
2237                                   0);
2239   if (dump_file && (dump_flags & TDF_DETAILS))
2240     {
2241       fprintf (dump_file, "  (res = ");
2242       print_generic_expr (dump_file, res, 0);
2243       fprintf (dump_file, "))\n");
2244     }
2246   htab_delete (cache);
2248   return res;
2249 }
2251 /* Similar to instantiate_parameters, but does not introduce the
2252    evolutions in outer loops for LOOP invariants in CHREC, and does not
2253    care about causing overflows, as long as they do not affect value
2254    of an expression.  */
2256 tree
2257 resolve_mixers (struct loop *loop, tree chrec)
2258 {
2259   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2260   tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0);
2261   htab_delete (cache);
2262   return ret;
2263 }
2265 /* Entry point for the analysis of the number of iterations pass.
2266    This function tries to safely approximate the number of iterations
2267    the loop will run.  When this property is not decidable at compile
2268    time, the result is chrec_dont_know.  Otherwise the result is
2269    a scalar or a symbolic parameter.
2271    Example of analysis: suppose that the loop has an exit condition:
2273    "if (b > 49) goto end_loop;"
2275    and that in a previous analysis we have determined that the
2276    variable 'b' has an evolution function:
2278    "EF = {23, +, 5}_2".
2280    When we evaluate the function at the point 5, i.e. the value of the
2281    variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2282    and EF (6) = 53.  In this case the value of 'b' on exit is '53' and
2283    the loop body has been executed 6 times.  */
2285 tree
2286 number_of_latch_executions (struct loop *loop)
2287 {
2288   tree res, type;
2289   edge exit;
2290   struct tree_niter_desc niter_desc;
2292   /* Determine whether the number_of_iterations_in_loop has already
2293      been computed.  */
2294   res = loop->nb_iterations;
2295   if (res)
2296     return res;
2297   res = chrec_dont_know;
2299   if (dump_file && (dump_flags & TDF_DETAILS))
2300     fprintf (dump_file, "(number_of_iterations_in_loop\n");
2302   exit = single_exit (loop);
2303   if (!exit)
2304     goto end;
2306   if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2307     goto end;
2309   type = TREE_TYPE (niter_desc.niter);
2310   if (integer_nonzerop (niter_desc.may_be_zero))
2311     res = build_int_cst (type, 0);
2312   else if (integer_zerop (niter_desc.may_be_zero))
2313     res = niter_desc.niter;
2314   else
2315     res = chrec_dont_know;
2317 end:
2318   return set_nb_iterations_in_loop (loop, res);
2319 }
2321 /* Returns the number of executions of the exit condition of LOOP,
2322    i.e., the number by one higher than number_of_latch_executions.
2323    Note that unline number_of_latch_executions, this number does
2324    not necessarily fit in the unsigned variant of the type of
2325    the control variable -- if the number of iterations is a constant,
2326    we return chrec_dont_know if adding one to number_of_latch_executions
2327    overflows; however, in case the number of iterations is symbolic
2328    expression, the caller is responsible for dealing with this
2329    the possible overflow.  */
2331 tree
2332 number_of_exit_cond_executions (struct loop *loop)
2333 {
2334   tree ret = number_of_latch_executions (loop);
2335   tree type = chrec_type (ret);
2337   if (chrec_contains_undetermined (ret))
2338     return ret;
2340   ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
2341   if (TREE_CODE (ret) == INTEGER_CST
2342       && TREE_OVERFLOW (ret))
2343     return chrec_dont_know;
2345   return ret;
2346 }
2348 /* One of the drivers for testing the scalar evolutions analysis.
2349    This function computes the number of iterations for all the loops
2350    from the EXIT_CONDITIONS array.  */
2352 static void
2353 number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2354 {
2355   unsigned int i;
2356   unsigned nb_chrec_dont_know_loops = 0;
2357   unsigned nb_static_loops = 0;
2358   tree cond;
2360   for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2361     {
2362       tree res = number_of_latch_executions (loop_containing_stmt (cond));
2363       if (chrec_contains_undetermined (res))
2364         nb_chrec_dont_know_loops++;
2365       else
2366         nb_static_loops++;
2367     }
2369   if (dump_file)
2370     {
2371       fprintf (dump_file, "\n(\n");
2372       fprintf (dump_file, "-----------------------------------------\n");
2373       fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2374       fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2375       fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2376       fprintf (dump_file, "-----------------------------------------\n");
2377       fprintf (dump_file, ")\n\n");
2379       print_loops (dump_file, 3);
2380     }
2381 }
2383 \f
2385 /* Counters for the stats.  */
2387 struct chrec_stats
2388 {
2389   unsigned nb_chrecs;
2390   unsigned nb_affine;
2391   unsigned nb_affine_multivar;
2392   unsigned nb_higher_poly;
2393   unsigned nb_chrec_dont_know;
2394   unsigned nb_undetermined;
2395 };
2397 /* Reset the counters.  */
2399 static inline void
2400 reset_chrecs_counters (struct chrec_stats *stats)
2401 {
2402   stats->nb_chrecs = 0;
2403   stats->nb_affine = 0;
2404   stats->nb_affine_multivar = 0;
2405   stats->nb_higher_poly = 0;
2406   stats->nb_chrec_dont_know = 0;
2407   stats->nb_undetermined = 0;
2408 }
2410 /* Dump the contents of a CHREC_STATS structure.  */
2412 static void
2413 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2414 {
2415   fprintf (file, "\n(\n");
2416   fprintf (file, "-----------------------------------------\n");
2417   fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2418   fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2419   fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2420            stats->nb_higher_poly);
2421   fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2422   fprintf (file, "-----------------------------------------\n");
2423   fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2424   fprintf (file, "%d\twith undetermined coefficients\n",
2425            stats->nb_undetermined);
2426   fprintf (file, "-----------------------------------------\n");
2427   fprintf (file, "%d\tchrecs in the scev database\n",
2428            (int) htab_elements (scalar_evolution_info));
2429   fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2430   fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2431   fprintf (file, "-----------------------------------------\n");
2432   fprintf (file, ")\n\n");
2433 }
2435 /* Gather statistics about CHREC.  */
2437 static void
2438 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2439 {
2440   if (dump_file && (dump_flags & TDF_STATS))
2441     {
2442       fprintf (dump_file, "(classify_chrec ");
2443       print_generic_expr (dump_file, chrec, 0);
2444       fprintf (dump_file, "\n");
2445     }
2447   stats->nb_chrecs++;
2449   if (chrec == NULL_TREE)
2450     {
2451       stats->nb_undetermined++;
2452       return;
2453     }
2455   switch (TREE_CODE (chrec))
2456     {
2457     case POLYNOMIAL_CHREC:
2458       if (evolution_function_is_affine_p (chrec))
2459         {
2460           if (dump_file && (dump_flags & TDF_STATS))
2461             fprintf (dump_file, "  affine_univariate\n");
2462           stats->nb_affine++;
2463         }
2464       else if (evolution_function_is_affine_multivariate_p (chrec, 0))
2465         {
2466           if (dump_file && (dump_flags & TDF_STATS))
2467             fprintf (dump_file, "  affine_multivariate\n");
2468           stats->nb_affine_multivar++;
2469         }
2470       else
2471         {
2472           if (dump_file && (dump_flags & TDF_STATS))
2473             fprintf (dump_file, "  higher_degree_polynomial\n");
2474           stats->nb_higher_poly++;
2475         }
2477       break;
2479     default:
2480       break;
2481     }
2483   if (chrec_contains_undetermined (chrec))
2484     {
2485       if (dump_file && (dump_flags & TDF_STATS))
2486         fprintf (dump_file, "  undetermined\n");
2487       stats->nb_undetermined++;
2488     }
2490   if (dump_file && (dump_flags & TDF_STATS))
2491     fprintf (dump_file, ")\n");
2492 }
2494 /* One of the drivers for testing the scalar evolutions analysis.
2495    This function analyzes the scalar evolution of all the scalars
2496    defined as loop phi nodes in one of the loops from the
2497    EXIT_CONDITIONS array.
2499    TODO Optimization: A loop is in canonical form if it contains only
2500    a single scalar loop phi node.  All the other scalars that have an
2501    evolution in the loop are rewritten in function of this single
2502    index.  This allows the parallelization of the loop.  */
2504 static void
2505 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2506 {
2507   unsigned int i;
2508   struct chrec_stats stats;
2509   tree cond;
2511   reset_chrecs_counters (&stats);
2513   for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2514     {
2515       struct loop *loop;
2516       basic_block bb;
2517       tree phi, chrec;
2519       loop = loop_containing_stmt (cond);
2520       bb = loop->header;
2522       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2523         if (is_gimple_reg (PHI_RESULT (phi)))
2524           {
2525             chrec = instantiate_parameters
2526               (loop,
2527                analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2529             if (dump_file && (dump_flags & TDF_STATS))
2530               gather_chrec_stats (chrec, &stats);
2531           }
2532     }
2534   if (dump_file && (dump_flags & TDF_STATS))
2535     dump_chrecs_stats (dump_file, &stats);
2536 }
2538 /* Callback for htab_traverse, gathers information on chrecs in the
2539    hashtable.  */
2541 static int
2542 gather_stats_on_scev_database_1 (void **slot, void *stats)
2543 {
2544   struct scev_info_str *entry = (struct scev_info_str *) *slot;
2546   gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2548   return 1;
2549 }
2551 /* Classify the chrecs of the whole database.  */
2553 void
2554 gather_stats_on_scev_database (void)
2555 {
2556   struct chrec_stats stats;
2558   if (!dump_file)
2559     return;
2561   reset_chrecs_counters (&stats);
2563   htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2564                  &stats);
2566   dump_chrecs_stats (dump_file, &stats);
2567 }
2569 \f
2571 /* Initializer.  */
2573 static void
2574 initialize_scalar_evolutions_analyzer (void)
2575 {
2576   /* The elements below are unique.  */
2577   if (chrec_dont_know == NULL_TREE)
2578     {
2579       chrec_not_analyzed_yet = NULL_TREE;
2580       chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2581       chrec_known = make_node (SCEV_KNOWN);
2582       TREE_TYPE (chrec_dont_know) = void_type_node;
2583       TREE_TYPE (chrec_known) = void_type_node;
2584     }
2585 }
2587 /* Initialize the analysis of scalar evolutions for LOOPS.  */
2589 void
2590 scev_initialize (void)
2591 {
2592   loop_iterator li;
2593   struct loop *loop;
2595   scalar_evolution_info = htab_create_alloc (100,
2596                                              hash_scev_info,
2597                                              eq_scev_info,
2598                                              del_scev_info,
2599                                              ggc_calloc,
2600                                              ggc_free);
2601   already_instantiated = BITMAP_ALLOC (NULL);
2603   initialize_scalar_evolutions_analyzer ();
2605   FOR_EACH_LOOP (li, loop, 0)
2606     {
2607       loop->nb_iterations = NULL_TREE;
2608     }
2609 }
2611 /* Clean the scalar evolution analysis cache, but preserve the cached
2612    numbers of iterations for the loops.  */
2614 void
2615 scev_reset_except_niters (void)
2616 {
2617   if (scalar_evolution_info)
2618     htab_empty (scalar_evolution_info);
2619 }
2621 /* Cleans up the information cached by the scalar evolutions analysis.  */
2623 void
2624 scev_reset (void)
2625 {
2626   loop_iterator li;
2627   struct loop *loop;
2629   if (!scalar_evolution_info || !current_loops)
2630     return;
2632   scev_reset_except_niters ();
2634   FOR_EACH_LOOP (li, loop, 0)
2635     {
2636       loop->nb_iterations = NULL_TREE;
2637     }
2638 }
2640 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2641    its base and step in IV if possible.  If ALLOW_NONCONSTANT_STEP is true, we
2642    want step to be invariant in LOOP.  Otherwise we require it to be an
2643    integer constant.  IV->no_overflow is set to true if we are sure the iv cannot
2644    overflow (e.g.  because it is computed in signed arithmetics).  */
2646 bool
2647 simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
2648            bool allow_nonconstant_step)
2649 {
2650   basic_block bb = bb_for_stmt (stmt);
2651   tree type, ev;
2652   bool folded_casts;
2654   iv->base = NULL_TREE;
2655   iv->step = NULL_TREE;
2656   iv->no_overflow = false;
2658   type = TREE_TYPE (op);
2659   if (TREE_CODE (type) != INTEGER_TYPE
2660       && TREE_CODE (type) != POINTER_TYPE)
2661     return false;
2663   ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
2664                                          &folded_casts);
2665   if (chrec_contains_undetermined (ev))
2666     return false;
2668   if (tree_does_not_contain_chrecs (ev)
2669       && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2670     {
2671       iv->base = ev;
2672       iv->step = build_int_cst (TREE_TYPE (ev), 0);
2673       iv->no_overflow = true;
2674       return true;
2675     }
2677   if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2678       || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2679     return false;
2681   iv->step = CHREC_RIGHT (ev);
2682   if (allow_nonconstant_step)
2683     {
2684       if (tree_contains_chrecs (iv->step, NULL)
2685           || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
2686         return false;
2687     }
2688   else if (TREE_CODE (iv->step) != INTEGER_CST)
2689     return false;
2691   iv->base = CHREC_LEFT (ev);
2692   if (tree_contains_chrecs (iv->base, NULL)
2693       || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
2694     return false;
2696   iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
2698   return true;
2699 }
2701 /* Runs the analysis of scalar evolutions.  */
2703 void
2704 scev_analysis (void)
2705 {
2706   VEC(tree,heap) *exit_conditions;
2708   exit_conditions = VEC_alloc (tree, heap, 37);
2709   select_loops_exit_conditions (&exit_conditions);
2711   if (dump_file && (dump_flags & TDF_STATS))
2712     analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2714   number_of_iterations_for_all_loops (&exit_conditions);
2715   VEC_free (tree, heap, exit_conditions);
2716 }
2718 /* Finalize the scalar evolution analysis.  */
2720 void
2721 scev_finalize (void)
2722 {
2723   if (!scalar_evolution_info)
2724     return;
2725   htab_delete (scalar_evolution_info);
2726   BITMAP_FREE (already_instantiated);
2727   scalar_evolution_info = NULL;
2728 }
2730 /* Replace ssa names for that scev can prove they are constant by the
2731    appropriate constants.  Also perform final value replacement in loops,
2732    in case the replacement expressions are cheap.
2734    We only consider SSA names defined by phi nodes; rest is left to the
2735    ordinary constant propagation pass.  */
2737 unsigned int
2738 scev_const_prop (void)
2739 {
2740   basic_block bb;
2741   tree name, phi, next_phi, type, ev;
2742   struct loop *loop, *ex_loop;
2743   bitmap ssa_names_to_remove = NULL;
2744   unsigned i;
2745   loop_iterator li;
2747   if (number_of_loops () <= 1)
2748     return 0;
2750   FOR_EACH_BB (bb)
2751     {
2752       loop = bb->loop_father;
2754       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2755         {
2756           name = PHI_RESULT (phi);
2758           if (!is_gimple_reg (name))
2759             continue;
2761           type = TREE_TYPE (name);
2763           if (!POINTER_TYPE_P (type)
2764               && !INTEGRAL_TYPE_P (type))
2765             continue;
2767           ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2768           if (!is_gimple_min_invariant (ev)
2769               || !may_propagate_copy (name, ev))
2770             continue;
2772           /* Replace the uses of the name.  */
2773           if (name != ev)
2774             replace_uses_by (name, ev);
2776           if (!ssa_names_to_remove)
2777             ssa_names_to_remove = BITMAP_ALLOC (NULL);
2778           bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
2779         }
2780     }
2782   /* Remove the ssa names that were replaced by constants.  We do not
2783      remove them directly in the previous cycle, since this
2784      invalidates scev cache.  */
2785   if (ssa_names_to_remove)
2786     {
2787       bitmap_iterator bi;
2789       EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
2790         {
2791           name = ssa_name (i);
2792           phi = SSA_NAME_DEF_STMT (name);
2794           gcc_assert (TREE_CODE (phi) == PHI_NODE);
2795           remove_phi_node (phi, NULL, true);
2796         }
2798       BITMAP_FREE (ssa_names_to_remove);
2799       scev_reset ();
2800     }
2802   /* Now the regular final value replacement.  */
2803   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
2804     {
2805       edge exit;
2806       tree def, rslt, ass, niter;
2807       block_stmt_iterator bsi;
2809       /* If we do not know exact number of iterations of the loop, we cannot
2810          replace the final value.  */
2811       exit = single_exit (loop);
2812       if (!exit)
2813         continue;
2815       niter = number_of_latch_executions (loop);
2816       /* We used to check here whether the computation of NITER is expensive,
2817          and avoided final value elimination if that is the case.  The problem
2818          is that it is hard to evaluate whether the expression is too
2819          expensive, as we do not know what optimization opportunities the
2820          the elimination of the final value may reveal.  Therefore, we now
2821          eliminate the final values of induction variables unconditionally.  */
2822       if (niter == chrec_dont_know)
2823         continue;
2825       /* Ensure that it is possible to insert new statements somewhere.  */
2826       if (!single_pred_p (exit->dest))
2827         split_loop_exit_edge (exit);
2828       bsi = bsi_after_labels (exit->dest);
2830       ex_loop = superloop_at_depth (loop,
2831                                     loop_depth (exit->dest->loop_father) + 1);
2833       for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
2834         {
2835           next_phi = PHI_CHAIN (phi);
2836           rslt = PHI_RESULT (phi);
2837           def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2838           if (!is_gimple_reg (def))
2839             continue;
2841           if (!POINTER_TYPE_P (TREE_TYPE (def))
2842               && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
2843             continue;
2845           def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
2846           def = compute_overall_effect_of_inner_loop (ex_loop, def);
2847           if (!tree_does_not_contain_chrecs (def)
2848               || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
2849               /* Moving the computation from the loop may prolong life range
2850                  of some ssa names, which may cause problems if they appear
2851                  on abnormal edges.  */
2852               || contains_abnormal_ssa_name_p (def))
2853             continue;
2855           /* Eliminate the PHI node and replace it by a computation outside
2856              the loop.  */
2857           def = unshare_expr (def);
2858           remove_phi_node (phi, NULL_TREE, false);
2860           ass = build_gimple_modify_stmt (rslt, NULL_TREE);
2861           SSA_NAME_DEF_STMT (rslt) = ass;
2862           {
2863             block_stmt_iterator dest = bsi;
2864             bsi_insert_before (&dest, ass, BSI_NEW_STMT);
2865             def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE,
2866                                             true, BSI_SAME_STMT);
2867           }
2868           GIMPLE_STMT_OPERAND (ass, 1) = def;
2869           update_stmt (ass);
2870         }
2871     }
2872   return 0;
2873 }
2875 #include "gt-tree-scalar-evolution.h"
About OSDN
Find Software
Develop Software