OSDN Git Service

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