OSDN Git Service

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