OSDN Git Service

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