OSDN Git Service

4019f78c0aeb511de65cc0449db5d38231ffd6b6
[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, 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
926       && (TREE_INT_CST_LOW (res) == 0
927           || TREE_OVERFLOW (res)))
928     res = chrec_dont_know;
929   
930   if (dump_file && (dump_flags & TDF_DETAILS))
931     {
932       fprintf (dump_file, "  (set_nb_iterations_in_loop = ");
933       print_generic_expr (dump_file, res, 0);
934       fprintf (dump_file, "))\n");
935     }
936   
937   loop->nb_iterations = res;
938   return res;
939 }
940
941 \f
942
943 /* This section selects the loops that will be good candidates for the
944    scalar evolution analysis.  For the moment, greedily select all the
945    loop nests we could analyze.  */
946
947 /* Return true when it is possible to analyze the condition expression
948    EXPR.  */
949
950 static bool
951 analyzable_condition (tree expr)
952 {
953   tree condition;
954   
955   if (TREE_CODE (expr) != COND_EXPR)
956     return false;
957   
958   condition = TREE_OPERAND (expr, 0);
959   
960   switch (TREE_CODE (condition))
961     {
962     case SSA_NAME:
963       return true;
964       
965     case LT_EXPR:
966     case LE_EXPR:
967     case GT_EXPR:
968     case GE_EXPR:
969     case EQ_EXPR:
970     case NE_EXPR:
971       return true;
972       
973     default:
974       return false;
975     }
976   
977   return false;
978 }
979
980 /* For a loop with a single exit edge, return the COND_EXPR that
981    guards the exit edge.  If the expression is too difficult to
982    analyze, then give up.  */
983
984 tree 
985 get_loop_exit_condition (struct loop *loop)
986 {
987   tree res = NULL_TREE;
988   edge exit_edge = loop->single_exit;
989
990   
991   if (dump_file && (dump_flags & TDF_DETAILS))
992     fprintf (dump_file, "(get_loop_exit_condition \n  ");
993   
994   if (exit_edge)
995     {
996       tree expr;
997       
998       expr = last_stmt (exit_edge->src);
999       if (analyzable_condition (expr))
1000         res = expr;
1001     }
1002   
1003   if (dump_file && (dump_flags & TDF_DETAILS))
1004     {
1005       print_generic_expr (dump_file, res, 0);
1006       fprintf (dump_file, ")\n");
1007     }
1008   
1009   return res;
1010 }
1011
1012 /* Recursively determine and enqueue the exit conditions for a loop.  */
1013
1014 static void 
1015 get_exit_conditions_rec (struct loop *loop, 
1016                          VEC(tree,heap) **exit_conditions)
1017 {
1018   if (!loop)
1019     return;
1020   
1021   /* Recurse on the inner loops, then on the next (sibling) loops.  */
1022   get_exit_conditions_rec (loop->inner, exit_conditions);
1023   get_exit_conditions_rec (loop->next, exit_conditions);
1024   
1025   if (loop->single_exit)
1026     {
1027       tree loop_condition = get_loop_exit_condition (loop);
1028       
1029       if (loop_condition)
1030         VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
1031     }
1032 }
1033
1034 /* Select the candidate loop nests for the analysis.  This function
1035    initializes the EXIT_CONDITIONS array.  */
1036
1037 static void
1038 select_loops_exit_conditions (struct loops *loops, 
1039                               VEC(tree,heap) **exit_conditions)
1040 {
1041   struct loop *function_body = loops->parray[0];
1042   
1043   get_exit_conditions_rec (function_body->inner, exit_conditions);
1044 }
1045
1046 \f
1047 /* Depth first search algorithm.  */
1048
1049 static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
1050
1051 /* Follow the ssa edge into the right hand side RHS of an assignment.
1052    Return true if the strongly connected component has been found.  */
1053
1054 static bool
1055 follow_ssa_edge_in_rhs (struct loop *loop,
1056                         tree rhs, 
1057                         tree halting_phi, 
1058                         tree *evolution_of_loop)
1059 {
1060   bool res = false;
1061   tree rhs0, rhs1;
1062   tree type_rhs = TREE_TYPE (rhs);
1063   
1064   /* The RHS is one of the following cases:
1065      - an SSA_NAME, 
1066      - an INTEGER_CST,
1067      - a PLUS_EXPR, 
1068      - a MINUS_EXPR,
1069      - an ASSERT_EXPR,
1070      - other cases are not yet handled.  */
1071   switch (TREE_CODE (rhs))
1072     {
1073     case NOP_EXPR:
1074       /* This assignment is under the form "a_1 = (cast) rhs.  */
1075       res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi, 
1076                                     evolution_of_loop);
1077       *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop);
1078       break;
1079
1080     case INTEGER_CST:
1081       /* This assignment is under the form "a_1 = 7".  */
1082       res = false;
1083       break;
1084       
1085     case SSA_NAME:
1086       /* This assignment is under the form: "a_1 = b_2".  */
1087       res = follow_ssa_edge 
1088         (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop);
1089       break;
1090       
1091     case PLUS_EXPR:
1092       /* This case is under the form "rhs0 + rhs1".  */
1093       rhs0 = TREE_OPERAND (rhs, 0);
1094       rhs1 = TREE_OPERAND (rhs, 1);
1095       STRIP_TYPE_NOPS (rhs0);
1096       STRIP_TYPE_NOPS (rhs1);
1097
1098       if (TREE_CODE (rhs0) == SSA_NAME)
1099         {
1100           if (TREE_CODE (rhs1) == SSA_NAME)
1101             {
1102               /* Match an assignment under the form: 
1103                  "a = b + c".  */
1104               res = follow_ssa_edge 
1105                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
1106                  evolution_of_loop);
1107               
1108               if (res)
1109                 *evolution_of_loop = add_to_evolution 
1110                   (loop->num, 
1111                    chrec_convert (type_rhs, *evolution_of_loop), 
1112                    PLUS_EXPR, rhs1);
1113               
1114               else
1115                 {
1116                   res = follow_ssa_edge 
1117                     (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 
1118                      evolution_of_loop);
1119                   
1120                   if (res)
1121                     *evolution_of_loop = add_to_evolution 
1122                       (loop->num, 
1123                        chrec_convert (type_rhs, *evolution_of_loop), 
1124                        PLUS_EXPR, rhs0);
1125                 }
1126             }
1127           
1128           else
1129             {
1130               /* Match an assignment under the form: 
1131                  "a = b + ...".  */
1132               res = follow_ssa_edge 
1133                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
1134                  evolution_of_loop);
1135               if (res)
1136                 *evolution_of_loop = add_to_evolution 
1137                   (loop->num, chrec_convert (type_rhs, *evolution_of_loop), 
1138                    PLUS_EXPR, rhs1);
1139             }
1140         }
1141       
1142       else if (TREE_CODE (rhs1) == SSA_NAME)
1143         {
1144           /* Match an assignment under the form: 
1145              "a = ... + c".  */
1146           res = follow_ssa_edge 
1147             (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 
1148              evolution_of_loop);
1149           if (res)
1150             *evolution_of_loop = add_to_evolution 
1151               (loop->num, chrec_convert (type_rhs, *evolution_of_loop), 
1152                PLUS_EXPR, rhs0);
1153         }
1154
1155       else
1156         /* Otherwise, match an assignment under the form: 
1157            "a = ... + ...".  */
1158         /* And there is nothing to do.  */
1159         res = false;
1160       
1161       break;
1162       
1163     case MINUS_EXPR:
1164       /* This case is under the form "opnd0 = rhs0 - rhs1".  */
1165       rhs0 = TREE_OPERAND (rhs, 0);
1166       rhs1 = TREE_OPERAND (rhs, 1);
1167       STRIP_TYPE_NOPS (rhs0);
1168       STRIP_TYPE_NOPS (rhs1);
1169
1170       if (TREE_CODE (rhs0) == SSA_NAME)
1171         {
1172           /* Match an assignment under the form: 
1173              "a = b - ...".  */
1174           res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
1175                                  evolution_of_loop);
1176           if (res)
1177             *evolution_of_loop = add_to_evolution 
1178                     (loop->num, chrec_convert (type_rhs, *evolution_of_loop), 
1179                      MINUS_EXPR, rhs1);
1180         }
1181       else
1182         /* Otherwise, match an assignment under the form: 
1183            "a = ... - ...".  */
1184         /* And there is nothing to do.  */
1185         res = false;
1186       
1187       break;
1188     
1189     case MULT_EXPR:
1190       /* This case is under the form "opnd0 = rhs0 * rhs1".  */
1191       rhs0 = TREE_OPERAND (rhs, 0);
1192       rhs1 = TREE_OPERAND (rhs, 1);
1193       STRIP_TYPE_NOPS (rhs0);
1194       STRIP_TYPE_NOPS (rhs1);
1195
1196       if (TREE_CODE (rhs0) == SSA_NAME)
1197         {
1198           if (TREE_CODE (rhs1) == SSA_NAME)
1199             {
1200               /* Match an assignment under the form: 
1201                  "a = b * c".  */
1202               res = follow_ssa_edge 
1203                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
1204                  evolution_of_loop);
1205               
1206               if (res)
1207                 *evolution_of_loop = chrec_dont_know;
1208               
1209               else
1210                 {
1211                   res = follow_ssa_edge 
1212                     (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 
1213                      evolution_of_loop);
1214                   
1215                   if (res)
1216                     *evolution_of_loop = chrec_dont_know;
1217                 }
1218             }
1219           
1220           else
1221             {
1222               /* Match an assignment under the form: 
1223                  "a = b * ...".  */
1224               res = follow_ssa_edge 
1225                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
1226                  evolution_of_loop);
1227               if (res)
1228                 *evolution_of_loop = chrec_dont_know;
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 = chrec_dont_know;
1241         }
1242       
1243       else
1244         /* Otherwise, match an assignment under the form: 
1245            "a = ... * ...".  */
1246         /* And there is nothing to do.  */
1247         res = false;
1248       
1249       break;
1250
1251     case ASSERT_EXPR:
1252       {
1253         /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1254            It must be handled as a copy assignment of the form a_1 = a_2.  */
1255         tree op0 = ASSERT_EXPR_VAR (rhs);
1256         if (TREE_CODE (op0) == SSA_NAME)
1257           res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1258                                  halting_phi, evolution_of_loop);
1259         else
1260           res = false;
1261         break;
1262       }
1263
1264
1265     default:
1266       res = false;
1267       break;
1268     }
1269   
1270   return res;
1271 }
1272
1273 /* Checks whether the I-th argument of a PHI comes from a backedge.  */
1274
1275 static bool
1276 backedge_phi_arg_p (tree phi, int i)
1277 {
1278   edge e = PHI_ARG_EDGE (phi, i);
1279
1280   /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1281      about updating it anywhere, and this should work as well most of the
1282      time.  */
1283   if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1284     return true;
1285
1286   return false;
1287 }
1288
1289 /* Helper function for one branch of the condition-phi-node.  Return
1290    true if the strongly connected component has been found following
1291    this path.  */
1292
1293 static inline bool
1294 follow_ssa_edge_in_condition_phi_branch (int i,
1295                                          struct loop *loop, 
1296                                          tree condition_phi, 
1297                                          tree halting_phi,
1298                                          tree *evolution_of_branch,
1299                                          tree init_cond)
1300 {
1301   tree branch = PHI_ARG_DEF (condition_phi, i);
1302   *evolution_of_branch = chrec_dont_know;
1303
1304   /* Do not follow back edges (they must belong to an irreducible loop, which
1305      we really do not want to worry about).  */
1306   if (backedge_phi_arg_p (condition_phi, i))
1307     return false;
1308
1309   if (TREE_CODE (branch) == SSA_NAME)
1310     {
1311       *evolution_of_branch = init_cond;
1312       return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, 
1313                               evolution_of_branch);
1314     }
1315
1316   /* This case occurs when one of the condition branches sets 
1317      the variable to a constant: i.e. a phi-node like
1318      "a_2 = PHI <a_7(5), 2(6)>;".  
1319          
1320      FIXME:  This case have to be refined correctly: 
1321      in some cases it is possible to say something better than
1322      chrec_dont_know, for example using a wrap-around notation.  */
1323   return false;
1324 }
1325
1326 /* This function merges the branches of a condition-phi-node in a
1327    loop.  */
1328
1329 static bool
1330 follow_ssa_edge_in_condition_phi (struct loop *loop,
1331                                   tree condition_phi, 
1332                                   tree halting_phi, 
1333                                   tree *evolution_of_loop)
1334 {
1335   int i;
1336   tree init = *evolution_of_loop;
1337   tree evolution_of_branch;
1338
1339   if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1340                                                 halting_phi,
1341                                                 &evolution_of_branch,
1342                                                 init))
1343     return false;
1344   *evolution_of_loop = evolution_of_branch;
1345
1346   for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1347     {
1348       /* Quickly give up when the evolution of one of the branches is
1349          not known.  */
1350       if (*evolution_of_loop == chrec_dont_know)
1351         return true;
1352
1353       if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1354                                                     halting_phi,
1355                                                     &evolution_of_branch,
1356                                                     init))
1357         return false;
1358
1359       *evolution_of_loop = chrec_merge (*evolution_of_loop,
1360                                         evolution_of_branch);
1361     }
1362   
1363   return true;
1364 }
1365
1366 /* Follow an SSA edge in an inner loop.  It computes the overall
1367    effect of the loop, and following the symbolic initial conditions,
1368    it follows the edges in the parent loop.  The inner loop is
1369    considered as a single statement.  */
1370
1371 static bool
1372 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1373                                 tree loop_phi_node, 
1374                                 tree halting_phi,
1375                                 tree *evolution_of_loop)
1376 {
1377   struct loop *loop = loop_containing_stmt (loop_phi_node);
1378   tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1379
1380   /* Sometimes, the inner loop is too difficult to analyze, and the
1381      result of the analysis is a symbolic parameter.  */
1382   if (ev == PHI_RESULT (loop_phi_node))
1383     {
1384       bool res = false;
1385       int i;
1386
1387       for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1388         {
1389           tree arg = PHI_ARG_DEF (loop_phi_node, i);
1390           basic_block bb;
1391
1392           /* Follow the edges that exit the inner loop.  */
1393           bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1394           if (!flow_bb_inside_loop_p (loop, bb))
1395             res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi,
1396                                                  evolution_of_loop);
1397         }
1398
1399       /* If the path crosses this loop-phi, give up.  */
1400       if (res == true)
1401         *evolution_of_loop = chrec_dont_know;
1402
1403       return res;
1404     }
1405
1406   /* Otherwise, compute the overall effect of the inner loop.  */
1407   ev = compute_overall_effect_of_inner_loop (loop, ev);
1408   return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi,
1409                                  evolution_of_loop);
1410 }
1411
1412 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1413    path that is analyzed on the return walk.  */
1414
1415 static bool
1416 follow_ssa_edge (struct loop *loop, 
1417                  tree def, 
1418                  tree halting_phi,
1419                  tree *evolution_of_loop)
1420 {
1421   struct loop *def_loop;
1422   
1423   if (TREE_CODE (def) == NOP_EXPR)
1424     return false;
1425   
1426   def_loop = loop_containing_stmt (def);
1427   
1428   switch (TREE_CODE (def))
1429     {
1430     case PHI_NODE:
1431       if (!loop_phi_node_p (def))
1432         /* DEF is a condition-phi-node.  Follow the branches, and
1433            record their evolutions.  Finally, merge the collected
1434            information and set the approximation to the main
1435            variable.  */
1436         return follow_ssa_edge_in_condition_phi 
1437           (loop, def, halting_phi, evolution_of_loop);
1438
1439       /* When the analyzed phi is the halting_phi, the
1440          depth-first search is over: we have found a path from
1441          the halting_phi to itself in the loop.  */
1442       if (def == halting_phi)
1443         return true;
1444           
1445       /* Otherwise, the evolution of the HALTING_PHI depends
1446          on the evolution of another loop-phi-node, i.e. the
1447          evolution function is a higher degree polynomial.  */
1448       if (def_loop == loop)
1449         return false;
1450           
1451       /* Inner loop.  */
1452       if (flow_loop_nested_p (loop, def_loop))
1453         return follow_ssa_edge_inner_loop_phi 
1454           (loop, def, halting_phi, evolution_of_loop);
1455
1456       /* Outer loop.  */
1457       return false;
1458
1459     case MODIFY_EXPR:
1460       return follow_ssa_edge_in_rhs (loop,
1461                                      TREE_OPERAND (def, 1), 
1462                                      halting_phi, 
1463                                      evolution_of_loop);
1464       
1465     default:
1466       /* At this level of abstraction, the program is just a set
1467          of MODIFY_EXPRs and PHI_NODEs.  In principle there is no
1468          other node to be handled.  */
1469       return false;
1470     }
1471 }
1472
1473 \f
1474
1475 /* Given a LOOP_PHI_NODE, this function determines the evolution
1476    function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.  */
1477
1478 static tree
1479 analyze_evolution_in_loop (tree loop_phi_node, 
1480                            tree init_cond)
1481 {
1482   int i;
1483   tree evolution_function = chrec_not_analyzed_yet;
1484   struct loop *loop = loop_containing_stmt (loop_phi_node);
1485   basic_block bb;
1486   
1487   if (dump_file && (dump_flags & TDF_DETAILS))
1488     {
1489       fprintf (dump_file, "(analyze_evolution_in_loop \n");
1490       fprintf (dump_file, "  (loop_phi_node = ");
1491       print_generic_expr (dump_file, loop_phi_node, 0);
1492       fprintf (dump_file, ")\n");
1493     }
1494   
1495   for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1496     {
1497       tree arg = PHI_ARG_DEF (loop_phi_node, i);
1498       tree ssa_chain, ev_fn;
1499       bool res;
1500
1501       /* Select the edges that enter the loop body.  */
1502       bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1503       if (!flow_bb_inside_loop_p (loop, bb))
1504         continue;
1505       
1506       if (TREE_CODE (arg) == SSA_NAME)
1507         {
1508           ssa_chain = SSA_NAME_DEF_STMT (arg);
1509
1510           /* Pass in the initial condition to the follow edge function.  */
1511           ev_fn = init_cond;
1512           res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn);
1513         }
1514       else
1515         res = false;
1516               
1517       /* When it is impossible to go back on the same
1518          loop_phi_node by following the ssa edges, the
1519          evolution is represented by a peeled chrec, i.e. the
1520          first iteration, EV_FN has the value INIT_COND, then
1521          all the other iterations it has the value of ARG.  
1522          For the moment, PEELED_CHREC nodes are not built.  */
1523       if (!res)
1524         ev_fn = chrec_dont_know;
1525       
1526       /* When there are multiple back edges of the loop (which in fact never
1527          happens currently, but nevertheless), merge their evolutions.  */
1528       evolution_function = chrec_merge (evolution_function, ev_fn);
1529     }
1530   
1531   if (dump_file && (dump_flags & TDF_DETAILS))
1532     {
1533       fprintf (dump_file, "  (evolution_function = ");
1534       print_generic_expr (dump_file, evolution_function, 0);
1535       fprintf (dump_file, "))\n");
1536     }
1537   
1538   return evolution_function;
1539 }
1540
1541 /* Given a loop-phi-node, return the initial conditions of the
1542    variable on entry of the loop.  When the CCP has propagated
1543    constants into the loop-phi-node, the initial condition is
1544    instantiated, otherwise the initial condition is kept symbolic.
1545    This analyzer does not analyze the evolution outside the current
1546    loop, and leaves this task to the on-demand tree reconstructor.  */
1547
1548 static tree 
1549 analyze_initial_condition (tree loop_phi_node)
1550 {
1551   int i;
1552   tree init_cond = chrec_not_analyzed_yet;
1553   struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1554   
1555   if (dump_file && (dump_flags & TDF_DETAILS))
1556     {
1557       fprintf (dump_file, "(analyze_initial_condition \n");
1558       fprintf (dump_file, "  (loop_phi_node = \n");
1559       print_generic_expr (dump_file, loop_phi_node, 0);
1560       fprintf (dump_file, ")\n");
1561     }
1562   
1563   for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1564     {
1565       tree branch = PHI_ARG_DEF (loop_phi_node, i);
1566       basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1567       
1568       /* When the branch is oriented to the loop's body, it does
1569          not contribute to the initial condition.  */
1570       if (flow_bb_inside_loop_p (loop, bb))
1571         continue;
1572
1573       if (init_cond == chrec_not_analyzed_yet)
1574         {
1575           init_cond = branch;
1576           continue;
1577         }
1578
1579       if (TREE_CODE (branch) == SSA_NAME)
1580         {
1581           init_cond = chrec_dont_know;
1582           break;
1583         }
1584
1585       init_cond = chrec_merge (init_cond, branch);
1586     }
1587
1588   /* Ooops -- a loop without an entry???  */
1589   if (init_cond == chrec_not_analyzed_yet)
1590     init_cond = chrec_dont_know;
1591
1592   if (dump_file && (dump_flags & TDF_DETAILS))
1593     {
1594       fprintf (dump_file, "  (init_cond = ");
1595       print_generic_expr (dump_file, init_cond, 0);
1596       fprintf (dump_file, "))\n");
1597     }
1598   
1599   return init_cond;
1600 }
1601
1602 /* Analyze the scalar evolution for LOOP_PHI_NODE.  */
1603
1604 static tree 
1605 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1606 {
1607   tree res;
1608   struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1609   tree init_cond;
1610   
1611   if (phi_loop != loop)
1612     {
1613       struct loop *subloop;
1614       tree evolution_fn = analyze_scalar_evolution
1615         (phi_loop, PHI_RESULT (loop_phi_node));
1616
1617       /* Dive one level deeper.  */
1618       subloop = superloop_at_depth (phi_loop, loop->depth + 1);
1619
1620       /* Interpret the subloop.  */
1621       res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1622       return res;
1623     }
1624
1625   /* Otherwise really interpret the loop phi.  */
1626   init_cond = analyze_initial_condition (loop_phi_node);
1627   res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1628
1629   return res;
1630 }
1631
1632 /* This function merges the branches of a condition-phi-node,
1633    contained in the outermost loop, and whose arguments are already
1634    analyzed.  */
1635
1636 static tree
1637 interpret_condition_phi (struct loop *loop, tree condition_phi)
1638 {
1639   int i;
1640   tree res = chrec_not_analyzed_yet;
1641   
1642   for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1643     {
1644       tree branch_chrec;
1645       
1646       if (backedge_phi_arg_p (condition_phi, i))
1647         {
1648           res = chrec_dont_know;
1649           break;
1650         }
1651
1652       branch_chrec = analyze_scalar_evolution
1653         (loop, PHI_ARG_DEF (condition_phi, i));
1654       
1655       res = chrec_merge (res, branch_chrec);
1656     }
1657
1658   return res;
1659 }
1660
1661 /* Interpret the right hand side of a modify_expr OPND1.  If we didn't
1662    analyze this node before, follow the definitions until ending
1663    either on an analyzed modify_expr, or on a loop-phi-node.  On the
1664    return path, this function propagates evolutions (ala constant copy
1665    propagation).  OPND1 is not a GIMPLE expression because we could
1666    analyze the effect of an inner loop: see interpret_loop_phi.  */
1667
1668 static tree
1669 interpret_rhs_modify_expr (struct loop *loop,
1670                            tree opnd1, tree type)
1671 {
1672   tree res, opnd10, opnd11, chrec10, chrec11;
1673   
1674   if (is_gimple_min_invariant (opnd1))
1675     return chrec_convert (type, opnd1);
1676   
1677   switch (TREE_CODE (opnd1))
1678     {
1679     case PLUS_EXPR:
1680       opnd10 = TREE_OPERAND (opnd1, 0);
1681       opnd11 = TREE_OPERAND (opnd1, 1);
1682       chrec10 = analyze_scalar_evolution (loop, opnd10);
1683       chrec11 = analyze_scalar_evolution (loop, opnd11);
1684       chrec10 = chrec_convert (type, chrec10);
1685       chrec11 = chrec_convert (type, chrec11);
1686       res = chrec_fold_plus (type, chrec10, chrec11);
1687       break;
1688       
1689     case MINUS_EXPR:
1690       opnd10 = TREE_OPERAND (opnd1, 0);
1691       opnd11 = TREE_OPERAND (opnd1, 1);
1692       chrec10 = analyze_scalar_evolution (loop, opnd10);
1693       chrec11 = analyze_scalar_evolution (loop, opnd11);
1694       chrec10 = chrec_convert (type, chrec10);
1695       chrec11 = chrec_convert (type, chrec11);
1696       res = chrec_fold_minus (type, chrec10, chrec11);
1697       break;
1698
1699     case NEGATE_EXPR:
1700       opnd10 = TREE_OPERAND (opnd1, 0);
1701       chrec10 = analyze_scalar_evolution (loop, opnd10);
1702       chrec10 = chrec_convert (type, chrec10);
1703       res = chrec_fold_minus (type, build_int_cst (type, 0), chrec10);
1704       break;
1705
1706     case MULT_EXPR:
1707       opnd10 = TREE_OPERAND (opnd1, 0);
1708       opnd11 = TREE_OPERAND (opnd1, 1);
1709       chrec10 = analyze_scalar_evolution (loop, opnd10);
1710       chrec11 = analyze_scalar_evolution (loop, opnd11);
1711       chrec10 = chrec_convert (type, chrec10);
1712       chrec11 = chrec_convert (type, chrec11);
1713       res = chrec_fold_multiply (type, chrec10, chrec11);
1714       break;
1715       
1716     case SSA_NAME:
1717       res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1));
1718       break;
1719
1720     case ASSERT_EXPR:
1721       opnd10 = ASSERT_EXPR_VAR (opnd1);
1722       res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10));
1723       break;
1724       
1725     case NOP_EXPR:
1726     case CONVERT_EXPR:
1727       opnd10 = TREE_OPERAND (opnd1, 0);
1728       chrec10 = analyze_scalar_evolution (loop, opnd10);
1729       res = chrec_convert (type, chrec10);
1730       break;
1731       
1732     default:
1733       res = chrec_dont_know;
1734       break;
1735     }
1736   
1737   return res;
1738 }
1739
1740 \f
1741
1742 /* This section contains all the entry points: 
1743    - number_of_iterations_in_loop,
1744    - analyze_scalar_evolution,
1745    - instantiate_parameters.
1746 */
1747
1748 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1749    common ancestor of DEF_LOOP and USE_LOOP.  */
1750
1751 static tree 
1752 compute_scalar_evolution_in_loop (struct loop *wrto_loop, 
1753                                   struct loop *def_loop, 
1754                                   tree ev)
1755 {
1756   tree res;
1757   if (def_loop == wrto_loop)
1758     return ev;
1759
1760   def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
1761   res = compute_overall_effect_of_inner_loop (def_loop, ev);
1762
1763   return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1764 }
1765
1766 /* Helper recursive function.  */
1767
1768 static tree
1769 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1770 {
1771   tree def, type = TREE_TYPE (var);
1772   basic_block bb;
1773   struct loop *def_loop;
1774
1775   if (loop == NULL)
1776     return chrec_dont_know;
1777
1778   if (TREE_CODE (var) != SSA_NAME)
1779     return interpret_rhs_modify_expr (loop, var, type);
1780
1781   def = SSA_NAME_DEF_STMT (var);
1782   bb = bb_for_stmt (def);
1783   def_loop = bb ? bb->loop_father : NULL;
1784
1785   if (bb == NULL
1786       || !flow_bb_inside_loop_p (loop, bb))
1787     {
1788       /* Keep the symbolic form.  */
1789       res = var;
1790       goto set_and_end;
1791     }
1792
1793   if (res != chrec_not_analyzed_yet)
1794     {
1795       if (loop != bb->loop_father)
1796         res = compute_scalar_evolution_in_loop 
1797             (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1798
1799       goto set_and_end;
1800     }
1801
1802   if (loop != def_loop)
1803     {
1804       res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1805       res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1806
1807       goto set_and_end;
1808     }
1809
1810   switch (TREE_CODE (def))
1811     {
1812     case MODIFY_EXPR:
1813       res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type);
1814       break;
1815
1816     case PHI_NODE:
1817       if (loop_phi_node_p (def))
1818         res = interpret_loop_phi (loop, def);
1819       else
1820         res = interpret_condition_phi (loop, def);
1821       break;
1822
1823     default:
1824       res = chrec_dont_know;
1825       break;
1826     }
1827
1828  set_and_end:
1829
1830   /* Keep the symbolic form.  */
1831   if (res == chrec_dont_know)
1832     res = var;
1833
1834   if (loop == def_loop)
1835     set_scalar_evolution (var, res);
1836
1837   return res;
1838 }
1839
1840 /* Entry point for the scalar evolution analyzer.
1841    Analyzes and returns the scalar evolution of the ssa_name VAR.
1842    LOOP_NB is the identifier number of the loop in which the variable
1843    is used.
1844    
1845    Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1846    pointer to the statement that uses this variable, in order to
1847    determine the evolution function of the variable, use the following
1848    calls:
1849    
1850    unsigned loop_nb = loop_containing_stmt (stmt)->num;
1851    tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1852    tree chrec_instantiated = instantiate_parameters 
1853    (loop_nb, chrec_with_symbols);
1854 */
1855
1856 tree 
1857 analyze_scalar_evolution (struct loop *loop, tree var)
1858 {
1859   tree res;
1860
1861   if (dump_file && (dump_flags & TDF_DETAILS))
1862     {
1863       fprintf (dump_file, "(analyze_scalar_evolution \n");
1864       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
1865       fprintf (dump_file, "  (scalar = ");
1866       print_generic_expr (dump_file, var, 0);
1867       fprintf (dump_file, ")\n");
1868     }
1869
1870   res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
1871
1872   if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
1873     res = var;
1874
1875   if (dump_file && (dump_flags & TDF_DETAILS))
1876     fprintf (dump_file, ")\n");
1877
1878   return res;
1879 }
1880
1881 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1882    WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1883    of VERSION).  */
1884
1885 static tree
1886 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1887                                   tree version)
1888 {
1889   bool val = false;
1890   tree ev = version;
1891
1892   while (1)
1893     {
1894       ev = analyze_scalar_evolution (use_loop, ev);
1895       ev = resolve_mixers (use_loop, ev);
1896
1897       if (use_loop == wrto_loop)
1898         return ev;
1899
1900       /* If the value of the use changes in the inner loop, we cannot express
1901          its value in the outer loop (we might try to return interval chrec,
1902          but we do not have a user for it anyway)  */
1903       if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1904           || !val)
1905         return chrec_dont_know;
1906
1907       use_loop = use_loop->outer;
1908     }
1909 }
1910
1911 /* Returns instantiated value for VERSION in CACHE.  */
1912
1913 static tree
1914 get_instantiated_value (htab_t cache, tree version)
1915 {
1916   struct scev_info_str *info, pattern;
1917   
1918   pattern.var = version;
1919   info = htab_find (cache, &pattern);
1920
1921   if (info)
1922     return info->chrec;
1923   else
1924     return NULL_TREE;
1925 }
1926
1927 /* Sets instantiated value for VERSION to VAL in CACHE.  */
1928
1929 static void
1930 set_instantiated_value (htab_t cache, tree version, tree val)
1931 {
1932   struct scev_info_str *info, pattern;
1933   PTR *slot;
1934   
1935   pattern.var = version;
1936   slot = htab_find_slot (cache, &pattern, INSERT);
1937
1938   if (*slot)
1939     info = *slot;
1940   else
1941     info = *slot = new_scev_info_str (version);
1942   info->chrec = val;
1943 }
1944
1945 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1946    with respect to LOOP.  CHREC is the chrec to instantiate.  If
1947    ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
1948    outer loop chrecs is done.  CACHE is the cache of already instantiated
1949    values.  */
1950
1951 static tree
1952 instantiate_parameters_1 (struct loop *loop, tree chrec,
1953                           bool allow_superloop_chrecs,
1954                           htab_t cache)
1955 {
1956   tree res, op0, op1, op2;
1957   basic_block def_bb;
1958   struct loop *def_loop;
1959  
1960   if (chrec == NULL_TREE
1961       || automatically_generated_chrec_p (chrec))
1962     return chrec;
1963  
1964   if (is_gimple_min_invariant (chrec))
1965     return chrec;
1966
1967   switch (TREE_CODE (chrec))
1968     {
1969     case SSA_NAME:
1970       def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
1971
1972       /* A parameter (or loop invariant and we do not want to include
1973          evolutions in outer loops), nothing to do.  */
1974       if (!def_bb
1975           || (!allow_superloop_chrecs
1976               && !flow_bb_inside_loop_p (loop, def_bb)))
1977         return chrec;
1978
1979       /* We cache the value of instantiated variable to avoid exponential
1980          time complexity due to reevaluations.  We also store the convenient
1981          value in the cache in order to prevent infinite recursion -- we do
1982          not want to instantiate the SSA_NAME if it is in a mixer
1983          structure.  This is used for avoiding the instantiation of
1984          recursively defined functions, such as: 
1985
1986          | a_2 -> {0, +, 1, +, a_2}_1  */
1987
1988       res = get_instantiated_value (cache, chrec);
1989       if (res)
1990         return res;
1991
1992       /* Store the convenient value for chrec in the structure.  If it
1993          is defined outside of the loop, we may just leave it in symbolic
1994          form, otherwise we need to admit that we do not know its behavior
1995          inside the loop.  */
1996       res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
1997       set_instantiated_value (cache, chrec, res);
1998
1999       /* To make things even more complicated, instantiate_parameters_1
2000          calls analyze_scalar_evolution that may call # of iterations
2001          analysis that may in turn call instantiate_parameters_1 again.
2002          To prevent the infinite recursion, keep also the bitmap of
2003          ssa names that are being instantiated globally.  */
2004       if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
2005         return res;
2006
2007       def_loop = find_common_loop (loop, def_bb->loop_father);
2008
2009       /* If the analysis yields a parametric chrec, instantiate the
2010          result again.  */
2011       bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2012       res = analyze_scalar_evolution (def_loop, chrec);
2013       if (res != chrec_dont_know)
2014         res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs,
2015                                         cache);
2016       bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2017
2018       /* Store the correct value to the cache.  */
2019       set_instantiated_value (cache, chrec, res);
2020       return res;
2021
2022     case POLYNOMIAL_CHREC:
2023       op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2024                                       allow_superloop_chrecs, cache);
2025       if (op0 == chrec_dont_know)
2026         return chrec_dont_know;
2027
2028       op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2029                                       allow_superloop_chrecs, cache);
2030       if (op1 == chrec_dont_know)
2031         return chrec_dont_know;
2032
2033       if (CHREC_LEFT (chrec) != op0
2034           || CHREC_RIGHT (chrec) != op1)
2035         chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2036       return chrec;
2037
2038     case PLUS_EXPR:
2039       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2040                                       allow_superloop_chrecs, cache);
2041       if (op0 == chrec_dont_know)
2042         return chrec_dont_know;
2043
2044       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2045                                       allow_superloop_chrecs, cache);
2046       if (op1 == chrec_dont_know)
2047         return chrec_dont_know;
2048
2049       if (TREE_OPERAND (chrec, 0) != op0
2050           || TREE_OPERAND (chrec, 1) != op1)
2051         chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
2052       return chrec;
2053
2054     case MINUS_EXPR:
2055       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2056                                       allow_superloop_chrecs, cache);
2057       if (op0 == chrec_dont_know)
2058         return chrec_dont_know;
2059
2060       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2061                                       allow_superloop_chrecs, cache);
2062       if (op1 == chrec_dont_know)
2063         return chrec_dont_know;
2064
2065       if (TREE_OPERAND (chrec, 0) != op0
2066           || TREE_OPERAND (chrec, 1) != op1)
2067         chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
2068       return chrec;
2069
2070     case MULT_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       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2077                                       allow_superloop_chrecs, cache);
2078       if (op1 == chrec_dont_know)
2079         return chrec_dont_know;
2080
2081       if (TREE_OPERAND (chrec, 0) != op0
2082           || TREE_OPERAND (chrec, 1) != op1)
2083         chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
2084       return chrec;
2085
2086     case NOP_EXPR:
2087     case CONVERT_EXPR:
2088     case NON_LVALUE_EXPR:
2089       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2090                                       allow_superloop_chrecs, cache);
2091       if (op0 == chrec_dont_know)
2092         return chrec_dont_know;
2093
2094       if (op0 == TREE_OPERAND (chrec, 0))
2095         return chrec;
2096
2097       return chrec_convert (TREE_TYPE (chrec), op0);
2098
2099     case SCEV_NOT_KNOWN:
2100       return chrec_dont_know;
2101
2102     case SCEV_KNOWN:
2103       return chrec_known;
2104                                      
2105     default:
2106       break;
2107     }
2108
2109   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2110     {
2111     case 3:
2112       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2113                                       allow_superloop_chrecs, cache);
2114       if (op0 == chrec_dont_know)
2115         return chrec_dont_know;
2116
2117       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2118                                       allow_superloop_chrecs, cache);
2119       if (op1 == chrec_dont_know)
2120         return chrec_dont_know;
2121
2122       op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2123                                       allow_superloop_chrecs, cache);
2124       if (op2 == chrec_dont_know)
2125         return chrec_dont_know;
2126
2127       if (op0 == TREE_OPERAND (chrec, 0)
2128           && op1 == TREE_OPERAND (chrec, 1)
2129           && op2 == TREE_OPERAND (chrec, 2))
2130         return chrec;
2131
2132       return fold (build (TREE_CODE (chrec),
2133                           TREE_TYPE (chrec), op0, op1, op2));
2134
2135     case 2:
2136       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2137                                       allow_superloop_chrecs, cache);
2138       if (op0 == chrec_dont_know)
2139         return chrec_dont_know;
2140
2141       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2142                                       allow_superloop_chrecs, cache);
2143       if (op1 == chrec_dont_know)
2144         return chrec_dont_know;
2145
2146       if (op0 == TREE_OPERAND (chrec, 0)
2147           && op1 == TREE_OPERAND (chrec, 1))
2148         return chrec;
2149       return fold (build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1));
2150             
2151     case 1:
2152       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2153                                       allow_superloop_chrecs, cache);
2154       if (op0 == chrec_dont_know)
2155         return chrec_dont_know;
2156       if (op0 == TREE_OPERAND (chrec, 0))
2157         return chrec;
2158       return fold (build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0));
2159
2160     case 0:
2161       return chrec;
2162
2163     default:
2164       break;
2165     }
2166
2167   /* Too complicated to handle.  */
2168   return chrec_dont_know;
2169 }
2170
2171 /* Analyze all the parameters of the chrec that were left under a
2172    symbolic form.  LOOP is the loop in which symbolic names have to
2173    be analyzed and instantiated.  */
2174
2175 tree
2176 instantiate_parameters (struct loop *loop,
2177                         tree chrec)
2178 {
2179   tree res;
2180   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2181
2182   if (dump_file && (dump_flags & TDF_DETAILS))
2183     {
2184       fprintf (dump_file, "(instantiate_parameters \n");
2185       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
2186       fprintf (dump_file, "  (chrec = ");
2187       print_generic_expr (dump_file, chrec, 0);
2188       fprintf (dump_file, ")\n");
2189     }
2190  
2191   res = instantiate_parameters_1 (loop, chrec, true, cache);
2192
2193   if (dump_file && (dump_flags & TDF_DETAILS))
2194     {
2195       fprintf (dump_file, "  (res = ");
2196       print_generic_expr (dump_file, res, 0);
2197       fprintf (dump_file, "))\n");
2198     }
2199
2200   htab_delete (cache);
2201   
2202   return res;
2203 }
2204
2205 /* Similar to instantiate_parameters, but does not introduce the
2206    evolutions in outer loops for LOOP invariants in CHREC.  */
2207
2208 static tree
2209 resolve_mixers (struct loop *loop, tree chrec)
2210 {
2211   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2212   tree ret = instantiate_parameters_1 (loop, chrec, false, cache);
2213   htab_delete (cache);
2214   return ret;
2215 }
2216
2217 /* Entry point for the analysis of the number of iterations pass.  
2218    This function tries to safely approximate the number of iterations
2219    the loop will run.  When this property is not decidable at compile
2220    time, the result is chrec_dont_know.  Otherwise the result is
2221    a scalar or a symbolic parameter.
2222    
2223    Example of analysis: suppose that the loop has an exit condition:
2224    
2225    "if (b > 49) goto end_loop;"
2226    
2227    and that in a previous analysis we have determined that the
2228    variable 'b' has an evolution function:
2229    
2230    "EF = {23, +, 5}_2".  
2231    
2232    When we evaluate the function at the point 5, i.e. the value of the
2233    variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2234    and EF (6) = 53.  In this case the value of 'b' on exit is '53' and
2235    the loop body has been executed 6 times.  */
2236
2237 tree 
2238 number_of_iterations_in_loop (struct loop *loop)
2239 {
2240   tree res, type;
2241   edge exit;
2242   struct tree_niter_desc niter_desc;
2243
2244   /* Determine whether the number_of_iterations_in_loop has already
2245      been computed.  */
2246   res = loop->nb_iterations;
2247   if (res)
2248     return res;
2249   res = chrec_dont_know;
2250
2251   if (dump_file && (dump_flags & TDF_DETAILS))
2252     fprintf (dump_file, "(number_of_iterations_in_loop\n");
2253   
2254   exit = loop->single_exit;
2255   if (!exit)
2256     goto end;
2257
2258   if (!number_of_iterations_exit (loop, exit, &niter_desc))
2259     goto end;
2260
2261   type = TREE_TYPE (niter_desc.niter);
2262   if (integer_nonzerop (niter_desc.may_be_zero))
2263     res = build_int_cst (type, 0);
2264   else if (integer_zerop (niter_desc.may_be_zero))
2265     res = niter_desc.niter;
2266   else
2267     res = chrec_dont_know;
2268
2269 end:
2270   return set_nb_iterations_in_loop (loop, res);
2271 }
2272
2273 /* One of the drivers for testing the scalar evolutions analysis.
2274    This function computes the number of iterations for all the loops
2275    from the EXIT_CONDITIONS array.  */
2276
2277 static void 
2278 number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2279 {
2280   unsigned int i;
2281   unsigned nb_chrec_dont_know_loops = 0;
2282   unsigned nb_static_loops = 0;
2283   tree cond;
2284   
2285   for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2286     {
2287       tree res = number_of_iterations_in_loop (loop_containing_stmt (cond));
2288       if (chrec_contains_undetermined (res))
2289         nb_chrec_dont_know_loops++;
2290       else
2291         nb_static_loops++;
2292     }
2293   
2294   if (dump_file)
2295     {
2296       fprintf (dump_file, "\n(\n");
2297       fprintf (dump_file, "-----------------------------------------\n");
2298       fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2299       fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2300       fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
2301       fprintf (dump_file, "-----------------------------------------\n");
2302       fprintf (dump_file, ")\n\n");
2303       
2304       print_loop_ir (dump_file);
2305     }
2306 }
2307
2308 \f
2309
2310 /* Counters for the stats.  */
2311
2312 struct chrec_stats 
2313 {
2314   unsigned nb_chrecs;
2315   unsigned nb_affine;
2316   unsigned nb_affine_multivar;
2317   unsigned nb_higher_poly;
2318   unsigned nb_chrec_dont_know;
2319   unsigned nb_undetermined;
2320 };
2321
2322 /* Reset the counters.  */
2323
2324 static inline void
2325 reset_chrecs_counters (struct chrec_stats *stats)
2326 {
2327   stats->nb_chrecs = 0;
2328   stats->nb_affine = 0;
2329   stats->nb_affine_multivar = 0;
2330   stats->nb_higher_poly = 0;
2331   stats->nb_chrec_dont_know = 0;
2332   stats->nb_undetermined = 0;
2333 }
2334
2335 /* Dump the contents of a CHREC_STATS structure.  */
2336
2337 static void
2338 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2339 {
2340   fprintf (file, "\n(\n");
2341   fprintf (file, "-----------------------------------------\n");
2342   fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2343   fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2344   fprintf (file, "%d\tdegree greater than 2 polynomials\n", 
2345            stats->nb_higher_poly);
2346   fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2347   fprintf (file, "-----------------------------------------\n");
2348   fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2349   fprintf (file, "%d\twith undetermined coefficients\n", 
2350            stats->nb_undetermined);
2351   fprintf (file, "-----------------------------------------\n");
2352   fprintf (file, "%d\tchrecs in the scev database\n", 
2353            (int) htab_elements (scalar_evolution_info));
2354   fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2355   fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2356   fprintf (file, "-----------------------------------------\n");
2357   fprintf (file, ")\n\n");
2358 }
2359
2360 /* Gather statistics about CHREC.  */
2361
2362 static void
2363 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2364 {
2365   if (dump_file && (dump_flags & TDF_STATS))
2366     {
2367       fprintf (dump_file, "(classify_chrec ");
2368       print_generic_expr (dump_file, chrec, 0);
2369       fprintf (dump_file, "\n");
2370     }
2371   
2372   stats->nb_chrecs++;
2373   
2374   if (chrec == NULL_TREE)
2375     {
2376       stats->nb_undetermined++;
2377       return;
2378     }
2379   
2380   switch (TREE_CODE (chrec))
2381     {
2382     case POLYNOMIAL_CHREC:
2383       if (evolution_function_is_affine_p (chrec))
2384         {
2385           if (dump_file && (dump_flags & TDF_STATS))
2386             fprintf (dump_file, "  affine_univariate\n");
2387           stats->nb_affine++;
2388         }
2389       else if (evolution_function_is_affine_multivariate_p (chrec))
2390         {
2391           if (dump_file && (dump_flags & TDF_STATS))
2392             fprintf (dump_file, "  affine_multivariate\n");
2393           stats->nb_affine_multivar++;
2394         }
2395       else
2396         {
2397           if (dump_file && (dump_flags & TDF_STATS))
2398             fprintf (dump_file, "  higher_degree_polynomial\n");
2399           stats->nb_higher_poly++;
2400         }
2401       
2402       break;
2403
2404     default:
2405       break;
2406     }
2407   
2408   if (chrec_contains_undetermined (chrec))
2409     {
2410       if (dump_file && (dump_flags & TDF_STATS))
2411         fprintf (dump_file, "  undetermined\n");
2412       stats->nb_undetermined++;
2413     }
2414   
2415   if (dump_file && (dump_flags & TDF_STATS))
2416     fprintf (dump_file, ")\n");
2417 }
2418
2419 /* One of the drivers for testing the scalar evolutions analysis.
2420    This function analyzes the scalar evolution of all the scalars
2421    defined as loop phi nodes in one of the loops from the
2422    EXIT_CONDITIONS array.  
2423    
2424    TODO Optimization: A loop is in canonical form if it contains only
2425    a single scalar loop phi node.  All the other scalars that have an
2426    evolution in the loop are rewritten in function of this single
2427    index.  This allows the parallelization of the loop.  */
2428
2429 static void 
2430 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2431 {
2432   unsigned int i;
2433   struct chrec_stats stats;
2434   tree cond;
2435   
2436   reset_chrecs_counters (&stats);
2437   
2438   for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2439     {
2440       struct loop *loop;
2441       basic_block bb;
2442       tree phi, chrec;
2443       
2444       loop = loop_containing_stmt (cond);
2445       bb = loop->header;
2446       
2447       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2448         if (is_gimple_reg (PHI_RESULT (phi)))
2449           {
2450             chrec = instantiate_parameters 
2451               (loop, 
2452                analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2453             
2454             if (dump_file && (dump_flags & TDF_STATS))
2455               gather_chrec_stats (chrec, &stats);
2456           }
2457     }
2458   
2459   if (dump_file && (dump_flags & TDF_STATS))
2460     dump_chrecs_stats (dump_file, &stats);
2461 }
2462
2463 /* Callback for htab_traverse, gathers information on chrecs in the
2464    hashtable.  */
2465
2466 static int
2467 gather_stats_on_scev_database_1 (void **slot, void *stats)
2468 {
2469   struct scev_info_str *entry = *slot;
2470
2471   gather_chrec_stats (entry->chrec, stats);
2472
2473   return 1;
2474 }
2475
2476 /* Classify the chrecs of the whole database.  */
2477
2478 void 
2479 gather_stats_on_scev_database (void)
2480 {
2481   struct chrec_stats stats;
2482   
2483   if (!dump_file)
2484     return;
2485   
2486   reset_chrecs_counters (&stats);
2487  
2488   htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2489                  &stats);
2490
2491   dump_chrecs_stats (dump_file, &stats);
2492 }
2493
2494 \f
2495
2496 /* Initializer.  */
2497
2498 static void
2499 initialize_scalar_evolutions_analyzer (void)
2500 {
2501   /* The elements below are unique.  */
2502   if (chrec_dont_know == NULL_TREE)
2503     {
2504       chrec_not_analyzed_yet = NULL_TREE;
2505       chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2506       chrec_known = make_node (SCEV_KNOWN);
2507       TREE_TYPE (chrec_dont_know) = NULL_TREE;
2508       TREE_TYPE (chrec_known) = NULL_TREE;
2509     }
2510 }
2511
2512 /* Initialize the analysis of scalar evolutions for LOOPS.  */
2513
2514 void
2515 scev_initialize (struct loops *loops)
2516 {
2517   unsigned i;
2518   current_loops = loops;
2519
2520   scalar_evolution_info = htab_create (100, hash_scev_info,
2521                                        eq_scev_info, del_scev_info);
2522   already_instantiated = BITMAP_ALLOC (NULL);
2523   
2524   initialize_scalar_evolutions_analyzer ();
2525
2526   for (i = 1; i < loops->num; i++)
2527     if (loops->parray[i])
2528       loops->parray[i]->nb_iterations = NULL_TREE;
2529 }
2530
2531 /* Cleans up the information cached by the scalar evolutions analysis.  */
2532
2533 void
2534 scev_reset (void)
2535 {
2536   unsigned i;
2537   struct loop *loop;
2538
2539   if (!scalar_evolution_info || !current_loops)
2540     return;
2541
2542   htab_empty (scalar_evolution_info);
2543   for (i = 1; i < current_loops->num; i++)
2544     {
2545       loop = current_loops->parray[i];
2546       if (loop)
2547         loop->nb_iterations = NULL_TREE;
2548     }
2549 }
2550
2551 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2552    its BASE and STEP if possible.  If ALLOW_NONCONSTANT_STEP is true, we
2553    want STEP to be invariant in LOOP.  Otherwise we require it to be an
2554    integer constant.  */
2555
2556 bool
2557 simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step,
2558            bool allow_nonconstant_step)
2559 {
2560   basic_block bb = bb_for_stmt (stmt);
2561   tree type, ev;
2562
2563   *base = NULL_TREE;
2564   *step = NULL_TREE;
2565
2566   type = TREE_TYPE (op);
2567   if (TREE_CODE (type) != INTEGER_TYPE
2568       && TREE_CODE (type) != POINTER_TYPE)
2569     return false;
2570
2571   ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op);
2572   if (chrec_contains_undetermined (ev))
2573     return false;
2574
2575   if (tree_does_not_contain_chrecs (ev)
2576       && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2577     {
2578       *base = ev;
2579       return true;
2580     }
2581
2582   if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2583       || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2584     return false;
2585
2586   *step = CHREC_RIGHT (ev);
2587   if (allow_nonconstant_step)
2588     {
2589       if (tree_contains_chrecs (*step, NULL)
2590           || chrec_contains_symbols_defined_in_loop (*step, loop->num))
2591         return false;
2592     }
2593   else if (TREE_CODE (*step) != INTEGER_CST)
2594     return false;
2595
2596   *base = CHREC_LEFT (ev);
2597   if (tree_contains_chrecs (*base, NULL)
2598       || chrec_contains_symbols_defined_in_loop (*base, loop->num))
2599     return false;
2600
2601   return true;
2602 }
2603
2604 /* Runs the analysis of scalar evolutions.  */
2605
2606 void
2607 scev_analysis (void)
2608 {
2609   VEC(tree,heap) *exit_conditions;
2610   
2611   exit_conditions = VEC_alloc (tree, heap, 37);
2612   select_loops_exit_conditions (current_loops, &exit_conditions);
2613
2614   if (dump_file && (dump_flags & TDF_STATS))
2615     analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2616   
2617   number_of_iterations_for_all_loops (&exit_conditions);
2618   VEC_free (tree, heap, exit_conditions);
2619 }
2620
2621 /* Finalize the scalar evolution analysis.  */
2622
2623 void
2624 scev_finalize (void)
2625 {
2626   htab_delete (scalar_evolution_info);
2627   BITMAP_FREE (already_instantiated);
2628 }
2629