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 /* Do not attempt to infer anything in names that flow through
1285 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1288 if (POINTER_TYPE_P (TREE_TYPE (op)))
1291 unsigned num_uses, num_derefs;
1293 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
1294 if (num_derefs > 0 && flag_delete_null_pointer_checks)
1296 /* We can only assume that a pointer dereference will yield
1297 non-NULL if -fdelete-null-pointer-checks is enabled. */
1298 tree null = build_int_cst (TREE_TYPE (op), 0);
1299 tree t = build (NE_EXPR, boolean_type_node, op, null);
1308 /* Return true if OP is the result of an ASSERT_EXPR that tests the
1309 same condition as COND. */
1312 has_assert_expr (tree op, tree cond)
1314 tree def_stmt = SSA_NAME_DEF_STMT (op);
1315 tree assert_expr, other_cond, other_op;
1317 /* If OP was not generated by an ASSERT_EXPR, return false. */
1318 if (TREE_CODE (def_stmt) != MODIFY_EXPR
1319 || TREE_CODE (TREE_OPERAND (def_stmt, 1)) != ASSERT_EXPR)
1322 assert_expr = TREE_OPERAND (def_stmt, 1);
1323 other_cond = ASSERT_EXPR_COND (assert_expr);
1324 other_op = ASSERT_EXPR_VAR (assert_expr);
1326 if (TREE_CODE (cond) == TREE_CODE (other_cond))
1330 /* If COND is not a comparison predicate, something is wrong. */
1331 gcc_assert (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
1333 /* Note that we only need to compare against one of the operands
1336 Suppose that we are about to insert the assertion ASSERT_EXPR
1337 <x_4, x_4 != 0> and the defining statement for x_4 is x_4 =
1338 ASSERT_EXPR <x_3, x_3 != 0>.
1340 In this case, we don't really want to insert a new
1341 ASSERT_EXPR for x_4 because that would be redundant. We
1342 already know that x_4 is not 0. So, when comparing the
1343 conditionals 'x_3 != 0' and 'x_4 != 0', we don't want to
1344 compare x_3 and x_4, we just want to compare the predicate's
1345 code (!=) and the other operand (0). */
1346 if (TREE_OPERAND (cond, 0) == op)
1347 t1 = TREE_OPERAND (cond, 1);
1349 t1 = TREE_OPERAND (cond, 0);
1351 if (TREE_OPERAND (other_cond, 0) == other_op)
1352 t2 = TREE_OPERAND (other_cond, 1);
1354 t2 = TREE_OPERAND (other_cond, 0);
1356 return (t1 == t2 || operand_equal_p (t1, t2, 0));
1363 /* Traverse all the statements in block BB looking for used variables.
1364 Variables used in BB are added to bitmap FOUND. The algorithm
1365 works in three main parts:
1367 1- For every statement S in BB, all the variables used by S are
1368 added to bitmap FOUND.
1370 2- If statement S uses an operand N in a way that exposes a known
1371 value range for N, then if N was not already generated by an
1372 ASSERT_EXPR, create a new ASSERT_EXPR for N. For instance, if N
1373 is a pointer and the statement dereferences it, we can assume
1376 3- COND_EXPRs are a special case of #2. We can derive range
1377 information from the predicate but need to insert different
1378 ASSERT_EXPRs for each of the sub-graphs rooted at the
1379 conditional block. If the last statement of BB is a conditional
1380 expression of the form 'X op Y', then
1382 a) Remove X and Y from the set FOUND.
1384 b) If the conditional dominates its THEN_CLAUSE sub-graph,
1385 recurse into it. On return, if X and/or Y are marked in
1386 FOUND, then an ASSERT_EXPR is added for the corresponding
1389 c) Repeat step (b) on the ELSE_CLAUSE.
1391 d) Mark X and Y in FOUND.
1393 4- If BB does not end in a conditional expression, then we recurse
1394 into BB's dominator children.
1396 At the end of the recursive traversal, ASSERT_EXPRs will have been
1397 added to the edges of COND_EXPR blocks that have sub-graphs using
1398 one or both predicate operands. For instance,
1405 In this case, an assertion on the THEN clause is useful to
1406 determine that 'a' is always 9 on that edge. However, an assertion
1407 on the ELSE clause would be unnecessary.
1409 On exit from this function, all the names created by the newly
1410 inserted ASSERT_EXPRs need to be added to the SSA web by rewriting
1411 the SSA names that they replace.
1413 TODO. Handle SWITCH_EXPR. */
1416 maybe_add_assert_expr (basic_block bb)
1418 block_stmt_iterator si;
1423 /* Step 1. Mark all the SSA names used in BB in bitmap FOUND. */
1426 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1431 stmt = bsi_stmt (si);
1432 get_stmt_operands (stmt);
1434 /* Mark all the SSA names used by STMT in bitmap FOUND. If STMT
1435 is inside the sub-graph of a conditional block, when we
1436 return from this recursive walk, our parent will use the
1437 FOUND bitset to determine if one of the operands it was
1438 looking for was present in the sub-graph. */
1439 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
1443 SET_BIT (found, SSA_NAME_VERSION (op));
1445 cond = infer_value_range (stmt, op);
1449 /* Step 2. If OP is used in such a way that we can infer a
1450 value range for it, create a new ASSERT_EXPR for OP
1451 (unless OP already has an ASSERT_EXPR). */
1452 gcc_assert (!is_ctrl_stmt (stmt));
1454 if (has_assert_expr (op, cond))
1457 if (!stmt_ends_bb_p (stmt))
1459 /* If STMT does not end the block, we can insert the new
1460 assertion right after it. */
1461 tree t = build_assert_expr_for (cond, op);
1462 bsi_insert_after (&si, t, BSI_NEW_STMT);
1467 /* STMT must be the last statement in BB. We can only
1468 insert new assertions on the non-abnormal edge out of
1469 BB. Note that since STMT is not control flow, there
1470 may only be one non-abnormal edge out of BB. */
1474 FOR_EACH_EDGE (e, ei, bb->succs)
1475 if (!(e->flags & EDGE_ABNORMAL))
1477 tree t = build_assert_expr_for (cond, op);
1478 bsi_insert_on_edge (e, t);
1485 /* Remember the last statement of the block. */
1489 /* Step 3. If BB's last statement is a conditional expression
1490 involving integer operands, recurse into each of the sub-graphs
1491 rooted at BB to determine if we need to add ASSERT_EXPRs.
1492 Notice that we only care about the first operand of the
1493 conditional. Adding assertions for both operands may actually
1494 hinder VRP. FIXME, add example. */
1496 && TREE_CODE (last) == COND_EXPR
1497 && !fp_predicate (COND_EXPR_COND (last))
1498 && NUM_USES (uses = STMT_USE_OPS (last)) > 0)
1504 cond = COND_EXPR_COND (last);
1506 /* Remove the COND_EXPR operand from the FOUND bitmap.
1507 Otherwise, when we finish traversing each of the sub-graphs,
1508 we won't know whether the variables were found in the
1509 sub-graphs or if they had been found in a block upstream from
1511 op = USE_OP (uses, 0);
1513 /* Do not attempt to infer anything in names that flow through
1515 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1518 RESET_BIT (found, SSA_NAME_VERSION (op));
1520 /* Look for uses of the operands in each of the sub-graphs
1521 rooted at BB. We need to check each of the outgoing edges
1522 separately, so that we know what kind of ASSERT_EXPR to
1524 FOR_EACH_EDGE (e, ei, bb->succs)
1526 /* If BB strictly dominates the sub-graph at E->DEST,
1529 && dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1530 added |= maybe_add_assert_expr (e->dest);
1532 /* Once we traversed the sub-graph, check if any block inside
1533 used either of the predicate's operands. If so, add the
1534 appropriate ASSERT_EXPR. */
1535 if (TEST_BIT (found, SSA_NAME_VERSION (op)))
1537 /* We found a use of OP in the sub-graph rooted at
1538 E->DEST. Add an ASSERT_EXPR according to whether
1539 E goes to THEN_CLAUSE or ELSE_CLAUSE. */
1542 if (e->flags & EDGE_TRUE_VALUE)
1543 c = unshare_expr (cond);
1544 else if (e->flags & EDGE_FALSE_VALUE)
1545 c = invert_truthvalue (cond);
1549 t = build_assert_expr_for (c, op);
1550 bsi_insert_on_edge (e, t);
1555 /* Finally, mark all the COND_EXPR operands as found. */
1556 SET_BIT (found, SSA_NAME_VERSION (op));
1560 /* Step 4. Recurse into the dominator children of BB. */
1563 for (son = first_dom_son (CDI_DOMINATORS, bb);
1565 son = next_dom_son (CDI_DOMINATORS, son))
1566 added |= maybe_add_assert_expr (son);
1573 /* Traverse the flowgraph looking for conditional jumps to insert range
1574 expressions. These range expressions are meant to provide information
1575 to optimizations that need to reason in terms of value ranges. They
1576 will not be expanded into RTL. For instance, given:
1585 this pass will transform the code into:
1591 x = ASSERT_EXPR <x, x < y>
1596 y = ASSERT_EXPR <y, x <= y>
1600 The idea is that once copy and constant propagation have run, other
1601 optimizations will be able to determine what ranges of values can 'x'
1602 take in different paths of the code, simply by checking the reaching
1603 definition of 'x'. */
1606 insert_range_assertions (void)
1612 found = sbitmap_alloc (num_ssa_names);
1613 sbitmap_zero (found);
1615 calculate_dominance_info (CDI_DOMINATORS);
1617 update_ssa_p = false;
1618 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1619 if (maybe_add_assert_expr (e->dest))
1620 update_ssa_p = true;
1624 bsi_commit_edge_inserts ();
1625 update_ssa (TODO_update_ssa_no_phi);
1628 if (dump_file && (dump_flags & TDF_DETAILS))
1630 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
1631 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1634 sbitmap_free (found);
1638 /* Convert range assertion expressions into copies. FIXME, explain why. */
1641 remove_range_assertions (void)
1644 block_stmt_iterator si;
1647 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1649 tree stmt = bsi_stmt (si);
1651 if (TREE_CODE (stmt) == MODIFY_EXPR
1652 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1654 tree rhs = TREE_OPERAND (stmt, 1);
1655 tree cond = fold (ASSERT_EXPR_COND (rhs));
1656 gcc_assert (cond != boolean_false_node);
1657 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
1664 /* Return true if STMT is interesting for VRP. */
1667 stmt_interesting_for_vrp (tree stmt)
1669 if (TREE_CODE (stmt) == PHI_NODE
1670 && is_gimple_reg (PHI_RESULT (stmt))
1671 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
1672 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
1674 else if (TREE_CODE (stmt) == MODIFY_EXPR)
1676 tree lhs = TREE_OPERAND (stmt, 0);
1677 stmt_ann_t ann = stmt_ann (stmt);
1679 if (TREE_CODE (lhs) == SSA_NAME
1680 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1681 || POINTER_TYPE_P (TREE_TYPE (lhs)))
1682 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
1683 && NUM_VUSES (VUSE_OPS (ann)) == 0
1684 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
1687 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1694 /* Initialize local data structures for VRP. Return true if VRP
1695 is worth running (i.e. if we found any statements that could
1696 benefit from range information). */
1699 vrp_initialize (void)
1704 /* If we don't find any ASSERT_EXPRs in the code, there's no point
1710 block_stmt_iterator si;
1713 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1715 if (!stmt_interesting_for_vrp (phi))
1717 tree lhs = PHI_RESULT (phi);
1718 set_value_range (get_value_range (lhs), VR_VARYING, 0, 0);
1719 DONT_SIMULATE_AGAIN (phi) = true;
1722 DONT_SIMULATE_AGAIN (phi) = false;
1725 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1727 tree stmt = bsi_stmt (si);
1729 if (!stmt_interesting_for_vrp (stmt))
1733 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
1734 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1735 DONT_SIMULATE_AGAIN (stmt) = true;
1739 if (TREE_CODE (stmt) == MODIFY_EXPR
1740 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1743 DONT_SIMULATE_AGAIN (stmt) = false;
1752 /* Visit assignment STMT. If it produces an interesting range, record
1753 the SSA name in *OUTPUT_P. */
1755 static enum ssa_prop_result
1756 vrp_visit_assignment (tree stmt, tree *output_p)
1761 lhs = TREE_OPERAND (stmt, 0);
1762 rhs = TREE_OPERAND (stmt, 1);
1764 /* We only keep track of ranges in integral and pointer types. */
1765 if (TREE_CODE (lhs) == SSA_NAME
1766 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1767 || POINTER_TYPE_P (TREE_TYPE (lhs))))
1769 value_range *vr, new_vr;
1772 vr = get_value_range (lhs);
1773 extract_range_from_expr (&new_vr, rhs);
1775 /* If STMT is inside a loop, we may be able to know something
1776 else about the range of LHS by examining scalar evolution
1778 if (cfg_loops && (l = loop_containing_stmt (stmt)))
1779 adjust_range_with_scev (&new_vr, l, lhs);
1781 if (update_value_range (vr, new_vr.type, new_vr.min, new_vr.max))
1785 if (dump_file && (dump_flags & TDF_DETAILS))
1787 fprintf (dump_file, "Found new range ");
1788 dump_value_range (dump_file, &new_vr);
1789 fprintf (dump_file, " for ");
1790 print_generic_expr (dump_file, lhs, 0);
1791 fprintf (dump_file, "\n\n");
1794 if (new_vr.type == VR_VARYING)
1795 return SSA_PROP_VARYING;
1797 return SSA_PROP_INTERESTING;
1800 return SSA_PROP_NOT_INTERESTING;
1803 /* Every other statements produces no useful ranges. */
1804 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1805 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1807 return SSA_PROP_VARYING;
1811 /* Given a conditional predicate COND, try to determine if COND yields
1812 true or false based on the value ranges of its operands. */
1815 vrp_evaluate_conditional (tree cond)
1817 gcc_assert (TREE_CODE (cond) == SSA_NAME
1818 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
1820 if (TREE_CODE (cond) == SSA_NAME)
1822 /* For SSA names, only return a truth value if the range is
1823 known and contains exactly one value. */
1824 value_range *vr = SSA_NAME_VALUE_RANGE (cond);
1825 if (vr && vr->type == VR_RANGE && vr->min == vr->max)
1830 /* For comparisons, evaluate each operand and compare their
1833 value_range *vr0, *vr1;
1835 op0 = TREE_OPERAND (cond, 0);
1836 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
1838 op1 = TREE_OPERAND (cond, 1);
1839 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
1842 return compare_ranges (TREE_CODE (cond), vr0, vr1);
1843 else if (vr0 && vr1 == NULL)
1844 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
1845 else if (vr0 == NULL && vr1)
1846 return compare_range_with_value (opposite_comparison (TREE_CODE (cond)),
1850 /* Anything else cannot be computed statically. */
1855 /* Visit conditional statement STMT. If we can determine which edge
1856 will be taken out of STMT's basic block, record it in
1857 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
1858 SSA_PROP_VARYING. */
1860 static enum ssa_prop_result
1861 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
1865 *taken_edge_p = NULL;
1867 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
1868 add ASSERT_EXPRs for them. */
1869 if (TREE_CODE (stmt) == SWITCH_EXPR)
1870 return SSA_PROP_VARYING;
1872 cond = COND_EXPR_COND (stmt);
1874 if (dump_file && (dump_flags & TDF_DETAILS))
1879 fprintf (dump_file, "\nVisiting conditional with predicate: ");
1880 print_generic_expr (dump_file, cond, 0);
1881 fprintf (dump_file, "\nWith known ranges\n");
1883 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
1885 fprintf (dump_file, "\t");
1886 print_generic_expr (dump_file, use, 0);
1887 fprintf (dump_file, ": ");
1888 dump_value_range (dump_file, SSA_NAME_VALUE_RANGE (use));
1891 fprintf (dump_file, "\n");
1894 /* Compute the value of the predicate COND by checking the known
1895 ranges of each of its operands. */
1896 val = vrp_evaluate_conditional (cond);
1898 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
1900 if (dump_file && (dump_flags & TDF_DETAILS))
1902 fprintf (dump_file, "\nPredicate evaluates to: ");
1903 if (val == NULL_TREE)
1904 fprintf (dump_file, "DON'T KNOW\n");
1906 print_generic_stmt (dump_file, val, 0);
1909 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
1913 /* Evaluate statement STMT. If the statement produces a useful range,
1914 return SSA_PROP_INTERESTING and record the SSA name with the
1915 interesting range into *OUTPUT_P.
1917 If STMT is a conditional branch and we can determine its truth
1918 value, the taken edge is recorded in *TAKEN_EDGE_P.
1920 If STMT produces a varying value, return SSA_PROP_VARYING. */
1922 static enum ssa_prop_result
1923 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
1929 if (dump_file && (dump_flags & TDF_DETAILS))
1931 fprintf (dump_file, "\nVisiting statement:\n");
1932 print_generic_stmt (dump_file, stmt, dump_flags);
1933 fprintf (dump_file, "\n");
1936 ann = stmt_ann (stmt);
1937 if (TREE_CODE (stmt) == MODIFY_EXPR
1938 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
1939 && NUM_VUSES (VUSE_OPS (ann)) == 0
1940 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
1941 return vrp_visit_assignment (stmt, output_p);
1942 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1943 return vrp_visit_cond_stmt (stmt, taken_edge_p);
1945 /* All other statements produce nothing of interest for VRP, so mark
1946 their outputs varying and prevent further simulation. */
1947 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1948 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1950 return SSA_PROP_VARYING;
1954 /* Meet operation for value ranges. Given two value ranges VR0 and
1955 VR1, store in VR0 the result of meeting VR0 and VR1.
1957 The meeting rules are as follows:
1959 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
1961 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
1962 union of VR0 and VR1. */
1965 vrp_meet (value_range *vr0, value_range *vr1)
1967 if (vr0->type == VR_UNDEFINED)
1973 if (vr1->type == VR_UNDEFINED)
1975 /* Nothing to do. VR0 already has the resulting range. */
1979 if (vr0->type == VR_VARYING)
1981 /* Nothing to do. VR0 already has the resulting range. */
1985 if (vr1->type == VR_VARYING)
1991 /* If either is a symbolic range, drop to VARYING. */
1992 if (symbolic_range_p (vr0) || symbolic_range_p (vr1))
1994 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
1998 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
2000 /* If VR0 and VR1 have a non-empty intersection, compute the
2001 union of both ranges. */
2002 if (value_ranges_intersect_p (vr0, vr1))
2009 /* The lower limit of the new range is the minimum of the
2011 if (compare_values (vr0->min, vr1->min) == 1)
2014 /* The upper limit of the new range is the maximum of the
2016 if (compare_values (vr0->max, vr1->max) == -1)
2019 set_value_range (vr0, vr0->type, min, max);
2023 /* The two ranges don't intersect, set the result to VR_VARYING. */
2024 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2027 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
2029 /* Two anti-ranges meet only if they are both identical. */
2030 if (compare_values (vr0->min, vr1->min) == 0
2031 && compare_values (vr0->max, vr1->max) == 0
2032 && compare_values (vr0->min, vr0->max) == 0)
2033 /* Nothing to do. */ ;
2035 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2037 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
2039 /* A range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] meet
2040 only if the ranges have an empty intersection. The result of
2041 the meet operation is the anti-range. */
2042 if (!value_ranges_intersect_p (vr0, vr1))
2044 if (vr1->type == VR_ANTI_RANGE)
2048 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2055 /* Visit all arguments for PHI node PHI that flow through executable
2056 edges. If a valid value range can be derived from all the incoming
2057 value ranges, set a new range for the LHS of PHI. */
2059 static enum ssa_prop_result
2060 vrp_visit_phi_node (tree phi)
2063 tree lhs = PHI_RESULT (phi);
2064 value_range *lhs_vr = get_value_range (lhs);
2065 value_range vr_result = *lhs_vr;
2067 if (dump_file && (dump_flags & TDF_DETAILS))
2069 fprintf (dump_file, "\nVisiting PHI node: ");
2070 print_generic_expr (dump_file, phi, dump_flags);
2073 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2075 edge e = PHI_ARG_EDGE (phi, i);
2077 if (dump_file && (dump_flags & TDF_DETAILS))
2080 "\n Argument #%d (%d -> %d %sexecutable)\n",
2081 i, e->src->index, e->dest->index,
2082 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
2085 if (e->flags & EDGE_EXECUTABLE)
2087 tree arg = PHI_ARG_DEF (phi, i);
2090 if (TREE_CODE (arg) == SSA_NAME)
2091 vr_arg = *(get_value_range (arg));
2094 vr_arg.type = VR_RANGE;
2099 if (dump_file && (dump_flags & TDF_DETAILS))
2101 fprintf (dump_file, "\t");
2102 print_generic_expr (dump_file, arg, dump_flags);
2103 fprintf (dump_file, "\n\tValue: ");
2104 dump_value_range (dump_file, &vr_arg);
2105 fprintf (dump_file, "\n");
2108 vrp_meet (&vr_result, &vr_arg);
2110 if (vr_result.type == VR_VARYING)
2115 if (vr_result.type == VR_VARYING)
2117 set_value_range (lhs_vr, VR_VARYING, 0, 0);
2118 return SSA_PROP_VARYING;
2121 /* To prevent infinite iterations in the algorithm, derive ranges
2122 when the new value is slightly bigger or smaller than the
2124 if (lhs_vr->type == VR_RANGE)
2126 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
2128 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
2129 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
2131 /* If the new minimum is smaller or larger than the previous
2132 one, go all the way to -INF. In the first case, to avoid
2133 iterating millions of times to reach -INF, and in the
2134 other case to avoid infinite bouncing between different
2136 if (cmp_min > 0 || cmp_min < 0)
2137 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
2139 /* Similarly, if the new maximum is smaller or larger than
2140 the previous one, go all the way to +INF. */
2141 if (cmp_max < 0 || cmp_max > 0)
2142 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
2144 /* If we ended up with a (-INF, +INF) range, set it to
2146 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
2147 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
2149 set_value_range (lhs_vr, VR_VARYING, 0, 0);
2150 return SSA_PROP_VARYING;
2155 /* If the new range is different than the previous value, keep
2157 if (update_value_range (lhs_vr, vr_result.type, vr_result.min, vr_result.max))
2158 return SSA_PROP_INTERESTING;
2160 /* Nothing changed, don't add outgoing edges. */
2161 return SSA_PROP_NOT_INTERESTING;
2165 /* Traverse all the blocks folding conditionals with known ranges. */
2171 int num_pred_folded = 0;
2175 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
2176 dump_all_value_ranges (dump_file);
2177 fprintf (dump_file, "\n");
2182 tree last = last_stmt (bb);
2183 if (last && TREE_CODE (last) == COND_EXPR)
2185 tree val = vrp_evaluate_conditional (COND_EXPR_COND (last));
2190 fprintf (dump_file, "Folding predicate ");
2191 print_generic_expr (dump_file, COND_EXPR_COND (last), 0);
2192 fprintf (dump_file, " to ");
2193 print_generic_expr (dump_file, val, 0);
2194 fprintf (dump_file, "\n");
2198 COND_EXPR_COND (last) = val;
2204 if (dump_file && (dump_flags & TDF_STATS))
2205 fprintf (dump_file, "\nNumber of predicates folded: %d\n\n",
2210 /* Main entry point to VRP (Value Range Propagation). This pass is
2211 loosely based on J. R. C. Patterson, ``Accurate Static Branch
2212 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
2213 Programming Language Design and Implementation, pp. 67-78, 1995.
2214 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
2216 This is essentially an SSA-CCP pass modified to deal with ranges
2217 instead of constants.
2219 TODO, the main difference between this pass and Patterson's is that
2220 we do not propagate edge probabilities. We only compute whether
2221 edges can be taken or not. That is, instead of having a spectrum
2222 of jump probabilities between 0 and 1, we only deal with 0, 1 and
2223 DON'T KNOW. In the future, it may be worthwhile to propagate
2224 probabilities to aid branch prediction. */
2229 insert_range_assertions ();
2231 cfg_loops = loop_optimizer_init (NULL);
2233 scev_initialize (cfg_loops);
2235 if (vrp_initialize ())
2237 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
2244 loop_optimizer_finalize (cfg_loops, NULL);
2245 current_loops = NULL;
2248 remove_range_assertions ();
2254 return flag_tree_vrp != 0;
2257 struct tree_opt_pass pass_vrp =
2260 gate_vrp, /* gate */
2261 execute_vrp, /* execute */
2264 0, /* static_pass_number */
2265 TV_TREE_VRP, /* tv_id */
2266 PROP_ssa | PROP_alias, /* properties_required */
2267 0, /* properties_provided */
2268 0, /* properties_destroyed */
2269 0, /* todo_flags_start */
2274 | TODO_update_ssa, /* todo_flags_finish */