OSDN Git Service

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