OSDN Git Service

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