OSDN Git Service

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