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);
194 /* Set value range VR to a non-negative range of type TYPE. */
197 set_value_range_to_nonnegative (value_range_t *vr, tree type)
199 tree zero = build_int_cst (type, 0);
200 set_value_range (vr, VR_RANGE, zero, TYPE_MAX_VALUE (type), vr->equiv);
203 /* Set value range VR to a non-NULL range of type TYPE. */
206 set_value_range_to_nonnull (value_range_t *vr, tree type)
208 tree zero = build_int_cst (type, 0);
209 set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
213 /* Set value range VR to a NULL range of type TYPE. */
216 set_value_range_to_null (value_range_t *vr, tree type)
218 tree zero = build_int_cst (type, 0);
219 set_value_range (vr, VR_RANGE, zero, zero, vr->equiv);
223 /* Set value range VR to VR_VARYING. */
226 set_value_range_to_varying (value_range_t *vr)
228 vr->type = VR_VARYING;
229 vr->min = vr->max = NULL_TREE;
231 bitmap_clear (vr->equiv);
235 /* Set value range VR to VR_UNDEFINED. */
238 set_value_range_to_undefined (value_range_t *vr)
240 vr->type = VR_UNDEFINED;
241 vr->min = vr->max = NULL_TREE;
243 bitmap_clear (vr->equiv);
247 /* Return value range information for VAR.
249 If we have no values ranges recorded (ie, VRP is not running), then
250 return NULL. Otherwise create an empty range if none existed for VAR. */
252 static value_range_t *
253 get_value_range (tree var)
257 unsigned ver = SSA_NAME_VERSION (var);
259 /* If we have no recorded ranges, then return NULL. */
267 /* Create a default value range. */
268 vr_value[ver] = vr = XNEW (value_range_t);
269 memset (vr, 0, sizeof (*vr));
271 /* Allocate an equivalence set. */
272 vr->equiv = BITMAP_ALLOC (NULL);
274 /* If VAR is a default definition, the variable can take any value
276 sym = SSA_NAME_VAR (var);
277 if (var == default_def (sym))
279 /* Try to use the "nonnull" attribute to create ~[0, 0]
280 anti-ranges for pointers. Note that this is only valid with
281 default definitions of PARM_DECLs. */
282 if (TREE_CODE (sym) == PARM_DECL
283 && POINTER_TYPE_P (TREE_TYPE (sym))
284 && nonnull_arg_p (sym))
285 set_value_range_to_nonnull (vr, TREE_TYPE (sym));
287 set_value_range_to_varying (vr);
294 /* Update the value range and equivalence set for variable VAR to
295 NEW_VR. Return true if NEW_VR is different from VAR's previous
298 NOTE: This function assumes that NEW_VR is a temporary value range
299 object created for the sole purpose of updating VAR's range. The
300 storage used by the equivalence set from NEW_VR will be freed by
301 this function. Do not call update_value_range when NEW_VR
302 is the range object associated with another SSA name. */
305 update_value_range (tree var, value_range_t *new_vr)
307 value_range_t *old_vr;
310 /* Update the value range, if necessary. */
311 old_vr = get_value_range (var);
312 is_new = old_vr->type != new_vr->type
313 || old_vr->min != new_vr->min
314 || old_vr->max != new_vr->max
315 || (old_vr->equiv == NULL && new_vr->equiv)
316 || (old_vr->equiv && new_vr->equiv == NULL)
317 || (!bitmap_equal_p (old_vr->equiv, new_vr->equiv));
320 set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
323 BITMAP_FREE (new_vr->equiv);
324 new_vr->equiv = NULL;
330 /* Add VAR and VAR's equivalence set to EQUIV. */
333 add_equivalence (bitmap equiv, tree var)
335 unsigned ver = SSA_NAME_VERSION (var);
336 value_range_t *vr = vr_value[ver];
338 bitmap_set_bit (equiv, ver);
340 bitmap_ior_into (equiv, vr->equiv);
344 /* Return true if VR is ~[0, 0]. */
347 range_is_nonnull (value_range_t *vr)
349 return vr->type == VR_ANTI_RANGE
350 && integer_zerop (vr->min)
351 && integer_zerop (vr->max);
355 /* Return true if VR is [0, 0]. */
358 range_is_null (value_range_t *vr)
360 return vr->type == VR_RANGE
361 && integer_zerop (vr->min)
362 && integer_zerop (vr->max);
366 /* Return true if value range VR involves at least one symbol. */
369 symbolic_range_p (value_range_t *vr)
371 return (!is_gimple_min_invariant (vr->min)
372 || !is_gimple_min_invariant (vr->max));
375 /* Like tree_expr_nonnegative_p, but this function uses value ranges
379 vrp_expr_computes_nonnegative (tree expr)
381 return tree_expr_nonnegative_p (expr);
384 /* Like tree_expr_nonzero_p, but this function uses value ranges
388 vrp_expr_computes_nonzero (tree expr)
390 if (tree_expr_nonzero_p (expr))
393 /* If we have an expression of the form &X->a, then the expression
394 is nonnull if X is nonnull. */
395 if (TREE_CODE (expr) == ADDR_EXPR)
397 tree base = get_base_address (TREE_OPERAND (expr, 0));
399 if (base != NULL_TREE
400 && TREE_CODE (base) == INDIRECT_REF
401 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
403 value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
404 if (range_is_nonnull (vr))
413 /* Compare two values VAL1 and VAL2. Return
415 -2 if VAL1 and VAL2 cannot be compared at compile-time,
418 +1 if VAL1 > VAL2, and
421 This is similar to tree_int_cst_compare but supports pointer values
422 and values that cannot be compared at compile time. */
425 compare_values (tree val1, tree val2)
430 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
432 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
433 == POINTER_TYPE_P (TREE_TYPE (val2)));
435 if ((TREE_CODE (val1) == SSA_NAME
436 || TREE_CODE (val1) == PLUS_EXPR
437 || TREE_CODE (val1) == MINUS_EXPR)
438 && (TREE_CODE (val2) == SSA_NAME
439 || TREE_CODE (val2) == PLUS_EXPR
440 || TREE_CODE (val2) == MINUS_EXPR))
443 enum tree_code code1, code2;
445 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
446 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
447 same name, return -2. */
448 if (TREE_CODE (val1) == SSA_NAME)
456 code1 = TREE_CODE (val1);
457 n1 = TREE_OPERAND (val1, 0);
458 c1 = TREE_OPERAND (val1, 1);
459 if (tree_int_cst_sgn (c1) == -1)
461 c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1);
464 code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
468 if (TREE_CODE (val2) == SSA_NAME)
476 code2 = TREE_CODE (val2);
477 n2 = TREE_OPERAND (val2, 0);
478 c2 = TREE_OPERAND (val2, 1);
479 if (tree_int_cst_sgn (c2) == -1)
481 c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2);
484 code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
488 /* Both values must use the same name. */
492 if (code1 == SSA_NAME
493 && code2 == SSA_NAME)
497 /* If overflow is defined we cannot simplify more. */
498 if (TYPE_UNSIGNED (TREE_TYPE (val1))
502 if (code1 == SSA_NAME)
504 if (code2 == PLUS_EXPR)
505 /* NAME < NAME + CST */
507 else if (code2 == MINUS_EXPR)
508 /* NAME > NAME - CST */
511 else if (code1 == PLUS_EXPR)
513 if (code2 == SSA_NAME)
514 /* NAME + CST > NAME */
516 else if (code2 == PLUS_EXPR)
517 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
518 return compare_values (c1, c2);
519 else if (code2 == MINUS_EXPR)
520 /* NAME + CST1 > NAME - CST2 */
523 else if (code1 == MINUS_EXPR)
525 if (code2 == SSA_NAME)
526 /* NAME - CST < NAME */
528 else if (code2 == PLUS_EXPR)
529 /* NAME - CST1 < NAME + CST2 */
531 else if (code2 == MINUS_EXPR)
532 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
533 C1 and C2 are swapped in the call to compare_values. */
534 return compare_values (c2, c1);
540 /* We cannot compare non-constants. */
541 if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
544 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
546 /* We cannot compare overflowed values. */
547 if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
550 return tree_int_cst_compare (val1, val2);
556 /* First see if VAL1 and VAL2 are not the same. */
557 if (val1 == val2 || operand_equal_p (val1, val2, 0))
560 /* If VAL1 is a lower address than VAL2, return -1. */
561 t = fold_binary (LT_EXPR, boolean_type_node, val1, val2);
562 if (t == boolean_true_node)
565 /* If VAL1 is a higher address than VAL2, return +1. */
566 t = fold_binary (GT_EXPR, boolean_type_node, val1, val2);
567 if (t == boolean_true_node)
570 /* If VAL1 is different than VAL2, return +2. */
571 t = fold_binary (NE_EXPR, boolean_type_node, val1, val2);
572 if (t == boolean_true_node)
580 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
581 0 if VAL is not inside VR,
582 -2 if we cannot tell either way.
584 FIXME, the current semantics of this functions are a bit quirky
585 when taken in the context of VRP. In here we do not care
586 about VR's type. If VR is the anti-range ~[3, 5] the call
587 value_inside_range (4, VR) will return 1.
589 This is counter-intuitive in a strict sense, but the callers
590 currently expect this. They are calling the function
591 merely to determine whether VR->MIN <= VAL <= VR->MAX. The
592 callers are applying the VR_RANGE/VR_ANTI_RANGE semantics
595 This also applies to value_ranges_intersect_p and
596 range_includes_zero_p. The semantics of VR_RANGE and
597 VR_ANTI_RANGE should be encoded here, but that also means
598 adapting the users of these functions to the new semantics. */
601 value_inside_range (tree val, value_range_t *vr)
605 cmp1 = fold_binary_to_constant (GE_EXPR, boolean_type_node, val, vr->min);
609 cmp2 = fold_binary_to_constant (LE_EXPR, boolean_type_node, val, vr->max);
613 return cmp1 == boolean_true_node && cmp2 == boolean_true_node;
617 /* Return true if value ranges VR0 and VR1 have a non-empty
621 value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
623 return (value_inside_range (vr1->min, vr0) == 1
624 || value_inside_range (vr1->max, vr0) == 1
625 || value_inside_range (vr0->min, vr1) == 1
626 || value_inside_range (vr0->max, vr1) == 1);
630 /* Return true if VR includes the value zero, false otherwise. FIXME,
631 currently this will return false for an anti-range like ~[-4, 3].
632 This will be wrong when the semantics of value_inside_range are
633 modified (currently the users of this function expect these
637 range_includes_zero_p (value_range_t *vr)
641 gcc_assert (vr->type != VR_UNDEFINED
642 && vr->type != VR_VARYING
643 && !symbolic_range_p (vr));
645 zero = build_int_cst (TREE_TYPE (vr->min), 0);
646 return (value_inside_range (zero, vr) == 1);
649 /* Return true if T, an SSA_NAME, is known to be nonnegative. Return
650 false otherwise or if no value range information is available. */
653 ssa_name_nonnegative_p (tree t)
655 value_range_t *vr = get_value_range (t);
660 /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
661 which would return a useful value should be encoded as a VR_RANGE. */
662 if (vr->type == VR_RANGE)
664 int result = compare_values (vr->min, integer_zero_node);
666 return (result == 0 || result == 1);
671 /* Return true if T, an SSA_NAME, is known to be nonzero. Return
672 false otherwise or if no value range information is available. */
675 ssa_name_nonzero_p (tree t)
677 value_range_t *vr = get_value_range (t);
682 /* A VR_RANGE which does not include zero is a nonzero value. */
683 if (vr->type == VR_RANGE && !symbolic_range_p (vr))
684 return ! range_includes_zero_p (vr);
686 /* A VR_ANTI_RANGE which does include zero is a nonzero value. */
687 if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr))
688 return range_includes_zero_p (vr);
694 /* When extracting ranges from X_i = ASSERT_EXPR <Y_j, pred>, we will
695 initially consider X_i and Y_j equivalent, so the equivalence set
696 of Y_j is added to the equivalence set of X_i. However, it is
697 possible to have a chain of ASSERT_EXPRs whose predicates are
698 actually incompatible. This is usually the result of nesting of
699 contradictory if-then-else statements. For instance, in PR 24670:
701 count_4 has range [-INF, 63]
705 count_19 = ASSERT_EXPR <count_4, count_4 != 0>
708 count_18 = ASSERT_EXPR <count_19, count_19 > 63>
714 Notice that 'if (count_19 > 63)' is trivially false and will be
715 folded out at the end. However, during propagation, the flowgraph
716 is not cleaned up and so, VRP will evaluate predicates more
717 predicates than necessary, so it must support these
718 inconsistencies. The problem here is that because of the chaining
719 of ASSERT_EXPRs, the equivalency set for count_18 includes count_4.
720 Since count_4 has an incompatible range, we ICE when evaluating the
721 ranges in the equivalency set. So, we need to remove count_4 from
725 fix_equivalence_set (value_range_t *vr_p)
729 bitmap e = vr_p->equiv;
730 bitmap to_remove = BITMAP_ALLOC (NULL);
732 /* Only detect inconsistencies on numeric ranges. */
733 if (vr_p->type == VR_VARYING
734 || vr_p->type == VR_UNDEFINED
735 || symbolic_range_p (vr_p))
738 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
740 value_range_t *equiv_vr = vr_value[i];
742 if (equiv_vr->type == VR_VARYING
743 || equiv_vr->type == VR_UNDEFINED
744 || symbolic_range_p (equiv_vr))
747 if (equiv_vr->type == VR_RANGE
748 && vr_p->type == VR_RANGE
749 && !value_ranges_intersect_p (vr_p, equiv_vr))
750 bitmap_set_bit (to_remove, i);
751 else if ((equiv_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
752 || (equiv_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
754 /* A range and an anti-range have an empty intersection if
755 their end points are the same. FIXME,
756 value_ranges_intersect_p should handle this
758 if (compare_values (equiv_vr->min, vr_p->min) == 0
759 && compare_values (equiv_vr->max, vr_p->max) == 0)
760 bitmap_set_bit (to_remove, i);
764 bitmap_and_compl_into (vr_p->equiv, to_remove);
765 BITMAP_FREE (to_remove);
769 /* Extract value range information from an ASSERT_EXPR EXPR and store
773 extract_range_from_assert (value_range_t *vr_p, tree expr)
775 tree var, cond, limit, min, max, type;
776 value_range_t *var_vr, *limit_vr;
777 enum tree_code cond_code;
779 var = ASSERT_EXPR_VAR (expr);
780 cond = ASSERT_EXPR_COND (expr);
782 gcc_assert (COMPARISON_CLASS_P (cond));
784 /* Find VAR in the ASSERT_EXPR conditional. */
785 if (var == TREE_OPERAND (cond, 0))
787 /* If the predicate is of the form VAR COMP LIMIT, then we just
788 take LIMIT from the RHS and use the same comparison code. */
789 limit = TREE_OPERAND (cond, 1);
790 cond_code = TREE_CODE (cond);
794 /* If the predicate is of the form LIMIT COMP VAR, then we need
795 to flip around the comparison code to create the proper range
797 limit = TREE_OPERAND (cond, 0);
798 cond_code = swap_tree_comparison (TREE_CODE (cond));
801 type = TREE_TYPE (limit);
802 gcc_assert (limit != var);
804 /* For pointer arithmetic, we only keep track of pointer equality
806 if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
808 set_value_range_to_varying (vr_p);
812 /* If LIMIT is another SSA name and LIMIT has a range of its own,
813 try to use LIMIT's range to avoid creating symbolic ranges
815 limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
817 /* LIMIT's range is only interesting if it has any useful information. */
819 && (limit_vr->type == VR_UNDEFINED
820 || limit_vr->type == VR_VARYING
821 || symbolic_range_p (limit_vr)))
824 /* Initially, the new range has the same set of equivalences of
825 VAR's range. This will be revised before returning the final
826 value. Since assertions may be chained via mutually exclusive
827 predicates, we will need to trim the set of equivalences before
829 gcc_assert (vr_p->equiv == NULL);
830 vr_p->equiv = BITMAP_ALLOC (NULL);
831 add_equivalence (vr_p->equiv, var);
833 /* Extract a new range based on the asserted comparison for VAR and
834 LIMIT's value range. Notice that if LIMIT has an anti-range, we
835 will only use it for equality comparisons (EQ_EXPR). For any
836 other kind of assertion, we cannot derive a range from LIMIT's
837 anti-range that can be used to describe the new range. For
838 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
839 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
840 no single range for x_2 that could describe LE_EXPR, so we might
841 as well build the range [b_4, +INF] for it. */
842 if (cond_code == EQ_EXPR)
844 enum value_range_type range_type;
848 range_type = limit_vr->type;
854 range_type = VR_RANGE;
859 set_value_range (vr_p, range_type, min, max, vr_p->equiv);
861 /* When asserting the equality VAR == LIMIT and LIMIT is another
862 SSA name, the new range will also inherit the equivalence set
864 if (TREE_CODE (limit) == SSA_NAME)
865 add_equivalence (vr_p->equiv, limit);
867 else if (cond_code == NE_EXPR)
869 /* As described above, when LIMIT's range is an anti-range and
870 this assertion is an inequality (NE_EXPR), then we cannot
871 derive anything from the anti-range. For instance, if
872 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
873 not imply that VAR's range is [0, 0]. So, in the case of
874 anti-ranges, we just assert the inequality using LIMIT and
877 If LIMIT_VR is a range, we can only use it to build a new
878 anti-range if LIMIT_VR is a single-valued range. For
879 instance, if LIMIT_VR is [0, 1], the predicate
880 VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
881 Rather, it means that for value 0 VAR should be ~[0, 0]
882 and for value 1, VAR should be ~[1, 1]. We cannot
883 represent these ranges.
885 The only situation in which we can build a valid
886 anti-range is when LIMIT_VR is a single-valued range
887 (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
888 build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
890 && limit_vr->type == VR_RANGE
891 && compare_values (limit_vr->min, limit_vr->max) == 0)
898 /* In any other case, we cannot use LIMIT's range to build a
903 /* If MIN and MAX cover the whole range for their type, then
904 just use the original LIMIT. */
905 if (INTEGRAL_TYPE_P (type)
906 && min == TYPE_MIN_VALUE (type)
907 && max == TYPE_MAX_VALUE (type))
910 set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
912 else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
914 min = TYPE_MIN_VALUE (type);
916 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
920 /* If LIMIT_VR is of the form [N1, N2], we need to build the
921 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
926 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
927 if (cond_code == LT_EXPR)
929 tree one = build_int_cst (type, 1);
930 max = fold_build2 (MINUS_EXPR, type, max, one);
933 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
935 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
937 max = TYPE_MAX_VALUE (type);
939 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
943 /* If LIMIT_VR is of the form [N1, N2], we need to build the
944 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
949 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
950 if (cond_code == GT_EXPR)
952 tree one = build_int_cst (type, 1);
953 min = fold_build2 (PLUS_EXPR, type, min, one);
956 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
961 /* If VAR already had a known range, it may happen that the new
962 range we have computed and VAR's range are not compatible. For
966 p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
968 p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
970 While the above comes from a faulty program, it will cause an ICE
971 later because p_8 and p_6 will have incompatible ranges and at
972 the same time will be considered equivalent. A similar situation
976 i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
978 i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
980 Again i_6 and i_7 will have incompatible ranges. It would be
981 pointless to try and do anything with i_7's range because
982 anything dominated by 'if (i_5 < 5)' will be optimized away.
983 Note, due to the wa in which simulation proceeds, the statement
984 i_7 = ASSERT_EXPR <...> we would never be visited because the
985 conditional 'if (i_5 < 5)' always evaluates to false. However,
986 this extra check does not hurt and may protect against future
987 changes to VRP that may get into a situation similar to the
988 NULL pointer dereference example.
990 Note that these compatibility tests are only needed when dealing
991 with ranges or a mix of range and anti-range. If VAR_VR and VR_P
992 are both anti-ranges, they will always be compatible, because two
993 anti-ranges will always have a non-empty intersection. */
995 var_vr = get_value_range (var);
997 /* We may need to make adjustments when VR_P and VAR_VR are numeric
998 ranges or anti-ranges. */
999 if (vr_p->type == VR_VARYING
1000 || vr_p->type == VR_UNDEFINED
1001 || var_vr->type == VR_VARYING
1002 || var_vr->type == VR_UNDEFINED
1003 || symbolic_range_p (vr_p)
1004 || symbolic_range_p (var_vr))
1007 if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
1009 /* If the two ranges have a non-empty intersection, we can
1010 refine the resulting range. Since the assert expression
1011 creates an equivalency and at the same time it asserts a
1012 predicate, we can take the intersection of the two ranges to
1013 get better precision. */
1014 if (value_ranges_intersect_p (var_vr, vr_p))
1016 /* Use the larger of the two minimums. */
1017 if (compare_values (vr_p->min, var_vr->min) == -1)
1022 /* Use the smaller of the two maximums. */
1023 if (compare_values (vr_p->max, var_vr->max) == 1)
1028 set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
1032 /* The two ranges do not intersect, set the new range to
1033 VARYING, because we will not be able to do anything
1034 meaningful with it. */
1035 set_value_range_to_varying (vr_p);
1038 else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
1039 || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
1041 /* A range and an anti-range will cancel each other only if
1042 their ends are the same. For instance, in the example above,
1043 p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
1044 so VR_P should be set to VR_VARYING. */
1045 if (compare_values (var_vr->min, vr_p->min) == 0
1046 && compare_values (var_vr->max, vr_p->max) == 0)
1047 set_value_range_to_varying (vr_p);
1050 tree min, max, anti_min, anti_max, real_min, real_max;
1052 /* We want to compute the logical AND of the two ranges;
1053 there are three cases to consider.
1056 1. The VR_ANTI_RANGE range is completely within the
1057 VR_RANGE and the endpoints of the ranges are
1058 different. In that case the resulting range
1059 should be whichever range is more precise.
1060 Typically that will be the VR_RANGE.
1062 2. The VR_ANTI_RANGE is completely disjoint from
1063 the VR_RANGE. In this case the resulting range
1064 should be the VR_RANGE.
1066 3. There is some overlap between the VR_ANTI_RANGE
1069 3a. If the high limit of the VR_ANTI_RANGE resides
1070 within the VR_RANGE, then the result is a new
1071 VR_RANGE starting at the high limit of the
1072 the VR_ANTI_RANGE + 1 and extending to the
1073 high limit of the original VR_RANGE.
1075 3b. If the low limit of the VR_ANTI_RANGE resides
1076 within the VR_RANGE, then the result is a new
1077 VR_RANGE starting at the low limit of the original
1078 VR_RANGE and extending to the low limit of the
1079 VR_ANTI_RANGE - 1. */
1080 if (vr_p->type == VR_ANTI_RANGE)
1082 anti_min = vr_p->min;
1083 anti_max = vr_p->max;
1084 real_min = var_vr->min;
1085 real_max = var_vr->max;
1089 anti_min = var_vr->min;
1090 anti_max = var_vr->max;
1091 real_min = vr_p->min;
1092 real_max = vr_p->max;
1096 /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
1097 not including any endpoints. */
1098 if (compare_values (anti_max, real_max) == -1
1099 && compare_values (anti_min, real_min) == 1)
1101 set_value_range (vr_p, VR_RANGE, real_min,
1102 real_max, vr_p->equiv);
1104 /* Case 2, VR_ANTI_RANGE completely disjoint from
1106 else if (compare_values (anti_min, real_max) == 1
1107 || compare_values (anti_max, real_min) == -1)
1109 set_value_range (vr_p, VR_RANGE, real_min,
1110 real_max, vr_p->equiv);
1112 /* Case 3a, the anti-range extends into the low
1113 part of the real range. Thus creating a new
1114 low for the real range. */
1115 else if ((compare_values (anti_max, real_min) == 1
1116 || compare_values (anti_max, real_min) == 0)
1117 && compare_values (anti_max, real_max) == -1)
1119 min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
1121 build_int_cst (TREE_TYPE (var_vr->min), 1));
1123 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1125 /* Case 3b, the anti-range extends into the high
1126 part of the real range. Thus creating a new
1127 higher for the real range. */
1128 else if (compare_values (anti_min, real_min) == 1
1129 && (compare_values (anti_min, real_max) == -1
1130 || compare_values (anti_min, real_max) == 0))
1132 max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
1134 build_int_cst (TREE_TYPE (var_vr->min), 1));
1136 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1141 /* Remove names from the equivalence set that have ranges
1142 incompatible with VR_P. */
1144 fix_equivalence_set (vr_p);
1148 /* Extract range information from SSA name VAR and store it in VR. If
1149 VAR has an interesting range, use it. Otherwise, create the
1150 range [VAR, VAR] and return it. This is useful in situations where
1151 we may have conditionals testing values of VARYING names. For
1158 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
1162 extract_range_from_ssa_name (value_range_t *vr, tree var)
1164 value_range_t *var_vr = get_value_range (var);
1166 if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
1167 copy_value_range (vr, var_vr);
1169 set_value_range (vr, VR_RANGE, var, var, NULL);
1171 add_equivalence (vr->equiv, var);
1175 /* Wrapper around int_const_binop. If the operation overflows and we
1176 are not using wrapping arithmetic, then adjust the result to be
1177 -INF or +INF depending on CODE, VAL1 and VAL2. */
1180 vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
1185 return int_const_binop (code, val1, val2, 0);
1187 /* If we are not using wrapping arithmetic, operate symbolically
1188 on -INF and +INF. */
1189 res = int_const_binop (code, val1, val2, 0);
1191 if (TYPE_UNSIGNED (TREE_TYPE (val1)))
1193 int checkz = compare_values (res, val1);
1195 /* Ensure that res = val1 [+*] val2 >= val1
1196 or that res = val1 - val2 <= val1. */
1197 if (((code == PLUS_EXPR || code == MULT_EXPR)
1198 && !(checkz == 1 || checkz == 0))
1199 || (code == MINUS_EXPR
1200 && !(checkz == 0 || checkz == -1)))
1202 res = copy_node (res);
1203 TREE_OVERFLOW (res) = 1;
1206 else if (TREE_OVERFLOW (res)
1207 && !TREE_OVERFLOW (val1)
1208 && !TREE_OVERFLOW (val2))
1210 /* If the operation overflowed but neither VAL1 nor VAL2 are
1211 overflown, return -INF or +INF depending on the operation
1212 and the combination of signs of the operands. */
1213 int sgn1 = tree_int_cst_sgn (val1);
1214 int sgn2 = tree_int_cst_sgn (val2);
1216 /* Notice that we only need to handle the restricted set of
1217 operations handled by extract_range_from_binary_expr.
1218 Among them, only multiplication, addition and subtraction
1219 can yield overflow without overflown operands because we
1220 are working with integral types only... except in the
1221 case VAL1 = -INF and VAL2 = -1 which overflows to +INF
1222 for division too. */
1224 /* For multiplication, the sign of the overflow is given
1225 by the comparison of the signs of the operands. */
1226 if ((code == MULT_EXPR && sgn1 == sgn2)
1227 /* For addition, the operands must be of the same sign
1228 to yield an overflow. Its sign is therefore that
1229 of one of the operands, for example the first. */
1230 || (code == PLUS_EXPR && sgn1 > 0)
1231 /* For subtraction, the operands must be of different
1232 signs to yield an overflow. Its sign is therefore
1233 that of the first operand or the opposite of that
1234 of the second operand. A first operand of 0 counts
1235 as positive here, for the corner case 0 - (-INF),
1236 which overflows, but must yield +INF. */
1237 || (code == MINUS_EXPR && sgn1 >= 0)
1238 /* For division, the only case is -INF / -1 = +INF. */
1239 || code == TRUNC_DIV_EXPR
1240 || code == FLOOR_DIV_EXPR
1241 || code == CEIL_DIV_EXPR
1242 || code == EXACT_DIV_EXPR
1243 || code == ROUND_DIV_EXPR)
1244 return TYPE_MAX_VALUE (TREE_TYPE (res));
1246 return TYPE_MIN_VALUE (TREE_TYPE (res));
1253 /* Extract range information from a binary expression EXPR based on
1254 the ranges of each of its operands and the expression code. */
1257 extract_range_from_binary_expr (value_range_t *vr, tree expr)
1259 enum tree_code code = TREE_CODE (expr);
1260 enum value_range_type type;
1261 tree op0, op1, min, max;
1263 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1264 value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1266 /* Not all binary expressions can be applied to ranges in a
1267 meaningful way. Handle only arithmetic operations. */
1268 if (code != PLUS_EXPR
1269 && code != MINUS_EXPR
1270 && code != MULT_EXPR
1271 && code != TRUNC_DIV_EXPR
1272 && code != FLOOR_DIV_EXPR
1273 && code != CEIL_DIV_EXPR
1274 && code != EXACT_DIV_EXPR
1275 && code != ROUND_DIV_EXPR
1278 && code != BIT_AND_EXPR
1279 && code != TRUTH_ANDIF_EXPR
1280 && code != TRUTH_ORIF_EXPR
1281 && code != TRUTH_AND_EXPR
1282 && code != TRUTH_OR_EXPR)
1284 set_value_range_to_varying (vr);
1288 /* Get value ranges for each operand. For constant operands, create
1289 a new value range with the operand to simplify processing. */
1290 op0 = TREE_OPERAND (expr, 0);
1291 if (TREE_CODE (op0) == SSA_NAME)
1292 vr0 = *(get_value_range (op0));
1293 else if (is_gimple_min_invariant (op0))
1294 set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1296 set_value_range_to_varying (&vr0);
1298 op1 = TREE_OPERAND (expr, 1);
1299 if (TREE_CODE (op1) == SSA_NAME)
1300 vr1 = *(get_value_range (op1));
1301 else if (is_gimple_min_invariant (op1))
1302 set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
1304 set_value_range_to_varying (&vr1);
1306 /* If either range is UNDEFINED, so is the result. */
1307 if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
1309 set_value_range_to_undefined (vr);
1313 /* The type of the resulting value range defaults to VR0.TYPE. */
1316 /* Refuse to operate on VARYING ranges, ranges of different kinds
1317 and symbolic ranges. As an exception, we allow BIT_AND_EXPR
1318 because we may be able to derive a useful range even if one of
1319 the operands is VR_VARYING or symbolic range. TODO, we may be
1320 able to derive anti-ranges in some cases. */
1321 if (code != BIT_AND_EXPR
1322 && code != TRUTH_AND_EXPR
1323 && code != TRUTH_OR_EXPR
1324 && (vr0.type == VR_VARYING
1325 || vr1.type == VR_VARYING
1326 || vr0.type != vr1.type
1327 || symbolic_range_p (&vr0)
1328 || symbolic_range_p (&vr1)))
1330 set_value_range_to_varying (vr);
1334 /* Now evaluate the expression to determine the new range. */
1335 if (POINTER_TYPE_P (TREE_TYPE (expr))
1336 || POINTER_TYPE_P (TREE_TYPE (op0))
1337 || POINTER_TYPE_P (TREE_TYPE (op1)))
1339 /* For pointer types, we are really only interested in asserting
1340 whether the expression evaluates to non-NULL. FIXME, we used
1341 to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
1342 ivopts is generating expressions with pointer multiplication
1344 if (code == PLUS_EXPR)
1346 if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
1347 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1348 else if (range_is_null (&vr0) && range_is_null (&vr1))
1349 set_value_range_to_null (vr, TREE_TYPE (expr));
1351 set_value_range_to_varying (vr);
1355 /* Subtracting from a pointer, may yield 0, so just drop the
1356 resulting range to varying. */
1357 set_value_range_to_varying (vr);
1363 /* For integer ranges, apply the operation to each end of the
1364 range and see what we end up with. */
1365 if (code == TRUTH_ANDIF_EXPR
1366 || code == TRUTH_ORIF_EXPR
1367 || code == TRUTH_AND_EXPR
1368 || code == TRUTH_OR_EXPR)
1370 /* If one of the operands is zero, we know that the whole
1371 expression evaluates zero. */
1372 if (code == TRUTH_AND_EXPR
1373 && ((vr0.type == VR_RANGE
1374 && integer_zerop (vr0.min)
1375 && integer_zerop (vr0.max))
1376 || (vr1.type == VR_RANGE
1377 && integer_zerop (vr1.min)
1378 && integer_zerop (vr1.max))))
1381 min = max = build_int_cst (TREE_TYPE (expr), 0);
1383 /* If one of the operands is one, we know that the whole
1384 expression evaluates one. */
1385 else if (code == TRUTH_OR_EXPR
1386 && ((vr0.type == VR_RANGE
1387 && integer_onep (vr0.min)
1388 && integer_onep (vr0.max))
1389 || (vr1.type == VR_RANGE
1390 && integer_onep (vr1.min)
1391 && integer_onep (vr1.max))))
1394 min = max = build_int_cst (TREE_TYPE (expr), 1);
1396 else if (vr0.type != VR_VARYING
1397 && vr1.type != VR_VARYING
1398 && vr0.type == vr1.type
1399 && !symbolic_range_p (&vr0)
1400 && !symbolic_range_p (&vr1))
1402 /* Boolean expressions cannot be folded with int_const_binop. */
1403 min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
1404 max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
1408 set_value_range_to_varying (vr);
1412 else if (code == PLUS_EXPR
1414 || code == MAX_EXPR)
1416 /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
1417 VR_VARYING. It would take more effort to compute a precise
1418 range for such a case. For example, if we have op0 == 1 and
1419 op1 == -1 with their ranges both being ~[0,0], we would have
1420 op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
1421 Note that we are guaranteed to have vr0.type == vr1.type at
1423 if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
1425 set_value_range_to_varying (vr);
1429 /* For operations that make the resulting range directly
1430 proportional to the original ranges, apply the operation to
1431 the same end of each range. */
1432 min = vrp_int_const_binop (code, vr0.min, vr1.min);
1433 max = vrp_int_const_binop (code, vr0.max, vr1.max);
1435 else if (code == MULT_EXPR
1436 || code == TRUNC_DIV_EXPR
1437 || code == FLOOR_DIV_EXPR
1438 || code == CEIL_DIV_EXPR
1439 || code == EXACT_DIV_EXPR
1440 || code == ROUND_DIV_EXPR)
1445 /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
1446 drop to VR_VARYING. It would take more effort to compute a
1447 precise range for such a case. For example, if we have
1448 op0 == 65536 and op1 == 65536 with their ranges both being
1449 ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
1450 we cannot claim that the product is in ~[0,0]. Note that we
1451 are guaranteed to have vr0.type == vr1.type at this
1453 if (code == MULT_EXPR
1454 && vr0.type == VR_ANTI_RANGE
1455 && (flag_wrapv || TYPE_UNSIGNED (TREE_TYPE (op0))))
1457 set_value_range_to_varying (vr);
1461 /* Multiplications and divisions are a bit tricky to handle,
1462 depending on the mix of signs we have in the two ranges, we
1463 need to operate on different values to get the minimum and
1464 maximum values for the new range. One approach is to figure
1465 out all the variations of range combinations and do the
1468 However, this involves several calls to compare_values and it
1469 is pretty convoluted. It's simpler to do the 4 operations
1470 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
1471 MAX1) and then figure the smallest and largest values to form
1474 /* Divisions by zero result in a VARYING value. */
1475 if (code != MULT_EXPR
1476 && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
1478 set_value_range_to_varying (vr);
1482 /* Compute the 4 cross operations. */
1483 val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
1485 val[1] = (vr1.max != vr1.min)
1486 ? vrp_int_const_binop (code, vr0.min, vr1.max)
1489 val[2] = (vr0.max != vr0.min)
1490 ? vrp_int_const_binop (code, vr0.max, vr1.min)
1493 val[3] = (vr0.min != vr0.max && vr1.min != vr1.max)
1494 ? vrp_int_const_binop (code, vr0.max, vr1.max)
1497 /* Set MIN to the minimum of VAL[i] and MAX to the maximum
1501 for (i = 1; i < 4; i++)
1503 if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
1504 || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
1509 if (!is_gimple_min_invariant (val[i]) || TREE_OVERFLOW (val[i]))
1511 /* If we found an overflowed value, set MIN and MAX
1512 to it so that we set the resulting range to
1518 if (compare_values (val[i], min) == -1)
1521 if (compare_values (val[i], max) == 1)
1526 else if (code == MINUS_EXPR)
1528 /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
1529 VR_VARYING. It would take more effort to compute a precise
1530 range for such a case. For example, if we have op0 == 1 and
1531 op1 == 1 with their ranges both being ~[0,0], we would have
1532 op0 - op1 == 0, so we cannot claim that the difference is in
1533 ~[0,0]. Note that we are guaranteed to have
1534 vr0.type == vr1.type at this point. */
1535 if (vr0.type == VR_ANTI_RANGE)
1537 set_value_range_to_varying (vr);
1541 /* For MINUS_EXPR, apply the operation to the opposite ends of
1543 min = vrp_int_const_binop (code, vr0.min, vr1.max);
1544 max = vrp_int_const_binop (code, vr0.max, vr1.min);
1546 else if (code == BIT_AND_EXPR)
1548 if (vr0.type == VR_RANGE
1549 && vr0.min == vr0.max
1550 && tree_expr_nonnegative_p (vr0.max)
1551 && TREE_CODE (vr0.max) == INTEGER_CST)
1553 min = build_int_cst (TREE_TYPE (expr), 0);
1556 else if (vr1.type == VR_RANGE
1557 && vr1.min == vr1.max
1558 && tree_expr_nonnegative_p (vr1.max)
1559 && TREE_CODE (vr1.max) == INTEGER_CST)
1562 min = build_int_cst (TREE_TYPE (expr), 0);
1567 set_value_range_to_varying (vr);
1574 /* If either MIN or MAX overflowed, then set the resulting range to
1576 if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
1577 || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
1579 set_value_range_to_varying (vr);
1583 cmp = compare_values (min, max);
1584 if (cmp == -2 || cmp == 1)
1586 /* If the new range has its limits swapped around (MIN > MAX),
1587 then the operation caused one of them to wrap around, mark
1588 the new range VARYING. */
1589 set_value_range_to_varying (vr);
1592 set_value_range (vr, type, min, max, NULL);
1596 /* Extract range information from a unary expression EXPR based on
1597 the range of its operand and the expression code. */
1600 extract_range_from_unary_expr (value_range_t *vr, tree expr)
1602 enum tree_code code = TREE_CODE (expr);
1605 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1607 /* Refuse to operate on certain unary expressions for which we
1608 cannot easily determine a resulting range. */
1609 if (code == FIX_TRUNC_EXPR
1610 || code == FIX_CEIL_EXPR
1611 || code == FIX_FLOOR_EXPR
1612 || code == FIX_ROUND_EXPR
1613 || code == FLOAT_EXPR
1614 || code == BIT_NOT_EXPR
1615 || code == NON_LVALUE_EXPR
1616 || code == CONJ_EXPR)
1618 set_value_range_to_varying (vr);
1622 /* Get value ranges for the operand. For constant operands, create
1623 a new value range with the operand to simplify processing. */
1624 op0 = TREE_OPERAND (expr, 0);
1625 if (TREE_CODE (op0) == SSA_NAME)
1626 vr0 = *(get_value_range (op0));
1627 else if (is_gimple_min_invariant (op0))
1628 set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1630 set_value_range_to_varying (&vr0);
1632 /* If VR0 is UNDEFINED, so is the result. */
1633 if (vr0.type == VR_UNDEFINED)
1635 set_value_range_to_undefined (vr);
1639 /* Refuse to operate on symbolic ranges, or if neither operand is
1640 a pointer or integral type. */
1641 if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0))
1642 && !POINTER_TYPE_P (TREE_TYPE (op0)))
1643 || (vr0.type != VR_VARYING
1644 && symbolic_range_p (&vr0)))
1646 set_value_range_to_varying (vr);
1650 /* If the expression involves pointers, we are only interested in
1651 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
1652 if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
1654 if (range_is_nonnull (&vr0) || tree_expr_nonzero_p (expr))
1655 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1656 else if (range_is_null (&vr0))
1657 set_value_range_to_null (vr, TREE_TYPE (expr));
1659 set_value_range_to_varying (vr);
1664 /* Handle unary expressions on integer ranges. */
1665 if (code == NOP_EXPR || code == CONVERT_EXPR)
1667 tree inner_type = TREE_TYPE (op0);
1668 tree outer_type = TREE_TYPE (expr);
1670 /* If VR0 represents a simple range, then try to convert
1671 the min and max values for the range to the same type
1672 as OUTER_TYPE. If the results compare equal to VR0's
1673 min and max values and the new min is still less than
1674 or equal to the new max, then we can safely use the newly
1675 computed range for EXPR. This allows us to compute
1676 accurate ranges through many casts. */
1677 if (vr0.type == VR_RANGE
1678 || (vr0.type == VR_VARYING
1679 && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)))
1681 tree new_min, new_max, orig_min, orig_max;
1683 /* Convert the input operand min/max to OUTER_TYPE. If
1684 the input has no range information, then use the min/max
1685 for the input's type. */
1686 if (vr0.type == VR_RANGE)
1693 orig_min = TYPE_MIN_VALUE (inner_type);
1694 orig_max = TYPE_MAX_VALUE (inner_type);
1697 new_min = fold_convert (outer_type, orig_min);
1698 new_max = fold_convert (outer_type, orig_max);
1700 /* Verify the new min/max values are gimple values and
1701 that they compare equal to the original input's
1703 if (is_gimple_val (new_min)
1704 && is_gimple_val (new_max)
1705 && tree_int_cst_equal (new_min, orig_min)
1706 && tree_int_cst_equal (new_max, orig_max)
1707 && compare_values (new_min, new_max) <= 0
1708 && compare_values (new_min, new_max) >= -1)
1710 set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv);
1715 /* When converting types of different sizes, set the result to
1716 VARYING. Things like sign extensions and precision loss may
1717 change the range. For instance, if x_3 is of type 'long long
1718 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
1719 is impossible to know at compile time whether y_5 will be
1721 if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type)
1722 || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1724 set_value_range_to_varying (vr);
1729 /* Conversion of a VR_VARYING value to a wider type can result
1730 in a usable range. So wait until after we've handled conversions
1731 before dropping the result to VR_VARYING if we had a source
1732 operand that is VR_VARYING. */
1733 if (vr0.type == VR_VARYING)
1735 set_value_range_to_varying (vr);
1739 /* Apply the operation to each end of the range and see what we end
1741 if (code == NEGATE_EXPR
1742 && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1744 /* NEGATE_EXPR flips the range around. */
1745 min = (vr0.max == TYPE_MAX_VALUE (TREE_TYPE (expr)) && !flag_wrapv)
1746 ? TYPE_MIN_VALUE (TREE_TYPE (expr))
1747 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1749 max = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)) && !flag_wrapv)
1750 ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1751 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1754 else if (code == NEGATE_EXPR
1755 && TYPE_UNSIGNED (TREE_TYPE (expr)))
1757 if (!range_includes_zero_p (&vr0))
1759 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1760 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1764 if (range_is_null (&vr0))
1765 set_value_range_to_null (vr, TREE_TYPE (expr));
1767 set_value_range_to_varying (vr);
1771 else if (code == ABS_EXPR
1772 && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1774 /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
1777 && ((vr0.type == VR_RANGE
1778 && vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1779 || (vr0.type == VR_ANTI_RANGE
1780 && vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))
1781 && !range_includes_zero_p (&vr0))))
1783 set_value_range_to_varying (vr);
1787 /* ABS_EXPR may flip the range around, if the original range
1788 included negative values. */
1789 min = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1790 ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1791 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1793 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1795 cmp = compare_values (min, max);
1797 /* If a VR_ANTI_RANGEs contains zero, then we have
1798 ~[-INF, min(MIN, MAX)]. */
1799 if (vr0.type == VR_ANTI_RANGE)
1801 if (range_includes_zero_p (&vr0))
1803 tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr));
1805 /* Take the lower of the two values. */
1809 /* Create ~[-INF, min (abs(MIN), abs(MAX))]
1810 or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
1811 flag_wrapv is set and the original anti-range doesn't include
1812 TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */
1813 min = (flag_wrapv && vr0.min != type_min_value
1814 ? int_const_binop (PLUS_EXPR,
1816 integer_one_node, 0)
1821 /* All else has failed, so create the range [0, INF], even for
1822 flag_wrapv since TYPE_MIN_VALUE is in the original
1824 vr0.type = VR_RANGE;
1825 min = build_int_cst (TREE_TYPE (expr), 0);
1826 max = TYPE_MAX_VALUE (TREE_TYPE (expr));
1830 /* If the range contains zero then we know that the minimum value in the
1831 range will be zero. */
1832 else if (range_includes_zero_p (&vr0))
1836 min = build_int_cst (TREE_TYPE (expr), 0);
1840 /* If the range was reversed, swap MIN and MAX. */
1851 /* Otherwise, operate on each end of the range. */
1852 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1853 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1856 cmp = compare_values (min, max);
1857 if (cmp == -2 || cmp == 1)
1859 /* If the new range has its limits swapped around (MIN > MAX),
1860 then the operation caused one of them to wrap around, mark
1861 the new range VARYING. */
1862 set_value_range_to_varying (vr);
1865 set_value_range (vr, vr0.type, min, max, NULL);
1869 /* Extract range information from a comparison expression EXPR based
1870 on the range of its operand and the expression code. */
1873 extract_range_from_comparison (value_range_t *vr, tree expr)
1875 tree val = vrp_evaluate_conditional (expr, false);
1878 /* Since this expression was found on the RHS of an assignment,
1879 its type may be different from _Bool. Convert VAL to EXPR's
1881 val = fold_convert (TREE_TYPE (expr), val);
1882 set_value_range (vr, VR_RANGE, val, val, vr->equiv);
1885 set_value_range_to_varying (vr);
1889 /* Try to compute a useful range out of expression EXPR and store it
1893 extract_range_from_expr (value_range_t *vr, tree expr)
1895 enum tree_code code = TREE_CODE (expr);
1897 if (code == ASSERT_EXPR)
1898 extract_range_from_assert (vr, expr);
1899 else if (code == SSA_NAME)
1900 extract_range_from_ssa_name (vr, expr);
1901 else if (TREE_CODE_CLASS (code) == tcc_binary
1902 || code == TRUTH_ANDIF_EXPR
1903 || code == TRUTH_ORIF_EXPR
1904 || code == TRUTH_AND_EXPR
1905 || code == TRUTH_OR_EXPR
1906 || code == TRUTH_XOR_EXPR)
1907 extract_range_from_binary_expr (vr, expr);
1908 else if (TREE_CODE_CLASS (code) == tcc_unary)
1909 extract_range_from_unary_expr (vr, expr);
1910 else if (TREE_CODE_CLASS (code) == tcc_comparison)
1911 extract_range_from_comparison (vr, expr);
1912 else if (is_gimple_min_invariant (expr))
1913 set_value_range (vr, VR_RANGE, expr, expr, NULL);
1915 set_value_range_to_varying (vr);
1917 /* If we got a varying range from the tests above, try a final
1918 time to derive a nonnegative or nonzero range. This time
1919 relying primarily on generic routines in fold in conjunction
1921 if (vr->type == VR_VARYING)
1923 if (INTEGRAL_TYPE_P (TREE_TYPE (expr))
1924 && vrp_expr_computes_nonnegative (expr))
1925 set_value_range_to_nonnegative (vr, TREE_TYPE (expr));
1926 else if (vrp_expr_computes_nonzero (expr))
1927 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1931 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1932 would be profitable to adjust VR using scalar evolution information
1933 for VAR. If so, update VR with the new limits. */
1936 adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
1939 tree init, step, chrec;
1940 bool init_is_max, unknown_max;
1942 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1943 better opportunities than a regular range, but I'm not sure. */
1944 if (vr->type == VR_ANTI_RANGE)
1947 chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
1948 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1951 init = initial_condition_in_loop_num (chrec, loop->num);
1952 step = evolution_part_in_loop_num (chrec, loop->num);
1954 /* If STEP is symbolic, we can't know whether INIT will be the
1955 minimum or maximum value in the range. */
1956 if (step == NULL_TREE
1957 || !is_gimple_min_invariant (step))
1960 /* Do not adjust ranges when chrec may wrap. */
1961 if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,
1962 current_loops->parray[CHREC_VARIABLE (chrec)],
1963 &init_is_max, &unknown_max)
1967 if (!POINTER_TYPE_P (TREE_TYPE (init))
1968 && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
1970 /* For VARYING or UNDEFINED ranges, just about anything we get
1971 from scalar evolutions should be better. */
1972 tree min = TYPE_MIN_VALUE (TREE_TYPE (init));
1973 tree max = TYPE_MAX_VALUE (TREE_TYPE (init));
1980 /* If we would create an invalid range, then just assume we
1981 know absolutely nothing. This may be over-conservative,
1982 but it's clearly safe. */
1983 if (compare_values (min, max) == 1)
1986 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
1988 else if (vr->type == VR_RANGE)
1995 /* INIT is the maximum value. If INIT is lower than VR->MAX
1996 but no smaller than VR->MIN, set VR->MAX to INIT. */
1997 if (compare_values (init, max) == -1)
2001 /* If we just created an invalid range with the minimum
2002 greater than the maximum, take the minimum all the
2004 if (compare_values (min, max) == 1)
2005 min = TYPE_MIN_VALUE (TREE_TYPE (min));
2010 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
2011 if (compare_values (init, min) == 1)
2015 /* If we just created an invalid range with the minimum
2016 greater than the maximum, take the maximum all the
2018 if (compare_values (min, max) == 1)
2019 max = TYPE_MAX_VALUE (TREE_TYPE (max));
2023 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
2028 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
2030 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
2031 all the values in the ranges.
2033 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
2035 - Return NULL_TREE if it is not always possible to determine the
2036 value of the comparison. */
2040 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1)
2042 /* VARYING or UNDEFINED ranges cannot be compared. */
2043 if (vr0->type == VR_VARYING
2044 || vr0->type == VR_UNDEFINED
2045 || vr1->type == VR_VARYING
2046 || vr1->type == VR_UNDEFINED)
2049 /* Anti-ranges need to be handled separately. */
2050 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
2052 /* If both are anti-ranges, then we cannot compute any
2054 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
2057 /* These comparisons are never statically computable. */
2064 /* Equality can be computed only between a range and an
2065 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
2066 if (vr0->type == VR_RANGE)
2068 /* To simplify processing, make VR0 the anti-range. */
2069 value_range_t *tmp = vr0;
2074 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
2076 if (compare_values (vr0->min, vr1->min) == 0
2077 && compare_values (vr0->max, vr1->max) == 0)
2078 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
2083 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
2084 operands around and change the comparison code. */
2085 if (comp == GT_EXPR || comp == GE_EXPR)
2088 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
2094 if (comp == EQ_EXPR)
2096 /* Equality may only be computed if both ranges represent
2097 exactly one value. */
2098 if (compare_values (vr0->min, vr0->max) == 0
2099 && compare_values (vr1->min, vr1->max) == 0)
2101 int cmp_min = compare_values (vr0->min, vr1->min);
2102 int cmp_max = compare_values (vr0->max, vr1->max);
2103 if (cmp_min == 0 && cmp_max == 0)
2104 return boolean_true_node;
2105 else if (cmp_min != -2 && cmp_max != -2)
2106 return boolean_false_node;
2108 /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
2109 else if (compare_values (vr0->min, vr1->max) == 1
2110 || compare_values (vr1->min, vr0->max) == 1)
2111 return boolean_false_node;
2115 else if (comp == NE_EXPR)
2119 /* If VR0 is completely to the left or completely to the right
2120 of VR1, they are always different. Notice that we need to
2121 make sure that both comparisons yield similar results to
2122 avoid comparing values that cannot be compared at
2124 cmp1 = compare_values (vr0->max, vr1->min);
2125 cmp2 = compare_values (vr0->min, vr1->max);
2126 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
2127 return boolean_true_node;
2129 /* If VR0 and VR1 represent a single value and are identical,
2131 else if (compare_values (vr0->min, vr0->max) == 0
2132 && compare_values (vr1->min, vr1->max) == 0
2133 && compare_values (vr0->min, vr1->min) == 0
2134 && compare_values (vr0->max, vr1->max) == 0)
2135 return boolean_false_node;
2137 /* Otherwise, they may or may not be different. */
2141 else if (comp == LT_EXPR || comp == LE_EXPR)
2145 /* If VR0 is to the left of VR1, return true. */
2146 tst = compare_values (vr0->max, vr1->min);
2147 if ((comp == LT_EXPR && tst == -1)
2148 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
2149 return boolean_true_node;
2151 /* If VR0 is to the right of VR1, return false. */
2152 tst = compare_values (vr0->min, vr1->max);
2153 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
2154 || (comp == LE_EXPR && tst == 1))
2155 return boolean_false_node;
2157 /* Otherwise, we don't know. */
2165 /* Given a value range VR, a value VAL and a comparison code COMP, return
2166 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
2167 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
2168 always returns false. Return NULL_TREE if it is not always
2169 possible to determine the value of the comparison. */
2172 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val)
2174 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
2177 /* Anti-ranges need to be handled separately. */
2178 if (vr->type == VR_ANTI_RANGE)
2180 /* For anti-ranges, the only predicates that we can compute at
2181 compile time are equality and inequality. */
2188 /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
2189 if (value_inside_range (val, vr) == 1)
2190 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
2195 if (comp == EQ_EXPR)
2197 /* EQ_EXPR may only be computed if VR represents exactly
2199 if (compare_values (vr->min, vr->max) == 0)
2201 int cmp = compare_values (vr->min, val);
2203 return boolean_true_node;
2204 else if (cmp == -1 || cmp == 1 || cmp == 2)
2205 return boolean_false_node;
2207 else if (compare_values (val, vr->min) == -1
2208 || compare_values (vr->max, val) == -1)
2209 return boolean_false_node;
2213 else if (comp == NE_EXPR)
2215 /* If VAL is not inside VR, then they are always different. */
2216 if (compare_values (vr->max, val) == -1
2217 || compare_values (vr->min, val) == 1)
2218 return boolean_true_node;
2220 /* If VR represents exactly one value equal to VAL, then return
2222 if (compare_values (vr->min, vr->max) == 0
2223 && compare_values (vr->min, val) == 0)
2224 return boolean_false_node;
2226 /* Otherwise, they may or may not be different. */
2229 else if (comp == LT_EXPR || comp == LE_EXPR)
2233 /* If VR is to the left of VAL, return true. */
2234 tst = compare_values (vr->max, val);
2235 if ((comp == LT_EXPR && tst == -1)
2236 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
2237 return boolean_true_node;
2239 /* If VR is to the right of VAL, return false. */
2240 tst = compare_values (vr->min, val);
2241 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
2242 || (comp == LE_EXPR && tst == 1))
2243 return boolean_false_node;
2245 /* Otherwise, we don't know. */
2248 else if (comp == GT_EXPR || comp == GE_EXPR)
2252 /* If VR is to the right of VAL, return true. */
2253 tst = compare_values (vr->min, val);
2254 if ((comp == GT_EXPR && tst == 1)
2255 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
2256 return boolean_true_node;
2258 /* If VR is to the left of VAL, return false. */
2259 tst = compare_values (vr->max, val);
2260 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
2261 || (comp == GE_EXPR && tst == -1))
2262 return boolean_false_node;
2264 /* Otherwise, we don't know. */
2272 /* Debugging dumps. */
2274 void dump_value_range (FILE *, value_range_t *);
2275 void debug_value_range (value_range_t *);
2276 void dump_all_value_ranges (FILE *);
2277 void debug_all_value_ranges (void);
2278 void dump_vr_equiv (FILE *, bitmap);
2279 void debug_vr_equiv (bitmap);
2282 /* Dump value range VR to FILE. */
2285 dump_value_range (FILE *file, value_range_t *vr)
2288 fprintf (file, "[]");
2289 else if (vr->type == VR_UNDEFINED)
2290 fprintf (file, "UNDEFINED");
2291 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
2293 tree type = TREE_TYPE (vr->min);
2295 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
2297 if (INTEGRAL_TYPE_P (type)
2298 && !TYPE_UNSIGNED (type)
2299 && vr->min == TYPE_MIN_VALUE (type))
2300 fprintf (file, "-INF");
2302 print_generic_expr (file, vr->min, 0);
2304 fprintf (file, ", ");
2306 if (INTEGRAL_TYPE_P (type)
2307 && vr->max == TYPE_MAX_VALUE (type))
2308 fprintf (file, "+INF");
2310 print_generic_expr (file, vr->max, 0);
2312 fprintf (file, "]");
2319 fprintf (file, " EQUIVALENCES: { ");
2321 EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
2323 print_generic_expr (file, ssa_name (i), 0);
2324 fprintf (file, " ");
2328 fprintf (file, "} (%u elements)", c);
2331 else if (vr->type == VR_VARYING)
2332 fprintf (file, "VARYING");
2334 fprintf (file, "INVALID RANGE");
2338 /* Dump value range VR to stderr. */
2341 debug_value_range (value_range_t *vr)
2343 dump_value_range (stderr, vr);
2347 /* Dump value ranges of all SSA_NAMEs to FILE. */
2350 dump_all_value_ranges (FILE *file)
2354 for (i = 0; i < num_ssa_names; i++)
2358 print_generic_expr (file, ssa_name (i), 0);
2359 fprintf (file, ": ");
2360 dump_value_range (file, vr_value[i]);
2361 fprintf (file, "\n");
2365 fprintf (file, "\n");
2369 /* Dump all value ranges to stderr. */
2372 debug_all_value_ranges (void)
2374 dump_all_value_ranges (stderr);
2378 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
2379 create a new SSA name N and return the assertion assignment
2380 'V = ASSERT_EXPR <V, V OP W>'. */
2383 build_assert_expr_for (tree cond, tree v)
2387 gcc_assert (TREE_CODE (v) == SSA_NAME);
2388 n = duplicate_ssa_name (v, NULL_TREE);
2390 if (COMPARISON_CLASS_P (cond))
2392 tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
2393 assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, a);
2395 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2397 /* Given !V, build the assignment N = false. */
2398 tree op0 = TREE_OPERAND (cond, 0);
2399 gcc_assert (op0 == v);
2400 assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
2402 else if (TREE_CODE (cond) == SSA_NAME)
2404 /* Given V, build the assignment N = true. */
2405 gcc_assert (v == cond);
2406 assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
2411 SSA_NAME_DEF_STMT (n) = assertion;
2413 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
2414 operand of the ASSERT_EXPR. Register the new name and the old one
2415 in the replacement table so that we can fix the SSA web after
2416 adding all the ASSERT_EXPRs. */
2417 register_new_name_mapping (n, v);
2423 /* Return false if EXPR is a predicate expression involving floating
2427 fp_predicate (tree expr)
2429 return (COMPARISON_CLASS_P (expr)
2430 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
2434 /* If the range of values taken by OP can be inferred after STMT executes,
2435 return the comparison code (COMP_CODE_P) and value (VAL_P) that
2436 describes the inferred range. Return true if a range could be
2440 infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
2443 *comp_code_p = ERROR_MARK;
2445 /* Do not attempt to infer anything in names that flow through
2447 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
2450 /* Similarly, don't infer anything from statements that may throw
2452 if (tree_could_throw_p (stmt))
2455 /* If STMT is the last statement of a basic block with no
2456 successors, there is no point inferring anything about any of its
2457 operands. We would not be able to find a proper insertion point
2458 for the assertion, anyway. */
2459 if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
2462 /* We can only assume that a pointer dereference will yield
2463 non-NULL if -fdelete-null-pointer-checks is enabled. */
2464 if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op)))
2467 unsigned num_uses, num_derefs;
2469 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
2472 *val_p = build_int_cst (TREE_TYPE (op), 0);
2473 *comp_code_p = NE_EXPR;
2482 void dump_asserts_for (FILE *, tree);
2483 void debug_asserts_for (tree);
2484 void dump_all_asserts (FILE *);
2485 void debug_all_asserts (void);
2487 /* Dump all the registered assertions for NAME to FILE. */
2490 dump_asserts_for (FILE *file, tree name)
2494 fprintf (file, "Assertions to be inserted for ");
2495 print_generic_expr (file, name, 0);
2496 fprintf (file, "\n");
2498 loc = asserts_for[SSA_NAME_VERSION (name)];
2501 fprintf (file, "\t");
2502 print_generic_expr (file, bsi_stmt (loc->si), 0);
2503 fprintf (file, "\n\tBB #%d", loc->bb->index);
2506 fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
2507 loc->e->dest->index);
2508 dump_edge_info (file, loc->e, 0);
2510 fprintf (file, "\n\tPREDICATE: ");
2511 print_generic_expr (file, name, 0);
2512 fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
2513 print_generic_expr (file, loc->val, 0);
2514 fprintf (file, "\n\n");
2518 fprintf (file, "\n");
2522 /* Dump all the registered assertions for NAME to stderr. */
2525 debug_asserts_for (tree name)
2527 dump_asserts_for (stderr, name);
2531 /* Dump all the registered assertions for all the names to FILE. */
2534 dump_all_asserts (FILE *file)
2539 fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
2540 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2541 dump_asserts_for (file, ssa_name (i));
2542 fprintf (file, "\n");
2546 /* Dump all the registered assertions for all the names to stderr. */
2549 debug_all_asserts (void)
2551 dump_all_asserts (stderr);
2555 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
2556 'NAME COMP_CODE VAL' at a location that dominates block BB or
2557 E->DEST, then register this location as a possible insertion point
2558 for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
2560 BB, E and SI provide the exact insertion point for the new
2561 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
2562 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
2563 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
2564 must not be NULL. */
2567 register_new_assert_for (tree name,
2568 enum tree_code comp_code,
2572 block_stmt_iterator si)
2574 assert_locus_t n, loc, last_loc;
2576 basic_block dest_bb;
2578 #if defined ENABLE_CHECKING
2579 gcc_assert (bb == NULL || e == NULL);
2582 gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
2583 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
2586 /* The new assertion A will be inserted at BB or E. We need to
2587 determine if the new location is dominated by a previously
2588 registered location for A. If we are doing an edge insertion,
2589 assume that A will be inserted at E->DEST. Note that this is not
2592 If E is a critical edge, it will be split. But even if E is
2593 split, the new block will dominate the same set of blocks that
2596 The reverse, however, is not true, blocks dominated by E->DEST
2597 will not be dominated by the new block created to split E. So,
2598 if the insertion location is on a critical edge, we will not use
2599 the new location to move another assertion previously registered
2600 at a block dominated by E->DEST. */
2601 dest_bb = (bb) ? bb : e->dest;
2603 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
2604 VAL at a block dominating DEST_BB, then we don't need to insert a new
2605 one. Similarly, if the same assertion already exists at a block
2606 dominated by DEST_BB and the new location is not on a critical
2607 edge, then update the existing location for the assertion (i.e.,
2608 move the assertion up in the dominance tree).
2610 Note, this is implemented as a simple linked list because there
2611 should not be more than a handful of assertions registered per
2612 name. If this becomes a performance problem, a table hashed by
2613 COMP_CODE and VAL could be implemented. */
2614 loc = asserts_for[SSA_NAME_VERSION (name)];
2619 if (loc->comp_code == comp_code
2621 || operand_equal_p (loc->val, val, 0)))
2623 /* If the assertion NAME COMP_CODE VAL has already been
2624 registered at a basic block that dominates DEST_BB, then
2625 we don't need to insert the same assertion again. Note
2626 that we don't check strict dominance here to avoid
2627 replicating the same assertion inside the same basic
2628 block more than once (e.g., when a pointer is
2629 dereferenced several times inside a block).
2631 An exception to this rule are edge insertions. If the
2632 new assertion is to be inserted on edge E, then it will
2633 dominate all the other insertions that we may want to
2634 insert in DEST_BB. So, if we are doing an edge
2635 insertion, don't do this dominance check. */
2637 && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
2640 /* Otherwise, if E is not a critical edge and DEST_BB
2641 dominates the existing location for the assertion, move
2642 the assertion up in the dominance tree by updating its
2643 location information. */
2644 if ((e == NULL || !EDGE_CRITICAL_P (e))
2645 && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
2654 /* Update the last node of the list and move to the next one. */
2659 /* If we didn't find an assertion already registered for
2660 NAME COMP_CODE VAL, add a new one at the end of the list of
2661 assertions associated with NAME. */
2662 n = XNEW (struct assert_locus_d);
2666 n->comp_code = comp_code;
2673 asserts_for[SSA_NAME_VERSION (name)] = n;
2675 bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
2679 /* Try to register an edge assertion for SSA name NAME on edge E for
2680 the conditional jump pointed to by SI. Return true if an assertion
2681 for NAME could be registered. */
2684 register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
2687 enum tree_code comp_code;
2689 stmt = bsi_stmt (si);
2691 /* Do not attempt to infer anything in names that flow through
2693 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
2696 /* If NAME was not found in the sub-graph reachable from E, then
2697 there's nothing to do. */
2698 if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
2701 /* We found a use of NAME in the sub-graph rooted at E->DEST.
2702 Register an assertion for NAME according to the value that NAME
2704 if (TREE_CODE (stmt) == COND_EXPR)
2706 /* If BB ends in a COND_EXPR then NAME then we should insert
2707 the original predicate on EDGE_TRUE_VALUE and the
2708 opposite predicate on EDGE_FALSE_VALUE. */
2709 tree cond = COND_EXPR_COND (stmt);
2710 bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
2712 /* Predicates may be a single SSA name or NAME OP VAL. */
2715 /* If the predicate is a name, it must be NAME, in which
2716 case we create the predicate NAME == true or
2717 NAME == false accordingly. */
2718 comp_code = EQ_EXPR;
2719 val = (is_else_edge) ? boolean_false_node : boolean_true_node;
2723 /* Otherwise, we have a comparison of the form NAME COMP VAL
2724 or VAL COMP NAME. */
2725 if (name == TREE_OPERAND (cond, 1))
2727 /* If the predicate is of the form VAL COMP NAME, flip
2728 COMP around because we need to register NAME as the
2729 first operand in the predicate. */
2730 comp_code = swap_tree_comparison (TREE_CODE (cond));
2731 val = TREE_OPERAND (cond, 0);
2735 /* The comparison is of the form NAME COMP VAL, so the
2736 comparison code remains unchanged. */
2737 comp_code = TREE_CODE (cond);
2738 val = TREE_OPERAND (cond, 1);
2741 /* If we are inserting the assertion on the ELSE edge, we
2742 need to invert the sign comparison. */
2744 comp_code = invert_tree_comparison (comp_code, 0);
2746 /* Do not register always-false predicates. FIXME, this
2747 works around a limitation in fold() when dealing with
2748 enumerations. Given 'enum { N1, N2 } x;', fold will not
2749 fold 'if (x > N2)' to 'if (0)'. */
2750 if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
2751 && (INTEGRAL_TYPE_P (TREE_TYPE (val))
2752 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val))))
2754 tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
2755 tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
2757 if (comp_code == GT_EXPR && compare_values (val, max) == 0)
2760 if (comp_code == LT_EXPR && compare_values (val, min) == 0)
2767 /* FIXME. Handle SWITCH_EXPR. */
2771 register_new_assert_for (name, comp_code, val, NULL, e, si);
2776 static bool find_assert_locations (basic_block bb);
2778 /* Determine whether the outgoing edges of BB should receive an
2779 ASSERT_EXPR for each of the operands of BB's last statement. The
2780 last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
2782 If any of the sub-graphs rooted at BB have an interesting use of
2783 the predicate operands, an assert location node is added to the
2784 list of assertions for the corresponding operands. */
2787 find_conditional_asserts (basic_block bb)
2790 block_stmt_iterator last_si;
2796 need_assert = false;
2797 last_si = bsi_last (bb);
2798 last = bsi_stmt (last_si);
2800 /* Look for uses of the operands in each of the sub-graphs
2801 rooted at BB. We need to check each of the outgoing edges
2802 separately, so that we know what kind of ASSERT_EXPR to
2804 FOR_EACH_EDGE (e, ei, bb->succs)
2809 /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
2810 Otherwise, when we finish traversing each of the sub-graphs, we
2811 won't know whether the variables were found in the sub-graphs or
2812 if they had been found in a block upstream from BB.
2814 This is actually a bad idea is some cases, particularly jump
2815 threading. Consider a CFG like the following:
2825 Assume that one or more operands in the conditional at the
2826 end of block 0 are used in a conditional in block 2, but not
2827 anywhere in block 1. In this case we will not insert any
2828 assert statements in block 1, which may cause us to miss
2829 opportunities to optimize, particularly for jump threading. */
2830 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2831 RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2833 /* Traverse the strictly dominated sub-graph rooted at E->DEST
2834 to determine if any of the operands in the conditional
2835 predicate are used. */
2837 need_assert |= find_assert_locations (e->dest);
2839 /* Register the necessary assertions for each operand in the
2840 conditional predicate. */
2841 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2842 need_assert |= register_edge_assert_for (op, e, last_si);
2845 /* Finally, indicate that we have found the operands in the
2847 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2848 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2854 /* Traverse all the statements in block BB looking for statements that
2855 may generate useful assertions for the SSA names in their operand.
2856 If a statement produces a useful assertion A for name N_i, then the
2857 list of assertions already generated for N_i is scanned to
2858 determine if A is actually needed.
2860 If N_i already had the assertion A at a location dominating the
2861 current location, then nothing needs to be done. Otherwise, the
2862 new location for A is recorded instead.
2864 1- For every statement S in BB, all the variables used by S are
2865 added to bitmap FOUND_IN_SUBGRAPH.
2867 2- If statement S uses an operand N in a way that exposes a known
2868 value range for N, then if N was not already generated by an
2869 ASSERT_EXPR, create a new assert location for N. For instance,
2870 if N is a pointer and the statement dereferences it, we can
2871 assume that N is not NULL.
2873 3- COND_EXPRs are a special case of #2. We can derive range
2874 information from the predicate but need to insert different
2875 ASSERT_EXPRs for each of the sub-graphs rooted at the
2876 conditional block. If the last statement of BB is a conditional
2877 expression of the form 'X op Y', then
2879 a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
2881 b) If the conditional is the only entry point to the sub-graph
2882 corresponding to the THEN_CLAUSE, recurse into it. On
2883 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
2884 an ASSERT_EXPR is added for the corresponding variable.
2886 c) Repeat step (b) on the ELSE_CLAUSE.
2888 d) Mark X and Y in FOUND_IN_SUBGRAPH.
2897 In this case, an assertion on the THEN clause is useful to
2898 determine that 'a' is always 9 on that edge. However, an assertion
2899 on the ELSE clause would be unnecessary.
2901 4- If BB does not end in a conditional expression, then we recurse
2902 into BB's dominator children.
2904 At the end of the recursive traversal, every SSA name will have a
2905 list of locations where ASSERT_EXPRs should be added. When a new
2906 location for name N is found, it is registered by calling
2907 register_new_assert_for. That function keeps track of all the
2908 registered assertions to prevent adding unnecessary assertions.
2909 For instance, if a pointer P_4 is dereferenced more than once in a
2910 dominator tree, only the location dominating all the dereference of
2911 P_4 will receive an ASSERT_EXPR.
2913 If this function returns true, then it means that there are names
2914 for which we need to generate ASSERT_EXPRs. Those assertions are
2915 inserted by process_assert_insertions.
2917 TODO. Handle SWITCH_EXPR. */
2920 find_assert_locations (basic_block bb)
2922 block_stmt_iterator si;
2927 if (TEST_BIT (blocks_visited, bb->index))
2930 SET_BIT (blocks_visited, bb->index);
2932 need_assert = false;
2934 /* Traverse all PHI nodes in BB marking used operands. */
2935 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2937 use_operand_p arg_p;
2940 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
2942 tree arg = USE_FROM_PTR (arg_p);
2943 if (TREE_CODE (arg) == SSA_NAME)
2945 gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
2946 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
2951 /* Traverse all the statements in BB marking used names and looking
2952 for statements that may infer assertions for their used operands. */
2954 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2959 stmt = bsi_stmt (si);
2961 /* See if we can derive an assertion for any of STMT's operands. */
2962 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
2965 enum tree_code comp_code;
2967 /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside
2968 the sub-graph of a conditional block, when we return from
2969 this recursive walk, our parent will use the
2970 FOUND_IN_SUBGRAPH bitset to determine if one of the
2971 operands it was looking for was present in the sub-graph. */
2972 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2974 /* If OP is used in such a way that we can infer a value
2975 range for it, and we don't find a previous assertion for
2976 it, create a new assertion location node for OP. */
2977 if (infer_value_range (stmt, op, &comp_code, &value))
2979 /* If we are able to infer a nonzero value range for OP,
2980 then walk backwards through the use-def chain to see if OP
2981 was set via a typecast.
2983 If so, then we can also infer a nonzero value range
2984 for the operand of the NOP_EXPR. */
2985 if (comp_code == NE_EXPR && integer_zerop (value))
2988 tree def_stmt = SSA_NAME_DEF_STMT (t);
2990 while (TREE_CODE (def_stmt) == MODIFY_EXPR
2991 && TREE_CODE (TREE_OPERAND (def_stmt, 1)) == NOP_EXPR
2992 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)) == SSA_NAME
2993 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0))))
2995 t = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
2996 def_stmt = SSA_NAME_DEF_STMT (t);
2998 /* Note we want to register the assert for the
2999 operand of the NOP_EXPR after SI, not after the
3001 if (! has_single_use (t))
3003 register_new_assert_for (t, comp_code, value,
3010 /* If OP is used only once, namely in this STMT, don't
3011 bother creating an ASSERT_EXPR for it. Such an
3012 ASSERT_EXPR would do nothing but increase compile time. */
3013 if (!has_single_use (op))
3015 register_new_assert_for (op, comp_code, value, bb, NULL, si);
3021 /* Remember the last statement of the block. */
3025 /* If BB's last statement is a conditional expression
3026 involving integer operands, recurse into each of the sub-graphs
3027 rooted at BB to determine if we need to add ASSERT_EXPRs. */
3029 && TREE_CODE (last) == COND_EXPR
3030 && !fp_predicate (COND_EXPR_COND (last))
3031 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
3032 need_assert |= find_conditional_asserts (bb);
3034 /* Recurse into the dominator children of BB. */
3035 for (son = first_dom_son (CDI_DOMINATORS, bb);
3037 son = next_dom_son (CDI_DOMINATORS, son))
3038 need_assert |= find_assert_locations (son);
3044 /* Create an ASSERT_EXPR for NAME and insert it in the location
3045 indicated by LOC. Return true if we made any edge insertions. */
3048 process_assert_insertions_for (tree name, assert_locus_t loc)
3050 /* Build the comparison expression NAME_i COMP_CODE VAL. */
3051 tree stmt, cond, assert_expr;
3055 cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
3056 assert_expr = build_assert_expr_for (cond, name);
3060 /* We have been asked to insert the assertion on an edge. This
3061 is used only by COND_EXPR and SWITCH_EXPR assertions. */
3062 #if defined ENABLE_CHECKING
3063 gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
3064 || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
3067 bsi_insert_on_edge (loc->e, assert_expr);
3071 /* Otherwise, we can insert right after LOC->SI iff the
3072 statement must not be the last statement in the block. */
3073 stmt = bsi_stmt (loc->si);
3074 if (!stmt_ends_bb_p (stmt))
3076 bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
3080 /* If STMT must be the last statement in BB, we can only insert new
3081 assertions on the non-abnormal edge out of BB. Note that since
3082 STMT is not control flow, there may only be one non-abnormal edge
3084 FOR_EACH_EDGE (e, ei, loc->bb->succs)
3085 if (!(e->flags & EDGE_ABNORMAL))
3087 bsi_insert_on_edge (e, assert_expr);
3095 /* Process all the insertions registered for every name N_i registered
3096 in NEED_ASSERT_FOR. The list of assertions to be inserted are
3097 found in ASSERTS_FOR[i]. */
3100 process_assert_insertions (void)
3104 bool update_edges_p = false;
3105 int num_asserts = 0;
3107 if (dump_file && (dump_flags & TDF_DETAILS))
3108 dump_all_asserts (dump_file);
3110 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
3112 assert_locus_t loc = asserts_for[i];
3117 assert_locus_t next = loc->next;
3118 update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
3126 bsi_commit_edge_inserts ();
3128 if (dump_file && (dump_flags & TDF_STATS))
3129 fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
3134 /* Traverse the flowgraph looking for conditional jumps to insert range
3135 expressions. These range expressions are meant to provide information
3136 to optimizations that need to reason in terms of value ranges. They
3137 will not be expanded into RTL. For instance, given:
3146 this pass will transform the code into:
3152 x = ASSERT_EXPR <x, x < y>
3157 y = ASSERT_EXPR <y, x <= y>
3161 The idea is that once copy and constant propagation have run, other
3162 optimizations will be able to determine what ranges of values can 'x'
3163 take in different paths of the code, simply by checking the reaching
3164 definition of 'x'. */
3167 insert_range_assertions (void)
3173 found_in_subgraph = sbitmap_alloc (num_ssa_names);
3174 sbitmap_zero (found_in_subgraph);
3176 blocks_visited = sbitmap_alloc (last_basic_block);
3177 sbitmap_zero (blocks_visited);
3179 need_assert_for = BITMAP_ALLOC (NULL);
3180 asserts_for = XNEWVEC (assert_locus_t, num_ssa_names);
3181 memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t));
3183 calculate_dominance_info (CDI_DOMINATORS);
3185 update_ssa_p = false;
3186 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
3187 if (find_assert_locations (e->dest))
3188 update_ssa_p = true;
3192 process_assert_insertions ();
3193 update_ssa (TODO_update_ssa_no_phi);
3196 if (dump_file && (dump_flags & TDF_DETAILS))
3198 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
3199 dump_function_to_file (current_function_decl, dump_file, dump_flags);
3202 sbitmap_free (found_in_subgraph);
3204 BITMAP_FREE (need_assert_for);
3208 /* Convert range assertion expressions into the implied copies and
3209 copy propagate away the copies. Doing the trivial copy propagation
3210 here avoids the need to run the full copy propagation pass after
3213 FIXME, this will eventually lead to copy propagation removing the
3214 names that had useful range information attached to them. For
3215 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
3216 then N_i will have the range [3, +INF].
3218 However, by converting the assertion into the implied copy
3219 operation N_i = N_j, we will then copy-propagate N_j into the uses
3220 of N_i and lose the range information. We may want to hold on to
3221 ASSERT_EXPRs a little while longer as the ranges could be used in
3222 things like jump threading.
3224 The problem with keeping ASSERT_EXPRs around is that passes after
3225 VRP need to handle them appropriately.
3227 Another approach would be to make the range information a first
3228 class property of the SSA_NAME so that it can be queried from
3229 any pass. This is made somewhat more complex by the need for
3230 multiple ranges to be associated with one SSA_NAME. */
3233 remove_range_assertions (void)
3236 block_stmt_iterator si;
3238 /* Note that the BSI iterator bump happens at the bottom of the
3239 loop and no bump is necessary if we're removing the statement
3240 referenced by the current BSI. */
3242 for (si = bsi_start (bb); !bsi_end_p (si);)
3244 tree stmt = bsi_stmt (si);
3246 if (TREE_CODE (stmt) == MODIFY_EXPR
3247 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
3249 tree rhs = TREE_OPERAND (stmt, 1), var;
3250 tree cond = fold (ASSERT_EXPR_COND (rhs));
3251 use_operand_p use_p;
3252 imm_use_iterator iter;
3254 gcc_assert (cond != boolean_false_node);
3256 /* Propagate the RHS into every use of the LHS. */
3257 var = ASSERT_EXPR_VAR (rhs);
3258 FOR_EACH_IMM_USE_SAFE (use_p, iter, TREE_OPERAND (stmt, 0))
3260 SET_USE (use_p, var);
3261 gcc_assert (TREE_CODE (var) == SSA_NAME);
3264 /* And finally, remove the copy, it is not needed. */
3265 bsi_remove (&si, true);
3271 sbitmap_free (blocks_visited);
3275 /* Return true if STMT is interesting for VRP. */
3278 stmt_interesting_for_vrp (tree stmt)
3280 if (TREE_CODE (stmt) == PHI_NODE
3281 && is_gimple_reg (PHI_RESULT (stmt))
3282 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
3283 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
3285 else if (TREE_CODE (stmt) == MODIFY_EXPR)
3287 tree lhs = TREE_OPERAND (stmt, 0);
3288 tree rhs = TREE_OPERAND (stmt, 1);
3290 /* In general, assignments with virtual operands are not useful
3291 for deriving ranges, with the obvious exception of calls to
3292 builtin functions. */
3293 if (TREE_CODE (lhs) == SSA_NAME
3294 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
3295 || POINTER_TYPE_P (TREE_TYPE (lhs)))
3296 && ((TREE_CODE (rhs) == CALL_EXPR
3297 && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
3298 && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
3299 && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
3300 || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)))
3303 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3310 /* Initialize local data structures for VRP. */
3313 vrp_initialize (void)
3317 vr_value = XNEWVEC (value_range_t *, num_ssa_names);
3318 memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *));
3322 block_stmt_iterator si;
3325 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3327 if (!stmt_interesting_for_vrp (phi))
3329 tree lhs = PHI_RESULT (phi);
3330 set_value_range_to_varying (get_value_range (lhs));
3331 DONT_SIMULATE_AGAIN (phi) = true;
3334 DONT_SIMULATE_AGAIN (phi) = false;
3337 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
3339 tree stmt = bsi_stmt (si);
3341 if (!stmt_interesting_for_vrp (stmt))
3345 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
3346 set_value_range_to_varying (get_value_range (def));
3347 DONT_SIMULATE_AGAIN (stmt) = true;
3351 DONT_SIMULATE_AGAIN (stmt) = false;
3358 /* Visit assignment STMT. If it produces an interesting range, record
3359 the SSA name in *OUTPUT_P. */
3361 static enum ssa_prop_result
3362 vrp_visit_assignment (tree stmt, tree *output_p)
3367 lhs = TREE_OPERAND (stmt, 0);
3368 rhs = TREE_OPERAND (stmt, 1);
3370 /* We only keep track of ranges in integral and pointer types. */
3371 if (TREE_CODE (lhs) == SSA_NAME
3372 && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
3373 /* It is valid to have NULL MIN/MAX values on a type. See
3374 build_range_type. */
3375 && TYPE_MIN_VALUE (TREE_TYPE (lhs))
3376 && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
3377 || POINTER_TYPE_P (TREE_TYPE (lhs))))
3380 value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3382 extract_range_from_expr (&new_vr, rhs);
3384 /* If STMT is inside a loop, we may be able to know something
3385 else about the range of LHS by examining scalar evolution
3387 if (current_loops && (l = loop_containing_stmt (stmt)))
3388 adjust_range_with_scev (&new_vr, l, stmt, lhs);
3390 if (update_value_range (lhs, &new_vr))
3394 if (dump_file && (dump_flags & TDF_DETAILS))
3396 fprintf (dump_file, "Found new range for ");
3397 print_generic_expr (dump_file, lhs, 0);
3398 fprintf (dump_file, ": ");
3399 dump_value_range (dump_file, &new_vr);
3400 fprintf (dump_file, "\n\n");
3403 if (new_vr.type == VR_VARYING)
3404 return SSA_PROP_VARYING;
3406 return SSA_PROP_INTERESTING;
3409 return SSA_PROP_NOT_INTERESTING;
3412 /* Every other statement produces no useful ranges. */
3413 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3414 set_value_range_to_varying (get_value_range (def));
3416 return SSA_PROP_VARYING;
3420 /* Compare all the value ranges for names equivalent to VAR with VAL
3421 using comparison code COMP. Return the same value returned by
3422 compare_range_with_value. */
3425 compare_name_with_value (enum tree_code comp, tree var, tree val)
3432 t = retval = NULL_TREE;
3434 /* Get the set of equivalences for VAR. */
3435 e = get_value_range (var)->equiv;
3437 /* Add VAR to its own set of equivalences so that VAR's value range
3438 is processed by this loop (otherwise, we would have to replicate
3439 the body of the loop just to check VAR's value range). */
3440 bitmap_set_bit (e, SSA_NAME_VERSION (var));
3442 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
3444 value_range_t equiv_vr = *(vr_value[i]);
3446 /* If name N_i does not have a valid range, use N_i as its own
3447 range. This allows us to compare against names that may
3448 have N_i in their ranges. */
3449 if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
3451 equiv_vr.type = VR_RANGE;
3452 equiv_vr.min = ssa_name (i);
3453 equiv_vr.max = ssa_name (i);
3456 t = compare_range_with_value (comp, &equiv_vr, val);
3459 /* All the ranges should compare the same against VAL. */
3460 gcc_assert (retval == NULL || t == retval);
3465 /* Remove VAR from its own equivalence set. */
3466 bitmap_clear_bit (e, SSA_NAME_VERSION (var));
3471 /* We couldn't find a non-NULL value for the predicate. */
3476 /* Given a comparison code COMP and names N1 and N2, compare all the
3477 ranges equivalent to N1 against all the ranges equivalent to N2
3478 to determine the value of N1 COMP N2. Return the same value
3479 returned by compare_ranges. */
3482 compare_names (enum tree_code comp, tree n1, tree n2)
3486 bitmap_iterator bi1, bi2;
3489 /* Compare the ranges of every name equivalent to N1 against the
3490 ranges of every name equivalent to N2. */
3491 e1 = get_value_range (n1)->equiv;
3492 e2 = get_value_range (n2)->equiv;
3494 /* Add N1 and N2 to their own set of equivalences to avoid
3495 duplicating the body of the loop just to check N1 and N2
3497 bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
3498 bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
3500 /* If the equivalence sets have a common intersection, then the two
3501 names can be compared without checking their ranges. */
3502 if (bitmap_intersect_p (e1, e2))
3504 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3505 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3507 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
3509 : boolean_false_node;
3512 /* Otherwise, compare all the equivalent ranges. First, add N1 and
3513 N2 to their own set of equivalences to avoid duplicating the body
3514 of the loop just to check N1 and N2 ranges. */
3515 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
3517 value_range_t vr1 = *(vr_value[i1]);
3519 /* If the range is VARYING or UNDEFINED, use the name itself. */
3520 if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
3522 vr1.type = VR_RANGE;
3523 vr1.min = ssa_name (i1);
3524 vr1.max = ssa_name (i1);
3527 t = retval = NULL_TREE;
3528 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
3530 value_range_t vr2 = *(vr_value[i2]);
3532 if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
3534 vr2.type = VR_RANGE;
3535 vr2.min = ssa_name (i2);
3536 vr2.max = ssa_name (i2);
3539 t = compare_ranges (comp, &vr1, &vr2);
3542 /* All the ranges in the equivalent sets should compare
3544 gcc_assert (retval == NULL || t == retval);
3551 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3552 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3557 /* None of the equivalent ranges are useful in computing this
3559 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3560 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3565 /* Given a conditional predicate COND, try to determine if COND yields
3566 true or false based on the value ranges of its operands. Return
3567 BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
3568 BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
3569 NULL if the conditional cannot be evaluated at compile time.
3571 If USE_EQUIV_P is true, the ranges of all the names equivalent with
3572 the operands in COND are used when trying to compute its value.
3573 This is only used during final substitution. During propagation,
3574 we only check the range of each variable and not its equivalents. */
3577 vrp_evaluate_conditional (tree cond, bool use_equiv_p)
3579 gcc_assert (TREE_CODE (cond) == SSA_NAME
3580 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
3582 if (TREE_CODE (cond) == SSA_NAME)
3588 retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node);
3591 value_range_t *vr = get_value_range (cond);
3592 retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node);
3595 /* If COND has a known boolean range, return it. */
3599 /* Otherwise, if COND has a symbolic range of exactly one value,
3601 vr = get_value_range (cond);
3602 if (vr->type == VR_RANGE && vr->min == vr->max)
3607 tree op0 = TREE_OPERAND (cond, 0);
3608 tree op1 = TREE_OPERAND (cond, 1);
3610 /* We only deal with integral and pointer types. */
3611 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3612 && !POINTER_TYPE_P (TREE_TYPE (op0)))
3617 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
3618 return compare_names (TREE_CODE (cond), op0, op1);
3619 else if (TREE_CODE (op0) == SSA_NAME)
3620 return compare_name_with_value (TREE_CODE (cond), op0, op1);
3621 else if (TREE_CODE (op1) == SSA_NAME)
3622 return compare_name_with_value (
3623 swap_tree_comparison (TREE_CODE (cond)), op1, op0);
3627 value_range_t *vr0, *vr1;
3629 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
3630 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
3633 return compare_ranges (TREE_CODE (cond), vr0, vr1);
3634 else if (vr0 && vr1 == NULL)
3635 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
3636 else if (vr0 == NULL && vr1)
3637 return compare_range_with_value (
3638 swap_tree_comparison (TREE_CODE (cond)), vr1, op0);
3642 /* Anything else cannot be computed statically. */
3647 /* Visit conditional statement STMT. If we can determine which edge
3648 will be taken out of STMT's basic block, record it in
3649 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
3650 SSA_PROP_VARYING. */
3652 static enum ssa_prop_result
3653 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
3657 *taken_edge_p = NULL;
3659 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
3660 add ASSERT_EXPRs for them. */
3661 if (TREE_CODE (stmt) == SWITCH_EXPR)
3662 return SSA_PROP_VARYING;
3664 cond = COND_EXPR_COND (stmt);
3666 if (dump_file && (dump_flags & TDF_DETAILS))
3671 fprintf (dump_file, "\nVisiting conditional with predicate: ");
3672 print_generic_expr (dump_file, cond, 0);
3673 fprintf (dump_file, "\nWith known ranges\n");
3675 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
3677 fprintf (dump_file, "\t");
3678 print_generic_expr (dump_file, use, 0);
3679 fprintf (dump_file, ": ");
3680 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
3683 fprintf (dump_file, "\n");
3686 /* Compute the value of the predicate COND by checking the known
3687 ranges of each of its operands.
3689 Note that we cannot evaluate all the equivalent ranges here
3690 because those ranges may not yet be final and with the current
3691 propagation strategy, we cannot determine when the value ranges
3692 of the names in the equivalence set have changed.
3694 For instance, given the following code fragment
3698 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
3702 Assume that on the first visit to i_14, i_5 has the temporary
3703 range [8, 8] because the second argument to the PHI function is
3704 not yet executable. We derive the range ~[0, 0] for i_14 and the
3705 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
3706 the first time, since i_14 is equivalent to the range [8, 8], we
3707 determine that the predicate is always false.
3709 On the next round of propagation, i_13 is determined to be
3710 VARYING, which causes i_5 to drop down to VARYING. So, another
3711 visit to i_14 is scheduled. In this second visit, we compute the
3712 exact same range and equivalence set for i_14, namely ~[0, 0] and
3713 { i_5 }. But we did not have the previous range for i_5
3714 registered, so vrp_visit_assignment thinks that the range for
3715 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
3716 is not visited again, which stops propagation from visiting
3717 statements in the THEN clause of that if().
3719 To properly fix this we would need to keep the previous range
3720 value for the names in the equivalence set. This way we would've
3721 discovered that from one visit to the other i_5 changed from
3722 range [8, 8] to VR_VARYING.
3724 However, fixing this apparent limitation may not be worth the
3725 additional checking. Testing on several code bases (GCC, DLV,
3726 MICO, TRAMP3D and SPEC2000) showed that doing this results in
3727 4 more predicates folded in SPEC. */
3728 val = vrp_evaluate_conditional (cond, false);
3730 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
3732 if (dump_file && (dump_flags & TDF_DETAILS))
3734 fprintf (dump_file, "\nPredicate evaluates to: ");
3735 if (val == NULL_TREE)
3736 fprintf (dump_file, "DON'T KNOW\n");
3738 print_generic_stmt (dump_file, val, 0);
3741 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
3745 /* Evaluate statement STMT. If the statement produces a useful range,
3746 return SSA_PROP_INTERESTING and record the SSA name with the
3747 interesting range into *OUTPUT_P.
3749 If STMT is a conditional branch and we can determine its truth
3750 value, the taken edge is recorded in *TAKEN_EDGE_P.
3752 If STMT produces a varying value, return SSA_PROP_VARYING. */
3754 static enum ssa_prop_result
3755 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
3761 if (dump_file && (dump_flags & TDF_DETAILS))
3763 fprintf (dump_file, "\nVisiting statement:\n");
3764 print_generic_stmt (dump_file, stmt, dump_flags);
3765 fprintf (dump_file, "\n");
3768 ann = stmt_ann (stmt);
3769 if (TREE_CODE (stmt) == MODIFY_EXPR)
3771 tree rhs = TREE_OPERAND (stmt, 1);
3773 /* In general, assignments with virtual operands are not useful
3774 for deriving ranges, with the obvious exception of calls to
3775 builtin functions. */
3776 if ((TREE_CODE (rhs) == CALL_EXPR
3777 && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
3778 && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
3779 && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
3780 || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3781 return vrp_visit_assignment (stmt, output_p);
3783 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3784 return vrp_visit_cond_stmt (stmt, taken_edge_p);
3786 /* All other statements produce nothing of interest for VRP, so mark
3787 their outputs varying and prevent further simulation. */
3788 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3789 set_value_range_to_varying (get_value_range (def));
3791 return SSA_PROP_VARYING;
3795 /* Meet operation for value ranges. Given two value ranges VR0 and
3796 VR1, store in VR0 the result of meeting VR0 and VR1.
3798 The meeting rules are as follows:
3800 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
3802 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
3803 union of VR0 and VR1. */
3806 vrp_meet (value_range_t *vr0, value_range_t *vr1)
3808 if (vr0->type == VR_UNDEFINED)
3810 copy_value_range (vr0, vr1);
3814 if (vr1->type == VR_UNDEFINED)
3816 /* Nothing to do. VR0 already has the resulting range. */
3820 if (vr0->type == VR_VARYING)
3822 /* Nothing to do. VR0 already has the resulting range. */
3826 if (vr1->type == VR_VARYING)
3828 set_value_range_to_varying (vr0);
3832 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
3834 /* If VR0 and VR1 have a non-empty intersection, compute the
3835 union of both ranges. */
3836 if (value_ranges_intersect_p (vr0, vr1))
3841 /* The lower limit of the new range is the minimum of the
3842 two ranges. If they cannot be compared, the result is
3844 cmp = compare_values (vr0->min, vr1->min);
3845 if (cmp == 0 || cmp == 1)
3851 set_value_range_to_varying (vr0);
3855 /* Similarly, the upper limit of the new range is the
3856 maximum of the two ranges. If they cannot be compared,
3857 the result is VARYING. */
3858 cmp = compare_values (vr0->max, vr1->max);
3859 if (cmp == 0 || cmp == -1)
3865 set_value_range_to_varying (vr0);
3869 /* The resulting set of equivalences is the intersection of
3871 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3872 bitmap_and_into (vr0->equiv, vr1->equiv);
3873 else if (vr0->equiv && !vr1->equiv)
3874 bitmap_clear (vr0->equiv);
3876 set_value_range (vr0, vr0->type, min, max, vr0->equiv);
3881 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3883 /* Two anti-ranges meet only if they are both identical. */
3884 if (compare_values (vr0->min, vr1->min) == 0
3885 && compare_values (vr0->max, vr1->max) == 0
3886 && compare_values (vr0->min, vr0->max) == 0)
3888 /* The resulting set of equivalences is the intersection of
3890 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3891 bitmap_and_into (vr0->equiv, vr1->equiv);
3892 else if (vr0->equiv && !vr1->equiv)
3893 bitmap_clear (vr0->equiv);
3898 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
3900 /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4]
3901 meet only if the ranges have an empty intersection. The
3902 result of the meet operation is the anti-range. */
3903 if (!symbolic_range_p (vr0)
3904 && !symbolic_range_p (vr1)
3905 && !value_ranges_intersect_p (vr0, vr1))
3907 /* Copy most of VR1 into VR0. Don't copy VR1's equivalence
3908 set. We need to compute the intersection of the two
3909 equivalence sets. */
3910 if (vr1->type == VR_ANTI_RANGE)
3911 set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
3913 /* The resulting set of equivalences is the intersection of
3915 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3916 bitmap_and_into (vr0->equiv, vr1->equiv);
3917 else if (vr0->equiv && !vr1->equiv)
3918 bitmap_clear (vr0->equiv);
3929 /* The two range VR0 and VR1 do not meet. Before giving up and
3930 setting the result to VARYING, see if we can at least derive a
3931 useful anti-range. FIXME, all this nonsense about distinguishing
3932 anti-ranges from ranges is necessary because of the odd
3933 semantics of range_includes_zero_p and friends. */
3934 if (!symbolic_range_p (vr0)
3935 && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0))
3936 || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0)))
3937 && !symbolic_range_p (vr1)
3938 && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1))
3939 || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1))))
3941 set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
3943 /* Since this meet operation did not result from the meeting of
3944 two equivalent names, VR0 cannot have any equivalences. */
3946 bitmap_clear (vr0->equiv);
3949 set_value_range_to_varying (vr0);
3953 /* Visit all arguments for PHI node PHI that flow through executable
3954 edges. If a valid value range can be derived from all the incoming
3955 value ranges, set a new range for the LHS of PHI. */
3957 static enum ssa_prop_result
3958 vrp_visit_phi_node (tree phi)
3961 tree lhs = PHI_RESULT (phi);
3962 value_range_t *lhs_vr = get_value_range (lhs);
3963 value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3965 copy_value_range (&vr_result, lhs_vr);
3967 if (dump_file && (dump_flags & TDF_DETAILS))
3969 fprintf (dump_file, "\nVisiting PHI node: ");
3970 print_generic_expr (dump_file, phi, dump_flags);
3973 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
3975 edge e = PHI_ARG_EDGE (phi, i);
3977 if (dump_file && (dump_flags & TDF_DETAILS))
3980 "\n Argument #%d (%d -> %d %sexecutable)\n",
3981 i, e->src->index, e->dest->index,
3982 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
3985 if (e->flags & EDGE_EXECUTABLE)
3987 tree arg = PHI_ARG_DEF (phi, i);
3988 value_range_t vr_arg;
3990 if (TREE_CODE (arg) == SSA_NAME)
3991 vr_arg = *(get_value_range (arg));
3994 vr_arg.type = VR_RANGE;
3997 vr_arg.equiv = NULL;
4000 if (dump_file && (dump_flags & TDF_DETAILS))
4002 fprintf (dump_file, "\t");
4003 print_generic_expr (dump_file, arg, dump_flags);
4004 fprintf (dump_file, "\n\tValue: ");
4005 dump_value_range (dump_file, &vr_arg);
4006 fprintf (dump_file, "\n");
4009 vrp_meet (&vr_result, &vr_arg);
4011 if (vr_result.type == VR_VARYING)
4016 if (vr_result.type == VR_VARYING)
4019 /* To prevent infinite iterations in the algorithm, derive ranges
4020 when the new value is slightly bigger or smaller than the
4022 if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE)
4024 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
4026 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
4027 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
4029 /* If the new minimum is smaller or larger than the previous
4030 one, go all the way to -INF. In the first case, to avoid
4031 iterating millions of times to reach -INF, and in the
4032 other case to avoid infinite bouncing between different
4034 if (cmp_min > 0 || cmp_min < 0)
4035 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
4037 /* Similarly, if the new maximum is smaller or larger than
4038 the previous one, go all the way to +INF. */
4039 if (cmp_max < 0 || cmp_max > 0)
4040 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
4042 /* If we ended up with a (-INF, +INF) range, set it to
4044 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
4045 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
4050 /* If the new range is different than the previous value, keep
4052 if (update_value_range (lhs, &vr_result))
4053 return SSA_PROP_INTERESTING;
4055 /* Nothing changed, don't add outgoing edges. */
4056 return SSA_PROP_NOT_INTERESTING;
4058 /* No match found. Set the LHS to VARYING. */
4060 set_value_range_to_varying (lhs_vr);
4061 return SSA_PROP_VARYING;
4064 /* Simplify a division or modulo operator to a right shift or
4065 bitwise and if the first operand is unsigned or is greater
4066 than zero and the second operand is an exact power of two. */
4069 simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code)
4072 tree op = TREE_OPERAND (rhs, 0);
4073 value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
4075 if (TYPE_UNSIGNED (TREE_TYPE (op)))
4077 val = integer_one_node;
4081 val = compare_range_with_value (GT_EXPR, vr, integer_zero_node);
4084 if (val && integer_onep (val))
4087 tree op0 = TREE_OPERAND (rhs, 0);
4088 tree op1 = TREE_OPERAND (rhs, 1);
4090 if (rhs_code == TRUNC_DIV_EXPR)
4092 t = build_int_cst (NULL_TREE, tree_log2 (op1));
4093 t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
4097 t = build_int_cst (TREE_TYPE (op1), 1);
4098 t = int_const_binop (MINUS_EXPR, op1, t, 0);
4099 t = fold_convert (TREE_TYPE (op0), t);
4100 t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
4103 TREE_OPERAND (stmt, 1) = t;
4108 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
4109 ABS_EXPR. If the operand is <= 0, then simplify the
4110 ABS_EXPR into a NEGATE_EXPR. */
4113 simplify_abs_using_ranges (tree stmt, tree rhs)
4116 tree op = TREE_OPERAND (rhs, 0);
4117 tree type = TREE_TYPE (op);
4118 value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
4120 if (TYPE_UNSIGNED (type))
4122 val = integer_zero_node;
4126 val = compare_range_with_value (LE_EXPR, vr, integer_zero_node);
4129 val = compare_range_with_value (GE_EXPR, vr, integer_zero_node);
4133 if (integer_zerop (val))
4134 val = integer_one_node;
4135 else if (integer_onep (val))
4136 val = integer_zero_node;
4141 && (integer_onep (val) || integer_zerop (val)))
4145 if (integer_onep (val))
4146 t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
4150 TREE_OPERAND (stmt, 1) = t;
4156 /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
4157 a known value range VR.
4159 If there is one and only one value which will satisfy the
4160 conditional, then return that value. Else return NULL. */
4163 test_for_singularity (enum tree_code cond_code, tree op0,
4164 tree op1, value_range_t *vr)
4169 /* Extract minimum/maximum values which satisfy the
4170 the conditional as it was written. */
4171 if (cond_code == LE_EXPR || cond_code == LT_EXPR)
4173 min = TYPE_MIN_VALUE (TREE_TYPE (op0));
4176 if (cond_code == LT_EXPR)
4178 tree one = build_int_cst (TREE_TYPE (op0), 1);
4179 max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
4182 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
4184 max = TYPE_MAX_VALUE (TREE_TYPE (op0));
4187 if (cond_code == GT_EXPR)
4189 tree one = build_int_cst (TREE_TYPE (op0), 1);
4190 min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
4194 /* Now refine the minimum and maximum values using any
4195 value range information we have for op0. */
4198 if (compare_values (vr->min, min) == -1)
4202 if (compare_values (vr->max, max) == 1)
4207 /* If the new min/max values have converged to a single value,
4208 then there is only one value which can satisfy the condition,
4209 return that value. */
4210 if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
4216 /* Simplify a conditional using a relational operator to an equality
4217 test if the range information indicates only one value can satisfy
4218 the original conditional. */
4221 simplify_cond_using_ranges (tree stmt)
4223 tree cond = COND_EXPR_COND (stmt);
4224 tree op0 = TREE_OPERAND (cond, 0);
4225 tree op1 = TREE_OPERAND (cond, 1);
4226 enum tree_code cond_code = TREE_CODE (cond);
4228 if (cond_code != NE_EXPR
4229 && cond_code != EQ_EXPR
4230 && TREE_CODE (op0) == SSA_NAME
4231 && INTEGRAL_TYPE_P (TREE_TYPE (op0))
4232 && is_gimple_min_invariant (op1))
4234 value_range_t *vr = get_value_range (op0);
4236 /* If we have range information for OP0, then we might be
4237 able to simplify this conditional. */
4238 if (vr->type == VR_RANGE)
4240 tree new = test_for_singularity (cond_code, op0, op1, vr);
4246 fprintf (dump_file, "Simplified relational ");
4247 print_generic_expr (dump_file, cond, 0);
4248 fprintf (dump_file, " into ");
4251 COND_EXPR_COND (stmt)
4252 = build2 (EQ_EXPR, boolean_type_node, op0, new);
4257 print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
4258 fprintf (dump_file, "\n");
4264 /* Try again after inverting the condition. We only deal
4265 with integral types here, so no need to worry about
4266 issues with inverting FP comparisons. */
4267 cond_code = invert_tree_comparison (cond_code, false);
4268 new = test_for_singularity (cond_code, op0, op1, vr);
4274 fprintf (dump_file, "Simplified relational ");
4275 print_generic_expr (dump_file, cond, 0);
4276 fprintf (dump_file, " into ");
4279 COND_EXPR_COND (stmt)
4280 = build2 (NE_EXPR, boolean_type_node, op0, new);
4285 print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
4286 fprintf (dump_file, "\n");
4295 /* Simplify STMT using ranges if possible. */
4298 simplify_stmt_using_ranges (tree stmt)
4300 if (TREE_CODE (stmt) == MODIFY_EXPR)
4302 tree rhs = TREE_OPERAND (stmt, 1);
4303 enum tree_code rhs_code = TREE_CODE (rhs);
4305 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4306 and BIT_AND_EXPR respectively if the first operand is greater
4307 than zero and the second operand is an exact power of two. */
4308 if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
4309 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
4310 && integer_pow2p (TREE_OPERAND (rhs, 1)))
4311 simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code);
4313 /* Transform ABS (X) into X or -X as appropriate. */
4314 if (rhs_code == ABS_EXPR
4315 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
4316 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
4317 simplify_abs_using_ranges (stmt, rhs);
4319 else if (TREE_CODE (stmt) == COND_EXPR
4320 && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
4322 simplify_cond_using_ranges (stmt);
4326 /* Stack of dest,src equivalency pairs that need to be restored after
4327 each attempt to thread a block's incoming edge to an outgoing edge.
4329 A NULL entry is used to mark the end of pairs which need to be
4331 static VEC(tree,heap) *stack;
4333 /* A trivial wrapper so that we can present the generic jump
4334 threading code with a simple API for simplifying statements. */
4336 simplify_stmt_for_jump_threading (tree stmt)
4338 /* We only use VRP information to simplify conditionals. This is
4339 overly conservative, but it's unclear if doing more would be
4340 worth the compile time cost. */
4341 if (TREE_CODE (stmt) != COND_EXPR)
4344 return vrp_evaluate_conditional (COND_EXPR_COND (stmt), true);
4347 /* Blocks which have more than one predecessor and more than
4348 one successor present jump threading opportunities. ie,
4349 when the block is reached from a specific predecessor, we
4350 may be able to determine which of the outgoing edges will
4351 be traversed. When this optimization applies, we are able
4352 to avoid conditionals at runtime and we may expose secondary
4353 optimization opportunities.
4355 This routine is effectively a driver for the generic jump
4356 threading code. It basically just presents the generic code
4357 with edges that may be suitable for jump threading.
4359 Unlike DOM, we do not iterate VRP if jump threading was successful.
4360 While iterating may expose new opportunities for VRP, it is expected
4361 those opportunities would be very limited and the compile time cost
4362 to expose those opportunities would be significant.
4364 As jump threading opportunities are discovered, they are registered
4365 for later realization. */
4368 identify_jump_threads (void)
4373 /* Ugh. When substituting values earlier in this pass we can
4374 wipe the dominance information. So rebuild the dominator
4375 information as we need it within the jump threading code. */
4376 calculate_dominance_info (CDI_DOMINATORS);
4378 /* We do not allow VRP information to be used for jump threading
4379 across a back edge in the CFG. Otherwise it becomes too
4380 difficult to avoid eliminating loop exit tests. Of course
4381 EDGE_DFS_BACK is not accurate at this time so we have to
4383 mark_dfs_back_edges ();
4385 /* Allocate our unwinder stack to unwind any temporary equivalences
4386 that might be recorded. */
4387 stack = VEC_alloc (tree, heap, 20);
4389 /* To avoid lots of silly node creation, we create a single
4390 conditional and just modify it in-place when attempting to
4392 dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL);
4393 dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL);
4395 /* Walk through all the blocks finding those which present a
4396 potential jump threading opportunity. We could set this up
4397 as a dominator walker and record data during the walk, but
4398 I doubt it's worth the effort for the classes of jump
4399 threading opportunities we are trying to identify at this
4400 point in compilation. */
4405 /* If the generic jump threading code does not find this block
4406 interesting, then there is nothing to do. */
4407 if (! potentially_threadable_block (bb))
4410 /* We only care about blocks ending in a COND_EXPR. While there
4411 may be some value in handling SWITCH_EXPR here, I doubt it's
4412 terribly important. */
4413 last = bsi_stmt (bsi_last (bb));
4414 if (TREE_CODE (last) != COND_EXPR)
4417 /* We're basically looking for any kind of conditional with
4418 integral type arguments. */
4419 cond = COND_EXPR_COND (last);
4420 if ((TREE_CODE (cond) == SSA_NAME
4421 && INTEGRAL_TYPE_P (TREE_TYPE (cond)))
4422 || (COMPARISON_CLASS_P (cond)
4423 && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
4424 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 0)))
4425 && (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME
4426 || is_gimple_min_invariant (TREE_OPERAND (cond, 1)))
4427 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
4432 /* We've got a block with multiple predecessors and multiple
4433 successors which also ends in a suitable conditional. For
4434 each predecessor, see if we can thread it to a specific
4436 FOR_EACH_EDGE (e, ei, bb->preds)
4438 /* Do not thread across back edges or abnormal edges
4440 if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
4443 thread_across_edge (dummy, e, true,
4445 simplify_stmt_for_jump_threading);
4450 /* We do not actually update the CFG or SSA graphs at this point as
4451 ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet
4452 handle ASSERT_EXPRs gracefully. */
4455 /* We identified all the jump threading opportunities earlier, but could
4456 not transform the CFG at that time. This routine transforms the
4457 CFG and arranges for the dominator tree to be rebuilt if necessary.
4459 Note the SSA graph update will occur during the normal TODO
4460 processing by the pass manager. */
4462 finalize_jump_threads (void)
4464 bool cfg_altered = false;
4465 cfg_altered = thread_through_all_blocks ();
4467 /* If we threaded jumps, then we need to recompute the dominance
4468 information, to safely do that we must clean up the CFG first. */
4471 free_dominance_info (CDI_DOMINATORS);
4472 cleanup_tree_cfg ();
4473 calculate_dominance_info (CDI_DOMINATORS);
4475 VEC_free (tree, heap, stack);
4479 /* Traverse all the blocks folding conditionals with known ranges. */
4485 prop_value_t *single_val_range;
4486 bool do_value_subst_p;
4490 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
4491 dump_all_value_ranges (dump_file);
4492 fprintf (dump_file, "\n");
4495 /* We may have ended with ranges that have exactly one value. Those
4496 values can be substituted as any other copy/const propagated
4497 value using substitute_and_fold. */
4498 single_val_range = XNEWVEC (prop_value_t, num_ssa_names);
4499 memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range));
4501 do_value_subst_p = false;
4502 for (i = 0; i < num_ssa_names; i++)
4504 && vr_value[i]->type == VR_RANGE
4505 && vr_value[i]->min == vr_value[i]->max)
4507 single_val_range[i].value = vr_value[i]->min;
4508 do_value_subst_p = true;
4511 if (!do_value_subst_p)
4513 /* We found no single-valued ranges, don't waste time trying to
4514 do single value substitution in substitute_and_fold. */
4515 free (single_val_range);
4516 single_val_range = NULL;
4519 substitute_and_fold (single_val_range, true);
4521 /* We must identify jump threading opportunities before we release
4522 the datastructures built by VRP. */
4523 identify_jump_threads ();
4525 /* Free allocated memory. */
4526 for (i = 0; i < num_ssa_names; i++)
4529 BITMAP_FREE (vr_value[i]->equiv);
4533 free (single_val_range);
4536 /* So that we can distinguish between VRP data being available
4537 and not available. */
4542 /* Main entry point to VRP (Value Range Propagation). This pass is
4543 loosely based on J. R. C. Patterson, ``Accurate Static Branch
4544 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
4545 Programming Language Design and Implementation, pp. 67-78, 1995.
4546 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
4548 This is essentially an SSA-CCP pass modified to deal with ranges
4549 instead of constants.
4551 While propagating ranges, we may find that two or more SSA name
4552 have equivalent, though distinct ranges. For instance,
4555 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0>
4557 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
4561 In the code above, pointer p_5 has range [q_2, q_2], but from the
4562 code we can also determine that p_5 cannot be NULL and, if q_2 had
4563 a non-varying range, p_5's range should also be compatible with it.
4565 These equivalences are created by two expressions: ASSERT_EXPR and
4566 copy operations. Since p_5 is an assertion on p_4, and p_4 was the
4567 result of another assertion, then we can use the fact that p_5 and
4568 p_4 are equivalent when evaluating p_5's range.
4570 Together with value ranges, we also propagate these equivalences
4571 between names so that we can take advantage of information from
4572 multiple ranges when doing final replacement. Note that this
4573 equivalency relation is transitive but not symmetric.
4575 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
4576 cannot assert that q_2 is equivalent to p_5 because q_2 may be used
4577 in contexts where that assertion does not hold (e.g., in line 6).
4579 TODO, the main difference between this pass and Patterson's is that
4580 we do not propagate edge probabilities. We only compute whether
4581 edges can be taken or not. That is, instead of having a spectrum
4582 of jump probabilities between 0 and 1, we only deal with 0, 1 and
4583 DON'T KNOW. In the future, it may be worthwhile to propagate
4584 probabilities to aid branch prediction. */
4589 insert_range_assertions ();
4591 current_loops = loop_optimizer_init (LOOPS_NORMAL);
4593 scev_initialize (current_loops);
4596 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
4602 loop_optimizer_finalize (current_loops);
4603 current_loops = NULL;
4606 /* ASSERT_EXPRs must be removed before finalizing jump threads
4607 as finalizing jump threads calls the CFG cleanup code which
4608 does not properly handle ASSERT_EXPRs. */
4609 remove_range_assertions ();
4611 /* If we exposed any new variables, go ahead and put them into
4612 SSA form now, before we handle jump threading. This simplifies
4613 interactions between rewriting of _DECL nodes into SSA form
4614 and rewriting SSA_NAME nodes into SSA form after block
4615 duplication and CFG manipulation. */
4616 update_ssa (TODO_update_ssa);
4618 finalize_jump_threads ();
4625 return flag_tree_vrp != 0;
4628 struct tree_opt_pass pass_vrp =
4631 gate_vrp, /* gate */
4632 execute_vrp, /* execute */
4635 0, /* static_pass_number */
4636 TV_TREE_VRP, /* tv_id */
4637 PROP_ssa | PROP_alias, /* properties_required */
4638 0, /* properties_provided */
4639 PROP_smt_usage, /* properties_destroyed */
4640 0, /* todo_flags_start */
4646 | TODO_update_smt_usage, /* todo_flags_finish */