OSDN Git Service

2005-11-04 Richard Guenther <rguenther@suse.de>
[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;
638
639   if (expr == NULL_TREE)
640     return expr;
641
642   if (is_gimple_min_invariant (expr))
643     return expr;
644
645   code = TREE_CODE (expr);
646   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
647     {
648       n = TREE_CODE_LENGTH (code);
649       for (i = 0; i < n; i++)
650         {
651           e = TREE_OPERAND (expr, i);
652           ee = expand_simple_operations (e);
653           if (e == ee)
654             continue;
655
656           if (!ret)
657             ret = copy_node (expr);
658
659           TREE_OPERAND (ret, i) = ee;
660         }
661
662       return (ret ? fold (ret) : expr);
663     }
664
665   if (TREE_CODE (expr) != SSA_NAME)
666     return expr;
667
668   stmt = SSA_NAME_DEF_STMT (expr);
669   if (TREE_CODE (stmt) != MODIFY_EXPR)
670     return expr;
671
672   e = TREE_OPERAND (stmt, 1);
673   if (/* Casts are simple.  */
674       TREE_CODE (e) != NOP_EXPR
675       && TREE_CODE (e) != CONVERT_EXPR
676       /* Copies are simple.  */
677       && TREE_CODE (e) != SSA_NAME
678       /* Assignments of invariants are simple.  */
679       && !is_gimple_min_invariant (e)
680       /* And increments and decrements by a constant are simple.  */
681       && !((TREE_CODE (e) == PLUS_EXPR
682             || TREE_CODE (e) == MINUS_EXPR)
683            && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
684     return expr;
685
686   return expand_simple_operations (e);
687 }
688
689 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
690    expression (or EXPR unchanged, if no simplification was possible).  */
691
692 static tree
693 tree_simplify_using_condition_1 (tree cond, tree expr)
694 {
695   bool changed;
696   tree e, te, e0, e1, e2, notcond;
697   enum tree_code code = TREE_CODE (expr);
698
699   if (code == INTEGER_CST)
700     return expr;
701
702   if (code == TRUTH_OR_EXPR
703       || code == TRUTH_AND_EXPR
704       || code == COND_EXPR)
705     {
706       changed = false;
707
708       e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
709       if (TREE_OPERAND (expr, 0) != e0)
710         changed = true;
711
712       e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
713       if (TREE_OPERAND (expr, 1) != e1)
714         changed = true;
715
716       if (code == COND_EXPR)
717         {
718           e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
719           if (TREE_OPERAND (expr, 2) != e2)
720             changed = true;
721         }
722       else
723         e2 = NULL_TREE;
724
725       if (changed)
726         {
727           if (code == COND_EXPR)
728             expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
729           else
730             expr = fold_build2 (code, boolean_type_node, e0, e1);
731         }
732
733       return expr;
734     }
735
736   /* In case COND is equality, we may be able to simplify EXPR by copy/constant
737      propagation, and vice versa.  Fold does not handle this, since it is
738      considered too expensive.  */
739   if (TREE_CODE (cond) == EQ_EXPR)
740     {
741       e0 = TREE_OPERAND (cond, 0);
742       e1 = TREE_OPERAND (cond, 1);
743
744       /* We know that e0 == e1.  Check whether we cannot simplify expr
745          using this fact.  */
746       e = simplify_replace_tree (expr, e0, e1);
747       if (zero_p (e) || nonzero_p (e))
748         return e;
749
750       e = simplify_replace_tree (expr, e1, e0);
751       if (zero_p (e) || nonzero_p (e))
752         return e;
753     }
754   if (TREE_CODE (expr) == EQ_EXPR)
755     {
756       e0 = TREE_OPERAND (expr, 0);
757       e1 = TREE_OPERAND (expr, 1);
758
759       /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true.  */
760       e = simplify_replace_tree (cond, e0, e1);
761       if (zero_p (e))
762         return e;
763       e = simplify_replace_tree (cond, e1, e0);
764       if (zero_p (e))
765         return e;
766     }
767   if (TREE_CODE (expr) == NE_EXPR)
768     {
769       e0 = TREE_OPERAND (expr, 0);
770       e1 = TREE_OPERAND (expr, 1);
771
772       /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true.  */
773       e = simplify_replace_tree (cond, e0, e1);
774       if (zero_p (e))
775         return boolean_true_node;
776       e = simplify_replace_tree (cond, e1, e0);
777       if (zero_p (e))
778         return boolean_true_node;
779     }
780
781   te = expand_simple_operations (expr);
782
783   /* Check whether COND ==> EXPR.  */
784   notcond = invert_truthvalue (cond);
785   e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
786   if (nonzero_p (e))
787     return e;
788
789   /* Check whether COND ==> not EXPR.  */
790   e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
791   if (e && zero_p (e))
792     return e;
793
794   return expr;
795 }
796
797 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
798    expression (or EXPR unchanged, if no simplification was possible).
799    Wrapper around tree_simplify_using_condition_1 that ensures that chains
800    of simple operations in definitions of ssa names in COND are expanded,
801    so that things like casts or incrementing the value of the bound before
802    the loop do not cause us to fail.  */
803
804 static tree
805 tree_simplify_using_condition (tree cond, tree expr)
806 {
807   cond = expand_simple_operations (cond);
808
809   return tree_simplify_using_condition_1 (cond, expr);
810 }
811      
812 /* Tries to simplify EXPR using the conditions on entry to LOOP.
813    Record the conditions used for simplification to CONDS_USED.
814    Returns the simplified expression (or EXPR unchanged, if no
815    simplification was possible).*/
816
817 static tree
818 simplify_using_initial_conditions (struct loop *loop, tree expr,
819                                    tree *conds_used)
820 {
821   edge e;
822   basic_block bb;
823   tree exp, cond;
824
825   if (TREE_CODE (expr) == INTEGER_CST)
826     return expr;
827
828   for (bb = loop->header;
829        bb != ENTRY_BLOCK_PTR;
830        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
831     {
832       if (!single_pred_p (bb))
833         continue;
834       e = single_pred_edge (bb);
835
836       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
837         continue;
838
839       cond = COND_EXPR_COND (last_stmt (e->src));
840       if (e->flags & EDGE_FALSE_VALUE)
841         cond = invert_truthvalue (cond);
842       exp = tree_simplify_using_condition (cond, expr);
843
844       if (exp != expr)
845         *conds_used = fold_build2 (TRUTH_AND_EXPR,
846                                    boolean_type_node,
847                                    *conds_used,
848                                    cond);
849
850       expr = exp;
851     }
852
853   return expr;
854 }
855
856 /* Tries to simplify EXPR using the evolutions of the loop invariants
857    in the superloops of LOOP.  Returns the simplified expression
858    (or EXPR unchanged, if no simplification was possible).  */
859
860 static tree
861 simplify_using_outer_evolutions (struct loop *loop, tree expr)
862 {
863   enum tree_code code = TREE_CODE (expr);
864   bool changed;
865   tree e, e0, e1, e2;
866
867   if (is_gimple_min_invariant (expr))
868     return expr;
869
870   if (code == TRUTH_OR_EXPR
871       || code == TRUTH_AND_EXPR
872       || code == COND_EXPR)
873     {
874       changed = false;
875
876       e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
877       if (TREE_OPERAND (expr, 0) != e0)
878         changed = true;
879
880       e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
881       if (TREE_OPERAND (expr, 1) != e1)
882         changed = true;
883
884       if (code == COND_EXPR)
885         {
886           e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
887           if (TREE_OPERAND (expr, 2) != e2)
888             changed = true;
889         }
890       else
891         e2 = NULL_TREE;
892
893       if (changed)
894         {
895           if (code == COND_EXPR)
896             expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
897           else
898             expr = fold_build2 (code, boolean_type_node, e0, e1);
899         }
900
901       return expr;
902     }
903
904   e = instantiate_parameters (loop, expr);
905   if (is_gimple_min_invariant (e))
906     return e;
907
908   return expr;
909 }
910
911 /* Stores description of number of iterations of LOOP derived from
912    EXIT (an exit edge of the LOOP) in NITER.  Returns true if some
913    useful information could be derived (and fields of NITER has
914    meaning described in comments at struct tree_niter_desc
915    declaration), false otherwise.  If WARN is true and
916    -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
917    potentially unsafe assumptions.  */
918
919 bool
920 number_of_iterations_exit (struct loop *loop, edge exit,
921                            struct tree_niter_desc *niter,
922                            bool warn)
923 {
924   tree stmt, cond, type;
925   tree op0, base0, step0;
926   tree op1, base1, step1;
927   enum tree_code code;
928
929   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
930     return false;
931
932   niter->assumptions = boolean_false_node;
933   stmt = last_stmt (exit->src);
934   if (!stmt || TREE_CODE (stmt) != COND_EXPR)
935     return false;
936
937   /* We want the condition for staying inside loop.  */
938   cond = COND_EXPR_COND (stmt);
939   if (exit->flags & EDGE_TRUE_VALUE)
940     cond = invert_truthvalue (cond);
941
942   code = TREE_CODE (cond);
943   switch (code)
944     {
945     case GT_EXPR:
946     case GE_EXPR:
947     case NE_EXPR:
948     case LT_EXPR:
949     case LE_EXPR:
950       break;
951
952     default:
953       return false;
954     }
955   
956   op0 = TREE_OPERAND (cond, 0);
957   op1 = TREE_OPERAND (cond, 1);
958   type = TREE_TYPE (op0);
959
960   if (TREE_CODE (type) != INTEGER_TYPE
961       && !POINTER_TYPE_P (type))
962     return false;
963      
964   if (!simple_iv (loop, stmt, op0, &base0, &step0, false))
965     return false;
966   if (!simple_iv (loop, stmt, op1, &base1, &step1, false))
967     return false;
968
969   niter->niter = NULL_TREE;
970
971   /* Handle common special cases first, so that we do not need to use
972      generic (and slow) analysis very often.  */
973   if (!number_of_iterations_special (type, base0, step0, code, base1, step1,
974                                      niter))
975     {
976
977       number_of_iterations_cond (type, base0, step0, code, base1, step1,
978                                  niter);
979
980       if (!niter->niter)
981         return false;
982     }
983
984   if (optimize >= 3)
985     {
986       niter->assumptions = simplify_using_outer_evolutions (loop,
987                                                             niter->assumptions);
988       niter->may_be_zero = simplify_using_outer_evolutions (loop,
989                                                             niter->may_be_zero);
990       niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
991     }
992
993   niter->additional_info = boolean_true_node;
994   niter->assumptions
995           = simplify_using_initial_conditions (loop,
996                                                niter->assumptions,
997                                                &niter->additional_info);
998   niter->may_be_zero
999           = simplify_using_initial_conditions (loop,
1000                                                niter->may_be_zero,
1001                                                &niter->additional_info);
1002
1003   if (integer_onep (niter->assumptions))
1004     return true;
1005
1006   /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1007      But if we can prove that there is overflow or some other source of weird
1008      behavior, ignore the loop even with -funsafe-loop-optimizations.  */
1009   if (integer_zerop (niter->assumptions))
1010     return false;
1011
1012   if (flag_unsafe_loop_optimizations)
1013     niter->assumptions = boolean_true_node;
1014
1015   if (warn)
1016     {
1017       const char *wording;
1018       location_t loc = EXPR_LOCATION (stmt);
1019   
1020       /* We can provide a more specific warning if one of the operator is
1021          constant and the other advances by +1 or -1.  */
1022       if (step1 ? !step0 && (integer_onep (step1) || integer_all_onesp (step1))
1023                 : step0 && (integer_onep (step0) || integer_all_onesp (step0)))
1024         wording =
1025           flag_unsafe_loop_optimizations
1026           ? N_("assuming that the loop is not infinite")
1027           : N_("cannot optimize possibly infinite loops");
1028       else
1029         wording = 
1030           flag_unsafe_loop_optimizations
1031           ? N_("assuming that the loop counter does not overflow")
1032           : N_("cannot optimize loop, the loop counter may overflow");
1033
1034       if (LOCATION_LINE (loc) > 0)
1035         warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
1036       else
1037         warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1038     }
1039
1040   return flag_unsafe_loop_optimizations;
1041 }
1042
1043 /* Try to determine the number of iterations of LOOP.  If we succeed,
1044    expression giving number of iterations is returned and *EXIT is
1045    set to the edge from that the information is obtained.  Otherwise
1046    chrec_dont_know is returned.  */
1047
1048 tree
1049 find_loop_niter (struct loop *loop, edge *exit)
1050 {
1051   unsigned n_exits, i;
1052   edge *exits = get_loop_exit_edges (loop, &n_exits);
1053   edge ex;
1054   tree niter = NULL_TREE, aniter;
1055   struct tree_niter_desc desc;
1056
1057   *exit = NULL;
1058   for (i = 0; i < n_exits; i++)
1059     {
1060       ex = exits[i];
1061       if (!just_once_each_iteration_p (loop, ex->src))
1062         continue;
1063
1064       if (!number_of_iterations_exit (loop, ex, &desc, false))
1065         continue;
1066
1067       if (nonzero_p (desc.may_be_zero))
1068         {
1069           /* We exit in the first iteration through this exit.
1070              We won't find anything better.  */
1071           niter = build_int_cst_type (unsigned_type_node, 0);
1072           *exit = ex;
1073           break;
1074         }
1075
1076       if (!zero_p (desc.may_be_zero))
1077         continue;
1078
1079       aniter = desc.niter;
1080
1081       if (!niter)
1082         {
1083           /* Nothing recorded yet.  */
1084           niter = aniter;
1085           *exit = ex;
1086           continue;
1087         }
1088
1089       /* Prefer constants, the lower the better.  */
1090       if (TREE_CODE (aniter) != INTEGER_CST)
1091         continue;
1092
1093       if (TREE_CODE (niter) != INTEGER_CST)
1094         {
1095           niter = aniter;
1096           *exit = ex;
1097           continue;
1098         }
1099
1100       if (tree_int_cst_lt (aniter, niter))
1101         {
1102           niter = aniter;
1103           *exit = ex;
1104           continue;
1105         }
1106     }
1107   free (exits);
1108
1109   return niter ? niter : chrec_dont_know;
1110 }
1111
1112 /*
1113
1114    Analysis of a number of iterations of a loop by a brute-force evaluation.
1115
1116 */
1117
1118 /* Bound on the number of iterations we try to evaluate.  */
1119
1120 #define MAX_ITERATIONS_TO_TRACK \
1121   ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1122
1123 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1124    result by a chain of operations such that all but exactly one of their
1125    operands are constants.  */
1126
1127 static tree
1128 chain_of_csts_start (struct loop *loop, tree x)
1129 {
1130   tree stmt = SSA_NAME_DEF_STMT (x);
1131   tree use;
1132   basic_block bb = bb_for_stmt (stmt);
1133
1134   if (!bb
1135       || !flow_bb_inside_loop_p (loop, bb))
1136     return NULL_TREE;
1137   
1138   if (TREE_CODE (stmt) == PHI_NODE)
1139     {
1140       if (bb == loop->header)
1141         return stmt;
1142
1143       return NULL_TREE;
1144     }
1145
1146   if (TREE_CODE (stmt) != MODIFY_EXPR)
1147     return NULL_TREE;
1148
1149   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1150     return NULL_TREE;
1151   if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
1152     return NULL_TREE;
1153
1154   use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1155   if (use == NULL_USE_OPERAND_P)
1156     return NULL_TREE;
1157
1158   return chain_of_csts_start (loop, use);
1159 }
1160
1161 /* Determines whether the expression X is derived from a result of a phi node
1162    in header of LOOP such that
1163
1164    * the derivation of X consists only from operations with constants
1165    * the initial value of the phi node is constant
1166    * the value of the phi node in the next iteration can be derived from the
1167      value in the current iteration by a chain of operations with constants.
1168    
1169    If such phi node exists, it is returned.  If X is a constant, X is returned
1170    unchanged.  Otherwise NULL_TREE is returned.  */
1171
1172 static tree
1173 get_base_for (struct loop *loop, tree x)
1174 {
1175   tree phi, init, next;
1176
1177   if (is_gimple_min_invariant (x))
1178     return x;
1179
1180   phi = chain_of_csts_start (loop, x);
1181   if (!phi)
1182     return NULL_TREE;
1183
1184   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1185   next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1186
1187   if (TREE_CODE (next) != SSA_NAME)
1188     return NULL_TREE;
1189
1190   if (!is_gimple_min_invariant (init))
1191     return NULL_TREE;
1192
1193   if (chain_of_csts_start (loop, next) != phi)
1194     return NULL_TREE;
1195
1196   return phi;
1197 }
1198
1199 /* Given an expression X, then 
1200  
1201    * if BASE is NULL_TREE, X must be a constant and we return X.
1202    * otherwise X is a SSA name, whose value in the considered loop is derived
1203      by a chain of operations with constant from a result of a phi node in
1204      the header of the loop.  Then we return value of X when the value of the
1205      result of this phi node is given by the constant BASE.  */
1206
1207 static tree
1208 get_val_for (tree x, tree base)
1209 {
1210   tree stmt, nx, val;
1211   use_operand_p op;
1212   ssa_op_iter iter;
1213
1214   if (!x)
1215     return base;
1216
1217   stmt = SSA_NAME_DEF_STMT (x);
1218   if (TREE_CODE (stmt) == PHI_NODE)
1219     return base;
1220
1221   FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
1222     {
1223       nx = USE_FROM_PTR (op);
1224       val = get_val_for (nx, base);
1225       SET_USE (op, val);
1226       val = fold (TREE_OPERAND (stmt, 1));
1227       SET_USE (op, nx);
1228       /* only iterate loop once.  */
1229       return val;
1230     }
1231
1232   /* Should never reach here.  */
1233   gcc_unreachable();
1234 }
1235
1236 /* Tries to count the number of iterations of LOOP till it exits by EXIT
1237    by brute force -- i.e. by determining the value of the operands of the
1238    condition at EXIT in first few iterations of the loop (assuming that
1239    these values are constant) and determining the first one in that the
1240    condition is not satisfied.  Returns the constant giving the number
1241    of the iterations of LOOP if successful, chrec_dont_know otherwise.  */
1242
1243 tree
1244 loop_niter_by_eval (struct loop *loop, edge exit)
1245 {
1246   tree cond, cnd, acnd;
1247   tree op[2], val[2], next[2], aval[2], phi[2];
1248   unsigned i, j;
1249   enum tree_code cmp;
1250
1251   cond = last_stmt (exit->src);
1252   if (!cond || TREE_CODE (cond) != COND_EXPR)
1253     return chrec_dont_know;
1254
1255   cnd = COND_EXPR_COND (cond);
1256   if (exit->flags & EDGE_TRUE_VALUE)
1257     cnd = invert_truthvalue (cnd);
1258
1259   cmp = TREE_CODE (cnd);
1260   switch (cmp)
1261     {
1262     case EQ_EXPR:
1263     case NE_EXPR:
1264     case GT_EXPR:
1265     case GE_EXPR:
1266     case LT_EXPR:
1267     case LE_EXPR:
1268       for (j = 0; j < 2; j++)
1269         op[j] = TREE_OPERAND (cnd, j);
1270       break;
1271
1272     default:
1273       return chrec_dont_know;
1274     }
1275
1276   for (j = 0; j < 2; j++)
1277     {
1278       phi[j] = get_base_for (loop, op[j]);
1279       if (!phi[j])
1280         return chrec_dont_know;
1281     }
1282
1283   for (j = 0; j < 2; j++)
1284     {
1285       if (TREE_CODE (phi[j]) == PHI_NODE)
1286         {
1287           val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
1288           next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
1289         }
1290       else
1291         {
1292           val[j] = phi[j];
1293           next[j] = NULL_TREE;
1294           op[j] = NULL_TREE;
1295         }
1296     }
1297
1298   for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
1299     {
1300       for (j = 0; j < 2; j++)
1301         aval[j] = get_val_for (op[j], val[j]);
1302
1303       acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
1304       if (acnd && zero_p (acnd))
1305         {
1306           if (dump_file && (dump_flags & TDF_DETAILS))
1307             fprintf (dump_file,
1308                      "Proved that loop %d iterates %d times using brute force.\n",
1309                      loop->num, i);
1310           return build_int_cst (unsigned_type_node, i);
1311         }
1312
1313       for (j = 0; j < 2; j++)
1314         val[j] = get_val_for (next[j], val[j]);
1315     }
1316
1317   return chrec_dont_know;
1318 }
1319
1320 /* Finds the exit of the LOOP by that the loop exits after a constant
1321    number of iterations and stores the exit edge to *EXIT.  The constant
1322    giving the number of iterations of LOOP is returned.  The number of
1323    iterations is determined using loop_niter_by_eval (i.e. by brute force
1324    evaluation).  If we are unable to find the exit for that loop_niter_by_eval
1325    determines the number of iterations, chrec_dont_know is returned.  */
1326
1327 tree
1328 find_loop_niter_by_eval (struct loop *loop, edge *exit)
1329 {
1330   unsigned n_exits, i;
1331   edge *exits = get_loop_exit_edges (loop, &n_exits);
1332   edge ex;
1333   tree niter = NULL_TREE, aniter;
1334
1335   *exit = NULL;
1336   for (i = 0; i < n_exits; i++)
1337     {
1338       ex = exits[i];
1339       if (!just_once_each_iteration_p (loop, ex->src))
1340         continue;
1341
1342       aniter = loop_niter_by_eval (loop, ex);
1343       if (chrec_contains_undetermined (aniter))
1344         continue;
1345
1346       if (niter
1347           && !tree_int_cst_lt (aniter, niter))
1348         continue;
1349
1350       niter = aniter;
1351       *exit = ex;
1352     }
1353   free (exits);
1354
1355   return niter ? niter : chrec_dont_know;
1356 }
1357
1358 /*
1359
1360    Analysis of upper bounds on number of iterations of a loop.
1361
1362 */
1363
1364 /* Records that AT_STMT is executed at most BOUND times in LOOP.  The
1365    additional condition ADDITIONAL is recorded with the bound.  */
1366
1367 void
1368 record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
1369 {
1370   struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
1371
1372   if (dump_file && (dump_flags & TDF_DETAILS))
1373     {
1374       fprintf (dump_file, "Statements after ");
1375       print_generic_expr (dump_file, at_stmt, TDF_SLIM);
1376       fprintf (dump_file, " are executed at most ");
1377       print_generic_expr (dump_file, bound, TDF_SLIM);
1378       fprintf (dump_file, " times in loop %d.\n", loop->num);
1379     }
1380
1381   elt->bound = bound;
1382   elt->at_stmt = at_stmt;
1383   elt->additional = additional;
1384   elt->next = loop->bounds;
1385   loop->bounds = elt;
1386 }
1387
1388 /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
1389    approximation of the number of iterations for LOOP.  */
1390
1391 static void
1392 compute_estimated_nb_iterations (struct loop *loop)
1393 {
1394   struct nb_iter_bound *bound;
1395   
1396   for (bound = loop->bounds; bound; bound = bound->next)
1397     if (TREE_CODE (bound->bound) == INTEGER_CST
1398         /* Update only when there is no previous estimation.  */
1399         && (chrec_contains_undetermined (loop->estimated_nb_iterations)
1400             /* Or when the current estimation is smaller.  */
1401             || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)))
1402       loop->estimated_nb_iterations = bound->bound;
1403 }
1404
1405 /* The following analyzers are extracting informations on the bounds
1406    of LOOP from the following undefined behaviors:
1407
1408    - data references should not access elements over the statically
1409      allocated size,
1410
1411    - signed variables should not overflow when flag_wrapv is not set.
1412 */
1413
1414 static void
1415 infer_loop_bounds_from_undefined (struct loop *loop)
1416 {
1417   unsigned i;
1418   basic_block bb, *bbs;
1419   block_stmt_iterator bsi;
1420   
1421   bbs = get_loop_body (loop);
1422
1423   for (i = 0; i < loop->num_nodes; i++)
1424     {
1425       bb = bbs[i];
1426
1427       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1428         {
1429           tree stmt = bsi_stmt (bsi);
1430
1431           switch (TREE_CODE (stmt))
1432             {
1433             case MODIFY_EXPR:
1434               {
1435                 tree op0 = TREE_OPERAND (stmt, 0);
1436                 tree op1 = TREE_OPERAND (stmt, 1);
1437
1438                 /* For each array access, analyze its access function
1439                    and record a bound on the loop iteration domain.  */
1440                 if (TREE_CODE (op1) == ARRAY_REF 
1441                     && !array_ref_contains_indirect_ref (op1))
1442                   estimate_iters_using_array (stmt, op1);
1443
1444                 if (TREE_CODE (op0) == ARRAY_REF 
1445                     && !array_ref_contains_indirect_ref (op0))
1446                   estimate_iters_using_array (stmt, op0);
1447
1448                 /* For each signed type variable in LOOP, analyze its
1449                    scalar evolution and record a bound of the loop
1450                    based on the type's ranges.  */
1451                 else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME)
1452                   {
1453                     tree init, step, diff, estimation;
1454                     tree scev = instantiate_parameters 
1455                       (loop, analyze_scalar_evolution (loop, op0));
1456                     tree type = chrec_type (scev);
1457                     tree utype;
1458
1459                     if (chrec_contains_undetermined (scev)
1460                         || TYPE_UNSIGNED (type))
1461                       break;
1462
1463                     init = initial_condition_in_loop_num (scev, loop->num);
1464                     step = evolution_part_in_loop_num (scev, loop->num);
1465
1466                     if (init == NULL_TREE
1467                         || step == NULL_TREE
1468                         || TREE_CODE (init) != INTEGER_CST
1469                         || TREE_CODE (step) != INTEGER_CST
1470                         || TYPE_MIN_VALUE (type) == NULL_TREE
1471                         || TYPE_MAX_VALUE (type) == NULL_TREE)
1472                       break;
1473
1474                     utype = unsigned_type_for (type);
1475                     if (tree_int_cst_lt (step, integer_zero_node))
1476                       diff = fold_build2 (MINUS_EXPR, utype, init,
1477                                           TYPE_MIN_VALUE (type));
1478                     else
1479                       diff = fold_build2 (MINUS_EXPR, utype,
1480                                           TYPE_MAX_VALUE (type), init);
1481
1482                     estimation = fold_build2 (CEIL_DIV_EXPR, utype, diff,
1483                                               step);
1484                     record_estimate (loop, estimation, boolean_true_node, stmt);
1485                   }
1486
1487                 break;
1488               }
1489
1490             case CALL_EXPR:
1491               {
1492                 tree args;
1493
1494                 for (args = TREE_OPERAND (stmt, 1); args;
1495                      args = TREE_CHAIN (args))
1496                   if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
1497                       && !array_ref_contains_indirect_ref (TREE_VALUE (args)))
1498                     estimate_iters_using_array (stmt, TREE_VALUE (args));
1499
1500                 break;
1501               }
1502
1503             default:
1504               break;
1505             }
1506         }
1507
1508       if (chrec_contains_undetermined (loop->estimated_nb_iterations))
1509         compute_estimated_nb_iterations (loop);
1510     }
1511
1512   free (bbs);
1513 }
1514
1515 /* Records estimates on numbers of iterations of LOOP.  */
1516
1517 static void
1518 estimate_numbers_of_iterations_loop (struct loop *loop)
1519 {
1520   edge *exits;
1521   tree niter, type;
1522   unsigned i, n_exits;
1523   struct tree_niter_desc niter_desc;
1524
1525   /* Give up if we already have tried to compute an estimation.  */
1526   if (loop->estimated_nb_iterations == chrec_dont_know
1527       /* Or when we already have an estimation.  */
1528       || (loop->estimated_nb_iterations != NULL_TREE
1529           && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
1530     return;
1531   else
1532     loop->estimated_nb_iterations = chrec_dont_know;
1533
1534   exits = get_loop_exit_edges (loop, &n_exits);
1535   for (i = 0; i < n_exits; i++)
1536     {
1537       if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false))
1538         continue;
1539
1540       niter = niter_desc.niter;
1541       type = TREE_TYPE (niter);
1542       if (!zero_p (niter_desc.may_be_zero)
1543           && !nonzero_p (niter_desc.may_be_zero))
1544         niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
1545                         build_int_cst_type (type, 0),
1546                         niter);
1547       record_estimate (loop, niter,
1548                        niter_desc.additional_info,
1549                        last_stmt (exits[i]->src));
1550     }
1551   free (exits);
1552   
1553   if (chrec_contains_undetermined (loop->estimated_nb_iterations))
1554     infer_loop_bounds_from_undefined (loop);
1555 }
1556
1557 /* Records estimates on numbers of iterations of LOOPS.  */
1558
1559 void
1560 estimate_numbers_of_iterations (struct loops *loops)
1561 {
1562   unsigned i;
1563   struct loop *loop;
1564
1565   for (i = 1; i < loops->num; i++)
1566     {
1567       loop = loops->parray[i];
1568       if (loop)
1569         estimate_numbers_of_iterations_loop (loop);
1570     }
1571 }
1572
1573 /* If A > B, returns -1.  If A == B, returns 0.  If A < B, returns 1.
1574    If neither of these relations can be proved, returns 2.  */
1575
1576 static int
1577 compare_trees (tree a, tree b)
1578 {
1579   tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
1580   tree type;
1581
1582   if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
1583     type = typea;
1584   else
1585     type = typeb;
1586
1587   a = fold_convert (type, a);
1588   b = fold_convert (type, b);
1589
1590   if (nonzero_p (fold_binary (EQ_EXPR, boolean_type_node, a, b)))
1591     return 0;
1592   if (nonzero_p (fold_binary (LT_EXPR, boolean_type_node, a, b)))
1593     return 1;
1594   if (nonzero_p (fold_binary (GT_EXPR, boolean_type_node, a, b)))
1595     return -1;
1596
1597   return 2;
1598 }
1599
1600 /* Returns true if statement S1 dominates statement S2.  */
1601
1602 static bool
1603 stmt_dominates_stmt_p (tree s1, tree s2)
1604 {
1605   basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
1606
1607   if (!bb1
1608       || s1 == s2)
1609     return true;
1610
1611   if (bb1 == bb2)
1612     {
1613       block_stmt_iterator bsi;
1614
1615       for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
1616         if (bsi_stmt (bsi) == s1)
1617           return true;
1618
1619       return false;
1620     }
1621
1622   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
1623 }
1624
1625 /* Return true when it is possible to prove that the induction
1626    variable does not wrap: vary outside the type specified bounds.
1627    Checks whether BOUND < VALID_NITER that means in the context of iv
1628    conversion that all the iterations in the loop are safe: not
1629    producing wraps.
1630
1631    The statement NITER_BOUND->AT_STMT is executed at most
1632    NITER_BOUND->BOUND times in the loop.
1633    
1634    NITER_BOUND->ADDITIONAL is the additional condition recorded for
1635    operands of the bound.  This is useful in the following case,
1636    created by loop header copying:
1637
1638    i = 0;
1639    if (n > 0)
1640      do
1641        {
1642          something;
1643        } while (++i < n)
1644
1645    If the n > 0 condition is taken into account, the number of iterations of the
1646    loop can be expressed as n - 1.  If the type of n is signed, the ADDITIONAL
1647    assumption "n > 0" says us that the value of the number of iterations is at
1648    most MAX_TYPE - 1 (without this assumption, it might overflow).  */
1649
1650 static bool
1651 proved_non_wrapping_p (tree at_stmt,
1652                        struct nb_iter_bound *niter_bound, 
1653                        tree new_type,
1654                        tree valid_niter)
1655 {
1656   tree cond;
1657   tree bound = niter_bound->bound;
1658   enum tree_code cmp;
1659
1660   if (TYPE_PRECISION (new_type) > TYPE_PRECISION (TREE_TYPE (bound)))
1661     bound = fold_convert (unsigned_type_for (new_type), bound);
1662   else
1663     valid_niter = fold_convert (TREE_TYPE (bound), valid_niter);
1664
1665   /* Give up if BOUND was not folded to an INTEGER_CST, as in PR23434.  */
1666   if (TREE_CODE (bound) != INTEGER_CST)
1667     return false;
1668
1669   /* After the statement niter_bound->at_stmt we know that anything is
1670      executed at most BOUND times.  */
1671   if (at_stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, at_stmt))
1672     cmp = GE_EXPR;
1673   /* Before the statement niter_bound->at_stmt we know that anything
1674      is executed at most BOUND + 1 times.  */
1675   else
1676     cmp = GT_EXPR;
1677
1678   cond = fold_binary (cmp, boolean_type_node, valid_niter, bound);
1679   if (nonzero_p (cond))
1680     return true;
1681
1682   cond = build2 (cmp, boolean_type_node, valid_niter, bound);
1683   /* Try taking additional conditions into account.  */
1684   cond = fold_binary (TRUTH_OR_EXPR, boolean_type_node,
1685                       invert_truthvalue (niter_bound->additional),
1686                       cond);
1687
1688   if (nonzero_p (cond))
1689     return true;
1690
1691   return false;
1692 }
1693
1694 /* Checks whether it is correct to count the induction variable BASE +
1695    STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
1696    numbers of iterations of a LOOP.  If it is possible, return the
1697    value of step of the induction variable in the NEW_TYPE, otherwise
1698    return NULL_TREE.  */
1699
1700 static tree
1701 convert_step_widening (struct loop *loop, tree new_type, tree base, tree step,
1702                        tree at_stmt)
1703 {
1704   struct nb_iter_bound *bound;
1705   tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type;
1706   tree delta, step_abs;
1707   tree unsigned_type, valid_niter;
1708
1709   /* Compute the new step.  For example, {(uchar) 100, +, (uchar) 240}
1710      is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to
1711      keep the values of the induction variable unchanged: 100, 84, 68,
1712      ...
1713
1714      Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
1715      to {(uint)100, +, (uint)3}.  
1716
1717      Before returning the new step, verify that the number of
1718      iterations is less than DELTA / STEP_ABS (i.e. in the previous
1719      example (256 - 100) / 3) such that the iv does not wrap (in which
1720      case the operations are too difficult to be represented and
1721      handled: the values of the iv should be taken modulo 256 in the
1722      wider type; this is not implemented).  */
1723   base_in_new_type = fold_convert (new_type, base);
1724   base_plus_step_in_new_type = 
1725     fold_convert (new_type,
1726                   fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step));
1727   step_in_new_type = fold_build2 (MINUS_EXPR, new_type,
1728                                   base_plus_step_in_new_type,
1729                                   base_in_new_type);
1730
1731   if (TREE_CODE (step_in_new_type) != INTEGER_CST)
1732     return NULL_TREE;
1733
1734   switch (compare_trees (base_plus_step_in_new_type, base_in_new_type))
1735     {
1736     case -1:
1737       {
1738         tree extreme = upper_bound_in_type (new_type, TREE_TYPE (base));
1739         delta = fold_build2 (MINUS_EXPR, new_type, extreme,
1740                              base_in_new_type);
1741         step_abs = step_in_new_type;
1742         break;
1743       }
1744
1745     case 1:
1746       {
1747         tree extreme = lower_bound_in_type (new_type, TREE_TYPE (base));
1748         delta = fold_build2 (MINUS_EXPR, new_type, base_in_new_type,
1749                              extreme);
1750         step_abs = fold_build1 (NEGATE_EXPR, new_type, step_in_new_type);
1751         break;
1752       }
1753
1754     case 0:
1755       return step_in_new_type;
1756
1757     default:
1758       return NULL_TREE;
1759     }
1760
1761   unsigned_type = unsigned_type_for (new_type);
1762   delta = fold_convert (unsigned_type, delta);
1763   step_abs = fold_convert (unsigned_type, step_abs);
1764   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
1765                              delta, step_abs);
1766
1767   estimate_numbers_of_iterations_loop (loop);
1768   for (bound = loop->bounds; bound; bound = bound->next)
1769     if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter))
1770       return step_in_new_type;
1771
1772   /* Fail when the loop has no bound estimations, or when no bound can
1773      be used for verifying the conversion.  */
1774   return NULL_TREE;
1775 }
1776
1777 /* Returns true when VAR is used in pointer arithmetics.  DEPTH is
1778    used for limiting the search.  */
1779
1780 static bool
1781 used_in_pointer_arithmetic_p (tree var, int depth)
1782 {
1783   use_operand_p use_p;
1784   imm_use_iterator iter;
1785
1786   if (depth == 0
1787       || TREE_CODE (var) != SSA_NAME
1788       || !has_single_use (var))
1789     return false;
1790
1791   FOR_EACH_IMM_USE_FAST (use_p, iter, var)
1792     {
1793       tree stmt = USE_STMT (use_p);
1794
1795       if (stmt && TREE_CODE (stmt) == MODIFY_EXPR)
1796         {
1797           tree rhs = TREE_OPERAND (stmt, 1);
1798
1799           if (TREE_CODE (rhs) == NOP_EXPR
1800               || TREE_CODE (rhs) == CONVERT_EXPR)
1801             {
1802               if (POINTER_TYPE_P (TREE_TYPE (rhs)))
1803                 return true;
1804               return false;
1805             }
1806           else
1807             return used_in_pointer_arithmetic_p (TREE_OPERAND (stmt, 0),
1808                                                  depth - 1);
1809         }
1810     }
1811   return false;
1812 }
1813
1814 /* Return false only when the induction variable BASE + STEP * I is
1815    known to not overflow: i.e. when the number of iterations is small
1816    enough with respect to the step and initial condition in order to
1817    keep the evolution confined in TYPEs bounds.  Return true when the
1818    iv is known to overflow or when the property is not computable.
1819
1820    Initialize INIT_IS_MAX to true when the evolution goes from
1821    INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case.
1822    When this property cannot be determined, UNKNOWN_MAX is set to
1823    true.  */
1824
1825 bool
1826 scev_probably_wraps_p (tree type, tree base, tree step, 
1827                        tree at_stmt, struct loop *loop,
1828                        bool *init_is_max, bool *unknown_max)
1829 {
1830   struct nb_iter_bound *bound;
1831   tree delta, step_abs;
1832   tree unsigned_type, valid_niter;
1833   tree base_plus_step, bpsps;
1834   int cps, cpsps;
1835
1836   /* FIXME: The following code will not be used anymore once
1837      http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is
1838      committed.
1839
1840      If AT_STMT is a cast to unsigned that is later used for
1841      referencing a memory location, it is followed by a pointer
1842      conversion just after.  Because pointers do not wrap, the
1843      sequences that reference the memory do not wrap either.  In the
1844      following example, sequences corresponding to D_13 and to D_14
1845      can be proved to not wrap because they are used for computing a
1846      memory access:
1847          
1848        D.1621_13 = (long unsigned intD.4) D.1620_12;
1849        D.1622_14 = D.1621_13 * 8;
1850        D.1623_15 = (doubleD.29 *) D.1622_14;
1851   */
1852   if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
1853     {
1854       tree op0 = TREE_OPERAND (at_stmt, 0);
1855       tree op1 = TREE_OPERAND (at_stmt, 1);
1856       tree type_op1 = TREE_TYPE (op1);
1857
1858       if ((TYPE_UNSIGNED (type_op1)
1859            && used_in_pointer_arithmetic_p (op0, 2))
1860           || POINTER_TYPE_P (type_op1))
1861         {
1862           *unknown_max = true;
1863           return false;
1864         }
1865     }
1866
1867   if (chrec_contains_undetermined (base)
1868       || chrec_contains_undetermined (step)
1869       || TREE_CODE (base) == REAL_CST
1870       || TREE_CODE (step) == REAL_CST)
1871     {
1872       *unknown_max = true;
1873       return true;
1874     }
1875
1876   *unknown_max = false;
1877   base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
1878   bpsps = fold_build2 (PLUS_EXPR, type, base_plus_step, step);
1879   cps = compare_trees (base_plus_step, base);
1880   cpsps = compare_trees (bpsps, base_plus_step);
1881
1882   /* Check that the sequence is not wrapping in the first step: it
1883      should have the same monotonicity for the first two steps.  See
1884      PR23410.  */
1885   if (cps != cpsps)
1886     return true;
1887
1888   switch (cps)
1889     {
1890     case -1:
1891       {
1892         tree extreme = upper_bound_in_type (type, TREE_TYPE (base));
1893         delta = fold_build2 (MINUS_EXPR, type, extreme, base);
1894         step_abs = step;
1895         *init_is_max = false;
1896         break;
1897       }
1898
1899     case 1:
1900       {
1901         tree extreme = lower_bound_in_type (type, TREE_TYPE (base));
1902         delta = fold_build2 (MINUS_EXPR, type, base, extreme);
1903         step_abs = fold_build1 (NEGATE_EXPR, type, step);
1904         *init_is_max = true;
1905         break;
1906       }
1907
1908     case 0:
1909       /* This means step is equal to 0.  This should not happen.  It
1910          could happen in convert step, but not here.  Safely answer
1911          don't know as in the default case.  */
1912
1913     default:
1914       *unknown_max = true;
1915       return true;
1916     }
1917
1918   /* If AT_STMT represents a cast operation, we may not be able to
1919      take advantage of the undefinedness of signed type evolutions.
1920
1921      implement-c.texi states: "For conversion to a type of width
1922      N, the value is reduced modulo 2^N to be within range of the
1923      type;"
1924
1925      See PR 21959 for a test case.  Essentially, given a cast
1926      operation
1927                 unsigned char uc;
1928                 signed char sc;
1929                 ...
1930                 sc = (signed char) uc;
1931                 if (sc < 0)
1932                   ...
1933
1934      where uc and sc have the scev {0, +, 1}, we would consider uc to
1935      wrap around, but not sc, because it is of a signed type.  This
1936      causes VRP to erroneously fold the predicate above because it
1937      thinks that sc cannot be negative.  */
1938   if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
1939     {
1940       tree rhs = TREE_OPERAND (at_stmt, 1);
1941       tree outer_t = TREE_TYPE (rhs);
1942
1943       if (!TYPE_UNSIGNED (outer_t)
1944           && (TREE_CODE (rhs) == NOP_EXPR || TREE_CODE (rhs) == CONVERT_EXPR))
1945         {
1946           tree inner_t = TREE_TYPE (TREE_OPERAND (rhs, 0));
1947
1948           /* If the inner type is unsigned and its size and/or
1949              precision are smaller to that of the outer type, then the
1950              expression may wrap around.  */
1951           if (TYPE_UNSIGNED (inner_t)
1952               && (TYPE_SIZE (inner_t) <= TYPE_SIZE (outer_t)
1953                   || TYPE_PRECISION (inner_t) <= TYPE_PRECISION (outer_t)))
1954             {
1955               *unknown_max = true;
1956               return true;
1957             }
1958         }
1959     }
1960
1961   /* After having set INIT_IS_MAX, we can return false: when not using
1962      wrapping arithmetic, signed types don't wrap.  */
1963   if (!flag_wrapv && !TYPE_UNSIGNED (type))
1964     return false;
1965
1966   unsigned_type = unsigned_type_for (type);
1967   delta = fold_convert (unsigned_type, delta);
1968   step_abs = fold_convert (unsigned_type, step_abs);
1969   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
1970
1971   estimate_numbers_of_iterations_loop (loop);
1972   for (bound = loop->bounds; bound; bound = bound->next)
1973     if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter))
1974       return false;
1975
1976   /* At this point we still don't have a proof that the iv does not
1977      overflow: give up.  */
1978   *unknown_max = true;
1979   return true;
1980 }
1981
1982 /* Return the conversion to NEW_TYPE of the STEP of an induction
1983    variable BASE + STEP * I at AT_STMT.  When it fails, return
1984    NULL_TREE.  */
1985
1986 tree
1987 convert_step (struct loop *loop, tree new_type, tree base, tree step,
1988               tree at_stmt)
1989 {
1990   tree base_type;
1991
1992   if (chrec_contains_undetermined (base)
1993       || chrec_contains_undetermined (step))
1994     return NULL_TREE;
1995
1996   base_type = TREE_TYPE (base);
1997
1998   /* When not using wrapping arithmetic, signed types don't wrap.  */
1999   if (!flag_wrapv && !TYPE_UNSIGNED (base_type))
2000     return fold_convert (new_type, step);
2001
2002   if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type))
2003     return convert_step_widening (loop, new_type, base, step, at_stmt);
2004
2005   return fold_convert (new_type, step);
2006 }
2007
2008 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
2009
2010 void
2011 free_numbers_of_iterations_estimates_loop (struct loop *loop)
2012 {
2013   struct nb_iter_bound *bound, *next;
2014
2015   loop->nb_iterations = NULL;
2016   loop->estimated_nb_iterations = NULL;
2017   for (bound = loop->bounds; bound; bound = next)
2018     {
2019       next = bound->next;
2020       free (bound);
2021     }
2022
2023   loop->bounds = NULL;
2024 }
2025
2026 /* Frees the information on upper bounds on numbers of iterations of LOOPS.  */
2027
2028 void
2029 free_numbers_of_iterations_estimates (struct loops *loops)
2030 {
2031   unsigned i;
2032   struct loop *loop;
2033
2034   for (i = 1; i < loops->num; i++)
2035     {
2036       loop = loops->parray[i];
2037       if (loop)
2038         free_numbers_of_iterations_estimates_loop (loop);
2039     }
2040 }
2041
2042 /* Substitute value VAL for ssa name NAME inside expressions held
2043    at LOOP.  */
2044
2045 void
2046 substitute_in_loop_info (struct loop *loop, tree name, tree val)
2047 {
2048   struct nb_iter_bound *bound;
2049
2050   loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
2051   loop->estimated_nb_iterations
2052           = simplify_replace_tree (loop->estimated_nb_iterations, name, val);
2053   for (bound = loop->bounds; bound; bound = bound->next)
2054     {
2055       bound->bound = simplify_replace_tree (bound->bound, name, val);
2056       bound->additional = simplify_replace_tree (bound->additional, name, val);
2057     }
2058 }