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));
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)
1505 cond = COND_EXPR_COND (last);
1507 op = USE_OP (uses, 0);
1509 /* Do not attempt to infer anything in names that flow through
1511 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
1514 /* Remove the COND_EXPR operand from the FOUND bitmap.
1515 Otherwise, when we finish traversing each of the sub-graphs,
1516 we won't know whether the variables were found in the
1517 sub-graphs or if they had been found in a block upstream from
1519 RESET_BIT (found, SSA_NAME_VERSION (op));
1521 /* Look for uses of the operands in each of the sub-graphs
1522 rooted at BB. We need to check each of the outgoing edges
1523 separately, so that we know what kind of ASSERT_EXPR to
1525 FOR_EACH_EDGE (e, ei, bb->succs)
1527 /* If BB strictly dominates the sub-graph at E->DEST,
1530 && dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1531 added |= maybe_add_assert_expr (e->dest);
1533 /* Once we traversed the sub-graph, check if any block inside
1534 used either of the predicate's operands. If so, add the
1535 appropriate ASSERT_EXPR. */
1536 if (TEST_BIT (found, SSA_NAME_VERSION (op)))
1538 /* We found a use of OP in the sub-graph rooted at
1539 E->DEST. Add an ASSERT_EXPR according to whether
1540 E goes to THEN_CLAUSE or ELSE_CLAUSE. */
1543 if (e->flags & EDGE_TRUE_VALUE)
1544 c = unshare_expr (cond);
1545 else if (e->flags & EDGE_FALSE_VALUE)
1546 c = invert_truthvalue (cond);
1550 t = build_assert_expr_for (c, op);
1551 bsi_insert_on_edge (e, t);
1556 /* Finally, mark all the COND_EXPR operands as found. */
1557 SET_BIT (found, SSA_NAME_VERSION (op));
1559 /* Recurse into the dominator children of BB that are not BB's
1560 immediate successors. Note that we have already visited BB's
1561 other dominator children above. */
1562 for (son = first_dom_son (CDI_DOMINATORS, bb);
1564 son = next_dom_son (CDI_DOMINATORS, son))
1566 if (find_edge (bb, son) == NULL)
1567 added |= maybe_add_assert_expr (son);
1572 /* Step 4. Recurse into the dominator children of BB. */
1575 for (son = first_dom_son (CDI_DOMINATORS, bb);
1577 son = next_dom_son (CDI_DOMINATORS, son))
1578 added |= maybe_add_assert_expr (son);
1585 /* Traverse the flowgraph looking for conditional jumps to insert range
1586 expressions. These range expressions are meant to provide information
1587 to optimizations that need to reason in terms of value ranges. They
1588 will not be expanded into RTL. For instance, given:
1597 this pass will transform the code into:
1603 x = ASSERT_EXPR <x, x < y>
1608 y = ASSERT_EXPR <y, x <= y>
1612 The idea is that once copy and constant propagation have run, other
1613 optimizations will be able to determine what ranges of values can 'x'
1614 take in different paths of the code, simply by checking the reaching
1615 definition of 'x'. */
1618 insert_range_assertions (void)
1624 found = sbitmap_alloc (num_ssa_names);
1625 sbitmap_zero (found);
1627 calculate_dominance_info (CDI_DOMINATORS);
1629 update_ssa_p = false;
1630 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1631 if (maybe_add_assert_expr (e->dest))
1632 update_ssa_p = true;
1636 bsi_commit_edge_inserts ();
1637 update_ssa (TODO_update_ssa_no_phi);
1640 if (dump_file && (dump_flags & TDF_DETAILS))
1642 fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
1643 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1646 sbitmap_free (found);
1650 /* Convert range assertion expressions into copies. FIXME, explain why. */
1653 remove_range_assertions (void)
1656 block_stmt_iterator si;
1659 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1661 tree stmt = bsi_stmt (si);
1663 if (TREE_CODE (stmt) == MODIFY_EXPR
1664 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1666 tree rhs = TREE_OPERAND (stmt, 1);
1667 tree cond = fold (ASSERT_EXPR_COND (rhs));
1668 gcc_assert (cond != boolean_false_node);
1669 TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
1676 /* Return true if STMT is interesting for VRP. */
1679 stmt_interesting_for_vrp (tree stmt)
1681 if (TREE_CODE (stmt) == PHI_NODE
1682 && is_gimple_reg (PHI_RESULT (stmt))
1683 && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
1684 || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
1686 else if (TREE_CODE (stmt) == MODIFY_EXPR)
1688 tree lhs = TREE_OPERAND (stmt, 0);
1689 stmt_ann_t ann = stmt_ann (stmt);
1691 if (TREE_CODE (lhs) == SSA_NAME
1692 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1693 || POINTER_TYPE_P (TREE_TYPE (lhs)))
1694 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
1695 && NUM_VUSES (VUSE_OPS (ann)) == 0
1696 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
1699 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1706 /* Initialize local data structures for VRP. Return true if VRP
1707 is worth running (i.e. if we found any statements that could
1708 benefit from range information). */
1711 vrp_initialize (void)
1716 /* If we don't find any ASSERT_EXPRs in the code, there's no point
1722 block_stmt_iterator si;
1725 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1727 if (!stmt_interesting_for_vrp (phi))
1729 tree lhs = PHI_RESULT (phi);
1730 set_value_range (get_value_range (lhs), VR_VARYING, 0, 0);
1731 DONT_SIMULATE_AGAIN (phi) = true;
1734 DONT_SIMULATE_AGAIN (phi) = false;
1737 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1739 tree stmt = bsi_stmt (si);
1741 if (!stmt_interesting_for_vrp (stmt))
1745 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
1746 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1747 DONT_SIMULATE_AGAIN (stmt) = true;
1751 if (TREE_CODE (stmt) == MODIFY_EXPR
1752 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
1755 DONT_SIMULATE_AGAIN (stmt) = false;
1764 /* Visit assignment STMT. If it produces an interesting range, record
1765 the SSA name in *OUTPUT_P. */
1767 static enum ssa_prop_result
1768 vrp_visit_assignment (tree stmt, tree *output_p)
1773 lhs = TREE_OPERAND (stmt, 0);
1774 rhs = TREE_OPERAND (stmt, 1);
1776 /* We only keep track of ranges in integral and pointer types. */
1777 if (TREE_CODE (lhs) == SSA_NAME
1778 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1779 || POINTER_TYPE_P (TREE_TYPE (lhs))))
1781 value_range *vr, new_vr;
1784 vr = get_value_range (lhs);
1785 extract_range_from_expr (&new_vr, rhs);
1787 /* If STMT is inside a loop, we may be able to know something
1788 else about the range of LHS by examining scalar evolution
1790 if (cfg_loops && (l = loop_containing_stmt (stmt)))
1791 adjust_range_with_scev (&new_vr, l, lhs);
1793 if (update_value_range (vr, new_vr.type, new_vr.min, new_vr.max))
1797 if (dump_file && (dump_flags & TDF_DETAILS))
1799 fprintf (dump_file, "Found new range ");
1800 dump_value_range (dump_file, &new_vr);
1801 fprintf (dump_file, " for ");
1802 print_generic_expr (dump_file, lhs, 0);
1803 fprintf (dump_file, "\n\n");
1806 if (new_vr.type == VR_VARYING)
1807 return SSA_PROP_VARYING;
1809 return SSA_PROP_INTERESTING;
1812 return SSA_PROP_NOT_INTERESTING;
1815 /* Every other statements produces no useful ranges. */
1816 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1817 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1819 return SSA_PROP_VARYING;
1823 /* Given a conditional predicate COND, try to determine if COND yields
1824 true or false based on the value ranges of its operands. */
1827 vrp_evaluate_conditional (tree cond)
1829 gcc_assert (TREE_CODE (cond) == SSA_NAME
1830 || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
1832 if (TREE_CODE (cond) == SSA_NAME)
1834 /* For SSA names, only return a truth value if the range is
1835 known and contains exactly one value. */
1836 value_range *vr = SSA_NAME_VALUE_RANGE (cond);
1837 if (vr && vr->type == VR_RANGE && vr->min == vr->max)
1842 /* For comparisons, evaluate each operand and compare their
1845 value_range *vr0, *vr1;
1847 op0 = TREE_OPERAND (cond, 0);
1848 vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
1850 op1 = TREE_OPERAND (cond, 1);
1851 vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
1854 return compare_ranges (TREE_CODE (cond), vr0, vr1);
1855 else if (vr0 && vr1 == NULL)
1856 return compare_range_with_value (TREE_CODE (cond), vr0, op1);
1857 else if (vr0 == NULL && vr1)
1858 return compare_range_with_value (opposite_comparison (TREE_CODE (cond)),
1862 /* Anything else cannot be computed statically. */
1867 /* Visit conditional statement STMT. If we can determine which edge
1868 will be taken out of STMT's basic block, record it in
1869 *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
1870 SSA_PROP_VARYING. */
1872 static enum ssa_prop_result
1873 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
1877 *taken_edge_p = NULL;
1879 /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
1880 add ASSERT_EXPRs for them. */
1881 if (TREE_CODE (stmt) == SWITCH_EXPR)
1882 return SSA_PROP_VARYING;
1884 cond = COND_EXPR_COND (stmt);
1886 if (dump_file && (dump_flags & TDF_DETAILS))
1891 fprintf (dump_file, "\nVisiting conditional with predicate: ");
1892 print_generic_expr (dump_file, cond, 0);
1893 fprintf (dump_file, "\nWith known ranges\n");
1895 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
1897 fprintf (dump_file, "\t");
1898 print_generic_expr (dump_file, use, 0);
1899 fprintf (dump_file, ": ");
1900 dump_value_range (dump_file, SSA_NAME_VALUE_RANGE (use));
1903 fprintf (dump_file, "\n");
1906 /* Compute the value of the predicate COND by checking the known
1907 ranges of each of its operands. */
1908 val = vrp_evaluate_conditional (cond);
1910 *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
1912 if (dump_file && (dump_flags & TDF_DETAILS))
1914 fprintf (dump_file, "\nPredicate evaluates to: ");
1915 if (val == NULL_TREE)
1916 fprintf (dump_file, "DON'T KNOW\n");
1918 print_generic_stmt (dump_file, val, 0);
1921 return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
1925 /* Evaluate statement STMT. If the statement produces a useful range,
1926 return SSA_PROP_INTERESTING and record the SSA name with the
1927 interesting range into *OUTPUT_P.
1929 If STMT is a conditional branch and we can determine its truth
1930 value, the taken edge is recorded in *TAKEN_EDGE_P.
1932 If STMT produces a varying value, return SSA_PROP_VARYING. */
1934 static enum ssa_prop_result
1935 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
1941 if (dump_file && (dump_flags & TDF_DETAILS))
1943 fprintf (dump_file, "\nVisiting statement:\n");
1944 print_generic_stmt (dump_file, stmt, dump_flags);
1945 fprintf (dump_file, "\n");
1948 ann = stmt_ann (stmt);
1949 if (TREE_CODE (stmt) == MODIFY_EXPR
1950 && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
1951 && NUM_VUSES (VUSE_OPS (ann)) == 0
1952 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
1953 return vrp_visit_assignment (stmt, output_p);
1954 else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
1955 return vrp_visit_cond_stmt (stmt, taken_edge_p);
1957 /* All other statements produce nothing of interest for VRP, so mark
1958 their outputs varying and prevent further simulation. */
1959 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1960 set_value_range (get_value_range (def), VR_VARYING, 0, 0);
1962 return SSA_PROP_VARYING;
1966 /* Meet operation for value ranges. Given two value ranges VR0 and
1967 VR1, store in VR0 the result of meeting VR0 and VR1.
1969 The meeting rules are as follows:
1971 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
1973 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
1974 union of VR0 and VR1. */
1977 vrp_meet (value_range *vr0, value_range *vr1)
1979 if (vr0->type == VR_UNDEFINED)
1985 if (vr1->type == VR_UNDEFINED)
1987 /* Nothing to do. VR0 already has the resulting range. */
1991 if (vr0->type == VR_VARYING)
1993 /* Nothing to do. VR0 already has the resulting range. */
1997 if (vr1->type == VR_VARYING)
2003 /* If either is a symbolic range, drop to VARYING. */
2004 if (symbolic_range_p (vr0) || symbolic_range_p (vr1))
2006 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2010 if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
2012 /* If VR0 and VR1 have a non-empty intersection, compute the
2013 union of both ranges. */
2014 if (value_ranges_intersect_p (vr0, vr1))
2021 /* The lower limit of the new range is the minimum of the
2023 if (compare_values (vr0->min, vr1->min) == 1)
2026 /* The upper limit of the new range is the maximum of the
2028 if (compare_values (vr0->max, vr1->max) == -1)
2031 set_value_range (vr0, vr0->type, min, max);
2035 /* The two ranges don't intersect, set the result to VR_VARYING. */
2036 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2039 else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
2041 /* Two anti-ranges meet only if they are both identical. */
2042 if (compare_values (vr0->min, vr1->min) == 0
2043 && compare_values (vr0->max, vr1->max) == 0
2044 && compare_values (vr0->min, vr0->max) == 0)
2045 /* Nothing to do. */ ;
2047 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2049 else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
2051 /* A range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] meet
2052 only if the ranges have an empty intersection. The result of
2053 the meet operation is the anti-range. */
2054 if (!value_ranges_intersect_p (vr0, vr1))
2056 if (vr1->type == VR_ANTI_RANGE)
2060 set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
2067 /* Visit all arguments for PHI node PHI that flow through executable
2068 edges. If a valid value range can be derived from all the incoming
2069 value ranges, set a new range for the LHS of PHI. */
2071 static enum ssa_prop_result
2072 vrp_visit_phi_node (tree phi)
2075 tree lhs = PHI_RESULT (phi);
2076 value_range *lhs_vr = get_value_range (lhs);
2077 value_range vr_result = *lhs_vr;
2079 if (dump_file && (dump_flags & TDF_DETAILS))
2081 fprintf (dump_file, "\nVisiting PHI node: ");
2082 print_generic_expr (dump_file, phi, dump_flags);
2085 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2087 edge e = PHI_ARG_EDGE (phi, i);
2089 if (dump_file && (dump_flags & TDF_DETAILS))
2092 "\n Argument #%d (%d -> %d %sexecutable)\n",
2093 i, e->src->index, e->dest->index,
2094 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
2097 if (e->flags & EDGE_EXECUTABLE)
2099 tree arg = PHI_ARG_DEF (phi, i);
2102 if (TREE_CODE (arg) == SSA_NAME)
2103 vr_arg = *(get_value_range (arg));
2106 vr_arg.type = VR_RANGE;
2111 if (dump_file && (dump_flags & TDF_DETAILS))
2113 fprintf (dump_file, "\t");
2114 print_generic_expr (dump_file, arg, dump_flags);
2115 fprintf (dump_file, "\n\tValue: ");
2116 dump_value_range (dump_file, &vr_arg);
2117 fprintf (dump_file, "\n");
2120 vrp_meet (&vr_result, &vr_arg);
2122 if (vr_result.type == VR_VARYING)
2127 if (vr_result.type == VR_VARYING)
2129 set_value_range (lhs_vr, VR_VARYING, 0, 0);
2130 return SSA_PROP_VARYING;
2133 /* To prevent infinite iterations in the algorithm, derive ranges
2134 when the new value is slightly bigger or smaller than the
2136 if (lhs_vr->type == VR_RANGE)
2138 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
2140 int cmp_min = compare_values (lhs_vr->min, vr_result.min);
2141 int cmp_max = compare_values (lhs_vr->max, vr_result.max);
2143 /* If the new minimum is smaller or larger than the previous
2144 one, go all the way to -INF. In the first case, to avoid
2145 iterating millions of times to reach -INF, and in the
2146 other case to avoid infinite bouncing between different
2148 if (cmp_min > 0 || cmp_min < 0)
2149 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
2151 /* Similarly, if the new maximum is smaller or larger than
2152 the previous one, go all the way to +INF. */
2153 if (cmp_max < 0 || cmp_max > 0)
2154 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
2156 /* If we ended up with a (-INF, +INF) range, set it to
2158 if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
2159 && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
2161 set_value_range (lhs_vr, VR_VARYING, 0, 0);
2162 return SSA_PROP_VARYING;
2167 /* If the new range is different than the previous value, keep
2169 if (update_value_range (lhs_vr, vr_result.type, vr_result.min, vr_result.max))
2170 return SSA_PROP_INTERESTING;
2172 /* Nothing changed, don't add outgoing edges. */
2173 return SSA_PROP_NOT_INTERESTING;
2177 /* Traverse all the blocks folding conditionals with known ranges. */
2183 int num_pred_folded = 0;
2187 fprintf (dump_file, "\nValue ranges after VRP:\n\n");
2188 dump_all_value_ranges (dump_file);
2189 fprintf (dump_file, "\n");
2194 tree last = last_stmt (bb);
2195 if (last && TREE_CODE (last) == COND_EXPR)
2197 tree val = vrp_evaluate_conditional (COND_EXPR_COND (last));
2202 fprintf (dump_file, "Folding predicate ");
2203 print_generic_expr (dump_file, COND_EXPR_COND (last), 0);
2204 fprintf (dump_file, " to ");
2205 print_generic_expr (dump_file, val, 0);
2206 fprintf (dump_file, "\n");
2210 COND_EXPR_COND (last) = val;
2216 if (dump_file && (dump_flags & TDF_STATS))
2217 fprintf (dump_file, "\nNumber of predicates folded: %d\n\n",
2222 /* Main entry point to VRP (Value Range Propagation). This pass is
2223 loosely based on J. R. C. Patterson, ``Accurate Static Branch
2224 Prediction by Value Range Propagation,'' in SIGPLAN Conference on
2225 Programming Language Design and Implementation, pp. 67-78, 1995.
2226 Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
2228 This is essentially an SSA-CCP pass modified to deal with ranges
2229 instead of constants.
2231 TODO, the main difference between this pass and Patterson's is that
2232 we do not propagate edge probabilities. We only compute whether
2233 edges can be taken or not. That is, instead of having a spectrum
2234 of jump probabilities between 0 and 1, we only deal with 0, 1 and
2235 DON'T KNOW. In the future, it may be worthwhile to propagate
2236 probabilities to aid branch prediction. */
2241 insert_range_assertions ();
2243 cfg_loops = loop_optimizer_init (NULL);
2245 scev_initialize (cfg_loops);
2247 if (vrp_initialize ())
2249 ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
2256 loop_optimizer_finalize (cfg_loops, NULL);
2257 current_loops = NULL;
2260 remove_range_assertions ();
2266 return flag_tree_vrp != 0;
2269 struct tree_opt_pass pass_vrp =
2272 gate_vrp, /* gate */
2273 execute_vrp, /* execute */
2276 0, /* static_pass_number */
2277 TV_TREE_VRP, /* tv_id */
2278 PROP_ssa | PROP_alias, /* properties_required */
2279 0, /* properties_provided */
2280 0, /* properties_destroyed */
2281 0, /* todo_flags_start */
2286 | TODO_update_ssa, /* todo_flags_finish */