VOP_FSYNC.9: Missing comma
[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     return NULL;
2073
2074   code = gimple_assign_rhs_code (stmt);
2075   if (gimple_references_memory_p (stmt)
2076       || TREE_CODE_CLASS (code) == tcc_reference
2077       || (code == ADDR_EXPR
2078           && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
2079     return NULL;
2080
2081   use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2082   if (use == NULL_TREE)
2083     return NULL;
2084
2085   return chain_of_csts_start (loop, use);
2086 }
2087
2088 /* Determines whether the expression X is derived from a result of a phi node
2089    in header of LOOP such that
2090
2091    * the derivation of X consists only from operations with constants
2092    * the initial value of the phi node is constant
2093    * the value of the phi node in the next iteration can be derived from the
2094      value in the current iteration by a chain of operations with constants.
2095
2096    If such phi node exists, it is returned, otherwise NULL is returned.  */
2097
2098 static gimple
2099 get_base_for (struct loop *loop, tree x)
2100 {
2101   gimple phi;
2102   tree init, next;
2103
2104   if (is_gimple_min_invariant (x))
2105     return NULL;
2106
2107   phi = chain_of_csts_start (loop, x);
2108   if (!phi)
2109     return NULL;
2110
2111   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2112   next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2113
2114   if (TREE_CODE (next) != SSA_NAME)
2115     return NULL;
2116
2117   if (!is_gimple_min_invariant (init))
2118     return NULL;
2119
2120   if (chain_of_csts_start (loop, next) != phi)
2121     return NULL;
2122
2123   return phi;
2124 }
2125
2126 /* Given an expression X, then
2127
2128    * if X is NULL_TREE, we return the constant BASE.
2129    * otherwise X is a SSA name, whose value in the considered loop is derived
2130      by a chain of operations with constant from a result of a phi node in
2131      the header of the loop.  Then we return value of X when the value of the
2132      result of this phi node is given by the constant BASE.  */
2133
2134 static tree
2135 get_val_for (tree x, tree base)
2136 {
2137   gimple stmt;
2138
2139   gcc_assert (is_gimple_min_invariant (base));
2140
2141   if (!x)
2142     return base;
2143
2144   stmt = SSA_NAME_DEF_STMT (x);
2145   if (gimple_code (stmt) == GIMPLE_PHI)
2146     return base;
2147
2148   gcc_assert (is_gimple_assign (stmt));
2149
2150   /* STMT must be either an assignment of a single SSA name or an
2151      expression involving an SSA name and a constant.  Try to fold that
2152      expression using the value for the SSA name.  */
2153   if (gimple_assign_ssa_name_copy_p (stmt))
2154     return get_val_for (gimple_assign_rhs1 (stmt), base);
2155   else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
2156            && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2157     {
2158       return fold_build1 (gimple_assign_rhs_code (stmt),
2159                           gimple_expr_type (stmt),
2160                           get_val_for (gimple_assign_rhs1 (stmt), base));
2161     }
2162   else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
2163     {
2164       tree rhs1 = gimple_assign_rhs1 (stmt);
2165       tree rhs2 = gimple_assign_rhs2 (stmt);
2166       if (TREE_CODE (rhs1) == SSA_NAME)
2167         rhs1 = get_val_for (rhs1, base);
2168       else if (TREE_CODE (rhs2) == SSA_NAME)
2169         rhs2 = get_val_for (rhs2, base);
2170       else
2171         gcc_unreachable ();
2172       return fold_build2 (gimple_assign_rhs_code (stmt),
2173                           gimple_expr_type (stmt), rhs1, rhs2);
2174     }
2175   else
2176     gcc_unreachable ();
2177 }
2178
2179
2180 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2181    by brute force -- i.e. by determining the value of the operands of the
2182    condition at EXIT in first few iterations of the loop (assuming that
2183    these values are constant) and determining the first one in that the
2184    condition is not satisfied.  Returns the constant giving the number
2185    of the iterations of LOOP if successful, chrec_dont_know otherwise.  */
2186
2187 tree
2188 loop_niter_by_eval (struct loop *loop, edge exit)
2189 {
2190   tree acnd;
2191   tree op[2], val[2], next[2], aval[2];
2192   gimple phi, cond;
2193   unsigned i, j;
2194   enum tree_code cmp;
2195
2196   cond = last_stmt (exit->src);
2197   if (!cond || gimple_code (cond) != GIMPLE_COND)
2198     return chrec_dont_know;
2199
2200   cmp = gimple_cond_code (cond);
2201   if (exit->flags & EDGE_TRUE_VALUE)
2202     cmp = invert_tree_comparison (cmp, false);
2203
2204   switch (cmp)
2205     {
2206     case EQ_EXPR:
2207     case NE_EXPR:
2208     case GT_EXPR:
2209     case GE_EXPR:
2210     case LT_EXPR:
2211     case LE_EXPR:
2212       op[0] = gimple_cond_lhs (cond);
2213       op[1] = gimple_cond_rhs (cond);
2214       break;
2215
2216     default:
2217       return chrec_dont_know;
2218     }
2219
2220   for (j = 0; j < 2; j++)
2221     {
2222       if (is_gimple_min_invariant (op[j]))
2223         {
2224           val[j] = op[j];
2225           next[j] = NULL_TREE;
2226           op[j] = NULL_TREE;
2227         }
2228       else
2229         {
2230           phi = get_base_for (loop, op[j]);
2231           if (!phi)
2232             return chrec_dont_know;
2233           val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2234           next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2235         }
2236     }
2237
2238   /* Don't issue signed overflow warnings.  */
2239   fold_defer_overflow_warnings ();
2240
2241   for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2242     {
2243       for (j = 0; j < 2; j++)
2244         aval[j] = get_val_for (op[j], val[j]);
2245
2246       acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2247       if (acnd && integer_zerop (acnd))
2248         {
2249           fold_undefer_and_ignore_overflow_warnings ();
2250           if (dump_file && (dump_flags & TDF_DETAILS))
2251             fprintf (dump_file,
2252                      "Proved that loop %d iterates %d times using brute force.\n",
2253                      loop->num, i);
2254           return build_int_cst (unsigned_type_node, i);
2255         }
2256
2257       for (j = 0; j < 2; j++)
2258         {
2259           val[j] = get_val_for (next[j], val[j]);
2260           if (!is_gimple_min_invariant (val[j]))
2261             {
2262               fold_undefer_and_ignore_overflow_warnings ();
2263               return chrec_dont_know;
2264             }
2265         }
2266     }
2267
2268   fold_undefer_and_ignore_overflow_warnings ();
2269
2270   return chrec_dont_know;
2271 }
2272
2273 /* Finds the exit of the LOOP by that the loop exits after a constant
2274    number of iterations and stores the exit edge to *EXIT.  The constant
2275    giving the number of iterations of LOOP is returned.  The number of
2276    iterations is determined using loop_niter_by_eval (i.e. by brute force
2277    evaluation).  If we are unable to find the exit for that loop_niter_by_eval
2278    determines the number of iterations, chrec_dont_know is returned.  */
2279
2280 tree
2281 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2282 {
2283   unsigned i;
2284   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2285   edge ex;
2286   tree niter = NULL_TREE, aniter;
2287
2288   *exit = NULL;
2289
2290   /* Loops with multiple exits are expensive to handle and less important.  */
2291   if (!flag_expensive_optimizations
2292       && VEC_length (edge, exits) > 1)
2293     {
2294       VEC_free (edge, heap, exits);
2295       return chrec_dont_know;
2296     }
2297
2298   FOR_EACH_VEC_ELT (edge, exits, i, ex)
2299     {
2300       if (!just_once_each_iteration_p (loop, ex->src))
2301         continue;
2302
2303       aniter = loop_niter_by_eval (loop, ex);
2304       if (chrec_contains_undetermined (aniter))
2305         continue;
2306
2307       if (niter
2308           && !tree_int_cst_lt (aniter, niter))
2309         continue;
2310
2311       niter = aniter;
2312       *exit = ex;
2313     }
2314   VEC_free (edge, heap, exits);
2315
2316   return niter ? niter : chrec_dont_know;
2317 }
2318
2319 /*
2320
2321    Analysis of upper bounds on number of iterations of a loop.
2322
2323 */
2324
2325 static double_int derive_constant_upper_bound_ops (tree, tree,
2326                                                    enum tree_code, tree);
2327
2328 /* Returns a constant upper bound on the value of the right-hand side of
2329    an assignment statement STMT.  */
2330
2331 static double_int
2332 derive_constant_upper_bound_assign (gimple stmt)
2333 {
2334   enum tree_code code = gimple_assign_rhs_code (stmt);
2335   tree op0 = gimple_assign_rhs1 (stmt);
2336   tree op1 = gimple_assign_rhs2 (stmt);
2337
2338   return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
2339                                           op0, code, op1);
2340 }
2341
2342 /* Returns a constant upper bound on the value of expression VAL.  VAL
2343    is considered to be unsigned.  If its type is signed, its value must
2344    be nonnegative.  */
2345
2346 static double_int
2347 derive_constant_upper_bound (tree val)
2348 {
2349   enum tree_code code;
2350   tree op0, op1;
2351
2352   extract_ops_from_tree (val, &code, &op0, &op1);
2353   return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
2354 }
2355
2356 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2357    whose type is TYPE.  The expression is considered to be unsigned.  If
2358    its type is signed, its value must be nonnegative.  */
2359
2360 static double_int
2361 derive_constant_upper_bound_ops (tree type, tree op0,
2362                                  enum tree_code code, tree op1)
2363 {
2364   tree subtype, maxt;
2365   double_int bnd, max, mmax, cst;
2366   gimple stmt;
2367
2368   if (INTEGRAL_TYPE_P (type))
2369     maxt = TYPE_MAX_VALUE (type);
2370   else
2371     maxt = upper_bound_in_type (type, type);
2372
2373   max = tree_to_double_int (maxt);
2374
2375   switch (code)
2376     {
2377     case INTEGER_CST:
2378       return tree_to_double_int (op0);
2379
2380     CASE_CONVERT:
2381       subtype = TREE_TYPE (op0);
2382       if (!TYPE_UNSIGNED (subtype)
2383           /* If TYPE is also signed, the fact that VAL is nonnegative implies
2384              that OP0 is nonnegative.  */
2385           && TYPE_UNSIGNED (type)
2386           && !tree_expr_nonnegative_p (op0))
2387         {
2388           /* If we cannot prove that the casted expression is nonnegative,
2389              we cannot establish more useful upper bound than the precision
2390              of the type gives us.  */
2391           return max;
2392         }
2393
2394       /* We now know that op0 is an nonnegative value.  Try deriving an upper
2395          bound for it.  */
2396       bnd = derive_constant_upper_bound (op0);
2397
2398       /* If the bound does not fit in TYPE, max. value of TYPE could be
2399          attained.  */
2400       if (double_int_ucmp (max, bnd) < 0)
2401         return max;
2402
2403       return bnd;
2404
2405     case PLUS_EXPR:
2406     case POINTER_PLUS_EXPR:
2407     case MINUS_EXPR:
2408       if (TREE_CODE (op1) != INTEGER_CST
2409           || !tree_expr_nonnegative_p (op0))
2410         return max;
2411
2412       /* Canonicalize to OP0 - CST.  Consider CST to be signed, in order to
2413          choose the most logical way how to treat this constant regardless
2414          of the signedness of the type.  */
2415       cst = tree_to_double_int (op1);
2416       cst = double_int_sext (cst, TYPE_PRECISION (type));
2417       if (code != MINUS_EXPR)
2418         cst = double_int_neg (cst);
2419
2420       bnd = derive_constant_upper_bound (op0);
2421
2422       if (double_int_negative_p (cst))
2423         {
2424           cst = double_int_neg (cst);
2425           /* Avoid CST == 0x80000...  */
2426           if (double_int_negative_p (cst))
2427             return max;;
2428
2429           /* OP0 + CST.  We need to check that
2430              BND <= MAX (type) - CST.  */
2431
2432           mmax = double_int_sub (max, cst);
2433           if (double_int_ucmp (bnd, mmax) > 0)
2434             return max;
2435
2436           return double_int_add (bnd, cst);
2437         }
2438       else
2439         {
2440           /* OP0 - CST, where CST >= 0.
2441
2442              If TYPE is signed, we have already verified that OP0 >= 0, and we
2443              know that the result is nonnegative.  This implies that
2444              VAL <= BND - CST.
2445
2446              If TYPE is unsigned, we must additionally know that OP0 >= CST,
2447              otherwise the operation underflows.
2448            */
2449
2450           /* This should only happen if the type is unsigned; however, for
2451              buggy programs that use overflowing signed arithmetics even with
2452              -fno-wrapv, this condition may also be true for signed values.  */
2453           if (double_int_ucmp (bnd, cst) < 0)
2454             return max;
2455
2456           if (TYPE_UNSIGNED (type))
2457             {
2458               tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
2459                                       double_int_to_tree (type, cst));
2460               if (!tem || integer_nonzerop (tem))
2461                 return max;
2462             }
2463
2464           bnd = double_int_sub (bnd, cst);
2465         }
2466
2467       return bnd;
2468
2469     case FLOOR_DIV_EXPR:
2470     case EXACT_DIV_EXPR:
2471       if (TREE_CODE (op1) != INTEGER_CST
2472           || tree_int_cst_sign_bit (op1))
2473         return max;
2474
2475       bnd = derive_constant_upper_bound (op0);
2476       return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
2477
2478     case BIT_AND_EXPR:
2479       if (TREE_CODE (op1) != INTEGER_CST
2480           || tree_int_cst_sign_bit (op1))
2481         return max;
2482       return tree_to_double_int (op1);
2483
2484     case SSA_NAME:
2485       stmt = SSA_NAME_DEF_STMT (op0);
2486       if (gimple_code (stmt) != GIMPLE_ASSIGN
2487           || gimple_assign_lhs (stmt) != op0)
2488         return max;
2489       return derive_constant_upper_bound_assign (stmt);
2490
2491     default:
2492       return max;
2493     }
2494 }
2495
2496 /* Records that every statement in LOOP is executed I_BOUND times.
2497    REALISTIC is true if I_BOUND is expected to be close to the real number
2498    of iterations.  UPPER is true if we are sure the loop iterates at most
2499    I_BOUND times.  */
2500
2501 static void
2502 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
2503                     bool upper)
2504 {
2505   /* Update the bounds only when there is no previous estimation, or when the current
2506      estimation is smaller.  */
2507   if (upper
2508       && (!loop->any_upper_bound
2509           || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
2510     {
2511       loop->any_upper_bound = true;
2512       loop->nb_iterations_upper_bound = i_bound;
2513     }
2514   if (realistic
2515       && (!loop->any_estimate
2516           || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
2517     {
2518       loop->any_estimate = true;
2519       loop->nb_iterations_estimate = i_bound;
2520     }
2521 }
2522
2523 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP.  IS_EXIT
2524    is true if the loop is exited immediately after STMT, and this exit
2525    is taken at last when the STMT is executed BOUND + 1 times.
2526    REALISTIC is true if BOUND is expected to be close to the real number
2527    of iterations.  UPPER is true if we are sure the loop iterates at most
2528    BOUND times.  I_BOUND is an unsigned double_int upper estimate on BOUND.  */
2529
2530 static void
2531 record_estimate (struct loop *loop, tree bound, double_int i_bound,
2532                  gimple at_stmt, bool is_exit, bool realistic, bool upper)
2533 {
2534   double_int delta;
2535   edge exit;
2536
2537   if (dump_file && (dump_flags & TDF_DETAILS))
2538     {
2539       fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
2540       print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
2541       fprintf (dump_file, " is %sexecuted at most ",
2542                upper ? "" : "probably ");
2543       print_generic_expr (dump_file, bound, TDF_SLIM);
2544       fprintf (dump_file, " (bounded by ");
2545       dump_double_int (dump_file, i_bound, true);
2546       fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2547     }
2548
2549   /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2550      real number of iterations.  */
2551   if (TREE_CODE (bound) != INTEGER_CST)
2552     realistic = false;
2553   if (!upper && !realistic)
2554     return;
2555
2556   /* If we have a guaranteed upper bound, record it in the appropriate
2557      list.  */
2558   if (upper)
2559     {
2560       struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound ();
2561
2562       elt->bound = i_bound;
2563       elt->stmt = at_stmt;
2564       elt->is_exit = is_exit;
2565       elt->next = loop->bounds;
2566       loop->bounds = elt;
2567     }
2568
2569   /* Update the number of iteration estimates according to the bound.
2570      If at_stmt is an exit or dominates the single exit from the loop,
2571      then the loop latch is executed at most BOUND times, otherwise
2572      it can be executed BOUND + 1 times.  */
2573   exit = single_exit (loop);
2574   if (is_exit
2575       || (exit != NULL
2576           && dominated_by_p (CDI_DOMINATORS,
2577                              exit->src, gimple_bb (at_stmt))))
2578     delta = double_int_zero;
2579   else
2580     delta = double_int_one;
2581   i_bound = double_int_add (i_bound, delta);
2582
2583   /* If an overflow occurred, ignore the result.  */
2584   if (double_int_ucmp (i_bound, delta) < 0)
2585     return;
2586
2587   record_niter_bound (loop, i_bound, realistic, upper);
2588 }
2589
2590 /* Record the estimate on number of iterations of LOOP based on the fact that
2591    the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2592    its values belong to the range <LOW, HIGH>.  REALISTIC is true if the
2593    estimated number of iterations is expected to be close to the real one.
2594    UPPER is true if we are sure the induction variable does not wrap.  */
2595
2596 static void
2597 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
2598                        tree low, tree high, bool realistic, bool upper)
2599 {
2600   tree niter_bound, extreme, delta;
2601   tree type = TREE_TYPE (base), unsigned_type;
2602   double_int max;
2603
2604   if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
2605     return;
2606
2607   if (dump_file && (dump_flags & TDF_DETAILS))
2608     {
2609       fprintf (dump_file, "Induction variable (");
2610       print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
2611       fprintf (dump_file, ") ");
2612       print_generic_expr (dump_file, base, TDF_SLIM);
2613       fprintf (dump_file, " + ");
2614       print_generic_expr (dump_file, step, TDF_SLIM);
2615       fprintf (dump_file, " * iteration does not wrap in statement ");
2616       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2617       fprintf (dump_file, " in loop %d.\n", loop->num);
2618     }
2619
2620   unsigned_type = unsigned_type_for (type);
2621   base = fold_convert (unsigned_type, base);
2622   step = fold_convert (unsigned_type, step);
2623
2624   if (tree_int_cst_sign_bit (step))
2625     {
2626       extreme = fold_convert (unsigned_type, low);
2627       if (TREE_CODE (base) != INTEGER_CST)
2628         base = fold_convert (unsigned_type, high);
2629       delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2630       step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
2631     }
2632   else
2633     {
2634       extreme = fold_convert (unsigned_type, high);
2635       if (TREE_CODE (base) != INTEGER_CST)
2636         base = fold_convert (unsigned_type, low);
2637       delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2638     }
2639
2640   /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2641      would get out of the range.  */
2642   niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
2643   max = derive_constant_upper_bound (niter_bound);
2644   record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2645 }
2646
2647 /* Returns true if REF is a reference to an array at the end of a dynamically
2648    allocated structure.  If this is the case, the array may be allocated larger
2649    than its upper bound implies.  */
2650
2651 bool
2652 array_at_struct_end_p (tree ref)
2653 {
2654   tree base = get_base_address (ref);
2655   tree parent, field;
2656
2657   /* Unless the reference is through a pointer, the size of the array matches
2658      its declaration.  */
2659   if (!base || (!INDIRECT_REF_P (base) && TREE_CODE (base) != MEM_REF))
2660     return false;
2661
2662   for (;handled_component_p (ref); ref = parent)
2663     {
2664       parent = TREE_OPERAND (ref, 0);
2665
2666       if (TREE_CODE (ref) == COMPONENT_REF)
2667         {
2668           /* All fields of a union are at its end.  */
2669           if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
2670             continue;
2671
2672           /* Unless the field is at the end of the struct, we are done.  */
2673           field = TREE_OPERAND (ref, 1);
2674           if (DECL_CHAIN (field))
2675             return false;
2676         }
2677
2678       /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2679          In all these cases, we might be accessing the last element, and
2680          although in practice this will probably never happen, it is legal for
2681          the indices of this last element to exceed the bounds of the array.
2682          Therefore, continue checking.  */
2683     }
2684
2685   return true;
2686 }
2687
2688 /* Determine information about number of iterations a LOOP from the index
2689    IDX of a data reference accessed in STMT.  RELIABLE is true if STMT is
2690    guaranteed to be executed in every iteration of LOOP.  Callback for
2691    for_each_index.  */
2692
2693 struct ilb_data
2694 {
2695   struct loop *loop;
2696   gimple stmt;
2697   bool reliable;
2698 };
2699
2700 static bool
2701 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
2702 {
2703   struct ilb_data *data = (struct ilb_data *) dta;
2704   tree ev, init, step;
2705   tree low, high, type, next;
2706   bool sign, upper = data->reliable, at_end = false;
2707   struct loop *loop = data->loop;
2708
2709   if (TREE_CODE (base) != ARRAY_REF)
2710     return true;
2711
2712   /* For arrays at the end of the structure, we are not guaranteed that they
2713      do not really extend over their declared size.  However, for arrays of
2714      size greater than one, this is unlikely to be intended.  */
2715   if (array_at_struct_end_p (base))
2716     {
2717       at_end = true;
2718       upper = false;
2719     }
2720
2721   ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
2722   init = initial_condition (ev);
2723   step = evolution_part_in_loop_num (ev, loop->num);
2724
2725   if (!init
2726       || !step
2727       || TREE_CODE (step) != INTEGER_CST
2728       || integer_zerop (step)
2729       || tree_contains_chrecs (init, NULL)
2730       || chrec_contains_symbols_defined_in_loop (init, loop->num))
2731     return true;
2732
2733   low = array_ref_low_bound (base);
2734   high = array_ref_up_bound (base);
2735
2736   /* The case of nonconstant bounds could be handled, but it would be
2737      complicated.  */
2738   if (TREE_CODE (low) != INTEGER_CST
2739       || !high
2740       || TREE_CODE (high) != INTEGER_CST)
2741     return true;
2742   sign = tree_int_cst_sign_bit (step);
2743   type = TREE_TYPE (step);
2744
2745   /* The array of length 1 at the end of a structure most likely extends
2746      beyond its bounds.  */
2747   if (at_end
2748       && operand_equal_p (low, high, 0))
2749     return true;
2750
2751   /* In case the relevant bound of the array does not fit in type, or
2752      it does, but bound + step (in type) still belongs into the range of the
2753      array, the index may wrap and still stay within the range of the array
2754      (consider e.g. if the array is indexed by the full range of
2755      unsigned char).
2756
2757      To make things simpler, we require both bounds to fit into type, although
2758      there are cases where this would not be strictly necessary.  */
2759   if (!int_fits_type_p (high, type)
2760       || !int_fits_type_p (low, type))
2761     return true;
2762   low = fold_convert (type, low);
2763   high = fold_convert (type, high);
2764
2765   if (sign)
2766     next = fold_binary (PLUS_EXPR, type, low, step);
2767   else
2768     next = fold_binary (PLUS_EXPR, type, high, step);
2769
2770   if (tree_int_cst_compare (low, next) <= 0
2771       && tree_int_cst_compare (next, high) <= 0)
2772     return true;
2773
2774   record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
2775   return true;
2776 }
2777
2778 /* Determine information about number of iterations a LOOP from the bounds
2779    of arrays in the data reference REF accessed in STMT.  RELIABLE is true if
2780    STMT is guaranteed to be executed in every iteration of LOOP.*/
2781
2782 static void
2783 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
2784                             bool reliable)
2785 {
2786   struct ilb_data data;
2787
2788   data.loop = loop;
2789   data.stmt = stmt;
2790   data.reliable = reliable;
2791   for_each_index (&ref, idx_infer_loop_bounds, &data);
2792 }
2793
2794 /* Determine information about number of iterations of a LOOP from the way
2795    arrays are used in STMT.  RELIABLE is true if STMT is guaranteed to be
2796    executed in every iteration of LOOP.  */
2797
2798 static void
2799 infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
2800 {
2801   if (is_gimple_assign (stmt))
2802     {
2803       tree op0 = gimple_assign_lhs (stmt);
2804       tree op1 = gimple_assign_rhs1 (stmt);
2805
2806       /* For each memory access, analyze its access function
2807          and record a bound on the loop iteration domain.  */
2808       if (REFERENCE_CLASS_P (op0))
2809         infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
2810
2811       if (REFERENCE_CLASS_P (op1))
2812         infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
2813     }
2814   else if (is_gimple_call (stmt))
2815     {
2816       tree arg, lhs;
2817       unsigned i, n = gimple_call_num_args (stmt);
2818
2819       lhs = gimple_call_lhs (stmt);
2820       if (lhs && REFERENCE_CLASS_P (lhs))
2821         infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
2822
2823       for (i = 0; i < n; i++)
2824         {
2825           arg = gimple_call_arg (stmt, i);
2826           if (REFERENCE_CLASS_P (arg))
2827             infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
2828         }
2829     }
2830 }
2831
2832 /* Determine information about number of iterations of a LOOP from the fact
2833    that pointer arithmetics in STMT does not overflow.  */
2834
2835 static void
2836 infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple stmt)
2837 {
2838   tree def, base, step, scev, type, low, high;
2839   tree var, ptr;
2840
2841   if (!is_gimple_assign (stmt)
2842       || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR)
2843     return;
2844
2845   def = gimple_assign_lhs (stmt);
2846   if (TREE_CODE (def) != SSA_NAME)
2847     return;
2848
2849   type = TREE_TYPE (def);
2850   if (!nowrap_type_p (type))
2851     return;
2852
2853   ptr = gimple_assign_rhs1 (stmt);
2854   if (!expr_invariant_in_loop_p (loop, ptr))
2855     return;
2856
2857   var = gimple_assign_rhs2 (stmt);
2858   if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var)))
2859     return;
2860
2861   scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2862   if (chrec_contains_undetermined (scev))
2863     return;
2864
2865   base = initial_condition_in_loop_num (scev, loop->num);
2866   step = evolution_part_in_loop_num (scev, loop->num);
2867
2868   if (!base || !step
2869       || TREE_CODE (step) != INTEGER_CST
2870       || tree_contains_chrecs (base, NULL)
2871       || chrec_contains_symbols_defined_in_loop (base, loop->num))
2872     return;
2873
2874   low = lower_bound_in_type (type, type);
2875   high = upper_bound_in_type (type, type);
2876
2877   /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2878      produce a NULL pointer.  The contrary would mean NULL points to an object,
2879      while NULL is supposed to compare unequal with the address of all objects.
2880      Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2881      NULL pointer since that would mean wrapping, which we assume here not to
2882      happen.  So, we can exclude NULL from the valid range of pointer
2883      arithmetic.  */
2884   if (flag_delete_null_pointer_checks && int_cst_value (low) == 0)
2885     low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
2886
2887   record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2888 }
2889
2890 /* Determine information about number of iterations of a LOOP from the fact
2891    that signed arithmetics in STMT does not overflow.  */
2892
2893 static void
2894 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
2895 {
2896   tree def, base, step, scev, type, low, high;
2897
2898   if (gimple_code (stmt) != GIMPLE_ASSIGN)
2899     return;
2900
2901   def = gimple_assign_lhs (stmt);
2902
2903   if (TREE_CODE (def) != SSA_NAME)
2904     return;
2905
2906   type = TREE_TYPE (def);
2907   if (!INTEGRAL_TYPE_P (type)
2908       || !TYPE_OVERFLOW_UNDEFINED (type))
2909     return;
2910
2911   scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2912   if (chrec_contains_undetermined (scev))
2913     return;
2914
2915   base = initial_condition_in_loop_num (scev, loop->num);
2916   step = evolution_part_in_loop_num (scev, loop->num);
2917
2918   if (!base || !step
2919       || TREE_CODE (step) != INTEGER_CST
2920       || tree_contains_chrecs (base, NULL)
2921       || chrec_contains_symbols_defined_in_loop (base, loop->num))
2922     return;
2923
2924   low = lower_bound_in_type (type, type);
2925   high = upper_bound_in_type (type, type);
2926
2927   record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2928 }
2929
2930 /* The following analyzers are extracting informations on the bounds
2931    of LOOP from the following undefined behaviors:
2932
2933    - data references should not access elements over the statically
2934      allocated size,
2935
2936    - signed variables should not overflow when flag_wrapv is not set.
2937 */
2938
2939 static void
2940 infer_loop_bounds_from_undefined (struct loop *loop)
2941 {
2942   unsigned i;
2943   basic_block *bbs;
2944   gimple_stmt_iterator bsi;
2945   basic_block bb;
2946   bool reliable;
2947
2948   bbs = get_loop_body (loop);
2949
2950   for (i = 0; i < loop->num_nodes; i++)
2951     {
2952       bb = bbs[i];
2953
2954       /* If BB is not executed in each iteration of the loop, we cannot
2955          use the operations in it to infer reliable upper bound on the
2956          # of iterations of the loop.  However, we can use it as a guess.  */
2957       reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
2958
2959       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2960         {
2961           gimple stmt = gsi_stmt (bsi);
2962
2963           infer_loop_bounds_from_array (loop, stmt, reliable);
2964
2965           if (reliable)
2966             {
2967               infer_loop_bounds_from_signedness (loop, stmt);
2968               infer_loop_bounds_from_pointer_arith (loop, stmt);
2969             }
2970         }
2971
2972     }
2973
2974   free (bbs);
2975 }
2976
2977 /* Converts VAL to double_int.  */
2978
2979 static double_int
2980 gcov_type_to_double_int (gcov_type val)
2981 {
2982   double_int ret;
2983
2984   ret.low = (unsigned HOST_WIDE_INT) val;
2985   /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2986      the size of type.  */
2987   val >>= HOST_BITS_PER_WIDE_INT - 1;
2988   val >>= 1;
2989   ret.high = (unsigned HOST_WIDE_INT) val;
2990
2991   return ret;
2992 }
2993
2994 /* Records estimates on numbers of iterations of LOOP.  If USE_UNDEFINED_P
2995    is true also use estimates derived from undefined behavior.  */
2996
2997 void
2998 estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p)
2999 {
3000   VEC (edge, heap) *exits;
3001   tree niter, type;
3002   unsigned i;
3003   struct tree_niter_desc niter_desc;
3004   edge ex;
3005   double_int bound;
3006
3007   /* Give up if we already have tried to compute an estimation.  */
3008   if (loop->estimate_state != EST_NOT_COMPUTED)
3009     return;
3010   loop->estimate_state = EST_AVAILABLE;
3011   loop->any_upper_bound = false;
3012   loop->any_estimate = false;
3013
3014   exits = get_loop_exit_edges (loop);
3015   FOR_EACH_VEC_ELT (edge, exits, i, ex)
3016     {
3017       if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
3018         continue;
3019
3020       niter = niter_desc.niter;
3021       type = TREE_TYPE (niter);
3022       if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
3023         niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
3024                         build_int_cst (type, 0),
3025                         niter);
3026       record_estimate (loop, niter, niter_desc.max,
3027                        last_stmt (ex->src),
3028                        true, true, true);
3029     }
3030   VEC_free (edge, heap, exits);
3031
3032   if (use_undefined_p)
3033     infer_loop_bounds_from_undefined (loop);
3034
3035   /* If we have a measured profile, use it to estimate the number of
3036      iterations.  */
3037   if (loop->header->count != 0)
3038     {
3039       gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
3040       bound = gcov_type_to_double_int (nit);
3041       record_niter_bound (loop, bound, true, false);
3042     }
3043
3044   /* If an upper bound is smaller than the realistic estimate of the
3045      number of iterations, use the upper bound instead.  */
3046   if (loop->any_upper_bound
3047       && loop->any_estimate
3048       && double_int_ucmp (loop->nb_iterations_upper_bound,
3049                           loop->nb_iterations_estimate) < 0)
3050     loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
3051 }
3052
3053 /* Sets NIT to the estimated number of executions of the latch of the
3054    LOOP.  If CONSERVATIVE is true, we must be sure that NIT is at least as
3055    large as the number of iterations.  If we have no reliable estimate,
3056    the function returns false, otherwise returns true.  */
3057
3058 bool
3059 estimated_loop_iterations (struct loop *loop, bool conservative,
3060                            double_int *nit)
3061 {
3062   estimate_numbers_of_iterations_loop (loop, true);
3063   if (conservative)
3064     {
3065       if (!loop->any_upper_bound)
3066         return false;
3067
3068       *nit = loop->nb_iterations_upper_bound;
3069     }
3070   else
3071     {
3072       if (!loop->any_estimate)
3073         return false;
3074
3075       *nit = loop->nb_iterations_estimate;
3076     }
3077
3078   return true;
3079 }
3080
3081 /* Similar to estimated_loop_iterations, but returns the estimate only
3082    if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
3083    on the number of iterations of LOOP could not be derived, returns -1.  */
3084
3085 HOST_WIDE_INT
3086 estimated_loop_iterations_int (struct loop *loop, bool conservative)
3087 {
3088   double_int nit;
3089   HOST_WIDE_INT hwi_nit;
3090
3091   if (!estimated_loop_iterations (loop, conservative, &nit))
3092     return -1;
3093
3094   if (!double_int_fits_in_shwi_p (nit))
3095     return -1;
3096   hwi_nit = double_int_to_shwi (nit);
3097
3098   return hwi_nit < 0 ? -1 : hwi_nit;
3099 }
3100
3101 /* Returns an upper bound on the number of executions of statements
3102    in the LOOP.  For statements before the loop exit, this exceeds
3103    the number of execution of the latch by one.  */
3104
3105 HOST_WIDE_INT
3106 max_stmt_executions_int (struct loop *loop, bool conservative)
3107 {
3108   HOST_WIDE_INT nit = estimated_loop_iterations_int (loop, conservative);
3109   HOST_WIDE_INT snit;
3110
3111   if (nit == -1)
3112     return -1;
3113
3114   snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
3115
3116   /* If the computation overflows, return -1.  */
3117   return snit < 0 ? -1 : snit;
3118 }
3119
3120 /* Sets NIT to the estimated number of executions of the latch of the
3121    LOOP, plus one.  If CONSERVATIVE is true, we must be sure that NIT is at
3122    least as large as the number of iterations.  If we have no reliable
3123    estimate, the function returns false, otherwise returns true.  */
3124
3125 bool
3126 max_stmt_executions (struct loop *loop, bool conservative, double_int *nit)
3127 {
3128   double_int nit_minus_one;
3129
3130   if (!estimated_loop_iterations (loop, conservative, nit))
3131     return false;
3132
3133   nit_minus_one = *nit;
3134
3135   *nit = double_int_add (*nit, double_int_one);
3136
3137   return double_int_ucmp (*nit, nit_minus_one) > 0;
3138 }
3139
3140 /* Records estimates on numbers of iterations of loops.  */
3141
3142 void
3143 estimate_numbers_of_iterations (bool use_undefined_p)
3144 {
3145   loop_iterator li;
3146   struct loop *loop;
3147
3148   /* We don't want to issue signed overflow warnings while getting
3149      loop iteration estimates.  */
3150   fold_defer_overflow_warnings ();
3151
3152   FOR_EACH_LOOP (li, loop, 0)
3153     {
3154       estimate_numbers_of_iterations_loop (loop, use_undefined_p);
3155     }
3156
3157   fold_undefer_and_ignore_overflow_warnings ();
3158 }
3159
3160 /* Returns true if statement S1 dominates statement S2.  */
3161
3162 bool
3163 stmt_dominates_stmt_p (gimple s1, gimple s2)
3164 {
3165   basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
3166
3167   if (!bb1
3168       || s1 == s2)
3169     return true;
3170
3171   if (bb1 == bb2)
3172     {
3173       gimple_stmt_iterator bsi;
3174
3175       if (gimple_code (s2) == GIMPLE_PHI)
3176         return false;
3177
3178       if (gimple_code (s1) == GIMPLE_PHI)
3179         return true;
3180
3181       for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
3182         if (gsi_stmt (bsi) == s1)
3183           return true;
3184
3185       return false;
3186     }
3187
3188   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
3189 }
3190
3191 /* Returns true when we can prove that the number of executions of
3192    STMT in the loop is at most NITER, according to the bound on
3193    the number of executions of the statement NITER_BOUND->stmt recorded in
3194    NITER_BOUND.  If STMT is NULL, we must prove this bound for all
3195    statements in the loop.  */
3196
3197 static bool
3198 n_of_executions_at_most (gimple stmt,
3199                          struct nb_iter_bound *niter_bound,
3200                          tree niter)
3201 {
3202   double_int bound = niter_bound->bound;
3203   tree nit_type = TREE_TYPE (niter), e;
3204   enum tree_code cmp;
3205
3206   gcc_assert (TYPE_UNSIGNED (nit_type));
3207
3208   /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3209      the number of iterations is small.  */
3210   if (!double_int_fits_to_tree_p (nit_type, bound))
3211     return false;
3212
3213   /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3214      times.  This means that:
3215
3216      -- if NITER_BOUND->is_exit is true, then everything before
3217         NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3218         times, and everything after it at most NITER_BOUND->bound times.
3219
3220      -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3221         is executed, then NITER_BOUND->stmt is executed as well in the same
3222         iteration (we conclude that if both statements belong to the same
3223         basic block, or if STMT is after NITER_BOUND->stmt), then STMT
3224         is executed at most NITER_BOUND->bound + 1 times.  Otherwise STMT is
3225         executed at most NITER_BOUND->bound + 2 times.  */
3226
3227   if (niter_bound->is_exit)
3228     {
3229       if (stmt
3230           && stmt != niter_bound->stmt
3231           && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
3232         cmp = GE_EXPR;
3233       else
3234         cmp = GT_EXPR;
3235     }
3236   else
3237     {
3238       if (!stmt
3239           || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
3240               && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
3241         {
3242           bound = double_int_add (bound, double_int_one);
3243           if (double_int_zero_p (bound)
3244               || !double_int_fits_to_tree_p (nit_type, bound))
3245             return false;
3246         }
3247       cmp = GT_EXPR;
3248     }
3249
3250   e = fold_binary (cmp, boolean_type_node,
3251                    niter, double_int_to_tree (nit_type, bound));
3252   return e && integer_nonzerop (e);
3253 }
3254
3255 /* Returns true if the arithmetics in TYPE can be assumed not to wrap.  */
3256
3257 bool
3258 nowrap_type_p (tree type)
3259 {
3260   if (INTEGRAL_TYPE_P (type)
3261       && TYPE_OVERFLOW_UNDEFINED (type))
3262     return true;
3263
3264   if (POINTER_TYPE_P (type))
3265     return true;
3266
3267   return false;
3268 }
3269
3270 /* Return false only when the induction variable BASE + STEP * I is
3271    known to not overflow: i.e. when the number of iterations is small
3272    enough with respect to the step and initial condition in order to
3273    keep the evolution confined in TYPEs bounds.  Return true when the
3274    iv is known to overflow or when the property is not computable.
3275
3276    USE_OVERFLOW_SEMANTICS is true if this function should assume that
3277    the rules for overflow of the given language apply (e.g., that signed
3278    arithmetics in C does not overflow).  */
3279
3280 bool
3281 scev_probably_wraps_p (tree base, tree step,
3282                        gimple at_stmt, struct loop *loop,
3283                        bool use_overflow_semantics)
3284 {
3285   struct nb_iter_bound *bound;
3286   tree delta, step_abs;
3287   tree unsigned_type, valid_niter;
3288   tree type = TREE_TYPE (step);
3289
3290   /* FIXME: We really need something like
3291      http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3292
3293      We used to test for the following situation that frequently appears
3294      during address arithmetics:
3295
3296        D.1621_13 = (long unsigned intD.4) D.1620_12;
3297        D.1622_14 = D.1621_13 * 8;
3298        D.1623_15 = (doubleD.29 *) D.1622_14;
3299
3300      And derived that the sequence corresponding to D_14
3301      can be proved to not wrap because it is used for computing a
3302      memory access; however, this is not really the case -- for example,
3303      if D_12 = (unsigned char) [254,+,1], then D_14 has values
3304      2032, 2040, 0, 8, ..., but the code is still legal.  */
3305
3306   if (chrec_contains_undetermined (base)
3307       || chrec_contains_undetermined (step))
3308     return true;
3309
3310   if (integer_zerop (step))
3311     return false;
3312
3313   /* If we can use the fact that signed and pointer arithmetics does not
3314      wrap, we are done.  */
3315   if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
3316     return false;
3317
3318   /* To be able to use estimates on number of iterations of the loop,
3319      we must have an upper bound on the absolute value of the step.  */
3320   if (TREE_CODE (step) != INTEGER_CST)
3321     return true;
3322
3323   /* Don't issue signed overflow warnings.  */
3324   fold_defer_overflow_warnings ();
3325
3326   /* Otherwise, compute the number of iterations before we reach the
3327      bound of the type, and verify that the loop is exited before this
3328      occurs.  */
3329   unsigned_type = unsigned_type_for (type);
3330   base = fold_convert (unsigned_type, base);
3331
3332   if (tree_int_cst_sign_bit (step))
3333     {
3334       tree extreme = fold_convert (unsigned_type,
3335                                    lower_bound_in_type (type, type));
3336       delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3337       step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
3338                               fold_convert (unsigned_type, step));
3339     }
3340   else
3341     {
3342       tree extreme = fold_convert (unsigned_type,
3343                                    upper_bound_in_type (type, type));
3344       delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3345       step_abs = fold_convert (unsigned_type, step);
3346     }
3347
3348   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
3349
3350   estimate_numbers_of_iterations_loop (loop, true);
3351   for (bound = loop->bounds; bound; bound = bound->next)
3352     {
3353       if (n_of_executions_at_most (at_stmt, bound, valid_niter))
3354         {
3355           fold_undefer_and_ignore_overflow_warnings ();
3356           return false;
3357         }
3358     }
3359
3360   fold_undefer_and_ignore_overflow_warnings ();
3361
3362   /* At this point we still don't have a proof that the iv does not
3363      overflow: give up.  */
3364   return true;
3365 }
3366
3367 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
3368
3369 void
3370 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3371 {
3372   struct nb_iter_bound *bound, *next;
3373
3374   loop->nb_iterations = NULL;
3375   loop->estimate_state = EST_NOT_COMPUTED;
3376   for (bound = loop->bounds; bound; bound = next)
3377     {
3378       next = bound->next;
3379       ggc_free (bound);
3380     }
3381
3382   loop->bounds = NULL;
3383 }
3384
3385 /* Frees the information on upper bounds on numbers of iterations of loops.  */
3386
3387 void
3388 free_numbers_of_iterations_estimates (void)
3389 {
3390   loop_iterator li;
3391   struct loop *loop;
3392
3393   FOR_EACH_LOOP (li, loop, 0)
3394     {
3395       free_numbers_of_iterations_estimates_loop (loop);
3396     }
3397 }
3398
3399 /* Substitute value VAL for ssa name NAME inside expressions held
3400    at LOOP.  */
3401
3402 void
3403 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3404 {
3405   loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
3406 }