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;
1911 /* Return true if OP is the result of an ASSERT_EXPR that tests the
1912 same condition as COND. */
1915 has_assert_expr (tree op, tree cond)
1917 tree def_stmt = SSA_NAME_DEF_STMT (op);
1918 tree assert_expr, other_cond, other_op;
1920 /* If OP was not generated by an ASSERT_EXPR, return false. */
1921 if (TREE_CODE (def_stmt) != MODIFY_EXPR
1922 || TREE_CODE (TREE_OPERAND (def_stmt, 1)) != ASSERT_EXPR)
1925 assert_expr = TREE_OPERAND (def_stmt, 1);
1926 other_cond = ASSERT_EXPR_COND (assert_expr);
1927 other_op = ASSERT_EXPR_VAR (assert_expr);
1929 if (TREE_CODE (cond) == TREE_CODE (other_cond))
1933 /* If COND is not a comparison predicate, something is wrong. */
1934 gcc_assert (COMPARISON_CLASS_P (cond));
1936 /* Note that we only need to compare against one of the operands
1939 Suppose that we are about to insert the assertion ASSERT_EXPR
1940 <x_4, x_4 != 0> and the defining statement for x_4 is x_4 =
1941 ASSERT_EXPR <x_3, x_3 != 0>.
1943 In this case, we don't really want to insert a new
1944 ASSERT_EXPR for x_4 because that would be redundant. We
1945 already know that x_4 is not 0. So, when comparing the
1946 conditionals 'x_3 != 0' and 'x_4 != 0', we don't want to
1947 compare x_3 and x_4, we just want to compare the predicate's
1948 code (!=) and the other operand (0). */
1949 if (TREE_OPERAND (cond, 0) == op)
1950 t1 = TREE_OPERAND (cond, 1);
1952 t1 = TREE_OPERAND (cond, 0);
1954 if (TREE_OPERAND (other_cond, 0) == other_op)
1955 t2 = TREE_OPERAND (other_cond, 1);
1957 t2 = TREE_OPERAND (other_cond, 0);
1959 return (t1 == t2 || operand_equal_p (t1, t2, 0));
1966 /* Traverse all the statements in block BB looking for used variables.
1967 Variables used in BB are added to bitmap FOUND. The algorithm
1968 works in three main parts:
1970 1- For every statement S in BB, all the variables used by S are
1971 added to bitmap FOUND.
1973 2- If statement S uses an operand N in a way that exposes a known
1974 value range for N, then if N was not already generated by an
1975 ASSERT_EXPR, create a new ASSERT_EXPR for N. For instance, if N
1976 is a pointer and the statement dereferences it, we can assume
1979 3- COND_EXPRs are a special case of #2. We can derive range
1980 information from the predicate but need to insert different
1981 ASSERT_EXPRs for each of the sub-graphs rooted at the
1982 conditional block. If the last statement of BB is a conditional
1983 expression of the form 'X op Y', then
1985 a) Remove X and Y from the set FOUND.
1987 b) If the conditional dominates its THEN_CLAUSE sub-graph,
1988 recurse into it. On return, if X and/or Y are marked in
1989 FOUND, then an ASSERT_EXPR is added for the corresponding
1992 c) Repeat step (b) on the ELSE_CLAUSE.
1994 d) Mark X and Y in FOUND.
1996 4- If BB does not end in a conditional expression, then we recurse
1997 into BB's dominator children.
1999 At the end of the recursive traversal, ASSERT_EXPRs will have been
2000 added to the edges of COND_EXPR blocks that have sub-graphs using
2001 one or both predicate operands. For instance,
2008 In this case, an assertion on the THEN clause is useful to
2009 determine that 'a' is always 9 on that edge. However, an assertion
2010 on the ELSE clause would be unnecessary.
2012 On exit from this function, all the names created by the newly
2013 inserted ASSERT_EXPRs need to be added to the SSA web by rewriting
2014 the SSA names that they replace.
2016 TODO. Handle SWITCH_EXPR. */
2019 maybe_add_assert_expr (basic_block bb)
2021 block_stmt_iterator si;
2025 /* Step 1. Mark all the SSA names used in BB in bitmap FOUND. */
2028 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2033 stmt = bsi_stmt (si);
2035 /* Mark all the SSA names used by STMT in bitmap FOUND. If STMT
2036 is inside the sub-graph of a conditional block, when we
2037 return from this recursive walk, our parent will use the
2038 FOUND bitset to determine if one of the operands it was
2039 looking for was present in the sub-graph. */
2040 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
2044 /* If OP is used only once, namely in this STMT, don't
2045 bother inserting an ASSERT_EXPR for it. Such an
2046 ASSERT_EXPR would do nothing but increase compile time.
2047 Experiments show that with this simple check, we can save
2048 more than 20% of ASSERT_EXPRs. */
2049 if (has_single_use (op))
2052 SET_BIT (found, SSA_NAME_VERSION (op));
2054 cond = infer_value_range (stmt, op);
2058 /* Step 2. If OP is used in such a way that we can infer a
2059 value range for it, create a new ASSERT_EXPR for OP
2060 (unless OP already has an ASSERT_EXPR). */
2061 gcc_assert (!is_ctrl_stmt (stmt));
2063 if (has_assert_expr (op, cond))
2066 if (!stmt_ends_bb_p (stmt))
2068 /* If STMT does not end the block, we can insert the new
2069 assertion right after it. */
2070 tree t = build_assert_expr_for (cond, op);
2071 bsi_insert_after (&si, t, BSI_NEW_STMT);
2076 /* STMT must be the last statement in BB. We can only
2077 insert new assertions on the non-abnormal edge out of
2078 BB. Note that since STMT is not control flow, there
2079 may only be one non-abnormal edge out of BB. */
2083 FOR_EACH_EDGE (e, ei, bb->succs)
2084 if (!(e->flags & EDGE_ABNORMAL))
2086 tree t = build_assert_expr_for (cond, op);
2087 bsi_insert_on_edge (e, t);
2094 /* Remember the last statement of the block. */
2098 /* Step 3. If BB's last statement is a conditional expression
2099 involving integer operands, recurse into each of the sub-graphs
2100 rooted at BB to determine if we need to add ASSERT_EXPRs.
2101 Notice that we only care about the first operand of the
2102 conditional. Adding assertions for both operands may actually
2103 hinder VRP. FIXME, add example. */
2105 && TREE_CODE (last) == COND_EXPR
2106 && !fp_predicate (COND_EXPR_COND (last))
2107 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
2115 cond = COND_EXPR_COND (last);
2117 /* Get just the first use operand. */
2118 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2120 gcc_assert (op != NULL);
2122 /* Do not attempt to infer anything in names that flow through
2124 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
2127 /* Remove the COND_EXPR operand from the FOUND bitmap.
2128 Otherwise, when we finish traversing each of the sub-graphs,
2129 we won't know whether the variables were found in the
2130 sub-graphs or if they had been found in a block upstream from
2132 RESET_BIT (found, SSA_NAME_VERSION (op));
2134 /* Look for uses of the operands in each of the sub-graphs
2135 rooted at BB. We need to check each of the outgoing edges
2136 separately, so that we know what kind of ASSERT_EXPR to
2138 FOR_EACH_EDGE (e, ei, bb->succs)
2140 /* If BB strictly dominates the sub-graph at E->DEST,
2143 && dominated_by_p (CDI_DOMINATORS, e->dest, bb))
2144 added |= maybe_add_assert_expr (e->dest);
2146 /* Once we traversed the sub-graph, check if any block inside
2147 used either of the predicate's operands. If so, add the
2148 appropriate ASSERT_EXPR. */
2149 if (TEST_BIT (found, SSA_NAME_VERSION (op)))
2151 /* We found a use of OP in the sub-graph rooted at
2152 E->DEST. Add an ASSERT_EXPR according to whether
2153 E goes to THEN_CLAUSE or ELSE_CLAUSE. */
2156 if (e->flags & EDGE_TRUE_VALUE)
2157 c = unshare_expr (cond);
2158 else if (e->flags & EDGE_FALSE_VALUE)
2159 c = invert_truthvalue (cond);
2163 t = build_assert_expr_for (c, op);
2164 bsi_insert_on_edge (e, t);
2169 /* Finally, mark all the COND_EXPR operands as found. */
2170 SET_BIT (found, SSA_NAME_VERSION (op));
2172 /* Recurse into the dominator children of BB that are not BB's
2173 immediate successors. Note that we have already visited BB's
2174 other dominator children above. */
2175 for (son = first_dom_son (CDI_DOMINATORS, bb);
2177 son = next_dom_son (CDI_DOMINATORS, son))
2179 if (find_edge (bb, son) == NULL)
2180 added |= maybe_add_assert_expr (son);
2185 /* Step 4. Recurse into the dominator children of BB. */
2188 for (son = first_dom_son (CDI_DOMINATORS, bb);
2190 son = next_dom_son (CDI_DOMINATORS, son))
2191 added |= maybe_add_assert_expr (son);
2199 void dump_asserts_for (FILE *, tree);
2200 void debug_asserts_for (tree);
2201 void dump_all_asserts (FILE *);
2202 void debug_all_asserts (void);
2204 /* Dump all the registered assertions for NAME to FILE. */
2207 dump_asserts_for (FILE *file, tree name)
2211 fprintf (file, "Assertions to be inserted for ");
2212 print_generic_expr (file, name, 0);
2213 fprintf (file, "\n");
2215 loc = asserts_for[SSA_NAME_VERSION (name)];
2218 fprintf (file, "\t");
2219 print_generic_expr (file, bsi_stmt (loc->si), 0);
2220 fprintf (file, "\n\tBB #%d", loc->bb->index);
2223 fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
2224 loc->e->dest->index);
2225 dump_edge_info (file, loc->e, 0);
2227 fprintf (file, "\n\tPREDICATE: ");
2228 print_generic_expr (file, name, 0);
2229 fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
2230 print_generic_expr (file, loc->val, 0);
2231 fprintf (file, "\n\n");
2235 fprintf (file, "\n");
2239 /* Dump all the registered assertions for NAME to stderr. */
2242 debug_asserts_for (tree name)
2244 dump_asserts_for (stderr, name);
2248 /* Dump all the registered assertions for all the names to FILE. */
2251 dump_all_asserts (FILE *file)
2256 fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
2257 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2258 dump_asserts_for (file, ssa_name (i));
2259 fprintf (file, "\n");
2263 /* Dump all the registered assertions for all the names to stderr. */
2266 debug_all_asserts (void)
2268 dump_all_asserts (stderr);
2272 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
2273 'NAME COMP_CODE VAL' at a location that dominates block BB or
2274 E->DEST, then register this location as a possible insertion point
2275 for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
2277 BB, E and SI provide the exact insertion point for the new
2278 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
2279 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
2280 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
2281 must not be NULL. */
2284 register_new_assert_for (tree name,
2285 enum tree_code comp_code,
2289 block_stmt_iterator si)
2291 assert_locus_t n, loc, last_loc;
2293 basic_block dest_bb;
2295 #if defined ENABLE_CHECKING
2296 gcc_assert (bb == NULL || e == NULL);
2299 gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
2300 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
2303 /* The new assertion A will be inserted at BB or E. We need to
2304 determine if the new location is dominated by a previously
2305 registered location for A. If we are doing an edge insertion,
2306 assume that A will be inserted at E->DEST. Note that this is not
2309 If E is a critical edge, it will be split. But even if E is
2310 split, the new block will dominate the same set of blocks that
2313 The reverse, however, is not true, blocks dominated by E->DEST
2314 will not be dominated by the new block created to split E. So,
2315 if the insertion location is on a critical edge, we will not use
2316 the new location to move another assertion previously registered
2317 at a block dominated by E->DEST. */
2318 dest_bb = (bb) ? bb : e->dest;
2320 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
2321 VAL at a block dominating DEST_BB, then we don't need to insert a new
2322 one. Similarly, if the same assertion already exists at a block
2323 dominated by DEST_BB and the new location is not on a critical
2324 edge, then update the existing location for the assertion (i.e.,
2325 move the assertion up in the dominance tree).
2327 Note, this is implemented as a simple linked list because there
2328 should not be more than a handful of assertions registered per
2329 name. If this becomes a performance problem, a table hashed by
2330 COMP_CODE and VAL could be implemented. */
2331 loc = asserts_for[SSA_NAME_VERSION (name)];
2336 if (loc->comp_code == comp_code
2338 || operand_equal_p (loc->val, val, 0)))
2340 /* If the assertion NAME COMP_CODE VAL has already been
2341 registered at a basic block that dominates DEST_BB, then
2342 we don't need to insert the same assertion again. Note
2343 that we don't check strict dominance here to avoid
2344 replicating the same assertion inside the same basic
2345 block more than once (e.g., when a pointer is
2346 dereferenced several times inside a block).
2348 An exception to this rule are edge insertions. If the
2349 new assertion is to be inserted on edge E, then it will
2350 dominate all the other insertions that we may want to
2351 insert in DEST_BB. So, if we are doing an edge
2352 insertion, don't do this dominance check. */
2354 && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
2357 /* Otherwise, if E is not a critical edge and DEST_BB
2358 dominates the existing location for the assertion, move
2359 the assertion up in the dominance tree by updating its
2360 location information. */
2361 if ((e == NULL || !EDGE_CRITICAL_P (e))
2362 && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
2371 /* Update the last node of the list and move to the next one. */
2376 /* If we didn't find an assertion already registered for
2377 NAME COMP_CODE VAL, add a new one at the end of the list of
2378 assertions associated with NAME. */
2379 n = xmalloc (sizeof (*n));
2383 n->comp_code = comp_code;
2390 asserts_for[SSA_NAME_VERSION (name)] = n;
2392 bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
2396 /* Try to register an edge assertion for SSA name NAME on edge E for
2397 the conditional jump pointed by SI. Return true if an assertion
2398 for NAME could be registered. */
2401 register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
2404 enum tree_code comp_code;
2406 stmt = bsi_stmt (si);
2408 /* Do not attempt to infer anything in names that flow through
2410 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
2413 /* If NAME was not found in the sub-graph reachable from E, then
2414 there's nothing to do. */
2415 if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
2418 /* We found a use of NAME in the sub-graph rooted at E->DEST.
2419 Register an assertion for NAME according to the value that NAME
2421 if (TREE_CODE (stmt) == COND_EXPR)
2423 /* If BB ends in a COND_EXPR then NAME then we should insert
2424 the original predicate on EDGE_TRUE_VALUE and the
2425 opposite predicate on EDGE_FALSE_VALUE. */
2426 tree cond = COND_EXPR_COND (stmt);
2427 bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
2429 /* Predicates may be a single SSA name or NAME OP VAL. */
2432 /* If the predicate is a name, it must be NAME, in which
2433 case we create the predicate NAME == true or
2434 NAME == false accordingly. */
2435 comp_code = EQ_EXPR;
2436 val = (is_else_edge) ? boolean_false_node : boolean_true_node;
2440 /* Otherwise, we have a comparison of the form NAME COMP VAL
2441 or VAL COMP NAME. */
2442 if (name == TREE_OPERAND (cond, 1))
2444 /* If the predicate is of the form VAL COMP NAME, flip
2445 COMP around because we need to register NAME as the
2446 first operand in the predicate. */
2447 comp_code = opposite_comparison (TREE_CODE (cond));
2448 val = TREE_OPERAND (cond, 0);
2452 /* The comparison is of the form NAME COMP VAL, so the
2453 comparison code remains unchanged. */
2454 comp_code = TREE_CODE (cond);
2455 val = TREE_OPERAND (cond, 1);
2458 /* If we are inserting the assertion on the ELSE edge, we
2459 need to invert the sign comparison. */
2461 comp_code = invert_tree_comparison (comp_code, 0);
2466 /* FIXME. Handle SWITCH_EXPR. */
2470 register_new_assert_for (name, comp_code, val, NULL, e, si);
2475 static bool find_assert_locations (basic_block bb);
2477 /* Determine whether the outgoing edges of BB should receive an
2478 ASSERT_EXPR for each of the operands of BB's last statement. The
2479 last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
2481 If any of the sub-graphs rooted at BB have an interesting use of
2482 the predicate operands, an assert location node is added to the
2483 list of assertions for the corresponding operands. */
2486 find_conditional_asserts (basic_block bb)
2489 block_stmt_iterator last_si;
2495 need_assert = false;
2496 last_si = bsi_last (bb);
2497 last = bsi_stmt (last_si);
2499 /* Look for uses of the operands in each of the sub-graphs
2500 rooted at BB. We need to check each of the outgoing edges
2501 separately, so that we know what kind of ASSERT_EXPR to
2503 FOR_EACH_EDGE (e, ei, bb->succs)
2508 /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
2509 Otherwise, when we finish traversing each of the sub-graphs, we
2510 won't know whether the variables were found in the sub-graphs or
2511 if they had been found in a block upstream from BB. */
2512 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2513 RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2515 /* Traverse the strictly dominated sub-graph rooted at E->DEST
2516 to determine if any of the operands in the conditional
2517 predicate are used. */
2519 need_assert |= find_assert_locations (e->dest);
2521 /* Register the necessary assertions for each operand in the
2522 conditional predicate. */
2523 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2524 need_assert |= register_edge_assert_for (op, e, last_si);
2527 /* Finally, indicate that we have found the operands in the
2529 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2530 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2536 /* Traverse all the statements in block BB looking for statements that
2537 may generate useful assertions for the SSA names in their operand.
2538 If a statement produces a useful assertion A for name N_i, then the
2539 list of assertions already generated for N_i is scanned to
2540 determine if A is actually needed.
2542 If N_i already had the assertion A at a location dominating the
2543 current location, then nothing needs to be done. Otherwise, the
2544 new location for A is recorded instead.
2546 1- For every statement S in BB, all the variables used by S are
2547 added to bitmap FOUND_IN_SUBGRAPH.
2549 2- If statement S uses an operand N in a way that exposes a known
2550 value range for N, then if N was not already generated by an
2551 ASSERT_EXPR, create a new assert location for N. For instance,
2552 if N is a pointer and the statement dereferences it, we can
2553 assume that N is not NULL.
2555 3- COND_EXPRs are a special case of #2. We can derive range
2556 information from the predicate but need to insert different
2557 ASSERT_EXPRs for each of the sub-graphs rooted at the
2558 conditional block. If the last statement of BB is a conditional
2559 expression of the form 'X op Y', then
2561 a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
2563 b) If the conditional is the only entry point to the sub-graph
2564 corresponding to the THEN_CLAUSE, recurse into it. On
2565 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
2566 an ASSERT_EXPR is added for the corresponding variable.
2568 c) Repeat step (b) on the ELSE_CLAUSE.
2570 d) Mark X and Y in FOUND_IN_SUBGRAPH.
2579 In this case, an assertion on the THEN clause is useful to
2580 determine that 'a' is always 9 on that edge. However, an assertion
2581 on the ELSE clause would be unnecessary.
2583 4- If BB does not end in a conditional expression, then we recurse
2584 into BB's dominator children.
2586 At the end of the recursive traversal, every SSA name will have a
2587 list of locations where ASSERT_EXPRs should be added. When a new
2588 location for name N is found, it is registered by calling
2589 register_new_assert_for. That function keeps track of all the
2590 registered assertions to prevent adding unnecessary assertions.
2591 For instance, if a pointer P_4 is dereferenced more than once in a
2592 dominator tree, only the location dominating all the dereference of
2593 P_4 will receive an ASSERT_EXPR.
2595 If this function returns true, then it means that there are names
2596 for which we need to generate ASSERT_EXPRs. Those assertions are
2597 inserted by process_assert_insertions.
2599 TODO. Handle SWITCH_EXPR. */
2602 find_assert_locations (basic_block bb)
2604 block_stmt_iterator si;
2609 if (TEST_BIT (blocks_visited, bb->index))
2612 SET_BIT (blocks_visited, bb->index);
2614 need_assert = false;
2616 /* Traverse all PHI nodes in BB marking used operands. */
2617 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2619 use_operand_p arg_p;
2622 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
2624 tree arg = USE_FROM_PTR (arg_p);
2625 if (TREE_CODE (arg) == SSA_NAME)
2627 gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
2628 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
2633 /* Traverse all the statements in BB marking used names and looking
2634 for statements that may infer assertions for their used operands. */
2636 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2641 stmt = bsi_stmt (si);
2643 /* See if we can derive an assertion for any of STMT's operands. */
2644 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
2647 enum tree_code comp_code;
2649 /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside
2650 the sub-graph of a conditional block, when we return from
2651 this recursive walk, our parent will use the
2652 FOUND_IN_SUBGRAPH bitset to determine if one of the
2653 operands it was looking for was present in the sub-graph. */
2654 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2656 /* If OP is used only once, namely in this STMT, don't
2657 bother creating an ASSERT_EXPR for it. Such an
2658 ASSERT_EXPR would do nothing but increase compile time.
2659 Experiments show that with this simple check, we can save
2660 more than 20% of ASSERT_EXPRs. */
2661 if (has_single_use (op))
2664 /* If OP is used in such a way that we can infer a value
2665 range for it, and we don't find a previous assertion for
2666 it, create a new assertion location node for OP. */
2667 if (infer_value_range (stmt, op, &comp_code, &value))
2669 register_new_assert_for (op, comp_code, value, bb, NULL, si);
2674 /* Remember the last statement of the block. */
2678 /* If BB's last statement is a conditional expression
2679 involving integer operands, recurse into each of the sub-graphs
2680 rooted at BB to determine if we need to add ASSERT_EXPRs. */
2682 && TREE_CODE (last) == COND_EXPR
2683 && !fp_predicate (COND_EXPR_COND (last))
2684 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
2685 need_assert |= find_conditional_asserts (bb);
2687 /* Recurse into the dominator children of BB. */
2688 for (son = first_dom_son (CDI_DOMINATORS, bb);
2690 son = next_dom_son (CDI_DOMINATORS, son))
2691 need_assert |= find_assert_locations (son);
2697 /* Create an ASSERT_EXPR for NAME and insert it in the location
2698 indicated by LOC. Return true if we made any edge insertions. */
2701 process_assert_insertions_for (tree name, assert_locus_t loc)
2703 /* Build the comparison expression NAME_i COMP_CODE VAL. */
2704 tree stmt, cond, assert_expr;
2708 cond = build (loc->comp_code, boolean_type_node, name, loc->val);
2709 assert_expr = build_assert_expr_for (cond, name);
2713 /* We have been asked to insert the assertion on an edge. This
2714 is used only by COND_EXPR and SWITCH_EXPR assertions. */
2715 #if defined ENABLE_CHECKING
2716 gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
2717 || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
2720 bsi_insert_on_edge (loc->e, assert_expr);
2724 /* Otherwise, we can insert right after LOC->SI iff the
2725 statement must not be the last statement in the block. */
2726 stmt = bsi_stmt (loc->si);
2727 if (!stmt_ends_bb_p (stmt))
2729 bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
2733 /* If STMT must be the last statement in BB, we can only insert new
2734 assertions on the non-abnormal edge out of BB. Note that since
2735 STMT is not control flow, there may only be one non-abnormal edge
2737 FOR_EACH_EDGE (e, ei, loc->bb->succs)
2738 if (!(e->flags & EDGE_ABNORMAL))
2740 bsi_insert_on_edge (e, assert_expr);
2748 /* Process all the insertions registered for every name N_i registered
2749 in NEED_ASSERT_FOR. The list of assertions to be inserted are
2750 found in ASSERTS_FOR[i]. */
2753 process_assert_insertions (void)
2757 bool update_edges_p = false;
2758 int num_asserts = 0;
2760 if (dump_file && (dump_flags & TDF_DETAILS))
2761 dump_all_asserts (dump_file);
2763 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2765 assert_locus_t loc = asserts_for[i];
2770 assert_locus_t next = loc->next;
2771 update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
2779 bsi_commit_edge_inserts ();
2781 if (dump_file && (dump_flags & TDF_STATS))
2782 fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
2787 /* Traverse the flowgraph looking for conditional jumps to insert range
2788 expressions. These range expressions are meant to provide information
2789 to optimizations that need to reason in terms of value ranges. They
2790 will not be expanded into RTL. For instance, given:
2799 this pass will transform the code into:
2805 x = ASSERT_EXPR <x, x < y>
2810 y = ASSERT_EXPR <y, x <= y>
2814 The idea is that once copy and constant propagation have run, other
2815 optimizations will be able to determine what ranges of values can 'x'
2816 take in different paths of the code, simply by checking the reaching
2817 definition of 'x'. */
2820 insert_range_assertions (void)
2826 found_in_subgraph = sbitmap_alloc (num_ssa_names);
2827 sbitmap_zero (found_in_subgraph);
2829 blocks_visited = sbitmap_alloc (last_basic_block);
2830 sbitmap_zero (blocks_visited);
2832 need_assert_for = BITMAP_ALLOC (NULL);
2833 asserts_for = xmalloc (num_ssa_names * sizeof (assert_locus_t));
2834 memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t));
2836 calculate_dominance_info (CDI_DOMINATORS);
2838 update_ssa_p = false;
2839 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2840 if (find_assert_locations (e->dest))
2841 update_ssa_p = true;
2845 process_assert_insertions ();
2846 update_ssa (TODO_update_ssa_no_phi);
2849 if (dump_file && (dump_flags & TDF_DETAILS))
2851 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
2852 dump_function_to_file (current_function_decl, dump_file, dump_flags);
2855 sbitmap_free (found_in_subgraph);
2857 BITMAP_FREE (need_assert_for);
2861 /* Convert range assertion expressions into the implied copies.
2863 FIXME, this will eventually lead to copy propagation removing the
2864 names that had useful range information attached to them. For
2865 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
2866 then N_i will have the range [3, +INF].
2868 However, by converting the assertion into the implied copy
2869 operation N_i = N_j, we will then copy-propagate N_j into the uses
2870 of N_i and lose the range information. We may want to hold on to
2871 ASSERT_EXPRs a little while longer as the ranges could be used in
2872 things like jump threading.
2874 The problem with keeping ASSERT_EXPRs around is that passes after
2875 VRP need to handle them appropriately. */
2878 remove_range_assertions (void)
2881 block_stmt_iterator si;
2884 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2886 tree stmt = bsi_stmt (si);
2888 if (TREE_CODE (stmt) == MODIFY_EXPR
2889 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
2891 tree rhs = TREE_OPERAND (stmt, 1);
2892 tree cond = fold (ASSERT_EXPR_COND (rhs));
2893 gcc_assert (cond != boolean_false_node);
2894 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
2901 /* Return true if STMT is interesting for VRP. */
2904 stmt_interesting_for_vrp (tree stmt)
2906 if (TREE_CODE (stmt) == PHI_NODE
2907 && is_gimple_reg (PHI_RESULT (stmt))
2908 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
2909 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
2911 else if (TREE_CODE (stmt) == MODIFY_EXPR)
2913 tree lhs = TREE_OPERAND (stmt, 0);
2915 if (TREE_CODE (lhs) == SSA_NAME
2916 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2917 || POINTER_TYPE_P (TREE_TYPE (lhs)))
2918 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
2921 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
2928 /* Initialize local data structures for VRP. Return true if VRP
2929 is worth running (i.e. if we found any statements that could
2930 benefit from range information). */
2933 vrp_initialize (void)
2937 vr_value = xmalloc (num_ssa_names * sizeof (value_range_t *));
2938 memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *));
2942 block_stmt_iterator si;
2945 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2947 if (!stmt_interesting_for_vrp (phi))
2949 tree lhs = PHI_RESULT (phi);
2950 set_value_range_to_varying (get_value_range (lhs));
2951 DONT_SIMULATE_AGAIN (phi) = true;
2954 DONT_SIMULATE_AGAIN (phi) = false;
2957 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2959 tree stmt = bsi_stmt (si);
2961 if (!stmt_interesting_for_vrp (stmt))
2965 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
2966 set_value_range_to_varying (get_value_range (def));
2967 DONT_SIMULATE_AGAIN (stmt) = true;
2971 DONT_SIMULATE_AGAIN (stmt) = false;
2978 /* Visit assignment STMT. If it produces an interesting range, record
2979 the SSA name in *OUTPUT_P. */
2981 static enum ssa_prop_result
2982 vrp_visit_assignment (tree stmt, tree *output_p)
2987 lhs = TREE_OPERAND (stmt, 0);
2988 rhs = TREE_OPERAND (stmt, 1);
2990 /* We only keep track of ranges in integral and pointer types. */
2991 if (TREE_CODE (lhs) == SSA_NAME
2992 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2993 || POINTER_TYPE_P (TREE_TYPE (lhs))))
2996 value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2998 extract_range_from_expr (&new_vr, rhs);
3000 /* If STMT is inside a loop, we may be able to know something
3001 else about the range of LHS by examining scalar evolution
3003 if (cfg_loops && (l = loop_containing_stmt (stmt)))
3004 adjust_range_with_scev (&new_vr, l, lhs);
3006 if (update_value_range (lhs, &new_vr))
3010 if (dump_file && (dump_flags & TDF_DETAILS))
3012 fprintf (dump_file, "Found new range for ");
3013 print_generic_expr (dump_file, lhs, 0);
3014 fprintf (dump_file, ": ");
3015 dump_value_range (dump_file, &new_vr);
3016 fprintf (dump_file, "\n\n");
3019 if (new_vr.type == VR_VARYING)
3020 return SSA_PROP_VARYING;
3022 return SSA_PROP_INTERESTING;
3025 return SSA_PROP_NOT_INTERESTING;
3028 /* Every other statement produces no useful ranges. */
3029 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3030 set_value_range_to_varying (get_value_range (def));
3032 return SSA_PROP_VARYING;
3036 /* Compare all the value ranges for names equivalent to VAR with VAL
3037 using comparison code COMP. Return the same value returned by
3038 compare_range_with_value. */
3041 compare_name_with_value (enum tree_code comp, tree var, tree val)
3048 t = retval = NULL_TREE;
3050 /* Get the set of equivalences for VAR. */
3051 e = get_value_range (var)->equiv;
3053 /* Add VAR to its own set of equivalences so that VAR's value range
3054 is processed by this loop (otherwise, we would have to replicate
3055 the body of the loop just to check VAR's value range). */
3056 bitmap_set_bit (e, SSA_NAME_VERSION (var));
3058 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
3060 value_range_t equiv_vr = *(vr_value[i]);
3062 /* If name N_i does not have a valid range, use N_i as its own
3063 range. This allows us to compare against names that may
3064 have N_i in their ranges. */
3065 if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
3067 equiv_vr.type = VR_RANGE;
3068 equiv_vr.min = ssa_name (i);
3069 equiv_vr.max = ssa_name (i);
3072 t = compare_range_with_value (comp, &equiv_vr, val);
3075 /* All the ranges should compare the same against VAL. */
3076 gcc_assert (retval == NULL || t == retval);
3081 /* Remove VAR from its own equivalence set. */
3082 bitmap_clear_bit (e, SSA_NAME_VERSION (var));
3087 /* We couldn't find a non-NULL value for the predicate. */
3092 /* Given a comparison code COMP and names N1 and N2, compare all the
3093 ranges equivalent to N1 against all the ranges equivalente to N2
3094 to determine the value of N1 COMP N2. Return the same value
3095 returned by compare_ranges. */
3098 compare_names (enum tree_code comp, tree n1, tree n2)
3102 bitmap_iterator bi1, bi2;
3105 /* Compare the ranges of every name equivalent to N1 against the
3106 ranges of every name equivalent to N2. */
3107 e1 = get_value_range (n1)->equiv;
3108 e2 = get_value_range (n2)->equiv;
3110 /* Add N1 and N2 to their own set of equivalences to avoid
3111 duplicating the body of the loop just to check N1 and N2
3113 bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
3114 bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
3116 /* If the equivalence sets have a common intersection, then the two
3117 names can be compared without checking their ranges. */
3118 if (bitmap_intersect_p (e1, e2))
3120 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3121 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3123 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
3125 : boolean_false_node;
3128 /* Otherwise, compare all the equivalent ranges. First, add N1 and
3129 N2 to their own set of equivalences to avoid duplicating the body
3130 of the loop just to check N1 and N2 ranges. */
3131 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
3133 value_range_t vr1 = *(vr_value[i1]);
3135 /* If the range is VARYING or UNDEFINED, use the name itself. */
3136 if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
3138 vr1.type = VR_RANGE;
3139 vr1.min = ssa_name (i1);
3140 vr1.max = ssa_name (i1);
3143 t = retval = NULL_TREE;
3144 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
3146 value_range_t vr2 = *(vr_value[i2]);
3148 if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
3150 vr2.type = VR_RANGE;
3151 vr2.min = ssa_name (i2);
3152 vr2.max = ssa_name (i2);
3155 t = compare_ranges (comp, &vr1, &vr2);
3158 /* All the ranges in the equivalent sets should compare
3160 gcc_assert (retval == NULL || t == retval);
3167 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3168 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3173 /* None of the equivalent ranges are useful in computing this
3175 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3176 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3181 /* Given a conditional predicate COND, try to determine if COND yields
3182 true or false based on the value ranges of its operands. Return
3183 BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
3184 BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
3185 NULL if the conditional cannot be evaluated at compile time.
3187 If USE_EQUIV_P is true, the ranges of all the names equivalent with
3188 the operands in COND are used when trying to compute its value.
3189 This is only used during final substitution. During propagation,
3190 we only check the range of each variable and not its equivalents. */
3193 vrp_evaluate_conditional (tree cond, bool use_equiv_p)
3195 gcc_assert (TREE_CODE (cond) == SSA_NAME
3196 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
3198 if (TREE_CODE (cond) == SSA_NAME)
3204 retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node);
3207 value_range_t *vr = get_value_range (cond);
3208 retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node);
3211 /* If COND has a known boolean range, return it. */
3215 /* Otherwise, if COND has a symbolic range of exactly one value,
3217 vr = get_value_range (cond);
3218 if (vr->type == VR_RANGE && vr->min == vr->max)
3223 tree op0 = TREE_OPERAND (cond, 0);
3224 tree op1 = TREE_OPERAND (cond, 1);
3226 /* We only deal with integral and pointer types. */
3227 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3228 && !POINTER_TYPE_P (TREE_TYPE (op0)))
3233 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
3234 return compare_names (TREE_CODE (cond), op0, op1);
3235 else if (TREE_CODE (op0) == SSA_NAME)
3236 return compare_name_with_value (TREE_CODE (cond), op0, op1);
3237 else if (TREE_CODE (op1) == SSA_NAME)
3238 return compare_name_with_value (
3239 opposite_comparison (TREE_CODE (cond)), op1, op0);
3243 value_range_t *vr0, *vr1;
3245 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
3246 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
3249 return compare_ranges (TREE_CODE (cond), vr0, vr1);
3250 else if (vr0 && vr1 == NULL)
3251 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
3252 else if (vr0 == NULL && vr1)
3253 return compare_range_with_value (
3254 opposite_comparison (TREE_CODE (cond)), vr1, op0);
3258 /* Anything else cannot be computed statically. */
3263 /* Visit conditional statement STMT. If we can determine which edge
3264 will be taken out of STMT's basic block, record it in
3265 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
3266 SSA_PROP_VARYING. */
3268 static enum ssa_prop_result
3269 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
3273 *taken_edge_p = NULL;
3275 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
3276 add ASSERT_EXPRs for them. */
3277 if (TREE_CODE (stmt) == SWITCH_EXPR)
3278 return SSA_PROP_VARYING;
3280 cond = COND_EXPR_COND (stmt);
3282 if (dump_file && (dump_flags & TDF_DETAILS))
3287 fprintf (dump_file, "\nVisiting conditional with predicate: ");
3288 print_generic_expr (dump_file, cond, 0);
3289 fprintf (dump_file, "\nWith known ranges\n");
3291 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
3293 fprintf (dump_file, "\t");
3294 print_generic_expr (dump_file, use, 0);
3295 fprintf (dump_file, ": ");
3296 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
3299 fprintf (dump_file, "\n");
3302 /* Compute the value of the predicate COND by checking the known
3303 ranges of each of its operands.
3305 Note that we cannot evaluate all the equivalent ranges here
3306 because those ranges may not yet be final and with the current
3307 propagation strategy, we cannot determine when the value ranges
3308 of the names in the equivalence set have changed.
3310 For instance, given the following code fragment
3314 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
3318 Assume that on the first visit to i_14, i_5 has the temporary
3319 range [8, 8] because the second argument to the PHI function is
3320 not yet executable. We derive the range ~[0, 0] for i_14 and the
3321 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
3322 the first time, since i_14 is equivalent to the range [8, 8], we
3323 determine that the predicate is always false.
3325 On the next round of propagation, i_13 is determined to be
3326 VARYING, which causes i_5 to drop down to VARYING. So, another
3327 visit to i_14 is scheduled. In this second visit, we compute the
3328 exact same range and equivalence set for i_14, namely ~[0, 0] and
3329 { i_5 }. But we did not have the previous range for i_5
3330 registered, so vrp_visit_assignment thinks that the range for
3331 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
3332 is not visited again, which stops propagation from visiting
3333 statements in the THEN clause of that if().
3335 To properly fix this we would need to keep the previous range
3336 value for the names in the equivalence set. This way we would've
3337 discovered that from one visit to the other i_5 changed from
3338 range [8, 8] to VR_VARYING.
3340 However, fixing this apparent limitation may not be worth the
3341 additional checking. Testing on several code bases (GCC, DLV,
3342 MICO, TRAMP3D and SPEC2000) showed that doing this results in
3343 4 more predicates folded in SPEC. */
3344 val = vrp_evaluate_conditional (cond, false);
3346 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
3348 if (dump_file && (dump_flags & TDF_DETAILS))
3350 fprintf (dump_file, "\nPredicate evaluates to: ");
3351 if (val == NULL_TREE)
3352 fprintf (dump_file, "DON'T KNOW\n");
3354 print_generic_stmt (dump_file, val, 0);
3357 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
3361 /* Evaluate statement STMT. If the statement produces a useful range,
3362 return SSA_PROP_INTERESTING and record the SSA name with the
3363 interesting range into *OUTPUT_P.
3365 If STMT is a conditional branch and we can determine its truth
3366 value, the taken edge is recorded in *TAKEN_EDGE_P.
3368 If STMT produces a varying value, return SSA_PROP_VARYING. */
3370 static enum ssa_prop_result
3371 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
3377 if (dump_file && (dump_flags & TDF_DETAILS))
3379 fprintf (dump_file, "\nVisiting statement:\n");
3380 print_generic_stmt (dump_file, stmt, dump_flags);
3381 fprintf (dump_file, "\n");
3384 ann = stmt_ann (stmt);
3385 if (TREE_CODE (stmt) == MODIFY_EXPR
3386 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3387 return vrp_visit_assignment (stmt, output_p);
3388 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3389 return vrp_visit_cond_stmt (stmt, taken_edge_p);
3391 /* All other statements produce nothing of interest for VRP, so mark
3392 their outputs varying and prevent further simulation. */
3393 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3394 set_value_range_to_varying (get_value_range (def));
3396 return SSA_PROP_VARYING;
3400 /* Meet operation for value ranges. Given two value ranges VR0 and
3401 VR1, store in VR0 the result of meeting VR0 and VR1.
3403 The meeting rules are as follows:
3405 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
3407 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
3408 union of VR0 and VR1. */
3411 vrp_meet (value_range_t *vr0, value_range_t *vr1)
3413 if (vr0->type == VR_UNDEFINED)
3415 copy_value_range (vr0, vr1);
3419 if (vr1->type == VR_UNDEFINED)
3421 /* Nothing to do. VR0 already has the resulting range. */
3425 if (vr0->type == VR_VARYING)
3427 /* Nothing to do. VR0 already has the resulting range. */
3431 if (vr1->type == VR_VARYING)
3433 set_value_range_to_varying (vr0);
3437 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
3439 /* If VR0 and VR1 have a non-empty intersection, compute the
3440 union of both ranges. */
3441 if (value_ranges_intersect_p (vr0, vr1))
3446 /* The lower limit of the new range is the minimum of the
3447 two ranges. If they cannot be compared, the result is
3449 cmp = compare_values (vr0->min, vr1->min);
3450 if (cmp == 0 || cmp == 1)
3456 set_value_range_to_varying (vr0);
3460 /* Similarly, the upper limit of the new range is the
3461 maximum of the two ranges. If they cannot be compared,
3462 the result is VARYING. */
3463 cmp = compare_values (vr0->max, vr1->max);
3464 if (cmp == 0 || cmp == -1)
3470 set_value_range_to_varying (vr0);
3474 /* The resulting set of equivalencies is the intersection of
3476 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3477 bitmap_and_into (vr0->equiv, vr1->equiv);
3479 set_value_range (vr0, vr0->type, min, max, vr0->equiv);
3484 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3486 /* Two anti-ranges meet only if they are both identical. */
3487 if (compare_values (vr0->min, vr1->min) == 0
3488 && compare_values (vr0->max, vr1->max) == 0
3489 && compare_values (vr0->min, vr0->max) == 0)
3491 /* The resulting set of equivalencies is the intersection of
3493 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3494 bitmap_and_into (vr0->equiv, vr1->equiv);
3499 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
3501 /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4]
3502 meet only if the ranges have an empty intersection. The
3503 result of the meet operation is the anti-range. */
3504 if (!symbolic_range_p (vr0)
3505 && !symbolic_range_p (vr1)
3506 && !value_ranges_intersect_p (vr0, vr1))
3508 if (vr1->type == VR_ANTI_RANGE)
3509 copy_value_range (vr0, vr1);
3520 /* The two range VR0 and VR1 do not meet. Before giving up and
3521 setting the result to VARYING, see if we can at least derive a
3522 useful anti-range. */
3523 if (!symbolic_range_p (vr0)
3524 && !range_includes_zero_p (vr0)
3525 && !symbolic_range_p (vr1)
3526 && !range_includes_zero_p (vr1))
3527 set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
3529 set_value_range_to_varying (vr0);
3533 /* Visit all arguments for PHI node PHI that flow through executable
3534 edges. If a valid value range can be derived from all the incoming
3535 value ranges, set a new range for the LHS of PHI. */
3537 static enum ssa_prop_result
3538 vrp_visit_phi_node (tree phi)
3541 tree lhs = PHI_RESULT (phi);
3542 value_range_t *lhs_vr = get_value_range (lhs);
3543 value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3545 copy_value_range (&vr_result, lhs_vr);
3547 if (dump_file && (dump_flags & TDF_DETAILS))
3549 fprintf (dump_file, "\nVisiting PHI node: ");
3550 print_generic_expr (dump_file, phi, dump_flags);
3553 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
3555 edge e = PHI_ARG_EDGE (phi, i);
3557 if (dump_file && (dump_flags & TDF_DETAILS))
3560 "\n Argument #%d (%d -> %d %sexecutable)\n",
3561 i, e->src->index, e->dest->index,
3562 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
3565 if (e->flags & EDGE_EXECUTABLE)
3567 tree arg = PHI_ARG_DEF (phi, i);
3568 value_range_t vr_arg;
3570 if (TREE_CODE (arg) == SSA_NAME)
3571 vr_arg = *(get_value_range (arg));
3574 vr_arg.type = VR_RANGE;
3577 vr_arg.equiv = NULL;
3580 if (dump_file && (dump_flags & TDF_DETAILS))
3582 fprintf (dump_file, "\t");
3583 print_generic_expr (dump_file, arg, dump_flags);
3584 fprintf (dump_file, "\n\tValue: ");
3585 dump_value_range (dump_file, &vr_arg);
3586 fprintf (dump_file, "\n");
3589 vrp_meet (&vr_result, &vr_arg);
3591 if (vr_result.type == VR_VARYING)
3596 if (vr_result.type == VR_VARYING)
3599 /* To prevent infinite iterations in the algorithm, derive ranges
3600 when the new value is slightly bigger or smaller than the
3602 if (lhs_vr->type == VR_RANGE)
3604 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
3606 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
3607 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
3609 /* If the new minimum is smaller or larger than the previous
3610 one, go all the way to -INF. In the first case, to avoid
3611 iterating millions of times to reach -INF, and in the
3612 other case to avoid infinite bouncing between different
3614 if (cmp_min > 0 || cmp_min < 0)
3615 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
3617 /* Similarly, if the new maximum is smaller or larger than
3618 the previous one, go all the way to +INF. */
3619 if (cmp_max < 0 || cmp_max > 0)
3620 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
3622 /* If we ended up with a (-INF, +INF) range, set it to
3624 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
3625 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
3630 /* If the new range is different than the previous value, keep
3632 if (update_value_range (lhs, &vr_result))
3633 return SSA_PROP_INTERESTING;
3635 /* Nothing changed, don't add outgoing edges. */
3636 return SSA_PROP_NOT_INTERESTING;
3638 /* No match found. Set the LHS to VARYING. */
3640 set_value_range_to_varying (lhs_vr);
3641 return SSA_PROP_VARYING;
3645 /* Traverse all the blocks folding conditionals with known ranges. */
3651 prop_value_t *single_val_range;
3652 bool do_value_subst_p;
3656 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
3657 dump_all_value_ranges (dump_file);
3658 fprintf (dump_file, "\n");
3661 /* We may have ended with ranges that have exactly one value. Those
3662 values can be substituted as any other copy/const propagated
3663 value using substitute_and_fold. */
3664 single_val_range = xmalloc (num_ssa_names * sizeof (*single_val_range));
3665 memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range));
3667 do_value_subst_p = false;
3668 for (i = 0; i < num_ssa_names; i++)
3670 && vr_value[i]->type == VR_RANGE
3671 && vr_value[i]->min == vr_value[i]->max)
3673 single_val_range[i].value = vr_value[i]->min;
3674 do_value_subst_p = true;
3677 if (!do_value_subst_p)
3679 /* We found no single-valued ranges, don't waste time trying to
3680 do single value substitution in substitute_and_fold. */
3681 free (single_val_range);
3682 single_val_range = NULL;
3685 substitute_and_fold (single_val_range, true);
3687 /* Free allocated memory. */
3688 for (i = 0; i < num_ssa_names; i++)
3691 BITMAP_FREE (vr_value[i]->equiv);
3695 free (single_val_range);
3700 /* Main entry point to VRP (Value Range Propagation). This pass is
3701 loosely based on J. R. C. Patterson, ``Accurate Static Branch
3702 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
3703 Programming Language Design and Implementation, pp. 67-78, 1995.
3704 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
3706 This is essentially an SSA-CCP pass modified to deal with ranges
3707 instead of constants.
3709 While propagating ranges, we may find that two or more SSA name
3710 have equivalent, though distinct ranges. For instance,
3713 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0>
3715 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
3719 In the code above, pointer p_5 has range [q_2, q_2], but from the
3720 code we can also determine that p_5 cannot be NULL and, if q_2 had
3721 a non-varying range, p_5's range should also be compatible with it.
3723 These equivalencies are created by two expressions: ASSERT_EXPR and
3724 copy operations. Since p_5 is an assertion on p_4, and p_4 was the
3725 result of another assertion, then we can use the fact that p_5 and
3726 p_4 are equivalent when evaluating p_5's range.
3728 Together with value ranges, we also propagate these equivalencies
3729 between names so that we can take advantage of information from
3730 multiple ranges when doing final replacement. Note that this
3731 equivalency relation is transitive but not symmetric.
3733 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
3734 cannot assert that q_2 is equivalent to p_5 because q_2 may be used
3735 in contexts where that assertion does not hold (e.g., in line 6).
3737 TODO, the main difference between this pass and Patterson's is that
3738 we do not propagate edge probabilities. We only compute whether
3739 edges can be taken or not. That is, instead of having a spectrum
3740 of jump probabilities between 0 and 1, we only deal with 0, 1 and
3741 DON'T KNOW. In the future, it may be worthwhile to propagate
3742 probabilities to aid branch prediction. */
3747 insert_range_assertions ();
3749 cfg_loops = loop_optimizer_init (NULL);
3751 scev_initialize (cfg_loops);
3754 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
3760 loop_optimizer_finalize (cfg_loops, NULL);
3761 current_loops = NULL;
3764 remove_range_assertions ();
3770 return flag_tree_vrp != 0;
3773 struct tree_opt_pass pass_vrp =
3776 gate_vrp, /* gate */
3777 execute_vrp, /* execute */
3780 0, /* static_pass_number */
3781 TV_TREE_VRP, /* tv_id */
3782 PROP_ssa | PROP_alias, /* properties_required */
3783 0, /* properties_provided */
3784 0, /* properties_destroyed */
3785 0, /* todo_flags_start */
3790 | TODO_update_ssa, /* todo_flags_finish */