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