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 /* Return true if ARG is marked with the nonnull attribute in the
169 current function signature. */
172 nonnull_arg_p (tree arg)
174 tree t, attrs, fntype;
175 unsigned HOST_WIDE_INT arg_num;
177 gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg)));
179 fntype = TREE_TYPE (current_function_decl);
180 attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype));
182 /* If "nonnull" wasn't specified, we know nothing about the argument. */
183 if (attrs == NULL_TREE)
186 /* If "nonnull" applies to all the arguments, then ARG is non-null. */
187 if (TREE_VALUE (attrs) == NULL_TREE)
190 /* Get the position number for ARG in the function signature. */
191 for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl);
193 t = TREE_CHAIN (t), arg_num++)
199 gcc_assert (t == arg);
201 /* Now see if ARG_NUM is mentioned in the nonnull list. */
202 for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
204 if (compare_tree_int (TREE_VALUE (t), arg_num) == 0)
212 /* Set value range VR to {T, MIN, MAX, EQUIV}. */
215 set_value_range (value_range_t *vr, enum value_range_type t, tree min,
216 tree max, bitmap equiv)
218 #if defined ENABLE_CHECKING
219 /* Check the validity of the range. */
220 if (t == VR_RANGE || t == VR_ANTI_RANGE)
224 gcc_assert (min && max);
226 if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
227 gcc_assert (min != TYPE_MIN_VALUE (TREE_TYPE (min))
228 || max != TYPE_MAX_VALUE (TREE_TYPE (max)));
230 cmp = compare_values (min, max);
231 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
234 if (t == VR_UNDEFINED || t == VR_VARYING)
235 gcc_assert (min == NULL_TREE && max == NULL_TREE);
237 if (t == VR_UNDEFINED || t == VR_VARYING)
238 gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
245 /* Since updating the equivalence set involves deep copying the
246 bitmaps, only do it if absolutely necessary. */
247 if (vr->equiv == NULL)
248 vr->equiv = BITMAP_ALLOC (NULL);
250 if (equiv != vr->equiv)
252 if (equiv && !bitmap_empty_p (equiv))
253 bitmap_copy (vr->equiv, equiv);
255 bitmap_clear (vr->equiv);
260 /* Copy value range FROM into value range TO. */
263 copy_value_range (value_range_t *to, value_range_t *from)
265 set_value_range (to, from->type, from->min, from->max, from->equiv);
269 /* Set value range VR to a non-NULL range of type TYPE. */
272 set_value_range_to_nonnull (value_range_t *vr, tree type)
274 tree zero = build_int_cst (type, 0);
275 set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
279 /* Set value range VR to a NULL range of type TYPE. */
282 set_value_range_to_null (value_range_t *vr, tree type)
284 tree zero = build_int_cst (type, 0);
285 set_value_range (vr, VR_RANGE, zero, zero, vr->equiv);
289 /* Set value range VR to VR_VARYING. */
292 set_value_range_to_varying (value_range_t *vr)
294 vr->type = VR_VARYING;
295 vr->min = vr->max = NULL_TREE;
297 bitmap_clear (vr->equiv);
301 /* Set value range VR to VR_UNDEFINED. */
304 set_value_range_to_undefined (value_range_t *vr)
306 vr->type = VR_UNDEFINED;
307 vr->min = vr->max = NULL_TREE;
309 bitmap_clear (vr->equiv);
313 /* Return value range information for VAR. Create an empty range
316 static value_range_t *
317 get_value_range (tree var)
321 unsigned ver = SSA_NAME_VERSION (var);
327 /* Create a default value range. */
328 vr_value[ver] = vr = xmalloc (sizeof (*vr));
329 memset (vr, 0, sizeof (*vr));
331 /* Allocate an equivalence set. */
332 vr->equiv = BITMAP_ALLOC (NULL);
334 /* If VAR is a default definition, the variable can take any value
336 sym = SSA_NAME_VAR (var);
337 if (var == var_ann (sym)->default_def)
339 /* Try to use the "nonnull" attribute to create ~[0, 0]
340 anti-ranges for pointers. Note that this is only valid with
341 default definitions of PARM_DECLs. */
342 if (TREE_CODE (sym) == PARM_DECL
343 && POINTER_TYPE_P (TREE_TYPE (sym))
344 && nonnull_arg_p (sym))
345 set_value_range_to_nonnull (vr, TREE_TYPE (sym));
347 set_value_range_to_varying (vr);
354 /* Update the value range and equivalence set for variable VAR to
355 NEW_VR. Return true if NEW_VR is different from VAR's previous
358 NOTE: This function assumes that NEW_VR is a temporary value range
359 object created for the sole purpose of updating VAR's range. The
360 storage used by the equivalence set from NEW_VR will be freed by
361 this function. Do not call update_value_range when NEW_VR
362 is the range object associated with another SSA name. */
365 update_value_range (tree var, value_range_t *new_vr)
367 value_range_t *old_vr;
370 /* Update the value range, if necessary. */
371 old_vr = get_value_range (var);
372 is_new = old_vr->type != new_vr->type
373 || old_vr->min != new_vr->min
374 || old_vr->max != new_vr->max
375 || (old_vr->equiv == NULL && new_vr->equiv)
376 || (old_vr->equiv && new_vr->equiv == NULL)
377 || (!bitmap_equal_p (old_vr->equiv, new_vr->equiv));
380 set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
383 BITMAP_FREE (new_vr->equiv);
384 new_vr->equiv = NULL;
390 /* Add VAR and VAR's equivalence set to EQUIV. */
393 add_equivalence (bitmap equiv, tree var)
395 unsigned ver = SSA_NAME_VERSION (var);
396 value_range_t *vr = vr_value[ver];
398 bitmap_set_bit (equiv, ver);
400 bitmap_ior_into (equiv, vr->equiv);
404 /* Return true if VR is ~[0, 0]. */
407 range_is_nonnull (value_range_t *vr)
409 return vr->type == VR_ANTI_RANGE
410 && integer_zerop (vr->min)
411 && integer_zerop (vr->max);
415 /* Return true if VR is [0, 0]. */
418 range_is_null (value_range_t *vr)
420 return vr->type == VR_RANGE
421 && integer_zerop (vr->min)
422 && integer_zerop (vr->max);
426 /* Return true if value range VR involves at least one symbol. */
429 symbolic_range_p (value_range_t *vr)
431 return (!is_gimple_min_invariant (vr->min)
432 || !is_gimple_min_invariant (vr->max));
436 /* Like expr_computes_nonzero, but this function uses value ranges
440 vrp_expr_computes_nonzero (tree expr)
442 if (expr_computes_nonzero (expr))
445 /* If we have an expression of the form &X->a, then the expression
446 is nonnull if X is nonnull. */
447 if (TREE_CODE (expr) == ADDR_EXPR)
449 tree base = get_base_address (TREE_OPERAND (expr, 0));
451 if (base != NULL_TREE
452 && TREE_CODE (base) == INDIRECT_REF
453 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
455 value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
456 if (range_is_nonnull (vr))
465 /* Compare two values VAL1 and VAL2. Return
467 -2 if VAL1 and VAL2 cannot be compared at compile-time,
470 +1 if VAL1 > VAL2, and
473 This is similar to tree_int_cst_compare but supports pointer values
474 and values that cannot be compared at compile time. */
477 compare_values (tree val1, tree val2)
482 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
484 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
485 == POINTER_TYPE_P (TREE_TYPE (val2)));
487 /* Do some limited symbolic comparisons. */
488 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
490 /* We can determine some comparisons against +INF and -INF even
491 if the other value is an expression. */
492 if (val1 == TYPE_MAX_VALUE (TREE_TYPE (val1))
493 && TREE_CODE (val2) == MINUS_EXPR)
495 /* +INF > NAME - CST. */
498 else if (val1 == TYPE_MIN_VALUE (TREE_TYPE (val1))
499 && TREE_CODE (val2) == PLUS_EXPR)
501 /* -INF < NAME + CST. */
504 else if (TREE_CODE (val1) == MINUS_EXPR
505 && val2 == TYPE_MAX_VALUE (TREE_TYPE (val2)))
507 /* NAME - CST < +INF. */
510 else if (TREE_CODE (val1) == PLUS_EXPR
511 && val2 == TYPE_MIN_VALUE (TREE_TYPE (val2)))
513 /* NAME + CST > -INF. */
518 if ((TREE_CODE (val1) == SSA_NAME
519 || TREE_CODE (val1) == PLUS_EXPR
520 || TREE_CODE (val1) == MINUS_EXPR)
521 && (TREE_CODE (val2) == SSA_NAME
522 || TREE_CODE (val2) == PLUS_EXPR
523 || TREE_CODE (val2) == MINUS_EXPR))
527 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
528 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
529 same name, return -2. */
530 if (TREE_CODE (val1) == SSA_NAME)
537 n1 = TREE_OPERAND (val1, 0);
538 c1 = TREE_OPERAND (val1, 1);
541 if (TREE_CODE (val2) == SSA_NAME)
548 n2 = TREE_OPERAND (val2, 0);
549 c2 = TREE_OPERAND (val2, 1);
552 /* Both values must use the same name. */
556 if (TREE_CODE (val1) == SSA_NAME)
558 if (TREE_CODE (val2) == SSA_NAME)
561 else if (TREE_CODE (val2) == PLUS_EXPR)
562 /* NAME < NAME + CST */
564 else if (TREE_CODE (val2) == MINUS_EXPR)
565 /* NAME > NAME - CST */
568 else if (TREE_CODE (val1) == PLUS_EXPR)
570 if (TREE_CODE (val2) == SSA_NAME)
571 /* NAME + CST > NAME */
573 else if (TREE_CODE (val2) == PLUS_EXPR)
574 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
575 return compare_values (c1, c2);
576 else if (TREE_CODE (val2) == MINUS_EXPR)
577 /* NAME + CST1 > NAME - CST2 */
580 else if (TREE_CODE (val1) == MINUS_EXPR)
582 if (TREE_CODE (val2) == SSA_NAME)
583 /* NAME - CST < NAME */
585 else if (TREE_CODE (val2) == PLUS_EXPR)
586 /* NAME - CST1 < NAME + CST2 */
588 else if (TREE_CODE (val2) == MINUS_EXPR)
589 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
590 C1 and C2 are swapped in the call to compare_values. */
591 return compare_values (c2, c1);
597 /* We cannot compare non-constants. */
598 if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
601 /* We cannot compare overflowed values. */
602 if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
605 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
606 return tree_int_cst_compare (val1, val2);
611 /* First see if VAL1 and VAL2 are not the same. */
612 if (val1 == val2 || operand_equal_p (val1, val2, 0))
615 /* If VAL1 is a lower address than VAL2, return -1. */
616 t = fold_binary (LT_EXPR, boolean_type_node, val1, val2);
617 if (t == boolean_true_node)
620 /* If VAL1 is a higher address than VAL2, return +1. */
621 t = fold_binary (GT_EXPR, boolean_type_node, val1, val2);
622 if (t == boolean_true_node)
625 /* If VAL1 is different than VAL2, return +2. */
626 t = fold_binary (NE_EXPR, boolean_type_node, val1, val2);
627 if (t == boolean_true_node)
635 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
636 0 if VAL is not inside VR,
637 -2 if we cannot tell either way. */
640 value_inside_range (tree val, value_range_t *vr)
644 cmp1 = compare_values (val, vr->min);
645 if (cmp1 == -2 || cmp1 == 2)
648 cmp2 = compare_values (val, vr->max);
649 if (cmp2 == -2 || cmp2 == 2)
652 return (cmp1 == 0 || cmp1 == 1) && (cmp2 == -1 || cmp2 == 0);
656 /* Return true if value ranges VR0 and VR1 have a non-empty
660 value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
662 return (value_inside_range (vr1->min, vr0) == 1
663 || value_inside_range (vr1->max, vr0) == 1
664 || value_inside_range (vr0->min, vr1) == 1
665 || value_inside_range (vr0->max, vr1) == 1);
669 /* Return true if VR includes the value zero, false otherwise. */
672 range_includes_zero_p (value_range_t *vr)
676 gcc_assert (vr->type != VR_UNDEFINED
677 && vr->type != VR_VARYING
678 && !symbolic_range_p (vr));
680 zero = build_int_cst (TREE_TYPE (vr->min), 0);
681 return (value_inside_range (zero, vr) == 1);
685 /* Extract value range information from an ASSERT_EXPR EXPR and store
689 extract_range_from_assert (value_range_t *vr_p, tree expr)
691 tree var, cond, limit, min, max, type;
692 value_range_t *var_vr, *limit_vr;
693 enum tree_code cond_code;
695 var = ASSERT_EXPR_VAR (expr);
696 cond = ASSERT_EXPR_COND (expr);
698 gcc_assert (COMPARISON_CLASS_P (cond));
700 /* Find VAR in the ASSERT_EXPR conditional. */
701 if (var == TREE_OPERAND (cond, 0))
703 /* If the predicate is of the form VAR COMP LIMIT, then we just
704 take LIMIT from the RHS and use the same comparison code. */
705 limit = TREE_OPERAND (cond, 1);
706 cond_code = TREE_CODE (cond);
710 /* If the predicate is of the form LIMIT COMP VAR, then we need
711 to flip around the comparison code to create the proper range
713 limit = TREE_OPERAND (cond, 0);
714 cond_code = opposite_comparison (TREE_CODE (cond));
717 type = TREE_TYPE (limit);
718 gcc_assert (limit != var);
720 /* For pointer arithmetic, we only keep track of pointer equality
722 if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
724 set_value_range_to_varying (vr_p);
728 /* If LIMIT is another SSA name and LIMIT has a range of its own,
729 try to use LIMIT's range to avoid creating symbolic ranges
731 limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
733 /* LIMIT's range is only interesting if it has any useful information. */
735 && (limit_vr->type == VR_UNDEFINED
736 || limit_vr->type == VR_VARYING
737 || symbolic_range_p (limit_vr)))
740 /* Special handling for integral types with super-types. Some FEs
741 construct integral types derived from other types and restrict
742 the range of values these new types may take.
744 It may happen that LIMIT is actually smaller than TYPE's minimum
745 value. For instance, the Ada FE is generating code like this
748 D.1480_32 = nam_30 - 300000361;
749 if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
751 D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;
753 All the names are of type types__name_id___XDLU_300000000__399999999
754 which has min == 300000000 and max == 399999999. This means that
755 the ASSERT_EXPR would try to create the range [3000000, 1] which
758 The fact that the type specifies MIN and MAX values does not
759 automatically mean that every variable of that type will always
760 be within that range, so the predicate may well be true at run
761 time. If we had symbolic -INF and +INF values, we could
762 represent this range, but we currently represent -INF and +INF
763 using the type's min and max values.
765 So, the only sensible thing we can do for now is set the
766 resulting range to VR_VARYING. TODO, would having symbolic -INF
767 and +INF values be worth the trouble? */
768 if (TREE_CODE (limit) != SSA_NAME
769 && INTEGRAL_TYPE_P (type)
772 if (cond_code == LE_EXPR || cond_code == LT_EXPR)
774 tree type_min = TYPE_MIN_VALUE (type);
775 int cmp = compare_values (limit, type_min);
777 /* For < or <= comparisons, if LIMIT is smaller than
778 TYPE_MIN, set the range to VR_VARYING. */
779 if (cmp == -1 || cmp == 0)
781 set_value_range_to_varying (vr_p);
785 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
787 tree type_max = TYPE_MIN_VALUE (type);
788 int cmp = compare_values (limit, type_max);
790 /* For > or >= comparisons, if LIMIT is bigger than
791 TYPE_MAX, set the range to VR_VARYING. */
792 if (cmp == 1 || cmp == 0)
794 set_value_range_to_varying (vr_p);
800 /* The new range has the same set of equivalences of VAR's range. */
801 gcc_assert (vr_p->equiv == NULL);
802 vr_p->equiv = BITMAP_ALLOC (NULL);
803 add_equivalence (vr_p->equiv, var);
805 /* Extract a new range based on the asserted comparison for VAR and
806 LIMIT's value range. Notice that if LIMIT has an anti-range, we
807 will only use it for equality comparisons (EQ_EXPR). For any
808 other kind of assertion, we cannot derive a range from LIMIT's
809 anti-range that can be used to describe the new range. For
810 instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
811 then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
812 no single range for x_2 that could describe LE_EXPR, so we might
813 as well build the range [b_4, +INF] for it. */
814 if (cond_code == EQ_EXPR)
816 enum value_range_type range_type;
820 range_type = limit_vr->type;
826 range_type = VR_RANGE;
831 set_value_range (vr_p, range_type, min, max, vr_p->equiv);
833 /* When asserting the equality VAR == LIMIT and LIMIT is another
834 SSA name, the new range will also inherit the equivalence set
836 if (TREE_CODE (limit) == SSA_NAME)
837 add_equivalence (vr_p->equiv, limit);
839 else if (cond_code == NE_EXPR)
841 /* As described above, when LIMIT's range is an anti-range and
842 this assertion is an inequality (NE_EXPR), then we cannot
843 derive anything from the anti-range. For instance, if
844 LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
845 not imply that VAR's range is [0, 0]. So, in the case of
846 anti-ranges, we just assert the inequality using LIMIT and
847 not its anti-range. */
849 || limit_vr->type == VR_ANTI_RANGE)
860 /* If MIN and MAX cover the whole range for their type, then
861 just use the original LIMIT. */
862 if (INTEGRAL_TYPE_P (type)
863 && min == TYPE_MIN_VALUE (type)
864 && max == TYPE_MAX_VALUE (type))
867 set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
869 else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
871 min = TYPE_MIN_VALUE (type);
873 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
877 /* If LIMIT_VR is of the form [N1, N2], we need to build the
878 range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
883 /* For LT_EXPR, we create the range [MIN, MAX - 1]. */
884 if (cond_code == LT_EXPR)
886 tree one = build_int_cst (type, 1);
887 max = fold (build (MINUS_EXPR, type, max, one));
890 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
892 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
894 max = TYPE_MAX_VALUE (type);
896 if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
900 /* If LIMIT_VR is of the form [N1, N2], we need to build the
901 range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
906 /* For GT_EXPR, we create the range [MIN + 1, MAX]. */
907 if (cond_code == GT_EXPR)
909 tree one = build_int_cst (type, 1);
910 min = fold (build (PLUS_EXPR, type, min, one));
913 set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
918 /* If VAR already had a known range and the two ranges have a
919 non-empty intersection, we can refine the resulting range.
920 Since the assert expression creates an equivalency and at the
921 same time it asserts a predicate, we can take the intersection of
922 the two ranges to get better precision. */
923 var_vr = get_value_range (var);
924 if (var_vr->type == VR_RANGE
925 && vr_p->type == VR_RANGE
926 && value_ranges_intersect_p (var_vr, vr_p))
928 /* Use the larger of the two minimums. */
929 if (compare_values (vr_p->min, var_vr->min) == -1)
934 /* Use the smaller of the two maximums. */
935 if (compare_values (vr_p->max, var_vr->max) == 1)
940 set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
945 /* Extract range information from SSA name VAR and store it in VR. If
946 VAR has an interesting range, use it. Otherwise, create the
947 range [VAR, VAR] and return it. This is useful in situations where
948 we may have conditionals testing values of VARYING names. For
955 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
959 extract_range_from_ssa_name (value_range_t *vr, tree var)
961 value_range_t *var_vr = get_value_range (var);
963 if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
964 copy_value_range (vr, var_vr);
966 set_value_range (vr, VR_RANGE, var, var, NULL);
968 add_equivalence (vr->equiv, var);
972 /* Wrapper around int_const_binop. If the operation overflows and we
973 are not using wrapping arithmetic, then adjust the result to be
974 -INF or +INF depending on CODE, VAL1 and VAL2. */
977 vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
982 return int_const_binop (code, val1, val2, 0);
984 /* If we are not using wrapping arithmetic, operate symbolically
986 res = int_const_binop (code, val1, val2, 0);
988 /* If the operation overflowed but neither VAL1 nor VAL2 are
989 overflown, return -INF or +INF depending on the operation
990 and the combination of signs of the operands. */
991 if (TREE_OVERFLOW (res)
992 && !TREE_OVERFLOW (val1)
993 && !TREE_OVERFLOW (val2))
995 int sgn1 = tree_int_cst_sgn (val1);
996 int sgn2 = tree_int_cst_sgn (val2);
998 /* Notice that we only need to handle the restricted set of
999 operations handled by extract_range_from_binary_expr.
1000 Among them, only multiplication, addition and subtraction
1001 can yield overflow without overflown operands because we
1002 are working with integral types only... except in the
1003 case VAL1 = -INF and VAL2 = -1 which overflows to +INF
1004 for division too. */
1006 /* For multiplication, the sign of the overflow is given
1007 by the comparison of the signs of the operands. */
1008 if ((code == MULT_EXPR && sgn1 == sgn2)
1009 /* For addition, the operands must be of the same sign
1010 to yield an overflow. Its sign is therefore that
1011 of one of the operands, for example the first. */
1012 || (code == PLUS_EXPR && sgn1 > 0)
1013 /* For subtraction, the operands must be of different
1014 signs to yield an overflow. Its sign is therefore
1015 that of the first operand or the opposite of that
1016 of the second operand. */
1017 || (code == MINUS_EXPR && sgn1 > 0)
1018 /* For division, the only case is -INF / -1 = +INF. */
1019 || code == TRUNC_DIV_EXPR
1020 || code == FLOOR_DIV_EXPR
1021 || code == CEIL_DIV_EXPR
1022 || code == EXACT_DIV_EXPR
1023 || code == ROUND_DIV_EXPR)
1024 return TYPE_MAX_VALUE (TREE_TYPE (res));
1026 return TYPE_MIN_VALUE (TREE_TYPE (res));
1033 /* Extract range information from a binary expression EXPR based on
1034 the ranges of each of its operands and the expression code. */
1037 extract_range_from_binary_expr (value_range_t *vr, tree expr)
1039 enum tree_code code = TREE_CODE (expr);
1040 tree op0, op1, min, max;
1042 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1043 value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1045 /* Not all binary expressions can be applied to ranges in a
1046 meaningful way. Handle only arithmetic operations. */
1047 if (code != PLUS_EXPR
1048 && code != MINUS_EXPR
1049 && code != MULT_EXPR
1050 && code != TRUNC_DIV_EXPR
1051 && code != FLOOR_DIV_EXPR
1052 && code != CEIL_DIV_EXPR
1053 && code != EXACT_DIV_EXPR
1054 && code != ROUND_DIV_EXPR
1057 && code != TRUTH_ANDIF_EXPR
1058 && code != TRUTH_ORIF_EXPR
1059 && code != TRUTH_AND_EXPR
1060 && code != TRUTH_OR_EXPR
1061 && code != TRUTH_XOR_EXPR)
1063 set_value_range_to_varying (vr);
1067 /* Get value ranges for each operand. For constant operands, create
1068 a new value range with the operand to simplify processing. */
1069 op0 = TREE_OPERAND (expr, 0);
1070 if (TREE_CODE (op0) == SSA_NAME)
1071 vr0 = *(get_value_range (op0));
1072 else if (is_gimple_min_invariant (op0))
1073 set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1075 set_value_range_to_varying (&vr0);
1077 op1 = TREE_OPERAND (expr, 1);
1078 if (TREE_CODE (op1) == SSA_NAME)
1079 vr1 = *(get_value_range (op1));
1080 else if (is_gimple_min_invariant (op1))
1081 set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
1083 set_value_range_to_varying (&vr1);
1085 /* If either range is UNDEFINED, so is the result. */
1086 if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
1088 set_value_range_to_undefined (vr);
1092 /* Refuse to operate on VARYING ranges, ranges of different kinds
1093 and symbolic ranges. TODO, we may be able to derive anti-ranges
1095 if (vr0.type == VR_VARYING
1096 || vr1.type == VR_VARYING
1097 || vr0.type != vr1.type
1098 || symbolic_range_p (&vr0)
1099 || symbolic_range_p (&vr1))
1101 set_value_range_to_varying (vr);
1105 /* Now evaluate the expression to determine the new range. */
1106 if (POINTER_TYPE_P (TREE_TYPE (expr))
1107 || POINTER_TYPE_P (TREE_TYPE (op0))
1108 || POINTER_TYPE_P (TREE_TYPE (op1)))
1110 /* For pointer types, we are really only interested in asserting
1111 whether the expression evaluates to non-NULL. FIXME, we used
1112 to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
1113 ivopts is generating expressions with pointer multiplication
1115 if (code == PLUS_EXPR)
1116 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1119 /* Subtracting from a pointer, may yield 0, so just drop the
1120 resulting range to varying. */
1121 set_value_range_to_varying (vr);
1127 /* For integer ranges, apply the operation to each end of the
1128 range and see what we end up with. */
1129 if (code == TRUTH_ANDIF_EXPR
1130 || code == TRUTH_ORIF_EXPR
1131 || code == TRUTH_AND_EXPR
1132 || code == TRUTH_OR_EXPR
1133 || code == TRUTH_XOR_EXPR)
1135 /* Boolean expressions cannot be folded with int_const_binop. */
1136 min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
1137 max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
1139 else if (code == PLUS_EXPR
1141 || code == MAX_EXPR)
1143 /* For operations that make the resulting range directly
1144 proportional to the original ranges, apply the operation to
1145 the same end of each range. */
1146 min = vrp_int_const_binop (code, vr0.min, vr1.min);
1147 max = vrp_int_const_binop (code, vr0.max, vr1.max);
1149 else if (code == MULT_EXPR
1150 || code == TRUNC_DIV_EXPR
1151 || code == FLOOR_DIV_EXPR
1152 || code == CEIL_DIV_EXPR
1153 || code == EXACT_DIV_EXPR
1154 || code == ROUND_DIV_EXPR)
1159 /* Multiplications and divisions are a bit tricky to handle,
1160 depending on the mix of signs we have in the two ranges, we
1161 need to operate on different values to get the minimum and
1162 maximum values for the new range. One approach is to figure
1163 out all the variations of range combinations and do the
1166 However, this involves several calls to compare_values and it
1167 is pretty convoluted. It's simpler to do the 4 operations
1168 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
1169 MAX1) and then figure the smallest and largest values to form
1172 /* Divisions by zero result in a VARYING value. */
1173 if (code != MULT_EXPR && range_includes_zero_p (&vr1))
1175 set_value_range_to_varying (vr);
1179 /* Compute the 4 cross operations. */
1180 val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
1182 val[1] = (vr1.max != vr1.min)
1183 ? vrp_int_const_binop (code, vr0.min, vr1.max)
1186 val[2] = (vr0.max != vr0.min)
1187 ? vrp_int_const_binop (code, vr0.max, vr1.min)
1190 val[3] = (vr0.min != vr1.min && vr0.max != vr1.max)
1191 ? vrp_int_const_binop (code, vr0.max, vr1.max)
1194 /* Set MIN to the minimum of VAL[i] and MAX to the maximum
1198 for (i = 1; i < 4; i++)
1200 if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
1205 if (TREE_OVERFLOW (val[i]))
1207 /* If we found an overflowed value, set MIN and MAX
1208 to it so that we set the resulting range to
1214 if (compare_values (val[i], min) == -1)
1217 if (compare_values (val[i], max) == 1)
1222 else if (code == MINUS_EXPR)
1224 /* For MINUS_EXPR, apply the operation to the opposite ends of
1226 min = vrp_int_const_binop (code, vr0.min, vr1.max);
1227 max = vrp_int_const_binop (code, vr0.max, vr1.min);
1232 /* If either MIN or MAX overflowed, then set the resulting range to
1234 if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
1236 set_value_range_to_varying (vr);
1240 cmp = compare_values (min, max);
1241 if (cmp == -2 || cmp == 1)
1243 /* If the new range has its limits swapped around (MIN > MAX),
1244 then the operation caused one of them to wrap around, mark
1245 the new range VARYING. */
1246 set_value_range_to_varying (vr);
1249 set_value_range (vr, vr0.type, min, max, NULL);
1253 /* Extract range information from a unary expression EXPR based on
1254 the range of its operand and the expression code. */
1257 extract_range_from_unary_expr (value_range_t *vr, tree expr)
1259 enum tree_code code = TREE_CODE (expr);
1262 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1264 /* Refuse to operate on certain unary expressions for which we
1265 cannot easily determine a resulting range. */
1266 if (code == FIX_TRUNC_EXPR
1267 || code == FIX_CEIL_EXPR
1268 || code == FIX_FLOOR_EXPR
1269 || code == FIX_ROUND_EXPR
1270 || code == FLOAT_EXPR
1271 || code == BIT_NOT_EXPR
1272 || code == NON_LVALUE_EXPR
1273 || code == CONJ_EXPR)
1275 set_value_range_to_varying (vr);
1279 /* Get value ranges for the operand. For constant operands, create
1280 a new value range with the operand to simplify processing. */
1281 op0 = TREE_OPERAND (expr, 0);
1282 if (TREE_CODE (op0) == SSA_NAME)
1283 vr0 = *(get_value_range (op0));
1284 else if (is_gimple_min_invariant (op0))
1285 set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1287 set_value_range_to_varying (&vr0);
1289 /* If VR0 is UNDEFINED, so is the result. */
1290 if (vr0.type == VR_UNDEFINED)
1292 set_value_range_to_undefined (vr);
1296 /* Refuse to operate on varying and symbolic ranges. Also, if the
1297 operand is neither a pointer nor an integral type, set the
1298 resulting range to VARYING. TODO, in some cases we may be able
1299 to derive anti-ranges (like non-zero values). */
1300 if (vr0.type == VR_VARYING
1301 || (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
1302 && !POINTER_TYPE_P (TREE_TYPE (op0)))
1303 || symbolic_range_p (&vr0))
1305 set_value_range_to_varying (vr);
1309 /* If the expression involves pointers, we are only interested in
1310 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
1311 if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
1313 if (range_is_nonnull (&vr0) || expr_computes_nonzero (expr))
1314 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1315 else if (range_is_null (&vr0))
1316 set_value_range_to_null (vr, TREE_TYPE (expr));
1318 set_value_range_to_varying (vr);
1323 /* Handle unary expressions on integer ranges. */
1324 if (code == NOP_EXPR || code == CONVERT_EXPR)
1326 tree inner_type = TREE_TYPE (op0);
1327 tree outer_type = TREE_TYPE (expr);
1329 /* When converting types of different sizes, set the result to
1330 VARYING. Things like sign extensions and precision loss may
1331 change the range. For instance, if x_3 is of type 'long long
1332 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
1333 is impossible to know at compile time whether y_5 will be
1335 if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type)
1336 || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1338 set_value_range_to_varying (vr);
1343 /* Apply the operation to each end of the range and see what we end
1345 if (code == NEGATE_EXPR
1346 && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1348 /* Negating an anti-range doesn't really do anything to it. The
1349 new range will also not take on the same range of values
1350 excluded by the original anti-range. */
1351 if (vr0.type == VR_ANTI_RANGE)
1353 copy_value_range (vr, &vr0);
1357 /* NEGATE_EXPR flips the range around. */
1358 min = (vr0.max == TYPE_MAX_VALUE (TREE_TYPE (expr)))
1359 ? TYPE_MIN_VALUE (TREE_TYPE (expr))
1360 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1362 max = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1363 ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1364 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1366 else if (code == ABS_EXPR
1367 && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1369 /* ABS_EXPR may flip the range around, if the original range
1370 included negative values. */
1371 min = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1372 ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1373 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1375 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1377 /* If the range was reversed, swap MIN and MAX. */
1378 if (compare_values (min, max) == 1)
1387 /* Otherwise, operate on each end of the range. */
1388 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1389 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1392 cmp = compare_values (min, max);
1393 if (cmp == -2 || cmp == 1)
1395 /* If the new range has its limits swapped around (MIN > MAX),
1396 then the operation caused one of them to wrap around, mark
1397 the new range VARYING. */
1398 set_value_range_to_varying (vr);
1401 set_value_range (vr, vr0.type, min, max, NULL);
1405 /* Extract range information from a comparison expression EXPR based
1406 on the range of its operand and the expression code. */
1409 extract_range_from_comparison (value_range_t *vr, tree expr)
1411 tree val = vrp_evaluate_conditional (expr, false);
1414 /* Since this expression was found on the RHS of an assignment,
1415 its type may be different from _Bool. Convert VAL to EXPR's
1417 val = fold_convert (TREE_TYPE (expr), val);
1418 set_value_range (vr, VR_RANGE, val, val, vr->equiv);
1421 set_value_range_to_varying (vr);
1425 /* Try to compute a useful range out of expression EXPR and store it
1429 extract_range_from_expr (value_range_t *vr, tree expr)
1431 enum tree_code code = TREE_CODE (expr);
1433 if (code == ASSERT_EXPR)
1434 extract_range_from_assert (vr, expr);
1435 else if (code == SSA_NAME)
1436 extract_range_from_ssa_name (vr, expr);
1437 else if (TREE_CODE_CLASS (code) == tcc_binary
1438 || code == TRUTH_ANDIF_EXPR
1439 || code == TRUTH_ORIF_EXPR
1440 || code == TRUTH_AND_EXPR
1441 || code == TRUTH_OR_EXPR
1442 || code == TRUTH_XOR_EXPR)
1443 extract_range_from_binary_expr (vr, expr);
1444 else if (TREE_CODE_CLASS (code) == tcc_unary)
1445 extract_range_from_unary_expr (vr, expr);
1446 else if (TREE_CODE_CLASS (code) == tcc_comparison)
1447 extract_range_from_comparison (vr, expr);
1448 else if (vrp_expr_computes_nonzero (expr))
1449 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1450 else if (is_gimple_min_invariant (expr))
1451 set_value_range (vr, VR_RANGE, expr, expr, NULL);
1453 set_value_range_to_varying (vr);
1456 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1457 would be profitable to adjust VR using scalar evolution information
1458 for VAR. If so, update VR with the new limits. */
1461 adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
1464 tree init, step, chrec;
1467 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1468 better opportunities than a regular range, but I'm not sure. */
1469 if (vr->type == VR_ANTI_RANGE)
1472 chrec = analyze_scalar_evolution (loop, var);
1473 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1476 init = CHREC_LEFT (chrec);
1477 step = CHREC_RIGHT (chrec);
1479 /* If STEP is symbolic, we can't know whether INIT will be the
1480 minimum or maximum value in the range. */
1481 if (!is_gimple_min_invariant (step))
1484 /* Do not adjust ranges when chrec may wrap. */
1485 if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,
1486 cfg_loops->parray[CHREC_VARIABLE (chrec)],
1490 if (!POINTER_TYPE_P (TREE_TYPE (init))
1491 && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
1493 /* For VARYING or UNDEFINED ranges, just about anything we get
1494 from scalar evolutions should be better. */
1496 set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)),
1499 set_value_range (vr, VR_RANGE, init, TYPE_MAX_VALUE (TREE_TYPE (init)),
1502 else if (vr->type == VR_RANGE)
1509 /* INIT is the maximum value. If INIT is lower than VR->MAX
1510 but no smaller than VR->MIN, set VR->MAX to INIT. */
1511 if (compare_values (init, max) == -1)
1515 /* If we just created an invalid range with the minimum
1516 greater than the maximum, take the minimum all the
1518 if (compare_values (min, max) == 1)
1519 min = TYPE_MIN_VALUE (TREE_TYPE (min));
1524 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1525 if (compare_values (init, min) == 1)
1529 /* If we just created an invalid range with the minimum
1530 greater than the maximum, take the maximum all the
1532 if (compare_values (min, max) == 1)
1533 max = TYPE_MAX_VALUE (TREE_TYPE (max));
1537 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
1542 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1544 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1545 all the values in the ranges.
1547 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1549 - Return NULL_TREE if it is not always possible to determine the
1550 value of the comparison. */
1554 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1)
1556 /* VARYING or UNDEFINED ranges cannot be compared. */
1557 if (vr0->type == VR_VARYING
1558 || vr0->type == VR_UNDEFINED
1559 || vr1->type == VR_VARYING
1560 || vr1->type == VR_UNDEFINED)
1563 /* Anti-ranges need to be handled separately. */
1564 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
1566 /* If both are anti-ranges, then we cannot compute any
1568 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
1571 /* These comparisons are never statically computable. */
1578 /* Equality can be computed only between a range and an
1579 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1580 if (vr0->type == VR_RANGE)
1582 /* To simplify processing, make VR0 the anti-range. */
1583 value_range_t *tmp = vr0;
1588 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
1590 if (compare_values (vr0->min, vr1->min) == 0
1591 && compare_values (vr0->max, vr1->max) == 0)
1592 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1597 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1598 operands around and change the comparison code. */
1599 if (comp == GT_EXPR || comp == GE_EXPR)
1602 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
1608 if (comp == EQ_EXPR)
1610 /* Equality may only be computed if both ranges represent
1611 exactly one value. */
1612 if (compare_values (vr0->min, vr0->max) == 0
1613 && compare_values (vr1->min, vr1->max) == 0)
1615 int cmp_min = compare_values (vr0->min, vr1->min);
1616 int cmp_max = compare_values (vr0->max, vr1->max);
1617 if (cmp_min == 0 && cmp_max == 0)
1618 return boolean_true_node;
1619 else if (cmp_min != -2 && cmp_max != -2)
1620 return boolean_false_node;
1625 else if (comp == NE_EXPR)
1629 /* If VR0 is completely to the left or completely to the right
1630 of VR1, they are always different. Notice that we need to
1631 make sure that both comparisons yield similar results to
1632 avoid comparing values that cannot be compared at
1634 cmp1 = compare_values (vr0->max, vr1->min);
1635 cmp2 = compare_values (vr0->min, vr1->max);
1636 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
1637 return boolean_true_node;
1639 /* If VR0 and VR1 represent a single value and are identical,
1641 else if (compare_values (vr0->min, vr0->max) == 0
1642 && compare_values (vr1->min, vr1->max) == 0
1643 && compare_values (vr0->min, vr1->min) == 0
1644 && compare_values (vr0->max, vr1->max) == 0)
1645 return boolean_false_node;
1647 /* Otherwise, they may or may not be different. */
1651 else if (comp == LT_EXPR || comp == LE_EXPR)
1655 /* If VR0 is to the left of VR1, return true. */
1656 tst = compare_values (vr0->max, vr1->min);
1657 if ((comp == LT_EXPR && tst == -1)
1658 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1659 return boolean_true_node;
1661 /* If VR0 is to the right of VR1, return false. */
1662 tst = compare_values (vr0->min, vr1->max);
1663 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1664 || (comp == LE_EXPR && tst == 1))
1665 return boolean_false_node;
1667 /* Otherwise, we don't know. */
1675 /* Given a value range VR, a value VAL and a comparison code COMP, return
1676 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1677 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1678 always returns false. Return NULL_TREE if it is not always
1679 possible to determine the value of the comparison. */
1682 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val)
1684 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1687 /* Anti-ranges need to be handled separately. */
1688 if (vr->type == VR_ANTI_RANGE)
1690 /* For anti-ranges, the only predicates that we can compute at
1691 compile time are equality and inequality. */
1698 /* ~[VAL, VAL] == VAL is always false. */
1699 if (compare_values (vr->min, val) == 0
1700 && compare_values (vr->max, val) == 0)
1701 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1706 if (comp == EQ_EXPR)
1708 /* EQ_EXPR may only be computed if VR represents exactly
1710 if (compare_values (vr->min, vr->max) == 0)
1712 int cmp = compare_values (vr->min, val);
1714 return boolean_true_node;
1715 else if (cmp == -1 || cmp == 1 || cmp == 2)
1716 return boolean_false_node;
1718 else if (compare_values (val, vr->min) == -1
1719 || compare_values (vr->max, val) == -1)
1720 return boolean_false_node;
1724 else if (comp == NE_EXPR)
1726 /* If VAL is not inside VR, then they are always different. */
1727 if (compare_values (vr->max, val) == -1
1728 || compare_values (vr->min, val) == 1)
1729 return boolean_true_node;
1731 /* If VR represents exactly one value equal to VAL, then return
1733 if (compare_values (vr->min, vr->max) == 0
1734 && compare_values (vr->min, val) == 0)
1735 return boolean_false_node;
1737 /* Otherwise, they may or may not be different. */
1740 else if (comp == LT_EXPR || comp == LE_EXPR)
1744 /* If VR is to the left of VAL, return true. */
1745 tst = compare_values (vr->max, val);
1746 if ((comp == LT_EXPR && tst == -1)
1747 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1748 return boolean_true_node;
1750 /* If VR is to the right of VAL, return false. */
1751 tst = compare_values (vr->min, val);
1752 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1753 || (comp == LE_EXPR && tst == 1))
1754 return boolean_false_node;
1756 /* Otherwise, we don't know. */
1759 else if (comp == GT_EXPR || comp == GE_EXPR)
1763 /* If VR is to the right of VAL, return true. */
1764 tst = compare_values (vr->min, val);
1765 if ((comp == GT_EXPR && tst == 1)
1766 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
1767 return boolean_true_node;
1769 /* If VR is to the left of VAL, return false. */
1770 tst = compare_values (vr->max, val);
1771 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
1772 || (comp == GE_EXPR && tst == -1))
1773 return boolean_false_node;
1775 /* Otherwise, we don't know. */
1783 /* Debugging dumps. */
1785 void dump_value_range (FILE *, value_range_t *);
1786 void debug_value_range (value_range_t *);
1787 void dump_all_value_ranges (FILE *);
1788 void debug_all_value_ranges (void);
1789 void dump_vr_equiv (FILE *, bitmap);
1790 void debug_vr_equiv (bitmap);
1793 /* Dump value range VR to FILE. */
1796 dump_value_range (FILE *file, value_range_t *vr)
1799 fprintf (file, "[]");
1800 else if (vr->type == VR_UNDEFINED)
1801 fprintf (file, "UNDEFINED");
1802 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
1804 tree type = TREE_TYPE (vr->min);
1806 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
1808 if (INTEGRAL_TYPE_P (type)
1809 && !TYPE_UNSIGNED (type)
1810 && vr->min == TYPE_MIN_VALUE (type))
1811 fprintf (file, "-INF");
1813 print_generic_expr (file, vr->min, 0);
1815 fprintf (file, ", ");
1817 if (INTEGRAL_TYPE_P (type)
1818 && vr->max == TYPE_MAX_VALUE (type))
1819 fprintf (file, "+INF");
1821 print_generic_expr (file, vr->max, 0);
1823 fprintf (file, "]");
1830 fprintf (file, " EQUIVALENCES: { ");
1832 EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
1834 print_generic_expr (file, ssa_name (i), 0);
1835 fprintf (file, " ");
1839 fprintf (file, "} (%u elements)", c);
1842 else if (vr->type == VR_VARYING)
1843 fprintf (file, "VARYING");
1845 fprintf (file, "INVALID RANGE");
1849 /* Dump value range VR to stderr. */
1852 debug_value_range (value_range_t *vr)
1854 dump_value_range (stderr, vr);
1858 /* Dump value ranges of all SSA_NAMEs to FILE. */
1861 dump_all_value_ranges (FILE *file)
1865 for (i = 0; i < num_ssa_names; i++)
1869 print_generic_expr (file, ssa_name (i), 0);
1870 fprintf (file, ": ");
1871 dump_value_range (file, vr_value[i]);
1872 fprintf (file, "\n");
1876 fprintf (file, "\n");
1880 /* Dump all value ranges to stderr. */
1883 debug_all_value_ranges (void)
1885 dump_all_value_ranges (stderr);
1889 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
1890 create a new SSA name N and return the assertion assignment
1891 'V = ASSERT_EXPR <V, V OP W>'. */
1894 build_assert_expr_for (tree cond, tree v)
1898 gcc_assert (TREE_CODE (v) == SSA_NAME);
1899 n = duplicate_ssa_name (v, NULL_TREE);
1901 if (COMPARISON_CLASS_P (cond))
1903 tree a = build (ASSERT_EXPR, TREE_TYPE (v), v, cond);
1904 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, a);
1906 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1908 /* Given !V, build the assignment N = false. */
1909 tree op0 = TREE_OPERAND (cond, 0);
1910 gcc_assert (op0 == v);
1911 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
1913 else if (TREE_CODE (cond) == SSA_NAME)
1915 /* Given V, build the assignment N = true. */
1916 gcc_assert (v == cond);
1917 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
1922 SSA_NAME_DEF_STMT (n) = assertion;
1924 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
1925 operand of the ASSERT_EXPR. Register the new name and the old one
1926 in the replacement table so that we can fix the SSA web after
1927 adding all the ASSERT_EXPRs. */
1928 register_new_name_mapping (n, v);
1934 /* Return false if EXPR is a predicate expression involving floating
1938 fp_predicate (tree expr)
1940 return (COMPARISON_CLASS_P (expr)
1941 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
1945 /* If the range of values taken by OP can be inferred after STMT executes,
1946 return the comparison code (COMP_CODE_P) and value (VAL_P) that
1947 describes the inferred range. Return true if a range could be
1951 infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
1954 *comp_code_p = ERROR_MARK;
1956 /* Do not attempt to infer anything in names that flow through
1958 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1961 /* Similarly, don't infer anything from statements that may throw
1963 if (tree_could_throw_p (stmt))
1966 if (POINTER_TYPE_P (TREE_TYPE (op)))
1969 unsigned num_uses, num_derefs;
1971 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
1972 if (num_derefs > 0 && flag_delete_null_pointer_checks)
1974 /* We can only assume that a pointer dereference will yield
1975 non-NULL if -fdelete-null-pointer-checks is enabled. */
1976 *val_p = build_int_cst (TREE_TYPE (op), 0);
1977 *comp_code_p = NE_EXPR;
1986 void dump_asserts_for (FILE *, tree);
1987 void debug_asserts_for (tree);
1988 void dump_all_asserts (FILE *);
1989 void debug_all_asserts (void);
1991 /* Dump all the registered assertions for NAME to FILE. */
1994 dump_asserts_for (FILE *file, tree name)
1998 fprintf (file, "Assertions to be inserted for ");
1999 print_generic_expr (file, name, 0);
2000 fprintf (file, "\n");
2002 loc = asserts_for[SSA_NAME_VERSION (name)];
2005 fprintf (file, "\t");
2006 print_generic_expr (file, bsi_stmt (loc->si), 0);
2007 fprintf (file, "\n\tBB #%d", loc->bb->index);
2010 fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
2011 loc->e->dest->index);
2012 dump_edge_info (file, loc->e, 0);
2014 fprintf (file, "\n\tPREDICATE: ");
2015 print_generic_expr (file, name, 0);
2016 fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
2017 print_generic_expr (file, loc->val, 0);
2018 fprintf (file, "\n\n");
2022 fprintf (file, "\n");
2026 /* Dump all the registered assertions for NAME to stderr. */
2029 debug_asserts_for (tree name)
2031 dump_asserts_for (stderr, name);
2035 /* Dump all the registered assertions for all the names to FILE. */
2038 dump_all_asserts (FILE *file)
2043 fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
2044 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2045 dump_asserts_for (file, ssa_name (i));
2046 fprintf (file, "\n");
2050 /* Dump all the registered assertions for all the names to stderr. */
2053 debug_all_asserts (void)
2055 dump_all_asserts (stderr);
2059 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
2060 'NAME COMP_CODE VAL' at a location that dominates block BB or
2061 E->DEST, then register this location as a possible insertion point
2062 for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
2064 BB, E and SI provide the exact insertion point for the new
2065 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
2066 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
2067 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
2068 must not be NULL. */
2071 register_new_assert_for (tree name,
2072 enum tree_code comp_code,
2076 block_stmt_iterator si)
2078 assert_locus_t n, loc, last_loc;
2080 basic_block dest_bb;
2082 #if defined ENABLE_CHECKING
2083 gcc_assert (bb == NULL || e == NULL);
2086 gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
2087 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
2090 /* The new assertion A will be inserted at BB or E. We need to
2091 determine if the new location is dominated by a previously
2092 registered location for A. If we are doing an edge insertion,
2093 assume that A will be inserted at E->DEST. Note that this is not
2096 If E is a critical edge, it will be split. But even if E is
2097 split, the new block will dominate the same set of blocks that
2100 The reverse, however, is not true, blocks dominated by E->DEST
2101 will not be dominated by the new block created to split E. So,
2102 if the insertion location is on a critical edge, we will not use
2103 the new location to move another assertion previously registered
2104 at a block dominated by E->DEST. */
2105 dest_bb = (bb) ? bb : e->dest;
2107 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
2108 VAL at a block dominating DEST_BB, then we don't need to insert a new
2109 one. Similarly, if the same assertion already exists at a block
2110 dominated by DEST_BB and the new location is not on a critical
2111 edge, then update the existing location for the assertion (i.e.,
2112 move the assertion up in the dominance tree).
2114 Note, this is implemented as a simple linked list because there
2115 should not be more than a handful of assertions registered per
2116 name. If this becomes a performance problem, a table hashed by
2117 COMP_CODE and VAL could be implemented. */
2118 loc = asserts_for[SSA_NAME_VERSION (name)];
2123 if (loc->comp_code == comp_code
2125 || operand_equal_p (loc->val, val, 0)))
2127 /* If the assertion NAME COMP_CODE VAL has already been
2128 registered at a basic block that dominates DEST_BB, then
2129 we don't need to insert the same assertion again. Note
2130 that we don't check strict dominance here to avoid
2131 replicating the same assertion inside the same basic
2132 block more than once (e.g., when a pointer is
2133 dereferenced several times inside a block).
2135 An exception to this rule are edge insertions. If the
2136 new assertion is to be inserted on edge E, then it will
2137 dominate all the other insertions that we may want to
2138 insert in DEST_BB. So, if we are doing an edge
2139 insertion, don't do this dominance check. */
2141 && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
2144 /* Otherwise, if E is not a critical edge and DEST_BB
2145 dominates the existing location for the assertion, move
2146 the assertion up in the dominance tree by updating its
2147 location information. */
2148 if ((e == NULL || !EDGE_CRITICAL_P (e))
2149 && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
2158 /* Update the last node of the list and move to the next one. */
2163 /* If we didn't find an assertion already registered for
2164 NAME COMP_CODE VAL, add a new one at the end of the list of
2165 assertions associated with NAME. */
2166 n = xmalloc (sizeof (*n));
2170 n->comp_code = comp_code;
2177 asserts_for[SSA_NAME_VERSION (name)] = n;
2179 bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
2183 /* Try to register an edge assertion for SSA name NAME on edge E for
2184 the conditional jump pointed by SI. Return true if an assertion
2185 for NAME could be registered. */
2188 register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
2191 enum tree_code comp_code;
2193 stmt = bsi_stmt (si);
2195 /* Do not attempt to infer anything in names that flow through
2197 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
2200 /* If NAME was not found in the sub-graph reachable from E, then
2201 there's nothing to do. */
2202 if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
2205 /* We found a use of NAME in the sub-graph rooted at E->DEST.
2206 Register an assertion for NAME according to the value that NAME
2208 if (TREE_CODE (stmt) == COND_EXPR)
2210 /* If BB ends in a COND_EXPR then NAME then we should insert
2211 the original predicate on EDGE_TRUE_VALUE and the
2212 opposite predicate on EDGE_FALSE_VALUE. */
2213 tree cond = COND_EXPR_COND (stmt);
2214 bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
2216 /* Predicates may be a single SSA name or NAME OP VAL. */
2219 /* If the predicate is a name, it must be NAME, in which
2220 case we create the predicate NAME == true or
2221 NAME == false accordingly. */
2222 comp_code = EQ_EXPR;
2223 val = (is_else_edge) ? boolean_false_node : boolean_true_node;
2227 /* Otherwise, we have a comparison of the form NAME COMP VAL
2228 or VAL COMP NAME. */
2229 if (name == TREE_OPERAND (cond, 1))
2231 /* If the predicate is of the form VAL COMP NAME, flip
2232 COMP around because we need to register NAME as the
2233 first operand in the predicate. */
2234 comp_code = opposite_comparison (TREE_CODE (cond));
2235 val = TREE_OPERAND (cond, 0);
2239 /* The comparison is of the form NAME COMP VAL, so the
2240 comparison code remains unchanged. */
2241 comp_code = TREE_CODE (cond);
2242 val = TREE_OPERAND (cond, 1);
2245 /* If we are inserting the assertion on the ELSE edge, we
2246 need to invert the sign comparison. */
2248 comp_code = invert_tree_comparison (comp_code, 0);
2253 /* FIXME. Handle SWITCH_EXPR. */
2257 register_new_assert_for (name, comp_code, val, NULL, e, si);
2262 static bool find_assert_locations (basic_block bb);
2264 /* Determine whether the outgoing edges of BB should receive an
2265 ASSERT_EXPR for each of the operands of BB's last statement. The
2266 last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
2268 If any of the sub-graphs rooted at BB have an interesting use of
2269 the predicate operands, an assert location node is added to the
2270 list of assertions for the corresponding operands. */
2273 find_conditional_asserts (basic_block bb)
2276 block_stmt_iterator last_si;
2282 need_assert = false;
2283 last_si = bsi_last (bb);
2284 last = bsi_stmt (last_si);
2286 /* Look for uses of the operands in each of the sub-graphs
2287 rooted at BB. We need to check each of the outgoing edges
2288 separately, so that we know what kind of ASSERT_EXPR to
2290 FOR_EACH_EDGE (e, ei, bb->succs)
2295 /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
2296 Otherwise, when we finish traversing each of the sub-graphs, we
2297 won't know whether the variables were found in the sub-graphs or
2298 if they had been found in a block upstream from BB. */
2299 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2300 RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2302 /* Traverse the strictly dominated sub-graph rooted at E->DEST
2303 to determine if any of the operands in the conditional
2304 predicate are used. */
2306 need_assert |= find_assert_locations (e->dest);
2308 /* Register the necessary assertions for each operand in the
2309 conditional predicate. */
2310 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2311 need_assert |= register_edge_assert_for (op, e, last_si);
2314 /* Finally, indicate that we have found the operands in the
2316 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2317 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2323 /* Traverse all the statements in block BB looking for statements that
2324 may generate useful assertions for the SSA names in their operand.
2325 If a statement produces a useful assertion A for name N_i, then the
2326 list of assertions already generated for N_i is scanned to
2327 determine if A is actually needed.
2329 If N_i already had the assertion A at a location dominating the
2330 current location, then nothing needs to be done. Otherwise, the
2331 new location for A is recorded instead.
2333 1- For every statement S in BB, all the variables used by S are
2334 added to bitmap FOUND_IN_SUBGRAPH.
2336 2- If statement S uses an operand N in a way that exposes a known
2337 value range for N, then if N was not already generated by an
2338 ASSERT_EXPR, create a new assert location for N. For instance,
2339 if N is a pointer and the statement dereferences it, we can
2340 assume that N is not NULL.
2342 3- COND_EXPRs are a special case of #2. We can derive range
2343 information from the predicate but need to insert different
2344 ASSERT_EXPRs for each of the sub-graphs rooted at the
2345 conditional block. If the last statement of BB is a conditional
2346 expression of the form 'X op Y', then
2348 a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
2350 b) If the conditional is the only entry point to the sub-graph
2351 corresponding to the THEN_CLAUSE, recurse into it. On
2352 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
2353 an ASSERT_EXPR is added for the corresponding variable.
2355 c) Repeat step (b) on the ELSE_CLAUSE.
2357 d) Mark X and Y in FOUND_IN_SUBGRAPH.
2366 In this case, an assertion on the THEN clause is useful to
2367 determine that 'a' is always 9 on that edge. However, an assertion
2368 on the ELSE clause would be unnecessary.
2370 4- If BB does not end in a conditional expression, then we recurse
2371 into BB's dominator children.
2373 At the end of the recursive traversal, every SSA name will have a
2374 list of locations where ASSERT_EXPRs should be added. When a new
2375 location for name N is found, it is registered by calling
2376 register_new_assert_for. That function keeps track of all the
2377 registered assertions to prevent adding unnecessary assertions.
2378 For instance, if a pointer P_4 is dereferenced more than once in a
2379 dominator tree, only the location dominating all the dereference of
2380 P_4 will receive an ASSERT_EXPR.
2382 If this function returns true, then it means that there are names
2383 for which we need to generate ASSERT_EXPRs. Those assertions are
2384 inserted by process_assert_insertions.
2386 TODO. Handle SWITCH_EXPR. */
2389 find_assert_locations (basic_block bb)
2391 block_stmt_iterator si;
2396 if (TEST_BIT (blocks_visited, bb->index))
2399 SET_BIT (blocks_visited, bb->index);
2401 need_assert = false;
2403 /* Traverse all PHI nodes in BB marking used operands. */
2404 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2406 use_operand_p arg_p;
2409 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
2411 tree arg = USE_FROM_PTR (arg_p);
2412 if (TREE_CODE (arg) == SSA_NAME)
2414 gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
2415 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
2420 /* Traverse all the statements in BB marking used names and looking
2421 for statements that may infer assertions for their used operands. */
2423 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2428 stmt = bsi_stmt (si);
2430 /* See if we can derive an assertion for any of STMT's operands. */
2431 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
2434 enum tree_code comp_code;
2436 /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside
2437 the sub-graph of a conditional block, when we return from
2438 this recursive walk, our parent will use the
2439 FOUND_IN_SUBGRAPH bitset to determine if one of the
2440 operands it was looking for was present in the sub-graph. */
2441 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2443 /* If OP is used only once, namely in this STMT, don't
2444 bother creating an ASSERT_EXPR for it. Such an
2445 ASSERT_EXPR would do nothing but increase compile time.
2446 Experiments show that with this simple check, we can save
2447 more than 20% of ASSERT_EXPRs. */
2448 if (has_single_use (op))
2451 /* If OP is used in such a way that we can infer a value
2452 range for it, and we don't find a previous assertion for
2453 it, create a new assertion location node for OP. */
2454 if (infer_value_range (stmt, op, &comp_code, &value))
2456 register_new_assert_for (op, comp_code, value, bb, NULL, si);
2461 /* Remember the last statement of the block. */
2465 /* If BB's last statement is a conditional expression
2466 involving integer operands, recurse into each of the sub-graphs
2467 rooted at BB to determine if we need to add ASSERT_EXPRs. */
2469 && TREE_CODE (last) == COND_EXPR
2470 && !fp_predicate (COND_EXPR_COND (last))
2471 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
2472 need_assert |= find_conditional_asserts (bb);
2474 /* Recurse into the dominator children of BB. */
2475 for (son = first_dom_son (CDI_DOMINATORS, bb);
2477 son = next_dom_son (CDI_DOMINATORS, son))
2478 need_assert |= find_assert_locations (son);
2484 /* Create an ASSERT_EXPR for NAME and insert it in the location
2485 indicated by LOC. Return true if we made any edge insertions. */
2488 process_assert_insertions_for (tree name, assert_locus_t loc)
2490 /* Build the comparison expression NAME_i COMP_CODE VAL. */
2491 tree stmt, cond, assert_expr;
2495 cond = build (loc->comp_code, boolean_type_node, name, loc->val);
2496 assert_expr = build_assert_expr_for (cond, name);
2500 /* We have been asked to insert the assertion on an edge. This
2501 is used only by COND_EXPR and SWITCH_EXPR assertions. */
2502 #if defined ENABLE_CHECKING
2503 gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
2504 || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
2507 bsi_insert_on_edge (loc->e, assert_expr);
2511 /* Otherwise, we can insert right after LOC->SI iff the
2512 statement must not be the last statement in the block. */
2513 stmt = bsi_stmt (loc->si);
2514 if (!stmt_ends_bb_p (stmt))
2516 bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
2520 /* If STMT must be the last statement in BB, we can only insert new
2521 assertions on the non-abnormal edge out of BB. Note that since
2522 STMT is not control flow, there may only be one non-abnormal edge
2524 FOR_EACH_EDGE (e, ei, loc->bb->succs)
2525 if (!(e->flags & EDGE_ABNORMAL))
2527 bsi_insert_on_edge (e, assert_expr);
2535 /* Process all the insertions registered for every name N_i registered
2536 in NEED_ASSERT_FOR. The list of assertions to be inserted are
2537 found in ASSERTS_FOR[i]. */
2540 process_assert_insertions (void)
2544 bool update_edges_p = false;
2545 int num_asserts = 0;
2547 if (dump_file && (dump_flags & TDF_DETAILS))
2548 dump_all_asserts (dump_file);
2550 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2552 assert_locus_t loc = asserts_for[i];
2557 assert_locus_t next = loc->next;
2558 update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
2566 bsi_commit_edge_inserts ();
2568 if (dump_file && (dump_flags & TDF_STATS))
2569 fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
2574 /* Traverse the flowgraph looking for conditional jumps to insert range
2575 expressions. These range expressions are meant to provide information
2576 to optimizations that need to reason in terms of value ranges. They
2577 will not be expanded into RTL. For instance, given:
2586 this pass will transform the code into:
2592 x = ASSERT_EXPR <x, x < y>
2597 y = ASSERT_EXPR <y, x <= y>
2601 The idea is that once copy and constant propagation have run, other
2602 optimizations will be able to determine what ranges of values can 'x'
2603 take in different paths of the code, simply by checking the reaching
2604 definition of 'x'. */
2607 insert_range_assertions (void)
2613 found_in_subgraph = sbitmap_alloc (num_ssa_names);
2614 sbitmap_zero (found_in_subgraph);
2616 blocks_visited = sbitmap_alloc (last_basic_block);
2617 sbitmap_zero (blocks_visited);
2619 need_assert_for = BITMAP_ALLOC (NULL);
2620 asserts_for = xmalloc (num_ssa_names * sizeof (assert_locus_t));
2621 memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t));
2623 calculate_dominance_info (CDI_DOMINATORS);
2625 update_ssa_p = false;
2626 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2627 if (find_assert_locations (e->dest))
2628 update_ssa_p = true;
2632 process_assert_insertions ();
2633 update_ssa (TODO_update_ssa_no_phi);
2636 if (dump_file && (dump_flags & TDF_DETAILS))
2638 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
2639 dump_function_to_file (current_function_decl, dump_file, dump_flags);
2642 sbitmap_free (found_in_subgraph);
2644 BITMAP_FREE (need_assert_for);
2648 /* Convert range assertion expressions into the implied copies.
2650 FIXME, this will eventually lead to copy propagation removing the
2651 names that had useful range information attached to them. For
2652 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
2653 then N_i will have the range [3, +INF].
2655 However, by converting the assertion into the implied copy
2656 operation N_i = N_j, we will then copy-propagate N_j into the uses
2657 of N_i and lose the range information. We may want to hold on to
2658 ASSERT_EXPRs a little while longer as the ranges could be used in
2659 things like jump threading.
2661 The problem with keeping ASSERT_EXPRs around is that passes after
2662 VRP need to handle them appropriately. */
2665 remove_range_assertions (void)
2668 block_stmt_iterator si;
2671 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2673 tree stmt = bsi_stmt (si);
2675 if (TREE_CODE (stmt) == MODIFY_EXPR
2676 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
2678 tree rhs = TREE_OPERAND (stmt, 1);
2679 tree cond = fold (ASSERT_EXPR_COND (rhs));
2680 gcc_assert (cond != boolean_false_node);
2681 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
2688 /* Return true if STMT is interesting for VRP. */
2691 stmt_interesting_for_vrp (tree stmt)
2693 if (TREE_CODE (stmt) == PHI_NODE
2694 && is_gimple_reg (PHI_RESULT (stmt))
2695 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
2696 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
2698 else if (TREE_CODE (stmt) == MODIFY_EXPR)
2700 tree lhs = TREE_OPERAND (stmt, 0);
2702 if (TREE_CODE (lhs) == SSA_NAME
2703 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2704 || POINTER_TYPE_P (TREE_TYPE (lhs)))
2705 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
2708 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
2715 /* Initialize local data structures for VRP. Return true if VRP
2716 is worth running (i.e. if we found any statements that could
2717 benefit from range information). */
2720 vrp_initialize (void)
2724 vr_value = xmalloc (num_ssa_names * sizeof (value_range_t *));
2725 memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *));
2729 block_stmt_iterator si;
2732 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2734 if (!stmt_interesting_for_vrp (phi))
2736 tree lhs = PHI_RESULT (phi);
2737 set_value_range_to_varying (get_value_range (lhs));
2738 DONT_SIMULATE_AGAIN (phi) = true;
2741 DONT_SIMULATE_AGAIN (phi) = false;
2744 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2746 tree stmt = bsi_stmt (si);
2748 if (!stmt_interesting_for_vrp (stmt))
2752 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
2753 set_value_range_to_varying (get_value_range (def));
2754 DONT_SIMULATE_AGAIN (stmt) = true;
2758 DONT_SIMULATE_AGAIN (stmt) = false;
2765 /* Visit assignment STMT. If it produces an interesting range, record
2766 the SSA name in *OUTPUT_P. */
2768 static enum ssa_prop_result
2769 vrp_visit_assignment (tree stmt, tree *output_p)
2774 lhs = TREE_OPERAND (stmt, 0);
2775 rhs = TREE_OPERAND (stmt, 1);
2777 /* We only keep track of ranges in integral and pointer types. */
2778 if (TREE_CODE (lhs) == SSA_NAME
2779 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2780 || POINTER_TYPE_P (TREE_TYPE (lhs))))
2783 value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2785 extract_range_from_expr (&new_vr, rhs);
2787 /* If STMT is inside a loop, we may be able to know something
2788 else about the range of LHS by examining scalar evolution
2790 if (cfg_loops && (l = loop_containing_stmt (stmt)))
2791 adjust_range_with_scev (&new_vr, l, stmt, lhs);
2793 if (update_value_range (lhs, &new_vr))
2797 if (dump_file && (dump_flags & TDF_DETAILS))
2799 fprintf (dump_file, "Found new range for ");
2800 print_generic_expr (dump_file, lhs, 0);
2801 fprintf (dump_file, ": ");
2802 dump_value_range (dump_file, &new_vr);
2803 fprintf (dump_file, "\n\n");
2806 if (new_vr.type == VR_VARYING)
2807 return SSA_PROP_VARYING;
2809 return SSA_PROP_INTERESTING;
2812 return SSA_PROP_NOT_INTERESTING;
2815 /* Every other statement produces no useful ranges. */
2816 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
2817 set_value_range_to_varying (get_value_range (def));
2819 return SSA_PROP_VARYING;
2823 /* Compare all the value ranges for names equivalent to VAR with VAL
2824 using comparison code COMP. Return the same value returned by
2825 compare_range_with_value. */
2828 compare_name_with_value (enum tree_code comp, tree var, tree val)
2835 t = retval = NULL_TREE;
2837 /* Get the set of equivalences for VAR. */
2838 e = get_value_range (var)->equiv;
2840 /* Add VAR to its own set of equivalences so that VAR's value range
2841 is processed by this loop (otherwise, we would have to replicate
2842 the body of the loop just to check VAR's value range). */
2843 bitmap_set_bit (e, SSA_NAME_VERSION (var));
2845 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
2847 value_range_t equiv_vr = *(vr_value[i]);
2849 /* If name N_i does not have a valid range, use N_i as its own
2850 range. This allows us to compare against names that may
2851 have N_i in their ranges. */
2852 if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
2854 equiv_vr.type = VR_RANGE;
2855 equiv_vr.min = ssa_name (i);
2856 equiv_vr.max = ssa_name (i);
2859 t = compare_range_with_value (comp, &equiv_vr, val);
2862 /* All the ranges should compare the same against VAL. */
2863 gcc_assert (retval == NULL || t == retval);
2868 /* Remove VAR from its own equivalence set. */
2869 bitmap_clear_bit (e, SSA_NAME_VERSION (var));
2874 /* We couldn't find a non-NULL value for the predicate. */
2879 /* Given a comparison code COMP and names N1 and N2, compare all the
2880 ranges equivalent to N1 against all the ranges equivalent to N2
2881 to determine the value of N1 COMP N2. Return the same value
2882 returned by compare_ranges. */
2885 compare_names (enum tree_code comp, tree n1, tree n2)
2889 bitmap_iterator bi1, bi2;
2892 /* Compare the ranges of every name equivalent to N1 against the
2893 ranges of every name equivalent to N2. */
2894 e1 = get_value_range (n1)->equiv;
2895 e2 = get_value_range (n2)->equiv;
2897 /* Add N1 and N2 to their own set of equivalences to avoid
2898 duplicating the body of the loop just to check N1 and N2
2900 bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
2901 bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
2903 /* If the equivalence sets have a common intersection, then the two
2904 names can be compared without checking their ranges. */
2905 if (bitmap_intersect_p (e1, e2))
2907 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2908 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2910 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
2912 : boolean_false_node;
2915 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2916 N2 to their own set of equivalences to avoid duplicating the body
2917 of the loop just to check N1 and N2 ranges. */
2918 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
2920 value_range_t vr1 = *(vr_value[i1]);
2922 /* If the range is VARYING or UNDEFINED, use the name itself. */
2923 if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
2925 vr1.type = VR_RANGE;
2926 vr1.min = ssa_name (i1);
2927 vr1.max = ssa_name (i1);
2930 t = retval = NULL_TREE;
2931 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
2933 value_range_t vr2 = *(vr_value[i2]);
2935 if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
2937 vr2.type = VR_RANGE;
2938 vr2.min = ssa_name (i2);
2939 vr2.max = ssa_name (i2);
2942 t = compare_ranges (comp, &vr1, &vr2);
2945 /* All the ranges in the equivalent sets should compare
2947 gcc_assert (retval == NULL || t == retval);
2954 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2955 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2960 /* None of the equivalent ranges are useful in computing this
2962 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2963 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2968 /* Given a conditional predicate COND, try to determine if COND yields
2969 true or false based on the value ranges of its operands. Return
2970 BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
2971 BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
2972 NULL if the conditional cannot be evaluated at compile time.
2974 If USE_EQUIV_P is true, the ranges of all the names equivalent with
2975 the operands in COND are used when trying to compute its value.
2976 This is only used during final substitution. During propagation,
2977 we only check the range of each variable and not its equivalents. */
2980 vrp_evaluate_conditional (tree cond, bool use_equiv_p)
2982 gcc_assert (TREE_CODE (cond) == SSA_NAME
2983 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
2985 if (TREE_CODE (cond) == SSA_NAME)
2991 retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node);
2994 value_range_t *vr = get_value_range (cond);
2995 retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node);
2998 /* If COND has a known boolean range, return it. */
3002 /* Otherwise, if COND has a symbolic range of exactly one value,
3004 vr = get_value_range (cond);
3005 if (vr->type == VR_RANGE && vr->min == vr->max)
3010 tree op0 = TREE_OPERAND (cond, 0);
3011 tree op1 = TREE_OPERAND (cond, 1);
3013 /* We only deal with integral and pointer types. */
3014 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3015 && !POINTER_TYPE_P (TREE_TYPE (op0)))
3020 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
3021 return compare_names (TREE_CODE (cond), op0, op1);
3022 else if (TREE_CODE (op0) == SSA_NAME)
3023 return compare_name_with_value (TREE_CODE (cond), op0, op1);
3024 else if (TREE_CODE (op1) == SSA_NAME)
3025 return compare_name_with_value (
3026 opposite_comparison (TREE_CODE (cond)), op1, op0);
3030 value_range_t *vr0, *vr1;
3032 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
3033 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
3036 return compare_ranges (TREE_CODE (cond), vr0, vr1);
3037 else if (vr0 && vr1 == NULL)
3038 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
3039 else if (vr0 == NULL && vr1)
3040 return compare_range_with_value (
3041 opposite_comparison (TREE_CODE (cond)), vr1, op0);
3045 /* Anything else cannot be computed statically. */
3050 /* Visit conditional statement STMT. If we can determine which edge
3051 will be taken out of STMT's basic block, record it in
3052 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
3053 SSA_PROP_VARYING. */
3055 static enum ssa_prop_result
3056 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
3060 *taken_edge_p = NULL;
3062 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
3063 add ASSERT_EXPRs for them. */
3064 if (TREE_CODE (stmt) == SWITCH_EXPR)
3065 return SSA_PROP_VARYING;
3067 cond = COND_EXPR_COND (stmt);
3069 if (dump_file && (dump_flags & TDF_DETAILS))
3074 fprintf (dump_file, "\nVisiting conditional with predicate: ");
3075 print_generic_expr (dump_file, cond, 0);
3076 fprintf (dump_file, "\nWith known ranges\n");
3078 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
3080 fprintf (dump_file, "\t");
3081 print_generic_expr (dump_file, use, 0);
3082 fprintf (dump_file, ": ");
3083 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
3086 fprintf (dump_file, "\n");
3089 /* Compute the value of the predicate COND by checking the known
3090 ranges of each of its operands.
3092 Note that we cannot evaluate all the equivalent ranges here
3093 because those ranges may not yet be final and with the current
3094 propagation strategy, we cannot determine when the value ranges
3095 of the names in the equivalence set have changed.
3097 For instance, given the following code fragment
3101 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
3105 Assume that on the first visit to i_14, i_5 has the temporary
3106 range [8, 8] because the second argument to the PHI function is
3107 not yet executable. We derive the range ~[0, 0] for i_14 and the
3108 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
3109 the first time, since i_14 is equivalent to the range [8, 8], we
3110 determine that the predicate is always false.
3112 On the next round of propagation, i_13 is determined to be
3113 VARYING, which causes i_5 to drop down to VARYING. So, another
3114 visit to i_14 is scheduled. In this second visit, we compute the
3115 exact same range and equivalence set for i_14, namely ~[0, 0] and
3116 { i_5 }. But we did not have the previous range for i_5
3117 registered, so vrp_visit_assignment thinks that the range for
3118 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
3119 is not visited again, which stops propagation from visiting
3120 statements in the THEN clause of that if().
3122 To properly fix this we would need to keep the previous range
3123 value for the names in the equivalence set. This way we would've
3124 discovered that from one visit to the other i_5 changed from
3125 range [8, 8] to VR_VARYING.
3127 However, fixing this apparent limitation may not be worth the
3128 additional checking. Testing on several code bases (GCC, DLV,
3129 MICO, TRAMP3D and SPEC2000) showed that doing this results in
3130 4 more predicates folded in SPEC. */
3131 val = vrp_evaluate_conditional (cond, false);
3133 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
3135 if (dump_file && (dump_flags & TDF_DETAILS))
3137 fprintf (dump_file, "\nPredicate evaluates to: ");
3138 if (val == NULL_TREE)
3139 fprintf (dump_file, "DON'T KNOW\n");
3141 print_generic_stmt (dump_file, val, 0);
3144 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
3148 /* Evaluate statement STMT. If the statement produces a useful range,
3149 return SSA_PROP_INTERESTING and record the SSA name with the
3150 interesting range into *OUTPUT_P.
3152 If STMT is a conditional branch and we can determine its truth
3153 value, the taken edge is recorded in *TAKEN_EDGE_P.
3155 If STMT produces a varying value, return SSA_PROP_VARYING. */
3157 static enum ssa_prop_result
3158 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
3164 if (dump_file && (dump_flags & TDF_DETAILS))
3166 fprintf (dump_file, "\nVisiting statement:\n");
3167 print_generic_stmt (dump_file, stmt, dump_flags);
3168 fprintf (dump_file, "\n");
3171 ann = stmt_ann (stmt);
3172 if (TREE_CODE (stmt) == MODIFY_EXPR
3173 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3174 return vrp_visit_assignment (stmt, output_p);
3175 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3176 return vrp_visit_cond_stmt (stmt, taken_edge_p);
3178 /* All other statements produce nothing of interest for VRP, so mark
3179 their outputs varying and prevent further simulation. */
3180 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3181 set_value_range_to_varying (get_value_range (def));
3183 return SSA_PROP_VARYING;
3187 /* Meet operation for value ranges. Given two value ranges VR0 and
3188 VR1, store in VR0 the result of meeting VR0 and VR1.
3190 The meeting rules are as follows:
3192 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
3194 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
3195 union of VR0 and VR1. */
3198 vrp_meet (value_range_t *vr0, value_range_t *vr1)
3200 if (vr0->type == VR_UNDEFINED)
3202 copy_value_range (vr0, vr1);
3206 if (vr1->type == VR_UNDEFINED)
3208 /* Nothing to do. VR0 already has the resulting range. */
3212 if (vr0->type == VR_VARYING)
3214 /* Nothing to do. VR0 already has the resulting range. */
3218 if (vr1->type == VR_VARYING)
3220 set_value_range_to_varying (vr0);
3224 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
3226 /* If VR0 and VR1 have a non-empty intersection, compute the
3227 union of both ranges. */
3228 if (value_ranges_intersect_p (vr0, vr1))
3233 /* The lower limit of the new range is the minimum of the
3234 two ranges. If they cannot be compared, the result is
3236 cmp = compare_values (vr0->min, vr1->min);
3237 if (cmp == 0 || cmp == 1)
3243 set_value_range_to_varying (vr0);
3247 /* Similarly, the upper limit of the new range is the
3248 maximum of the two ranges. If they cannot be compared,
3249 the result is VARYING. */
3250 cmp = compare_values (vr0->max, vr1->max);
3251 if (cmp == 0 || cmp == -1)
3257 set_value_range_to_varying (vr0);
3261 /* The resulting set of equivalences is the intersection of
3263 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3264 bitmap_and_into (vr0->equiv, vr1->equiv);
3266 set_value_range (vr0, vr0->type, min, max, vr0->equiv);
3271 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3273 /* Two anti-ranges meet only if they are both identical. */
3274 if (compare_values (vr0->min, vr1->min) == 0
3275 && compare_values (vr0->max, vr1->max) == 0
3276 && compare_values (vr0->min, vr0->max) == 0)
3278 /* The resulting set of equivalences is the intersection of
3280 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3281 bitmap_and_into (vr0->equiv, vr1->equiv);
3286 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
3288 /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4]
3289 meet only if the ranges have an empty intersection. The
3290 result of the meet operation is the anti-range. */
3291 if (!symbolic_range_p (vr0)
3292 && !symbolic_range_p (vr1)
3293 && !value_ranges_intersect_p (vr0, vr1))
3295 if (vr1->type == VR_ANTI_RANGE)
3296 copy_value_range (vr0, vr1);
3307 /* The two range VR0 and VR1 do not meet. Before giving up and
3308 setting the result to VARYING, see if we can at least derive a
3309 useful anti-range. */
3310 if (!symbolic_range_p (vr0)
3311 && !range_includes_zero_p (vr0)
3312 && !symbolic_range_p (vr1)
3313 && !range_includes_zero_p (vr1))
3314 set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
3316 set_value_range_to_varying (vr0);
3320 /* Visit all arguments for PHI node PHI that flow through executable
3321 edges. If a valid value range can be derived from all the incoming
3322 value ranges, set a new range for the LHS of PHI. */
3324 static enum ssa_prop_result
3325 vrp_visit_phi_node (tree phi)
3328 tree lhs = PHI_RESULT (phi);
3329 value_range_t *lhs_vr = get_value_range (lhs);
3330 value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3332 copy_value_range (&vr_result, lhs_vr);
3334 if (dump_file && (dump_flags & TDF_DETAILS))
3336 fprintf (dump_file, "\nVisiting PHI node: ");
3337 print_generic_expr (dump_file, phi, dump_flags);
3340 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
3342 edge e = PHI_ARG_EDGE (phi, i);
3344 if (dump_file && (dump_flags & TDF_DETAILS))
3347 "\n Argument #%d (%d -> %d %sexecutable)\n",
3348 i, e->src->index, e->dest->index,
3349 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
3352 if (e->flags & EDGE_EXECUTABLE)
3354 tree arg = PHI_ARG_DEF (phi, i);
3355 value_range_t vr_arg;
3357 if (TREE_CODE (arg) == SSA_NAME)
3358 vr_arg = *(get_value_range (arg));
3361 vr_arg.type = VR_RANGE;
3364 vr_arg.equiv = NULL;
3367 if (dump_file && (dump_flags & TDF_DETAILS))
3369 fprintf (dump_file, "\t");
3370 print_generic_expr (dump_file, arg, dump_flags);
3371 fprintf (dump_file, "\n\tValue: ");
3372 dump_value_range (dump_file, &vr_arg);
3373 fprintf (dump_file, "\n");
3376 vrp_meet (&vr_result, &vr_arg);
3378 if (vr_result.type == VR_VARYING)
3383 if (vr_result.type == VR_VARYING)
3386 /* To prevent infinite iterations in the algorithm, derive ranges
3387 when the new value is slightly bigger or smaller than the
3389 if (lhs_vr->type == VR_RANGE)
3391 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
3393 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
3394 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
3396 /* If the new minimum is smaller or larger than the previous
3397 one, go all the way to -INF. In the first case, to avoid
3398 iterating millions of times to reach -INF, and in the
3399 other case to avoid infinite bouncing between different
3401 if (cmp_min > 0 || cmp_min < 0)
3402 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
3404 /* Similarly, if the new maximum is smaller or larger than
3405 the previous one, go all the way to +INF. */
3406 if (cmp_max < 0 || cmp_max > 0)
3407 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
3409 /* If we ended up with a (-INF, +INF) range, set it to
3411 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
3412 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
3417 /* If the new range is different than the previous value, keep
3419 if (update_value_range (lhs, &vr_result))
3420 return SSA_PROP_INTERESTING;
3422 /* Nothing changed, don't add outgoing edges. */
3423 return SSA_PROP_NOT_INTERESTING;
3425 /* No match found. Set the LHS to VARYING. */
3427 set_value_range_to_varying (lhs_vr);
3428 return SSA_PROP_VARYING;
3431 /* Walk through the IL simplifying expressions using knowledge
3435 simplify_using_ranges (void)
3441 block_stmt_iterator bsi;
3443 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3445 tree stmt = bsi_stmt (bsi);
3447 if (TREE_CODE (stmt) == MODIFY_EXPR)
3449 tree rhs = TREE_OPERAND (stmt, 1);
3450 enum tree_code rhs_code = TREE_CODE (rhs);
3452 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
3453 and BIT_AND_EXPR respectively if the first operand is greater
3454 than zero and the second operand is an exact power of two. */
3455 if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
3456 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
3457 && integer_pow2p (TREE_OPERAND (rhs, 1)))
3460 tree op = TREE_OPERAND (rhs, 0);
3461 value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
3463 if (TYPE_UNSIGNED (TREE_TYPE (op)))
3465 val = integer_one_node;
3469 val = compare_range_with_value (GT_EXPR, vr,
3473 if (val && integer_onep (val))
3476 tree op0 = TREE_OPERAND (rhs, 0);
3477 tree op1 = TREE_OPERAND (rhs, 1);
3479 if (rhs_code == TRUNC_DIV_EXPR)
3481 t = build_int_cst (NULL_TREE, tree_log2 (op1));
3482 t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
3486 t = build_int_cst (TREE_TYPE (op1), 1);
3487 t = int_const_binop (MINUS_EXPR, op1, t, 0);
3488 t = fold_convert (TREE_TYPE (op0), t);
3489 t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
3492 TREE_OPERAND (stmt, 1) = t;
3498 /* Transform ABS (X) into X or -X as appropriate. */
3499 if (rhs_code == ABS_EXPR
3500 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
3501 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
3504 tree op = TREE_OPERAND (rhs, 0);
3505 tree type = TREE_TYPE (op);
3506 value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
3508 if (TYPE_UNSIGNED (type))
3510 val = integer_zero_node;
3514 val = compare_range_with_value (LE_EXPR, vr,
3518 val = compare_range_with_value (GE_EXPR, vr,
3523 if (integer_zerop (val))
3524 val = integer_one_node;
3525 else if (integer_onep (val))
3526 val = integer_zero_node;
3531 && (integer_onep (val) || integer_zerop (val)))
3535 if (integer_onep (val))
3536 t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
3540 TREE_OPERAND (stmt, 1) = t;
3547 /* TODO. Simplify conditionals. */
3553 /* Traverse all the blocks folding conditionals with known ranges. */
3559 prop_value_t *single_val_range;
3560 bool do_value_subst_p;
3564 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
3565 dump_all_value_ranges (dump_file);
3566 fprintf (dump_file, "\n");
3569 /* We may have ended with ranges that have exactly one value. Those
3570 values can be substituted as any other copy/const propagated
3571 value using substitute_and_fold. */
3572 single_val_range = xmalloc (num_ssa_names * sizeof (*single_val_range));
3573 memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range));
3575 do_value_subst_p = false;
3576 for (i = 0; i < num_ssa_names; i++)
3578 && vr_value[i]->type == VR_RANGE
3579 && vr_value[i]->min == vr_value[i]->max)
3581 single_val_range[i].value = vr_value[i]->min;
3582 do_value_subst_p = true;
3585 if (!do_value_subst_p)
3587 /* We found no single-valued ranges, don't waste time trying to
3588 do single value substitution in substitute_and_fold. */
3589 free (single_val_range);
3590 single_val_range = NULL;
3593 substitute_and_fold (single_val_range, true);
3595 /* One could argue all simplifications should be done here
3596 rather than using substitute_and_fold since this code
3597 is going to have to perform a complete walk through the
3599 simplify_using_ranges ();
3601 /* Free allocated memory. */
3602 for (i = 0; i < num_ssa_names; i++)
3605 BITMAP_FREE (vr_value[i]->equiv);
3609 free (single_val_range);
3614 /* Main entry point to VRP (Value Range Propagation). This pass is
3615 loosely based on J. R. C. Patterson, ``Accurate Static Branch
3616 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
3617 Programming Language Design and Implementation, pp. 67-78, 1995.
3618 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
3620 This is essentially an SSA-CCP pass modified to deal with ranges
3621 instead of constants.
3623 While propagating ranges, we may find that two or more SSA name
3624 have equivalent, though distinct ranges. For instance,
3627 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0>
3629 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
3633 In the code above, pointer p_5 has range [q_2, q_2], but from the
3634 code we can also determine that p_5 cannot be NULL and, if q_2 had
3635 a non-varying range, p_5's range should also be compatible with it.
3637 These equivalences are created by two expressions: ASSERT_EXPR and
3638 copy operations. Since p_5 is an assertion on p_4, and p_4 was the
3639 result of another assertion, then we can use the fact that p_5 and
3640 p_4 are equivalent when evaluating p_5's range.
3642 Together with value ranges, we also propagate these equivalences
3643 between names so that we can take advantage of information from
3644 multiple ranges when doing final replacement. Note that this
3645 equivalency relation is transitive but not symmetric.
3647 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
3648 cannot assert that q_2 is equivalent to p_5 because q_2 may be used
3649 in contexts where that assertion does not hold (e.g., in line 6).
3651 TODO, the main difference between this pass and Patterson's is that
3652 we do not propagate edge probabilities. We only compute whether
3653 edges can be taken or not. That is, instead of having a spectrum
3654 of jump probabilities between 0 and 1, we only deal with 0, 1 and
3655 DON'T KNOW. In the future, it may be worthwhile to propagate
3656 probabilities to aid branch prediction. */
3661 insert_range_assertions ();
3663 cfg_loops = loop_optimizer_init (NULL);
3665 scev_initialize (cfg_loops);
3668 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
3674 loop_optimizer_finalize (cfg_loops, NULL);
3675 current_loops = NULL;
3678 remove_range_assertions ();
3684 return flag_tree_vrp != 0;
3687 struct tree_opt_pass pass_vrp =
3690 gate_vrp, /* gate */
3691 execute_vrp, /* execute */
3694 0, /* static_pass_number */
3695 TV_TREE_VRP, /* tv_id */
3696 PROP_ssa | PROP_alias, /* properties_required */
3697 0, /* properties_provided */
3698 0, /* properties_destroyed */
3699 0, /* todo_flags_start */
3704 | TODO_update_ssa, /* todo_flags_finish */