OSDN Git Service

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