aboutsummaryrefslogtreecommitdiff
path: root/gcc
diff options
context:
space:
mode:
Diffstat (limited to 'gcc')
-rw-r--r--gcc/ChangeLog13
-rw-r--r--gcc/testsuite/ChangeLog4
-rw-r--r--gcc/testsuite/gcc.dg/tree-ssa/vrp17.c39
-rw-r--r--gcc/tree-flow.h1
-rw-r--r--gcc/tree-ssa-propagate.c9
-rw-r--r--gcc/tree-vrp.c292
6 files changed, 250 insertions, 108 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index e19f26f..13ddd5c 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,16 @@
+2005-07-06 Jeff Law <law@redhat.com>
+
+ * tree-vrp.c (simplify_using_ranges): Kill.
+ (vrp_finalize): Remove call to simplify_using_ranges.
+ (simplify_stmt_using_ranges): New function extracted from
+ simplify_using_ranges.
+ (simplify_div_or_mod_using_ranges): Likewise.
+ (simplify_abs_using_ranges): Likewise.
+ (simplify_cond_using_ranges): New function.
+ * tree-flow.h (simplify_stmt_using_ranges): Prototype.
+ * tree-ssa-propagate.c (substitute_and_fold): Call
+ simplify_stmt_using_ranges if we have range information.
+
2005-07-06 James E. Wilson <wilson@specifixinc.com>
* config/ia64/ia64.c (ia64_reorg): Check optimize before
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 1cbe9d6..7c793be 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2005-07-06 Jeff Law <law@redhat.com>
+
+ * gcc.dg/tree-ssa/vrp17.c: New test.
+
2005-07-07 Feng Wang <fengwang@nudt.edu.cn>
PR fortran/22327
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp17.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp17.c
new file mode 100644
index 0000000..b4e0a5b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp17.c
@@ -0,0 +1,39 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp" } */
+
+extern void abort (void) __attribute__ ((__noreturn__));
+union tree_node;
+typedef union tree_node *tree;
+extern const unsigned char tree_code_length[];
+struct tree_common
+{
+ int code;
+};
+struct tree_exp
+{
+ tree operands[1];
+};
+union tree_node
+{
+ struct tree_common common;
+ struct tree_exp exp;
+};
+int
+gimplify_for_stmt (tree * stmt_p, tree * pre_p)
+{
+ tree stmt = *stmt_p;
+ arf (({
+ if (3 >= tree_code_length[stmt->common.code])
+ abort ();
+ stmt->exp.operands[3];
+ }),
+ ({
+ if (2 >= tree_code_length[stmt->common.code])
+ abort ();
+ stmt->exp.operands[2];
+ }));
+}
+
+/* { dg-final { scan-tree-dump-times "== 3" 1 "vrp" } } */
+/* { dg-final { cleanup-tree-dump "vrp" } } */
+
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index 4a11a4e..773a76f 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -626,6 +626,7 @@ tree widen_bitfield (tree, tree, tree);
/* In tree-vrp.c */
bool expr_computes_nonzero (tree);
tree vrp_evaluate_conditional (tree, bool);
+void simplify_stmt_using_ranges (tree);
/* In tree-ssa-dom.c */
extern void dump_dominator_optimization_stats (FILE *);
diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index ce73ae3..b9b308e 100644
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -1108,7 +1108,14 @@ substitute_and_fold (prop_value_t *prop_value, bool use_ranges_p)
/* If we have range information, see if we can fold
predicate expressions. */
if (use_ranges_p)
- did_replace = fold_predicate_in (stmt);
+ {
+ did_replace = fold_predicate_in (stmt);
+
+ /* Some statements may be simplified using ranges. For
+ example, division may be replaced by shifts, modulo
+ replaced with bitwise and, etc. */
+ simplify_stmt_using_ranges (stmt);
+ }
if (prop_value)
{
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 1167e38..91be397 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -3493,127 +3493,211 @@ varying:
return SSA_PROP_VARYING;
}
-/* Walk through the IL simplifying expressions using knowledge
- gathered by VRP. */
+/* Simplify a division or modulo operator to a right shift or
+ bitwise and if the first operand is unsigned or is greater
+ than zero and the second operand is an exact power of two. */
static void
-simplify_using_ranges (void)
+simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code)
{
- basic_block bb;
+ tree val = NULL;
+ tree op = TREE_OPERAND (rhs, 0);
+ value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
- FOR_EACH_BB (bb)
+ if (TYPE_UNSIGNED (TREE_TYPE (op)))
+ {
+ val = integer_one_node;
+ }
+ else
+ {
+ val = compare_range_with_value (GT_EXPR, vr, integer_zero_node);
+ }
+
+ if (val && integer_onep (val))
{
- block_stmt_iterator bsi;
+ tree t;
+ tree op0 = TREE_OPERAND (rhs, 0);
+ tree op1 = TREE_OPERAND (rhs, 1);
+
+ if (rhs_code == TRUNC_DIV_EXPR)
+ {
+ t = build_int_cst (NULL_TREE, tree_log2 (op1));
+ t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
+ }
+ else
+ {
+ t = build_int_cst (TREE_TYPE (op1), 1);
+ t = int_const_binop (MINUS_EXPR, op1, t, 0);
+ t = fold_convert (TREE_TYPE (op0), t);
+ t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
+ }
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ TREE_OPERAND (stmt, 1) = t;
+ update_stmt (stmt);
+ }
+}
+
+/* If the operand to an ABS_EXPR is >= 0, then eliminate the
+ ABS_EXPR. If the operand is <= 0, then simplify the
+ ABS_EXPR into a NEGATE_EXPR. */
+
+static void
+simplify_abs_using_ranges (tree stmt, tree rhs)
+{
+ tree val = NULL;
+ tree op = TREE_OPERAND (rhs, 0);
+ tree type = TREE_TYPE (op);
+ value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
+
+ if (TYPE_UNSIGNED (type))
+ {
+ val = integer_zero_node;
+ }
+ else if (vr)
+ {
+ val = compare_range_with_value (LE_EXPR, vr, integer_zero_node);
+ if (!val)
{
- tree stmt = bsi_stmt (bsi);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node);
- if (TREE_CODE (stmt) == MODIFY_EXPR)
+ if (val)
{
- tree rhs = TREE_OPERAND (stmt, 1);
- enum tree_code rhs_code = TREE_CODE (rhs);
-
- /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
- and BIT_AND_EXPR respectively if the first operand is greater
- than zero and the second operand is an exact power of two. */
- if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
- && integer_pow2p (TREE_OPERAND (rhs, 1)))
- {
- tree val = NULL;
- tree op = TREE_OPERAND (rhs, 0);
- value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
-
- if (TYPE_UNSIGNED (TREE_TYPE (op)))
- {
- val = integer_one_node;
- }
- else
- {
- val = compare_range_with_value (GT_EXPR, vr,
- integer_zero_node);
- }
-
- if (val && integer_onep (val))
- {
- tree t;
- tree op0 = TREE_OPERAND (rhs, 0);
- tree op1 = TREE_OPERAND (rhs, 1);
-
- if (rhs_code == TRUNC_DIV_EXPR)
- {
- t = build_int_cst (NULL_TREE, tree_log2 (op1));
- t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
- }
- else
- {
- t = build_int_cst (TREE_TYPE (op1), 1);
- t = int_const_binop (MINUS_EXPR, op1, t, 0);
- t = fold_convert (TREE_TYPE (op0), t);
- t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
- }
-
- TREE_OPERAND (stmt, 1) = t;
- update_stmt (stmt);
- }
+ if (integer_zerop (val))
+ val = integer_one_node;
+ else if (integer_onep (val))
+ val = integer_zero_node;
+ }
+ }
+
+ if (val
+ && (integer_onep (val) || integer_zerop (val)))
+ {
+ tree t;
+ if (integer_onep (val))
+ t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
+ else
+ t = op;
+
+ TREE_OPERAND (stmt, 1) = t;
+ update_stmt (stmt);
+ }
+ }
+}
+
+/* Simplify a conditional using a relational operator to an equality
+ test if the range information indicates only one value can satisfy
+ the original conditional. */
+
+static void
+simplify_cond_using_ranges (tree stmt)
+{
+ tree cond = COND_EXPR_COND (stmt);
+ tree op0 = TREE_OPERAND (cond, 0);
+ tree op1 = TREE_OPERAND (cond, 1);
+ enum tree_code cond_code = TREE_CODE (cond);
+
+ if (cond_code != NE_EXPR
+ && cond_code != EQ_EXPR
+ && TREE_CODE (op0) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ && is_gimple_min_invariant (op1))
+ {
+ value_range_t *vr = get_value_range (op0);
+
+ /* If we have range information for OP0, then we might be
+ able to simplify this conditional. */
+ if (vr->type == VR_RANGE)
+ {
+ tree min = NULL;
+ tree max = NULL;
+
+ /* Extract minimum/maximum values which satisfy the
+ the conditional as it was written. */
+ if (cond_code == LE_EXPR || cond_code == LT_EXPR)
+ {
+ min = TYPE_MIN_VALUE (TREE_TYPE (op0));
+
+ max = op1;
+ if (cond_code == LT_EXPR)
+ {
+ tree one = build_int_cst (TREE_TYPE (op0), 1);
+ max = fold (build (MINUS_EXPR, TREE_TYPE (op0), max, one));
}
+ }
+ else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
+ {
+ max = TYPE_MAX_VALUE (TREE_TYPE (op0));
- /* Transform ABS (X) into X or -X as appropriate. */
- if (rhs_code == ABS_EXPR
- && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
+ min = op1;
+ if (cond_code == GT_EXPR)
{
- tree val = NULL;
- tree op = TREE_OPERAND (rhs, 0);
- tree type = TREE_TYPE (op);
- value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
-
- if (TYPE_UNSIGNED (type))
- {
- val = integer_zero_node;
- }
- else if (vr)
- {
- val = compare_range_with_value (LE_EXPR, vr,
- integer_zero_node);
- if (!val)
- {
- val = compare_range_with_value (GE_EXPR, vr,
- integer_zero_node);
-
- if (val)
- {
- if (integer_zerop (val))
- val = integer_one_node;
- else if (integer_onep (val))
- val = integer_zero_node;
- }
- }
-
- if (val
- && (integer_onep (val) || integer_zerop (val)))
- {
- tree t;
-
- if (integer_onep (val))
- t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
- else
- t = op;
-
- TREE_OPERAND (stmt, 1) = t;
- update_stmt (stmt);
- }
- }
+ tree one = build_int_cst (TREE_TYPE (op0), 1);
+ max = fold (build (PLUS_EXPR, TREE_TYPE (op0), max, one));
}
}
- /* TODO. Simplify conditionals. */
+ /* Now refine the minimum and maximum values using any
+ value range information we have for op0. */
+ if (min && max)
+ {
+ if (compare_values (vr->min, min) == -1)
+ min = min;
+ else
+ min = vr->min;
+ if (compare_values (vr->max, max) == 1)
+ max = max;
+ else
+ max = vr->max;
+
+ /* If the new min/max values have converged to a
+ single value, then there is only one value which
+ can satisfy the condition. Rewrite the condition
+ to test for equality. */
+ if (min == max
+ && is_gimple_min_invariant (min))
+ {
+ COND_EXPR_COND (stmt)
+ = build (EQ_EXPR, boolean_type_node, op0, min);
+ update_stmt (stmt);
+ }
+ }
}
}
}
+/* Simplify STMT using ranges if possible. */
+
+void
+simplify_stmt_using_ranges (tree stmt)
+{
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ {
+ tree rhs = TREE_OPERAND (stmt, 1);
+ enum tree_code rhs_code = TREE_CODE (rhs);
+
+ /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
+ and BIT_AND_EXPR respectively if the first operand is greater
+ than zero and the second operand is an exact power of two. */
+ if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
+ && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
+ && integer_pow2p (TREE_OPERAND (rhs, 1)))
+ simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code);
+
+ /* Transform ABS (X) into X or -X as appropriate. */
+ if (rhs_code == ABS_EXPR
+ && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
+ simplify_abs_using_ranges (stmt, rhs);
+ }
+ else if (TREE_CODE (stmt) == COND_EXPR
+ && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
+ {
+ simplify_cond_using_ranges (stmt);
+ }
+}
+
+
/* Traverse all the blocks folding conditionals with known ranges. */
@@ -3657,12 +3741,6 @@ vrp_finalize (void)
substitute_and_fold (single_val_range, true);
- /* One could argue all simplifications should be done here
- rather than using substitute_and_fold since this code
- is going to have to perform a complete walk through the
- IL anyway. */
- simplify_using_ranges ();
-
/* Free allocated memory. */
for (i = 0; i < num_ssa_names; i++)
if (vr_value[i])
generated by cgit v1.1 at 2025-06-05 18:16:59 +0000