OSDN Git Service

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