#include "tree-dump.h"
#include "timevar.h"
#include "diagnostic.h"
+#include "toplev.h"
#include "cfgloop.h"
#include "tree-scalar-evolution.h"
#include "tree-ssa-propagate.h"
/* Local functions. */
static int compare_values (tree val1, tree val2);
+static void vrp_meet (value_range_t *, value_range_t *);
/* Location information for ASSERT_EXPRs. Each instance of this
structure describes an ASSERT_EXPR for an SSA name. Since a single
}
+/* Set value range VR to a range of a truthvalue of type TYPE. */
+
+static inline void
+set_value_range_to_truthvalue (value_range_t *vr, tree type)
+{
+ if (TYPE_PRECISION (type) == 1)
+ set_value_range_to_varying (vr);
+ else
+ set_value_range (vr, VR_RANGE,
+ build_int_cst (type, 0), build_int_cst (type, 1),
+ vr->equiv);
+}
+
+
/* Set value range VR to VR_UNDEFINED. */
static inline void
else
{
tree min, max, anti_min, anti_max, real_min, real_max;
+ int cmp;
/* We want to compute the logical AND of the two ranges;
there are three cases to consider.
/* Case 3a, the anti-range extends into the low
part of the real range. Thus creating a new
low for the real range. */
- else if ((compare_values (anti_max, real_min) == 1
- || compare_values (anti_max, real_min) == 0)
+ else if (((cmp = compare_values (anti_max, real_min)) == 1
+ || cmp == 0)
&& compare_values (anti_max, real_max) == -1)
{
min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
part of the real range. Thus creating a new
higher for the real range. */
else if (compare_values (anti_min, real_min) == 1
- && (compare_values (anti_min, real_max) == -1
- || compare_values (anti_min, real_max) == 0))
+ && ((cmp = compare_values (anti_min, real_max)) == -1
+ || cmp == 0))
{
max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
anti_min,
}
else
{
- set_value_range_to_varying (vr);
+ /* The result of a TRUTH_*_EXPR is always true or false. */
+ set_value_range_to_truthvalue (vr, TREE_TYPE (expr));
return;
}
}
&& is_gimple_val (new_max)
&& tree_int_cst_equal (new_min, orig_min)
&& tree_int_cst_equal (new_max, orig_max)
- && compare_values (new_min, new_max) <= 0
- && compare_values (new_min, new_max) >= -1)
+ && (cmp = compare_values (new_min, new_max)) <= 0
+ && cmp >= -1)
{
set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv);
return;
}
+/* Extract range information from a conditional expression EXPR based on
+ the ranges of each of its operands and the expression code. */
+
+static void
+extract_range_from_cond_expr (value_range_t *vr, tree expr)
+{
+ tree op0, op1;
+ value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+
+ /* Get value ranges for each operand. For constant operands, create
+ a new value range with the operand to simplify processing. */
+ op0 = COND_EXPR_THEN (expr);
+ if (TREE_CODE (op0) == SSA_NAME)
+ vr0 = *(get_value_range (op0));
+ else if (is_gimple_min_invariant (op0))
+ set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
+ else
+ set_value_range_to_varying (&vr0);
+
+ op1 = COND_EXPR_ELSE (expr);
+ if (TREE_CODE (op1) == SSA_NAME)
+ vr1 = *(get_value_range (op1));
+ else if (is_gimple_min_invariant (op1))
+ set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
+ else
+ set_value_range_to_varying (&vr1);
+
+ /* The resulting value range is the union of the operand ranges */
+ vrp_meet (&vr0, &vr1);
+ copy_value_range (vr, &vr0);
+}
+
+
/* Extract range information from a comparison expression EXPR based
on the range of its operand and the expression code. */
set_value_range (vr, VR_RANGE, val, val, vr->equiv);
}
else
- set_value_range_to_varying (vr);
+ /* The result of a comparison is always true or false. */
+ set_value_range_to_truthvalue (vr, TREE_TYPE (expr));
}
extract_range_from_binary_expr (vr, expr);
else if (TREE_CODE_CLASS (code) == tcc_unary)
extract_range_from_unary_expr (vr, expr);
+ else if (code == COND_EXPR)
+ extract_range_from_cond_expr (vr, expr);
else if (TREE_CODE_CLASS (code) == tcc_comparison)
extract_range_from_comparison (vr, expr);
else if (is_gimple_min_invariant (expr))
BITMAP_FREE (need_assert_for);
}
+/* Checks one ARRAY_REF in REF, located at LOCUS. Ignores flexible arrays
+ and "struct" hacks. If VRP can determine that the
+ array subscript is a contant, check if it is outside valid
+ range. If the array subscript is a RANGE, warn if it is
+ non-overlapping with valid range.
+ IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR. */
+
+static void
+check_array_ref (tree ref, location_t* locus, bool ignore_off_by_one)
+{
+ value_range_t* vr = NULL;
+ tree low_sub, up_sub;
+ tree low_bound, up_bound = array_ref_up_bound (ref);
+
+ low_sub = up_sub = TREE_OPERAND (ref, 1);
+
+ if (!up_bound || !locus || TREE_NO_WARNING (ref)
+ || TREE_CODE (up_bound) != INTEGER_CST
+ /* Can not check flexible arrays. */
+ || (TYPE_SIZE (TREE_TYPE (ref)) == NULL_TREE
+ && TYPE_DOMAIN (TREE_TYPE (ref)) != NULL_TREE
+ && TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (ref))) == NULL_TREE)
+ /* Accesses after the end of arrays of size 0 (gcc
+ extension) and 1 are likely intentional ("struct
+ hack"). */
+ || compare_tree_int (up_bound, 1) <= 0)
+ return;
+
+ low_bound = array_ref_low_bound (ref);
+
+ if (TREE_CODE (low_sub) == SSA_NAME)
+ {
+ vr = get_value_range (low_sub);
+ if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
+ {
+ low_sub = vr->type == VR_RANGE ? vr->max : vr->min;
+ up_sub = vr->type == VR_RANGE ? vr->min : vr->max;
+ }
+ }
+
+ if (vr && vr->type == VR_ANTI_RANGE)
+ {
+ if (TREE_CODE (up_sub) == INTEGER_CST
+ && tree_int_cst_lt (up_bound, up_sub)
+ && TREE_CODE (low_sub) == INTEGER_CST
+ && tree_int_cst_lt (low_sub, low_bound))
+ {
+ warning (OPT_Warray_bounds,
+ "%Harray subscript is outside array bounds", locus);
+ TREE_NO_WARNING (ref) = 1;
+ }
+ }
+ else if (TREE_CODE (up_sub) == INTEGER_CST
+ && tree_int_cst_lt (up_bound, up_sub)
+ && !tree_int_cst_equal (up_bound, up_sub)
+ && (!ignore_off_by_one
+ || !tree_int_cst_equal (int_const_binop (PLUS_EXPR,
+ up_bound,
+ integer_one_node,
+ 0),
+ up_sub)))
+ {
+ warning (OPT_Warray_bounds, "%Harray subscript is above array bounds",
+ locus);
+ TREE_NO_WARNING (ref) = 1;
+ }
+ else if (TREE_CODE (low_sub) == INTEGER_CST
+ && tree_int_cst_lt (low_sub, low_bound))
+ {
+ warning (OPT_Warray_bounds, "%Harray subscript is below array bounds",
+ locus);
+ TREE_NO_WARNING (ref) = 1;
+ }
+}
+
+/* walk_tree() callback that checks if *TP is
+ an ARRAY_REF inside an ADDR_EXPR (in which an array
+ subscript one outside the valid range is allowed). Call
+ check_array_ref for each ARRAY_REF found. The location is
+ passed in DATA. */
+
+static tree
+check_array_bounds (tree *tp, int *walk_subtree, void *data)
+{
+ tree t = *tp;
+ tree stmt = (tree)data;
+ location_t *location = EXPR_LOCUS (stmt);
+
+ *walk_subtree = TRUE;
+
+ if (TREE_CODE (t) == ARRAY_REF)
+ check_array_ref (t, location, false /*ignore_off_by_one*/);
+ else if (TREE_CODE (t) == ADDR_EXPR)
+ {
+ use_operand_p op;
+ tree use_stmt;
+ t = TREE_OPERAND (t, 0);
+
+ /* Don't warn on statements like
+
+ ssa_name = 500 + &array[-200]
+
+ or
+
+ ssa_name = &array[-200]
+ other_name = ssa_name + 300;
+
+ which are sometimes
+ produced by other optimizing passes. */
+
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+ && BINARY_CLASS_P (GIMPLE_STMT_OPERAND (stmt, 1)))
+ *walk_subtree = FALSE;
+
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
+ && single_imm_use (GIMPLE_STMT_OPERAND (stmt, 0), &op, &use_stmt)
+ && TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT
+ && BINARY_CLASS_P (GIMPLE_STMT_OPERAND (use_stmt, 1)))
+ *walk_subtree = FALSE;
+
+ while (*walk_subtree && handled_component_p (t))
+ {
+ if (TREE_CODE (t) == ARRAY_REF)
+ check_array_ref (t, location, true /*ignore_off_by_one*/);
+ t = TREE_OPERAND (t, 0);
+ }
+ *walk_subtree = FALSE;
+ }
+
+ return NULL_TREE;
+}
+
+/* Walk over all statements of all reachable BBs and call check_array_bounds
+ on them. */
+
+static void
+check_all_array_refs (void)
+{
+ basic_block bb;
+ block_stmt_iterator si;
+
+ FOR_EACH_BB (bb)
+ {
+ /* Skip bb's that are clearly unreachable. */
+ if (single_pred_p (bb))
+ {
+ basic_block pred_bb = EDGE_PRED (bb, 0)->src;
+ tree ls = NULL_TREE;
+
+ if (!bsi_end_p (bsi_last (pred_bb)))
+ ls = bsi_stmt (bsi_last (pred_bb));
+
+ if (ls && TREE_CODE (ls) == COND_EXPR
+ && ((COND_EXPR_COND (ls) == boolean_false_node
+ && (EDGE_PRED (bb, 0)->flags & EDGE_TRUE_VALUE))
+ || (COND_EXPR_COND (ls) == boolean_true_node
+ && (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE))))
+ continue;
+ }
+ for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ walk_tree (bsi_stmt_ptr (si), check_array_bounds,
+ bsi_stmt (si), NULL);
+ }
+}
/* Convert range assertion expressions into the implied copies and
copy propagate away the copies. Doing the trivial copy propagation
/* And finally, remove the copy, it is not needed. */
bsi_remove (&si, true);
+ release_defs (stmt);
}
else
bsi_next (&si);
tree lhs = PHI_RESULT (phi);
value_range_t *lhs_vr = get_value_range (lhs);
value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ bool all_const = true;
copy_value_range (&vr_result, lhs_vr);
value_range_t vr_arg;
if (TREE_CODE (arg) == SSA_NAME)
- vr_arg = *(get_value_range (arg));
+ {
+ vr_arg = *(get_value_range (arg));
+ all_const = false;
+ }
else
{
vr_arg.type = VR_RANGE;
/* To prevent infinite iterations in the algorithm, derive ranges
when the new value is slightly bigger or smaller than the
previous one. */
- if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE)
+ if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE
+ && !all_const)
{
if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
{
cfg_altered = thread_through_all_blocks ();
/* If we threaded jumps, then we need to recompute the dominance
- information, to safely do that we must clean up the CFG first. */
+ information. */
if (cfg_altered)
- {
- free_dominance_info (CDI_DOMINATORS);
- cleanup_tree_cfg ();
- calculate_dominance_info (CDI_DOMINATORS);
- }
+ free_dominance_info (CDI_DOMINATORS);
VEC_free (tree, heap, stack);
}
substitute_and_fold (single_val_range, true);
+ if (warn_array_bounds)
+ check_all_array_refs();
+
/* We must identify jump threading opportunities before we release
the datastructures built by VRP. */
identify_jump_threads ();
OSDN Git Service
