OSDN Git Service

a8e4737633d5fb97011af96b87fd6801f9ee76cc
[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 = int_const_binop (MULT_EXPR, rslt, x, 0);
121           x = int_const_binop (MULT_EXPR, x, x, 0);
122         }
123       rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
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 /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
1385    approximation of the number of iterations for LOOP.  */
1386
1387 static void
1388 compute_estimated_nb_iterations (struct loop *loop)
1389 {
1390   struct nb_iter_bound *bound;
1391   
1392   for (bound = loop->bounds; bound; bound = bound->next)
1393     if (TREE_CODE (bound->bound) == INTEGER_CST
1394         /* Update only when there is no previous estimation.  */
1395         && (chrec_contains_undetermined (loop->estimated_nb_iterations)
1396             /* Or when the current estimation is smaller.  */
1397             || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)))
1398       loop->estimated_nb_iterations = bound->bound;
1399 }
1400
1401 /* The following analyzers are extracting informations on the bounds
1402    of LOOP from the following undefined behaviors:
1403
1404    - data references should not access elements over the statically
1405      allocated size,
1406
1407    - signed variables should not overflow when flag_wrapv is not set.
1408 */
1409
1410 static void
1411 infer_loop_bounds_from_undefined (struct loop *loop)
1412 {
1413   unsigned i;
1414   basic_block bb, *bbs;
1415   block_stmt_iterator bsi;
1416   
1417   bbs = get_loop_body (loop);
1418
1419   for (i = 0; i < loop->num_nodes; i++)
1420     {
1421       bb = bbs[i];
1422
1423       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1424         {
1425           tree stmt = bsi_stmt (bsi);
1426
1427           switch (TREE_CODE (stmt))
1428             {
1429             case MODIFY_EXPR:
1430               {
1431                 tree op0 = TREE_OPERAND (stmt, 0);
1432                 tree op1 = TREE_OPERAND (stmt, 1);
1433
1434                 /* For each array access, analyze its access function
1435                    and record a bound on the loop iteration domain.  */
1436                 if (TREE_CODE (op1) == ARRAY_REF)
1437                   analyze_array (stmt, op1, true);
1438
1439                 if (TREE_CODE (op0) == ARRAY_REF)
1440                   analyze_array (stmt, op0, false);
1441
1442                 /* For each signed type variable in LOOP, analyze its
1443                    scalar evolution and record a bound of the loop
1444                    based on the type's ranges.  */
1445                 else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME)
1446                   {
1447                     tree init, step, diff, estimation;
1448                     tree scev = instantiate_parameters 
1449                       (loop, analyze_scalar_evolution (loop, op0));
1450                     tree type = chrec_type (scev);
1451                     tree utype;
1452
1453                     if (chrec_contains_undetermined (scev)
1454                         || TYPE_UNSIGNED (type))
1455                       break;
1456
1457                     init = initial_condition_in_loop_num (scev, loop->num);
1458                     step = evolution_part_in_loop_num (scev, loop->num);
1459
1460                     if (init == NULL_TREE
1461                         || step == NULL_TREE
1462                         || TREE_CODE (init) != INTEGER_CST
1463                         || TREE_CODE (step) != INTEGER_CST)
1464                       break;
1465
1466                     utype = unsigned_type_for (type);
1467                     if (tree_int_cst_lt (step, integer_zero_node))
1468                       diff = fold_build2 (MINUS_EXPR, utype, init,
1469                                           TYPE_MIN_VALUE (type));
1470                     else
1471                       diff = fold_build2 (MINUS_EXPR, utype,
1472                                           TYPE_MAX_VALUE (type), init);
1473
1474                     estimation = fold_build2 (CEIL_DIV_EXPR, utype, diff,
1475                                               step);
1476                     record_estimate (loop, estimation, boolean_true_node, stmt);
1477                   }
1478
1479                 break;
1480               }
1481
1482             case CALL_EXPR:
1483               {
1484                 tree args;
1485
1486                 for (args = TREE_OPERAND (stmt, 1); args;
1487                      args = TREE_CHAIN (args))
1488                   if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF)
1489                     analyze_array (stmt, TREE_VALUE (args), true);
1490
1491                 break;
1492               }
1493
1494             default:
1495               break;
1496             }
1497         }
1498
1499       if (chrec_contains_undetermined (loop->estimated_nb_iterations))
1500         compute_estimated_nb_iterations (loop);
1501     }
1502
1503   free (bbs);
1504 }
1505
1506 /* Records estimates on numbers of iterations of LOOP.  */
1507
1508 static void
1509 estimate_numbers_of_iterations_loop (struct loop *loop)
1510 {
1511   edge *exits;
1512   tree niter, type;
1513   unsigned i, n_exits;
1514   struct tree_niter_desc niter_desc;
1515
1516   /* Give up if we already have tried to compute an estimation.  */
1517   if (loop->estimated_nb_iterations == chrec_dont_know
1518       /* Or when we already have an estimation.  */
1519       || (loop->estimated_nb_iterations != NULL_TREE
1520           && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
1521     return;
1522   else
1523     loop->estimated_nb_iterations = chrec_dont_know;
1524
1525   exits = get_loop_exit_edges (loop, &n_exits);
1526   for (i = 0; i < n_exits; i++)
1527     {
1528       if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false))
1529         continue;
1530
1531       niter = niter_desc.niter;
1532       type = TREE_TYPE (niter);
1533       if (!zero_p (niter_desc.may_be_zero)
1534           && !nonzero_p (niter_desc.may_be_zero))
1535         niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
1536                         build_int_cst_type (type, 0),
1537                         niter);
1538       record_estimate (loop, niter,
1539                        niter_desc.additional_info,
1540                        last_stmt (exits[i]->src));
1541     }
1542   free (exits);
1543   
1544   if (chrec_contains_undetermined (loop->estimated_nb_iterations))
1545     infer_loop_bounds_from_undefined (loop);
1546 }
1547
1548 /* Records estimates on numbers of iterations of LOOPS.  */
1549
1550 void
1551 estimate_numbers_of_iterations (struct loops *loops)
1552 {
1553   unsigned i;
1554   struct loop *loop;
1555
1556   for (i = 1; i < loops->num; i++)
1557     {
1558       loop = loops->parray[i];
1559       if (loop)
1560         estimate_numbers_of_iterations_loop (loop);
1561     }
1562 }
1563
1564 /* If A > B, returns -1.  If A == B, returns 0.  If A < B, returns 1.
1565    If neither of these relations can be proved, returns 2.  */
1566
1567 static int
1568 compare_trees (tree a, tree b)
1569 {
1570   tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
1571   tree type;
1572
1573   if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
1574     type = typea;
1575   else
1576     type = typeb;
1577
1578   a = fold_convert (type, a);
1579   b = fold_convert (type, b);
1580
1581   if (nonzero_p (fold_binary (EQ_EXPR, boolean_type_node, a, b)))
1582     return 0;
1583   if (nonzero_p (fold_binary (LT_EXPR, boolean_type_node, a, b)))
1584     return 1;
1585   if (nonzero_p (fold_binary (GT_EXPR, boolean_type_node, a, b)))
1586     return -1;
1587
1588   return 2;
1589 }
1590
1591 /* Returns true if statement S1 dominates statement S2.  */
1592
1593 static bool
1594 stmt_dominates_stmt_p (tree s1, tree s2)
1595 {
1596   basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
1597
1598   if (!bb1
1599       || s1 == s2)
1600     return true;
1601
1602   if (bb1 == bb2)
1603     {
1604       block_stmt_iterator bsi;
1605
1606       for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
1607         if (bsi_stmt (bsi) == s1)
1608           return true;
1609
1610       return false;
1611     }
1612
1613   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
1614 }
1615
1616 /* Return true when it is possible to prove that the induction
1617    variable does not wrap: vary outside the type specified bounds.
1618    Checks whether BOUND < VALID_NITER that means in the context of iv
1619    conversion that all the iterations in the loop are safe: not
1620    producing wraps.
1621
1622    The statement NITER_BOUND->AT_STMT is executed at most
1623    NITER_BOUND->BOUND times in the loop.
1624    
1625    NITER_BOUND->ADDITIONAL is the additional condition recorded for
1626    operands of the bound.  This is useful in the following case,
1627    created by loop header copying:
1628
1629    i = 0;
1630    if (n > 0)
1631      do
1632        {
1633          something;
1634        } while (++i < n)
1635
1636    If the n > 0 condition is taken into account, the number of iterations of the
1637    loop can be expressed as n - 1.  If the type of n is signed, the ADDITIONAL
1638    assumption "n > 0" says us that the value of the number of iterations is at
1639    most MAX_TYPE - 1 (without this assumption, it might overflow).  */
1640
1641 static bool
1642 proved_non_wrapping_p (tree at_stmt,
1643                        struct nb_iter_bound *niter_bound, 
1644                        tree new_type,
1645                        tree valid_niter)
1646 {
1647   tree cond;
1648   tree bound = niter_bound->bound;
1649   enum tree_code cmp;
1650
1651   if (TYPE_PRECISION (new_type) > TYPE_PRECISION (TREE_TYPE (bound)))
1652     bound = fold_convert (unsigned_type_for (new_type), bound);
1653   else
1654     valid_niter = fold_convert (TREE_TYPE (bound), valid_niter);
1655
1656   /* Give up if BOUND was not folded to an INTEGER_CST, as in PR23434.  */
1657   if (TREE_CODE (bound) != INTEGER_CST)
1658     return false;
1659
1660   /* After the statement niter_bound->at_stmt we know that anything is
1661      executed at most BOUND times.  */
1662   if (at_stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, at_stmt))
1663     cmp = GE_EXPR;
1664   /* Before the statement niter_bound->at_stmt we know that anything
1665      is executed at most BOUND + 1 times.  */
1666   else
1667     cmp = GT_EXPR;
1668
1669   cond = fold_binary (cmp, boolean_type_node, valid_niter, bound);
1670   if (nonzero_p (cond))
1671     return true;
1672
1673   cond = build2 (cmp, boolean_type_node, valid_niter, bound);
1674   /* Try taking additional conditions into account.  */
1675   cond = fold_binary (TRUTH_OR_EXPR, boolean_type_node,
1676                       invert_truthvalue (niter_bound->additional),
1677                       cond);
1678
1679   if (nonzero_p (cond))
1680     return true;
1681
1682   return false;
1683 }
1684
1685 /* Checks whether it is correct to count the induction variable BASE +
1686    STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
1687    numbers of iterations of a LOOP.  If it is possible, return the
1688    value of step of the induction variable in the NEW_TYPE, otherwise
1689    return NULL_TREE.  */
1690
1691 static tree
1692 convert_step_widening (struct loop *loop, tree new_type, tree base, tree step,
1693                        tree at_stmt)
1694 {
1695   struct nb_iter_bound *bound;
1696   tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type;
1697   tree delta, step_abs;
1698   tree unsigned_type, valid_niter;
1699
1700   /* Compute the new step.  For example, {(uchar) 100, +, (uchar) 240}
1701      is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to
1702      keep the values of the induction variable unchanged: 100, 84, 68,
1703      ...
1704
1705      Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
1706      to {(uint)100, +, (uint)3}.  
1707
1708      Before returning the new step, verify that the number of
1709      iterations is less than DELTA / STEP_ABS (i.e. in the previous
1710      example (256 - 100) / 3) such that the iv does not wrap (in which
1711      case the operations are too difficult to be represented and
1712      handled: the values of the iv should be taken modulo 256 in the
1713      wider type; this is not implemented).  */
1714   base_in_new_type = fold_convert (new_type, base);
1715   base_plus_step_in_new_type = 
1716     fold_convert (new_type,
1717                   fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step));
1718   step_in_new_type = fold_build2 (MINUS_EXPR, new_type,
1719                                   base_plus_step_in_new_type,
1720                                   base_in_new_type);
1721
1722   if (TREE_CODE (step_in_new_type) != INTEGER_CST)
1723     return NULL_TREE;
1724
1725   switch (compare_trees (base_plus_step_in_new_type, base_in_new_type))
1726     {
1727     case -1:
1728       {
1729         tree extreme = upper_bound_in_type (new_type, TREE_TYPE (base));
1730         delta = fold_build2 (MINUS_EXPR, new_type, extreme,
1731                              base_in_new_type);
1732         step_abs = step_in_new_type;
1733         break;
1734       }
1735
1736     case 1:
1737       {
1738         tree extreme = lower_bound_in_type (new_type, TREE_TYPE (base));
1739         delta = fold_build2 (MINUS_EXPR, new_type, base_in_new_type,
1740                              extreme);
1741         step_abs = fold_build1 (NEGATE_EXPR, new_type, step_in_new_type);
1742         break;
1743       }
1744
1745     case 0:
1746       return step_in_new_type;
1747
1748     default:
1749       return NULL_TREE;
1750     }
1751
1752   unsigned_type = unsigned_type_for (new_type);
1753   delta = fold_convert (unsigned_type, delta);
1754   step_abs = fold_convert (unsigned_type, step_abs);
1755   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
1756                              delta, step_abs);
1757
1758   estimate_numbers_of_iterations_loop (loop);
1759   for (bound = loop->bounds; bound; bound = bound->next)
1760     if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter))
1761       return step_in_new_type;
1762
1763   /* Fail when the loop has no bound estimations, or when no bound can
1764      be used for verifying the conversion.  */
1765   return NULL_TREE;
1766 }
1767
1768 /* Returns true when VAR is used in pointer arithmetics.  DEPTH is
1769    used for limiting the search.  */
1770
1771 static bool
1772 used_in_pointer_arithmetic_p (tree var, int depth)
1773 {
1774   use_operand_p use_p;
1775   imm_use_iterator iter;
1776
1777   if (depth == 0
1778       || TREE_CODE (var) != SSA_NAME
1779       || !has_single_use (var))
1780     return false;
1781
1782   FOR_EACH_IMM_USE_FAST (use_p, iter, var)
1783     {
1784       tree stmt = USE_STMT (use_p);
1785
1786       if (stmt && TREE_CODE (stmt) == MODIFY_EXPR)
1787         {
1788           tree rhs = TREE_OPERAND (stmt, 1);
1789
1790           if (TREE_CODE (rhs) == NOP_EXPR
1791               || TREE_CODE (rhs) == CONVERT_EXPR)
1792             {
1793               if (POINTER_TYPE_P (TREE_TYPE (rhs)))
1794                 return true;
1795               return false;
1796             }
1797           else
1798             return used_in_pointer_arithmetic_p (TREE_OPERAND (stmt, 0),
1799                                                  depth - 1);
1800         }
1801     }
1802   return false;
1803 }
1804
1805 /* Return false only when the induction variable BASE + STEP * I is
1806    known to not overflow: i.e. when the number of iterations is small
1807    enough with respect to the step and initial condition in order to
1808    keep the evolution confined in TYPEs bounds.  Return true when the
1809    iv is known to overflow or when the property is not computable.
1810
1811    Initialize INIT_IS_MAX to true when the evolution goes from
1812    INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case.
1813    When this property cannot be determined, UNKNOWN_MAX is set to
1814    true.  */
1815
1816 bool
1817 scev_probably_wraps_p (tree type, tree base, tree step, 
1818                        tree at_stmt, struct loop *loop,
1819                        bool *init_is_max, bool *unknown_max)
1820 {
1821   struct nb_iter_bound *bound;
1822   tree delta, step_abs;
1823   tree unsigned_type, valid_niter;
1824   tree base_plus_step;
1825
1826   /* FIXME: The following code will not be used anymore once
1827      http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is
1828      committed.
1829
1830      If AT_STMT is a cast to unsigned that is later used for
1831      referencing a memory location, it is followed by a pointer
1832      conversion just after.  Because pointers do not wrap, the
1833      sequences that reference the memory do not wrap either.  In the
1834      following example, sequences corresponding to D_13 and to D_14
1835      can be proved to not wrap because they are used for computing a
1836      memory access:
1837          
1838        D.1621_13 = (long unsigned intD.4) D.1620_12;
1839        D.1622_14 = D.1621_13 * 8;
1840        D.1623_15 = (doubleD.29 *) D.1622_14;
1841   */
1842   if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
1843     {
1844       tree op0 = TREE_OPERAND (at_stmt, 0);
1845       tree op1 = TREE_OPERAND (at_stmt, 1);
1846       tree type_op1 = TREE_TYPE (op1);
1847
1848       if ((TYPE_UNSIGNED (type_op1)
1849            && used_in_pointer_arithmetic_p (op0, 2))
1850           || POINTER_TYPE_P (type_op1))
1851         {
1852           *unknown_max = true;
1853           return false;
1854         }
1855     }
1856
1857   if (TREE_CODE (base) == REAL_CST
1858       || TREE_CODE (step) == REAL_CST)
1859     {
1860       *unknown_max = true;
1861       return true;
1862     }
1863
1864   *unknown_max = false;
1865   base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
1866   switch (compare_trees (base_plus_step, base))
1867     {
1868     case -1:
1869       {
1870         tree extreme = upper_bound_in_type (type, TREE_TYPE (base));
1871         delta = fold_build2 (MINUS_EXPR, type, extreme, base);
1872         step_abs = step;
1873         *init_is_max = false;
1874         break;
1875       }
1876
1877     case 1:
1878       {
1879         tree extreme = lower_bound_in_type (type, TREE_TYPE (base));
1880         delta = fold_build2 (MINUS_EXPR, type, base, extreme);
1881         step_abs = fold_build1 (NEGATE_EXPR, type, step);
1882         *init_is_max = true;
1883         break;
1884       }
1885
1886     case 0:
1887       /* This means step is equal to 0.  This should not happen.  It
1888          could happen in convert step, but not here.  Safely answer
1889          don't know as in the default case.  */
1890
1891     default:
1892       *unknown_max = true;
1893       return true;
1894     }
1895
1896   /* If AT_STMT represents a cast operation, we may not be able to
1897      take advantage of the undefinedness of signed type evolutions.
1898
1899      implement-c.texi states: "For conversion to a type of width
1900      N, the value is reduced modulo 2^N to be within range of the
1901      type;"
1902
1903      See PR 21959 for a test case.  Essentially, given a cast
1904      operation
1905                 unsigned char uc;
1906                 signed char sc;
1907                 ...
1908                 sc = (signed char) uc;
1909                 if (sc < 0)
1910                   ...
1911
1912      where uc and sc have the scev {0, +, 1}, we would consider uc to
1913      wrap around, but not sc, because it is of a signed type.  This
1914      causes VRP to erroneously fold the predicate above because it
1915      thinks that sc cannot be negative.  */
1916   if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
1917     {
1918       tree rhs = TREE_OPERAND (at_stmt, 1);
1919       tree outer_t = TREE_TYPE (rhs);
1920
1921       if (!TYPE_UNSIGNED (outer_t)
1922           && (TREE_CODE (rhs) == NOP_EXPR || TREE_CODE (rhs) == CONVERT_EXPR))
1923         {
1924           tree inner_t = TREE_TYPE (TREE_OPERAND (rhs, 0));
1925
1926           /* If the inner type is unsigned and its size and/or
1927              precision are smaller to that of the outer type, then the
1928              expression may wrap around.  */
1929           if (TYPE_UNSIGNED (inner_t)
1930               && (TYPE_SIZE (inner_t) <= TYPE_SIZE (outer_t)
1931                   || TYPE_PRECISION (inner_t) <= TYPE_PRECISION (outer_t)))
1932             {
1933               *unknown_max = true;
1934               return true;
1935             }
1936         }
1937     }
1938
1939   /* After having set INIT_IS_MAX, we can return false: when not using
1940      wrapping arithmetic, signed types don't wrap.  */
1941   if (!flag_wrapv && !TYPE_UNSIGNED (type))
1942     return false;
1943
1944   unsigned_type = unsigned_type_for (type);
1945   delta = fold_convert (unsigned_type, delta);
1946   step_abs = fold_convert (unsigned_type, step_abs);
1947   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
1948
1949   estimate_numbers_of_iterations_loop (loop);
1950   for (bound = loop->bounds; bound; bound = bound->next)
1951     if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter))
1952       return false;
1953
1954   /* At this point we still don't have a proof that the iv does not
1955      overflow: give up.  */
1956   *unknown_max = true;
1957   return true;
1958 }
1959
1960 /* Return the conversion to NEW_TYPE of the STEP of an induction
1961    variable BASE + STEP * I at AT_STMT.  When it fails, return
1962    NULL_TREE.  */
1963
1964 tree
1965 convert_step (struct loop *loop, tree new_type, tree base, tree step,
1966               tree at_stmt)
1967 {
1968   tree base_type = TREE_TYPE (base);
1969
1970   /* When not using wrapping arithmetic, signed types don't wrap.  */
1971   if (!flag_wrapv && !TYPE_UNSIGNED (base_type))
1972     return fold_convert (new_type, step);
1973
1974   if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type))
1975     return convert_step_widening (loop, new_type, base, step, at_stmt);
1976
1977   return fold_convert (new_type, step);
1978 }
1979
1980 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
1981
1982 static void
1983 free_numbers_of_iterations_estimates_loop (struct loop *loop)
1984 {
1985   struct nb_iter_bound *bound, *next;
1986   
1987   for (bound = loop->bounds; bound; bound = next)
1988     {
1989       next = bound->next;
1990       free (bound);
1991     }
1992
1993   loop->bounds = NULL;
1994 }
1995
1996 /* Frees the information on upper bounds on numbers of iterations of LOOPS.  */
1997
1998 void
1999 free_numbers_of_iterations_estimates (struct loops *loops)
2000 {
2001   unsigned i;
2002   struct loop *loop;
2003
2004   for (i = 1; i < loops->num; i++)
2005     {
2006       loop = loops->parray[i];
2007       if (loop)
2008         free_numbers_of_iterations_estimates_loop (loop);
2009     }
2010 }
2011
2012 /* Substitute value VAL for ssa name NAME inside expressions held
2013    at LOOP.  */
2014
2015 void
2016 substitute_in_loop_info (struct loop *loop, tree name, tree val)
2017 {
2018   struct nb_iter_bound *bound;
2019
2020   loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
2021   loop->estimated_nb_iterations
2022           = simplify_replace_tree (loop->estimated_nb_iterations, name, val);
2023   for (bound = loop->bounds; bound; bound = bound->next)
2024     {
2025       bound->bound = simplify_replace_tree (bound->bound, name, val);
2026       bound->additional = simplify_replace_tree (bound->additional, name, val);
2027     }
2028 }