OSDN Git Service

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