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 /* Extract range information from a binary expression EXPR based on
973 the ranges of each of its operands and the expression code. */
976 extract_range_from_binary_expr (value_range_t *vr, tree expr)
978 enum tree_code code = TREE_CODE (expr);
979 tree op0, op1, min, max;
981 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
982 value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
984 /* Not all binary expressions can be applied to ranges in a
985 meaningful way. Handle only arithmetic operations. */
986 if (code != PLUS_EXPR
987 && code != MINUS_EXPR
989 && code != TRUNC_DIV_EXPR
990 && code != FLOOR_DIV_EXPR
991 && code != CEIL_DIV_EXPR
992 && code != EXACT_DIV_EXPR
993 && code != ROUND_DIV_EXPR
996 && code != TRUTH_ANDIF_EXPR
997 && code != TRUTH_ORIF_EXPR
998 && code != TRUTH_AND_EXPR
999 && code != TRUTH_OR_EXPR
1000 && code != TRUTH_XOR_EXPR)
1002 set_value_range_to_varying (vr);
1006 /* Get value ranges for each operand. For constant operands, create
1007 a new value range with the operand to simplify processing. */
1008 op0 = TREE_OPERAND (expr, 0);
1009 if (TREE_CODE (op0) == SSA_NAME)
1010 vr0 = *(get_value_range (op0));
1011 else if (is_gimple_min_invariant (op0))
1012 set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1014 set_value_range_to_varying (&vr0);
1016 op1 = TREE_OPERAND (expr, 1);
1017 if (TREE_CODE (op1) == SSA_NAME)
1018 vr1 = *(get_value_range (op1));
1019 else if (is_gimple_min_invariant (op1))
1020 set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
1022 set_value_range_to_varying (&vr1);
1024 /* If either range is UNDEFINED, so is the result. */
1025 if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
1027 set_value_range_to_undefined (vr);
1031 /* Refuse to operate on VARYING ranges, ranges of different kinds
1032 and symbolic ranges. TODO, we may be able to derive anti-ranges
1034 if (vr0.type == VR_VARYING
1035 || vr1.type == VR_VARYING
1036 || vr0.type != vr1.type
1037 || symbolic_range_p (&vr0)
1038 || symbolic_range_p (&vr1))
1040 set_value_range_to_varying (vr);
1044 /* Now evaluate the expression to determine the new range. */
1045 if (POINTER_TYPE_P (TREE_TYPE (expr))
1046 || POINTER_TYPE_P (TREE_TYPE (op0))
1047 || POINTER_TYPE_P (TREE_TYPE (op1)))
1049 /* For pointer types, we are really only interested in asserting
1050 whether the expression evaluates to non-NULL. FIXME, we used
1051 to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
1052 ivopts is generating expressions with pointer multiplication
1054 if (code == PLUS_EXPR)
1055 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1058 /* Subtracting from a pointer, may yield 0, so just drop the
1059 resulting range to varying. */
1060 set_value_range_to_varying (vr);
1066 /* For integer ranges, apply the operation to each end of the
1067 range and see what we end up with. */
1068 if (code == TRUTH_ANDIF_EXPR
1069 || code == TRUTH_ORIF_EXPR
1070 || code == TRUTH_AND_EXPR
1071 || code == TRUTH_OR_EXPR
1072 || code == TRUTH_XOR_EXPR)
1074 /* Boolean expressions cannot be folded with int_const_binop. */
1075 min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
1076 max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
1078 else if (code == PLUS_EXPR
1079 || code == MULT_EXPR
1081 || code == MAX_EXPR)
1083 /* For operations that make the resulting range directly
1084 proportional to the original ranges, apply the operation to
1085 the same end of each range. */
1086 min = int_const_binop (code, vr0.min, vr1.min, 0);
1087 max = int_const_binop (code, vr0.max, vr1.max, 0);
1089 else if (code == TRUNC_DIV_EXPR
1090 || code == FLOOR_DIV_EXPR
1091 || code == CEIL_DIV_EXPR
1092 || code == EXACT_DIV_EXPR
1093 || code == ROUND_DIV_EXPR)
1097 /* Divisions are a bit tricky to handle, depending on the mix of
1098 signs we have in the two range, we will need to divide
1099 different values to get the minimum and maximum values for
1100 the new range. If VR1 includes zero, the result is VARYING. */
1101 if (range_includes_zero_p (&vr1))
1103 set_value_range_to_varying (vr);
1107 /* We have three main variations to handle for VR0: all negative
1108 values, all positive values and a mix of negative and
1109 positive. For each of these, we need to consider if VR1 is
1110 all negative or all positive. In total, there are 6
1111 combinations to handle. */
1112 zero = build_int_cst (TREE_TYPE (expr), 0);
1113 if (compare_values (vr0.max, zero) == -1)
1115 /* VR0 is all negative. */
1116 if (compare_values (vr1.min, zero) == 1)
1118 /* If VR1 is all positive, the new range is obtained
1119 with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MAX]. */
1120 min = int_const_binop (code, vr0.min, vr1.min, 0);
1121 max = int_const_binop (code, vr0.max, vr1.max, 0);
1125 /* If VR1 is all negative, the new range is obtained
1126 with [VR0.MAX / VR1.MIN, VR0.MIN / VR1.MAX]. */
1127 gcc_assert (compare_values (vr1.max, zero) == -1);
1128 min = int_const_binop (code, vr0.max, vr1.min, 0);
1129 max = int_const_binop (code, vr0.min, vr1.max, 0);
1132 else if (range_includes_zero_p (&vr0))
1134 /* VR0 is a mix of negative and positive values. */
1135 if (compare_values (vr1.min, zero) == 1)
1137 /* If VR1 is all positive, the new range is obtained
1138 with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MIN]. */
1139 min = int_const_binop (code, vr0.min, vr1.min, 0);
1140 max = int_const_binop (code, vr0.max, vr1.min, 0);
1144 /* If VR1 is all negative, the new range is obtained
1145 with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MAX]. */
1146 gcc_assert (compare_values (vr1.max, zero) == -1);
1147 min = int_const_binop (code, vr0.max, vr1.max, 0);
1148 max = int_const_binop (code, vr0.min, vr1.max, 0);
1153 /* VR0 is all positive. */
1154 gcc_assert (compare_values (vr0.min, zero) == 1);
1155 if (compare_values (vr1.min, zero) == 1)
1157 /* If VR1 is all positive, the new range is obtained
1158 with [VR0.MIN / VR1.MAX, VR0.MAX / VR1.MIN]. */
1159 min = int_const_binop (code, vr0.min, vr1.max, 0);
1160 max = int_const_binop (code, vr0.max, vr1.min, 0);
1164 /* If VR1 is all negative, the new range is obtained
1165 with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MIN]. */
1166 gcc_assert (compare_values (vr1.max, zero) == -1);
1167 min = int_const_binop (code, vr0.max, vr1.max, 0);
1168 max = int_const_binop (code, vr0.min, vr1.min, 0);
1172 else if (code == MINUS_EXPR)
1174 /* For MINUS_EXPR, apply the operation to the opposite ends of
1176 min = int_const_binop (code, vr0.min, vr1.max, 0);
1177 max = int_const_binop (code, vr0.max, vr1.min, 0);
1182 /* If MAX overflowed, then the result depends on whether we are
1183 using wrapping arithmetic or not. */
1184 if (TREE_OVERFLOW (max))
1186 /* If we are using wrapping arithmetic, set the result to
1190 set_value_range_to_varying (vr);
1194 /* Otherwise, set MAX to +INF. */
1195 max = TYPE_MAX_VALUE (TREE_TYPE (expr));
1198 /* If MIN overflowed, then the result depends on whether we are
1199 using wrapping arithmetic or not. */
1200 if (TREE_OVERFLOW (min))
1202 /* If we are using wrapping arithmetic, set the result to
1206 set_value_range_to_varying (vr);
1210 /* Otherwise, set MIN to -INF. */
1211 min = TYPE_MIN_VALUE (TREE_TYPE (expr));
1214 cmp = compare_values (min, max);
1215 if (cmp == -2 || cmp == 1)
1217 /* If the new range has its limits swapped around (MIN > MAX),
1218 then the operation caused one of them to wrap around, mark
1219 the new range VARYING. */
1220 set_value_range_to_varying (vr);
1223 set_value_range (vr, vr0.type, min, max, NULL);
1227 /* Extract range information from a unary expression EXPR based on
1228 the range of its operand and the expression code. */
1231 extract_range_from_unary_expr (value_range_t *vr, tree expr)
1233 enum tree_code code = TREE_CODE (expr);
1236 value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1238 /* Refuse to operate on certain unary expressions for which we
1239 cannot easily determine a resulting range. */
1240 if (code == FIX_TRUNC_EXPR
1241 || code == FIX_CEIL_EXPR
1242 || code == FIX_FLOOR_EXPR
1243 || code == FIX_ROUND_EXPR
1244 || code == FLOAT_EXPR
1245 || code == BIT_NOT_EXPR
1246 || code == NON_LVALUE_EXPR
1247 || code == CONJ_EXPR)
1249 set_value_range_to_varying (vr);
1253 /* Get value ranges for the operand. For constant operands, create
1254 a new value range with the operand to simplify processing. */
1255 op0 = TREE_OPERAND (expr, 0);
1256 if (TREE_CODE (op0) == SSA_NAME)
1257 vr0 = *(get_value_range (op0));
1258 else if (is_gimple_min_invariant (op0))
1259 set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1261 set_value_range_to_varying (&vr0);
1263 /* If VR0 is UNDEFINED, so is the result. */
1264 if (vr0.type == VR_UNDEFINED)
1266 set_value_range_to_undefined (vr);
1270 /* Refuse to operate on varying and symbolic ranges. Also, if the
1271 operand is neither a pointer nor an integral type, set the
1272 resulting range to VARYING. TODO, in some cases we may be able
1273 to derive anti-ranges (like non-zero values). */
1274 if (vr0.type == VR_VARYING
1275 || (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
1276 && !POINTER_TYPE_P (TREE_TYPE (op0)))
1277 || symbolic_range_p (&vr0))
1279 set_value_range_to_varying (vr);
1283 /* If the expression involves pointers, we are only interested in
1284 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
1285 if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
1287 if (range_is_nonnull (&vr0) || expr_computes_nonzero (expr))
1288 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1289 else if (range_is_null (&vr0))
1290 set_value_range_to_null (vr, TREE_TYPE (expr));
1292 set_value_range_to_varying (vr);
1297 /* Handle unary expressions on integer ranges. */
1298 if (code == NOP_EXPR || code == CONVERT_EXPR)
1300 tree inner_type = TREE_TYPE (op0);
1301 tree outer_type = TREE_TYPE (expr);
1303 /* When converting types of different sizes, set the result to
1304 VARYING. Things like sign extensions and precision loss may
1305 change the range. For instance, if x_3 is of type 'long long
1306 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
1307 is impossible to know at compile time whether y_5 will be
1309 if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type)
1310 || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1312 set_value_range_to_varying (vr);
1317 /* Apply the operation to each end of the range and see what we end
1319 if (code == NEGATE_EXPR
1320 && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1322 /* Negating an anti-range doesn't really do anything to it. The
1323 new range will also not take on the same range of values
1324 excluded by the original anti-range. */
1325 if (vr0.type == VR_ANTI_RANGE)
1327 copy_value_range (vr, &vr0);
1331 /* NEGATE_EXPR flips the range around. */
1332 min = (vr0.max == TYPE_MAX_VALUE (TREE_TYPE (expr)))
1333 ? TYPE_MIN_VALUE (TREE_TYPE (expr))
1334 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1336 max = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1337 ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1338 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1340 else if (code == ABS_EXPR
1341 && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1343 /* ABS_EXPR may flip the range around, if the original range
1344 included negative values. */
1345 min = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1346 ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1347 : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1349 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1351 /* If the range was reversed, swap MIN and MAX. */
1352 if (compare_values (min, max) == 1)
1361 /* Otherwise, operate on each end of the range. */
1362 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1363 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1366 cmp = compare_values (min, max);
1367 if (cmp == -2 || cmp == 1)
1369 /* If the new range has its limits swapped around (MIN > MAX),
1370 then the operation caused one of them to wrap around, mark
1371 the new range VARYING. */
1372 set_value_range_to_varying (vr);
1375 set_value_range (vr, vr0.type, min, max, NULL);
1379 /* Extract range information from a comparison expression EXPR based
1380 on the range of its operand and the expression code. */
1383 extract_range_from_comparison (value_range_t *vr, tree expr)
1385 tree val = vrp_evaluate_conditional (expr, false);
1388 /* Since this expression was found on the RHS of an assignment,
1389 its type may be different from _Bool. Convert VAL to EXPR's
1391 val = fold_convert (TREE_TYPE (expr), val);
1392 set_value_range (vr, VR_RANGE, val, val, vr->equiv);
1395 set_value_range_to_varying (vr);
1399 /* Try to compute a useful range out of expression EXPR and store it
1403 extract_range_from_expr (value_range_t *vr, tree expr)
1405 enum tree_code code = TREE_CODE (expr);
1407 if (code == ASSERT_EXPR)
1408 extract_range_from_assert (vr, expr);
1409 else if (code == SSA_NAME)
1410 extract_range_from_ssa_name (vr, expr);
1411 else if (TREE_CODE_CLASS (code) == tcc_binary
1412 || code == TRUTH_ANDIF_EXPR
1413 || code == TRUTH_ORIF_EXPR
1414 || code == TRUTH_AND_EXPR
1415 || code == TRUTH_OR_EXPR
1416 || code == TRUTH_XOR_EXPR)
1417 extract_range_from_binary_expr (vr, expr);
1418 else if (TREE_CODE_CLASS (code) == tcc_unary)
1419 extract_range_from_unary_expr (vr, expr);
1420 else if (TREE_CODE_CLASS (code) == tcc_comparison)
1421 extract_range_from_comparison (vr, expr);
1422 else if (vrp_expr_computes_nonzero (expr))
1423 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1424 else if (is_gimple_min_invariant (expr))
1425 set_value_range (vr, VR_RANGE, expr, expr, NULL);
1427 set_value_range_to_varying (vr);
1430 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1431 would be profitable to adjust VR using scalar evolution information
1432 for VAR. If so, update VR with the new limits. */
1435 adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
1438 tree init, step, chrec;
1441 /* TODO. Don't adjust anti-ranges. An anti-range may provide
1442 better opportunities than a regular range, but I'm not sure. */
1443 if (vr->type == VR_ANTI_RANGE)
1446 chrec = analyze_scalar_evolution (loop, var);
1447 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1450 init = CHREC_LEFT (chrec);
1451 step = CHREC_RIGHT (chrec);
1453 /* If STEP is symbolic, we can't know whether INIT will be the
1454 minimum or maximum value in the range. */
1455 if (!is_gimple_min_invariant (step))
1458 /* Do not adjust ranges when chrec may wrap. */
1459 if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,
1460 cfg_loops->parray[CHREC_VARIABLE (chrec)],
1464 if (!POINTER_TYPE_P (TREE_TYPE (init))
1465 && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
1467 /* For VARYING or UNDEFINED ranges, just about anything we get
1468 from scalar evolutions should be better. */
1470 set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)),
1473 set_value_range (vr, VR_RANGE, init, TYPE_MAX_VALUE (TREE_TYPE (init)),
1476 else if (vr->type == VR_RANGE)
1483 /* INIT is the maximum value. If INIT is lower than VR->MAX
1484 but no smaller than VR->MIN, set VR->MAX to INIT. */
1485 if (compare_values (init, max) == -1)
1489 /* If we just created an invalid range with the minimum
1490 greater than the maximum, take the minimum all the
1492 if (compare_values (min, max) == 1)
1493 min = TYPE_MIN_VALUE (TREE_TYPE (min));
1498 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1499 if (compare_values (init, min) == 1)
1503 /* If we just created an invalid range with the minimum
1504 greater than the maximum, take the maximum all the
1506 if (compare_values (min, max) == 1)
1507 max = TYPE_MAX_VALUE (TREE_TYPE (max));
1511 set_value_range (vr, VR_RANGE, min, max, vr->equiv);
1516 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1518 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
1519 all the values in the ranges.
1521 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1523 - Return NULL_TREE if it is not always possible to determine the
1524 value of the comparison. */
1528 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1)
1530 /* VARYING or UNDEFINED ranges cannot be compared. */
1531 if (vr0->type == VR_VARYING
1532 || vr0->type == VR_UNDEFINED
1533 || vr1->type == VR_VARYING
1534 || vr1->type == VR_UNDEFINED)
1537 /* Anti-ranges need to be handled separately. */
1538 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
1540 /* If both are anti-ranges, then we cannot compute any
1542 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
1545 /* These comparisons are never statically computable. */
1552 /* Equality can be computed only between a range and an
1553 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1554 if (vr0->type == VR_RANGE)
1556 /* To simplify processing, make VR0 the anti-range. */
1557 value_range_t *tmp = vr0;
1562 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
1564 if (compare_values (vr0->min, vr1->min) == 0
1565 && compare_values (vr0->max, vr1->max) == 0)
1566 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1571 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1572 operands around and change the comparison code. */
1573 if (comp == GT_EXPR || comp == GE_EXPR)
1576 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
1582 if (comp == EQ_EXPR)
1584 /* Equality may only be computed if both ranges represent
1585 exactly one value. */
1586 if (compare_values (vr0->min, vr0->max) == 0
1587 && compare_values (vr1->min, vr1->max) == 0)
1589 int cmp_min = compare_values (vr0->min, vr1->min);
1590 int cmp_max = compare_values (vr0->max, vr1->max);
1591 if (cmp_min == 0 && cmp_max == 0)
1592 return boolean_true_node;
1593 else if (cmp_min != -2 && cmp_max != -2)
1594 return boolean_false_node;
1599 else if (comp == NE_EXPR)
1603 /* If VR0 is completely to the left or completely to the right
1604 of VR1, they are always different. Notice that we need to
1605 make sure that both comparisons yield similar results to
1606 avoid comparing values that cannot be compared at
1608 cmp1 = compare_values (vr0->max, vr1->min);
1609 cmp2 = compare_values (vr0->min, vr1->max);
1610 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
1611 return boolean_true_node;
1613 /* If VR0 and VR1 represent a single value and are identical,
1615 else if (compare_values (vr0->min, vr0->max) == 0
1616 && compare_values (vr1->min, vr1->max) == 0
1617 && compare_values (vr0->min, vr1->min) == 0
1618 && compare_values (vr0->max, vr1->max) == 0)
1619 return boolean_false_node;
1621 /* Otherwise, they may or may not be different. */
1625 else if (comp == LT_EXPR || comp == LE_EXPR)
1629 /* If VR0 is to the left of VR1, return true. */
1630 tst = compare_values (vr0->max, vr1->min);
1631 if ((comp == LT_EXPR && tst == -1)
1632 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1633 return boolean_true_node;
1635 /* If VR0 is to the right of VR1, return false. */
1636 tst = compare_values (vr0->min, vr1->max);
1637 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1638 || (comp == LE_EXPR && tst == 1))
1639 return boolean_false_node;
1641 /* Otherwise, we don't know. */
1649 /* Given a value range VR, a value VAL and a comparison code COMP, return
1650 BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
1651 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1652 always returns false. Return NULL_TREE if it is not always
1653 possible to determine the value of the comparison. */
1656 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val)
1658 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1661 /* Anti-ranges need to be handled separately. */
1662 if (vr->type == VR_ANTI_RANGE)
1664 /* For anti-ranges, the only predicates that we can compute at
1665 compile time are equality and inequality. */
1672 /* ~[VAL, VAL] == VAL is always false. */
1673 if (compare_values (vr->min, val) == 0
1674 && compare_values (vr->max, val) == 0)
1675 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1680 if (comp == EQ_EXPR)
1682 /* EQ_EXPR may only be computed if VR represents exactly
1684 if (compare_values (vr->min, vr->max) == 0)
1686 int cmp = compare_values (vr->min, val);
1688 return boolean_true_node;
1689 else if (cmp == -1 || cmp == 1 || cmp == 2)
1690 return boolean_false_node;
1692 else if (compare_values (val, vr->min) == -1
1693 || compare_values (vr->max, val) == -1)
1694 return boolean_false_node;
1698 else if (comp == NE_EXPR)
1700 /* If VAL is not inside VR, then they are always different. */
1701 if (compare_values (vr->max, val) == -1
1702 || compare_values (vr->min, val) == 1)
1703 return boolean_true_node;
1705 /* If VR represents exactly one value equal to VAL, then return
1707 if (compare_values (vr->min, vr->max) == 0
1708 && compare_values (vr->min, val) == 0)
1709 return boolean_false_node;
1711 /* Otherwise, they may or may not be different. */
1714 else if (comp == LT_EXPR || comp == LE_EXPR)
1718 /* If VR is to the left of VAL, return true. */
1719 tst = compare_values (vr->max, val);
1720 if ((comp == LT_EXPR && tst == -1)
1721 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1722 return boolean_true_node;
1724 /* If VR is to the right of VAL, return false. */
1725 tst = compare_values (vr->min, val);
1726 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1727 || (comp == LE_EXPR && tst == 1))
1728 return boolean_false_node;
1730 /* Otherwise, we don't know. */
1733 else if (comp == GT_EXPR || comp == GE_EXPR)
1737 /* If VR is to the right of VAL, return true. */
1738 tst = compare_values (vr->min, val);
1739 if ((comp == GT_EXPR && tst == 1)
1740 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
1741 return boolean_true_node;
1743 /* If VR is to the left of VAL, return false. */
1744 tst = compare_values (vr->max, val);
1745 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
1746 || (comp == GE_EXPR && tst == -1))
1747 return boolean_false_node;
1749 /* Otherwise, we don't know. */
1757 /* Debugging dumps. */
1759 void dump_value_range (FILE *, value_range_t *);
1760 void debug_value_range (value_range_t *);
1761 void dump_all_value_ranges (FILE *);
1762 void debug_all_value_ranges (void);
1763 void dump_vr_equiv (FILE *, bitmap);
1764 void debug_vr_equiv (bitmap);
1767 /* Dump value range VR to FILE. */
1770 dump_value_range (FILE *file, value_range_t *vr)
1773 fprintf (file, "[]");
1774 else if (vr->type == VR_UNDEFINED)
1775 fprintf (file, "UNDEFINED");
1776 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
1778 tree type = TREE_TYPE (vr->min);
1780 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
1782 if (INTEGRAL_TYPE_P (type)
1783 && !TYPE_UNSIGNED (type)
1784 && vr->min == TYPE_MIN_VALUE (type))
1785 fprintf (file, "-INF");
1787 print_generic_expr (file, vr->min, 0);
1789 fprintf (file, ", ");
1791 if (INTEGRAL_TYPE_P (type)
1792 && vr->max == TYPE_MAX_VALUE (type))
1793 fprintf (file, "+INF");
1795 print_generic_expr (file, vr->max, 0);
1797 fprintf (file, "]");
1804 fprintf (file, " EQUIVALENCES: { ");
1806 EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
1808 print_generic_expr (file, ssa_name (i), 0);
1809 fprintf (file, " ");
1813 fprintf (file, "} (%u elements)", c);
1816 else if (vr->type == VR_VARYING)
1817 fprintf (file, "VARYING");
1819 fprintf (file, "INVALID RANGE");
1823 /* Dump value range VR to stderr. */
1826 debug_value_range (value_range_t *vr)
1828 dump_value_range (stderr, vr);
1832 /* Dump value ranges of all SSA_NAMEs to FILE. */
1835 dump_all_value_ranges (FILE *file)
1839 for (i = 0; i < num_ssa_names; i++)
1843 print_generic_expr (file, ssa_name (i), 0);
1844 fprintf (file, ": ");
1845 dump_value_range (file, vr_value[i]);
1846 fprintf (file, "\n");
1850 fprintf (file, "\n");
1854 /* Dump all value ranges to stderr. */
1857 debug_all_value_ranges (void)
1859 dump_all_value_ranges (stderr);
1863 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
1864 create a new SSA name N and return the assertion assignment
1865 'V = ASSERT_EXPR <V, V OP W>'. */
1868 build_assert_expr_for (tree cond, tree v)
1872 gcc_assert (TREE_CODE (v) == SSA_NAME);
1873 n = duplicate_ssa_name (v, NULL_TREE);
1875 if (COMPARISON_CLASS_P (cond))
1877 tree a = build (ASSERT_EXPR, TREE_TYPE (v), v, cond);
1878 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, a);
1880 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1882 /* Given !V, build the assignment N = false. */
1883 tree op0 = TREE_OPERAND (cond, 0);
1884 gcc_assert (op0 == v);
1885 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
1887 else if (TREE_CODE (cond) == SSA_NAME)
1889 /* Given V, build the assignment N = true. */
1890 gcc_assert (v == cond);
1891 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
1896 SSA_NAME_DEF_STMT (n) = assertion;
1898 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
1899 operand of the ASSERT_EXPR. Register the new name and the old one
1900 in the replacement table so that we can fix the SSA web after
1901 adding all the ASSERT_EXPRs. */
1902 register_new_name_mapping (n, v);
1908 /* Return false if EXPR is a predicate expression involving floating
1912 fp_predicate (tree expr)
1914 return (COMPARISON_CLASS_P (expr)
1915 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
1919 /* If the range of values taken by OP can be inferred after STMT executes,
1920 return the comparison code (COMP_CODE_P) and value (VAL_P) that
1921 describes the inferred range. Return true if a range could be
1925 infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
1928 *comp_code_p = ERROR_MARK;
1930 /* Do not attempt to infer anything in names that flow through
1932 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1935 /* Similarly, don't infer anything from statements that may throw
1937 if (tree_could_throw_p (stmt))
1940 if (POINTER_TYPE_P (TREE_TYPE (op)))
1943 unsigned num_uses, num_derefs;
1945 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
1946 if (num_derefs > 0 && flag_delete_null_pointer_checks)
1948 /* We can only assume that a pointer dereference will yield
1949 non-NULL if -fdelete-null-pointer-checks is enabled. */
1950 *val_p = build_int_cst (TREE_TYPE (op), 0);
1951 *comp_code_p = NE_EXPR;
1960 void dump_asserts_for (FILE *, tree);
1961 void debug_asserts_for (tree);
1962 void dump_all_asserts (FILE *);
1963 void debug_all_asserts (void);
1965 /* Dump all the registered assertions for NAME to FILE. */
1968 dump_asserts_for (FILE *file, tree name)
1972 fprintf (file, "Assertions to be inserted for ");
1973 print_generic_expr (file, name, 0);
1974 fprintf (file, "\n");
1976 loc = asserts_for[SSA_NAME_VERSION (name)];
1979 fprintf (file, "\t");
1980 print_generic_expr (file, bsi_stmt (loc->si), 0);
1981 fprintf (file, "\n\tBB #%d", loc->bb->index);
1984 fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
1985 loc->e->dest->index);
1986 dump_edge_info (file, loc->e, 0);
1988 fprintf (file, "\n\tPREDICATE: ");
1989 print_generic_expr (file, name, 0);
1990 fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
1991 print_generic_expr (file, loc->val, 0);
1992 fprintf (file, "\n\n");
1996 fprintf (file, "\n");
2000 /* Dump all the registered assertions for NAME to stderr. */
2003 debug_asserts_for (tree name)
2005 dump_asserts_for (stderr, name);
2009 /* Dump all the registered assertions for all the names to FILE. */
2012 dump_all_asserts (FILE *file)
2017 fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
2018 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2019 dump_asserts_for (file, ssa_name (i));
2020 fprintf (file, "\n");
2024 /* Dump all the registered assertions for all the names to stderr. */
2027 debug_all_asserts (void)
2029 dump_all_asserts (stderr);
2033 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
2034 'NAME COMP_CODE VAL' at a location that dominates block BB or
2035 E->DEST, then register this location as a possible insertion point
2036 for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
2038 BB, E and SI provide the exact insertion point for the new
2039 ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
2040 on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
2041 BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
2042 must not be NULL. */
2045 register_new_assert_for (tree name,
2046 enum tree_code comp_code,
2050 block_stmt_iterator si)
2052 assert_locus_t n, loc, last_loc;
2054 basic_block dest_bb;
2056 #if defined ENABLE_CHECKING
2057 gcc_assert (bb == NULL || e == NULL);
2060 gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
2061 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
2064 /* The new assertion A will be inserted at BB or E. We need to
2065 determine if the new location is dominated by a previously
2066 registered location for A. If we are doing an edge insertion,
2067 assume that A will be inserted at E->DEST. Note that this is not
2070 If E is a critical edge, it will be split. But even if E is
2071 split, the new block will dominate the same set of blocks that
2074 The reverse, however, is not true, blocks dominated by E->DEST
2075 will not be dominated by the new block created to split E. So,
2076 if the insertion location is on a critical edge, we will not use
2077 the new location to move another assertion previously registered
2078 at a block dominated by E->DEST. */
2079 dest_bb = (bb) ? bb : e->dest;
2081 /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
2082 VAL at a block dominating DEST_BB, then we don't need to insert a new
2083 one. Similarly, if the same assertion already exists at a block
2084 dominated by DEST_BB and the new location is not on a critical
2085 edge, then update the existing location for the assertion (i.e.,
2086 move the assertion up in the dominance tree).
2088 Note, this is implemented as a simple linked list because there
2089 should not be more than a handful of assertions registered per
2090 name. If this becomes a performance problem, a table hashed by
2091 COMP_CODE and VAL could be implemented. */
2092 loc = asserts_for[SSA_NAME_VERSION (name)];
2097 if (loc->comp_code == comp_code
2099 || operand_equal_p (loc->val, val, 0)))
2101 /* If the assertion NAME COMP_CODE VAL has already been
2102 registered at a basic block that dominates DEST_BB, then
2103 we don't need to insert the same assertion again. Note
2104 that we don't check strict dominance here to avoid
2105 replicating the same assertion inside the same basic
2106 block more than once (e.g., when a pointer is
2107 dereferenced several times inside a block).
2109 An exception to this rule are edge insertions. If the
2110 new assertion is to be inserted on edge E, then it will
2111 dominate all the other insertions that we may want to
2112 insert in DEST_BB. So, if we are doing an edge
2113 insertion, don't do this dominance check. */
2115 && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
2118 /* Otherwise, if E is not a critical edge and DEST_BB
2119 dominates the existing location for the assertion, move
2120 the assertion up in the dominance tree by updating its
2121 location information. */
2122 if ((e == NULL || !EDGE_CRITICAL_P (e))
2123 && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
2132 /* Update the last node of the list and move to the next one. */
2137 /* If we didn't find an assertion already registered for
2138 NAME COMP_CODE VAL, add a new one at the end of the list of
2139 assertions associated with NAME. */
2140 n = xmalloc (sizeof (*n));
2144 n->comp_code = comp_code;
2151 asserts_for[SSA_NAME_VERSION (name)] = n;
2153 bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
2157 /* Try to register an edge assertion for SSA name NAME on edge E for
2158 the conditional jump pointed by SI. Return true if an assertion
2159 for NAME could be registered. */
2162 register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
2165 enum tree_code comp_code;
2167 stmt = bsi_stmt (si);
2169 /* Do not attempt to infer anything in names that flow through
2171 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
2174 /* If NAME was not found in the sub-graph reachable from E, then
2175 there's nothing to do. */
2176 if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
2179 /* We found a use of NAME in the sub-graph rooted at E->DEST.
2180 Register an assertion for NAME according to the value that NAME
2182 if (TREE_CODE (stmt) == COND_EXPR)
2184 /* If BB ends in a COND_EXPR then NAME then we should insert
2185 the original predicate on EDGE_TRUE_VALUE and the
2186 opposite predicate on EDGE_FALSE_VALUE. */
2187 tree cond = COND_EXPR_COND (stmt);
2188 bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
2190 /* Predicates may be a single SSA name or NAME OP VAL. */
2193 /* If the predicate is a name, it must be NAME, in which
2194 case we create the predicate NAME == true or
2195 NAME == false accordingly. */
2196 comp_code = EQ_EXPR;
2197 val = (is_else_edge) ? boolean_false_node : boolean_true_node;
2201 /* Otherwise, we have a comparison of the form NAME COMP VAL
2202 or VAL COMP NAME. */
2203 if (name == TREE_OPERAND (cond, 1))
2205 /* If the predicate is of the form VAL COMP NAME, flip
2206 COMP around because we need to register NAME as the
2207 first operand in the predicate. */
2208 comp_code = opposite_comparison (TREE_CODE (cond));
2209 val = TREE_OPERAND (cond, 0);
2213 /* The comparison is of the form NAME COMP VAL, so the
2214 comparison code remains unchanged. */
2215 comp_code = TREE_CODE (cond);
2216 val = TREE_OPERAND (cond, 1);
2219 /* If we are inserting the assertion on the ELSE edge, we
2220 need to invert the sign comparison. */
2222 comp_code = invert_tree_comparison (comp_code, 0);
2227 /* FIXME. Handle SWITCH_EXPR. */
2231 register_new_assert_for (name, comp_code, val, NULL, e, si);
2236 static bool find_assert_locations (basic_block bb);
2238 /* Determine whether the outgoing edges of BB should receive an
2239 ASSERT_EXPR for each of the operands of BB's last statement. The
2240 last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
2242 If any of the sub-graphs rooted at BB have an interesting use of
2243 the predicate operands, an assert location node is added to the
2244 list of assertions for the corresponding operands. */
2247 find_conditional_asserts (basic_block bb)
2250 block_stmt_iterator last_si;
2256 need_assert = false;
2257 last_si = bsi_last (bb);
2258 last = bsi_stmt (last_si);
2260 /* Look for uses of the operands in each of the sub-graphs
2261 rooted at BB. We need to check each of the outgoing edges
2262 separately, so that we know what kind of ASSERT_EXPR to
2264 FOR_EACH_EDGE (e, ei, bb->succs)
2269 /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
2270 Otherwise, when we finish traversing each of the sub-graphs, we
2271 won't know whether the variables were found in the sub-graphs or
2272 if they had been found in a block upstream from BB. */
2273 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2274 RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2276 /* Traverse the strictly dominated sub-graph rooted at E->DEST
2277 to determine if any of the operands in the conditional
2278 predicate are used. */
2280 need_assert |= find_assert_locations (e->dest);
2282 /* Register the necessary assertions for each operand in the
2283 conditional predicate. */
2284 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2285 need_assert |= register_edge_assert_for (op, e, last_si);
2288 /* Finally, indicate that we have found the operands in the
2290 FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2291 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2297 /* Traverse all the statements in block BB looking for statements that
2298 may generate useful assertions for the SSA names in their operand.
2299 If a statement produces a useful assertion A for name N_i, then the
2300 list of assertions already generated for N_i is scanned to
2301 determine if A is actually needed.
2303 If N_i already had the assertion A at a location dominating the
2304 current location, then nothing needs to be done. Otherwise, the
2305 new location for A is recorded instead.
2307 1- For every statement S in BB, all the variables used by S are
2308 added to bitmap FOUND_IN_SUBGRAPH.
2310 2- If statement S uses an operand N in a way that exposes a known
2311 value range for N, then if N was not already generated by an
2312 ASSERT_EXPR, create a new assert location for N. For instance,
2313 if N is a pointer and the statement dereferences it, we can
2314 assume that N is not NULL.
2316 3- COND_EXPRs are a special case of #2. We can derive range
2317 information from the predicate but need to insert different
2318 ASSERT_EXPRs for each of the sub-graphs rooted at the
2319 conditional block. If the last statement of BB is a conditional
2320 expression of the form 'X op Y', then
2322 a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
2324 b) If the conditional is the only entry point to the sub-graph
2325 corresponding to the THEN_CLAUSE, recurse into it. On
2326 return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
2327 an ASSERT_EXPR is added for the corresponding variable.
2329 c) Repeat step (b) on the ELSE_CLAUSE.
2331 d) Mark X and Y in FOUND_IN_SUBGRAPH.
2340 In this case, an assertion on the THEN clause is useful to
2341 determine that 'a' is always 9 on that edge. However, an assertion
2342 on the ELSE clause would be unnecessary.
2344 4- If BB does not end in a conditional expression, then we recurse
2345 into BB's dominator children.
2347 At the end of the recursive traversal, every SSA name will have a
2348 list of locations where ASSERT_EXPRs should be added. When a new
2349 location for name N is found, it is registered by calling
2350 register_new_assert_for. That function keeps track of all the
2351 registered assertions to prevent adding unnecessary assertions.
2352 For instance, if a pointer P_4 is dereferenced more than once in a
2353 dominator tree, only the location dominating all the dereference of
2354 P_4 will receive an ASSERT_EXPR.
2356 If this function returns true, then it means that there are names
2357 for which we need to generate ASSERT_EXPRs. Those assertions are
2358 inserted by process_assert_insertions.
2360 TODO. Handle SWITCH_EXPR. */
2363 find_assert_locations (basic_block bb)
2365 block_stmt_iterator si;
2370 if (TEST_BIT (blocks_visited, bb->index))
2373 SET_BIT (blocks_visited, bb->index);
2375 need_assert = false;
2377 /* Traverse all PHI nodes in BB marking used operands. */
2378 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2380 use_operand_p arg_p;
2383 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
2385 tree arg = USE_FROM_PTR (arg_p);
2386 if (TREE_CODE (arg) == SSA_NAME)
2388 gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
2389 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
2394 /* Traverse all the statements in BB marking used names and looking
2395 for statements that may infer assertions for their used operands. */
2397 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2402 stmt = bsi_stmt (si);
2404 /* See if we can derive an assertion for any of STMT's operands. */
2405 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
2408 enum tree_code comp_code;
2410 /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside
2411 the sub-graph of a conditional block, when we return from
2412 this recursive walk, our parent will use the
2413 FOUND_IN_SUBGRAPH bitset to determine if one of the
2414 operands it was looking for was present in the sub-graph. */
2415 SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2417 /* If OP is used only once, namely in this STMT, don't
2418 bother creating an ASSERT_EXPR for it. Such an
2419 ASSERT_EXPR would do nothing but increase compile time.
2420 Experiments show that with this simple check, we can save
2421 more than 20% of ASSERT_EXPRs. */
2422 if (has_single_use (op))
2425 /* If OP is used in such a way that we can infer a value
2426 range for it, and we don't find a previous assertion for
2427 it, create a new assertion location node for OP. */
2428 if (infer_value_range (stmt, op, &comp_code, &value))
2430 register_new_assert_for (op, comp_code, value, bb, NULL, si);
2435 /* Remember the last statement of the block. */
2439 /* If BB's last statement is a conditional expression
2440 involving integer operands, recurse into each of the sub-graphs
2441 rooted at BB to determine if we need to add ASSERT_EXPRs. */
2443 && TREE_CODE (last) == COND_EXPR
2444 && !fp_predicate (COND_EXPR_COND (last))
2445 && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
2446 need_assert |= find_conditional_asserts (bb);
2448 /* Recurse into the dominator children of BB. */
2449 for (son = first_dom_son (CDI_DOMINATORS, bb);
2451 son = next_dom_son (CDI_DOMINATORS, son))
2452 need_assert |= find_assert_locations (son);
2458 /* Create an ASSERT_EXPR for NAME and insert it in the location
2459 indicated by LOC. Return true if we made any edge insertions. */
2462 process_assert_insertions_for (tree name, assert_locus_t loc)
2464 /* Build the comparison expression NAME_i COMP_CODE VAL. */
2465 tree stmt, cond, assert_expr;
2469 cond = build (loc->comp_code, boolean_type_node, name, loc->val);
2470 assert_expr = build_assert_expr_for (cond, name);
2474 /* We have been asked to insert the assertion on an edge. This
2475 is used only by COND_EXPR and SWITCH_EXPR assertions. */
2476 #if defined ENABLE_CHECKING
2477 gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
2478 || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
2481 bsi_insert_on_edge (loc->e, assert_expr);
2485 /* Otherwise, we can insert right after LOC->SI iff the
2486 statement must not be the last statement in the block. */
2487 stmt = bsi_stmt (loc->si);
2488 if (!stmt_ends_bb_p (stmt))
2490 bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
2494 /* If STMT must be the last statement in BB, we can only insert new
2495 assertions on the non-abnormal edge out of BB. Note that since
2496 STMT is not control flow, there may only be one non-abnormal edge
2498 FOR_EACH_EDGE (e, ei, loc->bb->succs)
2499 if (!(e->flags & EDGE_ABNORMAL))
2501 bsi_insert_on_edge (e, assert_expr);
2509 /* Process all the insertions registered for every name N_i registered
2510 in NEED_ASSERT_FOR. The list of assertions to be inserted are
2511 found in ASSERTS_FOR[i]. */
2514 process_assert_insertions (void)
2518 bool update_edges_p = false;
2519 int num_asserts = 0;
2521 if (dump_file && (dump_flags & TDF_DETAILS))
2522 dump_all_asserts (dump_file);
2524 EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2526 assert_locus_t loc = asserts_for[i];
2531 assert_locus_t next = loc->next;
2532 update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
2540 bsi_commit_edge_inserts ();
2542 if (dump_file && (dump_flags & TDF_STATS))
2543 fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
2548 /* Traverse the flowgraph looking for conditional jumps to insert range
2549 expressions. These range expressions are meant to provide information
2550 to optimizations that need to reason in terms of value ranges. They
2551 will not be expanded into RTL. For instance, given:
2560 this pass will transform the code into:
2566 x = ASSERT_EXPR <x, x < y>
2571 y = ASSERT_EXPR <y, x <= y>
2575 The idea is that once copy and constant propagation have run, other
2576 optimizations will be able to determine what ranges of values can 'x'
2577 take in different paths of the code, simply by checking the reaching
2578 definition of 'x'. */
2581 insert_range_assertions (void)
2587 found_in_subgraph = sbitmap_alloc (num_ssa_names);
2588 sbitmap_zero (found_in_subgraph);
2590 blocks_visited = sbitmap_alloc (last_basic_block);
2591 sbitmap_zero (blocks_visited);
2593 need_assert_for = BITMAP_ALLOC (NULL);
2594 asserts_for = xmalloc (num_ssa_names * sizeof (assert_locus_t));
2595 memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t));
2597 calculate_dominance_info (CDI_DOMINATORS);
2599 update_ssa_p = false;
2600 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2601 if (find_assert_locations (e->dest))
2602 update_ssa_p = true;
2606 process_assert_insertions ();
2607 update_ssa (TODO_update_ssa_no_phi);
2610 if (dump_file && (dump_flags & TDF_DETAILS))
2612 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
2613 dump_function_to_file (current_function_decl, dump_file, dump_flags);
2616 sbitmap_free (found_in_subgraph);
2618 BITMAP_FREE (need_assert_for);
2622 /* Convert range assertion expressions into the implied copies.
2624 FIXME, this will eventually lead to copy propagation removing the
2625 names that had useful range information attached to them. For
2626 instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
2627 then N_i will have the range [3, +INF].
2629 However, by converting the assertion into the implied copy
2630 operation N_i = N_j, we will then copy-propagate N_j into the uses
2631 of N_i and lose the range information. We may want to hold on to
2632 ASSERT_EXPRs a little while longer as the ranges could be used in
2633 things like jump threading.
2635 The problem with keeping ASSERT_EXPRs around is that passes after
2636 VRP need to handle them appropriately. */
2639 remove_range_assertions (void)
2642 block_stmt_iterator si;
2645 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2647 tree stmt = bsi_stmt (si);
2649 if (TREE_CODE (stmt) == MODIFY_EXPR
2650 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
2652 tree rhs = TREE_OPERAND (stmt, 1);
2653 tree cond = fold (ASSERT_EXPR_COND (rhs));
2654 gcc_assert (cond != boolean_false_node);
2655 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
2662 /* Return true if STMT is interesting for VRP. */
2665 stmt_interesting_for_vrp (tree stmt)
2667 if (TREE_CODE (stmt) == PHI_NODE
2668 && is_gimple_reg (PHI_RESULT (stmt))
2669 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
2670 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
2672 else if (TREE_CODE (stmt) == MODIFY_EXPR)
2674 tree lhs = TREE_OPERAND (stmt, 0);
2676 if (TREE_CODE (lhs) == SSA_NAME
2677 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2678 || POINTER_TYPE_P (TREE_TYPE (lhs)))
2679 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
2682 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
2689 /* Initialize local data structures for VRP. Return true if VRP
2690 is worth running (i.e. if we found any statements that could
2691 benefit from range information). */
2694 vrp_initialize (void)
2698 vr_value = xmalloc (num_ssa_names * sizeof (value_range_t *));
2699 memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *));
2703 block_stmt_iterator si;
2706 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2708 if (!stmt_interesting_for_vrp (phi))
2710 tree lhs = PHI_RESULT (phi);
2711 set_value_range_to_varying (get_value_range (lhs));
2712 DONT_SIMULATE_AGAIN (phi) = true;
2715 DONT_SIMULATE_AGAIN (phi) = false;
2718 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2720 tree stmt = bsi_stmt (si);
2722 if (!stmt_interesting_for_vrp (stmt))
2726 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
2727 set_value_range_to_varying (get_value_range (def));
2728 DONT_SIMULATE_AGAIN (stmt) = true;
2732 DONT_SIMULATE_AGAIN (stmt) = false;
2739 /* Visit assignment STMT. If it produces an interesting range, record
2740 the SSA name in *OUTPUT_P. */
2742 static enum ssa_prop_result
2743 vrp_visit_assignment (tree stmt, tree *output_p)
2748 lhs = TREE_OPERAND (stmt, 0);
2749 rhs = TREE_OPERAND (stmt, 1);
2751 /* We only keep track of ranges in integral and pointer types. */
2752 if (TREE_CODE (lhs) == SSA_NAME
2753 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2754 || POINTER_TYPE_P (TREE_TYPE (lhs))))
2757 value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2759 extract_range_from_expr (&new_vr, rhs);
2761 /* If STMT is inside a loop, we may be able to know something
2762 else about the range of LHS by examining scalar evolution
2764 if (cfg_loops && (l = loop_containing_stmt (stmt)))
2765 adjust_range_with_scev (&new_vr, l, stmt, lhs);
2767 if (update_value_range (lhs, &new_vr))
2771 if (dump_file && (dump_flags & TDF_DETAILS))
2773 fprintf (dump_file, "Found new range for ");
2774 print_generic_expr (dump_file, lhs, 0);
2775 fprintf (dump_file, ": ");
2776 dump_value_range (dump_file, &new_vr);
2777 fprintf (dump_file, "\n\n");
2780 if (new_vr.type == VR_VARYING)
2781 return SSA_PROP_VARYING;
2783 return SSA_PROP_INTERESTING;
2786 return SSA_PROP_NOT_INTERESTING;
2789 /* Every other statement produces no useful ranges. */
2790 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
2791 set_value_range_to_varying (get_value_range (def));
2793 return SSA_PROP_VARYING;
2797 /* Compare all the value ranges for names equivalent to VAR with VAL
2798 using comparison code COMP. Return the same value returned by
2799 compare_range_with_value. */
2802 compare_name_with_value (enum tree_code comp, tree var, tree val)
2809 t = retval = NULL_TREE;
2811 /* Get the set of equivalences for VAR. */
2812 e = get_value_range (var)->equiv;
2814 /* Add VAR to its own set of equivalences so that VAR's value range
2815 is processed by this loop (otherwise, we would have to replicate
2816 the body of the loop just to check VAR's value range). */
2817 bitmap_set_bit (e, SSA_NAME_VERSION (var));
2819 EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
2821 value_range_t equiv_vr = *(vr_value[i]);
2823 /* If name N_i does not have a valid range, use N_i as its own
2824 range. This allows us to compare against names that may
2825 have N_i in their ranges. */
2826 if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
2828 equiv_vr.type = VR_RANGE;
2829 equiv_vr.min = ssa_name (i);
2830 equiv_vr.max = ssa_name (i);
2833 t = compare_range_with_value (comp, &equiv_vr, val);
2836 /* All the ranges should compare the same against VAL. */
2837 gcc_assert (retval == NULL || t == retval);
2842 /* Remove VAR from its own equivalence set. */
2843 bitmap_clear_bit (e, SSA_NAME_VERSION (var));
2848 /* We couldn't find a non-NULL value for the predicate. */
2853 /* Given a comparison code COMP and names N1 and N2, compare all the
2854 ranges equivalent to N1 against all the ranges equivalent to N2
2855 to determine the value of N1 COMP N2. Return the same value
2856 returned by compare_ranges. */
2859 compare_names (enum tree_code comp, tree n1, tree n2)
2863 bitmap_iterator bi1, bi2;
2866 /* Compare the ranges of every name equivalent to N1 against the
2867 ranges of every name equivalent to N2. */
2868 e1 = get_value_range (n1)->equiv;
2869 e2 = get_value_range (n2)->equiv;
2871 /* Add N1 and N2 to their own set of equivalences to avoid
2872 duplicating the body of the loop just to check N1 and N2
2874 bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
2875 bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
2877 /* If the equivalence sets have a common intersection, then the two
2878 names can be compared without checking their ranges. */
2879 if (bitmap_intersect_p (e1, e2))
2881 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2882 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2884 return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
2886 : boolean_false_node;
2889 /* Otherwise, compare all the equivalent ranges. First, add N1 and
2890 N2 to their own set of equivalences to avoid duplicating the body
2891 of the loop just to check N1 and N2 ranges. */
2892 EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
2894 value_range_t vr1 = *(vr_value[i1]);
2896 /* If the range is VARYING or UNDEFINED, use the name itself. */
2897 if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
2899 vr1.type = VR_RANGE;
2900 vr1.min = ssa_name (i1);
2901 vr1.max = ssa_name (i1);
2904 t = retval = NULL_TREE;
2905 EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
2907 value_range_t vr2 = *(vr_value[i2]);
2909 if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
2911 vr2.type = VR_RANGE;
2912 vr2.min = ssa_name (i2);
2913 vr2.max = ssa_name (i2);
2916 t = compare_ranges (comp, &vr1, &vr2);
2919 /* All the ranges in the equivalent sets should compare
2921 gcc_assert (retval == NULL || t == retval);
2928 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2929 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2934 /* None of the equivalent ranges are useful in computing this
2936 bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
2937 bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
2942 /* Given a conditional predicate COND, try to determine if COND yields
2943 true or false based on the value ranges of its operands. Return
2944 BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
2945 BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
2946 NULL if the conditional cannot be evaluated at compile time.
2948 If USE_EQUIV_P is true, the ranges of all the names equivalent with
2949 the operands in COND are used when trying to compute its value.
2950 This is only used during final substitution. During propagation,
2951 we only check the range of each variable and not its equivalents. */
2954 vrp_evaluate_conditional (tree cond, bool use_equiv_p)
2956 gcc_assert (TREE_CODE (cond) == SSA_NAME
2957 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
2959 if (TREE_CODE (cond) == SSA_NAME)
2965 retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node);
2968 value_range_t *vr = get_value_range (cond);
2969 retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node);
2972 /* If COND has a known boolean range, return it. */
2976 /* Otherwise, if COND has a symbolic range of exactly one value,
2978 vr = get_value_range (cond);
2979 if (vr->type == VR_RANGE && vr->min == vr->max)
2984 tree op0 = TREE_OPERAND (cond, 0);
2985 tree op1 = TREE_OPERAND (cond, 1);
2987 /* We only deal with integral and pointer types. */
2988 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
2989 && !POINTER_TYPE_P (TREE_TYPE (op0)))
2994 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
2995 return compare_names (TREE_CODE (cond), op0, op1);
2996 else if (TREE_CODE (op0) == SSA_NAME)
2997 return compare_name_with_value (TREE_CODE (cond), op0, op1);
2998 else if (TREE_CODE (op1) == SSA_NAME)
2999 return compare_name_with_value (
3000 opposite_comparison (TREE_CODE (cond)), op1, op0);
3004 value_range_t *vr0, *vr1;
3006 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
3007 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
3010 return compare_ranges (TREE_CODE (cond), vr0, vr1);
3011 else if (vr0 && vr1 == NULL)
3012 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
3013 else if (vr0 == NULL && vr1)
3014 return compare_range_with_value (
3015 opposite_comparison (TREE_CODE (cond)), vr1, op0);
3019 /* Anything else cannot be computed statically. */
3024 /* Visit conditional statement STMT. If we can determine which edge
3025 will be taken out of STMT's basic block, record it in
3026 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
3027 SSA_PROP_VARYING. */
3029 static enum ssa_prop_result
3030 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
3034 *taken_edge_p = NULL;
3036 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
3037 add ASSERT_EXPRs for them. */
3038 if (TREE_CODE (stmt) == SWITCH_EXPR)
3039 return SSA_PROP_VARYING;
3041 cond = COND_EXPR_COND (stmt);
3043 if (dump_file && (dump_flags & TDF_DETAILS))
3048 fprintf (dump_file, "\nVisiting conditional with predicate: ");
3049 print_generic_expr (dump_file, cond, 0);
3050 fprintf (dump_file, "\nWith known ranges\n");
3052 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
3054 fprintf (dump_file, "\t");
3055 print_generic_expr (dump_file, use, 0);
3056 fprintf (dump_file, ": ");
3057 dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
3060 fprintf (dump_file, "\n");
3063 /* Compute the value of the predicate COND by checking the known
3064 ranges of each of its operands.
3066 Note that we cannot evaluate all the equivalent ranges here
3067 because those ranges may not yet be final and with the current
3068 propagation strategy, we cannot determine when the value ranges
3069 of the names in the equivalence set have changed.
3071 For instance, given the following code fragment
3075 i_14 = ASSERT_EXPR <i_5, i_5 != 0>
3079 Assume that on the first visit to i_14, i_5 has the temporary
3080 range [8, 8] because the second argument to the PHI function is
3081 not yet executable. We derive the range ~[0, 0] for i_14 and the
3082 equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for
3083 the first time, since i_14 is equivalent to the range [8, 8], we
3084 determine that the predicate is always false.
3086 On the next round of propagation, i_13 is determined to be
3087 VARYING, which causes i_5 to drop down to VARYING. So, another
3088 visit to i_14 is scheduled. In this second visit, we compute the
3089 exact same range and equivalence set for i_14, namely ~[0, 0] and
3090 { i_5 }. But we did not have the previous range for i_5
3091 registered, so vrp_visit_assignment thinks that the range for
3092 i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)'
3093 is not visited again, which stops propagation from visiting
3094 statements in the THEN clause of that if().
3096 To properly fix this we would need to keep the previous range
3097 value for the names in the equivalence set. This way we would've
3098 discovered that from one visit to the other i_5 changed from
3099 range [8, 8] to VR_VARYING.
3101 However, fixing this apparent limitation may not be worth the
3102 additional checking. Testing on several code bases (GCC, DLV,
3103 MICO, TRAMP3D and SPEC2000) showed that doing this results in
3104 4 more predicates folded in SPEC. */
3105 val = vrp_evaluate_conditional (cond, false);
3107 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
3109 if (dump_file && (dump_flags & TDF_DETAILS))
3111 fprintf (dump_file, "\nPredicate evaluates to: ");
3112 if (val == NULL_TREE)
3113 fprintf (dump_file, "DON'T KNOW\n");
3115 print_generic_stmt (dump_file, val, 0);
3118 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
3122 /* Evaluate statement STMT. If the statement produces a useful range,
3123 return SSA_PROP_INTERESTING and record the SSA name with the
3124 interesting range into *OUTPUT_P.
3126 If STMT is a conditional branch and we can determine its truth
3127 value, the taken edge is recorded in *TAKEN_EDGE_P.
3129 If STMT produces a varying value, return SSA_PROP_VARYING. */
3131 static enum ssa_prop_result
3132 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
3138 if (dump_file && (dump_flags & TDF_DETAILS))
3140 fprintf (dump_file, "\nVisiting statement:\n");
3141 print_generic_stmt (dump_file, stmt, dump_flags);
3142 fprintf (dump_file, "\n");
3145 ann = stmt_ann (stmt);
3146 if (TREE_CODE (stmt) == MODIFY_EXPR
3147 && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3148 return vrp_visit_assignment (stmt, output_p);
3149 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3150 return vrp_visit_cond_stmt (stmt, taken_edge_p);
3152 /* All other statements produce nothing of interest for VRP, so mark
3153 their outputs varying and prevent further simulation. */
3154 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3155 set_value_range_to_varying (get_value_range (def));
3157 return SSA_PROP_VARYING;
3161 /* Meet operation for value ranges. Given two value ranges VR0 and
3162 VR1, store in VR0 the result of meeting VR0 and VR1.
3164 The meeting rules are as follows:
3166 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
3168 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
3169 union of VR0 and VR1. */
3172 vrp_meet (value_range_t *vr0, value_range_t *vr1)
3174 if (vr0->type == VR_UNDEFINED)
3176 copy_value_range (vr0, vr1);
3180 if (vr1->type == VR_UNDEFINED)
3182 /* Nothing to do. VR0 already has the resulting range. */
3186 if (vr0->type == VR_VARYING)
3188 /* Nothing to do. VR0 already has the resulting range. */
3192 if (vr1->type == VR_VARYING)
3194 set_value_range_to_varying (vr0);
3198 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
3200 /* If VR0 and VR1 have a non-empty intersection, compute the
3201 union of both ranges. */
3202 if (value_ranges_intersect_p (vr0, vr1))
3207 /* The lower limit of the new range is the minimum of the
3208 two ranges. If they cannot be compared, the result is
3210 cmp = compare_values (vr0->min, vr1->min);
3211 if (cmp == 0 || cmp == 1)
3217 set_value_range_to_varying (vr0);
3221 /* Similarly, the upper limit of the new range is the
3222 maximum of the two ranges. If they cannot be compared,
3223 the result is VARYING. */
3224 cmp = compare_values (vr0->max, vr1->max);
3225 if (cmp == 0 || cmp == -1)
3231 set_value_range_to_varying (vr0);
3235 /* The resulting set of equivalences is the intersection of
3237 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3238 bitmap_and_into (vr0->equiv, vr1->equiv);
3240 set_value_range (vr0, vr0->type, min, max, vr0->equiv);
3245 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3247 /* Two anti-ranges meet only if they are both identical. */
3248 if (compare_values (vr0->min, vr1->min) == 0
3249 && compare_values (vr0->max, vr1->max) == 0
3250 && compare_values (vr0->min, vr0->max) == 0)
3252 /* The resulting set of equivalences is the intersection of
3254 if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3255 bitmap_and_into (vr0->equiv, vr1->equiv);
3260 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
3262 /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4]
3263 meet only if the ranges have an empty intersection. The
3264 result of the meet operation is the anti-range. */
3265 if (!symbolic_range_p (vr0)
3266 && !symbolic_range_p (vr1)
3267 && !value_ranges_intersect_p (vr0, vr1))
3269 if (vr1->type == VR_ANTI_RANGE)
3270 copy_value_range (vr0, vr1);
3281 /* The two range VR0 and VR1 do not meet. Before giving up and
3282 setting the result to VARYING, see if we can at least derive a
3283 useful anti-range. */
3284 if (!symbolic_range_p (vr0)
3285 && !range_includes_zero_p (vr0)
3286 && !symbolic_range_p (vr1)
3287 && !range_includes_zero_p (vr1))
3288 set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
3290 set_value_range_to_varying (vr0);
3294 /* Visit all arguments for PHI node PHI that flow through executable
3295 edges. If a valid value range can be derived from all the incoming
3296 value ranges, set a new range for the LHS of PHI. */
3298 static enum ssa_prop_result
3299 vrp_visit_phi_node (tree phi)
3302 tree lhs = PHI_RESULT (phi);
3303 value_range_t *lhs_vr = get_value_range (lhs);
3304 value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3306 copy_value_range (&vr_result, lhs_vr);
3308 if (dump_file && (dump_flags & TDF_DETAILS))
3310 fprintf (dump_file, "\nVisiting PHI node: ");
3311 print_generic_expr (dump_file, phi, dump_flags);
3314 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
3316 edge e = PHI_ARG_EDGE (phi, i);
3318 if (dump_file && (dump_flags & TDF_DETAILS))
3321 "\n Argument #%d (%d -> %d %sexecutable)\n",
3322 i, e->src->index, e->dest->index,
3323 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
3326 if (e->flags & EDGE_EXECUTABLE)
3328 tree arg = PHI_ARG_DEF (phi, i);
3329 value_range_t vr_arg;
3331 if (TREE_CODE (arg) == SSA_NAME)
3332 vr_arg = *(get_value_range (arg));
3335 vr_arg.type = VR_RANGE;
3338 vr_arg.equiv = NULL;
3341 if (dump_file && (dump_flags & TDF_DETAILS))
3343 fprintf (dump_file, "\t");
3344 print_generic_expr (dump_file, arg, dump_flags);
3345 fprintf (dump_file, "\n\tValue: ");
3346 dump_value_range (dump_file, &vr_arg);
3347 fprintf (dump_file, "\n");
3350 vrp_meet (&vr_result, &vr_arg);
3352 if (vr_result.type == VR_VARYING)
3357 if (vr_result.type == VR_VARYING)
3360 /* To prevent infinite iterations in the algorithm, derive ranges
3361 when the new value is slightly bigger or smaller than the
3363 if (lhs_vr->type == VR_RANGE)
3365 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
3367 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
3368 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
3370 /* If the new minimum is smaller or larger than the previous
3371 one, go all the way to -INF. In the first case, to avoid
3372 iterating millions of times to reach -INF, and in the
3373 other case to avoid infinite bouncing between different
3375 if (cmp_min > 0 || cmp_min < 0)
3376 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
3378 /* Similarly, if the new maximum is smaller or larger than
3379 the previous one, go all the way to +INF. */
3380 if (cmp_max < 0 || cmp_max > 0)
3381 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
3383 /* If we ended up with a (-INF, +INF) range, set it to
3385 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
3386 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
3391 /* If the new range is different than the previous value, keep
3393 if (update_value_range (lhs, &vr_result))
3394 return SSA_PROP_INTERESTING;
3396 /* Nothing changed, don't add outgoing edges. */
3397 return SSA_PROP_NOT_INTERESTING;
3399 /* No match found. Set the LHS to VARYING. */
3401 set_value_range_to_varying (lhs_vr);
3402 return SSA_PROP_VARYING;
3406 /* Traverse all the blocks folding conditionals with known ranges. */
3412 prop_value_t *single_val_range;
3413 bool do_value_subst_p;
3417 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
3418 dump_all_value_ranges (dump_file);
3419 fprintf (dump_file, "\n");
3422 /* We may have ended with ranges that have exactly one value. Those
3423 values can be substituted as any other copy/const propagated
3424 value using substitute_and_fold. */
3425 single_val_range = xmalloc (num_ssa_names * sizeof (*single_val_range));
3426 memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range));
3428 do_value_subst_p = false;
3429 for (i = 0; i < num_ssa_names; i++)
3431 && vr_value[i]->type == VR_RANGE
3432 && vr_value[i]->min == vr_value[i]->max)
3434 single_val_range[i].value = vr_value[i]->min;
3435 do_value_subst_p = true;
3438 if (!do_value_subst_p)
3440 /* We found no single-valued ranges, don't waste time trying to
3441 do single value substitution in substitute_and_fold. */
3442 free (single_val_range);
3443 single_val_range = NULL;
3446 substitute_and_fold (single_val_range, true);
3448 /* Free allocated memory. */
3449 for (i = 0; i < num_ssa_names; i++)
3452 BITMAP_FREE (vr_value[i]->equiv);
3456 free (single_val_range);
3461 /* Main entry point to VRP (Value Range Propagation). This pass is
3462 loosely based on J. R. C. Patterson, ``Accurate Static Branch
3463 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
3464 Programming Language Design and Implementation, pp. 67-78, 1995.
3465 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
3467 This is essentially an SSA-CCP pass modified to deal with ranges
3468 instead of constants.
3470 While propagating ranges, we may find that two or more SSA name
3471 have equivalent, though distinct ranges. For instance,
3474 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0>
3476 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
3480 In the code above, pointer p_5 has range [q_2, q_2], but from the
3481 code we can also determine that p_5 cannot be NULL and, if q_2 had
3482 a non-varying range, p_5's range should also be compatible with it.
3484 These equivalences are created by two expressions: ASSERT_EXPR and
3485 copy operations. Since p_5 is an assertion on p_4, and p_4 was the
3486 result of another assertion, then we can use the fact that p_5 and
3487 p_4 are equivalent when evaluating p_5's range.
3489 Together with value ranges, we also propagate these equivalences
3490 between names so that we can take advantage of information from
3491 multiple ranges when doing final replacement. Note that this
3492 equivalency relation is transitive but not symmetric.
3494 In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
3495 cannot assert that q_2 is equivalent to p_5 because q_2 may be used
3496 in contexts where that assertion does not hold (e.g., in line 6).
3498 TODO, the main difference between this pass and Patterson's is that
3499 we do not propagate edge probabilities. We only compute whether
3500 edges can be taken or not. That is, instead of having a spectrum
3501 of jump probabilities between 0 and 1, we only deal with 0, 1 and
3502 DON'T KNOW. In the future, it may be worthwhile to propagate
3503 probabilities to aid branch prediction. */
3508 insert_range_assertions ();
3510 cfg_loops = loop_optimizer_init (NULL);
3513 scev_initialize (cfg_loops);
3514 estimate_numbers_of_iterations (cfg_loops);
3518 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
3524 loop_optimizer_finalize (cfg_loops, NULL);
3525 current_loops = NULL;
3528 remove_range_assertions ();
3534 return flag_tree_vrp != 0;
3537 struct tree_opt_pass pass_vrp =
3540 gate_vrp, /* gate */
3541 execute_vrp, /* execute */
3544 0, /* static_pass_number */
3545 TV_TREE_VRP, /* tv_id */
3546 PROP_ssa | PROP_alias, /* properties_required */
3547 0, /* properties_provided */
3548 0, /* properties_destroyed */
3549 0, /* todo_flags_start */
3554 | TODO_update_ssa, /* todo_flags_finish */