OSDN Git Service

ad8f2f0f190b2b3f65bcea2f535a3637c4d61515
[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 3, 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 COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 /* 
22    Description: 
23    
24    This pass analyzes the evolution of scalar variables in loop
25    structures.  The algorithm is based on the SSA representation,
26    and on the loop hierarchy tree.  This algorithm is not based on
27    the notion of versions of a variable, as it was the case for the
28    previous implementations of the scalar evolution algorithm, but
29    it assumes that each defined name is unique.
30
31    The notation used in this file is called "chains of recurrences",
32    and has been proposed by Eugene Zima, Robert Van Engelen, and
33    others for describing induction variables in programs.  For example
34    "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
35    when entering in the loop_1 and has a step 2 in this loop, in other
36    words "for (b = 0; b < N; b+=2);".  Note that the coefficients of
37    this chain of recurrence (or chrec [shrek]) can contain the name of
38    other variables, in which case they are called parametric chrecs.
39    For example, "b -> {a, +, 2}_1" means that the initial value of "b"
40    is the value of "a".  In most of the cases these parametric chrecs
41    are fully instantiated before their use because symbolic names can
42    hide some difficult cases such as self-references described later
43    (see the Fibonacci example).
44    
45    A short sketch of the algorithm is:
46      
47    Given a scalar variable to be analyzed, follow the SSA edge to
48    its definition:
49      
50    - When the definition is a GIMPLE_MODIFY_STMT: if the right hand side
51    (RHS) of the definition cannot be statically analyzed, the answer
52    of the analyzer is: "don't know".  
53    Otherwise, for all the variables that are not yet analyzed in the
54    RHS, try to determine their evolution, and finally try to
55    evaluate the operation of the RHS that gives the evolution
56    function of the analyzed variable.
57
58    - When the definition is a condition-phi-node: determine the
59    evolution function for all the branches of the phi node, and
60    finally merge these evolutions (see chrec_merge).
61
62    - When the definition is a loop-phi-node: determine its initial
63    condition, that is the SSA edge defined in an outer loop, and
64    keep it symbolic.  Then determine the SSA edges that are defined
65    in the body of the loop.  Follow the inner edges until ending on
66    another loop-phi-node of the same analyzed loop.  If the reached
67    loop-phi-node is not the starting loop-phi-node, then we keep
68    this definition under a symbolic form.  If the reached
69    loop-phi-node is the same as the starting one, then we compute a
70    symbolic stride on the return path.  The result is then the
71    symbolic chrec {initial_condition, +, symbolic_stride}_loop.
72
73    Examples:
74    
75    Example 1: Illustration of the basic algorithm.
76    
77    | a = 3
78    | loop_1
79    |   b = phi (a, c)
80    |   c = b + 1
81    |   if (c > 10) exit_loop
82    | endloop
83    
84    Suppose that we want to know the number of iterations of the
85    loop_1.  The exit_loop is controlled by a COND_EXPR (c > 10).  We
86    ask the scalar evolution analyzer two questions: what's the
87    scalar evolution (scev) of "c", and what's the scev of "10".  For
88    "10" the answer is "10" since it is a scalar constant.  For the
89    scalar variable "c", it follows the SSA edge to its definition,
90    "c = b + 1", and then asks again what's the scev of "b".
91    Following the SSA edge, we end on a loop-phi-node "b = phi (a,
92    c)", where the initial condition is "a", and the inner loop edge
93    is "c".  The initial condition is kept under a symbolic form (it
94    may be the case that the copy constant propagation has done its
95    work and we end with the constant "3" as one of the edges of the
96    loop-phi-node).  The update edge is followed to the end of the
97    loop, and until reaching again the starting loop-phi-node: b -> c
98    -> b.  At this point we have drawn a path from "b" to "b" from
99    which we compute the stride in the loop: in this example it is
100    "+1".  The resulting scev for "b" is "b -> {a, +, 1}_1".  Now
101    that the scev for "b" is known, it is possible to compute the
102    scev for "c", that is "c -> {a + 1, +, 1}_1".  In order to
103    determine the number of iterations in the loop_1, we have to
104    instantiate_parameters ({a + 1, +, 1}_1), that gives after some
105    more analysis the scev {4, +, 1}_1, or in other words, this is
106    the function "f (x) = x + 4", where x is the iteration count of
107    the loop_1.  Now we have to solve the inequality "x + 4 > 10",
108    and take the smallest iteration number for which the loop is
109    exited: x = 7.  This loop runs from x = 0 to x = 7, and in total
110    there are 8 iterations.  In terms of loop normalization, we have
111    created a variable that is implicitly defined, "x" or just "_1",
112    and all the other analyzed scalars of the loop are defined in
113    function of this variable:
114    
115    a -> 3
116    b -> {3, +, 1}_1
117    c -> {4, +, 1}_1
118      
119    or in terms of a C program: 
120      
121    | a = 3
122    | for (x = 0; x <= 7; x++)
123    |   {
124    |     b = x + 3
125    |     c = x + 4
126    |   }
127      
128    Example 2: Illustration of the algorithm on nested loops.
129      
130    | loop_1
131    |   a = phi (1, b)
132    |   c = a + 2
133    |   loop_2  10 times
134    |     b = phi (c, d)
135    |     d = b + 3
136    |   endloop
137    | endloop
138      
139    For analyzing the scalar evolution of "a", the algorithm follows
140    the SSA edge into the loop's body: "a -> b".  "b" is an inner
141    loop-phi-node, and its analysis as in Example 1, gives: 
142      
143    b -> {c, +, 3}_2
144    d -> {c + 3, +, 3}_2
145      
146    Following the SSA edge for the initial condition, we end on "c = a
147    + 2", and then on the starting loop-phi-node "a".  From this point,
148    the loop stride is computed: back on "c = a + 2" we get a "+2" in
149    the loop_1, then on the loop-phi-node "b" we compute the overall
150    effect of the inner loop that is "b = c + 30", and we get a "+30"
151    in the loop_1.  That means that the overall stride in loop_1 is
152    equal to "+32", and the result is: 
153      
154    a -> {1, +, 32}_1
155    c -> {3, +, 32}_1
156      
157    Example 3: Higher degree polynomials.
158      
159    | loop_1
160    |   a = phi (2, b)
161    |   c = phi (5, d)
162    |   b = a + 1
163    |   d = c + a
164    | endloop
165      
166    a -> {2, +, 1}_1
167    b -> {3, +, 1}_1
168    c -> {5, +, a}_1
169    d -> {5 + a, +, a}_1
170      
171    instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
172    instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
173      
174    Example 4: Lucas, Fibonacci, or mixers in general.
175      
176    | loop_1
177    |   a = phi (1, b)
178    |   c = phi (3, d)
179    |   b = c
180    |   d = c + a
181    | endloop
182      
183    a -> (1, c)_1
184    c -> {3, +, a}_1
185      
186    The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
187    following semantics: during the first iteration of the loop_1, the
188    variable contains the value 1, and then it contains the value "c".
189    Note that this syntax is close to the syntax of the loop-phi-node:
190    "a -> (1, c)_1" vs. "a = phi (1, c)".
191      
192    The symbolic chrec representation contains all the semantics of the
193    original code.  What is more difficult is to use this information.
194      
195    Example 5: Flip-flops, or exchangers.
196      
197    | loop_1
198    |   a = phi (1, b)
199    |   c = phi (3, d)
200    |   b = c
201    |   d = a
202    | endloop
203      
204    a -> (1, c)_1
205    c -> (3, a)_1
206      
207    Based on these symbolic chrecs, it is possible to refine this
208    information into the more precise PERIODIC_CHRECs: 
209      
210    a -> |1, 3|_1
211    c -> |3, 1|_1
212      
213    This transformation is not yet implemented.
214      
215    Further readings:
216    
217    You can find a more detailed description of the algorithm in:
218    http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
219    http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz.  But note that
220    this is a preliminary report and some of the details of the
221    algorithm have changed.  I'm working on a research report that
222    updates the description of the algorithms to reflect the design
223    choices used in this implementation.
224      
225    A set of slides show a high level overview of the algorithm and run
226    an example through the scalar evolution analyzer:
227    http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
228
229    The slides that I have presented at the GCC Summit'04 are available
230    at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
231 */
232
233 #include "config.h"
234 #include "system.h"
235 #include "coretypes.h"
236 #include "tm.h"
237 #include "ggc.h"
238 #include "tree.h"
239 #include "real.h"
240
241 /* These RTL headers are needed for basic-block.h.  */
242 #include "rtl.h"
243 #include "basic-block.h"
244 #include "diagnostic.h"
245 #include "tree-flow.h"
246 #include "tree-dump.h"
247 #include "timevar.h"
248 #include "cfgloop.h"
249 #include "tree-chrec.h"
250 #include "tree-scalar-evolution.h"
251 #include "tree-pass.h"
252 #include "flags.h"
253 #include "params.h"
254
255 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
256
257 /* The cached information about a ssa name VAR, claiming that inside LOOP,
258    the value of VAR can be expressed as CHREC.  */
259
260 struct scev_info_str GTY(())
261 {
262   tree var;
263   tree chrec;
264 };
265
266 /* Counters for the scev database.  */
267 static unsigned nb_set_scev = 0;
268 static unsigned nb_get_scev = 0;
269
270 /* The following trees are unique elements.  Thus the comparison of
271    another element to these elements should be done on the pointer to
272    these trees, and not on their value.  */
273
274 /* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE.  */
275 tree chrec_not_analyzed_yet;
276
277 /* Reserved to the cases where the analyzer has detected an
278    undecidable property at compile time.  */
279 tree chrec_dont_know;
280
281 /* When the analyzer has detected that a property will never
282    happen, then it qualifies it with chrec_known.  */
283 tree chrec_known;
284
285 static bitmap already_instantiated;
286
287 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
288
289 \f
290 /* Constructs a new SCEV_INFO_STR structure.  */
291
292 static inline struct scev_info_str *
293 new_scev_info_str (tree var)
294 {
295   struct scev_info_str *res;
296   
297   res = GGC_NEW (struct scev_info_str);
298   res->var = var;
299   res->chrec = chrec_not_analyzed_yet;
300   
301   return res;
302 }
303
304 /* Computes a hash function for database element ELT.  */
305
306 static hashval_t
307 hash_scev_info (const void *elt)
308 {
309   return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
310 }
311
312 /* Compares database elements E1 and E2.  */
313
314 static int
315 eq_scev_info (const void *e1, const void *e2)
316 {
317   const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
318   const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
319
320   return elt1->var == elt2->var;
321 }
322
323 /* Deletes database element E.  */
324
325 static void
326 del_scev_info (void *e)
327 {
328   ggc_free (e);
329 }
330
331 /* Get the index corresponding to VAR in the current LOOP.  If
332    it's the first time we ask for this VAR, then we return
333    chrec_not_analyzed_yet for this VAR and return its index.  */
334
335 static tree *
336 find_var_scev_info (tree var)
337 {
338   struct scev_info_str *res;
339   struct scev_info_str tmp;
340   PTR *slot;
341
342   tmp.var = var;
343   slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
344
345   if (!*slot)
346     *slot = new_scev_info_str (var);
347   res = (struct scev_info_str *) *slot;
348
349   return &res->chrec;
350 }
351
352 /* Return true when CHREC contains symbolic names defined in
353    LOOP_NB.  */
354
355 bool 
356 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
357 {
358   int i, n;
359
360   if (chrec == NULL_TREE)
361     return false;
362
363   if (TREE_INVARIANT (chrec))
364     return false;
365
366   if (TREE_CODE (chrec) == VAR_DECL
367       || TREE_CODE (chrec) == PARM_DECL
368       || TREE_CODE (chrec) == FUNCTION_DECL
369       || TREE_CODE (chrec) == LABEL_DECL
370       || TREE_CODE (chrec) == RESULT_DECL
371       || TREE_CODE (chrec) == FIELD_DECL)
372     return true;
373
374   if (TREE_CODE (chrec) == SSA_NAME)
375     {
376       tree def = SSA_NAME_DEF_STMT (chrec);
377       struct loop *def_loop = loop_containing_stmt (def);
378       struct loop *loop = get_loop (loop_nb);
379
380       if (def_loop == NULL)
381         return false;
382
383       if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
384         return true;
385
386       return false;
387     }
388
389   n = TREE_OPERAND_LENGTH (chrec);
390   for (i = 0; i < n; i++)
391     if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i), 
392                                                 loop_nb))
393       return true;
394   return false;
395 }
396
397 /* Return true when PHI is a loop-phi-node.  */
398
399 static bool
400 loop_phi_node_p (tree phi)
401 {
402   /* The implementation of this function is based on the following
403      property: "all the loop-phi-nodes of a loop are contained in the
404      loop's header basic block".  */
405
406   return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
407 }
408
409 /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
410    In general, in the case of multivariate evolutions we want to get
411    the evolution in different loops.  LOOP specifies the level for
412    which to get the evolution.
413    
414    Example:
415    
416    | for (j = 0; j < 100; j++)
417    |   {
418    |     for (k = 0; k < 100; k++)
419    |       {
420    |         i = k + j;   - Here the value of i is a function of j, k. 
421    |       }
422    |      ... = i         - Here the value of i is a function of j. 
423    |   }
424    | ... = i              - Here the value of i is a scalar.  
425    
426    Example:  
427    
428    | i_0 = ...
429    | loop_1 10 times
430    |   i_1 = phi (i_0, i_2)
431    |   i_2 = i_1 + 2
432    | endloop
433     
434    This loop has the same effect as:
435    LOOP_1 has the same effect as:
436     
437    | i_1 = i_0 + 20
438    
439    The overall effect of the loop, "i_0 + 20" in the previous example, 
440    is obtained by passing in the parameters: LOOP = 1, 
441    EVOLUTION_FN = {i_0, +, 2}_1.
442 */
443  
444 static tree 
445 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
446 {
447   bool val = false;
448
449   if (evolution_fn == chrec_dont_know)
450     return chrec_dont_know;
451
452   else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
453     {
454       struct loop *inner_loop = get_chrec_loop (evolution_fn);
455
456       if (inner_loop == loop
457           || flow_loop_nested_p (loop, inner_loop))
458         {
459           tree nb_iter = number_of_latch_executions (inner_loop);
460
461           if (nb_iter == chrec_dont_know)
462             return chrec_dont_know;
463           else
464             {
465               tree res;
466
467               /* evolution_fn is the evolution function in LOOP.  Get
468                  its value in the nb_iter-th iteration.  */
469               res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
470               
471               /* Continue the computation until ending on a parent of LOOP.  */
472               return compute_overall_effect_of_inner_loop (loop, res);
473             }
474         }
475       else
476         return evolution_fn;
477      }
478   
479   /* If the evolution function is an invariant, there is nothing to do.  */
480   else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
481     return evolution_fn;
482   
483   else
484     return chrec_dont_know;
485 }
486
487 /* Determine whether the CHREC is always positive/negative.  If the expression
488    cannot be statically analyzed, return false, otherwise set the answer into
489    VALUE.  */
490
491 bool
492 chrec_is_positive (tree chrec, bool *value)
493 {
494   bool value0, value1, value2;
495   tree end_value, nb_iter;
496   
497   switch (TREE_CODE (chrec))
498     {
499     case POLYNOMIAL_CHREC:
500       if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
501           || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
502         return false;
503      
504       /* FIXME -- overflows.  */
505       if (value0 == value1)
506         {
507           *value = value0;
508           return true;
509         }
510
511       /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
512          and the proof consists in showing that the sign never
513          changes during the execution of the loop, from 0 to
514          loop->nb_iterations.  */
515       if (!evolution_function_is_affine_p (chrec))
516         return false;
517
518       nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
519       if (chrec_contains_undetermined (nb_iter))
520         return false;
521
522 #if 0
523       /* TODO -- If the test is after the exit, we may decrease the number of
524          iterations by one.  */
525       if (after_exit)
526         nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
527 #endif
528
529       end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
530               
531       if (!chrec_is_positive (end_value, &value2))
532         return false;
533         
534       *value = value0;
535       return value0 == value1;
536       
537     case INTEGER_CST:
538       *value = (tree_int_cst_sgn (chrec) == 1);
539       return true;
540       
541     default:
542       return false;
543     }
544 }
545
546 /* Associate CHREC to SCALAR.  */
547
548 static void
549 set_scalar_evolution (tree scalar, tree chrec)
550 {
551   tree *scalar_info;
552  
553   if (TREE_CODE (scalar) != SSA_NAME)
554     return;
555
556   scalar_info = find_var_scev_info (scalar);
557   
558   if (dump_file)
559     {
560       if (dump_flags & TDF_DETAILS)
561         {
562           fprintf (dump_file, "(set_scalar_evolution \n");
563           fprintf (dump_file, "  (scalar = ");
564           print_generic_expr (dump_file, scalar, 0);
565           fprintf (dump_file, ")\n  (scalar_evolution = ");
566           print_generic_expr (dump_file, chrec, 0);
567           fprintf (dump_file, "))\n");
568         }
569       if (dump_flags & TDF_STATS)
570         nb_set_scev++;
571     }
572   
573   *scalar_info = chrec;
574 }
575
576 /* Retrieve the chrec associated to SCALAR in the LOOP.  */
577
578 static tree
579 get_scalar_evolution (tree scalar)
580 {
581   tree res;
582   
583   if (dump_file)
584     {
585       if (dump_flags & TDF_DETAILS)
586         {
587           fprintf (dump_file, "(get_scalar_evolution \n");
588           fprintf (dump_file, "  (scalar = ");
589           print_generic_expr (dump_file, scalar, 0);
590           fprintf (dump_file, ")\n");
591         }
592       if (dump_flags & TDF_STATS)
593         nb_get_scev++;
594     }
595   
596   switch (TREE_CODE (scalar))
597     {
598     case SSA_NAME:
599       res = *find_var_scev_info (scalar);
600       break;
601
602     case REAL_CST:
603     case FIXED_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_rhs (type, right, at_stmt);
669           right = chrec_fold_plus (chrec_type (right), 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_rhs (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_rhs (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 (const_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 (const 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   enum tree_code code;
1018   
1019   /* The RHS is one of the following cases:
1020      - an SSA_NAME, 
1021      - an INTEGER_CST,
1022      - a PLUS_EXPR, 
1023      - a POINTER_PLUS_EXPR, 
1024      - a MINUS_EXPR,
1025      - an ASSERT_EXPR,
1026      - other cases are not yet handled.  */
1027   code = TREE_CODE (rhs);
1028   switch (code)
1029     {
1030     case NOP_EXPR:
1031       /* This assignment is under the form "a_1 = (cast) rhs.  */
1032       res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
1033                                     halting_phi, evolution_of_loop, limit);
1034       *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
1035                                           *evolution_of_loop, at_stmt);
1036       break;
1037
1038     case INTEGER_CST:
1039       /* This assignment is under the form "a_1 = 7".  */
1040       res = t_false;
1041       break;
1042       
1043     case SSA_NAME:
1044       /* This assignment is under the form: "a_1 = b_2".  */
1045       res = follow_ssa_edge 
1046         (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
1047       break;
1048       
1049     case POINTER_PLUS_EXPR:
1050     case PLUS_EXPR:
1051       /* This case is under the form "rhs0 + rhs1".  */
1052       rhs0 = TREE_OPERAND (rhs, 0);
1053       rhs1 = TREE_OPERAND (rhs, 1);
1054       STRIP_TYPE_NOPS (rhs0);
1055       STRIP_TYPE_NOPS (rhs1);
1056
1057       if (TREE_CODE (rhs0) == SSA_NAME)
1058         {
1059           if (TREE_CODE (rhs1) == SSA_NAME)
1060             {
1061               /* Match an assignment under the form: 
1062                  "a = b + c".  */
1063       
1064               /* We want only assignments of form "name + name" contribute to
1065                  LIMIT, as the other cases do not necessarily contribute to
1066                  the complexity of the expression.  */
1067               limit++;
1068
1069               evol = *evolution_of_loop;
1070               res = follow_ssa_edge 
1071                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
1072                  &evol, limit);
1073               
1074               if (res == t_true)
1075                 *evolution_of_loop = add_to_evolution 
1076                   (loop->num, 
1077                    chrec_convert (type_rhs, evol, at_stmt), 
1078                    code, rhs1, at_stmt);
1079               
1080               else if (res == t_false)
1081                 {
1082                   res = follow_ssa_edge 
1083                     (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 
1084                      evolution_of_loop, limit);
1085                   
1086                   if (res == t_true)
1087                     *evolution_of_loop = add_to_evolution 
1088                       (loop->num, 
1089                        chrec_convert (type_rhs, *evolution_of_loop, at_stmt), 
1090                        code, rhs0, at_stmt);
1091
1092                   else if (res == t_dont_know)
1093                     *evolution_of_loop = chrec_dont_know;
1094                 }
1095
1096               else if (res == t_dont_know)
1097                 *evolution_of_loop = chrec_dont_know;
1098             }
1099           
1100           else
1101             {
1102               /* Match an assignment under the form: 
1103                  "a = b + ...".  */
1104               res = follow_ssa_edge 
1105                 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
1106                  evolution_of_loop, limit);
1107               if (res == t_true)
1108                 *evolution_of_loop = add_to_evolution 
1109                   (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1110                                              at_stmt),
1111                    code, rhs1, at_stmt);
1112
1113               else if (res == t_dont_know)
1114                 *evolution_of_loop = chrec_dont_know;
1115             }
1116         }
1117       
1118       else if (TREE_CODE (rhs1) == SSA_NAME)
1119         {
1120           /* Match an assignment under the form: 
1121              "a = ... + c".  */
1122           res = follow_ssa_edge 
1123             (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 
1124              evolution_of_loop, limit);
1125           if (res == t_true)
1126             *evolution_of_loop = add_to_evolution 
1127               (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1128                                          at_stmt),
1129                code, rhs0, at_stmt);
1130
1131           else if (res == t_dont_know)
1132             *evolution_of_loop = chrec_dont_know;
1133         }
1134
1135       else
1136         /* Otherwise, match an assignment under the form: 
1137            "a = ... + ...".  */
1138         /* And there is nothing to do.  */
1139         res = t_false;
1140       
1141       break;
1142       
1143     case MINUS_EXPR:
1144       /* This case is under the form "opnd0 = rhs0 - rhs1".  */
1145       rhs0 = TREE_OPERAND (rhs, 0);
1146       rhs1 = TREE_OPERAND (rhs, 1);
1147       STRIP_TYPE_NOPS (rhs0);
1148       STRIP_TYPE_NOPS (rhs1);
1149
1150       if (TREE_CODE (rhs0) == SSA_NAME)
1151         {
1152           /* Match an assignment under the form: 
1153              "a = b - ...".  */
1154
1155           /* We want only assignments of form "name - name" contribute to
1156              LIMIT, as the other cases do not necessarily contribute to
1157              the complexity of the expression.  */
1158           if (TREE_CODE (rhs1) == SSA_NAME)
1159             limit++;
1160
1161           res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
1162                                  evolution_of_loop, limit);
1163           if (res == t_true)
1164             *evolution_of_loop = add_to_evolution 
1165               (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1166                MINUS_EXPR, rhs1, at_stmt);
1167
1168           else if (res == t_dont_know)
1169             *evolution_of_loop = chrec_dont_know;
1170         }
1171       else
1172         /* Otherwise, match an assignment under the form: 
1173            "a = ... - ...".  */
1174         /* And there is nothing to do.  */
1175         res = t_false;
1176       
1177       break;
1178     
1179     case ASSERT_EXPR:
1180       {
1181         /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1182            It must be handled as a copy assignment of the form a_1 = a_2.  */
1183         tree op0 = ASSERT_EXPR_VAR (rhs);
1184         if (TREE_CODE (op0) == SSA_NAME)
1185           res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1186                                  halting_phi, evolution_of_loop, limit);
1187         else
1188           res = t_false;
1189         break;
1190       }
1191
1192
1193     default:
1194       res = t_false;
1195       break;
1196     }
1197   
1198   return res;
1199 }
1200
1201 /* Checks whether the I-th argument of a PHI comes from a backedge.  */
1202
1203 static bool
1204 backedge_phi_arg_p (const_tree phi, int i)
1205 {
1206   const_edge e = PHI_ARG_EDGE (phi, i);
1207
1208   /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1209      about updating it anywhere, and this should work as well most of the
1210      time.  */
1211   if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1212     return true;
1213
1214   return false;
1215 }
1216
1217 /* Helper function for one branch of the condition-phi-node.  Return
1218    true if the strongly connected component has been found following
1219    this path.  */
1220
1221 static inline t_bool
1222 follow_ssa_edge_in_condition_phi_branch (int i,
1223                                          struct loop *loop, 
1224                                          tree condition_phi, 
1225                                          tree halting_phi,
1226                                          tree *evolution_of_branch,
1227                                          tree init_cond, int limit)
1228 {
1229   tree branch = PHI_ARG_DEF (condition_phi, i);
1230   *evolution_of_branch = chrec_dont_know;
1231
1232   /* Do not follow back edges (they must belong to an irreducible loop, which
1233      we really do not want to worry about).  */
1234   if (backedge_phi_arg_p (condition_phi, i))
1235     return t_false;
1236
1237   if (TREE_CODE (branch) == SSA_NAME)
1238     {
1239       *evolution_of_branch = init_cond;
1240       return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, 
1241                               evolution_of_branch, limit);
1242     }
1243
1244   /* This case occurs when one of the condition branches sets 
1245      the variable to a constant: i.e. a phi-node like
1246      "a_2 = PHI <a_7(5), 2(6)>;".  
1247          
1248      FIXME:  This case have to be refined correctly: 
1249      in some cases it is possible to say something better than
1250      chrec_dont_know, for example using a wrap-around notation.  */
1251   return t_false;
1252 }
1253
1254 /* This function merges the branches of a condition-phi-node in a
1255    loop.  */
1256
1257 static t_bool
1258 follow_ssa_edge_in_condition_phi (struct loop *loop,
1259                                   tree condition_phi, 
1260                                   tree halting_phi, 
1261                                   tree *evolution_of_loop, int limit)
1262 {
1263   int i;
1264   tree init = *evolution_of_loop;
1265   tree evolution_of_branch;
1266   t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1267                                                         halting_phi,
1268                                                         &evolution_of_branch,
1269                                                         init, limit);
1270   if (res == t_false || res == t_dont_know)
1271     return res;
1272
1273   *evolution_of_loop = evolution_of_branch;
1274
1275   /* If the phi node is just a copy, do not increase the limit.  */
1276   if (PHI_NUM_ARGS (condition_phi) > 1)
1277     limit++;
1278
1279   for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1280     {
1281       /* Quickly give up when the evolution of one of the branches is
1282          not known.  */
1283       if (*evolution_of_loop == chrec_dont_know)
1284         return t_true;
1285
1286       res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1287                                                      halting_phi,
1288                                                      &evolution_of_branch,
1289                                                      init, limit);
1290       if (res == t_false || res == t_dont_know)
1291         return res;
1292
1293       *evolution_of_loop = chrec_merge (*evolution_of_loop,
1294                                         evolution_of_branch);
1295     }
1296   
1297   return t_true;
1298 }
1299
1300 /* Follow an SSA edge in an inner loop.  It computes the overall
1301    effect of the loop, and following the symbolic initial conditions,
1302    it follows the edges in the parent loop.  The inner loop is
1303    considered as a single statement.  */
1304
1305 static t_bool
1306 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1307                                 tree loop_phi_node, 
1308                                 tree halting_phi,
1309                                 tree *evolution_of_loop, int limit)
1310 {
1311   struct loop *loop = loop_containing_stmt (loop_phi_node);
1312   tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1313
1314   /* Sometimes, the inner loop is too difficult to analyze, and the
1315      result of the analysis is a symbolic parameter.  */
1316   if (ev == PHI_RESULT (loop_phi_node))
1317     {
1318       t_bool res = t_false;
1319       int i;
1320
1321       for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1322         {
1323           tree arg = PHI_ARG_DEF (loop_phi_node, i);
1324           basic_block bb;
1325
1326           /* Follow the edges that exit the inner loop.  */
1327           bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1328           if (!flow_bb_inside_loop_p (loop, bb))
1329             res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
1330                                           arg, halting_phi,
1331                                           evolution_of_loop, limit);
1332           if (res == t_true)
1333             break;
1334         }
1335
1336       /* If the path crosses this loop-phi, give up.  */
1337       if (res == t_true)
1338         *evolution_of_loop = chrec_dont_know;
1339
1340       return res;
1341     }
1342
1343   /* Otherwise, compute the overall effect of the inner loop.  */
1344   ev = compute_overall_effect_of_inner_loop (loop, ev);
1345   return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
1346                                  evolution_of_loop, limit);
1347 }
1348
1349 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1350    path that is analyzed on the return walk.  */
1351
1352 static t_bool
1353 follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
1354                  tree *evolution_of_loop, int limit)
1355 {
1356   struct loop *def_loop;
1357   
1358   if (TREE_CODE (def) == NOP_EXPR)
1359     return t_false;
1360   
1361   /* Give up if the path is longer than the MAX that we allow.  */
1362   if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1363     return t_dont_know;
1364   
1365   def_loop = loop_containing_stmt (def);
1366   
1367   switch (TREE_CODE (def))
1368     {
1369     case PHI_NODE:
1370       if (!loop_phi_node_p (def))
1371         /* DEF is a condition-phi-node.  Follow the branches, and
1372            record their evolutions.  Finally, merge the collected
1373            information and set the approximation to the main
1374            variable.  */
1375         return follow_ssa_edge_in_condition_phi 
1376           (loop, def, halting_phi, evolution_of_loop, limit);
1377
1378       /* When the analyzed phi is the halting_phi, the
1379          depth-first search is over: we have found a path from
1380          the halting_phi to itself in the loop.  */
1381       if (def == halting_phi)
1382         return t_true;
1383           
1384       /* Otherwise, the evolution of the HALTING_PHI depends
1385          on the evolution of another loop-phi-node, i.e. the
1386          evolution function is a higher degree polynomial.  */
1387       if (def_loop == loop)
1388         return t_false;
1389           
1390       /* Inner loop.  */
1391       if (flow_loop_nested_p (loop, def_loop))
1392         return follow_ssa_edge_inner_loop_phi 
1393           (loop, def, halting_phi, evolution_of_loop, limit + 1);
1394
1395       /* Outer loop.  */
1396       return t_false;
1397
1398     case GIMPLE_MODIFY_STMT:
1399       return follow_ssa_edge_in_rhs (loop, def,
1400                                      GIMPLE_STMT_OPERAND (def, 1), 
1401                                      halting_phi, 
1402                                      evolution_of_loop, limit);
1403       
1404     default:
1405       /* At this level of abstraction, the program is just a set
1406          of GIMPLE_MODIFY_STMTs and PHI_NODEs.  In principle there is no
1407          other node to be handled.  */
1408       return t_false;
1409     }
1410 }
1411
1412 \f
1413
1414 /* Given a LOOP_PHI_NODE, this function determines the evolution
1415    function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.  */
1416
1417 static tree
1418 analyze_evolution_in_loop (tree loop_phi_node, 
1419                            tree init_cond)
1420 {
1421   int i;
1422   tree evolution_function = chrec_not_analyzed_yet;
1423   struct loop *loop = loop_containing_stmt (loop_phi_node);
1424   basic_block bb;
1425   
1426   if (dump_file && (dump_flags & TDF_DETAILS))
1427     {
1428       fprintf (dump_file, "(analyze_evolution_in_loop \n");
1429       fprintf (dump_file, "  (loop_phi_node = ");
1430       print_generic_expr (dump_file, loop_phi_node, 0);
1431       fprintf (dump_file, ")\n");
1432     }
1433   
1434   for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1435     {
1436       tree arg = PHI_ARG_DEF (loop_phi_node, i);
1437       tree ssa_chain, ev_fn;
1438       t_bool res;
1439
1440       /* Select the edges that enter the loop body.  */
1441       bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1442       if (!flow_bb_inside_loop_p (loop, bb))
1443         continue;
1444       
1445       if (TREE_CODE (arg) == SSA_NAME)
1446         {
1447           ssa_chain = SSA_NAME_DEF_STMT (arg);
1448
1449           /* Pass in the initial condition to the follow edge function.  */
1450           ev_fn = init_cond;
1451           res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1452         }
1453       else
1454         res = t_false;
1455               
1456       /* When it is impossible to go back on the same
1457          loop_phi_node by following the ssa edges, the
1458          evolution is represented by a peeled chrec, i.e. the
1459          first iteration, EV_FN has the value INIT_COND, then
1460          all the other iterations it has the value of ARG.  
1461          For the moment, PEELED_CHREC nodes are not built.  */
1462       if (res != t_true)
1463         ev_fn = chrec_dont_know;
1464       
1465       /* When there are multiple back edges of the loop (which in fact never
1466          happens currently, but nevertheless), merge their evolutions.  */
1467       evolution_function = chrec_merge (evolution_function, ev_fn);
1468     }
1469   
1470   if (dump_file && (dump_flags & TDF_DETAILS))
1471     {
1472       fprintf (dump_file, "  (evolution_function = ");
1473       print_generic_expr (dump_file, evolution_function, 0);
1474       fprintf (dump_file, "))\n");
1475     }
1476   
1477   return evolution_function;
1478 }
1479
1480 /* Given a loop-phi-node, return the initial conditions of the
1481    variable on entry of the loop.  When the CCP has propagated
1482    constants into the loop-phi-node, the initial condition is
1483    instantiated, otherwise the initial condition is kept symbolic.
1484    This analyzer does not analyze the evolution outside the current
1485    loop, and leaves this task to the on-demand tree reconstructor.  */
1486
1487 static tree 
1488 analyze_initial_condition (tree loop_phi_node)
1489 {
1490   int i;
1491   tree init_cond = chrec_not_analyzed_yet;
1492   struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1493   
1494   if (dump_file && (dump_flags & TDF_DETAILS))
1495     {
1496       fprintf (dump_file, "(analyze_initial_condition \n");
1497       fprintf (dump_file, "  (loop_phi_node = \n");
1498       print_generic_expr (dump_file, loop_phi_node, 0);
1499       fprintf (dump_file, ")\n");
1500     }
1501   
1502   for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1503     {
1504       tree branch = PHI_ARG_DEF (loop_phi_node, i);
1505       basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1506       
1507       /* When the branch is oriented to the loop's body, it does
1508          not contribute to the initial condition.  */
1509       if (flow_bb_inside_loop_p (loop, bb))
1510         continue;
1511
1512       if (init_cond == chrec_not_analyzed_yet)
1513         {
1514           init_cond = branch;
1515           continue;
1516         }
1517
1518       if (TREE_CODE (branch) == SSA_NAME)
1519         {
1520           init_cond = chrec_dont_know;
1521           break;
1522         }
1523
1524       init_cond = chrec_merge (init_cond, branch);
1525     }
1526
1527   /* Ooops -- a loop without an entry???  */
1528   if (init_cond == chrec_not_analyzed_yet)
1529     init_cond = chrec_dont_know;
1530
1531   if (dump_file && (dump_flags & TDF_DETAILS))
1532     {
1533       fprintf (dump_file, "  (init_cond = ");
1534       print_generic_expr (dump_file, init_cond, 0);
1535       fprintf (dump_file, "))\n");
1536     }
1537   
1538   return init_cond;
1539 }
1540
1541 /* Analyze the scalar evolution for LOOP_PHI_NODE.  */
1542
1543 static tree 
1544 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1545 {
1546   tree res;
1547   struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1548   tree init_cond;
1549   
1550   if (phi_loop != loop)
1551     {
1552       struct loop *subloop;
1553       tree evolution_fn = analyze_scalar_evolution
1554         (phi_loop, PHI_RESULT (loop_phi_node));
1555
1556       /* Dive one level deeper.  */
1557       subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1558
1559       /* Interpret the subloop.  */
1560       res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1561       return res;
1562     }
1563
1564   /* Otherwise really interpret the loop phi.  */
1565   init_cond = analyze_initial_condition (loop_phi_node);
1566   res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1567
1568   return res;
1569 }
1570
1571 /* This function merges the branches of a condition-phi-node,
1572    contained in the outermost loop, and whose arguments are already
1573    analyzed.  */
1574
1575 static tree
1576 interpret_condition_phi (struct loop *loop, tree condition_phi)
1577 {
1578   int i;
1579   tree res = chrec_not_analyzed_yet;
1580   
1581   for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1582     {
1583       tree branch_chrec;
1584       
1585       if (backedge_phi_arg_p (condition_phi, i))
1586         {
1587           res = chrec_dont_know;
1588           break;
1589         }
1590
1591       branch_chrec = analyze_scalar_evolution
1592         (loop, PHI_ARG_DEF (condition_phi, i));
1593       
1594       res = chrec_merge (res, branch_chrec);
1595     }
1596
1597   return res;
1598 }
1599
1600 /* Interpret the right hand side of a GIMPLE_MODIFY_STMT OPND1.  If we didn't
1601    analyze this node before, follow the definitions until ending
1602    either on an analyzed GIMPLE_MODIFY_STMT, or on a loop-phi-node.  On the
1603    return path, this function propagates evolutions (ala constant copy
1604    propagation).  OPND1 is not a GIMPLE expression because we could
1605    analyze the effect of an inner loop: see interpret_loop_phi.  */
1606
1607 static tree
1608 interpret_rhs_modify_stmt (struct loop *loop, tree at_stmt,
1609                                   tree opnd1, tree type)
1610 {
1611   tree res, opnd10, opnd11, chrec10, chrec11;
1612
1613   if (is_gimple_min_invariant (opnd1))
1614     return chrec_convert (type, opnd1, at_stmt);
1615
1616   switch (TREE_CODE (opnd1))
1617     {
1618     case POINTER_PLUS_EXPR:
1619       opnd10 = TREE_OPERAND (opnd1, 0);
1620       opnd11 = TREE_OPERAND (opnd1, 1);
1621       chrec10 = analyze_scalar_evolution (loop, opnd10);
1622       chrec11 = analyze_scalar_evolution (loop, opnd11);
1623       chrec10 = chrec_convert (type, chrec10, at_stmt);
1624       chrec11 = chrec_convert (sizetype, chrec11, at_stmt);
1625       res = chrec_fold_plus (type, chrec10, chrec11);
1626       break;
1627
1628     case PLUS_EXPR:
1629       opnd10 = TREE_OPERAND (opnd1, 0);
1630       opnd11 = TREE_OPERAND (opnd1, 1);
1631       chrec10 = analyze_scalar_evolution (loop, opnd10);
1632       chrec11 = analyze_scalar_evolution (loop, opnd11);
1633       chrec10 = chrec_convert (type, chrec10, at_stmt);
1634       chrec11 = chrec_convert (type, chrec11, at_stmt);
1635       res = chrec_fold_plus (type, chrec10, chrec11);
1636       break;
1637       
1638     case MINUS_EXPR:
1639       opnd10 = TREE_OPERAND (opnd1, 0);
1640       opnd11 = TREE_OPERAND (opnd1, 1);
1641       chrec10 = analyze_scalar_evolution (loop, opnd10);
1642       chrec11 = analyze_scalar_evolution (loop, opnd11);
1643       chrec10 = chrec_convert (type, chrec10, at_stmt);
1644       chrec11 = chrec_convert (type, chrec11, at_stmt);
1645       res = chrec_fold_minus (type, chrec10, chrec11);
1646       break;
1647
1648     case NEGATE_EXPR:
1649       opnd10 = TREE_OPERAND (opnd1, 0);
1650       chrec10 = analyze_scalar_evolution (loop, opnd10);
1651       chrec10 = chrec_convert (type, chrec10, at_stmt);
1652       /* TYPE may be integer, real or complex, so use fold_convert.  */
1653       res = chrec_fold_multiply (type, chrec10,
1654                                  fold_convert (type, integer_minus_one_node));
1655       break;
1656
1657     case MULT_EXPR:
1658       opnd10 = TREE_OPERAND (opnd1, 0);
1659       opnd11 = TREE_OPERAND (opnd1, 1);
1660       chrec10 = analyze_scalar_evolution (loop, opnd10);
1661       chrec11 = analyze_scalar_evolution (loop, opnd11);
1662       chrec10 = chrec_convert (type, chrec10, at_stmt);
1663       chrec11 = chrec_convert (type, chrec11, at_stmt);
1664       res = chrec_fold_multiply (type, chrec10, chrec11);
1665       break;
1666       
1667     case SSA_NAME:
1668       res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
1669                            at_stmt);
1670       break;
1671
1672     case ASSERT_EXPR:
1673       opnd10 = ASSERT_EXPR_VAR (opnd1);
1674       res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
1675                            at_stmt);
1676       break;
1677       
1678     case NOP_EXPR:
1679     case CONVERT_EXPR:
1680       opnd10 = TREE_OPERAND (opnd1, 0);
1681       chrec10 = analyze_scalar_evolution (loop, opnd10);
1682       res = chrec_convert (type, chrec10, at_stmt);
1683       break;
1684       
1685     default:
1686       res = chrec_dont_know;
1687       break;
1688     }
1689   
1690   return res;
1691 }
1692
1693 \f
1694
1695 /* This section contains all the entry points: 
1696    - number_of_iterations_in_loop,
1697    - analyze_scalar_evolution,
1698    - instantiate_parameters.
1699 */
1700
1701 /* Compute and return the evolution function in WRTO_LOOP, the nearest
1702    common ancestor of DEF_LOOP and USE_LOOP.  */
1703
1704 static tree 
1705 compute_scalar_evolution_in_loop (struct loop *wrto_loop, 
1706                                   struct loop *def_loop, 
1707                                   tree ev)
1708 {
1709   tree res;
1710   if (def_loop == wrto_loop)
1711     return ev;
1712
1713   def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1714   res = compute_overall_effect_of_inner_loop (def_loop, ev);
1715
1716   return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1717 }
1718
1719 /* Helper recursive function.  */
1720
1721 static tree
1722 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1723 {
1724   tree def, type = TREE_TYPE (var);
1725   basic_block bb;
1726   struct loop *def_loop;
1727
1728   if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1729     return chrec_dont_know;
1730
1731   if (TREE_CODE (var) != SSA_NAME)
1732     return interpret_rhs_modify_stmt (loop, NULL_TREE, var, type);
1733
1734   def = SSA_NAME_DEF_STMT (var);
1735   bb = bb_for_stmt (def);
1736   def_loop = bb ? bb->loop_father : NULL;
1737
1738   if (bb == NULL
1739       || !flow_bb_inside_loop_p (loop, bb))
1740     {
1741       /* Keep the symbolic form.  */
1742       res = var;
1743       goto set_and_end;
1744     }
1745
1746   if (res != chrec_not_analyzed_yet)
1747     {
1748       if (loop != bb->loop_father)
1749         res = compute_scalar_evolution_in_loop 
1750             (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1751
1752       goto set_and_end;
1753     }
1754
1755   if (loop != def_loop)
1756     {
1757       res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1758       res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1759
1760       goto set_and_end;
1761     }
1762
1763   switch (TREE_CODE (def))
1764     {
1765     case GIMPLE_MODIFY_STMT:
1766       res = interpret_rhs_modify_stmt (loop, def,
1767                                        GIMPLE_STMT_OPERAND (def, 1), type);
1768       break;
1769
1770     case PHI_NODE:
1771       if (loop_phi_node_p (def))
1772         res = interpret_loop_phi (loop, def);
1773       else
1774         res = interpret_condition_phi (loop, def);
1775       break;
1776
1777     default:
1778       res = chrec_dont_know;
1779       break;
1780     }
1781
1782  set_and_end:
1783
1784   /* Keep the symbolic form.  */
1785   if (res == chrec_dont_know)
1786     res = var;
1787
1788   if (loop == def_loop)
1789     set_scalar_evolution (var, res);
1790
1791   return res;
1792 }
1793
1794 /* Entry point for the scalar evolution analyzer.
1795    Analyzes and returns the scalar evolution of the ssa_name VAR.
1796    LOOP_NB is the identifier number of the loop in which the variable
1797    is used.
1798    
1799    Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1800    pointer to the statement that uses this variable, in order to
1801    determine the evolution function of the variable, use the following
1802    calls:
1803    
1804    unsigned loop_nb = loop_containing_stmt (stmt)->num;
1805    tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1806    tree chrec_instantiated = instantiate_parameters 
1807    (loop_nb, chrec_with_symbols);
1808 */
1809
1810 tree 
1811 analyze_scalar_evolution (struct loop *loop, tree var)
1812 {
1813   tree res;
1814
1815   if (dump_file && (dump_flags & TDF_DETAILS))
1816     {
1817       fprintf (dump_file, "(analyze_scalar_evolution \n");
1818       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
1819       fprintf (dump_file, "  (scalar = ");
1820       print_generic_expr (dump_file, var, 0);
1821       fprintf (dump_file, ")\n");
1822     }
1823
1824   res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
1825
1826   if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
1827     res = var;
1828
1829   if (dump_file && (dump_flags & TDF_DETAILS))
1830     fprintf (dump_file, ")\n");
1831
1832   return res;
1833 }
1834
1835 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1836    WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
1837    of VERSION).
1838
1839    FOLDED_CASTS is set to true if resolve_mixers used
1840    chrec_convert_aggressive (TODO -- not really, we are way too conservative
1841    at the moment in order to keep things simple).  */
1842
1843 static tree
1844 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
1845                                   tree version, bool *folded_casts)
1846 {
1847   bool val = false;
1848   tree ev = version, tmp;
1849
1850   if (folded_casts)
1851     *folded_casts = false;
1852   while (1)
1853     {
1854       tmp = analyze_scalar_evolution (use_loop, ev);
1855       ev = resolve_mixers (use_loop, tmp);
1856
1857       if (folded_casts && tmp != ev)
1858         *folded_casts = true;
1859
1860       if (use_loop == wrto_loop)
1861         return ev;
1862
1863       /* If the value of the use changes in the inner loop, we cannot express
1864          its value in the outer loop (we might try to return interval chrec,
1865          but we do not have a user for it anyway)  */
1866       if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
1867           || !val)
1868         return chrec_dont_know;
1869
1870       use_loop = loop_outer (use_loop);
1871     }
1872 }
1873
1874 /* Returns instantiated value for VERSION in CACHE.  */
1875
1876 static tree
1877 get_instantiated_value (htab_t cache, tree version)
1878 {
1879   struct scev_info_str *info, pattern;
1880   
1881   pattern.var = version;
1882   info = (struct scev_info_str *) htab_find (cache, &pattern);
1883
1884   if (info)
1885     return info->chrec;
1886   else
1887     return NULL_TREE;
1888 }
1889
1890 /* Sets instantiated value for VERSION to VAL in CACHE.  */
1891
1892 static void
1893 set_instantiated_value (htab_t cache, tree version, tree val)
1894 {
1895   struct scev_info_str *info, pattern;
1896   PTR *slot;
1897   
1898   pattern.var = version;
1899   slot = htab_find_slot (cache, &pattern, INSERT);
1900
1901   if (!*slot)
1902     *slot = new_scev_info_str (version);
1903   info = (struct scev_info_str *) *slot;
1904   info->chrec = val;
1905 }
1906
1907 /* Return the closed_loop_phi node for VAR.  If there is none, return
1908    NULL_TREE.  */
1909
1910 static tree
1911 loop_closed_phi_def (tree var)
1912 {
1913   struct loop *loop;
1914   edge exit;
1915   tree phi;
1916
1917   if (var == NULL_TREE
1918       || TREE_CODE (var) != SSA_NAME)
1919     return NULL_TREE;
1920
1921   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
1922   exit = single_exit (loop);
1923   if (!exit)
1924     return NULL_TREE;
1925
1926   for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1927     if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
1928       return PHI_RESULT (phi);
1929
1930   return NULL_TREE;
1931 }
1932
1933 /* Analyze all the parameters of the chrec that were left under a symbolic form,
1934    with respect to LOOP.  CHREC is the chrec to instantiate.  CACHE is the cache
1935    of already instantiated values.  FLAGS modify the way chrecs are
1936    instantiated.  SIZE_EXPR is used for computing the size of the expression to
1937    be instantiated, and to stop if it exceeds some limit.  */
1938
1939 /* Values for FLAGS.  */
1940 enum
1941 {
1942   INSERT_SUPERLOOP_CHRECS = 1,  /* Loop invariants are replaced with chrecs
1943                                    in outer loops.  */
1944   FOLD_CONVERSIONS = 2          /* The conversions that may wrap in
1945                                    signed/pointer type are folded, as long as the
1946                                    value of the chrec is preserved.  */
1947 };
1948   
1949 static tree
1950 instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache,
1951                           int size_expr)
1952 {
1953   tree res, op0, op1, op2;
1954   basic_block def_bb;
1955   struct loop *def_loop;
1956   tree type = chrec_type (chrec);
1957
1958   /* Give up if the expression is larger than the MAX that we allow.  */
1959   if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1960     return chrec_dont_know;
1961
1962   if (automatically_generated_chrec_p (chrec)
1963       || is_gimple_min_invariant (chrec))
1964     return chrec;
1965
1966   switch (TREE_CODE (chrec))
1967     {
1968     case SSA_NAME:
1969       def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
1970
1971       /* A parameter (or loop invariant and we do not want to include
1972          evolutions in outer loops), nothing to do.  */
1973       if (!def_bb
1974           || (!(flags & INSERT_SUPERLOOP_CHRECS)
1975               && !flow_bb_inside_loop_p (loop, def_bb)))
1976         return chrec;
1977
1978       /* We cache the value of instantiated variable to avoid exponential
1979          time complexity due to reevaluations.  We also store the convenient
1980          value in the cache in order to prevent infinite recursion -- we do
1981          not want to instantiate the SSA_NAME if it is in a mixer
1982          structure.  This is used for avoiding the instantiation of
1983          recursively defined functions, such as: 
1984
1985          | a_2 -> {0, +, 1, +, a_2}_1  */
1986
1987       res = get_instantiated_value (cache, chrec);
1988       if (res)
1989         return res;
1990
1991       /* Store the convenient value for chrec in the structure.  If it
1992          is defined outside of the loop, we may just leave it in symbolic
1993          form, otherwise we need to admit that we do not know its behavior
1994          inside the loop.  */
1995       res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
1996       set_instantiated_value (cache, chrec, res);
1997
1998       /* To make things even more complicated, instantiate_parameters_1
1999          calls analyze_scalar_evolution that may call # of iterations
2000          analysis that may in turn call instantiate_parameters_1 again.
2001          To prevent the infinite recursion, keep also the bitmap of
2002          ssa names that are being instantiated globally.  */
2003       if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
2004         return res;
2005
2006       def_loop = find_common_loop (loop, def_bb->loop_father);
2007
2008       /* If the analysis yields a parametric chrec, instantiate the
2009          result again.  */
2010       bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2011       res = analyze_scalar_evolution (def_loop, chrec);
2012
2013       /* Don't instantiate loop-closed-ssa phi nodes.  */
2014       if (TREE_CODE (res) == SSA_NAME
2015           && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2016               || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2017                   > loop_depth (def_loop))))
2018         {
2019           if (res == chrec)
2020             res = loop_closed_phi_def (chrec);
2021           else
2022             res = chrec;
2023
2024           if (res == NULL_TREE)
2025             res = chrec_dont_know;
2026         }
2027
2028       else if (res != chrec_dont_know)
2029         res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
2030
2031       bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2032
2033       /* Store the correct value to the cache.  */
2034       set_instantiated_value (cache, chrec, res);
2035       return res;
2036
2037     case POLYNOMIAL_CHREC:
2038       op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2039                                       flags, cache, size_expr);
2040       if (op0 == chrec_dont_know)
2041         return chrec_dont_know;
2042
2043       op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2044                                       flags, cache, size_expr);
2045       if (op1 == chrec_dont_know)
2046         return chrec_dont_know;
2047
2048       if (CHREC_LEFT (chrec) != op0
2049           || CHREC_RIGHT (chrec) != op1)
2050         {
2051           op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL_TREE);
2052           chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2053         }
2054       return chrec;
2055
2056     case POINTER_PLUS_EXPR:
2057     case PLUS_EXPR:
2058       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2059                                       flags, cache, size_expr);
2060       if (op0 == chrec_dont_know)
2061         return chrec_dont_know;
2062
2063       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2064                                       flags, cache, size_expr);
2065       if (op1 == chrec_dont_know)
2066         return chrec_dont_know;
2067
2068       if (TREE_OPERAND (chrec, 0) != op0
2069           || TREE_OPERAND (chrec, 1) != op1)
2070         {
2071           op0 = chrec_convert (type, op0, NULL_TREE);
2072           op1 = chrec_convert_rhs (type, op1, NULL_TREE);
2073           chrec = chrec_fold_plus (type, op0, op1);
2074         }
2075       return chrec;
2076
2077     case MINUS_EXPR:
2078       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2079                                       flags, cache, size_expr);
2080       if (op0 == chrec_dont_know)
2081         return chrec_dont_know;
2082
2083       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2084                                       flags, cache, size_expr);
2085       if (op1 == chrec_dont_know)
2086         return chrec_dont_know;
2087
2088       if (TREE_OPERAND (chrec, 0) != op0
2089           || TREE_OPERAND (chrec, 1) != op1)
2090         {
2091           op0 = chrec_convert (type, op0, NULL_TREE);
2092           op1 = chrec_convert (type, op1, NULL_TREE);
2093           chrec = chrec_fold_minus (type, op0, op1);
2094         }
2095       return chrec;
2096
2097     case MULT_EXPR:
2098       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2099                                       flags, cache, size_expr);
2100       if (op0 == chrec_dont_know)
2101         return chrec_dont_know;
2102
2103       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2104                                       flags, cache, size_expr);
2105       if (op1 == chrec_dont_know)
2106         return chrec_dont_know;
2107
2108       if (TREE_OPERAND (chrec, 0) != op0
2109           || TREE_OPERAND (chrec, 1) != op1)
2110         {
2111           op0 = chrec_convert (type, op0, NULL_TREE);
2112           op1 = chrec_convert (type, op1, NULL_TREE);
2113           chrec = chrec_fold_multiply (type, op0, op1);
2114         }
2115       return chrec;
2116
2117     case NOP_EXPR:
2118     case CONVERT_EXPR:
2119     case NON_LVALUE_EXPR:
2120       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2121                                       flags, cache, size_expr);
2122       if (op0 == chrec_dont_know)
2123         return chrec_dont_know;
2124
2125       if (flags & FOLD_CONVERSIONS)
2126         {
2127           tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
2128           if (tmp)
2129             return tmp;
2130         }
2131
2132       if (op0 == TREE_OPERAND (chrec, 0))
2133         return chrec;
2134
2135       /* If we used chrec_convert_aggressive, we can no longer assume that
2136          signed chrecs do not overflow, as chrec_convert does, so avoid
2137          calling it in that case.  */
2138       if (flags & FOLD_CONVERSIONS)
2139         return fold_convert (TREE_TYPE (chrec), op0);
2140
2141       return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
2142
2143     case SCEV_NOT_KNOWN:
2144       return chrec_dont_know;
2145
2146     case SCEV_KNOWN:
2147       return chrec_known;
2148                                      
2149     default:
2150       break;
2151     }
2152
2153   gcc_assert (!VL_EXP_CLASS_P (chrec));
2154   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2155     {
2156     case 3:
2157       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2158                                       flags, cache, size_expr);
2159       if (op0 == chrec_dont_know)
2160         return chrec_dont_know;
2161
2162       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2163                                       flags, cache, size_expr);
2164       if (op1 == chrec_dont_know)
2165         return chrec_dont_know;
2166
2167       op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2168                                       flags, cache, size_expr);
2169       if (op2 == chrec_dont_know)
2170         return chrec_dont_know;
2171
2172       if (op0 == TREE_OPERAND (chrec, 0)
2173           && op1 == TREE_OPERAND (chrec, 1)
2174           && op2 == TREE_OPERAND (chrec, 2))
2175         return chrec;
2176
2177       return fold_build3 (TREE_CODE (chrec),
2178                           TREE_TYPE (chrec), op0, op1, op2);
2179
2180     case 2:
2181       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2182                                       flags, cache, size_expr);
2183       if (op0 == chrec_dont_know)
2184         return chrec_dont_know;
2185
2186       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2187                                       flags, cache, size_expr);
2188       if (op1 == chrec_dont_know)
2189         return chrec_dont_know;
2190
2191       if (op0 == TREE_OPERAND (chrec, 0)
2192           && op1 == TREE_OPERAND (chrec, 1))
2193         return chrec;
2194       return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2195             
2196     case 1:
2197       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2198                                       flags, cache, size_expr);
2199       if (op0 == chrec_dont_know)
2200         return chrec_dont_know;
2201       if (op0 == TREE_OPERAND (chrec, 0))
2202         return chrec;
2203       return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2204
2205     case 0:
2206       return chrec;
2207
2208     default:
2209       break;
2210     }
2211
2212   /* Too complicated to handle.  */
2213   return chrec_dont_know;
2214 }
2215
2216 /* Analyze all the parameters of the chrec that were left under a
2217    symbolic form.  LOOP is the loop in which symbolic names have to
2218    be analyzed and instantiated.  */
2219
2220 tree
2221 instantiate_parameters (struct loop *loop,
2222                         tree chrec)
2223 {
2224   tree res;
2225   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2226
2227   if (dump_file && (dump_flags & TDF_DETAILS))
2228     {
2229       fprintf (dump_file, "(instantiate_parameters \n");
2230       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
2231       fprintf (dump_file, "  (chrec = ");
2232       print_generic_expr (dump_file, chrec, 0);
2233       fprintf (dump_file, ")\n");
2234     }
2235  
2236   res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
2237                                   0);
2238
2239   if (dump_file && (dump_flags & TDF_DETAILS))
2240     {
2241       fprintf (dump_file, "  (res = ");
2242       print_generic_expr (dump_file, res, 0);
2243       fprintf (dump_file, "))\n");
2244     }
2245
2246   htab_delete (cache);
2247   
2248   return res;
2249 }
2250
2251 /* Similar to instantiate_parameters, but does not introduce the
2252    evolutions in outer loops for LOOP invariants in CHREC, and does not
2253    care about causing overflows, as long as they do not affect value
2254    of an expression.  */
2255
2256 tree
2257 resolve_mixers (struct loop *loop, tree chrec)
2258 {
2259   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2260   tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0);
2261   htab_delete (cache);
2262   return ret;
2263 }
2264
2265 /* Entry point for the analysis of the number of iterations pass.  
2266    This function tries to safely approximate the number of iterations
2267    the loop will run.  When this property is not decidable at compile
2268    time, the result is chrec_dont_know.  Otherwise the result is
2269    a scalar or a symbolic parameter.
2270    
2271    Example of analysis: suppose that the loop has an exit condition:
2272    
2273    "if (b > 49) goto end_loop;"
2274    
2275    and that in a previous analysis we have determined that the
2276    variable 'b' has an evolution function:
2277    
2278    "EF = {23, +, 5}_2".  
2279    
2280    When we evaluate the function at the point 5, i.e. the value of the
2281    variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2282    and EF (6) = 53.  In this case the value of 'b' on exit is '53' and
2283    the loop body has been executed 6 times.  */
2284
2285 tree 
2286 number_of_latch_executions (struct loop *loop)
2287 {
2288   tree res, type;
2289   edge exit;
2290   struct tree_niter_desc niter_desc;
2291
2292   /* Determine whether the number_of_iterations_in_loop has already
2293      been computed.  */
2294   res = loop->nb_iterations;
2295   if (res)
2296     return res;
2297   res = chrec_dont_know;
2298
2299   if (dump_file && (dump_flags & TDF_DETAILS))
2300     fprintf (dump_file, "(number_of_iterations_in_loop\n");
2301   
2302   exit = single_exit (loop);
2303   if (!exit)
2304     goto end;
2305
2306   if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2307     goto end;
2308
2309   type = TREE_TYPE (niter_desc.niter);
2310   if (integer_nonzerop (niter_desc.may_be_zero))
2311     res = build_int_cst (type, 0);
2312   else if (integer_zerop (niter_desc.may_be_zero))
2313     res = niter_desc.niter;
2314   else
2315     res = chrec_dont_know;
2316
2317 end:
2318   return set_nb_iterations_in_loop (loop, res);
2319 }
2320
2321 /* Returns the number of executions of the exit condition of LOOP,
2322    i.e., the number by one higher than number_of_latch_executions.
2323    Note that unline number_of_latch_executions, this number does
2324    not necessarily fit in the unsigned variant of the type of
2325    the control variable -- if the number of iterations is a constant,
2326    we return chrec_dont_know if adding one to number_of_latch_executions
2327    overflows; however, in case the number of iterations is symbolic
2328    expression, the caller is responsible for dealing with this
2329    the possible overflow.  */
2330
2331 tree 
2332 number_of_exit_cond_executions (struct loop *loop)
2333 {
2334   tree ret = number_of_latch_executions (loop);
2335   tree type = chrec_type (ret);
2336
2337   if (chrec_contains_undetermined (ret))
2338     return ret;
2339
2340   ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
2341   if (TREE_CODE (ret) == INTEGER_CST
2342       && TREE_OVERFLOW (ret))
2343     return chrec_dont_know;
2344
2345   return ret;
2346 }
2347
2348 /* One of the drivers for testing the scalar evolutions analysis.
2349    This function computes the number of iterations for all the loops
2350    from the EXIT_CONDITIONS array.  */
2351
2352 static void 
2353 number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2354 {
2355   unsigned int i;
2356   unsigned nb_chrec_dont_know_loops = 0;
2357   unsigned nb_static_loops = 0;
2358   tree cond;
2359   
2360   for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2361     {
2362       tree res = number_of_latch_executions (loop_containing_stmt (cond));
2363       if (chrec_contains_undetermined (res))
2364         nb_chrec_dont_know_loops++;
2365       else
2366         nb_static_loops++;
2367     }
2368   
2369   if (dump_file)
2370     {
2371       fprintf (dump_file, "\n(\n");
2372       fprintf (dump_file, "-----------------------------------------\n");
2373       fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2374       fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2375       fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2376       fprintf (dump_file, "-----------------------------------------\n");
2377       fprintf (dump_file, ")\n\n");
2378       
2379       print_loops (dump_file, 3);
2380     }
2381 }
2382
2383 \f
2384
2385 /* Counters for the stats.  */
2386
2387 struct chrec_stats 
2388 {
2389   unsigned nb_chrecs;
2390   unsigned nb_affine;
2391   unsigned nb_affine_multivar;
2392   unsigned nb_higher_poly;
2393   unsigned nb_chrec_dont_know;
2394   unsigned nb_undetermined;
2395 };
2396
2397 /* Reset the counters.  */
2398
2399 static inline void
2400 reset_chrecs_counters (struct chrec_stats *stats)
2401 {
2402   stats->nb_chrecs = 0;
2403   stats->nb_affine = 0;
2404   stats->nb_affine_multivar = 0;
2405   stats->nb_higher_poly = 0;
2406   stats->nb_chrec_dont_know = 0;
2407   stats->nb_undetermined = 0;
2408 }
2409
2410 /* Dump the contents of a CHREC_STATS structure.  */
2411
2412 static void
2413 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2414 {
2415   fprintf (file, "\n(\n");
2416   fprintf (file, "-----------------------------------------\n");
2417   fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2418   fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2419   fprintf (file, "%d\tdegree greater than 2 polynomials\n", 
2420            stats->nb_higher_poly);
2421   fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2422   fprintf (file, "-----------------------------------------\n");
2423   fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2424   fprintf (file, "%d\twith undetermined coefficients\n", 
2425            stats->nb_undetermined);
2426   fprintf (file, "-----------------------------------------\n");
2427   fprintf (file, "%d\tchrecs in the scev database\n", 
2428            (int) htab_elements (scalar_evolution_info));
2429   fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2430   fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2431   fprintf (file, "-----------------------------------------\n");
2432   fprintf (file, ")\n\n");
2433 }
2434
2435 /* Gather statistics about CHREC.  */
2436
2437 static void
2438 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2439 {
2440   if (dump_file && (dump_flags & TDF_STATS))
2441     {
2442       fprintf (dump_file, "(classify_chrec ");
2443       print_generic_expr (dump_file, chrec, 0);
2444       fprintf (dump_file, "\n");
2445     }
2446   
2447   stats->nb_chrecs++;
2448   
2449   if (chrec == NULL_TREE)
2450     {
2451       stats->nb_undetermined++;
2452       return;
2453     }
2454   
2455   switch (TREE_CODE (chrec))
2456     {
2457     case POLYNOMIAL_CHREC:
2458       if (evolution_function_is_affine_p (chrec))
2459         {
2460           if (dump_file && (dump_flags & TDF_STATS))
2461             fprintf (dump_file, "  affine_univariate\n");
2462           stats->nb_affine++;
2463         }
2464       else if (evolution_function_is_affine_multivariate_p (chrec, 0))
2465         {
2466           if (dump_file && (dump_flags & TDF_STATS))
2467             fprintf (dump_file, "  affine_multivariate\n");
2468           stats->nb_affine_multivar++;
2469         }
2470       else
2471         {
2472           if (dump_file && (dump_flags & TDF_STATS))
2473             fprintf (dump_file, "  higher_degree_polynomial\n");
2474           stats->nb_higher_poly++;
2475         }
2476       
2477       break;
2478
2479     default:
2480       break;
2481     }
2482   
2483   if (chrec_contains_undetermined (chrec))
2484     {
2485       if (dump_file && (dump_flags & TDF_STATS))
2486         fprintf (dump_file, "  undetermined\n");
2487       stats->nb_undetermined++;
2488     }
2489   
2490   if (dump_file && (dump_flags & TDF_STATS))
2491     fprintf (dump_file, ")\n");
2492 }
2493
2494 /* One of the drivers for testing the scalar evolutions analysis.
2495    This function analyzes the scalar evolution of all the scalars
2496    defined as loop phi nodes in one of the loops from the
2497    EXIT_CONDITIONS array.  
2498    
2499    TODO Optimization: A loop is in canonical form if it contains only
2500    a single scalar loop phi node.  All the other scalars that have an
2501    evolution in the loop are rewritten in function of this single
2502    index.  This allows the parallelization of the loop.  */
2503
2504 static void 
2505 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2506 {
2507   unsigned int i;
2508   struct chrec_stats stats;
2509   tree cond;
2510   
2511   reset_chrecs_counters (&stats);
2512   
2513   for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2514     {
2515       struct loop *loop;
2516       basic_block bb;
2517       tree phi, chrec;
2518       
2519       loop = loop_containing_stmt (cond);
2520       bb = loop->header;
2521       
2522       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2523         if (is_gimple_reg (PHI_RESULT (phi)))
2524           {
2525             chrec = instantiate_parameters 
2526               (loop, 
2527                analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2528             
2529             if (dump_file && (dump_flags & TDF_STATS))
2530               gather_chrec_stats (chrec, &stats);
2531           }
2532     }
2533   
2534   if (dump_file && (dump_flags & TDF_STATS))
2535     dump_chrecs_stats (dump_file, &stats);
2536 }
2537
2538 /* Callback for htab_traverse, gathers information on chrecs in the
2539    hashtable.  */
2540
2541 static int
2542 gather_stats_on_scev_database_1 (void **slot, void *stats)
2543 {
2544   struct scev_info_str *entry = (struct scev_info_str *) *slot;
2545
2546   gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2547
2548   return 1;
2549 }
2550
2551 /* Classify the chrecs of the whole database.  */
2552
2553 void 
2554 gather_stats_on_scev_database (void)
2555 {
2556   struct chrec_stats stats;
2557   
2558   if (!dump_file)
2559     return;
2560   
2561   reset_chrecs_counters (&stats);
2562  
2563   htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2564                  &stats);
2565
2566   dump_chrecs_stats (dump_file, &stats);
2567 }
2568
2569 \f
2570
2571 /* Initializer.  */
2572
2573 static void
2574 initialize_scalar_evolutions_analyzer (void)
2575 {
2576   /* The elements below are unique.  */
2577   if (chrec_dont_know == NULL_TREE)
2578     {
2579       chrec_not_analyzed_yet = NULL_TREE;
2580       chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2581       chrec_known = make_node (SCEV_KNOWN);
2582       TREE_TYPE (chrec_dont_know) = void_type_node;
2583       TREE_TYPE (chrec_known) = void_type_node;
2584     }
2585 }
2586
2587 /* Initialize the analysis of scalar evolutions for LOOPS.  */
2588
2589 void
2590 scev_initialize (void)
2591 {
2592   loop_iterator li;
2593   struct loop *loop;
2594
2595   scalar_evolution_info = htab_create_alloc (100,
2596                                              hash_scev_info,
2597                                              eq_scev_info,
2598                                              del_scev_info,
2599                                              ggc_calloc,
2600                                              ggc_free);
2601   already_instantiated = BITMAP_ALLOC (NULL);
2602   
2603   initialize_scalar_evolutions_analyzer ();
2604
2605   FOR_EACH_LOOP (li, loop, 0)
2606     {
2607       loop->nb_iterations = NULL_TREE;
2608     }
2609 }
2610
2611 /* Clean the scalar evolution analysis cache, but preserve the cached
2612    numbers of iterations for the loops.  */
2613
2614 void
2615 scev_reset_except_niters (void)
2616 {
2617   if (scalar_evolution_info)
2618     htab_empty (scalar_evolution_info);
2619 }
2620
2621 /* Cleans up the information cached by the scalar evolutions analysis.  */
2622
2623 void
2624 scev_reset (void)
2625 {
2626   loop_iterator li;
2627   struct loop *loop;
2628
2629   if (!scalar_evolution_info || !current_loops)
2630     return;
2631
2632   scev_reset_except_niters ();
2633
2634   FOR_EACH_LOOP (li, loop, 0)
2635     {
2636       loop->nb_iterations = NULL_TREE;
2637     }
2638 }
2639
2640 /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2641    its base and step in IV if possible.  If ALLOW_NONCONSTANT_STEP is true, we
2642    want step to be invariant in LOOP.  Otherwise we require it to be an
2643    integer constant.  IV->no_overflow is set to true if we are sure the iv cannot
2644    overflow (e.g.  because it is computed in signed arithmetics).  */
2645
2646 bool
2647 simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
2648            bool allow_nonconstant_step)
2649 {
2650   basic_block bb = bb_for_stmt (stmt);
2651   tree type, ev;
2652   bool folded_casts;
2653
2654   iv->base = NULL_TREE;
2655   iv->step = NULL_TREE;
2656   iv->no_overflow = false;
2657
2658   type = TREE_TYPE (op);
2659   if (TREE_CODE (type) != INTEGER_TYPE
2660       && TREE_CODE (type) != POINTER_TYPE)
2661     return false;
2662
2663   ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
2664                                          &folded_casts);
2665   if (chrec_contains_undetermined (ev))
2666     return false;
2667
2668   if (tree_does_not_contain_chrecs (ev)
2669       && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2670     {
2671       iv->base = ev;
2672       iv->step = build_int_cst (TREE_TYPE (ev), 0);
2673       iv->no_overflow = true;
2674       return true;
2675     }
2676
2677   if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2678       || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2679     return false;
2680
2681   iv->step = CHREC_RIGHT (ev);
2682   if (allow_nonconstant_step)
2683     {
2684       if (tree_contains_chrecs (iv->step, NULL)
2685           || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
2686         return false;
2687     }
2688   else if (TREE_CODE (iv->step) != INTEGER_CST)
2689     return false;
2690
2691   iv->base = CHREC_LEFT (ev);
2692   if (tree_contains_chrecs (iv->base, NULL)
2693       || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
2694     return false;
2695
2696   iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
2697
2698   return true;
2699 }
2700
2701 /* Runs the analysis of scalar evolutions.  */
2702
2703 void
2704 scev_analysis (void)
2705 {
2706   VEC(tree,heap) *exit_conditions;
2707   
2708   exit_conditions = VEC_alloc (tree, heap, 37);
2709   select_loops_exit_conditions (&exit_conditions);
2710
2711   if (dump_file && (dump_flags & TDF_STATS))
2712     analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2713   
2714   number_of_iterations_for_all_loops (&exit_conditions);
2715   VEC_free (tree, heap, exit_conditions);
2716 }
2717
2718 /* Finalize the scalar evolution analysis.  */
2719
2720 void
2721 scev_finalize (void)
2722 {
2723   if (!scalar_evolution_info)
2724     return;
2725   htab_delete (scalar_evolution_info);
2726   BITMAP_FREE (already_instantiated);
2727   scalar_evolution_info = NULL;
2728 }
2729
2730 /* Replace ssa names for that scev can prove they are constant by the
2731    appropriate constants.  Also perform final value replacement in loops,
2732    in case the replacement expressions are cheap.
2733    
2734    We only consider SSA names defined by phi nodes; rest is left to the
2735    ordinary constant propagation pass.  */
2736
2737 unsigned int
2738 scev_const_prop (void)
2739 {
2740   basic_block bb;
2741   tree name, phi, next_phi, type, ev;
2742   struct loop *loop, *ex_loop;
2743   bitmap ssa_names_to_remove = NULL;
2744   unsigned i;
2745   loop_iterator li;
2746
2747   if (number_of_loops () <= 1)
2748     return 0;
2749
2750   FOR_EACH_BB (bb)
2751     {
2752       loop = bb->loop_father;
2753
2754       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2755         {
2756           name = PHI_RESULT (phi);
2757
2758           if (!is_gimple_reg (name))
2759             continue;
2760
2761           type = TREE_TYPE (name);
2762
2763           if (!POINTER_TYPE_P (type)
2764               && !INTEGRAL_TYPE_P (type))
2765             continue;
2766
2767           ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2768           if (!is_gimple_min_invariant (ev)
2769               || !may_propagate_copy (name, ev))
2770             continue;
2771
2772           /* Replace the uses of the name.  */
2773           if (name != ev)
2774             replace_uses_by (name, ev);
2775
2776           if (!ssa_names_to_remove)
2777             ssa_names_to_remove = BITMAP_ALLOC (NULL);
2778           bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
2779         }
2780     }
2781
2782   /* Remove the ssa names that were replaced by constants.  We do not
2783      remove them directly in the previous cycle, since this
2784      invalidates scev cache.  */
2785   if (ssa_names_to_remove)
2786     {
2787       bitmap_iterator bi;
2788
2789       EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
2790         {
2791           name = ssa_name (i);
2792           phi = SSA_NAME_DEF_STMT (name);
2793
2794           gcc_assert (TREE_CODE (phi) == PHI_NODE);
2795           remove_phi_node (phi, NULL, true);
2796         }
2797
2798       BITMAP_FREE (ssa_names_to_remove);
2799       scev_reset ();
2800     }
2801
2802   /* Now the regular final value replacement.  */
2803   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
2804     {
2805       edge exit;
2806       tree def, rslt, ass, niter;
2807       block_stmt_iterator bsi;
2808
2809       /* If we do not know exact number of iterations of the loop, we cannot
2810          replace the final value.  */
2811       exit = single_exit (loop);
2812       if (!exit)
2813         continue;
2814
2815       niter = number_of_latch_executions (loop);
2816       /* We used to check here whether the computation of NITER is expensive,
2817          and avoided final value elimination if that is the case.  The problem
2818          is that it is hard to evaluate whether the expression is too
2819          expensive, as we do not know what optimization opportunities the
2820          the elimination of the final value may reveal.  Therefore, we now
2821          eliminate the final values of induction variables unconditionally.  */
2822       if (niter == chrec_dont_know)
2823         continue;
2824
2825       /* Ensure that it is possible to insert new statements somewhere.  */
2826       if (!single_pred_p (exit->dest))
2827         split_loop_exit_edge (exit);
2828       bsi = bsi_after_labels (exit->dest);
2829
2830       ex_loop = superloop_at_depth (loop,
2831                                     loop_depth (exit->dest->loop_father) + 1);
2832
2833       for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
2834         {
2835           next_phi = PHI_CHAIN (phi);
2836           rslt = PHI_RESULT (phi);
2837           def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2838           if (!is_gimple_reg (def))
2839             continue;
2840
2841           if (!POINTER_TYPE_P (TREE_TYPE (def))
2842               && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
2843             continue;
2844
2845           def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
2846           def = compute_overall_effect_of_inner_loop (ex_loop, def);
2847           if (!tree_does_not_contain_chrecs (def)
2848               || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
2849               /* Moving the computation from the loop may prolong life range
2850                  of some ssa names, which may cause problems if they appear
2851                  on abnormal edges.  */
2852               || contains_abnormal_ssa_name_p (def))
2853             continue;
2854
2855           /* Eliminate the PHI node and replace it by a computation outside
2856              the loop.  */
2857           def = unshare_expr (def);
2858           remove_phi_node (phi, NULL_TREE, false);
2859
2860           ass = build_gimple_modify_stmt (rslt, NULL_TREE);
2861           SSA_NAME_DEF_STMT (rslt) = ass;
2862           {
2863             block_stmt_iterator dest = bsi;
2864             bsi_insert_before (&dest, ass, BSI_NEW_STMT);
2865             def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE,
2866                                             true, BSI_SAME_STMT);
2867           }
2868           GIMPLE_STMT_OPERAND (ass, 1) = def;
2869           update_stmt (ass);
2870         }
2871     }
2872   return 0;
2873 }
2874
2875 #include "gt-tree-scalar-evolution.h"