OSDN Git Service

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