OSDN Git Service

09c634246ecf2c221fea545ef53773d8c8a13777
[pf3gnuchains/gcc-fork.git] / gcc / tree-vrp.c
1 /* Support routines for Value Range Propagation (VRP).
2    Copyright (C) 2005, 2006, 2007, 2008, 2009 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 3, 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 COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "ggc.h"
26 #include "flags.h"
27 #include "tree.h"
28 #include "basic-block.h"
29 #include "tree-flow.h"
30 #include "tree-pass.h"
31 #include "tree-dump.h"
32 #include "timevar.h"
33 #include "diagnostic.h"
34 #include "toplev.h"
35 #include "intl.h"
36 #include "cfgloop.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-ssa-propagate.h"
39 #include "tree-chrec.h"
40
41
42 /* Set of SSA names found live during the RPO traversal of the function
43    for still active basic-blocks.  */
44 static sbitmap *live;
45
46 /* Return true if the SSA name NAME is live on the edge E.  */
47
48 static bool
49 live_on_edge (edge e, tree name)
50 {
51   return (live[e->dest->index]
52           && TEST_BIT (live[e->dest->index], SSA_NAME_VERSION (name)));
53 }
54
55 /* Local functions.  */
56 static int compare_values (tree val1, tree val2);
57 static int compare_values_warnv (tree val1, tree val2, bool *);
58 static void vrp_meet (value_range_t *, value_range_t *);
59 static tree vrp_evaluate_conditional_warnv_with_ops (enum tree_code,
60                                                      tree, tree, bool, bool *,
61                                                      bool *);
62
63 /* Location information for ASSERT_EXPRs.  Each instance of this
64    structure describes an ASSERT_EXPR for an SSA name.  Since a single
65    SSA name may have more than one assertion associated with it, these
66    locations are kept in a linked list attached to the corresponding
67    SSA name.  */
68 struct assert_locus_d
69 {
70   /* Basic block where the assertion would be inserted.  */
71   basic_block bb;
72
73   /* Some assertions need to be inserted on an edge (e.g., assertions
74      generated by COND_EXPRs).  In those cases, BB will be NULL.  */
75   edge e;
76
77   /* Pointer to the statement that generated this assertion.  */
78   gimple_stmt_iterator si;
79
80   /* Predicate code for the ASSERT_EXPR.  Must be COMPARISON_CLASS_P.  */
81   enum tree_code comp_code;
82
83   /* Value being compared against.  */
84   tree val;
85
86   /* Expression to compare.  */
87   tree expr;
88
89   /* Next node in the linked list.  */
90   struct assert_locus_d *next;
91 };
92
93 typedef struct assert_locus_d *assert_locus_t;
94
95 /* If bit I is present, it means that SSA name N_i has a list of
96    assertions that should be inserted in the IL.  */
97 static bitmap need_assert_for;
98
99 /* Array of locations lists where to insert assertions.  ASSERTS_FOR[I]
100    holds a list of ASSERT_LOCUS_T nodes that describe where
101    ASSERT_EXPRs for SSA name N_I should be inserted.  */
102 static assert_locus_t *asserts_for;
103
104 /* Value range array.  After propagation, VR_VALUE[I] holds the range
105    of values that SSA name N_I may take.  */
106 static value_range_t **vr_value;
107
108 /* For a PHI node which sets SSA name N_I, VR_COUNTS[I] holds the
109    number of executable edges we saw the last time we visited the
110    node.  */
111 static int *vr_phi_edge_counts;
112
113 typedef struct {
114   gimple stmt;
115   tree vec;
116 } switch_update;
117
118 static VEC (edge, heap) *to_remove_edges;
119 DEF_VEC_O(switch_update);
120 DEF_VEC_ALLOC_O(switch_update, heap);
121 static VEC (switch_update, heap) *to_update_switch_stmts;
122
123
124 /* Return the maximum value for TYPEs base type.  */
125
126 static inline tree
127 vrp_val_max (const_tree type)
128 {
129   if (!INTEGRAL_TYPE_P (type))
130     return NULL_TREE;
131
132   /* For integer sub-types the values for the base type are relevant.  */
133   if (TREE_TYPE (type))
134     type = TREE_TYPE (type);
135
136   return TYPE_MAX_VALUE (type);
137 }
138
139 /* Return the minimum value for TYPEs base type.  */
140
141 static inline tree
142 vrp_val_min (const_tree type)
143 {
144   if (!INTEGRAL_TYPE_P (type))
145     return NULL_TREE;
146
147   /* For integer sub-types the values for the base type are relevant.  */
148   if (TREE_TYPE (type))
149     type = TREE_TYPE (type);
150
151   return TYPE_MIN_VALUE (type);
152 }
153
154 /* Return whether VAL is equal to the maximum value of its type.  This
155    will be true for a positive overflow infinity.  We can't do a
156    simple equality comparison with TYPE_MAX_VALUE because C typedefs
157    and Ada subtypes can produce types whose TYPE_MAX_VALUE is not ==
158    to the integer constant with the same value in the type.  */
159
160 static inline bool
161 vrp_val_is_max (const_tree val)
162 {
163   tree type_max = vrp_val_max (TREE_TYPE (val));
164   return (val == type_max
165           || (type_max != NULL_TREE
166               && operand_equal_p (val, type_max, 0)));
167 }
168
169 /* Return whether VAL is equal to the minimum value of its type.  This
170    will be true for a negative overflow infinity.  */
171
172 static inline bool
173 vrp_val_is_min (const_tree val)
174 {
175   tree type_min = vrp_val_min (TREE_TYPE (val));
176   return (val == type_min
177           || (type_min != NULL_TREE
178               && operand_equal_p (val, type_min, 0)));
179 }
180
181
182 /* Return whether TYPE should use an overflow infinity distinct from
183    TYPE_{MIN,MAX}_VALUE.  We use an overflow infinity value to
184    represent a signed overflow during VRP computations.  An infinity
185    is distinct from a half-range, which will go from some number to
186    TYPE_{MIN,MAX}_VALUE.  */
187
188 static inline bool
189 needs_overflow_infinity (const_tree type)
190 {
191   return (INTEGRAL_TYPE_P (type)
192           && !TYPE_OVERFLOW_WRAPS (type)
193           /* Integer sub-types never overflow as they are never
194              operands of arithmetic operators.  */
195           && !(TREE_TYPE (type) && TREE_TYPE (type) != type));
196 }
197
198 /* Return whether TYPE can support our overflow infinity
199    representation: we use the TREE_OVERFLOW flag, which only exists
200    for constants.  If TYPE doesn't support this, we don't optimize
201    cases which would require signed overflow--we drop them to
202    VARYING.  */
203
204 static inline bool
205 supports_overflow_infinity (const_tree type)
206 {
207   tree min = vrp_val_min (type), max = vrp_val_max (type);
208 #ifdef ENABLE_CHECKING
209   gcc_assert (needs_overflow_infinity (type));
210 #endif
211   return (min != NULL_TREE
212           && CONSTANT_CLASS_P (min)
213           && max != NULL_TREE
214           && CONSTANT_CLASS_P (max));
215 }
216
217 /* VAL is the maximum or minimum value of a type.  Return a
218    corresponding overflow infinity.  */
219
220 static inline tree
221 make_overflow_infinity (tree val)
222 {
223 #ifdef ENABLE_CHECKING
224   gcc_assert (val != NULL_TREE && CONSTANT_CLASS_P (val));
225 #endif
226   val = copy_node (val);
227   TREE_OVERFLOW (val) = 1;
228   return val;
229 }
230
231 /* Return a negative overflow infinity for TYPE.  */
232
233 static inline tree
234 negative_overflow_infinity (tree type)
235 {
236 #ifdef ENABLE_CHECKING
237   gcc_assert (supports_overflow_infinity (type));
238 #endif
239   return make_overflow_infinity (vrp_val_min (type));
240 }
241
242 /* Return a positive overflow infinity for TYPE.  */
243
244 static inline tree
245 positive_overflow_infinity (tree type)
246 {
247 #ifdef ENABLE_CHECKING
248   gcc_assert (supports_overflow_infinity (type));
249 #endif
250   return make_overflow_infinity (vrp_val_max (type));
251 }
252
253 /* Return whether VAL is a negative overflow infinity.  */
254
255 static inline bool
256 is_negative_overflow_infinity (const_tree val)
257 {
258   return (needs_overflow_infinity (TREE_TYPE (val))
259           && CONSTANT_CLASS_P (val)
260           && TREE_OVERFLOW (val)
261           && vrp_val_is_min (val));
262 }
263
264 /* Return whether VAL is a positive overflow infinity.  */
265
266 static inline bool
267 is_positive_overflow_infinity (const_tree val)
268 {
269   return (needs_overflow_infinity (TREE_TYPE (val))
270           && CONSTANT_CLASS_P (val)
271           && TREE_OVERFLOW (val)
272           && vrp_val_is_max (val));
273 }
274
275 /* Return whether VAL is a positive or negative overflow infinity.  */
276
277 static inline bool
278 is_overflow_infinity (const_tree val)
279 {
280   return (needs_overflow_infinity (TREE_TYPE (val))
281           && CONSTANT_CLASS_P (val)
282           && TREE_OVERFLOW (val)
283           && (vrp_val_is_min (val) || vrp_val_is_max (val)));
284 }
285
286 /* Return whether STMT has a constant rhs that is_overflow_infinity. */
287
288 static inline bool
289 stmt_overflow_infinity (gimple stmt)
290 {
291   if (is_gimple_assign (stmt)
292       && get_gimple_rhs_class (gimple_assign_rhs_code (stmt)) ==
293       GIMPLE_SINGLE_RHS)
294     return is_overflow_infinity (gimple_assign_rhs1 (stmt));
295   return false;
296 }
297
298 /* If VAL is now an overflow infinity, return VAL.  Otherwise, return
299    the same value with TREE_OVERFLOW clear.  This can be used to avoid
300    confusing a regular value with an overflow value.  */
301
302 static inline tree
303 avoid_overflow_infinity (tree val)
304 {
305   if (!is_overflow_infinity (val))
306     return val;
307
308   if (vrp_val_is_max (val))
309     return vrp_val_max (TREE_TYPE (val));
310   else
311     {
312 #ifdef ENABLE_CHECKING
313       gcc_assert (vrp_val_is_min (val));
314 #endif
315       return vrp_val_min (TREE_TYPE (val));
316     }
317 }
318
319
320 /* Return true if ARG is marked with the nonnull attribute in the
321    current function signature.  */
322
323 static bool
324 nonnull_arg_p (const_tree arg)
325 {
326   tree t, attrs, fntype;
327   unsigned HOST_WIDE_INT arg_num;
328
329   gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg)));
330
331   /* The static chain decl is always non null.  */
332   if (arg == cfun->static_chain_decl)
333     return true;
334
335   fntype = TREE_TYPE (current_function_decl);
336   attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype));
337
338   /* If "nonnull" wasn't specified, we know nothing about the argument.  */
339   if (attrs == NULL_TREE)
340     return false;
341
342   /* If "nonnull" applies to all the arguments, then ARG is non-null.  */
343   if (TREE_VALUE (attrs) == NULL_TREE)
344     return true;
345
346   /* Get the position number for ARG in the function signature.  */
347   for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl);
348        t;
349        t = TREE_CHAIN (t), arg_num++)
350     {
351       if (t == arg)
352         break;
353     }
354
355   gcc_assert (t == arg);
356
357   /* Now see if ARG_NUM is mentioned in the nonnull list.  */
358   for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
359     {
360       if (compare_tree_int (TREE_VALUE (t), arg_num) == 0)
361         return true;
362     }
363
364   return false;
365 }
366
367
368 /* Set value range VR to VR_VARYING.  */
369
370 static inline void
371 set_value_range_to_varying (value_range_t *vr)
372 {
373   vr->type = VR_VARYING;
374   vr->min = vr->max = NULL_TREE;
375   if (vr->equiv)
376     bitmap_clear (vr->equiv);
377 }
378
379
380 /* Set value range VR to {T, MIN, MAX, EQUIV}.  */
381
382 static void
383 set_value_range (value_range_t *vr, enum value_range_type t, tree min,
384                  tree max, bitmap equiv)
385 {
386 #if defined ENABLE_CHECKING
387   /* Check the validity of the range.  */
388   if (t == VR_RANGE || t == VR_ANTI_RANGE)
389     {
390       int cmp;
391
392       gcc_assert (min && max);
393
394       if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
395         gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max));
396
397       cmp = compare_values (min, max);
398       gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
399
400       if (needs_overflow_infinity (TREE_TYPE (min)))
401         gcc_assert (!is_overflow_infinity (min)
402                     || !is_overflow_infinity (max));
403     }
404
405   if (t == VR_UNDEFINED || t == VR_VARYING)
406     gcc_assert (min == NULL_TREE && max == NULL_TREE);
407
408   if (t == VR_UNDEFINED || t == VR_VARYING)
409     gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
410 #endif
411
412   vr->type = t;
413   vr->min = min;
414   vr->max = max;
415
416   /* Since updating the equivalence set involves deep copying the
417      bitmaps, only do it if absolutely necessary.  */
418   if (vr->equiv == NULL
419       && equiv != NULL)
420     vr->equiv = BITMAP_ALLOC (NULL);
421
422   if (equiv != vr->equiv)
423     {
424       if (equiv && !bitmap_empty_p (equiv))
425         bitmap_copy (vr->equiv, equiv);
426       else
427         bitmap_clear (vr->equiv);
428     }
429 }
430
431
432 /* Set value range VR to the canonical form of {T, MIN, MAX, EQUIV}.
433    This means adjusting T, MIN and MAX representing the case of a
434    wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
435    as anti-rage ~[MAX+1, MIN-1].  Likewise for wrapping anti-ranges.
436    In corner cases where MAX+1 or MIN-1 wraps this will fall back
437    to varying.
438    This routine exists to ease canonicalization in the case where we
439    extract ranges from var + CST op limit.  */
440
441 static void
442 set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
443                                   tree min, tree max, bitmap equiv)
444 {
445   /* Nothing to canonicalize for symbolic or unknown or varying ranges.  */
446   if ((t != VR_RANGE
447        && t != VR_ANTI_RANGE)
448       || TREE_CODE (min) != INTEGER_CST
449       || TREE_CODE (max) != INTEGER_CST)
450     {
451       set_value_range (vr, t, min, max, equiv);
452       return;
453     }
454
455   /* Wrong order for min and max, to swap them and the VR type we need
456      to adjust them.  */
457   if (tree_int_cst_lt (max, min))
458     {
459       tree one = build_int_cst (TREE_TYPE (min), 1);
460       tree tmp = int_const_binop (PLUS_EXPR, max, one, 0);
461       max = int_const_binop (MINUS_EXPR, min, one, 0);
462       min = tmp;
463
464       /* There's one corner case, if we had [C+1, C] before we now have
465          that again.  But this represents an empty value range, so drop
466          to varying in this case.  */
467       if (tree_int_cst_lt (max, min))
468         {
469           set_value_range_to_varying (vr);
470           return;
471         }
472
473       t = t == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
474     }
475
476   /* Anti-ranges that can be represented as ranges should be so.  */
477   if (t == VR_ANTI_RANGE)
478     {
479       bool is_min = vrp_val_is_min (min);
480       bool is_max = vrp_val_is_max (max);
481
482       if (is_min && is_max)
483         {
484           /* We cannot deal with empty ranges, drop to varying.  */
485           set_value_range_to_varying (vr);
486           return;
487         }
488       else if (is_min
489                /* As a special exception preserve non-null ranges.  */
490                && !(TYPE_UNSIGNED (TREE_TYPE (min))
491                     && integer_zerop (max)))
492         {
493           tree one = build_int_cst (TREE_TYPE (max), 1);
494           min = int_const_binop (PLUS_EXPR, max, one, 0);
495           max = vrp_val_max (TREE_TYPE (max));
496           t = VR_RANGE;
497         }
498       else if (is_max)
499         {
500           tree one = build_int_cst (TREE_TYPE (min), 1);
501           max = int_const_binop (MINUS_EXPR, min, one, 0);
502           min = vrp_val_min (TREE_TYPE (min));
503           t = VR_RANGE;
504         }
505     }
506
507   set_value_range (vr, t, min, max, equiv);
508 }
509
510 /* Copy value range FROM into value range TO.  */
511
512 static inline void
513 copy_value_range (value_range_t *to, value_range_t *from)
514 {
515   set_value_range (to, from->type, from->min, from->max, from->equiv);
516 }
517
518 /* Set value range VR to a single value.  This function is only called
519    with values we get from statements, and exists to clear the
520    TREE_OVERFLOW flag so that we don't think we have an overflow
521    infinity when we shouldn't.  */
522
523 static inline void
524 set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv)
525 {
526   gcc_assert (is_gimple_min_invariant (val));
527   val = avoid_overflow_infinity (val);
528   set_value_range (vr, VR_RANGE, val, val, equiv);
529 }
530
531 /* Set value range VR to a non-negative range of type TYPE.
532    OVERFLOW_INFINITY indicates whether to use an overflow infinity
533    rather than TYPE_MAX_VALUE; this should be true if we determine
534    that the range is nonnegative based on the assumption that signed
535    overflow does not occur.  */
536
537 static inline void
538 set_value_range_to_nonnegative (value_range_t *vr, tree type,
539                                 bool overflow_infinity)
540 {
541   tree zero;
542
543   if (overflow_infinity && !supports_overflow_infinity (type))
544     {
545       set_value_range_to_varying (vr);
546       return;
547     }
548
549   zero = build_int_cst (type, 0);
550   set_value_range (vr, VR_RANGE, zero,
551                    (overflow_infinity
552                     ? positive_overflow_infinity (type)
553                     : TYPE_MAX_VALUE (type)),
554                    vr->equiv);
555 }
556
557 /* Set value range VR to a non-NULL range of type TYPE.  */
558
559 static inline void
560 set_value_range_to_nonnull (value_range_t *vr, tree type)
561 {
562   tree zero = build_int_cst (type, 0);
563   set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
564 }
565
566
567 /* Set value range VR to a NULL range of type TYPE.  */
568
569 static inline void
570 set_value_range_to_null (value_range_t *vr, tree type)
571 {
572   set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv);
573 }
574
575
576 /* Set value range VR to a range of a truthvalue of type TYPE.  */
577
578 static inline void
579 set_value_range_to_truthvalue (value_range_t *vr, tree type)
580 {
581   if (TYPE_PRECISION (type) == 1)
582     set_value_range_to_varying (vr);
583   else
584     set_value_range (vr, VR_RANGE,
585                      build_int_cst (type, 0), build_int_cst (type, 1),
586                      vr->equiv);
587 }
588
589
590 /* Set value range VR to VR_UNDEFINED.  */
591
592 static inline void
593 set_value_range_to_undefined (value_range_t *vr)
594 {
595   vr->type = VR_UNDEFINED;
596   vr->min = vr->max = NULL_TREE;
597   if (vr->equiv)
598     bitmap_clear (vr->equiv);
599 }
600
601
602 /* If abs (min) < abs (max), set VR to [-max, max], if
603    abs (min) >= abs (max), set VR to [-min, min].  */
604
605 static void
606 abs_extent_range (value_range_t *vr, tree min, tree max)
607 {
608   int cmp;
609
610   gcc_assert (TREE_CODE (min) == INTEGER_CST);
611   gcc_assert (TREE_CODE (max) == INTEGER_CST);
612   gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (min)));
613   gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (min)));
614   min = fold_unary (ABS_EXPR, TREE_TYPE (min), min);
615   max = fold_unary (ABS_EXPR, TREE_TYPE (max), max);
616   if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
617     {
618       set_value_range_to_varying (vr);
619       return;
620     }
621   cmp = compare_values (min, max);
622   if (cmp == -1)
623     min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), max);
624   else if (cmp == 0 || cmp == 1)
625     {
626       max = min;
627       min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), min);
628     }
629   else
630     {
631       set_value_range_to_varying (vr);
632       return;
633     }
634   set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
635 }
636
637
638 /* Return value range information for VAR.  
639
640    If we have no values ranges recorded (ie, VRP is not running), then
641    return NULL.  Otherwise create an empty range if none existed for VAR.  */
642
643 static value_range_t *
644 get_value_range (const_tree var)
645 {
646   value_range_t *vr;
647   tree sym;
648   unsigned ver = SSA_NAME_VERSION (var);
649
650   /* If we have no recorded ranges, then return NULL.  */
651   if (! vr_value)
652     return NULL;
653
654   vr = vr_value[ver];
655   if (vr)
656     return vr;
657
658   /* Create a default value range.  */
659   vr_value[ver] = vr = XCNEW (value_range_t);
660
661   /* Defer allocating the equivalence set.  */
662   vr->equiv = NULL;
663
664   /* If VAR is a default definition, the variable can take any value
665      in VAR's type.  */
666   sym = SSA_NAME_VAR (var);
667   if (SSA_NAME_IS_DEFAULT_DEF (var))
668     {
669       /* Try to use the "nonnull" attribute to create ~[0, 0]
670          anti-ranges for pointers.  Note that this is only valid with
671          default definitions of PARM_DECLs.  */
672       if (TREE_CODE (sym) == PARM_DECL
673           && POINTER_TYPE_P (TREE_TYPE (sym))
674           && nonnull_arg_p (sym))
675         set_value_range_to_nonnull (vr, TREE_TYPE (sym));
676       else
677         set_value_range_to_varying (vr);
678     }
679
680   return vr;
681 }
682
683 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes.  */
684
685 static inline bool
686 vrp_operand_equal_p (const_tree val1, const_tree val2)
687 {
688   if (val1 == val2)
689     return true;
690   if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
691     return false;
692   if (is_overflow_infinity (val1))
693     return is_overflow_infinity (val2);
694   return true;
695 }
696
697 /* Return true, if the bitmaps B1 and B2 are equal.  */
698
699 static inline bool
700 vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
701 {
702   return (b1 == b2
703           || (b1 && b2
704               && bitmap_equal_p (b1, b2)));
705 }
706
707 /* Update the value range and equivalence set for variable VAR to
708    NEW_VR.  Return true if NEW_VR is different from VAR's previous
709    value.
710
711    NOTE: This function assumes that NEW_VR is a temporary value range
712    object created for the sole purpose of updating VAR's range.  The
713    storage used by the equivalence set from NEW_VR will be freed by
714    this function.  Do not call update_value_range when NEW_VR
715    is the range object associated with another SSA name.  */
716
717 static inline bool
718 update_value_range (const_tree var, value_range_t *new_vr)
719 {
720   value_range_t *old_vr;
721   bool is_new;
722
723   /* Update the value range, if necessary.  */
724   old_vr = get_value_range (var);
725   is_new = old_vr->type != new_vr->type
726            || !vrp_operand_equal_p (old_vr->min, new_vr->min)
727            || !vrp_operand_equal_p (old_vr->max, new_vr->max)
728            || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv);
729
730   if (is_new)
731     set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
732                      new_vr->equiv);
733
734   BITMAP_FREE (new_vr->equiv);
735
736   return is_new;
737 }
738
739
740 /* Add VAR and VAR's equivalence set to EQUIV.  This is the central
741    point where equivalence processing can be turned on/off.  */
742
743 static void
744 add_equivalence (bitmap *equiv, const_tree var)
745 {
746   unsigned ver = SSA_NAME_VERSION (var);
747   value_range_t *vr = vr_value[ver];
748
749   if (*equiv == NULL)
750     *equiv = BITMAP_ALLOC (NULL);
751   bitmap_set_bit (*equiv, ver);
752   if (vr && vr->equiv)
753     bitmap_ior_into (*equiv, vr->equiv);
754 }
755
756
757 /* Return true if VR is ~[0, 0].  */
758
759 static inline bool
760 range_is_nonnull (value_range_t *vr)
761 {
762   return vr->type == VR_ANTI_RANGE
763          && integer_zerop (vr->min)
764          && integer_zerop (vr->max);
765 }
766
767
768 /* Return true if VR is [0, 0].  */
769
770 static inline bool
771 range_is_null (value_range_t *vr)
772 {
773   return vr->type == VR_RANGE
774          && integer_zerop (vr->min)
775          && integer_zerop (vr->max);
776 }
777
778
779 /* Return true if value range VR involves at least one symbol.  */
780
781 static inline bool
782 symbolic_range_p (value_range_t *vr)
783 {
784   return (!is_gimple_min_invariant (vr->min)
785           || !is_gimple_min_invariant (vr->max));
786 }
787
788 /* Return true if value range VR uses an overflow infinity.  */
789
790 static inline bool
791 overflow_infinity_range_p (value_range_t *vr)
792 {
793   return (vr->type == VR_RANGE
794           && (is_overflow_infinity (vr->min)
795               || is_overflow_infinity (vr->max)));
796 }
797
798 /* Return false if we can not make a valid comparison based on VR;
799    this will be the case if it uses an overflow infinity and overflow
800    is not undefined (i.e., -fno-strict-overflow is in effect).
801    Otherwise return true, and set *STRICT_OVERFLOW_P to true if VR
802    uses an overflow infinity.  */
803
804 static bool
805 usable_range_p (value_range_t *vr, bool *strict_overflow_p)
806 {
807   gcc_assert (vr->type == VR_RANGE);
808   if (is_overflow_infinity (vr->min))
809     {
810       *strict_overflow_p = true;
811       if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->min)))
812         return false;
813     }
814   if (is_overflow_infinity (vr->max))
815     {
816       *strict_overflow_p = true;
817       if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->max)))
818         return false;
819     }
820   return true;
821 }
822
823
824 /* Like tree_expr_nonnegative_warnv_p, but this function uses value
825    ranges obtained so far.  */
826
827 static bool
828 vrp_expr_computes_nonnegative (tree expr, bool *strict_overflow_p)
829 {
830   return (tree_expr_nonnegative_warnv_p (expr, strict_overflow_p)
831           || (TREE_CODE (expr) == SSA_NAME
832               && ssa_name_nonnegative_p (expr)));
833 }
834
835 /* Return true if the result of assignment STMT is know to be non-negative.
836    If the return value is based on the assumption that signed overflow is
837    undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
838    *STRICT_OVERFLOW_P.*/
839
840 static bool
841 gimple_assign_nonnegative_warnv_p (gimple stmt, bool *strict_overflow_p)
842 {
843   enum tree_code code = gimple_assign_rhs_code (stmt);
844   switch (get_gimple_rhs_class (code))
845     {
846     case GIMPLE_UNARY_RHS:
847       return tree_unary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt),
848                                              gimple_expr_type (stmt),
849                                              gimple_assign_rhs1 (stmt),
850                                              strict_overflow_p);
851     case GIMPLE_BINARY_RHS:
852       return tree_binary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt),
853                                               gimple_expr_type (stmt),
854                                               gimple_assign_rhs1 (stmt),
855                                               gimple_assign_rhs2 (stmt),
856                                               strict_overflow_p);
857     case GIMPLE_SINGLE_RHS:
858       return tree_single_nonnegative_warnv_p (gimple_assign_rhs1 (stmt),
859                                               strict_overflow_p);
860     case GIMPLE_INVALID_RHS:
861       gcc_unreachable ();
862     default:
863       gcc_unreachable ();
864     }
865 }
866
867 /* Return true if return value of call STMT is know to be non-negative.
868    If the return value is based on the assumption that signed overflow is
869    undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
870    *STRICT_OVERFLOW_P.*/
871
872 static bool
873 gimple_call_nonnegative_warnv_p (gimple stmt, bool *strict_overflow_p)
874 {
875   tree arg0 = gimple_call_num_args (stmt) > 0 ?
876     gimple_call_arg (stmt, 0) : NULL_TREE;
877   tree arg1 = gimple_call_num_args (stmt) > 1 ?
878     gimple_call_arg (stmt, 1) : NULL_TREE;
879
880   return tree_call_nonnegative_warnv_p (gimple_expr_type (stmt),
881                                         gimple_call_fndecl (stmt),
882                                         arg0,
883                                         arg1,
884                                         strict_overflow_p);
885 }
886
887 /* Return true if STMT is know to to compute a non-negative value.
888    If the return value is based on the assumption that signed overflow is
889    undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
890    *STRICT_OVERFLOW_P.*/
891
892 static bool
893 gimple_stmt_nonnegative_warnv_p (gimple stmt, bool *strict_overflow_p)
894 {
895   switch (gimple_code (stmt))
896     {
897     case GIMPLE_ASSIGN:
898       return gimple_assign_nonnegative_warnv_p (stmt, strict_overflow_p);
899     case GIMPLE_CALL:
900       return gimple_call_nonnegative_warnv_p (stmt, strict_overflow_p);
901     default:
902       gcc_unreachable ();
903     }
904 }
905
906 /* Return true if the result of assignment STMT is know to be non-zero.
907    If the return value is based on the assumption that signed overflow is
908    undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
909    *STRICT_OVERFLOW_P.*/
910
911 static bool
912 gimple_assign_nonzero_warnv_p (gimple stmt, bool *strict_overflow_p)
913 {
914   enum tree_code code = gimple_assign_rhs_code (stmt);
915   switch (get_gimple_rhs_class (code))
916     {
917     case GIMPLE_UNARY_RHS:
918       return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt),
919                                          gimple_expr_type (stmt),
920                                          gimple_assign_rhs1 (stmt),
921                                          strict_overflow_p);
922     case GIMPLE_BINARY_RHS:
923       return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt),
924                                           gimple_expr_type (stmt),
925                                           gimple_assign_rhs1 (stmt),
926                                           gimple_assign_rhs2 (stmt),
927                                           strict_overflow_p);
928     case GIMPLE_SINGLE_RHS:
929       return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt),
930                                           strict_overflow_p);
931     case GIMPLE_INVALID_RHS:
932       gcc_unreachable ();
933     default:
934       gcc_unreachable ();
935     }
936 }
937
938 /* Return true if STMT is know to to compute a non-zero value.
939    If the return value is based on the assumption that signed overflow is
940    undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
941    *STRICT_OVERFLOW_P.*/
942
943 static bool
944 gimple_stmt_nonzero_warnv_p (gimple stmt, bool *strict_overflow_p)
945 {
946   switch (gimple_code (stmt))
947     {
948     case GIMPLE_ASSIGN:
949       return gimple_assign_nonzero_warnv_p (stmt, strict_overflow_p);
950     case GIMPLE_CALL:
951       return gimple_alloca_call_p (stmt);
952     default:
953       gcc_unreachable ();
954     }
955 }
956
957 /* Like tree_expr_nonzero_warnv_p, but this function uses value ranges
958    obtained so far.  */
959
960 static bool
961 vrp_stmt_computes_nonzero (gimple stmt, bool *strict_overflow_p)
962 {
963   if (gimple_stmt_nonzero_warnv_p (stmt, strict_overflow_p))
964     return true;
965
966   /* If we have an expression of the form &X->a, then the expression
967      is nonnull if X is nonnull.  */
968   if (is_gimple_assign (stmt)
969       && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
970     {
971       tree expr = gimple_assign_rhs1 (stmt);
972       tree base = get_base_address (TREE_OPERAND (expr, 0));
973
974       if (base != NULL_TREE
975           && TREE_CODE (base) == INDIRECT_REF
976           && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
977         {
978           value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
979           if (range_is_nonnull (vr))
980             return true;
981         }
982     }
983
984   return false;
985 }
986
987 /* Returns true if EXPR is a valid value (as expected by compare_values) --
988    a gimple invariant, or SSA_NAME +- CST.  */
989
990 static bool
991 valid_value_p (tree expr)
992 {
993   if (TREE_CODE (expr) == SSA_NAME)
994     return true;
995
996   if (TREE_CODE (expr) == PLUS_EXPR
997       || TREE_CODE (expr) == MINUS_EXPR)
998     return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
999             && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST);
1000   
1001   return is_gimple_min_invariant (expr);
1002 }
1003
1004 /* Return 
1005    1 if VAL < VAL2
1006    0 if !(VAL < VAL2)
1007    -2 if those are incomparable.  */
1008 static inline int
1009 operand_less_p (tree val, tree val2)
1010 {
1011   /* LT is folded faster than GE and others.  Inline the common case.  */
1012   if (TREE_CODE (val) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST)
1013     {
1014       if (TYPE_UNSIGNED (TREE_TYPE (val)))
1015         return INT_CST_LT_UNSIGNED (val, val2);
1016       else
1017         {
1018           if (INT_CST_LT (val, val2))
1019             return 1;
1020         }
1021     }
1022   else
1023     {
1024       tree tcmp;
1025
1026       fold_defer_overflow_warnings ();
1027
1028       tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2);
1029
1030       fold_undefer_and_ignore_overflow_warnings ();
1031
1032       if (!tcmp
1033           || TREE_CODE (tcmp) != INTEGER_CST)
1034         return -2;
1035
1036       if (!integer_zerop (tcmp))
1037         return 1;
1038     }
1039
1040   /* val >= val2, not considering overflow infinity.  */
1041   if (is_negative_overflow_infinity (val))
1042     return is_negative_overflow_infinity (val2) ? 0 : 1;
1043   else if (is_positive_overflow_infinity (val2))
1044     return is_positive_overflow_infinity (val) ? 0 : 1;
1045
1046   return 0;
1047 }
1048
1049 /* Compare two values VAL1 and VAL2.  Return
1050    
1051         -2 if VAL1 and VAL2 cannot be compared at compile-time,
1052         -1 if VAL1 < VAL2,
1053          0 if VAL1 == VAL2,
1054         +1 if VAL1 > VAL2, and
1055         +2 if VAL1 != VAL2
1056
1057    This is similar to tree_int_cst_compare but supports pointer values
1058    and values that cannot be compared at compile time.
1059
1060    If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to
1061    true if the return value is only valid if we assume that signed
1062    overflow is undefined.  */
1063
1064 static int
1065 compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p)
1066 {
1067   if (val1 == val2)
1068     return 0;
1069
1070   /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
1071      both integers.  */
1072   gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
1073               == POINTER_TYPE_P (TREE_TYPE (val2)));
1074   /* Convert the two values into the same type.  This is needed because
1075      sizetype causes sign extension even for unsigned types.  */
1076   val2 = fold_convert (TREE_TYPE (val1), val2);
1077   STRIP_USELESS_TYPE_CONVERSION (val2);
1078
1079   if ((TREE_CODE (val1) == SSA_NAME
1080        || TREE_CODE (val1) == PLUS_EXPR
1081        || TREE_CODE (val1) == MINUS_EXPR)
1082       && (TREE_CODE (val2) == SSA_NAME
1083           || TREE_CODE (val2) == PLUS_EXPR
1084           || TREE_CODE (val2) == MINUS_EXPR))
1085     {
1086       tree n1, c1, n2, c2;
1087       enum tree_code code1, code2;
1088   
1089       /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
1090          return -1 or +1 accordingly.  If VAL1 and VAL2 don't use the
1091          same name, return -2.  */
1092       if (TREE_CODE (val1) == SSA_NAME)
1093         {
1094           code1 = SSA_NAME;
1095           n1 = val1;
1096           c1 = NULL_TREE;
1097         }
1098       else
1099         {
1100           code1 = TREE_CODE (val1);
1101           n1 = TREE_OPERAND (val1, 0);
1102           c1 = TREE_OPERAND (val1, 1);
1103           if (tree_int_cst_sgn (c1) == -1)
1104             {
1105               if (is_negative_overflow_infinity (c1))
1106                 return -2;
1107               c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1);
1108               if (!c1)
1109                 return -2;
1110               code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
1111             }
1112         }
1113
1114       if (TREE_CODE (val2) == SSA_NAME)
1115         {
1116           code2 = SSA_NAME;
1117           n2 = val2;
1118           c2 = NULL_TREE;
1119         }
1120       else
1121         {
1122           code2 = TREE_CODE (val2);
1123           n2 = TREE_OPERAND (val2, 0);
1124           c2 = TREE_OPERAND (val2, 1);
1125           if (tree_int_cst_sgn (c2) == -1)
1126             {
1127               if (is_negative_overflow_infinity (c2))
1128                 return -2;
1129               c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2);
1130               if (!c2)
1131                 return -2;
1132               code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
1133             }
1134         }
1135
1136       /* Both values must use the same name.  */
1137       if (n1 != n2)
1138         return -2;
1139
1140       if (code1 == SSA_NAME
1141           && code2 == SSA_NAME)
1142         /* NAME == NAME  */
1143         return 0;
1144
1145       /* If overflow is defined we cannot simplify more.  */
1146       if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
1147         return -2;
1148
1149       if (strict_overflow_p != NULL
1150           && (code1 == SSA_NAME || !TREE_NO_WARNING (val1))
1151           && (code2 == SSA_NAME || !TREE_NO_WARNING (val2)))
1152         *strict_overflow_p = true;
1153
1154       if (code1 == SSA_NAME)
1155         {
1156           if (code2 == PLUS_EXPR)
1157             /* NAME < NAME + CST  */
1158             return -1;
1159           else if (code2 == MINUS_EXPR)
1160             /* NAME > NAME - CST  */
1161             return 1;
1162         }
1163       else if (code1 == PLUS_EXPR)
1164         {
1165           if (code2 == SSA_NAME)
1166             /* NAME + CST > NAME  */
1167             return 1;
1168           else if (code2 == PLUS_EXPR)
1169             /* NAME + CST1 > NAME + CST2, if CST1 > CST2  */
1170             return compare_values_warnv (c1, c2, strict_overflow_p);
1171           else if (code2 == MINUS_EXPR)
1172             /* NAME + CST1 > NAME - CST2  */
1173             return 1;
1174         }
1175       else if (code1 == MINUS_EXPR)
1176         {
1177           if (code2 == SSA_NAME)
1178             /* NAME - CST < NAME  */
1179             return -1;
1180           else if (code2 == PLUS_EXPR)
1181             /* NAME - CST1 < NAME + CST2  */
1182             return -1;
1183           else if (code2 == MINUS_EXPR)
1184             /* NAME - CST1 > NAME - CST2, if CST1 < CST2.  Notice that
1185                C1 and C2 are swapped in the call to compare_values.  */
1186             return compare_values_warnv (c2, c1, strict_overflow_p);
1187         }
1188
1189       gcc_unreachable ();
1190     }
1191
1192   /* We cannot compare non-constants.  */
1193   if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
1194     return -2;
1195
1196   if (!POINTER_TYPE_P (TREE_TYPE (val1)))
1197     {
1198       /* We cannot compare overflowed values, except for overflow
1199          infinities.  */
1200       if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
1201         {
1202           if (strict_overflow_p != NULL)
1203             *strict_overflow_p = true;
1204           if (is_negative_overflow_infinity (val1))
1205             return is_negative_overflow_infinity (val2) ? 0 : -1;
1206           else if (is_negative_overflow_infinity (val2))
1207             return 1;
1208           else if (is_positive_overflow_infinity (val1))
1209             return is_positive_overflow_infinity (val2) ? 0 : 1;
1210           else if (is_positive_overflow_infinity (val2))
1211             return -1;
1212           return -2;
1213         }
1214
1215       return tree_int_cst_compare (val1, val2);
1216     }
1217   else
1218     {
1219       tree t;
1220
1221       /* First see if VAL1 and VAL2 are not the same.  */
1222       if (val1 == val2 || operand_equal_p (val1, val2, 0))
1223         return 0;
1224       
1225       /* If VAL1 is a lower address than VAL2, return -1.  */
1226       if (operand_less_p (val1, val2) == 1)
1227         return -1;
1228
1229       /* If VAL1 is a higher address than VAL2, return +1.  */
1230       if (operand_less_p (val2, val1) == 1)
1231         return 1;
1232
1233       /* If VAL1 is different than VAL2, return +2.
1234          For integer constants we either have already returned -1 or 1
1235          or they are equivalent.  We still might succeed in proving
1236          something about non-trivial operands.  */
1237       if (TREE_CODE (val1) != INTEGER_CST
1238           || TREE_CODE (val2) != INTEGER_CST)
1239         {
1240           t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2);
1241           if (t && integer_onep (t))
1242             return 2;
1243         }
1244
1245       return -2;
1246     }
1247 }
1248
1249 /* Compare values like compare_values_warnv, but treat comparisons of
1250    nonconstants which rely on undefined overflow as incomparable.  */
1251
1252 static int
1253 compare_values (tree val1, tree val2)
1254 {
1255   bool sop;
1256   int ret;
1257
1258   sop = false;
1259   ret = compare_values_warnv (val1, val2, &sop);
1260   if (sop
1261       && (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)))
1262     ret = -2;
1263   return ret;
1264 }
1265
1266
1267 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
1268           0 if VAL is not inside VR,
1269          -2 if we cannot tell either way.
1270
1271    FIXME, the current semantics of this functions are a bit quirky
1272           when taken in the context of VRP.  In here we do not care
1273           about VR's type.  If VR is the anti-range ~[3, 5] the call
1274           value_inside_range (4, VR) will return 1.
1275
1276           This is counter-intuitive in a strict sense, but the callers
1277           currently expect this.  They are calling the function
1278           merely to determine whether VR->MIN <= VAL <= VR->MAX.  The
1279           callers are applying the VR_RANGE/VR_ANTI_RANGE semantics
1280           themselves.
1281
1282           This also applies to value_ranges_intersect_p and
1283           range_includes_zero_p.  The semantics of VR_RANGE and
1284           VR_ANTI_RANGE should be encoded here, but that also means
1285           adapting the users of these functions to the new semantics.  
1286
1287    Benchmark compile/20001226-1.c compilation time after changing this
1288    function.  */
1289
1290 static inline int
1291 value_inside_range (tree val, value_range_t * vr)
1292 {
1293   int cmp1, cmp2;
1294
1295   cmp1 = operand_less_p (val, vr->min);
1296   if (cmp1 == -2)
1297     return -2;
1298   if (cmp1 == 1)
1299     return 0;
1300
1301   cmp2 = operand_less_p (vr->max, val);
1302   if (cmp2 == -2)
1303     return -2;
1304
1305   return !cmp2;
1306 }
1307
1308
1309 /* Return true if value ranges VR0 and VR1 have a non-empty
1310    intersection.  
1311    
1312    Benchmark compile/20001226-1.c compilation time after changing this
1313    function.
1314    */
1315
1316 static inline bool
1317 value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
1318 {
1319   /* The value ranges do not intersect if the maximum of the first range is
1320      less than the minimum of the second range or vice versa.
1321      When those relations are unknown, we can't do any better.  */
1322   if (operand_less_p (vr0->max, vr1->min) != 0)
1323     return false;
1324   if (operand_less_p (vr1->max, vr0->min) != 0)
1325     return false;
1326   return true;
1327 }
1328
1329
1330 /* Return true if VR includes the value zero, false otherwise.  FIXME,
1331    currently this will return false for an anti-range like ~[-4, 3].
1332    This will be wrong when the semantics of value_inside_range are
1333    modified (currently the users of this function expect these
1334    semantics).  */
1335
1336 static inline bool
1337 range_includes_zero_p (value_range_t *vr)
1338 {
1339   tree zero;
1340
1341   gcc_assert (vr->type != VR_UNDEFINED
1342               && vr->type != VR_VARYING
1343               && !symbolic_range_p (vr));
1344
1345   zero = build_int_cst (TREE_TYPE (vr->min), 0);
1346   return (value_inside_range (zero, vr) == 1);
1347 }
1348
1349 /* Return true if T, an SSA_NAME, is known to be nonnegative.  Return
1350    false otherwise or if no value range information is available.  */
1351
1352 bool
1353 ssa_name_nonnegative_p (const_tree t)
1354 {
1355   value_range_t *vr = get_value_range (t);
1356
1357   if (!vr)
1358     return false;
1359
1360   /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
1361      which would return a useful value should be encoded as a VR_RANGE.  */
1362   if (vr->type == VR_RANGE)
1363     {
1364       int result = compare_values (vr->min, integer_zero_node);
1365
1366       return (result == 0 || result == 1);
1367     }
1368   return false;
1369 }
1370
1371 /* If OP has a value range with a single constant value return that,
1372    otherwise return NULL_TREE.  This returns OP itself if OP is a
1373    constant.  */
1374
1375 static tree
1376 op_with_constant_singleton_value_range (tree op)
1377 {
1378   value_range_t *vr;
1379
1380   if (is_gimple_min_invariant (op))
1381     return op;
1382
1383   if (TREE_CODE (op) != SSA_NAME)
1384     return NULL_TREE;
1385
1386   vr = get_value_range (op);
1387   if (vr->type == VR_RANGE
1388       && operand_equal_p (vr->min, vr->max, 0)
1389       && is_gimple_min_invariant (vr->min))
1390     return vr->min;
1391
1392   return NULL_TREE;
1393 }
1394
1395
1396 /* Extract value range information from an ASSERT_EXPR EXPR and store
1397    it in *VR_P.  */
1398
1399 static void
1400 extract_range_from_assert (value_range_t *vr_p, tree expr)
1401 {
1402   tree var, cond, limit, min, max, type;
1403   value_range_t *var_vr, *limit_vr;
1404   enum tree_code cond_code;
1405
1406   var = ASSERT_EXPR_VAR (expr);
1407   cond = ASSERT_EXPR_COND (expr);
1408
1409   gcc_assert (COMPARISON_CLASS_P (cond));
1410
1411   /* Find VAR in the ASSERT_EXPR conditional.  */
1412   if (var == TREE_OPERAND (cond, 0)
1413       || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
1414       || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
1415     {
1416       /* If the predicate is of the form VAR COMP LIMIT, then we just
1417          take LIMIT from the RHS and use the same comparison code.  */
1418       cond_code = TREE_CODE (cond);
1419       limit = TREE_OPERAND (cond, 1);
1420       cond = TREE_OPERAND (cond, 0);
1421     }
1422   else
1423     {
1424       /* If the predicate is of the form LIMIT COMP VAR, then we need
1425          to flip around the comparison code to create the proper range
1426          for VAR.  */
1427       cond_code = swap_tree_comparison (TREE_CODE (cond));
1428       limit = TREE_OPERAND (cond, 0);
1429       cond = TREE_OPERAND (cond, 1);
1430     }
1431
1432   limit = avoid_overflow_infinity (limit);
1433
1434   type = TREE_TYPE (limit);
1435   gcc_assert (limit != var);
1436
1437   /* For pointer arithmetic, we only keep track of pointer equality
1438      and inequality.  */
1439   if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
1440     {
1441       set_value_range_to_varying (vr_p);
1442       return;
1443     }
1444
1445   /* If LIMIT is another SSA name and LIMIT has a range of its own,
1446      try to use LIMIT's range to avoid creating symbolic ranges
1447      unnecessarily. */
1448   limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
1449
1450   /* LIMIT's range is only interesting if it has any useful information.  */
1451   if (limit_vr
1452       && (limit_vr->type == VR_UNDEFINED
1453           || limit_vr->type == VR_VARYING
1454           || symbolic_range_p (limit_vr)))
1455     limit_vr = NULL;
1456
1457   /* Initially, the new range has the same set of equivalences of
1458      VAR's range.  This will be revised before returning the final
1459      value.  Since assertions may be chained via mutually exclusive
1460      predicates, we will need to trim the set of equivalences before
1461      we are done.  */
1462   gcc_assert (vr_p->equiv == NULL);
1463   add_equivalence (&vr_p->equiv, var);
1464
1465   /* Extract a new range based on the asserted comparison for VAR and
1466      LIMIT's value range.  Notice that if LIMIT has an anti-range, we
1467      will only use it for equality comparisons (EQ_EXPR).  For any
1468      other kind of assertion, we cannot derive a range from LIMIT's
1469      anti-range that can be used to describe the new range.  For
1470      instance, ASSERT_EXPR <x_2, x_2 <= b_4>.  If b_4 is ~[2, 10],
1471      then b_4 takes on the ranges [-INF, 1] and [11, +INF].  There is
1472      no single range for x_2 that could describe LE_EXPR, so we might
1473      as well build the range [b_4, +INF] for it.
1474      One special case we handle is extracting a range from a
1475      range test encoded as (unsigned)var + CST <= limit.  */
1476   if (TREE_CODE (cond) == NOP_EXPR
1477       || TREE_CODE (cond) == PLUS_EXPR)
1478     {
1479       if (TREE_CODE (cond) == PLUS_EXPR)
1480         {
1481           min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (cond, 1)),
1482                              TREE_OPERAND (cond, 1));
1483           max = int_const_binop (PLUS_EXPR, limit, min, 0);
1484           cond = TREE_OPERAND (cond, 0);
1485         }
1486       else
1487         {
1488           min = build_int_cst (TREE_TYPE (var), 0);
1489           max = limit;
1490         }
1491
1492       /* Make sure to not set TREE_OVERFLOW on the final type
1493          conversion.  We are willingly interpreting large positive
1494          unsigned values as negative singed values here.  */
1495       min = force_fit_type_double (TREE_TYPE (var), TREE_INT_CST_LOW (min),
1496                                    TREE_INT_CST_HIGH (min), 0, false);
1497       max = force_fit_type_double (TREE_TYPE (var), TREE_INT_CST_LOW (max),
1498                                    TREE_INT_CST_HIGH (max), 0, false);
1499
1500       /* We can transform a max, min range to an anti-range or
1501          vice-versa.  Use set_and_canonicalize_value_range which does
1502          this for us.  */
1503       if (cond_code == LE_EXPR)
1504         set_and_canonicalize_value_range (vr_p, VR_RANGE,
1505                                           min, max, vr_p->equiv);
1506       else if (cond_code == GT_EXPR)
1507         set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
1508                                           min, max, vr_p->equiv);
1509       else
1510         gcc_unreachable ();
1511     }
1512   else if (cond_code == EQ_EXPR)
1513     {
1514       enum value_range_type range_type;
1515
1516       if (limit_vr)
1517         {
1518           range_type = limit_vr->type;
1519           min = limit_vr->min;
1520           max = limit_vr->max;
1521         }
1522       else
1523         {
1524           range_type = VR_RANGE;
1525           min = limit;
1526           max = limit;
1527         }
1528
1529       set_value_range (vr_p, range_type, min, max, vr_p->equiv);
1530
1531       /* When asserting the equality VAR == LIMIT and LIMIT is another
1532          SSA name, the new range will also inherit the equivalence set
1533          from LIMIT.  */
1534       if (TREE_CODE (limit) == SSA_NAME)
1535         add_equivalence (&vr_p->equiv, limit);
1536     }
1537   else if (cond_code == NE_EXPR)
1538     {
1539       /* As described above, when LIMIT's range is an anti-range and
1540          this assertion is an inequality (NE_EXPR), then we cannot
1541          derive anything from the anti-range.  For instance, if
1542          LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
1543          not imply that VAR's range is [0, 0].  So, in the case of
1544          anti-ranges, we just assert the inequality using LIMIT and
1545          not its anti-range.
1546
1547          If LIMIT_VR is a range, we can only use it to build a new
1548          anti-range if LIMIT_VR is a single-valued range.  For
1549          instance, if LIMIT_VR is [0, 1], the predicate
1550          VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
1551          Rather, it means that for value 0 VAR should be ~[0, 0]
1552          and for value 1, VAR should be ~[1, 1].  We cannot
1553          represent these ranges.
1554
1555          The only situation in which we can build a valid
1556          anti-range is when LIMIT_VR is a single-valued range
1557          (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX).  In that case, 
1558          build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX].  */
1559       if (limit_vr
1560           && limit_vr->type == VR_RANGE
1561           && compare_values (limit_vr->min, limit_vr->max) == 0)
1562         {
1563           min = limit_vr->min;
1564           max = limit_vr->max;
1565         }
1566       else
1567         {
1568           /* In any other case, we cannot use LIMIT's range to build a
1569              valid anti-range.  */
1570           min = max = limit;
1571         }
1572
1573       /* If MIN and MAX cover the whole range for their type, then
1574          just use the original LIMIT.  */
1575       if (INTEGRAL_TYPE_P (type)
1576           && vrp_val_is_min (min)
1577           && vrp_val_is_max (max))
1578         min = max = limit;
1579
1580       set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
1581     }
1582   else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
1583     {
1584       min = TYPE_MIN_VALUE (type);
1585
1586       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
1587         max = limit;
1588       else
1589         {
1590           /* If LIMIT_VR is of the form [N1, N2], we need to build the
1591              range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
1592              LT_EXPR.  */
1593           max = limit_vr->max;
1594         }
1595
1596       /* If the maximum value forces us to be out of bounds, simply punt.
1597          It would be pointless to try and do anything more since this
1598          all should be optimized away above us.  */
1599       if ((cond_code == LT_EXPR
1600            && compare_values (max, min) == 0)
1601           || (CONSTANT_CLASS_P (max) && TREE_OVERFLOW (max)))
1602         set_value_range_to_varying (vr_p);
1603       else
1604         {
1605           /* For LT_EXPR, we create the range [MIN, MAX - 1].  */
1606           if (cond_code == LT_EXPR)
1607             {
1608               tree one = build_int_cst (type, 1);
1609               max = fold_build2 (MINUS_EXPR, type, max, one);
1610               if (EXPR_P (max))
1611                 TREE_NO_WARNING (max) = 1;
1612             }
1613
1614           set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1615         }
1616     }
1617   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
1618     {
1619       max = TYPE_MAX_VALUE (type);
1620
1621       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
1622         min = limit;
1623       else
1624         {
1625           /* If LIMIT_VR is of the form [N1, N2], we need to build the
1626              range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
1627              GT_EXPR.  */
1628           min = limit_vr->min;
1629         }
1630
1631       /* If the minimum value forces us to be out of bounds, simply punt.
1632          It would be pointless to try and do anything more since this
1633          all should be optimized away above us.  */
1634       if ((cond_code == GT_EXPR
1635            && compare_values (min, max) == 0)
1636           || (CONSTANT_CLASS_P (min) && TREE_OVERFLOW (min)))
1637         set_value_range_to_varying (vr_p);
1638       else
1639         {
1640           /* For GT_EXPR, we create the range [MIN + 1, MAX].  */
1641           if (cond_code == GT_EXPR)
1642             {
1643               tree one = build_int_cst (type, 1);
1644               min = fold_build2 (PLUS_EXPR, type, min, one);
1645               if (EXPR_P (min))
1646                 TREE_NO_WARNING (min) = 1;
1647             }
1648
1649           set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1650         }
1651     }
1652   else
1653     gcc_unreachable ();
1654
1655   /* If VAR already had a known range, it may happen that the new
1656      range we have computed and VAR's range are not compatible.  For
1657      instance,
1658
1659         if (p_5 == NULL)
1660           p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
1661           x_7 = p_6->fld;
1662           p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
1663
1664      While the above comes from a faulty program, it will cause an ICE
1665      later because p_8 and p_6 will have incompatible ranges and at
1666      the same time will be considered equivalent.  A similar situation
1667      would arise from
1668
1669         if (i_5 > 10)
1670           i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
1671           if (i_5 < 5)
1672             i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
1673
1674      Again i_6 and i_7 will have incompatible ranges.  It would be
1675      pointless to try and do anything with i_7's range because
1676      anything dominated by 'if (i_5 < 5)' will be optimized away.
1677      Note, due to the wa in which simulation proceeds, the statement
1678      i_7 = ASSERT_EXPR <...> we would never be visited because the
1679      conditional 'if (i_5 < 5)' always evaluates to false.  However,
1680      this extra check does not hurt and may protect against future
1681      changes to VRP that may get into a situation similar to the
1682      NULL pointer dereference example.
1683
1684      Note that these compatibility tests are only needed when dealing
1685      with ranges or a mix of range and anti-range.  If VAR_VR and VR_P
1686      are both anti-ranges, they will always be compatible, because two
1687      anti-ranges will always have a non-empty intersection.  */
1688
1689   var_vr = get_value_range (var);
1690
1691   /* We may need to make adjustments when VR_P and VAR_VR are numeric
1692      ranges or anti-ranges.  */
1693   if (vr_p->type == VR_VARYING
1694       || vr_p->type == VR_UNDEFINED
1695       || var_vr->type == VR_VARYING
1696       || var_vr->type == VR_UNDEFINED
1697       || symbolic_range_p (vr_p)
1698       || symbolic_range_p (var_vr))
1699     return;
1700
1701   if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
1702     {
1703       /* If the two ranges have a non-empty intersection, we can
1704          refine the resulting range.  Since the assert expression
1705          creates an equivalency and at the same time it asserts a
1706          predicate, we can take the intersection of the two ranges to
1707          get better precision.  */
1708       if (value_ranges_intersect_p (var_vr, vr_p))
1709         {
1710           /* Use the larger of the two minimums.  */
1711           if (compare_values (vr_p->min, var_vr->min) == -1)
1712             min = var_vr->min;
1713           else
1714             min = vr_p->min;
1715
1716           /* Use the smaller of the two maximums.  */
1717           if (compare_values (vr_p->max, var_vr->max) == 1)
1718             max = var_vr->max;
1719           else
1720             max = vr_p->max;
1721
1722           set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
1723         }
1724       else
1725         {
1726           /* The two ranges do not intersect, set the new range to
1727              VARYING, because we will not be able to do anything
1728              meaningful with it.  */
1729           set_value_range_to_varying (vr_p);
1730         }
1731     }
1732   else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
1733            || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
1734     {
1735       /* A range and an anti-range will cancel each other only if
1736          their ends are the same.  For instance, in the example above,
1737          p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
1738          so VR_P should be set to VR_VARYING.  */
1739       if (compare_values (var_vr->min, vr_p->min) == 0
1740           && compare_values (var_vr->max, vr_p->max) == 0)
1741         set_value_range_to_varying (vr_p);
1742       else
1743         {
1744           tree min, max, anti_min, anti_max, real_min, real_max;
1745           int cmp;
1746
1747           /* We want to compute the logical AND of the two ranges;
1748              there are three cases to consider.
1749
1750
1751              1. The VR_ANTI_RANGE range is completely within the 
1752                 VR_RANGE and the endpoints of the ranges are
1753                 different.  In that case the resulting range
1754                 should be whichever range is more precise.
1755                 Typically that will be the VR_RANGE.
1756
1757              2. The VR_ANTI_RANGE is completely disjoint from
1758                 the VR_RANGE.  In this case the resulting range
1759                 should be the VR_RANGE.
1760
1761              3. There is some overlap between the VR_ANTI_RANGE
1762                 and the VR_RANGE.
1763
1764                 3a. If the high limit of the VR_ANTI_RANGE resides
1765                     within the VR_RANGE, then the result is a new
1766                     VR_RANGE starting at the high limit of the
1767                     VR_ANTI_RANGE + 1 and extending to the
1768                     high limit of the original VR_RANGE.
1769
1770                 3b. If the low limit of the VR_ANTI_RANGE resides
1771                     within the VR_RANGE, then the result is a new
1772                     VR_RANGE starting at the low limit of the original
1773                     VR_RANGE and extending to the low limit of the
1774                     VR_ANTI_RANGE - 1.  */
1775           if (vr_p->type == VR_ANTI_RANGE)
1776             {
1777               anti_min = vr_p->min;
1778               anti_max = vr_p->max;
1779               real_min = var_vr->min;
1780               real_max = var_vr->max;
1781             }
1782           else
1783             {
1784               anti_min = var_vr->min;
1785               anti_max = var_vr->max;
1786               real_min = vr_p->min;
1787               real_max = vr_p->max;
1788             }
1789
1790
1791           /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
1792              not including any endpoints.  */
1793           if (compare_values (anti_max, real_max) == -1
1794               && compare_values (anti_min, real_min) == 1)
1795             {
1796               /* If the range is covering the whole valid range of
1797                  the type keep the anti-range.  */
1798               if (!vrp_val_is_min (real_min)
1799                   || !vrp_val_is_max (real_max))
1800                 set_value_range (vr_p, VR_RANGE, real_min,
1801                                  real_max, vr_p->equiv);
1802             }
1803           /* Case 2, VR_ANTI_RANGE completely disjoint from
1804              VR_RANGE.  */
1805           else if (compare_values (anti_min, real_max) == 1
1806                    || compare_values (anti_max, real_min) == -1)
1807             {
1808               set_value_range (vr_p, VR_RANGE, real_min,
1809                                real_max, vr_p->equiv);
1810             }
1811           /* Case 3a, the anti-range extends into the low
1812              part of the real range.  Thus creating a new
1813              low for the real range.  */
1814           else if (((cmp = compare_values (anti_max, real_min)) == 1
1815                     || cmp == 0)
1816                    && compare_values (anti_max, real_max) == -1)
1817             {
1818               gcc_assert (!is_positive_overflow_infinity (anti_max));
1819               if (needs_overflow_infinity (TREE_TYPE (anti_max))
1820                   && vrp_val_is_max (anti_max))
1821                 {
1822                   if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
1823                     {
1824                       set_value_range_to_varying (vr_p);
1825                       return;
1826                     }
1827                   min = positive_overflow_infinity (TREE_TYPE (var_vr->min));
1828                 }
1829               else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
1830                 min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
1831                                    anti_max,
1832                                    build_int_cst (TREE_TYPE (var_vr->min), 1));
1833               else
1834                 min = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
1835                                    anti_max, size_int (1));
1836               max = real_max;
1837               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1838             }
1839           /* Case 3b, the anti-range extends into the high
1840              part of the real range.  Thus creating a new
1841              higher for the real range.  */
1842           else if (compare_values (anti_min, real_min) == 1
1843                    && ((cmp = compare_values (anti_min, real_max)) == -1
1844                        || cmp == 0))
1845             {
1846               gcc_assert (!is_negative_overflow_infinity (anti_min));
1847               if (needs_overflow_infinity (TREE_TYPE (anti_min))
1848                   && vrp_val_is_min (anti_min))
1849                 {
1850                   if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
1851                     {
1852                       set_value_range_to_varying (vr_p);
1853                       return;
1854                     }
1855                   max = negative_overflow_infinity (TREE_TYPE (var_vr->min));
1856                 }
1857               else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
1858                 max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
1859                                    anti_min,
1860                                    build_int_cst (TREE_TYPE (var_vr->min), 1));
1861               else
1862                 max = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
1863                                    anti_min,
1864                                    size_int (-1));
1865               min = real_min;
1866               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1867             }
1868         }
1869     }
1870 }
1871
1872
1873 /* Extract range information from SSA name VAR and store it in VR.  If
1874    VAR has an interesting range, use it.  Otherwise, create the
1875    range [VAR, VAR] and return it.  This is useful in situations where
1876    we may have conditionals testing values of VARYING names.  For
1877    instance,
1878
1879         x_3 = y_5;
1880         if (x_3 > y_5)
1881           ...
1882
1883     Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
1884     always false.  */
1885
1886 static void
1887 extract_range_from_ssa_name (value_range_t *vr, tree var)
1888 {
1889   value_range_t *var_vr = get_value_range (var);
1890
1891   if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
1892     copy_value_range (vr, var_vr);
1893   else
1894     set_value_range (vr, VR_RANGE, var, var, NULL);
1895
1896   add_equivalence (&vr->equiv, var);
1897 }
1898
1899
1900 /* Wrapper around int_const_binop.  If the operation overflows and we
1901    are not using wrapping arithmetic, then adjust the result to be
1902    -INF or +INF depending on CODE, VAL1 and VAL2.  This can return
1903    NULL_TREE if we need to use an overflow infinity representation but
1904    the type does not support it.  */
1905
1906 static tree
1907 vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
1908 {
1909   tree res;
1910
1911   res = int_const_binop (code, val1, val2, 0);
1912
1913   /* If we are not using wrapping arithmetic, operate symbolically
1914      on -INF and +INF.  */
1915   if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
1916     {
1917       int checkz = compare_values (res, val1);
1918       bool overflow = false;
1919
1920       /* Ensure that res = val1 [+*] val2 >= val1
1921          or that res = val1 - val2 <= val1.  */
1922       if ((code == PLUS_EXPR
1923            && !(checkz == 1 || checkz == 0))
1924           || (code == MINUS_EXPR
1925               && !(checkz == 0 || checkz == -1)))
1926         {
1927           overflow = true;
1928         }
1929       /* Checking for multiplication overflow is done by dividing the
1930          output of the multiplication by the first input of the
1931          multiplication.  If the result of that division operation is
1932          not equal to the second input of the multiplication, then the
1933          multiplication overflowed.  */
1934       else if (code == MULT_EXPR && !integer_zerop (val1))
1935         {
1936           tree tmp = int_const_binop (TRUNC_DIV_EXPR,
1937                                       res,
1938                                       val1, 0);
1939           int check = compare_values (tmp, val2);
1940
1941           if (check != 0)
1942             overflow = true;
1943         }
1944
1945       if (overflow)
1946         {
1947           res = copy_node (res);
1948           TREE_OVERFLOW (res) = 1;
1949         }
1950
1951     }
1952   else if ((TREE_OVERFLOW (res)
1953             && !TREE_OVERFLOW (val1)
1954             && !TREE_OVERFLOW (val2))
1955            || is_overflow_infinity (val1)
1956            || is_overflow_infinity (val2))
1957     {
1958       /* If the operation overflowed but neither VAL1 nor VAL2 are
1959          overflown, return -INF or +INF depending on the operation
1960          and the combination of signs of the operands.  */
1961       int sgn1 = tree_int_cst_sgn (val1);
1962       int sgn2 = tree_int_cst_sgn (val2);
1963
1964       if (needs_overflow_infinity (TREE_TYPE (res))
1965           && !supports_overflow_infinity (TREE_TYPE (res)))
1966         return NULL_TREE;
1967
1968       /* We have to punt on adding infinities of different signs,
1969          since we can't tell what the sign of the result should be.
1970          Likewise for subtracting infinities of the same sign.  */
1971       if (((code == PLUS_EXPR && sgn1 != sgn2)
1972            || (code == MINUS_EXPR && sgn1 == sgn2))
1973           && is_overflow_infinity (val1)
1974           && is_overflow_infinity (val2))
1975         return NULL_TREE;
1976
1977       /* Don't try to handle division or shifting of infinities.  */
1978       if ((code == TRUNC_DIV_EXPR
1979            || code == FLOOR_DIV_EXPR
1980            || code == CEIL_DIV_EXPR
1981            || code == EXACT_DIV_EXPR
1982            || code == ROUND_DIV_EXPR
1983            || code == RSHIFT_EXPR)
1984           && (is_overflow_infinity (val1)
1985               || is_overflow_infinity (val2)))
1986         return NULL_TREE;
1987
1988       /* Notice that we only need to handle the restricted set of
1989          operations handled by extract_range_from_binary_expr.
1990          Among them, only multiplication, addition and subtraction
1991          can yield overflow without overflown operands because we
1992          are working with integral types only... except in the
1993          case VAL1 = -INF and VAL2 = -1 which overflows to +INF
1994          for division too.  */
1995
1996       /* For multiplication, the sign of the overflow is given
1997          by the comparison of the signs of the operands.  */
1998       if ((code == MULT_EXPR && sgn1 == sgn2)
1999           /* For addition, the operands must be of the same sign
2000              to yield an overflow.  Its sign is therefore that
2001              of one of the operands, for example the first.  For
2002              infinite operands X + -INF is negative, not positive.  */
2003           || (code == PLUS_EXPR
2004               && (sgn1 >= 0
2005                   ? !is_negative_overflow_infinity (val2)
2006                   : is_positive_overflow_infinity (val2)))
2007           /* For subtraction, non-infinite operands must be of
2008              different signs to yield an overflow.  Its sign is
2009              therefore that of the first operand or the opposite of
2010              that of the second operand.  A first operand of 0 counts
2011              as positive here, for the corner case 0 - (-INF), which
2012              overflows, but must yield +INF.  For infinite operands 0
2013              - INF is negative, not positive.  */
2014           || (code == MINUS_EXPR
2015               && (sgn1 >= 0
2016                   ? !is_positive_overflow_infinity (val2)
2017                   : is_negative_overflow_infinity (val2)))
2018           /* We only get in here with positive shift count, so the
2019              overflow direction is the same as the sign of val1.
2020              Actually rshift does not overflow at all, but we only
2021              handle the case of shifting overflowed -INF and +INF.  */
2022           || (code == RSHIFT_EXPR
2023               && sgn1 >= 0)
2024           /* For division, the only case is -INF / -1 = +INF.  */
2025           || code == TRUNC_DIV_EXPR
2026           || code == FLOOR_DIV_EXPR
2027           || code == CEIL_DIV_EXPR
2028           || code == EXACT_DIV_EXPR
2029           || code == ROUND_DIV_EXPR)
2030         return (needs_overflow_infinity (TREE_TYPE (res))
2031                 ? positive_overflow_infinity (TREE_TYPE (res))
2032                 : TYPE_MAX_VALUE (TREE_TYPE (res)));
2033       else
2034         return (needs_overflow_infinity (TREE_TYPE (res))
2035                 ? negative_overflow_infinity (TREE_TYPE (res))
2036                 : TYPE_MIN_VALUE (TREE_TYPE (res)));
2037     }
2038
2039   return res;
2040 }
2041
2042
2043 /* Extract range information from a binary expression EXPR based on
2044    the ranges of each of its operands and the expression code.  */
2045
2046 static void
2047 extract_range_from_binary_expr (value_range_t *vr,
2048                                 enum tree_code code,
2049                                 tree expr_type, tree op0, tree op1)
2050 {
2051   enum value_range_type type;
2052   tree min, max;
2053   int cmp;
2054   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2055   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2056
2057   /* Not all binary expressions can be applied to ranges in a
2058      meaningful way.  Handle only arithmetic operations.  */
2059   if (code != PLUS_EXPR
2060       && code != MINUS_EXPR
2061       && code != POINTER_PLUS_EXPR
2062       && code != MULT_EXPR
2063       && code != TRUNC_DIV_EXPR
2064       && code != FLOOR_DIV_EXPR
2065       && code != CEIL_DIV_EXPR
2066       && code != EXACT_DIV_EXPR
2067       && code != ROUND_DIV_EXPR
2068       && code != RSHIFT_EXPR
2069       && code != MIN_EXPR
2070       && code != MAX_EXPR
2071       && code != BIT_AND_EXPR
2072       && code != BIT_IOR_EXPR
2073       && code != TRUTH_AND_EXPR
2074       && code != TRUTH_OR_EXPR)
2075     {
2076       /* We can still do constant propagation here.  */
2077       tree const_op0 = op_with_constant_singleton_value_range (op0);
2078       tree const_op1 = op_with_constant_singleton_value_range (op1);
2079       if (const_op0 || const_op1)
2080         {
2081           tree tem = fold_binary (code, expr_type,
2082                                   const_op0 ? const_op0 : op0,
2083                                   const_op1 ? const_op1 : op1);
2084           if (tem
2085               && is_gimple_min_invariant (tem)
2086               && !is_overflow_infinity (tem))
2087             {
2088               set_value_range (vr, VR_RANGE, tem, tem, NULL);
2089               return;
2090             }
2091         }
2092       set_value_range_to_varying (vr);
2093       return;
2094     }
2095
2096   /* Get value ranges for each operand.  For constant operands, create
2097      a new value range with the operand to simplify processing.  */
2098   if (TREE_CODE (op0) == SSA_NAME)
2099     vr0 = *(get_value_range (op0));
2100   else if (is_gimple_min_invariant (op0))
2101     set_value_range_to_value (&vr0, op0, NULL);
2102   else
2103     set_value_range_to_varying (&vr0);
2104
2105   if (TREE_CODE (op1) == SSA_NAME)
2106     vr1 = *(get_value_range (op1));
2107   else if (is_gimple_min_invariant (op1))
2108     set_value_range_to_value (&vr1, op1, NULL);
2109   else
2110     set_value_range_to_varying (&vr1);
2111
2112   /* If either range is UNDEFINED, so is the result.  */
2113   if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
2114     {
2115       set_value_range_to_undefined (vr);
2116       return;
2117     }
2118
2119   /* The type of the resulting value range defaults to VR0.TYPE.  */
2120   type = vr0.type;
2121
2122   /* Refuse to operate on VARYING ranges, ranges of different kinds
2123      and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
2124      because we may be able to derive a useful range even if one of
2125      the operands is VR_VARYING or symbolic range.  Similarly for
2126      divisions.  TODO, we may be able to derive anti-ranges in
2127      some cases.  */
2128   if (code != BIT_AND_EXPR
2129       && code != TRUTH_AND_EXPR
2130       && code != TRUTH_OR_EXPR
2131       && code != TRUNC_DIV_EXPR
2132       && code != FLOOR_DIV_EXPR
2133       && code != CEIL_DIV_EXPR
2134       && code != EXACT_DIV_EXPR
2135       && code != ROUND_DIV_EXPR
2136       && (vr0.type == VR_VARYING
2137           || vr1.type == VR_VARYING
2138           || vr0.type != vr1.type
2139           || symbolic_range_p (&vr0)
2140           || symbolic_range_p (&vr1)))
2141     {
2142       set_value_range_to_varying (vr);
2143       return;
2144     }
2145
2146   /* Now evaluate the expression to determine the new range.  */
2147   if (POINTER_TYPE_P (expr_type)
2148       || POINTER_TYPE_P (TREE_TYPE (op0))
2149       || POINTER_TYPE_P (TREE_TYPE (op1)))
2150     {
2151       if (code == MIN_EXPR || code == MAX_EXPR)
2152         {
2153           /* For MIN/MAX expressions with pointers, we only care about
2154              nullness, if both are non null, then the result is nonnull.
2155              If both are null, then the result is null. Otherwise they
2156              are varying.  */
2157           if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1))
2158             set_value_range_to_nonnull (vr, expr_type);
2159           else if (range_is_null (&vr0) && range_is_null (&vr1))
2160             set_value_range_to_null (vr, expr_type);
2161           else
2162             set_value_range_to_varying (vr);
2163
2164           return;
2165         }
2166       gcc_assert (code == POINTER_PLUS_EXPR);
2167       /* For pointer types, we are really only interested in asserting
2168          whether the expression evaluates to non-NULL.  */
2169       if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
2170         set_value_range_to_nonnull (vr, expr_type);
2171       else if (range_is_null (&vr0) && range_is_null (&vr1))
2172         set_value_range_to_null (vr, expr_type);
2173       else
2174         set_value_range_to_varying (vr);
2175
2176       return;
2177     }
2178
2179   /* For integer ranges, apply the operation to each end of the
2180      range and see what we end up with.  */
2181   if (code == TRUTH_AND_EXPR
2182       || code == TRUTH_OR_EXPR)
2183     {
2184       /* If one of the operands is zero, we know that the whole
2185          expression evaluates zero.  */
2186       if (code == TRUTH_AND_EXPR
2187           && ((vr0.type == VR_RANGE
2188                && integer_zerop (vr0.min)
2189                && integer_zerop (vr0.max))
2190               || (vr1.type == VR_RANGE
2191                   && integer_zerop (vr1.min)
2192                   && integer_zerop (vr1.max))))
2193         {
2194           type = VR_RANGE;
2195           min = max = build_int_cst (expr_type, 0);
2196         }
2197       /* If one of the operands is one, we know that the whole
2198          expression evaluates one.  */
2199       else if (code == TRUTH_OR_EXPR
2200                && ((vr0.type == VR_RANGE
2201                     && integer_onep (vr0.min)
2202                     && integer_onep (vr0.max))
2203                    || (vr1.type == VR_RANGE
2204                        && integer_onep (vr1.min)
2205                        && integer_onep (vr1.max))))
2206         {
2207           type = VR_RANGE;
2208           min = max = build_int_cst (expr_type, 1);
2209         }
2210       else if (vr0.type != VR_VARYING
2211                && vr1.type != VR_VARYING
2212                && vr0.type == vr1.type
2213                && !symbolic_range_p (&vr0)
2214                && !overflow_infinity_range_p (&vr0)
2215                && !symbolic_range_p (&vr1)
2216                && !overflow_infinity_range_p (&vr1))
2217         {
2218           /* Boolean expressions cannot be folded with int_const_binop.  */
2219           min = fold_binary (code, expr_type, vr0.min, vr1.min);
2220           max = fold_binary (code, expr_type, vr0.max, vr1.max);
2221         }
2222       else
2223         {
2224           /* The result of a TRUTH_*_EXPR is always true or false.  */
2225           set_value_range_to_truthvalue (vr, expr_type);
2226           return;
2227         }
2228     }
2229   else if (code == PLUS_EXPR
2230            || code == MIN_EXPR
2231            || code == MAX_EXPR)
2232     {
2233       /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
2234          VR_VARYING.  It would take more effort to compute a precise
2235          range for such a case.  For example, if we have op0 == 1 and
2236          op1 == -1 with their ranges both being ~[0,0], we would have
2237          op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
2238          Note that we are guaranteed to have vr0.type == vr1.type at
2239          this point.  */
2240       if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
2241         {
2242           set_value_range_to_varying (vr);
2243           return;
2244         }
2245
2246       /* For operations that make the resulting range directly
2247          proportional to the original ranges, apply the operation to
2248          the same end of each range.  */
2249       min = vrp_int_const_binop (code, vr0.min, vr1.min);
2250       max = vrp_int_const_binop (code, vr0.max, vr1.max);
2251
2252       /* If both additions overflowed the range kind is still correct.
2253          This happens regularly with subtracting something in unsigned
2254          arithmetic.
2255          ???  See PR30318 for all the cases we do not handle.  */
2256       if (code == PLUS_EXPR
2257           && (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2258           && (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2259         {
2260           min = build_int_cst_wide (TREE_TYPE (min),
2261                                     TREE_INT_CST_LOW (min),
2262                                     TREE_INT_CST_HIGH (min));
2263           max = build_int_cst_wide (TREE_TYPE (max),
2264                                     TREE_INT_CST_LOW (max),
2265                                     TREE_INT_CST_HIGH (max));
2266         }
2267     }
2268   else if (code == MULT_EXPR
2269            || code == TRUNC_DIV_EXPR
2270            || code == FLOOR_DIV_EXPR
2271            || code == CEIL_DIV_EXPR
2272            || code == EXACT_DIV_EXPR
2273            || code == ROUND_DIV_EXPR
2274            || code == RSHIFT_EXPR)
2275     {
2276       tree val[4];
2277       size_t i;
2278       bool sop;
2279
2280       /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
2281          drop to VR_VARYING.  It would take more effort to compute a
2282          precise range for such a case.  For example, if we have
2283          op0 == 65536 and op1 == 65536 with their ranges both being
2284          ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
2285          we cannot claim that the product is in ~[0,0].  Note that we
2286          are guaranteed to have vr0.type == vr1.type at this
2287          point.  */
2288       if (code == MULT_EXPR
2289           && vr0.type == VR_ANTI_RANGE
2290           && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)))
2291         {
2292           set_value_range_to_varying (vr);
2293           return;
2294         }
2295
2296       /* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
2297          then drop to VR_VARYING.  Outside of this range we get undefined
2298          behavior from the shift operation.  We cannot even trust
2299          SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
2300          shifts, and the operation at the tree level may be widened.  */
2301       if (code == RSHIFT_EXPR)
2302         {
2303           if (vr1.type == VR_ANTI_RANGE
2304               || !vrp_expr_computes_nonnegative (op1, &sop)
2305               || (operand_less_p
2306                   (build_int_cst (TREE_TYPE (vr1.max),
2307                                   TYPE_PRECISION (expr_type) - 1),
2308                    vr1.max) != 0))
2309             {
2310               set_value_range_to_varying (vr);
2311               return;
2312             }
2313         }
2314
2315       else if ((code == TRUNC_DIV_EXPR
2316                 || code == FLOOR_DIV_EXPR
2317                 || code == CEIL_DIV_EXPR
2318                 || code == EXACT_DIV_EXPR
2319                 || code == ROUND_DIV_EXPR)
2320                && (vr0.type != VR_RANGE || symbolic_range_p (&vr0)))
2321         {
2322           /* For division, if op1 has VR_RANGE but op0 does not, something
2323              can be deduced just from that range.  Say [min, max] / [4, max]
2324              gives [min / 4, max / 4] range.  */
2325           if (vr1.type == VR_RANGE
2326               && !symbolic_range_p (&vr1)
2327               && !range_includes_zero_p (&vr1))
2328             {
2329               vr0.type = type = VR_RANGE;
2330               vr0.min = vrp_val_min (TREE_TYPE (op0));
2331               vr0.max = vrp_val_max (TREE_TYPE (op1));
2332             }
2333           else
2334             {
2335               set_value_range_to_varying (vr);
2336               return;
2337             }
2338         }
2339
2340       /* For divisions, if op0 is VR_RANGE, we can deduce a range
2341          even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can
2342          include 0.  */
2343       if ((code == TRUNC_DIV_EXPR
2344            || code == FLOOR_DIV_EXPR
2345            || code == CEIL_DIV_EXPR
2346            || code == EXACT_DIV_EXPR
2347            || code == ROUND_DIV_EXPR)
2348           && vr0.type == VR_RANGE
2349           && (vr1.type != VR_RANGE
2350               || symbolic_range_p (&vr1)
2351               || range_includes_zero_p (&vr1)))
2352         {
2353           tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
2354           int cmp;
2355
2356           sop = false;
2357           min = NULL_TREE;
2358           max = NULL_TREE;
2359           if (vrp_expr_computes_nonnegative (op1, &sop) && !sop)
2360             {
2361               /* For unsigned division or when divisor is known
2362                  to be non-negative, the range has to cover
2363                  all numbers from 0 to max for positive max
2364                  and all numbers from min to 0 for negative min.  */
2365               cmp = compare_values (vr0.max, zero);
2366               if (cmp == -1)
2367                 max = zero;
2368               else if (cmp == 0 || cmp == 1)
2369                 max = vr0.max;
2370               else
2371                 type = VR_VARYING;
2372               cmp = compare_values (vr0.min, zero);
2373               if (cmp == 1)
2374                 min = zero;
2375               else if (cmp == 0 || cmp == -1)
2376                 min = vr0.min;
2377               else
2378                 type = VR_VARYING;
2379             }
2380           else
2381             {
2382               /* Otherwise the range is -max .. max or min .. -min
2383                  depending on which bound is bigger in absolute value,
2384                  as the division can change the sign.  */
2385               abs_extent_range (vr, vr0.min, vr0.max);
2386               return;
2387             }
2388           if (type == VR_VARYING)
2389             {
2390               set_value_range_to_varying (vr);
2391               return;
2392             }
2393         }
2394
2395       /* Multiplications and divisions are a bit tricky to handle,
2396          depending on the mix of signs we have in the two ranges, we
2397          need to operate on different values to get the minimum and
2398          maximum values for the new range.  One approach is to figure
2399          out all the variations of range combinations and do the
2400          operations.
2401
2402          However, this involves several calls to compare_values and it
2403          is pretty convoluted.  It's simpler to do the 4 operations
2404          (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
2405          MAX1) and then figure the smallest and largest values to form
2406          the new range.  */
2407       else
2408         {
2409           gcc_assert ((vr0.type == VR_RANGE
2410                        || (code == MULT_EXPR && vr0.type == VR_ANTI_RANGE))
2411                       && vr0.type == vr1.type);
2412
2413           /* Compute the 4 cross operations.  */
2414           sop = false;
2415           val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
2416           if (val[0] == NULL_TREE)
2417             sop = true;
2418
2419           if (vr1.max == vr1.min)
2420             val[1] = NULL_TREE;
2421           else
2422             {
2423               val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
2424               if (val[1] == NULL_TREE)
2425                 sop = true;
2426             }
2427
2428           if (vr0.max == vr0.min)
2429             val[2] = NULL_TREE;
2430           else
2431             {
2432               val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
2433               if (val[2] == NULL_TREE)
2434                 sop = true;
2435             }
2436
2437           if (vr0.min == vr0.max || vr1.min == vr1.max)
2438             val[3] = NULL_TREE;
2439           else
2440             {
2441               val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
2442               if (val[3] == NULL_TREE)
2443                 sop = true;
2444             }
2445
2446           if (sop)
2447             {
2448               set_value_range_to_varying (vr);
2449               return;
2450             }
2451
2452           /* Set MIN to the minimum of VAL[i] and MAX to the maximum
2453              of VAL[i].  */
2454           min = val[0];
2455           max = val[0];
2456           for (i = 1; i < 4; i++)
2457             {
2458               if (!is_gimple_min_invariant (min)
2459                   || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2460                   || !is_gimple_min_invariant (max)
2461                   || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2462                 break;
2463
2464               if (val[i])
2465                 {
2466                   if (!is_gimple_min_invariant (val[i])
2467                       || (TREE_OVERFLOW (val[i])
2468                           && !is_overflow_infinity (val[i])))
2469                     {
2470                       /* If we found an overflowed value, set MIN and MAX
2471                          to it so that we set the resulting range to
2472                          VARYING.  */
2473                       min = max = val[i];
2474                       break;
2475                     }
2476
2477                   if (compare_values (val[i], min) == -1)
2478                     min = val[i];
2479
2480                   if (compare_values (val[i], max) == 1)
2481                     max = val[i];
2482                 }
2483             }
2484         }
2485     }
2486   else if (code == MINUS_EXPR)
2487     {
2488       /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
2489          VR_VARYING.  It would take more effort to compute a precise
2490          range for such a case.  For example, if we have op0 == 1 and
2491          op1 == 1 with their ranges both being ~[0,0], we would have
2492          op0 - op1 == 0, so we cannot claim that the difference is in
2493          ~[0,0].  Note that we are guaranteed to have
2494          vr0.type == vr1.type at this point.  */
2495       if (vr0.type == VR_ANTI_RANGE)
2496         {
2497           set_value_range_to_varying (vr);
2498           return;
2499         }
2500
2501       /* For MINUS_EXPR, apply the operation to the opposite ends of
2502          each range.  */
2503       min = vrp_int_const_binop (code, vr0.min, vr1.max);
2504       max = vrp_int_const_binop (code, vr0.max, vr1.min);
2505     }
2506   else if (code == BIT_AND_EXPR)
2507     {
2508       if (vr0.type == VR_RANGE
2509           && vr0.min == vr0.max
2510           && TREE_CODE (vr0.max) == INTEGER_CST
2511           && !TREE_OVERFLOW (vr0.max)
2512           && tree_int_cst_sgn (vr0.max) >= 0)
2513         {
2514           min = build_int_cst (expr_type, 0);
2515           max = vr0.max;
2516         }
2517       else if (vr1.type == VR_RANGE
2518                && vr1.min == vr1.max
2519                && TREE_CODE (vr1.max) == INTEGER_CST
2520                && !TREE_OVERFLOW (vr1.max)
2521                && tree_int_cst_sgn (vr1.max) >= 0)
2522         {
2523           type = VR_RANGE;
2524           min = build_int_cst (expr_type, 0);
2525           max = vr1.max;
2526         }
2527       else
2528         {
2529           set_value_range_to_varying (vr);
2530           return;
2531         }
2532     }
2533   else if (code == BIT_IOR_EXPR)
2534     {
2535       if (vr0.type == VR_RANGE
2536           && vr1.type == VR_RANGE
2537           && TREE_CODE (vr0.min) == INTEGER_CST
2538           && TREE_CODE (vr1.min) == INTEGER_CST
2539           && TREE_CODE (vr0.max) == INTEGER_CST
2540           && TREE_CODE (vr1.max) == INTEGER_CST
2541           && tree_int_cst_sgn (vr0.min) >= 0
2542           && tree_int_cst_sgn (vr1.min) >= 0)
2543         {
2544           double_int vr0_max = tree_to_double_int (vr0.max);
2545           double_int vr1_max = tree_to_double_int (vr1.max);
2546           double_int ior_max;
2547
2548           /* Set all bits to the right of the most significant one to 1.
2549              For example, [0, 4] | [4, 4] = [4, 7]. */
2550           ior_max.low = vr0_max.low | vr1_max.low;
2551           ior_max.high = vr0_max.high | vr1_max.high;
2552           if (ior_max.high != 0)
2553             {
2554               ior_max.low = ~(unsigned HOST_WIDE_INT)0u;
2555               ior_max.high |= ((HOST_WIDE_INT) 1
2556                                << floor_log2 (ior_max.high)) - 1;
2557             }
2558           else if (ior_max.low != 0)
2559             ior_max.low |= ((unsigned HOST_WIDE_INT) 1u
2560                             << floor_log2 (ior_max.low)) - 1;
2561
2562           /* Both of these endpoints are conservative.  */
2563           min = vrp_int_const_binop (MAX_EXPR, vr0.min, vr1.min);
2564           max = double_int_to_tree (expr_type, ior_max);
2565         }
2566       else
2567         {
2568           set_value_range_to_varying (vr);
2569           return;
2570         }
2571     }
2572   else
2573     gcc_unreachable ();
2574
2575   /* If either MIN or MAX overflowed, then set the resulting range to
2576      VARYING.  But we do accept an overflow infinity
2577      representation.  */
2578   if (min == NULL_TREE
2579       || !is_gimple_min_invariant (min)
2580       || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2581       || max == NULL_TREE
2582       || !is_gimple_min_invariant (max)
2583       || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2584     {
2585       set_value_range_to_varying (vr);
2586       return;
2587     }
2588
2589   /* We punt if:
2590      1) [-INF, +INF]
2591      2) [-INF, +-INF(OVF)]
2592      3) [+-INF(OVF), +INF]
2593      4) [+-INF(OVF), +-INF(OVF)]
2594      We learn nothing when we have INF and INF(OVF) on both sides.
2595      Note that we do accept [-INF, -INF] and [+INF, +INF] without
2596      overflow.  */
2597   if ((vrp_val_is_min (min) || is_overflow_infinity (min))
2598       && (vrp_val_is_max (max) || is_overflow_infinity (max)))
2599     {
2600       set_value_range_to_varying (vr);
2601       return;
2602     }
2603
2604   cmp = compare_values (min, max);
2605   if (cmp == -2 || cmp == 1)
2606     {
2607       /* If the new range has its limits swapped around (MIN > MAX),
2608          then the operation caused one of them to wrap around, mark
2609          the new range VARYING.  */
2610       set_value_range_to_varying (vr);
2611     }
2612   else
2613     set_value_range (vr, type, min, max, NULL);
2614 }
2615
2616
2617 /* Extract range information from a unary expression EXPR based on
2618    the range of its operand and the expression code.  */
2619
2620 static void
2621 extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
2622                                tree type, tree op0)
2623 {
2624   tree min, max;
2625   int cmp;
2626   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2627
2628   /* Refuse to operate on certain unary expressions for which we
2629      cannot easily determine a resulting range.  */
2630   if (code == FIX_TRUNC_EXPR
2631       || code == FLOAT_EXPR
2632       || code == BIT_NOT_EXPR
2633       || code == CONJ_EXPR)
2634     {
2635       /* We can still do constant propagation here.  */
2636       if ((op0 = op_with_constant_singleton_value_range (op0)) != NULL_TREE)
2637         {
2638           tree tem = fold_unary (code, type, op0);
2639           if (tem
2640               && is_gimple_min_invariant (tem)
2641               && !is_overflow_infinity (tem))
2642             {
2643               set_value_range (vr, VR_RANGE, tem, tem, NULL);
2644               return;
2645             }
2646         }
2647       set_value_range_to_varying (vr);
2648       return;
2649     }
2650
2651   /* Get value ranges for the operand.  For constant operands, create
2652      a new value range with the operand to simplify processing.  */
2653   if (TREE_CODE (op0) == SSA_NAME)
2654     vr0 = *(get_value_range (op0));
2655   else if (is_gimple_min_invariant (op0))
2656     set_value_range_to_value (&vr0, op0, NULL);
2657   else
2658     set_value_range_to_varying (&vr0);
2659
2660   /* If VR0 is UNDEFINED, so is the result.  */
2661   if (vr0.type == VR_UNDEFINED)
2662     {
2663       set_value_range_to_undefined (vr);
2664       return;
2665     }
2666
2667   /* Refuse to operate on symbolic ranges, or if neither operand is
2668      a pointer or integral type.  */
2669   if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0))
2670        && !POINTER_TYPE_P (TREE_TYPE (op0)))
2671       || (vr0.type != VR_VARYING
2672           && symbolic_range_p (&vr0)))
2673     {
2674       set_value_range_to_varying (vr);
2675       return;
2676     }
2677
2678   /* If the expression involves pointers, we are only interested in
2679      determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]).  */
2680   if (POINTER_TYPE_P (type) || POINTER_TYPE_P (TREE_TYPE (op0)))
2681     {
2682       bool sop;
2683
2684       sop = false;
2685       if (range_is_nonnull (&vr0)
2686           || (tree_unary_nonzero_warnv_p (code, type, op0, &sop)
2687               && !sop))
2688         set_value_range_to_nonnull (vr, type);
2689       else if (range_is_null (&vr0))
2690         set_value_range_to_null (vr, type);
2691       else
2692         set_value_range_to_varying (vr);
2693
2694       return;
2695     }
2696
2697   /* Handle unary expressions on integer ranges.  */
2698   if (CONVERT_EXPR_CODE_P (code)
2699       && INTEGRAL_TYPE_P (type)
2700       && INTEGRAL_TYPE_P (TREE_TYPE (op0)))
2701     {
2702       tree inner_type = TREE_TYPE (op0);
2703       tree outer_type = type;
2704
2705       /* Always use base-types here.  This is important for the
2706          correct signedness.  */
2707       if (TREE_TYPE (inner_type))
2708         inner_type = TREE_TYPE (inner_type);
2709       if (TREE_TYPE (outer_type))
2710         outer_type = TREE_TYPE (outer_type);
2711
2712       /* If VR0 is varying and we increase the type precision, assume
2713          a full range for the following transformation.  */
2714       if (vr0.type == VR_VARYING
2715           && TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type))
2716         {
2717           vr0.type = VR_RANGE;
2718           vr0.min = TYPE_MIN_VALUE (inner_type);
2719           vr0.max = TYPE_MAX_VALUE (inner_type);
2720         }
2721
2722       /* If VR0 is a constant range or anti-range and the conversion is
2723          not truncating we can convert the min and max values and
2724          canonicalize the resulting range.  Otherwise we can do the
2725          conversion if the size of the range is less than what the
2726          precision of the target type can represent and the range is
2727          not an anti-range.  */
2728       if ((vr0.type == VR_RANGE
2729            || vr0.type == VR_ANTI_RANGE)
2730           && TREE_CODE (vr0.min) == INTEGER_CST
2731           && TREE_CODE (vr0.max) == INTEGER_CST
2732           && !is_overflow_infinity (vr0.min)
2733           && !is_overflow_infinity (vr0.max)
2734           && (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type)
2735               || (vr0.type == VR_RANGE
2736                   && integer_zerop (int_const_binop (RSHIFT_EXPR,
2737                        int_const_binop (MINUS_EXPR, vr0.max, vr0.min, 0),
2738                          size_int (TYPE_PRECISION (outer_type)), 0)))))
2739         {
2740           tree new_min, new_max;
2741           new_min = force_fit_type_double (outer_type,
2742                                            TREE_INT_CST_LOW (vr0.min),
2743                                            TREE_INT_CST_HIGH (vr0.min), 0, 0);
2744           new_max = force_fit_type_double (outer_type,
2745                                            TREE_INT_CST_LOW (vr0.max),
2746                                            TREE_INT_CST_HIGH (vr0.max), 0, 0);
2747           set_and_canonicalize_value_range (vr, vr0.type,
2748                                             new_min, new_max, NULL);
2749           return;
2750         }
2751
2752       set_value_range_to_varying (vr);
2753       return;
2754     }
2755
2756   /* Conversion of a VR_VARYING value to a wider type can result
2757      in a usable range.  So wait until after we've handled conversions
2758      before dropping the result to VR_VARYING if we had a source
2759      operand that is VR_VARYING.  */
2760   if (vr0.type == VR_VARYING)
2761     {
2762       set_value_range_to_varying (vr);
2763       return;
2764     }
2765
2766   /* Apply the operation to each end of the range and see what we end
2767      up with.  */
2768   if (code == NEGATE_EXPR
2769       && !TYPE_UNSIGNED (type))
2770     {
2771       /* NEGATE_EXPR flips the range around.  We need to treat
2772          TYPE_MIN_VALUE specially.  */
2773       if (is_positive_overflow_infinity (vr0.max))
2774         min = negative_overflow_infinity (type);
2775       else if (is_negative_overflow_infinity (vr0.max))
2776         min = positive_overflow_infinity (type);
2777       else if (!vrp_val_is_min (vr0.max))
2778         min = fold_unary_to_constant (code, type, vr0.max);
2779       else if (needs_overflow_infinity (type))
2780         {
2781           if (supports_overflow_infinity (type)
2782               && !is_overflow_infinity (vr0.min)
2783               && !vrp_val_is_min (vr0.min))
2784             min = positive_overflow_infinity (type);
2785           else
2786             {
2787               set_value_range_to_varying (vr);
2788               return;
2789             }
2790         }
2791       else
2792         min = TYPE_MIN_VALUE (type);
2793
2794       if (is_positive_overflow_infinity (vr0.min))
2795         max = negative_overflow_infinity (type);
2796       else if (is_negative_overflow_infinity (vr0.min))
2797         max = positive_overflow_infinity (type);
2798       else if (!vrp_val_is_min (vr0.min))
2799         max = fold_unary_to_constant (code, type, vr0.min);
2800       else if (needs_overflow_infinity (type))
2801         {
2802           if (supports_overflow_infinity (type))
2803             max = positive_overflow_infinity (type);
2804           else
2805             {
2806               set_value_range_to_varying (vr);
2807               return;
2808             }
2809         }
2810       else
2811         max = TYPE_MIN_VALUE (type);
2812     }
2813   else if (code == NEGATE_EXPR
2814            && TYPE_UNSIGNED (type))
2815     {
2816       if (!range_includes_zero_p (&vr0))
2817         {
2818           max = fold_unary_to_constant (code, type, vr0.min);
2819           min = fold_unary_to_constant (code, type, vr0.max);
2820         }
2821       else
2822         {
2823           if (range_is_null (&vr0))
2824             set_value_range_to_null (vr, type);
2825           else
2826             set_value_range_to_varying (vr);
2827           return;
2828         }
2829     }
2830   else if (code == ABS_EXPR
2831            && !TYPE_UNSIGNED (type))
2832     {
2833       /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
2834          useful range.  */
2835       if (!TYPE_OVERFLOW_UNDEFINED (type)
2836           && ((vr0.type == VR_RANGE
2837                && vrp_val_is_min (vr0.min))
2838               || (vr0.type == VR_ANTI_RANGE
2839                   && !vrp_val_is_min (vr0.min)
2840                   && !range_includes_zero_p (&vr0))))
2841         {
2842           set_value_range_to_varying (vr);
2843           return;
2844         }
2845         
2846       /* ABS_EXPR may flip the range around, if the original range
2847          included negative values.  */
2848       if (is_overflow_infinity (vr0.min))
2849         min = positive_overflow_infinity (type);
2850       else if (!vrp_val_is_min (vr0.min))
2851         min = fold_unary_to_constant (code, type, vr0.min);
2852       else if (!needs_overflow_infinity (type))
2853         min = TYPE_MAX_VALUE (type);
2854       else if (supports_overflow_infinity (type))
2855         min = positive_overflow_infinity (type);
2856       else
2857         {
2858           set_value_range_to_varying (vr);
2859           return;
2860         }
2861
2862       if (is_overflow_infinity (vr0.max))
2863         max = positive_overflow_infinity (type);
2864       else if (!vrp_val_is_min (vr0.max))
2865         max = fold_unary_to_constant (code, type, vr0.max);
2866       else if (!needs_overflow_infinity (type))
2867         max = TYPE_MAX_VALUE (type);
2868       else if (supports_overflow_infinity (type)
2869                /* We shouldn't generate [+INF, +INF] as set_value_range
2870                   doesn't like this and ICEs.  */
2871                && !is_positive_overflow_infinity (min))
2872         max = positive_overflow_infinity (type);
2873       else
2874         {
2875           set_value_range_to_varying (vr);
2876           return;
2877         }
2878
2879       cmp = compare_values (min, max);
2880
2881       /* If a VR_ANTI_RANGEs contains zero, then we have
2882          ~[-INF, min(MIN, MAX)].  */
2883       if (vr0.type == VR_ANTI_RANGE)
2884         { 
2885           if (range_includes_zero_p (&vr0))
2886             {
2887               /* Take the lower of the two values.  */
2888               if (cmp != 1)
2889                 max = min;
2890
2891               /* Create ~[-INF, min (abs(MIN), abs(MAX))]
2892                  or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
2893                  flag_wrapv is set and the original anti-range doesn't include
2894                  TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE.  */
2895               if (TYPE_OVERFLOW_WRAPS (type))
2896                 {
2897                   tree type_min_value = TYPE_MIN_VALUE (type);
2898
2899                   min = (vr0.min != type_min_value
2900                          ? int_const_binop (PLUS_EXPR, type_min_value,
2901                                             integer_one_node, 0)
2902                          : type_min_value);
2903                 }
2904               else
2905                 {
2906                   if (overflow_infinity_range_p (&vr0))
2907                     min = negative_overflow_infinity (type);
2908                   else
2909                     min = TYPE_MIN_VALUE (type);
2910                 }
2911             }
2912           else
2913             {
2914               /* All else has failed, so create the range [0, INF], even for
2915                  flag_wrapv since TYPE_MIN_VALUE is in the original
2916                  anti-range.  */
2917               vr0.type = VR_RANGE;
2918               min = build_int_cst (type, 0);
2919               if (needs_overflow_infinity (type))
2920                 {
2921                   if (supports_overflow_infinity (type))
2922                     max = positive_overflow_infinity (type);
2923                   else
2924                     {
2925                       set_value_range_to_varying (vr);
2926                       return;
2927                     }
2928                 }
2929               else
2930                 max = TYPE_MAX_VALUE (type);
2931             }
2932         }
2933
2934       /* If the range contains zero then we know that the minimum value in the
2935          range will be zero.  */
2936       else if (range_includes_zero_p (&vr0))
2937         {
2938           if (cmp == 1)
2939             max = min;
2940           min = build_int_cst (type, 0);
2941         }
2942       else
2943         {
2944           /* If the range was reversed, swap MIN and MAX.  */
2945           if (cmp == 1)
2946             {
2947               tree t = min;
2948               min = max;
2949               max = t;
2950             }
2951         }
2952     }
2953   else
2954     {
2955       /* Otherwise, operate on each end of the range.  */
2956       min = fold_unary_to_constant (code, type, vr0.min);
2957       max = fold_unary_to_constant (code, type, vr0.max);
2958
2959       if (needs_overflow_infinity (type))
2960         {
2961           gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR);
2962
2963           /* If both sides have overflowed, we don't know
2964              anything.  */
2965           if ((is_overflow_infinity (vr0.min)
2966                || TREE_OVERFLOW (min))
2967               && (is_overflow_infinity (vr0.max)
2968                   || TREE_OVERFLOW (max)))
2969             {
2970               set_value_range_to_varying (vr);
2971               return;
2972             }
2973
2974           if (is_overflow_infinity (vr0.min))
2975             min = vr0.min;
2976           else if (TREE_OVERFLOW (min))
2977             {
2978               if (supports_overflow_infinity (type))
2979                 min = (tree_int_cst_sgn (min) >= 0
2980                        ? positive_overflow_infinity (TREE_TYPE (min))
2981                        : negative_overflow_infinity (TREE_TYPE (min)));
2982               else
2983                 {
2984                   set_value_range_to_varying (vr);
2985                   return;
2986                 }
2987             }
2988
2989           if (is_overflow_infinity (vr0.max))
2990             max = vr0.max;
2991           else if (TREE_OVERFLOW (max))
2992             {
2993               if (supports_overflow_infinity (type))
2994                 max = (tree_int_cst_sgn (max) >= 0
2995                        ? positive_overflow_infinity (TREE_TYPE (max))
2996                        : negative_overflow_infinity (TREE_TYPE (max)));
2997               else
2998                 {
2999                   set_value_range_to_varying (vr);
3000                   return;
3001                 }
3002             }
3003         }
3004     }
3005
3006   cmp = compare_values (min, max);
3007   if (cmp == -2 || cmp == 1)
3008     {
3009       /* If the new range has its limits swapped around (MIN > MAX),
3010          then the operation caused one of them to wrap around, mark
3011          the new range VARYING.  */
3012       set_value_range_to_varying (vr);
3013     }
3014   else
3015     set_value_range (vr, vr0.type, min, max, NULL);
3016 }
3017
3018
3019 /* Extract range information from a conditional expression EXPR based on
3020    the ranges of each of its operands and the expression code.  */
3021
3022 static void
3023 extract_range_from_cond_expr (value_range_t *vr, tree expr)
3024 {
3025   tree op0, op1;
3026   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3027   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3028
3029   /* Get value ranges for each operand.  For constant operands, create
3030      a new value range with the operand to simplify processing.  */
3031   op0 = COND_EXPR_THEN (expr);
3032   if (TREE_CODE (op0) == SSA_NAME)
3033     vr0 = *(get_value_range (op0));
3034   else if (is_gimple_min_invariant (op0))
3035     set_value_range_to_value (&vr0, op0, NULL);
3036   else
3037     set_value_range_to_varying (&vr0);
3038
3039   op1 = COND_EXPR_ELSE (expr);
3040   if (TREE_CODE (op1) == SSA_NAME)
3041     vr1 = *(get_value_range (op1));
3042   else if (is_gimple_min_invariant (op1))
3043     set_value_range_to_value (&vr1, op1, NULL);
3044   else
3045     set_value_range_to_varying (&vr1);
3046
3047   /* The resulting value range is the union of the operand ranges */
3048   vrp_meet (&vr0, &vr1);
3049   copy_value_range (vr, &vr0);
3050 }
3051
3052
3053 /* Extract range information from a comparison expression EXPR based
3054    on the range of its operand and the expression code.  */
3055
3056 static void
3057 extract_range_from_comparison (value_range_t *vr, enum tree_code code,
3058                                tree type, tree op0, tree op1)
3059 {
3060   bool sop = false;
3061   tree val;
3062   
3063   val = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, false, &sop,
3064                                                  NULL);
3065
3066   /* A disadvantage of using a special infinity as an overflow
3067      representation is that we lose the ability to record overflow
3068      when we don't have an infinity.  So we have to ignore a result
3069      which relies on overflow.  */
3070
3071   if (val && !is_overflow_infinity (val) && !sop)
3072     {
3073       /* Since this expression was found on the RHS of an assignment,
3074          its type may be different from _Bool.  Convert VAL to EXPR's
3075          type.  */
3076       val = fold_convert (type, val);
3077       if (is_gimple_min_invariant (val))
3078         set_value_range_to_value (vr, val, vr->equiv);
3079       else
3080         set_value_range (vr, VR_RANGE, val, val, vr->equiv);
3081     }
3082   else
3083     /* The result of a comparison is always true or false.  */
3084     set_value_range_to_truthvalue (vr, type);
3085 }
3086
3087 /* Try to derive a nonnegative or nonzero range out of STMT relying
3088    primarily on generic routines in fold in conjunction with range data.
3089    Store the result in *VR */
3090
3091 static void
3092 extract_range_basic (value_range_t *vr, gimple stmt)
3093 {
3094   bool sop = false;
3095   tree type = gimple_expr_type (stmt);
3096
3097   if (INTEGRAL_TYPE_P (type)
3098       && gimple_stmt_nonnegative_warnv_p (stmt, &sop))
3099     set_value_range_to_nonnegative (vr, type,
3100                                     sop || stmt_overflow_infinity (stmt));
3101   else if (vrp_stmt_computes_nonzero (stmt, &sop)
3102            && !sop)
3103     set_value_range_to_nonnull (vr, type);
3104   else
3105     set_value_range_to_varying (vr);
3106 }
3107
3108
3109 /* Try to compute a useful range out of assignment STMT and store it
3110    in *VR.  */
3111
3112 static void
3113 extract_range_from_assignment (value_range_t *vr, gimple stmt)
3114 {
3115   enum tree_code code = gimple_assign_rhs_code (stmt);
3116
3117   if (code == ASSERT_EXPR)
3118     extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
3119   else if (code == SSA_NAME)
3120     extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
3121   else if (TREE_CODE_CLASS (code) == tcc_binary
3122            || code == TRUTH_AND_EXPR
3123            || code == TRUTH_OR_EXPR
3124            || code == TRUTH_XOR_EXPR)
3125     extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt),
3126                                     gimple_expr_type (stmt),
3127                                     gimple_assign_rhs1 (stmt),
3128                                     gimple_assign_rhs2 (stmt));
3129   else if (TREE_CODE_CLASS (code) == tcc_unary)
3130     extract_range_from_unary_expr (vr, gimple_assign_rhs_code (stmt),
3131                                    gimple_expr_type (stmt),
3132                                    gimple_assign_rhs1 (stmt));
3133   else if (code == COND_EXPR)
3134     extract_range_from_cond_expr (vr, gimple_assign_rhs1 (stmt));
3135   else if (TREE_CODE_CLASS (code) == tcc_comparison)
3136     extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt),
3137                                    gimple_expr_type (stmt),
3138                                    gimple_assign_rhs1 (stmt),
3139                                    gimple_assign_rhs2 (stmt));
3140   else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
3141            && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
3142     set_value_range_to_value (vr, gimple_assign_rhs1 (stmt), NULL);
3143   else
3144     set_value_range_to_varying (vr);
3145
3146   if (vr->type == VR_VARYING)
3147     extract_range_basic (vr, stmt);
3148 }
3149
3150 /* Given a range VR, a LOOP and a variable VAR, determine whether it
3151    would be profitable to adjust VR using scalar evolution information
3152    for VAR.  If so, update VR with the new limits.  */
3153
3154 static void
3155 adjust_range_with_scev (value_range_t *vr, struct loop *loop,
3156                         gimple stmt, tree var)
3157 {
3158   tree init, step, chrec, tmin, tmax, min, max, type;
3159   enum ev_direction dir;
3160
3161   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
3162      better opportunities than a regular range, but I'm not sure.  */
3163   if (vr->type == VR_ANTI_RANGE)
3164     return;
3165
3166   chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
3167
3168   /* Like in PR19590, scev can return a constant function.  */
3169   if (is_gimple_min_invariant (chrec))
3170     {
3171       set_value_range_to_value (vr, chrec, vr->equiv);
3172       return;
3173     }
3174
3175   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
3176     return;
3177
3178   init = initial_condition_in_loop_num (chrec, loop->num);
3179   step = evolution_part_in_loop_num (chrec, loop->num);
3180
3181   /* If STEP is symbolic, we can't know whether INIT will be the
3182      minimum or maximum value in the range.  Also, unless INIT is
3183      a simple expression, compare_values and possibly other functions
3184      in tree-vrp won't be able to handle it.  */
3185   if (step == NULL_TREE
3186       || !is_gimple_min_invariant (step)
3187       || !valid_value_p (init))
3188     return;
3189
3190   dir = scev_direction (chrec);
3191   if (/* Do not adjust ranges if we do not know whether the iv increases
3192          or decreases,  ... */
3193       dir == EV_DIR_UNKNOWN
3194       /* ... or if it may wrap.  */
3195       || scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
3196                                 true))
3197     return;
3198
3199   /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of
3200      negative_overflow_infinity and positive_overflow_infinity,
3201      because we have concluded that the loop probably does not
3202      wrap.  */
3203
3204   type = TREE_TYPE (var);
3205   if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
3206     tmin = lower_bound_in_type (type, type);
3207   else
3208     tmin = TYPE_MIN_VALUE (type);
3209   if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
3210     tmax = upper_bound_in_type (type, type);
3211   else
3212     tmax = TYPE_MAX_VALUE (type);
3213
3214   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
3215     {
3216       min = tmin;
3217       max = tmax;
3218
3219       /* For VARYING or UNDEFINED ranges, just about anything we get
3220          from scalar evolutions should be better.  */
3221
3222       if (dir == EV_DIR_DECREASES)
3223         max = init;
3224       else
3225         min = init;
3226
3227       /* If we would create an invalid range, then just assume we
3228          know absolutely nothing.  This may be over-conservative,
3229          but it's clearly safe, and should happen only in unreachable
3230          parts of code, or for invalid programs.  */
3231       if (compare_values (min, max) == 1)
3232         return;
3233
3234       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
3235     }
3236   else if (vr->type == VR_RANGE)
3237     {
3238       min = vr->min;
3239       max = vr->max;
3240
3241       if (dir == EV_DIR_DECREASES)
3242         {
3243           /* INIT is the maximum value.  If INIT is lower than VR->MAX
3244              but no smaller than VR->MIN, set VR->MAX to INIT.  */
3245           if (compare_values (init, max) == -1)
3246             {
3247               max = init;
3248
3249               /* If we just created an invalid range with the minimum
3250                  greater than the maximum, we fail conservatively.
3251                  This should happen only in unreachable
3252                  parts of code, or for invalid programs.  */
3253               if (compare_values (min, max) == 1)
3254                 return;
3255             }
3256
3257           /* According to the loop information, the variable does not
3258              overflow.  If we think it does, probably because of an
3259              overflow due to arithmetic on a different INF value,
3260              reset now.  */
3261           if (is_negative_overflow_infinity (min))
3262             min = tmin;
3263         }
3264       else
3265         {
3266           /* If INIT is bigger than VR->MIN, set VR->MIN to INIT.  */
3267           if (compare_values (init, min) == 1)
3268             {
3269               min = init;
3270
3271               /* Again, avoid creating invalid range by failing.  */
3272               if (compare_values (min, max) == 1)
3273                 return;
3274             }
3275
3276           if (is_positive_overflow_infinity (max))
3277             max = tmax;
3278         }
3279
3280       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
3281     }
3282 }
3283
3284 /* Return true if VAR may overflow at STMT.  This checks any available
3285    loop information to see if we can determine that VAR does not
3286    overflow.  */
3287
3288 static bool
3289 vrp_var_may_overflow (tree var, gimple stmt)
3290 {
3291   struct loop *l;
3292   tree chrec, init, step;
3293
3294   if (current_loops == NULL)
3295     return true;
3296
3297   l = loop_containing_stmt (stmt);
3298   if (l == NULL)
3299     return true;
3300
3301   chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
3302   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
3303     return true;
3304
3305   init = initial_condition_in_loop_num (chrec, l->num);
3306   step = evolution_part_in_loop_num (chrec, l->num);
3307
3308   if (step == NULL_TREE
3309       || !is_gimple_min_invariant (step)
3310       || !valid_value_p (init))
3311     return true;
3312
3313   /* If we get here, we know something useful about VAR based on the
3314      loop information.  If it wraps, it may overflow.  */
3315
3316   if (scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
3317                              true))
3318     return true;
3319
3320   if (dump_file && (dump_flags & TDF_DETAILS) != 0)
3321     {
3322       print_generic_expr (dump_file, var, 0);
3323       fprintf (dump_file, ": loop information indicates does not overflow\n");
3324     }
3325
3326   return false;
3327 }
3328
3329
3330 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
3331    
3332    - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
3333      all the values in the ranges.
3334
3335    - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
3336
3337    - Return NULL_TREE if it is not always possible to determine the
3338      value of the comparison.
3339
3340    Also set *STRICT_OVERFLOW_P to indicate whether a range with an
3341    overflow infinity was used in the test.  */
3342
3343
3344 static tree
3345 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1,
3346                 bool *strict_overflow_p)
3347 {
3348   /* VARYING or UNDEFINED ranges cannot be compared.  */
3349   if (vr0->type == VR_VARYING
3350       || vr0->type == VR_UNDEFINED
3351       || vr1->type == VR_VARYING
3352       || vr1->type == VR_UNDEFINED)
3353     return NULL_TREE;
3354
3355   /* Anti-ranges need to be handled separately.  */
3356   if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
3357     {
3358       /* If both are anti-ranges, then we cannot compute any
3359          comparison.  */
3360       if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3361         return NULL_TREE;
3362
3363       /* These comparisons are never statically computable.  */
3364       if (comp == GT_EXPR
3365           || comp == GE_EXPR
3366           || comp == LT_EXPR
3367           || comp == LE_EXPR)
3368         return NULL_TREE;
3369
3370       /* Equality can be computed only between a range and an
3371          anti-range.  ~[VAL1, VAL2] == [VAL1, VAL2] is always false.  */
3372       if (vr0->type == VR_RANGE)
3373         {
3374           /* To simplify processing, make VR0 the anti-range.  */
3375           value_range_t *tmp = vr0;
3376           vr0 = vr1;
3377           vr1 = tmp;
3378         }
3379
3380       gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
3381
3382       if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0
3383           && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0)
3384         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
3385
3386       return NULL_TREE;
3387     }
3388
3389   if (!usable_range_p (vr0, strict_overflow_p)
3390       || !usable_range_p (vr1, strict_overflow_p))
3391     return NULL_TREE;
3392
3393   /* Simplify processing.  If COMP is GT_EXPR or GE_EXPR, switch the
3394      operands around and change the comparison code.  */
3395   if (comp == GT_EXPR || comp == GE_EXPR)
3396     {
3397       value_range_t *tmp;
3398       comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
3399       tmp = vr0;
3400       vr0 = vr1;
3401       vr1 = tmp;
3402     }
3403
3404   if (comp == EQ_EXPR)
3405     {
3406       /* Equality may only be computed if both ranges represent
3407          exactly one value.  */
3408       if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0
3409           && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0)
3410         {
3411           int cmp_min = compare_values_warnv (vr0->min, vr1->min,
3412                                               strict_overflow_p);
3413           int cmp_max = compare_values_warnv (vr0->max, vr1->max,
3414                                               strict_overflow_p);
3415           if (cmp_min == 0 && cmp_max == 0)
3416             return boolean_true_node;
3417           else if (cmp_min != -2 && cmp_max != -2)
3418             return boolean_false_node;
3419         }
3420       /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1.  */
3421       else if (compare_values_warnv (vr0->min, vr1->max,
3422                                      strict_overflow_p) == 1
3423                || compare_values_warnv (vr1->min, vr0->max,
3424                                         strict_overflow_p) == 1)
3425         return boolean_false_node;
3426
3427       return NULL_TREE;
3428     }
3429   else if (comp == NE_EXPR)
3430     {
3431       int cmp1, cmp2;
3432
3433       /* If VR0 is completely to the left or completely to the right
3434          of VR1, they are always different.  Notice that we need to
3435          make sure that both comparisons yield similar results to
3436          avoid comparing values that cannot be compared at
3437          compile-time.  */
3438       cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
3439       cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
3440       if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
3441         return boolean_true_node;
3442
3443       /* If VR0 and VR1 represent a single value and are identical,
3444          return false.  */
3445       else if (compare_values_warnv (vr0->min, vr0->max,
3446                                      strict_overflow_p) == 0
3447                && compare_values_warnv (vr1->min, vr1->max,
3448                                         strict_overflow_p) == 0
3449                && compare_values_warnv (vr0->min, vr1->min,
3450                                         strict_overflow_p) == 0
3451                && compare_values_warnv (vr0->max, vr1->max,
3452                                         strict_overflow_p) == 0)
3453         return boolean_false_node;
3454
3455       /* Otherwise, they may or may not be different.  */
3456       else
3457         return NULL_TREE;
3458     }
3459   else if (comp == LT_EXPR || comp == LE_EXPR)
3460     {
3461       int tst;
3462
3463       /* If VR0 is to the left of VR1, return true.  */
3464       tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
3465       if ((comp == LT_EXPR && tst == -1)
3466           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
3467         {
3468           if (overflow_infinity_range_p (vr0)
3469               || overflow_infinity_range_p (vr1))
3470             *strict_overflow_p = true;
3471           return boolean_true_node;
3472         }
3473
3474       /* If VR0 is to the right of VR1, return false.  */
3475       tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
3476       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
3477           || (comp == LE_EXPR && tst == 1))
3478         {
3479           if (overflow_infinity_range_p (vr0)
3480               || overflow_infinity_range_p (vr1))
3481             *strict_overflow_p = true;
3482           return boolean_false_node;
3483         }
3484
3485       /* Otherwise, we don't know.  */
3486       return NULL_TREE;
3487     }
3488     
3489   gcc_unreachable ();
3490 }
3491
3492
3493 /* Given a value range VR, a value VAL and a comparison code COMP, return
3494    BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
3495    values in VR.  Return BOOLEAN_FALSE_NODE if the comparison
3496    always returns false.  Return NULL_TREE if it is not always
3497    possible to determine the value of the comparison.  Also set
3498    *STRICT_OVERFLOW_P to indicate whether a range with an overflow
3499    infinity was used in the test.  */
3500
3501 static tree
3502 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val,
3503                           bool *strict_overflow_p)
3504 {
3505   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
3506     return NULL_TREE;
3507
3508   /* Anti-ranges need to be handled separately.  */
3509   if (vr->type == VR_ANTI_RANGE)
3510     {
3511       /* For anti-ranges, the only predicates that we can compute at
3512          compile time are equality and inequality.  */
3513       if (comp == GT_EXPR
3514           || comp == GE_EXPR
3515           || comp == LT_EXPR
3516           || comp == LE_EXPR)
3517         return NULL_TREE;
3518
3519       /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2.  */
3520       if (value_inside_range (val, vr) == 1)
3521         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
3522
3523       return NULL_TREE;
3524     }
3525
3526   if (!usable_range_p (vr, strict_overflow_p))
3527     return NULL_TREE;
3528
3529   if (comp == EQ_EXPR)
3530     {
3531       /* EQ_EXPR may only be computed if VR represents exactly
3532          one value.  */
3533       if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0)
3534         {
3535           int cmp = compare_values_warnv (vr->min, val, strict_overflow_p);
3536           if (cmp == 0)
3537             return boolean_true_node;
3538           else if (cmp == -1 || cmp == 1 || cmp == 2)
3539             return boolean_false_node;
3540         }
3541       else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1
3542                || compare_values_warnv (vr->max, val, strict_overflow_p) == -1)
3543         return boolean_false_node;
3544
3545       return NULL_TREE;
3546     }
3547   else if (comp == NE_EXPR)
3548     {
3549       /* If VAL is not inside VR, then they are always different.  */
3550       if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1
3551           || compare_values_warnv (vr->min, val, strict_overflow_p) == 1)
3552         return boolean_true_node;
3553
3554       /* If VR represents exactly one value equal to VAL, then return
3555          false.  */
3556       if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0
3557           && compare_values_warnv (vr->min, val, strict_overflow_p) == 0)
3558         return boolean_false_node;
3559
3560       /* Otherwise, they may or may not be different.  */
3561       return NULL_TREE;
3562     }
3563   else if (comp == LT_EXPR || comp == LE_EXPR)
3564     {
3565       int tst;
3566
3567       /* If VR is to the left of VAL, return true.  */
3568       tst = compare_values_warnv (vr->max, val, strict_overflow_p);
3569       if ((comp == LT_EXPR && tst == -1)
3570           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
3571         {
3572           if (overflow_infinity_range_p (vr))
3573             *strict_overflow_p = true;
3574           return boolean_true_node;
3575         }
3576
3577       /* If VR is to the right of VAL, return false.  */
3578       tst = compare_values_warnv (vr->min, val, strict_overflow_p);
3579       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
3580           || (comp == LE_EXPR && tst == 1))
3581         {
3582           if (overflow_infinity_range_p (vr))
3583             *strict_overflow_p = true;
3584           return boolean_false_node;
3585         }
3586
3587       /* Otherwise, we don't know.  */
3588       return NULL_TREE;
3589     }
3590   else if (comp == GT_EXPR || comp == GE_EXPR)
3591     {
3592       int tst;
3593
3594       /* If VR is to the right of VAL, return true.  */
3595       tst = compare_values_warnv (vr->min, val, strict_overflow_p);
3596       if ((comp == GT_EXPR && tst == 1)
3597           || (comp == GE_EXPR && (tst == 0 || tst == 1)))
3598         {
3599           if (overflow_infinity_range_p (vr))
3600             *strict_overflow_p = true;
3601           return boolean_true_node;
3602         }
3603
3604       /* If VR is to the left of VAL, return false.  */
3605       tst = compare_values_warnv (vr->max, val, strict_overflow_p);
3606       if ((comp == GT_EXPR && (tst == -1 || tst == 0))
3607           || (comp == GE_EXPR && tst == -1))
3608         {
3609           if (overflow_infinity_range_p (vr))
3610             *strict_overflow_p = true;
3611           return boolean_false_node;
3612         }
3613
3614       /* Otherwise, we don't know.  */
3615       return NULL_TREE;
3616     }
3617
3618   gcc_unreachable ();
3619 }
3620
3621
3622 /* Debugging dumps.  */
3623
3624 void dump_value_range (FILE *, value_range_t *);
3625 void debug_value_range (value_range_t *);
3626 void dump_all_value_ranges (FILE *);
3627 void debug_all_value_ranges (void);
3628 void dump_vr_equiv (FILE *, bitmap);
3629 void debug_vr_equiv (bitmap);
3630
3631
3632 /* Dump value range VR to FILE.  */
3633
3634 void
3635 dump_value_range (FILE *file, value_range_t *vr)
3636 {
3637   if (vr == NULL)
3638     fprintf (file, "[]");
3639   else if (vr->type == VR_UNDEFINED)
3640     fprintf (file, "UNDEFINED");
3641   else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
3642     {
3643       tree type = TREE_TYPE (vr->min);
3644
3645       fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
3646
3647       if (is_negative_overflow_infinity (vr->min))
3648         fprintf (file, "-INF(OVF)");
3649       else if (INTEGRAL_TYPE_P (type)
3650                && !TYPE_UNSIGNED (type)
3651                && vrp_val_is_min (vr->min))
3652         fprintf (file, "-INF");
3653       else
3654         print_generic_expr (file, vr->min, 0);
3655
3656       fprintf (file, ", ");
3657
3658       if (is_positive_overflow_infinity (vr->max))
3659         fprintf (file, "+INF(OVF)");
3660       else if (INTEGRAL_TYPE_P (type)
3661                && vrp_val_is_max (vr->max))
3662         fprintf (file, "+INF");
3663       else
3664         print_generic_expr (file, vr->max, 0);
3665
3666       fprintf (file, "]");
3667
3668       if (vr->equiv)
3669         {
3670           bitmap_iterator bi;
3671           unsigned i, c = 0;
3672
3673           fprintf (file, "  EQUIVALENCES: { ");
3674
3675           EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
3676             {
3677               print_generic_expr (file, ssa_name (i), 0);
3678               fprintf (file, " ");
3679               c++;
3680             }
3681
3682           fprintf (file, "} (%u elements)", c);
3683         }
3684     }
3685   else if (vr->type == VR_VARYING)
3686     fprintf (file, "VARYING");
3687   else
3688     fprintf (file, "INVALID RANGE");
3689 }
3690
3691
3692 /* Dump value range VR to stderr.  */
3693
3694 void
3695 debug_value_range (value_range_t *vr)
3696 {
3697   dump_value_range (stderr, vr);
3698   fprintf (stderr, "\n");
3699 }
3700
3701
3702 /* Dump value ranges of all SSA_NAMEs to FILE.  */
3703
3704 void
3705 dump_all_value_ranges (FILE *file)
3706 {
3707   size_t i;
3708
3709   for (i = 0; i < num_ssa_names; i++)
3710     {
3711       if (vr_value[i])
3712         {
3713           print_generic_expr (file, ssa_name (i), 0);
3714           fprintf (file, ": ");
3715           dump_value_range (file, vr_value[i]);
3716           fprintf (file, "\n");
3717         }
3718     }
3719
3720   fprintf (file, "\n");
3721 }
3722
3723
3724 /* Dump all value ranges to stderr.  */
3725
3726 void
3727 debug_all_value_ranges (void)
3728 {
3729   dump_all_value_ranges (stderr);
3730 }
3731
3732
3733 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
3734    create a new SSA name N and return the assertion assignment
3735    'V = ASSERT_EXPR <V, V OP W>'.  */
3736
3737 static gimple
3738 build_assert_expr_for (tree cond, tree v)
3739 {
3740   tree n;
3741   gimple assertion;
3742
3743   gcc_assert (TREE_CODE (v) == SSA_NAME);
3744   n = duplicate_ssa_name (v, NULL);
3745
3746   if (COMPARISON_CLASS_P (cond))
3747     {
3748       tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond); 
3749       assertion = gimple_build_assign (n, a);
3750     }
3751   else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
3752     {
3753       /* Given !V, build the assignment N = false.  */
3754       tree op0 = TREE_OPERAND (cond, 0);
3755       gcc_assert (op0 == v);
3756       assertion = gimple_build_assign (n, boolean_false_node);
3757     }
3758   else if (TREE_CODE (cond) == SSA_NAME)
3759     {
3760       /* Given V, build the assignment N = true.  */
3761       gcc_assert (v == cond);
3762       assertion = gimple_build_assign (n, boolean_true_node);
3763     }
3764   else
3765     gcc_unreachable ();
3766
3767   SSA_NAME_DEF_STMT (n) = assertion;
3768
3769   /* The new ASSERT_EXPR, creates a new SSA name that replaces the
3770      operand of the ASSERT_EXPR. Register the new name and the old one
3771      in the replacement table so that we can fix the SSA web after
3772      adding all the ASSERT_EXPRs.  */
3773   register_new_name_mapping (n, v);
3774
3775   return assertion;
3776 }
3777
3778
3779 /* Return false if EXPR is a predicate expression involving floating
3780    point values.  */
3781
3782 static inline bool
3783 fp_predicate (gimple stmt)
3784 {
3785   GIMPLE_CHECK (stmt, GIMPLE_COND);
3786
3787   return FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)));
3788 }
3789
3790
3791 /* If the range of values taken by OP can be inferred after STMT executes,
3792    return the comparison code (COMP_CODE_P) and value (VAL_P) that
3793    describes the inferred range.  Return true if a range could be
3794    inferred.  */
3795
3796 static bool
3797 infer_value_range (gimple stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
3798 {
3799   *val_p = NULL_TREE;
3800   *comp_code_p = ERROR_MARK;
3801
3802   /* Do not attempt to infer anything in names that flow through
3803      abnormal edges.  */
3804   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
3805     return false;
3806
3807   /* Similarly, don't infer anything from statements that may throw
3808      exceptions.  */
3809   if (stmt_could_throw_p (stmt))
3810     return false;
3811
3812   /* If STMT is the last statement of a basic block with no
3813      successors, there is no point inferring anything about any of its
3814      operands.  We would not be able to find a proper insertion point
3815      for the assertion, anyway.  */
3816   if (stmt_ends_bb_p (stmt) && EDGE_COUNT (gimple_bb (stmt)->succs) == 0)
3817     return false;
3818
3819   /* We can only assume that a pointer dereference will yield
3820      non-NULL if -fdelete-null-pointer-checks is enabled.  */
3821   if (flag_delete_null_pointer_checks
3822       && POINTER_TYPE_P (TREE_TYPE (op))
3823       && gimple_code (stmt) != GIMPLE_ASM)
3824     {
3825       unsigned num_uses, num_loads, num_stores;
3826
3827       count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores);
3828       if (num_loads + num_stores > 0)
3829         {
3830           *val_p = build_int_cst (TREE_TYPE (op), 0);
3831           *comp_code_p = NE_EXPR;
3832           return true;
3833         }
3834     }
3835
3836   return false;
3837 }
3838
3839
3840 void dump_asserts_for (FILE *, tree);
3841 void debug_asserts_for (tree);
3842 void dump_all_asserts (FILE *);
3843 void debug_all_asserts (void);
3844
3845 /* Dump all the registered assertions for NAME to FILE.  */
3846
3847 void
3848 dump_asserts_for (FILE *file, tree name)
3849 {
3850   assert_locus_t loc;
3851
3852   fprintf (file, "Assertions to be inserted for ");
3853   print_generic_expr (file, name, 0);
3854   fprintf (file, "\n");
3855
3856   loc = asserts_for[SSA_NAME_VERSION (name)];
3857   while (loc)
3858     {
3859       fprintf (file, "\t");
3860       print_gimple_stmt (file, gsi_stmt (loc->si), 0, 0);
3861       fprintf (file, "\n\tBB #%d", loc->bb->index);
3862       if (loc->e)
3863         {
3864           fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
3865                    loc->e->dest->index);
3866           dump_edge_info (file, loc->e, 0);
3867         }
3868       fprintf (file, "\n\tPREDICATE: ");
3869       print_generic_expr (file, name, 0);
3870       fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
3871       print_generic_expr (file, loc->val, 0);
3872       fprintf (file, "\n\n");
3873       loc = loc->next;
3874     }
3875
3876   fprintf (file, "\n");
3877 }
3878
3879
3880 /* Dump all the registered assertions for NAME to stderr.  */
3881
3882 void
3883 debug_asserts_for (tree name)
3884 {
3885   dump_asserts_for (stderr, name);
3886 }
3887
3888
3889 /* Dump all the registered assertions for all the names to FILE.  */
3890
3891 void
3892 dump_all_asserts (FILE *file)
3893 {
3894   unsigned i;
3895   bitmap_iterator bi;
3896
3897   fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
3898   EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
3899     dump_asserts_for (file, ssa_name (i));
3900   fprintf (file, "\n");
3901 }
3902
3903
3904 /* Dump all the registered assertions for all the names to stderr.  */
3905
3906 void
3907 debug_all_asserts (void)
3908 {
3909   dump_all_asserts (stderr);
3910 }
3911
3912
3913 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
3914    'EXPR COMP_CODE VAL' at a location that dominates block BB or
3915    E->DEST, then register this location as a possible insertion point
3916    for ASSERT_EXPR <NAME, EXPR COMP_CODE VAL>.
3917
3918    BB, E and SI provide the exact insertion point for the new
3919    ASSERT_EXPR.  If BB is NULL, then the ASSERT_EXPR is to be inserted
3920    on edge E.  Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
3921    BB.  If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
3922    must not be NULL.  */
3923
3924 static void
3925 register_new_assert_for (tree name, tree expr,
3926                          enum tree_code comp_code,
3927                          tree val,
3928                          basic_block bb,
3929                          edge e,
3930                          gimple_stmt_iterator si)
3931 {
3932   assert_locus_t n, loc, last_loc;
3933   bool found;
3934   basic_block dest_bb;
3935
3936 #if defined ENABLE_CHECKING
3937   gcc_assert (bb == NULL || e == NULL);
3938
3939   if (e == NULL)
3940     gcc_assert (gimple_code (gsi_stmt (si)) != GIMPLE_COND
3941                 && gimple_code (gsi_stmt (si)) != GIMPLE_SWITCH);
3942 #endif
3943
3944   /* Never build an assert comparing against an integer constant with
3945      TREE_OVERFLOW set.  This confuses our undefined overflow warning
3946      machinery.  */
3947   if (TREE_CODE (val) == INTEGER_CST
3948       && TREE_OVERFLOW (val))
3949     val = build_int_cst_wide (TREE_TYPE (val),
3950                               TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val));
3951
3952   /* The new assertion A will be inserted at BB or E.  We need to
3953      determine if the new location is dominated by a previously
3954      registered location for A.  If we are doing an edge insertion,
3955      assume that A will be inserted at E->DEST.  Note that this is not
3956      necessarily true.
3957      
3958      If E is a critical edge, it will be split.  But even if E is
3959      split, the new block will dominate the same set of blocks that
3960      E->DEST dominates.
3961      
3962      The reverse, however, is not true, blocks dominated by E->DEST
3963      will not be dominated by the new block created to split E.  So,
3964      if the insertion location is on a critical edge, we will not use
3965      the new location to move another assertion previously registered
3966      at a block dominated by E->DEST.  */
3967   dest_bb = (bb) ? bb : e->dest;
3968
3969   /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
3970      VAL at a block dominating DEST_BB, then we don't need to insert a new
3971      one.  Similarly, if the same assertion already exists at a block
3972      dominated by DEST_BB and the new location is not on a critical
3973      edge, then update the existing location for the assertion (i.e.,
3974      move the assertion up in the dominance tree).
3975
3976      Note, this is implemented as a simple linked list because there
3977      should not be more than a handful of assertions registered per
3978      name.  If this becomes a performance problem, a table hashed by
3979      COMP_CODE and VAL could be implemented.  */
3980   loc = asserts_for[SSA_NAME_VERSION (name)];
3981   last_loc = loc;
3982   found = false;
3983   while (loc)
3984     {
3985       if (loc->comp_code == comp_code
3986           && (loc->val == val
3987               || operand_equal_p (loc->val, val, 0))
3988           && (loc->expr == expr
3989               || operand_equal_p (loc->expr, expr, 0)))
3990         {
3991           /* If the assertion NAME COMP_CODE VAL has already been
3992              registered at a basic block that dominates DEST_BB, then
3993              we don't need to insert the same assertion again.  Note
3994              that we don't check strict dominance here to avoid
3995              replicating the same assertion inside the same basic
3996              block more than once (e.g., when a pointer is
3997              dereferenced several times inside a block).
3998
3999              An exception to this rule are edge insertions.  If the
4000              new assertion is to be inserted on edge E, then it will
4001              dominate all the other insertions that we may want to
4002              insert in DEST_BB.  So, if we are doing an edge
4003              insertion, don't do this dominance check.  */
4004           if (e == NULL
4005               && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
4006             return;
4007
4008           /* Otherwise, if E is not a critical edge and DEST_BB
4009              dominates the existing location for the assertion, move
4010              the assertion up in the dominance tree by updating its
4011              location information.  */
4012           if ((e == NULL || !EDGE_CRITICAL_P (e))
4013               && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
4014             {
4015               loc->bb = dest_bb;
4016               loc->e = e;
4017               loc->si = si;
4018               return;
4019             }
4020         }
4021
4022       /* Update the last node of the list and move to the next one.  */
4023       last_loc = loc;
4024       loc = loc->next;
4025     }
4026
4027   /* If we didn't find an assertion already registered for
4028      NAME COMP_CODE VAL, add a new one at the end of the list of
4029      assertions associated with NAME.  */
4030   n = XNEW (struct assert_locus_d);
4031   n->bb = dest_bb;
4032   n->e = e;
4033   n->si = si;
4034   n->comp_code = comp_code;
4035   n->val = val;
4036   n->expr = expr;
4037   n->next = NULL;
4038
4039   if (last_loc)
4040     last_loc->next = n;
4041   else
4042     asserts_for[SSA_NAME_VERSION (name)] = n;
4043
4044   bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
4045 }
4046
4047 /* (COND_OP0 COND_CODE COND_OP1) is a predicate which uses NAME.
4048    Extract a suitable test code and value and store them into *CODE_P and
4049    *VAL_P so the predicate is normalized to NAME *CODE_P *VAL_P.
4050
4051    If no extraction was possible, return FALSE, otherwise return TRUE.
4052
4053    If INVERT is true, then we invert the result stored into *CODE_P.  */
4054
4055 static bool
4056 extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code,
4057                                          tree cond_op0, tree cond_op1,
4058                                          bool invert, enum tree_code *code_p,
4059                                          tree *val_p)
4060 {
4061   enum tree_code comp_code;
4062   tree val;
4063
4064   /* Otherwise, we have a comparison of the form NAME COMP VAL
4065      or VAL COMP NAME.  */
4066   if (name == cond_op1)
4067     {
4068       /* If the predicate is of the form VAL COMP NAME, flip
4069          COMP around because we need to register NAME as the
4070          first operand in the predicate.  */
4071       comp_code = swap_tree_comparison (cond_code);
4072       val = cond_op0;
4073     }
4074   else
4075     {
4076       /* The comparison is of the form NAME COMP VAL, so the
4077          comparison code remains unchanged.  */
4078       comp_code = cond_code;
4079       val = cond_op1;
4080     }
4081
4082   /* Invert the comparison code as necessary.  */
4083   if (invert)
4084     comp_code = invert_tree_comparison (comp_code, 0);
4085