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