OSDN Git Service

8cac4dfc45a03b0a1dabedd944c71030ccf29d1b
[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 != RSHIFT_EXPR
2088       && code != MIN_EXPR
2089       && code != MAX_EXPR
2090       && code != BIT_AND_EXPR
2091       && code != BIT_IOR_EXPR
2092       && code != TRUTH_AND_EXPR
2093       && code != TRUTH_OR_EXPR)
2094     {
2095       /* We can still do constant propagation here.  */
2096       tree const_op0 = op_with_constant_singleton_value_range (op0);
2097       tree const_op1 = op_with_constant_singleton_value_range (op1);
2098       if (const_op0 || const_op1)
2099         {
2100           tree tem = fold_binary (code, expr_type,
2101                                   const_op0 ? const_op0 : op0,
2102                                   const_op1 ? const_op1 : op1);
2103           if (tem
2104               && is_gimple_min_invariant (tem)
2105               && !is_overflow_infinity (tem))
2106             {
2107               set_value_range (vr, VR_RANGE, tem, tem, NULL);
2108               return;
2109             }
2110         }
2111       set_value_range_to_varying (vr);
2112       return;
2113     }
2114
2115   /* Get value ranges for each operand.  For constant operands, create
2116      a new value range with the operand to simplify processing.  */
2117   if (TREE_CODE (op0) == SSA_NAME)
2118     vr0 = *(get_value_range (op0));
2119   else if (is_gimple_min_invariant (op0))
2120     set_value_range_to_value (&vr0, op0, NULL);
2121   else
2122     set_value_range_to_varying (&vr0);
2123
2124   if (TREE_CODE (op1) == SSA_NAME)
2125     vr1 = *(get_value_range (op1));
2126   else if (is_gimple_min_invariant (op1))
2127     set_value_range_to_value (&vr1, op1, NULL);
2128   else
2129     set_value_range_to_varying (&vr1);
2130
2131   /* If either range is UNDEFINED, so is the result.  */
2132   if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
2133     {
2134       set_value_range_to_undefined (vr);
2135       return;
2136     }
2137
2138   /* The type of the resulting value range defaults to VR0.TYPE.  */
2139   type = vr0.type;
2140
2141   /* Refuse to operate on VARYING ranges, ranges of different kinds
2142      and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
2143      because we may be able to derive a useful range even if one of
2144      the operands is VR_VARYING or symbolic range.  Similarly for
2145      divisions.  TODO, we may be able to derive anti-ranges in
2146      some cases.  */
2147   if (code != BIT_AND_EXPR
2148       && code != TRUTH_AND_EXPR
2149       && code != TRUTH_OR_EXPR
2150       && code != TRUNC_DIV_EXPR
2151       && code != FLOOR_DIV_EXPR
2152       && code != CEIL_DIV_EXPR
2153       && code != EXACT_DIV_EXPR
2154       && code != ROUND_DIV_EXPR
2155       && code != TRUNC_MOD_EXPR
2156       && (vr0.type == VR_VARYING
2157           || vr1.type == VR_VARYING
2158           || vr0.type != vr1.type
2159           || symbolic_range_p (&vr0)
2160           || symbolic_range_p (&vr1)))
2161     {
2162       set_value_range_to_varying (vr);
2163       return;
2164     }
2165
2166   /* Now evaluate the expression to determine the new range.  */
2167   if (POINTER_TYPE_P (expr_type)
2168       || POINTER_TYPE_P (TREE_TYPE (op0))
2169       || POINTER_TYPE_P (TREE_TYPE (op1)))
2170     {
2171       if (code == MIN_EXPR || code == MAX_EXPR)
2172         {
2173           /* For MIN/MAX expressions with pointers, we only care about
2174              nullness, if both are non null, then the result is nonnull.
2175              If both are null, then the result is null. Otherwise they
2176              are varying.  */
2177           if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1))
2178             set_value_range_to_nonnull (vr, expr_type);
2179           else if (range_is_null (&vr0) && range_is_null (&vr1))
2180             set_value_range_to_null (vr, expr_type);
2181           else
2182             set_value_range_to_varying (vr);
2183
2184           return;
2185         }
2186       gcc_assert (code == POINTER_PLUS_EXPR);
2187       /* For pointer types, we are really only interested in asserting
2188          whether the expression evaluates to non-NULL.  */
2189       if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
2190         set_value_range_to_nonnull (vr, expr_type);
2191       else if (range_is_null (&vr0) && range_is_null (&vr1))
2192         set_value_range_to_null (vr, expr_type);
2193       else
2194         set_value_range_to_varying (vr);
2195
2196       return;
2197     }
2198
2199   /* For integer ranges, apply the operation to each end of the
2200      range and see what we end up with.  */
2201   if (code == TRUTH_AND_EXPR
2202       || code == TRUTH_OR_EXPR)
2203     {
2204       /* If one of the operands is zero, we know that the whole
2205          expression evaluates zero.  */
2206       if (code == TRUTH_AND_EXPR
2207           && ((vr0.type == VR_RANGE
2208                && integer_zerop (vr0.min)
2209                && integer_zerop (vr0.max))
2210               || (vr1.type == VR_RANGE
2211                   && integer_zerop (vr1.min)
2212                   && integer_zerop (vr1.max))))
2213         {
2214           type = VR_RANGE;
2215           min = max = build_int_cst (expr_type, 0);
2216         }
2217       /* If one of the operands is one, we know that the whole
2218          expression evaluates one.  */
2219       else if (code == TRUTH_OR_EXPR
2220                && ((vr0.type == VR_RANGE
2221                     && integer_onep (vr0.min)
2222                     && integer_onep (vr0.max))
2223                    || (vr1.type == VR_RANGE
2224                        && integer_onep (vr1.min)
2225                        && integer_onep (vr1.max))))
2226         {
2227           type = VR_RANGE;
2228           min = max = build_int_cst (expr_type, 1);
2229         }
2230       else if (vr0.type != VR_VARYING
2231                && vr1.type != VR_VARYING
2232                && vr0.type == vr1.type
2233                && !symbolic_range_p (&vr0)
2234                && !overflow_infinity_range_p (&vr0)
2235                && !symbolic_range_p (&vr1)
2236                && !overflow_infinity_range_p (&vr1))
2237         {
2238           /* Boolean expressions cannot be folded with int_const_binop.  */
2239           min = fold_binary (code, expr_type, vr0.min, vr1.min);
2240           max = fold_binary (code, expr_type, vr0.max, vr1.max);
2241         }
2242       else
2243         {
2244           /* The result of a TRUTH_*_EXPR is always true or false.  */
2245           set_value_range_to_truthvalue (vr, expr_type);
2246           return;
2247         }
2248     }
2249   else if (code == PLUS_EXPR
2250            || code == MIN_EXPR
2251            || code == MAX_EXPR)
2252     {
2253       /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
2254          VR_VARYING.  It would take more effort to compute a precise
2255          range for such a case.  For example, if we have op0 == 1 and
2256          op1 == -1 with their ranges both being ~[0,0], we would have
2257          op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
2258          Note that we are guaranteed to have vr0.type == vr1.type at
2259          this point.  */
2260       if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
2261         {
2262           set_value_range_to_varying (vr);
2263           return;
2264         }
2265
2266       /* For operations that make the resulting range directly
2267          proportional to the original ranges, apply the operation to
2268          the same end of each range.  */
2269       min = vrp_int_const_binop (code, vr0.min, vr1.min);
2270       max = vrp_int_const_binop (code, vr0.max, vr1.max);
2271
2272       /* If both additions overflowed the range kind is still correct.
2273          This happens regularly with subtracting something in unsigned
2274          arithmetic.
2275          ???  See PR30318 for all the cases we do not handle.  */
2276       if (code == PLUS_EXPR
2277           && (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2278           && (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2279         {
2280           min = build_int_cst_wide (TREE_TYPE (min),
2281                                     TREE_INT_CST_LOW (min),
2282                                     TREE_INT_CST_HIGH (min));
2283           max = build_int_cst_wide (TREE_TYPE (max),
2284                                     TREE_INT_CST_LOW (max),
2285                                     TREE_INT_CST_HIGH (max));
2286         }
2287     }
2288   else if (code == MULT_EXPR
2289            || code == TRUNC_DIV_EXPR
2290            || code == FLOOR_DIV_EXPR
2291            || code == CEIL_DIV_EXPR
2292            || code == EXACT_DIV_EXPR
2293            || code == ROUND_DIV_EXPR
2294            || code == RSHIFT_EXPR)
2295     {
2296       tree val[4];
2297       size_t i;
2298       bool sop;
2299
2300       /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
2301          drop to VR_VARYING.  It would take more effort to compute a
2302          precise range for such a case.  For example, if we have
2303          op0 == 65536 and op1 == 65536 with their ranges both being
2304          ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
2305          we cannot claim that the product is in ~[0,0].  Note that we
2306          are guaranteed to have vr0.type == vr1.type at this
2307          point.  */
2308       if (code == MULT_EXPR
2309           && vr0.type == VR_ANTI_RANGE
2310           && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)))
2311         {
2312           set_value_range_to_varying (vr);
2313           return;
2314         }
2315
2316       /* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
2317          then drop to VR_VARYING.  Outside of this range we get undefined
2318          behavior from the shift operation.  We cannot even trust
2319          SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
2320          shifts, and the operation at the tree level may be widened.  */
2321       if (code == RSHIFT_EXPR)
2322         {
2323           if (vr1.type == VR_ANTI_RANGE
2324               || !vrp_expr_computes_nonnegative (op1, &sop)
2325               || (operand_less_p
2326                   (build_int_cst (TREE_TYPE (vr1.max),
2327                                   TYPE_PRECISION (expr_type) - 1),
2328                    vr1.max) != 0))
2329             {
2330               set_value_range_to_varying (vr);
2331               return;
2332             }
2333         }
2334
2335       else if ((code == TRUNC_DIV_EXPR
2336                 || code == FLOOR_DIV_EXPR
2337                 || code == CEIL_DIV_EXPR
2338                 || code == EXACT_DIV_EXPR
2339                 || code == ROUND_DIV_EXPR)
2340                && (vr0.type != VR_RANGE || symbolic_range_p (&vr0)))
2341         {
2342           /* For division, if op1 has VR_RANGE but op0 does not, something
2343              can be deduced just from that range.  Say [min, max] / [4, max]
2344              gives [min / 4, max / 4] range.  */
2345           if (vr1.type == VR_RANGE
2346               && !symbolic_range_p (&vr1)
2347               && !range_includes_zero_p (&vr1))
2348             {
2349               vr0.type = type = VR_RANGE;
2350               vr0.min = vrp_val_min (TREE_TYPE (op0));
2351               vr0.max = vrp_val_max (TREE_TYPE (op1));
2352             }
2353           else
2354             {
2355               set_value_range_to_varying (vr);
2356               return;
2357             }
2358         }
2359
2360       /* For divisions, if op0 is VR_RANGE, we can deduce a range
2361          even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can
2362          include 0.  */
2363       if ((code == TRUNC_DIV_EXPR
2364            || code == FLOOR_DIV_EXPR
2365            || code == CEIL_DIV_EXPR
2366            || code == EXACT_DIV_EXPR
2367            || code == ROUND_DIV_EXPR)
2368           && vr0.type == VR_RANGE
2369           && (vr1.type != VR_RANGE
2370               || symbolic_range_p (&vr1)
2371               || range_includes_zero_p (&vr1)))
2372         {
2373           tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
2374           int cmp;
2375
2376           sop = false;
2377           min = NULL_TREE;
2378           max = NULL_TREE;
2379           if (vrp_expr_computes_nonnegative (op1, &sop) && !sop)
2380             {
2381               /* For unsigned division or when divisor is known
2382                  to be non-negative, the range has to cover
2383                  all numbers from 0 to max for positive max
2384                  and all numbers from min to 0 for negative min.  */
2385               cmp = compare_values (vr0.max, zero);
2386               if (cmp == -1)
2387                 max = zero;
2388               else if (cmp == 0 || cmp == 1)
2389                 max = vr0.max;
2390               else
2391                 type = VR_VARYING;
2392               cmp = compare_values (vr0.min, zero);
2393               if (cmp == 1)
2394                 min = zero;
2395               else if (cmp == 0 || cmp == -1)
2396                 min = vr0.min;
2397               else
2398                 type = VR_VARYING;
2399             }
2400           else
2401             {
2402               /* Otherwise the range is -max .. max or min .. -min
2403                  depending on which bound is bigger in absolute value,
2404                  as the division can change the sign.  */
2405               abs_extent_range (vr, vr0.min, vr0.max);
2406               return;
2407             }
2408           if (type == VR_VARYING)
2409             {
2410               set_value_range_to_varying (vr);
2411               return;
2412             }
2413         }
2414
2415       /* Multiplications and divisions are a bit tricky to handle,
2416          depending on the mix of signs we have in the two ranges, we
2417          need to operate on different values to get the minimum and
2418          maximum values for the new range.  One approach is to figure
2419          out all the variations of range combinations and do the
2420          operations.
2421
2422          However, this involves several calls to compare_values and it
2423          is pretty convoluted.  It's simpler to do the 4 operations
2424          (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
2425          MAX1) and then figure the smallest and largest values to form
2426          the new range.  */
2427       else
2428         {
2429           gcc_assert ((vr0.type == VR_RANGE
2430                        || (code == MULT_EXPR && vr0.type == VR_ANTI_RANGE))
2431                       && vr0.type == vr1.type);
2432
2433           /* Compute the 4 cross operations.  */
2434           sop = false;
2435           val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
2436           if (val[0] == NULL_TREE)
2437             sop = true;
2438
2439           if (vr1.max == vr1.min)
2440             val[1] = NULL_TREE;
2441           else
2442             {
2443               val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
2444               if (val[1] == NULL_TREE)
2445                 sop = true;
2446             }
2447
2448           if (vr0.max == vr0.min)
2449             val[2] = NULL_TREE;
2450           else
2451             {
2452               val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
2453               if (val[2] == NULL_TREE)
2454                 sop = true;
2455             }
2456
2457           if (vr0.min == vr0.max || vr1.min == vr1.max)
2458             val[3] = NULL_TREE;
2459           else
2460             {
2461               val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
2462               if (val[3] == NULL_TREE)
2463                 sop = true;
2464             }
2465
2466           if (sop)
2467             {
2468               set_value_range_to_varying (vr);
2469               return;
2470             }
2471
2472           /* Set MIN to the minimum of VAL[i] and MAX to the maximum
2473              of VAL[i].  */
2474           min = val[0];
2475           max = val[0];
2476           for (i = 1; i < 4; i++)
2477             {
2478               if (!is_gimple_min_invariant (min)
2479                   || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2480                   || !is_gimple_min_invariant (max)
2481                   || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2482                 break;
2483
2484               if (val[i])
2485                 {
2486                   if (!is_gimple_min_invariant (val[i])
2487                       || (TREE_OVERFLOW (val[i])
2488                           && !is_overflow_infinity (val[i])))
2489                     {
2490                       /* If we found an overflowed value, set MIN and MAX
2491                          to it so that we set the resulting range to
2492                          VARYING.  */
2493                       min = max = val[i];
2494                       break;
2495                     }
2496
2497                   if (compare_values (val[i], min) == -1)
2498                     min = val[i];
2499
2500                   if (compare_values (val[i], max) == 1)
2501                     max = val[i];
2502                 }
2503             }
2504         }
2505     }
2506   else if (code == TRUNC_MOD_EXPR)
2507     {
2508       bool sop = false;
2509       if (vr1.type != VR_RANGE
2510           || symbolic_range_p (&vr1)
2511           || range_includes_zero_p (&vr1)
2512           || vrp_val_is_min (vr1.min))
2513         {
2514           set_value_range_to_varying (vr);
2515           return;
2516         }
2517       type = VR_RANGE;
2518       /* Compute MAX <|vr1.min|, |vr1.max|> - 1.  */
2519       max = fold_unary_to_constant (ABS_EXPR, TREE_TYPE (vr1.min), vr1.min);
2520       if (tree_int_cst_lt (max, vr1.max))
2521         max = vr1.max;
2522       max = int_const_binop (MINUS_EXPR, max, integer_one_node, 0);
2523       /* If the dividend is non-negative the modulus will be
2524          non-negative as well.  */
2525       if (TYPE_UNSIGNED (TREE_TYPE (max))
2526           || (vrp_expr_computes_nonnegative (op0, &sop) && !sop))
2527         min = build_int_cst (TREE_TYPE (max), 0);
2528       else
2529         min = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (max), max);
2530     }
2531   else if (code == MINUS_EXPR)
2532     {
2533       /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
2534          VR_VARYING.  It would take more effort to compute a precise
2535          range for such a case.  For example, if we have op0 == 1 and
2536          op1 == 1 with their ranges both being ~[0,0], we would have
2537          op0 - op1 == 0, so we cannot claim that the difference is in
2538          ~[0,0].  Note that we are guaranteed to have
2539          vr0.type == vr1.type at this point.  */
2540       if (vr0.type == VR_ANTI_RANGE)
2541         {
2542           set_value_range_to_varying (vr);
2543           return;
2544         }
2545
2546       /* For MINUS_EXPR, apply the operation to the opposite ends of
2547          each range.  */
2548       min = vrp_int_const_binop (code, vr0.min, vr1.max);
2549       max = vrp_int_const_binop (code, vr0.max, vr1.min);
2550     }
2551   else if (code == BIT_AND_EXPR)
2552     {
2553       bool vr0_int_cst_singleton_p, vr1_int_cst_singleton_p;
2554
2555       vr0_int_cst_singleton_p = range_int_cst_singleton_p (&vr0);
2556       vr1_int_cst_singleton_p = range_int_cst_singleton_p (&vr1);
2557
2558       if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
2559         min = max = int_const_binop (code, vr0.max, vr1.max, 0);
2560       else if (vr0_int_cst_singleton_p
2561                && tree_int_cst_sgn (vr0.max) >= 0)
2562         {
2563           min = build_int_cst (expr_type, 0);
2564           max = vr0.max;
2565         }
2566       else if (vr1_int_cst_singleton_p
2567                && tree_int_cst_sgn (vr1.max) >= 0)
2568         {
2569           type = VR_RANGE;
2570           min = build_int_cst (expr_type, 0);
2571           max = vr1.max;
2572         }
2573       else
2574         {
2575           set_value_range_to_varying (vr);
2576           return;
2577         }
2578     }
2579   else if (code == BIT_IOR_EXPR)
2580     {
2581       if (range_int_cst_p (&vr0)
2582           && range_int_cst_p (&vr1)
2583           && tree_int_cst_sgn (vr0.min) >= 0
2584           && tree_int_cst_sgn (vr1.min) >= 0)
2585         {
2586           double_int vr0_max = tree_to_double_int (vr0.max);
2587           double_int vr1_max = tree_to_double_int (vr1.max);
2588           double_int ior_max;
2589
2590           /* Set all bits to the right of the most significant one to 1.
2591              For example, [0, 4] | [4, 4] = [4, 7]. */
2592           ior_max.low = vr0_max.low | vr1_max.low;
2593           ior_max.high = vr0_max.high | vr1_max.high;
2594           if (ior_max.high != 0)
2595             {
2596               ior_max.low = ~(unsigned HOST_WIDE_INT)0u;
2597               ior_max.high |= ((HOST_WIDE_INT) 1
2598                                << floor_log2 (ior_max.high)) - 1;
2599             }
2600           else if (ior_max.low != 0)
2601             ior_max.low |= ((unsigned HOST_WIDE_INT) 1u
2602                             << floor_log2 (ior_max.low)) - 1;
2603
2604           /* Both of these endpoints are conservative.  */
2605           min = vrp_int_const_binop (MAX_EXPR, vr0.min, vr1.min);
2606           max = double_int_to_tree (expr_type, ior_max);
2607         }
2608       else
2609         {
2610           set_value_range_to_varying (vr);
2611           return;
2612         }
2613     }
2614   else
2615     gcc_unreachable ();
2616
2617   /* If either MIN or MAX overflowed, then set the resulting range to
2618      VARYING.  But we do accept an overflow infinity
2619      representation.  */
2620   if (min == NULL_TREE
2621       || !is_gimple_min_invariant (min)
2622       || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2623       || max == NULL_TREE
2624       || !is_gimple_min_invariant (max)
2625       || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2626     {
2627       set_value_range_to_varying (vr);
2628       return;
2629     }
2630
2631   /* We punt if:
2632      1) [-INF, +INF]
2633      2) [-INF, +-INF(OVF)]
2634      3) [+-INF(OVF), +INF]
2635      4) [+-INF(OVF), +-INF(OVF)]
2636      We learn nothing when we have INF and INF(OVF) on both sides.
2637      Note that we do accept [-INF, -INF] and [+INF, +INF] without
2638      overflow.  */
2639   if ((vrp_val_is_min (min) || is_overflow_infinity (min))
2640       && (vrp_val_is_max (max) || is_overflow_infinity (max)))
2641     {
2642       set_value_range_to_varying (vr);
2643       return;
2644     }
2645
2646   cmp = compare_values (min, max);
2647   if (cmp == -2 || cmp == 1)
2648     {
2649       /* If the new range has its limits swapped around (MIN > MAX),
2650          then the operation caused one of them to wrap around, mark
2651          the new range VARYING.  */
2652       set_value_range_to_varying (vr);
2653     }
2654   else
2655     set_value_range (vr, type, min, max, NULL);
2656 }
2657
2658
2659 /* Extract range information from a unary expression EXPR based on
2660    the range of its operand and the expression code.  */
2661
2662 static void
2663 extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
2664                                tree type, tree op0)
2665 {
2666   tree min, max;
2667   int cmp;
2668   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2669
2670   /* Refuse to operate on certain unary expressions for which we
2671      cannot easily determine a resulting range.  */
2672   if (code == FIX_TRUNC_EXPR
2673       || code == FLOAT_EXPR
2674       || code == BIT_NOT_EXPR
2675       || code == CONJ_EXPR)
2676     {
2677       /* We can still do constant propagation here.  */
2678       if ((op0 = op_with_constant_singleton_value_range (op0)) != NULL_TREE)
2679         {
2680           tree tem = fold_unary (code, type, op0);
2681           if (tem
2682               && is_gimple_min_invariant (tem)
2683               && !is_overflow_infinity (tem))
2684             {
2685               set_value_range (vr, VR_RANGE, tem, tem, NULL);
2686               return;
2687             }
2688         }
2689       set_value_range_to_varying (vr);
2690       return;
2691     }
2692
2693   /* Get value ranges for the operand.  For constant operands, create
2694      a new value range with the operand to simplify processing.  */
2695   if (TREE_CODE (op0) == SSA_NAME)
2696     vr0 = *(get_value_range (op0));
2697   else if (is_gimple_min_invariant (op0))
2698     set_value_range_to_value (&vr0, op0, NULL);
2699   else
2700     set_value_range_to_varying (&vr0);
2701
2702   /* If VR0 is UNDEFINED, so is the result.  */
2703   if (vr0.type == VR_UNDEFINED)
2704     {
2705       set_value_range_to_undefined (vr);
2706       return;
2707     }
2708
2709   /* Refuse to operate on symbolic ranges, or if neither operand is
2710      a pointer or integral type.  */
2711   if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0))
2712        && !POINTER_TYPE_P (TREE_TYPE (op0)))
2713       || (vr0.type != VR_VARYING
2714           && symbolic_range_p (&vr0)))
2715     {
2716       set_value_range_to_varying (vr);
2717       return;
2718     }
2719
2720   /* If the expression involves pointers, we are only interested in
2721      determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]).  */
2722   if (POINTER_TYPE_P (type) || POINTER_TYPE_P (TREE_TYPE (op0)))
2723     {
2724       bool sop;
2725
2726       sop = false;
2727       if (range_is_nonnull (&vr0)
2728           || (tree_unary_nonzero_warnv_p (code, type, op0, &sop)
2729               && !sop))
2730         set_value_range_to_nonnull (vr, type);
2731       else if (range_is_null (&vr0))
2732         set_value_range_to_null (vr, type);
2733       else
2734         set_value_range_to_varying (vr);
2735
2736       return;
2737     }
2738
2739   /* Handle unary expressions on integer ranges.  */
2740   if (CONVERT_EXPR_CODE_P (code)
2741       && INTEGRAL_TYPE_P (type)
2742       && INTEGRAL_TYPE_P (TREE_TYPE (op0)))
2743     {
2744       tree inner_type = TREE_TYPE (op0);
2745       tree outer_type = type;
2746
2747       /* If VR0 is varying and we increase the type precision, assume
2748          a full range for the following transformation.  */
2749       if (vr0.type == VR_VARYING
2750           && TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type))
2751         {
2752           vr0.type = VR_RANGE;
2753           vr0.min = TYPE_MIN_VALUE (inner_type);
2754           vr0.max = TYPE_MAX_VALUE (inner_type);
2755         }
2756
2757       /* If VR0 is a constant range or anti-range and the conversion is
2758          not truncating we can convert the min and max values and
2759          canonicalize the resulting range.  Otherwise we can do the
2760          conversion if the size of the range is less than what the
2761          precision of the target type can represent and the range is
2762          not an anti-range.  */
2763       if ((vr0.type == VR_RANGE
2764            || vr0.type == VR_ANTI_RANGE)
2765           && TREE_CODE (vr0.min) == INTEGER_CST
2766           && TREE_CODE (vr0.max) == INTEGER_CST
2767           && (!is_overflow_infinity (vr0.min)
2768               || (vr0.type == VR_RANGE
2769                   && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
2770                   && needs_overflow_infinity (outer_type)
2771                   && supports_overflow_infinity (outer_type)))
2772           && (!is_overflow_infinity (vr0.max)
2773               || (vr0.type == VR_RANGE
2774                   && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
2775                   && needs_overflow_infinity (outer_type)
2776                   && supports_overflow_infinity (outer_type)))
2777           && (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type)
2778               || (vr0.type == VR_RANGE
2779                   && integer_zerop (int_const_binop (RSHIFT_EXPR,
2780                        int_const_binop (MINUS_EXPR, vr0.max, vr0.min, 0),
2781                          size_int (TYPE_PRECISION (outer_type)), 0)))))
2782         {
2783           tree new_min, new_max;
2784           new_min = force_fit_type_double (outer_type,
2785                                            TREE_INT_CST_LOW (vr0.min),
2786                                            TREE_INT_CST_HIGH (vr0.min), 0, 0);
2787           new_max = force_fit_type_double (outer_type,
2788                                            TREE_INT_CST_LOW (vr0.max),
2789                                            TREE_INT_CST_HIGH (vr0.max), 0, 0);
2790           if (is_overflow_infinity (vr0.min))
2791             new_min = negative_overflow_infinity (outer_type);
2792           if (is_overflow_infinity (vr0.max))
2793             new_max = positive_overflow_infinity (outer_type);
2794           set_and_canonicalize_value_range (vr, vr0.type,
2795                                             new_min, new_max, NULL);
2796           return;
2797         }
2798
2799       set_value_range_to_varying (vr);
2800       return;
2801     }
2802
2803   /* Conversion of a VR_VARYING value to a wider type can result
2804      in a usable range.  So wait until after we've handled conversions
2805      before dropping the result to VR_VARYING if we had a source
2806      operand that is VR_VARYING.  */
2807   if (vr0.type == VR_VARYING)
2808     {
2809       set_value_range_to_varying (vr);
2810       return;
2811     }
2812
2813   /* Apply the operation to each end of the range and see what we end
2814      up with.  */
2815   if (code == NEGATE_EXPR
2816       && !TYPE_UNSIGNED (type))
2817     {
2818       /* NEGATE_EXPR flips the range around.  We need to treat
2819          TYPE_MIN_VALUE specially.  */
2820       if (is_positive_overflow_infinity (vr0.max))
2821         min = negative_overflow_infinity (type);
2822       else if (is_negative_overflow_infinity (vr0.max))
2823         min = positive_overflow_infinity (type);
2824       else if (!vrp_val_is_min (vr0.max))
2825         min = fold_unary_to_constant (code, type, vr0.max);
2826       else if (needs_overflow_infinity (type))
2827         {
2828           if (supports_overflow_infinity (type)
2829               && !is_overflow_infinity (vr0.min)
2830               && !vrp_val_is_min (vr0.min))
2831             min = positive_overflow_infinity (type);
2832           else
2833             {
2834               set_value_range_to_varying (vr);
2835               return;
2836             }
2837         }
2838       else
2839         min = TYPE_MIN_VALUE (type);
2840
2841       if (is_positive_overflow_infinity (vr0.min))
2842         max = negative_overflow_infinity (type);
2843       else if (is_negative_overflow_infinity (vr0.min))
2844         max = positive_overflow_infinity (type);
2845       else if (!vrp_val_is_min (vr0.min))
2846         max = fold_unary_to_constant (code, type, vr0.min);
2847       else if (needs_overflow_infinity (type))
2848         {
2849           if (supports_overflow_infinity (type))
2850             max = positive_overflow_infinity (type);
2851           else
2852             {
2853               set_value_range_to_varying (vr);
2854               return;
2855             }
2856         }
2857       else
2858         max = TYPE_MIN_VALUE (type);
2859     }
2860   else if (code == NEGATE_EXPR
2861            && TYPE_UNSIGNED (type))
2862     {
2863       if (!range_includes_zero_p (&vr0))
2864         {
2865           max = fold_unary_to_constant (code, type, vr0.min);
2866           min = fold_unary_to_constant (code, type, vr0.max);
2867         }
2868       else
2869         {
2870           if (range_is_null (&vr0))
2871             set_value_range_to_null (vr, type);
2872           else
2873             set_value_range_to_varying (vr);
2874           return;
2875         }
2876     }
2877   else if (code == ABS_EXPR
2878            && !TYPE_UNSIGNED (type))
2879     {
2880       /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
2881          useful range.  */
2882       if (!TYPE_OVERFLOW_UNDEFINED (type)
2883           && ((vr0.type == VR_RANGE
2884                && vrp_val_is_min (vr0.min))
2885               || (vr0.type == VR_ANTI_RANGE
2886                   && !vrp_val_is_min (vr0.min)
2887                   && !range_includes_zero_p (&vr0))))
2888         {
2889           set_value_range_to_varying (vr);
2890           return;
2891         }
2892
2893       /* ABS_EXPR may flip the range around, if the original range
2894          included negative values.  */
2895       if (is_overflow_infinity (vr0.min))
2896         min = positive_overflow_infinity (type);
2897       else if (!vrp_val_is_min (vr0.min))
2898         min = fold_unary_to_constant (code, type, vr0.min);
2899       else if (!needs_overflow_infinity (type))
2900         min = TYPE_MAX_VALUE (type);
2901       else if (supports_overflow_infinity (type))
2902         min = positive_overflow_infinity (type);
2903       else
2904         {
2905           set_value_range_to_varying (vr);
2906           return;
2907         }
2908
2909       if (is_overflow_infinity (vr0.max))
2910         max = positive_overflow_infinity (type);
2911       else if (!vrp_val_is_min (vr0.max))
2912         max = fold_unary_to_constant (code, type, vr0.max);
2913       else if (!needs_overflow_infinity (type))
2914         max = TYPE_MAX_VALUE (type);
2915       else if (supports_overflow_infinity (type)
2916                /* We shouldn't generate [+INF, +INF] as set_value_range
2917                   doesn't like this and ICEs.  */
2918                && !is_positive_overflow_infinity (min))
2919         max = positive_overflow_infinity (type);
2920       else
2921         {
2922           set_value_range_to_varying (vr);
2923           return;
2924         }
2925
2926       cmp = compare_values (min, max);
2927
2928       /* If a VR_ANTI_RANGEs contains zero, then we have
2929          ~[-INF, min(MIN, MAX)].  */
2930       if (vr0.type == VR_ANTI_RANGE)
2931         {
2932           if (range_includes_zero_p (&vr0))
2933             {
2934               /* Take the lower of the two values.  */
2935               if (cmp != 1)
2936                 max = min;
2937
2938               /* Create ~[-INF, min (abs(MIN), abs(MAX))]
2939                  or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
2940                  flag_wrapv is set and the original anti-range doesn't include
2941                  TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE.  */
2942               if (TYPE_OVERFLOW_WRAPS (type))
2943                 {
2944                   tree type_min_value = TYPE_MIN_VALUE (type);
2945
2946                   min = (vr0.min != type_min_value
2947                          ? int_const_binop (PLUS_EXPR, type_min_value,
2948                                             integer_one_node, 0)
2949                          : type_min_value);
2950                 }
2951               else
2952                 {
2953                   if (overflow_infinity_range_p (&vr0))
2954                     min = negative_overflow_infinity (type);
2955                   else
2956                     min = TYPE_MIN_VALUE (type);
2957                 }
2958             }
2959           else
2960             {
2961               /* All else has failed, so create the range [0, INF], even for
2962                  flag_wrapv since TYPE_MIN_VALUE is in the original
2963                  anti-range.  */
2964               vr0.type = VR_RANGE;
2965               min = build_int_cst (type, 0);
2966               if (needs_overflow_infinity (type))
2967                 {
2968                   if (supports_overflow_infinity (type))
2969                     max = positive_overflow_infinity (type);
2970                   else
2971                     {
2972                       set_value_range_to_varying (vr);
2973                       return;
2974                     }
2975                 }
2976               else
2977                 max = TYPE_MAX_VALUE (type);
2978             }
2979         }
2980
2981       /* If the range contains zero then we know that the minimum value in the
2982          range will be zero.  */
2983       else if (range_includes_zero_p (&vr0))
2984         {
2985           if (cmp == 1)
2986             max = min;
2987           min = build_int_cst (type, 0);
2988         }
2989       else
2990         {
2991           /* If the range was reversed, swap MIN and MAX.  */
2992           if (cmp == 1)
2993             {
2994               tree t = min;
2995               min = max;
2996               max = t;
2997             }
2998         }
2999     }
3000   else
3001     {
3002       /* Otherwise, operate on each end of the range.  */
3003       min = fold_unary_to_constant (code, type, vr0.min);
3004       max = fold_unary_to_constant (code, type, vr0.max);
3005
3006       if (needs_overflow_infinity (type))
3007         {
3008           gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR);
3009
3010           /* If both sides have overflowed, we don't know
3011              anything.  */
3012           if ((is_overflow_infinity (vr0.min)
3013                || TREE_OVERFLOW (min))
3014               && (is_overflow_infinity (vr0.max)
3015                   || TREE_OVERFLOW (max)))
3016             {
3017               set_value_range_to_varying (vr);
3018               return;
3019             }
3020
3021           if (is_overflow_infinity (vr0.min))
3022             min = vr0.min;
3023           else if (TREE_OVERFLOW (min))
3024             {
3025               if (supports_overflow_infinity (type))
3026                 min = (tree_int_cst_sgn (min) >= 0
3027                        ? positive_overflow_infinity (TREE_TYPE (min))
3028                        : negative_overflow_infinity (TREE_TYPE (min)));
3029               else
3030                 {
3031                   set_value_range_to_varying (vr);
3032                   return;
3033                 }
3034             }
3035
3036           if (is_overflow_infinity (vr0.max))
3037             max = vr0.max;
3038           else if (TREE_OVERFLOW (max))
3039             {
3040               if (supports_overflow_infinity (type))
3041                 max = (tree_int_cst_sgn (max) >= 0
3042                        ? positive_overflow_infinity (TREE_TYPE (max))
3043                        : negative_overflow_infinity (TREE_TYPE (max)));
3044               else
3045                 {
3046                   set_value_range_to_varying (vr);
3047                   return;
3048                 }
3049             }
3050         }
3051     }
3052
3053   cmp = compare_values (min, max);
3054   if (cmp == -2 || cmp == 1)
3055     {
3056       /* If the new range has its limits swapped around (MIN > MAX),
3057          then the operation caused one of them to wrap around, mark
3058          the new range VARYING.  */
3059       set_value_range_to_varying (vr);
3060     }
3061   else
3062     set_value_range (vr, vr0.type, min, max, NULL);
3063 }
3064
3065
3066 /* Extract range information from a conditional expression EXPR based on
3067    the ranges of each of its operands and the expression code.  */
3068
3069 static void
3070 extract_range_from_cond_expr (value_range_t *vr, tree expr)
3071 {
3072   tree op0, op1;
3073   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3074   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3075
3076   /* Get value ranges for each operand.  For constant operands, create
3077      a new value range with the operand to simplify processing.  */
3078   op0 = COND_EXPR_THEN (expr);
3079   if (TREE_CODE (op0) == SSA_NAME)
3080     vr0 = *(get_value_range (op0));
3081   else if (is_gimple_min_invariant (op0))
3082     set_value_range_to_value (&vr0, op0, NULL);
3083   else
3084     set_value_range_to_varying (&vr0);
3085
3086   op1 = COND_EXPR_ELSE (expr);
3087   if (TREE_CODE (op1) == SSA_NAME)
3088     vr1 = *(get_value_range (op1));
3089   else if (is_gimple_min_invariant (op1))
3090     set_value_range_to_value (&vr1, op1, NULL);
3091   else
3092     set_value_range_to_varying (&vr1);
3093
3094   /* The resulting value range is the union of the operand ranges */
3095   vrp_meet (&vr0, &vr1);
3096   copy_value_range (vr, &vr0);
3097 }
3098
3099
3100 /* Extract range information from a comparison expression EXPR based
3101    on the range of its operand and the expression code.  */
3102
3103 static void
3104 extract_range_from_comparison (value_range_t *vr, enum tree_code code,
3105                                tree type, tree op0, tree op1)
3106 {
3107   bool sop = false;
3108   tree val;
3109
3110   val = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, false, &sop,
3111                                                  NULL);
3112
3113   /* A disadvantage of using a special infinity as an overflow
3114      representation is that we lose the ability to record overflow
3115      when we don't have an infinity.  So we have to ignore a result
3116      which relies on overflow.  */
3117
3118   if (val && !is_overflow_infinity (val) && !sop)
3119     {
3120       /* Since this expression was found on the RHS of an assignment,
3121          its type may be different from _Bool.  Convert VAL to EXPR's
3122          type.  */
3123       val = fold_convert (type, val);
3124       if (is_gimple_min_invariant (val))
3125         set_value_range_to_value (vr, val, vr->equiv);
3126       else
3127         set_value_range (vr, VR_RANGE, val, val, vr->equiv);
3128     }
3129   else
3130     /* The result of a comparison is always true or false.  */
3131     set_value_range_to_truthvalue (vr, type);
3132 }
3133
3134 /* Try to derive a nonnegative or nonzero range out of STMT relying
3135    primarily on generic routines in fold in conjunction with range data.
3136    Store the result in *VR */
3137
3138 static void
3139 extract_range_basic (value_range_t *vr, gimple stmt)
3140 {
3141   bool sop = false;
3142   tree type = gimple_expr_type (stmt);
3143
3144   if (INTEGRAL_TYPE_P (type)
3145       && gimple_stmt_nonnegative_warnv_p (stmt, &sop))
3146     set_value_range_to_nonnegative (vr, type,
3147                                     sop || stmt_overflow_infinity (stmt));
3148   else if (vrp_stmt_computes_nonzero (stmt, &sop)
3149            && !sop)
3150     set_value_range_to_nonnull (vr, type);
3151   else
3152     set_value_range_to_varying (vr);
3153 }
3154
3155
3156 /* Try to compute a useful range out of assignment STMT and store it
3157    in *VR.  */
3158
3159 static void
3160 extract_range_from_assignment (value_range_t *vr, gimple stmt)
3161 {
3162   enum tree_code code = gimple_assign_rhs_code (stmt);
3163
3164   if (code == ASSERT_EXPR)
3165     extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
3166   else if (code == SSA_NAME)
3167     extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
3168   else if (TREE_CODE_CLASS (code) == tcc_binary
3169            || code == TRUTH_AND_EXPR
3170            || code == TRUTH_OR_EXPR
3171            || code == TRUTH_XOR_EXPR)
3172     extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt),
3173                                     gimple_expr_type (stmt),
3174                                     gimple_assign_rhs1 (stmt),
3175                                     gimple_assign_rhs2 (stmt));
3176   else if (TREE_CODE_CLASS (code) == tcc_unary)
3177     extract_range_from_unary_expr (vr, gimple_assign_rhs_code (stmt),
3178                                    gimple_expr_type (stmt),
3179                                    gimple_assign_rhs1 (stmt));
3180   else if (code == COND_EXPR)
3181     extract_range_from_cond_expr (vr, gimple_assign_rhs1 (stmt));
3182   else if (TREE_CODE_CLASS (code) == tcc_comparison)
3183     extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt),
3184                                    gimple_expr_type (stmt),
3185                                    gimple_assign_rhs1 (stmt),
3186                                    gimple_assign_rhs2 (stmt));
3187   else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
3188            && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
3189     set_value_range_to_value (vr, gimple_assign_rhs1 (stmt), NULL);
3190   else
3191     set_value_range_to_varying (vr);
3192
3193   if (vr->type == VR_VARYING)
3194     extract_range_basic (vr, stmt);
3195 }
3196
3197 /* Given a range VR, a LOOP and a variable VAR, determine whether it
3198    would be profitable to adjust VR using scalar evolution information
3199    for VAR.  If so, update VR with the new limits.  */
3200
3201 static void
3202 adjust_range_with_scev (value_range_t *vr, struct loop *loop,
3203                         gimple stmt, tree var)
3204 {
3205   tree init, step, chrec, tmin, tmax, min, max, type, tem;
3206   enum ev_direction dir;
3207
3208   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
3209      better opportunities than a regular range, but I'm not sure.  */
3210   if (vr->type == VR_ANTI_RANGE)
3211     return;
3212
3213   chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
3214
3215   /* Like in PR19590, scev can return a constant function.  */
3216   if (is_gimple_min_invariant (chrec))
3217     {
3218       set_value_range_to_value (vr, chrec, vr->equiv);
3219       return;
3220     }
3221
3222   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
3223     return;
3224
3225   init = initial_condition_in_loop_num (chrec, loop->num);
3226   tem = op_with_constant_singleton_value_range (init);
3227   if (tem)
3228     init = tem;
3229   step = evolution_part_in_loop_num (chrec, loop->num);
3230   tem = op_with_constant_singleton_value_range (step);
3231   if (tem)
3232     step = tem;
3233
3234   /* If STEP is symbolic, we can't know whether INIT will be the
3235      minimum or maximum value in the range.  Also, unless INIT is
3236      a simple expression, compare_values and possibly other functions
3237      in tree-vrp won't be able to handle it.  */
3238   if (step == NULL_TREE
3239       || !is_gimple_min_invariant (step)
3240       || !valid_value_p (init))
3241     return;
3242
3243   dir = scev_direction (chrec);
3244   if (/* Do not adjust ranges if we do not know whether the iv increases
3245          or decreases,  ... */
3246       dir == EV_DIR_UNKNOWN
3247       /* ... or if it may wrap.  */
3248       || scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
3249                                 true))
3250     return;
3251
3252   /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of
3253      negative_overflow_infinity and positive_overflow_infinity,
3254      because we have concluded that the loop probably does not
3255      wrap.  */
3256
3257   type = TREE_TYPE (var);
3258   if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
3259     tmin = lower_bound_in_type (type, type);
3260   else
3261     tmin = TYPE_MIN_VALUE (type);
3262   if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
3263     tmax = upper_bound_in_type (type, type);
3264   else
3265     tmax = TYPE_MAX_VALUE (type);
3266
3267   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
3268     {
3269       min = tmin;
3270       max = tmax;
3271
3272       /* For VARYING or UNDEFINED ranges, just about anything we get
3273          from scalar evolutions should be better.  */
3274
3275       if (dir == EV_DIR_DECREASES)
3276         max = init;
3277       else
3278         min = init;
3279
3280       /* If we would create an invalid range, then just assume we
3281          know absolutely nothing.  This may be over-conservative,
3282          but it's clearly safe, and should happen only in unreachable
3283          parts of code, or for invalid programs.  */
3284       if (compare_values (min, max) == 1)
3285         return;
3286
3287       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
3288     }
3289   else if (vr->type == VR_RANGE)
3290     {
3291       min = vr->min;
3292       max = vr->max;
3293
3294       if (dir == EV_DIR_DECREASES)
3295         {
3296           /* INIT is the maximum value.  If INIT is lower than VR->MAX
3297              but no smaller than VR->MIN, set VR->MAX to INIT.  */
3298           if (compare_values (init, max) == -1)
3299             {
3300               max = init;
3301
3302               /* If we just created an invalid range with the minimum
3303                  greater than the maximum, we fail conservatively.
3304                  This should happen only in unreachable
3305                  parts of code, or for invalid programs.  */
3306               if (compare_values (min, max) == 1)
3307                 return;
3308             }
3309
3310           /* According to the loop information, the variable does not
3311              overflow.  If we think it does, probably because of an
3312              overflow due to arithmetic on a different INF value,
3313              reset now.  */
3314           if (is_negative_overflow_infinity (min))
3315             min = tmin;
3316         }
3317       else
3318         {
3319           /* If INIT is bigger than VR->MIN, set VR->MIN to INIT.  */
3320           if (compare_values (init, min) == 1)
3321             {
3322               min = init;
3323
3324               /* Again, avoid creating invalid range by failing.  */
3325               if (compare_values (min, max) == 1)
3326                 return;
3327             }
3328
3329           if (is_positive_overflow_infinity (max))
3330             max = tmax;
3331         }
3332
3333       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
3334     }
3335 }
3336
3337 /* Return true if VAR may overflow at STMT.  This checks any available
3338    loop information to see if we can determine that VAR does not
3339    overflow.  */
3340
3341 static bool
3342 vrp_var_may_overflow (tree var, gimple stmt)
3343 {
3344   struct loop *l;
3345   tree chrec, init, step;
3346
3347   if (current_loops == NULL)
3348     return true;
3349
3350   l = loop_containing_stmt (stmt);
3351   if (l == NULL
3352       || !loop_outer (l))
3353     return true;
3354
3355   chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
3356   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
3357     return true;
3358
3359   init = initial_condition_in_loop_num (chrec, l->num);
3360   step = evolution_part_in_loop_num (chrec, l->num);
3361
3362   if (step == NULL_TREE
3363       || !is_gimple_min_invariant (step)
3364       || !valid_value_p (init))
3365     return true;
3366
3367   /* If we get here, we know something useful about VAR based on the
3368      loop information.  If it wraps, it may overflow.  */
3369
3370   if (scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
3371                              true))
3372     return true;
3373
3374   if (dump_file && (dump_flags & TDF_DETAILS) != 0)
3375     {
3376       print_generic_expr (dump_file, var, 0);
3377       fprintf (dump_file, ": loop information indicates does not overflow\n");
3378     }
3379
3380   return false;
3381 }
3382
3383
3384 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
3385
3386    - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
3387      all the values in the ranges.
3388
3389    - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
3390
3391    - Return NULL_TREE if it is not always possible to determine the
3392      value of the comparison.
3393
3394    Also set *STRICT_OVERFLOW_P to indicate whether a range with an
3395    overflow infinity was used in the test.  */
3396
3397
3398 static tree
3399 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1,
3400                 bool *strict_overflow_p)
3401 {
3402   /* VARYING or UNDEFINED ranges cannot be compared.  */
3403   if (vr0->type == VR_VARYING
3404       || vr0->type == VR_UNDEFINED
3405       || vr1->type == VR_VARYING
3406       || vr1->type == VR_UNDEFINED)
3407     return NULL_TREE;
3408
3409   /* Anti-ranges need to be handled separately.  */
3410   if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
3411     {
3412       /* If both are anti-ranges, then we cannot compute any
3413          comparison.  */
3414       if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3415         return NULL_TREE;
3416
3417       /* These comparisons are never statically computable.  */
3418       if (comp == GT_EXPR
3419           || comp == GE_EXPR
3420           || comp == LT_EXPR
3421           || comp == LE_EXPR)
3422         return NULL_TREE;
3423
3424       /* Equality can be computed only between a range and an
3425          anti-range.  ~[VAL1, VAL2] == [VAL1, VAL2] is always false.  */
3426       if (vr0->type == VR_RANGE)
3427         {
3428           /* To simplify processing, make VR0 the anti-range.  */
3429           value_range_t *tmp = vr0;
3430           vr0 = vr1;
3431           vr1 = tmp;
3432         }
3433
3434       gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
3435
3436       if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0
3437           && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0)
3438         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
3439
3440       return NULL_TREE;
3441     }
3442
3443   if (!usable_range_p (vr0, strict_overflow_p)
3444       || !usable_range_p (vr1, strict_overflow_p))
3445     return NULL_TREE;
3446
3447   /* Simplify processing.  If COMP is GT_EXPR or GE_EXPR, switch the
3448      operands around and change the comparison code.  */
3449   if (comp == GT_EXPR || comp == GE_EXPR)
3450     {
3451       value_range_t *tmp;
3452       comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
3453       tmp = vr0;
3454       vr0 = vr1;
3455       vr1 = tmp;
3456     }
3457
3458   if (comp == EQ_EXPR)
3459     {
3460       /* Equality may only be computed if both ranges represent
3461          exactly one value.  */
3462       if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0
3463           && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0)
3464         {
3465           int cmp_min = compare_values_warnv (vr0->min, vr1->min,
3466                                               strict_overflow_p);
3467           int cmp_max = compare_values_warnv (vr0->max, vr1->max,
3468                                               strict_overflow_p);
3469           if (cmp_min == 0 && cmp_max == 0)
3470             return boolean_true_node;
3471           else if (cmp_min != -2 && cmp_max != -2)
3472             return boolean_false_node;
3473         }