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 maybe_add_assert_expr. */
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 /* Given a conditional predicate COND that has WHICH as one of its
52 operands, return the other operand. No error checking is done.
53 This helper assumes that COND is a comparison and WHICH is one of
57 get_opposite_operand (tree cond, tree which)
59 if (TREE_OPERAND (cond, 0) == which)
60 return TREE_OPERAND (cond, 1);
62 return TREE_OPERAND (cond, 0);
66 /* Given a comparison code, return its opposite. Note that this is *not*
67 the same as inverting its truth value (invert_tree_comparison). Here we
68 just want to literally flip the comparison around.
70 So, '<' gets '>', '<=' gets '>='. Both '==' and '!=' are returned
74 opposite_comparison (enum tree_code code)
107 /* Set value range VR to {T, MIN, MAX}. */
110 set_value_range (value_range *vr, enum value_range_type t, tree min, tree max)
112 #if defined ENABLE_CHECKING
113 if (t == VR_RANGE || t == VR_ANTI_RANGE)
117 gcc_assert (min && max);
119 if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
120 gcc_assert (min != TYPE_MIN_VALUE (TREE_TYPE (min))
121 || max != TYPE_MAX_VALUE (TREE_TYPE (max)));
123 cmp = compare_values (min, max);
124 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
129 && INTEGRAL_TYPE_P (TREE_TYPE (min))
130 && min == TYPE_MIN_VALUE (TREE_TYPE (min))
131 && max == TYPE_MAX_VALUE (TREE_TYPE (max)))
133 /* Ranges that cover all the possible values for the type decay
135 vr->type = VR_VARYING;
147 /* Similar to set_value_range but return true if any field of VR
148 changed from its previous value. */
151 update_value_range (value_range *vr, enum value_range_type t, tree min,
154 bool is_new = vr->type != t || vr->min != min || vr->max != max;
156 set_value_range (vr, t, min, max);
162 /* Return value range information for VAR. Create an empty range if
166 get_value_range (tree var)
171 vr = SSA_NAME_VALUE_RANGE (var);
175 /* Create a default value range. */
176 vr = ggc_alloc (sizeof (*vr));
177 memset ((void *) vr, 0, sizeof (*vr));
178 SSA_NAME_VALUE_RANGE (var) = vr;
180 /* If VAR is a default definition for a PARM_DECL, then we have to
181 assume a VARYING range for it. */
182 sym = SSA_NAME_VAR (var);
183 if (TREE_CODE (sym) == PARM_DECL && var == var_ann (sym)->default_def)
184 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
190 /* Return true if value range VR involves at least one symbol. */
193 symbolic_range_p (value_range *vr)
195 return (!is_gimple_min_invariant (vr->min)
196 || !is_gimple_min_invariant (vr->max));
200 /* Return true if EXPR computes a non-zero value. */
203 expr_computes_nonzero (tree expr)
205 /* Type casts won't change anything, so just strip it. */
208 /* Calling alloca, guarantees that the value is non-NULL. */
209 if (alloca_call_p (expr))
212 /* The address of a non-weak symbol is never NULL, unless the user
213 has requested not to remove NULL pointer checks. */
214 if (flag_delete_null_pointer_checks
215 && TREE_CODE (expr) == ADDR_EXPR
216 && DECL_P (TREE_OPERAND (expr, 0))
217 && !DECL_WEAK (TREE_OPERAND (expr, 0)))
220 /* IOR of any value with a nonzero value will result in a nonzero
222 if (TREE_CODE (expr) == BIT_IOR_EXPR
223 && integer_nonzerop (TREE_OPERAND (expr, 1)))
230 /* Return true if VR is ~[0, 0]. */
233 range_is_nonnull (value_range *vr)
235 return vr->type == VR_ANTI_RANGE
236 && integer_zerop (vr->min)
237 && integer_zerop (vr->max);
241 /* Return true if VR is [0, 0]. */
244 range_is_null (value_range *vr)
246 return vr->type == VR_RANGE
247 && integer_zerop (vr->min)
248 && integer_zerop (vr->max);
252 /* Set value range VR to a non-NULL range of type TYPE. */
255 set_value_range_to_nonnull (value_range *vr, tree type)
257 tree zero = build_int_cst (type, 0);
258 set_value_range (vr, VR_ANTI_RANGE, zero, zero);
262 /* Set value range VR to a NULL range of type TYPE. */
265 set_value_range_to_null (value_range *vr, tree type)
267 tree zero = build_int_cst (type, 0);
268 set_value_range (vr, VR_RANGE, zero, zero);
272 /* Set value range VR to VR_VARYING. */
275 set_value_range_to_varying (value_range *vr)
277 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
281 /* Compare two values VAL1 and VAL2. Return
283 -2 if VAL1 and VAL2 cannot be compared at compile-time,
286 +1 if VAL1 > VAL2, and
289 This is similar to tree_int_cst_compare but supports pointer values
290 and values that cannot be compared at compile time. */
293 compare_values (tree val1, tree val2)
298 /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
300 gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
301 == POINTER_TYPE_P (TREE_TYPE (val2)));
303 /* Do some limited symbolic comparisons. */
304 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
306 /* We can determine some comparisons against +INF and -INF even
307 if the other value is an expression. */
308 if (val1 == TYPE_MAX_VALUE (TREE_TYPE (val1))
309 && TREE_CODE (val2) == MINUS_EXPR)
311 /* +INF > NAME - CST. */
314 else if (val1 == TYPE_MIN_VALUE (TREE_TYPE (val1))
315 && TREE_CODE (val2) == PLUS_EXPR)
317 /* -INF < NAME + CST. */
320 else if (TREE_CODE (val1) == MINUS_EXPR
321 && val2 == TYPE_MAX_VALUE (TREE_TYPE (val2)))
323 /* NAME - CST < +INF. */
326 else if (TREE_CODE (val1) == PLUS_EXPR
327 && val2 == TYPE_MIN_VALUE (TREE_TYPE (val2)))
329 /* NAME + CST > -INF. */
334 if ((TREE_CODE (val1) == SSA_NAME
335 || TREE_CODE (val1) == PLUS_EXPR
336 || TREE_CODE (val1) == MINUS_EXPR)
337 && (TREE_CODE (val2) == SSA_NAME
338 || TREE_CODE (val2) == PLUS_EXPR
339 || TREE_CODE (val2) == MINUS_EXPR))
343 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
344 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
345 same name, return -2. */
346 if (TREE_CODE (val1) == SSA_NAME)
353 n1 = TREE_OPERAND (val1, 0);
354 c1 = TREE_OPERAND (val1, 1);
357 if (TREE_CODE (val2) == SSA_NAME)
364 n2 = TREE_OPERAND (val2, 0);
365 c2 = TREE_OPERAND (val2, 1);
368 /* Both values must use the same name. */
372 if (TREE_CODE (val1) == SSA_NAME)
374 if (TREE_CODE (val2) == SSA_NAME)
377 else if (TREE_CODE (val2) == PLUS_EXPR)
378 /* NAME < NAME + CST */
380 else if (TREE_CODE (val2) == MINUS_EXPR)
381 /* NAME > NAME - CST */
384 else if (TREE_CODE (val1) == PLUS_EXPR)
386 if (TREE_CODE (val2) == SSA_NAME)
387 /* NAME + CST > NAME */
389 else if (TREE_CODE (val2) == PLUS_EXPR)
390 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
391 return compare_values (c1, c2);
392 else if (TREE_CODE (val2) == MINUS_EXPR)
393 /* NAME + CST1 > NAME - CST2 */
396 else if (TREE_CODE (val1) == MINUS_EXPR)
398 if (TREE_CODE (val2) == SSA_NAME)
399 /* NAME - CST < NAME */
401 else if (TREE_CODE (val2) == PLUS_EXPR)
402 /* NAME - CST1 < NAME + CST2 */
404 else if (TREE_CODE (val2) == MINUS_EXPR)
405 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
406 C1 and C2 are swapped in the call to compare_values. */
407 return compare_values (c2, c1);
413 /* We cannot compare non-constants. */
414 if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
417 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
418 return tree_int_cst_compare (val1, val2);
423 /* First see if VAL1 and VAL2 are not the same. */
424 if (val1 == val2 || operand_equal_p (val1, val2, 0))
427 /* If VAL1 is a lower address than VAL2, return -1. */
428 t = fold_binary (LT_EXPR, boolean_type_node, val1, val2);
429 if (t == boolean_true_node)
432 /* If VAL1 is a higher address than VAL2, return +1. */
433 t = fold_binary (GT_EXPR, boolean_type_node, val1, val2);
434 if (t == boolean_true_node)
437 /* If VAL1 is different than VAL2, return +2. */
438 t = fold_binary (NE_EXPR, boolean_type_node, val1, val2);
439 if (t == boolean_true_node)
447 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
448 0 if VAL is not inside VR,
449 -2 if we cannot tell either way. */
452 value_inside_range (tree val, value_range *vr)
456 cmp1 = compare_values (val, vr->min);
457 if (cmp1 == -2 || cmp1 == 2)
460 cmp2 = compare_values (val, vr->max);
461 if (cmp2 == -2 || cmp2 == 2)
464 return (cmp1 == 0 || cmp1 == 1) && (cmp2 == -1 || cmp2 == 0);
468 /* Return true if value ranges VR0 and VR1 have a non-empty
472 value_ranges_intersect_p (value_range *vr0, value_range *vr1)
474 return (value_inside_range (vr1->min, vr0) == 1
475 || value_inside_range (vr1->max, vr0) == 1
476 || value_inside_range (vr0->min, vr1) == 1
477 || value_inside_range (vr0->max, vr1) == 1);
481 /* Extract value range information from an ASSERT_EXPR EXPR and store
485 extract_range_from_assert (value_range *vr_p, tree expr)
487 tree var, cond, limit, type;
489 enum tree_code cond_code;
491 var = ASSERT_EXPR_VAR (expr);
492 cond = ASSERT_EXPR_COND (expr);
493 cond_code = TREE_CODE (cond);
495 gcc_assert (COMPARISON_CLASS_P (cond));
497 /* Find VAR in the ASSERT_EXPR conditional. */
498 limit = get_opposite_operand (cond, var);
499 type = TREE_TYPE (limit);
501 gcc_assert (limit != var);
503 /* For pointer arithmetic, we only keep track of anti-ranges
504 (NE_EXPR). Notice that we don't need to handle EQ_EXPR in these
505 cases because assertions with equalities are never generated.
506 The assert pass generates straight assignments in those cases. */
507 if (POINTER_TYPE_P (type) && cond_code != NE_EXPR)
509 set_value_range_to_varying (vr_p);
513 /* Special handling for integral types with super-types. Some FEs
514 construct integral types derived from other types and restrict
515 the range of values these new types may take.
517 It may happen that LIMIT is actually smaller than TYPE's minimum
518 value. For instance, the Ada FE is generating code like this
521 D.1480_32 = nam_30 - 300000361;
522 if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
524 D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;
526 All the names are of type types__name_id___XDLU_300000000__399999999
527 which has min == 300000000 and max == 399999999. This means that
528 the ASSERT_EXPR would try to create the range [3000000, 1] which
531 The fact that the type specifies MIN and MAX values does not
532 automatically mean that every variable of that type will always
533 be within that range, so the predicate may well be true at run
534 time. If we had symbolic -INF and +INF values, we could
535 represent this range, but we currently represent -INF and +INF
536 using the type's min and max values.
538 So, the only sensible thing we can do for now is set the
539 resulting range to VR_VARYING. TODO, would having symbolic -INF
540 and +INF values be worth the trouble? */
541 if (TREE_TYPE (type))
543 if (cond_code == LE_EXPR || cond_code == LT_EXPR)
545 tree type_min = TYPE_MIN_VALUE (type);
546 int cmp = compare_values (limit, type_min);
548 /* For < or <= comparisons, if LIMIT is smaller than
549 TYPE_MIN, set the range to VR_VARYING. */
550 if (cmp == -1 || cmp == 0)
552 set_value_range_to_varying (vr_p);
556 else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
558 tree type_max = TYPE_MIN_VALUE (type);
559 int cmp = compare_values (limit, type_max);
561 /* For > or >= comparisons, if LIMIT is bigger than
562 TYPE_MAX, set the range to VR_VARYING. */
563 if (cmp == 1 || cmp == 0)
565 set_value_range_to_varying (vr_p);
571 if (TREE_CODE (cond) == NE_EXPR)
572 set_value_range (vr_p, VR_ANTI_RANGE, limit, limit);
573 else if (TREE_CODE (cond) == LE_EXPR)
574 set_value_range (vr_p, VR_RANGE, TYPE_MIN_VALUE (type), limit);
575 else if (TREE_CODE (cond) == LT_EXPR)
577 tree one = build_int_cst (type, 1);
578 set_value_range (vr_p, VR_RANGE, TYPE_MIN_VALUE (type),
579 fold (build (MINUS_EXPR, type, limit, one)));
581 else if (TREE_CODE (cond) == GE_EXPR)
582 set_value_range (vr_p, VR_RANGE, limit, TYPE_MAX_VALUE (type));
583 else if (TREE_CODE (cond) == GT_EXPR)
585 tree one = build_int_cst (type, 1);
586 set_value_range (vr_p, VR_RANGE,
587 fold (build (PLUS_EXPR, type, limit, one)),
588 TYPE_MAX_VALUE (type));
593 /* If VAR already has a known range and the two ranges have a
594 non-empty intersection, we can refine the resulting range.
595 Since the assert expression creates an equivalency and at the
596 same time it asserts a predicate, we can take the intersection of
597 the two ranges to get better precision. */
598 var_vr = get_value_range (var);
599 if (var_vr->type == VR_RANGE
600 && vr_p->type == VR_RANGE
601 && value_ranges_intersect_p (var_vr, vr_p))
605 /* Use the larger of the two minimums. */
606 if (compare_values (vr_p->min, var_vr->min) == -1)
611 /* Use the smaller of the two maximums. */
612 if (compare_values (vr_p->max, var_vr->max) == 1)
617 set_value_range (vr_p, vr_p->type, min, max);
622 /* Extract range information from SSA name VAR and store it in VR. If
623 VAR has an interesting range, use it. Otherwise, create the
624 range [VAR, VAR] and return it. This is useful in situations where
625 we may have conditionals testing values of VARYING names. For
632 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
636 extract_range_from_ssa_name (value_range *vr, tree var)
638 value_range *var_vr = get_value_range (var);
640 if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
643 set_value_range (vr, VR_RANGE, var, var);
647 /* Extract range information from a binary expression EXPR based on
648 the ranges of each of its operands and the expression code. */
651 extract_range_from_binary_expr (value_range *vr, tree expr)
653 enum tree_code code = TREE_CODE (expr);
654 tree op0, op1, min, max;
655 value_range vr0, vr1;
658 /* Not all binary expressions can be applied to ranges in a
659 meaningful way. Handle only arithmetic operations. */
660 if (code != PLUS_EXPR
661 && code != MINUS_EXPR
663 && code != TRUNC_DIV_EXPR
664 && code != FLOOR_DIV_EXPR
665 && code != CEIL_DIV_EXPR
666 && code != EXACT_DIV_EXPR
667 && code != ROUND_DIV_EXPR
671 set_value_range_to_varying (vr);
675 /* Get value ranges for each operand. For constant operands, create
676 a new value range with the operand to simplify processing. */
677 op0 = TREE_OPERAND (expr, 0);
678 if (TREE_CODE (op0) == SSA_NAME)
679 vr0 = *(get_value_range (op0));
682 if (is_gimple_min_invariant (op0))
683 set_value_range (&vr0, VR_RANGE, op0, op0);
685 set_value_range_to_varying (&vr0);
688 op1 = TREE_OPERAND (expr, 1);
689 if (TREE_CODE (op1) == SSA_NAME)
690 vr1 = *(get_value_range (op1));
693 if (is_gimple_min_invariant (op1))
694 set_value_range (&vr1, VR_RANGE, op1, op1);
696 set_value_range_to_varying (&vr1);
699 /* If either range is UNDEFINED, so is the result. */
700 if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
702 set_value_range (vr, VR_UNDEFINED, NULL_TREE, NULL_TREE);
706 /* If either range is VARYING, so is the result. */
707 if (vr0.type == VR_VARYING || vr1.type == VR_VARYING)
709 set_value_range_to_varying (vr);
713 /* If the ranges are of different types, the result is VARYING. */
714 if (vr0.type != vr1.type)
716 set_value_range_to_varying (vr);
720 /* TODO. Refuse to do any symbolic range operations for now. */
721 if (symbolic_range_p (&vr0) || symbolic_range_p (&vr1))
723 set_value_range_to_varying (vr);
727 /* Now evaluate the expression to determine the new range. */
728 if (POINTER_TYPE_P (TREE_TYPE (expr))
729 || POINTER_TYPE_P (TREE_TYPE (op0))
730 || POINTER_TYPE_P (TREE_TYPE (op1)))
732 /* For pointer types, we are really only interested in asserting
733 whether the expression evaluates to non-NULL. FIXME. We
734 used to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR),
735 but ivopts is generating expressions with pointer
736 multiplication in them. */
737 if (code == PLUS_EXPR)
739 /* Assume that pointers can never wrap around. FIXME, Is
741 tree zero = build_int_cst (TREE_TYPE (expr), 0);
742 set_value_range (vr, VR_ANTI_RANGE, zero, zero);
746 /* Subtracting from a pointer, may yield 0, so just drop the
747 resulting range to varying. */
748 set_value_range_to_varying (vr);
754 /* For integer ranges, apply the operation to each end of the
755 range and see what we end up with. */
756 if (code == PLUS_EXPR
761 /* For operations that make the resulting range directly
762 proportional to the original ranges, apply the operation to
763 the same end of each range. */
764 min = int_const_binop (code, vr0.min, vr1.min, 0);
765 max = int_const_binop (code, vr0.max, vr1.max, 0);
769 /* For operations that make the resulting range inversely
770 proportional to the original ranges (-, /), apply the
771 operation to the opposite ends of each range. */
772 min = int_const_binop (code, vr0.min, vr1.max, 0);
773 max = int_const_binop (code, vr0.max, vr1.min, 0);
776 cmp = compare_values (min, max);
777 if (cmp == -2 || cmp == 1)
779 /* If the new range has its limits swapped around (MIN > MAX),
780 then the operation caused one of them to wrap around, mark
781 the new range VARYING. */
782 set_value_range_to_varying (vr);
785 set_value_range (vr, vr0.type, min, max);
789 /* Like expr_computes_nonzero, but this function uses value ranges
793 vrp_expr_computes_nonzero (tree expr)
795 if (expr_computes_nonzero (expr))
798 /* If we have an expression of the form &X->a, then the expression
799 is nonnull if X is nonnull. */
800 if (TREE_CODE (expr) == ADDR_EXPR)
802 tree base = get_base_address (TREE_OPERAND (expr, 0));
804 if (base != NULL_TREE
805 && TREE_CODE (base) == INDIRECT_REF
806 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
808 value_range *vr = get_value_range (TREE_OPERAND (base, 0));
809 if (range_is_nonnull (vr))
818 /* Extract range information from a unary expression EXPR based on
819 the range of its operand and the expression code. */
822 extract_range_from_unary_expr (value_range *vr, tree expr)
824 enum tree_code code = TREE_CODE (expr);
829 /* Get value ranges for the operand. For constant operands, create
830 a new value range with the operand to simplify processing. */
831 op0 = TREE_OPERAND (expr, 0);
832 if (TREE_CODE (op0) == SSA_NAME)
833 vr0 = *(get_value_range (op0));
836 if (is_gimple_min_invariant (op0))
837 set_value_range (&vr0, VR_RANGE, op0, op0);
839 set_value_range_to_varying (&vr0);
842 /* If VR0 is UNDEFINED, so is the result. */
843 if (vr0.type == VR_UNDEFINED)
845 set_value_range (vr, VR_UNDEFINED, NULL_TREE, NULL_TREE);
849 /* If VR0 is VARYING, so is the result. */
850 if (vr0.type == VR_VARYING)
852 set_value_range_to_varying (vr);
856 /* TODO. Refuse to do any symbolic range operations for now. */
857 if (symbolic_range_p (&vr0))
859 set_value_range_to_varying (vr);
863 /* If the operand is neither a pointer nor an integral type, set the
864 range to VARYING. TODO, we may set the range to non-zero. */
865 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
866 && !POINTER_TYPE_P (TREE_TYPE (op0)))
868 set_value_range_to_varying (vr);
872 /* If the expression involves pointers, we are only interested in
873 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
874 if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
876 if (range_is_nonnull (&vr0) || expr_computes_nonzero (expr))
877 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
878 else if (range_is_null (&vr0))
879 set_value_range_to_null (vr, TREE_TYPE (expr));
881 set_value_range_to_varying (vr);
886 /* Handle unary expressions on integer ranges. */
887 if ((code == NOP_EXPR || code == CONVERT_EXPR)
888 && (TYPE_SIZE (TREE_TYPE (vr0.min)) != TYPE_SIZE (TREE_TYPE (expr))))
890 /* When converting types of different sizes, set the result to
891 VARYING. Things like sign extensions and precision loss may
892 change the range. For instance, if x_3 is of type 'long long
893 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
894 is impossible to know at compile time whether y_5 will be
896 set_value_range_to_varying (vr);
900 /* Apply the operation to each end of the range and see what we end
902 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
903 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
905 cmp = compare_values (min, max);
906 if (cmp == -2 || cmp == 1)
908 /* If the new range has its limits swapped around (MIN > MAX),
909 then the operation caused one of them to wrap around, mark
910 the new range VARYING. */
911 set_value_range_to_varying (vr);
914 set_value_range (vr, vr0.type, min, max);
918 /* Try to compute a useful range out of expression EXPR and store it
922 extract_range_from_expr (value_range *vr, tree expr)
924 enum tree_code code = TREE_CODE (expr);
926 if (code == ASSERT_EXPR)
927 extract_range_from_assert (vr, expr);
928 else if (code == SSA_NAME)
929 extract_range_from_ssa_name (vr, expr);
930 else if (TREE_CODE_CLASS (code) == tcc_binary)
931 extract_range_from_binary_expr (vr, expr);
932 else if (TREE_CODE_CLASS (code) == tcc_unary)
933 extract_range_from_unary_expr (vr, expr);
934 else if (vrp_expr_computes_nonzero (expr))
935 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
936 else if (TREE_CODE (expr) == INTEGER_CST)
937 set_value_range (vr, VR_RANGE, expr, expr);
939 set_value_range_to_varying (vr);
943 /* Given a range VR, a loop L and a variable VAR, determine whether it
944 would be profitable to adjust VR using scalar evolution information
945 for VAR. If so, update VR with the new limits. */
948 adjust_range_with_scev (value_range *vr, struct loop *l, tree var)
950 tree init, step, chrec;
953 /* TODO. Don't adjust anti-ranges. An anti-range may provide
954 better opportunities than a regular range, but I'm not sure. */
955 if (vr->type == VR_ANTI_RANGE)
958 chrec = analyze_scalar_evolution (l, var);
959 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
962 init = CHREC_LEFT (chrec);
963 step = CHREC_RIGHT (chrec);
965 /* If STEP is symbolic, we can't know whether INIT will be the
966 minimum or maximum value in the range. */
967 if (!is_gimple_min_invariant (step))
970 /* FIXME. When dealing with unsigned types,
971 analyze_scalar_evolution sets STEP to very large unsigned values
972 when the evolution goes backwards. This confuses this analysis
973 because we think that INIT is the smallest value that the range
974 can take, instead of the largest. Ignore these chrecs for now. */
975 if (INTEGRAL_TYPE_P (TREE_TYPE (step)) && TYPE_UNSIGNED (TREE_TYPE (step)))
978 /* If STEP is negative, then INIT is the maximum value the range
979 will take. Otherwise, INIT is the minimum value. */
980 init_is_max = (tree_int_cst_sgn (step) < 0);
982 if (!POINTER_TYPE_P (TREE_TYPE (init))
983 && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
985 /* For VARYING or UNDEFINED ranges, just about anything we get
986 from scalar evolutions should be better. */
988 set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)), init);
990 set_value_range (vr, VR_RANGE, init, TYPE_MAX_VALUE (TREE_TYPE (init)));
992 else if (vr->type == VR_RANGE)
999 /* INIT is the maximum value. If INIT is lower than VR->MAX
1000 but no smaller than VR->MIN, set VR->MAX to INIT. */
1001 if (compare_values (init, max) == -1)
1005 /* If we just created an invalid range with the minimum
1006 greater than the maximum, take the minimum all the
1008 if (compare_values (min, max) == 1)
1009 min = TYPE_MIN_VALUE (TREE_TYPE (min));
1014 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
1015 if (compare_values (init, min) == 1)
1019 /* If we just created an invalid range with the minimum
1020 greater than the maximum, take the maximum all the
1022 if (compare_values (min, max) == 1)
1023 max = TYPE_MAX_VALUE (TREE_TYPE (max));
1027 set_value_range (vr, VR_RANGE, min, max);
1032 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
1034 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for all the
1035 values in the ranges.
1037 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
1039 - Return NULL_TREE if it is not always possible to determine the value of
1043 compare_ranges (enum tree_code comp, value_range *vr0, value_range *vr1)
1045 /* VARYING or UNDEFINED ranges cannot be compared. */
1046 if (vr0->type == VR_VARYING
1047 || vr0->type == VR_UNDEFINED
1048 || vr1->type == VR_VARYING
1049 || vr1->type == VR_UNDEFINED)
1052 /* Anti-ranges need to be handled separately. */
1053 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
1055 /* If both are anti-ranges, then we cannot compute any
1057 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
1060 /* These comparisons are never statically computable. */
1067 /* Equality can be computed only between a range and an
1068 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
1069 if (vr0->type == VR_RANGE)
1071 /* To simplify processing, make VR0 the anti-range. */
1072 value_range *tmp = vr0;
1077 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
1079 if (compare_values (vr0->min, vr1->min) == 0
1080 && compare_values (vr0->max, vr1->max) == 0)
1081 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1086 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
1087 operands around and change the comparison code. */
1088 if (comp == GT_EXPR || comp == GE_EXPR)
1091 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
1097 if (comp == EQ_EXPR)
1099 /* Equality may only be computed if both ranges represent
1100 exactly one value. */
1101 if (compare_values (vr0->min, vr0->max) == 0
1102 && compare_values (vr1->min, vr1->max) == 0)
1104 int cmp_min = compare_values (vr0->min, vr1->min);
1105 int cmp_max = compare_values (vr0->max, vr1->max);
1106 if (cmp_min == 0 && cmp_max == 0)
1107 return boolean_true_node;
1108 else if (cmp_min != -2 && cmp_max != -2)
1109 return boolean_false_node;
1114 else if (comp == NE_EXPR)
1118 /* If VR0 is completely to the left or completely to the right
1119 of VR1, they are always different. Notice that we need to
1120 make sure that both comparisons yield similar results to
1121 avoid comparing values that cannot be compared at
1123 cmp1 = compare_values (vr0->max, vr1->min);
1124 cmp2 = compare_values (vr0->min, vr1->max);
1125 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
1126 return boolean_true_node;
1128 /* If VR0 and VR1 represent a single value and are identical,
1130 else if (compare_values (vr0->min, vr0->max) == 0
1131 && compare_values (vr1->min, vr1->max) == 0
1132 && compare_values (vr0->min, vr1->min) == 0
1133 && compare_values (vr0->max, vr1->max) == 0)
1134 return boolean_false_node;
1136 /* Otherwise, they may or may not be different. */
1140 else if (comp == LT_EXPR || comp == LE_EXPR)
1144 /* If VR0 is to the left of VR1, return true. */
1145 tst = compare_values (vr0->max, vr1->min);
1146 if ((comp == LT_EXPR && tst == -1)
1147 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1148 return boolean_true_node;
1150 /* If VR0 is to the right of VR1, return false. */
1151 tst = compare_values (vr0->min, vr1->max);
1152 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1153 || (comp == LE_EXPR && tst == 1))
1154 return boolean_false_node;
1156 /* Otherwise, we don't know. */
1164 /* Given a value range VR, a value VAL and a comparison code COMP, return
1165 BOOLEAN_TRUE_NODE if VR COMP VR1 always returns true for all the
1166 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1167 always returns false. Return NULL_TREE if it is not always
1168 possible to determine the value of the comparison. */
1171 compare_range_with_value (enum tree_code comp, value_range *vr, tree val)
1173 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1176 /* Anti-ranges need to be handled separately. */
1177 if (vr->type == VR_ANTI_RANGE)
1179 /* For anti-ranges, the only predicates that we can compute at
1180 compile time are equality and inequality. */
1187 /* ~[VAL, VAL] == VAL is always false. */
1188 if (compare_values (vr->min, val) == 0
1189 && compare_values (vr->max, val) == 0)
1190 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1195 if (comp == EQ_EXPR)
1197 /* EQ_EXPR may only be computed if VR represents exactly
1199 if (compare_values (vr->min, vr->max) == 0)
1201 int cmp = compare_values (vr->min, val);
1203 return boolean_true_node;
1204 else if (cmp == -1 || cmp == 1 || cmp == 2)
1205 return boolean_false_node;
1210 else if (comp == NE_EXPR)
1212 /* If VAL is not inside VR, then they are always different. */
1213 if (compare_values (vr->max, val) == -1
1214 || compare_values (vr->min, val) == 1)
1215 return boolean_true_node;
1217 /* If VR represents exactly one value equal to VAL, then return
1219 if (compare_values (vr->min, vr->max) == 0
1220 && compare_values (vr->min, val) == 0)
1221 return boolean_false_node;
1223 /* Otherwise, they may or may not be different. */
1226 else if (comp == LT_EXPR || comp == LE_EXPR)
1230 /* If VR is to the left of VAL, return true. */
1231 tst = compare_values (vr->max, val);
1232 if ((comp == LT_EXPR && tst == -1)
1233 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1234 return boolean_true_node;
1236 /* If VR is to the right of VAL, return false. */
1237 tst = compare_values (vr->min, val);
1238 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1239 || (comp == LE_EXPR && tst == 1))
1240 return boolean_false_node;
1242 /* Otherwise, we don't know. */
1245 else if (comp == GT_EXPR || comp == GE_EXPR)
1249 /* If VR is to the right of VAL, return true. */
1250 tst = compare_values (vr->min, val);
1251 if ((comp == GT_EXPR && tst == 1)
1252 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
1253 return boolean_true_node;
1255 /* If VR is to the left of VAL, return false. */
1256 tst = compare_values (vr->max, val);
1257 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
1258 || (comp == GE_EXPR && tst == -1))
1259 return boolean_false_node;
1261 /* Otherwise, we don't know. */
1269 /* Debugging dumps. */
1272 dump_value_range (FILE *file, value_range *vr)
1275 fprintf (file, "[]");
1276 else if (vr->type == VR_UNDEFINED)
1277 fprintf (file, "UNDEFINED");
1278 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
1280 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
1281 print_generic_expr (file, vr->min, 0);
1282 fprintf (file, ", ");
1283 print_generic_expr (file, vr->max, 0);
1284 fprintf (file, "]");
1286 else if (vr->type == VR_VARYING)
1287 fprintf (file, "VARYING");
1289 fprintf (file, "INVALID RANGE");
1293 /* Dump value range VR to stderr. */
1296 debug_value_range (value_range *vr)
1298 dump_value_range (stderr, vr);
1302 /* Dump value ranges of all SSA_NAMEs to FILE. */
1305 dump_all_value_ranges (FILE *file)
1309 for (i = 0; i < num_ssa_names; i++)
1311 tree var = ssa_name (i);
1312 if (var && SSA_NAME_VALUE_RANGE (var))
1314 print_generic_expr (file, var, 0);
1315 fprintf (file, ": ");
1316 dump_value_range (file, SSA_NAME_VALUE_RANGE (var));
1317 fprintf (file, "\n");
1321 fprintf (file, "\n");
1325 /* Dump all value ranges to stderr. */
1328 debug_all_value_ranges (void)
1330 dump_all_value_ranges (stderr);
1334 /*---------------------------------------------------------------------------
1335 Value Range Propagation
1336 ---------------------------------------------------------------------------*/
1338 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
1339 create a new SSA name N and return the assertion assignment
1340 'V = ASSERT_EXPR <V, V OP W>'. */
1343 build_assert_expr_for (tree cond, tree v)
1347 gcc_assert (TREE_CODE (v) == SSA_NAME);
1348 n = duplicate_ssa_name (v, NULL_TREE);
1350 if (COMPARISON_CLASS_P (cond))
1352 /* Build N = ASSERT_EXPR <V, COND>. As a special case, if the
1353 conditional is an EQ_EXPR (V == Z), just build the assignment
1355 if (TREE_CODE (cond) == EQ_EXPR)
1357 tree other = get_opposite_operand (cond, v);
1358 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, other);
1361 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n,
1362 build (ASSERT_EXPR, TREE_TYPE (v), v, cond));
1364 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1366 /* Given !V, build the assignment N = false. */
1367 tree op0 = TREE_OPERAND (cond, 0);
1368 gcc_assert (op0 == v);
1369 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
1371 else if (TREE_CODE (cond) == SSA_NAME)
1373 /* Given V, build the assignment N = true. */
1374 gcc_assert (v == cond);
1375 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
1380 SSA_NAME_DEF_STMT (n) = assertion;
1382 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
1383 operand of the ASSERT_EXPR. Register the new name and the old one
1384 in the replacement table so that we can fix the SSA web after
1385 adding all the ASSERT_EXPRs. */
1386 register_new_name_mapping (n, v);
1392 /* Return false if EXPR is a predicate expression involving floating
1396 fp_predicate (tree expr)
1398 return (COMPARISON_CLASS_P (expr)
1399 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
1403 /* Return an expression predicate that represents the range of values
1404 that can be taken by operand OP after STMT executes. */
1407 infer_value_range (tree stmt, tree op)
1409 /* Do not attempt to infer anything in names that flow through
1411 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1414 if (POINTER_TYPE_P (TREE_TYPE (op)))
1417 unsigned num_uses, num_derefs;
1419 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
1420 if (num_derefs > 0 && flag_delete_null_pointer_checks)
1422 /* We can only assume that a pointer dereference will yield
1423 non-NULL if -fdelete-null-pointer-checks is enabled. */
1424 tree null = build_int_cst (TREE_TYPE (op), 0);
1425 tree t = build (NE_EXPR, boolean_type_node, op, null);
1434 /* Return true if OP is the result of an ASSERT_EXPR that tests the
1435 same condition as COND. */
1438 has_assert_expr (tree op, tree cond)
1440 tree def_stmt = SSA_NAME_DEF_STMT (op);
1441 tree assert_expr, other_cond, other_op;
1443 /* If OP was not generated by an ASSERT_EXPR, return false. */
1444 if (TREE_CODE (def_stmt) != MODIFY_EXPR
1445 || TREE_CODE (TREE_OPERAND (def_stmt, 1)) != ASSERT_EXPR)
1448 assert_expr = TREE_OPERAND (def_stmt, 1);
1449 other_cond = ASSERT_EXPR_COND (assert_expr);
1450 other_op = ASSERT_EXPR_VAR (assert_expr);
1452 if (TREE_CODE (cond) == TREE_CODE (other_cond))
1456 /* If COND is not a comparison predicate, something is wrong. */
1457 gcc_assert (COMPARISON_CLASS_P (cond));
1459 /* Note that we only need to compare against one of the operands
1462 Suppose that we are about to insert the assertion ASSERT_EXPR
1463 <x_4, x_4 != 0> and the defining statement for x_4 is x_4 =
1464 ASSERT_EXPR <x_3, x_3 != 0>.
1466 In this case, we don't really want to insert a new
1467 ASSERT_EXPR for x_4 because that would be redundant. We
1468 already know that x_4 is not 0. So, when comparing the
1469 conditionals 'x_3 != 0' and 'x_4 != 0', we don't want to
1470 compare x_3 and x_4, we just want to compare the predicate's
1471 code (!=) and the other operand (0). */
1472 if (TREE_OPERAND (cond, 0) == op)
1473 t1 = TREE_OPERAND (cond, 1);
1475 t1 = TREE_OPERAND (cond, 0);
1477 if (TREE_OPERAND (other_cond, 0) == other_op)
1478 t2 = TREE_OPERAND (other_cond, 1);
1480 t2 = TREE_OPERAND (other_cond, 0);
1482 return (t1 == t2 || operand_equal_p (t1, t2, 0));
1489 /* Traverse all the statements in block BB looking for used variables.
1490 Variables used in BB are added to bitmap FOUND. The algorithm
1491 works in three main parts:
1493 1- For every statement S in BB, all the variables used by S are
1494 added to bitmap FOUND.
1496 2- If statement S uses an operand N in a way that exposes a known
1497 value range for N, then if N was not already generated by an
1498 ASSERT_EXPR, create a new ASSERT_EXPR for N. For instance, if N
1499 is a pointer and the statement dereferences it, we can assume
1502 3- COND_EXPRs are a special case of #2. We can derive range
1503 information from the predicate but need to insert different
1504 ASSERT_EXPRs for each of the sub-graphs rooted at the
1505 conditional block. If the last statement of BB is a conditional
1506 expression of the form 'X op Y', then
1508 a) Remove X and Y from the set FOUND.
1510 b) If the conditional dominates its THEN_CLAUSE sub-graph,
1511 recurse into it. On return, if X and/or Y are marked in
1512 FOUND, then an ASSERT_EXPR is added for the corresponding
1515 c) Repeat step (b) on the ELSE_CLAUSE.
1517 d) Mark X and Y in FOUND.
1519 4- If BB does not end in a conditional expression, then we recurse
1520 into BB's dominator children.
1522 At the end of the recursive traversal, ASSERT_EXPRs will have been
1523 added to the edges of COND_EXPR blocks that have sub-graphs using
1524 one or both predicate operands. For instance,
1531 In this case, an assertion on the THEN clause is useful to
1532 determine that 'a' is always 9 on that edge. However, an assertion
1533 on the ELSE clause would be unnecessary.
1535 On exit from this function, all the names created by the newly
1536 inserted ASSERT_EXPRs need to be added to the SSA web by rewriting
1537 the SSA names that they replace.
1539 TODO. Handle SWITCH_EXPR. */
1542 maybe_add_assert_expr (basic_block bb)
1544 block_stmt_iterator si;
1549 /* Step 1. Mark all the SSA names used in BB in bitmap FOUND. */
1552 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1557 stmt = bsi_stmt (si);
1559 /* Mark all the SSA names used by STMT in bitmap FOUND. If STMT
1560 is inside the sub-graph of a conditional block, when we
1561 return from this recursive walk, our parent will use the
1562 FOUND bitset to determine if one of the operands it was
1563 looking for was present in the sub-graph. */
1564 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
1568 /* If OP is used only once, namely in this STMT, don't
1569 bother inserting an ASSERT_EXPR for it. Such an
1570 ASSERT_EXPR would do nothing but increase compile time.
1571 Experiments show that with this simple check, we can save
1572 more than 20% of ASSERT_EXPRs. */
1573 if (has_single_use (op))
1576 SET_BIT (found, SSA_NAME_VERSION (op));
1578 cond = infer_value_range (stmt, op);
1582 /* Step 2. If OP is used in such a way that we can infer a
1583 value range for it, create a new ASSERT_EXPR for OP
1584 (unless OP already has an ASSERT_EXPR). */
1585 gcc_assert (!is_ctrl_stmt (stmt));
1587 if (has_assert_expr (op, cond))
1590 if (!stmt_ends_bb_p (stmt))
1592 /* If STMT does not end the block, we can insert the new
1593 assertion right after it. */
1594 tree t = build_assert_expr_for (cond, op);
1595 bsi_insert_after (&si, t, BSI_NEW_STMT);
1600 /* STMT must be the last statement in BB. We can only
1601 insert new assertions on the non-abnormal edge out of
1602 BB. Note that since STMT is not control flow, there
1603 may only be one non-abnormal edge out of BB. */
1607 FOR_EACH_EDGE (e, ei, bb->succs)
1608 if (!(e->flags & EDGE_ABNORMAL))
1610 tree t = build_assert_expr_for (cond, op);
1611 bsi_insert_on_edge (e, t);
1618 /* Remember the last statement of the block. */
1622 /* Step 3. If BB's last statement is a conditional expression
1623 involving integer operands, recurse into each of the sub-graphs
1624 rooted at BB to determine if we need to add ASSERT_EXPRs.
1625 Notice that we only care about the first operand of the
1626 conditional. Adding assertions for both operands may actually
1627 hinder VRP. FIXME, add example. */
1629 && TREE_CODE (last) == COND_EXPR
1630 && !fp_predicate (COND_EXPR_COND (last))
1631 && NUM_USES (uses = STMT_USE_OPS (last)) > 0)
1638 cond = COND_EXPR_COND (last);
1640 op = USE_OP (uses, 0);
1642 /* Do not attempt to infer anything in names that flow through
1644 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1647 /* Remove the COND_EXPR operand from the FOUND bitmap.
1648 Otherwise, when we finish traversing each of the sub-graphs,
1649 we won't know whether the variables were found in the
1650 sub-graphs or if they had been found in a block upstream from
1652 RESET_BIT (found, SSA_NAME_VERSION (op));
1654 /* Look for uses of the operands in each of the sub-graphs
1655 rooted at BB. We need to check each of the outgoing edges
1656 separately, so that we know what kind of ASSERT_EXPR to
1658 FOR_EACH_EDGE (e, ei, bb->succs)
1660 /* If BB strictly dominates the sub-graph at E->DEST,
1663 && dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1664 added |= maybe_add_assert_expr (e->dest);
1666 /* Once we traversed the sub-graph, check if any block inside
1667 used either of the predicate's operands. If so, add the
1668 appropriate ASSERT_EXPR. */
1669 if (TEST_BIT (found, SSA_NAME_VERSION (op)))
1671 /* We found a use of OP in the sub-graph rooted at
1672 E->DEST. Add an ASSERT_EXPR according to whether
1673 E goes to THEN_CLAUSE or ELSE_CLAUSE. */
1676 if (e->flags & EDGE_TRUE_VALUE)
1677 c = unshare_expr (cond);
1678 else if (e->flags & EDGE_FALSE_VALUE)
1679 c = invert_truthvalue (cond);
1683 t = build_assert_expr_for (c, op);
1684 bsi_insert_on_edge (e, t);
1689 /* Finally, mark all the COND_EXPR operands as found. */
1690 SET_BIT (found, SSA_NAME_VERSION (op));
1692 /* Recurse into the dominator children of BB that are not BB's
1693 immediate successors. Note that we have already visited BB's
1694 other dominator children above. */
1695 for (son = first_dom_son (CDI_DOMINATORS, bb);
1697 son = next_dom_son (CDI_DOMINATORS, son))
1699 if (find_edge (bb, son) == NULL)
1700 added |= maybe_add_assert_expr (son);
1705 /* Step 4. Recurse into the dominator children of BB. */
1708 for (son = first_dom_son (CDI_DOMINATORS, bb);
1710 son = next_dom_son (CDI_DOMINATORS, son))
1711 added |= maybe_add_assert_expr (son);
1718 /* Traverse the flowgraph looking for conditional jumps to insert range
1719 expressions. These range expressions are meant to provide information
1720 to optimizations that need to reason in terms of value ranges. They
1721 will not be expanded into RTL. For instance, given:
1730 this pass will transform the code into:
1736 x = ASSERT_EXPR <x, x < y>
1741 y = ASSERT_EXPR <y, x <= y>
1745 The idea is that once copy and constant propagation have run, other
1746 optimizations will be able to determine what ranges of values can 'x'
1747 take in different paths of the code, simply by checking the reaching
1748 definition of 'x'. */
1751 insert_range_assertions (void)
1757 found = sbitmap_alloc (num_ssa_names);
1758 sbitmap_zero (found);
1760 calculate_dominance_info (CDI_DOMINATORS);
1762 update_ssa_p = false;
1763 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1764 if (maybe_add_assert_expr (e->dest))
1765 update_ssa_p = true;
1769 bsi_commit_edge_inserts ();
1770 update_ssa (TODO_update_ssa_no_phi);
1773 if (dump_file && (dump_flags & TDF_DETAILS))
1775 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
1776 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1779 sbitmap_free (found);
1783 /* Convert range assertion expressions into copies. FIXME, explain why. */
1786 remove_range_assertions (void)
1789 block_stmt_iterator si;
1792 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1794 tree stmt = bsi_stmt (si);
1796 if (TREE_CODE (stmt) == MODIFY_EXPR
1797 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1799 tree rhs = TREE_OPERAND (stmt, 1);
1800 tree cond = fold (ASSERT_EXPR_COND (rhs));
1801 gcc_assert (cond != boolean_false_node);
1802 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
1809 /* Return true if STMT is interesting for VRP. */
1812 stmt_interesting_for_vrp (tree stmt)
1814 if (TREE_CODE (stmt) == PHI_NODE
1815 && is_gimple_reg (PHI_RESULT (stmt))
1816 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
1817 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
1819 else if (TREE_CODE (stmt) == MODIFY_EXPR)
1821 tree lhs = TREE_OPERAND (stmt, 0);
1822 stmt_ann_t ann = stmt_ann (stmt);
1824 if (TREE_CODE (lhs) == SSA_NAME
1825 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1826 || POINTER_TYPE_P (TREE_TYPE (lhs)))
1827 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
1828 && NUM_VUSES (VUSE_OPS (ann)) == 0
1829 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
1832 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1839 /* Initialize local data structures for VRP. Return true if VRP
1840 is worth running (i.e. if we found any statements that could
1841 benefit from range information). */
1844 vrp_initialize (void)
1849 /* If we don't find any ASSERT_EXPRs in the code, there's no point
1855 block_stmt_iterator si;
1858 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1860 if (!stmt_interesting_for_vrp (phi))
1862 tree lhs = PHI_RESULT (phi);
1863 set_value_range_to_varying (get_value_range (lhs));
1864 DONT_SIMULATE_AGAIN (phi) = true;
1867 DONT_SIMULATE_AGAIN (phi) = false;
1870 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1872 tree stmt = bsi_stmt (si);
1874 if (!stmt_interesting_for_vrp (stmt))
1878 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
1879 set_value_range_to_varying (get_value_range (def));
1880 DONT_SIMULATE_AGAIN (stmt) = true;
1884 if (TREE_CODE (stmt) == MODIFY_EXPR
1885 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1888 DONT_SIMULATE_AGAIN (stmt) = false;
1897 /* Visit assignment STMT. If it produces an interesting range, record
1898 the SSA name in *OUTPUT_P. */
1900 static enum ssa_prop_result
1901 vrp_visit_assignment (tree stmt, tree *output_p)
1906 lhs = TREE_OPERAND (stmt, 0);
1907 rhs = TREE_OPERAND (stmt, 1);
1909 /* We only keep track of ranges in integral and pointer types. */
1910 if (TREE_CODE (lhs) == SSA_NAME
1911 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1912 || POINTER_TYPE_P (TREE_TYPE (lhs))))
1914 value_range *vr, new_vr;
1917 vr = get_value_range (lhs);
1918 extract_range_from_expr (&new_vr, rhs);
1920 /* If STMT is inside a loop, we may be able to know something
1921 else about the range of LHS by examining scalar evolution
1923 if (cfg_loops && (l = loop_containing_stmt (stmt)))
1924 adjust_range_with_scev (&new_vr, l, lhs);
1926 if (update_value_range (vr, new_vr.type, new_vr.min, new_vr.max))
1930 if (dump_file && (dump_flags & TDF_DETAILS))
1932 fprintf (dump_file, "Found new range ");
1933 dump_value_range (dump_file, &new_vr);
1934 fprintf (dump_file, " for ");
1935 print_generic_expr (dump_file, lhs, 0);
1936 fprintf (dump_file, "\n\n");
1939 if (new_vr.type == VR_VARYING)
1940 return SSA_PROP_VARYING;
1942 return SSA_PROP_INTERESTING;
1945 return SSA_PROP_NOT_INTERESTING;
1948 /* Every other statements produces no useful ranges. */
1949 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1950 set_value_range_to_varying (get_value_range (def));
1952 return SSA_PROP_VARYING;
1956 /* Given a conditional predicate COND, try to determine if COND yields
1957 true or false based on the value ranges of its operands. */
1960 vrp_evaluate_conditional (tree cond)
1962 gcc_assert (TREE_CODE (cond) == SSA_NAME
1963 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
1965 if (TREE_CODE (cond) == SSA_NAME)
1967 /* For SSA names, only return a truth value if the range is
1968 known and contains exactly one value. */
1969 value_range *vr = SSA_NAME_VALUE_RANGE (cond);
1970 if (vr && vr->type == VR_RANGE && vr->min == vr->max)
1975 /* For comparisons, evaluate each operand and compare their
1978 value_range *vr0, *vr1;
1980 op0 = TREE_OPERAND (cond, 0);
1981 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
1983 op1 = TREE_OPERAND (cond, 1);
1984 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
1987 return compare_ranges (TREE_CODE (cond), vr0, vr1);
1988 else if (vr0 && vr1 == NULL)
1989 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
1990 else if (vr0 == NULL && vr1)
1991 return compare_range_with_value (opposite_comparison (TREE_CODE (cond)),
1995 /* Anything else cannot be computed statically. */
2000 /* Visit conditional statement STMT. If we can determine which edge
2001 will be taken out of STMT's basic block, record it in
2002 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
2003 SSA_PROP_VARYING. */
2005 static enum ssa_prop_result
2006 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
2010 *taken_edge_p = NULL;
2012 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
2013 add ASSERT_EXPRs for them. */
2014 if (TREE_CODE (stmt) == SWITCH_EXPR)
2015 return SSA_PROP_VARYING;
2017 cond = COND_EXPR_COND (stmt);
2019 if (dump_file && (dump_flags & TDF_DETAILS))
2024 fprintf (dump_file, "\nVisiting conditional with predicate: ");
2025 print_generic_expr (dump_file, cond, 0);
2026 fprintf (dump_file, "\nWith known ranges\n");
2028 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
2030 fprintf (dump_file, "\t");
2031 print_generic_expr (dump_file, use, 0);
2032 fprintf (dump_file, ": ");
2033 dump_value_range (dump_file, SSA_NAME_VALUE_RANGE (use));
2036 fprintf (dump_file, "\n");
2039 /* Compute the value of the predicate COND by checking the known
2040 ranges of each of its operands. */
2041 val = vrp_evaluate_conditional (cond);
2043 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
2045 if (dump_file && (dump_flags & TDF_DETAILS))
2047 fprintf (dump_file, "\nPredicate evaluates to: ");
2048 if (val == NULL_TREE)
2049 fprintf (dump_file, "DON'T KNOW\n");
2051 print_generic_stmt (dump_file, val, 0);
2054 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
2058 /* Evaluate statement STMT. If the statement produces a useful range,
2059 return SSA_PROP_INTERESTING and record the SSA name with the
2060 interesting range into *OUTPUT_P.
2062 If STMT is a conditional branch and we can determine its truth
2063 value, the taken edge is recorded in *TAKEN_EDGE_P.
2065 If STMT produces a varying value, return SSA_PROP_VARYING. */
2067 static enum ssa_prop_result
2068 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
2074 if (dump_file && (dump_flags & TDF_DETAILS))
2076 fprintf (dump_file, "\nVisiting statement:\n");
2077 print_generic_stmt (dump_file, stmt, dump_flags);
2078 fprintf (dump_file, "\n");
2081 ann = stmt_ann (stmt);
2082 if (TREE_CODE (stmt) == MODIFY_EXPR
2083 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
2084 && NUM_VUSES (VUSE_OPS (ann)) == 0
2085 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
2086 return vrp_visit_assignment (stmt, output_p);
2087 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
2088 return vrp_visit_cond_stmt (stmt, taken_edge_p);
2090 /* All other statements produce nothing of interest for VRP, so mark
2091 their outputs varying and prevent further simulation. */
2092 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
2093 set_value_range_to_varying (get_value_range (def));
2095 return SSA_PROP_VARYING;
2099 /* Meet operation for value ranges. Given two value ranges VR0 and
2100 VR1, store in VR0 the result of meeting VR0 and VR1.
2102 The meeting rules are as follows:
2104 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
2106 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
2107 union of VR0 and VR1. */
2110 vrp_meet (value_range *vr0, value_range *vr1)
2112 if (vr0->type == VR_UNDEFINED)
2118 if (vr1->type == VR_UNDEFINED)
2120 /* Nothing to do. VR0 already has the resulting range. */
2124 if (vr0->type == VR_VARYING)
2126 /* Nothing to do. VR0 already has the resulting range. */
2130 if (vr1->type == VR_VARYING)
2136 /* If either is a symbolic range, drop to VARYING. */
2137 if (symbolic_range_p (vr0) || symbolic_range_p (vr1))
2139 set_value_range_to_varying (vr0);
2143 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
2145 /* If VR0 and VR1 have a non-empty intersection, compute the
2146 union of both ranges. */
2147 if (value_ranges_intersect_p (vr0, vr1))
2154 /* The lower limit of the new range is the minimum of the
2156 if (compare_values (vr0->min, vr1->min) == 1)
2159 /* The upper limit of the new range is the maximum of the
2161 if (compare_values (vr0->max, vr1->max) == -1)
2164 set_value_range (vr0, vr0->type, min, max);
2168 /* The two ranges don't intersect, set the result to VR_VARYING. */
2169 set_value_range_to_varying (vr0);
2172 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
2174 /* Two anti-ranges meet only if they are both identical. */
2175 if (compare_values (vr0->min, vr1->min) == 0
2176 && compare_values (vr0->max, vr1->max) == 0
2177 && compare_values (vr0->min, vr0->max) == 0)
2178 /* Nothing to do. */ ;
2180 set_value_range_to_varying (vr0);
2182 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
2184 /* A range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] meet
2185 only if the ranges have an empty intersection. The result of
2186 the meet operation is the anti-range. */
2187 if (!value_ranges_intersect_p (vr0, vr1))
2189 if (vr1->type == VR_ANTI_RANGE)
2193 set_value_range_to_varying (vr0);
2200 /* Visit all arguments for PHI node PHI that flow through executable
2201 edges. If a valid value range can be derived from all the incoming
2202 value ranges, set a new range for the LHS of PHI. */
2204 static enum ssa_prop_result
2205 vrp_visit_phi_node (tree phi)
2208 tree lhs = PHI_RESULT (phi);
2209 value_range *lhs_vr = get_value_range (lhs);
2210 value_range vr_result = *lhs_vr;
2212 if (dump_file && (dump_flags & TDF_DETAILS))
2214 fprintf (dump_file, "\nVisiting PHI node: ");
2215 print_generic_expr (dump_file, phi, dump_flags);
2218 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2220 edge e = PHI_ARG_EDGE (phi, i);
2222 if (dump_file && (dump_flags & TDF_DETAILS))
2225 "\n Argument #%d (%d -> %d %sexecutable)\n",
2226 i, e->src->index, e->dest->index,
2227 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
2230 if (e->flags & EDGE_EXECUTABLE)
2232 tree arg = PHI_ARG_DEF (phi, i);
2235 if (TREE_CODE (arg) == SSA_NAME)
2236 vr_arg = *(get_value_range (arg));
2239 vr_arg.type = VR_RANGE;
2244 if (dump_file && (dump_flags & TDF_DETAILS))
2246 fprintf (dump_file, "\t");
2247 print_generic_expr (dump_file, arg, dump_flags);
2248 fprintf (dump_file, "\n\tValue: ");
2249 dump_value_range (dump_file, &vr_arg);
2250 fprintf (dump_file, "\n");
2253 vrp_meet (&vr_result, &vr_arg);
2255 if (vr_result.type == VR_VARYING)
2260 if (vr_result.type == VR_VARYING)
2262 set_value_range_to_varying (lhs_vr);
2263 return SSA_PROP_VARYING;
2266 /* To prevent infinite iterations in the algorithm, derive ranges
2267 when the new value is slightly bigger or smaller than the
2269 if (lhs_vr->type == VR_RANGE)
2271 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
2273 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
2274 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
2276 /* If the new minimum is smaller or larger than the previous
2277 one, go all the way to -INF. In the first case, to avoid
2278 iterating millions of times to reach -INF, and in the
2279 other case to avoid infinite bouncing between different
2281 if (cmp_min > 0 || cmp_min < 0)
2282 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
2284 /* Similarly, if the new maximum is smaller or larger than
2285 the previous one, go all the way to +INF. */
2286 if (cmp_max < 0 || cmp_max > 0)
2287 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
2289 /* If we ended up with a (-INF, +INF) range, set it to
2291 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
2292 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
2294 set_value_range_to_varying (lhs_vr);
2295 return SSA_PROP_VARYING;
2300 /* If the new range is different than the previous value, keep
2302 if (update_value_range (lhs_vr, vr_result.type, vr_result.min, vr_result.max))
2303 return SSA_PROP_INTERESTING;
2305 /* Nothing changed, don't add outgoing edges. */
2306 return SSA_PROP_NOT_INTERESTING;
2310 /* Traverse all the blocks folding conditionals with known ranges. */
2316 int num_pred_folded = 0;
2320 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
2321 dump_all_value_ranges (dump_file);
2322 fprintf (dump_file, "\n");
2327 tree last = last_stmt (bb);
2328 if (last && TREE_CODE (last) == COND_EXPR)
2330 tree val = vrp_evaluate_conditional (COND_EXPR_COND (last));
2335 fprintf (dump_file, "Folding predicate ");
2336 print_generic_expr (dump_file, COND_EXPR_COND (last), 0);
2337 fprintf (dump_file, " to ");
2338 print_generic_expr (dump_file, val, 0);
2339 fprintf (dump_file, "\n");
2343 COND_EXPR_COND (last) = val;
2349 if (dump_file && (dump_flags & TDF_STATS))
2350 fprintf (dump_file, "\nNumber of predicates folded: %d\n\n",
2355 /* Main entry point to VRP (Value Range Propagation). This pass is
2356 loosely based on J. R. C. Patterson, ``Accurate Static Branch
2357 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
2358 Programming Language Design and Implementation, pp. 67-78, 1995.
2359 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
2361 This is essentially an SSA-CCP pass modified to deal with ranges
2362 instead of constants.
2364 TODO, the main difference between this pass and Patterson's is that
2365 we do not propagate edge probabilities. We only compute whether
2366 edges can be taken or not. That is, instead of having a spectrum
2367 of jump probabilities between 0 and 1, we only deal with 0, 1 and
2368 DON'T KNOW. In the future, it may be worthwhile to propagate
2369 probabilities to aid branch prediction. */
2374 insert_range_assertions ();
2376 cfg_loops = loop_optimizer_init (NULL);
2378 scev_initialize (cfg_loops);
2380 if (vrp_initialize ())
2382 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
2389 loop_optimizer_finalize (cfg_loops, NULL);
2390 current_loops = NULL;
2393 remove_range_assertions ();
2399 return flag_tree_vrp != 0;
2402 struct tree_opt_pass pass_vrp =
2405 gate_vrp, /* gate */
2406 execute_vrp, /* execute */
2409 0, /* static_pass_number */
2410 TV_TREE_VRP, /* tv_id */
2411 PROP_ssa | PROP_alias, /* properties_required */
2412 0, /* properties_provided */
2413 0, /* properties_destroyed */
2414 0, /* todo_flags_start */
2419 | TODO_update_ssa, /* todo_flags_finish */