OSDN Git Service

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