1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005, 2006 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>.
5 This file is part of GCC.
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)
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.
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. */
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "tree-dump.h"
34 #include "diagnostic.h"
36 #include "tree-scalar-evolution.h"
37 #include "tree-ssa-propagate.h"
38 #include "tree-chrec.h"
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;
44 /* Local functions. */
45 static int compare_values (tree val1, tree val2);
47 /* Location information for ASSERT_EXPRs. Each instance of this
48 structure describes an ASSERT_EXPR for an SSA name. Since a single
49 SSA name may have more than one assertion associated with it, these
50 locations are kept in a linked list attached to the corresponding
54 /* Basic block where the assertion would be inserted. */
57 /* Some assertions need to be inserted on an edge (e.g., assertions
58 generated by COND_EXPRs). In those cases, BB will be NULL. */
61 /* Pointer to the statement that generated this assertion. */
62 block_stmt_iterator si;
64 /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */
65 enum tree_code comp_code;
67 /* Value being compared against. */
70 /* Next node in the linked list. */
71 struct assert_locus_d *next;
74 typedef struct assert_locus_d *assert_locus_t;
76 /* If bit I is present, it means that SSA name N_i has a list of
77 assertions that should be inserted in the IL. */
78 static bitmap need_assert_for;
80 /* Array of locations lists where to insert assertions. ASSERTS_FOR[I]
81 holds a list of ASSERT_LOCUS_T nodes that describe where
82 ASSERT_EXPRs for SSA name N_I should be inserted. */
83 static assert_locus_t *asserts_for;
85 /* Set of blocks visited in find_assert_locations. Used to avoid
86 visiting the same block more than once. */
87 static sbitmap blocks_visited;
89 /* Value range array. After propagation, VR_VALUE[I] holds the range
90 of values that SSA name N_I may take. */
91 static value_range_t **vr_value;
94 /* Return true if ARG is marked with the nonnull attribute in the
95 current function signature. */
98 nonnull_arg_p (tree arg)
100 tree t, attrs, fntype;
101 unsigned HOST_WIDE_INT arg_num;
103 gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg)));
105 fntype = TREE_TYPE (current_function_decl);
106 attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype));
108 /* If "nonnull" wasn't specified, we know nothing about the argument. */
109 if (attrs == NULL_TREE)
112 /* If "nonnull" applies to all the arguments, then ARG is non-null. */
113 if (TREE_VALUE (attrs) == NULL_TREE)
116 /* Get the position number for ARG in the function signature. */
117 for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl);
119 t = TREE_CHAIN (t), arg_num++)
125 gcc_assert (t == arg);
127 /* Now see if ARG_NUM is mentioned in the nonnull list. */
128 for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
130 if (compare_tree_int (TREE_VALUE (t), arg_num) == 0)
138 /* Set value range VR to {T, MIN, MAX, EQUIV}. */
141 set_value_range (value_range_t *vr, enum value_range_type t, tree min,
142 tree max, bitmap equiv)
144 #if defined ENABLE_CHECKING
145 /* Check the validity of the range. */
146 if (t == VR_RANGE || t == VR_ANTI_RANGE)
150 gcc_assert (min && max);
152 if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
153 gcc_assert (min != TYPE_MIN_VALUE (TREE_TYPE (min))
154 || max != TYPE_MAX_VALUE (TREE_TYPE (max)));
156 cmp = compare_values (min, max);
157 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
160 if (t == VR_UNDEFINED || t == VR_VARYING)
161 gcc_assert (min == NULL_TREE && max == NULL_TREE);
163 if (t == VR_UNDEFINED || t == VR_VARYING)
164 gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
171 /* Since updating the equivalence set involves deep copying the
172 bitmaps, only do it if absolutely necessary. */
173 if (vr->equiv == NULL)
174 vr->equiv = BITMAP_ALLOC (NULL);
176 if (equiv != vr->equiv)
178 if (equiv && !bitmap_empty_p (equiv))
179 bitmap_copy (vr->equiv, equiv);
181 bitmap_clear (vr->equiv);
186 /* Copy value range FROM into value range TO. */
189 copy_value_range (value_range_t *to, value_range_t *from)
191 set_value_range (to, from->type, from->min, from->max, from->equiv);
195 /* Set value range VR to a non-NULL range of type TYPE. */
198 set_value_range_to_nonnull (value_range_t *vr, tree type)
200 tree zero = build_int_cst (type, 0);
201 set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
205 /* Set value range VR to a NULL range of type TYPE. */
208 set_value_range_to_null (value_range_t *vr, tree type)
210 tree zero = build_int_cst (type, 0);
211 set_value_range (vr, VR_RANGE, zero, zero, vr->equiv);
215 /* Set value range VR to VR_VARYING. */
218 set_value_range_to_varying (value_range_t *vr)
220 vr->type = VR_VARYING;
221 vr->min = vr->max = NULL_TREE;
223 bitmap_clear (vr->equiv);
227 /* Set value range VR to VR_UNDEFINED. */
230 set_value_range_to_undefined (value_range_t *vr)
232 vr->type = VR_UNDEFINED;
233 vr->min = vr->max = NULL_TREE;
235 bitmap_clear (vr->equiv);
239 /* Return value range information for VAR. Create an empty range
242 static value_range_t *
243 get_value_range (tree var)
247 unsigned ver = SSA_NAME_VERSION (var);
253 /* Create a default value range. */
254 vr_value[ver] = vr = XNEW (value_range_t);
255 memset (vr, 0, sizeof (*vr));
257 /* Allocate an equivalence set. */
258 vr->equiv = BITMAP_ALLOC (NULL);
260 /* If VAR is a default definition, the variable can take any value
262 sym = SSA_NAME_VAR (var);
263 if (var == default_def (sym))
265 /* Try to use the "nonnull" attribute to create ~[0, 0]
266 anti-ranges for pointers. Note that this is only valid with
267 default definitions of PARM_DECLs. */
268 if (TREE_CODE (sym) == PARM_DECL
269 && POINTER_TYPE_P (TREE_TYPE (sym))
270 && nonnull_arg_p (sym))
271 set_value_range_to_nonnull (vr, TREE_TYPE (sym));
273 set_value_range_to_varying (vr);
280 /* Update the value range and equivalence set for variable VAR to
281 NEW_VR. Return true if NEW_VR is different from VAR's previous
284 NOTE: This function assumes that NEW_VR is a temporary value range
285 object created for the sole purpose of updating VAR's range. The
286 storage used by the equivalence set from NEW_VR will be freed by
287 this function. Do not call update_value_range when NEW_VR
288 is the range object associated with another SSA name. */
291 update_value_range (tree var, value_range_t *new_vr)
293 value_range_t *old_vr;
296 /* Update the value range, if necessary. */
297 old_vr = get_value_range (var);
298 is_new = old_vr->type != new_vr->type
299 || old_vr->min != new_vr->min
300 || old_vr->max != new_vr->max
301 || (old_vr->equiv == NULL && new_vr->equiv)
302 || (old_vr->equiv && new_vr->equiv == NULL)
303 || (!bitmap_equal_p (old_vr->equiv, new_vr->equiv));
306 set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
309 BITMAP_FREE (new_vr->equiv);
310 new_vr->equiv = NULL;
316 /* Add VAR and VAR's equivalence set to EQUIV. */
319 add_equivalence (bitmap equiv, tree var)
321 unsigned ver = SSA_NAME_VERSION (var);
322 value_range_t *vr = vr_value[ver];
324 bitmap_set_bit (equiv, ver);
326 bitmap_ior_into (equiv, vr->equiv);
330 /* Return true if VR is ~[0, 0]. */
333 range_is_nonnull (value_range_t *vr)
335 return vr->type == VR_ANTI_RANGE
336 && integer_zerop (vr->min)
337 && integer_zerop (vr->max);
341 /* Return true if VR is [0, 0]. */
344 range_is_null (value_range_t *vr)
346 return vr->type == VR_RANGE
347 && integer_zerop (vr->min)
348 && integer_zerop (vr->max);
352 /* Return true if value range VR involves at least one symbol. */
355 symbolic_range_p (value_range_t *vr)
357 return (!is_gimple_min_invariant (vr->min)
358 || !is_gimple_min_invariant (vr->max));
362 /* Like tree_expr_nonzero_p, but this function uses value ranges
366 vrp_expr_computes_nonzero (tree expr)
368 if (tree_expr_nonzero_p (expr))
371 /* If we have an expression of the form &X->a, then the expression
372 is nonnull if X is nonnull. */
373 if (TREE_CODE (expr) == ADDR_EXPR)
375 tree base = get_base_address (TREE_OPERAND (expr, 0));
377 if (base != NULL_TREE
378 && TREE_CODE (base) == INDIRECT_REF
379 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
381 value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
382 if (range_is_nonnull (vr))
391 /* Compare two values VAL1 and VAL2. Return
393 -2 if VAL1 and VAL2 cannot be compared at compile-time,
396 +1 if VAL1 > VAL2, and
399 This is similar to tree_int_cst_compare but supports pointer values
400 and values that cannot be compared at compile time. */
403 compare_values (tree val1, tree val2)
408 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
410 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
411 == POINTER_TYPE_P (TREE_TYPE (val2)));
413 /* Do some limited symbolic comparisons. */
414 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
416 /* We can determine some comparisons against +INF and -INF even
417 if the other value is an expression. */
418 if (val1 == TYPE_MAX_VALUE (TREE_TYPE (val1))
419 && TREE_CODE (val2) == MINUS_EXPR)
421 /* +INF > NAME - CST. */
424 else if (val1 == TYPE_MIN_VALUE (TREE_TYPE (val1))
425 && TREE_CODE (val2) == PLUS_EXPR)
427 /* -INF < NAME + CST. */
430 else if (TREE_CODE (val1) == MINUS_EXPR
431 && val2 == TYPE_MAX_VALUE (TREE_TYPE (val2)))
433 /* NAME - CST < +INF. */
436 else if (TREE_CODE (val1) == PLUS_EXPR
437 && val2 == TYPE_MIN_VALUE (TREE_TYPE (val2)))
439 /* NAME + CST > -INF. */
444 if ((TREE_CODE (val1) == SSA_NAME
445 || TREE_CODE (val1) == PLUS_EXPR
446 || TREE_CODE (val1) == MINUS_EXPR)
447 && (TREE_CODE (val2) == SSA_NAME
448 || TREE_CODE (val2) == PLUS_EXPR
449 || TREE_CODE (val2) == MINUS_EXPR))
453 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
454 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
455 same name, return -2. */
456 if (TREE_CODE (val1) == SSA_NAME)
463 n1 = TREE_OPERAND (val1, 0);
464 c1 = TREE_OPERAND (val1, 1);
467 if (TREE_CODE (val2) == SSA_NAME)
474 n2 = TREE_OPERAND (val2, 0);
475 c2 = TREE_OPERAND (val2, 1);
478 /* Both values must use the same name. */
482 if (TREE_CODE (val1) == SSA_NAME)
484 if (TREE_CODE (val2) == SSA_NAME)
487 else if (TREE_CODE (val2) == PLUS_EXPR)
488 /* NAME < NAME + CST */
490 else if (TREE_CODE (val2) == MINUS_EXPR)
491 /* NAME > NAME - CST */
494 else if (TREE_CODE (val1) == PLUS_EXPR)
496 if (TREE_CODE (val2) == SSA_NAME)
497 /* NAME + CST > NAME */
499 else if (TREE_CODE (val2) == PLUS_EXPR)
500 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
501 return compare_values (c1, c2);
502 else if (TREE_CODE (val2) == MINUS_EXPR)
503 /* NAME + CST1 > NAME - CST2 */
506 else if (TREE_CODE (val1) == MINUS_EXPR)
508 if (TREE_CODE (val2) == SSA_NAME)
509 /* NAME - CST < NAME */
511 else if (TREE_CODE (val2) == PLUS_EXPR)
512 /* NAME - CST1 < NAME + CST2 */
514 else if (TREE_CODE (val2) == MINUS_EXPR)
515 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
516 C1 and C2 are swapped in the call to compare_values. */
517 return compare_values (c2, c1);
523 /* We cannot compare non-constants. */
524 if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
527 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
529 /* We cannot compare overflowed values. */
530 if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
533 return tree_int_cst_compare (val1, val2);
539 /* First see if VAL1 and VAL2 are not the same. */
540 if (val1 == val2 || operand_equal_p (val1, val2, 0))
543 /* If VAL1 is a lower address than VAL2, return -1. */
544 t = fold_binary (LT_EXPR, boolean_type_node, val1, val2);
545 if (t == boolean_true_node)
548 /* If VAL1 is a higher address than VAL2, return +1. */
549 t = fold_binary (GT_EXPR, boolean_type_node, val1, val2);
550 if (t == boolean_true_node)
553 /* If VAL1 is different than VAL2, return +2. */
554 t = fold_binary (NE_EXPR, boolean_type_node, val1, val2);
555 if (t == boolean_true_node)
563 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
564 0 if VAL is not inside VR,
565 -2 if we cannot tell either way.
567 FIXME, the current semantics of this functions are a bit quirky
568 when taken in the context of VRP. In here we do not care
569 about VR's type. If VR is the anti-range ~[3, 5] the call
570 value_inside_range (4, VR) will return 1.
572 This is counter-intuitive in a strict sense, but the callers
573 currently expect this. They are calling the function
574 merely to determine whether VR->MIN <= VAL <= VR->MAX. The
575 callers are applying the VR_RANGE/VR_ANTI_RANGE semantics
578 This also applies to value_ranges_intersect_p and
579 range_includes_zero_p. The semantics of VR_RANGE and
580 VR_ANTI_RANGE should be encoded here, but that also means
581 adapting the users of these functions to the new semantics. */
584 value_inside_range (tree val, value_range_t *vr)
588 cmp1 = compare_values (val, vr->min);
589 if (cmp1 == -2 || cmp1 == 2)
592 cmp2 = compare_values (val, vr->max);
593 if (cmp2 == -2 || cmp2 == 2)
596 return (cmp1 == 0 || cmp1 == 1) && (cmp2 == -1 || cmp2 == 0);
600 /* Return true if value ranges VR0 and VR1 have a non-empty
604 value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
606 return (value_inside_range (vr1->min, vr0) == 1
607 || value_inside_range (vr1->max, vr0) == 1
608 || value_inside_range (vr0->min, vr1) == 1
609 || value_inside_range (vr0->max, vr1) == 1);
613 /* Return true if VR includes the value zero, false otherwise. FIXME,
614 currently this will return false for an anti-range like ~[-4, 3].
615 This will be wrong when the semantics of value_inside_range are
616 modified (currently the users of this function expect these
620 range_includes_zero_p (value_range_t *vr)
624 gcc_assert (vr->type != VR_UNDEFINED
625 && vr->type != VR_VARYING
626 && !symbolic_range_p (vr));
628 zero = build_int_cst (TREE_TYPE (vr->min), 0);
629 return (value_inside_range (zero, vr) == 1);
633 /* When extracting ranges from X_i = ASSERT_EXPR <Y_j, pred>, we will
634 initially consider X_i and Y_j equivalent, so the equivalence set
635 of Y_j is added to the equivalence set of X_i. However, it is
636 possible to have a chain of ASSERT_EXPRs whose predicates are
637 actually incompatible. This is usually the result of nesting of
638 contradictory if-then-else statements. For instance, in PR 24670:
640 count_4 has range [-INF, 63]
644 count_19 = ASSERT_EXPR <count_4, count_4 != 0>
647 count_18 = ASSERT_EXPR <count_19, count_19 > 63>
653 Notice that 'if (count_19 > 63)' is trivially false and will be
654 folded out at the end. However, during propagation, the flowgraph
655 is not cleaned up and so, VRP will evaluate predicates more
656 predicates than necessary, so it must support these
657 inconsistencies. The problem here is that because of the chaining
658 of ASSERT_EXPRs, the equivalency set for count_18 includes count_4.
659 Since count_4 has an incompatible range, we ICE when evaluating the
660 ranges in the equivalency set. So, we need to remove count_4 from
664 fix_equivalence_set (value_range_t *vr_p)
668 bitmap e = vr_p->equiv;
669 bitmap to_remove = BITMAP_ALLOC (NULL);
671 /* Only detect inconsistencies on numeric ranges. */
672 if (vr_p->type == VR_VARYING
673 || vr_p->type == VR_UNDEFINED
674 || symbolic_range_p (vr_p))
677 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
679 value_range_t *equiv_vr = vr_value[i];
681 if (equiv_vr->type == VR_VARYING
682 || equiv_vr->type == VR_UNDEFINED
683 || symbolic_range_p (equiv_vr))
686 if (equiv_vr->type == VR_RANGE
687 && vr_p->type == VR_RANGE
688 && !value_ranges_intersect_p (vr_p, equiv_vr))
689 bitmap_set_bit (to_remove, i);
690 else if ((equiv_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
691 || (equiv_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
693 /* A range and an anti-range have an empty intersection if
694 their end points are the same. FIXME,
695 value_ranges_intersect_p should handle this
697 if (compare_values (equiv_vr->min, vr_p->min) == 0
698 && compare_values (equiv_vr->max, vr_p->max) == 0)
699 bitmap_set_bit (to_remove, i);
703 bitmap_and_compl_into (vr_p->equiv, to_remove);
704 BITMAP_FREE (to_remove);
708 /* Extract value range information from an ASSERT_EXPR EXPR and store
712 extract_range_from_assert (value_range_t *vr_p, tree expr)
714 tree var, cond, limit, min, max, type;
715 value_range_t *var_vr, *limit_vr;
716 enum tree_code cond_code;
718 var = ASSERT_EXPR_VAR (expr);
719 cond = ASSERT_EXPR_COND (expr);
721 gcc_assert (COMPARISON_CLASS_P (cond));
723 /* Find VAR in the ASSERT_EXPR conditional. */
724 if (var == TREE_OPERAND (cond, 0))
726 /* If the predicate is of the form VAR COMP LIMIT, then we just
727 take LIMIT from the RHS and use the same comparison code. */
728 limit = TREE_OPERAND (cond, 1);
729 cond_code = TREE_CODE (cond);
733 /* If the predicate is of the form LIMIT COMP VAR, then we need
734 to flip around the comparison code to create the proper range
736 limit = TREE_OPERAND (cond, 0);
737 cond_code = swap_tree_comparison (TREE_CODE (cond));
740 type = TREE_TYPE (limit);
741 gcc_assert (limit != var);
743 /* For pointer arithmetic, we only keep track of pointer equality
745 if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
747 set_value_range_to_varying (vr_p);
751 /* If LIMIT is another SSA name and LIMIT has a range of its own,
752 try to use LIMIT's range to avoid creating symbolic ranges
754 limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
756 /* LIMIT's range is only interesting if it has any useful information. */
758 && (limit_vr->type == VR_UNDEFINED
759 || limit_vr->type == VR_VARYING
760 || symbolic_range_p (limit_vr)))
763 /* Special handling for integral types with super-types. Some FEs
764 construct integral types derived from other types and restrict
765 the range of values these new types may take.
767 It may happen that LIMIT is actually smaller than TYPE's minimum
768 value. For instance, the Ada FE is generating code like this
771 D.1480_32 = nam_30 - 300000361;
772 if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
774 D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;
776 All the names are of type types__name_id___XDLU_300000000__399999999
777 which has min == 300000000 and max == 399999999. This means that
778 the ASSERT_EXPR would try to create the range [3000000, 1] which
781 The fact that the type specifies MIN and MAX values does not
782 automatically mean that every variable of that type will always
783 be within that range, so the predicate may well be true at run
784 time. If we had symbolic -INF and +INF values, we could
785 represent this range, but we currently represent -INF and +INF
786 using the type's min and max values.
788 So, the only sensible thing we can do for now is set the
789 resulting range to VR_VARYING. TODO, would having symbolic -INF
790 and +INF values be worth the trouble? */
791 if (TREE_CODE (limit) != SSA_NAME
792 && INTEGRAL_TYPE_P (type)
795 if (cond_code == LE_EXPR || cond_code == LT_EXPR)
797 tree type_min = TYPE_MIN_VALUE (type);
798 int cmp = compare_values (limit, type_min);
800 /* For < or <= comparisons, if LIMIT is smaller than
801 TYPE_MIN, set the range to VR_VARYING. */
802 if (cmp == -1 || cmp == 0)
804 set_value_range_to_varying (vr_p);
808 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
810 tree type_max = TYPE_MIN_VALUE (type);
811 int cmp = compare_values (limit, type_max);
813 /* For > or >= comparisons, if LIMIT is bigger than
814 TYPE_MAX, set the range to VR_VARYING. */
815 if (cmp == 1 || cmp == 0)
817 set_value_range_to_varying (vr_p);
823 /* Initially, the new range has the same set of equivalences of
824 VAR's range. This will be revised before returning the final
825 value. Since assertions may be chained via mutually exclusive
826 predicates, we will need to trim the set of equivalences before
828 gcc_assert (vr_p->equiv == NULL);
829 vr_p->equiv = BITMAP_ALLOC (NULL);
830 add_equivalence (vr_p->equiv, var);
832 /* Extract a new range based on the asserted comparison for VAR and
833 LIMIT's value range. Notice that if LIMIT has an anti-range, we
834 will only use it for equality comparisons (EQ_EXPR). For any
835 other kind of assertion, we cannot derive a range from LIMIT's
836 anti-range that can be used to describe the new range. For
837 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
838 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
839 no single range for x_2 that could describe LE_EXPR, so we might
840 as well build the range [b_4, +INF] for it. */
841 if (cond_code == EQ_EXPR)
843 enum value_range_type range_type;
847 range_type = limit_vr->type;
853 range_type = VR_RANGE;
858 set_value_range (vr_p, range_type, min, max, vr_p->equiv);
860 /* When asserting the equality VAR == LIMIT and LIMIT is another
861 SSA name, the new range will also inherit the equivalence set
863 if (TREE_CODE (limit) == SSA_NAME)
864 add_equivalence (vr_p->equiv, limit);
866 else if (cond_code == NE_EXPR)
868 /* As described above, when LIMIT's range is an anti-range and
869 this assertion is an inequality (NE_EXPR), then we cannot
870 derive anything from the anti-range. For instance, if
871 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
872 not imply that VAR's range is [0, 0]. So, in the case of
873 anti-ranges, we just assert the inequality using LIMIT and
876 If LIMIT_VR is a range, we can only use it to build a new
877 anti-range if LIMIT_VR is a single-valued range. For
878 instance, if LIMIT_VR is [0, 1], the predicate
879 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
880 Rather, it means that for value 0 VAR should be ~[0, 0]
881 and for value 1, VAR should be ~[1, 1]. We cannot
882 represent these ranges.
884 The only situation in which we can build a valid
885 anti-range is when LIMIT_VR is a single-valued range
886 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
887 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
889 && limit_vr->type == VR_RANGE
890 && compare_values (limit_vr->min, limit_vr->max) == 0)
897 /* In any other case, we cannot use LIMIT's range to build a
902 /* If MIN and MAX cover the whole range for their type, then
903 just use the original LIMIT. */
904 if (INTEGRAL_TYPE_P (type)
905 && min == TYPE_MIN_VALUE (type)
906 && max == TYPE_MAX_VALUE (type))
909 set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
911 else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
913 min = TYPE_MIN_VALUE (type);
915 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
919 /* If LIMIT_VR is of the form [N1, N2], we need to build the
920 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
925 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
926 if (cond_code == LT_EXPR)
928 tree one = build_int_cst (type, 1);
929 max = fold_build2 (MINUS_EXPR, type, max, one);
932 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
934 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
936 max = TYPE_MAX_VALUE (type);
938 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
942 /* If LIMIT_VR is of the form [N1, N2], we need to build the
943 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
948 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
949 if (cond_code == GT_EXPR)
951 tree one = build_int_cst (type, 1);
952 min = fold_build2 (PLUS_EXPR, type, min, one);
955 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
960 /* If VAR already had a known range, it may happen that the new
961 range we have computed and VAR's range are not compatible. For
965 p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
967 p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
969 While the above comes from a faulty program, it will cause an ICE
970 later because p_8 and p_6 will have incompatible ranges and at
971 the same time will be considered equivalent. A similar situation
975 i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
977 i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
979 Again i_6 and i_7 will have incompatible ranges. It would be
980 pointless to try and do anything with i_7's range because
981 anything dominated by 'if (i_5 < 5)' will be optimized away.
982 Note, due to the wa in which simulation proceeds, the statement
983 i_7 = ASSERT_EXPR <...> we would never be visited because the
984 conditional 'if (i_5 < 5)' always evaluates to false. However,
985 this extra check does not hurt and may protect against future
986 changes to VRP that may get into a situation similar to the
987 NULL pointer dereference example.
989 Note that these compatibility tests are only needed when dealing
990 with ranges or a mix of range and anti-range. If VAR_VR and VR_P
991 are both anti-ranges, they will always be compatible, because two
992 anti-ranges will always have a non-empty intersection. */
994 var_vr = get_value_range (var);
996 /* We may need to make adjustments when VR_P and VAR_VR are numeric
997 ranges or anti-ranges. */
998 if (vr_p->type == VR_VARYING
999 || vr_p->type == VR_UNDEFINED
1000 || var_vr->type == VR_VARYING
1001 || var_vr->type == VR_UNDEFINED
1002 || symbolic_range_p (vr_p)
1003 || symbolic_range_p (var_vr))
1006 if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
1008 /* If the two ranges have a non-empty intersection, we can
1009 refine the resulting range. Since the assert expression
1010 creates an equivalency and at the same time it asserts a
1011 predicate, we can take the intersection of the two ranges to
1012 get better precision. */
1013 if (value_ranges_intersect_p (var_vr, vr_p))
1015 /* Use the larger of the two minimums. */
1016 if (compare_values (vr_p->min, var_vr->min) == -1)
1021 /* Use the smaller of the two maximums. */
1022 if (compare_values (vr_p->max, var_vr->max) == 1)
1027 set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
1031 /* The two ranges do not intersect, set the new range to
1032 VARYING, because we will not be able to do anything
1033 meaningful with it. */
1034 set_value_range_to_varying (vr_p);
1037 else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
1038 || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
1040 /* A range and an anti-range will cancel each other only if
1041 their ends are the same. For instance, in the example above,
1042 p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
1043 so VR_P should be set to VR_VARYING. */
1044 if (compare_values (var_vr->min, vr_p->min) == 0
1045 && compare_values (var_vr->max, vr_p->max) == 0)
1046 set_value_range_to_varying (vr_p);
1049 tree min, max, anti_min, anti_max, real_min, real_max;
1051 /* We want to compute the logical AND of the two ranges;
1052 there are three cases to consider.
1055 1. The VR_ANTI_RANGE range is competely within the
1056 VR_RANGE and the endpoints of the ranges are
1057 different. In that case the resulting range
1058 should be whichever range is more precise.
1059 Typically that will be the VR_RANGE.
1061 2. The VR_ANTI_RANGE is completely disjoint from
1062 the VR_RANGE. In this case the resulting range
1063 should be the VR_RANGE.
1065 3. There is some overlap between the VR_ANTI_RANGE
1068 3a. If the high limit of the VR_ANTI_RANGE resides
1069 within the VR_RANGE, then the result is a new
1070 VR_RANGE starting at the high limit of the
1071 the VR_ANTI_RANGE + 1 and extending to the
1072 high limit of the original VR_RANGE.
1074 3b. If the low limit of the VR_ANTI_RANGE resides
1075 within the VR_RANGE, then the result is a new
1076 VR_RANGE starting at the low limit of the original
1077 VR_RANGE and extending to the low limit of the
1078 VR_ANTI_RANGE - 1. */
1079 if (vr_p->type == VR_ANTI_RANGE)
1081 anti_min = vr_p->min;
1082 anti_max = vr_p->max;
1083 real_min = var_vr->min;
1084 real_max = var_vr->max;
1088 anti_min = var_vr->min;
1089 anti_max = var_vr->max;
1090 real_min = vr_p->min;
1091 real_max = vr_p->max;
1095 /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
1096 not including any endpoints. */
1097 if (compare_values (anti_max, real_max) == -1
1098 && compare_values (anti_min, real_min) == 1)
1100 set_value_range (vr_p, VR_RANGE, real_min,
1101 real_max, vr_p->equiv);
1103 /* Case 2, VR_ANTI_RANGE completely disjoint from
1105 else if (compare_values (anti_min, real_max) == 1
1106 || compare_values (anti_max, real_min) == -1)
1108 set_value_range (vr_p, VR_RANGE, real_min,
1109 real_max, vr_p->equiv);
1111 /* Case 3a, the anti-range extends into the low
1112 part of the real range. Thus creating a new
1113 low for the real reange. */
1114 else if ((compare_values (anti_max, real_min) == 1
1115 || compare_values (anti_max, real_min) == 0)
1116 && compare_values (anti_max, real_max) == -1)
1118 min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
1120 build_int_cst (TREE_TYPE (var_vr->min), 1));
1122 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1124 /* Case 3b, the anti-range extends into the high
1125 part of the real range. Thus creating a new
1126 higher for the real reange. */
1127 else if (compare_values (anti_min, real_min) == 1
1128 && (compare_values (anti_min, real_max) == -1
1129 || compare_values (anti_min, real_max) == 0))
1131 max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
1133 build_int_cst (TREE_TYPE (var_vr->min), 1));
1135 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1140 /* Remove names from the equivalence set that have ranges
1141 incompatible with VR_P. */
1143 fix_equivalence_set (vr_p);
1147 /* Extract range information from SSA name VAR and store it in VR. If
1148 VAR has an interesting range, use it. Otherwise, create the
1149 range [VAR, VAR] and return it. This is useful in situations where
1150 we may have conditionals testing values of VARYING names. For
1157 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
1161 extract_range_from_ssa_name (value_range_t *vr, tree var)
1163 value_range_t *var_vr = get_value_range (var);
1165 if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
1166 copy_value_range (vr, var_vr);
1168 set_value_range (vr, VR_RANGE, var, var, NULL);
1170 add_equivalence (vr->equiv, var);
1174 /* Wrapper around int_const_binop. If the operation overflows and we
1175 are not using wrapping arithmetic, then adjust the result to be
1176 -INF or +INF depending on CODE, VAL1 and VAL2. */
1179 vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
1184 return int_const_binop (code, val1, val2, 0);
1186 /* If we are not using wrapping arithmetic, operate symbolically
1187 on -INF and +INF. */
1188 res = int_const_binop (code, val1, val2, 0);
1190 if (TYPE_UNSIGNED (TREE_TYPE (val1)))
1192 int checkz = compare_values (res, val1);
1194 /* Ensure that res = val1 + val2 >= val1
1195 or that res = val1 - val2 <= val1. */
1196 if ((code == PLUS_EXPR && !(checkz == 1 || checkz == 0))
1197 || (code == MINUS_EXPR && !(checkz == 0 || checkz == -1)))
1199 res = copy_node (res);
1200 TREE_OVERFLOW (res) = 1;
1203 /* If the operation overflowed but neither VAL1 nor VAL2 are
1204 overflown, return -INF or +INF depending on the operation
1205 and the combination of signs of the operands. */
1206 else if (TREE_OVERFLOW (res)
1207 && !TREE_OVERFLOW (val1)
1208 && !TREE_OVERFLOW (val2))
1210 int sgn1 = tree_int_cst_sgn (val1);
1211 int sgn2 = tree_int_cst_sgn (val2);
1213 /* Notice that we only need to handle the restricted set of
1214 operations handled by extract_range_from_binary_expr.
1215 Among them, only multiplication, addition and subtraction
1216 can yield overflow without overflown operands because we
1217 are working with integral types only... except in the
1218 case VAL1 = -INF and VAL2 = -1 which overflows to +INF
1219 for division too. */
1221 /* For multiplication, the sign of the overflow is given
1222 by the comparison of the signs of the operands. */
1223 if ((code == MULT_EXPR && sgn1 == sgn2)
1224 /* For addition, the operands must be of the same sign
1225 to yield an overflow. Its sign is therefore that
1226 of one of the operands, for example the first. */
1227 || (code == PLUS_EXPR && sgn1 > 0)
1228 /* For subtraction, the operands must be of different
1229 signs to yield an overflow. Its sign is therefore
1230 that of the first operand or the opposite of that
1231 of the second operand. A first operand of 0 counts
1232 as positive here, for the corner case 0 - (-INF),
1233 which overflows, but must yield +INF. */
1234 || (code == MINUS_EXPR && sgn1 >= 0)
1235 /* For division, the only case is -INF / -1 = +INF. */
1236 || code == TRUNC_DIV_EXPR
1237 || code == FLOOR_DIV_EXPR
1238 || code == CEIL_DIV_EXPR
1239 || code == EXACT_DIV_EXPR
1240 || code == ROUND_DIV_EXPR)
1241 return TYPE_MAX_VALUE (TREE_TYPE (res));
1243 return TYPE_MIN_VALUE (TREE_TYPE (res));
1250 /* Extract range information from a binary expression EXPR based on
1251 the ranges of each of its operands and the expression code. */
1254 extract_range_from_binary_expr (value_range_t *vr, tree expr)
1256 enum tree_code code = TREE_CODE (expr);
1257 enum value_range_type type;
1258 tree op0, op1, min, max;
1260 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1261 value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1263 /* Not all binary expressions can be applied to ranges in a
1264 meaningful way. Handle only arithmetic operations. */
1265 if (code != PLUS_EXPR
1266 && code != MINUS_EXPR
1267 && code != MULT_EXPR
1268 && code != TRUNC_DIV_EXPR
1269 && code != FLOOR_DIV_EXPR
1270 && code != CEIL_DIV_EXPR
1271 && code != EXACT_DIV_EXPR
1272 && code != ROUND_DIV_EXPR
1275 && code != BIT_AND_EXPR
1276 && code != TRUTH_ANDIF_EXPR
1277 && code != TRUTH_ORIF_EXPR
1278 && code != TRUTH_AND_EXPR
1279 && code != TRUTH_OR_EXPR
1280 && code != TRUTH_XOR_EXPR)
1282 set_value_range_to_varying (vr);
1286 /* Get value ranges for each operand. For constant operands, create
1287 a new value range with the operand to simplify processing. */
1288 op0 = TREE_OPERAND (expr, 0);
1289 if (TREE_CODE (op0) == SSA_NAME)
1290 vr0 = *(get_value_range (op0));
1291 else if (is_gimple_min_invariant (op0))
1292 set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1294 set_value_range_to_varying (&vr0);
1296 op1 = TREE_OPERAND (expr, 1);
1297 if (TREE_CODE (op1) == SSA_NAME)
1298 vr1 = *(get_value_range (op1));
1299 else if (is_gimple_min_invariant (op1))
1300 set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
1302 set_value_range_to_varying (&vr1);
1304 /* If either range is UNDEFINED, so is the result. */
1305 if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
1307 set_value_range_to_undefined (vr);
1311 /* The type of the resulting value range defaults to VR0.TYPE. */
1314 /* Refuse to operate on VARYING ranges, ranges of different kinds
1315 and symbolic ranges. As an exception, we allow BIT_AND_EXPR
1316 because we may be able to derive a useful range even if one of
1317 the operands is VR_VARYING or symbolic range. TODO, we may be
1318 able to derive anti-ranges in some cases. */
1319 if (code != BIT_AND_EXPR
1320 && code != TRUTH_AND_EXPR
1321 && code != TRUTH_OR_EXPR
1322 && (vr0.type == VR_VARYING
1323 || vr1.type == VR_VARYING
1324 || vr0.type != vr1.type
1325 || symbolic_range_p (&vr0)
1326 || symbolic_range_p (&vr1)))
1328 set_value_range_to_varying (vr);
1332 /* Now evaluate the expression to determine the new range. */
1333 if (POINTER_TYPE_P (TREE_TYPE (expr))
1334 || POINTER_TYPE_P (TREE_TYPE (op0))
1335 || POINTER_TYPE_P (TREE_TYPE (op1)))
1337 /* For pointer types, we are really only interested in asserting
1338 whether the expression evaluates to non-NULL. FIXME, we used
1339 to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
1340 ivopts is generating expressions with pointer multiplication
1342 if (code == PLUS_EXPR)
1344 if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
1345 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1346 else if (range_is_null (&vr0) && range_is_null (&vr1))
1347 set_value_range_to_null (vr, TREE_TYPE (expr));
1349 set_value_range_to_varying (vr);
1353 /* Subtracting from a pointer, may yield 0, so just drop the
1354 resulting range to varying. */
1355 set_value_range_to_varying (vr);
1361 /* For integer ranges, apply the operation to each end of the
1362 range and see what we end up with. */
1363 if (code == TRUTH_ANDIF_EXPR
1364 || code == TRUTH_ORIF_EXPR
1365 || code == TRUTH_AND_EXPR
1366 || code == TRUTH_OR_EXPR
1367 || code == TRUTH_XOR_EXPR)
1369 /* If one of the operands is zero, we know that the whole
1370 expression evaluates zero. */
1371 if (code == TRUTH_AND_EXPR
1372 && ((vr0.type == VR_RANGE
1373 && integer_zerop (vr0.min)
1374 && integer_zerop (vr0.max))
1375 || (vr1.type == VR_RANGE
1376 && integer_zerop (vr1.min)
1377 && integer_zerop (vr1.max))))
1380 min = max = build_int_cst (TREE_TYPE (expr), 0);
1382 /* If one of the operands is one, we know that the whole
1383 expression evaluates one. */
1384 else if (code == TRUTH_OR_EXPR
1385 && ((vr0.type == VR_RANGE
1386 && integer_onep (vr0.min)
1387 && integer_onep (vr0.max))
1388 || (vr1.type == VR_RANGE
1389 && integer_onep (vr1.min)
1390 && integer_onep (vr1.max))))
1393 min = max = build_int_cst (TREE_TYPE (expr), 1);
1395 else if (vr0.type != VR_VARYING
1396 && vr1.type != VR_VARYING
1397 && vr0.type == vr1.type
1398 && !symbolic_range_p (&vr0)
1399 && !symbolic_range_p (&vr1))
1401 /* Boolean expressions cannot be folded with int_const_binop. */
1402 min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
1403 max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
1407 set_value_range_to_varying (vr);
1411 else if (code == PLUS_EXPR
1413 || code == MAX_EXPR)
1415 /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
1416 VR_VARYING. It would take more effort to compute a precise
1417 range for such a case. For example, if we have op0 == 1 and
1418 op1 == -1 with their ranges both being ~[0,0], we would have
1419 op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
1420 Note that we are guaranteed to have vr0.type == vr1.type at
1422 if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
1424 set_value_range_to_varying (vr);
1428 /* For operations that make the resulting range directly
1429 proportional to the original ranges, apply the operation to
1430 the same end of each range. */
1431 min = vrp_int_const_binop (code, vr0.min, vr1.min);
1432 max = vrp_int_const_binop (code, vr0.max, vr1.max);
1434 else if (code == MULT_EXPR
1435 || code == TRUNC_DIV_EXPR
1436 || code == FLOOR_DIV_EXPR
1437 || code == CEIL_DIV_EXPR
1438 || code == EXACT_DIV_EXPR
1439 || code == ROUND_DIV_EXPR)
1444 /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
1445 drop to VR_VARYING. It would take more effort to compute a
1446 precise range for such a case. For example, if we have
1447 op0 == 65536 and op1 == 65536 with their ranges both being
1448 ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
1449 we cannot claim that the product is in ~[0,0]. Note that we
1450 are guaranteed to have vr0.type == vr1.type at this
1452 if (code == MULT_EXPR
1453 && vr0.type == VR_ANTI_RANGE
1454 && (flag_wrapv || TYPE_UNSIGNED (TREE_TYPE (op0))))
1456 set_value_range_to_varying (vr);
1460 /* Multiplications and divisions are a bit tricky to handle,
1461 depending on the mix of signs we have in the two ranges, we
1462 need to operate on different values to get the minimum and
1463 maximum values for the new range. One approach is to figure
1464 out all the variations of range combinations and do the
1467 However, this involves several calls to compare_values and it
1468 is pretty convoluted. It's simpler to do the 4 operations
1469 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
1470 MAX1) and then figure the smallest and largest values to form
1473 /* Divisions by zero result in a VARYING value. */
1474 if (code != MULT_EXPR
1475 && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
1477 set_value_range_to_varying (vr);
1481 /* Compute the 4 cross operations. */
1482 val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
1484 val[1] = (vr1.max != vr1.min)
1485 ? vrp_int_const_binop (code, vr0.min, vr1.max)
1488 val[2] = (vr0.max != vr0.min)
1489 ? vrp_int_const_binop (code, vr0.max, vr1.min)
1492 val[3] = (vr0.min != vr0.max && vr1.min != vr1.max)
1493 ? vrp_int_const_binop (code, vr0.max, vr1.max)
1496 /* Set MIN to the minimum of VAL[i] and MAX to the maximum
1500 for (i = 1; i < 4; i++)
1502 if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
1503 || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
1508 if (!is_gimple_min_invariant (val[i]) || TREE_OVERFLOW (val[i]))
1510 /* If we found an overflowed value, set MIN and MAX
1511 to it so that we set the resulting range to
1517 if (compare_values (val[i], min) == -1)
1520 if (compare_values (val[i], max) == 1)
1525 else if (code == MINUS_EXPR)
1527 /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
1528 VR_VARYING. It would take more effort to compute a precise
1529 range for such a case. For example, if we have op0 == 1 and
1530 op1 == 1 with their ranges both being ~[0,0], we would have
1531 op0 - op1 == 0, so we cannot claim that the difference is in
1532 ~[0,0]. Note that we are guaranteed to have
1533 vr0.type == vr1.type at this point. */
1534 if (vr0.type == VR_ANTI_RANGE)
1536 set_value_range_to_varying (vr);
1540 /* For MINUS_EXPR, apply the operation to the opposite ends of
1542 min = vrp_int_const_binop (code, vr0.min, vr1.max);
1543 max = vrp_int_const_binop (code, vr0.max, vr1.min);
1545 else if (code == BIT_AND_EXPR)
1547 if (vr0.type == VR_RANGE
1548 && vr0.min == vr0.max
1549 && tree_expr_nonnegative_p (vr0.max)
1550 && TREE_CODE (vr0.max) == INTEGER_CST)
1552 min = build_int_cst (TREE_TYPE (expr), 0);
1555 else if (vr1.type == VR_RANGE
1556 && vr1.min == vr1.max
1557 && tree_expr_nonnegative_p (vr1.max)
1558 && TREE_CODE (vr1.max) == INTEGER_CST)
1561 min = build_int_cst (TREE_TYPE (expr), 0);
1566 set_value_range_to_varying (vr);
1573 /* If either MIN or MAX overflowed, then set the resulting range to
1575 if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
1576 || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
1578 set_value_range_to_varying (vr);
1582 cmp = compare_values (min, max);
1583 if (cmp == -2 || cmp == 1)
1585 /* If the new range has its limits swapped around (MIN > MAX),
1586 then the operation caused one of them to wrap around, mark
1587 the new range VARYING. */
1588 set_value_range_to_varying (vr);
1591 set_value_range (vr, type, min, max, NULL);
1595 /* Extract range information from a unary expression EXPR based on
1596 the range of its operand and the expression code. */
1599 extract_range_from_unary_expr (value_range_t *vr, tree expr)
1601 enum tree_code code = TREE_CODE (expr);
1604 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1606 /* Refuse to operate on certain unary expressions for which we
1607 cannot easily determine a resulting range. */
1608 if (code == FIX_TRUNC_EXPR
1609 || code == FIX_CEIL_EXPR
1610 || code == FIX_FLOOR_EXPR
1611 || code == FIX_ROUND_EXPR
1612 || code == FLOAT_EXPR
1613 || code == BIT_NOT_EXPR
1614 || code == NON_LVALUE_EXPR
1615 || code == CONJ_EXPR)
1617 set_value_range_to_varying (vr);
1621 /* Get value ranges for the operand. For constant operands, create
1622 a new value range with the operand to simplify processing. */
1623 op0 = TREE_OPERAND (expr, 0);
1624 if (TREE_CODE (op0) == SSA_NAME)
1625 vr0 = *(get_value_range (op0));
1626 else if (is_gimple_min_invariant (op0))
1627 set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1629 set_value_range_to_varying (&vr0);
1631 /* If VR0 is UNDEFINED, so is the result. */
1632 if (vr0.type == VR_UNDEFINED)
1634 set_value_range_to_undefined (vr);
1638 /* Refuse to operate on varying and symbolic ranges. Also, if the
1639 operand is neither a pointer nor an integral type, set the
1640 resulting range to VARYING. TODO, in some cases we may be able
1641 to derive anti-ranges (like nonzero values). */
1642 if (vr0.type == VR_VARYING
1643 || (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
1644 && !POINTER_TYPE_P (TREE_TYPE (op0)))
1645 || symbolic_range_p (&vr0))
1647 set_value_range_to_varying (vr);
1651 /* If the expression involves pointers, we are only interested in
1652 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
1653 if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
1655 if (range_is_nonnull (&vr0) || tree_expr_nonzero_p (expr))
1656 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1657 else if (range_is_null (&vr0))
1658 set_value_range_to_null (vr, TREE_TYPE (expr));
1660 set_value_range_to_varying (vr);
1665 /* Handle unary expressions on integer ranges. */
1666 if (code == NOP_EXPR || code == CONVERT_EXPR)
1668 tree inner_type = TREE_TYPE (op0);
1669 tree outer_type = TREE_TYPE (expr);
1671 /* If VR0 represents a simple range, then try to convert
1672 the min and max values for the range to the same type
1673 as OUTER_TYPE. If the results compare equal to VR0's
1674 min and max values and the new min is still less than
1675 or equal to the new max, then we can safely use the newly
1676 computed range for EXPR. This allows us to compute
1677 accurate ranges through many casts. */
1678 if (vr0.type == VR_RANGE)
1680 tree new_min, new_max;
1682 /* Convert VR0's min/max to OUTER_TYPE. */
1683 new_min = fold_convert (outer_type, vr0.min);
1684 new_max = fold_convert (outer_type, vr0.max);
1686 /* Verify the new min/max values are gimple values and
1687 that they compare equal to VR0's min/max values. */
1688 if (is_gimple_val (new_min)
1689 && is_gimple_val (new_max)
1690 && tree_int_cst_equal (new_min, vr0.min)
1691 && tree_int_cst_equal (new_max, vr0.max)
1692 && compare_values (new_min, new_max) <= 0
1693 && compare_values (new_min, new_max) >= -1)
1695 set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv);
1700 /* When converting types of different sizes, set the result to
1701 VARYING. Things like sign extensions and precision loss may
1702 change the range. For instance, if x_3 is of type 'long long
1703 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
1704 is impossible to know at compile time whether y_5 will be
1706 if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type)
1707 || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1709 set_value_range_to_varying (vr);
1714 /* Apply the operation to each end of the range and see what we end
1716 if (code == NEGATE_EXPR
1717 && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1719 /* NEGATE_EXPR flips the range around. */
1720 min = (vr0.max == TYPE_MAX_VALUE (TREE_TYPE (expr)) && !flag_wrapv)
1721 ? TYPE_MIN_VALUE (TREE_TYPE (expr))
1722 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1724 max = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)) && !flag_wrapv)
1725 ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1726 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1728 else if (code == ABS_EXPR
1729 && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1731 /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
1734 && ((vr0.type == VR_RANGE
1735 && vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1736 || (vr0.type == VR_ANTI_RANGE
1737 && vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))
1738 && !range_includes_zero_p (&vr0))))
1740 set_value_range_to_varying (vr);
1744 /* ABS_EXPR may flip the range around, if the original range
1745 included negative values. */
1746 min = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1747 ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1748 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1750 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1752 cmp = compare_values (min, max);
1754 /* If a VR_ANTI_RANGEs contains zero, then we have
1755 ~[-INF, min(MIN, MAX)]. */
1756 if (vr0.type == VR_ANTI_RANGE)
1758 if (range_includes_zero_p (&vr0))
1760 tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr));
1762 /* Take the lower of the two values. */
1766 /* Create ~[-INF, min (abs(MIN), abs(MAX))]
1767 or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
1768 flag_wrapv is set and the original anti-range doesn't include
1769 TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */
1770 min = (flag_wrapv && vr0.min != type_min_value
1771 ? int_const_binop (PLUS_EXPR,
1773 integer_one_node, 0)
1778 /* All else has failed, so create the range [0, INF], even for
1779 flag_wrapv since TYPE_MIN_VALUE is in the original
1781 vr0.type = VR_RANGE;
1782 min = build_int_cst (TREE_TYPE (expr), 0);
1783 max = TYPE_MAX_VALUE (TREE_TYPE (expr));
1787 /* If the range contains zero then we know that the minimum value in the
1788 range will be zero. */
1789 else if (range_includes_zero_p (&vr0))
1793 min = build_int_cst (TREE_TYPE (expr), 0);
1797 /* If the range was reversed, swap MIN and MAX. */
1808 /* Otherwise, operate on each end of the range. */
1809 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1810 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1813 cmp = compare_values (min, max);
1814 if (cmp == -2 || cmp == 1)
1816 /* If the new range has its limits swapped around (MIN > MAX),
1817 then the operation caused one of them to wrap around, mark
1818 the new range VARYING. */
1819 set_value_range_to_varying (vr);
1822 set_value_range (vr, vr0.type, min, max, NULL);
1826 /* Extract range information from a comparison expression EXPR based
1827 on the range of its operand and the expression code. */
1830 extract_range_from_comparison (value_range_t *vr, tree expr)
1832 tree val = vrp_evaluate_conditional (expr, false);
1835 /* Since this expression was found on the RHS of an assignment,
1836 its type may be different from _Bool. Convert VAL to EXPR's
1838 val = fold_convert (TREE_TYPE (expr), val);
1839 set_value_range (vr, VR_RANGE, val, val, vr->equiv);
1842 set_value_range_to_varying (vr);
1846 /* Try to compute a useful range out of expression EXPR and store it
1850 extract_range_from_expr (value_range_t *vr, tree expr)
1852 enum tree_code code = TREE_CODE (expr);
1854 if (code == ASSERT_EXPR)
1855 extract_range_from_assert (vr, expr);
1856 else if (code == SSA_NAME)
1857 extract_range_from_ssa_name (vr, expr);
1858 else if (TREE_CODE_CLASS (code) == tcc_binary
1859 || code == TRUTH_ANDIF_EXPR
1860 || code == TRUTH_ORIF_EXPR
1861 || code == TRUTH_AND_EXPR
1862 || code == TRUTH_OR_EXPR
1863 || code == TRUTH_XOR_EXPR)
1864 extract_range_from_binary_expr (vr, expr);
1865 else if (TREE_CODE_CLASS (code) == tcc_unary)
1866 extract_range_from_unary_expr (vr, expr);
1867 else if (TREE_CODE_CLASS (code) == tcc_comparison)
1868 extract_range_from_comparison (vr, expr);
1869 else if (is_gimple_min_invariant (expr))
1870 set_value_range (vr, VR_RANGE, expr, expr, NULL);
1871 else if (vrp_expr_computes_nonzero (expr))
1872 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1874 set_value_range_to_varying (vr);
1877 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1878 would be profitable to adjust VR using scalar evolution information
1879 for VAR. If so, update VR with the new limits. */
1882 adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
1885 tree init, step, chrec;
1886 bool init_is_max, unknown_max;
1888 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1889 better opportunities than a regular range, but I'm not sure. */
1890 if (vr->type == VR_ANTI_RANGE)
1893 chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
1894 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1897 init = initial_condition_in_loop_num (chrec, loop->num);
1898 step = evolution_part_in_loop_num (chrec, loop->num);
1900 /* If STEP is symbolic, we can't know whether INIT will be the
1901 minimum or maximum value in the range. */
1902 if (step == NULL_TREE
1903 || !is_gimple_min_invariant (step))
1906 /* Do not adjust ranges when chrec may wrap. */
1907 if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,
1908 current_loops->parray[CHREC_VARIABLE (chrec)],
1909 &init_is_max, &unknown_max)
1913 if (!POINTER_TYPE_P (TREE_TYPE (init))
1914 && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
1916 /* For VARYING or UNDEFINED ranges, just about anything we get
1917 from scalar evolutions should be better. */
1918 tree min = TYPE_MIN_VALUE (TREE_TYPE (init));
1919 tree max = TYPE_MAX_VALUE (TREE_TYPE (init));
1926 /* If we would create an invalid range, then just assume we
1927 know absolutely nothing. This may be over-conservative,
1928 but it's clearly safe. */
1929 if (compare_values (min, max) == 1)
1932 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
1934 else if (vr->type == VR_RANGE)
1941 /* INIT is the maximum value. If INIT is lower than VR->MAX
1942 but no smaller than VR->MIN, set VR->MAX to INIT. */
1943 if (compare_values (init, max) == -1)
1947 /* If we just created an invalid range with the minimum
1948 greater than the maximum, take the minimum all the
1950 if (compare_values (min, max) == 1)
1951 min = TYPE_MIN_VALUE (TREE_TYPE (min));
1956 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1957 if (compare_values (init, min) == 1)
1961 /* If we just created an invalid range with the minimum
1962 greater than the maximum, take the maximum all the
1964 if (compare_values (min, max) == 1)
1965 max = TYPE_MAX_VALUE (TREE_TYPE (max));
1969 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
1974 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1976 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1977 all the values in the ranges.
1979 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1981 - Return NULL_TREE if it is not always possible to determine the
1982 value of the comparison. */
1986 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1)
1988 /* VARYING or UNDEFINED ranges cannot be compared. */
1989 if (vr0->type == VR_VARYING
1990 || vr0->type == VR_UNDEFINED
1991 || vr1->type == VR_VARYING
1992 || vr1->type == VR_UNDEFINED)
1995 /* Anti-ranges need to be handled separately. */
1996 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
1998 /* If both are anti-ranges, then we cannot compute any
2000 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
2003 /* These comparisons are never statically computable. */
2010 /* Equality can be computed only between a range and an
2011 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
2012 if (vr0->type == VR_RANGE)
2014 /* To simplify processing, make VR0 the anti-range. */
2015 value_range_t *tmp = vr0;
2020 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
2022 if (compare_values (vr0->min, vr1->min) == 0
2023 && compare_values (vr0->max, vr1->max) == 0)
2024 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
2029 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
2030 operands around and change the comparison code. */
2031 if (comp == GT_EXPR || comp == GE_EXPR)
2034 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
2040 if (comp == EQ_EXPR)
2042 /* Equality may only be computed if both ranges represent
2043 exactly one value. */
2044 if (compare_values (vr0->min, vr0->max) == 0
2045 && compare_values (vr1->min, vr1->max) == 0)
2047 int cmp_min = compare_values (vr0->min, vr1->min);
2048 int cmp_max = compare_values (vr0->max, vr1->max);
2049 if (cmp_min == 0 && cmp_max == 0)
2050 return boolean_true_node;
2051 else if (cmp_min != -2 && cmp_max != -2)
2052 return boolean_false_node;
2054 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
2055 else if (compare_values (vr0->min, vr1->max) == 1
2056 || compare_values (vr1->min, vr0->max) == 1)
2057 return boolean_false_node;
2061 else if (comp == NE_EXPR)
2065 /* If VR0 is completely to the left or completely to the right
2066 of VR1, they are always different. Notice that we need to
2067 make sure that both comparisons yield similar results to
2068 avoid comparing values that cannot be compared at
2070 cmp1 = compare_values (vr0->max, vr1->min);
2071 cmp2 = compare_values (vr0->min, vr1->max);
2072 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
2073 return boolean_true_node;
2075 /* If VR0 and VR1 represent a single value and are identical,
2077 else if (compare_values (vr0->min, vr0->max) == 0
2078 && compare_values (vr1->min, vr1->max) == 0
2079 && compare_values (vr0->min, vr1->min) == 0
2080 && compare_values (vr0->max, vr1->max) == 0)
2081 return boolean_false_node;
2083 /* Otherwise, they may or may not be different. */
2087 else if (comp == LT_EXPR || comp == LE_EXPR)
2091 /* If VR0 is to the left of VR1, return true. */
2092 tst = compare_values (vr0->max, vr1->min);
2093 if ((comp == LT_EXPR && tst == -1)
2094 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
2095 return boolean_true_node;
2097 /* If VR0 is to the right of VR1, return false. */
2098 tst = compare_values (vr0->min, vr1->max);
2099 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
2100 || (comp == LE_EXPR && tst == 1))
2101 return boolean_false_node;
2103 /* Otherwise, we don't know. */
2111 /* Given a value range VR, a value VAL and a comparison code COMP, return
2112 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
2113 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
2114 always returns false. Return NULL_TREE if it is not always
2115 possible to determine the value of the comparison. */
2118 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val)
2120 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
2123 /* Anti-ranges need to be handled separately. */
2124 if (vr->type == VR_ANTI_RANGE)
2126 /* For anti-ranges, the only predicates that we can compute at
2127 compile time are equality and inequality. */
2134 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
2135 if (value_inside_range (val, vr) == 1)
2136 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
2141 if (comp == EQ_EXPR)
2143 /* EQ_EXPR may only be computed if VR represents exactly
2145 if (compare_values (vr->min, vr->max) == 0)
2147 int cmp = compare_values (vr->min, val);
2149 return boolean_true_node;
2150 else if (cmp == -1 || cmp == 1 || cmp == 2)
2151 return boolean_false_node;
2153 else if (compare_values (val, vr->min) == -1
2154 || compare_values (vr->max, val) == -1)
2155 return boolean_false_node;
2159 else if (comp == NE_EXPR)
2161 /* If VAL is not inside VR, then they are always different. */
2162 if (compare_values (vr->max, val) == -1
2163 || compare_values (vr->min, val) == 1)
2164 return boolean_true_node;
2166 /* If VR represents exactly one value equal to VAL, then return
2168 if (compare_values (vr->min, vr->max) == 0
2169 && compare_values (vr->min, val) == 0)
2170 return boolean_false_node;
2172 /* Otherwise, they may or may not be different. */
2175 else if (comp == LT_EXPR || comp == LE_EXPR)
2179 /* If VR is to the left of VAL, return true. */
2180 tst = compare_values (vr->max, val);
2181 if ((comp == LT_EXPR && tst == -1)
2182 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
2183 return boolean_true_node;
2185 /* If VR is to the right of VAL, return false. */
2186 tst = compare_values (vr->min, val);
2187 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
2188 || (comp == LE_EXPR && tst == 1))
2189 return boolean_false_node;
2191 /* Otherwise, we don't know. */
2194 else if (comp == GT_EXPR || comp == GE_EXPR)
2198 /* If VR is to the right of VAL, return true. */
2199 tst = compare_values (vr->min, val);
2200 if ((comp == GT_EXPR && tst == 1)
2201 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
2202 return boolean_true_node;
2204 /* If VR is to the left of VAL, return false. */
2205 tst = compare_values (vr->max, val);
2206 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
2207 || (comp == GE_EXPR && tst == -1))
2208 return boolean_false_node;
2210 /* Otherwise, we don't know. */
2218 /* Debugging dumps. */
2220 void dump_value_range (FILE *, value_range_t *);
2221 void debug_value_range (value_range_t *);
2222 void dump_all_value_ranges (FILE *);
2223 void debug_all_value_ranges (void);
2224 void dump_vr_equiv (FILE *, bitmap);
2225 void debug_vr_equiv (bitmap);
2228 /* Dump value range VR to FILE. */
2231 dump_value_range (FILE *file, value_range_t *vr)
2234 fprintf (file, "[]");
2235 else if (vr->type == VR_UNDEFINED)
2236 fprintf (file, "UNDEFINED");
2237 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
2239 tree type = TREE_TYPE (vr->min);
2241 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
2243 if (INTEGRAL_TYPE_P (type)
2244 && !TYPE_UNSIGNED (type)
2245 && vr->min == TYPE_MIN_VALUE (type))
2246 fprintf (file, "-INF");
2248 print_generic_expr (file, vr->min, 0);
2250 fprintf (file, ", ");
2252 if (INTEGRAL_TYPE_P (type)
2253 && vr->max == TYPE_MAX_VALUE (type))
2254 fprintf (file, "+INF");
2256 print_generic_expr (file, vr->max, 0);
2258 fprintf (file, "]");
2265 fprintf (file, " EQUIVALENCES: { ");
2267 EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
2269 print_generic_expr (file, ssa_name (i), 0);
2270 fprintf (file, " ");
2274 fprintf (file, "} (%u elements)", c);
2277 else if (vr->type == VR_VARYING)
2278 fprintf (file, "VARYING");
2280 fprintf (file, "INVALID RANGE");
2284 /* Dump value range VR to stderr. */
2287 debug_value_range (value_range_t *vr)
2289 dump_value_range (stderr, vr);
2293 /* Dump value ranges of all SSA_NAMEs to FILE. */
2296 dump_all_value_ranges (FILE *file)
2300 for (i = 0; i < num_ssa_names; i++)
2304 print_generic_expr (file, ssa_name (i), 0);
2305 fprintf (file, ": ");
2306 dump_value_range (file, vr_value[i]);
2307 fprintf (file, "\n");
2311 fprintf (file, "\n");
2315 /* Dump all value ranges to stderr. */
2318 debug_all_value_ranges (void)
2320 dump_all_value_ranges (stderr);
2324 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
2325 create a new SSA name N and return the assertion assignment
2326 'V = ASSERT_EXPR <V, V OP W>'. */
2329 build_assert_expr_for (tree cond, tree v)
2333 gcc_assert (TREE_CODE (v) == SSA_NAME);
2334 n = duplicate_ssa_name (v, NULL_TREE);
2336 if (COMPARISON_CLASS_P (cond))
2338 tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
2339 assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, a);
2341 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2343 /* Given !V, build the assignment N = false. */
2344 tree op0 = TREE_OPERAND (cond, 0);
2345 gcc_assert (op0 == v);
2346 assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
2348 else if (TREE_CODE (cond) == SSA_NAME)
2350 /* Given V, build the assignment N = true. */
2351 gcc_assert (v == cond);
2352 assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
2357 SSA_NAME_DEF_STMT (n) = assertion;
2359 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
2360 operand of the ASSERT_EXPR. Register the new name and the old one
2361 in the replacement table so that we can fix the SSA web after
2362 adding all the ASSERT_EXPRs. */
2363 register_new_name_mapping (n, v);
2369 /* Return false if EXPR is a predicate expression involving floating
2373 fp_predicate (tree expr)
2375 return (COMPARISON_CLASS_P (expr)
2376 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
2380 /* If the range of values taken by OP can be inferred after STMT executes,
2381 return the comparison code (COMP_CODE_P) and value (VAL_P) that
2382 describes the inferred range. Return true if a range could be
2386 infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
2389 *comp_code_p = ERROR_MARK;
2391 /* Do not attempt to infer anything in names that flow through
2393 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
2396 /* Similarly, don't infer anything from statements that may throw
2398 if (tree_could_throw_p (stmt))
2401 /* If STMT is the last statement of a basic block with no
2402 successors, there is no point inferring anything about any of its
2403 operands. We would not be able to find a proper insertion point
2404 for the assertion, anyway. */
2405 if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
2408 if (POINTER_TYPE_P (TREE_TYPE (op)))
2411 unsigned num_uses, num_derefs;
2413 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
2414 if (num_derefs > 0 && flag_delete_null_pointer_checks)
2416 /* We can only assume that a pointer dereference will yield
2417 non-NULL if -fdelete-null-pointer-checks is enabled. */
2418 *val_p = build_int_cst (TREE_TYPE (op), 0);
2419 *comp_code_p = NE_EXPR;
2428 void dump_asserts_for (FILE *, tree);
2429 void debug_asserts_for (tree);
2430 void dump_all_asserts (FILE *);
2431 void debug_all_asserts (void);
2433 /* Dump all the registered assertions for NAME to FILE. */
2436 dump_asserts_for (FILE *file, tree name)
2440 fprintf (file, "Assertions to be inserted for ");
2441 print_generic_expr (file, name, 0);
2442 fprintf (file, "\n");
2444 loc = asserts_for[SSA_NAME_VERSION (name)];
2447 fprintf (file, "\t");
2448 print_generic_expr (file, bsi_stmt (loc->si), 0);
2449 fprintf (file, "\n\tBB #%d", loc->bb->index);
2452 fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
2453 loc->e->dest->index);
2454 dump_edge_info (file, loc->e, 0);
2456 fprintf (file, "\n\tPREDICATE: ");
2457 print_generic_expr (file, name, 0);
2458 fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
2459 print_generic_expr (file, loc->val, 0);
2460 fprintf (file, "\n\n");
2464 fprintf (file, "\n");
2468 /* Dump all the registered assertions for NAME to stderr. */
2471 debug_asserts_for (tree name)
2473 dump_asserts_for (stderr, name);
2477 /* Dump all the registered assertions for all the names to FILE. */
2480 dump_all_asserts (FILE *file)
2485 fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
2486 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2487 dump_asserts_for (file, ssa_name (i));
2488 fprintf (file, "\n");
2492 /* Dump all the registered assertions for all the names to stderr. */
2495 debug_all_asserts (void)
2497 dump_all_asserts (stderr);
2501 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
2502 'NAME COMP_CODE VAL' at a location that dominates block BB or
2503 E->DEST, then register this location as a possible insertion point
2504 for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
2506 BB, E and SI provide the exact insertion point for the new
2507 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
2508 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
2509 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
2510 must not be NULL. */
2513 register_new_assert_for (tree name,
2514 enum tree_code comp_code,
2518 block_stmt_iterator si)
2520 assert_locus_t n, loc, last_loc;
2522 basic_block dest_bb;
2524 #if defined ENABLE_CHECKING
2525 gcc_assert (bb == NULL || e == NULL);
2528 gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
2529 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
2532 /* The new assertion A will be inserted at BB or E. We need to
2533 determine if the new location is dominated by a previously
2534 registered location for A. If we are doing an edge insertion,
2535 assume that A will be inserted at E->DEST. Note that this is not
2538 If E is a critical edge, it will be split. But even if E is
2539 split, the new block will dominate the same set of blocks that
2542 The reverse, however, is not true, blocks dominated by E->DEST
2543 will not be dominated by the new block created to split E. So,
2544 if the insertion location is on a critical edge, we will not use
2545 the new location to move another assertion previously registered
2546 at a block dominated by E->DEST. */
2547 dest_bb = (bb) ? bb : e->dest;
2549 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
2550 VAL at a block dominating DEST_BB, then we don't need to insert a new
2551 one. Similarly, if the same assertion already exists at a block
2552 dominated by DEST_BB and the new location is not on a critical
2553 edge, then update the existing location for the assertion (i.e.,
2554 move the assertion up in the dominance tree).
2556 Note, this is implemented as a simple linked list because there
2557 should not be more than a handful of assertions registered per
2558 name. If this becomes a performance problem, a table hashed by
2559 COMP_CODE and VAL could be implemented. */
2560 loc = asserts_for[SSA_NAME_VERSION (name)];
2565 if (loc->comp_code == comp_code
2567 || operand_equal_p (loc->val, val, 0)))
2569 /* If the assertion NAME COMP_CODE VAL has already been
2570 registered at a basic block that dominates DEST_BB, then
2571 we don't need to insert the same assertion again. Note
2572 that we don't check strict dominance here to avoid
2573 replicating the same assertion inside the same basic
2574 block more than once (e.g., when a pointer is
2575 dereferenced several times inside a block).
2577 An exception to this rule are edge insertions. If the
2578 new assertion is to be inserted on edge E, then it will
2579 dominate all the other insertions that we may want to
2580 insert in DEST_BB. So, if we are doing an edge
2581 insertion, don't do this dominance check. */
2583 && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
2586 /* Otherwise, if E is not a critical edge and DEST_BB
2587 dominates the existing location for the assertion, move
2588 the assertion up in the dominance tree by updating its
2589 location information. */
2590 if ((e == NULL || !EDGE_CRITICAL_P (e))
2591 && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
2600 /* Update the last node of the list and move to the next one. */
2605 /* If we didn't find an assertion already registered for
2606 NAME COMP_CODE VAL, add a new one at the end of the list of
2607 assertions associated with NAME. */
2608 n = XNEW (struct assert_locus_d);
2612 n->comp_code = comp_code;
2619 asserts_for[SSA_NAME_VERSION (name)] = n;
2621 bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
2625 /* Try to register an edge assertion for SSA name NAME on edge E for
2626 the conditional jump pointed to by SI. Return true if an assertion
2627 for NAME could be registered. */
2630 register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
2633 enum tree_code comp_code;
2635 stmt = bsi_stmt (si);
2637 /* Do not attempt to infer anything in names that flow through
2639 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
2642 /* If NAME was not found in the sub-graph reachable from E, then
2643 there's nothing to do. */
2644 if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
2647 /* We found a use of NAME in the sub-graph rooted at E->DEST.
2648 Register an assertion for NAME according to the value that NAME
2650 if (TREE_CODE (stmt) == COND_EXPR)
2652 /* If BB ends in a COND_EXPR then NAME then we should insert
2653 the original predicate on EDGE_TRUE_VALUE and the
2654 opposite predicate on EDGE_FALSE_VALUE. */
2655 tree cond = COND_EXPR_COND (stmt);
2656 bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
2658 /* Predicates may be a single SSA name or NAME OP VAL. */
2661 /* If the predicate is a name, it must be NAME, in which
2662 case we create the predicate NAME == true or
2663 NAME == false accordingly. */
2664 comp_code = EQ_EXPR;
2665 val = (is_else_edge) ? boolean_false_node : boolean_true_node;
2669 /* Otherwise, we have a comparison of the form NAME COMP VAL
2670 or VAL COMP NAME. */
2671 if (name == TREE_OPERAND (cond, 1))
2673 /* If the predicate is of the form VAL COMP NAME, flip
2674 COMP around because we need to register NAME as the
2675 first operand in the predicate. */
2676 comp_code = swap_tree_comparison (TREE_CODE (cond));
2677 val = TREE_OPERAND (cond, 0);
2681 /* The comparison is of the form NAME COMP VAL, so the
2682 comparison code remains unchanged. */
2683 comp_code = TREE_CODE (cond);
2684 val = TREE_OPERAND (cond, 1);
2687 /* If we are inserting the assertion on the ELSE edge, we
2688 need to invert the sign comparison. */
2690 comp_code = invert_tree_comparison (comp_code, 0);
2692 /* Do not register always-false predicates. FIXME, this
2693 works around a limitation in fold() when dealing with
2694 enumerations. Given 'enum { N1, N2 } x;', fold will not
2695 fold 'if (x > N2)' to 'if (0)'. */
2696 if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
2697 && (INTEGRAL_TYPE_P (TREE_TYPE (val))
2698 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val))))
2700 tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
2701 tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
2703 if (comp_code == GT_EXPR && compare_values (val, max) == 0)
2706 if (comp_code == LT_EXPR && compare_values (val, min) == 0)
2713 /* FIXME. Handle SWITCH_EXPR. */
2717 register_new_assert_for (name, comp_code, val, NULL, e, si);
2722 static bool find_assert_locations (basic_block bb);
2724 /* Determine whether the outgoing edges of BB should receive an
2725 ASSERT_EXPR for each of the operands of BB's last statement. The
2726 last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
2728 If any of the sub-graphs rooted at BB have an interesting use of
2729 the predicate operands, an assert location node is added to the
2730 list of assertions for the corresponding operands. */
2733 find_conditional_asserts (basic_block bb)
2736 block_stmt_iterator last_si;
2742 need_assert = false;
2743 last_si = bsi_last (bb);
2744 last = bsi_stmt (last_si);
2746 /* Look for uses of the operands in each of the sub-graphs
2747 rooted at BB. We need to check each of the outgoing edges
2748 separately, so that we know what kind of ASSERT_EXPR to
2750 FOR_EACH_EDGE (e, ei, bb->succs)
2755 /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
2756 Otherwise, when we finish traversing each of the sub-graphs, we
2757 won't know whether the variables were found in the sub-graphs or
2758 if they had been found in a block upstream from BB. */
2759 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2760 RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2762 /* Traverse the strictly dominated sub-graph rooted at E->DEST
2763 to determine if any of the operands in the conditional
2764 predicate are used. */
2766 need_assert |= find_assert_locations (e->dest);
2768 /* Register the necessary assertions for each operand in the
2769 conditional predicate. */
2770 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2771 need_assert |= register_edge_assert_for (op, e, last_si);
2774 /* Finally, indicate that we have found the operands in the
2776 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2777 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2783 /* Traverse all the statements in block BB looking for statements that
2784 may generate useful assertions for the SSA names in their operand.
2785 If a statement produces a useful assertion A for name N_i, then the
2786 list of assertions already generated for N_i is scanned to
2787 determine if A is actually needed.
2789 If N_i already had the assertion A at a location dominating the
2790 current location, then nothing needs to be done. Otherwise, the
2791 new location for A is recorded instead.
2793 1- For every statement S in BB, all the variables used by S are
2794 added to bitmap FOUND_IN_SUBGRAPH.
2796 2- If statement S uses an operand N in a way that exposes a known
2797 value range for N, then if N was not already generated by an
2798 ASSERT_EXPR, create a new assert location for N. For instance,
2799 if N is a pointer and the statement dereferences it, we can
2800 assume that N is not NULL.
2802 3- COND_EXPRs are a special case of #2. We can derive range
2803 information from the predicate but need to insert different
2804 ASSERT_EXPRs for each of the sub-graphs rooted at the
2805 conditional block. If the last statement of BB is a conditional
2806 expression of the form 'X op Y', then
2808 a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
2810 b) If the conditional is the only entry point to the sub-graph
2811 corresponding to the THEN_CLAUSE, recurse into it. On
2812 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
2813 an ASSERT_EXPR is added for the corresponding variable.
2815 c) Repeat step (b) on the ELSE_CLAUSE.
2817 d) Mark X and Y in FOUND_IN_SUBGRAPH.
2826 In this case, an assertion on the THEN clause is useful to
2827 determine that 'a' is always 9 on that edge. However, an assertion
2828 on the ELSE clause would be unnecessary.
2830 4- If BB does not end in a conditional expression, then we recurse
2831 into BB's dominator children.
2833 At the end of the recursive traversal, every SSA name will have a
2834 list of locations where ASSERT_EXPRs should be added. When a new
2835 location for name N is found, it is registered by calling
2836 register_new_assert_for. That function keeps track of all the
2837 registered assertions to prevent adding unnecessary assertions.
2838 For instance, if a pointer P_4 is dereferenced more than once in a
2839 dominator tree, only the location dominating all the dereference of
2840 P_4 will receive an ASSERT_EXPR.
2842 If this function returns true, then it means that there are names
2843 for which we need to generate ASSERT_EXPRs. Those assertions are
2844 inserted by process_assert_insertions.
2846 TODO. Handle SWITCH_EXPR. */
2849 find_assert_locations (basic_block bb)
2851 block_stmt_iterator si;
2856 if (TEST_BIT (blocks_visited, bb->index))
2859 SET_BIT (blocks_visited, bb->index);
2861 need_assert = false;
2863 /* Traverse all PHI nodes in BB marking used operands. */
2864 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2866 use_operand_p arg_p;
2869 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
2871 tree arg = USE_FROM_PTR (arg_p);
2872 if (TREE_CODE (arg) == SSA_NAME)
2874 gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
2875 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
2880 /* Traverse all the statements in BB marking used names and looking
2881 for statements that may infer assertions for their used operands. */
2883 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2888 stmt = bsi_stmt (si);
2890 /* See if we can derive an assertion for any of STMT's operands. */
2891 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
2894 enum tree_code comp_code;
2896 /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside
2897 the sub-graph of a conditional block, when we return from
2898 this recursive walk, our parent will use the
2899 FOUND_IN_SUBGRAPH bitset to determine if one of the
2900 operands it was looking for was present in the sub-graph. */
2901 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2903 /* If OP is used only once, namely in this STMT, don't
2904 bother creating an ASSERT_EXPR for it. Such an
2905 ASSERT_EXPR would do nothing but increase compile time.
2906 Experiments show that with this simple check, we can save
2907 more than 20% of ASSERT_EXPRs. */
2908 if (has_single_use (op))
2911 /* If OP is used in such a way that we can infer a value
2912 range for it, and we don't find a previous assertion for
2913 it, create a new assertion location node for OP. */
2914 if (infer_value_range (stmt, op, &comp_code, &value))
2916 register_new_assert_for (op, comp_code, value, bb, NULL, si);
2921 /* Remember the last statement of the block. */
2925 /* If BB's last statement is a conditional expression
2926 involving integer operands, recurse into each of the sub-graphs
2927 rooted at BB to determine if we need to add ASSERT_EXPRs. */
2929 && TREE_CODE (last) == COND_EXPR
2930 && !fp_predicate (COND_EXPR_COND (last))
2931 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
2932 need_assert |= find_conditional_asserts (bb);
2934 /* Recurse into the dominator children of BB. */
2935 for (son = first_dom_son (CDI_DOMINATORS, bb);
2937 son = next_dom_son (CDI_DOMINATORS, son))
2938 need_assert |= find_assert_locations (son);
2944 /* Create an ASSERT_EXPR for NAME and insert it in the location
2945 indicated by LOC. Return true if we made any edge insertions. */
2948 process_assert_insertions_for (tree name, assert_locus_t loc)
2950 /* Build the comparison expression NAME_i COMP_CODE VAL. */
2951 tree stmt, cond, assert_expr;
2955 cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
2956 assert_expr = build_assert_expr_for (cond, name);
2960 /* We have been asked to insert the assertion on an edge. This
2961 is used only by COND_EXPR and SWITCH_EXPR assertions. */
2962 #if defined ENABLE_CHECKING
2963 gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
2964 || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
2967 bsi_insert_on_edge (loc->e, assert_expr);
2971 /* Otherwise, we can insert right after LOC->SI iff the
2972 statement must not be the last statement in the block. */
2973 stmt = bsi_stmt (loc->si);
2974 if (!stmt_ends_bb_p (stmt))
2976 bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
2980 /* If STMT must be the last statement in BB, we can only insert new
2981 assertions on the non-abnormal edge out of BB. Note that since
2982 STMT is not control flow, there may only be one non-abnormal edge
2984 FOR_EACH_EDGE (e, ei, loc->bb->succs)
2985 if (!(e->flags & EDGE_ABNORMAL))
2987 bsi_insert_on_edge (e, assert_expr);
2995 /* Process all the insertions registered for every name N_i registered
2996 in NEED_ASSERT_FOR. The list of assertions to be inserted are
2997 found in ASSERTS_FOR[i]. */
3000 process_assert_insertions (void)
3004 bool update_edges_p = false;
3005 int num_asserts = 0;
3007 if (dump_file && (dump_flags & TDF_DETAILS))
3008 dump_all_asserts (dump_file);
3010 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
3012 assert_locus_t loc = asserts_for[i];
3017 assert_locus_t next = loc->next;
3018 update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
3026 bsi_commit_edge_inserts ();
3028 if (dump_file && (dump_flags & TDF_STATS))
3029 fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
3034 /* Traverse the flowgraph looking for conditional jumps to insert range
3035 expressions. These range expressions are meant to provide information
3036 to optimizations that need to reason in terms of value ranges. They
3037 will not be expanded into RTL. For instance, given:
3046 this pass will transform the code into:
3052 x = ASSERT_EXPR <x, x < y>
3057 y = ASSERT_EXPR <y, x <= y>
3061 The idea is that once copy and constant propagation have run, other
3062 optimizations will be able to determine what ranges of values can 'x'
3063 take in different paths of the code, simply by checking the reaching
3064 definition of 'x'. */
3067 insert_range_assertions (void)
3073 found_in_subgraph = sbitmap_alloc (num_ssa_names);
3074 sbitmap_zero (found_in_subgraph);
3076 blocks_visited = sbitmap_alloc (last_basic_block);
3077 sbitmap_zero (blocks_visited);
3079 need_assert_for = BITMAP_ALLOC (NULL);
3080 asserts_for = XNEWVEC (assert_locus_t, num_ssa_names);
3081 memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t));
3083 calculate_dominance_info (CDI_DOMINATORS);
3085 update_ssa_p = false;
3086 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
3087 if (find_assert_locations (e->dest))
3088 update_ssa_p = true;
3092 process_assert_insertions ();
3093 update_ssa (TODO_update_ssa_no_phi);
3096 if (dump_file && (dump_flags & TDF_DETAILS))
3098 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
3099 dump_function_to_file (current_function_decl, dump_file, dump_flags);
3102 sbitmap_free (found_in_subgraph);
3104 BITMAP_FREE (need_assert_for);
3108 /* Convert range assertion expressions into the implied copies and
3109 copy propagate away the copies. Doing the trivial copy propagation
3110 here avoids the need to run the full copy propagation pass after
3113 FIXME, this will eventually lead to copy propagation removing the
3114 names that had useful range information attached to them. For
3115 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
3116 then N_i will have the range [3, +INF].
3118 However, by converting the assertion into the implied copy
3119 operation N_i = N_j, we will then copy-propagate N_j into the uses
3120 of N_i and lose the range information. We may want to hold on to
3121 ASSERT_EXPRs a little while longer as the ranges could be used in
3122 things like jump threading.
3124 The problem with keeping ASSERT_EXPRs around is that passes after
3125 VRP need to handle them appropriately.
3127 Another approach would be to make the range information a first
3128 class property of the SSA_NAME so that it can be queried from
3129 any pass. This is made somewhat more complex by the need for
3130 multiple ranges to be associated with one SSA_NAME. */
3133 remove_range_assertions (void)
3136 block_stmt_iterator si;
3138 /* Note that the BSI iterator bump happens at the bottom of the
3139 loop and no bump is necessary if we're removing the statement
3140 referenced by the current BSI. */
3142 for (si = bsi_start (bb); !bsi_end_p (si);)
3144 tree stmt = bsi_stmt (si);
3146 if (TREE_CODE (stmt) == MODIFY_EXPR
3147 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
3149 tree rhs = TREE_OPERAND (stmt, 1);
3150 tree cond = fold (ASSERT_EXPR_COND (rhs));
3151 use_operand_p use_p;
3152 imm_use_iterator iter;
3154 gcc_assert (cond != boolean_false_node);
3155 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
3158 /* The statement is now a copy. Propagate the RHS into
3159 every use of the LHS. */
3160 FOR_EACH_IMM_USE_SAFE (use_p, iter, TREE_OPERAND (stmt, 0))
3162 SET_USE (use_p, ASSERT_EXPR_VAR (rhs));
3163 update_stmt (USE_STMT (use_p));
3166 /* And finally, remove the copy, it is not needed. */
3167 bsi_remove (&si, true);
3173 sbitmap_free (blocks_visited);
3177 /* Return true if STMT is interesting for VRP. */
3180 stmt_interesting_for_vrp (tree stmt)
3182 if (TREE_CODE (stmt) == PHI_NODE
3183 && is_gimple_reg (PHI_RESULT (stmt))
3184 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
3185 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
3187 else if (TREE_CODE (stmt) == MODIFY_EXPR)
3189 tree lhs = TREE_OPERAND (stmt, 0);
3191 if (TREE_CODE (lhs) == SSA_NAME
3192 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
3193 || POINTER_TYPE_P (TREE_TYPE (lhs)))
3194 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3197 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3204 /* Initialize local data structures for VRP. */
3207 vrp_initialize (void)
3211 vr_value = XNEWVEC (value_range_t *, num_ssa_names);
3212 memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *));
3216 block_stmt_iterator si;
3219 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3221 if (!stmt_interesting_for_vrp (phi))
3223 tree lhs = PHI_RESULT (phi);
3224 set_value_range_to_varying (get_value_range (lhs));
3225 DONT_SIMULATE_AGAIN (phi) = true;
3228 DONT_SIMULATE_AGAIN (phi) = false;
3231 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
3233 tree stmt = bsi_stmt (si);
3235 if (!stmt_interesting_for_vrp (stmt))
3239 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
3240 set_value_range_to_varying (get_value_range (def));
3241 DONT_SIMULATE_AGAIN (stmt) = true;
3245 DONT_SIMULATE_AGAIN (stmt) = false;
3252 /* Visit assignment STMT. If it produces an interesting range, record
3253 the SSA name in *OUTPUT_P. */
3255 static enum ssa_prop_result
3256 vrp_visit_assignment (tree stmt, tree *output_p)
3261 lhs = TREE_OPERAND (stmt, 0);
3262 rhs = TREE_OPERAND (stmt, 1);
3264 /* We only keep track of ranges in integral and pointer types. */
3265 if (TREE_CODE (lhs) == SSA_NAME
3266 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
3267 || POINTER_TYPE_P (TREE_TYPE (lhs))))
3270 value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3272 extract_range_from_expr (&new_vr, rhs);
3274 /* If STMT is inside a loop, we may be able to know something
3275 else about the range of LHS by examining scalar evolution
3277 if (current_loops && (l = loop_containing_stmt (stmt)))
3278 adjust_range_with_scev (&new_vr, l, stmt, lhs);
3280 if (update_value_range (lhs, &new_vr))
3284 if (dump_file && (dump_flags & TDF_DETAILS))
3286 fprintf (dump_file, "Found new range for ");
3287 print_generic_expr (dump_file, lhs, 0);
3288 fprintf (dump_file, ": ");
3289 dump_value_range (dump_file, &new_vr);
3290 fprintf (dump_file, "\n\n");
3293 if (new_vr.type == VR_VARYING)
3294 return SSA_PROP_VARYING;
3296 return SSA_PROP_INTERESTING;
3299 return SSA_PROP_NOT_INTERESTING;
3302 /* Every other statement produces no useful ranges. */
3303 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3304 set_value_range_to_varying (get_value_range (def));
3306 return SSA_PROP_VARYING;
3310 /* Compare all the value ranges for names equivalent to VAR with VAL
3311 using comparison code COMP. Return the same value returned by
3312 compare_range_with_value. */
3315 compare_name_with_value (enum tree_code comp, tree var, tree val)
3322 t = retval = NULL_TREE;
3324 /* Get the set of equivalences for VAR. */
3325 e = get_value_range (var)->equiv;
3327 /* Add VAR to its own set of equivalences so that VAR's value range
3328 is processed by this loop (otherwise, we would have to replicate
3329 the body of the loop just to check VAR's value range). */
3330 bitmap_set_bit (e, SSA_NAME_VERSION (var));
3332 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
3334 value_range_t equiv_vr = *(vr_value[i]);
3336 /* If name N_i does not have a valid range, use N_i as its own
3337 range. This allows us to compare against names that may
3338 have N_i in their ranges. */
3339 if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
3341 equiv_vr.type = VR_RANGE;
3342 equiv_vr.min = ssa_name (i);
3343 equiv_vr.max = ssa_name (i);
3346 t = compare_range_with_value (comp, &equiv_vr, val);
3349 /* All the ranges should compare the same against VAL. */
3350 gcc_assert (retval == NULL || t == retval);
3355 /* Remove VAR from its own equivalence set. */
3356 bitmap_clear_bit (e, SSA_NAME_VERSION (var));
3361 /* We couldn't find a non-NULL value for the predicate. */
3366 /* Given a comparison code COMP and names N1 and N2, compare all the
3367 ranges equivalent to N1 against all the ranges equivalent to N2
3368 to determine the value of N1 COMP N2. Return the same value
3369 returned by compare_ranges. */
3372 compare_names (enum tree_code comp, tree n1, tree n2)
3376 bitmap_iterator bi1, bi2;
3379 /* Compare the ranges of every name equivalent to N1 against the
3380 ranges of every name equivalent to N2. */
3381 e1 = get_value_range (n1)->equiv;
3382 e2 = get_value_range (n2)->equiv;
3384 /* Add N1 and N2 to their own set of equivalences to avoid
3385 duplicating the body of the loop just to check N1 and N2
3387 bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
3388 bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
3390 /* If the equivalence sets have a common intersection, then the two
3391 names can be compared without checking their ranges. */
3392 if (bitmap_intersect_p (e1, e2))
3394 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3395 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3397 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
3399 : boolean_false_node;
3402 /* Otherwise, compare all the equivalent ranges. First, add N1 and
3403 N2 to their own set of equivalences to avoid duplicating the body
3404 of the loop just to check N1 and N2 ranges. */
3405 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
3407 value_range_t vr1 = *(vr_value[i1]);
3409 /* If the range is VARYING or UNDEFINED, use the name itself. */
3410 if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
3412 vr1.type = VR_RANGE;
3413 vr1.min = ssa_name (i1);
3414 vr1.max = ssa_name (i1);
3417 t = retval = NULL_TREE;
3418 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
3420 value_range_t vr2 = *(vr_value[i2]);
3422 if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
3424 vr2.type = VR_RANGE;
3425 vr2.min = ssa_name (i2);
3426 vr2.max = ssa_name (i2);
3429 t = compare_ranges (comp, &vr1, &vr2);
3432 /* All the ranges in the equivalent sets should compare
3434 gcc_assert (retval == NULL || t == retval);
3441 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3442 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3447 /* None of the equivalent ranges are useful in computing this
3449 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3450 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3455 /* Given a conditional predicate COND, try to determine if COND yields
3456 true or false based on the value ranges of its operands. Return
3457 BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
3458 BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
3459 NULL if the conditional cannot be evaluated at compile time.
3461 If USE_EQUIV_P is true, the ranges of all the names equivalent with
3462 the operands in COND are used when trying to compute its value.
3463 This is only used during final substitution. During propagation,
3464 we only check the range of each variable and not its equivalents. */
3467 vrp_evaluate_conditional (tree cond, bool use_equiv_p)
3469 gcc_assert (TREE_CODE (cond) == SSA_NAME
3470 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
3472 if (TREE_CODE (cond) == SSA_NAME)
3478 retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node);
3481 value_range_t *vr = get_value_range (cond);
3482 retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node);
3485 /* If COND has a known boolean range, return it. */
3489 /* Otherwise, if COND has a symbolic range of exactly one value,
3491 vr = get_value_range (cond);
3492 if (vr->type == VR_RANGE && vr->min == vr->max)
3497 tree op0 = TREE_OPERAND (cond, 0);
3498 tree op1 = TREE_OPERAND (cond, 1);
3500 /* We only deal with integral and pointer types. */
3501 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3502 && !POINTER_TYPE_P (TREE_TYPE (op0)))
3507 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
3508 return compare_names (TREE_CODE (cond), op0, op1);
3509 else if (TREE_CODE (op0) == SSA_NAME)
3510 return compare_name_with_value (TREE_CODE (cond), op0, op1);
3511 else if (TREE_CODE (op1) == SSA_NAME)
3512 return compare_name_with_value (
3513 swap_tree_comparison (TREE_CODE (cond)), op1, op0);
3517 value_range_t *vr0, *vr1;
3519 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
3520 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
3523 return compare_ranges (TREE_CODE (cond), vr0, vr1);
3524 else if (vr0 && vr1 == NULL)
3525 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
3526 else if (vr0 == NULL && vr1)
3527 return compare_range_with_value (
3528 swap_tree_comparison (TREE_CODE (cond)), vr1, op0);
3532 /* Anything else cannot be computed statically. */
3537 /* Visit conditional statement STMT. If we can determine which edge
3538 will be taken out of STMT's basic block, record it in
3539 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
3540 SSA_PROP_VARYING. */
3542 static enum ssa_prop_result
3543 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
3547 *taken_edge_p = NULL;
3549 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
3550 add ASSERT_EXPRs for them. */
3551 if (TREE_CODE (stmt) == SWITCH_EXPR)
3552 return SSA_PROP_VARYING;
3554 cond = COND_EXPR_COND (stmt);
3556 if (dump_file && (dump_flags & TDF_DETAILS))
3561 fprintf (dump_file, "\nVisiting conditional with predicate: ");
3562 print_generic_expr (dump_file, cond, 0);
3563 fprintf (dump_file, "\nWith known ranges\n");
3565 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
3567 fprintf (dump_file, "\t");
3568 print_generic_expr (dump_file, use, 0);
3569 fprintf (dump_file, ": ");
3570 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
3573 fprintf (dump_file, "\n");
3576 /* Compute the value of the predicate COND by checking the known
3577 ranges of each of its operands.
3579 Note that we cannot evaluate all the equivalent ranges here
3580 because those ranges may not yet be final and with the current
3581 propagation strategy, we cannot determine when the value ranges
3582 of the names in the equivalence set have changed.
3584 For instance, given the following code fragment
3588 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
3592 Assume that on the first visit to i_14, i_5 has the temporary
3593 range [8, 8] because the second argument to the PHI function is
3594 not yet executable. We derive the range ~[0, 0] for i_14 and the
3595 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
3596 the first time, since i_14 is equivalent to the range [8, 8], we
3597 determine that the predicate is always false.
3599 On the next round of propagation, i_13 is determined to be
3600 VARYING, which causes i_5 to drop down to VARYING. So, another
3601 visit to i_14 is scheduled. In this second visit, we compute the
3602 exact same range and equivalence set for i_14, namely ~[0, 0] and
3603 { i_5 }. But we did not have the previous range for i_5
3604 registered, so vrp_visit_assignment thinks that the range for
3605 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
3606 is not visited again, which stops propagation from visiting
3607 statements in the THEN clause of that if().
3609 To properly fix this we would need to keep the previous range
3610 value for the names in the equivalence set. This way we would've
3611 discovered that from one visit to the other i_5 changed from
3612 range [8, 8] to VR_VARYING.
3614 However, fixing this apparent limitation may not be worth the
3615 additional checking. Testing on several code bases (GCC, DLV,
3616 MICO, TRAMP3D and SPEC2000) showed that doing this results in
3617 4 more predicates folded in SPEC. */
3618 val = vrp_evaluate_conditional (cond, false);
3620 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
3622 if (dump_file && (dump_flags & TDF_DETAILS))
3624 fprintf (dump_file, "\nPredicate evaluates to: ");
3625 if (val == NULL_TREE)
3626 fprintf (dump_file, "DON'T KNOW\n");
3628 print_generic_stmt (dump_file, val, 0);
3631 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
3635 /* Evaluate statement STMT. If the statement produces a useful range,
3636 return SSA_PROP_INTERESTING and record the SSA name with the
3637 interesting range into *OUTPUT_P.
3639 If STMT is a conditional branch and we can determine its truth
3640 value, the taken edge is recorded in *TAKEN_EDGE_P.
3642 If STMT produces a varying value, return SSA_PROP_VARYING. */
3644 static enum ssa_prop_result
3645 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
3651 if (dump_file && (dump_flags & TDF_DETAILS))
3653 fprintf (dump_file, "\nVisiting statement:\n");
3654 print_generic_stmt (dump_file, stmt, dump_flags);
3655 fprintf (dump_file, "\n");
3658 ann = stmt_ann (stmt);
3659 if (TREE_CODE (stmt) == MODIFY_EXPR
3660 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3661 return vrp_visit_assignment (stmt, output_p);
3662 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3663 return vrp_visit_cond_stmt (stmt, taken_edge_p);
3665 /* All other statements produce nothing of interest for VRP, so mark
3666 their outputs varying and prevent further simulation. */
3667 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3668 set_value_range_to_varying (get_value_range (def));
3670 return SSA_PROP_VARYING;
3674 /* Meet operation for value ranges. Given two value ranges VR0 and
3675 VR1, store in VR0 the result of meeting VR0 and VR1.
3677 The meeting rules are as follows:
3679 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
3681 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
3682 union of VR0 and VR1. */
3685 vrp_meet (value_range_t *vr0, value_range_t *vr1)
3687 if (vr0->type == VR_UNDEFINED)
3689 copy_value_range (vr0, vr1);
3693 if (vr1->type == VR_UNDEFINED)
3695 /* Nothing to do. VR0 already has the resulting range. */
3699 if (vr0->type == VR_VARYING)
3701 /* Nothing to do. VR0 already has the resulting range. */
3705 if (vr1->type == VR_VARYING)
3707 set_value_range_to_varying (vr0);
3711 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
3713 /* If VR0 and VR1 have a non-empty intersection, compute the
3714 union of both ranges. */
3715 if (value_ranges_intersect_p (vr0, vr1))
3720 /* The lower limit of the new range is the minimum of the
3721 two ranges. If they cannot be compared, the result is
3723 cmp = compare_values (vr0->min, vr1->min);
3724 if (cmp == 0 || cmp == 1)
3730 set_value_range_to_varying (vr0);
3734 /* Similarly, the upper limit of the new range is the
3735 maximum of the two ranges. If they cannot be compared,
3736 the result is VARYING. */
3737 cmp = compare_values (vr0->max, vr1->max);
3738 if (cmp == 0 || cmp == -1)
3744 set_value_range_to_varying (vr0);
3748 /* The resulting set of equivalences is the intersection of
3750 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3751 bitmap_and_into (vr0->equiv, vr1->equiv);
3752 else if (vr0->equiv && !vr1->equiv)
3753 bitmap_clear (vr0->equiv);
3755 set_value_range (vr0, vr0->type, min, max, vr0->equiv);
3760 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3762 /* Two anti-ranges meet only if they are both identical. */
3763 if (compare_values (vr0->min, vr1->min) == 0
3764 && compare_values (vr0->max, vr1->max) == 0
3765 && compare_values (vr0->min, vr0->max) == 0)
3767 /* The resulting set of equivalences is the intersection of
3769 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3770 bitmap_and_into (vr0->equiv, vr1->equiv);
3771 else if (vr0->equiv && !vr1->equiv)
3772 bitmap_clear (vr0->equiv);
3777 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
3779 /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4]
3780 meet only if the ranges have an empty intersection. The
3781 result of the meet operation is the anti-range. */
3782 if (!symbolic_range_p (vr0)
3783 && !symbolic_range_p (vr1)
3784 && !value_ranges_intersect_p (vr0, vr1))
3786 /* Copy most of VR1 into VR0. Don't copy VR1's equivalence
3787 set. We need to compute the intersection of the two
3788 equivalence sets. */
3789 if (vr1->type == VR_ANTI_RANGE)
3790 set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
3792 /* The resulting set of equivalences is the intersection of
3794 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3795 bitmap_and_into (vr0->equiv, vr1->equiv);
3796 else if (vr0->equiv && !vr1->equiv)
3797 bitmap_clear (vr0->equiv);
3808 /* The two range VR0 and VR1 do not meet. Before giving up and
3809 setting the result to VARYING, see if we can at least derive a
3810 useful anti-range. FIXME, all this nonsense about distinguishing
3811 anti-ranges from ranges is necessary because of the odd
3812 semantics of range_includes_zero_p and friends. */
3813 if (!symbolic_range_p (vr0)
3814 && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0))
3815 || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0)))
3816 && !symbolic_range_p (vr1)
3817 && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1))
3818 || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1))))
3820 set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
3822 /* Since this meet operation did not result from the meeting of
3823 two equivalent names, VR0 cannot have any equivalences. */
3825 bitmap_clear (vr0->equiv);
3828 set_value_range_to_varying (vr0);
3832 /* Visit all arguments for PHI node PHI that flow through executable
3833 edges. If a valid value range can be derived from all the incoming
3834 value ranges, set a new range for the LHS of PHI. */
3836 static enum ssa_prop_result
3837 vrp_visit_phi_node (tree phi)
3840 tree lhs = PHI_RESULT (phi);
3841 value_range_t *lhs_vr = get_value_range (lhs);
3842 value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3844 copy_value_range (&vr_result, lhs_vr);
3846 if (dump_file && (dump_flags & TDF_DETAILS))
3848 fprintf (dump_file, "\nVisiting PHI node: ");
3849 print_generic_expr (dump_file, phi, dump_flags);
3852 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
3854 edge e = PHI_ARG_EDGE (phi, i);
3856 if (dump_file && (dump_flags & TDF_DETAILS))
3859 "\n Argument #%d (%d -> %d %sexecutable)\n",
3860 i, e->src->index, e->dest->index,
3861 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
3864 if (e->flags & EDGE_EXECUTABLE)
3866 tree arg = PHI_ARG_DEF (phi, i);
3867 value_range_t vr_arg;
3869 if (TREE_CODE (arg) == SSA_NAME)
3870 vr_arg = *(get_value_range (arg));
3873 vr_arg.type = VR_RANGE;
3876 vr_arg.equiv = NULL;
3879 if (dump_file && (dump_flags & TDF_DETAILS))
3881 fprintf (dump_file, "\t");
3882 print_generic_expr (dump_file, arg, dump_flags);
3883 fprintf (dump_file, "\n\tValue: ");
3884 dump_value_range (dump_file, &vr_arg);
3885 fprintf (dump_file, "\n");
3888 vrp_meet (&vr_result, &vr_arg);
3890 if (vr_result.type == VR_VARYING)
3895 if (vr_result.type == VR_VARYING)
3898 /* To prevent infinite iterations in the algorithm, derive ranges
3899 when the new value is slightly bigger or smaller than the
3901 if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE)
3903 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
3905 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
3906 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
3908 /* If the new minimum is smaller or larger than the previous
3909 one, go all the way to -INF. In the first case, to avoid
3910 iterating millions of times to reach -INF, and in the
3911 other case to avoid infinite bouncing between different
3913 if (cmp_min > 0 || cmp_min < 0)
3914 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
3916 /* Similarly, if the new maximum is smaller or larger than
3917 the previous one, go all the way to +INF. */
3918 if (cmp_max < 0 || cmp_max > 0)
3919 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
3921 /* If we ended up with a (-INF, +INF) range, set it to
3923 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
3924 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
3929 /* If the new range is different than the previous value, keep
3931 if (update_value_range (lhs, &vr_result))
3932 return SSA_PROP_INTERESTING;
3934 /* Nothing changed, don't add outgoing edges. */
3935 return SSA_PROP_NOT_INTERESTING;
3937 /* No match found. Set the LHS to VARYING. */
3939 set_value_range_to_varying (lhs_vr);
3940 return SSA_PROP_VARYING;
3943 /* Simplify a division or modulo operator to a right shift or
3944 bitwise and if the first operand is unsigned or is greater
3945 than zero and the second operand is an exact power of two. */
3948 simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code)
3951 tree op = TREE_OPERAND (rhs, 0);
3952 value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
3954 if (TYPE_UNSIGNED (TREE_TYPE (op)))
3956 val = integer_one_node;
3960 val = compare_range_with_value (GT_EXPR, vr, integer_zero_node);
3963 if (val && integer_onep (val))
3966 tree op0 = TREE_OPERAND (rhs, 0);
3967 tree op1 = TREE_OPERAND (rhs, 1);
3969 if (rhs_code == TRUNC_DIV_EXPR)
3971 t = build_int_cst (NULL_TREE, tree_log2 (op1));
3972 t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
3976 t = build_int_cst (TREE_TYPE (op1), 1);
3977 t = int_const_binop (MINUS_EXPR, op1, t, 0);
3978 t = fold_convert (TREE_TYPE (op0), t);
3979 t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
3982 TREE_OPERAND (stmt, 1) = t;
3987 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
3988 ABS_EXPR. If the operand is <= 0, then simplify the
3989 ABS_EXPR into a NEGATE_EXPR. */
3992 simplify_abs_using_ranges (tree stmt, tree rhs)
3995 tree op = TREE_OPERAND (rhs, 0);
3996 tree type = TREE_TYPE (op);
3997 value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
3999 if (TYPE_UNSIGNED (type))
4001 val = integer_zero_node;
4005 val = compare_range_with_value (LE_EXPR, vr, integer_zero_node);
4008 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node);
4012 if (integer_zerop (val))
4013 val = integer_one_node;
4014 else if (integer_onep (val))
4015 val = integer_zero_node;
4020 && (integer_onep (val) || integer_zerop (val)))
4024 if (integer_onep (val))
4025 t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
4029 TREE_OPERAND (stmt, 1) = t;
4035 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
4036 a known value range VR.
4038 If there is one and only one value which will satisfy the
4039 conditional, then return that value. Else return NULL. */
4042 test_for_singularity (enum tree_code cond_code, tree op0,
4043 tree op1, value_range_t *vr)
4048 /* Extract minimum/maximum values which satisfy the
4049 the conditional as it was written. */
4050 if (cond_code == LE_EXPR || cond_code == LT_EXPR)
4052 min = TYPE_MIN_VALUE (TREE_TYPE (op0));
4055 if (cond_code == LT_EXPR)
4057 tree one = build_int_cst (TREE_TYPE (op0), 1);
4058 max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
4061 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
4063 max = TYPE_MAX_VALUE (TREE_TYPE (op0));
4066 if (cond_code == GT_EXPR)
4068 tree one = build_int_cst (TREE_TYPE (op0), 1);
4069 min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
4073 /* Now refine the minimum and maximum values using any
4074 value range information we have for op0. */
4077 if (compare_values (vr->min, min) == -1)
4081 if (compare_values (vr->max, max) == 1)
4086 /* If the new min/max values have converged to a single value,
4087 then there is only one value which can satisfy the condition,
4088 return that value. */
4089 if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
4095 /* Simplify a conditional using a relational operator to an equality
4096 test if the range information indicates only one value can satisfy
4097 the original conditional. */
4100 simplify_cond_using_ranges (tree stmt)
4102 tree cond = COND_EXPR_COND (stmt);
4103 tree op0 = TREE_OPERAND (cond, 0);
4104 tree op1 = TREE_OPERAND (cond, 1);
4105 enum tree_code cond_code = TREE_CODE (cond);
4107 if (cond_code != NE_EXPR
4108 && cond_code != EQ_EXPR
4109 && TREE_CODE (op0) == SSA_NAME
4110 && INTEGRAL_TYPE_P (TREE_TYPE (op0))
4111 && is_gimple_min_invariant (op1))
4113 value_range_t *vr = get_value_range (op0);
4115 /* If we have range information for OP0, then we might be
4116 able to simplify this conditional. */
4117 if (vr->type == VR_RANGE)
4119 tree new = test_for_singularity (cond_code, op0, op1, vr);
4125 fprintf (dump_file, "Simplified relational ");
4126 print_generic_expr (dump_file, cond, 0);
4127 fprintf (dump_file, " into ");
4130 COND_EXPR_COND (stmt)
4131 = build2 (EQ_EXPR, boolean_type_node, op0, new);
4136 print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
4137 fprintf (dump_file, "\n");
4143 /* Try again after inverting the condition. We only deal
4144 with integral types here, so no need to worry about
4145 issues with inverting FP comparisons. */
4146 cond_code = invert_tree_comparison (cond_code, false);
4147 new = test_for_singularity (cond_code, op0, op1, vr);
4153 fprintf (dump_file, "Simplified relational ");
4154 print_generic_expr (dump_file, cond, 0);
4155 fprintf (dump_file, " into ");
4158 COND_EXPR_COND (stmt)
4159 = build2 (NE_EXPR, boolean_type_node, op0, new);
4164 print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
4165 fprintf (dump_file, "\n");
4174 /* Simplify STMT using ranges if possible. */
4177 simplify_stmt_using_ranges (tree stmt)
4179 if (TREE_CODE (stmt) == MODIFY_EXPR)
4181 tree rhs = TREE_OPERAND (stmt, 1);
4182 enum tree_code rhs_code = TREE_CODE (rhs);
4184 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4185 and BIT_AND_EXPR respectively if the first operand is greater
4186 than zero and the second operand is an exact power of two. */
4187 if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
4188 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
4189 && integer_pow2p (TREE_OPERAND (rhs, 1)))
4190 simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code);
4192 /* Transform ABS (X) into X or -X as appropriate. */
4193 if (rhs_code == ABS_EXPR
4194 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
4195 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
4196 simplify_abs_using_ranges (stmt, rhs);
4198 else if (TREE_CODE (stmt) == COND_EXPR
4199 && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
4201 simplify_cond_using_ranges (stmt);
4207 /* Traverse all the blocks folding conditionals with known ranges. */
4213 prop_value_t *single_val_range;
4214 bool do_value_subst_p;
4218 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
4219 dump_all_value_ranges (dump_file);
4220 fprintf (dump_file, "\n");
4223 /* We may have ended with ranges that have exactly one value. Those
4224 values can be substituted as any other copy/const propagated
4225 value using substitute_and_fold. */
4226 single_val_range = XNEWVEC (prop_value_t, num_ssa_names);
4227 memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range));
4229 do_value_subst_p = false;
4230 for (i = 0; i < num_ssa_names; i++)
4232 && vr_value[i]->type == VR_RANGE
4233 && vr_value[i]->min == vr_value[i]->max)
4235 single_val_range[i].value = vr_value[i]->min;
4236 do_value_subst_p = true;
4239 if (!do_value_subst_p)
4241 /* We found no single-valued ranges, don't waste time trying to
4242 do single value substitution in substitute_and_fold. */
4243 free (single_val_range);
4244 single_val_range = NULL;
4247 substitute_and_fold (single_val_range, true);
4249 /* Free allocated memory. */
4250 for (i = 0; i < num_ssa_names; i++)
4253 BITMAP_FREE (vr_value[i]->equiv);
4257 free (single_val_range);
4262 /* Main entry point to VRP (Value Range Propagation). This pass is
4263 loosely based on J. R. C. Patterson, ``Accurate Static Branch
4264 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
4265 Programming Language Design and Implementation, pp. 67-78, 1995.
4266 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
4268 This is essentially an SSA-CCP pass modified to deal with ranges
4269 instead of constants.
4271 While propagating ranges, we may find that two or more SSA name
4272 have equivalent, though distinct ranges. For instance,
4275 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0>
4277 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
4281 In the code above, pointer p_5 has range [q_2, q_2], but from the
4282 code we can also determine that p_5 cannot be NULL and, if q_2 had
4283 a non-varying range, p_5's range should also be compatible with it.
4285 These equivalences are created by two expressions: ASSERT_EXPR and
4286 copy operations. Since p_5 is an assertion on p_4, and p_4 was the
4287 result of another assertion, then we can use the fact that p_5 and
4288 p_4 are equivalent when evaluating p_5's range.
4290 Together with value ranges, we also propagate these equivalences
4291 between names so that we can take advantage of information from
4292 multiple ranges when doing final replacement. Note that this
4293 equivalency relation is transitive but not symmetric.
4295 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
4296 cannot assert that q_2 is equivalent to p_5 because q_2 may be used
4297 in contexts where that assertion does not hold (e.g., in line 6).
4299 TODO, the main difference between this pass and Patterson's is that
4300 we do not propagate edge probabilities. We only compute whether
4301 edges can be taken or not. That is, instead of having a spectrum
4302 of jump probabilities between 0 and 1, we only deal with 0, 1 and
4303 DON'T KNOW. In the future, it may be worthwhile to propagate
4304 probabilities to aid branch prediction. */
4309 insert_range_assertions ();
4311 current_loops = loop_optimizer_init (LOOPS_NORMAL);
4313 scev_initialize (current_loops);
4316 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
4322 loop_optimizer_finalize (current_loops);
4323 current_loops = NULL;
4326 remove_range_assertions ();
4332 return flag_tree_vrp != 0;
4335 struct tree_opt_pass pass_vrp =
4338 gate_vrp, /* gate */
4339 execute_vrp, /* execute */
4342 0, /* static_pass_number */
4343 TV_TREE_VRP, /* tv_id */
4344 PROP_ssa | PROP_alias, /* properties_required */
4345 0, /* properties_provided */
4346 0, /* properties_destroyed */
4347 0, /* todo_flags_start */
4352 | TODO_update_ssa, /* todo_flags_finish */