OSDN Git Service

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