OSDN Git Service

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