OSDN Git Service

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