Merge branch 'vendor/GCC47'
[dragonfly.git] / contrib / gcc-4.7 / gcc / tree-ssa-loop-niter.c
1 /* Functions to determine/estimate number of iterations of a loop.
2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3    Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY 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 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "tm_p.h"
27 #include "basic-block.h"
28 #include "output.h"
29 #include "tree-pretty-print.h"
30 #include "gimple-pretty-print.h"
31 #include "intl.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "cfgloop.h"
35 #include "tree-pass.h"
36 #include "ggc.h"
37 #include "tree-chrec.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-data-ref.h"
40 #include "params.h"
41 #include "flags.h"
42 #include "diagnostic-core.h"
43 #include "tree-inline.h"
44 #include "gmp.h"
45
46 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
47
48 /* The maximum number of dominator BBs we search for conditions
49    of loop header copies we use for simplifying a conditional
50    expression.  */
51 #define MAX_DOMINATORS_TO_WALK 8
52
53 /*
54
55    Analysis of number of iterations of an affine exit test.
56
57 */
58
59 /* Bounds on some value, BELOW <= X <= UP.  */
60
61 typedef struct
62 {
63   mpz_t below, up;
64 } bounds;
65
66
67 /* Splits expression EXPR to a variable part VAR and constant OFFSET.  */
68
69 static void
70 split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
71 {
72   tree type = TREE_TYPE (expr);
73   tree op0, op1;
74   double_int off;
75   bool negate = false;
76
77   *var = expr;
78   mpz_set_ui (offset, 0);
79
80   switch (TREE_CODE (expr))
81     {
82     case MINUS_EXPR:
83       negate = true;
84       /* Fallthru.  */
85
86     case PLUS_EXPR:
87     case POINTER_PLUS_EXPR:
88       op0 = TREE_OPERAND (expr, 0);
89       op1 = TREE_OPERAND (expr, 1);
90
91       if (TREE_CODE (op1) != INTEGER_CST)
92         break;
93
94       *var = op0;
95       /* Always sign extend the offset.  */
96       off = tree_to_double_int (op1);
97       off = double_int_sext (off, TYPE_PRECISION (type));
98       mpz_set_double_int (offset, off, false);
99       if (negate)
100         mpz_neg (offset, offset);
101       break;
102
103     case INTEGER_CST:
104       *var = build_int_cst_type (type, 0);
105       off = tree_to_double_int (expr);
106       mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
107       break;
108
109     default:
110       break;
111     }
112 }
113
114 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
115    in TYPE to MIN and MAX.  */
116
117 static void
118 determine_value_range (tree type, tree var, mpz_t off,
119                        mpz_t min, mpz_t max)
120 {
121   /* If the expression is a constant, we know its value exactly.  */
122   if (integer_zerop (var))
123     {
124       mpz_set (min, off);
125       mpz_set (max, off);
126       return;
127     }
128
129   /* If the computation may wrap, we know nothing about the value, except for
130      the range of the type.  */
131   get_type_static_bounds (type, min, max);
132   if (!nowrap_type_p (type))
133     return;
134
135   /* Since the addition of OFF does not wrap, if OFF is positive, then we may
136      add it to MIN, otherwise to MAX.  */
137   if (mpz_sgn (off) < 0)
138     mpz_add (max, max, off);
139   else
140     mpz_add (min, min, off);
141 }
142
143 /* Stores the bounds on the difference of the values of the expressions
144    (var + X) and (var + Y), computed in TYPE, to BNDS.  */
145
146 static void
147 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
148                                     bounds *bnds)
149 {
150   int rel = mpz_cmp (x, y);
151   bool may_wrap = !nowrap_type_p (type);
152   mpz_t m;
153
154   /* If X == Y, then the expressions are always equal.
155      If X > Y, there are the following possibilities:
156        a) neither of var + X and var + Y overflow or underflow, or both of
157           them do.  Then their difference is X - Y.
158        b) var + X overflows, and var + Y does not.  Then the values of the
159           expressions are var + X - M and var + Y, where M is the range of
160           the type, and their difference is X - Y - M.
161        c) var + Y underflows and var + X does not.  Their difference again
162           is M - X + Y.
163        Therefore, if the arithmetics in type does not overflow, then the
164        bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
165      Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
166      (X - Y, X - Y + M).  */
167
168   if (rel == 0)
169     {
170       mpz_set_ui (bnds->below, 0);
171       mpz_set_ui (bnds->up, 0);
172       return;
173     }
174
175   mpz_init (m);
176   mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true);
177   mpz_add_ui (m, m, 1);
178   mpz_sub (bnds->up, x, y);
179   mpz_set (bnds->below, bnds->up);
180
181   if (may_wrap)
182     {
183       if (rel > 0)
184         mpz_sub (bnds->below, bnds->below, m);
185       else
186         mpz_add (bnds->up, bnds->up, m);
187     }
188
189   mpz_clear (m);
190 }
191
192 /* From condition C0 CMP C1 derives information regarding the
193    difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
194    and stores it to BNDS.  */
195
196 static void
197 refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
198                            tree vary, mpz_t offy,
199                            tree c0, enum tree_code cmp, tree c1,
200                            bounds *bnds)
201 {
202   tree varc0, varc1, tmp, ctype;
203   mpz_t offc0, offc1, loffx, loffy, bnd;
204   bool lbound = false;
205   bool no_wrap = nowrap_type_p (type);
206   bool x_ok, y_ok;
207
208   switch (cmp)
209     {
210     case LT_EXPR:
211     case LE_EXPR:
212     case GT_EXPR:
213     case GE_EXPR:
214       STRIP_SIGN_NOPS (c0);
215       STRIP_SIGN_NOPS (c1);
216       ctype = TREE_TYPE (c0);
217       if (!useless_type_conversion_p (ctype, type))
218         return;
219
220       break;
221
222     case EQ_EXPR:
223       /* We could derive quite precise information from EQ_EXPR, however, such
224          a guard is unlikely to appear, so we do not bother with handling
225          it.  */
226       return;
227
228     case NE_EXPR:
229       /* NE_EXPR comparisons do not contain much of useful information, except for
230          special case of comparing with the bounds of the type.  */
231       if (TREE_CODE (c1) != INTEGER_CST
232           || !INTEGRAL_TYPE_P (type))
233         return;
234
235       /* Ensure that the condition speaks about an expression in the same type
236          as X and Y.  */
237       ctype = TREE_TYPE (c0);
238       if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
239         return;
240       c0 = fold_convert (type, c0);
241       c1 = fold_convert (type, c1);
242
243       if (TYPE_MIN_VALUE (type)
244           && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
245         {
246           cmp = GT_EXPR;
247           break;
248         }
249       if (TYPE_MAX_VALUE (type)
250           && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
251         {
252           cmp = LT_EXPR;
253           break;
254         }
255
256       return;
257     default:
258       return;
259     }
260
261   mpz_init (offc0);
262   mpz_init (offc1);
263   split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
264   split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
265
266   /* We are only interested in comparisons of expressions based on VARX and
267      VARY.  TODO -- we might also be able to derive some bounds from
268      expressions containing just one of the variables.  */
269
270   if (operand_equal_p (varx, varc1, 0))
271     {
272       tmp = varc0; varc0 = varc1; varc1 = tmp;
273       mpz_swap (offc0, offc1);
274       cmp = swap_tree_comparison (cmp);
275     }
276
277   if (!operand_equal_p (varx, varc0, 0)
278       || !operand_equal_p (vary, varc1, 0))
279     goto end;
280
281   mpz_init_set (loffx, offx);
282   mpz_init_set (loffy, offy);
283
284   if (cmp == GT_EXPR || cmp == GE_EXPR)
285     {
286       tmp = varx; varx = vary; vary = tmp;
287       mpz_swap (offc0, offc1);
288       mpz_swap (loffx, loffy);
289       cmp = swap_tree_comparison (cmp);
290       lbound = true;
291     }
292
293   /* If there is no overflow, the condition implies that
294
295      (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
296
297      The overflows and underflows may complicate things a bit; each
298      overflow decreases the appropriate offset by M, and underflow
299      increases it by M.  The above inequality would not necessarily be
300      true if
301
302      -- VARX + OFFX underflows and VARX + OFFC0 does not, or
303         VARX + OFFC0 overflows, but VARX + OFFX does not.
304         This may only happen if OFFX < OFFC0.
305      -- VARY + OFFY overflows and VARY + OFFC1 does not, or
306         VARY + OFFC1 underflows and VARY + OFFY does not.
307         This may only happen if OFFY > OFFC1.  */
308
309   if (no_wrap)
310     {
311       x_ok = true;
312       y_ok = true;
313     }
314   else
315     {
316       x_ok = (integer_zerop (varx)
317               || mpz_cmp (loffx, offc0) >= 0);
318       y_ok = (integer_zerop (vary)
319               || mpz_cmp (loffy, offc1) <= 0);
320     }
321
322   if (x_ok && y_ok)
323     {
324       mpz_init (bnd);
325       mpz_sub (bnd, loffx, loffy);
326       mpz_add (bnd, bnd, offc1);
327       mpz_sub (bnd, bnd, offc0);
328
329       if (cmp == LT_EXPR)
330         mpz_sub_ui (bnd, bnd, 1);
331
332       if (lbound)
333         {
334           mpz_neg (bnd, bnd);
335           if (mpz_cmp (bnds->below, bnd) < 0)
336             mpz_set (bnds->below, bnd);
337         }
338       else
339         {
340           if (mpz_cmp (bnd, bnds->up) < 0)
341             mpz_set (bnds->up, bnd);
342         }
343       mpz_clear (bnd);
344     }
345
346   mpz_clear (loffx);
347   mpz_clear (loffy);
348 end:
349   mpz_clear (offc0);
350   mpz_clear (offc1);
351 }
352
353 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
354    The subtraction is considered to be performed in arbitrary precision,
355    without overflows.
356
357    We do not attempt to be too clever regarding the value ranges of X and
358    Y; most of the time, they are just integers or ssa names offsetted by
359    integer.  However, we try to use the information contained in the
360    comparisons before the loop (usually created by loop header copying).  */
361
362 static void
363 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
364 {
365   tree type = TREE_TYPE (x);
366   tree varx, vary;
367   mpz_t offx, offy;
368   mpz_t minx, maxx, miny, maxy;
369   int cnt = 0;
370   edge e;
371   basic_block bb;
372   tree c0, c1;
373   gimple cond;
374   enum tree_code cmp;
375
376   /* Get rid of unnecessary casts, but preserve the value of
377      the expressions.  */
378   STRIP_SIGN_NOPS (x);
379   STRIP_SIGN_NOPS (y);
380
381   mpz_init (bnds->below);
382   mpz_init (bnds->up);
383   mpz_init (offx);
384   mpz_init (offy);
385   split_to_var_and_offset (x, &varx, offx);
386   split_to_var_and_offset (y, &vary, offy);
387
388   if (!integer_zerop (varx)
389       && operand_equal_p (varx, vary, 0))
390     {
391       /* Special case VARX == VARY -- we just need to compare the
392          offsets.  The matters are a bit more complicated in the
393          case addition of offsets may wrap.  */
394       bound_difference_of_offsetted_base (type, offx, offy, bnds);
395     }
396   else
397     {
398       /* Otherwise, use the value ranges to determine the initial
399          estimates on below and up.  */
400       mpz_init (minx);
401       mpz_init (maxx);
402       mpz_init (miny);
403       mpz_init (maxy);
404       determine_value_range (type, varx, offx, minx, maxx);
405       determine_value_range (type, vary, offy, miny, maxy);
406
407       mpz_sub (bnds->below, minx, maxy);
408       mpz_sub (bnds->up, maxx, miny);
409       mpz_clear (minx);
410       mpz_clear (maxx);
411       mpz_clear (miny);
412       mpz_clear (maxy);
413     }
414
415   /* If both X and Y are constants, we cannot get any more precise.  */
416   if (integer_zerop (varx) && integer_zerop (vary))
417     goto end;
418
419   /* Now walk the dominators of the loop header and use the entry
420      guards to refine the estimates.  */
421   for (bb = loop->header;
422        bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
423        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
424     {
425       if (!single_pred_p (bb))
426         continue;
427       e = single_pred_edge (bb);
428
429       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
430         continue;
431
432       cond = last_stmt (e->src);
433       c0 = gimple_cond_lhs (cond);
434       cmp = gimple_cond_code (cond);
435       c1 = gimple_cond_rhs (cond);
436
437       if (e->flags & EDGE_FALSE_VALUE)
438         cmp = invert_tree_comparison (cmp, false);
439
440       refine_bounds_using_guard (type, varx, offx, vary, offy,
441                                  c0, cmp, c1, bnds);
442       ++cnt;
443     }
444
445 end:
446   mpz_clear (offx);
447   mpz_clear (offy);
448 }
449
450 /* Update the bounds in BNDS that restrict the value of X to the bounds
451    that restrict the value of X + DELTA.  X can be obtained as a
452    difference of two values in TYPE.  */
453
454 static void
455 bounds_add (bounds *bnds, double_int delta, tree type)
456 {
457   mpz_t mdelta, max;
458
459   mpz_init (mdelta);
460   mpz_set_double_int (mdelta, delta, false);
461
462   mpz_init (max);
463   mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
464
465   mpz_add (bnds->up, bnds->up, mdelta);
466   mpz_add (bnds->below, bnds->below, mdelta);
467
468   if (mpz_cmp (bnds->up, max) > 0)
469     mpz_set (bnds->up, max);
470
471   mpz_neg (max, max);
472   if (mpz_cmp (bnds->below, max) < 0)
473     mpz_set (bnds->below, max);
474
475   mpz_clear (mdelta);
476   mpz_clear (max);
477 }
478
479 /* Update the bounds in BNDS that restrict the value of X to the bounds
480    that restrict the value of -X.  */
481
482 static void
483 bounds_negate (bounds *bnds)
484 {
485   mpz_t tmp;
486
487   mpz_init_set (tmp, bnds->up);
488   mpz_neg (bnds->up, bnds->below);
489   mpz_neg (bnds->below, tmp);
490   mpz_clear (tmp);
491 }
492
493 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1.  */
494
495 static tree
496 inverse (tree x, tree mask)
497 {
498   tree type = TREE_TYPE (x);
499   tree rslt;
500   unsigned ctr = tree_floor_log2 (mask);
501
502   if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
503     {
504       unsigned HOST_WIDE_INT ix;
505       unsigned HOST_WIDE_INT imask;
506       unsigned HOST_WIDE_INT irslt = 1;
507
508       gcc_assert (cst_and_fits_in_hwi (x));
509       gcc_assert (cst_and_fits_in_hwi (mask));
510
511       ix = int_cst_value (x);
512       imask = int_cst_value (mask);
513
514       for (; ctr; ctr--)
515         {
516           irslt *= ix;
517           ix *= ix;
518         }
519       irslt &= imask;
520
521       rslt = build_int_cst_type (type, irslt);
522     }
523   else
524     {
525       rslt = build_int_cst (type, 1);
526       for (; ctr; ctr--)
527         {
528           rslt = int_const_binop (MULT_EXPR, rslt, x);
529           x = int_const_binop (MULT_EXPR, x, x);
530         }
531       rslt = int_const_binop (BIT_AND_EXPR, rslt, mask);
532     }
533
534   return rslt;
535 }
536
537 /* Derives the upper bound BND on the number of executions of loop with exit
538    condition S * i <> C.  If NO_OVERFLOW is true, then the control variable of
539    the loop does not overflow.  EXIT_MUST_BE_TAKEN is true if we are guaranteed
540    that the loop ends through this exit, i.e., the induction variable ever
541    reaches the value of C.  
542    
543    The value C is equal to final - base, where final and base are the final and
544    initial value of the actual induction variable in the analysed loop.  BNDS
545    bounds the value of this difference when computed in signed type with
546    unbounded range, while the computation of C is performed in an unsigned
547    type with the range matching the range of the type of the induction variable.
548    In particular, BNDS.up contains an upper bound on C in the following cases:
549    -- if the iv must reach its final value without overflow, i.e., if
550       NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
551    -- if final >= base, which we know to hold when BNDS.below >= 0.  */
552
553 static void
554 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
555                              bounds *bnds, bool exit_must_be_taken)
556 {
557   double_int max;
558   mpz_t d;
559   bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
560                        || mpz_sgn (bnds->below) >= 0);
561
562   if (multiple_of_p (TREE_TYPE (c), c, s))
563     {
564       /* If C is an exact multiple of S, then its value will be reached before
565          the induction variable overflows (unless the loop is exited in some
566          other way before).  Note that the actual induction variable in the
567          loop (which ranges from base to final instead of from 0 to C) may
568          overflow, in which case BNDS.up will not be giving a correct upper
569          bound on C; thus, BNDS_U_VALID had to be computed in advance.  */
570       no_overflow = true;
571       exit_must_be_taken = true;
572     }
573
574   /* If the induction variable can overflow, the number of iterations is at
575      most the period of the control variable (or infinite, but in that case
576      the whole # of iterations analysis will fail).  */
577   if (!no_overflow)
578     {
579       max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c))
580                              - tree_low_cst (num_ending_zeros (s), 1));
581       mpz_set_double_int (bnd, max, true);
582       return;
583     }
584
585   /* Now we know that the induction variable does not overflow, so the loop
586      iterates at most (range of type / S) times.  */
587   mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))),
588                       true);
589
590   /* If the induction variable is guaranteed to reach the value of C before
591      overflow, ... */
592   if (exit_must_be_taken)
593     {
594       /* ... then we can strenghten this to C / S, and possibly we can use
595          the upper bound on C given by BNDS.  */
596       if (TREE_CODE (c) == INTEGER_CST)
597         mpz_set_double_int (bnd, tree_to_double_int (c), true);
598       else if (bnds_u_valid)
599         mpz_set (bnd, bnds->up);
600     }
601
602   mpz_init (d);
603   mpz_set_double_int (d, tree_to_double_int (s), true);
604   mpz_fdiv_q (bnd, bnd, d);
605   mpz_clear (d);
606 }
607
608 /* Determines number of iterations of loop whose ending condition
609    is IV <> FINAL.  TYPE is the type of the iv.  The number of
610    iterations is stored to NITER.  EXIT_MUST_BE_TAKEN is true if
611    we know that the exit must be taken eventually, i.e., that the IV
612    ever reaches the value FINAL (we derived this earlier, and possibly set
613    NITER->assumptions to make sure this is the case).  BNDS contains the
614    bounds on the difference FINAL - IV->base.  */
615
616 static bool
617 number_of_iterations_ne (tree type, affine_iv *iv, tree final,
618                          struct tree_niter_desc *niter, bool exit_must_be_taken,
619                          bounds *bnds)
620 {
621   tree niter_type = unsigned_type_for (type);
622   tree s, c, d, bits, assumption, tmp, bound;
623   mpz_t max;
624
625   niter->control = *iv;
626   niter->bound = final;
627   niter->cmp = NE_EXPR;
628
629   /* Rearrange the terms so that we get inequality S * i <> C, with S
630      positive.  Also cast everything to the unsigned type.  If IV does
631      not overflow, BNDS bounds the value of C.  Also, this is the
632      case if the computation |FINAL - IV->base| does not overflow, i.e.,
633      if BNDS->below in the result is nonnegative.  */
634   if (tree_int_cst_sign_bit (iv->step))
635     {
636       s = fold_convert (niter_type,
637                         fold_build1 (NEGATE_EXPR, type, iv->step));
638       c = fold_build2 (MINUS_EXPR, niter_type,
639                        fold_convert (niter_type, iv->base),
640                        fold_convert (niter_type, final));
641       bounds_negate (bnds);
642     }
643   else
644     {
645       s = fold_convert (niter_type, iv->step);
646       c = fold_build2 (MINUS_EXPR, niter_type,
647                        fold_convert (niter_type, final),
648                        fold_convert (niter_type, iv->base));
649     }
650
651   mpz_init (max);
652   number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
653                                exit_must_be_taken);
654   niter->max = mpz_get_double_int (niter_type, max, false);
655   mpz_clear (max);
656
657   /* First the trivial cases -- when the step is 1.  */
658   if (integer_onep (s))
659     {
660       niter->niter = c;
661       return true;
662     }
663
664   /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
665      is infinite.  Otherwise, the number of iterations is
666      (inverse(s/d) * (c/d)) mod (size of mode/d).  */
667   bits = num_ending_zeros (s);
668   bound = build_low_bits_mask (niter_type,
669                                (TYPE_PRECISION (niter_type)
670                                 - tree_low_cst (bits, 1)));
671
672   d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
673                                build_int_cst (niter_type, 1), bits);
674   s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
675
676   if (!exit_must_be_taken)
677     {
678       /* If we cannot assume that the exit is taken eventually, record the
679          assumptions for divisibility of c.  */
680       assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
681       assumption = fold_build2 (EQ_EXPR, boolean_type_node,
682                                 assumption, build_int_cst (niter_type, 0));
683       if (!integer_nonzerop (assumption))
684         niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
685                                           niter->assumptions, assumption);
686     }
687
688   c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
689   tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
690   niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
691   return true;
692 }
693
694 /* Checks whether we can determine the final value of the control variable
695    of the loop with ending condition IV0 < IV1 (computed in TYPE).
696    DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
697    of the step.  The assumptions necessary to ensure that the computation
698    of the final value does not overflow are recorded in NITER.  If we
699    find the final value, we adjust DELTA and return TRUE.  Otherwise
700    we return false.  BNDS bounds the value of IV1->base - IV0->base,
701    and will be updated by the same amount as DELTA.  EXIT_MUST_BE_TAKEN is
702    true if we know that the exit must be taken eventually.  */
703
704 static bool
705 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
706                                struct tree_niter_desc *niter,
707                                tree *delta, tree step,
708                                bool exit_must_be_taken, bounds *bnds)
709 {
710   tree niter_type = TREE_TYPE (step);
711   tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
712   tree tmod;
713   mpz_t mmod;
714   tree assumption = boolean_true_node, bound, noloop;
715   bool ret = false, fv_comp_no_overflow;
716   tree type1 = type;
717   if (POINTER_TYPE_P (type))
718     type1 = sizetype;
719
720   if (TREE_CODE (mod) != INTEGER_CST)
721     return false;
722   if (integer_nonzerop (mod))
723     mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
724   tmod = fold_convert (type1, mod);
725
726   mpz_init (mmod);
727   mpz_set_double_int (mmod, tree_to_double_int (mod), true);
728   mpz_neg (mmod, mmod);
729
730   /* If the induction variable does not overflow and the exit is taken,
731      then the computation of the final value does not overflow.  This is
732      also obviously the case if the new final value is equal to the
733      current one.  Finally, we postulate this for pointer type variables,
734      as the code cannot rely on the object to that the pointer points being
735      placed at the end of the address space (and more pragmatically,
736      TYPE_{MIN,MAX}_VALUE is not defined for pointers).  */
737   if (integer_zerop (mod) || POINTER_TYPE_P (type))
738     fv_comp_no_overflow = true;
739   else if (!exit_must_be_taken)
740     fv_comp_no_overflow = false;
741   else
742     fv_comp_no_overflow =
743             (iv0->no_overflow && integer_nonzerop (iv0->step))
744             || (iv1->no_overflow && integer_nonzerop (iv1->step));
745
746   if (integer_nonzerop (iv0->step))
747     {
748       /* The final value of the iv is iv1->base + MOD, assuming that this
749          computation does not overflow, and that
750          iv0->base <= iv1->base + MOD.  */
751       if (!fv_comp_no_overflow)
752         {
753           bound = fold_build2 (MINUS_EXPR, type1,
754                                TYPE_MAX_VALUE (type1), tmod);
755           assumption = fold_build2 (LE_EXPR, boolean_type_node,
756                                     iv1->base, bound);
757           if (integer_zerop (assumption))
758             goto end;
759         }
760       if (mpz_cmp (mmod, bnds->below) < 0)
761         noloop = boolean_false_node;
762       else if (POINTER_TYPE_P (type))
763         noloop = fold_build2 (GT_EXPR, boolean_type_node,
764                               iv0->base,
765                               fold_build_pointer_plus (iv1->base, tmod));
766       else
767         noloop = fold_build2 (GT_EXPR, boolean_type_node,
768                               iv0->base,
769                               fold_build2 (PLUS_EXPR, type1,
770                                            iv1->base, tmod));
771     }
772   else
773     {
774       /* The final value of the iv is iv0->base - MOD, assuming that this
775          computation does not overflow, and that
776          iv0->base - MOD <= iv1->base. */
777       if (!fv_comp_no_overflow)
778         {
779           bound = fold_build2 (PLUS_EXPR, type1,
780                                TYPE_MIN_VALUE (type1), tmod);
781           assumption = fold_build2 (GE_EXPR, boolean_type_node,
782                                     iv0->base, bound);
783           if (integer_zerop (assumption))
784             goto end;
785         }
786       if (mpz_cmp (mmod, bnds->below) < 0)
787         noloop = boolean_false_node;
788       else if (POINTER_TYPE_P (type))
789         noloop = fold_build2 (GT_EXPR, boolean_type_node,
790                               fold_build_pointer_plus (iv0->base,
791                                                        fold_build1 (NEGATE_EXPR,
792                                                                     type1, tmod)),
793                               iv1->base);
794       else
795         noloop = fold_build2 (GT_EXPR, boolean_type_node,
796                               fold_build2 (MINUS_EXPR, type1,
797                                            iv0->base, tmod),
798                               iv1->base);
799     }
800
801   if (!integer_nonzerop (assumption))
802     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
803                                       niter->assumptions,
804                                       assumption);
805   if (!integer_zerop (noloop))
806     niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
807                                       niter->may_be_zero,
808                                       noloop);
809   bounds_add (bnds, tree_to_double_int (mod), type);
810   *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
811
812   ret = true;
813 end:
814   mpz_clear (mmod);
815   return ret;
816 }
817
818 /* Add assertions to NITER that ensure that the control variable of the loop
819    with ending condition IV0 < IV1 does not overflow.  Types of IV0 and IV1
820    are TYPE.  Returns false if we can prove that there is an overflow, true
821    otherwise.  STEP is the absolute value of the step.  */
822
823 static bool
824 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
825                        struct tree_niter_desc *niter, tree step)
826 {
827   tree bound, d, assumption, diff;
828   tree niter_type = TREE_TYPE (step);
829
830   if (integer_nonzerop (iv0->step))
831     {
832       /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
833       if (iv0->no_overflow)
834         return true;
835
836       /* If iv0->base is a constant, we can determine the last value before
837          overflow precisely; otherwise we conservatively assume
838          MAX - STEP + 1.  */
839
840       if (TREE_CODE (iv0->base) == INTEGER_CST)
841         {
842           d = fold_build2 (MINUS_EXPR, niter_type,
843                            fold_convert (niter_type, TYPE_MAX_VALUE (type)),
844                            fold_convert (niter_type, iv0->base));
845           diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
846         }
847       else
848         diff = fold_build2 (MINUS_EXPR, niter_type, step,
849                             build_int_cst (niter_type, 1));
850       bound = fold_build2 (MINUS_EXPR, type,
851                            TYPE_MAX_VALUE (type), fold_convert (type, diff));
852       assumption = fold_build2 (LE_EXPR, boolean_type_node,
853                                 iv1->base, bound);
854     }
855   else
856     {
857       /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
858       if (iv1->no_overflow)
859         return true;
860
861       if (TREE_CODE (iv1->base) == INTEGER_CST)
862         {
863           d = fold_build2 (MINUS_EXPR, niter_type,
864                            fold_convert (niter_type, iv1->base),
865                            fold_convert (niter_type, TYPE_MIN_VALUE (type)));
866           diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
867         }
868       else
869         diff = fold_build2 (MINUS_EXPR, niter_type, step,
870                             build_int_cst (niter_type, 1));
871       bound = fold_build2 (PLUS_EXPR, type,
872                            TYPE_MIN_VALUE (type), fold_convert (type, diff));
873       assumption = fold_build2 (GE_EXPR, boolean_type_node,
874                                 iv0->base, bound);
875     }
876
877   if (integer_zerop (assumption))
878     return false;
879   if (!integer_nonzerop (assumption))
880     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
881                                       niter->assumptions, assumption);
882
883   iv0->no_overflow = true;
884   iv1->no_overflow = true;
885   return true;
886 }
887
888 /* Add an assumption to NITER that a loop whose ending condition
889    is IV0 < IV1 rolls.  TYPE is the type of the control iv.  BNDS
890    bounds the value of IV1->base - IV0->base.  */
891
892 static void
893 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
894                       struct tree_niter_desc *niter, bounds *bnds)
895 {
896   tree assumption = boolean_true_node, bound, diff;
897   tree mbz, mbzl, mbzr, type1;
898   bool rolls_p, no_overflow_p;
899   double_int dstep;
900   mpz_t mstep, max;
901
902   /* We are going to compute the number of iterations as
903      (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
904      variant of TYPE.  This formula only works if
905
906      -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
907
908      (where MAX is the maximum value of the unsigned variant of TYPE, and
909      the computations in this formula are performed in full precision,
910      i.e., without overflows).
911
912      Usually, for loops with exit condition iv0->base + step * i < iv1->base,
913      we have a condition of the form iv0->base - step < iv1->base before the loop,
914      and for loops iv0->base < iv1->base - step * i the condition
915      iv0->base < iv1->base + step, due to loop header copying, which enable us
916      to prove the lower bound.
917
918      The upper bound is more complicated.  Unless the expressions for initial
919      and final value themselves contain enough information, we usually cannot
920      derive it from the context.  */
921
922   /* First check whether the answer does not follow from the bounds we gathered
923      before.  */
924   if (integer_nonzerop (iv0->step))
925     dstep = tree_to_double_int (iv0->step);
926   else
927     {
928       dstep = double_int_sext (tree_to_double_int (iv1->step),
929                                TYPE_PRECISION (type));
930       dstep = double_int_neg (dstep);
931     }
932
933   mpz_init (mstep);
934   mpz_set_double_int (mstep, dstep, true);
935   mpz_neg (mstep, mstep);
936   mpz_add_ui (mstep, mstep, 1);
937
938   rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
939
940   mpz_init (max);
941   mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
942   mpz_add (max, max, mstep);
943   no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
944                    /* For pointers, only values lying inside a single object
945                       can be compared or manipulated by pointer arithmetics.
946                       Gcc in general does not allow or handle objects larger
947                       than half of the address space, hence the upper bound
948                       is satisfied for pointers.  */
949                    || POINTER_TYPE_P (type));
950   mpz_clear (mstep);
951   mpz_clear (max);
952
953   if (rolls_p && no_overflow_p)
954     return;
955
956   type1 = type;
957   if (POINTER_TYPE_P (type))
958     type1 = sizetype;
959
960   /* Now the hard part; we must formulate the assumption(s) as expressions, and
961      we must be careful not to introduce overflow.  */
962
963   if (integer_nonzerop (iv0->step))
964     {
965       diff = fold_build2 (MINUS_EXPR, type1,
966                           iv0->step, build_int_cst (type1, 1));
967
968       /* We need to know that iv0->base >= MIN + iv0->step - 1.  Since
969          0 address never belongs to any object, we can assume this for
970          pointers.  */
971       if (!POINTER_TYPE_P (type))
972         {
973           bound = fold_build2 (PLUS_EXPR, type1,
974                                TYPE_MIN_VALUE (type), diff);
975           assumption = fold_build2 (GE_EXPR, boolean_type_node,
976                                     iv0->base, bound);
977         }
978
979       /* And then we can compute iv0->base - diff, and compare it with
980          iv1->base.  */
981       mbzl = fold_build2 (MINUS_EXPR, type1,
982                           fold_convert (type1, iv0->base), diff);
983       mbzr = fold_convert (type1, iv1->base);
984     }
985   else
986     {
987       diff = fold_build2 (PLUS_EXPR, type1,
988                           iv1->step, build_int_cst (type1, 1));
989
990       if (!POINTER_TYPE_P (type))
991         {
992           bound = fold_build2 (PLUS_EXPR, type1,
993                                TYPE_MAX_VALUE (type), diff);
994           assumption = fold_build2 (LE_EXPR, boolean_type_node,
995                                     iv1->base, bound);
996         }
997
998       mbzl = fold_convert (type1, iv0->base);
999       mbzr = fold_build2 (MINUS_EXPR, type1,
1000                           fold_convert (type1, iv1->base), diff);
1001     }
1002
1003   if (!integer_nonzerop (assumption))
1004     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1005                                       niter->assumptions, assumption);
1006   if (!rolls_p)
1007     {
1008       mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
1009       niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1010                                         niter->may_be_zero, mbz);
1011     }
1012 }
1013
1014 /* Determines number of iterations of loop whose ending condition
1015    is IV0 < IV1.  TYPE is the type of the iv.  The number of
1016    iterations is stored to NITER.  BNDS bounds the difference
1017    IV1->base - IV0->base.  EXIT_MUST_BE_TAKEN is true if we know
1018    that the exit must be taken eventually.  */
1019
1020 static bool
1021 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1022                          struct tree_niter_desc *niter,
1023                          bool exit_must_be_taken, bounds *bnds)
1024 {
1025   tree niter_type = unsigned_type_for (type);
1026   tree delta, step, s;
1027   mpz_t mstep, tmp;
1028
1029   if (integer_nonzerop (iv0->step))
1030     {
1031       niter->control = *iv0;
1032       niter->cmp = LT_EXPR;
1033       niter->bound = iv1->base;
1034     }
1035   else
1036     {
1037       niter->control = *iv1;
1038       niter->cmp = GT_EXPR;
1039       niter->bound = iv0->base;
1040     }
1041
1042   delta = fold_build2 (MINUS_EXPR, niter_type,
1043                        fold_convert (niter_type, iv1->base),
1044                        fold_convert (niter_type, iv0->base));
1045
1046   /* First handle the special case that the step is +-1.  */
1047   if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1048       || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
1049     {
1050       /* for (i = iv0->base; i < iv1->base; i++)
1051
1052          or
1053
1054          for (i = iv1->base; i > iv0->base; i--).
1055
1056          In both cases # of iterations is iv1->base - iv0->base, assuming that
1057          iv1->base >= iv0->base.
1058
1059          First try to derive a lower bound on the value of
1060          iv1->base - iv0->base, computed in full precision.  If the difference
1061          is nonnegative, we are done, otherwise we must record the
1062          condition.  */
1063
1064       if (mpz_sgn (bnds->below) < 0)
1065         niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1066                                           iv1->base, iv0->base);
1067       niter->niter = delta;
1068       niter->max = mpz_get_double_int (niter_type, bnds->up, false);
1069       return true;
1070     }
1071
1072   if (integer_nonzerop (iv0->step))
1073     step = fold_convert (niter_type, iv0->step);
1074   else
1075     step = fold_convert (niter_type,
1076                          fold_build1 (NEGATE_EXPR, type, iv1->step));
1077
1078   /* If we can determine the final value of the control iv exactly, we can
1079      transform the condition to != comparison.  In particular, this will be
1080      the case if DELTA is constant.  */
1081   if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1082                                      exit_must_be_taken, bnds))
1083     {
1084       affine_iv zps;
1085
1086       zps.base = build_int_cst (niter_type, 0);
1087       zps.step = step;
1088       /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1089          zps does not overflow.  */
1090       zps.no_overflow = true;
1091
1092       return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
1093     }
1094
1095   /* Make sure that the control iv does not overflow.  */
1096   if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1097     return false;
1098
1099   /* We determine the number of iterations as (delta + step - 1) / step.  For
1100      this to work, we must know that iv1->base >= iv0->base - step + 1,
1101      otherwise the loop does not roll.  */
1102   assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1103
1104   s = fold_build2 (MINUS_EXPR, niter_type,
1105                    step, build_int_cst (niter_type, 1));
1106   delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1107   niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1108
1109   mpz_init (mstep);
1110   mpz_init (tmp);
1111   mpz_set_double_int (mstep, tree_to_double_int (step), true);
1112   mpz_add (tmp, bnds->up, mstep);
1113   mpz_sub_ui (tmp, tmp, 1);
1114   mpz_fdiv_q (tmp, tmp, mstep);
1115   niter->max = mpz_get_double_int (niter_type, tmp, false);
1116   mpz_clear (mstep);
1117   mpz_clear (tmp);
1118
1119   return true;
1120 }
1121
1122 /* Determines number of iterations of loop whose ending condition
1123    is IV0 <= IV1.  TYPE is the type of the iv.  The number of
1124    iterations is stored to NITER.  EXIT_MUST_BE_TAKEN is true if
1125    we know that this condition must eventually become false (we derived this
1126    earlier, and possibly set NITER->assumptions to make sure this
1127    is the case).  BNDS bounds the difference IV1->base - IV0->base.  */
1128
1129 static bool
1130 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
1131                          struct tree_niter_desc *niter, bool exit_must_be_taken,
1132                          bounds *bnds)
1133 {
1134   tree assumption;
1135   tree type1 = type;
1136   if (POINTER_TYPE_P (type))
1137     type1 = sizetype;
1138
1139   /* Say that IV0 is the control variable.  Then IV0 <= IV1 iff
1140      IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1141      value of the type.  This we must know anyway, since if it is
1142      equal to this value, the loop rolls forever.  We do not check
1143      this condition for pointer type ivs, as the code cannot rely on
1144      the object to that the pointer points being placed at the end of
1145      the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1146      not defined for pointers).  */
1147
1148   if (!exit_must_be_taken && !POINTER_TYPE_P (type))
1149     {
1150       if (integer_nonzerop (iv0->step))
1151         assumption = fold_build2 (NE_EXPR, boolean_type_node,
1152                                   iv1->base, TYPE_MAX_VALUE (type));
1153       else
1154         assumption = fold_build2 (NE_EXPR, boolean_type_node,
1155                                   iv0->base, TYPE_MIN_VALUE (type));
1156
1157       if (integer_zerop (assumption))
1158         return false;
1159       if (!integer_nonzerop (assumption))
1160         niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1161                                           niter->assumptions, assumption);
1162     }
1163
1164   if (integer_nonzerop (iv0->step))
1165     {
1166       if (POINTER_TYPE_P (type))
1167         iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
1168       else
1169         iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
1170                                  build_int_cst (type1, 1));
1171     }
1172   else if (POINTER_TYPE_P (type))
1173     iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
1174   else
1175     iv0->base = fold_build2 (MINUS_EXPR, type1,
1176                              iv0->base, build_int_cst (type1, 1));
1177
1178   bounds_add (bnds, double_int_one, type1);
1179
1180   return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1181                                   bnds);
1182 }
1183
1184 /* Dumps description of affine induction variable IV to FILE.  */
1185
1186 static void
1187 dump_affine_iv (FILE *file, affine_iv *iv)
1188 {
1189   if (!integer_zerop (iv->step))
1190     fprintf (file, "[");
1191
1192   print_generic_expr (dump_file, iv->base, TDF_SLIM);
1193
1194   if (!integer_zerop (iv->step))
1195     {
1196       fprintf (file, ", + , ");
1197       print_generic_expr (dump_file, iv->step, TDF_SLIM);
1198       fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1199     }
1200 }
1201
1202 /* Determine the number of iterations according to condition (for staying
1203    inside loop) which compares two induction variables using comparison
1204    operator CODE.  The induction variable on left side of the comparison
1205    is IV0, the right-hand side is IV1.  Both induction variables must have
1206    type TYPE, which must be an integer or pointer type.  The steps of the
1207    ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1208
1209    LOOP is the loop whose number of iterations we are determining.
1210
1211    ONLY_EXIT is true if we are sure this is the only way the loop could be
1212    exited (including possibly non-returning function calls, exceptions, etc.)
1213    -- in this case we can use the information whether the control induction
1214    variables can overflow or not in a more efficient way.
1215
1216    The results (number of iterations and assumptions as described in
1217    comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1218    Returns false if it fails to determine number of iterations, true if it
1219    was determined (possibly with some assumptions).  */
1220
1221 static bool
1222 number_of_iterations_cond (struct loop *loop,
1223                            tree type, affine_iv *iv0, enum tree_code code,
1224                            affine_iv *iv1, struct tree_niter_desc *niter,
1225                            bool only_exit)
1226 {
1227   bool exit_must_be_taken = false, ret;
1228   bounds bnds;
1229
1230   /* The meaning of these assumptions is this:
1231      if !assumptions
1232        then the rest of information does not have to be valid
1233      if may_be_zero then the loop does not roll, even if
1234        niter != 0.  */
1235   niter->assumptions = boolean_true_node;
1236   niter->may_be_zero = boolean_false_node;
1237   niter->niter = NULL_TREE;
1238   niter->max = double_int_zero;
1239
1240   niter->bound = NULL_TREE;
1241   niter->cmp = ERROR_MARK;
1242
1243   /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1244      the control variable is on lhs.  */
1245   if (code == GE_EXPR || code == GT_EXPR
1246       || (code == NE_EXPR && integer_zerop (iv0->step)))
1247     {
1248       SWAP (iv0, iv1);
1249       code = swap_tree_comparison (code);
1250     }
1251
1252   if (POINTER_TYPE_P (type))
1253     {
1254       /* Comparison of pointers is undefined unless both iv0 and iv1 point
1255          to the same object.  If they do, the control variable cannot wrap
1256          (as wrap around the bounds of memory will never return a pointer
1257          that would be guaranteed to point to the same object, even if we
1258          avoid undefined behavior by casting to size_t and back).  */
1259       iv0->no_overflow = true;
1260       iv1->no_overflow = true;
1261     }
1262
1263   /* If the control induction variable does not overflow and the only exit
1264      from the loop is the one that we analyze, we know it must be taken
1265      eventually.  */
1266   if (only_exit)
1267     {
1268       if (!integer_zerop (iv0->step) && iv0->no_overflow)
1269         exit_must_be_taken = true;
1270       else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1271         exit_must_be_taken = true;
1272     }
1273
1274   /* We can handle the case when neither of the sides of the comparison is
1275      invariant, provided that the test is NE_EXPR.  This rarely occurs in
1276      practice, but it is simple enough to manage.  */
1277   if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1278     {
1279       tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1280       if (code != NE_EXPR)
1281         return false;
1282
1283       iv0->step = fold_binary_to_constant (MINUS_EXPR, step_type,
1284                                            iv0->step, iv1->step);
1285       iv0->no_overflow = false;
1286       iv1->step = build_int_cst (step_type, 0);
1287       iv1->no_overflow = true;
1288     }
1289
1290   /* If the result of the comparison is a constant,  the loop is weird.  More
1291      precise handling would be possible, but the situation is not common enough
1292      to waste time on it.  */
1293   if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1294     return false;
1295
1296   /* Ignore loops of while (i-- < 10) type.  */
1297   if (code != NE_EXPR)
1298     {
1299       if (iv0->step && tree_int_cst_sign_bit (iv0->step))
1300         return false;
1301
1302       if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
1303         return false;
1304     }
1305
1306   /* If the loop exits immediately, there is nothing to do.  */
1307   if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
1308     {
1309       niter->niter = build_int_cst (unsigned_type_for (type), 0);
1310       niter->max = double_int_zero;
1311       return true;
1312     }
1313
1314   /* OK, now we know we have a senseful loop.  Handle several cases, depending
1315      on what comparison operator is used.  */
1316   bound_difference (loop, iv1->base, iv0->base, &bnds);
1317
1318   if (dump_file && (dump_flags & TDF_DETAILS))
1319     {
1320       fprintf (dump_file,
1321                "Analyzing # of iterations of loop %d\n", loop->num);
1322
1323       fprintf (dump_file, "  exit condition ");
1324       dump_affine_iv (dump_file, iv0);
1325       fprintf (dump_file, " %s ",
1326                code == NE_EXPR ? "!="
1327                : code == LT_EXPR ? "<"
1328                : "<=");
1329       dump_affine_iv (dump_file, iv1);
1330       fprintf (dump_file, "\n");
1331
1332       fprintf (dump_file, "  bounds on difference of bases: ");
1333       mpz_out_str (dump_file, 10, bnds.below);
1334       fprintf (dump_file, " ... ");
1335       mpz_out_str (dump_file, 10, bnds.up);
1336       fprintf (dump_file, "\n");
1337     }
1338
1339   switch (code)
1340     {
1341     case NE_EXPR:
1342       gcc_assert (integer_zerop (iv1->step));
1343       ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
1344                                      exit_must_be_taken, &bnds);
1345       break;
1346
1347     case LT_EXPR:
1348       ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1349                                      &bnds);
1350       break;
1351
1352     case LE_EXPR:
1353       ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken,
1354                                      &bnds);
1355       break;
1356
1357     default:
1358       gcc_unreachable ();
1359     }
1360
1361   mpz_clear (bnds.up);
1362   mpz_clear (bnds.below);
1363
1364   if (dump_file && (dump_flags & TDF_DETAILS))
1365     {
1366       if (ret)
1367         {
1368           fprintf (dump_file, "  result:\n");
1369           if (!integer_nonzerop (niter->assumptions))
1370             {
1371               fprintf (dump_file, "    under assumptions ");
1372               print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1373               fprintf (dump_file, "\n");
1374             }
1375
1376           if (!integer_zerop (niter->may_be_zero))
1377             {
1378               fprintf (dump_file, "    zero if ");
1379               print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1380               fprintf (dump_file, "\n");
1381             }
1382
1383           fprintf (dump_file, "    # of iterations ");
1384           print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1385           fprintf (dump_file, ", bounded by ");
1386           dump_double_int (dump_file, niter->max, true);
1387           fprintf (dump_file, "\n");
1388         }
1389       else
1390         fprintf (dump_file, "  failed\n\n");
1391     }
1392   return ret;
1393 }
1394
1395 /* Substitute NEW for OLD in EXPR and fold the result.  */
1396
1397 static tree
1398 simplify_replace_tree (tree expr, tree old, tree new_tree)
1399 {
1400   unsigned i, n;
1401   tree ret = NULL_TREE, e, se;
1402
1403   if (!expr)
1404     return NULL_TREE;
1405
1406   /* Do not bother to replace constants.  */
1407   if (CONSTANT_CLASS_P (old))
1408     return expr;
1409
1410   if (expr == old
1411       || operand_equal_p (expr, old, 0))
1412     return unshare_expr (new_tree);
1413
1414   if (!EXPR_P (expr))
1415     return expr;
1416
1417   n = TREE_OPERAND_LENGTH (expr);
1418   for (i = 0; i < n; i++)
1419     {
1420       e = TREE_OPERAND (expr, i);
1421       se = simplify_replace_tree (e, old, new_tree);
1422       if (e == se)
1423         continue;
1424
1425       if (!ret)
1426         ret = copy_node (expr);
1427
1428       TREE_OPERAND (ret, i) = se;
1429     }
1430
1431   return (ret ? fold (ret) : expr);
1432 }
1433
1434 /* Expand definitions of ssa names in EXPR as long as they are simple
1435    enough, and return the new expression.  */
1436
1437 tree
1438 expand_simple_operations (tree expr)
1439 {
1440   unsigned i, n;
1441   tree ret = NULL_TREE, e, ee, e1;
1442   enum tree_code code;
1443   gimple stmt;
1444
1445   if (expr == NULL_TREE)
1446     return expr;
1447
1448   if (is_gimple_min_invariant (expr))
1449     return expr;
1450
1451   code = TREE_CODE (expr);
1452   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1453     {
1454       n = TREE_OPERAND_LENGTH (expr);
1455       for (i = 0; i < n; i++)
1456         {
1457           e = TREE_OPERAND (expr, i);
1458           ee = expand_simple_operations (e);
1459           if (e == ee)
1460             continue;
1461
1462           if (!ret)
1463             ret = copy_node (expr);
1464
1465           TREE_OPERAND (ret, i) = ee;
1466         }
1467
1468       if (!ret)
1469         return expr;
1470
1471       fold_defer_overflow_warnings ();
1472       ret = fold (ret);
1473       fold_undefer_and_ignore_overflow_warnings ();
1474       return ret;
1475     }
1476
1477   if (TREE_CODE (expr) != SSA_NAME)
1478     return expr;
1479
1480   stmt = SSA_NAME_DEF_STMT (expr);
1481   if (gimple_code (stmt) == GIMPLE_PHI)
1482     {
1483       basic_block src, dest;
1484
1485       if (gimple_phi_num_args (stmt) != 1)
1486         return expr;
1487       e = PHI_ARG_DEF (stmt, 0);
1488
1489       /* Avoid propagating through loop exit phi nodes, which
1490          could break loop-closed SSA form restrictions.  */
1491       dest = gimple_bb (stmt);
1492       src = single_pred (dest);
1493       if (TREE_CODE (e) == SSA_NAME
1494           && src->loop_father != dest->loop_father)
1495         return expr;
1496
1497       return expand_simple_operations (e);
1498     }
1499   if (gimple_code (stmt) != GIMPLE_ASSIGN)
1500     return expr;
1501
1502   e = gimple_assign_rhs1 (stmt);
1503   code = gimple_assign_rhs_code (stmt);
1504   if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1505     {
1506       if (is_gimple_min_invariant (e))
1507         return e;
1508
1509       if (code == SSA_NAME)
1510         return expand_simple_operations (e);
1511
1512       return expr;
1513     }
1514
1515   switch (code)
1516     {
1517     CASE_CONVERT:
1518       /* Casts are simple.  */
1519       ee = expand_simple_operations (e);
1520       return fold_build1 (code, TREE_TYPE (expr), ee);
1521
1522     case PLUS_EXPR:
1523     case MINUS_EXPR:
1524     case POINTER_PLUS_EXPR:
1525       /* And increments and decrements by a constant are simple.  */
1526       e1 = gimple_assign_rhs2 (stmt);
1527       if (!is_gimple_min_invariant (e1))
1528         return expr;
1529
1530       ee = expand_simple_operations (e);
1531       return fold_build2 (code, TREE_TYPE (expr), ee, e1);
1532
1533     default:
1534       return expr;
1535     }
1536 }
1537
1538 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
1539    expression (or EXPR unchanged, if no simplification was possible).  */
1540
1541 static tree
1542 tree_simplify_using_condition_1 (tree cond, tree expr)
1543 {
1544   bool changed;
1545   tree e, te, e0, e1, e2, notcond;
1546   enum tree_code code = TREE_CODE (expr);
1547
1548   if (code == INTEGER_CST)
1549     return expr;
1550
1551   if (code == TRUTH_OR_EXPR
1552       || code == TRUTH_AND_EXPR
1553       || code == COND_EXPR)
1554     {
1555       changed = false;
1556
1557       e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
1558       if (TREE_OPERAND (expr, 0) != e0)
1559         changed = true;
1560
1561       e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
1562       if (TREE_OPERAND (expr, 1) != e1)
1563         changed = true;
1564
1565       if (code == COND_EXPR)
1566         {
1567           e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
1568           if (TREE_OPERAND (expr, 2) != e2)
1569             changed = true;
1570         }
1571       else
1572         e2 = NULL_TREE;
1573
1574       if (changed)
1575         {
1576           if (code == COND_EXPR)
1577             expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1578           else
1579             expr = fold_build2 (code, boolean_type_node, e0, e1);
1580         }
1581
1582       return expr;
1583     }
1584
1585   /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1586      propagation, and vice versa.  Fold does not handle this, since it is
1587      considered too expensive.  */
1588   if (TREE_CODE (cond) == EQ_EXPR)
1589     {
1590       e0 = TREE_OPERAND (cond, 0);
1591       e1 = TREE_OPERAND (cond, 1);
1592
1593       /* We know that e0 == e1.  Check whether we cannot simplify expr
1594          using this fact.  */
1595       e = simplify_replace_tree (expr, e0, e1);
1596       if (integer_zerop (e) || integer_nonzerop (e))
1597         return e;
1598
1599       e = simplify_replace_tree (expr, e1, e0);
1600       if (integer_zerop (e) || integer_nonzerop (e))
1601         return e;
1602     }
1603   if (TREE_CODE (expr) == EQ_EXPR)
1604     {
1605       e0 = TREE_OPERAND (expr, 0);
1606       e1 = TREE_OPERAND (expr, 1);
1607
1608       /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true.  */
1609       e = simplify_replace_tree (cond, e0, e1);
1610       if (integer_zerop (e))
1611         return e;
1612       e = simplify_replace_tree (cond, e1, e0);
1613       if (integer_zerop (e))
1614         return e;
1615     }
1616   if (TREE_CODE (expr) == NE_EXPR)
1617     {
1618       e0 = TREE_OPERAND (expr, 0);
1619       e1 = TREE_OPERAND (expr, 1);
1620
1621       /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true.  */
1622       e = simplify_replace_tree (cond, e0, e1);
1623       if (integer_zerop (e))
1624         return boolean_true_node;
1625       e = simplify_replace_tree (cond, e1, e0);
1626       if (integer_zerop (e))
1627         return boolean_true_node;
1628     }
1629
1630   te = expand_simple_operations (expr);
1631
1632   /* Check whether COND ==> EXPR.  */
1633   notcond = invert_truthvalue (cond);
1634   e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
1635   if (e && integer_nonzerop (e))
1636     return e;
1637
1638   /* Check whether COND ==> not EXPR.  */
1639   e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
1640   if (e && integer_zerop (e))
1641     return e;
1642
1643   return expr;
1644 }
1645
1646 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
1647    expression (or EXPR unchanged, if no simplification was possible).
1648    Wrapper around tree_simplify_using_condition_1 that ensures that chains
1649    of simple operations in definitions of ssa names in COND are expanded,
1650    so that things like casts or incrementing the value of the bound before
1651    the loop do not cause us to fail.  */
1652
1653 static tree
1654 tree_simplify_using_condition (tree cond, tree expr)
1655 {
1656   cond = expand_simple_operations (cond);
1657
1658   return tree_simplify_using_condition_1 (cond, expr);
1659 }
1660
1661 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1662    Returns the simplified expression (or EXPR unchanged, if no
1663    simplification was possible).*/
1664
1665 static tree
1666 simplify_using_initial_conditions (struct loop *loop, tree expr)
1667 {
1668   edge e;
1669   basic_block bb;
1670   gimple stmt;
1671   tree cond;
1672   int cnt = 0;
1673
1674   if (TREE_CODE (expr) == INTEGER_CST)
1675     return expr;
1676
1677   /* Limit walking the dominators to avoid quadraticness in
1678      the number of BBs times the number of loops in degenerate
1679      cases.  */
1680   for (bb = loop->header;
1681        bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
1682        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1683     {
1684       if (!single_pred_p (bb))
1685         continue;
1686       e = single_pred_edge (bb);
1687
1688       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1689         continue;
1690
1691       stmt = last_stmt (e->src);
1692       cond = fold_build2 (gimple_cond_code (stmt),
1693                           boolean_type_node,
1694                           gimple_cond_lhs (stmt),
1695                           gimple_cond_rhs (stmt));
1696       if (e->flags & EDGE_FALSE_VALUE)
1697         cond = invert_truthvalue (cond);
1698       expr = tree_simplify_using_condition (cond, expr);
1699       ++cnt;
1700     }
1701
1702   return expr;
1703 }
1704
1705 /* Tries to simplify EXPR using the evolutions of the loop invariants
1706    in the superloops of LOOP.  Returns the simplified expression
1707    (or EXPR unchanged, if no simplification was possible).  */
1708
1709 static tree
1710 simplify_using_outer_evolutions (struct loop *loop, tree expr)
1711 {
1712   enum tree_code code = TREE_CODE (expr);
1713   bool changed;
1714   tree e, e0, e1, e2;
1715
1716   if (is_gimple_min_invariant (expr))
1717     return expr;
1718
1719   if (code == TRUTH_OR_EXPR
1720       || code == TRUTH_AND_EXPR
1721       || code == COND_EXPR)
1722     {
1723       changed = false;
1724
1725       e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
1726       if (TREE_OPERAND (expr, 0) != e0)
1727         changed = true;
1728
1729       e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
1730       if (TREE_OPERAND (expr, 1) != e1)
1731         changed = true;
1732
1733       if (code == COND_EXPR)
1734         {
1735           e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
1736           if (TREE_OPERAND (expr, 2) != e2)
1737             changed = true;
1738         }
1739       else
1740         e2 = NULL_TREE;
1741
1742       if (changed)
1743         {
1744           if (code == COND_EXPR)
1745             expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1746           else
1747             expr = fold_build2 (code, boolean_type_node, e0, e1);
1748         }
1749
1750       return expr;
1751     }
1752
1753   e = instantiate_parameters (loop, expr);
1754   if (is_gimple_min_invariant (e))
1755     return e;
1756
1757   return expr;
1758 }
1759
1760 /* Returns true if EXIT is the only possible exit from LOOP.  */
1761
1762 bool
1763 loop_only_exit_p (const struct loop *loop, const_edge exit)
1764 {
1765   basic_block *body;
1766   gimple_stmt_iterator bsi;
1767   unsigned i;
1768   gimple call;
1769
1770   if (exit != single_exit (loop))
1771     return false;
1772
1773   body = get_loop_body (loop);
1774   for (i = 0; i < loop->num_nodes; i++)
1775     {
1776       for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
1777         {
1778           call = gsi_stmt (bsi);
1779           if (gimple_code (call) != GIMPLE_CALL)
1780             continue;
1781
1782           if (gimple_has_side_effects (call))
1783             {
1784               free (body);
1785               return false;
1786             }
1787         }
1788     }
1789
1790   free (body);
1791   return true;
1792 }
1793
1794 /* Stores description of number of iterations of LOOP derived from
1795    EXIT (an exit edge of the LOOP) in NITER.  Returns true if some
1796    useful information could be derived (and fields of NITER has
1797    meaning described in comments at struct tree_niter_desc
1798    declaration), false otherwise.  If WARN is true and
1799    -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1800    potentially unsafe assumptions.  */
1801
1802 bool
1803 number_of_iterations_exit (struct loop *loop, edge exit,
1804                            struct tree_niter_desc *niter,
1805                            bool warn)
1806 {
1807   gimple stmt;
1808   tree type;
1809   tree op0, op1;
1810   enum tree_code code;
1811   affine_iv iv0, iv1;
1812
1813   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1814     return false;
1815
1816   niter->assumptions = boolean_false_node;
1817   stmt = last_stmt (exit->src);
1818   if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1819     return false;
1820
1821   /* We want the condition for staying inside loop.  */
1822   code = gimple_cond_code (stmt);
1823   if (exit->flags & EDGE_TRUE_VALUE)
1824     code = invert_tree_comparison (code, false);
1825
1826   switch (code)
1827     {
1828     case GT_EXPR:
1829     case GE_EXPR:
1830     case NE_EXPR:
1831     case LT_EXPR:
1832     case LE_EXPR:
1833       break;
1834
1835     default:
1836       return false;
1837     }
1838
1839   op0 = gimple_cond_lhs (stmt);
1840   op1 = gimple_cond_rhs (stmt);
1841   type = TREE_TYPE (op0);
1842
1843   if (TREE_CODE (type) != INTEGER_TYPE
1844       && !POINTER_TYPE_P (type))
1845     return false;
1846
1847   if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
1848     return false;
1849   if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
1850     return false;
1851
1852   /* We don't want to see undefined signed overflow warnings while
1853      computing the number of iterations.  */
1854   fold_defer_overflow_warnings ();
1855
1856   iv0.base = expand_simple_operations (iv0.base);
1857   iv1.base = expand_simple_operations (iv1.base);
1858   if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
1859                                   loop_only_exit_p (loop, exit)))
1860     {
1861       fold_undefer_and_ignore_overflow_warnings ();
1862       return false;
1863     }
1864
1865   if (optimize >= 3)
1866     {
1867       niter->assumptions = simplify_using_outer_evolutions (loop,
1868                                                             niter->assumptions);
1869       niter->may_be_zero = simplify_using_outer_evolutions (loop,
1870                                                             niter->may_be_zero);
1871       niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1872     }
1873
1874   niter->assumptions
1875           = simplify_using_initial_conditions (loop,
1876                                                niter->assumptions);
1877   niter->may_be_zero
1878           = simplify_using_initial_conditions (loop,
1879                                                niter->may_be_zero);
1880
1881   fold_undefer_and_ignore_overflow_warnings ();
1882
1883   if (integer_onep (niter->assumptions))
1884     return true;
1885
1886   /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1887      But if we can prove that there is overflow or some other source of weird
1888      behavior, ignore the loop even with -funsafe-loop-optimizations.  */
1889   if (integer_zerop (niter->assumptions) || !single_exit (loop))
1890     return false;
1891
1892   if (flag_unsafe_loop_optimizations)
1893     niter->assumptions = boolean_true_node;
1894
1895   if (warn)
1896     {
1897       const char *wording;
1898       location_t loc = gimple_location (stmt);
1899
1900       /* We can provide a more specific warning if one of the operator is
1901          constant and the other advances by +1 or -1.  */
1902       if (!integer_zerop (iv1.step)
1903           ? (integer_zerop (iv0.step)
1904              && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1905           : (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))
1906         wording =
1907           flag_unsafe_loop_optimizations
1908           ? N_("assuming that the loop is not infinite")
1909           : N_("cannot optimize possibly infinite loops");
1910       else
1911         wording =
1912           flag_unsafe_loop_optimizations
1913           ? N_("assuming that the loop counter does not overflow")
1914           : N_("cannot optimize loop, the loop counter may overflow");
1915
1916       warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location,
1917                   OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1918     }
1919
1920   return flag_unsafe_loop_optimizations;
1921 }
1922
1923 /* Try to determine the number of iterations of LOOP.  If we succeed,
1924    expression giving number of iterations is returned and *EXIT is
1925    set to the edge from that the information is obtained.  Otherwise
1926    chrec_dont_know is returned.  */
1927
1928 tree
1929 find_loop_niter (struct loop *loop, edge *exit)
1930 {
1931   unsigned i;
1932   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1933   edge ex;
1934   tree niter = NULL_TREE, aniter;
1935   struct tree_niter_desc desc;
1936
1937   *exit = NULL;
1938   FOR_EACH_VEC_ELT (edge, exits, i, ex)
1939     {
1940       if (!just_once_each_iteration_p (loop, ex->src))
1941         continue;
1942
1943       if (!number_of_iterations_exit (loop, ex, &desc, false))
1944         continue;
1945
1946       if (integer_nonzerop (desc.may_be_zero))
1947         {
1948           /* We exit in the first iteration through this exit.
1949              We won't find anything better.  */
1950           niter = build_int_cst (unsigned_type_node, 0);
1951           *exit = ex;
1952           break;
1953         }
1954
1955       if (!integer_zerop (desc.may_be_zero))
1956         continue;
1957
1958       aniter = desc.niter;
1959
1960       if (!niter)
1961         {
1962           /* Nothing recorded yet.  */
1963           niter = aniter;
1964           *exit = ex;
1965           continue;
1966         }
1967
1968       /* Prefer constants, the lower the better.  */
1969       if (TREE_CODE (aniter) != INTEGER_CST)
1970         continue;
1971
1972       if (TREE_CODE (niter) != INTEGER_CST)
1973         {
1974           niter = aniter;
1975           *exit = ex;
1976           continue;
1977         }
1978
1979       if (tree_int_cst_lt (aniter, niter))
1980         {
1981           niter = aniter;
1982           *exit = ex;
1983           continue;
1984         }
1985     }
1986   VEC_free (edge, heap, exits);
1987
1988   return niter ? niter : chrec_dont_know;
1989 }
1990
1991 /* Return true if loop is known to have bounded number of iterations.  */
1992
1993 bool
1994 finite_loop_p (struct loop *loop)
1995 {
1996   unsigned i;
1997   VEC (edge, heap) *exits;
1998   edge ex;
1999   struct tree_niter_desc desc;
2000   bool finite = false;
2001   int flags;
2002
2003   if (flag_unsafe_loop_optimizations)
2004     return true;
2005   flags = flags_from_decl_or_type (current_function_decl);
2006   if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
2007     {
2008       if (dump_file && (dump_flags & TDF_DETAILS))
2009         fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
2010                  loop->num);
2011       return true;
2012     }
2013
2014   exits = get_loop_exit_edges (loop);
2015   FOR_EACH_VEC_ELT (edge, exits, i, ex)
2016     {
2017       if (!just_once_each_iteration_p (loop, ex->src))
2018         continue;
2019
2020       if (number_of_iterations_exit (loop, ex, &desc, false))
2021         {
2022           if (dump_file && (dump_flags & TDF_DETAILS))
2023             {
2024               fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
2025               print_generic_expr (dump_file, desc.niter, TDF_SLIM);
2026               fprintf (dump_file, " times\n");
2027             }
2028           finite = true;
2029           break;
2030         }
2031     }
2032   VEC_free (edge, heap, exits);
2033   return finite;
2034 }
2035
2036 /*
2037
2038    Analysis of a number of iterations of a loop by a brute-force evaluation.
2039
2040 */
2041
2042 /* Bound on the number of iterations we try to evaluate.  */
2043
2044 #define MAX_ITERATIONS_TO_TRACK \
2045   ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2046
2047 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2048    result by a chain of operations such that all but exactly one of their
2049    operands are constants.  */
2050
2051 static gimple
2052 chain_of_csts_start (struct loop *loop, tree x)
2053 {
2054   gimple stmt = SSA_NAME_DEF_STMT (x);
2055   tree use;
2056   basic_block bb = gimple_bb (stmt);
2057   enum tree_code code;
2058
2059   if (!bb
2060       || !flow_bb_inside_loop_p (loop, bb))
2061     return NULL;
2062
2063   if (gimple_code (stmt) == GIMPLE_PHI)
2064     {
2065       if (bb == loop->header)
2066         return stmt;
2067
2068       return NULL;
2069     }
2070
2071   if (gimple_code (stmt) != GIMPLE_ASSIGN
2072       || gimple_assign_rhs_class (stmt) == GIMPLE_TERNARY_RHS)
2073     return NULL;
2074
2075   code = gimple_assign_rhs_code (stmt);
2076   if (gimple_references_memory_p (stmt)
2077       || TREE_CODE_CLASS (code) == tcc_reference
2078       || (code == ADDR_EXPR
2079           && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
2080     return NULL;
2081
2082   use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2083   if (use == NULL_TREE)
2084     return NULL;
2085
2086   return chain_of_csts_start (loop, use);
2087 }
2088
2089 /* Determines whether the expression X is derived from a result of a phi node
2090    in header of LOOP such that
2091
2092    * the derivation of X consists only from operations with constants
2093    * the initial value of the phi node is constant
2094    * the value of the phi node in the next iteration can be derived from the
2095      value in the current iteration by a chain of operations with constants.
2096
2097    If such phi node exists, it is returned, otherwise NULL is returned.  */
2098
2099 static gimple
2100 get_base_for (struct loop *loop, tree x)
2101 {
2102   gimple phi;
2103   tree init, next;
2104
2105   if (is_gimple_min_invariant (x))
2106     return NULL;
2107
2108   phi = chain_of_csts_start (loop, x);
2109   if (!phi)
2110     return NULL;
2111
2112   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2113   next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2114
2115   if (TREE_CODE (next) != SSA_NAME)
2116     return NULL;
2117
2118   if (!is_gimple_min_invariant (init))
2119     return NULL;
2120
2121   if (chain_of_csts_start (loop, next) != phi)
2122     return NULL;
2123
2124   return phi;
2125 }
2126
2127 /* Given an expression X, then
2128
2129    * if X is NULL_TREE, we return the constant BASE.
2130    * otherwise X is a SSA name, whose value in the considered loop is derived
2131      by a chain of operations with constant from a result of a phi node in
2132      the header of the loop.  Then we return value of X when the value of the
2133      result of this phi node is given by the constant BASE.  */
2134
2135 static tree
2136 get_val_for (tree x, tree base)
2137 {
2138   gimple stmt;
2139
2140   gcc_checking_assert (is_gimple_min_invariant (base));
2141
2142   if (!x)
2143     return base;
2144
2145   stmt = SSA_NAME_DEF_STMT (x);
2146   if (gimple_code (stmt) == GIMPLE_PHI)
2147     return base;
2148
2149   gcc_checking_assert (is_gimple_assign (stmt));
2150
2151   /* STMT must be either an assignment of a single SSA name or an
2152      expression involving an SSA name and a constant.  Try to fold that
2153      expression using the value for the SSA name.  */
2154   if (gimple_assign_ssa_name_copy_p (stmt))
2155     return get_val_for (gimple_assign_rhs1 (stmt), base);
2156   else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
2157            && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2158     {
2159       return fold_build1 (gimple_assign_rhs_code (stmt),
2160                           gimple_expr_type (stmt),
2161                           get_val_for (gimple_assign_rhs1 (stmt), base));
2162     }
2163   else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
2164     {
2165       tree rhs1 = gimple_assign_rhs1 (stmt);
2166       tree rhs2 = gimple_assign_rhs2 (stmt);
2167       if (TREE_CODE (rhs1) == SSA_NAME)
2168         rhs1 = get_val_for (rhs1, base);
2169       else if (TREE_CODE (rhs2) == SSA_NAME)
2170         rhs2 = get_val_for (rhs2, base);
2171       else
2172         gcc_unreachable ();
2173       return fold_build2 (gimple_assign_rhs_code (stmt),
2174                           gimple_expr_type (stmt), rhs1, rhs2);
2175     }
2176   else
2177     gcc_unreachable ();
2178 }
2179
2180
2181 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2182    by brute force -- i.e. by determining the value of the operands of the
2183    condition at EXIT in first few iterations of the loop (assuming that
2184    these values are constant) and determining the first one in that the
2185    condition is not satisfied.  Returns the constant giving the number
2186    of the iterations of LOOP if successful, chrec_dont_know otherwise.  */
2187
2188 tree
2189 loop_niter_by_eval (struct loop *loop, edge exit)
2190 {
2191   tree acnd;
2192   tree op[2], val[2], next[2], aval[2];
2193   gimple phi, cond;
2194   unsigned i, j;
2195   enum tree_code cmp;
2196
2197   cond = last_stmt (exit->src);
2198   if (!cond || gimple_code (cond) != GIMPLE_COND)
2199     return chrec_dont_know;
2200
2201   cmp = gimple_cond_code (cond);
2202   if (exit->flags & EDGE_TRUE_VALUE)
2203     cmp = invert_tree_comparison (cmp, false);
2204
2205   switch (cmp)
2206     {
2207     case EQ_EXPR:
2208     case NE_EXPR:
2209     case GT_EXPR:
2210     case GE_EXPR:
2211     case LT_EXPR:
2212     case LE_EXPR:
2213       op[0] = gimple_cond_lhs (cond);
2214       op[1] = gimple_cond_rhs (cond);
2215       break;
2216
2217     default:
2218       return chrec_dont_know;
2219     }
2220
2221   for (j = 0; j < 2; j++)
2222     {
2223       if (is_gimple_min_invariant (op[j]))
2224         {
2225           val[j] = op[j];
2226           next[j] = NULL_TREE;
2227           op[j] = NULL_TREE;
2228         }
2229       else
2230         {
2231           phi = get_base_for (loop, op[j]);
2232           if (!phi)
2233             return chrec_dont_know;
2234           val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2235           next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2236         }
2237     }
2238
2239   /* Don't issue signed overflow warnings.  */
2240   fold_defer_overflow_warnings ();
2241
2242   for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2243     {
2244       for (j = 0; j < 2; j++)
2245         aval[j] = get_val_for (op[j], val[j]);
2246
2247       acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2248       if (acnd && integer_zerop (acnd))
2249         {
2250           fold_undefer_and_ignore_overflow_warnings ();
2251           if (dump_file && (dump_flags & TDF_DETAILS))
2252             fprintf (dump_file,
2253                      "Proved that loop %d iterates %d times using brute force.\n",
2254                      loop->num, i);
2255           return build_int_cst (unsigned_type_node, i);
2256         }
2257
2258       for (j = 0; j < 2; j++)
2259         {
2260           val[j] = get_val_for (next[j], val[j]);
2261           if (!is_gimple_min_invariant (val[j]))
2262             {
2263               fold_undefer_and_ignore_overflow_warnings ();
2264               return chrec_dont_know;
2265             }
2266         }
2267     }
2268
2269   fold_undefer_and_ignore_overflow_warnings ();
2270
2271   return chrec_dont_know;
2272 }
2273
2274 /* Finds the exit of the LOOP by that the loop exits after a constant
2275    number of iterations and stores the exit edge to *EXIT.  The constant
2276    giving the number of iterations of LOOP is returned.  The number of
2277    iterations is determined using loop_niter_by_eval (i.e. by brute force
2278    evaluation).  If we are unable to find the exit for that loop_niter_by_eval
2279    determines the number of iterations, chrec_dont_know is returned.  */
2280
2281 tree
2282 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2283 {
2284   unsigned i;
2285   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2286   edge ex;
2287   tree niter = NULL_TREE, aniter;
2288
2289   *exit = NULL;
2290
2291   /* Loops with multiple exits are expensive to handle and less important.  */
2292   if (!flag_expensive_optimizations
2293       && VEC_length (edge, exits) > 1)
2294     {
2295       VEC_free (edge, heap, exits);
2296       return chrec_dont_know;
2297     }
2298
2299   FOR_EACH_VEC_ELT (edge, exits, i, ex)
2300     {
2301       if (!just_once_each_iteration_p (loop, ex->src))
2302         continue;
2303
2304       aniter = loop_niter_by_eval (loop, ex);
2305       if (chrec_contains_undetermined (aniter))
2306         continue;
2307
2308       if (niter
2309           && !tree_int_cst_lt (aniter, niter))
2310         continue;
2311
2312       niter = aniter;
2313       *exit = ex;
2314     }
2315   VEC_free (edge, heap, exits);
2316
2317   return niter ? niter : chrec_dont_know;
2318 }
2319
2320 /*
2321
2322    Analysis of upper bounds on number of iterations of a loop.
2323
2324 */
2325
2326 static double_int derive_constant_upper_bound_ops (tree, tree,
2327                                                    enum tree_code, tree);
2328
2329 /* Returns a constant upper bound on the value of the right-hand side of
2330    an assignment statement STMT.  */
2331
2332 static double_int
2333 derive_constant_upper_bound_assign (gimple stmt)
2334 {
2335   enum tree_code code = gimple_assign_rhs_code (stmt);
2336   tree op0 = gimple_assign_rhs1 (stmt);
2337   tree op1 = gimple_assign_rhs2 (stmt);
2338
2339   return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
2340                                           op0, code, op1);
2341 }
2342
2343 /* Returns a constant upper bound on the value of expression VAL.  VAL
2344    is considered to be unsigned.  If its type is signed, its value must
2345    be nonnegative.  */
2346
2347 static double_int
2348 derive_constant_upper_bound (tree val)
2349 {
2350   enum tree_code code;
2351   tree op0, op1;
2352
2353   extract_ops_from_tree (val, &code, &op0, &op1);
2354   return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
2355 }
2356
2357 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2358    whose type is TYPE.  The expression is considered to be unsigned.  If
2359    its type is signed, its value must be nonnegative.  */
2360
2361 static double_int
2362 derive_constant_upper_bound_ops (tree type, tree op0,
2363                                  enum tree_code code, tree op1)
2364 {
2365   tree subtype, maxt;
2366   double_int bnd, max, mmax, cst;
2367   gimple stmt;
2368
2369   if (INTEGRAL_TYPE_P (type))
2370     maxt = TYPE_MAX_VALUE (type);
2371   else
2372     maxt = upper_bound_in_type (type, type);
2373
2374   max = tree_to_double_int (maxt);
2375
2376   switch (code)
2377     {
2378     case INTEGER_CST:
2379       return tree_to_double_int (op0);
2380
2381     CASE_CONVERT:
2382       subtype = TREE_TYPE (op0);
2383       if (!TYPE_UNSIGNED (subtype)
2384           /* If TYPE is also signed, the fact that VAL is nonnegative implies
2385              that OP0 is nonnegative.  */
2386           && TYPE_UNSIGNED (type)
2387           && !tree_expr_nonnegative_p (op0))
2388         {
2389           /* If we cannot prove that the casted expression is nonnegative,
2390              we cannot establish more useful upper bound than the precision
2391              of the type gives us.  */
2392           return max;
2393         }
2394
2395       /* We now know that op0 is an nonnegative value.  Try deriving an upper
2396          bound for it.  */
2397       bnd = derive_constant_upper_bound (op0);
2398
2399       /* If the bound does not fit in TYPE, max. value of TYPE could be
2400          attained.  */
2401       if (double_int_ucmp (max, bnd) < 0)
2402         return max;
2403
2404       return bnd;
2405
2406     case PLUS_EXPR:
2407     case POINTER_PLUS_EXPR:
2408     case MINUS_EXPR:
2409       if (TREE_CODE (op1) != INTEGER_CST
2410           || !tree_expr_nonnegative_p (op0))
2411         return max;
2412
2413       /* Canonicalize to OP0 - CST.  Consider CST to be signed, in order to
2414          choose the most logical way how to treat this constant regardless
2415          of the signedness of the type.  */
2416       cst = tree_to_double_int (op1);
2417       cst = double_int_sext (cst, TYPE_PRECISION (type));
2418       if (code != MINUS_EXPR)
2419         cst = double_int_neg (cst);
2420
2421       bnd = derive_constant_upper_bound (op0);
2422
2423       if (double_int_negative_p (cst))
2424         {
2425           cst = double_int_neg (cst);
2426           /* Avoid CST == 0x80000...  */
2427           if (double_int_negative_p (cst))
2428             return max;;
2429
2430           /* OP0 + CST.  We need to check that
2431              BND <= MAX (type) - CST.  */
2432
2433           mmax = double_int_sub (max, cst);
2434           if (double_int_ucmp (bnd, mmax) > 0)
2435             return max;
2436
2437           return double_int_add (bnd, cst);
2438         }
2439       else
2440         {
2441           /* OP0 - CST, where CST >= 0.
2442
2443              If TYPE is signed, we have already verified that OP0 >= 0, and we
2444              know that the result is nonnegative.  This implies that
2445              VAL <= BND - CST.
2446
2447              If TYPE is unsigned, we must additionally know that OP0 >= CST,
2448              otherwise the operation underflows.
2449            */
2450
2451           /* This should only happen if the type is unsigned; however, for
2452              buggy programs that use overflowing signed arithmetics even with
2453              -fno-wrapv, this condition may also be true for signed values.  */
2454           if (double_int_ucmp (bnd, cst) < 0)
2455             return max;
2456
2457           if (TYPE_UNSIGNED (type))
2458             {
2459               tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
2460                                       double_int_to_tree (type, cst));
2461               if (!tem || integer_nonzerop (tem))
2462                 return max;
2463             }
2464
2465           bnd = double_int_sub (bnd, cst);
2466         }
2467
2468       return bnd;
2469
2470     case FLOOR_DIV_EXPR:
2471     case EXACT_DIV_EXPR:
2472       if (TREE_CODE (op1) != INTEGER_CST
2473           || tree_int_cst_sign_bit (op1))
2474         return max;
2475
2476       bnd = derive_constant_upper_bound (op0);
2477       return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
2478
2479     case BIT_AND_EXPR:
2480       if (TREE_CODE (op1) != INTEGER_CST
2481           || tree_int_cst_sign_bit (op1))
2482         return max;
2483       return tree_to_double_int (op1);
2484
2485     case SSA_NAME:
2486       stmt = SSA_NAME_DEF_STMT (op0);
2487       if (gimple_code (stmt) != GIMPLE_ASSIGN
2488           || gimple_assign_lhs (stmt) != op0)
2489         return max;
2490       return derive_constant_upper_bound_assign (stmt);
2491
2492     default:
2493       return max;
2494     }
2495 }
2496
2497 /* Records that every statement in LOOP is executed I_BOUND times.
2498    REALISTIC is true if I_BOUND is expected to be close to the real number
2499    of iterations.  UPPER is true if we are sure the loop iterates at most
2500    I_BOUND times.  */
2501
2502 static void
2503 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
2504                     bool upper)
2505 {
2506   /* Update the bounds only when there is no previous estimation, or when the current
2507      estimation is smaller.  */
2508   if (upper
2509       && (!loop->any_upper_bound
2510           || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
2511     {
2512       loop->any_upper_bound = true;
2513       loop->nb_iterations_upper_bound = i_bound;
2514     }
2515   if (realistic
2516       && (!loop->any_estimate
2517           || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
2518     {
2519       loop->any_estimate = true;
2520       loop->nb_iterations_estimate = i_bound;
2521     }
2522 }
2523
2524 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP.  IS_EXIT
2525    is true if the loop is exited immediately after STMT, and this exit
2526    is taken at last when the STMT is executed BOUND + 1 times.
2527    REALISTIC is true if BOUND is expected to be close to the real number
2528    of iterations.  UPPER is true if we are sure the loop iterates at most
2529    BOUND times.  I_BOUND is an unsigned double_int upper estimate on BOUND.  */
2530
2531 static void
2532 record_estimate (struct loop *loop, tree bound, double_int i_bound,
2533                  gimple at_stmt, bool is_exit, bool realistic, bool upper)
2534 {
2535   double_int delta;
2536   edge exit;
2537
2538   if (dump_file && (dump_flags & TDF_DETAILS))
2539     {
2540       fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
2541       print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
2542       fprintf (dump_file, " is %sexecuted at most ",
2543                upper ? "" : "probably ");
2544       print_generic_expr (dump_file, bound, TDF_SLIM);
2545       fprintf (dump_file, " (bounded by ");
2546       dump_double_int (dump_file, i_bound, true);
2547       fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2548     }
2549
2550   /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2551      real number of iterations.  */
2552   if (TREE_CODE (bound) != INTEGER_CST)
2553     realistic = false;
2554   if (!upper && !realistic)
2555     return;
2556
2557   /* If we have a guaranteed upper bound, record it in the appropriate
2558      list.  */
2559   if (upper)
2560     {
2561       struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound ();
2562
2563       elt->bound = i_bound;
2564       elt->stmt = at_stmt;
2565       elt->is_exit = is_exit;
2566       elt->next = loop->bounds;
2567       loop->bounds = elt;
2568     }
2569
2570   /* Update the number of iteration estimates according to the bound.
2571      If at_stmt is an exit or dominates the single exit from the loop,
2572      then the loop latch is executed at most BOUND times, otherwise
2573      it can be executed BOUND + 1 times.  */
2574   exit = single_exit (loop);
2575   if (is_exit
2576       || (exit != NULL
2577           && dominated_by_p (CDI_DOMINATORS,
2578                              exit->src, gimple_bb (at_stmt))))
2579     delta = double_int_zero;
2580   else
2581     delta = double_int_one;
2582   i_bound = double_int_add (i_bound, delta);
2583
2584   /* If an overflow occurred, ignore the result.  */
2585   if (double_int_ucmp (i_bound, delta) < 0)
2586     return;
2587
2588   record_niter_bound (loop, i_bound, realistic, upper);
2589 }
2590
2591 /* Record the estimate on number of iterations of LOOP based on the fact that
2592    the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2593    its values belong to the range <LOW, HIGH>.  REALISTIC is true if the
2594    estimated number of iterations is expected to be close to the real one.
2595    UPPER is true if we are sure the induction variable does not wrap.  */
2596
2597 static void
2598 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
2599                        tree low, tree high, bool realistic, bool upper)
2600 {
2601   tree niter_bound, extreme, delta;
2602   tree type = TREE_TYPE (base), unsigned_type;
2603   double_int max;
2604
2605   if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
2606     return;
2607
2608   if (dump_file && (dump_flags & TDF_DETAILS))
2609     {
2610       fprintf (dump_file, "Induction variable (");
2611       print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
2612       fprintf (dump_file, ") ");
2613       print_generic_expr (dump_file, base, TDF_SLIM);
2614       fprintf (dump_file, " + ");
2615       print_generic_expr (dump_file, step, TDF_SLIM);
2616       fprintf (dump_file, " * iteration does not wrap in statement ");
2617       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2618       fprintf (dump_file, " in loop %d.\n", loop->num);
2619     }
2620
2621   unsigned_type = unsigned_type_for (type);
2622   base = fold_convert (unsigned_type, base);
2623   step = fold_convert (unsigned_type, step);
2624
2625   if (tree_int_cst_sign_bit (step))
2626     {
2627       extreme = fold_convert (unsigned_type, low);
2628       if (TREE_CODE (base) != INTEGER_CST)
2629         base = fold_convert (unsigned_type, high);
2630       delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2631       step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
2632     }
2633   else
2634     {
2635       extreme = fold_convert (unsigned_type, high);
2636       if (TREE_CODE (base) != INTEGER_CST)
2637         base = fold_convert (unsigned_type, low);
2638       delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2639     }
2640
2641   /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2642      would get out of the range.  */
2643   niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
2644   max = derive_constant_upper_bound (niter_bound);
2645   record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2646 }
2647
2648 /* Returns true if REF is a reference to an array at the end of a dynamically
2649    allocated structure.  If this is the case, the array may be allocated larger
2650    than its upper bound implies.  */
2651
2652 bool
2653 array_at_struct_end_p (tree ref)
2654 {
2655   tree base = get_base_address (ref);
2656   tree parent, field;
2657
2658   /* Unless the reference is through a pointer, the size of the array matches
2659      its declaration.  */
2660   if (!base || (!INDIRECT_REF_P (base) && TREE_CODE (base) != MEM_REF))
2661     return false;
2662
2663   for (;handled_component_p (ref); ref = parent)
2664     {
2665       parent = TREE_OPERAND (ref, 0);
2666
2667       if (TREE_CODE (ref) == COMPONENT_REF)
2668         {
2669           /* All fields of a union are at its end.  */
2670           if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
2671             continue;
2672
2673           /* Unless the field is at the end of the struct, we are done.  */
2674           field = TREE_OPERAND (ref, 1);
2675           if (DECL_CHAIN (field))
2676             return false;
2677         }
2678
2679       /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2680          In all these cases, we might be accessing the last element, and
2681          although in practice this will probably never happen, it is legal for
2682          the indices of this last element to exceed the bounds of the array.
2683          Therefore, continue checking.  */
2684     }
2685
2686   return true;
2687 }
2688
2689 /* Determine information about number of iterations a LOOP from the index
2690    IDX of a data reference accessed in STMT.  RELIABLE is true if STMT is
2691    guaranteed to be executed in every iteration of LOOP.  Callback for
2692    for_each_index.  */
2693
2694 struct ilb_data
2695 {
2696   struct loop *loop;
2697   gimple stmt;
2698   bool reliable;
2699 };
2700
2701 static bool
2702 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
2703 {
2704   struct ilb_data *data = (struct ilb_data *) dta;
2705   tree ev, init, step;
2706   tree low, high, type, next;
2707   bool sign, upper = data->reliable, at_end = false;
2708   struct loop *loop = data->loop;
2709
2710   if (TREE_CODE (base) != ARRAY_REF)
2711     return true;
2712
2713   /* For arrays at the end of the structure, we are not guaranteed that they
2714      do not really extend over their declared size.  However, for arrays of
2715      size greater than one, this is unlikely to be intended.  */
2716   if (array_at_struct_end_p (base))
2717     {
2718       at_end = true;
2719       upper = false;
2720     }
2721
2722   ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
2723   init = initial_condition (ev);
2724   step = evolution_part_in_loop_num (ev, loop->num);
2725
2726   if (!init
2727       || !step
2728       || TREE_CODE (step) != INTEGER_CST
2729       || integer_zerop (step)
2730       || tree_contains_chrecs (init, NULL)
2731       || chrec_contains_symbols_defined_in_loop (init, loop->num))
2732     return true;
2733
2734   low = array_ref_low_bound (base);
2735   high = array_ref_up_bound (base);
2736
2737   /* The case of nonconstant bounds could be handled, but it would be
2738      complicated.  */
2739   if (TREE_CODE (low) != INTEGER_CST
2740       || !high
2741       || TREE_CODE (high) != INTEGER_CST)
2742     return true;
2743   sign = tree_int_cst_sign_bit (step);
2744   type = TREE_TYPE (step);
2745
2746   /* The array of length 1 at the end of a structure most likely extends
2747      beyond its bounds.  */
2748   if (at_end
2749       && operand_equal_p (low, high, 0))
2750     return true;
2751
2752   /* In case the relevant bound of the array does not fit in type, or
2753      it does, but bound + step (in type) still belongs into the range of the
2754      array, the index may wrap and still stay within the range of the array
2755      (consider e.g. if the array is indexed by the full range of
2756      unsigned char).
2757
2758      To make things simpler, we require both bounds to fit into type, although
2759      there are cases where this would not be strictly necessary.  */
2760   if (!int_fits_type_p (high, type)
2761       || !int_fits_type_p (low, type))
2762     return true;
2763   low = fold_convert (type, low);
2764   high = fold_convert (type, high);
2765
2766   if (sign)
2767     next = fold_binary (PLUS_EXPR, type, low, step);
2768   else
2769     next = fold_binary (PLUS_EXPR, type, high, step);
2770
2771   if (tree_int_cst_compare (low, next) <= 0
2772       && tree_int_cst_compare (next, high) <= 0)
2773     return true;
2774
2775   record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
2776   return true;
2777 }
2778
2779 /* Determine information about number of iterations a LOOP from the bounds
2780    of arrays in the data reference REF accessed in STMT.  RELIABLE is true if
2781    STMT is guaranteed to be executed in every iteration of LOOP.*/
2782
2783 static void
2784 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
2785                             bool reliable)
2786 {
2787   struct ilb_data data;
2788
2789   data.loop = loop;
2790   data.stmt = stmt;
2791   data.reliable = reliable;
2792   for_each_index (&ref, idx_infer_loop_bounds, &data);
2793 }
2794
2795 /* Determine information about number of iterations of a LOOP from the way
2796    arrays are used in STMT.  RELIABLE is true if STMT is guaranteed to be
2797    executed in every iteration of LOOP.  */
2798
2799 static void
2800 infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
2801 {
2802   if (is_gimple_assign (stmt))
2803     {
2804       tree op0 = gimple_assign_lhs (stmt);
2805       tree op1 = gimple_assign_rhs1 (stmt);
2806
2807       /* For each memory access, analyze its access function
2808          and record a bound on the loop iteration domain.  */
2809       if (REFERENCE_CLASS_P (op0))
2810         infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
2811
2812       if (REFERENCE_CLASS_P (op1))
2813         infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
2814     }
2815   else if (is_gimple_call (stmt))
2816     {
2817       tree arg, lhs;
2818       unsigned i, n = gimple_call_num_args (stmt);
2819
2820       lhs = gimple_call_lhs (stmt);
2821       if (lhs && REFERENCE_CLASS_P (lhs))
2822         infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
2823
2824       for (i = 0; i < n; i++)
2825         {
2826           arg = gimple_call_arg (stmt, i);
2827           if (REFERENCE_CLASS_P (arg))
2828             infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
2829         }
2830     }
2831 }
2832
2833 /* Determine information about number of iterations of a LOOP from the fact
2834    that pointer arithmetics in STMT does not overflow.  */
2835
2836 static void
2837 infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple stmt)
2838 {
2839   tree def, base, step, scev, type, low, high;
2840   tree var, ptr;
2841
2842   if (!is_gimple_assign (stmt)
2843       || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR)
2844     return;
2845
2846   def = gimple_assign_lhs (stmt);
2847   if (TREE_CODE (def) != SSA_NAME)
2848     return;
2849
2850   type = TREE_TYPE (def);
2851   if (!nowrap_type_p (type))
2852     return;
2853
2854   ptr = gimple_assign_rhs1 (stmt);
2855   if (!expr_invariant_in_loop_p (loop, ptr))
2856     return;
2857
2858   var = gimple_assign_rhs2 (stmt);
2859   if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var)))
2860     return;
2861
2862   scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2863   if (chrec_contains_undetermined (scev))
2864     return;
2865
2866   base = initial_condition_in_loop_num (scev, loop->num);
2867   step = evolution_part_in_loop_num (scev, loop->num);
2868
2869   if (!base || !step
2870       || TREE_CODE (step) != INTEGER_CST
2871       || tree_contains_chrecs (base, NULL)
2872       || chrec_contains_symbols_defined_in_loop (base, loop->num))
2873     return;
2874
2875   low = lower_bound_in_type (type, type);
2876   high = upper_bound_in_type (type, type);
2877
2878   /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2879      produce a NULL pointer.  The contrary would mean NULL points to an object,
2880      while NULL is supposed to compare unequal with the address of all objects.
2881      Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2882      NULL pointer since that would mean wrapping, which we assume here not to
2883      happen.  So, we can exclude NULL from the valid range of pointer
2884      arithmetic.  */
2885   if (flag_delete_null_pointer_checks && int_cst_value (low) == 0)
2886     low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
2887
2888   record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2889 }
2890
2891 /* Determine information about number of iterations of a LOOP from the fact
2892    that signed arithmetics in STMT does not overflow.  */
2893
2894 static void
2895 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
2896 {
2897   tree def, base, step, scev, type, low, high;
2898
2899   if (gimple_code (stmt) != GIMPLE_ASSIGN)
2900     return;
2901
2902   def = gimple_assign_lhs (stmt);
2903
2904   if (TREE_CODE (def) != SSA_NAME)
2905     return;
2906
2907   type = TREE_TYPE (def);
2908   if (!INTEGRAL_TYPE_P (type)
2909       || !TYPE_OVERFLOW_UNDEFINED (type))
2910     return;
2911
2912   scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2913   if (chrec_contains_undetermined (scev))
2914     return;
2915
2916   base = initial_condition_in_loop_num (scev, loop->num);
2917   step = evolution_part_in_loop_num (scev, loop->num);
2918
2919   if (!base || !step
2920       || TREE_CODE (step) != INTEGER_CST
2921       || tree_contains_chrecs (base, NULL)
2922       || chrec_contains_symbols_defined_in_loop (base, loop->num))
2923     return;
2924
2925   low = lower_bound_in_type (type, type);
2926   high = upper_bound_in_type (type, type);
2927
2928   record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2929 }
2930
2931 /* The following analyzers are extracting informations on the bounds
2932    of LOOP from the following undefined behaviors:
2933
2934    - data references should not access elements over the statically
2935      allocated size,
2936
2937    - signed variables should not overflow when flag_wrapv is not set.
2938 */
2939
2940 static void
2941 infer_loop_bounds_from_undefined (struct loop *loop)
2942 {
2943   unsigned i;
2944   basic_block *bbs;
2945   gimple_stmt_iterator bsi;
2946   basic_block bb;
2947   bool reliable;
2948
2949   bbs = get_loop_body (loop);
2950
2951   for (i = 0; i < loop->num_nodes; i++)
2952     {
2953       bb = bbs[i];
2954
2955       /* If BB is not executed in each iteration of the loop, we cannot
2956          use the operations in it to infer reliable upper bound on the
2957          # of iterations of the loop.  However, we can use it as a guess.  */
2958       reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
2959
2960       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2961         {
2962           gimple stmt = gsi_stmt (bsi);
2963
2964           infer_loop_bounds_from_array (loop, stmt, reliable);
2965
2966           if (reliable)
2967             {
2968               infer_loop_bounds_from_signedness (loop, stmt);
2969               infer_loop_bounds_from_pointer_arith (loop, stmt);
2970             }
2971         }
2972
2973     }
2974
2975   free (bbs);
2976 }
2977
2978 /* Converts VAL to double_int.  */
2979
2980 static double_int
2981 gcov_type_to_double_int (gcov_type val)
2982 {
2983   double_int ret;
2984
2985   ret.low = (unsigned HOST_WIDE_INT) val;
2986   /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2987      the size of type.  */
2988   val >>= HOST_BITS_PER_WIDE_INT - 1;
2989   val >>= 1;
2990   ret.high = (unsigned HOST_WIDE_INT) val;
2991
2992   return ret;
2993 }
2994
2995 /* Records estimates on numbers of iterations of LOOP.  If USE_UNDEFINED_P
2996    is true also use estimates derived from undefined behavior.  */
2997
2998 void
2999 estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p)
3000 {
3001   VEC (edge, heap) *exits;
3002   tree niter, type;
3003   unsigned i;
3004   struct tree_niter_desc niter_desc;
3005   edge ex;
3006   double_int bound;
3007
3008   /* Give up if we already have tried to compute an estimation.  */
3009   if (loop->estimate_state != EST_NOT_COMPUTED)
3010     return;
3011   loop->estimate_state = EST_AVAILABLE;
3012   loop->any_upper_bound = false;
3013   loop->any_estimate = false;
3014
3015   exits = get_loop_exit_edges (loop);
3016   FOR_EACH_VEC_ELT (edge, exits, i, ex)
3017     {
3018       if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
3019         continue;
3020
3021       niter = niter_desc.niter;
3022       type = TREE_TYPE (niter);
3023       if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
3024         niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
3025                         build_int_cst (type, 0),
3026                         niter);
3027       record_estimate (loop, niter, niter_desc.max,
3028                        last_stmt (ex->src),
3029                        true, true, true);
3030     }
3031   VEC_free (edge, heap, exits);
3032
3033   if (use_undefined_p)
3034     infer_loop_bounds_from_undefined (loop);
3035
3036   /* If we have a measured profile, use it to estimate the number of
3037      iterations.  */
3038   if (loop->header->count != 0)
3039     {
3040       gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
3041       bound = gcov_type_to_double_int (nit);
3042       record_niter_bound (loop, bound, true, false);
3043     }
3044
3045   /* If an upper bound is smaller than the realistic estimate of the
3046      number of iterations, use the upper bound instead.  */
3047   if (loop->any_upper_bound
3048       && loop->any_estimate
3049       && double_int_ucmp (loop->nb_iterations_upper_bound,
3050                           loop->nb_iterations_estimate) < 0)
3051     loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
3052 }
3053
3054 /* Sets NIT to the estimated number of executions of the latch of the
3055    LOOP.  If CONSERVATIVE is true, we must be sure that NIT is at least as
3056    large as the number of iterations.  If we have no reliable estimate,
3057    the function returns false, otherwise returns true.  */
3058
3059 bool
3060 estimated_loop_iterations (struct loop *loop, bool conservative,
3061                            double_int *nit)
3062 {
3063   estimate_numbers_of_iterations_loop (loop, true);
3064   if (conservative)
3065     {
3066       if (!loop->any_upper_bound)
3067         return false;
3068
3069       *nit = loop->nb_iterations_upper_bound;
3070     }
3071   else
3072     {
3073       if (!loop->any_estimate)
3074         return false;
3075
3076       *nit = loop->nb_iterations_estimate;
3077     }
3078
3079   return true;
3080 }
3081
3082 /* Similar to estimated_loop_iterations, but returns the estimate only
3083    if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
3084    on the number of iterations of LOOP could not be derived, returns -1.  */
3085
3086 HOST_WIDE_INT
3087 estimated_loop_iterations_int (struct loop *loop, bool conservative)
3088 {
3089   double_int nit;
3090   HOST_WIDE_INT hwi_nit;
3091
3092   if (!estimated_loop_iterations (loop, conservative, &nit))
3093     return -1;
3094
3095   if (!double_int_fits_in_shwi_p (nit))
3096     return -1;
3097   hwi_nit = double_int_to_shwi (nit);
3098
3099   return hwi_nit < 0 ? -1 : hwi_nit;
3100 }
3101
3102 /* Returns an upper bound on the number of executions of statements
3103    in the LOOP.  For statements before the loop exit, this exceeds
3104    the number of execution of the latch by one.  */
3105
3106 HOST_WIDE_INT
3107 max_stmt_executions_int (struct loop *loop, bool conservative)
3108 {
3109   HOST_WIDE_INT nit = estimated_loop_iterations_int (loop, conservative);
3110   HOST_WIDE_INT snit;
3111
3112   if (nit == -1)
3113     return -1;
3114
3115   snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
3116
3117   /* If the computation overflows, return -1.  */
3118   return snit < 0 ? -1 : snit;
3119 }
3120
3121 /* Sets NIT to the estimated number of executions of the latch of the
3122    LOOP, plus one.  If CONSERVATIVE is true, we must be sure that NIT is at
3123    least as large as the number of iterations.  If we have no reliable
3124    estimate, the function returns false, otherwise returns true.  */
3125
3126 bool
3127 max_stmt_executions (struct loop *loop, bool conservative, double_int *nit)
3128 {
3129   double_int nit_minus_one;
3130
3131   if (!estimated_loop_iterations (loop, conservative, nit))
3132     return false;
3133
3134   nit_minus_one = *nit;
3135
3136   *nit = double_int_add (*nit, double_int_one);
3137
3138   return double_int_ucmp (*nit, nit_minus_one) > 0;
3139 }
3140
3141 /* Records estimates on numbers of iterations of loops.  */
3142
3143 void
3144 estimate_numbers_of_iterations (bool use_undefined_p)
3145 {
3146   loop_iterator li;
3147   struct loop *loop;
3148
3149   /* We don't want to issue signed overflow warnings while getting
3150      loop iteration estimates.  */
3151   fold_defer_overflow_warnings ();
3152
3153   FOR_EACH_LOOP (li, loop, 0)
3154     {
3155       estimate_numbers_of_iterations_loop (loop, use_undefined_p);
3156     }
3157
3158   fold_undefer_and_ignore_overflow_warnings ();
3159 }
3160
3161 /* Returns true if statement S1 dominates statement S2.  */
3162
3163 bool
3164 stmt_dominates_stmt_p (gimple s1, gimple s2)
3165 {
3166   basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
3167
3168   if (!bb1
3169       || s1 == s2)
3170     return true;
3171
3172   if (bb1 == bb2)
3173     {
3174       gimple_stmt_iterator bsi;
3175
3176       if (gimple_code (s2) == GIMPLE_PHI)
3177         return false;
3178
3179       if (gimple_code (s1) == GIMPLE_PHI)
3180         return true;
3181
3182       for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
3183         if (gsi_stmt (bsi) == s1)
3184           return true;
3185
3186       return false;
3187     }
3188
3189   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
3190 }
3191
3192 /* Returns true when we can prove that the number of executions of
3193    STMT in the loop is at most NITER, according to the bound on
3194    the number of executions of the statement NITER_BOUND->stmt recorded in
3195    NITER_BOUND.  If STMT is NULL, we must prove this bound for all
3196    statements in the loop.  */
3197
3198 static bool
3199 n_of_executions_at_most (gimple stmt,
3200                          struct nb_iter_bound *niter_bound,
3201                          tree niter)
3202 {
3203   double_int bound = niter_bound->bound;
3204   tree nit_type = TREE_TYPE (niter), e;
3205   enum tree_code cmp;
3206
3207   gcc_assert (TYPE_UNSIGNED (nit_type));
3208
3209   /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3210      the number of iterations is small.  */
3211   if (!double_int_fits_to_tree_p (nit_type, bound))
3212     return false;
3213
3214   /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3215      times.  This means that:
3216
3217      -- if NITER_BOUND->is_exit is true, then everything before
3218         NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3219         times, and everything after it at most NITER_BOUND->bound times.
3220
3221      -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3222         is executed, then NITER_BOUND->stmt is executed as well in the same
3223         iteration (we conclude that if both statements belong to the same
3224         basic block, or if STMT is after NITER_BOUND->stmt), then STMT
3225         is executed at most NITER_BOUND->bound + 1 times.  Otherwise STMT is
3226         executed at most NITER_BOUND->bound + 2 times.  */
3227
3228   if (niter_bound->is_exit)
3229     {
3230       if (stmt
3231           && stmt != niter_bound->stmt
3232           && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
3233         cmp = GE_EXPR;
3234       else
3235         cmp = GT_EXPR;
3236     }
3237   else
3238     {
3239       if (!stmt
3240           || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
3241               && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
3242         {
3243           bound = double_int_add (bound, double_int_one);
3244           if (double_int_zero_p (bound)
3245               || !double_int_fits_to_tree_p (nit_type, bound))
3246             return false;
3247         }
3248       cmp = GT_EXPR;
3249     }
3250
3251   e = fold_binary (cmp, boolean_type_node,
3252                    niter, double_int_to_tree (nit_type, bound));
3253   return e && integer_nonzerop (e);
3254 }
3255
3256 /* Returns true if the arithmetics in TYPE can be assumed not to wrap.  */
3257
3258 bool
3259 nowrap_type_p (tree type)
3260 {
3261   if (INTEGRAL_TYPE_P (type)
3262       && TYPE_OVERFLOW_UNDEFINED (type))
3263     return true;
3264
3265   if (POINTER_TYPE_P (type))
3266     return true;
3267
3268   return false;
3269 }
3270
3271 /* Return false only when the induction variable BASE + STEP * I is
3272    known to not overflow: i.e. when the number of iterations is small
3273    enough with respect to the step and initial condition in order to
3274    keep the evolution confined in TYPEs bounds.  Return true when the
3275    iv is known to overflow or when the property is not computable.
3276
3277    USE_OVERFLOW_SEMANTICS is true if this function should assume that
3278    the rules for overflow of the given language apply (e.g., that signed
3279    arithmetics in C does not overflow).  */
3280
3281 bool
3282 scev_probably_wraps_p (tree base, tree step,
3283                        gimple at_stmt, struct loop *loop,
3284                        bool use_overflow_semantics)
3285 {
3286   struct nb_iter_bound *bound;
3287   tree delta, step_abs;
3288   tree unsigned_type, valid_niter;
3289   tree type = TREE_TYPE (step);
3290
3291   /* FIXME: We really need something like
3292      http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3293
3294      We used to test for the following situation that frequently appears
3295      during address arithmetics:
3296
3297        D.1621_13 = (long unsigned intD.4) D.1620_12;
3298        D.1622_14 = D.1621_13 * 8;
3299        D.1623_15 = (doubleD.29 *) D.1622_14;
3300
3301      And derived that the sequence corresponding to D_14
3302      can be proved to not wrap because it is used for computing a
3303      memory access; however, this is not really the case -- for example,
3304      if D_12 = (unsigned char) [254,+,1], then D_14 has values
3305      2032, 2040, 0, 8, ..., but the code is still legal.  */
3306
3307   if (chrec_contains_undetermined (base)
3308       || chrec_contains_undetermined (step))
3309     return true;
3310
3311   if (integer_zerop (step))
3312     return false;
3313
3314   /* If we can use the fact that signed and pointer arithmetics does not
3315      wrap, we are done.  */
3316   if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
3317     return false;
3318
3319   /* To be able to use estimates on number of iterations of the loop,
3320      we must have an upper bound on the absolute value of the step.  */
3321   if (TREE_CODE (step) != INTEGER_CST)
3322     return true;
3323
3324   /* Don't issue signed overflow warnings.  */
3325   fold_defer_overflow_warnings ();
3326
3327   /* Otherwise, compute the number of iterations before we reach the
3328      bound of the type, and verify that the loop is exited before this
3329      occurs.  */
3330   unsigned_type = unsigned_type_for (type);
3331   base = fold_convert (unsigned_type, base);
3332
3333   if (tree_int_cst_sign_bit (step))
3334     {
3335       tree extreme = fold_convert (unsigned_type,
3336                                    lower_bound_in_type (type, type));
3337       delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3338       step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
3339                               fold_convert (unsigned_type, step));
3340     }
3341   else
3342     {
3343       tree extreme = fold_convert (unsigned_type,
3344                                    upper_bound_in_type (type, type));
3345       delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3346       step_abs = fold_convert (unsigned_type, step);
3347     }
3348
3349   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
3350
3351   estimate_numbers_of_iterations_loop (loop, true);
3352   for (bound = loop->bounds; bound; bound = bound->next)
3353     {
3354       if (n_of_executions_at_most (at_stmt, bound, valid_niter))
3355         {
3356           fold_undefer_and_ignore_overflow_warnings ();
3357           return false;
3358         }
3359     }
3360
3361   fold_undefer_and_ignore_overflow_warnings ();
3362
3363   /* At this point we still don't have a proof that the iv does not
3364      overflow: give up.  */
3365   return true;
3366 }
3367
3368 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
3369
3370 void
3371 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3372 {
3373   struct nb_iter_bound *bound, *next;
3374
3375   loop->nb_iterations = NULL;
3376   loop->estimate_state = EST_NOT_COMPUTED;
3377   for (bound = loop->bounds; bound; bound = next)
3378     {
3379       next = bound->next;
3380       ggc_free (bound);
3381     }
3382
3383   loop->bounds = NULL;
3384 }
3385
3386 /* Frees the information on upper bounds on numbers of iterations of loops.  */
3387
3388 void
3389 free_numbers_of_iterations_estimates (void)
3390 {
3391   loop_iterator li;
3392   struct loop *loop;
3393
3394   FOR_EACH_LOOP (li, loop, 0)
3395     {
3396       free_numbers_of_iterations_estimates_loop (loop);
3397     }
3398 }
3399
3400 /* Substitute value VAL for ssa name NAME inside expressions held
3401    at LOOP.  */
3402
3403 void
3404 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3405 {
3406   loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
3407 }