OSDN Git Service

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