OSDN Git Service

* builtins.c, c-pragma.h, c-typeck.c, cgraph.c, cgraphunit.c,
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-loop-niter.c
1 /* Functions to determine/estimate number of iterations of a loop.
2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3    
4 This file is part of GCC.
5    
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version.
10    
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15    
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING.  If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "output.h"
31 #include "diagnostic.h"
32 #include "intl.h"
33 #include "tree-flow.h"
34 #include "tree-dump.h"
35 #include "cfgloop.h"
36 #include "tree-pass.h"
37 #include "ggc.h"
38 #include "tree-chrec.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-data-ref.h"
41 #include "params.h"
42 #include "flags.h"
43 #include "toplev.h"
44 #include "tree-inline.h"
45
46 #define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
47
48
49 /*
50
51    Analysis of number of iterations of an affine exit test.
52
53 */
54
55 /* Returns true if ARG is either NULL_TREE or constant zero.  Unlike
56    integer_zerop, it does not care about overflow flags.  */
57
58 bool
59 zero_p (tree arg)
60 {
61   if (!arg)
62     return true;
63
64   if (TREE_CODE (arg) != INTEGER_CST)
65     return false;
66
67   return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0);
68 }
69
70 /* Returns true if ARG a nonzero constant.  Unlike integer_nonzerop, it does
71    not care about overflow flags.  */
72
73 static bool
74 nonzero_p (tree arg)
75 {
76   if (!arg)
77     return false;
78
79   if (TREE_CODE (arg) != INTEGER_CST)
80     return false;
81
82   return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0);
83 }
84
85 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1.  */
86
87 static tree
88 inverse (tree x, tree mask)
89 {
90   tree type = TREE_TYPE (x);
91   tree rslt;
92   unsigned ctr = tree_floor_log2 (mask);
93
94   if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
95     {
96       unsigned HOST_WIDE_INT ix;
97       unsigned HOST_WIDE_INT imask;
98       unsigned HOST_WIDE_INT irslt = 1;
99
100       gcc_assert (cst_and_fits_in_hwi (x));
101       gcc_assert (cst_and_fits_in_hwi (mask));
102
103       ix = int_cst_value (x);
104       imask = int_cst_value (mask);
105
106       for (; ctr; ctr--)
107         {
108           irslt *= ix;
109           ix *= ix;
110         }
111       irslt &= imask;
112
113       rslt = build_int_cst_type (type, irslt);
114     }
115   else
116     {
117       rslt = build_int_cst_type (type, 1);
118       for (; ctr; ctr--)
119         {
120           rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
121           x = int_const_binop (MULT_EXPR, x, x, 0);
122         }
123       rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
124     }
125
126   return rslt;
127 }
128
129 /* Determines number of iterations of loop whose ending condition
130    is IV <> FINAL.  TYPE is the type of the iv.  The number of
131    iterations is stored to NITER.  NEVER_INFINITE is true if
132    we know that the loop cannot be infinite (we derived this
133    earlier, and possibly set NITER->assumptions to make sure this
134    is the case.  */
135
136 static bool
137 number_of_iterations_ne (tree type, affine_iv *iv, tree final,
138                          struct tree_niter_desc *niter, bool never_infinite)
139 {
140   tree niter_type = unsigned_type_for (type);
141   tree s, c, d, bits, assumption, tmp, bound;
142
143   niter->control = *iv;
144   niter->bound = final;
145   niter->cmp = NE_EXPR;
146
147   /* Rearrange the terms so that we get inequality s * i <> c, with s
148      positive.  Also cast everything to the unsigned type.  */
149   if (tree_int_cst_sign_bit (iv->step))
150     {
151       s = fold_convert (niter_type,
152                         fold_build1 (NEGATE_EXPR, type, iv->step));
153       c = fold_build2 (MINUS_EXPR, niter_type,
154                        fold_convert (niter_type, iv->base),
155                        fold_convert (niter_type, final));
156     }
157   else
158     {
159       s = fold_convert (niter_type, iv->step);
160       c = fold_build2 (MINUS_EXPR, niter_type,
161                        fold_convert (niter_type, final),
162                        fold_convert (niter_type, iv->base));
163     }
164
165   /* First the trivial cases -- when the step is 1.  */
166   if (integer_onep (s))
167     {
168       niter->niter = c;
169       return true;
170     }
171
172   /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
173      is infinite.  Otherwise, the number of iterations is
174      (inverse(s/d) * (c/d)) mod (size of mode/d).  */
175   bits = num_ending_zeros (s);
176   bound = build_low_bits_mask (niter_type,
177                                (TYPE_PRECISION (niter_type)
178                                 - tree_low_cst (bits, 1)));
179
180   d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
181                                build_int_cst_type (niter_type, 1), bits);
182   s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
183
184   if (!never_infinite)
185     {
186       /* If we cannot assume that the loop is not infinite, record the
187          assumptions for divisibility of c.  */
188       assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
189       assumption = fold_build2 (EQ_EXPR, boolean_type_node,
190                                 assumption, build_int_cst (niter_type, 0));
191       if (!nonzero_p (assumption))
192         niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
193                                           niter->assumptions, assumption);
194     }
195       
196   c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
197   tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
198   niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
199   return true;
200 }
201
202 /* Checks whether we can determine the final value of the control variable
203    of the loop with ending condition IV0 < IV1 (computed in TYPE).
204    DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
205    of the step.  The assumptions necessary to ensure that the computation
206    of the final value does not overflow are recorded in NITER.  If we
207    find the final value, we adjust DELTA and return TRUE.  Otherwise
208    we return false.  */
209
210 static bool
211 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
212                                struct tree_niter_desc *niter,
213                                tree *delta, tree step)
214 {
215   tree niter_type = TREE_TYPE (step);
216   tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
217   tree tmod;
218   tree assumption = boolean_true_node, bound, noloop;
219
220   if (TREE_CODE (mod) != INTEGER_CST)
221     return false;
222   if (nonzero_p (mod))
223     mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
224   tmod = fold_convert (type, mod);
225
226   if (nonzero_p (iv0->step))
227     {
228       /* The final value of the iv is iv1->base + MOD, assuming that this
229          computation does not overflow, and that
230          iv0->base <= iv1->base + MOD.  */
231       if (!iv1->no_overflow && !zero_p (mod))
232         {
233           bound = fold_build2 (MINUS_EXPR, type,
234                                TYPE_MAX_VALUE (type), tmod);
235           assumption = fold_build2 (LE_EXPR, boolean_type_node,
236                                     iv1->base, bound);
237           if (zero_p (assumption))
238             return false;
239         }
240       noloop = fold_build2 (GT_EXPR, boolean_type_node,
241                             iv0->base,
242                             fold_build2 (PLUS_EXPR, type,
243                                          iv1->base, tmod));
244     }
245   else
246     {
247       /* The final value of the iv is iv0->base - MOD, assuming that this
248          computation does not overflow, and that
249          iv0->base - MOD <= iv1->base. */
250       if (!iv0->no_overflow && !zero_p (mod))
251         {
252           bound = fold_build2 (PLUS_EXPR, type,
253                                TYPE_MIN_VALUE (type), tmod);
254           assumption = fold_build2 (GE_EXPR, boolean_type_node,
255                                     iv0->base, bound);
256           if (zero_p (assumption))
257             return false;
258         }
259       noloop = fold_build2 (GT_EXPR, boolean_type_node,
260                             fold_build2 (MINUS_EXPR, type,
261                                          iv0->base, tmod),
262                             iv1->base);
263     }
264
265   if (!nonzero_p (assumption))
266     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
267                                       niter->assumptions,
268                                       assumption);
269   if (!zero_p (noloop))
270     niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
271                                       niter->may_be_zero,
272                                       noloop);
273   *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
274   return true;
275 }
276
277 /* Add assertions to NITER that ensure that the control variable of the loop
278    with ending condition IV0 < IV1 does not overflow.  Types of IV0 and IV1
279    are TYPE.  Returns false if we can prove that there is an overflow, true
280    otherwise.  STEP is the absolute value of the step.  */
281
282 static bool
283 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
284                        struct tree_niter_desc *niter, tree step)
285 {
286   tree bound, d, assumption, diff;
287   tree niter_type = TREE_TYPE (step);
288
289   if (nonzero_p (iv0->step))
290     {
291       /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
292       if (iv0->no_overflow)
293         return true;
294
295       /* If iv0->base is a constant, we can determine the last value before
296          overflow precisely; otherwise we conservatively assume
297          MAX - STEP + 1.  */
298
299       if (TREE_CODE (iv0->base) == INTEGER_CST)
300         {
301           d = fold_build2 (MINUS_EXPR, niter_type,
302                            fold_convert (niter_type, TYPE_MAX_VALUE (type)),
303                            fold_convert (niter_type, iv0->base));
304           diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
305         }
306       else
307         diff = fold_build2 (MINUS_EXPR, niter_type, step,
308                             build_int_cst_type (niter_type, 1));
309       bound = fold_build2 (MINUS_EXPR, type,
310                            TYPE_MAX_VALUE (type), fold_convert (type, diff));
311       assumption = fold_build2 (LE_EXPR, boolean_type_node,
312                                 iv1->base, bound);
313     }
314   else
315     {
316       /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
317       if (iv1->no_overflow)
318         return true;
319
320       if (TREE_CODE (iv1->base) == INTEGER_CST)
321         {
322           d = fold_build2 (MINUS_EXPR, niter_type,
323                            fold_convert (niter_type, iv1->base),
324                            fold_convert (niter_type, TYPE_MIN_VALUE (type)));
325           diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
326         }
327       else
328         diff = fold_build2 (MINUS_EXPR, niter_type, step,
329                             build_int_cst_type (niter_type, 1));
330       bound = fold_build2 (PLUS_EXPR, type,
331                            TYPE_MIN_VALUE (type), fold_convert (type, diff));
332       assumption = fold_build2 (GE_EXPR, boolean_type_node,
333                                 iv0->base, bound);
334     }
335
336   if (zero_p (assumption))
337     return false;
338   if (!nonzero_p (assumption))
339     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
340                                       niter->assumptions, assumption);
341     
342   iv0->no_overflow = true;
343   iv1->no_overflow = true;
344   return true;
345 }
346
347 /* Add an assumption to NITER that a loop whose ending condition
348    is IV0 < IV1 rolls.  TYPE is the type of the control iv.  */
349
350 static void
351 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
352                       struct tree_niter_desc *niter)
353 {
354   tree assumption = boolean_true_node, bound, diff;
355   tree mbz, mbzl, mbzr;
356
357   if (nonzero_p (iv0->step))
358     {
359       diff = fold_build2 (MINUS_EXPR, type,
360                           iv0->step, build_int_cst_type (type, 1));
361
362       /* We need to know that iv0->base >= MIN + iv0->step - 1.  Since
363          0 address never belongs to any object, we can assume this for
364          pointers.  */
365       if (!POINTER_TYPE_P (type))
366         {
367           bound = fold_build2 (PLUS_EXPR, type,
368                                TYPE_MIN_VALUE (type), diff);
369           assumption = fold_build2 (GE_EXPR, boolean_type_node,
370                                     iv0->base, bound);
371         }
372
373       /* And then we can compute iv0->base - diff, and compare it with
374          iv1->base.  */      
375       mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff);
376       mbzr = iv1->base;
377     }
378   else
379     {
380       diff = fold_build2 (PLUS_EXPR, type,
381                           iv1->step, build_int_cst_type (type, 1));
382
383       if (!POINTER_TYPE_P (type))
384         {
385           bound = fold_build2 (PLUS_EXPR, type,
386                                TYPE_MAX_VALUE (type), diff);
387           assumption = fold_build2 (LE_EXPR, boolean_type_node,
388                                     iv1->base, bound);
389         }
390
391       mbzl = iv0->base;
392       mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
393     }
394
395   mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
396
397   if (!nonzero_p (assumption))
398     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
399                                       niter->assumptions, assumption);
400   if (!zero_p (mbz))
401     niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
402                                       niter->may_be_zero, mbz);
403 }
404
405 /* Determines number of iterations of loop whose ending condition
406    is IV0 < IV1.  TYPE is the type of the iv.  The number of
407    iterations is stored to NITER.  */
408
409 static bool
410 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
411                          struct tree_niter_desc *niter,
412                          bool never_infinite ATTRIBUTE_UNUSED)
413 {
414   tree niter_type = unsigned_type_for (type);
415   tree delta, step, s;
416
417   if (nonzero_p (iv0->step))
418     {
419       niter->control = *iv0;
420       niter->cmp = LT_EXPR;
421       niter->bound = iv1->base;
422     }
423   else
424     {
425       niter->control = *iv1;
426       niter->cmp = GT_EXPR;
427       niter->bound = iv0->base;
428     }
429
430   delta = fold_build2 (MINUS_EXPR, niter_type,
431                        fold_convert (niter_type, iv1->base),
432                        fold_convert (niter_type, iv0->base));
433
434   /* First handle the special case that the step is +-1.  */
435   if ((iv0->step && integer_onep (iv0->step)
436        && zero_p (iv1->step))
437       || (iv1->step && integer_all_onesp (iv1->step)
438           && zero_p (iv0->step)))
439     {
440       /* for (i = iv0->base; i < iv1->base; i++)
441
442          or
443
444          for (i = iv1->base; i > iv0->base; i--).
445              
446          In both cases # of iterations is iv1->base - iv0->base, assuming that
447          iv1->base >= iv0->base.  */
448       niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
449                                         iv1->base, iv0->base);
450       niter->niter = delta;
451       return true;
452     }
453
454   if (nonzero_p (iv0->step))
455     step = fold_convert (niter_type, iv0->step);
456   else
457     step = fold_convert (niter_type,
458                          fold_build1 (NEGATE_EXPR, type, iv1->step));
459
460   /* If we can determine the final value of the control iv exactly, we can
461      transform the condition to != comparison.  In particular, this will be
462      the case if DELTA is constant.  */
463   if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step))
464     {
465       affine_iv zps;
466
467       zps.base = build_int_cst_type (niter_type, 0);
468       zps.step = step;
469       /* number_of_iterations_lt_to_ne will add assumptions that ensure that
470          zps does not overflow.  */
471       zps.no_overflow = true;
472
473       return number_of_iterations_ne (type, &zps, delta, niter, true);
474     }
475
476   /* Make sure that the control iv does not overflow.  */
477   if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
478     return false;
479
480   /* We determine the number of iterations as (delta + step - 1) / step.  For
481      this to work, we must know that iv1->base >= iv0->base - step + 1,
482      otherwise the loop does not roll.  */
483   assert_loop_rolls_lt (type, iv0, iv1, niter);
484
485   s = fold_build2 (MINUS_EXPR, niter_type,
486                    step, build_int_cst_type (niter_type, 1));
487   delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
488   niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
489   return true;
490 }
491
492 /* Determines number of iterations of loop whose ending condition
493    is IV0 <= IV1.  TYPE is the type of the iv.  The number of
494    iterations is stored to NITER.  NEVER_INFINITE is true if
495    we know that the loop cannot be infinite (we derived this
496    earlier, and possibly set NITER->assumptions to make sure this
497    is the case.  */
498
499 static bool
500 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
501                          struct tree_niter_desc *niter, bool never_infinite)
502 {
503   tree assumption;
504
505   /* Say that IV0 is the control variable.  Then IV0 <= IV1 iff
506      IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
507      value of the type.  This we must know anyway, since if it is
508      equal to this value, the loop rolls forever.  */
509
510   if (!never_infinite)
511     {
512       if (nonzero_p (iv0->step))
513         assumption = fold_build2 (NE_EXPR, boolean_type_node,
514                                   iv1->base, TYPE_MAX_VALUE (type));
515       else
516         assumption = fold_build2 (NE_EXPR, boolean_type_node,
517                                   iv0->base, TYPE_MIN_VALUE (type));
518
519       if (zero_p (assumption))
520         return false;
521       if (!nonzero_p (assumption))
522         niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
523                                           niter->assumptions, assumption);
524     }
525
526   if (nonzero_p (iv0->step))
527     iv1->base = fold_build2 (PLUS_EXPR, type,
528                              iv1->base, build_int_cst_type (type, 1));
529   else
530     iv0->base = fold_build2 (MINUS_EXPR, type,
531                              iv0->base, build_int_cst_type (type, 1));
532   return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
533 }
534
535 /* Determine the number of iterations according to condition (for staying
536    inside loop) which compares two induction variables using comparison
537    operator CODE.  The induction variable on left side of the comparison
538    is IV0, the right-hand side is IV1.  Both induction variables must have
539    type TYPE, which must be an integer or pointer type.  The steps of the
540    ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
541    
542    The results (number of iterations and assumptions as described in
543    comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
544    Returns false if it fails to determine number of iterations, true if it
545    was determined (possibly with some assumptions).  */
546
547 static bool
548 number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code,
549                            affine_iv *iv1, struct tree_niter_desc *niter)
550 {
551   bool never_infinite;
552
553   /* The meaning of these assumptions is this:
554      if !assumptions
555        then the rest of information does not have to be valid
556      if may_be_zero then the loop does not roll, even if
557        niter != 0.  */
558   niter->assumptions = boolean_true_node;
559   niter->may_be_zero = boolean_false_node;
560   niter->niter = NULL_TREE;
561   niter->additional_info = boolean_true_node;
562
563   niter->bound = NULL_TREE;
564   niter->cmp = ERROR_MARK;
565
566   /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
567      the control variable is on lhs.  */
568   if (code == GE_EXPR || code == GT_EXPR
569       || (code == NE_EXPR && zero_p (iv0->step)))
570     {
571       SWAP (iv0, iv1);
572       code = swap_tree_comparison (code);
573     }
574
575   if (POINTER_TYPE_P (type))
576     {
577       /* Comparison of pointers is undefined unless both iv0 and iv1 point
578          to the same object.  If they do, the control variable cannot wrap
579          (as wrap around the bounds of memory will never return a pointer
580          that would be guaranteed to point to the same object, even if we
581          avoid undefined behavior by casting to size_t and back).  */
582       iv0->no_overflow = true;
583       iv1->no_overflow = true;
584     }
585
586   /* If the control induction variable does not overflow, the loop obviously
587      cannot be infinite.  */
588   if (!zero_p (iv0->step) && iv0->no_overflow)
589     never_infinite = true;
590   else if (!zero_p (iv1->step) && iv1->no_overflow)
591     never_infinite = true;
592   else
593     never_infinite = false;
594
595   /* We can handle the case when neither of the sides of the comparison is
596      invariant, provided that the test is NE_EXPR.  This rarely occurs in
597      practice, but it is simple enough to manage.  */
598   if (!zero_p (iv0->step) && !zero_p (iv1->step))
599     {
600       if (code != NE_EXPR)
601         return false;
602
603       iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
604                                            iv0->step, iv1->step);
605       iv0->no_overflow = false;
606       iv1->step = NULL_TREE;
607       iv1->no_overflow = true;
608     }
609
610   /* If the result of the comparison is a constant,  the loop is weird.  More
611      precise handling would be possible, but the situation is not common enough
612      to waste time on it.  */
613   if (zero_p (iv0->step) && zero_p (iv1->step))
614     return false;
615
616   /* Ignore loops of while (i-- < 10) type.  */
617   if (code != NE_EXPR)
618     {
619       if (iv0->step && tree_int_cst_sign_bit (iv0->step))
620         return false;
621
622       if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
623         return false;
624     }
625
626   /* If the loop exits immediately, there is nothing to do.  */
627   if (zero_p (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
628     {
629       niter->niter = build_int_cst_type (unsigned_type_for (type), 0);
630       return true;
631     }
632
633   /* OK, now we know we have a senseful loop.  Handle several cases, depending
634      on what comparison operator is used.  */
635   switch (code)
636     {
637     case NE_EXPR:
638       gcc_assert (zero_p (iv1->step));
639       return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite);
640     case LT_EXPR:
641       return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
642     case LE_EXPR:
643       return number_of_iterations_le (type, iv0, iv1, niter, never_infinite);
644     default:
645       gcc_unreachable ();
646     }
647 }
648
649 /* Substitute NEW for OLD in EXPR and fold the result.  */
650
651 static tree
652 simplify_replace_tree (tree expr, tree old, tree new)
653 {
654   unsigned i, n;
655   tree ret = NULL_TREE, e, se;
656
657   if (!expr)
658     return NULL_TREE;
659
660   if (expr == old
661       || operand_equal_p (expr, old, 0))
662     return unshare_expr (new);
663
664   if (!EXPR_P (expr))
665     return expr;
666
667   n = TREE_CODE_LENGTH (TREE_CODE (expr));
668   for (i = 0; i < n; i++)
669     {
670       e = TREE_OPERAND (expr, i);
671       se = simplify_replace_tree (e, old, new);
672       if (e == se)
673         continue;
674
675       if (!ret)
676         ret = copy_node (expr);
677
678       TREE_OPERAND (ret, i) = se;
679     }
680
681   return (ret ? fold (ret) : expr);
682 }
683
684 /* Expand definitions of ssa names in EXPR as long as they are simple
685    enough, and return the new expression.  */
686
687 tree
688 expand_simple_operations (tree expr)
689 {
690   unsigned i, n;
691   tree ret = NULL_TREE, e, ee, stmt;
692   enum tree_code code;
693
694   if (expr == NULL_TREE)
695     return expr;
696
697   if (is_gimple_min_invariant (expr))
698     return expr;
699
700   code = TREE_CODE (expr);
701   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
702     {
703       n = TREE_CODE_LENGTH (code);
704       for (i = 0; i < n; i++)
705         {
706           e = TREE_OPERAND (expr, i);
707           ee = expand_simple_operations (e);
708           if (e == ee)
709             continue;
710
711           if (!ret)
712             ret = copy_node (expr);
713
714           TREE_OPERAND (ret, i) = ee;
715         }
716
717       return (ret ? fold (ret) : expr);
718     }
719
720   if (TREE_CODE (expr) != SSA_NAME)
721     return expr;
722
723   stmt = SSA_NAME_DEF_STMT (expr);
724   if (TREE_CODE (stmt) != MODIFY_EXPR)
725     return expr;
726
727   e = TREE_OPERAND (stmt, 1);
728   if (/* Casts are simple.  */
729       TREE_CODE (e) != NOP_EXPR
730       && TREE_CODE (e) != CONVERT_EXPR
731       /* Copies are simple.  */
732       && TREE_CODE (e) != SSA_NAME
733       /* Assignments of invariants are simple.  */
734       && !is_gimple_min_invariant (e)
735       /* And increments and decrements by a constant are simple.  */
736       && !((TREE_CODE (e) == PLUS_EXPR
737             || TREE_CODE (e) == MINUS_EXPR)
738            && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
739     return expr;
740
741   return expand_simple_operations (e);
742 }
743
744 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
745    expression (or EXPR unchanged, if no simplification was possible).  */
746
747 static tree
748 tree_simplify_using_condition_1 (tree cond, tree expr)
749 {
750   bool changed;
751   tree e, te, e0, e1, e2, notcond;
752   enum tree_code code = TREE_CODE (expr);
753
754   if (code == INTEGER_CST)
755     return expr;
756
757   if (code == TRUTH_OR_EXPR
758       || code == TRUTH_AND_EXPR
759       || code == COND_EXPR)
760     {
761       changed = false;
762
763       e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
764       if (TREE_OPERAND (expr, 0) != e0)
765         changed = true;
766
767       e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
768       if (TREE_OPERAND (expr, 1) != e1)
769         changed = true;
770
771       if (code == COND_EXPR)
772         {
773           e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
774           if (TREE_OPERAND (expr, 2) != e2)
775             changed = true;
776         }
777       else
778         e2 = NULL_TREE;
779
780       if (changed)
781         {
782           if (code == COND_EXPR)
783             expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
784           else
785             expr = fold_build2 (code, boolean_type_node, e0, e1);
786         }
787
788       return expr;
789     }
790
791   /* In case COND is equality, we may be able to simplify EXPR by copy/constant
792      propagation, and vice versa.  Fold does not handle this, since it is
793      considered too expensive.  */
794   if (TREE_CODE (cond) == EQ_EXPR)
795     {
796       e0 = TREE_OPERAND (cond, 0);
797       e1 = TREE_OPERAND (cond, 1);
798
799       /* We know that e0 == e1.  Check whether we cannot simplify expr
800          using this fact.  */
801       e = simplify_replace_tree (expr, e0, e1);
802       if (zero_p (e) || nonzero_p (e))
803         return e;
804
805       e = simplify_replace_tree (expr, e1, e0);
806       if (zero_p (e) || nonzero_p (e))
807         return e;
808     }
809   if (TREE_CODE (expr) == EQ_EXPR)
810     {
811       e0 = TREE_OPERAND (expr, 0);
812       e1 = TREE_OPERAND (expr, 1);
813
814       /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true.  */
815       e = simplify_replace_tree (cond, e0, e1);
816       if (zero_p (e))
817         return e;
818       e = simplify_replace_tree (cond, e1, e0);
819       if (zero_p (e))
820         return e;
821     }
822   if (TREE_CODE (expr) == NE_EXPR)
823     {
824       e0 = TREE_OPERAND (expr, 0);
825       e1 = TREE_OPERAND (expr, 1);
826
827       /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true.  */
828       e = simplify_replace_tree (cond, e0, e1);
829       if (zero_p (e))
830         return boolean_true_node;
831       e = simplify_replace_tree (cond, e1, e0);
832       if (zero_p (e))
833         return boolean_true_node;
834     }
835
836   te = expand_simple_operations (expr);
837
838   /* Check whether COND ==> EXPR.  */
839   notcond = invert_truthvalue (cond);
840   e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
841   if (nonzero_p (e))
842     return e;
843
844   /* Check whether COND ==> not EXPR.  */
845   e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
846   if (e && zero_p (e))
847     return e;
848
849   return expr;
850 }
851
852 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
853    expression (or EXPR unchanged, if no simplification was possible).
854    Wrapper around tree_simplify_using_condition_1 that ensures that chains
855    of simple operations in definitions of ssa names in COND are expanded,
856    so that things like casts or incrementing the value of the bound before
857    the loop do not cause us to fail.  */
858
859 static tree
860 tree_simplify_using_condition (tree cond, tree expr)
861 {
862   cond = expand_simple_operations (cond);
863
864   return tree_simplify_using_condition_1 (cond, expr);
865 }
866      
867 /* Tries to simplify EXPR using the conditions on entry to LOOP.
868    Record the conditions used for simplification to CONDS_USED.
869    Returns the simplified expression (or EXPR unchanged, if no
870    simplification was possible).*/
871
872 static tree
873 simplify_using_initial_conditions (struct loop *loop, tree expr,
874                                    tree *conds_used)
875 {
876   edge e;
877   basic_block bb;
878   tree exp, cond;
879
880   if (TREE_CODE (expr) == INTEGER_CST)
881     return expr;
882
883   for (bb = loop->header;
884        bb != ENTRY_BLOCK_PTR;
885        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
886     {
887       if (!single_pred_p (bb))
888         continue;
889       e = single_pred_edge (bb);
890
891       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
892         continue;
893
894       cond = COND_EXPR_COND (last_stmt (e->src));
895       if (e->flags & EDGE_FALSE_VALUE)
896         cond = invert_truthvalue (cond);
897       exp = tree_simplify_using_condition (cond, expr);
898
899       if (exp != expr)
900         *conds_used = fold_build2 (TRUTH_AND_EXPR,
901                                    boolean_type_node,
902                                    *conds_used,
903                                    cond);
904
905       expr = exp;
906     }
907
908   return expr;
909 }
910
911 /* Tries to simplify EXPR using the evolutions of the loop invariants
912    in the superloops of LOOP.  Returns the simplified expression
913    (or EXPR unchanged, if no simplification was possible).  */
914
915 static tree
916 simplify_using_outer_evolutions (struct loop *loop, tree expr)
917 {
918   enum tree_code code = TREE_CODE (expr);
919   bool changed;
920   tree e, e0, e1, e2;
921
922   if (is_gimple_min_invariant (expr))
923     return expr;
924
925   if (code == TRUTH_OR_EXPR
926       || code == TRUTH_AND_EXPR
927       || code == COND_EXPR)
928     {
929       changed = false;
930
931       e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
932       if (TREE_OPERAND (expr, 0) != e0)
933         changed = true;
934
935       e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
936       if (TREE_OPERAND (expr, 1) != e1)
937         changed = true;
938
939       if (code == COND_EXPR)
940         {
941           e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
942           if (TREE_OPERAND (expr, 2) != e2)
943             changed = true;
944         }
945       else
946         e2 = NULL_TREE;
947
948       if (changed)
949         {
950           if (code == COND_EXPR)
951             expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
952           else
953             expr = fold_build2 (code, boolean_type_node, e0, e1);
954         }
955
956       return expr;
957     }
958
959   e = instantiate_parameters (loop, expr);
960   if (is_gimple_min_invariant (e))
961     return e;
962
963   return expr;
964 }
965
966 /* Stores description of number of iterations of LOOP derived from
967    EXIT (an exit edge of the LOOP) in NITER.  Returns true if some
968    useful information could be derived (and fields of NITER has
969    meaning described in comments at struct tree_niter_desc
970    declaration), false otherwise.  If WARN is true and
971    -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
972    potentially unsafe assumptions.  */
973
974 bool
975 number_of_iterations_exit (struct loop *loop, edge exit,
976                            struct tree_niter_desc *niter,
977                            bool warn)
978 {
979   tree stmt, cond, type;
980   tree op0, op1;
981   enum tree_code code;
982   affine_iv iv0, iv1;
983
984   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
985     return false;
986
987   niter->assumptions = boolean_false_node;
988   stmt = last_stmt (exit->src);
989   if (!stmt || TREE_CODE (stmt) != COND_EXPR)
990     return false;
991
992   /* We want the condition for staying inside loop.  */
993   cond = COND_EXPR_COND (stmt);
994   if (exit->flags & EDGE_TRUE_VALUE)
995     cond = invert_truthvalue (cond);
996
997   code = TREE_CODE (cond);
998   switch (code)
999     {
1000     case GT_EXPR:
1001     case GE_EXPR:
1002     case NE_EXPR:
1003     case LT_EXPR:
1004     case LE_EXPR:
1005       break;
1006
1007     default:
1008       return false;
1009     }
1010   
1011   op0 = TREE_OPERAND (cond, 0);
1012   op1 = TREE_OPERAND (cond, 1);
1013   type = TREE_TYPE (op0);
1014
1015   if (TREE_CODE (type) != INTEGER_TYPE
1016       && !POINTER_TYPE_P (type))
1017     return false;
1018      
1019   if (!simple_iv (loop, stmt, op0, &iv0, false))
1020     return false;
1021   if (!simple_iv (loop, stmt, op1, &iv1, false))
1022     return false;
1023
1024   iv0.base = expand_simple_operations (iv0.base);
1025   iv1.base = expand_simple_operations (iv1.base);
1026   if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter))
1027     return false;
1028
1029   if (optimize >= 3)
1030     {
1031       niter->assumptions = simplify_using_outer_evolutions (loop,
1032                                                             niter->assumptions);
1033       niter->may_be_zero = simplify_using_outer_evolutions (loop,
1034                                                             niter->may_be_zero);
1035       niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1036     }
1037
1038   niter->additional_info = boolean_true_node;
1039   niter->assumptions
1040           = simplify_using_initial_conditions (loop,
1041                                                niter->assumptions,
1042                                                &niter->additional_info);
1043   niter->may_be_zero
1044           = simplify_using_initial_conditions (loop,
1045                                                niter->may_be_zero,
1046                                                &niter->additional_info);
1047
1048   if (integer_onep (niter->assumptions))
1049     return true;
1050
1051   /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1052      But if we can prove that there is overflow or some other source of weird
1053      behavior, ignore the loop even with -funsafe-loop-optimizations.  */
1054   if (integer_zerop (niter->assumptions))
1055     return false;
1056
1057   if (flag_unsafe_loop_optimizations)
1058     niter->assumptions = boolean_true_node;
1059
1060   if (warn)
1061     {
1062       const char *wording;
1063       location_t loc = EXPR_LOCATION (stmt);
1064   
1065       /* We can provide a more specific warning if one of the operator is
1066          constant and the other advances by +1 or -1.  */
1067       if (!zero_p (iv1.step)
1068           ? (zero_p (iv0.step)
1069              && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1070           : (iv0.step
1071              && (integer_onep (iv0.step) || integer_all_onesp (iv0.step))))
1072         wording =
1073           flag_unsafe_loop_optimizations
1074           ? N_("assuming that the loop is not infinite")
1075           : N_("cannot optimize possibly infinite loops");
1076       else
1077         wording = 
1078           flag_unsafe_loop_optimizations
1079           ? N_("assuming that the loop counter does not overflow")
1080           : N_("cannot optimize loop, the loop counter may overflow");
1081
1082       if (LOCATION_LINE (loc) > 0)
1083         warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
1084       else
1085         warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1086     }
1087
1088   return flag_unsafe_loop_optimizations;
1089 }
1090
1091 /* Try to determine the number of iterations of LOOP.  If we succeed,
1092    expression giving number of iterations is returned and *EXIT is
1093    set to the edge from that the information is obtained.  Otherwise
1094    chrec_dont_know is returned.  */
1095
1096 tree
1097 find_loop_niter (struct loop *loop, edge *exit)
1098 {
1099   unsigned n_exits, i;
1100   edge *exits = get_loop_exit_edges (loop, &n_exits);
1101   edge ex;
1102   tree niter = NULL_TREE, aniter;
1103   struct tree_niter_desc desc;
1104
1105   *exit = NULL;
1106   for (i = 0; i < n_exits; i++)
1107     {
1108       ex = exits[i];
1109       if (!just_once_each_iteration_p (loop, ex->src))
1110         continue;
1111
1112       if (!number_of_iterations_exit (loop, ex, &desc, false))
1113         continue;
1114
1115       if (nonzero_p (desc.may_be_zero))
1116         {
1117           /* We exit in the first iteration through this exit.
1118              We won't find anything better.  */
1119           niter = build_int_cst_type (unsigned_type_node, 0);
1120           *exit = ex;
1121           break;
1122         }
1123
1124       if (!zero_p (desc.may_be_zero))
1125         continue;
1126
1127       aniter = desc.niter;
1128
1129       if (!niter)
1130         {
1131           /* Nothing recorded yet.  */
1132           niter = aniter;
1133           *exit = ex;
1134           continue;
1135         }
1136
1137       /* Prefer constants, the lower the better.  */
1138       if (TREE_CODE (aniter) != INTEGER_CST)
1139         continue;
1140
1141       if (TREE_CODE (niter) != INTEGER_CST)
1142         {
1143           niter = aniter;
1144           *exit = ex;
1145           continue;
1146         }
1147
1148       if (tree_int_cst_lt (aniter, niter))
1149         {
1150           niter = aniter;
1151           *exit = ex;
1152           continue;
1153         }
1154     }
1155   free (exits);
1156
1157   return niter ? niter : chrec_dont_know;
1158 }
1159
1160 /*
1161
1162    Analysis of a number of iterations of a loop by a brute-force evaluation.
1163
1164 */
1165
1166 /* Bound on the number of iterations we try to evaluate.  */
1167
1168 #define MAX_ITERATIONS_TO_TRACK \
1169   ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1170
1171 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1172    result by a chain of operations such that all but exactly one of their
1173    operands are constants.  */
1174
1175 static tree
1176 chain_of_csts_start (struct loop *loop, tree x)
1177 {
1178   tree stmt = SSA_NAME_DEF_STMT (x);
1179   tree use;
1180   basic_block bb = bb_for_stmt (stmt);
1181
1182   if (!bb
1183       || !flow_bb_inside_loop_p (loop, bb))
1184     return NULL_TREE;
1185   
1186   if (TREE_CODE (stmt) == PHI_NODE)
1187     {
1188       if (bb == loop->header)
1189         return stmt;
1190
1191       return NULL_TREE;
1192     }
1193
1194   if (TREE_CODE (stmt) != MODIFY_EXPR)
1195     return NULL_TREE;
1196
1197   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1198     return NULL_TREE;
1199   if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
1200     return NULL_TREE;
1201
1202   use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1203   if (use == NULL_USE_OPERAND_P)
1204     return NULL_TREE;
1205
1206   return chain_of_csts_start (loop, use);
1207 }
1208
1209 /* Determines whether the expression X is derived from a result of a phi node
1210    in header of LOOP such that
1211
1212    * the derivation of X consists only from operations with constants
1213    * the initial value of the phi node is constant
1214    * the value of the phi node in the next iteration can be derived from the
1215      value in the current iteration by a chain of operations with constants.
1216    
1217    If such phi node exists, it is returned.  If X is a constant, X is returned
1218    unchanged.  Otherwise NULL_TREE is returned.  */
1219
1220 static tree
1221 get_base_for (struct loop *loop, tree x)
1222 {
1223   tree phi, init, next;
1224
1225   if (is_gimple_min_invariant (x))
1226     return x;
1227
1228   phi = chain_of_csts_start (loop, x);
1229   if (!phi)
1230     return NULL_TREE;
1231
1232   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1233   next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1234
1235   if (TREE_CODE (next) != SSA_NAME)
1236     return NULL_TREE;
1237
1238   if (!is_gimple_min_invariant (init))
1239     return NULL_TREE;
1240
1241   if (chain_of_csts_start (loop, next) != phi)
1242     return NULL_TREE;
1243
1244   return phi;
1245 }
1246
1247 /* Given an expression X, then 
1248  
1249    * if BASE is NULL_TREE, X must be a constant and we return X.
1250    * otherwise X is a SSA name, whose value in the considered loop is derived
1251      by a chain of operations with constant from a result of a phi node in
1252      the header of the loop.  Then we return value of X when the value of the
1253      result of this phi node is given by the constant BASE.  */
1254
1255 static tree
1256 get_val_for (tree x, tree base)
1257 {
1258   tree stmt, nx, val;
1259   use_operand_p op;
1260   ssa_op_iter iter;
1261
1262   if (!x)
1263     return base;
1264
1265   stmt = SSA_NAME_DEF_STMT (x);
1266   if (TREE_CODE (stmt) == PHI_NODE)
1267     return base;
1268
1269   FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
1270     {
1271       nx = USE_FROM_PTR (op);
1272       val = get_val_for (nx, base);
1273       SET_USE (op, val);
1274       val = fold (TREE_OPERAND (stmt, 1));
1275       SET_USE (op, nx);
1276       /* only iterate loop once.  */
1277       return val;
1278     }
1279
1280   /* Should never reach here.  */
1281   gcc_unreachable();
1282 }
1283
1284 /* Tries to count the number of iterations of LOOP till it exits by EXIT
1285    by brute force -- i.e. by determining the value of the operands of the
1286    condition at EXIT in first few iterations of the loop (assuming that
1287    these values are constant) and determining the first one in that the
1288    condition is not satisfied.  Returns the constant giving the number
1289    of the iterations of LOOP if successful, chrec_dont_know otherwise.  */
1290
1291 tree
1292 loop_niter_by_eval (struct loop *loop, edge exit)
1293 {
1294   tree cond, cnd, acnd;
1295   tree op[2], val[2], next[2], aval[2], phi[2];
1296   unsigned i, j;
1297   enum tree_code cmp;
1298
1299   cond = last_stmt (exit->src);
1300   if (!cond || TREE_CODE (cond) != COND_EXPR)
1301     return chrec_dont_know;
1302
1303   cnd = COND_EXPR_COND (cond);
1304   if (exit->flags & EDGE_TRUE_VALUE)
1305     cnd = invert_truthvalue (cnd);
1306
1307   cmp = TREE_CODE (cnd);
1308   switch (cmp)
1309     {
1310     case EQ_EXPR:
1311     case NE_EXPR:
1312     case GT_EXPR:
1313     case GE_EXPR:
1314     case LT_EXPR:
1315     case LE_EXPR:
1316       for (j = 0; j < 2; j++)
1317         op[j] = TREE_OPERAND (cnd, j);
1318       break;
1319
1320     default:
1321       return chrec_dont_know;
1322     }
1323
1324   for (j = 0; j < 2; j++)
1325     {
1326       phi[j] = get_base_for (loop, op[j]);
1327       if (!phi[j])
1328         return chrec_dont_know;
1329     }
1330
1331   for (j = 0; j < 2; j++)
1332     {
1333       if (TREE_CODE (phi[j]) == PHI_NODE)
1334         {
1335           val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
1336           next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
1337         }
1338       else
1339         {
1340           val[j] = phi[j];
1341           next[j] = NULL_TREE;
1342           op[j] = NULL_TREE;
1343         }
1344     }
1345
1346   for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
1347     {
1348       for (j = 0; j < 2; j++)
1349         aval[j] = get_val_for (op[j], val[j]);
1350
1351       acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
1352       if (acnd && zero_p (acnd))
1353         {
1354           if (dump_file && (dump_flags & TDF_DETAILS))
1355             fprintf (dump_file,
1356                      "Proved that loop %d iterates %d times using brute force.\n",
1357                      loop->num, i);
1358           return build_int_cst (unsigned_type_node, i);
1359         }
1360
1361       for (j = 0; j < 2; j++)
1362         val[j] = get_val_for (next[j], val[j]);
1363     }
1364
1365   return chrec_dont_know;
1366 }
1367
1368 /* Finds the exit of the LOOP by that the loop exits after a constant
1369    number of iterations and stores the exit edge to *EXIT.  The constant
1370    giving the number of iterations of LOOP is returned.  The number of
1371    iterations is determined using loop_niter_by_eval (i.e. by brute force
1372    evaluation).  If we are unable to find the exit for that loop_niter_by_eval
1373    determines the number of iterations, chrec_dont_know is returned.  */
1374
1375 tree
1376 find_loop_niter_by_eval (struct loop *loop, edge *exit)
1377 {
1378   unsigned n_exits, i;
1379   edge *exits = get_loop_exit_edges (loop, &n_exits);
1380   edge ex;
1381   tree niter = NULL_TREE, aniter;
1382
1383   *exit = NULL;
1384   for (i = 0; i < n_exits; i++)
1385     {
1386       ex = exits[i];
1387       if (!just_once_each_iteration_p (loop, ex->src))
1388         continue;
1389
1390       aniter = loop_niter_by_eval (loop, ex);
1391       if (chrec_contains_undetermined (aniter))
1392         continue;
1393
1394       if (niter
1395           && !tree_int_cst_lt (aniter, niter))
1396         continue;
1397
1398       niter = aniter;
1399       *exit = ex;
1400     }
1401   free (exits);
1402
1403   return niter ? niter : chrec_dont_know;
1404 }
1405
1406 /*
1407
1408    Analysis of upper bounds on number of iterations of a loop.
1409
1410 */
1411
1412 /* Records that AT_STMT is executed at most BOUND times in LOOP.  The
1413    additional condition ADDITIONAL is recorded with the bound.  */
1414
1415 void
1416 record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
1417 {
1418   struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
1419
1420   if (dump_file && (dump_flags & TDF_DETAILS))
1421     {
1422       fprintf (dump_file, "Statements after ");
1423       print_generic_expr (dump_file, at_stmt, TDF_SLIM);
1424       fprintf (dump_file, " are executed at most ");
1425       print_generic_expr (dump_file, bound, TDF_SLIM);
1426       fprintf (dump_file, " times in loop %d.\n", loop->num);
1427     }
1428
1429   elt->bound = bound;
1430   elt->at_stmt = at_stmt;
1431   elt->additional = additional;
1432   elt->next = loop->bounds;
1433   loop->bounds = elt;
1434 }
1435
1436 /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
1437    approximation of the number of iterations for LOOP.  */
1438
1439 static void
1440 compute_estimated_nb_iterations (struct loop *loop)
1441 {
1442   struct nb_iter_bound *bound;
1443   
1444   for (bound = loop->bounds; bound; bound = bound->next)
1445     if (TREE_CODE (bound->bound) == INTEGER_CST
1446         /* Update only when there is no previous estimation.  */
1447         && (chrec_contains_undetermined (loop->estimated_nb_iterations)
1448             /* Or when the current estimation is smaller.  */
1449             || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)))
1450       loop->estimated_nb_iterations = bound->bound;
1451 }
1452
1453 /* The following analyzers are extracting informations on the bounds
1454    of LOOP from the following undefined behaviors:
1455
1456    - data references should not access elements over the statically
1457      allocated size,
1458
1459    - signed variables should not overflow when flag_wrapv is not set.
1460 */
1461
1462 static void
1463 infer_loop_bounds_from_undefined (struct loop *loop)
1464 {
1465   unsigned i;
1466   basic_block bb, *bbs;
1467   block_stmt_iterator bsi;
1468   
1469   bbs = get_loop_body (loop);
1470
1471   for (i = 0; i < loop->num_nodes; i++)
1472     {
1473       bb = bbs[i];
1474
1475       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1476         {
1477           tree stmt = bsi_stmt (bsi);
1478
1479           switch (TREE_CODE (stmt))
1480             {
1481             case MODIFY_EXPR:
1482               {
1483                 tree op0 = TREE_OPERAND (stmt, 0);
1484                 tree op1 = TREE_OPERAND (stmt, 1);
1485
1486                 /* For each array access, analyze its access function
1487                    and record a bound on the loop iteration domain.  */
1488                 if (TREE_CODE (op1) == ARRAY_REF 
1489                     && !array_ref_contains_indirect_ref (op1))
1490                   estimate_iters_using_array (stmt, op1);
1491
1492                 if (TREE_CODE (op0) == ARRAY_REF 
1493                     && !array_ref_contains_indirect_ref (op0))
1494                   estimate_iters_using_array (stmt, op0);
1495
1496                 /* For each signed type variable in LOOP, analyze its
1497                    scalar evolution and record a bound of the loop
1498                    based on the type's ranges.  */
1499                 else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME)
1500                   {
1501                     tree init, step, diff, estimation;
1502                     tree scev = instantiate_parameters 
1503                       (loop, analyze_scalar_evolution (loop, op0));
1504                     tree type = chrec_type (scev);
1505                     tree utype;
1506
1507                     if (chrec_contains_undetermined (scev)
1508                         || TYPE_UNSIGNED (type))
1509                       break;
1510
1511                     init = initial_condition_in_loop_num (scev, loop->num);
1512                     step = evolution_part_in_loop_num (scev, loop->num);
1513
1514                     if (init == NULL_TREE
1515                         || step == NULL_TREE
1516                         || TREE_CODE (init) != INTEGER_CST
1517                         || TREE_CODE (step) != INTEGER_CST
1518                         || TYPE_MIN_VALUE (type) == NULL_TREE
1519                         || TYPE_MAX_VALUE (type) == NULL_TREE)
1520                       break;
1521
1522                     utype = unsigned_type_for (type);
1523                     if (tree_int_cst_lt (step, integer_zero_node))
1524                       diff = fold_build2 (MINUS_EXPR, utype, init,
1525                                           TYPE_MIN_VALUE (type));
1526                     else
1527                       diff = fold_build2 (MINUS_EXPR, utype,
1528                                           TYPE_MAX_VALUE (type), init);
1529
1530                     estimation = fold_build2 (CEIL_DIV_EXPR, utype, diff,
1531                                               step);
1532                     record_estimate (loop, estimation, boolean_true_node, stmt);
1533                   }
1534
1535                 break;
1536               }
1537
1538             case CALL_EXPR:
1539               {
1540                 tree args;
1541
1542                 for (args = TREE_OPERAND (stmt, 1); args;
1543                      args = TREE_CHAIN (args))
1544                   if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
1545                       && !array_ref_contains_indirect_ref (TREE_VALUE (args)))
1546                     estimate_iters_using_array (stmt, TREE_VALUE (args));
1547
1548                 break;
1549               }
1550
1551             default:
1552               break;
1553             }
1554         }
1555
1556       if (chrec_contains_undetermined (loop->estimated_nb_iterations))
1557         compute_estimated_nb_iterations (loop);
1558     }
1559
1560   free (bbs);
1561 }
1562
1563 /* Records estimates on numbers of iterations of LOOP.  */
1564
1565 static void
1566 estimate_numbers_of_iterations_loop (struct loop *loop)
1567 {
1568   edge *exits;
1569   tree niter, type;
1570   unsigned i, n_exits;
1571   struct tree_niter_desc niter_desc;
1572
1573   /* Give up if we already have tried to compute an estimation.  */
1574   if (loop->estimated_nb_iterations == chrec_dont_know
1575       /* Or when we already have an estimation.  */
1576       || (loop->estimated_nb_iterations != NULL_TREE
1577           && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
1578     return;
1579   else
1580     loop->estimated_nb_iterations = chrec_dont_know;
1581
1582   exits = get_loop_exit_edges (loop, &n_exits);
1583   for (i = 0; i < n_exits; i++)
1584     {
1585       if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false))
1586         continue;
1587
1588       niter = niter_desc.niter;
1589       type = TREE_TYPE (niter);
1590       if (!zero_p (niter_desc.may_be_zero)
1591           && !nonzero_p (niter_desc.may_be_zero))
1592         niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
1593                         build_int_cst_type (type, 0),
1594                         niter);
1595       record_estimate (loop, niter,
1596                        niter_desc.additional_info,
1597                        last_stmt (exits[i]->src));
1598     }
1599   free (exits);
1600   
1601   if (chrec_contains_undetermined (loop->estimated_nb_iterations))
1602     infer_loop_bounds_from_undefined (loop);
1603 }
1604
1605 /* Records estimates on numbers of iterations of LOOPS.  */
1606
1607 void
1608 estimate_numbers_of_iterations (struct loops *loops)
1609 {
1610   unsigned i;
1611   struct loop *loop;
1612
1613   for (i = 1; i < loops->num; i++)
1614     {
1615       loop = loops->parray[i];
1616       if (loop)
1617         estimate_numbers_of_iterations_loop (loop);
1618     }
1619 }
1620
1621 /* If A > B, returns -1.  If A == B, returns 0.  If A < B, returns 1.
1622    If neither of these relations can be proved, returns 2.  */
1623
1624 static int
1625 compare_trees (tree a, tree b)
1626 {
1627   tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
1628   tree type;
1629
1630   if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
1631     type = typea;
1632   else
1633     type = typeb;
1634
1635   a = fold_convert (type, a);
1636   b = fold_convert (type, b);
1637
1638   if (nonzero_p (fold_binary (EQ_EXPR, boolean_type_node, a, b)))
1639     return 0;
1640   if (nonzero_p (fold_binary (LT_EXPR, boolean_type_node, a, b)))
1641     return 1;
1642   if (nonzero_p (fold_binary (GT_EXPR, boolean_type_node, a, b)))
1643     return -1;
1644
1645   return 2;
1646 }
1647
1648 /* Returns true if statement S1 dominates statement S2.  */
1649
1650 static bool
1651 stmt_dominates_stmt_p (tree s1, tree s2)
1652 {
1653   basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
1654
1655   if (!bb1
1656       || s1 == s2)
1657     return true;
1658
1659   if (bb1 == bb2)
1660     {
1661       block_stmt_iterator bsi;
1662
1663       for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
1664         if (bsi_stmt (bsi) == s1)
1665           return true;
1666
1667       return false;
1668     }
1669
1670   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
1671 }
1672
1673 /* Return true when it is possible to prove that the induction
1674    variable does not wrap: vary outside the type specified bounds.
1675    Checks whether BOUND < VALID_NITER that means in the context of iv
1676    conversion that all the iterations in the loop are safe: not
1677    producing wraps.
1678
1679    The statement NITER_BOUND->AT_STMT is executed at most
1680    NITER_BOUND->BOUND times in the loop.
1681    
1682    NITER_BOUND->ADDITIONAL is the additional condition recorded for
1683    operands of the bound.  This is useful in the following case,
1684    created by loop header copying:
1685
1686    i = 0;
1687    if (n > 0)
1688      do
1689        {
1690          something;
1691        } while (++i < n)
1692
1693    If the n > 0 condition is taken into account, the number of iterations of the
1694    loop can be expressed as n - 1.  If the type of n is signed, the ADDITIONAL
1695    assumption "n > 0" says us that the value of the number of iterations is at
1696    most MAX_TYPE - 1 (without this assumption, it might overflow).  */
1697
1698 static bool
1699 proved_non_wrapping_p (tree at_stmt,
1700                        struct nb_iter_bound *niter_bound, 
1701                        tree new_type,
1702                        tree valid_niter)
1703 {
1704   tree cond;
1705   tree bound = niter_bound->bound;
1706   enum tree_code cmp;
1707
1708   if (TYPE_PRECISION (new_type) > TYPE_PRECISION (TREE_TYPE (bound)))
1709     bound = fold_convert (unsigned_type_for (new_type), bound);
1710   else
1711     valid_niter = fold_convert (TREE_TYPE (bound), valid_niter);
1712
1713   /* Give up if BOUND was not folded to an INTEGER_CST, as in PR23434.  */
1714   if (TREE_CODE (bound) != INTEGER_CST)
1715     return false;
1716
1717   /* After the statement niter_bound->at_stmt we know that anything is
1718      executed at most BOUND times.  */
1719   if (at_stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, at_stmt))
1720     cmp = GE_EXPR;
1721   /* Before the statement niter_bound->at_stmt we know that anything
1722      is executed at most BOUND + 1 times.  */
1723   else
1724     cmp = GT_EXPR;
1725
1726   cond = fold_binary (cmp, boolean_type_node, valid_niter, bound);
1727   if (nonzero_p (cond))
1728     return true;
1729
1730   cond = build2 (cmp, boolean_type_node, valid_niter, bound);
1731   /* Try taking additional conditions into account.  */
1732   cond = fold_binary (TRUTH_OR_EXPR, boolean_type_node,
1733                       invert_truthvalue (niter_bound->additional),
1734                       cond);
1735
1736   if (nonzero_p (cond))
1737     return true;
1738
1739   return false;
1740 }
1741
1742 /* Checks whether it is correct to count the induction variable BASE +
1743    STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
1744    numbers of iterations of a LOOP.  If it is possible, return the
1745    value of step of the induction variable in the NEW_TYPE, otherwise
1746    return NULL_TREE.  */
1747
1748 static tree
1749 convert_step_widening (struct loop *loop, tree new_type, tree base, tree step,
1750                        tree at_stmt)
1751 {
1752   struct nb_iter_bound *bound;
1753   tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type;
1754   tree delta, step_abs;
1755   tree unsigned_type, valid_niter;
1756
1757   /* Compute the new step.  For example, {(uchar) 100, +, (uchar) 240}
1758      is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to
1759      keep the values of the induction variable unchanged: 100, 84, 68,
1760      ...
1761
1762      Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
1763      to {(uint)100, +, (uint)3}.  
1764
1765      Before returning the new step, verify that the number of
1766      iterations is less than DELTA / STEP_ABS (i.e. in the previous
1767      example (256 - 100) / 3) such that the iv does not wrap (in which
1768      case the operations are too difficult to be represented and
1769      handled: the values of the iv should be taken modulo 256 in the
1770      wider type; this is not implemented).  */
1771   base_in_new_type = fold_convert (new_type, base);
1772   base_plus_step_in_new_type = 
1773     fold_convert (new_type,
1774                   fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step));
1775   step_in_new_type = fold_build2 (MINUS_EXPR, new_type,
1776                                   base_plus_step_in_new_type,
1777                                   base_in_new_type);
1778
1779   if (TREE_CODE (step_in_new_type) != INTEGER_CST)
1780     return NULL_TREE;
1781
1782   switch (compare_trees (base_plus_step_in_new_type, base_in_new_type))
1783     {
1784     case -1:
1785       {
1786         tree extreme = upper_bound_in_type (new_type, TREE_TYPE (base));
1787         delta = fold_build2 (MINUS_EXPR, new_type, extreme,
1788                              base_in_new_type);
1789         step_abs = step_in_new_type;
1790         break;
1791       }
1792
1793     case 1:
1794       {
1795         tree extreme = lower_bound_in_type (new_type, TREE_TYPE (base));
1796         delta = fold_build2 (MINUS_EXPR, new_type, base_in_new_type,
1797                              extreme);
1798         step_abs = fold_build1 (NEGATE_EXPR, new_type, step_in_new_type);
1799         break;
1800       }
1801
1802     case 0:
1803       return step_in_new_type;
1804
1805     default:
1806       return NULL_TREE;
1807     }
1808
1809   unsigned_type = unsigned_type_for (new_type);
1810   delta = fold_convert (unsigned_type, delta);
1811   step_abs = fold_convert (unsigned_type, step_abs);
1812   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
1813                              delta, step_abs);
1814
1815   estimate_numbers_of_iterations_loop (loop);
1816   for (bound = loop->bounds; bound; bound = bound->next)
1817     if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter))
1818       return step_in_new_type;
1819
1820   /* Fail when the loop has no bound estimations, or when no bound can
1821      be used for verifying the conversion.  */
1822   return NULL_TREE;
1823 }
1824
1825 /* Returns true when VAR is used in pointer arithmetics.  DEPTH is
1826    used for limiting the search.  */
1827
1828 static bool
1829 used_in_pointer_arithmetic_p (tree var, int depth)
1830 {
1831   use_operand_p use_p;
1832   imm_use_iterator iter;
1833
1834   if (depth == 0
1835       || TREE_CODE (var) != SSA_NAME
1836       || !has_single_use (var))
1837     return false;
1838
1839   FOR_EACH_IMM_USE_FAST (use_p, iter, var)
1840     {
1841       tree stmt = USE_STMT (use_p);
1842
1843       if (stmt && TREE_CODE (stmt) == MODIFY_EXPR)
1844         {
1845           tree rhs = TREE_OPERAND (stmt, 1);
1846
1847           if (TREE_CODE (rhs) == NOP_EXPR
1848               || TREE_CODE (rhs) == CONVERT_EXPR)
1849             {
1850               if (POINTER_TYPE_P (TREE_TYPE (rhs)))
1851                 return true;
1852               return false;
1853             }
1854           else
1855             return used_in_pointer_arithmetic_p (TREE_OPERAND (stmt, 0),
1856                                                  depth - 1);
1857         }
1858     }
1859   return false;
1860 }
1861
1862 /* Return false only when the induction variable BASE + STEP * I is
1863    known to not overflow: i.e. when the number of iterations is small
1864    enough with respect to the step and initial condition in order to
1865    keep the evolution confined in TYPEs bounds.  Return true when the
1866    iv is known to overflow or when the property is not computable.
1867
1868    Initialize INIT_IS_MAX to true when the evolution goes from
1869    INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case.
1870    When this property cannot be determined, UNKNOWN_MAX is set to
1871    true.  */
1872
1873 bool
1874 scev_probably_wraps_p (tree type, tree base, tree step, 
1875                        tree at_stmt, struct loop *loop,
1876                        bool *init_is_max, bool *unknown_max)
1877 {
1878   struct nb_iter_bound *bound;
1879   tree delta, step_abs;
1880   tree unsigned_type, valid_niter;
1881   tree base_plus_step, bpsps;
1882   int cps, cpsps;
1883
1884   /* FIXME: The following code will not be used anymore once
1885      http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is
1886      committed.
1887
1888      If AT_STMT is a cast to unsigned that is later used for
1889      referencing a memory location, it is followed by a pointer
1890      conversion just after.  Because pointers do not wrap, the
1891      sequences that reference the memory do not wrap either.  In the
1892      following example, sequences corresponding to D_13 and to D_14
1893      can be proved to not wrap because they are used for computing a
1894      memory access:
1895          
1896        D.1621_13 = (long unsigned intD.4) D.1620_12;
1897        D.1622_14 = D.1621_13 * 8;
1898        D.1623_15 = (doubleD.29 *) D.1622_14;
1899   */
1900   if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
1901     {
1902       tree op0 = TREE_OPERAND (at_stmt, 0);
1903       tree op1 = TREE_OPERAND (at_stmt, 1);
1904       tree type_op1 = TREE_TYPE (op1);
1905
1906       if ((TYPE_UNSIGNED (type_op1)
1907            && used_in_pointer_arithmetic_p (op0, 2))
1908           || POINTER_TYPE_P (type_op1))
1909         {
1910           *unknown_max = true;
1911           return false;
1912         }
1913     }
1914
1915   if (chrec_contains_undetermined (base)
1916       || chrec_contains_undetermined (step)
1917       || TREE_CODE (base) == REAL_CST
1918       || TREE_CODE (step) == REAL_CST)
1919     {
1920       *unknown_max = true;
1921       return true;
1922     }
1923
1924   *unknown_max = false;
1925   base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
1926   bpsps = fold_build2 (PLUS_EXPR, type, base_plus_step, step);
1927   cps = compare_trees (base_plus_step, base);
1928   cpsps = compare_trees (bpsps, base_plus_step);
1929
1930   /* Check that the sequence is not wrapping in the first step: it
1931      should have the same monotonicity for the first two steps.  See
1932      PR23410.  */
1933   if (cps != cpsps)
1934     return true;
1935
1936   switch (cps)
1937     {
1938     case -1:
1939       {
1940         tree extreme = upper_bound_in_type (type, TREE_TYPE (base));
1941         delta = fold_build2 (MINUS_EXPR, type, extreme, base);
1942         step_abs = step;
1943         *init_is_max = false;
1944         break;
1945       }
1946
1947     case 1:
1948       {
1949         tree extreme = lower_bound_in_type (type, TREE_TYPE (base));
1950         delta = fold_build2 (MINUS_EXPR, type, base, extreme);
1951         step_abs = fold_build1 (NEGATE_EXPR, type, step);
1952         *init_is_max = true;
1953         break;
1954       }
1955
1956     case 0:
1957       /* This means step is equal to 0.  This should not happen.  It
1958          could happen in convert step, but not here.  Safely answer
1959          don't know as in the default case.  */
1960
1961     default:
1962       *unknown_max = true;
1963       return true;
1964     }
1965
1966   /* If AT_STMT represents a cast operation, we may not be able to
1967      take advantage of the undefinedness of signed type evolutions.
1968
1969      implement-c.texi states: "For conversion to a type of width
1970      N, the value is reduced modulo 2^N to be within range of the
1971      type;"
1972
1973      See PR 21959 for a test case.  Essentially, given a cast
1974      operation
1975                 unsigned char uc;
1976                 signed char sc;
1977                 ...
1978                 sc = (signed char) uc;
1979                 if (sc < 0)
1980                   ...
1981
1982      where uc and sc have the scev {0, +, 1}, we would consider uc to
1983      wrap around, but not sc, because it is of a signed type.  This
1984      causes VRP to erroneously fold the predicate above because it
1985      thinks that sc cannot be negative.  */
1986   if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
1987     {
1988       tree rhs = TREE_OPERAND (at_stmt, 1);
1989       tree outer_t = TREE_TYPE (rhs);
1990
1991       if (!TYPE_UNSIGNED (outer_t)
1992           && (TREE_CODE (rhs) == NOP_EXPR || TREE_CODE (rhs) == CONVERT_EXPR))
1993         {
1994           tree inner_t = TREE_TYPE (TREE_OPERAND (rhs, 0));
1995
1996           /* If the inner type is unsigned and its size and/or
1997              precision are smaller to that of the outer type, then the
1998              expression may wrap around.  */
1999           if (TYPE_UNSIGNED (inner_t)
2000               && (TYPE_SIZE (inner_t) <= TYPE_SIZE (outer_t)
2001                   || TYPE_PRECISION (inner_t) <= TYPE_PRECISION (outer_t)))
2002             {
2003               *unknown_max = true;
2004               return true;
2005             }
2006         }
2007     }
2008
2009   /* After having set INIT_IS_MAX, we can return false: when not using
2010      wrapping arithmetic, signed types don't wrap.  */
2011   if (!flag_wrapv && !TYPE_UNSIGNED (type))
2012     return false;
2013
2014   unsigned_type = unsigned_type_for (type);
2015   delta = fold_convert (unsigned_type, delta);
2016   step_abs = fold_convert (unsigned_type, step_abs);
2017   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
2018
2019   estimate_numbers_of_iterations_loop (loop);
2020   for (bound = loop->bounds; bound; bound = bound->next)
2021     if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter))
2022       return false;
2023
2024   /* At this point we still don't have a proof that the iv does not
2025      overflow: give up.  */
2026   *unknown_max = true;
2027   return true;
2028 }
2029
2030 /* Return the conversion to NEW_TYPE of the STEP of an induction
2031    variable BASE + STEP * I at AT_STMT.  When it fails, return
2032    NULL_TREE.  */
2033
2034 tree
2035 convert_step (struct loop *loop, tree new_type, tree base, tree step,
2036               tree at_stmt)
2037 {
2038   tree base_type;
2039
2040   if (chrec_contains_undetermined (base)
2041       || chrec_contains_undetermined (step))
2042     return NULL_TREE;
2043
2044   base_type = TREE_TYPE (base);
2045
2046   /* When not using wrapping arithmetic, signed types don't wrap.  */
2047   if (!flag_wrapv && !TYPE_UNSIGNED (base_type))
2048     return fold_convert (new_type, step);
2049
2050   if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type))
2051     return convert_step_widening (loop, new_type, base, step, at_stmt);
2052
2053   return fold_convert (new_type, step);
2054 }
2055
2056 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
2057
2058 void
2059 free_numbers_of_iterations_estimates_loop (struct loop *loop)
2060 {
2061   struct nb_iter_bound *bound, *next;
2062
2063   loop->nb_iterations = NULL;
2064   loop->estimated_nb_iterations = NULL;
2065   for (bound = loop->bounds; bound; bound = next)
2066     {
2067       next = bound->next;
2068       free (bound);
2069     }
2070
2071   loop->bounds = NULL;
2072 }
2073
2074 /* Frees the information on upper bounds on numbers of iterations of LOOPS.  */
2075
2076 void
2077 free_numbers_of_iterations_estimates (struct loops *loops)
2078 {
2079   unsigned i;
2080   struct loop *loop;
2081
2082   for (i = 1; i < loops->num; i++)
2083     {
2084       loop = loops->parray[i];
2085       if (loop)
2086         free_numbers_of_iterations_estimates_loop (loop);
2087     }
2088 }
2089
2090 /* Substitute value VAL for ssa name NAME inside expressions held
2091    at LOOP.  */
2092
2093 void
2094 substitute_in_loop_info (struct loop *loop, tree name, tree val)
2095 {
2096   struct nb_iter_bound *bound;
2097
2098   loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
2099   loop->estimated_nb_iterations
2100           = simplify_replace_tree (loop->estimated_nb_iterations, name, val);
2101   for (bound = loop->bounds; bound; bound = bound->next)
2102     {
2103       bound->bound = simplify_replace_tree (bound->bound, name, val);
2104       bound->additional = simplify_replace_tree (bound->additional, name, val);
2105     }
2106 }