OSDN Git Service

PR tree-optimization/22236
[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 /* 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   /* After the statement niter_bound->at_stmt we know that anything is
1657      executed at most BOUND times.  */
1658   if (at_stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, at_stmt))
1659     cmp = GE_EXPR;
1660   /* Before the statement niter_bound->at_stmt we know that anything
1661      is executed at most BOUND + 1 times.  */
1662   else
1663     cmp = GT_EXPR;
1664
1665   cond = fold_binary (cmp, boolean_type_node, valid_niter, bound);
1666   if (nonzero_p (cond))
1667     return true;
1668
1669   cond = build2 (cmp, boolean_type_node, valid_niter, bound);
1670   /* Try taking additional conditions into account.  */
1671   cond = fold_binary (TRUTH_OR_EXPR, boolean_type_node,
1672                       invert_truthvalue (niter_bound->additional),
1673                       cond);
1674
1675   if (nonzero_p (cond))
1676     return true;
1677
1678   return false;
1679 }
1680
1681 /* Checks whether it is correct to count the induction variable BASE +
1682    STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
1683    numbers of iterations of a LOOP.  If it is possible, return the
1684    value of step of the induction variable in the NEW_TYPE, otherwise
1685    return NULL_TREE.  */
1686
1687 static tree
1688 convert_step_widening (struct loop *loop, tree new_type, tree base, tree step,
1689                        tree at_stmt)
1690 {
1691   struct nb_iter_bound *bound;
1692   tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type;
1693   tree delta, step_abs;
1694   tree unsigned_type, valid_niter;
1695
1696   /* Compute the new step.  For example, {(uchar) 100, +, (uchar) 240}
1697      is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to
1698      keep the values of the induction variable unchanged: 100, 84, 68,
1699      ...
1700
1701      Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
1702      to {(uint)100, +, (uint)3}.  
1703
1704      Before returning the new step, verify that the number of
1705      iterations is less than DELTA / STEP_ABS (i.e. in the previous
1706      example (256 - 100) / 3) such that the iv does not wrap (in which
1707      case the operations are too difficult to be represented and
1708      handled: the values of the iv should be taken modulo 256 in the
1709      wider type; this is not implemented).  */
1710   base_in_new_type = fold_convert (new_type, base);
1711   base_plus_step_in_new_type = 
1712     fold_convert (new_type,
1713                   fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step));
1714   step_in_new_type = fold_build2 (MINUS_EXPR, new_type,
1715                                   base_plus_step_in_new_type,
1716                                   base_in_new_type);
1717
1718   if (TREE_CODE (step_in_new_type) != INTEGER_CST)
1719     return NULL_TREE;
1720
1721   switch (compare_trees (base_plus_step_in_new_type, base_in_new_type))
1722     {
1723     case -1:
1724       {
1725         tree extreme = upper_bound_in_type (new_type, TREE_TYPE (base));
1726         delta = fold_build2 (MINUS_EXPR, new_type, extreme,
1727                              base_in_new_type);
1728         step_abs = step_in_new_type;
1729         break;
1730       }
1731
1732     case 1:
1733       {
1734         tree extreme = lower_bound_in_type (new_type, TREE_TYPE (base));
1735         delta = fold_build2 (MINUS_EXPR, new_type, base_in_new_type,
1736                              extreme);
1737         step_abs = fold_build1 (NEGATE_EXPR, new_type, step_in_new_type);
1738         break;
1739       }
1740
1741     case 0:
1742       return step_in_new_type;
1743
1744     default:
1745       return NULL_TREE;
1746     }
1747
1748   unsigned_type = unsigned_type_for (new_type);
1749   delta = fold_convert (unsigned_type, delta);
1750   step_abs = fold_convert (unsigned_type, step_abs);
1751   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
1752                              delta, step_abs);
1753
1754   estimate_numbers_of_iterations_loop (loop);
1755   for (bound = loop->bounds; bound; bound = bound->next)
1756     if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter))
1757       return step_in_new_type;
1758
1759   /* Fail when the loop has no bound estimations, or when no bound can
1760      be used for verifying the conversion.  */
1761   return NULL_TREE;
1762 }
1763
1764 /* Returns true when VAR is used in pointer arithmetics.  DEPTH is
1765    used for limiting the search.  */
1766
1767 static bool
1768 used_in_pointer_arithmetic_p (tree var, int depth)
1769 {
1770   use_operand_p use_p;
1771   imm_use_iterator iter;
1772
1773   if (depth == 0
1774       || TREE_CODE (var) != SSA_NAME
1775       || !has_single_use (var))
1776     return false;
1777
1778   FOR_EACH_IMM_USE_FAST (use_p, iter, var)
1779     {
1780       tree stmt = USE_STMT (use_p);
1781
1782       if (stmt && TREE_CODE (stmt) == MODIFY_EXPR)
1783         {
1784           tree rhs = TREE_OPERAND (stmt, 1);
1785
1786           if (TREE_CODE (rhs) == NOP_EXPR
1787               || TREE_CODE (rhs) == CONVERT_EXPR)
1788             {
1789               if (POINTER_TYPE_P (TREE_TYPE (rhs)))
1790                 return true;
1791               return false;
1792             }
1793           else
1794             return used_in_pointer_arithmetic_p (TREE_OPERAND (stmt, 0),
1795                                                  depth - 1);
1796         }
1797     }
1798   return false;
1799 }
1800
1801 /* Return false only when the induction variable BASE + STEP * I is
1802    known to not overflow: i.e. when the number of iterations is small
1803    enough with respect to the step and initial condition in order to
1804    keep the evolution confined in TYPEs bounds.  Return true when the
1805    iv is known to overflow or when the property is not computable.
1806
1807    Initialize INIT_IS_MAX to true when the evolution goes from
1808    INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case.
1809    When this property cannot be determined, UNKNOWN_MAX is set to
1810    true.  */
1811
1812 bool
1813 scev_probably_wraps_p (tree type, tree base, tree step, 
1814                        tree at_stmt, struct loop *loop,
1815                        bool *init_is_max, bool *unknown_max)
1816 {
1817   struct nb_iter_bound *bound;
1818   tree delta, step_abs;
1819   tree unsigned_type, valid_niter;
1820   tree base_plus_step;
1821
1822   /* FIXME: The following code will not be used anymore once
1823      http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is
1824      committed.
1825
1826      If AT_STMT is a cast to unsigned that is later used for
1827      referencing a memory location, it is followed by a pointer
1828      conversion just after.  Because pointers do not wrap, the
1829      sequences that reference the memory do not wrap either.  In the
1830      following example, sequences corresponding to D_13 and to D_14
1831      can be proved to not wrap because they are used for computing a
1832      memory access:
1833          
1834        D.1621_13 = (long unsigned intD.4) D.1620_12;
1835        D.1622_14 = D.1621_13 * 8;
1836        D.1623_15 = (doubleD.29 *) D.1622_14;
1837   */
1838   if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
1839     {
1840       tree op0 = TREE_OPERAND (at_stmt, 0);
1841       tree op1 = TREE_OPERAND (at_stmt, 1);
1842       tree type_op1 = TREE_TYPE (op1);
1843
1844       if ((TYPE_UNSIGNED (type_op1)
1845            && used_in_pointer_arithmetic_p (op0, 2))
1846           || POINTER_TYPE_P (type_op1))
1847         {
1848           *unknown_max = true;
1849           return false;
1850         }
1851     }
1852
1853   if (TREE_CODE (base) == REAL_CST
1854       || TREE_CODE (step) == REAL_CST)
1855     {
1856       *unknown_max = true;
1857       return true;
1858     }
1859
1860   *unknown_max = false;
1861   base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
1862   switch (compare_trees (base_plus_step, base))
1863     {
1864     case -1:
1865       {
1866         tree extreme = upper_bound_in_type (type, TREE_TYPE (base));
1867         delta = fold_build2 (MINUS_EXPR, type, extreme, base);
1868         step_abs = step;
1869         *init_is_max = false;
1870         break;
1871       }
1872
1873     case 1:
1874       {
1875         tree extreme = lower_bound_in_type (type, TREE_TYPE (base));
1876         delta = fold_build2 (MINUS_EXPR, type, base, extreme);
1877         step_abs = fold_build1 (NEGATE_EXPR, type, step);
1878         *init_is_max = true;
1879         break;
1880       }
1881
1882     case 0:
1883       /* This means step is equal to 0.  This should not happen.  It
1884          could happen in convert step, but not here.  Safely answer
1885          don't know as in the default case.  */
1886
1887     default:
1888       *unknown_max = true;
1889       return true;
1890     }
1891
1892   /* If AT_STMT represents a cast operation, we may not be able to
1893      take advantage of the undefinedness of signed type evolutions.
1894      See PR 21959 for a test case.  Essentially, given a cast
1895      operation
1896                 unsigned char i;
1897                 signed char i.0;
1898                 ...
1899                 i.0_6 = (signed char) i_2;
1900                 if (i.0_6 < 0)
1901                   ...
1902
1903      where i_2 and i.0_6 have the scev {0, +, 1}, we would consider
1904      i_2 to wrap around, but not i.0_6, because it is of a signed
1905      type.  This causes VRP to erroneously fold the predicate above
1906      because it thinks that i.0_6 cannot be negative.  */
1907   if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
1908     {
1909       tree rhs = TREE_OPERAND (at_stmt, 1);
1910       tree outer_t = TREE_TYPE (rhs);
1911
1912       if (!TYPE_UNSIGNED (outer_t)
1913           && (TREE_CODE (rhs) == NOP_EXPR || TREE_CODE (rhs) == CONVERT_EXPR))
1914         {
1915           tree inner_t = TREE_TYPE (TREE_OPERAND (rhs, 0));
1916
1917           /* If the inner type is unsigned and its size and/or
1918              precision are smaller to that of the outer type, then the
1919              expression may wrap around.  */
1920           if (TYPE_UNSIGNED (inner_t)
1921               && (TYPE_SIZE (inner_t) <= TYPE_SIZE (outer_t)
1922                   || TYPE_PRECISION (inner_t) <= TYPE_PRECISION (outer_t)))
1923             {
1924               *unknown_max = true;
1925               return true;
1926             }
1927         }
1928     }
1929
1930   /* After having set INIT_IS_MAX, we can return false: when not using
1931      wrapping arithmetic, signed types don't wrap.  */
1932   if (!flag_wrapv && !TYPE_UNSIGNED (type))
1933     return false;
1934
1935   unsigned_type = unsigned_type_for (type);
1936   delta = fold_convert (unsigned_type, delta);
1937   step_abs = fold_convert (unsigned_type, step_abs);
1938   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
1939
1940   estimate_numbers_of_iterations_loop (loop);
1941   for (bound = loop->bounds; bound; bound = bound->next)
1942     if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter))
1943       return false;
1944
1945   /* At this point we still don't have a proof that the iv does not
1946      overflow: give up.  */
1947   *unknown_max = true;
1948   return true;
1949 }
1950
1951 /* Return the conversion to NEW_TYPE of the STEP of an induction
1952    variable BASE + STEP * I at AT_STMT.  When it fails, return
1953    NULL_TREE.  */
1954
1955 tree
1956 convert_step (struct loop *loop, tree new_type, tree base, tree step,
1957               tree at_stmt)
1958 {
1959   tree base_type = TREE_TYPE (base);
1960
1961   /* When not using wrapping arithmetic, signed types don't wrap.  */
1962   if (!flag_wrapv && !TYPE_UNSIGNED (base_type))
1963     return fold_convert (new_type, step);
1964
1965   if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type))
1966     return convert_step_widening (loop, new_type, base, step, at_stmt);
1967
1968   return fold_convert (new_type, step);
1969 }
1970
1971 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
1972
1973 static void
1974 free_numbers_of_iterations_estimates_loop (struct loop *loop)
1975 {
1976   struct nb_iter_bound *bound, *next;
1977   
1978   for (bound = loop->bounds; bound; bound = next)
1979     {
1980       next = bound->next;
1981       free (bound);
1982     }
1983
1984   loop->bounds = NULL;
1985 }
1986
1987 /* Frees the information on upper bounds on numbers of iterations of LOOPS.  */
1988
1989 void
1990 free_numbers_of_iterations_estimates (struct loops *loops)
1991 {
1992   unsigned i;
1993   struct loop *loop;
1994
1995   for (i = 1; i < loops->num; i++)
1996     {
1997       loop = loops->parray[i];
1998       if (loop)
1999         free_numbers_of_iterations_estimates_loop (loop);
2000     }
2001 }
2002
2003 /* Substitute value VAL for ssa name NAME inside expressions held
2004    at LOOP.  */
2005
2006 void
2007 substitute_in_loop_info (struct loop *loop, tree name, tree val)
2008 {
2009   struct nb_iter_bound *bound;
2010
2011   loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
2012   loop->estimated_nb_iterations
2013           = simplify_replace_tree (loop->estimated_nb_iterations, name, val);
2014   for (bound = loop->bounds; bound; bound = bound->next)
2015     {
2016       bound->bound = simplify_replace_tree (bound->bound, name, val);
2017       bound->additional = simplify_replace_tree (bound->additional, name, val);
2018     }
2019 }