OSDN Git Service

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