OSDN Git Service

* builtins.c, c-pragma.h, c-typeck.c, cgraph.c, cgraphunit.c,
[pf3gnuchains/gcc-fork.git] / gcc / tree-vrp.c
1 /* Support routines for Value Range Propagation (VRP).
2    Copyright (C) 2005, 2006 Free Software Foundation, Inc.
3    Contributed by Diego Novillo <dnovillo@redhat.com>.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "ggc.h"
27 #include "flags.h"
28 #include "tree.h"
29 #include "basic-block.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "tree-dump.h"
33 #include "timevar.h"
34 #include "diagnostic.h"
35 #include "cfgloop.h"
36 #include "tree-scalar-evolution.h"
37 #include "tree-ssa-propagate.h"
38 #include "tree-chrec.h"
39
40 /* Set of SSA names found during the dominator traversal of a
41    sub-graph in find_assert_locations.  */
42 static sbitmap found_in_subgraph;
43
44 /* Local functions.  */
45 static int compare_values (tree val1, tree val2);
46
47 /* Location information for ASSERT_EXPRs.  Each instance of this
48    structure describes an ASSERT_EXPR for an SSA name.  Since a single
49    SSA name may have more than one assertion associated with it, these
50    locations are kept in a linked list attached to the corresponding
51    SSA name.  */
52 struct assert_locus_d
53 {
54   /* Basic block where the assertion would be inserted.  */
55   basic_block bb;
56
57   /* Some assertions need to be inserted on an edge (e.g., assertions
58      generated by COND_EXPRs).  In those cases, BB will be NULL.  */
59   edge e;
60
61   /* Pointer to the statement that generated this assertion.  */
62   block_stmt_iterator si;
63
64   /* Predicate code for the ASSERT_EXPR.  Must be COMPARISON_CLASS_P.  */
65   enum tree_code comp_code;
66
67   /* Value being compared against.  */
68   tree val;
69
70   /* Next node in the linked list.  */
71   struct assert_locus_d *next;
72 };
73
74 typedef struct assert_locus_d *assert_locus_t;
75
76 /* If bit I is present, it means that SSA name N_i has a list of
77    assertions that should be inserted in the IL.  */
78 static bitmap need_assert_for;
79
80 /* Array of locations lists where to insert assertions.  ASSERTS_FOR[I]
81    holds a list of ASSERT_LOCUS_T nodes that describe where
82    ASSERT_EXPRs for SSA name N_I should be inserted.  */
83 static assert_locus_t *asserts_for;
84
85 /* Set of blocks visited in find_assert_locations.  Used to avoid
86    visiting the same block more than once.  */
87 static sbitmap blocks_visited;
88
89 /* Value range array.  After propagation, VR_VALUE[I] holds the range
90    of values that SSA name N_I may take.  */
91 static value_range_t **vr_value;
92
93
94 /* Return true if ARG is marked with the nonnull attribute in the
95    current function signature.  */
96
97 static bool
98 nonnull_arg_p (tree arg)
99 {
100   tree t, attrs, fntype;
101   unsigned HOST_WIDE_INT arg_num;
102
103   gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg)));
104
105   fntype = TREE_TYPE (current_function_decl);
106   attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype));
107
108   /* If "nonnull" wasn't specified, we know nothing about the argument.  */
109   if (attrs == NULL_TREE)
110     return false;
111
112   /* If "nonnull" applies to all the arguments, then ARG is non-null.  */
113   if (TREE_VALUE (attrs) == NULL_TREE)
114     return true;
115
116   /* Get the position number for ARG in the function signature.  */
117   for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl);
118        t;
119        t = TREE_CHAIN (t), arg_num++)
120     {
121       if (t == arg)
122         break;
123     }
124
125   gcc_assert (t == arg);
126
127   /* Now see if ARG_NUM is mentioned in the nonnull list.  */
128   for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
129     {
130       if (compare_tree_int (TREE_VALUE (t), arg_num) == 0)
131         return true;
132     }
133
134   return false;
135 }
136
137
138 /* Set value range VR to {T, MIN, MAX, EQUIV}.  */
139
140 static void
141 set_value_range (value_range_t *vr, enum value_range_type t, tree min,
142                  tree max, bitmap equiv)
143 {
144 #if defined ENABLE_CHECKING
145   /* Check the validity of the range.  */
146   if (t == VR_RANGE || t == VR_ANTI_RANGE)
147     {
148       int cmp;
149
150       gcc_assert (min && max);
151
152       if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
153         gcc_assert (min != TYPE_MIN_VALUE (TREE_TYPE (min))
154                     || max != TYPE_MAX_VALUE (TREE_TYPE (max)));
155
156       cmp = compare_values (min, max);
157       gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
158     }
159
160   if (t == VR_UNDEFINED || t == VR_VARYING)
161     gcc_assert (min == NULL_TREE && max == NULL_TREE);
162
163   if (t == VR_UNDEFINED || t == VR_VARYING)
164     gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
165 #endif
166
167   vr->type = t;
168   vr->min = min;
169   vr->max = max;
170
171   /* Since updating the equivalence set involves deep copying the
172      bitmaps, only do it if absolutely necessary.  */
173   if (vr->equiv == NULL)
174     vr->equiv = BITMAP_ALLOC (NULL);
175
176   if (equiv != vr->equiv)
177     {
178       if (equiv && !bitmap_empty_p (equiv))
179         bitmap_copy (vr->equiv, equiv);
180       else
181         bitmap_clear (vr->equiv);
182     }
183 }
184
185
186 /* Copy value range FROM into value range TO.  */
187
188 static inline void
189 copy_value_range (value_range_t *to, value_range_t *from)
190 {
191   set_value_range (to, from->type, from->min, from->max, from->equiv);
192 }
193
194 /* Set value range VR to a non-negative range of type TYPE.  */
195
196 static inline void
197 set_value_range_to_nonnegative (value_range_t *vr, tree type)
198 {
199   tree zero = build_int_cst (type, 0);
200   set_value_range (vr, VR_RANGE, zero, TYPE_MAX_VALUE (type), vr->equiv);
201 }
202
203 /* Set value range VR to a non-NULL range of type TYPE.  */
204
205 static inline void
206 set_value_range_to_nonnull (value_range_t *vr, tree type)
207 {
208   tree zero = build_int_cst (type, 0);
209   set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
210 }
211
212
213 /* Set value range VR to a NULL range of type TYPE.  */
214
215 static inline void
216 set_value_range_to_null (value_range_t *vr, tree type)
217 {
218   tree zero = build_int_cst (type, 0);
219   set_value_range (vr, VR_RANGE, zero, zero, vr->equiv);
220 }
221
222
223 /* Set value range VR to VR_VARYING.  */
224
225 static inline void
226 set_value_range_to_varying (value_range_t *vr)
227 {
228   vr->type = VR_VARYING;
229   vr->min = vr->max = NULL_TREE;
230   if (vr->equiv)
231     bitmap_clear (vr->equiv);
232 }
233
234
235 /* Set value range VR to VR_UNDEFINED.  */
236
237 static inline void
238 set_value_range_to_undefined (value_range_t *vr)
239 {
240   vr->type = VR_UNDEFINED;
241   vr->min = vr->max = NULL_TREE;
242   if (vr->equiv)
243     bitmap_clear (vr->equiv);
244 }
245
246
247 /* Return value range information for VAR.  
248
249    If we have no values ranges recorded (ie, VRP is not running), then
250    return NULL.  Otherwise create an empty range if none existed for VAR.  */
251
252 static value_range_t *
253 get_value_range (tree var)
254 {
255   value_range_t *vr;
256   tree sym;
257   unsigned ver = SSA_NAME_VERSION (var);
258
259   /* If we have no recorded ranges, then return NULL.  */
260   if (! vr_value)
261     return NULL;
262
263   vr = vr_value[ver];
264   if (vr)
265     return vr;
266
267   /* Create a default value range.  */
268   vr_value[ver] = vr = XNEW (value_range_t);
269   memset (vr, 0, sizeof (*vr));
270
271   /* Allocate an equivalence set.  */
272   vr->equiv = BITMAP_ALLOC (NULL);
273
274   /* If VAR is a default definition, the variable can take any value
275      in VAR's type.  */
276   sym = SSA_NAME_VAR (var);
277   if (var == default_def (sym))
278     {
279       /* Try to use the "nonnull" attribute to create ~[0, 0]
280          anti-ranges for pointers.  Note that this is only valid with
281          default definitions of PARM_DECLs.  */
282       if (TREE_CODE (sym) == PARM_DECL
283           && POINTER_TYPE_P (TREE_TYPE (sym))
284           && nonnull_arg_p (sym))
285         set_value_range_to_nonnull (vr, TREE_TYPE (sym));
286       else
287         set_value_range_to_varying (vr);
288     }
289
290   return vr;
291 }
292
293
294 /* Update the value range and equivalence set for variable VAR to
295    NEW_VR.  Return true if NEW_VR is different from VAR's previous
296    value.
297
298    NOTE: This function assumes that NEW_VR is a temporary value range
299    object created for the sole purpose of updating VAR's range.  The
300    storage used by the equivalence set from NEW_VR will be freed by
301    this function.  Do not call update_value_range when NEW_VR
302    is the range object associated with another SSA name.  */
303
304 static inline bool
305 update_value_range (tree var, value_range_t *new_vr)
306 {
307   value_range_t *old_vr;
308   bool is_new;
309
310   /* Update the value range, if necessary.  */
311   old_vr = get_value_range (var);
312   is_new = old_vr->type != new_vr->type
313            || old_vr->min != new_vr->min
314            || old_vr->max != new_vr->max
315            || (old_vr->equiv == NULL && new_vr->equiv)
316            || (old_vr->equiv && new_vr->equiv == NULL)
317            || (!bitmap_equal_p (old_vr->equiv, new_vr->equiv));
318
319   if (is_new)
320     set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
321                      new_vr->equiv);
322
323   BITMAP_FREE (new_vr->equiv);
324   new_vr->equiv = NULL;
325
326   return is_new;
327 }
328
329
330 /* Add VAR and VAR's equivalence set to EQUIV.  */
331
332 static void
333 add_equivalence (bitmap equiv, tree var)
334 {
335   unsigned ver = SSA_NAME_VERSION (var);
336   value_range_t *vr = vr_value[ver];
337
338   bitmap_set_bit (equiv, ver);
339   if (vr && vr->equiv)
340     bitmap_ior_into (equiv, vr->equiv);
341 }
342
343
344 /* Return true if VR is ~[0, 0].  */
345
346 static inline bool
347 range_is_nonnull (value_range_t *vr)
348 {
349   return vr->type == VR_ANTI_RANGE
350          && integer_zerop (vr->min)
351          && integer_zerop (vr->max);
352 }
353
354
355 /* Return true if VR is [0, 0].  */
356
357 static inline bool
358 range_is_null (value_range_t *vr)
359 {
360   return vr->type == VR_RANGE
361          && integer_zerop (vr->min)
362          && integer_zerop (vr->max);
363 }
364
365
366 /* Return true if value range VR involves at least one symbol.  */
367
368 static inline bool
369 symbolic_range_p (value_range_t *vr)
370 {
371   return (!is_gimple_min_invariant (vr->min)
372           || !is_gimple_min_invariant (vr->max));
373 }
374
375 /* Like tree_expr_nonnegative_p, but this function uses value ranges
376    obtained so far.  */
377
378 static bool
379 vrp_expr_computes_nonnegative (tree expr)
380 {
381   return tree_expr_nonnegative_p (expr);
382 }
383
384 /* Like tree_expr_nonzero_p, but this function uses value ranges
385    obtained so far.  */
386
387 static bool
388 vrp_expr_computes_nonzero (tree expr)
389 {
390   if (tree_expr_nonzero_p (expr))
391     return true;
392
393   /* If we have an expression of the form &X->a, then the expression
394      is nonnull if X is nonnull.  */
395   if (TREE_CODE (expr) == ADDR_EXPR)
396     {
397       tree base = get_base_address (TREE_OPERAND (expr, 0));
398
399       if (base != NULL_TREE
400           && TREE_CODE (base) == INDIRECT_REF
401           && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
402         {
403           value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
404           if (range_is_nonnull (vr))
405             return true;
406         }
407     }
408
409   return false;
410 }
411
412
413 /* Compare two values VAL1 and VAL2.  Return
414    
415         -2 if VAL1 and VAL2 cannot be compared at compile-time,
416         -1 if VAL1 < VAL2,
417          0 if VAL1 == VAL2,
418         +1 if VAL1 > VAL2, and
419         +2 if VAL1 != VAL2
420
421    This is similar to tree_int_cst_compare but supports pointer values
422    and values that cannot be compared at compile time.  */
423
424 static int
425 compare_values (tree val1, tree val2)
426 {
427   if (val1 == val2)
428     return 0;
429
430   /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
431      both integers.  */
432   gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
433               == POINTER_TYPE_P (TREE_TYPE (val2)));
434
435   /* Do some limited symbolic comparisons.  */
436   if (!POINTER_TYPE_P (TREE_TYPE (val1)))
437     {
438       /* We can determine some comparisons against +INF and -INF even
439          if the other value is an expression.  */
440       if (val1 == TYPE_MAX_VALUE (TREE_TYPE (val1))
441           && TREE_CODE (val2) == MINUS_EXPR)
442         {
443           /* +INF > NAME - CST.  */
444           return 1;
445         }
446       else if (val1 == TYPE_MIN_VALUE (TREE_TYPE (val1))
447                && TREE_CODE (val2) == PLUS_EXPR)
448         {
449           /* -INF < NAME + CST.  */
450           return -1;
451         }
452       else if (TREE_CODE (val1) == MINUS_EXPR
453                && val2 == TYPE_MAX_VALUE (TREE_TYPE (val2)))
454         {
455           /* NAME - CST < +INF.  */
456           return -1;
457         }
458       else if (TREE_CODE (val1) == PLUS_EXPR
459                && val2 == TYPE_MIN_VALUE (TREE_TYPE (val2)))
460         {
461           /* NAME + CST > -INF.  */
462           return 1;
463         }
464     }
465
466   if ((TREE_CODE (val1) == SSA_NAME
467        || TREE_CODE (val1) == PLUS_EXPR
468        || TREE_CODE (val1) == MINUS_EXPR)
469       && (TREE_CODE (val2) == SSA_NAME
470           || TREE_CODE (val2) == PLUS_EXPR
471           || TREE_CODE (val2) == MINUS_EXPR))
472     {
473       tree n1, c1, n2, c2;
474   
475       /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
476          return -1 or +1 accordingly.  If VAL1 and VAL2 don't use the
477          same name, return -2.  */
478       if (TREE_CODE (val1) == SSA_NAME)
479         {
480           n1 = val1;
481           c1 = NULL_TREE;
482         }
483       else
484         {
485           n1 = TREE_OPERAND (val1, 0);
486           c1 = TREE_OPERAND (val1, 1);
487         }
488
489       if (TREE_CODE (val2) == SSA_NAME)
490         {
491           n2 = val2;
492           c2 = NULL_TREE;
493         }
494       else
495         {
496           n2 = TREE_OPERAND (val2, 0);
497           c2 = TREE_OPERAND (val2, 1);
498         }
499
500       /* Both values must use the same name.  */
501       if (n1 != n2)
502         return -2;
503
504       if (TREE_CODE (val1) == SSA_NAME)
505         {
506           if (TREE_CODE (val2) == SSA_NAME)
507             /* NAME == NAME  */
508             return 0;
509           else if (TREE_CODE (val2) == PLUS_EXPR)
510             /* NAME < NAME + CST  */
511             return -1;
512           else if (TREE_CODE (val2) == MINUS_EXPR)
513             /* NAME > NAME - CST  */
514             return 1;
515         }
516       else if (TREE_CODE (val1) == PLUS_EXPR)
517         {
518           if (TREE_CODE (val2) == SSA_NAME)
519             /* NAME + CST > NAME  */
520             return 1;
521           else if (TREE_CODE (val2) == PLUS_EXPR)
522             /* NAME + CST1 > NAME + CST2, if CST1 > CST2  */
523             return compare_values (c1, c2);
524           else if (TREE_CODE (val2) == MINUS_EXPR)
525             /* NAME + CST1 > NAME - CST2  */
526             return 1;
527         }
528       else if (TREE_CODE (val1) == MINUS_EXPR)
529         {
530           if (TREE_CODE (val2) == SSA_NAME)
531             /* NAME - CST < NAME  */
532             return -1;
533           else if (TREE_CODE (val2) == PLUS_EXPR)
534             /* NAME - CST1 < NAME + CST2  */
535             return -1;
536           else if (TREE_CODE (val2) == MINUS_EXPR)
537             /* NAME - CST1 > NAME - CST2, if CST1 < CST2.  Notice that
538                C1 and C2 are swapped in the call to compare_values.  */
539             return compare_values (c2, c1);
540         }
541
542       gcc_unreachable ();
543     }
544
545   /* We cannot compare non-constants.  */
546   if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
547     return -2;
548
549   if (!POINTER_TYPE_P (TREE_TYPE (val1)))
550     {
551       /* We cannot compare overflowed values.  */
552       if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
553         return -2;
554
555       return tree_int_cst_compare (val1, val2);
556     }
557   else
558     {
559       tree t;
560
561       /* First see if VAL1 and VAL2 are not the same.  */
562       if (val1 == val2 || operand_equal_p (val1, val2, 0))
563         return 0;
564       
565       /* If VAL1 is a lower address than VAL2, return -1.  */
566       t = fold_binary (LT_EXPR, boolean_type_node, val1, val2);
567       if (t == boolean_true_node)
568         return -1;
569
570       /* If VAL1 is a higher address than VAL2, return +1.  */
571       t = fold_binary (GT_EXPR, boolean_type_node, val1, val2);
572       if (t == boolean_true_node)
573         return 1;
574
575       /* If VAL1 is different than VAL2, return +2.  */
576       t = fold_binary (NE_EXPR, boolean_type_node, val1, val2);
577       if (t == boolean_true_node)
578         return 2;
579
580       return -2;
581     }
582 }
583
584
585 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
586           0 if VAL is not inside VR,
587          -2 if we cannot tell either way.
588
589    FIXME, the current semantics of this functions are a bit quirky
590           when taken in the context of VRP.  In here we do not care
591           about VR's type.  If VR is the anti-range ~[3, 5] the call
592           value_inside_range (4, VR) will return 1.
593
594           This is counter-intuitive in a strict sense, but the callers
595           currently expect this.  They are calling the function
596           merely to determine whether VR->MIN <= VAL <= VR->MAX.  The
597           callers are applying the VR_RANGE/VR_ANTI_RANGE semantics
598           themselves.
599
600           This also applies to value_ranges_intersect_p and
601           range_includes_zero_p.  The semantics of VR_RANGE and
602           VR_ANTI_RANGE should be encoded here, but that also means
603           adapting the users of these functions to the new semantics.  */
604
605 static inline int
606 value_inside_range (tree val, value_range_t *vr)
607 {
608   int cmp1, cmp2;
609
610   cmp1 = compare_values (val, vr->min);
611   if (cmp1 == -2 || cmp1 == 2)
612     return -2;
613
614   cmp2 = compare_values (val, vr->max);
615   if (cmp2 == -2 || cmp2 == 2)
616     return -2;
617
618   return (cmp1 == 0 || cmp1 == 1) && (cmp2 == -1 || cmp2 == 0);
619 }
620
621
622 /* Return true if value ranges VR0 and VR1 have a non-empty
623    intersection.  */
624
625 static inline bool
626 value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
627 {
628   return (value_inside_range (vr1->min, vr0) == 1
629           || value_inside_range (vr1->max, vr0) == 1
630           || value_inside_range (vr0->min, vr1) == 1
631           || value_inside_range (vr0->max, vr1) == 1);
632 }
633
634
635 /* Return true if VR includes the value zero, false otherwise.  FIXME,
636    currently this will return false for an anti-range like ~[-4, 3].
637    This will be wrong when the semantics of value_inside_range are
638    modified (currently the users of this function expect these
639    semantics).  */
640
641 static inline bool
642 range_includes_zero_p (value_range_t *vr)
643 {
644   tree zero;
645
646   gcc_assert (vr->type != VR_UNDEFINED
647               && vr->type != VR_VARYING
648               && !symbolic_range_p (vr));
649
650   zero = build_int_cst (TREE_TYPE (vr->min), 0);
651   return (value_inside_range (zero, vr) == 1);
652 }
653
654 /* Return true if T, an SSA_NAME, is known to be nonnegative.  Return
655    false otherwise or if no value range information is available.  */
656
657 bool
658 ssa_name_nonnegative_p (tree t)
659 {
660   value_range_t *vr = get_value_range (t);
661
662   if (!vr)
663     return false;
664
665   /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
666      which would return a useful value should be encoded as a VR_RANGE.  */
667   if (vr->type == VR_RANGE)
668     {
669       int result = compare_values (vr->min, integer_zero_node);
670
671       return (result == 0 || result == 1);
672     }
673   return false;
674 }
675
676 /* Return true if T, an SSA_NAME, is known to be nonzero.  Return
677    false otherwise or if no value range information is available.  */
678
679 bool
680 ssa_name_nonzero_p (tree t)
681 {
682   value_range_t *vr = get_value_range (t);
683
684   if (!vr)
685     return false;
686
687   /* A VR_RANGE which does not include zero is a nonzero value.  */
688   if (vr->type == VR_RANGE && !symbolic_range_p (vr))
689     return ! range_includes_zero_p (vr);
690
691   /* A VR_ANTI_RANGE which does include zero is a nonzero value.  */
692   if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr))
693     return range_includes_zero_p (vr);
694
695   return false;
696 }
697
698
699 /* When extracting ranges from X_i = ASSERT_EXPR <Y_j, pred>, we will
700    initially consider X_i and Y_j equivalent, so the equivalence set
701    of Y_j is added to the equivalence set of X_i.  However, it is
702    possible to have a chain of ASSERT_EXPRs whose predicates are
703    actually incompatible.  This is usually the result of nesting of
704    contradictory if-then-else statements.  For instance, in PR 24670:
705
706         count_4 has range [-INF, 63]
707
708         if (count_4 != 0)
709           {
710             count_19 = ASSERT_EXPR <count_4, count_4 != 0>
711             if (count_19 > 63)
712               {
713                 count_18 = ASSERT_EXPR <count_19, count_19 > 63>
714                 if (count_18 <= 63)
715                   ...
716               }
717           }
718
719    Notice that 'if (count_19 > 63)' is trivially false and will be
720    folded out at the end.  However, during propagation, the flowgraph
721    is not cleaned up and so, VRP will evaluate predicates more
722    predicates than necessary, so it must support these
723    inconsistencies.  The problem here is that because of the chaining
724    of ASSERT_EXPRs, the equivalency set for count_18 includes count_4.
725    Since count_4 has an incompatible range, we ICE when evaluating the
726    ranges in the equivalency set.  So, we need to remove count_4 from
727    it.  */
728
729 static void
730 fix_equivalence_set (value_range_t *vr_p)
731 {
732   bitmap_iterator bi;
733   unsigned i;
734   bitmap e = vr_p->equiv;
735   bitmap to_remove = BITMAP_ALLOC (NULL);
736
737   /* Only detect inconsistencies on numeric ranges.  */
738   if (vr_p->type == VR_VARYING
739       || vr_p->type == VR_UNDEFINED
740       || symbolic_range_p (vr_p))
741     return;
742
743   EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
744     {
745       value_range_t *equiv_vr = vr_value[i];
746
747       if (equiv_vr->type == VR_VARYING
748           || equiv_vr->type == VR_UNDEFINED
749           || symbolic_range_p (equiv_vr))
750         continue;
751
752       if (equiv_vr->type == VR_RANGE
753           && vr_p->type == VR_RANGE
754           && !value_ranges_intersect_p (vr_p, equiv_vr))
755         bitmap_set_bit (to_remove, i);
756       else if ((equiv_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
757                || (equiv_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
758         {
759           /* A range and an anti-range have an empty intersection if
760              their end points are the same.  FIXME,
761              value_ranges_intersect_p should handle this
762              automatically.  */
763           if (compare_values (equiv_vr->min, vr_p->min) == 0
764               && compare_values (equiv_vr->max, vr_p->max) == 0)
765             bitmap_set_bit (to_remove, i);
766         }
767     }
768
769   bitmap_and_compl_into (vr_p->equiv, to_remove);
770   BITMAP_FREE (to_remove);
771 }
772
773
774 /* Extract value range information from an ASSERT_EXPR EXPR and store
775    it in *VR_P.  */
776
777 static void
778 extract_range_from_assert (value_range_t *vr_p, tree expr)
779 {
780   tree var, cond, limit, min, max, type;
781   value_range_t *var_vr, *limit_vr;
782   enum tree_code cond_code;
783
784   var = ASSERT_EXPR_VAR (expr);
785   cond = ASSERT_EXPR_COND (expr);
786
787   gcc_assert (COMPARISON_CLASS_P (cond));
788
789   /* Find VAR in the ASSERT_EXPR conditional.  */
790   if (var == TREE_OPERAND (cond, 0))
791     {
792       /* If the predicate is of the form VAR COMP LIMIT, then we just
793          take LIMIT from the RHS and use the same comparison code.  */
794       limit = TREE_OPERAND (cond, 1);
795       cond_code = TREE_CODE (cond);
796     }
797   else
798     {
799       /* If the predicate is of the form LIMIT COMP VAR, then we need
800          to flip around the comparison code to create the proper range
801          for VAR.  */
802       limit = TREE_OPERAND (cond, 0);
803       cond_code = swap_tree_comparison (TREE_CODE (cond));
804     }
805
806   type = TREE_TYPE (limit);
807   gcc_assert (limit != var);
808
809   /* For pointer arithmetic, we only keep track of pointer equality
810      and inequality.  */
811   if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
812     {
813       set_value_range_to_varying (vr_p);
814       return;
815     }
816
817   /* If LIMIT is another SSA name and LIMIT has a range of its own,
818      try to use LIMIT's range to avoid creating symbolic ranges
819      unnecessarily. */
820   limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
821
822   /* LIMIT's range is only interesting if it has any useful information.  */
823   if (limit_vr
824       && (limit_vr->type == VR_UNDEFINED
825           || limit_vr->type == VR_VARYING
826           || symbolic_range_p (limit_vr)))
827     limit_vr = NULL;
828
829   /* Initially, the new range has the same set of equivalences of
830      VAR's range.  This will be revised before returning the final
831      value.  Since assertions may be chained via mutually exclusive
832      predicates, we will need to trim the set of equivalences before
833      we are done.  */
834   gcc_assert (vr_p->equiv == NULL);
835   vr_p->equiv = BITMAP_ALLOC (NULL);
836   add_equivalence (vr_p->equiv, var);
837
838   /* Extract a new range based on the asserted comparison for VAR and
839      LIMIT's value range.  Notice that if LIMIT has an anti-range, we
840      will only use it for equality comparisons (EQ_EXPR).  For any
841      other kind of assertion, we cannot derive a range from LIMIT's
842      anti-range that can be used to describe the new range.  For
843      instance, ASSERT_EXPR <x_2, x_2 <= b_4>.  If b_4 is ~[2, 10],
844      then b_4 takes on the ranges [-INF, 1] and [11, +INF].  There is
845      no single range for x_2 that could describe LE_EXPR, so we might
846      as well build the range [b_4, +INF] for it.  */
847   if (cond_code == EQ_EXPR)
848     {
849       enum value_range_type range_type;
850
851       if (limit_vr)
852         {
853           range_type = limit_vr->type;
854           min = limit_vr->min;
855           max = limit_vr->max;
856         }
857       else
858         {
859           range_type = VR_RANGE;
860           min = limit;
861           max = limit;
862         }
863
864       set_value_range (vr_p, range_type, min, max, vr_p->equiv);
865
866       /* When asserting the equality VAR == LIMIT and LIMIT is another
867          SSA name, the new range will also inherit the equivalence set
868          from LIMIT.  */
869       if (TREE_CODE (limit) == SSA_NAME)
870         add_equivalence (vr_p->equiv, limit);
871     }
872   else if (cond_code == NE_EXPR)
873     {
874       /* As described above, when LIMIT's range is an anti-range and
875          this assertion is an inequality (NE_EXPR), then we cannot
876          derive anything from the anti-range.  For instance, if
877          LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
878          not imply that VAR's range is [0, 0].  So, in the case of
879          anti-ranges, we just assert the inequality using LIMIT and
880          not its anti-range.
881
882          If LIMIT_VR is a range, we can only use it to build a new
883          anti-range if LIMIT_VR is a single-valued range.  For
884          instance, if LIMIT_VR is [0, 1], the predicate
885          VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
886          Rather, it means that for value 0 VAR should be ~[0, 0]
887          and for value 1, VAR should be ~[1, 1].  We cannot
888          represent these ranges.
889
890          The only situation in which we can build a valid
891          anti-range is when LIMIT_VR is a single-valued range
892          (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX).  In that case, 
893          build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX].  */
894       if (limit_vr
895           && limit_vr->type == VR_RANGE
896           && compare_values (limit_vr->min, limit_vr->max) == 0)
897         {
898           min = limit_vr->min;
899           max = limit_vr->max;
900         }
901       else
902         {
903           /* In any other case, we cannot use LIMIT's range to build a
904              valid anti-range.  */
905           min = max = limit;
906         }
907
908       /* If MIN and MAX cover the whole range for their type, then
909          just use the original LIMIT.  */
910       if (INTEGRAL_TYPE_P (type)
911           && min == TYPE_MIN_VALUE (type)
912           && max == TYPE_MAX_VALUE (type))
913         min = max = limit;
914
915       set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
916     }
917   else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
918     {
919       min = TYPE_MIN_VALUE (type);
920
921       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
922         max = limit;
923       else
924         {
925           /* If LIMIT_VR is of the form [N1, N2], we need to build the
926              range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
927              LT_EXPR.  */
928           max = limit_vr->max;
929         }
930
931       /* For LT_EXPR, we create the range [MIN, MAX - 1].  */
932       if (cond_code == LT_EXPR)
933         {
934           tree one = build_int_cst (type, 1);
935           max = fold_build2 (MINUS_EXPR, type, max, one);
936         }
937
938       set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
939     }
940   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
941     {
942       max = TYPE_MAX_VALUE (type);
943
944       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
945         min = limit;
946       else
947         {
948           /* If LIMIT_VR is of the form [N1, N2], we need to build the
949              range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
950              GT_EXPR.  */
951           min = limit_vr->min;
952         }
953
954       /* For GT_EXPR, we create the range [MIN + 1, MAX].  */
955       if (cond_code == GT_EXPR)
956         {
957           tree one = build_int_cst (type, 1);
958           min = fold_build2 (PLUS_EXPR, type, min, one);
959         }
960
961       set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
962     }
963   else
964     gcc_unreachable ();
965
966   /* If VAR already had a known range, it may happen that the new
967      range we have computed and VAR's range are not compatible.  For
968      instance,
969
970         if (p_5 == NULL)
971           p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
972           x_7 = p_6->fld;
973           p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
974
975      While the above comes from a faulty program, it will cause an ICE
976      later because p_8 and p_6 will have incompatible ranges and at
977      the same time will be considered equivalent.  A similar situation
978      would arise from
979
980         if (i_5 > 10)
981           i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
982           if (i_5 < 5)
983             i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
984
985      Again i_6 and i_7 will have incompatible ranges.  It would be
986      pointless to try and do anything with i_7's range because
987      anything dominated by 'if (i_5 < 5)' will be optimized away.
988      Note, due to the wa in which simulation proceeds, the statement
989      i_7 = ASSERT_EXPR <...> we would never be visited because the
990      conditional 'if (i_5 < 5)' always evaluates to false.  However,
991      this extra check does not hurt and may protect against future
992      changes to VRP that may get into a situation similar to the
993      NULL pointer dereference example.
994
995      Note that these compatibility tests are only needed when dealing
996      with ranges or a mix of range and anti-range.  If VAR_VR and VR_P
997      are both anti-ranges, they will always be compatible, because two
998      anti-ranges will always have a non-empty intersection.  */
999
1000   var_vr = get_value_range (var);
1001
1002   /* We may need to make adjustments when VR_P and VAR_VR are numeric
1003      ranges or anti-ranges.  */
1004   if (vr_p->type == VR_VARYING
1005       || vr_p->type == VR_UNDEFINED
1006       || var_vr->type == VR_VARYING
1007       || var_vr->type == VR_UNDEFINED
1008       || symbolic_range_p (vr_p)
1009       || symbolic_range_p (var_vr))
1010     goto done;
1011
1012   if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
1013     {
1014       /* If the two ranges have a non-empty intersection, we can
1015          refine the resulting range.  Since the assert expression
1016          creates an equivalency and at the same time it asserts a
1017          predicate, we can take the intersection of the two ranges to
1018          get better precision.  */
1019       if (value_ranges_intersect_p (var_vr, vr_p))
1020         {
1021           /* Use the larger of the two minimums.  */
1022           if (compare_values (vr_p->min, var_vr->min) == -1)
1023             min = var_vr->min;
1024           else
1025             min = vr_p->min;
1026
1027           /* Use the smaller of the two maximums.  */
1028           if (compare_values (vr_p->max, var_vr->max) == 1)
1029             max = var_vr->max;
1030           else
1031             max = vr_p->max;
1032
1033           set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
1034         }
1035       else
1036         {
1037           /* The two ranges do not intersect, set the new range to
1038              VARYING, because we will not be able to do anything
1039              meaningful with it.  */
1040           set_value_range_to_varying (vr_p);
1041         }
1042     }
1043   else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
1044            || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
1045     {
1046       /* A range and an anti-range will cancel each other only if
1047          their ends are the same.  For instance, in the example above,
1048          p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
1049          so VR_P should be set to VR_VARYING.  */
1050       if (compare_values (var_vr->min, vr_p->min) == 0
1051           && compare_values (var_vr->max, vr_p->max) == 0)
1052         set_value_range_to_varying (vr_p);
1053       else
1054         {
1055           tree min, max, anti_min, anti_max, real_min, real_max;
1056
1057           /* We want to compute the logical AND of the two ranges;
1058              there are three cases to consider.
1059
1060
1061              1. The VR_ANTI_RANGE range is completely within the 
1062                 VR_RANGE and the endpoints of the ranges are
1063                 different.  In that case the resulting range
1064                 should be whichever range is more precise.
1065                 Typically that will be the VR_RANGE.
1066
1067              2. The VR_ANTI_RANGE is completely disjoint from
1068                 the VR_RANGE.  In this case the resulting range
1069                 should be the VR_RANGE.
1070
1071              3. There is some overlap between the VR_ANTI_RANGE
1072                 and the VR_RANGE.
1073
1074                 3a. If the high limit of the VR_ANTI_RANGE resides
1075                     within the VR_RANGE, then the result is a new
1076                     VR_RANGE starting at the high limit of the
1077                     the VR_ANTI_RANGE + 1 and extending to the
1078                     high limit of the original VR_RANGE.
1079
1080                 3b. If the low limit of the VR_ANTI_RANGE resides
1081                     within the VR_RANGE, then the result is a new
1082                     VR_RANGE starting at the low limit of the original
1083                     VR_RANGE and extending to the low limit of the
1084                     VR_ANTI_RANGE - 1.  */
1085           if (vr_p->type == VR_ANTI_RANGE)
1086             {
1087               anti_min = vr_p->min;
1088               anti_max = vr_p->max;
1089               real_min = var_vr->min;
1090               real_max = var_vr->max;
1091             }
1092           else
1093             {
1094               anti_min = var_vr->min;
1095               anti_max = var_vr->max;
1096               real_min = vr_p->min;
1097               real_max = vr_p->max;
1098             }
1099
1100
1101           /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
1102              not including any endpoints.  */
1103           if (compare_values (anti_max, real_max) == -1
1104               && compare_values (anti_min, real_min) == 1)
1105             {
1106               set_value_range (vr_p, VR_RANGE, real_min,
1107                                real_max, vr_p->equiv);
1108             }
1109           /* Case 2, VR_ANTI_RANGE completely disjoint from
1110              VR_RANGE.  */
1111           else if (compare_values (anti_min, real_max) == 1
1112                    || compare_values (anti_max, real_min) == -1)
1113             {
1114               set_value_range (vr_p, VR_RANGE, real_min,
1115                                real_max, vr_p->equiv);
1116             }
1117           /* Case 3a, the anti-range extends into the low
1118              part of the real range.  Thus creating a new
1119              low for the real reange.  */
1120           else if ((compare_values (anti_max, real_min) == 1
1121                     || compare_values (anti_max, real_min) == 0)
1122                    && compare_values (anti_max, real_max) == -1)
1123             {
1124               min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
1125                                  anti_max,
1126                                  build_int_cst (TREE_TYPE (var_vr->min), 1));
1127               max = real_max;
1128               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1129             }
1130           /* Case 3b, the anti-range extends into the high
1131              part of the real range.  Thus creating a new
1132              higher for the real reange.  */
1133           else if (compare_values (anti_min, real_min) == 1
1134                    && (compare_values (anti_min, real_max) == -1
1135                        || compare_values (anti_min, real_max) == 0))
1136             {
1137               max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
1138                                  anti_min,
1139                                  build_int_cst (TREE_TYPE (var_vr->min), 1));
1140               min = real_min;
1141               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1142             }
1143         }
1144     }
1145
1146   /* Remove names from the equivalence set that have ranges
1147      incompatible with VR_P.  */
1148 done:
1149   fix_equivalence_set (vr_p);
1150 }
1151
1152
1153 /* Extract range information from SSA name VAR and store it in VR.  If
1154    VAR has an interesting range, use it.  Otherwise, create the
1155    range [VAR, VAR] and return it.  This is useful in situations where
1156    we may have conditionals testing values of VARYING names.  For
1157    instance,
1158
1159         x_3 = y_5;
1160         if (x_3 > y_5)
1161           ...
1162
1163     Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
1164     always false.  */
1165
1166 static void
1167 extract_range_from_ssa_name (value_range_t *vr, tree var)
1168 {
1169   value_range_t *var_vr = get_value_range (var);
1170
1171   if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
1172     copy_value_range (vr, var_vr);
1173   else
1174     set_value_range (vr, VR_RANGE, var, var, NULL);
1175
1176   add_equivalence (vr->equiv, var);
1177 }
1178
1179
1180 /* Wrapper around int_const_binop.  If the operation overflows and we
1181    are not using wrapping arithmetic, then adjust the result to be
1182    -INF or +INF depending on CODE, VAL1 and VAL2.  */
1183
1184 static inline tree
1185 vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
1186 {
1187   tree res;
1188
1189   if (flag_wrapv)
1190     return int_const_binop (code, val1, val2, 0);
1191
1192   /* If we are not using wrapping arithmetic, operate symbolically
1193      on -INF and +INF.  */
1194   res = int_const_binop (code, val1, val2, 0);
1195
1196   if (TYPE_UNSIGNED (TREE_TYPE (val1)))
1197     {
1198       int checkz = compare_values (res, val1);
1199
1200       /* Ensure that res = val1 [+*] val2 >= val1
1201          or that res = val1 - val2 <= val1.  */
1202       if (((code == PLUS_EXPR || code == MULT_EXPR)
1203            && !(checkz == 1 || checkz == 0))
1204           || (code == MINUS_EXPR
1205               && !(checkz == 0 || checkz == -1)))
1206         {
1207           res = copy_node (res);
1208           TREE_OVERFLOW (res) = 1;
1209         }
1210     }
1211   else if (TREE_OVERFLOW (res)
1212            && !TREE_OVERFLOW (val1)
1213            && !TREE_OVERFLOW (val2))
1214     {
1215       /* If the operation overflowed but neither VAL1 nor VAL2 are
1216          overflown, return -INF or +INF depending on the operation
1217          and the combination of signs of the operands.  */
1218       int sgn1 = tree_int_cst_sgn (val1);
1219       int sgn2 = tree_int_cst_sgn (val2);
1220
1221       /* Notice that we only need to handle the restricted set of
1222          operations handled by extract_range_from_binary_expr.
1223          Among them, only multiplication, addition and subtraction
1224          can yield overflow without overflown operands because we
1225          are working with integral types only... except in the
1226          case VAL1 = -INF and VAL2 = -1 which overflows to +INF
1227          for division too.  */
1228
1229       /* For multiplication, the sign of the overflow is given
1230          by the comparison of the signs of the operands.  */
1231       if ((code == MULT_EXPR && sgn1 == sgn2)
1232           /* For addition, the operands must be of the same sign
1233              to yield an overflow.  Its sign is therefore that
1234              of one of the operands, for example the first.  */
1235           || (code == PLUS_EXPR && sgn1 > 0)
1236           /* For subtraction, the operands must be of different
1237              signs to yield an overflow.  Its sign is therefore
1238              that of the first operand or the opposite of that
1239              of the second operand.  A first operand of 0 counts
1240              as positive here, for the corner case 0 - (-INF),
1241              which overflows, but must yield +INF.  */
1242           || (code == MINUS_EXPR && sgn1 >= 0)
1243           /* For division, the only case is -INF / -1 = +INF.  */
1244           || code == TRUNC_DIV_EXPR
1245           || code == FLOOR_DIV_EXPR
1246           || code == CEIL_DIV_EXPR
1247           || code == EXACT_DIV_EXPR
1248           || code == ROUND_DIV_EXPR)
1249         return TYPE_MAX_VALUE (TREE_TYPE (res));
1250       else
1251         return TYPE_MIN_VALUE (TREE_TYPE (res));
1252     }
1253
1254   return res;
1255 }
1256
1257
1258 /* Extract range information from a binary expression EXPR based on
1259    the ranges of each of its operands and the expression code.  */
1260
1261 static void
1262 extract_range_from_binary_expr (value_range_t *vr, tree expr)
1263 {
1264   enum tree_code code = TREE_CODE (expr);
1265   enum value_range_type type;
1266   tree op0, op1, min, max;
1267   int cmp;
1268   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1269   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1270
1271   /* Not all binary expressions can be applied to ranges in a
1272      meaningful way.  Handle only arithmetic operations.  */
1273   if (code != PLUS_EXPR
1274       && code != MINUS_EXPR
1275       && code != MULT_EXPR
1276       && code != TRUNC_DIV_EXPR
1277       && code != FLOOR_DIV_EXPR
1278       && code != CEIL_DIV_EXPR
1279       && code != EXACT_DIV_EXPR
1280       && code != ROUND_DIV_EXPR
1281       && code != MIN_EXPR
1282       && code != MAX_EXPR
1283       && code != BIT_AND_EXPR
1284       && code != TRUTH_ANDIF_EXPR
1285       && code != TRUTH_ORIF_EXPR
1286       && code != TRUTH_AND_EXPR
1287       && code != TRUTH_OR_EXPR)
1288     {
1289       set_value_range_to_varying (vr);
1290       return;
1291     }
1292
1293   /* Get value ranges for each operand.  For constant operands, create
1294      a new value range with the operand to simplify processing.  */
1295   op0 = TREE_OPERAND (expr, 0);
1296   if (TREE_CODE (op0) == SSA_NAME)
1297     vr0 = *(get_value_range (op0));
1298   else if (is_gimple_min_invariant (op0))
1299     set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1300   else
1301     set_value_range_to_varying (&vr0);
1302
1303   op1 = TREE_OPERAND (expr, 1);
1304   if (TREE_CODE (op1) == SSA_NAME)
1305     vr1 = *(get_value_range (op1));
1306   else if (is_gimple_min_invariant (op1))
1307     set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
1308   else
1309     set_value_range_to_varying (&vr1);
1310
1311   /* If either range is UNDEFINED, so is the result.  */
1312   if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
1313     {
1314       set_value_range_to_undefined (vr);
1315       return;
1316     }
1317
1318   /* The type of the resulting value range defaults to VR0.TYPE.  */
1319   type = vr0.type;
1320
1321   /* Refuse to operate on VARYING ranges, ranges of different kinds
1322      and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
1323      because we may be able to derive a useful range even if one of
1324      the operands is VR_VARYING or symbolic range.  TODO, we may be
1325      able to derive anti-ranges in some cases.  */
1326   if (code != BIT_AND_EXPR
1327       && code != TRUTH_AND_EXPR
1328       && code != TRUTH_OR_EXPR
1329       && (vr0.type == VR_VARYING
1330           || vr1.type == VR_VARYING
1331           || vr0.type != vr1.type
1332           || symbolic_range_p (&vr0)
1333           || symbolic_range_p (&vr1)))
1334     {
1335       set_value_range_to_varying (vr);
1336       return;
1337     }
1338
1339   /* Now evaluate the expression to determine the new range.  */
1340   if (POINTER_TYPE_P (TREE_TYPE (expr))
1341       || POINTER_TYPE_P (TREE_TYPE (op0))
1342       || POINTER_TYPE_P (TREE_TYPE (op1)))
1343     {
1344       /* For pointer types, we are really only interested in asserting
1345          whether the expression evaluates to non-NULL.  FIXME, we used
1346          to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
1347          ivopts is generating expressions with pointer multiplication
1348          in them.  */
1349       if (code == PLUS_EXPR)
1350         {
1351           if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
1352             set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1353           else if (range_is_null (&vr0) && range_is_null (&vr1))
1354             set_value_range_to_null (vr, TREE_TYPE (expr));
1355           else
1356             set_value_range_to_varying (vr);
1357         }
1358       else
1359         {
1360           /* Subtracting from a pointer, may yield 0, so just drop the
1361              resulting range to varying.  */
1362           set_value_range_to_varying (vr);
1363         }
1364
1365       return;
1366     }
1367
1368   /* For integer ranges, apply the operation to each end of the
1369      range and see what we end up with.  */
1370   if (code == TRUTH_ANDIF_EXPR
1371       || code == TRUTH_ORIF_EXPR
1372       || code == TRUTH_AND_EXPR
1373       || code == TRUTH_OR_EXPR)
1374     {
1375       /* If one of the operands is zero, we know that the whole
1376          expression evaluates zero.  */
1377       if (code == TRUTH_AND_EXPR
1378           && ((vr0.type == VR_RANGE
1379                && integer_zerop (vr0.min)
1380                && integer_zerop (vr0.max))
1381               || (vr1.type == VR_RANGE
1382                   && integer_zerop (vr1.min)
1383                   && integer_zerop (vr1.max))))
1384         {
1385           type = VR_RANGE;
1386           min = max = build_int_cst (TREE_TYPE (expr), 0);
1387         }
1388       /* If one of the operands is one, we know that the whole
1389          expression evaluates one.  */
1390       else if (code == TRUTH_OR_EXPR
1391                && ((vr0.type == VR_RANGE
1392                     && integer_onep (vr0.min)
1393                     && integer_onep (vr0.max))
1394                    || (vr1.type == VR_RANGE
1395                        && integer_onep (vr1.min)
1396                        && integer_onep (vr1.max))))
1397         {
1398           type = VR_RANGE;
1399           min = max = build_int_cst (TREE_TYPE (expr), 1);
1400         }
1401       else if (vr0.type != VR_VARYING
1402                && vr1.type != VR_VARYING
1403                && vr0.type == vr1.type
1404                && !symbolic_range_p (&vr0)
1405                && !symbolic_range_p (&vr1))
1406         {
1407           /* Boolean expressions cannot be folded with int_const_binop.  */
1408           min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
1409           max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
1410         }
1411       else
1412         {
1413           set_value_range_to_varying (vr);
1414           return;
1415         }
1416     }
1417   else if (code == PLUS_EXPR
1418            || code == MIN_EXPR
1419            || code == MAX_EXPR)
1420     {
1421       /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
1422          VR_VARYING.  It would take more effort to compute a precise
1423          range for such a case.  For example, if we have op0 == 1 and
1424          op1 == -1 with their ranges both being ~[0,0], we would have
1425          op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
1426          Note that we are guaranteed to have vr0.type == vr1.type at
1427          this point.  */
1428       if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
1429         {
1430           set_value_range_to_varying (vr);
1431           return;
1432         }
1433
1434       /* For operations that make the resulting range directly
1435          proportional to the original ranges, apply the operation to
1436          the same end of each range.  */
1437       min = vrp_int_const_binop (code, vr0.min, vr1.min);
1438       max = vrp_int_const_binop (code, vr0.max, vr1.max);
1439     }
1440   else if (code == MULT_EXPR
1441            || code == TRUNC_DIV_EXPR
1442            || code == FLOOR_DIV_EXPR
1443            || code == CEIL_DIV_EXPR
1444            || code == EXACT_DIV_EXPR
1445            || code == ROUND_DIV_EXPR)
1446     {
1447       tree val[4];
1448       size_t i;
1449
1450       /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
1451          drop to VR_VARYING.  It would take more effort to compute a
1452          precise range for such a case.  For example, if we have
1453          op0 == 65536 and op1 == 65536 with their ranges both being
1454          ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
1455          we cannot claim that the product is in ~[0,0].  Note that we
1456          are guaranteed to have vr0.type == vr1.type at this
1457          point.  */
1458       if (code == MULT_EXPR
1459           && vr0.type == VR_ANTI_RANGE
1460           && (flag_wrapv || TYPE_UNSIGNED (TREE_TYPE (op0))))
1461         {
1462           set_value_range_to_varying (vr);
1463           return;
1464         }
1465
1466       /* Multiplications and divisions are a bit tricky to handle,
1467          depending on the mix of signs we have in the two ranges, we
1468          need to operate on different values to get the minimum and
1469          maximum values for the new range.  One approach is to figure
1470          out all the variations of range combinations and do the
1471          operations.
1472
1473          However, this involves several calls to compare_values and it
1474          is pretty convoluted.  It's simpler to do the 4 operations
1475          (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
1476          MAX1) and then figure the smallest and largest values to form
1477          the new range.  */
1478
1479       /* Divisions by zero result in a VARYING value.  */
1480       if (code != MULT_EXPR
1481           && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
1482         {
1483           set_value_range_to_varying (vr);
1484           return;
1485         }
1486
1487       /* Compute the 4 cross operations.  */
1488       val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
1489
1490       val[1] = (vr1.max != vr1.min)
1491                ? vrp_int_const_binop (code, vr0.min, vr1.max)
1492                : NULL_TREE;
1493
1494       val[2] = (vr0.max != vr0.min)
1495                ? vrp_int_const_binop (code, vr0.max, vr1.min)
1496                : NULL_TREE;
1497
1498       val[3] = (vr0.min != vr0.max && vr1.min != vr1.max)
1499                ? vrp_int_const_binop (code, vr0.max, vr1.max)
1500                : NULL_TREE;
1501
1502       /* Set MIN to the minimum of VAL[i] and MAX to the maximum
1503          of VAL[i].  */
1504       min = val[0];
1505       max = val[0];
1506       for (i = 1; i < 4; i++)
1507         {
1508           if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
1509               || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
1510             break;
1511
1512           if (val[i])
1513             {
1514               if (!is_gimple_min_invariant (val[i]) || TREE_OVERFLOW (val[i]))
1515                 {
1516                   /* If we found an overflowed value, set MIN and MAX
1517                      to it so that we set the resulting range to
1518                      VARYING.  */
1519                   min = max = val[i];
1520                   break;
1521                 }
1522
1523               if (compare_values (val[i], min) == -1)
1524                 min = val[i];
1525
1526               if (compare_values (val[i], max) == 1)
1527                 max = val[i];
1528             }
1529         }
1530     }
1531   else if (code == MINUS_EXPR)
1532     {
1533       /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
1534          VR_VARYING.  It would take more effort to compute a precise
1535          range for such a case.  For example, if we have op0 == 1 and
1536          op1 == 1 with their ranges both being ~[0,0], we would have
1537          op0 - op1 == 0, so we cannot claim that the difference is in
1538          ~[0,0].  Note that we are guaranteed to have
1539          vr0.type == vr1.type at this point.  */
1540       if (vr0.type == VR_ANTI_RANGE)
1541         {
1542           set_value_range_to_varying (vr);
1543           return;
1544         }
1545
1546       /* For MINUS_EXPR, apply the operation to the opposite ends of
1547          each range.  */
1548       min = vrp_int_const_binop (code, vr0.min, vr1.max);
1549       max = vrp_int_const_binop (code, vr0.max, vr1.min);
1550     }
1551   else if (code == BIT_AND_EXPR)
1552     {
1553       if (vr0.type == VR_RANGE
1554           && vr0.min == vr0.max
1555           && tree_expr_nonnegative_p (vr0.max)
1556           && TREE_CODE (vr0.max) == INTEGER_CST)
1557         {
1558           min = build_int_cst (TREE_TYPE (expr), 0);
1559           max = vr0.max;
1560         }
1561       else if (vr1.type == VR_RANGE
1562           && vr1.min == vr1.max
1563           && tree_expr_nonnegative_p (vr1.max)
1564           && TREE_CODE (vr1.max) == INTEGER_CST)
1565         {
1566           type = VR_RANGE;
1567           min = build_int_cst (TREE_TYPE (expr), 0);
1568           max = vr1.max;
1569         }
1570       else
1571         {
1572           set_value_range_to_varying (vr);
1573           return;
1574         }
1575     }
1576   else
1577     gcc_unreachable ();
1578
1579   /* If either MIN or MAX overflowed, then set the resulting range to
1580      VARYING.  */
1581   if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
1582       || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
1583     {
1584       set_value_range_to_varying (vr);
1585       return;
1586     }
1587
1588   cmp = compare_values (min, max);
1589   if (cmp == -2 || cmp == 1)
1590     {
1591       /* If the new range has its limits swapped around (MIN > MAX),
1592          then the operation caused one of them to wrap around, mark
1593          the new range VARYING.  */
1594       set_value_range_to_varying (vr);
1595     }
1596   else
1597     set_value_range (vr, type, min, max, NULL);
1598 }
1599
1600
1601 /* Extract range information from a unary expression EXPR based on
1602    the range of its operand and the expression code.  */
1603
1604 static void
1605 extract_range_from_unary_expr (value_range_t *vr, tree expr)
1606 {
1607   enum tree_code code = TREE_CODE (expr);
1608   tree min, max, op0;
1609   int cmp;
1610   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1611
1612   /* Refuse to operate on certain unary expressions for which we
1613      cannot easily determine a resulting range.  */
1614   if (code == FIX_TRUNC_EXPR
1615       || code == FIX_CEIL_EXPR
1616       || code == FIX_FLOOR_EXPR
1617       || code == FIX_ROUND_EXPR
1618       || code == FLOAT_EXPR
1619       || code == BIT_NOT_EXPR
1620       || code == NON_LVALUE_EXPR
1621       || code == CONJ_EXPR)
1622     {
1623       set_value_range_to_varying (vr);
1624       return;
1625     }
1626
1627   /* Get value ranges for the operand.  For constant operands, create
1628      a new value range with the operand to simplify processing.  */
1629   op0 = TREE_OPERAND (expr, 0);
1630   if (TREE_CODE (op0) == SSA_NAME)
1631     vr0 = *(get_value_range (op0));
1632   else if (is_gimple_min_invariant (op0))
1633     set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1634   else
1635     set_value_range_to_varying (&vr0);
1636
1637   /* If VR0 is UNDEFINED, so is the result.  */
1638   if (vr0.type == VR_UNDEFINED)
1639     {
1640       set_value_range_to_undefined (vr);
1641       return;
1642     }
1643
1644   /* Refuse to operate on varying and symbolic ranges.  Also, if the
1645      operand is neither a pointer nor an integral type, set the
1646      resulting range to VARYING.  TODO, in some cases we may be able
1647      to derive anti-ranges (like nonzero values).  */
1648   if (vr0.type == VR_VARYING
1649       || (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
1650           && !POINTER_TYPE_P (TREE_TYPE (op0)))
1651       || symbolic_range_p (&vr0))
1652     {
1653       set_value_range_to_varying (vr);
1654       return;
1655     }
1656
1657   /* If the expression involves pointers, we are only interested in
1658      determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]).  */
1659   if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
1660     {
1661       if (range_is_nonnull (&vr0) || tree_expr_nonzero_p (expr))
1662         set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1663       else if (range_is_null (&vr0))
1664         set_value_range_to_null (vr, TREE_TYPE (expr));
1665       else
1666         set_value_range_to_varying (vr);
1667
1668       return;
1669     }
1670
1671   /* Handle unary expressions on integer ranges.  */
1672   if (code == NOP_EXPR || code == CONVERT_EXPR)
1673     {
1674       tree inner_type = TREE_TYPE (op0);
1675       tree outer_type = TREE_TYPE (expr);
1676
1677       /* If VR0 represents a simple range, then try to convert
1678          the min and max values for the range to the same type
1679          as OUTER_TYPE.  If the results compare equal to VR0's
1680          min and max values and the new min is still less than
1681          or equal to the new max, then we can safely use the newly
1682          computed range for EXPR.  This allows us to compute
1683          accurate ranges through many casts.  */
1684       if (vr0.type == VR_RANGE)
1685         {
1686           tree new_min, new_max;
1687
1688           /* Convert VR0's min/max to OUTER_TYPE.  */
1689           new_min = fold_convert (outer_type, vr0.min);
1690           new_max = fold_convert (outer_type, vr0.max);
1691
1692           /* Verify the new min/max values are gimple values and
1693              that they compare equal to VR0's min/max values.  */
1694           if (is_gimple_val (new_min)
1695               && is_gimple_val (new_max)
1696               && tree_int_cst_equal (new_min, vr0.min)
1697               && tree_int_cst_equal (new_max, vr0.max)
1698               && compare_values (new_min, new_max) <= 0
1699               && compare_values (new_min, new_max) >= -1)
1700             {
1701               set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv);
1702               return;
1703             }
1704         }
1705
1706       /* When converting types of different sizes, set the result to
1707          VARYING.  Things like sign extensions and precision loss may
1708          change the range.  For instance, if x_3 is of type 'long long
1709          int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
1710          is impossible to know at compile time whether y_5 will be
1711          ~[0, 0].  */
1712       if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type)
1713           || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1714         {
1715           set_value_range_to_varying (vr);
1716           return;
1717         }
1718     }
1719
1720   /* Apply the operation to each end of the range and see what we end
1721      up with.  */
1722   if (code == NEGATE_EXPR
1723       && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1724     {
1725       /* NEGATE_EXPR flips the range around.  */
1726       min = (vr0.max == TYPE_MAX_VALUE (TREE_TYPE (expr)) && !flag_wrapv)
1727              ? TYPE_MIN_VALUE (TREE_TYPE (expr))
1728              : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1729
1730       max = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)) && !flag_wrapv)
1731              ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1732              : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1733
1734     }
1735   else if (code == NEGATE_EXPR
1736            && TYPE_UNSIGNED (TREE_TYPE (expr)))
1737     {
1738       if (!range_includes_zero_p (&vr0))
1739         {
1740           max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1741           min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1742         }
1743       else
1744         {
1745           if (range_is_null (&vr0))
1746             set_value_range_to_null (vr, TREE_TYPE (expr));
1747           else
1748             set_value_range_to_varying (vr);
1749           return;
1750         }
1751     }
1752   else if (code == ABS_EXPR
1753            && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1754     {
1755       /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
1756          useful range.  */
1757       if (flag_wrapv
1758           && ((vr0.type == VR_RANGE
1759                && vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1760               || (vr0.type == VR_ANTI_RANGE
1761                   && vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))
1762                   && !range_includes_zero_p (&vr0))))
1763         {
1764           set_value_range_to_varying (vr);
1765           return;
1766         }
1767         
1768       /* ABS_EXPR may flip the range around, if the original range
1769          included negative values.  */
1770       min = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1771             ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1772             : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1773
1774       max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1775
1776       cmp = compare_values (min, max);
1777
1778       /* If a VR_ANTI_RANGEs contains zero, then we have
1779          ~[-INF, min(MIN, MAX)].  */
1780       if (vr0.type == VR_ANTI_RANGE)
1781         { 
1782           if (range_includes_zero_p (&vr0))
1783             {
1784               tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr));
1785
1786               /* Take the lower of the two values.  */
1787               if (cmp != 1)
1788                 max = min;
1789
1790               /* Create ~[-INF, min (abs(MIN), abs(MAX))]
1791                  or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
1792                  flag_wrapv is set and the original anti-range doesn't include
1793                  TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE.  */
1794               min = (flag_wrapv && vr0.min != type_min_value
1795                      ? int_const_binop (PLUS_EXPR,
1796                                         type_min_value,
1797                                         integer_one_node, 0)
1798                      : type_min_value);
1799             }
1800           else
1801             {
1802               /* All else has failed, so create the range [0, INF], even for
1803                  flag_wrapv since TYPE_MIN_VALUE is in the original
1804                  anti-range.  */
1805               vr0.type = VR_RANGE;
1806               min = build_int_cst (TREE_TYPE (expr), 0);
1807               max = TYPE_MAX_VALUE (TREE_TYPE (expr));
1808             }
1809         }
1810
1811       /* If the range contains zero then we know that the minimum value in the
1812          range will be zero.  */
1813       else if (range_includes_zero_p (&vr0))
1814         {
1815           if (cmp == 1)
1816             max = min;
1817           min = build_int_cst (TREE_TYPE (expr), 0);
1818         }
1819       else
1820         {
1821           /* If the range was reversed, swap MIN and MAX.  */
1822           if (cmp == 1)
1823             {
1824               tree t = min;
1825               min = max;
1826               max = t;
1827             }
1828         }
1829     }
1830   else
1831     {
1832       /* Otherwise, operate on each end of the range.  */
1833       min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1834       max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1835     }
1836
1837   cmp = compare_values (min, max);
1838   if (cmp == -2 || cmp == 1)
1839     {
1840       /* If the new range has its limits swapped around (MIN > MAX),
1841          then the operation caused one of them to wrap around, mark
1842          the new range VARYING.  */
1843       set_value_range_to_varying (vr);
1844     }
1845   else
1846     set_value_range (vr, vr0.type, min, max, NULL);
1847 }
1848
1849
1850 /* Extract range information from a comparison expression EXPR based
1851    on the range of its operand and the expression code.  */
1852
1853 static void
1854 extract_range_from_comparison (value_range_t *vr, tree expr)
1855 {
1856   tree val = vrp_evaluate_conditional (expr, false);
1857   if (val)
1858     {
1859       /* Since this expression was found on the RHS of an assignment,
1860          its type may be different from _Bool.  Convert VAL to EXPR's
1861          type.  */
1862       val = fold_convert (TREE_TYPE (expr), val);
1863       set_value_range (vr, VR_RANGE, val, val, vr->equiv);
1864     }
1865   else
1866     set_value_range_to_varying (vr);
1867 }
1868
1869
1870 /* Try to compute a useful range out of expression EXPR and store it
1871    in *VR.  */
1872
1873 static void
1874 extract_range_from_expr (value_range_t *vr, tree expr)
1875 {
1876   enum tree_code code = TREE_CODE (expr);
1877
1878   if (code == ASSERT_EXPR)
1879     extract_range_from_assert (vr, expr);
1880   else if (code == SSA_NAME)
1881     extract_range_from_ssa_name (vr, expr);
1882   else if (TREE_CODE_CLASS (code) == tcc_binary
1883            || code == TRUTH_ANDIF_EXPR
1884            || code == TRUTH_ORIF_EXPR
1885            || code == TRUTH_AND_EXPR
1886            || code == TRUTH_OR_EXPR
1887            || code == TRUTH_XOR_EXPR)
1888     extract_range_from_binary_expr (vr, expr);
1889   else if (TREE_CODE_CLASS (code) == tcc_unary)
1890     extract_range_from_unary_expr (vr, expr);
1891   else if (TREE_CODE_CLASS (code) == tcc_comparison)
1892     extract_range_from_comparison (vr, expr);
1893   else if (is_gimple_min_invariant (expr))
1894     set_value_range (vr, VR_RANGE, expr, expr, NULL);
1895   else
1896     set_value_range_to_varying (vr);
1897
1898   /* If we got a varying range from the tests above, try a final
1899      time to derive a nonnegative or nonzero range.  This time
1900      relying primarily on generic routines in fold in conjunction
1901      with range data.  */
1902   if (vr->type == VR_VARYING)
1903     {
1904       if (INTEGRAL_TYPE_P (TREE_TYPE (expr))
1905           && vrp_expr_computes_nonnegative (expr))
1906         set_value_range_to_nonnegative (vr, TREE_TYPE (expr));
1907       else if (vrp_expr_computes_nonzero (expr))
1908         set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1909     }
1910 }
1911
1912 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1913    would be profitable to adjust VR using scalar evolution information
1914    for VAR.  If so, update VR with the new limits.  */
1915
1916 static void
1917 adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
1918                         tree var)
1919 {
1920   tree init, step, chrec;
1921   bool init_is_max, unknown_max;
1922
1923   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
1924      better opportunities than a regular range, but I'm not sure.  */
1925   if (vr->type == VR_ANTI_RANGE)
1926     return;
1927
1928   chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
1929   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1930     return;
1931
1932   init = initial_condition_in_loop_num (chrec, loop->num);
1933   step = evolution_part_in_loop_num (chrec, loop->num);
1934
1935   /* If STEP is symbolic, we can't know whether INIT will be the
1936      minimum or maximum value in the range.  */
1937   if (step == NULL_TREE
1938       || !is_gimple_min_invariant (step))
1939     return;
1940
1941   /* Do not adjust ranges when chrec may wrap.  */
1942   if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,
1943                              current_loops->parray[CHREC_VARIABLE (chrec)],
1944                              &init_is_max, &unknown_max)
1945       || unknown_max)
1946     return;
1947
1948   if (!POINTER_TYPE_P (TREE_TYPE (init))
1949       && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
1950     {
1951       /* For VARYING or UNDEFINED ranges, just about anything we get
1952          from scalar evolutions should be better.  */
1953       tree min = TYPE_MIN_VALUE (TREE_TYPE (init));
1954       tree max = TYPE_MAX_VALUE (TREE_TYPE (init));
1955
1956       if (init_is_max)
1957         max = init;
1958       else
1959         min = init;
1960
1961       /* If we would create an invalid range, then just assume we
1962          know absolutely nothing.  This may be over-conservative,
1963          but it's clearly safe.  */
1964       if (compare_values (min, max) == 1)
1965         return;
1966
1967       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
1968     }
1969   else if (vr->type == VR_RANGE)
1970     {
1971       tree min = vr->min;
1972       tree max = vr->max;
1973
1974       if (init_is_max)
1975         {
1976           /* INIT is the maximum value.  If INIT is lower than VR->MAX
1977              but no smaller than VR->MIN, set VR->MAX to INIT.  */
1978           if (compare_values (init, max) == -1)
1979             {
1980               max = init;
1981
1982               /* If we just created an invalid range with the minimum
1983                  greater than the maximum, take the minimum all the
1984                  way to -INF.  */
1985               if (compare_values (min, max) == 1)
1986                 min = TYPE_MIN_VALUE (TREE_TYPE (min));
1987             }
1988         }
1989       else
1990         {
1991           /* If INIT is bigger than VR->MIN, set VR->MIN to INIT.  */
1992           if (compare_values (init, min) == 1)
1993             {
1994               min = init;
1995
1996               /* If we just created an invalid range with the minimum
1997                  greater than the maximum, take the maximum all the
1998                  way to +INF.  */
1999               if (compare_values (min, max) == 1)
2000                 max = TYPE_MAX_VALUE (TREE_TYPE (max));
2001             }
2002         }
2003
2004       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
2005     }
2006 }
2007
2008
2009 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
2010    
2011    - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
2012      all the values in the ranges.
2013
2014    - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
2015
2016    - Return NULL_TREE if it is not always possible to determine the
2017      value of the comparison.  */
2018
2019
2020 static tree
2021 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1)
2022 {
2023   /* VARYING or UNDEFINED ranges cannot be compared.  */
2024   if (vr0->type == VR_VARYING
2025       || vr0->type == VR_UNDEFINED
2026       || vr1->type == VR_VARYING
2027       || vr1->type == VR_UNDEFINED)
2028     return NULL_TREE;
2029
2030   /* Anti-ranges need to be handled separately.  */
2031   if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
2032     {
2033       /* If both are anti-ranges, then we cannot compute any
2034          comparison.  */
2035       if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
2036         return NULL_TREE;
2037
2038       /* These comparisons are never statically computable.  */
2039       if (comp == GT_EXPR
2040           || comp == GE_EXPR
2041           || comp == LT_EXPR
2042           || comp == LE_EXPR)
2043         return NULL_TREE;
2044
2045       /* Equality can be computed only between a range and an
2046          anti-range.  ~[VAL1, VAL2] == [VAL1, VAL2] is always false.  */
2047       if (vr0->type == VR_RANGE)
2048         {
2049           /* To simplify processing, make VR0 the anti-range.  */
2050           value_range_t *tmp = vr0;
2051           vr0 = vr1;
2052           vr1 = tmp;
2053         }
2054
2055       gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
2056
2057       if (compare_values (vr0->min, vr1->min) == 0
2058           && compare_values (vr0->max, vr1->max) == 0)
2059         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
2060
2061       return NULL_TREE;
2062     }
2063
2064   /* Simplify processing.  If COMP is GT_EXPR or GE_EXPR, switch the
2065      operands around and change the comparison code.  */
2066   if (comp == GT_EXPR || comp == GE_EXPR)
2067     {
2068       value_range_t *tmp;
2069       comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
2070       tmp = vr0;
2071       vr0 = vr1;
2072       vr1 = tmp;
2073     }
2074
2075   if (comp == EQ_EXPR)
2076     {
2077       /* Equality may only be computed if both ranges represent
2078          exactly one value.  */
2079       if (compare_values (vr0->min, vr0->max) == 0
2080           && compare_values (vr1->min, vr1->max) == 0)
2081         {
2082           int cmp_min = compare_values (vr0->min, vr1->min);
2083           int cmp_max = compare_values (vr0->max, vr1->max);
2084           if (cmp_min == 0 && cmp_max == 0)
2085             return boolean_true_node;
2086           else if (cmp_min != -2 && cmp_max != -2)
2087             return boolean_false_node;
2088         }
2089       /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1.  */
2090       else if (compare_values (vr0->min, vr1->max) == 1
2091                || compare_values (vr1->min, vr0->max) == 1)
2092         return boolean_false_node;
2093
2094       return NULL_TREE;
2095     }
2096   else if (comp == NE_EXPR)
2097     {
2098       int cmp1, cmp2;
2099
2100       /* If VR0 is completely to the left or completely to the right
2101          of VR1, they are always different.  Notice that we need to
2102          make sure that both comparisons yield similar results to
2103          avoid comparing values that cannot be compared at
2104          compile-time.  */
2105       cmp1 = compare_values (vr0->max, vr1->min);
2106       cmp2 = compare_values (vr0->min, vr1->max);
2107       if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
2108         return boolean_true_node;
2109
2110       /* If VR0 and VR1 represent a single value and are identical,
2111          return false.  */
2112       else if (compare_values (vr0->min, vr0->max) == 0
2113                && compare_values (vr1->min, vr1->max) == 0
2114                && compare_values (vr0->min, vr1->min) == 0
2115                && compare_values (vr0->max, vr1->max) == 0)
2116         return boolean_false_node;
2117
2118       /* Otherwise, they may or may not be different.  */
2119       else
2120         return NULL_TREE;
2121     }
2122   else if (comp == LT_EXPR || comp == LE_EXPR)
2123     {
2124       int tst;
2125
2126       /* If VR0 is to the left of VR1, return true.  */
2127       tst = compare_values (vr0->max, vr1->min);
2128       if ((comp == LT_EXPR && tst == -1)
2129           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
2130         return boolean_true_node;
2131
2132       /* If VR0 is to the right of VR1, return false.  */
2133       tst = compare_values (vr0->min, vr1->max);
2134       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
2135           || (comp == LE_EXPR && tst == 1))
2136         return boolean_false_node;
2137
2138       /* Otherwise, we don't know.  */
2139       return NULL_TREE;
2140     }
2141     
2142   gcc_unreachable ();
2143 }
2144
2145
2146 /* Given a value range VR, a value VAL and a comparison code COMP, return
2147    BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
2148    values in VR.  Return BOOLEAN_FALSE_NODE if the comparison
2149    always returns false.  Return NULL_TREE if it is not always
2150    possible to determine the value of the comparison.  */
2151
2152 static tree
2153 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val)
2154 {
2155   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
2156     return NULL_TREE;
2157
2158   /* Anti-ranges need to be handled separately.  */
2159   if (vr->type == VR_ANTI_RANGE)
2160     {
2161       /* For anti-ranges, the only predicates that we can compute at
2162          compile time are equality and inequality.  */
2163       if (comp == GT_EXPR
2164           || comp == GE_EXPR
2165           || comp == LT_EXPR
2166           || comp == LE_EXPR)
2167         return NULL_TREE;
2168
2169       /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2.  */
2170       if (value_inside_range (val, vr) == 1)
2171         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
2172
2173       return NULL_TREE;
2174     }
2175
2176   if (comp == EQ_EXPR)
2177     {
2178       /* EQ_EXPR may only be computed if VR represents exactly
2179          one value.  */
2180       if (compare_values (vr->min, vr->max) == 0)
2181         {
2182           int cmp = compare_values (vr->min, val);
2183           if (cmp == 0)
2184             return boolean_true_node;
2185           else if (cmp == -1 || cmp == 1 || cmp == 2)
2186             return boolean_false_node;
2187         }
2188       else if (compare_values (val, vr->min) == -1
2189                || compare_values (vr->max, val) == -1)
2190         return boolean_false_node;
2191
2192       return NULL_TREE;
2193     }
2194   else if (comp == NE_EXPR)
2195     {
2196       /* If VAL is not inside VR, then they are always different.  */
2197       if (compare_values (vr->max, val) == -1
2198           || compare_values (vr->min, val) == 1)
2199         return boolean_true_node;
2200
2201       /* If VR represents exactly one value equal to VAL, then return
2202          false.  */
2203       if (compare_values (vr->min, vr->max) == 0
2204           && compare_values (vr->min, val) == 0)
2205         return boolean_false_node;
2206
2207       /* Otherwise, they may or may not be different.  */
2208       return NULL_TREE;
2209     }
2210   else if (comp == LT_EXPR || comp == LE_EXPR)
2211     {
2212       int tst;
2213
2214       /* If VR is to the left of VAL, return true.  */
2215       tst = compare_values (vr->max, val);
2216       if ((comp == LT_EXPR && tst == -1)
2217           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
2218         return boolean_true_node;
2219
2220       /* If VR is to the right of VAL, return false.  */
2221       tst = compare_values (vr->min, val);
2222       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
2223           || (comp == LE_EXPR && tst == 1))
2224         return boolean_false_node;
2225
2226       /* Otherwise, we don't know.  */
2227       return NULL_TREE;
2228     }
2229   else if (comp == GT_EXPR || comp == GE_EXPR)
2230     {
2231       int tst;
2232
2233       /* If VR is to the right of VAL, return true.  */
2234       tst = compare_values (vr->min, val);
2235       if ((comp == GT_EXPR && tst == 1)
2236           || (comp == GE_EXPR && (tst == 0 || tst == 1)))
2237         return boolean_true_node;
2238
2239       /* If VR is to the left of VAL, return false.  */
2240       tst = compare_values (vr->max, val);
2241       if ((comp == GT_EXPR && (tst == -1 || tst == 0))
2242           || (comp == GE_EXPR && tst == -1))
2243         return boolean_false_node;
2244
2245       /* Otherwise, we don't know.  */
2246       return NULL_TREE;
2247     }
2248
2249   gcc_unreachable ();
2250 }
2251
2252
2253 /* Debugging dumps.  */
2254
2255 void dump_value_range (FILE *, value_range_t *);
2256 void debug_value_range (value_range_t *);
2257 void dump_all_value_ranges (FILE *);
2258 void debug_all_value_ranges (void);
2259 void dump_vr_equiv (FILE *, bitmap);
2260 void debug_vr_equiv (bitmap);
2261
2262
2263 /* Dump value range VR to FILE.  */
2264
2265 void
2266 dump_value_range (FILE *file, value_range_t *vr)
2267 {
2268   if (vr == NULL)
2269     fprintf (file, "[]");
2270   else if (vr->type == VR_UNDEFINED)
2271     fprintf (file, "UNDEFINED");
2272   else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
2273     {
2274       tree type = TREE_TYPE (vr->min);
2275
2276       fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
2277
2278       if (INTEGRAL_TYPE_P (type)
2279           && !TYPE_UNSIGNED (type)
2280           && vr->min == TYPE_MIN_VALUE (type))
2281         fprintf (file, "-INF");
2282       else
2283         print_generic_expr (file, vr->min, 0);
2284
2285       fprintf (file, ", ");
2286
2287       if (INTEGRAL_TYPE_P (type)
2288           && vr->max == TYPE_MAX_VALUE (type))
2289         fprintf (file, "+INF");
2290       else
2291         print_generic_expr (file, vr->max, 0);
2292
2293       fprintf (file, "]");
2294
2295       if (vr->equiv)
2296         {
2297           bitmap_iterator bi;
2298           unsigned i, c = 0;
2299
2300           fprintf (file, "  EQUIVALENCES: { ");
2301
2302           EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
2303             {
2304               print_generic_expr (file, ssa_name (i), 0);
2305               fprintf (file, " ");
2306               c++;
2307             }
2308
2309           fprintf (file, "} (%u elements)", c);
2310         }
2311     }
2312   else if (vr->type == VR_VARYING)
2313     fprintf (file, "VARYING");
2314   else
2315     fprintf (file, "INVALID RANGE");
2316 }
2317
2318
2319 /* Dump value range VR to stderr.  */
2320
2321 void
2322 debug_value_range (value_range_t *vr)
2323 {
2324   dump_value_range (stderr, vr);
2325 }
2326
2327
2328 /* Dump value ranges of all SSA_NAMEs to FILE.  */
2329
2330 void
2331 dump_all_value_ranges (FILE *file)
2332 {
2333   size_t i;
2334
2335   for (i = 0; i < num_ssa_names; i++)
2336     {
2337       if (vr_value[i])
2338         {
2339           print_generic_expr (file, ssa_name (i), 0);
2340           fprintf (file, ": ");
2341           dump_value_range (file, vr_value[i]);
2342           fprintf (file, "\n");
2343         }
2344     }
2345
2346   fprintf (file, "\n");
2347 }
2348
2349
2350 /* Dump all value ranges to stderr.  */
2351
2352 void
2353 debug_all_value_ranges (void)
2354 {
2355   dump_all_value_ranges (stderr);
2356 }
2357
2358
2359 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
2360    create a new SSA name N and return the assertion assignment
2361    'V = ASSERT_EXPR <V, V OP W>'.  */
2362
2363 static tree
2364 build_assert_expr_for (tree cond, tree v)
2365 {
2366   tree n, assertion;
2367
2368   gcc_assert (TREE_CODE (v) == SSA_NAME);
2369   n = duplicate_ssa_name (v, NULL_TREE);
2370
2371   if (COMPARISON_CLASS_P (cond))
2372     {
2373       tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond); 
2374       assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, a);
2375     }
2376   else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2377     {
2378       /* Given !V, build the assignment N = false.  */
2379       tree op0 = TREE_OPERAND (cond, 0);
2380       gcc_assert (op0 == v);
2381       assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
2382     }
2383   else if (TREE_CODE (cond) == SSA_NAME)
2384     {
2385       /* Given V, build the assignment N = true.  */
2386       gcc_assert (v == cond);
2387       assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
2388     }
2389   else
2390     gcc_unreachable ();
2391
2392   SSA_NAME_DEF_STMT (n) = assertion;
2393
2394   /* The new ASSERT_EXPR, creates a new SSA name that replaces the
2395      operand of the ASSERT_EXPR. Register the new name and the old one
2396      in the replacement table so that we can fix the SSA web after
2397      adding all the ASSERT_EXPRs.  */
2398   register_new_name_mapping (n, v);
2399
2400   return assertion;
2401 }
2402
2403
2404 /* Return false if EXPR is a predicate expression involving floating
2405    point values.  */
2406
2407 static inline bool
2408 fp_predicate (tree expr)
2409 {
2410   return (COMPARISON_CLASS_P (expr)
2411           && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
2412 }
2413
2414
2415 /* If the range of values taken by OP can be inferred after STMT executes,
2416    return the comparison code (COMP_CODE_P) and value (VAL_P) that
2417    describes the inferred range.  Return true if a range could be
2418    inferred.  */
2419
2420 static bool
2421 infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
2422 {
2423   *val_p = NULL_TREE;
2424   *comp_code_p = ERROR_MARK;
2425
2426   /* Do not attempt to infer anything in names that flow through
2427      abnormal edges.  */
2428   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
2429     return false;
2430
2431   /* Similarly, don't infer anything from statements that may throw
2432      exceptions.  */
2433   if (tree_could_throw_p (stmt))
2434     return false;
2435
2436   /* If STMT is the last statement of a basic block with no
2437      successors, there is no point inferring anything about any of its
2438      operands.  We would not be able to find a proper insertion point
2439      for the assertion, anyway.  */
2440   if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
2441     return false;
2442
2443   if (POINTER_TYPE_P (TREE_TYPE (op)))
2444     {
2445       bool is_store;
2446       unsigned num_uses, num_derefs;
2447
2448       count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
2449       if (num_derefs > 0 && flag_delete_null_pointer_checks)
2450         {
2451           /* We can only assume that a pointer dereference will yield
2452              non-NULL if -fdelete-null-pointer-checks is enabled.  */
2453           *val_p = build_int_cst (TREE_TYPE (op), 0);
2454           *comp_code_p = NE_EXPR;
2455           return true;
2456         }
2457     }
2458
2459   return false;
2460 }
2461
2462
2463 void dump_asserts_for (FILE *, tree);
2464 void debug_asserts_for (tree);
2465 void dump_all_asserts (FILE *);
2466 void debug_all_asserts (void);
2467
2468 /* Dump all the registered assertions for NAME to FILE.  */
2469
2470 void
2471 dump_asserts_for (FILE *file, tree name)
2472 {
2473   assert_locus_t loc;
2474
2475   fprintf (file, "Assertions to be inserted for ");
2476   print_generic_expr (file, name, 0);
2477   fprintf (file, "\n");
2478
2479   loc = asserts_for[SSA_NAME_VERSION (name)];
2480   while (loc)
2481     {
2482       fprintf (file, "\t");
2483       print_generic_expr (file, bsi_stmt (loc->si), 0);
2484       fprintf (file, "\n\tBB #%d", loc->bb->index);
2485       if (loc->e)
2486         {
2487           fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
2488                    loc->e->dest->index);
2489           dump_edge_info (file, loc->e, 0);
2490         }
2491       fprintf (file, "\n\tPREDICATE: ");
2492       print_generic_expr (file, name, 0);
2493       fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
2494       print_generic_expr (file, loc->val, 0);
2495       fprintf (file, "\n\n");
2496       loc = loc->next;
2497     }
2498
2499   fprintf (file, "\n");
2500 }
2501
2502
2503 /* Dump all the registered assertions for NAME to stderr.  */
2504
2505 void
2506 debug_asserts_for (tree name)
2507 {
2508   dump_asserts_for (stderr, name);
2509 }
2510
2511
2512 /* Dump all the registered assertions for all the names to FILE.  */
2513
2514 void
2515 dump_all_asserts (FILE *file)
2516 {
2517   unsigned i;
2518   bitmap_iterator bi;
2519
2520   fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
2521   EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2522     dump_asserts_for (file, ssa_name (i));
2523   fprintf (file, "\n");
2524 }
2525
2526
2527 /* Dump all the registered assertions for all the names to stderr.  */
2528
2529 void
2530 debug_all_asserts (void)
2531 {
2532   dump_all_asserts (stderr);
2533 }
2534
2535
2536 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
2537    'NAME COMP_CODE VAL' at a location that dominates block BB or
2538    E->DEST, then register this location as a possible insertion point
2539    for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
2540
2541    BB, E and SI provide the exact insertion point for the new
2542    ASSERT_EXPR.  If BB is NULL, then the ASSERT_EXPR is to be inserted
2543    on edge E.  Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
2544    BB.  If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
2545    must not be NULL.  */
2546
2547 static void
2548 register_new_assert_for (tree name,
2549                          enum tree_code comp_code,
2550                          tree val,
2551                          basic_block bb,
2552                          edge e,
2553                          block_stmt_iterator si)
2554 {
2555   assert_locus_t n, loc, last_loc;
2556   bool found;
2557   basic_block dest_bb;
2558
2559 #if defined ENABLE_CHECKING
2560   gcc_assert (bb == NULL || e == NULL);
2561
2562   if (e == NULL)
2563     gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
2564                 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
2565 #endif
2566
2567   /* The new assertion A will be inserted at BB or E.  We need to
2568      determine if the new location is dominated by a previously
2569      registered location for A.  If we are doing an edge insertion,
2570      assume that A will be inserted at E->DEST.  Note that this is not
2571      necessarily true.
2572      
2573      If E is a critical edge, it will be split.  But even if E is
2574      split, the new block will dominate the same set of blocks that
2575      E->DEST dominates.
2576      
2577      The reverse, however, is not true, blocks dominated by E->DEST
2578      will not be dominated by the new block created to split E.  So,
2579      if the insertion location is on a critical edge, we will not use
2580      the new location to move another assertion previously registered
2581      at a block dominated by E->DEST.  */
2582   dest_bb = (bb) ? bb : e->dest;
2583
2584   /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
2585      VAL at a block dominating DEST_BB, then we don't need to insert a new
2586      one.  Similarly, if the same assertion already exists at a block
2587      dominated by DEST_BB and the new location is not on a critical
2588      edge, then update the existing location for the assertion (i.e.,
2589      move the assertion up in the dominance tree).
2590
2591      Note, this is implemented as a simple linked list because there
2592      should not be more than a handful of assertions registered per
2593      name.  If this becomes a performance problem, a table hashed by
2594      COMP_CODE and VAL could be implemented.  */
2595   loc = asserts_for[SSA_NAME_VERSION (name)];
2596   last_loc = loc;
2597   found = false;
2598   while (loc)
2599     {
2600       if (loc->comp_code == comp_code
2601           && (loc->val == val
2602               || operand_equal_p (loc->val, val, 0)))
2603         {
2604           /* If the assertion NAME COMP_CODE VAL has already been
2605              registered at a basic block that dominates DEST_BB, then
2606              we don't need to insert the same assertion again.  Note
2607              that we don't check strict dominance here to avoid
2608              replicating the same assertion inside the same basic
2609              block more than once (e.g., when a pointer is
2610              dereferenced several times inside a block).
2611
2612              An exception to this rule are edge insertions.  If the
2613              new assertion is to be inserted on edge E, then it will
2614              dominate all the other insertions that we may want to
2615              insert in DEST_BB.  So, if we are doing an edge
2616              insertion, don't do this dominance check.  */
2617           if (e == NULL
2618               && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
2619             return;
2620
2621           /* Otherwise, if E is not a critical edge and DEST_BB
2622              dominates the existing location for the assertion, move
2623              the assertion up in the dominance tree by updating its
2624              location information.  */
2625           if ((e == NULL || !EDGE_CRITICAL_P (e))
2626               && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
2627             {
2628               loc->bb = dest_bb;
2629               loc->e = e;
2630               loc->si = si;
2631               return;
2632             }
2633         }
2634
2635       /* Update the last node of the list and move to the next one.  */
2636       last_loc = loc;
2637       loc = loc->next;
2638     }
2639
2640   /* If we didn't find an assertion already registered for
2641      NAME COMP_CODE VAL, add a new one at the end of the list of
2642      assertions associated with NAME.  */
2643   n = XNEW (struct assert_locus_d);
2644   n->bb = dest_bb;
2645   n->e = e;
2646   n->si = si;
2647   n->comp_code = comp_code;
2648   n->val = val;
2649   n->next = NULL;
2650
2651   if (last_loc)
2652     last_loc->next = n;
2653   else
2654     asserts_for[SSA_NAME_VERSION (name)] = n;
2655
2656   bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
2657 }
2658
2659
2660 /* Try to register an edge assertion for SSA name NAME on edge E for
2661    the conditional jump pointed to by SI.  Return true if an assertion
2662    for NAME could be registered.  */
2663
2664 static bool
2665 register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
2666 {
2667   tree val, stmt;
2668   enum tree_code comp_code;
2669
2670   stmt = bsi_stmt (si);
2671
2672   /* Do not attempt to infer anything in names that flow through
2673      abnormal edges.  */
2674   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
2675     return false;
2676
2677   /* If NAME was not found in the sub-graph reachable from E, then
2678      there's nothing to do.  */
2679   if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
2680     return false;
2681
2682   /* We found a use of NAME in the sub-graph rooted at E->DEST.
2683      Register an assertion for NAME according to the value that NAME
2684      takes on edge E.  */
2685   if (TREE_CODE (stmt) == COND_EXPR)
2686     {
2687       /* If BB ends in a COND_EXPR then NAME then we should insert
2688          the original predicate on EDGE_TRUE_VALUE and the
2689          opposite predicate on EDGE_FALSE_VALUE.  */
2690       tree cond = COND_EXPR_COND (stmt);
2691       bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
2692
2693       /* Predicates may be a single SSA name or NAME OP VAL.  */
2694       if (cond == name)
2695         {
2696           /* If the predicate is a name, it must be NAME, in which
2697              case we create the predicate NAME == true or
2698              NAME == false accordingly.  */
2699           comp_code = EQ_EXPR;
2700           val = (is_else_edge) ? boolean_false_node : boolean_true_node;
2701         }
2702       else
2703         {
2704           /* Otherwise, we have a comparison of the form NAME COMP VAL
2705              or VAL COMP NAME.  */
2706           if (name == TREE_OPERAND (cond, 1))
2707             {
2708               /* If the predicate is of the form VAL COMP NAME, flip
2709                  COMP around because we need to register NAME as the
2710                  first operand in the predicate.  */
2711               comp_code = swap_tree_comparison (TREE_CODE (cond));
2712               val = TREE_OPERAND (cond, 0);
2713             }
2714           else
2715             {
2716               /* The comparison is of the form NAME COMP VAL, so the
2717                  comparison code remains unchanged.  */
2718               comp_code = TREE_CODE (cond);
2719               val = TREE_OPERAND (cond, 1);
2720             }
2721
2722           /* If we are inserting the assertion on the ELSE edge, we
2723              need to invert the sign comparison.  */
2724           if (is_else_edge)
2725             comp_code = invert_tree_comparison (comp_code, 0);
2726
2727           /* Do not register always-false predicates.  FIXME, this
2728              works around a limitation in fold() when dealing with
2729              enumerations.  Given 'enum { N1, N2 } x;', fold will not
2730              fold 'if (x > N2)' to 'if (0)'.  */
2731           if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
2732               && (INTEGRAL_TYPE_P (TREE_TYPE (val))
2733                   || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val))))
2734             {
2735               tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
2736               tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
2737
2738               if (comp_code == GT_EXPR && compare_values (val, max) == 0)
2739                 return false;
2740
2741               if (comp_code == LT_EXPR && compare_values (val, min) == 0)
2742                 return false;
2743             }
2744         }
2745     }
2746   else
2747     {
2748       /* FIXME.  Handle SWITCH_EXPR.  */
2749       gcc_unreachable ();
2750     }
2751
2752   register_new_assert_for (name, comp_code, val, NULL, e, si);
2753   return true;
2754 }
2755
2756
2757 static bool find_assert_locations (basic_block bb);
2758
2759 /* Determine whether the outgoing edges of BB should receive an
2760    ASSERT_EXPR for each of the operands of BB's last statement.  The
2761    last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
2762
2763    If any of the sub-graphs rooted at BB have an interesting use of
2764    the predicate operands, an assert location node is added to the
2765    list of assertions for the corresponding operands.  */
2766
2767 static bool
2768 find_conditional_asserts (basic_block bb)
2769 {
2770   bool need_assert;
2771   block_stmt_iterator last_si;
2772   tree op, last;
2773   edge_iterator ei;
2774   edge e;
2775   ssa_op_iter iter;
2776
2777   need_assert = false;
2778   last_si = bsi_last (bb);
2779   last = bsi_stmt (last_si);
2780
2781   /* Look for uses of the operands in each of the sub-graphs
2782      rooted at BB.  We need to check each of the outgoing edges
2783      separately, so that we know what kind of ASSERT_EXPR to
2784      insert.  */
2785   FOR_EACH_EDGE (e, ei, bb->succs)
2786     {
2787       if (e->dest == bb)
2788         continue;
2789
2790       /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
2791          Otherwise, when we finish traversing each of the sub-graphs, we
2792          won't know whether the variables were found in the sub-graphs or
2793          if they had been found in a block upstream from BB. 
2794
2795          This is actually a bad idea is some cases, particularly jump
2796          threading.  Consider a CFG like the following:
2797
2798                     0
2799                    /|
2800                   1 |
2801                    \|
2802                     2
2803                    / \
2804                   3   4
2805
2806          Assume that one or more operands in the conditional at the
2807          end of block 0 are used in a conditional in block 2, but not
2808          anywhere in block 1.  In this case we will not insert any
2809          assert statements in block 1, which may cause us to miss
2810          opportunities to optimize, particularly for jump threading.  */
2811       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2812         RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2813
2814       /* Traverse the strictly dominated sub-graph rooted at E->DEST
2815          to determine if any of the operands in the conditional
2816          predicate are used.  */
2817       if (e->dest != bb)
2818         need_assert |= find_assert_locations (e->dest);
2819
2820       /* Register the necessary assertions for each operand in the
2821          conditional predicate.  */
2822       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2823         need_assert |= register_edge_assert_for (op, e, last_si);
2824     }
2825
2826   /* Finally, indicate that we have found the operands in the
2827      conditional.  */
2828   FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2829     SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2830
2831   return need_assert;
2832 }
2833
2834
2835 /* Traverse all the statements in block BB looking for statements that
2836    may generate useful assertions for the SSA names in their operand.
2837    If a statement produces a useful assertion A for name N_i, then the
2838    list of assertions already generated for N_i is scanned to
2839    determine if A is actually needed.
2840    
2841    If N_i already had the assertion A at a location dominating the
2842    current location, then nothing needs to be done.  Otherwise, the
2843    new location for A is recorded instead.
2844
2845    1- For every statement S in BB, all the variables used by S are
2846       added to bitmap FOUND_IN_SUBGRAPH.
2847
2848    2- If statement S uses an operand N in a way that exposes a known
2849       value range for N, then if N was not already generated by an
2850       ASSERT_EXPR, create a new assert location for N.  For instance,
2851       if N is a pointer and the statement dereferences it, we can
2852       assume that N is not NULL.
2853
2854    3- COND_EXPRs are a special case of #2.  We can derive range
2855       information from the predicate but need to insert different
2856       ASSERT_EXPRs for each of the sub-graphs rooted at the
2857       conditional block.  If the last statement of BB is a conditional
2858       expression of the form 'X op Y', then
2859
2860       a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
2861
2862       b) If the conditional is the only entry point to the sub-graph
2863          corresponding to the THEN_CLAUSE, recurse into it.  On
2864          return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
2865          an ASSERT_EXPR is added for the corresponding variable.
2866
2867       c) Repeat step (b) on the ELSE_CLAUSE.
2868
2869       d) Mark X and Y in FOUND_IN_SUBGRAPH.
2870
2871       For instance,
2872
2873             if (a == 9)
2874               b = a;
2875             else
2876               b = c + 1;
2877
2878       In this case, an assertion on the THEN clause is useful to
2879       determine that 'a' is always 9 on that edge.  However, an assertion
2880       on the ELSE clause would be unnecessary.
2881
2882    4- If BB does not end in a conditional expression, then we recurse
2883       into BB's dominator children.
2884    
2885    At the end of the recursive traversal, every SSA name will have a
2886    list of locations where ASSERT_EXPRs should be added.  When a new
2887    location for name N is found, it is registered by calling
2888    register_new_assert_for.  That function keeps track of all the
2889    registered assertions to prevent adding unnecessary assertions.
2890    For instance, if a pointer P_4 is dereferenced more than once in a
2891    dominator tree, only the location dominating all the dereference of
2892    P_4 will receive an ASSERT_EXPR.
2893
2894    If this function returns true, then it means that there are names
2895    for which we need to generate ASSERT_EXPRs.  Those assertions are
2896    inserted by process_assert_insertions.
2897
2898    TODO.  Handle SWITCH_EXPR.  */
2899
2900 static bool
2901 find_assert_locations (basic_block bb)
2902 {
2903   block_stmt_iterator si;
2904   tree last, phi;
2905   bool need_assert;
2906   basic_block son;
2907
2908   if (TEST_BIT (blocks_visited, bb->index))
2909     return false;
2910
2911   SET_BIT (blocks_visited, bb->index);
2912
2913   need_assert = false;
2914
2915   /* Traverse all PHI nodes in BB marking used operands.  */
2916   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2917     {
2918       use_operand_p arg_p;
2919       ssa_op_iter i;
2920
2921       FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
2922         {
2923           tree arg = USE_FROM_PTR (arg_p);
2924           if (TREE_CODE (arg) == SSA_NAME)
2925             {
2926               gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
2927               SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
2928             }
2929         }
2930     }
2931
2932   /* Traverse all the statements in BB marking used names and looking
2933      for statements that may infer assertions for their used operands.  */
2934   last = NULL_TREE;
2935   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2936     {
2937       tree stmt, op;
2938       ssa_op_iter i;
2939
2940       stmt = bsi_stmt (si);
2941
2942       /* See if we can derive an assertion for any of STMT's operands.  */
2943       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
2944         {
2945           tree value;
2946           enum tree_code comp_code;
2947
2948           /* Mark OP in bitmap FOUND_IN_SUBGRAPH.  If STMT is inside
2949              the sub-graph of a conditional block, when we return from
2950              this recursive walk, our parent will use the
2951              FOUND_IN_SUBGRAPH bitset to determine if one of the
2952              operands it was looking for was present in the sub-graph.  */
2953           SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2954
2955           /* If OP is used only once, namely in this STMT, don't
2956              bother creating an ASSERT_EXPR for it.  Such an
2957              ASSERT_EXPR would do nothing but increase compile time.
2958              Experiments show that with this simple check, we can save
2959              more than 20% of ASSERT_EXPRs.  */
2960           if (has_single_use (op))
2961             continue;
2962
2963           /* If OP is used in such a way that we can infer a value
2964              range for it, and we don't find a previous assertion for
2965              it, create a new assertion location node for OP.  */
2966           if (infer_value_range (stmt, op, &comp_code, &value))
2967             {
2968               register_new_assert_for (op, comp_code, value, bb, NULL, si);
2969               need_assert = true;
2970             }
2971         }
2972
2973       /* Remember the last statement of the block.  */
2974       last = stmt;
2975     }
2976
2977   /* If BB's last statement is a conditional expression
2978      involving integer operands, recurse into each of the sub-graphs
2979      rooted at BB to determine if we need to add ASSERT_EXPRs.  */
2980   if (last
2981       && TREE_CODE (last) == COND_EXPR
2982       && !fp_predicate (COND_EXPR_COND (last))
2983       && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
2984     need_assert |= find_conditional_asserts (bb);
2985
2986   /* Recurse into the dominator children of BB.  */
2987   for (son = first_dom_son (CDI_DOMINATORS, bb);
2988        son;
2989        son = next_dom_son (CDI_DOMINATORS, son))
2990     need_assert |= find_assert_locations (son);
2991
2992   return need_assert;
2993 }
2994
2995
2996 /* Create an ASSERT_EXPR for NAME and insert it in the location
2997    indicated by LOC.  Return true if we made any edge insertions.  */
2998
2999 static bool
3000 process_assert_insertions_for (tree name, assert_locus_t loc)
3001 {
3002   /* Build the comparison expression NAME_i COMP_CODE VAL.  */
3003   tree stmt, cond, assert_expr;
3004   edge_iterator ei;
3005   edge e;
3006
3007   cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
3008   assert_expr = build_assert_expr_for (cond, name);
3009
3010   if (loc->e)
3011     {
3012       /* We have been asked to insert the assertion on an edge.  This
3013          is used only by COND_EXPR and SWITCH_EXPR assertions.  */
3014 #if defined ENABLE_CHECKING
3015       gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
3016           || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
3017 #endif
3018
3019       bsi_insert_on_edge (loc->e, assert_expr);
3020       return true;
3021     }
3022
3023   /* Otherwise, we can insert right after LOC->SI iff the
3024      statement must not be the last statement in the block.  */
3025   stmt = bsi_stmt (loc->si);
3026   if (!stmt_ends_bb_p (stmt))
3027     {
3028       bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
3029       return false;
3030     }
3031
3032   /* If STMT must be the last statement in BB, we can only insert new
3033      assertions on the non-abnormal edge out of BB.  Note that since
3034      STMT is not control flow, there may only be one non-abnormal edge
3035      out of BB.  */
3036   FOR_EACH_EDGE (e, ei, loc->bb->succs)
3037     if (!(e->flags & EDGE_ABNORMAL))
3038       {
3039         bsi_insert_on_edge (e, assert_expr);
3040         return true;
3041       }
3042
3043   gcc_unreachable ();
3044 }
3045
3046
3047 /* Process all the insertions registered for every name N_i registered
3048    in NEED_ASSERT_FOR.  The list of assertions to be inserted are
3049    found in ASSERTS_FOR[i].  */
3050
3051 static void
3052 process_assert_insertions (void)
3053 {
3054   unsigned i;
3055   bitmap_iterator bi;
3056   bool update_edges_p = false;
3057   int num_asserts = 0;
3058
3059   if (dump_file && (dump_flags & TDF_DETAILS))
3060     dump_all_asserts (dump_file);
3061
3062   EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
3063     {
3064       assert_locus_t loc = asserts_for[i];
3065       gcc_assert (loc);
3066
3067       while (loc)
3068         {
3069           assert_locus_t next = loc->next;
3070           update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
3071           free (loc);
3072           loc = next;
3073           num_asserts++;
3074         }
3075     }
3076
3077   if (update_edges_p)
3078     bsi_commit_edge_inserts ();
3079
3080   if (dump_file && (dump_flags & TDF_STATS))
3081     fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
3082              num_asserts);
3083 }
3084
3085
3086 /* Traverse the flowgraph looking for conditional jumps to insert range
3087    expressions.  These range expressions are meant to provide information
3088    to optimizations that need to reason in terms of value ranges.  They
3089    will not be expanded into RTL.  For instance, given:
3090
3091    x = ...
3092    y = ...
3093    if (x < y)
3094      y = x - 2;
3095    else
3096      x = y + 3;
3097
3098    this pass will transform the code into:
3099
3100    x = ...
3101    y = ...
3102    if (x < y)
3103     {
3104       x = ASSERT_EXPR <x, x < y>
3105       y = x - 2
3106     }
3107    else
3108     {
3109       y = ASSERT_EXPR <y, x <= y>
3110       x = y + 3
3111     }
3112
3113    The idea is that once copy and constant propagation have run, other
3114    optimizations will be able to determine what ranges of values can 'x'
3115    take in different paths of the code, simply by checking the reaching
3116    definition of 'x'.  */
3117
3118 static void
3119 insert_range_assertions (void)
3120 {
3121   edge e;
3122   edge_iterator ei;
3123   bool update_ssa_p;
3124   
3125   found_in_subgraph = sbitmap_alloc (num_ssa_names);
3126   sbitmap_zero (found_in_subgraph);
3127
3128   blocks_visited = sbitmap_alloc (last_basic_block);
3129   sbitmap_zero (blocks_visited);
3130
3131   need_assert_for = BITMAP_ALLOC (NULL);
3132   asserts_for = XNEWVEC (assert_locus_t, num_ssa_names);
3133   memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t));
3134
3135   calculate_dominance_info (CDI_DOMINATORS);
3136
3137   update_ssa_p = false;
3138   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
3139     if (find_assert_locations (e->dest))
3140       update_ssa_p = true;
3141
3142   if (update_ssa_p)
3143     {
3144       process_assert_insertions ();
3145       update_ssa (TODO_update_ssa_no_phi);
3146     }
3147
3148   if (dump_file && (dump_flags & TDF_DETAILS))
3149     {
3150       fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
3151       dump_function_to_file (current_function_decl, dump_file, dump_flags);
3152     }
3153
3154   sbitmap_free (found_in_subgraph);
3155   free (asserts_for);
3156   BITMAP_FREE (need_assert_for);
3157 }
3158
3159
3160 /* Convert range assertion expressions into the implied copies and
3161    copy propagate away the copies.  Doing the trivial copy propagation
3162    here avoids the need to run the full copy propagation pass after
3163    VRP. 
3164    
3165    FIXME, this will eventually lead to copy propagation removing the
3166    names that had useful range information attached to them.  For
3167    instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
3168    then N_i will have the range [3, +INF].
3169    
3170    However, by converting the assertion into the implied copy
3171    operation N_i = N_j, we will then copy-propagate N_j into the uses
3172    of N_i and lose the range information.  We may want to hold on to
3173    ASSERT_EXPRs a little while longer as the ranges could be used in
3174    things like jump threading.
3175    
3176    The problem with keeping ASSERT_EXPRs around is that passes after
3177    VRP need to handle them appropriately. 
3178
3179    Another approach would be to make the range information a first
3180    class property of the SSA_NAME so that it can be queried from
3181    any pass.  This is made somewhat more complex by the need for
3182    multiple ranges to be associated with one SSA_NAME.  */
3183
3184 static void
3185 remove_range_assertions (void)
3186 {
3187   basic_block bb;
3188   block_stmt_iterator si;
3189
3190   /* Note that the BSI iterator bump happens at the bottom of the
3191      loop and no bump is necessary if we're removing the statement
3192      referenced by the current BSI.  */
3193   FOR_EACH_BB (bb)
3194     for (si = bsi_start (bb); !bsi_end_p (si);)
3195       {
3196         tree stmt = bsi_stmt (si);
3197
3198         if (TREE_CODE (stmt) == MODIFY_EXPR
3199             && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
3200           {
3201             tree rhs = TREE_OPERAND (stmt, 1), var;
3202             tree cond = fold (ASSERT_EXPR_COND (rhs));
3203             use_operand_p use_p;
3204             imm_use_iterator iter;
3205
3206             gcc_assert (cond != boolean_false_node);
3207
3208             /* Propagate the RHS into every use of the LHS.  */
3209             var = ASSERT_EXPR_VAR (rhs);
3210             FOR_EACH_IMM_USE_SAFE (use_p, iter, TREE_OPERAND (stmt, 0))
3211               {
3212                 SET_USE (use_p, var);
3213                 gcc_assert (TREE_CODE (var) == SSA_NAME);
3214               }
3215
3216             /* And finally, remove the copy, it is not needed.  */
3217             bsi_remove (&si, true);
3218           }
3219         else
3220           bsi_next (&si);
3221       }
3222
3223   sbitmap_free (blocks_visited);
3224 }
3225
3226
3227 /* Return true if STMT is interesting for VRP.  */
3228
3229 static bool
3230 stmt_interesting_for_vrp (tree stmt)
3231 {
3232   if (TREE_CODE (stmt) == PHI_NODE
3233       && is_gimple_reg (PHI_RESULT (stmt))
3234       && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
3235           || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
3236     return true;
3237   else if (TREE_CODE (stmt) == MODIFY_EXPR)
3238     {
3239       tree lhs = TREE_OPERAND (stmt, 0);
3240
3241       if (TREE_CODE (lhs) == SSA_NAME
3242           && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
3243               || POINTER_TYPE_P (TREE_TYPE (lhs)))
3244           && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3245         return true;
3246     }
3247   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3248     return true;
3249
3250   return false;
3251 }
3252
3253
3254 /* Initialize local data structures for VRP.  */
3255
3256 static void
3257 vrp_initialize (void)
3258 {
3259   basic_block bb;
3260
3261   vr_value = XNEWVEC (value_range_t *, num_ssa_names);
3262   memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *));
3263
3264   FOR_EACH_BB (bb)
3265     {
3266       block_stmt_iterator si;
3267       tree phi;
3268
3269       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3270         {
3271           if (!stmt_interesting_for_vrp (phi))
3272             {
3273               tree lhs = PHI_RESULT (phi);
3274               set_value_range_to_varying (get_value_range (lhs));
3275               DONT_SIMULATE_AGAIN (phi) = true;
3276             }
3277           else
3278             DONT_SIMULATE_AGAIN (phi) = false;
3279         }
3280
3281       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
3282         {
3283           tree stmt = bsi_stmt (si);
3284
3285           if (!stmt_interesting_for_vrp (stmt))
3286             {
3287               ssa_op_iter i;
3288               tree def;
3289               FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
3290                 set_value_range_to_varying (get_value_range (def));
3291               DONT_SIMULATE_AGAIN (stmt) = true;
3292             }
3293           else
3294             {
3295               DONT_SIMULATE_AGAIN (stmt) = false;
3296             }
3297         }
3298     }
3299 }
3300
3301
3302 /* Visit assignment STMT.  If it produces an interesting range, record
3303    the SSA name in *OUTPUT_P.  */
3304
3305 static enum ssa_prop_result
3306 vrp_visit_assignment (tree stmt, tree *output_p)
3307 {
3308   tree lhs, rhs, def;
3309   ssa_op_iter iter;
3310
3311   lhs = TREE_OPERAND (stmt, 0);
3312   rhs = TREE_OPERAND (stmt, 1);
3313
3314   /* We only keep track of ranges in integral and pointer types.  */
3315   if (TREE_CODE (lhs) == SSA_NAME
3316       && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
3317            /* It is valid to have NULL MIN/MAX values on a type.  See
3318               build_range_type.  */
3319            && TYPE_MIN_VALUE (TREE_TYPE (lhs))
3320            && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
3321           || POINTER_TYPE_P (TREE_TYPE (lhs))))
3322     {
3323       struct loop *l;
3324       value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3325
3326       extract_range_from_expr (&new_vr, rhs);
3327
3328       /* If STMT is inside a loop, we may be able to know something
3329          else about the range of LHS by examining scalar evolution
3330          information.  */
3331       if (current_loops && (l = loop_containing_stmt (stmt)))
3332         adjust_range_with_scev (&new_vr, l, stmt, lhs);
3333
3334       if (update_value_range (lhs, &new_vr))
3335         {
3336           *output_p = lhs;
3337
3338           if (dump_file && (dump_flags & TDF_DETAILS))
3339             {
3340               fprintf (dump_file, "Found new range for ");
3341               print_generic_expr (dump_file, lhs, 0);
3342               fprintf (dump_file, ": ");
3343               dump_value_range (dump_file, &new_vr);
3344               fprintf (dump_file, "\n\n");
3345             }
3346
3347           if (new_vr.type == VR_VARYING)
3348             return SSA_PROP_VARYING;
3349
3350           return SSA_PROP_INTERESTING;
3351         }
3352
3353       return SSA_PROP_NOT_INTERESTING;
3354     }
3355   
3356   /* Every other statement produces no useful ranges.  */
3357   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3358     set_value_range_to_varying (get_value_range (def));
3359
3360   return SSA_PROP_VARYING;
3361 }
3362
3363
3364 /* Compare all the value ranges for names equivalent to VAR with VAL
3365    using comparison code COMP.  Return the same value returned by
3366    compare_range_with_value.  */
3367
3368 static tree
3369 compare_name_with_value (enum tree_code comp, tree var, tree val)
3370 {
3371   bitmap_iterator bi;
3372   unsigned i;
3373   bitmap e;
3374   tree retval, t;
3375   
3376   t = retval = NULL_TREE;
3377
3378   /* Get the set of equivalences for VAR.  */
3379   e = get_value_range (var)->equiv;
3380
3381   /* Add VAR to its own set of equivalences so that VAR's value range
3382      is processed by this loop (otherwise, we would have to replicate
3383      the body of the loop just to check VAR's value range).  */
3384   bitmap_set_bit (e, SSA_NAME_VERSION (var));
3385
3386   EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
3387     {
3388       value_range_t equiv_vr = *(vr_value[i]);
3389
3390       /* If name N_i does not have a valid range, use N_i as its own
3391          range.  This allows us to compare against names that may
3392          have N_i in their ranges.  */
3393       if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
3394         {
3395           equiv_vr.type = VR_RANGE;
3396           equiv_vr.min = ssa_name (i);
3397           equiv_vr.max = ssa_name (i);
3398         }
3399
3400       t = compare_range_with_value (comp, &equiv_vr, val);
3401       if (t)
3402         {
3403           /* All the ranges should compare the same against VAL.  */
3404           gcc_assert (retval == NULL || t == retval);
3405           retval = t;
3406         }
3407     }
3408
3409   /* Remove VAR from its own equivalence set.  */
3410   bitmap_clear_bit (e, SSA_NAME_VERSION (var));
3411
3412   if (retval)
3413     return retval;
3414
3415   /* We couldn't find a non-NULL value for the predicate.  */
3416   return NULL_TREE;
3417 }
3418
3419
3420 /* Given a comparison code COMP and names N1 and N2, compare all the
3421    ranges equivalent to N1 against all the ranges equivalent to N2
3422    to determine the value of N1 COMP N2.  Return the same value
3423    returned by compare_ranges.  */
3424
3425 static tree
3426 compare_names (enum tree_code comp, tree n1, tree n2)
3427 {
3428   tree t, retval;
3429   bitmap e1, e2;
3430   bitmap_iterator bi1, bi2;
3431   unsigned i1, i2;
3432
3433   /* Compare the ranges of every name equivalent to N1 against the
3434      ranges of every name equivalent to N2.  */
3435   e1 = get_value_range (n1)->equiv;
3436   e2 = get_value_range (n2)->equiv;
3437
3438   /* Add N1 and N2 to their own set of equivalences to avoid
3439      duplicating the body of the loop just to check N1 and N2
3440      ranges.  */
3441   bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
3442   bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
3443
3444   /* If the equivalence sets have a common intersection, then the two
3445      names can be compared without checking their ranges.  */
3446   if (bitmap_intersect_p (e1, e2))
3447     {
3448       bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3449       bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3450
3451       return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
3452              ? boolean_true_node
3453              : boolean_false_node;
3454     }
3455
3456   /* Otherwise, compare all the equivalent ranges.  First, add N1 and
3457      N2 to their own set of equivalences to avoid duplicating the body
3458      of the loop just to check N1 and N2 ranges.  */
3459   EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
3460     {
3461       value_range_t vr1 = *(vr_value[i1]);
3462
3463       /* If the range is VARYING or UNDEFINED, use the name itself.  */
3464       if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
3465         {
3466           vr1.type = VR_RANGE;
3467           vr1.min = ssa_name (i1);
3468           vr1.max = ssa_name (i1);
3469         }
3470
3471       t = retval = NULL_TREE;
3472       EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
3473         {
3474           value_range_t vr2 = *(vr_value[i2]);
3475
3476           if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
3477             {
3478               vr2.type = VR_RANGE;
3479               vr2.min = ssa_name (i2);
3480               vr2.max = ssa_name (i2);
3481             }
3482
3483           t = compare_ranges (comp, &vr1, &vr2);
3484           if (t)
3485             {
3486               /* All the ranges in the equivalent sets should compare
3487                  the same.  */
3488               gcc_assert (retval == NULL || t == retval);
3489               retval = t;
3490             }
3491         }
3492
3493       if (retval)
3494         {
3495           bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3496           bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3497           return retval;
3498         }
3499     }
3500
3501   /* None of the equivalent ranges are useful in computing this
3502      comparison.  */
3503   bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3504   bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3505   return NULL_TREE;
3506 }
3507
3508
3509 /* Given a conditional predicate COND, try to determine if COND yields
3510    true or false based on the value ranges of its operands.  Return
3511    BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
3512    BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
3513    NULL if the conditional cannot be evaluated at compile time.
3514
3515    If USE_EQUIV_P is true, the ranges of all the names equivalent with
3516    the operands in COND are used when trying to compute its value.
3517    This is only used during final substitution.  During propagation,
3518    we only check the range of each variable and not its equivalents.  */
3519
3520 tree
3521 vrp_evaluate_conditional (tree cond, bool use_equiv_p)
3522 {
3523   gcc_assert (TREE_CODE (cond) == SSA_NAME
3524               || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
3525
3526   if (TREE_CODE (cond) == SSA_NAME)
3527     {
3528       value_range_t *vr;
3529       tree retval;
3530
3531       if (use_equiv_p)
3532         retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node);
3533       else
3534         {