OSDN Git Service

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