OSDN Git Service

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