1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005 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, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, 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 /* Loop structure of the program. Used to analyze scalar evolutions
45 inside adjust_range_with_scev. */
46 static struct loops *cfg_loops;
48 /* Local functions. */
49 static int compare_values (tree val1, tree val2);
51 /* Location information for ASSERT_EXPRs. Each instance of this
52 structure describes an ASSERT_EXPR for an SSA name. Since a single
53 SSA name may have more than one assertion associated with it, these
54 locations are kept in a linked list attached to the corresponding
58 /* Basic block where the assertion would be inserted. */
61 /* Some assertions need to be inserted on an edge (e.g., assertions
62 generated by COND_EXPRs). In those cases, BB will be NULL. */
65 /* Pointer to the statement that generated this assertion. */
66 block_stmt_iterator si;
68 /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */
69 enum tree_code comp_code;
71 /* Value being compared against. */
74 /* Next node in the linked list. */
75 struct assert_locus_d *next;
78 typedef struct assert_locus_d *assert_locus_t;
80 /* If bit I is present, it means that SSA name N_i has a list of
81 assertions that should be inserted in the IL. */
82 static bitmap need_assert_for;
84 /* Array of locations lists where to insert assertions. ASSERTS_FOR[I]
85 holds a list of ASSERT_LOCUS_T nodes that describe where
86 ASSERT_EXPRs for SSA name N_I should be inserted. */
87 static assert_locus_t *asserts_for;
89 /* Set of blocks visited in find_assert_locations. Used to avoid
90 visiting the same block more than once. */
91 static sbitmap blocks_visited;
93 /* Value range array. After propagation, VR_VALUE[I] holds the range
94 of values that SSA name N_I may take. */
95 static value_range_t **vr_value;
97 /* Given a comparison code, return its opposite. Note that this is *not*
98 the same as inverting its truth value (invert_tree_comparison). Here we
99 just want to literally flip the comparison around.
101 So, '<' gets '>', '<=' gets '>='. Both '==' and '!=' are returned
104 static enum tree_code
105 opposite_comparison (enum tree_code code)
138 /* Return true if EXPR computes a non-zero value. */
141 expr_computes_nonzero (tree expr)
143 /* Type casts won't change anything, so just strip them. */
146 /* Calling alloca, guarantees that the value is non-NULL. */
147 if (alloca_call_p (expr))
150 /* The address of a non-weak symbol is never NULL, unless the user
151 has requested not to remove NULL pointer checks. */
152 if (flag_delete_null_pointer_checks
153 && TREE_CODE (expr) == ADDR_EXPR
154 && DECL_P (TREE_OPERAND (expr, 0))
155 && !DECL_WEAK (TREE_OPERAND (expr, 0)))
158 /* IOR of any value with a nonzero value will result in a nonzero
160 if (TREE_CODE (expr) == BIT_IOR_EXPR
161 && integer_nonzerop (TREE_OPERAND (expr, 1)))
168 /* Set value range VR to {T, MIN, MAX, EQUIV}. */
171 set_value_range (value_range_t *vr, enum value_range_type t, tree min,
172 tree max, bitmap equiv)
174 #if defined ENABLE_CHECKING
175 /* Check the validity of the range. */
176 if (t == VR_RANGE || t == VR_ANTI_RANGE)
180 gcc_assert (min && max);
182 if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
183 gcc_assert (min != TYPE_MIN_VALUE (TREE_TYPE (min))
184 || max != TYPE_MAX_VALUE (TREE_TYPE (max)));
186 cmp = compare_values (min, max);
187 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
190 if (t == VR_UNDEFINED || t == VR_VARYING)
191 gcc_assert (min == NULL_TREE && max == NULL_TREE);
193 if (t == VR_UNDEFINED || t == VR_VARYING)
194 gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
201 /* Since updating the equivalence set involves deep copying the
202 bitmaps, only do it if absolutely necessary. */
203 if (vr->equiv == NULL)
204 vr->equiv = BITMAP_ALLOC (NULL);
206 if (equiv != vr->equiv)
208 if (equiv && !bitmap_empty_p (equiv))
209 bitmap_copy (vr->equiv, equiv);
211 bitmap_clear (vr->equiv);
216 /* Copy value range FROM into value range TO. */
219 copy_value_range (value_range_t *to, value_range_t *from)
221 set_value_range (to, from->type, from->min, from->max, from->equiv);
225 /* Set value range VR to a non-NULL range of type TYPE. */
228 set_value_range_to_nonnull (value_range_t *vr, tree type)
230 tree zero = build_int_cst (type, 0);
231 set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
235 /* Set value range VR to a NULL range of type TYPE. */
238 set_value_range_to_null (value_range_t *vr, tree type)
240 tree zero = build_int_cst (type, 0);
241 set_value_range (vr, VR_RANGE, zero, zero, vr->equiv);
245 /* Set value range VR to VR_VARYING. */
248 set_value_range_to_varying (value_range_t *vr)
250 vr->type = VR_VARYING;
251 vr->min = vr->max = NULL_TREE;
253 bitmap_clear (vr->equiv);
257 /* Set value range VR to VR_UNDEFINED. */
260 set_value_range_to_undefined (value_range_t *vr)
262 vr->type = VR_UNDEFINED;
263 vr->min = vr->max = NULL_TREE;
265 bitmap_clear (vr->equiv);
269 /* Return value range information for VAR. Create an empty range
272 static value_range_t *
273 get_value_range (tree var)
277 unsigned ver = SSA_NAME_VERSION (var);
283 /* Create a default value range. */
284 vr_value[ver] = vr = xmalloc (sizeof (*vr));
285 memset (vr, 0, sizeof (*vr));
287 /* Allocate an equivalence set. */
288 vr->equiv = BITMAP_ALLOC (NULL);
290 /* If VAR is a default definition, the variable can take any value
292 sym = SSA_NAME_VAR (var);
293 if (var == var_ann (sym)->default_def)
294 set_value_range_to_varying (vr);
300 /* Update the value range and equivalence set for variable VAR to
301 NEW_VR. Return true if NEW_VR is different from VAR's previous
304 NOTE: This function assumes that NEW_VR is a temporary value range
305 object created for the sole purpose of updating VAR's range. The
306 storage used by the equivalence set from NEW_VR will be freed by
307 this function. Do not call update_value_range when NEW_VR
308 is the range object associated with another SSA name. */
311 update_value_range (tree var, value_range_t *new_vr)
313 value_range_t *old_vr;
316 /* Update the value range, if necessary. */
317 old_vr = get_value_range (var);
318 is_new = old_vr->type != new_vr->type
319 || old_vr->min != new_vr->min
320 || old_vr->max != new_vr->max
321 || (old_vr->equiv == NULL && new_vr->equiv)
322 || (old_vr->equiv && new_vr->equiv == NULL)
323 || (!bitmap_equal_p (old_vr->equiv, new_vr->equiv));
326 set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
329 BITMAP_FREE (new_vr->equiv);
330 new_vr->equiv = NULL;
336 /* Add VAR and VAR's equivalence set to EQUIV. */
339 add_equivalence (bitmap equiv, tree var)
341 unsigned ver = SSA_NAME_VERSION (var);
342 value_range_t *vr = vr_value[ver];
344 bitmap_set_bit (equiv, ver);
346 bitmap_ior_into (equiv, vr->equiv);
350 /* Return true if VR is ~[0, 0]. */
353 range_is_nonnull (value_range_t *vr)
355 return vr->type == VR_ANTI_RANGE
356 && integer_zerop (vr->min)
357 && integer_zerop (vr->max);
361 /* Return true if VR is [0, 0]. */
364 range_is_null (value_range_t *vr)
366 return vr->type == VR_RANGE
367 && integer_zerop (vr->min)
368 && integer_zerop (vr->max);
372 /* Return true if value range VR involves at least one symbol. */
375 symbolic_range_p (value_range_t *vr)
377 return (!is_gimple_min_invariant (vr->min)
378 || !is_gimple_min_invariant (vr->max));
382 /* Like expr_computes_nonzero, but this function uses value ranges
386 vrp_expr_computes_nonzero (tree expr)
388 if (expr_computes_nonzero (expr))
391 /* If we have an expression of the form &X->a, then the expression
392 is nonnull if X is nonnull. */
393 if (TREE_CODE (expr) == ADDR_EXPR)
395 tree base = get_base_address (TREE_OPERAND (expr, 0));
397 if (base != NULL_TREE
398 && TREE_CODE (base) == INDIRECT_REF
399 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
401 value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
402 if (range_is_nonnull (vr))
411 /* Compare two values VAL1 and VAL2. Return
413 -2 if VAL1 and VAL2 cannot be compared at compile-time,
416 +1 if VAL1 > VAL2, and
419 This is similar to tree_int_cst_compare but supports pointer values
420 and values that cannot be compared at compile time. */
423 compare_values (tree val1, tree val2)
428 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
430 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
431 == POINTER_TYPE_P (TREE_TYPE (val2)));
433 /* Do some limited symbolic comparisons. */
434 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
436 /* We can determine some comparisons against +INF and -INF even
437 if the other value is an expression. */
438 if (val1 == TYPE_MAX_VALUE (TREE_TYPE (val1))
439 && TREE_CODE (val2) == MINUS_EXPR)
441 /* +INF > NAME - CST. */
444 else if (val1 == TYPE_MIN_VALUE (TREE_TYPE (val1))
445 && TREE_CODE (val2) == PLUS_EXPR)
447 /* -INF < NAME + CST. */
450 else if (TREE_CODE (val1) == MINUS_EXPR
451 && val2 == TYPE_MAX_VALUE (TREE_TYPE (val2)))
453 /* NAME - CST < +INF. */
456 else if (TREE_CODE (val1) == PLUS_EXPR
457 && val2 == TYPE_MIN_VALUE (TREE_TYPE (val2)))
459 /* NAME + CST > -INF. */
464 if ((TREE_CODE (val1) == SSA_NAME
465 || TREE_CODE (val1) == PLUS_EXPR
466 || TREE_CODE (val1) == MINUS_EXPR)
467 && (TREE_CODE (val2) == SSA_NAME
468 || TREE_CODE (val2) == PLUS_EXPR
469 || TREE_CODE (val2) == MINUS_EXPR))
473 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
474 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
475 same name, return -2. */
476 if (TREE_CODE (val1) == SSA_NAME)
483 n1 = TREE_OPERAND (val1, 0);
484 c1 = TREE_OPERAND (val1, 1);
487 if (TREE_CODE (val2) == SSA_NAME)
494 n2 = TREE_OPERAND (val2, 0);
495 c2 = TREE_OPERAND (val2, 1);
498 /* Both values must use the same name. */
502 if (TREE_CODE (val1) == SSA_NAME)
504 if (TREE_CODE (val2) == SSA_NAME)
507 else if (TREE_CODE (val2) == PLUS_EXPR)
508 /* NAME < NAME + CST */
510 else if (TREE_CODE (val2) == MINUS_EXPR)
511 /* NAME > NAME - CST */
514 else if (TREE_CODE (val1) == PLUS_EXPR)
516 if (TREE_CODE (val2) == SSA_NAME)
517 /* NAME + CST > NAME */
519 else if (TREE_CODE (val2) == PLUS_EXPR)
520 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
521 return compare_values (c1, c2);
522 else if (TREE_CODE (val2) == MINUS_EXPR)
523 /* NAME + CST1 > NAME - CST2 */
526 else if (TREE_CODE (val1) == MINUS_EXPR)
528 if (TREE_CODE (val2) == SSA_NAME)
529 /* NAME - CST < NAME */
531 else if (TREE_CODE (val2) == PLUS_EXPR)
532 /* NAME - CST1 < NAME + CST2 */
534 else if (TREE_CODE (val2) == MINUS_EXPR)
535 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
536 C1 and C2 are swapped in the call to compare_values. */
537 return compare_values (c2, c1);
543 /* We cannot compare non-constants. */
544 if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
547 /* We cannot compare overflowed values. */
548 if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
551 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
552 return tree_int_cst_compare (val1, val2);
557 /* First see if VAL1 and VAL2 are not the same. */
558 if (val1 == val2 || operand_equal_p (val1, val2, 0))
561 /* If VAL1 is a lower address than VAL2, return -1. */
562 t = fold_binary (LT_EXPR, boolean_type_node, val1, val2);
563 if (t == boolean_true_node)
566 /* If VAL1 is a higher address than VAL2, return +1. */
567 t = fold_binary (GT_EXPR, boolean_type_node, val1, val2);
568 if (t == boolean_true_node)
571 /* If VAL1 is different than VAL2, return +2. */
572 t = fold_binary (NE_EXPR, boolean_type_node, val1, val2);
573 if (t == boolean_true_node)
581 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
582 0 if VAL is not inside VR,
583 -2 if we cannot tell either way. */
586 value_inside_range (tree val, value_range_t *vr)
590 cmp1 = compare_values (val, vr->min);
591 if (cmp1 == -2 || cmp1 == 2)
594 cmp2 = compare_values (val, vr->max);
595 if (cmp2 == -2 || cmp2 == 2)
598 return (cmp1 == 0 || cmp1 == 1) && (cmp2 == -1 || cmp2 == 0);
602 /* Return true if value ranges VR0 and VR1 have a non-empty
606 value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
608 return (value_inside_range (vr1->min, vr0) == 1
609 || value_inside_range (vr1->max, vr0) == 1
610 || value_inside_range (vr0->min, vr1) == 1
611 || value_inside_range (vr0->max, vr1) == 1);
615 /* Return true if VR includes the value zero, false otheriwse. */
618 range_includes_zero_p (value_range_t *vr)
622 gcc_assert (vr->type != VR_UNDEFINED
623 && vr->type != VR_VARYING
624 && !symbolic_range_p (vr));
626 zero = build_int_cst (TREE_TYPE (vr->min), 0);
627 return (value_inside_range (zero, vr) == 1);
631 /* Extract value range information from an ASSERT_EXPR EXPR and store
635 extract_range_from_assert (value_range_t *vr_p, tree expr)
637 tree var, cond, limit, min, max, type;
638 value_range_t *var_vr, *limit_vr;
639 enum tree_code cond_code;
641 var = ASSERT_EXPR_VAR (expr);
642 cond = ASSERT_EXPR_COND (expr);
644 gcc_assert (COMPARISON_CLASS_P (cond));
646 /* Find VAR in the ASSERT_EXPR conditional. */
647 if (var == TREE_OPERAND (cond, 0))
649 /* If the predicate is of the form VAR COMP LIMIT, then we just
650 take LIMIT from the RHS and use the same comparison code. */
651 limit = TREE_OPERAND (cond, 1);
652 cond_code = TREE_CODE (cond);
656 /* If the predicate is of the form LIMIT COMP VAR, then we need
657 to flip around the comparison code to create the proper range
659 limit = TREE_OPERAND (cond, 0);
660 cond_code = opposite_comparison (TREE_CODE (cond));
663 type = TREE_TYPE (limit);
664 gcc_assert (limit != var);
666 /* For pointer arithmetic, we only keep track of pointer equality
668 if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
670 set_value_range_to_varying (vr_p);
674 /* If LIMIT is another SSA name and LIMIT has a range of its own,
675 try to use LIMIT's range to avoid creating symbolic ranges
677 limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
679 /* LIMIT's range is only interesting if it has any useful information. */
681 && (limit_vr->type == VR_UNDEFINED
682 || limit_vr->type == VR_VARYING
683 || symbolic_range_p (limit_vr)))
686 /* Special handling for integral types with super-types. Some FEs
687 construct integral types derived from other types and restrict
688 the range of values these new types may take.
690 It may happen that LIMIT is actually smaller than TYPE's minimum
691 value. For instance, the Ada FE is generating code like this
694 D.1480_32 = nam_30 - 300000361;
695 if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
697 D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;
699 All the names are of type types__name_id___XDLU_300000000__399999999
700 which has min == 300000000 and max == 399999999. This means that
701 the ASSERT_EXPR would try to create the range [3000000, 1] which
704 The fact that the type specifies MIN and MAX values does not
705 automatically mean that every variable of that type will always
706 be within that range, so the predicate may well be true at run
707 time. If we had symbolic -INF and +INF values, we could
708 represent this range, but we currently represent -INF and +INF
709 using the type's min and max values.
711 So, the only sensible thing we can do for now is set the
712 resulting range to VR_VARYING. TODO, would having symbolic -INF
713 and +INF values be worth the trouble? */
714 if (TREE_CODE (limit) != SSA_NAME
715 && INTEGRAL_TYPE_P (type)
718 if (cond_code == LE_EXPR || cond_code == LT_EXPR)
720 tree type_min = TYPE_MIN_VALUE (type);
721 int cmp = compare_values (limit, type_min);
723 /* For < or <= comparisons, if LIMIT is smaller than
724 TYPE_MIN, set the range to VR_VARYING. */
725 if (cmp == -1 || cmp == 0)
727 set_value_range_to_varying (vr_p);
731 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
733 tree type_max = TYPE_MIN_VALUE (type);
734 int cmp = compare_values (limit, type_max);
736 /* For > or >= comparisons, if LIMIT is bigger than
737 TYPE_MAX, set the range to VR_VARYING. */
738 if (cmp == 1 || cmp == 0)
740 set_value_range_to_varying (vr_p);
746 /* The new range has the same set of equivalences of VAR's range. */
747 gcc_assert (vr_p->equiv == NULL);
748 vr_p->equiv = BITMAP_ALLOC (NULL);
749 add_equivalence (vr_p->equiv, var);
751 /* Extract a new range based on the asserted comparison for VAR and
752 LIMIT's value range. Notice that if LIMIT has an anti-range, we
753 will only use it for equality comparisons (EQ_EXPR). For any
754 other kind of assertion, we cannot derive a range from LIMIT's
755 anti-range that can be used to describe the new range. For
756 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
757 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
758 no single range for x_2 that could describe LE_EXPR, so we might
759 as well build the range [b_4, +INF] for it. */
760 if (cond_code == EQ_EXPR)
762 enum value_range_type range_type;
766 range_type = limit_vr->type;
772 range_type = VR_RANGE;
777 set_value_range (vr_p, range_type, min, max, vr_p->equiv);
779 /* When asserting the equality VAR == LIMIT and LIMIT is another
780 SSA name, the new range will also inherit the equivalence set
782 if (TREE_CODE (limit) == SSA_NAME)
783 add_equivalence (vr_p->equiv, limit);
785 else if (cond_code == NE_EXPR)
787 /* As described above, when LIMIT's range is an anti-range and
788 this assertion is an inequality (NE_EXPR), then we cannot
789 derive anything from the anti-range. For instance, if
790 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
791 not imply that VAR's range is [0, 0]. So, in the case of
792 anti-ranges, we just assert the inequality using LIMIT and
793 not its anti-range. */
795 || limit_vr->type == VR_ANTI_RANGE)
806 /* If MIN and MAX cover the whole range for their type, then
807 just use the original LIMIT. */
808 if (INTEGRAL_TYPE_P (type)
809 && min == TYPE_MIN_VALUE (type)
810 && max == TYPE_MAX_VALUE (type))
813 set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
815 else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
817 min = TYPE_MIN_VALUE (type);
819 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
823 /* If LIMIT_VR is of the form [N1, N2], we need to build the
824 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
829 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
830 if (cond_code == LT_EXPR)
832 tree one = build_int_cst (type, 1);
833 max = fold (build (MINUS_EXPR, type, max, one));
836 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
838 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
840 max = TYPE_MAX_VALUE (type);
842 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
846 /* If LIMIT_VR is of the form [N1, N2], we need to build the
847 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
852 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
853 if (cond_code == GT_EXPR)
855 tree one = build_int_cst (type, 1);
856 min = fold (build (PLUS_EXPR, type, min, one));
859 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
864 /* If VAR already had a known range and the two ranges have a
865 non-empty intersection, we can refine the resulting range.
866 Since the assert expression creates an equivalency and at the
867 same time it asserts a predicate, we can take the intersection of
868 the two ranges to get better precision. */
869 var_vr = get_value_range (var);
870 if (var_vr->type == VR_RANGE
871 && vr_p->type == VR_RANGE
872 && value_ranges_intersect_p (var_vr, vr_p))
874 /* Use the larger of the two minimums. */
875 if (compare_values (vr_p->min, var_vr->min) == -1)
880 /* Use the smaller of the two maximums. */
881 if (compare_values (vr_p->max, var_vr->max) == 1)
886 set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
891 /* Extract range information from SSA name VAR and store it in VR. If
892 VAR has an interesting range, use it. Otherwise, create the
893 range [VAR, VAR] and return it. This is useful in situations where
894 we may have conditionals testing values of VARYING names. For
901 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
905 extract_range_from_ssa_name (value_range_t *vr, tree var)
907 value_range_t *var_vr = get_value_range (var);
909 if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
910 copy_value_range (vr, var_vr);
912 set_value_range (vr, VR_RANGE, var, var, NULL);
914 add_equivalence (vr->equiv, var);
918 /* Extract range information from a binary expression EXPR based on
919 the ranges of each of its operands and the expression code. */
922 extract_range_from_binary_expr (value_range_t *vr, tree expr)
924 enum tree_code code = TREE_CODE (expr);
925 tree op0, op1, min, max;
927 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
928 value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
930 /* Not all binary expressions can be applied to ranges in a
931 meaningful way. Handle only arithmetic operations. */
932 if (code != PLUS_EXPR
933 && code != MINUS_EXPR
935 && code != TRUNC_DIV_EXPR
936 && code != FLOOR_DIV_EXPR
937 && code != CEIL_DIV_EXPR
938 && code != EXACT_DIV_EXPR
939 && code != ROUND_DIV_EXPR
942 && code != TRUTH_ANDIF_EXPR
943 && code != TRUTH_ORIF_EXPR
944 && code != TRUTH_AND_EXPR
945 && code != TRUTH_OR_EXPR
946 && code != TRUTH_XOR_EXPR)
948 set_value_range_to_varying (vr);
952 /* Get value ranges for each operand. For constant operands, create
953 a new value range with the operand to simplify processing. */
954 op0 = TREE_OPERAND (expr, 0);
955 if (TREE_CODE (op0) == SSA_NAME)
956 vr0 = *(get_value_range (op0));
957 else if (is_gimple_min_invariant (op0))
958 set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
960 set_value_range_to_varying (&vr0);
962 op1 = TREE_OPERAND (expr, 1);
963 if (TREE_CODE (op1) == SSA_NAME)
964 vr1 = *(get_value_range (op1));
965 else if (is_gimple_min_invariant (op1))
966 set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
968 set_value_range_to_varying (&vr1);
970 /* If either range is UNDEFINED, so is the result. */
971 if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
973 set_value_range_to_undefined (vr);
977 /* Refuse to operate on VARYING ranges, ranges of different kinds
978 and symbolic ranges. TODO, we may be able to derive anti-ranges
980 if (vr0.type == VR_VARYING
981 || vr1.type == VR_VARYING
982 || vr0.type != vr1.type
983 || symbolic_range_p (&vr0)
984 || symbolic_range_p (&vr1))
986 set_value_range_to_varying (vr);
990 /* Now evaluate the expression to determine the new range. */
991 if (POINTER_TYPE_P (TREE_TYPE (expr))
992 || POINTER_TYPE_P (TREE_TYPE (op0))
993 || POINTER_TYPE_P (TREE_TYPE (op1)))
995 /* For pointer types, we are really only interested in asserting
996 whether the expression evaluates to non-NULL. FIXME, we used
997 to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
998 ivopts is generating expressions with pointer multiplication
1000 if (code == PLUS_EXPR)
1001 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1004 /* Subtracting from a pointer, may yield 0, so just drop the
1005 resulting range to varying. */
1006 set_value_range_to_varying (vr);
1012 /* For integer ranges, apply the operation to each end of the
1013 range and see what we end up with. */
1014 if (code == TRUTH_ANDIF_EXPR
1015 || code == TRUTH_ORIF_EXPR
1016 || code == TRUTH_AND_EXPR
1017 || code == TRUTH_OR_EXPR
1018 || code == TRUTH_XOR_EXPR)
1020 /* Boolean expressions cannot be folded with int_const_binop. */
1021 min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
1022 max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
1024 else if (code == PLUS_EXPR
1025 || code == MULT_EXPR
1027 || code == MAX_EXPR)
1029 /* For operations that make the resulting range directly
1030 proportional to the original ranges, apply the operation to
1031 the same end of each range. */
1032 min = int_const_binop (code, vr0.min, vr1.min, 0);
1033 max = int_const_binop (code, vr0.max, vr1.max, 0);
1035 else if (code == TRUNC_DIV_EXPR
1036 || code == FLOOR_DIV_EXPR
1037 || code == CEIL_DIV_EXPR
1038 || code == EXACT_DIV_EXPR
1039 || code == ROUND_DIV_EXPR)
1043 /* Divisions are a bit tricky to handle, depending on the mix of
1044 signs we have in the two range, we will need to divide
1045 different values to get the minimum and maximum values for
1046 the new range. If VR1 includes zero, the result is VARYING. */
1047 if (range_includes_zero_p (&vr1))
1049 set_value_range_to_varying (vr);
1053 /* We have three main variations to handle for VR0: all negative
1054 values, all positive values and a mix of negative and
1055 positive. For each of these, we need to consider if VR1 is
1056 all negative or all positive. In total, there are 6
1057 combinations to handle. */
1058 zero = build_int_cst (TREE_TYPE (expr), 0);
1059 if (compare_values (vr0.max, zero) == -1)
1061 /* VR0 is all negative. */
1062 if (compare_values (vr1.min, zero) == 1)
1064 /* If VR1 is all positive, the new range is obtained
1065 with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MAX]. */
1066 min = int_const_binop (code, vr0.min, vr1.min, 0);
1067 max = int_const_binop (code, vr0.max, vr1.max, 0);
1071 /* If VR1 is all negative, the new range is obtained
1072 with [VR0.MAX / VR1.MIN, VR0.MIN / VR1.MAX]. */
1073 gcc_assert (compare_values (vr1.max, zero) == -1);
1074 min = int_const_binop (code, vr0.max, vr1.min, 0);
1075 max = int_const_binop (code, vr0.min, vr1.max, 0);
1078 else if (range_includes_zero_p (&vr0))
1080 /* VR0 is a mix of negative and positive values. */
1081 if (compare_values (vr1.min, zero) == 1)
1083 /* If VR1 is all positive, the new range is obtained
1084 with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MIN]. */
1085 min = int_const_binop (code, vr0.min, vr1.min, 0);
1086 max = int_const_binop (code, vr0.max, vr1.min, 0);
1090 /* If VR1 is all negative, the new range is obtained
1091 with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MAX]. */
1092 gcc_assert (compare_values (vr1.max, zero) == -1);
1093 min = int_const_binop (code, vr0.max, vr1.max, 0);
1094 max = int_const_binop (code, vr0.min, vr1.max, 0);
1099 /* VR0 is all positive. */
1100 gcc_assert (compare_values (vr0.min, zero) == 1);
1101 if (compare_values (vr1.min, zero) == 1)
1103 /* If VR1 is all positive, the new range is obtained
1104 with [VR0.MIN / VR1.MAX, VR0.MAX / VR1.MIN]. */
1105 min = int_const_binop (code, vr0.min, vr1.max, 0);
1106 max = int_const_binop (code, vr0.max, vr1.min, 0);
1110 /* If VR1 is all negative, the new range is obtained
1111 with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MIN]. */
1112 gcc_assert (compare_values (vr1.max, zero) == -1);
1113 min = int_const_binop (code, vr0.max, vr1.max, 0);
1114 max = int_const_binop (code, vr0.min, vr1.min, 0);
1118 else if (code == MINUS_EXPR)
1120 /* For MINUS_EXPR, apply the operation to the opposite ends of
1122 min = int_const_binop (code, vr0.min, vr1.max, 0);
1123 max = int_const_binop (code, vr0.max, vr1.min, 0);
1128 /* If MAX overflowed, then the result depends on whether we are
1129 using wrapping arithmetic or not. */
1130 if (TREE_OVERFLOW (max))
1132 /* If we are using wrapping arithmetic, set the result to
1136 set_value_range_to_varying (vr);
1140 /* Otherwise, set MAX to +INF. */
1141 max = TYPE_MAX_VALUE (TREE_TYPE (expr));
1144 /* If MIN overflowed, then the result depends on whether we are
1145 using wrapping arithmetic or not. */
1146 if (TREE_OVERFLOW (min))
1148 /* If we are using wrapping arithmetic, set the result to
1152 set_value_range_to_varying (vr);
1156 /* Otherwise, set MIN to -INF. */
1157 min = TYPE_MIN_VALUE (TREE_TYPE (expr));
1160 cmp = compare_values (min, max);
1161 if (cmp == -2 || cmp == 1)
1163 /* If the new range has its limits swapped around (MIN > MAX),
1164 then the operation caused one of them to wrap around, mark
1165 the new range VARYING. */
1166 set_value_range_to_varying (vr);
1169 set_value_range (vr, vr0.type, min, max, NULL);
1173 /* Extract range information from a unary expression EXPR based on
1174 the range of its operand and the expression code. */
1177 extract_range_from_unary_expr (value_range_t *vr, tree expr)
1179 enum tree_code code = TREE_CODE (expr);
1182 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1184 /* Refuse to operate on certain unary expressions for which we
1185 cannot easily determine a resulting range. */
1186 if (code == FIX_TRUNC_EXPR
1187 || code == FIX_CEIL_EXPR
1188 || code == FIX_FLOOR_EXPR
1189 || code == FIX_ROUND_EXPR
1190 || code == FLOAT_EXPR
1191 || code == BIT_NOT_EXPR
1192 || code == NON_LVALUE_EXPR
1193 || code == CONJ_EXPR)
1195 set_value_range_to_varying (vr);
1199 /* Get value ranges for the operand. For constant operands, create
1200 a new value range with the operand to simplify processing. */
1201 op0 = TREE_OPERAND (expr, 0);
1202 if (TREE_CODE (op0) == SSA_NAME)
1203 vr0 = *(get_value_range (op0));
1204 else if (is_gimple_min_invariant (op0))
1205 set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1207 set_value_range_to_varying (&vr0);
1209 /* If VR0 is UNDEFINED, so is the result. */
1210 if (vr0.type == VR_UNDEFINED)
1212 set_value_range_to_undefined (vr);
1216 /* Refuse to operate on varying and symbolic ranges. Also, if the
1217 operand is neither a pointer nor an integral type, set the
1218 resulting range to VARYING. TODO, in some cases we may be able
1219 to derive anti-ranges (like non-zero values). */
1220 if (vr0.type == VR_VARYING
1221 || (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
1222 && !POINTER_TYPE_P (TREE_TYPE (op0)))
1223 || symbolic_range_p (&vr0))
1225 set_value_range_to_varying (vr);
1229 /* If the expression involves pointers, we are only interested in
1230 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
1231 if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
1233 if (range_is_nonnull (&vr0) || expr_computes_nonzero (expr))
1234 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1235 else if (range_is_null (&vr0))
1236 set_value_range_to_null (vr, TREE_TYPE (expr));
1238 set_value_range_to_varying (vr);
1243 /* Handle unary expressions on integer ranges. */
1244 if ((code == NOP_EXPR || code == CONVERT_EXPR)
1245 && (TYPE_SIZE (TREE_TYPE (vr0.min)) != TYPE_SIZE (TREE_TYPE (expr))))
1247 /* When converting types of different sizes, set the result to
1248 VARYING. Things like sign extensions and precision loss may
1249 change the range. For instance, if x_3 is of type 'long long
1250 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
1251 is impossible to know at compile time whether y_5 will be
1253 set_value_range_to_varying (vr);
1257 /* Apply the operation to each end of the range and see what we end
1259 if (code == NEGATE_EXPR
1260 && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1262 /* Negating an anti-range doesn't really do anything to it. The
1263 new range will also not take on the same range of values
1264 excluded by the original anti-range. */
1265 if (vr0.type == VR_ANTI_RANGE)
1267 copy_value_range (vr, &vr0);
1271 /* NEGATE_EXPR flips the range around. */
1272 min = (vr0.max == TYPE_MAX_VALUE (TREE_TYPE (expr)))
1273 ? TYPE_MIN_VALUE (TREE_TYPE (expr))
1274 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1276 max = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1277 ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1278 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1280 else if (code == ABS_EXPR
1281 && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1283 /* ABS_EXPR may flip the range around, if the original range
1284 included negative values. */
1285 min = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1286 ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1287 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1289 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1291 /* If the range was reversed, swap MIN and MAX. */
1292 if (compare_values (min, max) == 1)
1301 /* Otherwise, operate on each end of the range. */
1302 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1303 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1306 cmp = compare_values (min, max);
1307 if (cmp == -2 || cmp == 1)
1309 /* If the new range has its limits swapped around (MIN > MAX),
1310 then the operation caused one of them to wrap around, mark
1311 the new range VARYING. */
1312 set_value_range_to_varying (vr);
1315 set_value_range (vr, vr0.type, min, max, NULL);
1319 /* Extract range information from a comparison expression EXPR based
1320 on the range of its operand and the expression code. */
1323 extract_range_from_comparison (value_range_t *vr, tree expr)
1325 tree val = vrp_evaluate_conditional (expr, false);
1328 /* Since this expression was found on the RHS of an assignment,
1329 its type may be different from _Bool. Convert VAL to EXPR's
1331 val = fold_convert (TREE_TYPE (expr), val);
1332 set_value_range (vr, VR_RANGE, val, val, vr->equiv);
1335 set_value_range_to_varying (vr);
1339 /* Try to compute a useful range out of expression EXPR and store it
1343 extract_range_from_expr (value_range_t *vr, tree expr)
1345 enum tree_code code = TREE_CODE (expr);
1347 if (code == ASSERT_EXPR)
1348 extract_range_from_assert (vr, expr);
1349 else if (code == SSA_NAME)
1350 extract_range_from_ssa_name (vr, expr);
1351 else if (TREE_CODE_CLASS (code) == tcc_binary
1352 || code == TRUTH_ANDIF_EXPR
1353 || code == TRUTH_ORIF_EXPR
1354 || code == TRUTH_AND_EXPR
1355 || code == TRUTH_OR_EXPR
1356 || code == TRUTH_XOR_EXPR)
1357 extract_range_from_binary_expr (vr, expr);
1358 else if (TREE_CODE_CLASS (code) == tcc_unary)
1359 extract_range_from_unary_expr (vr, expr);
1360 else if (TREE_CODE_CLASS (code) == tcc_comparison)
1361 extract_range_from_comparison (vr, expr);
1362 else if (vrp_expr_computes_nonzero (expr))
1363 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1364 else if (is_gimple_min_invariant (expr))
1365 set_value_range (vr, VR_RANGE, expr, expr, NULL);
1367 set_value_range_to_varying (vr);
1371 /* Given a range VR, a loop L and a variable VAR, determine whether it
1372 would be profitable to adjust VR using scalar evolution information
1373 for VAR. If so, update VR with the new limits. */
1376 adjust_range_with_scev (value_range_t *vr, struct loop *l, tree var)
1378 tree init, step, chrec;
1381 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1382 better opportunities than a regular range, but I'm not sure. */
1383 if (vr->type == VR_ANTI_RANGE)
1386 chrec = analyze_scalar_evolution (l, var);
1387 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1390 init = CHREC_LEFT (chrec);
1391 step = CHREC_RIGHT (chrec);
1393 /* If STEP is symbolic, we can't know whether INIT will be the
1394 minimum or maximum value in the range. */
1395 if (!is_gimple_min_invariant (step))
1398 /* FIXME. When dealing with unsigned types,
1399 analyze_scalar_evolution sets STEP to very large unsigned values
1400 when the evolution goes backwards. This confuses this analysis
1401 because we think that INIT is the smallest value that the range
1402 can take, instead of the largest. Ignore these chrecs for now. */
1403 if (INTEGRAL_TYPE_P (TREE_TYPE (step)) && TYPE_UNSIGNED (TREE_TYPE (step)))
1406 /* Do not adjust ranges when using wrapping arithmetic. */
1410 /* If STEP is negative, then INIT is the maximum value the range
1411 will take. Otherwise, INIT is the minimum value. */
1412 init_is_max = (tree_int_cst_sgn (step) < 0);
1414 if (!POINTER_TYPE_P (TREE_TYPE (init))
1415 && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
1417 /* For VARYING or UNDEFINED ranges, just about anything we get
1418 from scalar evolutions should be better. */
1420 set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)),
1423 set_value_range (vr, VR_RANGE, init, TYPE_MAX_VALUE (TREE_TYPE (init)),
1426 else if (vr->type == VR_RANGE)
1433 /* INIT is the maximum value. If INIT is lower than VR->MAX
1434 but no smaller than VR->MIN, set VR->MAX to INIT. */
1435 if (compare_values (init, max) == -1)
1439 /* If we just created an invalid range with the minimum
1440 greater than the maximum, take the minimum all the
1442 if (compare_values (min, max) == 1)
1443 min = TYPE_MIN_VALUE (TREE_TYPE (min));
1448 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1449 if (compare_values (init, min) == 1)
1453 /* If we just created an invalid range with the minimum
1454 greater than the maximum, take the maximum all the
1456 if (compare_values (min, max) == 1)
1457 max = TYPE_MAX_VALUE (TREE_TYPE (max));
1461 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
1466 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1468 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1469 all the values in the ranges.
1471 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1473 - Return NULL_TREE if it is not always possible to determine the
1474 value of the comparison. */
1478 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1)
1480 /* VARYING or UNDEFINED ranges cannot be compared. */
1481 if (vr0->type == VR_VARYING
1482 || vr0->type == VR_UNDEFINED
1483 || vr1->type == VR_VARYING
1484 || vr1->type == VR_UNDEFINED)
1487 /* Anti-ranges need to be handled separately. */
1488 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
1490 /* If both are anti-ranges, then we cannot compute any
1492 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
1495 /* These comparisons are never statically computable. */
1502 /* Equality can be computed only between a range and an
1503 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1504 if (vr0->type == VR_RANGE)
1506 /* To simplify processing, make VR0 the anti-range. */
1507 value_range_t *tmp = vr0;
1512 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
1514 if (compare_values (vr0->min, vr1->min) == 0
1515 && compare_values (vr0->max, vr1->max) == 0)
1516 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1521 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1522 operands around and change the comparison code. */
1523 if (comp == GT_EXPR || comp == GE_EXPR)
1526 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
1532 if (comp == EQ_EXPR)
1534 /* Equality may only be computed if both ranges represent
1535 exactly one value. */
1536 if (compare_values (vr0->min, vr0->max) == 0
1537 && compare_values (vr1->min, vr1->max) == 0)
1539 int cmp_min = compare_values (vr0->min, vr1->min);
1540 int cmp_max = compare_values (vr0->max, vr1->max);
1541 if (cmp_min == 0 && cmp_max == 0)
1542 return boolean_true_node;
1543 else if (cmp_min != -2 && cmp_max != -2)
1544 return boolean_false_node;
1549 else if (comp == NE_EXPR)
1553 /* If VR0 is completely to the left or completely to the right
1554 of VR1, they are always different. Notice that we need to
1555 make sure that both comparisons yield similar results to
1556 avoid comparing values that cannot be compared at
1558 cmp1 = compare_values (vr0->max, vr1->min);
1559 cmp2 = compare_values (vr0->min, vr1->max);
1560 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
1561 return boolean_true_node;
1563 /* If VR0 and VR1 represent a single value and are identical,
1565 else if (compare_values (vr0->min, vr0->max) == 0
1566 && compare_values (vr1->min, vr1->max) == 0
1567 && compare_values (vr0->min, vr1->min) == 0
1568 && compare_values (vr0->max, vr1->max) == 0)
1569 return boolean_false_node;
1571 /* Otherwise, they may or may not be different. */
1575 else if (comp == LT_EXPR || comp == LE_EXPR)
1579 /* If VR0 is to the left of VR1, return true. */
1580 tst = compare_values (vr0->max, vr1->min);
1581 if ((comp == LT_EXPR && tst == -1)
1582 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1583 return boolean_true_node;
1585 /* If VR0 is to the right of VR1, return false. */
1586 tst = compare_values (vr0->min, vr1->max);
1587 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1588 || (comp == LE_EXPR && tst == 1))
1589 return boolean_false_node;
1591 /* Otherwise, we don't know. */
1599 /* Given a value range VR, a value VAL and a comparison code COMP, return
1600 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1601 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1602 always returns false. Return NULL_TREE if it is not always
1603 possible to determine the value of the comparison. */
1606 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val)
1608 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1611 /* Anti-ranges need to be handled separately. */
1612 if (vr->type == VR_ANTI_RANGE)
1614 /* For anti-ranges, the only predicates that we can compute at
1615 compile time are equality and inequality. */
1622 /* ~[VAL, VAL] == VAL is always false. */
1623 if (compare_values (vr->min, val) == 0
1624 && compare_values (vr->max, val) == 0)
1625 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1630 if (comp == EQ_EXPR)
1632 /* EQ_EXPR may only be computed if VR represents exactly
1634 if (compare_values (vr->min, vr->max) == 0)
1636 int cmp = compare_values (vr->min, val);
1638 return boolean_true_node;
1639 else if (cmp == -1 || cmp == 1 || cmp == 2)
1640 return boolean_false_node;
1642 else if (compare_values (val, vr->min) == -1
1643 || compare_values (vr->max, val) == -1)
1644 return boolean_false_node;
1648 else if (comp == NE_EXPR)
1650 /* If VAL is not inside VR, then they are always different. */
1651 if (compare_values (vr->max, val) == -1
1652 || compare_values (vr->min, val) == 1)
1653 return boolean_true_node;
1655 /* If VR represents exactly one value equal to VAL, then return
1657 if (compare_values (vr->min, vr->max) == 0
1658 && compare_values (vr->min, val) == 0)
1659 return boolean_false_node;
1661 /* Otherwise, they may or may not be different. */
1664 else if (comp == LT_EXPR || comp == LE_EXPR)
1668 /* If VR is to the left of VAL, return true. */
1669 tst = compare_values (vr->max, val);
1670 if ((comp == LT_EXPR && tst == -1)
1671 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1672 return boolean_true_node;
1674 /* If VR is to the right of VAL, return false. */
1675 tst = compare_values (vr->min, val);
1676 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1677 || (comp == LE_EXPR && tst == 1))
1678 return boolean_false_node;
1680 /* Otherwise, we don't know. */
1683 else if (comp == GT_EXPR || comp == GE_EXPR)
1687 /* If VR is to the right of VAL, return true. */
1688 tst = compare_values (vr->min, val);
1689 if ((comp == GT_EXPR && tst == 1)
1690 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
1691 return boolean_true_node;
1693 /* If VR is to the left of VAL, return false. */
1694 tst = compare_values (vr->max, val);
1695 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
1696 || (comp == GE_EXPR && tst == -1))
1697 return boolean_false_node;
1699 /* Otherwise, we don't know. */
1707 /* Debugging dumps. */
1709 void dump_value_range (FILE *, value_range_t *);
1710 void debug_value_range (value_range_t *);
1711 void dump_all_value_ranges (FILE *);
1712 void debug_all_value_ranges (void);
1713 void dump_vr_equiv (FILE *, bitmap);
1714 void debug_vr_equiv (bitmap);
1717 /* Dump value range VR to FILE. */
1720 dump_value_range (FILE *file, value_range_t *vr)
1723 fprintf (file, "[]");
1724 else if (vr->type == VR_UNDEFINED)
1725 fprintf (file, "UNDEFINED");
1726 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
1728 tree type = TREE_TYPE (vr->min);
1730 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
1732 if (INTEGRAL_TYPE_P (type)
1733 && !TYPE_UNSIGNED (type)
1734 && vr->min == TYPE_MIN_VALUE (type))
1735 fprintf (file, "-INF");
1737 print_generic_expr (file, vr->min, 0);
1739 fprintf (file, ", ");
1741 if (INTEGRAL_TYPE_P (type)
1742 && vr->max == TYPE_MAX_VALUE (type))
1743 fprintf (file, "+INF");
1745 print_generic_expr (file, vr->max, 0);
1747 fprintf (file, "]");
1754 fprintf (file, " EQUIVALENCES: { ");
1756 EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
1758 print_generic_expr (file, ssa_name (i), 0);
1759 fprintf (file, " ");
1763 fprintf (file, "} (%u elements)", c);
1766 else if (vr->type == VR_VARYING)
1767 fprintf (file, "VARYING");
1769 fprintf (file, "INVALID RANGE");
1773 /* Dump value range VR to stderr. */
1776 debug_value_range (value_range_t *vr)
1778 dump_value_range (stderr, vr);
1782 /* Dump value ranges of all SSA_NAMEs to FILE. */
1785 dump_all_value_ranges (FILE *file)
1789 for (i = 0; i < num_ssa_names; i++)
1793 print_generic_expr (file, ssa_name (i), 0);
1794 fprintf (file, ": ");
1795 dump_value_range (file, vr_value[i]);
1796 fprintf (file, "\n");
1800 fprintf (file, "\n");
1804 /* Dump all value ranges to stderr. */
1807 debug_all_value_ranges (void)
1809 dump_all_value_ranges (stderr);
1813 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
1814 create a new SSA name N and return the assertion assignment
1815 'V = ASSERT_EXPR <V, V OP W>'. */
1818 build_assert_expr_for (tree cond, tree v)
1822 gcc_assert (TREE_CODE (v) == SSA_NAME);
1823 n = duplicate_ssa_name (v, NULL_TREE);
1825 if (COMPARISON_CLASS_P (cond))
1827 tree a = build (ASSERT_EXPR, TREE_TYPE (v), v, cond);
1828 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, a);
1830 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1832 /* Given !V, build the assignment N = false. */
1833 tree op0 = TREE_OPERAND (cond, 0);
1834 gcc_assert (op0 == v);
1835 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
1837 else if (TREE_CODE (cond) == SSA_NAME)
1839 /* Given V, build the assignment N = true. */
1840 gcc_assert (v == cond);
1841 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
1846 SSA_NAME_DEF_STMT (n) = assertion;
1848 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
1849 operand of the ASSERT_EXPR. Register the new name and the old one
1850 in the replacement table so that we can fix the SSA web after
1851 adding all the ASSERT_EXPRs. */
1852 register_new_name_mapping (n, v);
1858 /* Return false if EXPR is a predicate expression involving floating
1862 fp_predicate (tree expr)
1864 return (COMPARISON_CLASS_P (expr)
1865 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
1869 /* If the range of values taken by OP can be inferred after STMT executes,
1870 return the comparison code (COMP_CODE_P) and value (VAL_P) that
1871 describes the inferred range. Return true if a range could be
1875 infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
1878 *comp_code_p = ERROR_MARK;
1880 /* Do not attempt to infer anything in names that flow through
1882 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1885 /* Similarly, don't infer anything from statements that may throw
1887 if (tree_could_throw_p (stmt))
1890 if (POINTER_TYPE_P (TREE_TYPE (op)))
1893 unsigned num_uses, num_derefs;
1895 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
1896 if (num_derefs > 0 && flag_delete_null_pointer_checks)
1898 /* We can only assume that a pointer dereference will yield
1899 non-NULL if -fdelete-null-pointer-checks is enabled. */
1900 *val_p = build_int_cst (TREE_TYPE (op), 0);
1901 *comp_code_p = NE_EXPR;
1910 void dump_asserts_for (FILE *, tree);
1911 void debug_asserts_for (tree);
1912 void dump_all_asserts (FILE *);
1913 void debug_all_asserts (void);
1915 /* Dump all the registered assertions for NAME to FILE. */
1918 dump_asserts_for (FILE *file, tree name)
1922 fprintf (file, "Assertions to be inserted for ");
1923 print_generic_expr (file, name, 0);
1924 fprintf (file, "\n");
1926 loc = asserts_for[SSA_NAME_VERSION (name)];
1929 fprintf (file, "\t");
1930 print_generic_expr (file, bsi_stmt (loc->si), 0);
1931 fprintf (file, "\n\tBB #%d", loc->bb->index);
1934 fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
1935 loc->e->dest->index);
1936 dump_edge_info (file, loc->e, 0);
1938 fprintf (file, "\n\tPREDICATE: ");
1939 print_generic_expr (file, name, 0);
1940 fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
1941 print_generic_expr (file, loc->val, 0);
1942 fprintf (file, "\n\n");
1946 fprintf (file, "\n");
1950 /* Dump all the registered assertions for NAME to stderr. */
1953 debug_asserts_for (tree name)
1955 dump_asserts_for (stderr, name);
1959 /* Dump all the registered assertions for all the names to FILE. */
1962 dump_all_asserts (FILE *file)
1967 fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
1968 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
1969 dump_asserts_for (file, ssa_name (i));
1970 fprintf (file, "\n");
1974 /* Dump all the registered assertions for all the names to stderr. */
1977 debug_all_asserts (void)
1979 dump_all_asserts (stderr);
1983 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
1984 'NAME COMP_CODE VAL' at a location that dominates block BB or
1985 E->DEST, then register this location as a possible insertion point
1986 for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
1988 BB, E and SI provide the exact insertion point for the new
1989 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
1990 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
1991 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
1992 must not be NULL. */
1995 register_new_assert_for (tree name,
1996 enum tree_code comp_code,
2000 block_stmt_iterator si)
2002 assert_locus_t n, loc, last_loc;
2004 basic_block dest_bb;
2006 #if defined ENABLE_CHECKING
2007 gcc_assert (bb == NULL || e == NULL);
2010 gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
2011 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
2014 /* The new assertion A will be inserted at BB or E. We need to
2015 determine if the new location is dominated by a previously
2016 registered location for A. If we are doing an edge insertion,
2017 assume that A will be inserted at E->DEST. Note that this is not
2020 If E is a critical edge, it will be split. But even if E is
2021 split, the new block will dominate the same set of blocks that
2024 The reverse, however, is not true, blocks dominated by E->DEST
2025 will not be dominated by the new block created to split E. So,
2026 if the insertion location is on a critical edge, we will not use
2027 the new location to move another assertion previously registered
2028 at a block dominated by E->DEST. */
2029 dest_bb = (bb) ? bb : e->dest;
2031 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
2032 VAL at a block dominating DEST_BB, then we don't need to insert a new
2033 one. Similarly, if the same assertion already exists at a block
2034 dominated by DEST_BB and the new location is not on a critical
2035 edge, then update the existing location for the assertion (i.e.,
2036 move the assertion up in the dominance tree).
2038 Note, this is implemented as a simple linked list because there
2039 should not be more than a handful of assertions registered per
2040 name. If this becomes a performance problem, a table hashed by
2041 COMP_CODE and VAL could be implemented. */
2042 loc = asserts_for[SSA_NAME_VERSION (name)];
2047 if (loc->comp_code == comp_code
2049 || operand_equal_p (loc->val, val, 0)))
2051 /* If the assertion NAME COMP_CODE VAL has already been
2052 registered at a basic block that dominates DEST_BB, then
2053 we don't need to insert the same assertion again. Note
2054 that we don't check strict dominance here to avoid
2055 replicating the same assertion inside the same basic
2056 block more than once (e.g., when a pointer is
2057 dereferenced several times inside a block).
2059 An exception to this rule are edge insertions. If the
2060 new assertion is to be inserted on edge E, then it will
2061 dominate all the other insertions that we may want to
2062 insert in DEST_BB. So, if we are doing an edge
2063 insertion, don't do this dominance check. */
2065 && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
2068 /* Otherwise, if E is not a critical edge and DEST_BB
2069 dominates the existing location for the assertion, move
2070 the assertion up in the dominance tree by updating its
2071 location information. */
2072 if ((e == NULL || !EDGE_CRITICAL_P (e))
2073 && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
2082 /* Update the last node of the list and move to the next one. */
2087 /* If we didn't find an assertion already registered for
2088 NAME COMP_CODE VAL, add a new one at the end of the list of
2089 assertions associated with NAME. */
2090 n = xmalloc (sizeof (*n));
2094 n->comp_code = comp_code;
2101 asserts_for[SSA_NAME_VERSION (name)] = n;
2103 bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
2107 /* Try to register an edge assertion for SSA name NAME on edge E for
2108 the conditional jump pointed by SI. Return true if an assertion
2109 for NAME could be registered. */
2112 register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
2115 enum tree_code comp_code;
2117 stmt = bsi_stmt (si);
2119 /* Do not attempt to infer anything in names that flow through
2121 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
2124 /* If NAME was not found in the sub-graph reachable from E, then
2125 there's nothing to do. */
2126 if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
2129 /* We found a use of NAME in the sub-graph rooted at E->DEST.
2130 Register an assertion for NAME according to the value that NAME
2132 if (TREE_CODE (stmt) == COND_EXPR)
2134 /* If BB ends in a COND_EXPR then NAME then we should insert
2135 the original predicate on EDGE_TRUE_VALUE and the
2136 opposite predicate on EDGE_FALSE_VALUE. */
2137 tree cond = COND_EXPR_COND (stmt);
2138 bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
2140 /* Predicates may be a single SSA name or NAME OP VAL. */
2143 /* If the predicate is a name, it must be NAME, in which
2144 case we create the predicate NAME == true or
2145 NAME == false accordingly. */
2146 comp_code = EQ_EXPR;
2147 val = (is_else_edge) ? boolean_false_node : boolean_true_node;
2151 /* Otherwise, we have a comparison of the form NAME COMP VAL
2152 or VAL COMP NAME. */
2153 if (name == TREE_OPERAND (cond, 1))
2155 /* If the predicate is of the form VAL COMP NAME, flip
2156 COMP around because we need to register NAME as the
2157 first operand in the predicate. */
2158 comp_code = opposite_comparison (TREE_CODE (cond));
2159 val = TREE_OPERAND (cond, 0);
2163 /* The comparison is of the form NAME COMP VAL, so the
2164 comparison code remains unchanged. */
2165 comp_code = TREE_CODE (cond);
2166 val = TREE_OPERAND (cond, 1);
2169 /* If we are inserting the assertion on the ELSE edge, we
2170 need to invert the sign comparison. */
2172 comp_code = invert_tree_comparison (comp_code, 0);
2177 /* FIXME. Handle SWITCH_EXPR. */
2181 register_new_assert_for (name, comp_code, val, NULL, e, si);
2186 static bool find_assert_locations (basic_block bb);
2188 /* Determine whether the outgoing edges of BB should receive an
2189 ASSERT_EXPR for each of the operands of BB's last statement. The
2190 last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
2192 If any of the sub-graphs rooted at BB have an interesting use of
2193 the predicate operands, an assert location node is added to the
2194 list of assertions for the corresponding operands. */
2197 find_conditional_asserts (basic_block bb)
2200 block_stmt_iterator last_si;
2206 need_assert = false;
2207 last_si = bsi_last (bb);
2208 last = bsi_stmt (last_si);
2210 /* Look for uses of the operands in each of the sub-graphs
2211 rooted at BB. We need to check each of the outgoing edges
2212 separately, so that we know what kind of ASSERT_EXPR to
2214 FOR_EACH_EDGE (e, ei, bb->succs)
2219 /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
2220 Otherwise, when we finish traversing each of the sub-graphs, we
2221 won't know whether the variables were found in the sub-graphs or
2222 if they had been found in a block upstream from BB. */
2223 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2224 RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2226 /* Traverse the strictly dominated sub-graph rooted at E->DEST
2227 to determine if any of the operands in the conditional
2228 predicate are used. */
2230 need_assert |= find_assert_locations (e->dest);
2232 /* Register the necessary assertions for each operand in the
2233 conditional predicate. */
2234 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2235 need_assert |= register_edge_assert_for (op, e, last_si);
2238 /* Finally, indicate that we have found the operands in the
2240 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2241 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2247 /* Traverse all the statements in block BB looking for statements that
2248 may generate useful assertions for the SSA names in their operand.
2249 If a statement produces a useful assertion A for name N_i, then the
2250 list of assertions already generated for N_i is scanned to
2251 determine if A is actually needed.
2253 If N_i already had the assertion A at a location dominating the
2254 current location, then nothing needs to be done. Otherwise, the
2255 new location for A is recorded instead.
2257 1- For every statement S in BB, all the variables used by S are
2258 added to bitmap FOUND_IN_SUBGRAPH.
2260 2- If statement S uses an operand N in a way that exposes a known
2261 value range for N, then if N was not already generated by an
2262 ASSERT_EXPR, create a new assert location for N. For instance,
2263 if N is a pointer and the statement dereferences it, we can
2264 assume that N is not NULL.
2266 3- COND_EXPRs are a special case of #2. We can derive range
2267 information from the predicate but need to insert different
2268 ASSERT_EXPRs for each of the sub-graphs rooted at the
2269 conditional block. If the last statement of BB is a conditional
2270 expression of the form 'X op Y', then
2272 a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
2274 b) If the conditional is the only entry point to the sub-graph
2275 corresponding to the THEN_CLAUSE, recurse into it. On
2276 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
2277 an ASSERT_EXPR is added for the corresponding variable.
2279 c) Repeat step (b) on the ELSE_CLAUSE.
2281 d) Mark X and Y in FOUND_IN_SUBGRAPH.
2290 In this case, an assertion on the THEN clause is useful to
2291 determine that 'a' is always 9 on that edge. However, an assertion
2292 on the ELSE clause would be unnecessary.
2294 4- If BB does not end in a conditional expression, then we recurse
2295 into BB's dominator children.
2297 At the end of the recursive traversal, every SSA name will have a
2298 list of locations where ASSERT_EXPRs should be added. When a new
2299 location for name N is found, it is registered by calling
2300 register_new_assert_for. That function keeps track of all the
2301 registered assertions to prevent adding unnecessary assertions.
2302 For instance, if a pointer P_4 is dereferenced more than once in a
2303 dominator tree, only the location dominating all the dereference of
2304 P_4 will receive an ASSERT_EXPR.
2306 If this function returns true, then it means that there are names
2307 for which we need to generate ASSERT_EXPRs. Those assertions are
2308 inserted by process_assert_insertions.
2310 TODO. Handle SWITCH_EXPR. */
2313 find_assert_locations (basic_block bb)
2315 block_stmt_iterator si;
2320 if (TEST_BIT (blocks_visited, bb->index))
2323 SET_BIT (blocks_visited, bb->index);
2325 need_assert = false;
2327 /* Traverse all PHI nodes in BB marking used operands. */
2328 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2330 use_operand_p arg_p;
2333 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
2335 tree arg = USE_FROM_PTR (arg_p);
2336 if (TREE_CODE (arg) == SSA_NAME)
2338 gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
2339 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
2344 /* Traverse all the statements in BB marking used names and looking
2345 for statements that may infer assertions for their used operands. */
2347 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2352 stmt = bsi_stmt (si);
2354 /* See if we can derive an assertion for any of STMT's operands. */
2355 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
2358 enum tree_code comp_code;
2360 /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside
2361 the sub-graph of a conditional block, when we return from
2362 this recursive walk, our parent will use the
2363 FOUND_IN_SUBGRAPH bitset to determine if one of the
2364 operands it was looking for was present in the sub-graph. */
2365 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2367 /* If OP is used only once, namely in this STMT, don't
2368 bother creating an ASSERT_EXPR for it. Such an
2369 ASSERT_EXPR would do nothing but increase compile time.
2370 Experiments show that with this simple check, we can save
2371 more than 20% of ASSERT_EXPRs. */
2372 if (has_single_use (op))
2375 /* If OP is used in such a way that we can infer a value
2376 range for it, and we don't find a previous assertion for
2377 it, create a new assertion location node for OP. */
2378 if (infer_value_range (stmt, op, &comp_code, &value))
2380 register_new_assert_for (op, comp_code, value, bb, NULL, si);
2385 /* Remember the last statement of the block. */
2389 /* If BB's last statement is a conditional expression
2390 involving integer operands, recurse into each of the sub-graphs
2391 rooted at BB to determine if we need to add ASSERT_EXPRs. */
2393 && TREE_CODE (last) == COND_EXPR
2394 && !fp_predicate (COND_EXPR_COND (last))
2395 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
2396 need_assert |= find_conditional_asserts (bb);
2398 /* Recurse into the dominator children of BB. */
2399 for (son = first_dom_son (CDI_DOMINATORS, bb);
2401 son = next_dom_son (CDI_DOMINATORS, son))
2402 need_assert |= find_assert_locations (son);
2408 /* Create an ASSERT_EXPR for NAME and insert it in the location
2409 indicated by LOC. Return true if we made any edge insertions. */
2412 process_assert_insertions_for (tree name, assert_locus_t loc)
2414 /* Build the comparison expression NAME_i COMP_CODE VAL. */
2415 tree stmt, cond, assert_expr;
2419 cond = build (loc->comp_code, boolean_type_node, name, loc->val);
2420 assert_expr = build_assert_expr_for (cond, name);
2424 /* We have been asked to insert the assertion on an edge. This
2425 is used only by COND_EXPR and SWITCH_EXPR assertions. */
2426 #if defined ENABLE_CHECKING
2427 gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
2428 || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
2431 bsi_insert_on_edge (loc->e, assert_expr);
2435 /* Otherwise, we can insert right after LOC->SI iff the
2436 statement must not be the last statement in the block. */
2437 stmt = bsi_stmt (loc->si);
2438 if (!stmt_ends_bb_p (stmt))
2440 bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
2444 /* If STMT must be the last statement in BB, we can only insert new
2445 assertions on the non-abnormal edge out of BB. Note that since
2446 STMT is not control flow, there may only be one non-abnormal edge
2448 FOR_EACH_EDGE (e, ei, loc->bb->succs)
2449 if (!(e->flags & EDGE_ABNORMAL))
2451 bsi_insert_on_edge (e, assert_expr);
2459 /* Process all the insertions registered for every name N_i registered
2460 in NEED_ASSERT_FOR. The list of assertions to be inserted are
2461 found in ASSERTS_FOR[i]. */
2464 process_assert_insertions (void)
2468 bool update_edges_p = false;
2469 int num_asserts = 0;
2471 if (dump_file && (dump_flags & TDF_DETAILS))
2472 dump_all_asserts (dump_file);
2474 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2476 assert_locus_t loc = asserts_for[i];
2481 assert_locus_t next = loc->next;
2482 update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
2490 bsi_commit_edge_inserts ();
2492 if (dump_file && (dump_flags & TDF_STATS))
2493 fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
2498 /* Traverse the flowgraph looking for conditional jumps to insert range
2499 expressions. These range expressions are meant to provide information
2500 to optimizations that need to reason in terms of value ranges. They
2501 will not be expanded into RTL. For instance, given:
2510 this pass will transform the code into:
2516 x = ASSERT_EXPR <x, x < y>
2521 y = ASSERT_EXPR <y, x <= y>
2525 The idea is that once copy and constant propagation have run, other
2526 optimizations will be able to determine what ranges of values can 'x'
2527 take in different paths of the code, simply by checking the reaching
2528 definition of 'x'. */
2531 insert_range_assertions (void)
2537 found_in_subgraph = sbitmap_alloc (num_ssa_names);
2538 sbitmap_zero (found_in_subgraph);
2540 blocks_visited = sbitmap_alloc (last_basic_block);
2541 sbitmap_zero (blocks_visited);
2543 need_assert_for = BITMAP_ALLOC (NULL);
2544 asserts_for = xmalloc (num_ssa_names * sizeof (assert_locus_t));
2545 memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t));
2547 calculate_dominance_info (CDI_DOMINATORS);
2549 update_ssa_p = false;
2550 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2551 if (find_assert_locations (e->dest))
2552 update_ssa_p = true;
2556 process_assert_insertions ();
2557 update_ssa (TODO_update_ssa_no_phi);
2560 if (dump_file && (dump_flags & TDF_DETAILS))
2562 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
2563 dump_function_to_file (current_function_decl, dump_file, dump_flags);
2566 sbitmap_free (found_in_subgraph);
2568 BITMAP_FREE (need_assert_for);
2572 /* Convert range assertion expressions into the implied copies.
2574 FIXME, this will eventually lead to copy propagation removing the
2575 names that had useful range information attached to them. For
2576 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
2577 then N_i will have the range [3, +INF].
2579 However, by converting the assertion into the implied copy
2580 operation N_i = N_j, we will then copy-propagate N_j into the uses
2581 of N_i and lose the range information. We may want to hold on to
2582 ASSERT_EXPRs a little while longer as the ranges could be used in
2583 things like jump threading.
2585 The problem with keeping ASSERT_EXPRs around is that passes after
2586 VRP need to handle them appropriately. */
2589 remove_range_assertions (void)
2592 block_stmt_iterator si;
2595 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2597 tree stmt = bsi_stmt (si);
2599 if (TREE_CODE (stmt) == MODIFY_EXPR
2600 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
2602 tree rhs = TREE_OPERAND (stmt, 1);
2603 tree cond = fold (ASSERT_EXPR_COND (rhs));
2604 gcc_assert (cond != boolean_false_node);
2605 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
2612 /* Return true if STMT is interesting for VRP. */
2615 stmt_interesting_for_vrp (tree stmt)
2617 if (TREE_CODE (stmt) == PHI_NODE
2618 && is_gimple_reg (PHI_RESULT (stmt))
2619 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
2620 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
2622 else if (TREE_CODE (stmt) == MODIFY_EXPR)
2624 tree lhs = TREE_OPERAND (stmt, 0);
2626 if (TREE_CODE (lhs) == SSA_NAME
2627 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2628 || POINTER_TYPE_P (TREE_TYPE (lhs)))
2629 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
2632 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
2639 /* Initialize local data structures for VRP. Return true if VRP
2640 is worth running (i.e. if we found any statements that could
2641 benefit from range information). */
2644 vrp_initialize (void)
2648 vr_value = xmalloc (num_ssa_names * sizeof (value_range_t *));
2649 memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *));
2653 block_stmt_iterator si;
2656 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2658 if (!stmt_interesting_for_vrp (phi))
2660 tree lhs = PHI_RESULT (phi);
2661 set_value_range_to_varying (get_value_range (lhs));
2662 DONT_SIMULATE_AGAIN (phi) = true;
2665 DONT_SIMULATE_AGAIN (phi) = false;
2668 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2670 tree stmt = bsi_stmt (si);
2672 if (!stmt_interesting_for_vrp (stmt))
2676 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
2677 set_value_range_to_varying (get_value_range (def));
2678 DONT_SIMULATE_AGAIN (stmt) = true;
2682 DONT_SIMULATE_AGAIN (stmt) = false;
2689 /* Visit assignment STMT. If it produces an interesting range, record
2690 the SSA name in *OUTPUT_P. */
2692 static enum ssa_prop_result
2693 vrp_visit_assignment (tree stmt, tree *output_p)
2698 lhs = TREE_OPERAND (stmt, 0);
2699 rhs = TREE_OPERAND (stmt, 1);
2701 /* We only keep track of ranges in integral and pointer types. */
2702 if (TREE_CODE (lhs) == SSA_NAME
2703 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2704 || POINTER_TYPE_P (TREE_TYPE (lhs))))
2707 value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2709 extract_range_from_expr (&new_vr, rhs);
2711 /* If STMT is inside a loop, we may be able to know something
2712 else about the range of LHS by examining scalar evolution
2714 if (cfg_loops && (l = loop_containing_stmt (stmt)))
2715 adjust_range_with_scev (&new_vr, l, lhs);
2717 if (update_value_range (lhs, &new_vr))
2721 if (dump_file && (dump_flags & TDF_DETAILS))
2723 fprintf (dump_file, "Found new range for ");
2724 print_generic_expr (dump_file, lhs, 0);
2725 fprintf (dump_file, ": ");
2726 dump_value_range (dump_file, &new_vr);
2727 fprintf (dump_file, "\n\n");
2730 if (new_vr.type == VR_VARYING)
2731 return SSA_PROP_VARYING;
2733 return SSA_PROP_INTERESTING;
2736 return SSA_PROP_NOT_INTERESTING;
2739 /* Every other statement produces no useful ranges. */
2740 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
2741 set_value_range_to_varying (get_value_range (def));
2743 return SSA_PROP_VARYING;
2747 /* Compare all the value ranges for names equivalent to VAR with VAL
2748 using comparison code COMP. Return the same value returned by
2749 compare_range_with_value. */
2752 compare_name_with_value (enum tree_code comp, tree var, tree val)
2759 t = retval = NULL_TREE;
2761 /* Get the set of equivalences for VAR. */
2762 e = get_value_range (var)->equiv;
2764 /* Add VAR to its own set of equivalences so that VAR's value range
2765 is processed by this loop (otherwise, we would have to replicate
2766 the body of the loop just to check VAR's value range). */
2767 bitmap_set_bit (e, SSA_NAME_VERSION (var));
2769 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
2771 value_range_t equiv_vr = *(vr_value[i]);
2773 /* If name N_i does not have a valid range, use N_i as its own
2774 range. This allows us to compare against names that may
2775 have N_i in their ranges. */
2776 if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
2778 equiv_vr.type = VR_RANGE;
2779 equiv_vr.min = ssa_name (i);
2780 equiv_vr.max = ssa_name (i);
2783 t = compare_range_with_value (comp, &equiv_vr, val);
2786 /* All the ranges should compare the same against VAL. */
2787 gcc_assert (retval == NULL || t == retval);
2792 /* Remove VAR from its own equivalence set. */
2793 bitmap_clear_bit (e, SSA_NAME_VERSION (var));
2798 /* We couldn't find a non-NULL value for the predicate. */
2803 /* Given a comparison code COMP and names N1 and N2, compare all the
2804 ranges equivalent to N1 against all the ranges equivalente to N2
2805 to determine the value of N1 COMP N2. Return the same value
2806 returned by compare_ranges. */
2809 compare_names (enum tree_code comp, tree n1, tree n2)
2813 bitmap_iterator bi1, bi2;
2816 /* Compare the ranges of every name equivalent to N1 against the
2817 ranges of every name equivalent to N2. */
2818 e1 = get_value_range (n1)->equiv;
2819 e2 = get_value_range (n2)->equiv;
2821 /* Add N1 and N2 to their own set of equivalences to avoid
2822 duplicating the body of the loop just to check N1 and N2
2824 bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
2825 bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
2827 /* If the equivalence sets have a common intersection, then the two
2828 names can be compared without checking their ranges. */
2829 if (bitmap_intersect_p (e1, e2))
2831 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2832 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2834 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
2836 : boolean_false_node;
2839 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2840 N2 to their own set of equivalences to avoid duplicating the body
2841 of the loop just to check N1 and N2 ranges. */
2842 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
2844 value_range_t vr1 = *(vr_value[i1]);
2846 /* If the range is VARYING or UNDEFINED, use the name itself. */
2847 if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
2849 vr1.type = VR_RANGE;
2850 vr1.min = ssa_name (i1);
2851 vr1.max = ssa_name (i1);
2854 t = retval = NULL_TREE;
2855 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
2857 value_range_t vr2 = *(vr_value[i2]);
2859 if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
2861 vr2.type = VR_RANGE;
2862 vr2.min = ssa_name (i2);
2863 vr2.max = ssa_name (i2);
2866 t = compare_ranges (comp, &vr1, &vr2);
2869 /* All the ranges in the equivalent sets should compare
2871 gcc_assert (retval == NULL || t == retval);
2878 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2879 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2884 /* None of the equivalent ranges are useful in computing this
2886 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2887 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2892 /* Given a conditional predicate COND, try to determine if COND yields
2893 true or false based on the value ranges of its operands. Return
2894 BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
2895 BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
2896 NULL if the conditional cannot be evaluated at compile time.
2898 If USE_EQUIV_P is true, the ranges of all the names equivalent with
2899 the operands in COND are used when trying to compute its value.
2900 This is only used during final substitution. During propagation,
2901 we only check the range of each variable and not its equivalents. */
2904 vrp_evaluate_conditional (tree cond, bool use_equiv_p)
2906 gcc_assert (TREE_CODE (cond) == SSA_NAME
2907 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
2909 if (TREE_CODE (cond) == SSA_NAME)
2915 retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node);
2918 value_range_t *vr = get_value_range (cond);
2919 retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node);
2922 /* If COND has a known boolean range, return it. */
2926 /* Otherwise, if COND has a symbolic range of exactly one value,
2928 vr = get_value_range (cond);
2929 if (vr->type == VR_RANGE && vr->min == vr->max)
2934 tree op0 = TREE_OPERAND (cond, 0);
2935 tree op1 = TREE_OPERAND (cond, 1);
2937 /* We only deal with integral and pointer types. */
2938 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
2939 && !POINTER_TYPE_P (TREE_TYPE (op0)))
2944 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
2945 return compare_names (TREE_CODE (cond), op0, op1);
2946 else if (TREE_CODE (op0) == SSA_NAME)
2947 return compare_name_with_value (TREE_CODE (cond), op0, op1);
2948 else if (TREE_CODE (op1) == SSA_NAME)
2949 return compare_name_with_value (
2950 opposite_comparison (TREE_CODE (cond)), op1, op0);
2954 value_range_t *vr0, *vr1;
2956 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
2957 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
2960 return compare_ranges (TREE_CODE (cond), vr0, vr1);
2961 else if (vr0 && vr1 == NULL)
2962 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
2963 else if (vr0 == NULL && vr1)
2964 return compare_range_with_value (
2965 opposite_comparison (TREE_CODE (cond)), vr1, op0);
2969 /* Anything else cannot be computed statically. */
2974 /* Visit conditional statement STMT. If we can determine which edge
2975 will be taken out of STMT's basic block, record it in
2976 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
2977 SSA_PROP_VARYING. */
2979 static enum ssa_prop_result
2980 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
2984 *taken_edge_p = NULL;
2986 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
2987 add ASSERT_EXPRs for them. */
2988 if (TREE_CODE (stmt) == SWITCH_EXPR)
2989 return SSA_PROP_VARYING;
2991 cond = COND_EXPR_COND (stmt);
2993 if (dump_file && (dump_flags & TDF_DETAILS))
2998 fprintf (dump_file, "\nVisiting conditional with predicate: ");
2999 print_generic_expr (dump_file, cond, 0);
3000 fprintf (dump_file, "\nWith known ranges\n");
3002 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
3004 fprintf (dump_file, "\t");
3005 print_generic_expr (dump_file, use, 0);
3006 fprintf (dump_file, ": ");
3007 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
3010 fprintf (dump_file, "\n");
3013 /* Compute the value of the predicate COND by checking the known
3014 ranges of each of its operands.
3016 Note that we cannot evaluate all the equivalent ranges here
3017 because those ranges may not yet be final and with the current
3018 propagation strategy, we cannot determine when the value ranges
3019 of the names in the equivalence set have changed.
3021 For instance, given the following code fragment
3025 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
3029 Assume that on the first visit to i_14, i_5 has the temporary
3030 range [8, 8] because the second argument to the PHI function is
3031 not yet executable. We derive the range ~[0, 0] for i_14 and the
3032 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
3033 the first time, since i_14 is equivalent to the range [8, 8], we
3034 determine that the predicate is always false.
3036 On the next round of propagation, i_13 is determined to be
3037 VARYING, which causes i_5 to drop down to VARYING. So, another
3038 visit to i_14 is scheduled. In this second visit, we compute the
3039 exact same range and equivalence set for i_14, namely ~[0, 0] and
3040 { i_5 }. But we did not have the previous range for i_5
3041 registered, so vrp_visit_assignment thinks that the range for
3042 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
3043 is not visited again, which stops propagation from visiting
3044 statements in the THEN clause of that if().
3046 To properly fix this we would need to keep the previous range
3047 value for the names in the equivalence set. This way we would've
3048 discovered that from one visit to the other i_5 changed from
3049 range [8, 8] to VR_VARYING.
3051 However, fixing this apparent limitation may not be worth the
3052 additional checking. Testing on several code bases (GCC, DLV,
3053 MICO, TRAMP3D and SPEC2000) showed that doing this results in
3054 4 more predicates folded in SPEC. */
3055 val = vrp_evaluate_conditional (cond, false);
3057 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
3059 if (dump_file && (dump_flags & TDF_DETAILS))
3061 fprintf (dump_file, "\nPredicate evaluates to: ");
3062 if (val == NULL_TREE)
3063 fprintf (dump_file, "DON'T KNOW\n");
3065 print_generic_stmt (dump_file, val, 0);
3068 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
3072 /* Evaluate statement STMT. If the statement produces a useful range,
3073 return SSA_PROP_INTERESTING and record the SSA name with the
3074 interesting range into *OUTPUT_P.
3076 If STMT is a conditional branch and we can determine its truth
3077 value, the taken edge is recorded in *TAKEN_EDGE_P.
3079 If STMT produces a varying value, return SSA_PROP_VARYING. */
3081 static enum ssa_prop_result
3082 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
3088 if (dump_file && (dump_flags & TDF_DETAILS))
3090 fprintf (dump_file, "\nVisiting statement:\n");
3091 print_generic_stmt (dump_file, stmt, dump_flags);
3092 fprintf (dump_file, "\n");
3095 ann = stmt_ann (stmt);
3096 if (TREE_CODE (stmt) == MODIFY_EXPR
3097 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3098 return vrp_visit_assignment (stmt, output_p);
3099 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3100 return vrp_visit_cond_stmt (stmt, taken_edge_p);
3102 /* All other statements produce nothing of interest for VRP, so mark
3103 their outputs varying and prevent further simulation. */
3104 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3105 set_value_range_to_varying (get_value_range (def));
3107 return SSA_PROP_VARYING;
3111 /* Meet operation for value ranges. Given two value ranges VR0 and
3112 VR1, store in VR0 the result of meeting VR0 and VR1.
3114 The meeting rules are as follows:
3116 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
3118 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
3119 union of VR0 and VR1. */
3122 vrp_meet (value_range_t *vr0, value_range_t *vr1)
3124 if (vr0->type == VR_UNDEFINED)
3126 copy_value_range (vr0, vr1);
3130 if (vr1->type == VR_UNDEFINED)
3132 /* Nothing to do. VR0 already has the resulting range. */
3136 if (vr0->type == VR_VARYING)
3138 /* Nothing to do. VR0 already has the resulting range. */
3142 if (vr1->type == VR_VARYING)
3144 set_value_range_to_varying (vr0);
3148 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
3150 /* If VR0 and VR1 have a non-empty intersection, compute the
3151 union of both ranges. */
3152 if (value_ranges_intersect_p (vr0, vr1))
3157 /* The lower limit of the new range is the minimum of the
3158 two ranges. If they cannot be compared, the result is
3160 cmp = compare_values (vr0->min, vr1->min);
3161 if (cmp == 0 || cmp == 1)
3167 set_value_range_to_varying (vr0);
3171 /* Similarly, the upper limit of the new range is the
3172 maximum of the two ranges. If they cannot be compared,
3173 the result is VARYING. */
3174 cmp = compare_values (vr0->max, vr1->max);
3175 if (cmp == 0 || cmp == -1)
3181 set_value_range_to_varying (vr0);
3185 /* The resulting set of equivalencies is the intersection of
3187 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3188 bitmap_and_into (vr0->equiv, vr1->equiv);
3190 set_value_range (vr0, vr0->type, min, max, vr0->equiv);
3195 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3197 /* Two anti-ranges meet only if they are both identical. */
3198 if (compare_values (vr0->min, vr1->min) == 0
3199 && compare_values (vr0->max, vr1->max) == 0
3200 && compare_values (vr0->min, vr0->max) == 0)
3202 /* The resulting set of equivalencies is the intersection of
3204 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3205 bitmap_and_into (vr0->equiv, vr1->equiv);
3210 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
3212 /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4]
3213 meet only if the ranges have an empty intersection. The
3214 result of the meet operation is the anti-range. */
3215 if (!symbolic_range_p (vr0)
3216 && !symbolic_range_p (vr1)
3217 && !value_ranges_intersect_p (vr0, vr1))
3219 if (vr1->type == VR_ANTI_RANGE)
3220 copy_value_range (vr0, vr1);
3231 /* The two range VR0 and VR1 do not meet. Before giving up and
3232 setting the result to VARYING, see if we can at least derive a
3233 useful anti-range. */
3234 if (!symbolic_range_p (vr0)
3235 && !range_includes_zero_p (vr0)
3236 && !symbolic_range_p (vr1)
3237 && !range_includes_zero_p (vr1))
3238 set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
3240 set_value_range_to_varying (vr0);
3244 /* Visit all arguments for PHI node PHI that flow through executable
3245 edges. If a valid value range can be derived from all the incoming
3246 value ranges, set a new range for the LHS of PHI. */
3248 static enum ssa_prop_result
3249 vrp_visit_phi_node (tree phi)
3252 tree lhs = PHI_RESULT (phi);
3253 value_range_t *lhs_vr = get_value_range (lhs);
3254 value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3256 copy_value_range (&vr_result, lhs_vr);
3258 if (dump_file && (dump_flags & TDF_DETAILS))
3260 fprintf (dump_file, "\nVisiting PHI node: ");
3261 print_generic_expr (dump_file, phi, dump_flags);
3264 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
3266 edge e = PHI_ARG_EDGE (phi, i);
3268 if (dump_file && (dump_flags & TDF_DETAILS))
3271 "\n Argument #%d (%d -> %d %sexecutable)\n",
3272 i, e->src->index, e->dest->index,
3273 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
3276 if (e->flags & EDGE_EXECUTABLE)
3278 tree arg = PHI_ARG_DEF (phi, i);
3279 value_range_t vr_arg;
3281 if (TREE_CODE (arg) == SSA_NAME)
3282 vr_arg = *(get_value_range (arg));
3285 vr_arg.type = VR_RANGE;
3288 vr_arg.equiv = NULL;
3291 if (dump_file && (dump_flags & TDF_DETAILS))
3293 fprintf (dump_file, "\t");
3294 print_generic_expr (dump_file, arg, dump_flags);
3295 fprintf (dump_file, "\n\tValue: ");
3296 dump_value_range (dump_file, &vr_arg);
3297 fprintf (dump_file, "\n");
3300 vrp_meet (&vr_result, &vr_arg);
3302 if (vr_result.type == VR_VARYING)
3307 if (vr_result.type == VR_VARYING)
3310 /* To prevent infinite iterations in the algorithm, derive ranges
3311 when the new value is slightly bigger or smaller than the
3313 if (lhs_vr->type == VR_RANGE)
3315 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
3317 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
3318 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
3320 /* If the new minimum is smaller or larger than the previous
3321 one, go all the way to -INF. In the first case, to avoid
3322 iterating millions of times to reach -INF, and in the
3323 other case to avoid infinite bouncing between different
3325 if (cmp_min > 0 || cmp_min < 0)
3326 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
3328 /* Similarly, if the new maximum is smaller or larger than
3329 the previous one, go all the way to +INF. */
3330 if (cmp_max < 0 || cmp_max > 0)
3331 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
3333 /* If we ended up with a (-INF, +INF) range, set it to
3335 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
3336 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
3341 /* If the new range is different than the previous value, keep
3343 if (update_value_range (lhs, &vr_result))
3344 return SSA_PROP_INTERESTING;
3346 /* Nothing changed, don't add outgoing edges. */
3347 return SSA_PROP_NOT_INTERESTING;
3349 /* No match found. Set the LHS to VARYING. */
3351 set_value_range_to_varying (lhs_vr);
3352 return SSA_PROP_VARYING;
3356 /* Traverse all the blocks folding conditionals with known ranges. */
3362 prop_value_t *single_val_range;
3363 bool do_value_subst_p;
3367 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
3368 dump_all_value_ranges (dump_file);
3369 fprintf (dump_file, "\n");
3372 /* We may have ended with ranges that have exactly one value. Those
3373 values can be substituted as any other copy/const propagated
3374 value using substitute_and_fold. */
3375 single_val_range = xmalloc (num_ssa_names * sizeof (*single_val_range));
3376 memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range));
3378 do_value_subst_p = false;
3379 for (i = 0; i < num_ssa_names; i++)
3381 && vr_value[i]->type == VR_RANGE
3382 && vr_value[i]->min == vr_value[i]->max)
3384 single_val_range[i].value = vr_value[i]->min;
3385 do_value_subst_p = true;
3388 if (!do_value_subst_p)
3390 /* We found no single-valued ranges, don't waste time trying to
3391 do single value substitution in substitute_and_fold. */
3392 free (single_val_range);
3393 single_val_range = NULL;
3396 substitute_and_fold (single_val_range, true);
3398 /* Free allocated memory. */
3399 for (i = 0; i < num_ssa_names; i++)
3402 BITMAP_FREE (vr_value[i]->equiv);
3406 free (single_val_range);
3411 /* Main entry point to VRP (Value Range Propagation). This pass is
3412 loosely based on J. R. C. Patterson, ``Accurate Static Branch
3413 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
3414 Programming Language Design and Implementation, pp. 67-78, 1995.
3415 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
3417 This is essentially an SSA-CCP pass modified to deal with ranges
3418 instead of constants.
3420 While propagating ranges, we may find that two or more SSA name
3421 have equivalent, though distinct ranges. For instance,
3424 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0>
3426 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
3430 In the code above, pointer p_5 has range [q_2, q_2], but from the
3431 code we can also determine that p_5 cannot be NULL and, if q_2 had
3432 a non-varying range, p_5's range should also be compatible with it.
3434 These equivalencies are created by two expressions: ASSERT_EXPR and
3435 copy operations. Since p_5 is an assertion on p_4, and p_4 was the
3436 result of another assertion, then we can use the fact that p_5 and
3437 p_4 are equivalent when evaluating p_5's range.
3439 Together with value ranges, we also propagate these equivalencies
3440 between names so that we can take advantage of information from
3441 multiple ranges when doing final replacement. Note that this
3442 equivalency relation is transitive but not symmetric.
3444 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
3445 cannot assert that q_2 is equivalent to p_5 because q_2 may be used
3446 in contexts where that assertion does not hold (e.g., in line 6).
3448 TODO, the main difference between this pass and Patterson's is that
3449 we do not propagate edge probabilities. We only compute whether
3450 edges can be taken or not. That is, instead of having a spectrum
3451 of jump probabilities between 0 and 1, we only deal with 0, 1 and
3452 DON'T KNOW. In the future, it may be worthwhile to propagate
3453 probabilities to aid branch prediction. */
3458 insert_range_assertions ();
3460 cfg_loops = loop_optimizer_init (NULL);
3462 scev_initialize (cfg_loops);
3465 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
3471 loop_optimizer_finalize (cfg_loops, NULL);
3472 current_loops = NULL;
3475 remove_range_assertions ();
3481 return flag_tree_vrp != 0;
3484 struct tree_opt_pass pass_vrp =
3487 gate_vrp, /* gate */
3488 execute_vrp, /* execute */
3491 0, /* static_pass_number */
3492 TV_TREE_VRP, /* tv_id */
3493 PROP_ssa | PROP_alias, /* properties_required */
3494 0, /* properties_provided */
3495 0, /* properties_destroyed */
3496 0, /* todo_flags_start */
3501 | TODO_update_ssa, /* todo_flags_finish */