OSDN Git Service

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