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 /* Compare two values VAL1 and VAL2. Return
274 -2 if VAL1 and VAL2 cannot be compared at compile-time,
277 +1 if VAL1 > VAL2, and
280 This is similar to tree_int_cst_compare but supports pointer values
281 and values that cannot be compared at compile time. */
284 compare_values (tree val1, tree val2)
289 /* Do some limited symbolic comparisons. */
290 /* FIXME: The second check of POINTER_TYPE_P should not be necessary
291 because we should be comparing values of the same type here, but
292 for whatever reason, the front end throws us a type mismatched
293 comparison. For now, work around the problem by checking both
294 types. See PR 21021 and PR 21024. */
295 if (!POINTER_TYPE_P (TREE_TYPE (val1))
296 && !POINTER_TYPE_P (TREE_TYPE (val2)))
298 /* We can determine some comparisons against +INF and -INF even
299 if the other value is an expression. */
300 if (val1 == TYPE_MAX_VALUE (TREE_TYPE (val1))
301 && TREE_CODE (val2) == MINUS_EXPR)
303 /* +INF > NAME - CST. */
306 else if (val1 == TYPE_MIN_VALUE (TREE_TYPE (val1))
307 && TREE_CODE (val2) == PLUS_EXPR)
309 /* -INF < NAME + CST. */
312 else if (TREE_CODE (val1) == MINUS_EXPR
313 && val2 == TYPE_MAX_VALUE (TREE_TYPE (val2)))
315 /* NAME - CST < +INF. */
318 else if (TREE_CODE (val1) == PLUS_EXPR
319 && val2 == TYPE_MIN_VALUE (TREE_TYPE (val2)))
321 /* NAME + CST > -INF. */
326 if ((TREE_CODE (val1) == SSA_NAME
327 || TREE_CODE (val1) == PLUS_EXPR
328 || TREE_CODE (val1) == MINUS_EXPR)
329 && (TREE_CODE (val2) == SSA_NAME
330 || TREE_CODE (val2) == PLUS_EXPR
331 || TREE_CODE (val2) == MINUS_EXPR))
335 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
336 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
337 same name, return -2. */
338 if (TREE_CODE (val1) == SSA_NAME)
345 n1 = TREE_OPERAND (val1, 0);
346 c1 = TREE_OPERAND (val1, 1);
349 if (TREE_CODE (val2) == SSA_NAME)
356 n2 = TREE_OPERAND (val2, 0);
357 c2 = TREE_OPERAND (val2, 1);
360 /* Both values must use the same name. */
364 if (TREE_CODE (val1) == SSA_NAME)
366 if (TREE_CODE (val2) == SSA_NAME)
369 else if (TREE_CODE (val2) == PLUS_EXPR)
370 /* NAME < NAME + CST */
372 else if (TREE_CODE (val2) == MINUS_EXPR)
373 /* NAME > NAME - CST */
376 else if (TREE_CODE (val1) == PLUS_EXPR)
378 if (TREE_CODE (val2) == SSA_NAME)
379 /* NAME + CST > NAME */
381 else if (TREE_CODE (val2) == PLUS_EXPR)
382 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
383 return compare_values (c1, c2);
384 else if (TREE_CODE (val2) == MINUS_EXPR)
385 /* NAME + CST1 > NAME - CST2 */
388 else if (TREE_CODE (val1) == MINUS_EXPR)
390 if (TREE_CODE (val2) == SSA_NAME)
391 /* NAME - CST < NAME */
393 else if (TREE_CODE (val2) == PLUS_EXPR)
394 /* NAME - CST1 < NAME + CST2 */
396 else if (TREE_CODE (val2) == MINUS_EXPR)
397 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
398 C1 and C2 are swapped in the call to compare_values. */
399 return compare_values (c2, c1);
405 /* We cannot compare non-constants. */
406 if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
409 /* FIXME: The second check of POINTER_TYPE_P should not be necessary
410 because we should be comparing values of the same type here, but
411 for whatever reason, the front end throws us a type mismatched
412 comparison. For now, work around the problem by checking both
413 types. See PR 21021 and PR 21024. */
414 if (!POINTER_TYPE_P (TREE_TYPE (val1))
415 && !POINTER_TYPE_P (TREE_TYPE (val2)))
416 return tree_int_cst_compare (val1, val2);
421 /* First see if VAL1 and VAL2 are not the same. */
422 if (val1 == val2 || operand_equal_p (val1, val2, 0))
425 /* If VAL1 is a lower address than VAL2, return -1. */
426 t = fold (build2 (LT_EXPR, TREE_TYPE (val1), val1, val2));
427 if (t == boolean_true_node)
430 /* If VAL1 is a higher address than VAL2, return +1. */
431 t = fold (build2 (GT_EXPR, TREE_TYPE (val1), val1, val2));
432 if (t == boolean_true_node)
435 /* If VAL1 is different than VAL2, return +2. */
436 t = fold (build2 (NE_EXPR, TREE_TYPE (val1), val1, val2));
437 if (t == boolean_true_node)
445 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
446 0 if VAL is not inside VR,
447 -2 if we cannot tell either way. */
450 value_inside_range (tree val, value_range *vr)
454 cmp1 = compare_values (val, vr->min);
455 if (cmp1 == -2 || cmp1 == 2)
458 cmp2 = compare_values (val, vr->max);
459 if (cmp2 == -2 || cmp2 == 2)
462 return (cmp1 == 0 || cmp1 == 1) && (cmp2 == -1 || cmp2 == 0);
466 /* Return true if value ranges VR0 and VR1 have a non-empty
470 value_ranges_intersect_p (value_range *vr0, value_range *vr1)
472 return (value_inside_range (vr1->min, vr0) == 1
473 || value_inside_range (vr1->max, vr0) == 1
474 || value_inside_range (vr0->min, vr1) == 1
475 || value_inside_range (vr0->max, vr1) == 1);
479 /* Extract value range information from an ASSERT_EXPR EXPR and store
483 extract_range_from_assert (value_range *vr_p, tree expr)
485 tree var, cond, limit, type;
488 var = ASSERT_EXPR_VAR (expr);
489 cond = ASSERT_EXPR_COND (expr);
491 gcc_assert (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
493 /* Find VAR in the ASSERT_EXPR conditional. */
494 limit = get_opposite_operand (cond, var);
495 type = TREE_TYPE (limit);
497 gcc_assert (limit != var);
499 /* For pointer arithmetic, we only keep track of anti-ranges
500 (NE_EXPR). Notice that we don't need to handle EQ_EXPR in these
501 cases because assertions with equalities are never generated.
502 The assert pass generates straight assignments in those cases. */
503 if (POINTER_TYPE_P (type) && TREE_CODE (cond) != NE_EXPR)
505 set_value_range (vr_p, VR_VARYING, NULL_TREE, NULL_TREE);
509 if (TREE_CODE (cond) == NE_EXPR)
510 set_value_range (vr_p, VR_ANTI_RANGE, limit, limit);
511 else if (TREE_CODE (cond) == LE_EXPR)
512 set_value_range (vr_p, VR_RANGE, TYPE_MIN_VALUE (type), limit);
513 else if (TREE_CODE (cond) == LT_EXPR)
515 tree one = build_int_cst (type, 1);
516 set_value_range (vr_p, VR_RANGE, TYPE_MIN_VALUE (type),
517 fold (build (MINUS_EXPR, type, limit, one)));
519 else if (TREE_CODE (cond) == GE_EXPR)
520 set_value_range (vr_p, VR_RANGE, limit, TYPE_MAX_VALUE (type));
521 else if (TREE_CODE (cond) == GT_EXPR)
523 tree one = build_int_cst (type, 1);
524 set_value_range (vr_p, VR_RANGE,
525 fold (build (PLUS_EXPR, type, limit, one)),
526 TYPE_MAX_VALUE (type));
531 /* If VAR already has a known range and the two ranges have a
532 non-empty intersection, we can refine the resulting range.
533 Since the assert expression creates an equivalency and at the
534 same time it asserts a predicate, we can take the intersection of
535 the two ranges to get better precision. */
536 var_vr = get_value_range (var);
537 if (var_vr->type == VR_RANGE
538 && vr_p->type == VR_RANGE
539 && value_ranges_intersect_p (var_vr, vr_p))
543 /* Use the larger of the two minimums. */
544 if (compare_values (vr_p->min, var_vr->min) == -1)
549 /* Use the smaller of the two maximums. */
550 if (compare_values (vr_p->max, var_vr->max) == 1)
555 set_value_range (vr_p, vr_p->type, min, max);
560 /* Extract range information from SSA name VAR and store it in VR. If
561 VAR has an interesting range, use it. Otherwise, create the
562 range [VAR, VAR] and return it. This is useful in situations where
563 we may have conditionals testing values of VARYING names. For
570 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
574 extract_range_from_ssa_name (value_range *vr, tree var)
576 value_range *var_vr = get_value_range (var);
578 if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
581 set_value_range (vr, VR_RANGE, var, var);
585 /* Extract range information from a binary expression EXPR based on
586 the ranges of each of its operands and the expression code. */
589 extract_range_from_binary_expr (value_range *vr, tree expr)
591 enum tree_code code = TREE_CODE (expr);
592 tree op0, op1, min, max;
593 value_range vr0, vr1;
596 /* Not all binary expressions can be applied to ranges in a
597 meaningful way. Handle only arithmetic operations. */
598 if (code != PLUS_EXPR
599 && code != MINUS_EXPR
601 && code != TRUNC_DIV_EXPR
602 && code != FLOOR_DIV_EXPR
603 && code != CEIL_DIV_EXPR
604 && code != EXACT_DIV_EXPR
605 && code != ROUND_DIV_EXPR
609 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
613 /* Get value ranges for each operand. For constant operands, create
614 a new value range with the operand to simplify processing. */
615 op0 = TREE_OPERAND (expr, 0);
616 if (TREE_CODE (op0) == SSA_NAME)
617 vr0 = *(get_value_range (op0));
620 if (is_gimple_min_invariant (op0))
621 set_value_range (&vr0, VR_RANGE, op0, op0);
623 set_value_range (&vr0, VR_VARYING, NULL_TREE, NULL_TREE);
626 op1 = TREE_OPERAND (expr, 1);
627 if (TREE_CODE (op1) == SSA_NAME)
628 vr1 = *(get_value_range (op1));
631 if (is_gimple_min_invariant (op1))
632 set_value_range (&vr1, VR_RANGE, op1, op1);
634 set_value_range (&vr1, VR_VARYING, 0, 0);
637 /* If either range is UNDEFINED, so is the result. */
638 if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
640 set_value_range (vr, VR_UNDEFINED, NULL_TREE, NULL_TREE);
644 /* If either range is VARYING, so is the result. */
645 if (vr0.type == VR_VARYING || vr1.type == VR_VARYING)
647 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
651 /* If the ranges are of different types, the result is VARYING. */
652 if (vr0.type != vr1.type)
654 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
658 /* TODO. Refuse to do any symbolic range operations for now. */
659 if (symbolic_range_p (&vr0) || symbolic_range_p (&vr1))
661 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
665 /* Now evaluate the expression to determine the new range. */
666 if (POINTER_TYPE_P (TREE_TYPE (expr))
667 || POINTER_TYPE_P (TREE_TYPE (op0))
668 || POINTER_TYPE_P (TREE_TYPE (op1)))
670 /* For pointer types, we are really only interested in asserting
671 whether the expression evaluates to non-NULL. FIXME. We
672 used to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR),
673 but ivopts is generating expressions with pointer
674 multiplication in them. */
675 if (code == PLUS_EXPR)
677 /* Assume that pointers can never wrap around. FIXME, Is
679 tree zero = build_int_cst (TREE_TYPE (expr), 0);
680 set_value_range (vr, VR_ANTI_RANGE, zero, zero);
684 /* Subtracting from a pointer, may yield 0, so just drop the
685 resulting range to varying. */
686 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
692 /* For integer ranges, apply the operation to each end of the
693 range and see what we end up with. */
694 if (code == PLUS_EXPR
699 /* For operations that make the resulting range directly
700 proportional to the original ranges, apply the operation to
701 the same end of each range. */
702 min = int_const_binop (code, vr0.min, vr1.min, 0);
703 max = int_const_binop (code, vr0.max, vr1.max, 0);
707 /* For operations that make the resulting range inversely
708 proportional to the original ranges (-, /), apply the
709 operation to the opposite ends of each range. */
710 min = int_const_binop (code, vr0.min, vr1.max, 0);
711 max = int_const_binop (code, vr0.max, vr1.min, 0);
714 cmp = compare_values (min, max);
715 if (cmp == -2 || cmp == 1)
717 /* If the new range has its limits swapped around (MIN > MAX),
718 then the operation caused one of them to wrap around, mark
719 the new range VARYING. */
720 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
723 set_value_range (vr, vr0.type, min, max);
727 /* Extract range information from a unary expression EXPR based on
728 the range of its operand and the expression code. */
731 extract_range_from_unary_expr (value_range *vr, tree expr)
733 enum tree_code code = TREE_CODE (expr);
738 /* Get value ranges for the operand. For constant operands, create
739 a new value range with the operand to simplify processing. */
740 op0 = TREE_OPERAND (expr, 0);
741 if (TREE_CODE (op0) == SSA_NAME)
742 vr0 = *(get_value_range (op0));
745 if (is_gimple_min_invariant (op0))
746 set_value_range (&vr0, VR_RANGE, op0, op0);
748 set_value_range (&vr0, VR_VARYING, NULL_TREE, NULL_TREE);
751 /* If VR0 is UNDEFINED, so is the result. */
752 if (vr0.type == VR_UNDEFINED)
754 set_value_range (vr, VR_UNDEFINED, NULL_TREE, NULL_TREE);
758 /* If VR0 is VARYING, so is the result. */
759 if (vr0.type == VR_VARYING)
761 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
765 /* TODO. Refuse to do any symbolic range operations for now. */
766 if (symbolic_range_p (&vr0))
768 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
772 /* If the operand is neither a pointer nor an integral type, set the
773 range to VARYING. TODO, we may set the range to non-zero. */
774 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
775 && !POINTER_TYPE_P (TREE_TYPE (op0)))
777 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
781 /* If the expression involves pointers, we are only interested in
782 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
783 if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
785 if (range_is_nonnull (&vr0) || expr_computes_nonzero (expr))
786 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
787 else if (range_is_null (&vr0))
788 set_value_range_to_null (vr, TREE_TYPE (expr));
790 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
795 /* Handle unary expressions on integer ranges. */
796 if ((code == NOP_EXPR || code == CONVERT_EXPR)
797 && (TYPE_SIZE (TREE_TYPE (vr0.min)) != TYPE_SIZE (TREE_TYPE (expr))))
799 /* When converting types of different sizes, set the result to
800 VARYING. Things like sign extensions and precision loss may
801 change the range. For instance, if x_3 is of type 'long long
802 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
803 is impossible to know at compile time whether y_5 will be
805 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
809 /* Apply the operation to each end of the range and see what we end
811 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
812 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
814 cmp = compare_values (min, max);
815 if (cmp == -2 || cmp == 1)
817 /* If the new range has its limits swapped around (MIN > MAX),
818 then the operation caused one of them to wrap around, mark
819 the new range VARYING. */
820 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
823 set_value_range (vr, vr0.type, min, max);
827 /* Try to compute a useful range out of expression EXPR and store it
831 extract_range_from_expr (value_range *vr, tree expr)
833 enum tree_code code = TREE_CODE (expr);
835 if (code == ASSERT_EXPR)
836 extract_range_from_assert (vr, expr);
837 else if (code == SSA_NAME)
838 extract_range_from_ssa_name (vr, expr);
839 else if (TREE_CODE_CLASS (code) == tcc_binary)
840 extract_range_from_binary_expr (vr, expr);
841 else if (TREE_CODE_CLASS (code) == tcc_unary)
842 extract_range_from_unary_expr (vr, expr);
843 else if (expr_computes_nonzero (expr))
844 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
845 else if (TREE_CODE (expr) == INTEGER_CST)
846 set_value_range (vr, VR_RANGE, expr, expr);
848 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
852 /* Given a range VR, a loop L and a variable VAR, determine whether it
853 would be profitable to adjust VR using scalar evolution information
854 for VAR. If so, update VR with the new limits. */
857 adjust_range_with_scev (value_range *vr, struct loop *l, tree var)
859 tree init, step, chrec;
862 /* TODO. Don't adjust anti-ranges. An anti-range may provide
863 better opportunities than a regular range, but I'm not sure. */
864 if (vr->type == VR_ANTI_RANGE)
867 chrec = analyze_scalar_evolution (l, var);
868 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
871 init = CHREC_LEFT (chrec);
872 step = CHREC_RIGHT (chrec);
874 /* If STEP is symbolic, we can't know whether INIT will be the
875 minimum or maximum value in the range. */
876 if (!is_gimple_min_invariant (step))
879 /* FIXME. When dealing with unsigned types,
880 analyze_scalar_evolution sets STEP to very large unsigned values
881 when the evolution goes backwards. This confuses this analysis
882 because we think that INIT is the smallest value that the range
883 can take, instead of the largest. Ignore these chrecs for now. */
884 if (INTEGRAL_TYPE_P (TREE_TYPE (step)) && TYPE_UNSIGNED (TREE_TYPE (step)))
887 /* If STEP is negative, then INIT is the maximum value the range
888 will take. Otherwise, INIT is the minimum value. */
889 init_is_max = (tree_int_cst_sgn (step) < 0);
891 if (!POINTER_TYPE_P (TREE_TYPE (init))
892 && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
894 /* For VARYING or UNDEFINED ranges, just about anything we get
895 from scalar evolutions should be better. */
897 set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)), init);
899 set_value_range (vr, VR_RANGE, init, TYPE_MAX_VALUE (TREE_TYPE (init)));
901 else if (vr->type == VR_RANGE)
905 /* INIT is the maximum value. If INIT is lower than
906 VR->MAX, set VR->MAX to INIT. */
907 if (compare_values (init, vr->max) == -1)
908 set_value_range (vr, VR_RANGE, vr->min, init);
912 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
913 if (compare_values (init, vr->min) == 1)
914 set_value_range (vr, VR_RANGE, init, vr->max);
920 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
922 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for all the
923 values in the ranges.
925 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
927 - Return NULL_TREE if it is not always possible to determine the value of
931 compare_ranges (enum tree_code comp, value_range *vr0, value_range *vr1)
933 /* VARYING or UNDEFINED ranges cannot be compared. */
934 if (vr0->type == VR_VARYING
935 || vr0->type == VR_UNDEFINED
936 || vr1->type == VR_VARYING
937 || vr1->type == VR_UNDEFINED)
940 /* Anti-ranges need to be handled separately. */
941 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
943 /* If both are anti-ranges, then we cannot compute any
945 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
948 /* These comparisons are never statically computable. */
955 /* Equality can be computed only between a range and an
956 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
957 if (vr0->type == VR_RANGE)
959 /* To simplify processing, make VR0 the anti-range. */
960 value_range *tmp = vr0;
965 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
967 if (compare_values (vr0->min, vr1->min) == 0
968 && compare_values (vr0->max, vr1->max) == 0)
969 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
974 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
975 operands around and change the comparison code. */
976 if (comp == GT_EXPR || comp == GE_EXPR)
979 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
987 /* Equality may only be computed if both ranges represent
988 exactly one value. */
989 if (compare_values (vr0->min, vr0->max) == 0
990 && compare_values (vr1->min, vr1->max) == 0)
992 int cmp_min = compare_values (vr0->min, vr1->min);
993 int cmp_max = compare_values (vr0->max, vr1->max);
994 if (cmp_min == 0 && cmp_max == 0)
995 return boolean_true_node;
996 else if (cmp_min != -2 && cmp_max != -2)
997 return boolean_false_node;
1002 else if (comp == NE_EXPR)
1006 /* If VR0 is completely to the left or completely to the right
1007 of VR1, they are always different. Notice that we need to
1008 make sure that both comparisons yield similar results to
1009 avoid comparing values that cannot be compared at
1011 cmp1 = compare_values (vr0->max, vr1->min);
1012 cmp2 = compare_values (vr0->min, vr1->max);
1013 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
1014 return boolean_true_node;
1016 /* If VR0 and VR1 represent a single value and are identical,
1018 else if (compare_values (vr0->min, vr0->max) == 0
1019 && compare_values (vr1->min, vr1->max) == 0
1020 && compare_values (vr0->min, vr1->min) == 0
1021 && compare_values (vr0->max, vr1->max) == 0)
1022 return boolean_false_node;
1024 /* Otherwise, they may or may not be different. */
1028 else if (comp == LT_EXPR || comp == LE_EXPR)
1032 /* If VR0 is to the left of VR1, return true. */
1033 tst = compare_values (vr0->max, vr1->min);
1034 if ((comp == LT_EXPR && tst == -1)
1035 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1036 return boolean_true_node;
1038 /* If VR0 is to the right of VR1, return false. */
1039 tst = compare_values (vr0->min, vr1->max);
1040 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1041 || (comp == LE_EXPR && tst == 1))
1042 return boolean_false_node;
1044 /* Otherwise, we don't know. */
1052 /* Given a value range VR, a value VAL and a comparison code COMP, return
1053 BOOLEAN_TRUE_NODE if VR COMP VR1 always returns true for all the
1054 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1055 always returns false. Return NULL_TREE if it is not always
1056 possible to determine the value of the comparison. */
1059 compare_range_with_value (enum tree_code comp, value_range *vr, tree val)
1061 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1064 /* Anti-ranges need to be handled separately. */
1065 if (vr->type == VR_ANTI_RANGE)
1067 /* For anti-ranges, the only predicates that we can compute at
1068 compile time are equality and inequality. */
1075 /* ~[VAL, VAL] == VAL is always false. */
1076 if (compare_values (vr->min, val) == 0
1077 && compare_values (vr->max, val) == 0)
1078 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1083 if (comp == EQ_EXPR)
1085 /* EQ_EXPR may only be computed if VR represents exactly
1087 if (compare_values (vr->min, vr->max) == 0)
1089 int cmp = compare_values (vr->min, val);
1091 return boolean_true_node;
1092 else if (cmp == -1 || cmp == 1 || cmp == 2)
1093 return boolean_false_node;
1098 else if (comp == NE_EXPR)
1100 /* If VAL is not inside VR, then they are always different. */
1101 if (compare_values (vr->max, val) == -1
1102 || compare_values (vr->min, val) == 1)
1103 return boolean_true_node;
1105 /* If VR represents exactly one value equal to VAL, then return
1107 if (compare_values (vr->min, vr->max) == 0
1108 && compare_values (vr->min, val) == 0)
1109 return boolean_false_node;
1111 /* Otherwise, they may or may not be different. */
1114 else if (comp == LT_EXPR || comp == LE_EXPR)
1118 /* If VR is to the left of VAL, return true. */
1119 tst = compare_values (vr->max, val);
1120 if ((comp == LT_EXPR && tst == -1)
1121 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1122 return boolean_true_node;
1124 /* If VR is to the right of VAL, return false. */
1125 tst = compare_values (vr->min, val);
1126 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1127 || (comp == LE_EXPR && tst == 1))
1128 return boolean_false_node;
1130 /* Otherwise, we don't know. */
1133 else if (comp == GT_EXPR || comp == GE_EXPR)
1137 /* If VR is to the right of VAL, return true. */
1138 tst = compare_values (vr->min, val);
1139 if ((comp == GT_EXPR && tst == 1)
1140 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
1141 return boolean_true_node;
1143 /* If VR is to the left of VAL, return false. */
1144 tst = compare_values (vr->max, val);
1145 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
1146 || (comp == GE_EXPR && tst == -1))
1147 return boolean_false_node;
1149 /* Otherwise, we don't know. */
1157 /* Debugging dumps. */
1160 dump_value_range (FILE *file, value_range *vr)
1163 fprintf (file, "[]");
1164 else if (vr->type == VR_UNDEFINED)
1165 fprintf (file, "UNDEFINED");
1166 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
1168 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
1169 print_generic_expr (file, vr->min, 0);
1170 fprintf (file, ", ");
1171 print_generic_expr (file, vr->max, 0);
1172 fprintf (file, "]");
1174 else if (vr->type == VR_VARYING)
1175 fprintf (file, "VARYING");
1177 fprintf (file, "INVALID RANGE");
1181 /* Dump value range VR to stderr. */
1184 debug_value_range (value_range *vr)
1186 dump_value_range (stderr, vr);
1190 /* Dump value ranges of all SSA_NAMEs to FILE. */
1193 dump_all_value_ranges (FILE *file)
1197 for (i = 0; i < num_ssa_names; i++)
1199 tree var = ssa_name (i);
1200 if (var && SSA_NAME_VALUE_RANGE (var))
1202 print_generic_expr (file, var, 0);
1203 fprintf (file, ": ");
1204 dump_value_range (file, SSA_NAME_VALUE_RANGE (var));
1205 fprintf (file, "\n");
1209 fprintf (file, "\n");
1213 /* Dump all value ranges to stderr. */
1216 debug_all_value_ranges (void)
1218 dump_all_value_ranges (stderr);
1222 /*---------------------------------------------------------------------------
1223 Value Range Propagation
1224 ---------------------------------------------------------------------------*/
1226 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
1227 create a new SSA name N and return the assertion assignment
1228 'V = ASSERT_EXPR <V, V OP W>'. */
1231 build_assert_expr_for (tree cond, tree v)
1235 gcc_assert (TREE_CODE (v) == SSA_NAME);
1236 n = duplicate_ssa_name (v, NULL_TREE);
1238 if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison)
1240 /* Build N = ASSERT_EXPR <V, COND>. As a special case, if the
1241 conditional is an EQ_EXPR (V == Z), just build the assignment
1243 if (TREE_CODE (cond) == EQ_EXPR)
1245 tree other = get_opposite_operand (cond, v);
1246 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, other);
1249 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n,
1250 build (ASSERT_EXPR, TREE_TYPE (v), v, cond));
1252 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1254 /* Given !V, build the assignment N = false. */
1255 tree op0 = TREE_OPERAND (cond, 0);
1256 gcc_assert (op0 == v);
1257 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
1259 else if (TREE_CODE (cond) == SSA_NAME)
1261 /* Given V, build the assignment N = true. */
1262 gcc_assert (v == cond);
1263 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
1268 SSA_NAME_DEF_STMT (n) = assertion;
1270 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
1271 operand of the ASSERT_EXPR. Register the new name and the old one
1272 in the replacement table so that we can fix the SSA web after
1273 adding all the ASSERT_EXPRs. */
1274 register_new_name_mapping (n, v);
1280 /* Return false if EXPR is a predicate expression involving floating
1284 fp_predicate (tree expr)
1286 return TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison
1287 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)));
1291 /* Return an expression predicate that represents the range of values
1292 that can be taken by operand OP after STMT executes. */
1295 infer_value_range (tree stmt, tree op)
1297 /* Do not attempt to infer anything in names that flow through
1299 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1302 if (POINTER_TYPE_P (TREE_TYPE (op)))
1305 unsigned num_uses, num_derefs;
1307 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
1308 if (num_derefs > 0 && flag_delete_null_pointer_checks)
1310 /* We can only assume that a pointer dereference will yield
1311 non-NULL if -fdelete-null-pointer-checks is enabled. */
1312 tree null = build_int_cst (TREE_TYPE (op), 0);
1313 tree t = build (NE_EXPR, boolean_type_node, op, null);
1322 /* Return true if OP is the result of an ASSERT_EXPR that tests the
1323 same condition as COND. */
1326 has_assert_expr (tree op, tree cond)
1328 tree def_stmt = SSA_NAME_DEF_STMT (op);
1329 tree assert_expr, other_cond, other_op;
1331 /* If OP was not generated by an ASSERT_EXPR, return false. */
1332 if (TREE_CODE (def_stmt) != MODIFY_EXPR
1333 || TREE_CODE (TREE_OPERAND (def_stmt, 1)) != ASSERT_EXPR)
1336 assert_expr = TREE_OPERAND (def_stmt, 1);
1337 other_cond = ASSERT_EXPR_COND (assert_expr);
1338 other_op = ASSERT_EXPR_VAR (assert_expr);
1340 if (TREE_CODE (cond) == TREE_CODE (other_cond))
1344 /* If COND is not a comparison predicate, something is wrong. */
1345 gcc_assert (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
1347 /* Note that we only need to compare against one of the operands
1350 Suppose that we are about to insert the assertion ASSERT_EXPR
1351 <x_4, x_4 != 0> and the defining statement for x_4 is x_4 =
1352 ASSERT_EXPR <x_3, x_3 != 0>.
1354 In this case, we don't really want to insert a new
1355 ASSERT_EXPR for x_4 because that would be redundant. We
1356 already know that x_4 is not 0. So, when comparing the
1357 conditionals 'x_3 != 0' and 'x_4 != 0', we don't want to
1358 compare x_3 and x_4, we just want to compare the predicate's
1359 code (!=) and the other operand (0). */
1360 if (TREE_OPERAND (cond, 0) == op)
1361 t1 = TREE_OPERAND (cond, 1);
1363 t1 = TREE_OPERAND (cond, 0);
1365 if (TREE_OPERAND (other_cond, 0) == other_op)
1366 t2 = TREE_OPERAND (other_cond, 1);
1368 t2 = TREE_OPERAND (other_cond, 0);
1370 return (t1 == t2 || operand_equal_p (t1, t2, 0));
1377 /* Traverse all the statements in block BB looking for used variables.
1378 Variables used in BB are added to bitmap FOUND. The algorithm
1379 works in three main parts:
1381 1- For every statement S in BB, all the variables used by S are
1382 added to bitmap FOUND.
1384 2- If statement S uses an operand N in a way that exposes a known
1385 value range for N, then if N was not already generated by an
1386 ASSERT_EXPR, create a new ASSERT_EXPR for N. For instance, if N
1387 is a pointer and the statement dereferences it, we can assume
1390 3- COND_EXPRs are a special case of #2. We can derive range
1391 information from the predicate but need to insert different
1392 ASSERT_EXPRs for each of the sub-graphs rooted at the
1393 conditional block. If the last statement of BB is a conditional
1394 expression of the form 'X op Y', then
1396 a) Remove X and Y from the set FOUND.
1398 b) If the conditional dominates its THEN_CLAUSE sub-graph,
1399 recurse into it. On return, if X and/or Y are marked in
1400 FOUND, then an ASSERT_EXPR is added for the corresponding
1403 c) Repeat step (b) on the ELSE_CLAUSE.
1405 d) Mark X and Y in FOUND.
1407 4- If BB does not end in a conditional expression, then we recurse
1408 into BB's dominator children.
1410 At the end of the recursive traversal, ASSERT_EXPRs will have been
1411 added to the edges of COND_EXPR blocks that have sub-graphs using
1412 one or both predicate operands. For instance,
1419 In this case, an assertion on the THEN clause is useful to
1420 determine that 'a' is always 9 on that edge. However, an assertion
1421 on the ELSE clause would be unnecessary.
1423 On exit from this function, all the names created by the newly
1424 inserted ASSERT_EXPRs need to be added to the SSA web by rewriting
1425 the SSA names that they replace.
1427 TODO. Handle SWITCH_EXPR. */
1430 maybe_add_assert_expr (basic_block bb)
1432 block_stmt_iterator si;
1437 /* Step 1. Mark all the SSA names used in BB in bitmap FOUND. */
1440 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1445 stmt = bsi_stmt (si);
1447 /* Mark all the SSA names used by STMT in bitmap FOUND. If STMT
1448 is inside the sub-graph of a conditional block, when we
1449 return from this recursive walk, our parent will use the
1450 FOUND bitset to determine if one of the operands it was
1451 looking for was present in the sub-graph. */
1452 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
1456 SET_BIT (found, SSA_NAME_VERSION (op));
1458 cond = infer_value_range (stmt, op);
1462 /* Step 2. If OP is used in such a way that we can infer a
1463 value range for it, create a new ASSERT_EXPR for OP
1464 (unless OP already has an ASSERT_EXPR). */
1465 gcc_assert (!is_ctrl_stmt (stmt));
1467 if (has_assert_expr (op, cond))
1470 if (!stmt_ends_bb_p (stmt))
1472 /* If STMT does not end the block, we can insert the new
1473 assertion right after it. */
1474 tree t = build_assert_expr_for (cond, op);
1475 bsi_insert_after (&si, t, BSI_NEW_STMT);
1480 /* STMT must be the last statement in BB. We can only
1481 insert new assertions on the non-abnormal edge out of
1482 BB. Note that since STMT is not control flow, there
1483 may only be one non-abnormal edge out of BB. */
1487 FOR_EACH_EDGE (e, ei, bb->succs)
1488 if (!(e->flags & EDGE_ABNORMAL))
1490 tree t = build_assert_expr_for (cond, op);
1491 bsi_insert_on_edge (e, t);
1498 /* Remember the last statement of the block. */
1502 /* Step 3. If BB's last statement is a conditional expression
1503 involving integer operands, recurse into each of the sub-graphs
1504 rooted at BB to determine if we need to add ASSERT_EXPRs.
1505 Notice that we only care about the first operand of the
1506 conditional. Adding assertions for both operands may actually
1507 hinder VRP. FIXME, add example. */
1509 && TREE_CODE (last) == COND_EXPR
1510 && !fp_predicate (COND_EXPR_COND (last))
1511 && NUM_USES (uses = STMT_USE_OPS (last)) > 0)
1518 cond = COND_EXPR_COND (last);
1520 op = USE_OP (uses, 0);
1522 /* Do not attempt to infer anything in names that flow through
1524 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1527 /* Remove the COND_EXPR operand from the FOUND bitmap.
1528 Otherwise, when we finish traversing each of the sub-graphs,
1529 we won't know whether the variables were found in the
1530 sub-graphs or if they had been found in a block upstream from
1532 RESET_BIT (found, SSA_NAME_VERSION (op));
1534 /* Look for uses of the operands in each of the sub-graphs
1535 rooted at BB. We need to check each of the outgoing edges
1536 separately, so that we know what kind of ASSERT_EXPR to
1538 FOR_EACH_EDGE (e, ei, bb->succs)
1540 /* If BB strictly dominates the sub-graph at E->DEST,
1543 && dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1544 added |= maybe_add_assert_expr (e->dest);
1546 /* Once we traversed the sub-graph, check if any block inside
1547 used either of the predicate's operands. If so, add the
1548 appropriate ASSERT_EXPR. */
1549 if (TEST_BIT (found, SSA_NAME_VERSION (op)))
1551 /* We found a use of OP in the sub-graph rooted at
1552 E->DEST. Add an ASSERT_EXPR according to whether
1553 E goes to THEN_CLAUSE or ELSE_CLAUSE. */
1556 if (e->flags & EDGE_TRUE_VALUE)
1557 c = unshare_expr (cond);
1558 else if (e->flags & EDGE_FALSE_VALUE)
1559 c = invert_truthvalue (cond);
1563 t = build_assert_expr_for (c, op);
1564 bsi_insert_on_edge (e, t);
1569 /* Finally, mark all the COND_EXPR operands as found. */
1570 SET_BIT (found, SSA_NAME_VERSION (op));
1572 /* Recurse into the dominator children of BB that are not BB's
1573 immediate successors. Note that we have already visited BB's
1574 other dominator children above. */
1575 for (son = first_dom_son (CDI_DOMINATORS, bb);
1577 son = next_dom_son (CDI_DOMINATORS, son))
1579 if (find_edge (bb, son) == NULL)
1580 added |= maybe_add_assert_expr (son);
1585 /* Step 4. Recurse into the dominator children of BB. */
1588 for (son = first_dom_son (CDI_DOMINATORS, bb);
1590 son = next_dom_son (CDI_DOMINATORS, son))
1591 added |= maybe_add_assert_expr (son);
1598 /* Traverse the flowgraph looking for conditional jumps to insert range
1599 expressions. These range expressions are meant to provide information
1600 to optimizations that need to reason in terms of value ranges. They
1601 will not be expanded into RTL. For instance, given:
1610 this pass will transform the code into:
1616 x = ASSERT_EXPR <x, x < y>
1621 y = ASSERT_EXPR <y, x <= y>
1625 The idea is that once copy and constant propagation have run, other
1626 optimizations will be able to determine what ranges of values can 'x'
1627 take in different paths of the code, simply by checking the reaching
1628 definition of 'x'. */
1631 insert_range_assertions (void)
1637 found = sbitmap_alloc (num_ssa_names);
1638 sbitmap_zero (found);
1640 calculate_dominance_info (CDI_DOMINATORS);
1642 update_ssa_p = false;
1643 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1644 if (maybe_add_assert_expr (e->dest))
1645 update_ssa_p = true;
1649 bsi_commit_edge_inserts ();
1650 update_ssa (TODO_update_ssa_no_phi);
1653 if (dump_file && (dump_flags & TDF_DETAILS))
1655 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
1656 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1659 sbitmap_free (found);
1663 /* Convert range assertion expressions into copies. FIXME, explain why. */
1666 remove_range_assertions (void)
1669 block_stmt_iterator si;
1672 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1674 tree stmt = bsi_stmt (si);
1676 if (TREE_CODE (stmt) == MODIFY_EXPR
1677 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1679 tree rhs = TREE_OPERAND (stmt, 1);
1680 tree cond = fold (ASSERT_EXPR_COND (rhs));
1681 gcc_assert (cond != boolean_false_node);
1682 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
1689 /* Return true if STMT is interesting for VRP. */
1692 stmt_interesting_for_vrp (tree stmt)
1694 if (TREE_CODE (stmt) == PHI_NODE
1695 && is_gimple_reg (PHI_RESULT (stmt))
1696 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
1697 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
1699 else if (TREE_CODE (stmt) == MODIFY_EXPR)
1701 tree lhs = TREE_OPERAND (stmt, 0);
1702 stmt_ann_t ann = stmt_ann (stmt);
1704 if (TREE_CODE (lhs) == SSA_NAME
1705 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1706 || POINTER_TYPE_P (TREE_TYPE (lhs)))
1707 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
1708 && NUM_VUSES (VUSE_OPS (ann)) == 0
1709 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
1712 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1719 /* Initialize local data structures for VRP. Return true if VRP
1720 is worth running (i.e. if we found any statements that could
1721 benefit from range information). */
1724 vrp_initialize (void)
1729 /* If we don't find any ASSERT_EXPRs in the code, there's no point
1735 block_stmt_iterator si;
1738 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1740 if (!stmt_interesting_for_vrp (phi))
1742 tree lhs = PHI_RESULT (phi);
1743 set_value_range (get_value_range (lhs), VR_VARYING, 0, 0);
1744 DONT_SIMULATE_AGAIN (phi) = true;
1747 DONT_SIMULATE_AGAIN (phi) = false;
1750 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1752 tree stmt = bsi_stmt (si);
1754 if (!stmt_interesting_for_vrp (stmt))
1758 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
1759 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1760 DONT_SIMULATE_AGAIN (stmt) = true;
1764 if (TREE_CODE (stmt) == MODIFY_EXPR
1765 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1768 DONT_SIMULATE_AGAIN (stmt) = false;
1777 /* Visit assignment STMT. If it produces an interesting range, record
1778 the SSA name in *OUTPUT_P. */
1780 static enum ssa_prop_result
1781 vrp_visit_assignment (tree stmt, tree *output_p)
1786 lhs = TREE_OPERAND (stmt, 0);
1787 rhs = TREE_OPERAND (stmt, 1);
1789 /* We only keep track of ranges in integral and pointer types. */
1790 if (TREE_CODE (lhs) == SSA_NAME
1791 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1792 || POINTER_TYPE_P (TREE_TYPE (lhs))))
1794 value_range *vr, new_vr;
1797 vr = get_value_range (lhs);
1798 extract_range_from_expr (&new_vr, rhs);
1800 /* If STMT is inside a loop, we may be able to know something
1801 else about the range of LHS by examining scalar evolution
1803 if (cfg_loops && (l = loop_containing_stmt (stmt)))
1804 adjust_range_with_scev (&new_vr, l, lhs);
1806 if (update_value_range (vr, new_vr.type, new_vr.min, new_vr.max))
1810 if (dump_file && (dump_flags & TDF_DETAILS))
1812 fprintf (dump_file, "Found new range ");
1813 dump_value_range (dump_file, &new_vr);
1814 fprintf (dump_file, " for ");
1815 print_generic_expr (dump_file, lhs, 0);
1816 fprintf (dump_file, "\n\n");
1819 if (new_vr.type == VR_VARYING)
1820 return SSA_PROP_VARYING;
1822 return SSA_PROP_INTERESTING;
1825 return SSA_PROP_NOT_INTERESTING;
1828 /* Every other statements produces no useful ranges. */
1829 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1830 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1832 return SSA_PROP_VARYING;
1836 /* Given a conditional predicate COND, try to determine if COND yields
1837 true or false based on the value ranges of its operands. */
1840 vrp_evaluate_conditional (tree cond)
1842 gcc_assert (TREE_CODE (cond) == SSA_NAME
1843 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
1845 if (TREE_CODE (cond) == SSA_NAME)
1847 /* For SSA names, only return a truth value if the range is
1848 known and contains exactly one value. */
1849 value_range *vr = SSA_NAME_VALUE_RANGE (cond);
1850 if (vr && vr->type == VR_RANGE && vr->min == vr->max)
1855 /* For comparisons, evaluate each operand and compare their
1858 value_range *vr0, *vr1;
1860 op0 = TREE_OPERAND (cond, 0);
1861 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
1863 op1 = TREE_OPERAND (cond, 1);
1864 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
1867 return compare_ranges (TREE_CODE (cond), vr0, vr1);
1868 else if (vr0 && vr1 == NULL)
1869 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
1870 else if (vr0 == NULL && vr1)
1871 return compare_range_with_value (opposite_comparison (TREE_CODE (cond)),
1875 /* Anything else cannot be computed statically. */
1880 /* Visit conditional statement STMT. If we can determine which edge
1881 will be taken out of STMT's basic block, record it in
1882 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
1883 SSA_PROP_VARYING. */
1885 static enum ssa_prop_result
1886 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
1890 *taken_edge_p = NULL;
1892 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
1893 add ASSERT_EXPRs for them. */
1894 if (TREE_CODE (stmt) == SWITCH_EXPR)
1895 return SSA_PROP_VARYING;
1897 cond = COND_EXPR_COND (stmt);
1899 if (dump_file && (dump_flags & TDF_DETAILS))
1904 fprintf (dump_file, "\nVisiting conditional with predicate: ");
1905 print_generic_expr (dump_file, cond, 0);
1906 fprintf (dump_file, "\nWith known ranges\n");
1908 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
1910 fprintf (dump_file, "\t");
1911 print_generic_expr (dump_file, use, 0);
1912 fprintf (dump_file, ": ");
1913 dump_value_range (dump_file, SSA_NAME_VALUE_RANGE (use));
1916 fprintf (dump_file, "\n");
1919 /* Compute the value of the predicate COND by checking the known
1920 ranges of each of its operands. */
1921 val = vrp_evaluate_conditional (cond);
1923 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
1925 if (dump_file && (dump_flags & TDF_DETAILS))
1927 fprintf (dump_file, "\nPredicate evaluates to: ");
1928 if (val == NULL_TREE)
1929 fprintf (dump_file, "DON'T KNOW\n");
1931 print_generic_stmt (dump_file, val, 0);
1934 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
1938 /* Evaluate statement STMT. If the statement produces a useful range,
1939 return SSA_PROP_INTERESTING and record the SSA name with the
1940 interesting range into *OUTPUT_P.
1942 If STMT is a conditional branch and we can determine its truth
1943 value, the taken edge is recorded in *TAKEN_EDGE_P.
1945 If STMT produces a varying value, return SSA_PROP_VARYING. */
1947 static enum ssa_prop_result
1948 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
1954 if (dump_file && (dump_flags & TDF_DETAILS))
1956 fprintf (dump_file, "\nVisiting statement:\n");
1957 print_generic_stmt (dump_file, stmt, dump_flags);
1958 fprintf (dump_file, "\n");
1961 ann = stmt_ann (stmt);
1962 if (TREE_CODE (stmt) == MODIFY_EXPR
1963 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
1964 && NUM_VUSES (VUSE_OPS (ann)) == 0
1965 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
1966 return vrp_visit_assignment (stmt, output_p);
1967 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1968 return vrp_visit_cond_stmt (stmt, taken_edge_p);
1970 /* All other statements produce nothing of interest for VRP, so mark
1971 their outputs varying and prevent further simulation. */
1972 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1973 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1975 return SSA_PROP_VARYING;
1979 /* Meet operation for value ranges. Given two value ranges VR0 and
1980 VR1, store in VR0 the result of meeting VR0 and VR1.
1982 The meeting rules are as follows:
1984 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
1986 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
1987 union of VR0 and VR1. */
1990 vrp_meet (value_range *vr0, value_range *vr1)
1992 if (vr0->type == VR_UNDEFINED)
1998 if (vr1->type == VR_UNDEFINED)
2000 /* Nothing to do. VR0 already has the resulting range. */
2004 if (vr0->type == VR_VARYING)
2006 /* Nothing to do. VR0 already has the resulting range. */
2010 if (vr1->type == VR_VARYING)
2016 /* If either is a symbolic range, drop to VARYING. */
2017 if (symbolic_range_p (vr0) || symbolic_range_p (vr1))
2019 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2023 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
2025 /* If VR0 and VR1 have a non-empty intersection, compute the
2026 union of both ranges. */
2027 if (value_ranges_intersect_p (vr0, vr1))
2034 /* The lower limit of the new range is the minimum of the
2036 if (compare_values (vr0->min, vr1->min) == 1)
2039 /* The upper limit of the new range is the maximum of the
2041 if (compare_values (vr0->max, vr1->max) == -1)
2044 set_value_range (vr0, vr0->type, min, max);
2048 /* The two ranges don't intersect, set the result to VR_VARYING. */
2049 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2052 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
2054 /* Two anti-ranges meet only if they are both identical. */
2055 if (compare_values (vr0->min, vr1->min) == 0
2056 && compare_values (vr0->max, vr1->max) == 0
2057 && compare_values (vr0->min, vr0->max) == 0)
2058 /* Nothing to do. */ ;
2060 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2062 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
2064 /* A range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] meet
2065 only if the ranges have an empty intersection. The result of
2066 the meet operation is the anti-range. */
2067 if (!value_ranges_intersect_p (vr0, vr1))
2069 if (vr1->type == VR_ANTI_RANGE)
2073 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2080 /* Visit all arguments for PHI node PHI that flow through executable
2081 edges. If a valid value range can be derived from all the incoming
2082 value ranges, set a new range for the LHS of PHI. */
2084 static enum ssa_prop_result
2085 vrp_visit_phi_node (tree phi)
2088 tree lhs = PHI_RESULT (phi);
2089 value_range *lhs_vr = get_value_range (lhs);
2090 value_range vr_result = *lhs_vr;
2092 if (dump_file && (dump_flags & TDF_DETAILS))
2094 fprintf (dump_file, "\nVisiting PHI node: ");
2095 print_generic_expr (dump_file, phi, dump_flags);
2098 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2100 edge e = PHI_ARG_EDGE (phi, i);
2102 if (dump_file && (dump_flags & TDF_DETAILS))
2105 "\n Argument #%d (%d -> %d %sexecutable)\n",
2106 i, e->src->index, e->dest->index,
2107 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
2110 if (e->flags & EDGE_EXECUTABLE)
2112 tree arg = PHI_ARG_DEF (phi, i);
2115 if (TREE_CODE (arg) == SSA_NAME)
2116 vr_arg = *(get_value_range (arg));
2119 vr_arg.type = VR_RANGE;
2124 if (dump_file && (dump_flags & TDF_DETAILS))
2126 fprintf (dump_file, "\t");
2127 print_generic_expr (dump_file, arg, dump_flags);
2128 fprintf (dump_file, "\n\tValue: ");
2129 dump_value_range (dump_file, &vr_arg);
2130 fprintf (dump_file, "\n");
2133 vrp_meet (&vr_result, &vr_arg);
2135 if (vr_result.type == VR_VARYING)
2140 if (vr_result.type == VR_VARYING)
2142 set_value_range (lhs_vr, VR_VARYING, 0, 0);
2143 return SSA_PROP_VARYING;
2146 /* To prevent infinite iterations in the algorithm, derive ranges
2147 when the new value is slightly bigger or smaller than the
2149 if (lhs_vr->type == VR_RANGE)
2151 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
2153 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
2154 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
2156 /* If the new minimum is smaller or larger than the previous
2157 one, go all the way to -INF. In the first case, to avoid
2158 iterating millions of times to reach -INF, and in the
2159 other case to avoid infinite bouncing between different
2161 if (cmp_min > 0 || cmp_min < 0)
2162 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
2164 /* Similarly, if the new maximum is smaller or larger than
2165 the previous one, go all the way to +INF. */
2166 if (cmp_max < 0 || cmp_max > 0)
2167 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
2169 /* If we ended up with a (-INF, +INF) range, set it to
2171 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
2172 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
2174 set_value_range (lhs_vr, VR_VARYING, 0, 0);
2175 return SSA_PROP_VARYING;
2180 /* If the new range is different than the previous value, keep
2182 if (update_value_range (lhs_vr, vr_result.type, vr_result.min, vr_result.max))
2183 return SSA_PROP_INTERESTING;
2185 /* Nothing changed, don't add outgoing edges. */
2186 return SSA_PROP_NOT_INTERESTING;
2190 /* Traverse all the blocks folding conditionals with known ranges. */
2196 int num_pred_folded = 0;
2200 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
2201 dump_all_value_ranges (dump_file);
2202 fprintf (dump_file, "\n");
2207 tree last = last_stmt (bb);
2208 if (last && TREE_CODE (last) == COND_EXPR)
2210 tree val = vrp_evaluate_conditional (COND_EXPR_COND (last));
2215 fprintf (dump_file, "Folding predicate ");
2216 print_generic_expr (dump_file, COND_EXPR_COND (last), 0);
2217 fprintf (dump_file, " to ");
2218 print_generic_expr (dump_file, val, 0);
2219 fprintf (dump_file, "\n");
2223 COND_EXPR_COND (last) = val;
2229 if (dump_file && (dump_flags & TDF_STATS))
2230 fprintf (dump_file, "\nNumber of predicates folded: %d\n\n",
2235 /* Main entry point to VRP (Value Range Propagation). This pass is
2236 loosely based on J. R. C. Patterson, ``Accurate Static Branch
2237 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
2238 Programming Language Design and Implementation, pp. 67-78, 1995.
2239 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
2241 This is essentially an SSA-CCP pass modified to deal with ranges
2242 instead of constants.
2244 TODO, the main difference between this pass and Patterson's is that
2245 we do not propagate edge probabilities. We only compute whether
2246 edges can be taken or not. That is, instead of having a spectrum
2247 of jump probabilities between 0 and 1, we only deal with 0, 1 and
2248 DON'T KNOW. In the future, it may be worthwhile to propagate
2249 probabilities to aid branch prediction. */
2254 insert_range_assertions ();
2256 cfg_loops = loop_optimizer_init (NULL);
2258 scev_initialize (cfg_loops);
2260 if (vrp_initialize ())
2262 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
2269 loop_optimizer_finalize (cfg_loops, NULL);
2270 current_loops = NULL;
2273 remove_range_assertions ();
2279 return flag_tree_vrp != 0;
2282 struct tree_opt_pass pass_vrp =
2285 gate_vrp, /* gate */
2286 execute_vrp, /* execute */
2289 0, /* static_pass_number */
2290 TV_TREE_VRP, /* tv_id */
2291 PROP_ssa | PROP_alias, /* properties_required */
2292 0, /* properties_provided */
2293 0, /* properties_destroyed */
2294 0, /* todo_flags_start */
2299 | TODO_update_ssa, /* todo_flags_finish */