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