1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "tree-dump.h"
34 #include "diagnostic.h"
36 #include "tree-scalar-evolution.h"
37 #include "tree-ssa-propagate.h"
38 #include "tree-chrec.h"
40 /* Set of SSA names found during the dominator traversal of a
41 sub-graph in maybe_add_assert_expr. */
44 /* Loop structure of the program. Used to analyze scalar evolutions
45 inside adjust_range_with_scev. */
46 static struct loops *cfg_loops;
48 /* Local functions. */
49 static int compare_values (tree val1, tree val2);
51 /* Given a conditional predicate COND that has WHICH as one of its
52 operands, return the other operand. No error checking is done.
53 This helper assumes that COND is a comparison and WHICH is one of
57 get_opposite_operand (tree cond, tree which)
59 if (TREE_OPERAND (cond, 0) == which)
60 return TREE_OPERAND (cond, 1);
62 return TREE_OPERAND (cond, 0);
66 /* Given a comparison code, return its opposite. Note that this is *not*
67 the same as inverting its truth value (invert_tree_comparison). Here we
68 just want to literally flip the comparison around.
70 So, '<' gets '>', '<=' gets '>='. Both '==' and '!=' are returned
74 opposite_comparison (enum tree_code code)
107 /* Set value range VR to {T, MIN, MAX}. */
110 set_value_range (value_range *vr, enum value_range_type t, tree min, tree max)
112 #if defined ENABLE_CHECKING
113 if (t == VR_RANGE || t == VR_ANTI_RANGE)
117 gcc_assert (min && max);
119 if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
120 gcc_assert (min != TYPE_MIN_VALUE (TREE_TYPE (min))
121 || max != TYPE_MAX_VALUE (TREE_TYPE (max)));
123 cmp = compare_values (min, max);
124 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
129 && INTEGRAL_TYPE_P (TREE_TYPE (min))
130 && min == TYPE_MIN_VALUE (TREE_TYPE (min))
131 && max == TYPE_MAX_VALUE (TREE_TYPE (max)))
133 /* Ranges that cover all the possible values for the type decay
135 vr->type = VR_VARYING;
147 /* Similar to set_value_range but return true if any field of VR
148 changed from its previous value. */
151 update_value_range (value_range *vr, enum value_range_type t, tree min,
154 bool is_new = vr->type != t || vr->min != min || vr->max != max;
156 set_value_range (vr, t, min, max);
162 /* Return value range information for VAR. Create an empty range if
166 get_value_range (tree var)
171 vr = SSA_NAME_VALUE_RANGE (var);
175 /* Create a default value range. */
176 vr = ggc_alloc (sizeof (*vr));
177 memset ((void *) vr, 0, sizeof (*vr));
178 SSA_NAME_VALUE_RANGE (var) = vr;
180 /* If VAR is a default definition for a PARM_DECL, then we have to
181 assume a VARYING range for it. */
182 sym = SSA_NAME_VAR (var);
183 if (TREE_CODE (sym) == PARM_DECL && var == var_ann (sym)->default_def)
184 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
190 /* Return true if value range VR involves at least one symbol. */
193 symbolic_range_p (value_range *vr)
195 return (!is_gimple_min_invariant (vr->min)
196 || !is_gimple_min_invariant (vr->max));
200 /* Return true if EXPR computes a non-zero value. */
203 expr_computes_nonzero (tree expr)
205 /* Type casts won't change anything, so just strip it. */
208 /* Calling alloca, guarantees that the value is non-NULL. */
209 if (alloca_call_p (expr))
212 /* The address of a non-weak symbol is never NULL, unless the user
213 has requested not to remove NULL pointer checks. */
214 if (flag_delete_null_pointer_checks
215 && TREE_CODE (expr) == ADDR_EXPR
216 && DECL_P (TREE_OPERAND (expr, 0))
217 && !DECL_WEAK (TREE_OPERAND (expr, 0)))
220 /* IOR of any value with a nonzero value will result in a nonzero
222 if (TREE_CODE (expr) == BIT_IOR_EXPR
223 && integer_nonzerop (TREE_OPERAND (expr, 1)))
230 /* Return true if VR is ~[0, 0]. */
233 range_is_nonnull (value_range *vr)
235 return vr->type == VR_ANTI_RANGE
236 && integer_zerop (vr->min)
237 && integer_zerop (vr->max);
241 /* Return true if VR is [0, 0]. */
244 range_is_null (value_range *vr)
246 return vr->type == VR_RANGE
247 && integer_zerop (vr->min)
248 && integer_zerop (vr->max);
252 /* Set value range VR to a non-NULL range of type TYPE. */
255 set_value_range_to_nonnull (value_range *vr, tree type)
257 tree zero = build_int_cst (type, 0);
258 set_value_range (vr, VR_ANTI_RANGE, zero, zero);
262 /* Set value range VR to a NULL range of type TYPE. */
265 set_value_range_to_null (value_range *vr, tree type)
267 tree zero = build_int_cst (type, 0);
268 set_value_range (vr, VR_RANGE, zero, zero);
272 /* Compare two values VAL1 and VAL2. Return
274 -2 if VAL1 and VAL2 cannot be compared at compile-time,
277 +1 if VAL1 > VAL2, and
280 This is similar to tree_int_cst_compare but supports pointer values
281 and values that cannot be compared at compile time. */
284 compare_values (tree val1, tree val2)
289 /* Do some limited symbolic comparisons. */
290 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));
833 else if (TREE_CODE (expr) == INTEGER_CST)
834 set_value_range (vr, VR_RANGE, expr, expr);
836 set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
840 /* Given a range VR, a loop L and a variable VAR, determine whether it
841 would be profitable to adjust VR using scalar evolution information
842 for VAR. If so, update VR with the new limits. */
845 adjust_range_with_scev (value_range *vr, struct loop *l, tree var)
847 tree init, step, chrec;
850 /* TODO. Don't adjust anti-ranges. An anti-range may provide
851 better opportunities than a regular range, but I'm not sure. */
852 if (vr->type == VR_ANTI_RANGE)
855 chrec = analyze_scalar_evolution (l, var);
856 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
859 init = CHREC_LEFT (chrec);
860 step = CHREC_RIGHT (chrec);
862 /* If STEP is symbolic, we can't know whether INIT will be the
863 minimum or maximum value in the range. */
864 if (!is_gimple_min_invariant (step))
867 /* FIXME. When dealing with unsigned types,
868 analyze_scalar_evolution sets STEP to very large unsigned values
869 when the evolution goes backwards. This confuses this analysis
870 because we think that INIT is the smallest value that the range
871 can take, instead of the largest. Ignore these chrecs for now. */
872 if (INTEGRAL_TYPE_P (TREE_TYPE (step)) && TYPE_UNSIGNED (TREE_TYPE (step)))
875 /* If STEP is negative, then INIT is the maximum value the range
876 will take. Otherwise, INIT is the minimum value. */
877 init_is_max = (tree_int_cst_sgn (step) < 0);
879 if (!POINTER_TYPE_P (TREE_TYPE (init))
880 && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
882 /* For VARYING or UNDEFINED ranges, just about anything we get
883 from scalar evolutions should be better. */
885 set_value_range (vr, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (init)), init);
887 set_value_range (vr, VR_RANGE, init, TYPE_MAX_VALUE (TREE_TYPE (init)));
889 else if (vr->type == VR_RANGE)
893 /* INIT is the maximum value. If INIT is lower than
894 VR->MAX, set VR->MAX to INIT. */
895 if (compare_values (init, vr->max) == -1)
896 set_value_range (vr, VR_RANGE, vr->min, init);
900 /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
901 if (compare_values (init, vr->min) == 1)
902 set_value_range (vr, VR_RANGE, init, vr->max);
908 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
910 - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for all the
911 values in the ranges.
913 - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
915 - Return NULL_TREE if it is not always possible to determine the value of
919 compare_ranges (enum tree_code comp, value_range *vr0, value_range *vr1)
921 /* VARYING or UNDEFINED ranges cannot be compared. */
922 if (vr0->type == VR_VARYING
923 || vr0->type == VR_UNDEFINED
924 || vr1->type == VR_VARYING
925 || vr1->type == VR_UNDEFINED)
928 /* Anti-ranges need to be handled separately. */
929 if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
931 /* If both are anti-ranges, then we cannot compute any
933 if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
936 /* These comparisons are never statically computable. */
943 /* Equality can be computed only between a range and an
944 anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */
945 if (vr0->type == VR_RANGE)
947 /* To simplify processing, make VR0 the anti-range. */
948 value_range *tmp = vr0;
953 gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
955 if (compare_values (vr0->min, vr1->min) == 0
956 && compare_values (vr0->max, vr1->max) == 0)
957 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
962 /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
963 operands around and change the comparison code. */
964 if (comp == GT_EXPR || comp == GE_EXPR)
967 comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
975 /* Equality may only be computed if both ranges represent
976 exactly one value. */
977 if (compare_values (vr0->min, vr0->max) == 0
978 && compare_values (vr1->min, vr1->max) == 0)
980 int cmp_min = compare_values (vr0->min, vr1->min);
981 int cmp_max = compare_values (vr0->max, vr1->max);
982 if (cmp_min == 0 && cmp_max == 0)
983 return boolean_true_node;
984 else if (cmp_min != -2 && cmp_max != -2)
985 return boolean_false_node;
990 else if (comp == NE_EXPR)
994 /* If VR0 is completely to the left or completely to the right
995 of VR1, they are always different. Notice that we need to
996 make sure that both comparisons yield similar results to
997 avoid comparing values that cannot be compared at
999 cmp1 = compare_values (vr0->max, vr1->min);
1000 cmp2 = compare_values (vr0->min, vr1->max);
1001 if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
1002 return boolean_true_node;
1004 /* If VR0 and VR1 represent a single value and are identical,
1006 else if (compare_values (vr0->min, vr0->max) == 0
1007 && compare_values (vr1->min, vr1->max) == 0
1008 && compare_values (vr0->min, vr1->min) == 0
1009 && compare_values (vr0->max, vr1->max) == 0)
1010 return boolean_false_node;
1012 /* Otherwise, they may or may not be different. */
1016 else if (comp == LT_EXPR || comp == LE_EXPR)
1020 /* If VR0 is to the left of VR1, return true. */
1021 tst = compare_values (vr0->max, vr1->min);
1022 if ((comp == LT_EXPR && tst == -1)
1023 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1024 return boolean_true_node;
1026 /* If VR0 is to the right of VR1, return false. */
1027 tst = compare_values (vr0->min, vr1->max);
1028 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1029 || (comp == LE_EXPR && tst == 1))
1030 return boolean_false_node;
1032 /* Otherwise, we don't know. */
1040 /* Given a value range VR, a value VAL and a comparison code COMP, return
1041 BOOLEAN_TRUE_NODE if VR COMP VR1 always returns true for all the
1042 values in VR. Return BOOLEAN_FALSE_NODE if the comparison
1043 always returns false. Return NULL_TREE if it is not always
1044 possible to determine the value of the comparison. */
1047 compare_range_with_value (enum tree_code comp, value_range *vr, tree val)
1049 if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
1052 /* Anti-ranges need to be handled separately. */
1053 if (vr->type == VR_ANTI_RANGE)
1055 /* For anti-ranges, the only predicates that we can compute at
1056 compile time are equality and inequality. */
1063 /* ~[VAL, VAL] == VAL is always false. */
1064 if (compare_values (vr->min, val) == 0
1065 && compare_values (vr->max, val) == 0)
1066 return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
1071 if (comp == EQ_EXPR)
1073 /* EQ_EXPR may only be computed if VR represents exactly
1075 if (compare_values (vr->min, vr->max) == 0)
1077 int cmp = compare_values (vr->min, val);
1079 return boolean_true_node;
1080 else if (cmp == -1 || cmp == 1 || cmp == 2)
1081 return boolean_false_node;
1086 else if (comp == NE_EXPR)
1088 /* If VAL is not inside VR, then they are always different. */
1089 if (compare_values (vr->max, val) == -1
1090 || compare_values (vr->min, val) == 1)
1091 return boolean_true_node;
1093 /* If VR represents exactly one value equal to VAL, then return
1095 if (compare_values (vr->min, vr->max) == 0
1096 && compare_values (vr->min, val) == 0)
1097 return boolean_false_node;
1099 /* Otherwise, they may or may not be different. */
1102 else if (comp == LT_EXPR || comp == LE_EXPR)
1106 /* If VR is to the left of VAL, return true. */
1107 tst = compare_values (vr->max, val);
1108 if ((comp == LT_EXPR && tst == -1)
1109 || (comp == LE_EXPR && (tst == -1 || tst == 0)))
1110 return boolean_true_node;
1112 /* If VR is to the right of VAL, return false. */
1113 tst = compare_values (vr->min, val);
1114 if ((comp == LT_EXPR && (tst == 0 || tst == 1))
1115 || (comp == LE_EXPR && tst == 1))
1116 return boolean_false_node;
1118 /* Otherwise, we don't know. */
1121 else if (comp == GT_EXPR || comp == GE_EXPR)
1125 /* If VR is to the right of VAL, return true. */
1126 tst = compare_values (vr->min, val);
1127 if ((comp == GT_EXPR && tst == 1)
1128 || (comp == GE_EXPR && (tst == 0 || tst == 1)))
1129 return boolean_true_node;
1131 /* If VR is to the left of VAL, return false. */
1132 tst = compare_values (vr->max, val);
1133 if ((comp == GT_EXPR && (tst == -1 || tst == 0))
1134 || (comp == GE_EXPR && tst == -1))
1135 return boolean_false_node;
1137 /* Otherwise, we don't know. */
1145 /* Debugging dumps. */
1148 dump_value_range (FILE *file, value_range *vr)
1151 fprintf (file, "[]");
1152 else if (vr->type == VR_UNDEFINED)
1153 fprintf (file, "UNDEFINED");
1154 else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
1156 fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
1157 print_generic_expr (file, vr->min, 0);
1158 fprintf (file, ", ");
1159 print_generic_expr (file, vr->max, 0);
1160 fprintf (file, "]");
1162 else if (vr->type == VR_VARYING)
1163 fprintf (file, "VARYING");
1165 fprintf (file, "INVALID RANGE");
1169 /* Dump value range VR to stderr. */
1172 debug_value_range (value_range *vr)
1174 dump_value_range (stderr, vr);
1178 /* Dump value ranges of all SSA_NAMEs to FILE. */
1181 dump_all_value_ranges (FILE *file)
1185 for (i = 0; i < num_ssa_names; i++)
1187 tree var = ssa_name (i);
1188 if (var && SSA_NAME_VALUE_RANGE (var))
1190 print_generic_expr (file, var, 0);
1191 fprintf (file, ": ");
1192 dump_value_range (file, SSA_NAME_VALUE_RANGE (var));
1193 fprintf (file, "\n");
1197 fprintf (file, "\n");
1201 /* Dump all value ranges to stderr. */
1204 debug_all_value_ranges (void)
1206 dump_all_value_ranges (stderr);
1210 /*---------------------------------------------------------------------------
1211 Value Range Propagation
1212 ---------------------------------------------------------------------------*/
1214 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
1215 create a new SSA name N and return the assertion assignment
1216 'V = ASSERT_EXPR <V, V OP W>'. */
1219 build_assert_expr_for (tree cond, tree v)
1223 gcc_assert (TREE_CODE (v) == SSA_NAME);
1224 n = duplicate_ssa_name (v, NULL_TREE);
1226 if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison)
1228 /* Build N = ASSERT_EXPR <V, COND>. As a special case, if the
1229 conditional is an EQ_EXPR (V == Z), just build the assignment
1231 if (TREE_CODE (cond) == EQ_EXPR)
1233 tree other = get_opposite_operand (cond, v);
1234 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, other);
1237 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n,
1238 build (ASSERT_EXPR, TREE_TYPE (v), v, cond));
1240 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1242 /* Given !V, build the assignment N = false. */
1243 tree op0 = TREE_OPERAND (cond, 0);
1244 gcc_assert (op0 == v);
1245 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
1247 else if (TREE_CODE (cond) == SSA_NAME)
1249 /* Given V, build the assignment N = true. */
1250 gcc_assert (v == cond);
1251 assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
1256 SSA_NAME_DEF_STMT (n) = assertion;
1258 /* The new ASSERT_EXPR, creates a new SSA name that replaces the
1259 operand of the ASSERT_EXPR. Register the new name and the old one
1260 in the replacement table so that we can fix the SSA web after
1261 adding all the ASSERT_EXPRs. */
1262 register_new_name_mapping (n, v);
1268 /* Return false if EXPR is a predicate expression involving floating
1272 fp_predicate (tree expr)
1274 return TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison
1275 && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)));
1279 /* Return an expression predicate that represents the range of values
1280 that can be taken by operand OP after STMT executes. */
1283 infer_value_range (tree stmt, tree op)
1285 /* Do not attempt to infer anything in names that flow through
1287 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1290 if (POINTER_TYPE_P (TREE_TYPE (op)))
1293 unsigned num_uses, num_derefs;
1295 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
1296 if (num_derefs > 0 && flag_delete_null_pointer_checks)
1298 /* We can only assume that a pointer dereference will yield
1299 non-NULL if -fdelete-null-pointer-checks is enabled. */
1300 tree null = build_int_cst (TREE_TYPE (op), 0);
1301 tree t = build (NE_EXPR, boolean_type_node, op, null);
1310 /* Return true if OP is the result of an ASSERT_EXPR that tests the
1311 same condition as COND. */
1314 has_assert_expr (tree op, tree cond)
1316 tree def_stmt = SSA_NAME_DEF_STMT (op);
1317 tree assert_expr, other_cond, other_op;
1319 /* If OP was not generated by an ASSERT_EXPR, return false. */
1320 if (TREE_CODE (def_stmt) != MODIFY_EXPR
1321 || TREE_CODE (TREE_OPERAND (def_stmt, 1)) != ASSERT_EXPR)
1324 assert_expr = TREE_OPERAND (def_stmt, 1);
1325 other_cond = ASSERT_EXPR_COND (assert_expr);
1326 other_op = ASSERT_EXPR_VAR (assert_expr);
1328 if (TREE_CODE (cond) == TREE_CODE (other_cond))
1332 /* If COND is not a comparison predicate, something is wrong. */
1333 gcc_assert (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
1335 /* Note that we only need to compare against one of the operands
1338 Suppose that we are about to insert the assertion ASSERT_EXPR
1339 <x_4, x_4 != 0> and the defining statement for x_4 is x_4 =
1340 ASSERT_EXPR <x_3, x_3 != 0>.
1342 In this case, we don't really want to insert a new
1343 ASSERT_EXPR for x_4 because that would be redundant. We
1344 already know that x_4 is not 0. So, when comparing the
1345 conditionals 'x_3 != 0' and 'x_4 != 0', we don't want to
1346 compare x_3 and x_4, we just want to compare the predicate's
1347 code (!=) and the other operand (0). */
1348 if (TREE_OPERAND (cond, 0) == op)
1349 t1 = TREE_OPERAND (cond, 1);
1351 t1 = TREE_OPERAND (cond, 0);
1353 if (TREE_OPERAND (other_cond, 0) == other_op)
1354 t2 = TREE_OPERAND (other_cond, 1);
1356 t2 = TREE_OPERAND (other_cond, 0);
1358 return (t1 == t2 || operand_equal_p (t1, t2, 0));
1365 /* Traverse all the statements in block BB looking for used variables.
1366 Variables used in BB are added to bitmap FOUND. The algorithm
1367 works in three main parts:
1369 1- For every statement S in BB, all the variables used by S are
1370 added to bitmap FOUND.
1372 2- If statement S uses an operand N in a way that exposes a known
1373 value range for N, then if N was not already generated by an
1374 ASSERT_EXPR, create a new ASSERT_EXPR for N. For instance, if N
1375 is a pointer and the statement dereferences it, we can assume
1378 3- COND_EXPRs are a special case of #2. We can derive range
1379 information from the predicate but need to insert different
1380 ASSERT_EXPRs for each of the sub-graphs rooted at the
1381 conditional block. If the last statement of BB is a conditional
1382 expression of the form 'X op Y', then
1384 a) Remove X and Y from the set FOUND.
1386 b) If the conditional dominates its THEN_CLAUSE sub-graph,
1387 recurse into it. On return, if X and/or Y are marked in
1388 FOUND, then an ASSERT_EXPR is added for the corresponding
1391 c) Repeat step (b) on the ELSE_CLAUSE.
1393 d) Mark X and Y in FOUND.
1395 4- If BB does not end in a conditional expression, then we recurse
1396 into BB's dominator children.
1398 At the end of the recursive traversal, ASSERT_EXPRs will have been
1399 added to the edges of COND_EXPR blocks that have sub-graphs using
1400 one or both predicate operands. For instance,
1407 In this case, an assertion on the THEN clause is useful to
1408 determine that 'a' is always 9 on that edge. However, an assertion
1409 on the ELSE clause would be unnecessary.
1411 On exit from this function, all the names created by the newly
1412 inserted ASSERT_EXPRs need to be added to the SSA web by rewriting
1413 the SSA names that they replace.
1415 TODO. Handle SWITCH_EXPR. */
1418 maybe_add_assert_expr (basic_block bb)
1420 block_stmt_iterator si;
1425 /* Step 1. Mark all the SSA names used in BB in bitmap FOUND. */
1428 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1433 stmt = bsi_stmt (si);
1434 get_stmt_operands (stmt);
1436 /* Mark all the SSA names used by STMT in bitmap FOUND. If STMT
1437 is inside the sub-graph of a conditional block, when we
1438 return from this recursive walk, our parent will use the
1439 FOUND bitset to determine if one of the operands it was
1440 looking for was present in the sub-graph. */
1441 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
1445 SET_BIT (found, SSA_NAME_VERSION (op));
1447 cond = infer_value_range (stmt, op);
1451 /* Step 2. If OP is used in such a way that we can infer a
1452 value range for it, create a new ASSERT_EXPR for OP
1453 (unless OP already has an ASSERT_EXPR). */
1454 gcc_assert (!is_ctrl_stmt (stmt));
1456 if (has_assert_expr (op, cond))
1459 if (!stmt_ends_bb_p (stmt))
1461 /* If STMT does not end the block, we can insert the new
1462 assertion right after it. */
1463 tree t = build_assert_expr_for (cond, op);
1464 bsi_insert_after (&si, t, BSI_NEW_STMT);
1469 /* STMT must be the last statement in BB. We can only
1470 insert new assertions on the non-abnormal edge out of
1471 BB. Note that since STMT is not control flow, there
1472 may only be one non-abnormal edge out of BB. */
1476 FOR_EACH_EDGE (e, ei, bb->succs)
1477 if (!(e->flags & EDGE_ABNORMAL))
1479 tree t = build_assert_expr_for (cond, op);
1480 bsi_insert_on_edge (e, t);
1487 /* Remember the last statement of the block. */
1491 /* Step 3. If BB's last statement is a conditional expression
1492 involving integer operands, recurse into each of the sub-graphs
1493 rooted at BB to determine if we need to add ASSERT_EXPRs.
1494 Notice that we only care about the first operand of the
1495 conditional. Adding assertions for both operands may actually
1496 hinder VRP. FIXME, add example. */
1498 && TREE_CODE (last) == COND_EXPR
1499 && !fp_predicate (COND_EXPR_COND (last))
1500 && NUM_USES (uses = STMT_USE_OPS (last)) > 0)
1507 cond = COND_EXPR_COND (last);
1509 op = USE_OP (uses, 0);
1511 /* Do not attempt to infer anything in names that flow through
1513 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1516 /* Remove the COND_EXPR operand from the FOUND bitmap.
1517 Otherwise, when we finish traversing each of the sub-graphs,
1518 we won't know whether the variables were found in the
1519 sub-graphs or if they had been found in a block upstream from
1521 RESET_BIT (found, SSA_NAME_VERSION (op));
1523 /* Look for uses of the operands in each of the sub-graphs
1524 rooted at BB. We need to check each of the outgoing edges
1525 separately, so that we know what kind of ASSERT_EXPR to
1527 FOR_EACH_EDGE (e, ei, bb->succs)
1529 /* If BB strictly dominates the sub-graph at E->DEST,
1532 && dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1533 added |= maybe_add_assert_expr (e->dest);
1535 /* Once we traversed the sub-graph, check if any block inside
1536 used either of the predicate's operands. If so, add the
1537 appropriate ASSERT_EXPR. */
1538 if (TEST_BIT (found, SSA_NAME_VERSION (op)))
1540 /* We found a use of OP in the sub-graph rooted at
1541 E->DEST. Add an ASSERT_EXPR according to whether
1542 E goes to THEN_CLAUSE or ELSE_CLAUSE. */
1545 if (e->flags & EDGE_TRUE_VALUE)
1546 c = unshare_expr (cond);
1547 else if (e->flags & EDGE_FALSE_VALUE)
1548 c = invert_truthvalue (cond);
1552 t = build_assert_expr_for (c, op);
1553 bsi_insert_on_edge (e, t);
1558 /* Finally, mark all the COND_EXPR operands as found. */
1559 SET_BIT (found, SSA_NAME_VERSION (op));
1561 /* Recurse into the dominator children of BB that are not BB's
1562 immediate successors. Note that we have already visited BB's
1563 other dominator children above. */
1564 for (son = first_dom_son (CDI_DOMINATORS, bb);
1566 son = next_dom_son (CDI_DOMINATORS, son))
1568 if (find_edge (bb, son) == NULL)
1569 added |= maybe_add_assert_expr (son);
1574 /* Step 4. Recurse into the dominator children of BB. */
1577 for (son = first_dom_son (CDI_DOMINATORS, bb);
1579 son = next_dom_son (CDI_DOMINATORS, son))
1580 added |= maybe_add_assert_expr (son);
1587 /* Traverse the flowgraph looking for conditional jumps to insert range
1588 expressions. These range expressions are meant to provide information
1589 to optimizations that need to reason in terms of value ranges. They
1590 will not be expanded into RTL. For instance, given:
1599 this pass will transform the code into:
1605 x = ASSERT_EXPR <x, x < y>
1610 y = ASSERT_EXPR <y, x <= y>
1614 The idea is that once copy and constant propagation have run, other
1615 optimizations will be able to determine what ranges of values can 'x'
1616 take in different paths of the code, simply by checking the reaching
1617 definition of 'x'. */
1620 insert_range_assertions (void)
1626 found = sbitmap_alloc (num_ssa_names);
1627 sbitmap_zero (found);
1629 calculate_dominance_info (CDI_DOMINATORS);
1631 update_ssa_p = false;
1632 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1633 if (maybe_add_assert_expr (e->dest))
1634 update_ssa_p = true;
1638 bsi_commit_edge_inserts ();
1639 update_ssa (TODO_update_ssa_no_phi);
1642 if (dump_file && (dump_flags & TDF_DETAILS))
1644 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
1645 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1648 sbitmap_free (found);
1652 /* Convert range assertion expressions into copies. FIXME, explain why. */
1655 remove_range_assertions (void)
1658 block_stmt_iterator si;
1661 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1663 tree stmt = bsi_stmt (si);
1665 if (TREE_CODE (stmt) == MODIFY_EXPR
1666 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1668 tree rhs = TREE_OPERAND (stmt, 1);
1669 tree cond = fold (ASSERT_EXPR_COND (rhs));
1670 gcc_assert (cond != boolean_false_node);
1671 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
1678 /* Return true if STMT is interesting for VRP. */
1681 stmt_interesting_for_vrp (tree stmt)
1683 if (TREE_CODE (stmt) == PHI_NODE
1684 && is_gimple_reg (PHI_RESULT (stmt))
1685 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
1686 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
1688 else if (TREE_CODE (stmt) == MODIFY_EXPR)
1690 tree lhs = TREE_OPERAND (stmt, 0);
1691 stmt_ann_t ann = stmt_ann (stmt);
1693 if (TREE_CODE (lhs) == SSA_NAME
1694 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1695 || POINTER_TYPE_P (TREE_TYPE (lhs)))
1696 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
1697 && NUM_VUSES (VUSE_OPS (ann)) == 0
1698 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
1701 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1708 /* Initialize local data structures for VRP. Return true if VRP
1709 is worth running (i.e. if we found any statements that could
1710 benefit from range information). */
1713 vrp_initialize (void)
1718 /* If we don't find any ASSERT_EXPRs in the code, there's no point
1724 block_stmt_iterator si;
1727 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1729 if (!stmt_interesting_for_vrp (phi))
1731 tree lhs = PHI_RESULT (phi);
1732 set_value_range (get_value_range (lhs), VR_VARYING, 0, 0);
1733 DONT_SIMULATE_AGAIN (phi) = true;
1736 DONT_SIMULATE_AGAIN (phi) = false;
1739 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1741 tree stmt = bsi_stmt (si);
1743 if (!stmt_interesting_for_vrp (stmt))
1747 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
1748 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1749 DONT_SIMULATE_AGAIN (stmt) = true;
1753 if (TREE_CODE (stmt) == MODIFY_EXPR
1754 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1757 DONT_SIMULATE_AGAIN (stmt) = false;
1766 /* Visit assignment STMT. If it produces an interesting range, record
1767 the SSA name in *OUTPUT_P. */
1769 static enum ssa_prop_result
1770 vrp_visit_assignment (tree stmt, tree *output_p)
1775 lhs = TREE_OPERAND (stmt, 0);
1776 rhs = TREE_OPERAND (stmt, 1);
1778 /* We only keep track of ranges in integral and pointer types. */
1779 if (TREE_CODE (lhs) == SSA_NAME
1780 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1781 || POINTER_TYPE_P (TREE_TYPE (lhs))))
1783 value_range *vr, new_vr;
1786 vr = get_value_range (lhs);
1787 extract_range_from_expr (&new_vr, rhs);
1789 /* If STMT is inside a loop, we may be able to know something
1790 else about the range of LHS by examining scalar evolution
1792 if (cfg_loops && (l = loop_containing_stmt (stmt)))
1793 adjust_range_with_scev (&new_vr, l, lhs);
1795 if (update_value_range (vr, new_vr.type, new_vr.min, new_vr.max))
1799 if (dump_file && (dump_flags & TDF_DETAILS))
1801 fprintf (dump_file, "Found new range ");
1802 dump_value_range (dump_file, &new_vr);
1803 fprintf (dump_file, " for ");
1804 print_generic_expr (dump_file, lhs, 0);
1805 fprintf (dump_file, "\n\n");
1808 if (new_vr.type == VR_VARYING)
1809 return SSA_PROP_VARYING;
1811 return SSA_PROP_INTERESTING;
1814 return SSA_PROP_NOT_INTERESTING;
1817 /* Every other statements produces no useful ranges. */
1818 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1819 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1821 return SSA_PROP_VARYING;
1825 /* Given a conditional predicate COND, try to determine if COND yields
1826 true or false based on the value ranges of its operands. */
1829 vrp_evaluate_conditional (tree cond)
1831 gcc_assert (TREE_CODE (cond) == SSA_NAME
1832 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
1834 if (TREE_CODE (cond) == SSA_NAME)
1836 /* For SSA names, only return a truth value if the range is
1837 known and contains exactly one value. */
1838 value_range *vr = SSA_NAME_VALUE_RANGE (cond);
1839 if (vr && vr->type == VR_RANGE && vr->min == vr->max)
1844 /* For comparisons, evaluate each operand and compare their
1847 value_range *vr0, *vr1;
1849 op0 = TREE_OPERAND (cond, 0);
1850 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
1852 op1 = TREE_OPERAND (cond, 1);
1853 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
1856 return compare_ranges (TREE_CODE (cond), vr0, vr1);
1857 else if (vr0 && vr1 == NULL)
1858 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
1859 else if (vr0 == NULL && vr1)
1860 return compare_range_with_value (opposite_comparison (TREE_CODE (cond)),
1864 /* Anything else cannot be computed statically. */
1869 /* Visit conditional statement STMT. If we can determine which edge
1870 will be taken out of STMT's basic block, record it in
1871 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
1872 SSA_PROP_VARYING. */
1874 static enum ssa_prop_result
1875 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
1879 *taken_edge_p = NULL;
1881 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
1882 add ASSERT_EXPRs for them. */
1883 if (TREE_CODE (stmt) == SWITCH_EXPR)
1884 return SSA_PROP_VARYING;
1886 cond = COND_EXPR_COND (stmt);
1888 if (dump_file && (dump_flags & TDF_DETAILS))
1893 fprintf (dump_file, "\nVisiting conditional with predicate: ");
1894 print_generic_expr (dump_file, cond, 0);
1895 fprintf (dump_file, "\nWith known ranges\n");
1897 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
1899 fprintf (dump_file, "\t");
1900 print_generic_expr (dump_file, use, 0);
1901 fprintf (dump_file, ": ");
1902 dump_value_range (dump_file, SSA_NAME_VALUE_RANGE (use));
1905 fprintf (dump_file, "\n");
1908 /* Compute the value of the predicate COND by checking the known
1909 ranges of each of its operands. */
1910 val = vrp_evaluate_conditional (cond);
1912 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
1914 if (dump_file && (dump_flags & TDF_DETAILS))
1916 fprintf (dump_file, "\nPredicate evaluates to: ");
1917 if (val == NULL_TREE)
1918 fprintf (dump_file, "DON'T KNOW\n");
1920 print_generic_stmt (dump_file, val, 0);
1923 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
1927 /* Evaluate statement STMT. If the statement produces a useful range,
1928 return SSA_PROP_INTERESTING and record the SSA name with the
1929 interesting range into *OUTPUT_P.
1931 If STMT is a conditional branch and we can determine its truth
1932 value, the taken edge is recorded in *TAKEN_EDGE_P.
1934 If STMT produces a varying value, return SSA_PROP_VARYING. */
1936 static enum ssa_prop_result
1937 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
1943 if (dump_file && (dump_flags & TDF_DETAILS))
1945 fprintf (dump_file, "\nVisiting statement:\n");
1946 print_generic_stmt (dump_file, stmt, dump_flags);
1947 fprintf (dump_file, "\n");
1950 ann = stmt_ann (stmt);
1951 if (TREE_CODE (stmt) == MODIFY_EXPR
1952 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
1953 && NUM_VUSES (VUSE_OPS (ann)) == 0
1954 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
1955 return vrp_visit_assignment (stmt, output_p);
1956 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1957 return vrp_visit_cond_stmt (stmt, taken_edge_p);
1959 /* All other statements produce nothing of interest for VRP, so mark
1960 their outputs varying and prevent further simulation. */
1961 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1962 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1964 return SSA_PROP_VARYING;
1968 /* Meet operation for value ranges. Given two value ranges VR0 and
1969 VR1, store in VR0 the result of meeting VR0 and VR1.
1971 The meeting rules are as follows:
1973 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
1975 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
1976 union of VR0 and VR1. */
1979 vrp_meet (value_range *vr0, value_range *vr1)
1981 if (vr0->type == VR_UNDEFINED)
1987 if (vr1->type == VR_UNDEFINED)
1989 /* Nothing to do. VR0 already has the resulting range. */
1993 if (vr0->type == VR_VARYING)
1995 /* Nothing to do. VR0 already has the resulting range. */
1999 if (vr1->type == VR_VARYING)
2005 /* If either is a symbolic range, drop to VARYING. */
2006 if (symbolic_range_p (vr0) || symbolic_range_p (vr1))
2008 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2012 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
2014 /* If VR0 and VR1 have a non-empty intersection, compute the
2015 union of both ranges. */
2016 if (value_ranges_intersect_p (vr0, vr1))
2023 /* The lower limit of the new range is the minimum of the
2025 if (compare_values (vr0->min, vr1->min) == 1)
2028 /* The upper limit of the new range is the maximum of the
2030 if (compare_values (vr0->max, vr1->max) == -1)
2033 set_value_range (vr0, vr0->type, min, max);
2037 /* The two ranges don't intersect, set the result to VR_VARYING. */
2038 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2041 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
2043 /* Two anti-ranges meet only if they are both identical. */
2044 if (compare_values (vr0->min, vr1->min) == 0
2045 && compare_values (vr0->max, vr1->max) == 0
2046 && compare_values (vr0->min, vr0->max) == 0)
2047 /* Nothing to do. */ ;
2049 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2051 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
2053 /* A range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] meet
2054 only if the ranges have an empty intersection. The result of
2055 the meet operation is the anti-range. */
2056 if (!value_ranges_intersect_p (vr0, vr1))
2058 if (vr1->type == VR_ANTI_RANGE)
2062 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2069 /* Visit all arguments for PHI node PHI that flow through executable
2070 edges. If a valid value range can be derived from all the incoming
2071 value ranges, set a new range for the LHS of PHI. */
2073 static enum ssa_prop_result
2074 vrp_visit_phi_node (tree phi)
2077 tree lhs = PHI_RESULT (phi);
2078 value_range *lhs_vr = get_value_range (lhs);
2079 value_range vr_result = *lhs_vr;
2081 if (dump_file && (dump_flags & TDF_DETAILS))
2083 fprintf (dump_file, "\nVisiting PHI node: ");
2084 print_generic_expr (dump_file, phi, dump_flags);
2087 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2089 edge e = PHI_ARG_EDGE (phi, i);
2091 if (dump_file && (dump_flags & TDF_DETAILS))
2094 "\n Argument #%d (%d -> %d %sexecutable)\n",
2095 i, e->src->index, e->dest->index,
2096 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
2099 if (e->flags & EDGE_EXECUTABLE)
2101 tree arg = PHI_ARG_DEF (phi, i);
2104 if (TREE_CODE (arg) == SSA_NAME)
2105 vr_arg = *(get_value_range (arg));
2108 vr_arg.type = VR_RANGE;
2113 if (dump_file && (dump_flags & TDF_DETAILS))
2115 fprintf (dump_file, "\t");
2116 print_generic_expr (dump_file, arg, dump_flags);
2117 fprintf (dump_file, "\n\tValue: ");
2118 dump_value_range (dump_file, &vr_arg);
2119 fprintf (dump_file, "\n");
2122 vrp_meet (&vr_result, &vr_arg);
2124 if (vr_result.type == VR_VARYING)
2129 if (vr_result.type == VR_VARYING)
2131 set_value_range (lhs_vr, VR_VARYING, 0, 0);
2132 return SSA_PROP_VARYING;
2135 /* To prevent infinite iterations in the algorithm, derive ranges
2136 when the new value is slightly bigger or smaller than the
2138 if (lhs_vr->type == VR_RANGE)
2140 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
2142 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
2143 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
2145 /* If the new minimum is smaller or larger than the previous
2146 one, go all the way to -INF. In the first case, to avoid
2147 iterating millions of times to reach -INF, and in the
2148 other case to avoid infinite bouncing between different
2150 if (cmp_min > 0 || cmp_min < 0)
2151 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
2153 /* Similarly, if the new maximum is smaller or larger than
2154 the previous one, go all the way to +INF. */
2155 if (cmp_max < 0 || cmp_max > 0)
2156 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
2158 /* If we ended up with a (-INF, +INF) range, set it to
2160 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
2161 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
2163 set_value_range (lhs_vr, VR_VARYING, 0, 0);
2164 return SSA_PROP_VARYING;
2169 /* If the new range is different than the previous value, keep
2171 if (update_value_range (lhs_vr, vr_result.type, vr_result.min, vr_result.max))
2172 return SSA_PROP_INTERESTING;
2174 /* Nothing changed, don't add outgoing edges. */
2175 return SSA_PROP_NOT_INTERESTING;
2179 /* Traverse all the blocks folding conditionals with known ranges. */
2185 int num_pred_folded = 0;
2189 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
2190 dump_all_value_ranges (dump_file);
2191 fprintf (dump_file, "\n");
2196 tree last = last_stmt (bb);
2197 if (last && TREE_CODE (last) == COND_EXPR)
2199 tree val = vrp_evaluate_conditional (COND_EXPR_COND (last));
2204 fprintf (dump_file, "Folding predicate ");
2205 print_generic_expr (dump_file, COND_EXPR_COND (last), 0);
2206 fprintf (dump_file, " to ");
2207 print_generic_expr (dump_file, val, 0);
2208 fprintf (dump_file, "\n");
2212 COND_EXPR_COND (last) = val;
2218 if (dump_file && (dump_flags & TDF_STATS))
2219 fprintf (dump_file, "\nNumber of predicates folded: %d\n\n",
2224 /* Main entry point to VRP (Value Range Propagation). This pass is
2225 loosely based on J. R. C. Patterson, ``Accurate Static Branch
2226 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
2227 Programming Language Design and Implementation, pp. 67-78, 1995.
2228 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
2230 This is essentially an SSA-CCP pass modified to deal with ranges
2231 instead of constants.
2233 TODO, the main difference between this pass and Patterson's is that
2234 we do not propagate edge probabilities. We only compute whether
2235 edges can be taken or not. That is, instead of having a spectrum
2236 of jump probabilities between 0 and 1, we only deal with 0, 1 and
2237 DON'T KNOW. In the future, it may be worthwhile to propagate
2238 probabilities to aid branch prediction. */
2243 insert_range_assertions ();
2245 cfg_loops = loop_optimizer_init (NULL);
2247 scev_initialize (cfg_loops);
2249 if (vrp_initialize ())
2251 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
2258 loop_optimizer_finalize (cfg_loops, NULL);
2259 current_loops = NULL;
2262 remove_range_assertions ();
2268 return flag_tree_vrp != 0;
2271 struct tree_opt_pass pass_vrp =
2274 gate_vrp, /* gate */
2275 execute_vrp, /* execute */
2278 0, /* static_pass_number */
2279 TV_TREE_VRP, /* tv_id */
2280 PROP_ssa | PROP_alias, /* properties_required */
2281 0, /* properties_provided */
2282 0, /* properties_destroyed */
2283 0, /* todo_flags_start */
2288 | TODO_update_ssa, /* todo_flags_finish */