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_on_edges. */
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 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
292 /* We can determine some comparisons against +INF and -INF even
293 if the other value is an expression. */
294 if (val1 == TYPE_MAX_VALUE (TREE_TYPE (val1))
295 && TREE_CODE (val2) == MINUS_EXPR)
297 /* +INF > NAME - CST. */
300 else if (val1 == TYPE_MIN_VALUE (TREE_TYPE (val1))
301 && TREE_CODE (val2) == PLUS_EXPR)
303 /* -INF < NAME + CST. */
306 else if (TREE_CODE (val1) == MINUS_EXPR
307 && val2 == TYPE_MAX_VALUE (TREE_TYPE (val2)))
309 /* NAME - CST < +INF. */
312 else if (TREE_CODE (val1) == PLUS_EXPR
313 && val2 == TYPE_MIN_VALUE (TREE_TYPE (val2)))
315 /* NAME + CST > -INF. */
320 if ((TREE_CODE (val1) == SSA_NAME
321 || TREE_CODE (val1) == PLUS_EXPR
322 || TREE_CODE (val1) == MINUS_EXPR)
323 && (TREE_CODE (val2) == SSA_NAME
324 || TREE_CODE (val2) == PLUS_EXPR
325 || TREE_CODE (val2) == MINUS_EXPR))
329 /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
330 return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
331 same name, return -2. */
332 if (TREE_CODE (val1) == SSA_NAME)
339 n1 = TREE_OPERAND (val1, 0);
340 c1 = TREE_OPERAND (val1, 1);
343 if (TREE_CODE (val2) == SSA_NAME)
350 n2 = TREE_OPERAND (val2, 0);
351 c2 = TREE_OPERAND (val2, 1);
354 /* Both values must use the same name. */
358 if (TREE_CODE (val1) == SSA_NAME)
360 if (TREE_CODE (val2) == SSA_NAME)
363 else if (TREE_CODE (val2) == PLUS_EXPR)
364 /* NAME < NAME + CST */
366 else if (TREE_CODE (val2) == MINUS_EXPR)
367 /* NAME > NAME - CST */
370 else if (TREE_CODE (val1) == PLUS_EXPR)
372 if (TREE_CODE (val2) == SSA_NAME)
373 /* NAME + CST > NAME */
375 else if (TREE_CODE (val2) == PLUS_EXPR)
376 /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */
377 return compare_values (c1, c2);
378 else if (TREE_CODE (val2) == MINUS_EXPR)
379 /* NAME + CST1 > NAME - CST2 */
382 else if (TREE_CODE (val1) == MINUS_EXPR)
384 if (TREE_CODE (val2) == SSA_NAME)
385 /* NAME - CST < NAME */
387 else if (TREE_CODE (val2) == PLUS_EXPR)
388 /* NAME - CST1 < NAME + CST2 */
390 else if (TREE_CODE (val2) == MINUS_EXPR)
391 /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that
392 C1 and C2 are swapped in the call to compare_values. */
393 return compare_values (c2, c1);
399 /* We cannot compare non-constants. */
400 if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
403 if (!POINTER_TYPE_P (TREE_TYPE (val1)))
404 return tree_int_cst_compare (val1, val2);
409 /* First see if VAL1 and VAL2 are not the same. */
410 if (val1 == val2 || operand_equal_p (val1, val2, 0))
413 /* If VAL1 is a lower address than VAL2, return -1. */
414 t = fold (build2 (LT_EXPR, TREE_TYPE (val1), val1, val2));
415 if (t == boolean_true_node)
418 /* If VAL1 is a higher address than VAL2, return +1. */
419 t = fold (build2 (GT_EXPR, TREE_TYPE (val1), val1, val2));
420 if (t == boolean_true_node)
423 /* If VAL1 is different than VAL2, return +2. */
424 t = fold (build2 (NE_EXPR, TREE_TYPE (val1), val1, val2));
425 if (t == boolean_true_node)
433 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
434 0 if VAL is not inside VR,
435 -2 if we cannot tell either way. */
438 value_inside_range (tree val, value_range *vr)
442 cmp1 = compare_values (val, vr->min);
443 if (cmp1 == -2 || cmp1 == 2)
446 cmp2 = compare_values (val, vr->max);
447 if (cmp2 == -2 || cmp2 == 2)
450 return (cmp1 == 0 || cmp1 == 1) && (cmp2 == -1 || cmp2 == 0);
454 /* Return true if value ranges VR0 and VR1 have a non-empty
458 value_ranges_intersect_p (value_range *vr0, value_range *vr1)
460 return (value_inside_range (vr1->min, vr0) == 1
461 || value_inside_range (vr1->max, vr0) == 1
462 || value_inside_range (vr0->min, vr1) == 1
463 || value_inside_range (vr0->max, vr1) == 1);
467 /* Extract value range information from an ASSERT_EXPR EXPR and store
471 extract_range_from_assert (value_range *vr_p, tree expr)
473 tree var, cond, limit, type;
476 var = ASSERT_EXPR_VAR (expr);
477 cond = ASSERT_EXPR_COND (expr);
479 gcc_assert (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
481 /* Find VAR in the ASSERT_EXPR conditional. */
482 limit = get_opposite_operand (cond, var);
483 type = TREE_TYPE (limit);
485 gcc_assert (limit != var);
487 /* For pointer arithmetic, we only keep track of anti-ranges
488 (NE_EXPR). Notice that we don't need to handle EQ_EXPR in these
489 cases because assertions with equalities are never generated.
490 The assert pass generates straight assignments in those cases. */
491 if (POINTER_TYPE_P (type) && TREE_CODE (cond) != NE_EXPR)
493 set_value_range (vr_p, VR_VARYING, NULL_TREE, NULL_TREE);
497 if (TREE_CODE (cond) == NE_EXPR)
498 set_value_range (vr_p, VR_ANTI_RANGE, limit, limit);
499 else if (TREE_CODE (cond) == LE_EXPR)
500 set_value_range (vr_p, VR_RANGE, TYPE_MIN_VALUE (type), limit);
501 else if (TREE_CODE (cond) == LT_EXPR)
503 tree one = build_int_cst (type, 1);
504 set_value_range (vr_p, VR_RANGE, TYPE_MIN_VALUE (type),
505 fold (build (MINUS_EXPR, type, limit, one)));
507 else if (TREE_CODE (cond) == GE_EXPR)
508 set_value_range (vr_p, VR_RANGE, limit, TYPE_MAX_VALUE (type));
509 else if (TREE_CODE (cond) == GT_EXPR)
511 tree one = build_int_cst (type, 1);
512 set_value_range (vr_p, VR_RANGE,
513 fold (build (PLUS_EXPR, type, limit, one)),
514 TYPE_MAX_VALUE (type));
519 /* If VAR already has a known range and the two ranges have a
520 non-empty intersection, we can refine the resulting range.
521 Since the assert expression creates an equivalency and at the
522 same time it asserts a predicate, we can take the intersection of
523 the two ranges to get better precision. */
524 var_vr = get_value_range (var);
525 if (var_vr->type == VR_RANGE
526 && vr_p->type == VR_RANGE
527 && value_ranges_intersect_p (var_vr, vr_p))
531 /* Use the larger of the two minimums. */
532 if (compare_values (vr_p->min, var_vr->min) == -1)
537 /* Use the smaller of the two maximums. */
538 if (compare_values (vr_p->max, var_vr->max) == 1)
543 set_value_range (vr_p, vr_p->type, min, max);
548 /* Extract range information from SSA name VAR and store it in VR. If
549 VAR has an interesting range, use it. Otherwise, create the
550 range [VAR, VAR] and return it. This is useful in situations where
551 we may have conditionals testing values of VARYING names. For
558 Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
562 extract_range_from_ssa_name (value_range *vr, tree var)
564 value_range *var_vr = get_value_range (var);
566 if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
569 set_value_range (vr, VR_RANGE, var, var);
573 /* Extract range information from a binary expression EXPR based on
574 the ranges of each of its operands and the expression code. */
577 extract_range_from_binary_expr (value_range *vr, tree expr)
579 enum tree_code code = TREE_CODE (expr);
580 tree op0, op1, min, max;
581 value_range vr0, vr1;
584 /* Not all binary expressions can be applied to ranges in a
585 meaningful way. Handle only arithmetic operations. */
586 if (code != PLUS_EXPR
587 && code != MINUS_EXPR
589 && code != TRUNC_DIV_EXPR
590 && code != FLOOR_DIV_EXPR
591 && code != CEIL_DIV_EXPR
592 && code != EXACT_DIV_EXPR
593 && code != ROUND_DIV_EXPR
597 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
601 /* Get value ranges for each operand. For constant operands, create
602 a new value range with the operand to simplify processing. */
603 op0 = TREE_OPERAND (expr, 0);
604 if (TREE_CODE (op0) == SSA_NAME)
605 vr0 = *(get_value_range (op0));
608 if (is_gimple_min_invariant (op0))
609 set_value_range (&vr0, VR_RANGE, op0, op0);
611 set_value_range (&vr0, VR_VARYING, NULL_TREE, NULL_TREE);
614 op1 = TREE_OPERAND (expr, 1);
615 if (TREE_CODE (op1) == SSA_NAME)
616 vr1 = *(get_value_range (op1));
619 if (is_gimple_min_invariant (op1))
620 set_value_range (&vr1, VR_RANGE, op1, op1);
622 set_value_range (&vr1, VR_VARYING, 0, 0);
625 /* If either range is UNDEFINED, so is the result. */
626 if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
628 set_value_range (vr, VR_UNDEFINED, NULL_TREE, NULL_TREE);
632 /* If either range is VARYING, so is the result. */
633 if (vr0.type == VR_VARYING || vr1.type == VR_VARYING)
635 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
639 /* If the ranges are of different types, the result is VARYING. */
640 if (vr0.type != vr1.type)
642 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
646 /* TODO. Refuse to do any symbolic range operations for now. */
647 if (symbolic_range_p (&vr0) || symbolic_range_p (&vr1))
649 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
653 /* Now evaluate the expression to determine the new range. */
654 if (POINTER_TYPE_P (TREE_TYPE (expr))
655 || POINTER_TYPE_P (TREE_TYPE (op0))
656 || POINTER_TYPE_P (TREE_TYPE (op1)))
658 /* For pointer types, we are really only interested in asserting
659 whether the expression evaluates to non-NULL. FIXME. We
660 used to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR),
661 but ivopts is generating expressions with pointer
662 multiplication in them. */
663 if (code == PLUS_EXPR)
665 /* Assume that pointers can never wrap around. FIXME, Is
667 tree zero = build_int_cst (TREE_TYPE (expr), 0);
668 set_value_range (vr, VR_ANTI_RANGE, zero, zero);
672 /* Subtracting from a pointer, may yield 0, so just drop the
673 resulting range to varying. */
674 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
680 /* For integer ranges, apply the operation to each end of the
681 range and see what we end up with. */
682 if (code == PLUS_EXPR
687 /* For operations that make the resulting range directly
688 proportional to the original ranges, apply the operation to
689 the same end of each range. */
690 min = int_const_binop (code, vr0.min, vr1.min, 0);
691 max = int_const_binop (code, vr0.max, vr1.max, 0);
695 /* For operations that make the resulting range inversely
696 proportional to the original ranges (-, /), apply the
697 operation to the opposite ends of each range. */
698 min = int_const_binop (code, vr0.min, vr1.max, 0);
699 max = int_const_binop (code, vr0.max, vr1.min, 0);
702 cmp = compare_values (min, max);
703 if (cmp == -2 || cmp == 1)
705 /* If the new range has its limits swapped around (MIN > MAX),
706 then the operation caused one of them to wrap around, mark
707 the new range VARYING. */
708 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
711 set_value_range (vr, vr0.type, min, max);
715 /* Extract range information from a unary expression EXPR based on
716 the range of its operand and the expression code. */
719 extract_range_from_unary_expr (value_range *vr, tree expr)
721 enum tree_code code = TREE_CODE (expr);
726 /* Get value ranges for the operand. For constant operands, create
727 a new value range with the operand to simplify processing. */
728 op0 = TREE_OPERAND (expr, 0);
729 if (TREE_CODE (op0) == SSA_NAME)
730 vr0 = *(get_value_range (op0));
733 if (is_gimple_min_invariant (op0))
734 set_value_range (&vr0, VR_RANGE, op0, op0);
736 set_value_range (&vr0, VR_VARYING, NULL_TREE, NULL_TREE);
739 /* If VR0 is UNDEFINED, so is the result. */
740 if (vr0.type == VR_UNDEFINED)
742 set_value_range (vr, VR_UNDEFINED, NULL_TREE, NULL_TREE);
746 /* If VR0 is VARYING, so is the result. */
747 if (vr0.type == VR_VARYING)
749 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
753 /* TODO. Refuse to do any symbolic range operations for now. */
754 if (symbolic_range_p (&vr0))
756 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
760 /* If the operand is neither a pointer nor an integral type, set the
761 range to VARYING. TODO, we may set the range to non-zero. */
762 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
763 && !POINTER_TYPE_P (TREE_TYPE (op0)))
765 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
769 /* If the expression involves pointers, we are only interested in
770 determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
771 if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
773 if (range_is_nonnull (&vr0) || expr_computes_nonzero (expr))
774 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
775 else if (range_is_null (&vr0))
776 set_value_range_to_null (vr, TREE_TYPE (expr));
778 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
783 /* Handle unary expressions on integer ranges. */
784 if ((code == NOP_EXPR || code == CONVERT_EXPR)
785 && (TYPE_SIZE (TREE_TYPE (vr0.min)) != TYPE_SIZE (TREE_TYPE (expr))))
787 /* When converting types of different sizes, set the result to
788 VARYING. Things like sign extensions and precision loss may
789 change the range. For instance, if x_3 is of type 'long long
790 int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
791 is impossible to know at compile time whether y_5 will be
793 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
797 /* Apply the operation to each end of the range and see what we end
799 min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
800 max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
802 cmp = compare_values (min, max);
803 if (cmp == -2 || cmp == 1)
805 /* If the new range has its limits swapped around (MIN > MAX),
806 then the operation caused one of them to wrap around, mark
807 the new range VARYING. */
808 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
811 set_value_range (vr, vr0.type, min, max);
815 /* Try to compute a useful range out of expression EXPR and store it
819 extract_range_from_expr (value_range *vr, tree expr)
821 enum tree_code code = TREE_CODE (expr);
823 if (code == ASSERT_EXPR)
824 extract_range_from_assert (vr, expr);
825 else if (code == SSA_NAME)
826 extract_range_from_ssa_name (vr, expr);
827 else if (TREE_CODE_CLASS (code) == tcc_binary)
828 extract_range_from_binary_expr (vr, expr);
829 else if (TREE_CODE_CLASS (code) == tcc_unary)
830 extract_range_from_unary_expr (vr, expr);
831 else if (expr_computes_nonzero (expr))
832 set_value_range_to_nonnull (vr, TREE_TYPE (expr));
834 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
838 /* Given a range VR, a loop L and a variable VAR, determine whether it
839 would be profitable to adjust VR using scalar evolution information
840 for VAR. If so, update VR with the new limits. */
843 adjust_range_with_scev (value_range *vr, struct loop *l, tree var)
845 tree init, step, chrec;
848 /* TODO. Don't adjust anti-ranges. An anti-range may provide
849 better opportunities than a regular range, but I'm not sure. */
850 if (vr->type == VR_ANTI_RANGE)
853 chrec = analyze_scalar_evolution (l, var);
854 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
857 init = CHREC_LEFT (chrec);
858 step = CHREC_RIGHT (chrec);
860 /* If STEP is symbolic, we can't know whether INIT will be the
861 minimum or maximum value in the range. */
862 if (!is_gimple_min_invariant (step))
865 /* FIXME. When dealing with unsigned types,
866 analyze_scalar_evolution sets STEP to very large unsigned values
867 when the evolution goes backwards. This confuses this analysis
868 because we think that INIT is the smallest value that the range
869 can take, instead of the largest. Ignore these chrecs for now. */
870 if (INTEGRAL_TYPE_P (TREE_TYPE (step)) && TYPE_UNSIGNED (TREE_TYPE (step)))
873 /* If STEP is negative, then INIT is the maximum value the range
874 will take. Otherwise, INIT is the minimum value. */
875 init_is_max = (tree_int_cst_sgn (step) < 0);
877 if (!POINTER_TYPE_P (TREE_TYPE (init))
878 && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
880 /* For VARYING or UNDEFINED ranges, just about anything we get
881 from scalar evolutions should be better. */
883 set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)), init);
885 set_value_range (vr, VR_RANGE, init, TYPE_MAX_VALUE (TREE_TYPE (init)));
887 else if (vr->type == VR_RANGE)
891 /* INIT is the maximum value. If INIT is lower than
892 VR->MAX, set VR->MAX to INIT. */
893 if (compare_values (init, vr->max) == -1)
894 set_value_range (vr, VR_RANGE, vr->min, init);
898 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
899 if (compare_values (init, vr->min) == 1)
900 set_value_range (vr, VR_RANGE, init, vr->max);
906 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
908 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for all the
909 values in the ranges.
911 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
913 - Return NULL_TREE if it is not always possible to determine the value of
917 compare_ranges (enum tree_code comp, value_range *vr0, value_range *vr1)
919 /* VARYING or UNDEFINED ranges cannot be compared. */
920 if (vr0->type == VR_VARYING
921 || vr0->type == VR_UNDEFINED
922 || vr1->type == VR_VARYING
923 || vr1->type == VR_UNDEFINED)
926 /* Anti-ranges need to be handled separately. */
927 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
929 /* If both are anti-ranges, then we cannot compute any
931 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
934 /* These comparisons are never statically computable. */
941 /* Equality can be computed only between a range and an
942 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
943 if (vr0->type == VR_RANGE)
945 /* To simplify processing, make VR0 the anti-range. */
946 value_range *tmp = vr0;
951 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
953 if (compare_values (vr0->min, vr1->min) == 0
954 && compare_values (vr0->max, vr1->max) == 0)
955 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
960 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
961 operands around and change the comparison code. */
962 if (comp == GT_EXPR || comp == GE_EXPR)
965 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
973 /* Equality may only be computed if both ranges represent
974 exactly one value. */
975 if (compare_values (vr0->min, vr0->max) == 0
976 && compare_values (vr1->min, vr1->max) == 0)
978 int cmp_min = compare_values (vr0->min, vr1->min);
979 int cmp_max = compare_values (vr0->max, vr1->max);
980 if (cmp_min == 0 && cmp_max == 0)
981 return boolean_true_node;
982 else if (cmp_min != -2 && cmp_max != -2)
983 return boolean_false_node;
988 else if (comp == NE_EXPR)
992 /* If VR0 is completely to the left or completely to the right
993 of VR1, they are always different. Notice that we need to
994 make sure that both comparisons yield similar results to
995 avoid comparing values that cannot be compared at
997 cmp1 = compare_values (vr0->max, vr1->min);
998 cmp2 = compare_values (vr0->min, vr1->max);
999 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
1000 return boolean_true_node;
1002 /* If VR0 and VR1 represent a single value and are identical,
1004 else if (compare_values (vr0->min, vr0->max) == 0
1005 && compare_values (vr1->min, vr1->max) == 0
1006 && compare_values (vr0->min, vr1->min) == 0
1007 && compare_values (vr0->max, vr1->max) == 0)
1008 return boolean_false_node;
1010 /* Otherwise, they may or may not be different. */
1014 else if (comp == LT_EXPR || comp == LE_EXPR)
1018 /* If VR0 is to the left of VR1, return true. */
1019 tst = compare_values (vr0->max, vr1->min);
1020 if ((comp == LT_EXPR && tst == -1)
1021 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1022 return boolean_true_node;
1024 /* If VR0 is to the right of VR1, return false. */
1025 tst = compare_values (vr0->min, vr1->max);
1026 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1027 || (comp == LE_EXPR && tst == 1))
1028 return boolean_false_node;
1030 /* Otherwise, we don't know. */
1038 /* Given a value range VR, a value VAL and a comparison code COMP, return
1039 BOOLEAN_TRUE_NODE if VR COMP VR1 always returns true for all the
1040 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1041 always returns false. Return NULL_TREE if it is not always
1042 possible to determine the value of the comparison. */
1045 compare_range_with_value (enum tree_code comp, value_range *vr, tree val)
1047 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1050 /* Anti-ranges need to be handled separately. */
1051 if (vr->type == VR_ANTI_RANGE)
1053 /* For anti-ranges, the only predicates that we can compute at
1054 compile time are equality and inequality. */
1061 /* ~[VAL, VAL] == VAL is always false. */
1062 if (compare_values (vr->min, val) == 0
1063 && compare_values (vr->max, val) == 0)
1064 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1069 if (comp == EQ_EXPR)
1071 /* EQ_EXPR may only be computed if VR represents exactly
1073 if (compare_values (vr->min, vr->max) == 0)
1075 int cmp = compare_values (vr->min, val);
1077 return boolean_true_node;
1078 else if (cmp == -1 || cmp == 1 || cmp == 2)
1079 return boolean_false_node;
1084 else if (comp == NE_EXPR)
1086 /* If VAL is not inside VR, then they are always different. */
1087 if (compare_values (vr->max, val) == -1
1088 || compare_values (vr->min, val) == 1)
1089 return boolean_true_node;
1091 /* If VR represents exactly one value equal to VAL, then return
1093 if (compare_values (vr->min, vr->max) == 0
1094 && compare_values (vr->min, val) == 0)
1095 return boolean_false_node;
1097 /* Otherwise, they may or may not be different. */
1100 else if (comp == LT_EXPR || comp == LE_EXPR)
1104 /* If VR is to the left of VAL, return true. */
1105 tst = compare_values (vr->max, val);
1106 if ((comp == LT_EXPR && tst == -1)
1107 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1108 return boolean_true_node;
1110 /* If VR is to the right of VAL, return false. */
1111 tst = compare_values (vr->min, val);
1112 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1113 || (comp == LE_EXPR && tst == 1))
1114 return boolean_false_node;
1116 /* Otherwise, we don't know. */
1119 else if (comp == GT_EXPR || comp == GE_EXPR)
1123 /* If VR is to the right of VAL, return true. */
1124 tst = compare_values (vr->min, val);
1125 if ((comp == GT_EXPR && tst == 1)
1126 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
1127 return boolean_true_node;
1129 /* If VR is to the left of VAL, return false. */
1130 tst = compare_values (vr->max, val);
1131 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
1132 || (comp == GE_EXPR && tst == -1))
1133 return boolean_false_node;
1135 /* Otherwise, we don't know. */
1143 /* Debugging dumps. */
1146 dump_value_range (FILE *file, value_range *vr)
1149 fprintf (file, "[]");
1150 else if (vr->type == VR_UNDEFINED)
1151 fprintf (file, "UNDEFINED");
1152 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
1154 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
1155 print_generic_expr (file, vr->min, 0);
1156 fprintf (file, ", ");
1157 print_generic_expr (file, vr->max, 0);
1158 fprintf (file, "]");
1160 else if (vr->type == VR_VARYING)
1161 fprintf (file, "VARYING");
1163 fprintf (file, "INVALID RANGE");
1167 /* Dump value range VR to stderr. */
1170 debug_value_range (value_range *vr)
1172 dump_value_range (stderr, vr);
1176 /* Dump value ranges of all SSA_NAMEs to FILE. */
1179 dump_all_value_ranges (FILE *file)
1183 for (i = 0; i < num_ssa_names; i++)
1185 tree var = ssa_name (i);
1186 if (var && SSA_NAME_VALUE_RANGE (var))
1188 print_generic_expr (file, var, 0);
1189 fprintf (file, ": ");
1190 dump_value_range (file, SSA_NAME_VALUE_RANGE (var));
1191 fprintf (file, "\n");
1195 fprintf (file, "\n");
1199 /* Dump all value ranges to stderr. */
1202 debug_all_value_ranges (void)
1204 dump_all_value_ranges (stderr);
1208 /*---------------------------------------------------------------------------
1209 Value Range Propagation
1210 ---------------------------------------------------------------------------*/
1212 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
1213 create a new SSA name N and return the assertion assignment
1214 'V = ASSERT_EXPR <V, V OP W>'. */
1217 build_assert_expr_for (tree cond, tree v)
1221 gcc_assert (TREE_CODE (v) == SSA_NAME);
1222 n = duplicate_ssa_name (v, NULL_TREE);
1224 if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison)
1226 /* Build N = ASSERT_EXPR <V, COND>. As a special case, if the
1227 conditional is an EQ_EXPR (V == Z), just build the assignment
1229 if (TREE_CODE (cond) == EQ_EXPR)
1231 tree other = get_opposite_operand (cond, v);
1232 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, other);
1235 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n,
1236 build (ASSERT_EXPR, TREE_TYPE (v), v, cond));
1238 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1240 /* Given !V, build the assignment N = false. */
1241 tree op0 = TREE_OPERAND (cond, 0);
1242 gcc_assert (op0 == v);
1243 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
1245 else if (TREE_CODE (cond) == SSA_NAME)
1247 /* Given V, build the assignment N = true. */
1248 gcc_assert (v == cond);
1249 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
1254 SSA_NAME_DEF_STMT (n) = assertion;
1256 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
1257 operand of the ASSERT_EXPR. Register the new name and the old one
1258 in the replacement table so that we can fix the SSA web after
1259 adding all the ASSERT_EXPRs. */
1260 register_new_name_mapping (n, v);
1266 /* Return false if EXPR is a predicate expression involving floating
1270 fp_predicate (tree expr)
1272 return TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison
1273 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)));
1277 /* Return an expression predicate that represents the range of values
1278 that can be taken by operand OP after STMT executes. */
1281 infer_value_range (tree stmt, tree op)
1283 if (POINTER_TYPE_P (TREE_TYPE (op)))
1286 unsigned num_uses, num_derefs;
1288 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
1289 if (num_derefs > 0 && flag_delete_null_pointer_checks)
1291 /* We can only assume that a pointer dereference will yield
1292 non-NULL if -fdelete-null-pointer-checks is enabled. */
1293 tree null = build_int_cst (TREE_TYPE (op), 0);
1294 tree t = build (NE_EXPR, boolean_type_node, op, null);
1303 /* Return true if OP is the result of an ASSERT_EXPR that tests the
1304 same condition as COND. */
1307 has_assert_expr (tree op, tree cond)
1309 tree def_stmt = SSA_NAME_DEF_STMT (op);
1310 tree assert_expr, other_cond, other_op;
1312 /* If OP was not generated by an ASSERT_EXPR, return false. */
1313 if (TREE_CODE (def_stmt) != MODIFY_EXPR
1314 || TREE_CODE (TREE_OPERAND (def_stmt, 1)) != ASSERT_EXPR)
1317 assert_expr = TREE_OPERAND (def_stmt, 1);
1318 other_cond = ASSERT_EXPR_COND (assert_expr);
1319 other_op = ASSERT_EXPR_VAR (assert_expr);
1321 if (TREE_CODE (cond) == TREE_CODE (other_cond))
1325 /* If COND is not a comparison predicate, something is wrong. */
1326 gcc_assert (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
1328 /* Note that we only need to compare against one of the operands
1331 Suppose that we are about to insert the assertion ASSERT_EXPR
1332 <x_4, x_4 != 0> and the defining statement for x_4 is x_4 =
1333 ASSERT_EXPR <x_3, x_3 != 0>.
1335 In this case, we don't really want to insert a new
1336 ASSERT_EXPR for x_4 because that would be redundant. We
1337 already know that x_4 is not 0. So, when comparing the
1338 conditionals 'x_3 != 0' and 'x_4 != 0', we don't want to
1339 compare x_3 and x_4, we just want to compare the predicate's
1340 code (!=) and the other operand (0). */
1341 if (TREE_OPERAND (cond, 0) == op)
1342 t1 = TREE_OPERAND (cond, 1);
1344 t1 = TREE_OPERAND (cond, 0);
1346 if (TREE_OPERAND (other_cond, 0) == other_op)
1347 t2 = TREE_OPERAND (other_cond, 1);
1349 t2 = TREE_OPERAND (other_cond, 0);
1351 return (t1 == t2 || operand_equal_p (t1, t2, 0));
1358 /* Traverse all the statements in block BB looking for used variables.
1359 Variables used in BB are added to bitmap FOUND. The algorithm
1360 works in three main parts:
1362 1- For every statement S in BB, all the variables used by S are
1363 added to bitmap FOUND.
1365 2- If statement S uses an operand N in a way that exposes a known
1366 value range for N, then if N was not already generated by an
1367 ASSERT_EXPR, create a new ASSERT_EXPR for N. For instance, if N
1368 is a pointer and the statement dereferences it, we can assume
1371 3- COND_EXPRs are a special case of #2. We can derive range
1372 information from the predicate but need to insert different
1373 ASSERT_EXPRs for each of the sub-graphs rooted at the
1374 conditional block. If the last statement of BB is a conditional
1375 expression of the form 'X op Y', then
1377 a) Remove X and Y from the set FOUND.
1379 b) If the conditional dominates its THEN_CLAUSE sub-graph,
1380 recurse into it. On return, if X and/or Y are marked in
1381 FOUND, then an ASSERT_EXPR is added for the corresponding
1384 c) Repeat step (b) on the ELSE_CLAUSE.
1386 d) Mark X and Y in FOUND.
1388 3- If BB does not end in a conditional expression, then we recurse
1389 into BB's dominator children.
1391 At the end of the recursive traversal, ASSERT_EXPRs will have been
1392 added to the edges of COND_EXPR blocks that have sub-graphs using
1393 one or both predicate operands. For instance,
1400 In this case, an assertion on the THEN clause is useful to
1401 determine that 'a' is always 9 on that edge. However, an assertion
1402 on the ELSE clause would be unnecessary.
1404 On exit from this function, all the names created by the newly
1405 inserted ASSERT_EXPRs need to be added to the SSA web by rewriting
1406 the SSA names that they replace.
1408 TODO. Handle SWITCH_EXPR. */
1411 maybe_add_assert_expr (basic_block bb)
1413 block_stmt_iterator si;
1418 /* Step 1. Mark all the SSA names used in BB in bitmap FOUND. */
1421 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1426 stmt = bsi_stmt (si);
1427 get_stmt_operands (stmt);
1429 /* Mark all the SSA names used by STMT in bitmap FOUND. If STMT
1430 is inside the sub-graph of a conditional block, when we
1431 return from this recursive walk, our parent will use the
1432 FOUND bitset to determine if one of the operands it was
1433 looking for was present in the sub-graph. */
1434 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
1438 SET_BIT (found, SSA_NAME_VERSION (op));
1440 cond = infer_value_range (stmt, op);
1444 /* Step 3. If OP is used in such a way that we can infer a
1445 value range for it, create a new ASSERT_EXPR for OP
1446 (unless OP already has an ASSERT_EXPR). */
1447 gcc_assert (!is_ctrl_stmt (stmt));
1449 if (has_assert_expr (op, cond))
1452 if (!stmt_ends_bb_p (stmt))
1454 /* If STMT does not end the block, we can insert the new
1455 assertion right after it. */
1456 tree t = build_assert_expr_for (cond, op);
1457 bsi_insert_after (&si, t, BSI_NEW_STMT);
1462 /* STMT must be the last statement in BB. We can only
1463 insert new assertions on the non-abnormal edge out of
1464 BB. Note that since STMT is not control flow, there
1465 may only be one non-abnormal edge out of BB. */
1469 FOR_EACH_EDGE (e, ei, bb->succs)
1470 if (!(e->flags & EDGE_ABNORMAL))
1472 tree t = build_assert_expr_for (cond, op);
1473 bsi_insert_on_edge (e, t);
1480 /* Remember the last statement of the block. */
1484 /* Step 3. If BB's last statement is a conditional expression
1485 involving integer operands, recurse into each of the sub-graphs
1486 rooted at BB to determine if we need to add ASSERT_EXPRs.
1487 Notice that we only care about the first operand of the
1488 conditional. Adding assertions for both operands may actually
1489 hinder VRP. FIXME, add example. */
1491 && TREE_CODE (last) == COND_EXPR
1492 && !fp_predicate (COND_EXPR_COND (last))
1493 && NUM_USES (uses = STMT_USE_OPS (last)) > 0)
1499 cond = COND_EXPR_COND (last);
1501 /* Remove the COND_EXPR operand from the FOUND bitmap.
1502 Otherwise, when we finish traversing each of the sub-graphs,
1503 we won't know whether the variables were found in the
1504 sub-graphs or if they had been found in a block upstream from
1506 op = USE_OP (uses, 0);
1507 RESET_BIT (found, SSA_NAME_VERSION (op));
1509 /* Look for uses of the operands in each of the sub-graphs
1510 rooted at BB. We need to check each of the outgoing edges
1511 separately, so that we know what kind of ASSERT_EXPR to
1513 FOR_EACH_EDGE (e, ei, bb->succs)
1515 /* If BB strictly dominates the sub-graph at E->DEST,
1518 && dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1519 added |= maybe_add_assert_expr (e->dest);
1521 /* Once we traversed the sub-graph, check if any block inside
1522 used either of the predicate's operands. If so, add the
1523 appropriate ASSERT_EXPR. */
1524 if (TEST_BIT (found, SSA_NAME_VERSION (op)))
1526 /* We found a use of OP in the sub-graph rooted at
1527 E->DEST. Add an ASSERT_EXPR according to whether
1528 E goes to THEN_CLAUSE or ELSE_CLAUSE. */
1531 if (e->flags & EDGE_TRUE_VALUE)
1532 c = unshare_expr (cond);
1533 else if (e->flags & EDGE_FALSE_VALUE)
1534 c = invert_truthvalue (cond);
1538 t = build_assert_expr_for (c, op);
1539 bsi_insert_on_edge (e, t);
1544 /* Finally, mark all the COND_EXPR operands as found. */
1545 SET_BIT (found, SSA_NAME_VERSION (op));
1549 /* Step 3. Recurse into the dominator children of BB. */
1552 for (son = first_dom_son (CDI_DOMINATORS, bb);
1554 son = next_dom_son (CDI_DOMINATORS, son))
1555 added |= maybe_add_assert_expr (son);
1562 /* Traverse the flowgraph looking for conditional jumps to insert range
1563 expressions. These range expressions are meant to provide information
1564 to optimizations that need to reason in terms of value ranges. They
1565 will not be expanded into RTL. For instance, given:
1574 this pass will transform the code into:
1580 x = ASSERT_EXPR <x, x < y>
1585 y = ASSERT_EXPR <y, x <= y>
1589 The idea is that once copy and constant propagation have run, other
1590 optimizations will be able to determine what ranges of values can 'x'
1591 take in different paths of the code, simply by checking the reaching
1592 definition of 'x'. */
1595 insert_range_assertions (void)
1601 found = sbitmap_alloc (num_ssa_names);
1602 sbitmap_zero (found);
1604 calculate_dominance_info (CDI_DOMINATORS);
1606 update_ssa_p = false;
1607 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1608 if (maybe_add_assert_expr (e->dest))
1609 update_ssa_p = true;
1613 bsi_commit_edge_inserts ();
1614 update_ssa (TODO_update_ssa_no_phi);
1617 if (dump_file && (dump_flags & TDF_DETAILS))
1619 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
1620 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1623 sbitmap_free (found);
1627 /* Convert range assertion expressions into copies. FIXME, explain why. */
1630 remove_range_assertions (void)
1633 block_stmt_iterator si;
1636 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1638 tree stmt = bsi_stmt (si);
1640 if (TREE_CODE (stmt) == MODIFY_EXPR
1641 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1643 tree rhs = TREE_OPERAND (stmt, 1);
1644 tree cond = fold (ASSERT_EXPR_COND (rhs));
1645 gcc_assert (cond != boolean_false_node);
1646 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
1653 /* Return true if STMT is interesting for VRP. */
1656 stmt_interesting_for_vrp (tree stmt)
1658 if (TREE_CODE (stmt) == PHI_NODE
1659 && is_gimple_reg (PHI_RESULT (stmt))
1660 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
1661 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
1663 else if (TREE_CODE (stmt) == MODIFY_EXPR)
1665 tree lhs = TREE_OPERAND (stmt, 0);
1666 stmt_ann_t ann = stmt_ann (stmt);
1668 if (TREE_CODE (lhs) == SSA_NAME
1669 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1670 || POINTER_TYPE_P (TREE_TYPE (lhs)))
1671 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
1672 && NUM_VUSES (VUSE_OPS (ann)) == 0
1673 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
1676 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1683 /* Initialize local data structures for VRP. Return true if VRP
1684 is worth running (i.e. if we found any statements that could
1685 benefit from range information). */
1688 vrp_initialize (void)
1693 /* If we don't find any ASSERT_EXPRs in the code, there's no point
1699 block_stmt_iterator si;
1702 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1704 if (!stmt_interesting_for_vrp (phi))
1706 tree lhs = PHI_RESULT (phi);
1707 set_value_range (get_value_range (lhs), VR_VARYING, 0, 0);
1708 DONT_SIMULATE_AGAIN (phi) = true;
1711 DONT_SIMULATE_AGAIN (phi) = false;
1714 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1716 tree stmt = bsi_stmt (si);
1718 if (!stmt_interesting_for_vrp (stmt))
1722 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
1723 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1724 DONT_SIMULATE_AGAIN (stmt) = true;
1728 if (TREE_CODE (stmt) == MODIFY_EXPR
1729 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1732 DONT_SIMULATE_AGAIN (stmt) = false;
1741 /* Visit assignment STMT. If it produces an interesting range, record
1742 the SSA name in *OUTPUT_P. */
1744 static enum ssa_prop_result
1745 vrp_visit_assignment (tree stmt, tree *output_p)
1750 lhs = TREE_OPERAND (stmt, 0);
1751 rhs = TREE_OPERAND (stmt, 1);
1753 /* We only keep track of ranges in integral and pointer types. */
1754 if (TREE_CODE (lhs) == SSA_NAME
1755 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1756 || POINTER_TYPE_P (TREE_TYPE (lhs))))
1758 value_range *vr, new_vr;
1761 vr = get_value_range (lhs);
1762 extract_range_from_expr (&new_vr, rhs);
1764 /* If STMT is inside a loop, we may be able to know something
1765 else about the range of LHS by examining scalar evolution
1767 if (cfg_loops && (l = loop_containing_stmt (stmt)))
1768 adjust_range_with_scev (&new_vr, l, lhs);
1770 if (update_value_range (vr, new_vr.type, new_vr.min, new_vr.max))
1774 if (dump_file && (dump_flags & TDF_DETAILS))
1776 fprintf (dump_file, "Found new range ");
1777 dump_value_range (dump_file, &new_vr);
1778 fprintf (dump_file, " for ");
1779 print_generic_expr (dump_file, lhs, 0);
1780 fprintf (dump_file, "\n\n");
1783 if (new_vr.type == VR_VARYING)
1784 return SSA_PROP_VARYING;
1786 return SSA_PROP_INTERESTING;
1789 return SSA_PROP_NOT_INTERESTING;
1792 /* Every other statements produces no useful ranges. */
1793 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1794 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1796 return SSA_PROP_VARYING;
1800 /* Given a conditional predicate COND, try to determine if COND yields
1801 true or false based on the value ranges of its operands. */
1804 vrp_evaluate_conditional (tree cond)
1806 gcc_assert (TREE_CODE (cond) == SSA_NAME
1807 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
1809 if (TREE_CODE (cond) == SSA_NAME)
1811 /* For SSA names, only return a truth value if the range is
1812 known and contains exactly one value. */
1813 value_range *vr = SSA_NAME_VALUE_RANGE (cond);
1814 if (vr && vr->type == VR_RANGE && vr->min == vr->max)
1819 /* For comparisons, evaluate each operand and compare their
1822 value_range *vr0, *vr1;
1824 op0 = TREE_OPERAND (cond, 0);
1825 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
1827 op1 = TREE_OPERAND (cond, 1);
1828 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
1831 return compare_ranges (TREE_CODE (cond), vr0, vr1);
1832 else if (vr0 && vr1 == NULL)
1833 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
1834 else if (vr0 == NULL && vr1)
1835 return compare_range_with_value (opposite_comparison (TREE_CODE (cond)),
1839 /* Anything else cannot be computed statically. */
1844 /* Visit conditional statement STMT. If we can determine which edge
1845 will be taken out of STMT's basic block, record it in
1846 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
1847 SSA_PROP_VARYING. */
1849 static enum ssa_prop_result
1850 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
1854 *taken_edge_p = NULL;
1856 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
1857 add ASSERT_EXPRs for them. */
1858 if (TREE_CODE (stmt) == SWITCH_EXPR)
1859 return SSA_PROP_VARYING;
1861 cond = COND_EXPR_COND (stmt);
1863 if (dump_file && (dump_flags & TDF_DETAILS))
1868 fprintf (dump_file, "\nVisiting conditional with predicate: ");
1869 print_generic_expr (dump_file, cond, 0);
1870 fprintf (dump_file, "\nWith known ranges\n");
1872 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
1874 fprintf (dump_file, "\t");
1875 print_generic_expr (dump_file, use, 0);
1876 fprintf (dump_file, ": ");
1877 dump_value_range (dump_file, SSA_NAME_VALUE_RANGE (use));
1880 fprintf (dump_file, "\n");
1883 /* Compute the value of the predicate COND by checking the known
1884 ranges of each of its operands. */
1885 val = vrp_evaluate_conditional (cond);
1887 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
1889 if (dump_file && (dump_flags & TDF_DETAILS))
1891 fprintf (dump_file, "\nPredicate evaluates to: ");
1892 if (val == NULL_TREE)
1893 fprintf (dump_file, "DON'T KNOW\n");
1895 print_generic_stmt (dump_file, val, 0);
1898 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
1902 /* Evaluate statement STMT. If the statement produces a useful range,
1903 return SSA_PROP_INTERESTING and record the SSA name with the
1904 interesting range into *OUTPUT_P.
1906 If STMT is a conditional branch and we can determine its truth
1907 value, the taken edge is recorded in *TAKEN_EDGE_P.
1909 If STMT produces a varying value, return SSA_PROP_VARYING. */
1911 static enum ssa_prop_result
1912 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
1918 if (dump_file && (dump_flags & TDF_DETAILS))
1920 fprintf (dump_file, "\nVisiting statement:\n");
1921 print_generic_stmt (dump_file, stmt, dump_flags);
1922 fprintf (dump_file, "\n");
1925 ann = stmt_ann (stmt);
1926 if (TREE_CODE (stmt) == MODIFY_EXPR
1927 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
1928 && NUM_VUSES (VUSE_OPS (ann)) == 0
1929 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
1930 return vrp_visit_assignment (stmt, output_p);
1931 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1932 return vrp_visit_cond_stmt (stmt, taken_edge_p);
1934 /* All other statements produce nothing of interest for VRP, so mark
1935 their outputs varying and prevent further simulation. */
1936 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1937 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1939 return SSA_PROP_VARYING;
1943 /* Meet operation for value ranges. Given two value ranges VR0 and
1944 VR1, store in VR0 the result of meeting VR0 and VR1.
1946 The meeting rules are as follows:
1948 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
1950 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
1951 union of VR0 and VR1. */
1954 vrp_meet (value_range *vr0, value_range *vr1)
1956 if (vr0->type == VR_UNDEFINED)
1962 if (vr1->type == VR_UNDEFINED)
1964 /* Nothing to do. VR0 already has the resulting range. */
1968 if (vr0->type == VR_VARYING)
1970 /* Nothing to do. VR0 already has the resulting range. */
1974 if (vr1->type == VR_VARYING)
1980 /* If either is a symbolic range, drop to VARYING. */
1981 if (symbolic_range_p (vr0) || symbolic_range_p (vr1))
1983 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
1987 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
1989 /* If VR0 and VR1 have a non-empty intersection, compute the
1990 union of both ranges. */
1991 if (value_ranges_intersect_p (vr0, vr1))
1998 /* The lower limit of the new range is the minimum of the
2000 if (compare_values (vr0->min, vr1->min) == 1)
2003 /* The upper limit of the new range is the maximium of the
2005 if (compare_values (vr0->max, vr1->max) == -1)
2008 set_value_range (vr0, vr0->type, min, max);
2012 /* The two ranges don't intersect, set the result to VR_VARYING. */
2013 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2016 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
2018 /* Two anti-ranges meet only if they are both identical. */
2019 if (compare_values (vr0->min, vr1->min) == 0
2020 && compare_values (vr0->max, vr1->max) == 0
2021 && compare_values (vr0->min, vr0->max) == 0)
2022 /* Nothing to do. */ ;
2024 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2026 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
2028 /* A range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] meet
2029 only if the ranges have an empty intersection. The result of
2030 the meet operation is the anti-range. */
2031 if (!value_ranges_intersect_p (vr0, vr1))
2033 if (vr1->type == VR_ANTI_RANGE)
2037 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2044 /* Visit all arguments for PHI node PHI that flow through executable
2045 edges. If a valid value range can be derived from all the incoming
2046 value ranges, set a new range for the LHS of PHI. */
2048 static enum ssa_prop_result
2049 vrp_visit_phi_node (tree phi)
2052 tree lhs = PHI_RESULT (phi);
2053 value_range *lhs_vr = get_value_range (lhs);
2054 value_range vr_result = *lhs_vr;
2056 if (dump_file && (dump_flags & TDF_DETAILS))
2058 fprintf (dump_file, "\nVisiting PHI node: ");
2059 print_generic_expr (dump_file, phi, dump_flags);
2062 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2064 edge e = PHI_ARG_EDGE (phi, i);
2066 if (dump_file && (dump_flags & TDF_DETAILS))
2069 "\n Argument #%d (%d -> %d %sexecutable)\n",
2070 i, e->src->index, e->dest->index,
2071 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
2074 if (e->flags & EDGE_EXECUTABLE)
2076 tree arg = PHI_ARG_DEF (phi, i);
2079 if (TREE_CODE (arg) == SSA_NAME)
2080 vr_arg = *(get_value_range (arg));
2083 vr_arg.type = VR_RANGE;
2088 if (dump_file && (dump_flags & TDF_DETAILS))
2090 fprintf (dump_file, "\t");
2091 print_generic_expr (dump_file, arg, dump_flags);
2092 fprintf (dump_file, "\n\tValue: ");
2093 dump_value_range (dump_file, &vr_arg);
2094 fprintf (dump_file, "\n");
2097 vrp_meet (&vr_result, &vr_arg);
2099 if (vr_result.type == VR_VARYING)
2104 if (vr_result.type == VR_VARYING)
2106 set_value_range (lhs_vr, VR_VARYING, 0, 0);
2107 return SSA_PROP_VARYING;
2110 /* To prevent infinite iterations in the algorithm, derive ranges
2111 when the new value is slightly bigger or smaller than the
2113 if (lhs_vr->type == VR_RANGE)
2115 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
2117 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
2118 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
2120 /* If the new minimum is smaller or larger than the previous
2121 one, go all the way to -INF. In the first case, to avoid
2122 iterating millions of times to reach -INF, and in the
2123 other case to avoid infinite bouncing between different
2125 if (cmp_min > 0 || cmp_min < 0)
2126 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
2128 /* Similarly, if the new maximum is smaller or larger than
2129 the previous one, go all the way to +INF. */
2130 if (cmp_max < 0 || cmp_max > 0)
2131 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
2133 /* If we ended up with a (-INF, +INF) range, set it to
2135 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
2136 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
2138 set_value_range (lhs_vr, VR_VARYING, 0, 0);
2139 return SSA_PROP_VARYING;
2144 /* If the new range is different than the previous value, keep
2146 if (update_value_range (lhs_vr, vr_result.type, vr_result.min, vr_result.max))
2147 return SSA_PROP_INTERESTING;
2149 /* Nothing changed, don't add outgoing edges. */
2150 return SSA_PROP_NOT_INTERESTING;
2154 /* Traverse all the blocks folding conditionals with known ranges. */
2160 int num_pred_folded = 0;
2164 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
2165 dump_all_value_ranges (dump_file);
2166 fprintf (dump_file, "\n");
2171 tree last = last_stmt (bb);
2172 if (last && TREE_CODE (last) == COND_EXPR)
2174 tree val = vrp_evaluate_conditional (COND_EXPR_COND (last));
2179 fprintf (dump_file, "Folding predicate ");
2180 print_generic_expr (dump_file, COND_EXPR_COND (last), 0);
2181 fprintf (dump_file, " to ");
2182 print_generic_expr (dump_file, val, 0);
2183 fprintf (dump_file, "\n");
2187 COND_EXPR_COND (last) = val;
2193 if (dump_file && (dump_flags & TDF_STATS))
2194 fprintf (dump_file, "\nNumber of predicates folded: %d\n\n",
2199 /* Main entry point to VRP (Value Range Propagation). This pass is
2200 loosely based on J. R. C. Patterson, ``Accurate Static Branch
2201 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
2202 Programming Language Design and Implementation, pp. 67-78, 1995.
2203 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
2205 This is essentially an SSA-CCP pass modified to deal with ranges
2206 instead of constants.
2208 TODO, the main difference between this pass and Patterson's is that
2209 we do not propagate edge probabilities. We only compute whether
2210 edges can be taken or not. That is, instead of having a spectrum
2211 of jump probabilities between 0 and 1, we only deal with 0, 1 and
2212 DON'T KNOW. In the future, it may be worthwhile to propagate
2213 probabilities to aid branch prediction. */
2218 insert_range_assertions ();
2220 cfg_loops = loop_optimizer_init (NULL);
2222 scev_initialize (cfg_loops);
2224 if (vrp_initialize ())
2226 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
2233 loop_optimizer_finalize (cfg_loops, NULL);
2234 current_loops = NULL;
2237 remove_range_assertions ();
2243 return flag_tree_vrp != 0;
2246 struct tree_opt_pass pass_vrp =
2249 gate_vrp, /* gate */
2250 execute_vrp, /* execute */
2253 0, /* static_pass_number */
2254 TV_TREE_VRP, /* tv_id */
2255 PROP_ssa | PROP_alias, /* properties_required */
2256 0, /* properties_provided */
2257 0, /* properties_destroyed */
2258 0, /* todo_flags_start */
2263 | TODO_update_ssa, /* todo_flags_finish */