* [patch tree-optimization]: [3 of 3]: Boolify compares & more
@ 2011-07-07 16:14 Kai Tietz
2011-07-07 16:19 ` Paolo Bonzini
2011-07-08 9:39 ` Richard Guenther
0 siblings, 2 replies; 18+ messages in thread
From: Kai Tietz @ 2011-07-07 16:14 UTC (permalink / raw)
To: GCC Patches; +Cc: Richard Guenther
Hello,
This patch - third of series - fixes vrp to handle bitwise one-bit
precision typed operations.
And it introduces a second - limitted to non-switch-statement range - vrp pass.
Bootstrapped and regression tested for all standard-languages (plus
Ada and Obj-C++) on host x86_64-pc-linux-gnu.
Ok for apply?
Regards,
Kai
ChangeLog
2011-07-07 Kai Tietz <ktietz@redhat.com>
* tree-vrp.c (in_second_pass): New static variable.
(extract_range_from_binary_expr): Add handling for
BIT_IOR_EXPR, BIT_AND_EXPR, and BIT_NOT_EXPR.
(register_edge_assert_for_1): Add handling for 1-bit
BIT_IOR_EXPR and BIT_NOT_EXPR.
(register_edge_assert_for): Add handling for 1-bit
BIT_IOR_EXPR.
(ssa_name_get_inner_ssa_name_p): New helper function.
(ssa_name_get_cast_to_p): New helper function.
(simplify_truth_ops_using_ranges): Handle prefixed
cast instruction for result, and add support for one
bit precision BIT_IOR_EXPR, BIT_AND_EXPR, BIT_XOR_EXPR,
, and BIT_NOT_EXPR.
(simplify_stmt_using_ranges): Add handling for one bit
precision BIT_IOR_EXPR, BIT_AND_EXPR, BIT_XOR_EXPR,
and BIT_NOT_EXPR.
(vrp_finalize): Do substitute and fold pass a second
time for vrp_stmt and preserve switch-edge simplification
on second run.
(simplify_switch_using_ranges): Preserve rerun of function
in second pass.
Index: gcc-head/gcc/tree-vrp.c
===================================================================
--- gcc-head.orig/gcc/tree-vrp.c
+++ gcc-head/gcc/tree-vrp.c
@@ -74,6 +74,9 @@ struct value_range_d
typedef struct value_range_d value_range_t;
+/* This flag indicates that we are doing a second pass of VRP. */
+static bool in_second_pass = false;
+
/* Set of SSA names found live during the RPO traversal of the function
for still active basic-blocks. */
static sbitmap *live;
@@ -2232,6 +2235,7 @@ extract_range_from_binary_expr (value_ra
some cases. */
if (code != BIT_AND_EXPR
&& code != TRUTH_AND_EXPR
+ && code != BIT_IOR_EXPR
&& code != TRUTH_OR_EXPR
&& code != TRUNC_DIV_EXPR
&& code != FLOOR_DIV_EXPR
@@ -2291,6 +2295,8 @@ extract_range_from_binary_expr (value_ra
else
set_value_range_to_varying (vr);
}
+ else if (code == BIT_IOR_EXPR)
+ set_value_range_to_varying (vr);
else
gcc_unreachable ();
@@ -2300,11 +2306,13 @@ extract_range_from_binary_expr (value_ra
/* For integer ranges, apply the operation to each end of the
range and see what we end up with. */
if (code == TRUTH_AND_EXPR
- || code == TRUTH_OR_EXPR)
+ || code == TRUTH_OR_EXPR
+ || ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+ && TYPE_PRECISION (TREE_TYPE (op1)) == 1))
{
/* If one of the operands is zero, we know that the whole
expression evaluates zero. */
- if (code == TRUTH_AND_EXPR
+ if ((code == TRUTH_AND_EXPR || code == BIT_AND_EXPR)
&& ((vr0.type == VR_RANGE
&& integer_zerop (vr0.min)
&& integer_zerop (vr0.max))
@@ -2317,7 +2325,7 @@ extract_range_from_binary_expr (value_ra
}
/* If one of the operands is one, we know that the whole
expression evaluates one. */
- else if (code == TRUTH_OR_EXPR
+ else if ((code == TRUTH_OR_EXPR || code == BIT_IOR_EXPR)
&& ((vr0.type == VR_RANGE
&& integer_onep (vr0.min)
&& integer_onep (vr0.max))
@@ -2809,7 +2817,7 @@ extract_range_from_unary_expr (value_ran
cannot easily determine a resulting range. */
if (code == FIX_TRUNC_EXPR
|| code == FLOAT_EXPR
- || code == BIT_NOT_EXPR
+ || (code == BIT_NOT_EXPR && TYPE_PRECISION (type) != 1)
|| code == CONJ_EXPR)
{
/* We can still do constant propagation here. */
@@ -3976,7 +3984,9 @@ build_assert_expr_for (tree cond, tree v
tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
assertion = gimple_build_assign (n, a);
}
- else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
+ else if (TREE_CODE (cond) == TRUTH_NOT_EXPR
+ || (TREE_CODE (cond) == BIT_NOT_EXPR
+ && TYPE_PRECISION (TREE_TYPE (cond)) == 1))
{
/* Given !V, build the assignment N = false. */
tree op0 = TREE_OPERAND (cond, 0);
@@ -4531,7 +4541,9 @@ register_edge_assert_for_1 (tree op, enu
retval |= register_edge_assert_for_1 (gimple_assign_rhs2 (op_def),
code, e, bsi);
}
- else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR)
+ else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR
+ || (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
+ && TYPE_PRECISION (TREE_TYPE (op)) == 1))
{
/* Recurse, flipping CODE. */
code = invert_tree_comparison (code, false);
@@ -4617,6 +4629,9 @@ register_edge_assert_for (tree name, edg
if (is_gimple_assign (def_stmt)
&& (gimple_assign_rhs_code (def_stmt) == TRUTH_OR_EXPR
+ || (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR
+ && INTEGRAL_TYPE_P (TREE_TYPE (name))
+ && TYPE_PRECISION (TREE_TYPE (name)) == 1)
/* For BIT_IOR_EXPR only if NAME == 0 both operands have
necessarily zero value. */
|| (comp_code == EQ_EXPR
@@ -6747,19 +6762,96 @@ varying:
return SSA_PROP_VARYING;
}
+/* Returns operand1 of ssa-name with SSA_NAME as code, Otherwise it
+ returns NULL_TREE. */
+static tree
+ssa_name_get_inner_ssa_name_p (tree op)
+{
+ gimple stmt;
+
+ if (TREE_CODE (op) != SSA_NAME
+ || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
+ return NULL_TREE;
+ stmt = SSA_NAME_DEF_STMT (op);
+ if (gimple_assign_rhs_code (stmt) != SSA_NAME)
+ return NULL_TREE;
+ return gimple_assign_rhs1 (stmt);
+}
+
+/* Returns operand of cast operation, if OP is a type-conversion. Otherwise
+ return NULL_TREE. */
+static tree
+ssa_name_get_cast_to_p (tree op)
+{
+ gimple stmt;
+
+ if (TREE_CODE (op) != SSA_NAME
+ || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
+ return NULL_TREE;
+ stmt = SSA_NAME_DEF_STMT (op);
+ if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
+ return NULL_TREE;
+ return gimple_assign_rhs1 (stmt);
+}
+
/* Simplify boolean operations if the source is known
to be already a boolean. */
static bool
simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
{
enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+ gimple stmt2 = stmt;
tree val = NULL;
- tree op0, op1;
+ tree op0, op1, cop0, cop1;
value_range_t *vr;
bool sop = false;
bool need_conversion;
+ location_t loc = gimple_location (stmt);
op0 = gimple_assign_rhs1 (stmt);
+ op1 = NULL_TREE;
+
+ /* Handle cases with prefixed type-cast. */
+ if (CONVERT_EXPR_CODE_P (rhs_code)
+ && INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ && TREE_CODE (op0) == SSA_NAME
+ && is_gimple_assign (SSA_NAME_DEF_STMT (op0))
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
+ {
+ stmt2 = SSA_NAME_DEF_STMT (op0);
+ op0 = gimple_assign_rhs1 (stmt2);
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)))
+ return false;
+ rhs_code = gimple_assign_rhs_code (stmt2);
+ if (rhs_code != BIT_NOT_EXPR && rhs_code != TRUTH_NOT_EXPR
+ && rhs_code != TRUTH_AND_EXPR && rhs_code != BIT_AND_EXPR
+ && rhs_code != TRUTH_OR_EXPR && rhs_code != BIT_IOR_EXPR
+ && rhs_code != TRUTH_XOR_EXPR && rhs_code != BIT_XOR_EXPR
+ && rhs_code != NE_EXPR && rhs_code != EQ_EXPR)
+ return false;
+ if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
+ || rhs_code == BIT_XOR_EXPR || rhs_code == TRUTH_AND_EXPR
+ || rhs_code == TRUTH_OR_EXPR || rhs_code == TRUTH_XOR_EXPR
+ || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
+ op1 = gimple_assign_rhs2 (stmt2);
+ if (gimple_has_location (stmt2))
+ loc = gimple_location (stmt2);
+ }
+ else if (CONVERT_EXPR_CODE_P (rhs_code))
+ return false;
+ else if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
+ || rhs_code == BIT_XOR_EXPR || rhs_code == TRUTH_AND_EXPR
+ || rhs_code == TRUTH_OR_EXPR || rhs_code == TRUTH_XOR_EXPR
+ || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
+ op1 = gimple_assign_rhs2 (stmt);
+
+ /* ~X is only equivalent of !X, if type-precision is one and X has
+ an integral type. */
+ if (rhs_code == BIT_NOT_EXPR
+ && (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ || TYPE_PRECISION (TREE_TYPE (op0)) != 1))
+ return false;
+
if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
{
if (TREE_CODE (op0) != SSA_NAME)
@@ -6775,22 +6867,100 @@ simplify_truth_ops_using_ranges (gimple_
return false;
}
- if (rhs_code == TRUTH_NOT_EXPR)
+ if (op1 && TREE_CODE (op1) != INTEGER_CST
+ && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
+ {
+ vr = get_value_range (op1);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+
+ need_conversion =
+ !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
+ TREE_TYPE (op0));
+
+ /* As comparisons X != 0 getting folded by prior pass to (bool) X,
+ but X == 0 might be not folded for none boolean type of X
+ to (bool) (X ^ 1).
+ So for bitwise-binary operations we have three cases to handle:
+ a) ((bool) X) op ((bool) Y)
+ b) ((bool) X) op (Y == 0) OR (X == 0) op ((bool) Y)
+ c) (X == 0) op (Y == 0)
+ The later two cases can't be handled for now, as vr tables
+ would need to be adjusted. */
+ if (need_conversion
+ && (rhs_code == BIT_XOR_EXPR
+ || rhs_code == BIT_AND_EXPR
+ || rhs_code == BIT_IOR_EXPR)
+ && TREE_CODE (op1) == SSA_NAME && TREE_CODE (op0) == SSA_NAME)
+ {
+ cop0 = ssa_name_get_cast_to_p (op0);
+ cop1 = ssa_name_get_cast_to_p (op1);
+ if (!cop0 || !cop1)
+ /* We would need an new statment for cases b and c, and we can't
+ due vr table, so bail out. */
+ return false;
+
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (cop0))
+ || !types_compatible_p (TREE_TYPE (cop0), TREE_TYPE (cop1)))
+ return false;
+ need_conversion =
+ !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
+ TREE_TYPE (cop0));
+ if (need_conversion)
+ return false;
+ op0 = cop0;
+ op1 = cop1;
+
+ /* We need to re-check if value ranges for new operands
+ for 1-bit precision/range. */
+ if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
+ {
+ if (TREE_CODE (op0) != SSA_NAME)
+ return false;
+ vr = get_value_range (op0);
+
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+
+ if (op1 && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
+ {
+ vr = get_value_range (op1);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+ }
+ else if (rhs_code == TRUTH_NOT_EXPR || rhs_code == BIT_NOT_EXPR)
{
rhs_code = NE_EXPR;
op1 = build_int_cst (TREE_TYPE (op0), 1);
}
else
{
- op1 = gimple_assign_rhs2 (stmt);
-
/* Reduce number of cases to handle. */
if (is_gimple_min_invariant (op1))
{
/* Exclude anything that should have been already folded. */
if (rhs_code != EQ_EXPR
&& rhs_code != NE_EXPR
- && rhs_code != TRUTH_XOR_EXPR)
+ && rhs_code != TRUTH_XOR_EXPR
+ && rhs_code != BIT_XOR_EXPR)
return false;
if (!integer_zerop (op1)
@@ -6810,18 +6980,6 @@ simplify_truth_ops_using_ranges (gimple_
/* Punt on A == B as there is no BIT_XNOR_EXPR. */
if (rhs_code == EQ_EXPR)
return false;
-
- if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
- {
- vr = get_value_range (op1);
- val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
- if (!val || !integer_onep (val))
- return false;
-
- val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
- if (!val || !integer_onep (val))
- return false;
- }
}
}
@@ -6838,7 +6996,8 @@ simplify_truth_ops_using_ranges (gimple_
warning_at (location, OPT_Wstrict_overflow,
_("assuming signed overflow does not occur when "
"simplifying && or || to & or |"));
- else
+ else if (rhs_code != BIT_AND_EXPR && rhs_code != BIT_IOR_EXPR
+ && rhs_code != BIT_XOR_EXPR)
warning_at (location, OPT_Wstrict_overflow,
_("assuming signed overflow does not occur when "
"simplifying ==, != or ! to identity or ^"));
@@ -6859,16 +7018,21 @@ simplify_truth_ops_using_ranges (gimple_
case TRUTH_AND_EXPR:
rhs_code = BIT_AND_EXPR;
break;
+ case BIT_AND_EXPR:
+ break;
case TRUTH_OR_EXPR:
rhs_code = BIT_IOR_EXPR;
+ case BIT_IOR_EXPR:
break;
case TRUTH_XOR_EXPR:
+ case BIT_XOR_EXPR:
case NE_EXPR:
if (integer_zerop (op1))
{
gimple_assign_set_rhs_with_ops (gsi,
need_conversion ? NOP_EXPR : SSA_NAME,
op0, NULL);
+ gimple_set_location (stmt, loc);
update_stmt (gsi_stmt (*gsi));
return true;
}
@@ -6879,10 +7043,20 @@ simplify_truth_ops_using_ranges (gimple_
gcc_unreachable ();
}
+ /* We can't insert here new expression as otherwise
+ tracked vr tables getting out of bounds. */
if (need_conversion)
return false;
+ /* Reduce here SSA_NAME -> SSA_NAME. */
+ while ((cop0 = ssa_name_get_inner_ssa_name_p (op0)) != NULL_TREE)
+ op0 = cop0;
+
+ while ((cop1 = ssa_name_get_inner_ssa_name_p (op1)) != NULL_TREE)
+ op1 = cop1;
+
gimple_assign_set_rhs_with_ops (gsi, rhs_code, op0, op1);
+ gimple_set_location (stmt, loc);
update_stmt (gsi_stmt (*gsi));
return true;
}
@@ -7263,6 +7437,9 @@ simplify_switch_using_ranges (gimple stm
tree vec2;
switch_update su;
+ if (in_second_pass)
+ return false;
+
if (TREE_CODE (op) == SSA_NAME)
{
vr = get_value_range (op);
@@ -7390,6 +7567,7 @@ simplify_stmt_using_ranges (gimple_stmt_
{
case EQ_EXPR:
case NE_EXPR:
+ case BIT_NOT_EXPR:
case TRUTH_NOT_EXPR:
case TRUTH_AND_EXPR:
case TRUTH_OR_EXPR:
@@ -7425,13 +7603,21 @@ simplify_stmt_using_ranges (gimple_stmt_
if all the bits being cleared are already cleared or
all the bits being set are already set. */
if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
- return simplify_bit_ops_using_ranges (gsi, stmt);
+ {
+ if (simplify_truth_ops_using_ranges (gsi, stmt))
+ return true;
+ return simplify_bit_ops_using_ranges (gsi, stmt);
+ }
break;
CASE_CONVERT:
if (TREE_CODE (rhs1) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
- return simplify_conversion_using_ranges (stmt);
+ {
+ if (simplify_truth_ops_using_ranges (gsi, stmt))
+ return true;
+ return simplify_conversion_using_ranges (stmt);
+ }
break;
default:
@@ -7685,8 +7870,16 @@ vrp_finalize (void)
fprintf (dump_file, "\n");
}
+ /* We redo folding here one time for allowing to inspect more
+ complex reductions. */
+ substitute_and_fold (op_with_constant_singleton_value_range,
+ vrp_fold_stmt, false);
+ /* We need to mark this second pass to avoid re-entering of same
+ edges for switch statments. */
+ in_second_pass = true;
substitute_and_fold (op_with_constant_singleton_value_range,
vrp_fold_stmt, false);
+ in_second_pass = false;
if (warn_array_bounds)
check_all_array_refs ();
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-07 16:14 [patch tree-optimization]: [3 of 3]: Boolify compares & more Kai Tietz
@ 2011-07-07 16:19 ` Paolo Bonzini
2011-07-07 16:28 ` Kai Tietz
2011-07-08 9:39 ` Richard Guenther
1 sibling, 1 reply; 18+ messages in thread
From: Paolo Bonzini @ 2011-07-07 16:19 UTC (permalink / raw)
To: Kai Tietz; +Cc: GCC Patches, Richard Guenther
On 07/07/2011 06:07 PM, Kai Tietz wrote:
> + /* We redo folding here one time for allowing to inspect more
> + complex reductions. */
> + substitute_and_fold (op_with_constant_singleton_value_range,
> + vrp_fold_stmt, false);
> + /* We need to mark this second pass to avoid re-entering of same
> + edges for switch statments. */
> + in_second_pass = true;
> substitute_and_fold (op_with_constant_singleton_value_range,
> vrp_fold_stmt, false);
> + in_second_pass = false;
This needs a much better explanation.
Paolo
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-07 16:19 ` Paolo Bonzini
@ 2011-07-07 16:28 ` Kai Tietz
2011-07-08 9:45 ` Richard Guenther
0 siblings, 1 reply; 18+ messages in thread
From: Kai Tietz @ 2011-07-07 16:28 UTC (permalink / raw)
To: Paolo Bonzini; +Cc: GCC Patches, Richard Guenther
2011/7/7 Paolo Bonzini <bonzini@gnu.org>:
> On 07/07/2011 06:07 PM, Kai Tietz wrote:
>>
>> + /* We redo folding here one time for allowing to inspect more
>> + complex reductions. */
>> + substitute_and_fold (op_with_constant_singleton_value_range,
>> + vrp_fold_stmt, false);
>> + /* We need to mark this second pass to avoid re-entering of same
>> + edges for switch statments. */
>> + in_second_pass = true;
>> substitute_and_fold (op_with_constant_singleton_value_range,
>> vrp_fold_stmt, false);
>> + in_second_pass = false;
>
> This needs a much better explanation.
>
> Paolo
Well, I can work on a better comment. The complex reduction I mean
here are cases like
int x;
int y;
_Bool D1;
_Bool D2;
_Bool D3;
int R;
D1 = x[0..1] != 0;
D2 = y[0..1] != 0;
D3 = D1 & D2
R = (int) D3
(testcase is already present. See tree-ssa/vrp47.c).
As VRP in first pass produces (and replaces) to:
D1 = (_Bool) x[0..1];
D2 = (_Bool) y[0..1];
D3 = D1 & D2
R = (int) D3
Just in the second pass the reduction
R = x[0..1] & y[0..1]
can happen. In general it is sad that VRP can't insert during pass
new statements right now. This would cause issues in range-tables,
which aren't designed for insertations. As otherwise, we could do
also simplify things like
D1 = x[0..1] != 0;
D2 = y[0..1] == 0;
D3 = D1 & D2
R = (int) D3
to
R = x[0..1] & (y[0..1] ^ 1)
Regards,
Kai
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-07 16:14 [patch tree-optimization]: [3 of 3]: Boolify compares & more Kai Tietz
2011-07-07 16:19 ` Paolo Bonzini
@ 2011-07-08 9:39 ` Richard Guenther
2011-07-08 15:49 ` Kai Tietz
1 sibling, 1 reply; 18+ messages in thread
From: Richard Guenther @ 2011-07-08 9:39 UTC (permalink / raw)
To: Kai Tietz; +Cc: GCC Patches
On Thu, Jul 7, 2011 at 6:07 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Hello,
>
> This patch - third of series - fixes vrp to handle bitwise one-bit
> precision typed operations.
> And it introduces a second - limitted to non-switch-statement range - vrp pass.
Err - please split this patch. I agree with Paolo, this 2nd
substitute_and_fold call is bogus. More comments inline.
>
> Bootstrapped and regression tested for all standard-languages (plus
> Ada and Obj-C++) on host x86_64-pc-linux-gnu.
>
> Ok for apply?
>
> Regards,
> Kai
>
> ChangeLog
>
> 2011-07-07 Kai Tietz <ktietz@redhat.com>
>
> * tree-vrp.c (in_second_pass): New static variable.
> (extract_range_from_binary_expr): Add handling for
> BIT_IOR_EXPR, BIT_AND_EXPR, and BIT_NOT_EXPR.
> (register_edge_assert_for_1): Add handling for 1-bit
> BIT_IOR_EXPR and BIT_NOT_EXPR.
> (register_edge_assert_for): Add handling for 1-bit
> BIT_IOR_EXPR.
> (ssa_name_get_inner_ssa_name_p): New helper function.
> (ssa_name_get_cast_to_p): New helper function.
> (simplify_truth_ops_using_ranges): Handle prefixed
> cast instruction for result, and add support for one
> bit precision BIT_IOR_EXPR, BIT_AND_EXPR, BIT_XOR_EXPR,
> , and BIT_NOT_EXPR.
> (simplify_stmt_using_ranges): Add handling for one bit
> precision BIT_IOR_EXPR, BIT_AND_EXPR, BIT_XOR_EXPR,
> and BIT_NOT_EXPR.
> (vrp_finalize): Do substitute and fold pass a second
> time for vrp_stmt and preserve switch-edge simplification
> on second run.
> (simplify_switch_using_ranges): Preserve rerun of function
> in second pass.
>
> Index: gcc-head/gcc/tree-vrp.c
> ===================================================================
> --- gcc-head.orig/gcc/tree-vrp.c
> +++ gcc-head/gcc/tree-vrp.c
> @@ -74,6 +74,9 @@ struct value_range_d
>
> typedef struct value_range_d value_range_t;
>
> +/* This flag indicates that we are doing a second pass of VRP. */
> +static bool in_second_pass = false;
> +
> /* Set of SSA names found live during the RPO traversal of the function
> for still active basic-blocks. */
> static sbitmap *live;
> @@ -2232,6 +2235,7 @@ extract_range_from_binary_expr (value_ra
> some cases. */
> if (code != BIT_AND_EXPR
> && code != TRUTH_AND_EXPR
> + && code != BIT_IOR_EXPR
Huh? So how would VARYING | x ever produce something better
than VARYING?
> && code != TRUTH_OR_EXPR
> && code != TRUNC_DIV_EXPR
> && code != FLOOR_DIV_EXPR
> @@ -2291,6 +2295,8 @@ extract_range_from_binary_expr (value_ra
> else
> set_value_range_to_varying (vr);
> }
> + else if (code == BIT_IOR_EXPR)
> + set_value_range_to_varying (vr);
err - BIT_IOR_EXPR on pointers?
> else
> gcc_unreachable ();
>
> @@ -2300,11 +2306,13 @@ extract_range_from_binary_expr (value_ra
> /* For integer ranges, apply the operation to each end of the
> range and see what we end up with. */
> if (code == TRUTH_AND_EXPR
> - || code == TRUTH_OR_EXPR)
> + || code == TRUTH_OR_EXPR
> + || ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
> + && TYPE_PRECISION (TREE_TYPE (op1)) == 1))
Rather than adding code to handle BIT_*_EXPR this patch should
transform the TRUTH_*_EXPR handling to appropriate BIT_*_EXPR
handling as we no longer have TRUTH_*_EXPR in our IL.
In fact I would say the existing BIT_*_EXPR handling should already
cover all the TRUTH_*_CASES, so this patch patches the wrong
spot if it is necessary at all.
> {
> /* If one of the operands is zero, we know that the whole
> expression evaluates zero. */
> - if (code == TRUTH_AND_EXPR
> + if ((code == TRUTH_AND_EXPR || code == BIT_AND_EXPR)
> && ((vr0.type == VR_RANGE
> && integer_zerop (vr0.min)
> && integer_zerop (vr0.max))
> @@ -2317,7 +2325,7 @@ extract_range_from_binary_expr (value_ra
> }
> /* If one of the operands is one, we know that the whole
> expression evaluates one. */
> - else if (code == TRUTH_OR_EXPR
> + else if ((code == TRUTH_OR_EXPR || code == BIT_IOR_EXPR)
> && ((vr0.type == VR_RANGE
> && integer_onep (vr0.min)
> && integer_onep (vr0.max))
> @@ -2809,7 +2817,7 @@ extract_range_from_unary_expr (value_ran
> cannot easily determine a resulting range. */
> if (code == FIX_TRUNC_EXPR
> || code == FLOAT_EXPR
> - || code == BIT_NOT_EXPR
> + || (code == BIT_NOT_EXPR && TYPE_PRECISION (type) != 1)
> || code == CONJ_EXPR)
> {
> /* We can still do constant propagation here. */
> @@ -3976,7 +3984,9 @@ build_assert_expr_for (tree cond, tree v
> tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
> assertion = gimple_build_assign (n, a);
> }
> - else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
> + else if (TREE_CODE (cond) == TRUTH_NOT_EXPR
> + || (TREE_CODE (cond) == BIT_NOT_EXPR
> + && TYPE_PRECISION (TREE_TYPE (cond)) == 1))
> {
> /* Given !V, build the assignment N = false. */
> tree op0 = TREE_OPERAND (cond, 0);
> @@ -4531,7 +4541,9 @@ register_edge_assert_for_1 (tree op, enu
> retval |= register_edge_assert_for_1 (gimple_assign_rhs2 (op_def),
> code, e, bsi);
> }
> - else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR)
> + else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR
> + || (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
> + && TYPE_PRECISION (TREE_TYPE (op)) == 1))
> {
> /* Recurse, flipping CODE. */
> code = invert_tree_comparison (code, false);
> @@ -4617,6 +4629,9 @@ register_edge_assert_for (tree name, edg
>
> if (is_gimple_assign (def_stmt)
> && (gimple_assign_rhs_code (def_stmt) == TRUTH_OR_EXPR
> + || (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR
> + && INTEGRAL_TYPE_P (TREE_TYPE (name))
> + && TYPE_PRECISION (TREE_TYPE (name)) == 1)
> /* For BIT_IOR_EXPR only if NAME == 0 both operands have
> necessarily zero value. */
> || (comp_code == EQ_EXPR
> @@ -6747,19 +6762,96 @@ varying:
> return SSA_PROP_VARYING;
> }
>
> +/* Returns operand1 of ssa-name with SSA_NAME as code, Otherwise it
> + returns NULL_TREE. */
? Why would you want to look through a single copy?
> +static tree
> +ssa_name_get_inner_ssa_name_p (tree op)
> +{
> + gimple stmt;
> +
> + if (TREE_CODE (op) != SSA_NAME
> + || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
> + return NULL_TREE;
> + stmt = SSA_NAME_DEF_STMT (op);
> + if (gimple_assign_rhs_code (stmt) != SSA_NAME)
> + return NULL_TREE;
> + return gimple_assign_rhs1 (stmt);
> +}
> +
> +/* Returns operand of cast operation, if OP is a type-conversion. Otherwise
> + return NULL_TREE. */
> +static tree
> +ssa_name_get_cast_to_p (tree op)
> +{
> + gimple stmt;
> +
> + if (TREE_CODE (op) != SSA_NAME
> + || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
> + return NULL_TREE;
> + stmt = SSA_NAME_DEF_STMT (op);
> + if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
> + return NULL_TREE;
> + return gimple_assign_rhs1 (stmt);
> +}
> +
> /* Simplify boolean operations if the source is known
> to be already a boolean. */
> static bool
> simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
> {
> enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
> + gimple stmt2 = stmt;
> tree val = NULL;
> - tree op0, op1;
> + tree op0, op1, cop0, cop1;
> value_range_t *vr;
> bool sop = false;
> bool need_conversion;
> + location_t loc = gimple_location (stmt);
>
> op0 = gimple_assign_rhs1 (stmt);
> + op1 = NULL_TREE;
> +
> + /* Handle cases with prefixed type-cast. */
What cases? This code lacks comments.
> + if (CONVERT_EXPR_CODE_P (rhs_code)
So this simplifies conversions, not truth ops.
> + && INTEGRAL_TYPE_P (TREE_TYPE (op0))
> + && TREE_CODE (op0) == SSA_NAME
> + && is_gimple_assign (SSA_NAME_DEF_STMT (op0))
> + && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
> + {
> + stmt2 = SSA_NAME_DEF_STMT (op0);
> + op0 = gimple_assign_rhs1 (stmt2);
> + if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)))
> + return false;
> + rhs_code = gimple_assign_rhs_code (stmt2);
> + if (rhs_code != BIT_NOT_EXPR && rhs_code != TRUTH_NOT_EXPR
> + && rhs_code != TRUTH_AND_EXPR && rhs_code != BIT_AND_EXPR
> + && rhs_code != TRUTH_OR_EXPR && rhs_code != BIT_IOR_EXPR
> + && rhs_code != TRUTH_XOR_EXPR && rhs_code != BIT_XOR_EXPR
> + && rhs_code != NE_EXPR && rhs_code != EQ_EXPR)
> + return false;
> + if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
> + || rhs_code == BIT_XOR_EXPR || rhs_code == TRUTH_AND_EXPR
> + || rhs_code == TRUTH_OR_EXPR || rhs_code == TRUTH_XOR_EXPR
> + || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
> + op1 = gimple_assign_rhs2 (stmt2);
> + if (gimple_has_location (stmt2))
> + loc = gimple_location (stmt2);
> + }
> + else if (CONVERT_EXPR_CODE_P (rhs_code))
> + return false;
That's funny control flow.
> + else if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
> + || rhs_code == BIT_XOR_EXPR || rhs_code == TRUTH_AND_EXPR
> + || rhs_code == TRUTH_OR_EXPR || rhs_code == TRUTH_XOR_EXPR
> + || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
> + op1 = gimple_assign_rhs2 (stmt);
> +
> + /* ~X is only equivalent of !X, if type-precision is one and X has
> + an integral type. */
> + if (rhs_code == BIT_NOT_EXPR
> + && (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
> + || TYPE_PRECISION (TREE_TYPE (op0)) != 1))
> + return false;
> +
> if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
> {
> if (TREE_CODE (op0) != SSA_NAME)
> @@ -6775,22 +6867,100 @@ simplify_truth_ops_using_ranges (gimple_
> return false;
> }
>
> - if (rhs_code == TRUTH_NOT_EXPR)
> + if (op1 && TREE_CODE (op1) != INTEGER_CST
> + && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
> + {
> + vr = get_value_range (op1);
> + val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> +
> + val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> + }
> +
> + need_conversion =
> + !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
> + TREE_TYPE (op0));
> +
> + /* As comparisons X != 0 getting folded by prior pass to (bool) X,
> + but X == 0 might be not folded for none boolean type of X
> + to (bool) (X ^ 1).
> + So for bitwise-binary operations we have three cases to handle:
> + a) ((bool) X) op ((bool) Y)
> + b) ((bool) X) op (Y == 0) OR (X == 0) op ((bool) Y)
> + c) (X == 0) op (Y == 0)
> + The later two cases can't be handled for now, as vr tables
> + would need to be adjusted. */
> + if (need_conversion
> + && (rhs_code == BIT_XOR_EXPR
> + || rhs_code == BIT_AND_EXPR
> + || rhs_code == BIT_IOR_EXPR)
> + && TREE_CODE (op1) == SSA_NAME && TREE_CODE (op0) == SSA_NAME)
> + {
> + cop0 = ssa_name_get_cast_to_p (op0);
> + cop1 = ssa_name_get_cast_to_p (op1);
> + if (!cop0 || !cop1)
> + /* We would need an new statment for cases b and c, and we can't
> + due vr table, so bail out. */
> + return false;
> +
> + if (!INTEGRAL_TYPE_P (TREE_TYPE (cop0))
> + || !types_compatible_p (TREE_TYPE (cop0), TREE_TYPE (cop1)))
> + return false;
> + need_conversion =
> + !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
> + TREE_TYPE (cop0));
> + if (need_conversion)
> + return false;
> + op0 = cop0;
> + op1 = cop1;
> +
> + /* We need to re-check if value ranges for new operands
> + for 1-bit precision/range. */
> + if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
> + {
> + if (TREE_CODE (op0) != SSA_NAME)
> + return false;
> + vr = get_value_range (op0);
> +
> + val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> +
> + val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> + }
> +
> + if (op1 && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
> + {
> + vr = get_value_range (op1);
> + val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> +
> + val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> + }
> + }
> + else if (rhs_code == TRUTH_NOT_EXPR || rhs_code == BIT_NOT_EXPR)
> {
> rhs_code = NE_EXPR;
> op1 = build_int_cst (TREE_TYPE (op0), 1);
> }
> else
> {
> - op1 = gimple_assign_rhs2 (stmt);
> -
> /* Reduce number of cases to handle. */
> if (is_gimple_min_invariant (op1))
> {
> /* Exclude anything that should have been already folded. */
> if (rhs_code != EQ_EXPR
> && rhs_code != NE_EXPR
> - && rhs_code != TRUTH_XOR_EXPR)
> + && rhs_code != TRUTH_XOR_EXPR
> + && rhs_code != BIT_XOR_EXPR)
> return false;
>
> if (!integer_zerop (op1)
> @@ -6810,18 +6980,6 @@ simplify_truth_ops_using_ranges (gimple_
> /* Punt on A == B as there is no BIT_XNOR_EXPR. */
> if (rhs_code == EQ_EXPR)
> return false;
> -
> - if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
> - {
> - vr = get_value_range (op1);
> - val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> - if (!val || !integer_onep (val))
> - return false;
> -
> - val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> - if (!val || !integer_onep (val))
> - return false;
> - }
> }
> }
>
> @@ -6838,7 +6996,8 @@ simplify_truth_ops_using_ranges (gimple_
> warning_at (location, OPT_Wstrict_overflow,
> _("assuming signed overflow does not occur when "
> "simplifying && or || to & or |"));
> - else
> + else if (rhs_code != BIT_AND_EXPR && rhs_code != BIT_IOR_EXPR
> + && rhs_code != BIT_XOR_EXPR)
> warning_at (location, OPT_Wstrict_overflow,
> _("assuming signed overflow does not occur when "
> "simplifying ==, != or ! to identity or ^"));
> @@ -6859,16 +7018,21 @@ simplify_truth_ops_using_ranges (gimple_
> case TRUTH_AND_EXPR:
> rhs_code = BIT_AND_EXPR;
> break;
> + case BIT_AND_EXPR:
> + break;
> case TRUTH_OR_EXPR:
> rhs_code = BIT_IOR_EXPR;
> + case BIT_IOR_EXPR:
> break;
> case TRUTH_XOR_EXPR:
> + case BIT_XOR_EXPR:
> case NE_EXPR:
> if (integer_zerop (op1))
> {
> gimple_assign_set_rhs_with_ops (gsi,
> need_conversion ? NOP_EXPR : SSA_NAME,
> op0, NULL);
> + gimple_set_location (stmt, loc);
> update_stmt (gsi_stmt (*gsi));
> return true;
> }
> @@ -6879,10 +7043,20 @@ simplify_truth_ops_using_ranges (gimple_
> gcc_unreachable ();
> }
>
> + /* We can't insert here new expression as otherwise
> + tracked vr tables getting out of bounds. */
> if (need_conversion)
> return false;
>
> + /* Reduce here SSA_NAME -> SSA_NAME. */
> + while ((cop0 = ssa_name_get_inner_ssa_name_p (op0)) != NULL_TREE)
> + op0 = cop0;
> +
> + while ((cop1 = ssa_name_get_inner_ssa_name_p (op1)) != NULL_TREE)
> + op1 = cop1;
> +
> gimple_assign_set_rhs_with_ops (gsi, rhs_code, op0, op1);
> + gimple_set_location (stmt, loc);
> update_stmt (gsi_stmt (*gsi));
> return true;
> }
> @@ -7263,6 +7437,9 @@ simplify_switch_using_ranges (gimple stm
> tree vec2;
> switch_update su;
>
> + if (in_second_pass)
> + return false;
> +
> if (TREE_CODE (op) == SSA_NAME)
> {
> vr = get_value_range (op);
> @@ -7390,6 +7567,7 @@ simplify_stmt_using_ranges (gimple_stmt_
> {
> case EQ_EXPR:
> case NE_EXPR:
> + case BIT_NOT_EXPR:
> case TRUTH_NOT_EXPR:
> case TRUTH_AND_EXPR:
> case TRUTH_OR_EXPR:
> @@ -7425,13 +7603,21 @@ simplify_stmt_using_ranges (gimple_stmt_
> if all the bits being cleared are already cleared or
> all the bits being set are already set. */
> if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
> - return simplify_bit_ops_using_ranges (gsi, stmt);
> + {
> + if (simplify_truth_ops_using_ranges (gsi, stmt))
> + return true;
> + return simplify_bit_ops_using_ranges (gsi, stmt);
> + }
> break;
>
> CASE_CONVERT:
> if (TREE_CODE (rhs1) == SSA_NAME
> && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
> - return simplify_conversion_using_ranges (stmt);
> + {
> + if (simplify_truth_ops_using_ranges (gsi, stmt))
> + return true;
> + return simplify_conversion_using_ranges (stmt);
> + }
> break;
>
> default:
> @@ -7685,8 +7870,16 @@ vrp_finalize (void)
> fprintf (dump_file, "\n");
> }
>
> + /* We redo folding here one time for allowing to inspect more
> + complex reductions. */
> + substitute_and_fold (op_with_constant_singleton_value_range,
> + vrp_fold_stmt, false);
> + /* We need to mark this second pass to avoid re-entering of same
> + edges for switch statments. */
> + in_second_pass = true;
> substitute_and_fold (op_with_constant_singleton_value_range,
> vrp_fold_stmt, false);
> + in_second_pass = false;
If at all you only want to re-call vrp_fold_stmt on all stmts in the
function, not do a full-blown substitute_and_fold.
Richard.
> if (warn_array_bounds)
> check_all_array_refs ();
>
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-07 16:28 ` Kai Tietz
@ 2011-07-08 9:45 ` Richard Guenther
2011-07-08 10:59 ` Kai Tietz
` (2 more replies)
0 siblings, 3 replies; 18+ messages in thread
From: Richard Guenther @ 2011-07-08 9:45 UTC (permalink / raw)
To: Kai Tietz; +Cc: Paolo Bonzini, GCC Patches
On Thu, Jul 7, 2011 at 6:28 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2011/7/7 Paolo Bonzini <bonzini@gnu.org>:
>> On 07/07/2011 06:07 PM, Kai Tietz wrote:
>>>
>>> + /* We redo folding here one time for allowing to inspect more
>>> + complex reductions. */
>>> + substitute_and_fold (op_with_constant_singleton_value_range,
>>> + vrp_fold_stmt, false);
>>> + /* We need to mark this second pass to avoid re-entering of same
>>> + edges for switch statments. */
>>> + in_second_pass = true;
>>> substitute_and_fold (op_with_constant_singleton_value_range,
>>> vrp_fold_stmt, false);
>>> + in_second_pass = false;
>>
>> This needs a much better explanation.
>>
>> Paolo
>
> Well, I can work on a better comment. The complex reduction I mean
> here are cases like
>
> int x;
> int y;
> _Bool D1;
> _Bool D2;
> _Bool D3;
> int R;
>
> D1 = x[0..1] != 0;
> D2 = y[0..1] != 0;
> D3 = D1 & D2
> R = (int) D3
>
> (testcase is already present. See tree-ssa/vrp47.c).
>
> As VRP in first pass produces (and replaces) to:
>
> D1 = (_Bool) x[0..1];
> D2 = (_Bool) y[0..1];
> D3 = D1 & D2
> R = (int) D3
>
> Just in the second pass the reduction
>
> R = x[0..1] & y[0..1]
So why wouldn't that happen during the first pass? The first
pass could change the IL to
D1 = x[0..1] != 0;
D2 = y[0..1] != 0;
D3 = D1 & D2;
R = x & y;
if D3 only has a single use.
> can happen. In general it is sad that VRP can't insert during pass
> new statements right now. This would cause issues in range-tables,
> which aren't designed for insertations. As otherwise, we could do
> also simplify things like
>
> D1 = x[0..1] != 0;
> D2 = y[0..1] == 0;
> D3 = D1 & D2
> R = (int) D3
>
> to
> R = x[0..1] & (y[0..1] ^ 1)
Why that ^ 1? And why does that confuse the range tables
if you re-use R?
> Regards,
> Kai
>
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-08 9:45 ` Richard Guenther
@ 2011-07-08 10:59 ` Kai Tietz
2011-07-08 11:08 ` Kai Tietz
2011-07-08 14:40 ` Kai Tietz
2 siblings, 0 replies; 18+ messages in thread
From: Kai Tietz @ 2011-07-08 10:59 UTC (permalink / raw)
To: Richard Guenther; +Cc: Paolo Bonzini, GCC Patches
2011/7/8 Richard Guenther <richard.guenther@gmail.com>:
> On Thu, Jul 7, 2011 at 6:28 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> 2011/7/7 Paolo Bonzini <bonzini@gnu.org>:
>>> On 07/07/2011 06:07 PM, Kai Tietz wrote:
>>>>
>>>> + /* We redo folding here one time for allowing to inspect more
>>>> + complex reductions. */
>>>> + substitute_and_fold (op_with_constant_singleton_value_range,
>>>> + vrp_fold_stmt, false);
>>>> + /* We need to mark this second pass to avoid re-entering of same
>>>> + edges for switch statments. */
>>>> + in_second_pass = true;
>>>> substitute_and_fold (op_with_constant_singleton_value_range,
>>>> vrp_fold_stmt, false);
>>>> + in_second_pass = false;
>>>
>>> This needs a much better explanation.
>>>
>>> Paolo
>>
>> Well, I can work on a better comment. The complex reduction I mean
>> here are cases like
>>
>> int x;
>> int y;
>> _Bool D1;
>> _Bool D2;
>> _Bool D3;
>> int R;
>>
>> D1 = x[0..1] != 0;
>> D2 = y[0..1] != 0;
>> D3 = D1 & D2
>> R = (int) D3
>>
>> (testcase is already present. See tree-ssa/vrp47.c).
>>
>> As VRP in first pass produces (and replaces) to:
>>
>> D1 = (_Bool) x[0..1];
>> D2 = (_Bool) y[0..1];
>> D3 = D1 & D2
>> R = (int) D3
>>
>> Just in the second pass the reduction
>>
>> R = x[0..1] & y[0..1]
>
> So why wouldn't that happen during the first pass? The first
> pass could change the IL to
>
> D1 = x[0..1] != 0;
> D2 = y[0..1] != 0;
> D3 = D1 & D2;
> R = x & y;
>
> if D3 only has a single use.
>
>> can happen. In general it is sad that VRP can't insert during pass
>> new statements right now. This would cause issues in range-tables,
>> which aren't designed for insertations. As otherwise, we could do
>> also simplify things like
>>
>> D1 = x[0..1] != 0;
>> D2 = y[0..1] == 0;
>> D3 = D1 & D2
>> R = (int) D3
>>
>> to
>> R = x[0..1] & (y[0..1] ^ 1)
>
> Why that ^ 1? And why does that confuse the range tables
> if you re-use R?
Because (y[0..1] ^1) has a type change. All present SSA-nodes have
boolean type, but (y[0..1] ^ 1) is an integer one. We have just the
cast def, which has final type. See code of vrp_stmt truth and you
will notice that for X with range 0..1 it converts X == 0 -> X ^ 1.
But here we have possible type change as a comparison is boolean and X
might not.
Kai
>> Regards,
>> Kai
>>
>
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-08 9:45 ` Richard Guenther
2011-07-08 10:59 ` Kai Tietz
@ 2011-07-08 11:08 ` Kai Tietz
2011-07-08 14:40 ` Kai Tietz
2 siblings, 0 replies; 18+ messages in thread
From: Kai Tietz @ 2011-07-08 11:08 UTC (permalink / raw)
To: Richard Guenther; +Cc: Paolo Bonzini, GCC Patches
2011/7/8 Richard Guenther <richard.guenther@gmail.com>:
> On Thu, Jul 7, 2011 at 6:28 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> 2011/7/7 Paolo Bonzini <bonzini@gnu.org>:
>>> On 07/07/2011 06:07 PM, Kai Tietz wrote:
>>>>
>>>> + /* We redo folding here one time for allowing to inspect more
>>>> + complex reductions. */
>>>> + substitute_and_fold (op_with_constant_singleton_value_range,
>>>> + vrp_fold_stmt, false);
>>>> + /* We need to mark this second pass to avoid re-entering of same
>>>> + edges for switch statments. */
>>>> + in_second_pass = true;
>>>> substitute_and_fold (op_with_constant_singleton_value_range,
>>>> vrp_fold_stmt, false);
>>>> + in_second_pass = false;
>>>
>>> This needs a much better explanation.
>>>
>>> Paolo
>>
>> Well, I can work on a better comment. The complex reduction I mean
>> here are cases like
>>
>> int x;
>> int y;
>> _Bool D1;
>> _Bool D2;
>> _Bool D3;
>> int R;
>>
>> D1 = x[0..1] != 0;
>> D2 = y[0..1] != 0;
>> D3 = D1 & D2
>> R = (int) D3
>>
>> (testcase is already present. See tree-ssa/vrp47.c).
>>
>> As VRP in first pass produces (and replaces) to:
>>
>> D1 = (_Bool) x[0..1];
>> D2 = (_Bool) y[0..1];
>> D3 = D1 & D2
>> R = (int) D3
>>
>> Just in the second pass the reduction
>>
>> R = x[0..1] & y[0..1]
>
> So why wouldn't that happen during the first pass? The first
> pass could change the IL to
The issue is that substitute_and_fold runs within BBs statements
folding from last to first. So most simplifications are done too late
to recognize dependent one. Maybe it would be another way here to have
a flag for substitute_and_fold to indicate that folding pass shall run
first -> last or last->first?
> D1 = x[0..1] != 0;
> D2 = y[0..1] != 0;
> D3 = D1 & D2;
> R = x & y;
>
> if D3 only has a single use.
Well, to change type of an SSA-name, if it has single-use might be
another way here. To have the ability to enter new temp-registers
would be better and avoids the dependency of single use, but well,
range tables don't support that now.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-08 9:45 ` Richard Guenther
2011-07-08 10:59 ` Kai Tietz
2011-07-08 11:08 ` Kai Tietz
@ 2011-07-08 14:40 ` Kai Tietz
2011-07-08 14:57 ` Richard Guenther
2 siblings, 1 reply; 18+ messages in thread
From: Kai Tietz @ 2011-07-08 14:40 UTC (permalink / raw)
To: Richard Guenther; +Cc: Paolo Bonzini, GCC Patches
2011/7/8 Richard Guenther <richard.guenther@gmail.com>:
> On Thu, Jul 7, 2011 at 6:28 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> 2011/7/7 Paolo Bonzini <bonzini@gnu.org>:
>>> On 07/07/2011 06:07 PM, Kai Tietz wrote:
>>>>
>>>> + /* We redo folding here one time for allowing to inspect more
>>>> + complex reductions. */
>>>> + substitute_and_fold (op_with_constant_singleton_value_range,
>>>> + vrp_fold_stmt, false);
>>>> + /* We need to mark this second pass to avoid re-entering of same
>>>> + edges for switch statments. */
>>>> + in_second_pass = true;
>>>> substitute_and_fold (op_with_constant_singleton_value_range,
>>>> vrp_fold_stmt, false);
>>>> + in_second_pass = false;
>>>
>>> This needs a much better explanation.
>>>
>>> Paolo
>>
>> Well, I can work on a better comment. The complex reduction I mean
>> here are cases like
>>
>> int x;
>> int y;
>> _Bool D1;
>> _Bool D2;
>> _Bool D3;
>> int R;
>>
>> D1 = x[0..1] != 0;
>> D2 = y[0..1] != 0;
>> D3 = D1 & D2
>> R = (int) D3
>>
>> (testcase is already present. See tree-ssa/vrp47.c).
>>
>> As VRP in first pass produces (and replaces) to:
>>
>> D1 = (_Bool) x[0..1];
>> D2 = (_Bool) y[0..1];
>> D3 = D1 & D2
>> R = (int) D3
>>
>> Just in the second pass the reduction
>>
>> R = x[0..1] & y[0..1]
>
> So why wouldn't that happen during the first pass? The first
> pass could change the IL to
>
> D1 = x[0..1] != 0;
> D2 = y[0..1] != 0;
> D3 = D1 & D2;
> R = x & y;
>
> if D3 only has a single use.
No, as D3 would need a type change, and this isn't possible. If it
wasn't absolutely clear, this patch to VRP is necessary after patch 2,
as here D1, D2, and D3 have bool-type, and just R is of type int.
>> can happen. In general it is sad that VRP can't insert during pass
>> new statements right now. This would cause issues in range-tables,
>> which aren't designed for insertations. As otherwise, we could do
>> also simplify things like
>>
>> D1 = x[0..1] != 0;
>> D2 = y[0..1] == 0;
>> D3 = D1 & D2
>> R = (int) D3
>>
>> to
>> R = x[0..1] & (y[0..1] ^ 1)
>
> Why that ^ 1? And why does that confuse the range tables
> if you re-use R?
Because we would need to insert a new statement and this isn't allowed
in VRP. See the comments in VRP and substitute_and_fold. VRP
disallows to remove statements or to insert new ones.
>> Regards,
>> Kai
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-08 14:40 ` Kai Tietz
@ 2011-07-08 14:57 ` Richard Guenther
2011-07-08 15:05 ` Kai Tietz
0 siblings, 1 reply; 18+ messages in thread
From: Richard Guenther @ 2011-07-08 14:57 UTC (permalink / raw)
To: Kai Tietz; +Cc: Paolo Bonzini, GCC Patches
On Fri, Jul 8, 2011 at 4:35 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2011/7/8 Richard Guenther <richard.guenther@gmail.com>:
>> On Thu, Jul 7, 2011 at 6:28 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>> 2011/7/7 Paolo Bonzini <bonzini@gnu.org>:
>>>> On 07/07/2011 06:07 PM, Kai Tietz wrote:
>>>>>
>>>>> + /* We redo folding here one time for allowing to inspect more
>>>>> + complex reductions. */
>>>>> + substitute_and_fold (op_with_constant_singleton_value_range,
>>>>> + vrp_fold_stmt, false);
>>>>> + /* We need to mark this second pass to avoid re-entering of same
>>>>> + edges for switch statments. */
>>>>> + in_second_pass = true;
>>>>> substitute_and_fold (op_with_constant_singleton_value_range,
>>>>> vrp_fold_stmt, false);
>>>>> + in_second_pass = false;
>>>>
>>>> This needs a much better explanation.
>>>>
>>>> Paolo
>>>
>>> Well, I can work on a better comment. The complex reduction I mean
>>> here are cases like
>>>
>>> int x;
>>> int y;
>>> _Bool D1;
>>> _Bool D2;
>>> _Bool D3;
>>> int R;
>>>
>>> D1 = x[0..1] != 0;
>>> D2 = y[0..1] != 0;
>>> D3 = D1 & D2
>>> R = (int) D3
>>>
>>> (testcase is already present. See tree-ssa/vrp47.c).
>>>
>>> As VRP in first pass produces (and replaces) to:
>>>
>>> D1 = (_Bool) x[0..1];
>>> D2 = (_Bool) y[0..1];
>>> D3 = D1 & D2
>>> R = (int) D3
>>>
>>> Just in the second pass the reduction
>>>
>>> R = x[0..1] & y[0..1]
>>
>> So why wouldn't that happen during the first pass? The first
>> pass could change the IL to
>>
>> D1 = x[0..1] != 0;
>> D2 = y[0..1] != 0;
>> D3 = D1 & D2;
>> R = x & y;
>>
>> if D3 only has a single use.
> No, as D3 would need a type change, and this isn't possible. If it
> wasn't absolutely clear, this patch to VRP is necessary after patch 2,
> as here D1, D2, and D3 have bool-type, and just R is of type int.
In your example x,y and R are int, so it works with re-using R.
>>> can happen. In general it is sad that VRP can't insert during pass
>>> new statements right now. This would cause issues in range-tables,
>>> which aren't designed for insertations. As otherwise, we could do
>>> also simplify things like
>>>
>>> D1 = x[0..1] != 0;
>>> D2 = y[0..1] == 0;
>>> D3 = D1 & D2
>>> R = (int) D3
>>>
>>> to
>>> R = x[0..1] & (y[0..1] ^ 1)
>>
>> Why that ^ 1? And why does that confuse the range tables
>> if you re-use R?
> Because we would need to insert a new statement and this isn't allowed
> in VRP. See the comments in VRP and substitute_and_fold. VRP
> disallows to remove statements or to insert new ones.
That's not a hard limitation.
>>> Regards,
>>> Kai
>
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-08 14:57 ` Richard Guenther
@ 2011-07-08 15:05 ` Kai Tietz
0 siblings, 0 replies; 18+ messages in thread
From: Kai Tietz @ 2011-07-08 15:05 UTC (permalink / raw)
To: Richard Guenther; +Cc: Paolo Bonzini, GCC Patches
2011/7/8 Richard Guenther <richard.guenther@gmail.com>:
> On Fri, Jul 8, 2011 at 4:35 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> 2011/7/8 Richard Guenther <richard.guenther@gmail.com>:
>>> On Thu, Jul 7, 2011 at 6:28 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>>>> 2011/7/7 Paolo Bonzini <bonzini@gnu.org>:
>>>>> On 07/07/2011 06:07 PM, Kai Tietz wrote:
>>>>>>
>>>>>> + /* We redo folding here one time for allowing to inspect more
>>>>>> + complex reductions. */
>>>>>> + substitute_and_fold (op_with_constant_singleton_value_range,
>>>>>> + vrp_fold_stmt, false);
>>>>>> + /* We need to mark this second pass to avoid re-entering of same
>>>>>> + edges for switch statments. */
>>>>>> + in_second_pass = true;
>>>>>> substitute_and_fold (op_with_constant_singleton_value_range,
>>>>>> vrp_fold_stmt, false);
>>>>>> + in_second_pass = false;
>>>>>
>>>>> This needs a much better explanation.
>>>>>
>>>>> Paolo
>>>>
>>>> Well, I can work on a better comment. The complex reduction I mean
>>>> here are cases like
>>>>
>>>> int x;
>>>> int y;
>>>> _Bool D1;
>>>> _Bool D2;
>>>> _Bool D3;
>>>> int R;
>>>>
>>>> D1 = x[0..1] != 0;
>>>> D2 = y[0..1] != 0;
>>>> D3 = D1 & D2
>>>> R = (int) D3
>>>>
>>>> (testcase is already present. See tree-ssa/vrp47.c).
>>>>
>>>> As VRP in first pass produces (and replaces) to:
>>>>
>>>> D1 = (_Bool) x[0..1];
>>>> D2 = (_Bool) y[0..1];
>>>> D3 = D1 & D2
>>>> R = (int) D3
>>>>
>>>> Just in the second pass the reduction
>>>>
>>>> R = x[0..1] & y[0..1]
>>>
>>> So why wouldn't that happen during the first pass? The first
>>> pass could change the IL to
>>>
>>> D1 = x[0..1] != 0;
>>> D2 = y[0..1] != 0;
>>> D3 = D1 & D2;
>>> R = x & y;
>>>
>>> if D3 only has a single use.
>> No, as D3 would need a type change, and this isn't possible. If it
>> wasn't absolutely clear, this patch to VRP is necessary after patch 2,
>> as here D1, D2, and D3 have bool-type, and just R is of type int.
>
> In your example x,y and R are int, so it works with re-using R.
Well, if we add pattern match with prefixed cast, it works. This
actual my patch does, as it finds out that D1's and D2's operand is of
kind int, and matches R's type. So it uses R to simplify. This
pattern is better then nothing, but more complex operations can't be
handled without introducing new statements.
Eg:
int foo (int a, int b, int c)
{
if (a < 0 || a > 1 || b < 0 || b > 1 || c < 0 || c > 1)
return -1;
return (a != 0 | b != 0) | c != 0;
}
Here we get:
int a; int b; int c;
_Bool D1, D2, D3, D4;
int R;
...
D1 = (bool) a;
D2 = (bool) b;
D3 = (bool) c;
D4 = D1 | D2;
D5 = D4 | D3
R = (int) D5;
This can't be simplified by VRP without inserting new statement.
>>>> can happen. In general it is sad that VRP can't insert during pass
>>>> new statements right now. This would cause issues in range-tables,
>>>> which aren't designed for insertations. As otherwise, we could do
>>>> also simplify things like
>>>>
>>>> D1 = x[0..1] != 0;
>>>> D2 = y[0..1] == 0;
>>>> D3 = D1 & D2
>>>> R = (int) D3
>>>>
>>>> to
>>>> R = x[0..1] & (y[0..1] ^ 1)
>>>
>>> Why that ^ 1? And why does that confuse the range tables
>>> if you re-use R?
>> Because we would need to insert a new statement and this isn't allowed
>> in VRP. See the comments in VRP and substitute_and_fold. VRP
>> disallows to remove statements or to insert new ones.
>
> That's not a hard limitation.
Hmm, ok. I played by it for a while to add this, but some later passes
like switch-range analyzis and jump-threading (IIRC) getting confused
by this. AFAIU are the major culprits here the inserted ASSERTs, but
maybe I am wrong about this.
Kai
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-08 9:39 ` Richard Guenther
@ 2011-07-08 15:49 ` Kai Tietz
2011-07-08 16:31 ` Kai Tietz
0 siblings, 1 reply; 18+ messages in thread
From: Kai Tietz @ 2011-07-08 15:49 UTC (permalink / raw)
To: Richard Guenther; +Cc: GCC Patches
2011/7/8 Richard Guenther <richard.guenther@gmail.com>:
> On Thu, Jul 7, 2011 at 6:07 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> Index: gcc-head/gcc/tree-vrp.c
>> @@ -2232,6 +2235,7 @@ extract_range_from_binary_expr (value_ra
>> some cases. */
>> if (code != BIT_AND_EXPR
>> && code != TRUTH_AND_EXPR
>> + && code != BIT_IOR_EXPR
>
> Huh? So how would VARYING | x ever produce something better
> than VARYING?
Because BIT_IOR_EXPR might be a 1-bit precision operation and so
equivalent to TRUTH_OR_EXPR. It might be that BIT_XOR_EXPR is worth to
be added here too, as for one-bit precision typed expression it is
equivalent to TRUTH_XOR_EXPR.
Kai
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-08 15:49 ` Kai Tietz
@ 2011-07-08 16:31 ` Kai Tietz
2011-07-08 16:45 ` Michael Matz
0 siblings, 1 reply; 18+ messages in thread
From: Kai Tietz @ 2011-07-08 16:31 UTC (permalink / raw)
To: Richard Guenther; +Cc: GCC Patches
Hello,
This is the reworked patch, It fixes vrp to handle bitwise one-bit
precision typed operations
and to handle some type hoisting cases, Some cases can't be handled as
long as vrp doesn't
allows to insert new statements in folding pass.
To have in first pass better match, VRP uses for stmt-folding now for each BB
first -> last stepping. I extended for this function
substitute_and_fold function by an
new argument, which indicates if scanning within BB shall be done from
first to last,
or from last to first. I removed in this new patch the part of
re-doing stmt-fold pass, as
this is no longer necessary by changing folding direction within BB.
This modification of scanning direction plus type-cast handling allows
it to remove dom-dump
from the testcase tree-ssa/vrp47.c, as all cases are handled now
within vrp itself.
Bootstrapped and regression tested for all standard-languages (plus
Ada and Obj-C++) on host x86_64-pc-linux-gnu.
Ok for apply?
Regards,
Kai
ChangeLog gcc/
2011-07-08 Kai Tietz <ktietz@redhat.com>
* tree-ssa-ccp.c (ccp_finalize): Add new
argument for substitute_and_fold.
* tree-ssa-copy.c (fini_copy_prop): Likewise.
* tree-ssa-propagate.h (substitute_and_fold):
Likewise.
* tree-ssa-propagate.c (substitute_and_fold):
Likewise.
* tree-vrp.c (vrp_finalize): Likewise.
(extract_range_from_binary_expr): Add handling
for BIT_IOR_EXPR, BIT_AND_EXPR, and BIT_NOT_EXPR.
(register_edge_assert_for_1): Add handling for 1-bit
BIT_IOR_EXPR and BIT_NOT_EXPR.
(register_edge_assert_for): Add handling for 1-bit
BIT_IOR_EXPR.
(ssa_name_get_inner_ssa_name_p): New helper function.
(ssa_name_get_cast_to_p): New helper function.
(simplify_truth_ops_using_ranges): Handle prefixed
cast instruction for result, and add support for one
bit precision BIT_IOR_EXPR, BIT_AND_EXPR, BIT_XOR_EXPR,
and BIT_NOT_EXPR.
(simplify_stmt_using_ranges): Add handling for one bit
precision BIT_IOR_EXPR, BIT_AND_EXPR, BIT_XOR_EXPR,
and BIT_NOT_EXPR.
ChangeLog gcc/testsuite
2011-07-08 Kai Tietz <ktietz@redhat.com>
* gcc.dg/tree-ssa/vrp47.c: Remove dom-output
and adjust testcase for vrp output analysis.
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c
===================================================================
--- gcc.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c 2011-01-11
20:36:16.000000000 +0100
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c 2011-07-08
17:49:55.016847200 +0200
@@ -4,7 +4,7 @@
jumps when evaluating an && condition. VRP is not able to optimize
this. */
/* { dg-do compile { target { ! "mips*-*-* s390*-*-* avr-*-*
mn10300-*-*" } } } */
-/* { dg-options "-O2 -fdump-tree-vrp -fdump-tree-dom" } */
+/* { dg-options "-O2 -fdump-tree-vrp" } */
/* { dg-options "-O2 -fdump-tree-vrp -fdump-tree-dom -march=i586" {
target { i?86-*-* && ilp32 } } } */
int h(int x, int y)
@@ -36,13 +36,10 @@ int f(int x)
0 or 1. */
/* { dg-final { scan-tree-dump-times "\[xy\]\[^ \]* !=" 0 "vrp1" } } */
-/* This one needs more copy propagation that only happens in dom1. */
-/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "dom1" } } */
-/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" { xfail
*-*-* } } } */
+/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" } } */
/* These two are fully simplified by VRP. */
/* { dg-final { scan-tree-dump-times "x\[^ \]* \[|\] y" 1 "vrp1" } } */
/* { dg-final { scan-tree-dump-times "x\[^ \]* \\^ 1" 1 "vrp1" } } */
/* { dg-final { cleanup-tree-dump "vrp\[0-9\]" } } */
-/* { dg-final { cleanup-tree-dump "dom\[0-9\]" } } */
Index: gcc/gcc/tree-ssa-ccp.c
===================================================================
--- gcc.orig/gcc/tree-ssa-ccp.c 2011-06-30 11:30:12.000000000 +0200
+++ gcc/gcc/tree-ssa-ccp.c 2011-07-08 17:20:22.378750800 +0200
@@ -880,7 +880,8 @@ ccp_finalize (void)
/* Perform substitutions based on the known constant values. */
something_changed = substitute_and_fold (get_constant_value,
- ccp_fold_stmt, true);
+ ccp_fold_stmt, true,
+ true);
free (const_val);
const_val = NULL;
Index: gcc/gcc/tree-ssa-copy.c
===================================================================
--- gcc.orig/gcc/tree-ssa-copy.c 2011-06-17 11:52:51.000000000 +0200
+++ gcc/gcc/tree-ssa-copy.c 2011-07-08 17:19:32.464412500 +0200
@@ -778,7 +778,7 @@ fini_copy_prop (void)
/* Don't do DCE if we have loops. That's the simplest way to not
destroy the scev cache. */
- substitute_and_fold (get_value, NULL, !current_loops);
+ substitute_and_fold (get_value, NULL, !current_loops, true);
free (copy_of);
}
Index: gcc/gcc/tree-ssa-propagate.c
===================================================================
--- gcc.orig/gcc/tree-ssa-propagate.c 2011-05-12 21:01:07.000000000 +0200
+++ gcc/gcc/tree-ssa-propagate.c 2011-07-08 17:18:26.921089500 +0200
@@ -979,12 +979,15 @@ replace_phi_args_in (gimple phi, ssa_pro
DO_DCE is true if trivially dead stmts can be removed.
+ SCAN_BB_REVERSE is true, if the statements within a BB shall be from
+ last to first element. Otherwise we scan from first to last element.
+
Return TRUE when something changed. */
bool
substitute_and_fold (ssa_prop_get_value_fn get_value_fn,
ssa_prop_fold_stmt_fn fold_fn,
- bool do_dce)
+ bool do_dce, bool scan_bb_reverse)
{
basic_block bb;
bool something_changed = false;
@@ -1059,9 +1062,10 @@ substitute_and_fold (ssa_prop_get_value_
for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
replace_phi_args_in (gsi_stmt (i), get_value_fn);
- /* Propagate known values into stmts. Do a backward walk to expose
- more trivially deletable stmts. */
- for (i = gsi_last_bb (bb); !gsi_end_p (i);)
+ /* Propagate known values into stmts. Do a backward walk if
+ scan_bb_reverse is true. In some case it exposes
+ more trivially deletable stmts to walk backward. */
+ for (i = (scan_bb_reverse ? gsi_last_bb (bb) : gsi_start_bb
(bb)); !gsi_end_p (i);)
{
bool did_replace;
gimple stmt = gsi_stmt (i);
@@ -1070,7 +1074,10 @@ substitute_and_fold (ssa_prop_get_value_
gimple_stmt_iterator oldi;
oldi = i;
- gsi_prev (&i);
+ if (scan_bb_reverse)
+ gsi_prev (&i);
+ else
+ gsi_next (&i);
/* Ignore ASSERT_EXPRs. They are used by VRP to generate
range information for names and they are discarded
Index: gcc/gcc/tree-ssa-propagate.h
===================================================================
--- gcc.orig/gcc/tree-ssa-propagate.h 2010-09-09 16:09:48.000000000 +0200
+++ gcc/gcc/tree-ssa-propagate.h 2011-07-08 17:12:42.847397700 +0200
@@ -74,6 +74,7 @@ bool valid_gimple_rhs_p (tree);
void move_ssa_defining_stmt_for_defs (gimple, gimple);
bool update_call_from_tree (gimple_stmt_iterator *, tree);
bool stmt_makes_single_store (gimple);
-bool substitute_and_fold (ssa_prop_get_value_fn, ssa_prop_fold_stmt_fn, bool);
+bool substitute_and_fold (ssa_prop_get_value_fn, ssa_prop_fold_stmt_fn, bool,
+ bool);
#endif /* _TREE_SSA_PROPAGATE_H */
Index: gcc/gcc/tree-vrp.c
===================================================================
--- gcc.orig/gcc/tree-vrp.c 2011-07-08 14:07:42.000000000 +0200
+++ gcc/gcc/tree-vrp.c 2011-07-08 17:44:20.981930200 +0200
@@ -2232,6 +2232,7 @@ extract_range_from_binary_expr (value_ra
some cases. */
if (code != BIT_AND_EXPR
&& code != TRUTH_AND_EXPR
+ && code != BIT_IOR_EXPR
&& code != TRUTH_OR_EXPR
&& code != TRUNC_DIV_EXPR
&& code != FLOOR_DIV_EXPR
@@ -2291,6 +2292,8 @@ extract_range_from_binary_expr (value_ra
else
set_value_range_to_varying (vr);
}
+ else if (code == BIT_IOR_EXPR)
+ set_value_range_to_varying (vr);
else
gcc_unreachable ();
@@ -2300,11 +2303,13 @@ extract_range_from_binary_expr (value_ra
/* For integer ranges, apply the operation to each end of the
range and see what we end up with. */
if (code == TRUTH_AND_EXPR
- || code == TRUTH_OR_EXPR)
+ || code == TRUTH_OR_EXPR
+ || ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+ && TYPE_PRECISION (TREE_TYPE (op1)) == 1))
{
/* If one of the operands is zero, we know that the whole
expression evaluates zero. */
- if (code == TRUTH_AND_EXPR
+ if ((code == TRUTH_AND_EXPR || code == BIT_AND_EXPR)
&& ((vr0.type == VR_RANGE
&& integer_zerop (vr0.min)
&& integer_zerop (vr0.max))
@@ -2317,7 +2322,7 @@ extract_range_from_binary_expr (value_ra
}
/* If one of the operands is one, we know that the whole
expression evaluates one. */
- else if (code == TRUTH_OR_EXPR
+ else if ((code == TRUTH_OR_EXPR || code == BIT_IOR_EXPR)
&& ((vr0.type == VR_RANGE
&& integer_onep (vr0.min)
&& integer_onep (vr0.max))
@@ -2809,7 +2814,7 @@ extract_range_from_unary_expr (value_ran
cannot easily determine a resulting range. */
if (code == FIX_TRUNC_EXPR
|| code == FLOAT_EXPR
- || code == BIT_NOT_EXPR
+ || (code == BIT_NOT_EXPR && TYPE_PRECISION (type) != 1)
|| code == CONJ_EXPR)
{
/* We can still do constant propagation here. */
@@ -3976,7 +3981,9 @@ build_assert_expr_for (tree cond, tree v
tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
assertion = gimple_build_assign (n, a);
}
- else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
+ else if (TREE_CODE (cond) == TRUTH_NOT_EXPR
+ || (TREE_CODE (cond) == BIT_NOT_EXPR
+ && TYPE_PRECISION (TREE_TYPE (cond)) == 1))
{
/* Given !V, build the assignment N = false. */
tree op0 = TREE_OPERAND (cond, 0);
@@ -4531,7 +4538,9 @@ register_edge_assert_for_1 (tree op, enu
retval |= register_edge_assert_for_1 (gimple_assign_rhs2 (op_def),
code, e, bsi);
}
- else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR)
+ else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR
+ || (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
+ && TYPE_PRECISION (TREE_TYPE (op)) == 1))
{
/* Recurse, flipping CODE. */
code = invert_tree_comparison (code, false);
@@ -4617,6 +4626,9 @@ register_edge_assert_for (tree name, edg
if (is_gimple_assign (def_stmt)
&& (gimple_assign_rhs_code (def_stmt) == TRUTH_OR_EXPR
+ || (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR
+ && INTEGRAL_TYPE_P (TREE_TYPE (name))
+ && TYPE_PRECISION (TREE_TYPE (name)) == 1)
/* For BIT_IOR_EXPR only if NAME == 0 both operands have
necessarily zero value. */
|| (comp_code == EQ_EXPR
@@ -6747,19 +6759,96 @@ varying:
return SSA_PROP_VARYING;
}
+/* Returns operand1 of ssa-name with SSA_NAME as code, Otherwise it
+ returns NULL_TREE. */
+static tree
+ssa_name_get_inner_ssa_name_p (tree op)
+{
+ gimple stmt;
+
+ if (TREE_CODE (op) != SSA_NAME
+ || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
+ return NULL_TREE;
+ stmt = SSA_NAME_DEF_STMT (op);
+ if (gimple_assign_rhs_code (stmt) != SSA_NAME)
+ return NULL_TREE;
+ return gimple_assign_rhs1 (stmt);
+}
+
+/* Returns operand of cast operation, if OP is a type-conversion. Otherwise
+ return NULL_TREE. */
+static tree
+ssa_name_get_cast_to_p (tree op)
+{
+ gimple stmt;
+
+ if (TREE_CODE (op) != SSA_NAME
+ || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
+ return NULL_TREE;
+ stmt = SSA_NAME_DEF_STMT (op);
+ if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
+ return NULL_TREE;
+ return gimple_assign_rhs1 (stmt);
+}
+
/* Simplify boolean operations if the source is known
to be already a boolean. */
static bool
simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
{
enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+ gimple stmt2 = stmt;
tree val = NULL;
- tree op0, op1;
+ tree op0, op1, cop0, cop1;
value_range_t *vr;
bool sop = false;
bool need_conversion;
+ location_t loc = gimple_location (stmt);
op0 = gimple_assign_rhs1 (stmt);
+ op1 = NULL_TREE;
+
+ /* Handle cases with prefixed type-cast. */
+ if (CONVERT_EXPR_CODE_P (rhs_code)
+ && INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ && TREE_CODE (op0) == SSA_NAME
+ && is_gimple_assign (SSA_NAME_DEF_STMT (op0))
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
+ {
+ stmt2 = SSA_NAME_DEF_STMT (op0);
+ op0 = gimple_assign_rhs1 (stmt2);
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)))
+ return false;
+ rhs_code = gimple_assign_rhs_code (stmt2);
+ if (rhs_code != BIT_NOT_EXPR && rhs_code != TRUTH_NOT_EXPR
+ && rhs_code != TRUTH_AND_EXPR && rhs_code != BIT_AND_EXPR
+ && rhs_code != TRUTH_OR_EXPR && rhs_code != BIT_IOR_EXPR
+ && rhs_code != TRUTH_XOR_EXPR && rhs_code != BIT_XOR_EXPR
+ && rhs_code != NE_EXPR && rhs_code != EQ_EXPR)
+ return false;
+ if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
+ || rhs_code == BIT_XOR_EXPR || rhs_code == TRUTH_AND_EXPR
+ || rhs_code == TRUTH_OR_EXPR || rhs_code == TRUTH_XOR_EXPR
+ || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
+ op1 = gimple_assign_rhs2 (stmt2);
+ if (gimple_has_location (stmt2))
+ loc = gimple_location (stmt2);
+ }
+ else if (CONVERT_EXPR_CODE_P (rhs_code))
+ return false;
+ else if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
+ || rhs_code == BIT_XOR_EXPR || rhs_code == TRUTH_AND_EXPR
+ || rhs_code == TRUTH_OR_EXPR || rhs_code == TRUTH_XOR_EXPR
+ || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
+ op1 = gimple_assign_rhs2 (stmt);
+
+ /* ~X is only equivalent of !X, if type-precision is one and X has
+ an integral type. */
+ if (rhs_code == BIT_NOT_EXPR
+ && (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ || TYPE_PRECISION (TREE_TYPE (op0)) != 1))
+ return false;
+
if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
{
if (TREE_CODE (op0) != SSA_NAME)
@@ -6775,22 +6864,100 @@ simplify_truth_ops_using_ranges (gimple_
return false;
}
- if (rhs_code == TRUTH_NOT_EXPR)
+ if (op1 && TREE_CODE (op1) != INTEGER_CST
+ && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
+ {
+ vr = get_value_range (op1);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+
+ need_conversion =
+ !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
+ TREE_TYPE (op0));
+
+ /* As comparisons X != 0 getting folded by prior pass to (bool) X,
+ but X == 0 might be not folded for none boolean type of X
+ to (bool) (X ^ 1).
+ So for bitwise-binary operations we have three cases to handle:
+ a) ((bool) X) op ((bool) Y)
+ b) ((bool) X) op (Y == 0) OR (X == 0) op ((bool) Y)
+ c) (X == 0) op (Y == 0)
+ The later two cases can't be handled for now, as vr tables
+ would need to be adjusted. */
+ if (need_conversion
+ && (rhs_code == BIT_XOR_EXPR
+ || rhs_code == BIT_AND_EXPR
+ || rhs_code == BIT_IOR_EXPR)
+ && TREE_CODE (op1) == SSA_NAME && TREE_CODE (op0) == SSA_NAME)
+ {
+ cop0 = ssa_name_get_cast_to_p (op0);
+ cop1 = ssa_name_get_cast_to_p (op1);
+ if (!cop0 || !cop1)
+ /* We would need an new statment for cases b and c, and we can't
+ due vr table, so bail out. */
+ return false;
+
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (cop0))
+ || !types_compatible_p (TREE_TYPE (cop0), TREE_TYPE (cop1)))
+ return false;
+ need_conversion =
+ !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
+ TREE_TYPE (cop0));
+ if (need_conversion)
+ return false;
+ op0 = cop0;
+ op1 = cop1;
+
+ /* We need to re-check if value ranges for new operands
+ for 1-bit precision/range. */
+ if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
+ {
+ if (TREE_CODE (op0) != SSA_NAME)
+ return false;
+ vr = get_value_range (op0);
+
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+
+ if (op1 && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
+ {
+ vr = get_value_range (op1);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+ }
+ else if (rhs_code == TRUTH_NOT_EXPR || rhs_code == BIT_NOT_EXPR)
{
rhs_code = NE_EXPR;
op1 = build_int_cst (TREE_TYPE (op0), 1);
}
else
{
- op1 = gimple_assign_rhs2 (stmt);
-
/* Reduce number of cases to handle. */
if (is_gimple_min_invariant (op1))
{
/* Exclude anything that should have been already folded. */
if (rhs_code != EQ_EXPR
&& rhs_code != NE_EXPR
- && rhs_code != TRUTH_XOR_EXPR)
+ && rhs_code != TRUTH_XOR_EXPR
+ && rhs_code != BIT_XOR_EXPR)
return false;
if (!integer_zerop (op1)
@@ -6810,18 +6977,6 @@ simplify_truth_ops_using_ranges (gimple_
/* Punt on A == B as there is no BIT_XNOR_EXPR. */
if (rhs_code == EQ_EXPR)
return false;
-
- if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
- {
- vr = get_value_range (op1);
- val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
- if (!val || !integer_onep (val))
- return false;
-
- val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
- if (!val || !integer_onep (val))
- return false;
- }
}
}
@@ -6838,7 +6993,8 @@ simplify_truth_ops_using_ranges (gimple_
warning_at (location, OPT_Wstrict_overflow,
_("assuming signed overflow does not occur when "
"simplifying && or || to & or |"));
- else
+ else if (rhs_code != BIT_AND_EXPR && rhs_code != BIT_IOR_EXPR
+ && rhs_code != BIT_XOR_EXPR)
warning_at (location, OPT_Wstrict_overflow,
_("assuming signed overflow does not occur when "
"simplifying ==, != or ! to identity or ^"));
@@ -6859,16 +7015,21 @@ simplify_truth_ops_using_ranges (gimple_
case TRUTH_AND_EXPR:
rhs_code = BIT_AND_EXPR;
break;
+ case BIT_AND_EXPR:
+ break;
case TRUTH_OR_EXPR:
rhs_code = BIT_IOR_EXPR;
+ case BIT_IOR_EXPR:
break;
case TRUTH_XOR_EXPR:
+ case BIT_XOR_EXPR:
case NE_EXPR:
if (integer_zerop (op1))
{
gimple_assign_set_rhs_with_ops (gsi,
need_conversion ? NOP_EXPR : SSA_NAME,
op0, NULL);
+ gimple_set_location (stmt, loc);
update_stmt (gsi_stmt (*gsi));
return true;
}
@@ -6879,10 +7040,20 @@ simplify_truth_ops_using_ranges (gimple_
gcc_unreachable ();
}
+ /* We can't insert here new expression as otherwise
+ tracked vr tables getting out of bounds. */
if (need_conversion)
return false;
+ /* Reduce here SSA_NAME -> SSA_NAME. */
+ while ((cop0 = ssa_name_get_inner_ssa_name_p (op0)) != NULL_TREE)
+ op0 = cop0;
+
+ while ((cop1 = ssa_name_get_inner_ssa_name_p (op1)) != NULL_TREE)
+ op1 = cop1;
+
gimple_assign_set_rhs_with_ops (gsi, rhs_code, op0, op1);
+ gimple_set_location (stmt, loc);
update_stmt (gsi_stmt (*gsi));
return true;
}
@@ -7390,6 +7561,7 @@ simplify_stmt_using_ranges (gimple_stmt_
{
case EQ_EXPR:
case NE_EXPR:
+ case BIT_NOT_EXPR:
case TRUTH_NOT_EXPR:
case TRUTH_AND_EXPR:
case TRUTH_OR_EXPR:
@@ -7425,13 +7597,21 @@ simplify_stmt_using_ranges (gimple_stmt_
if all the bits being cleared are already cleared or
all the bits being set are already set. */
if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
- return simplify_bit_ops_using_ranges (gsi, stmt);
+ {
+ if (simplify_truth_ops_using_ranges (gsi, stmt))
+ return true;
+ return simplify_bit_ops_using_ranges (gsi, stmt);
+ }
break;
CASE_CONVERT:
if (TREE_CODE (rhs1) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
- return simplify_conversion_using_ranges (stmt);
+ {
+ if (simplify_truth_ops_using_ranges (gsi, stmt))
+ return true;
+ return simplify_conversion_using_ranges (stmt);
+ }
break;
default:
@@ -7686,7 +7866,7 @@ vrp_finalize (void)
}
substitute_and_fold (op_with_constant_singleton_value_range,
- vrp_fold_stmt, false);
+ vrp_fold_stmt, false, false);
if (warn_array_bounds)
check_all_array_refs ();
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-08 16:31 ` Kai Tietz
@ 2011-07-08 16:45 ` Michael Matz
2011-07-08 17:26 ` Kai Tietz
0 siblings, 1 reply; 18+ messages in thread
From: Michael Matz @ 2011-07-08 16:45 UTC (permalink / raw)
To: Kai Tietz; +Cc: Richard Guenther, GCC Patches
Hi,
On Fri, 8 Jul 2011, Kai Tietz wrote:
> This is the reworked patch, It fixes vrp to handle bitwise one-bit
> precision typed operations and to handle some type hoisting cases, Some
> cases can't be handled as long as vrp doesn't allows to insert new
> statements in folding pass. To have in first pass better match, VRP uses
> for stmt-folding now for each BB first -> last stepping. I extended for
> this function substitute_and_fold function by an new argument, which
> indicates if scanning within BB shall be done from first to last, or
> from last to first. I removed in this new patch the part of re-doing
> stmt-fold pass, as this is no longer necessary by changing folding
> direction within BB.
You still add BIT_IOR_EXPR for POINTER_TYPE_P, which seems strange. All
these test for TYPE_PRECISION being 1 (and then handling BIT_IOR/AND_EXPR
like TRUTH_IOR/AND_EXPR) aren't necessary if you extend the general
handling for BIT_IOR_EXPR (for instance) to deal with not only constant
1, but simply handling all-ones constants specially. That is replace
integer_onep with integer_all_onesp at certain places.
Because also for wider than 1-bit precision it's the case that we can
infer usefull ranges out of "VARYING | all-ones".
Certainly the special casing on 1-bit is ugly. Work towards making
tree-vrp more lean and handling cases more general instead of piling
special case over special case.
Ciao,
Michael.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-08 16:45 ` Michael Matz
@ 2011-07-08 17:26 ` Kai Tietz
2011-07-12 17:18 ` Kai Tietz
0 siblings, 1 reply; 18+ messages in thread
From: Kai Tietz @ 2011-07-08 17:26 UTC (permalink / raw)
To: Michael Matz; +Cc: Richard Guenther, GCC Patches
2011/7/8 Michael Matz <matz@suse.de>:
> Hi,
>
> On Fri, 8 Jul 2011, Kai Tietz wrote:
>
>> This is the reworked patch, It fixes vrp to handle bitwise one-bit
>> precision typed operations and to handle some type hoisting cases, Some
>> cases can't be handled as long as vrp doesn't allows to insert new
>> statements in folding pass. To have in first pass better match, VRP uses
>> for stmt-folding now for each BB first -> last stepping. I extended for
>> this function substitute_and_fold function by an new argument, which
>> indicates if scanning within BB shall be done from first to last, or
>> from last to first. I removed in this new patch the part of re-doing
>> stmt-fold pass, as this is no longer necessary by changing folding
>> direction within BB.
>
> You still add BIT_IOR_EXPR for POINTER_TYPE_P, which seems strange.
Yes, I am aware of that. I added old behavior for BIT_IOR_EXPR here as otherwise
it would run into the gcc_unreachable case. As here we want to say
varying ... Well, even this
is not necessarily true. As an bitwise-binary-op with different width
on both arguments sides might
still have a smaller range then the type itself.
Eg: x[0..255] | y[0..1024] has a limitted range in result of max.
As we handle here value-ranges and not bit-masks for VR-inspection,
there are some limitations, too.
Eg: (x[mask:0xf0] | y[mask:0x7]) & 8 is for sure zero.
> All
> these test for TYPE_PRECISION being 1 (and then handling BIT_IOR/AND_EXPR
> like TRUTH_IOR/AND_EXPR) aren't necessary if you extend the general
> handling for BIT_IOR_EXPR (for instance) to deal with not only constant
> 1, but simply handling all-ones constants specially. That is replace
> integer_onep with integer_all_onesp at certain places.
Well, in some cases this is true, but checking for precision has the
advantages that signed cases are covered here and we need not to
compare range min/max. Nevertheless some assumptions on combinations
are only true for one-bit precision types.
> Because also for wider than 1-bit precision it's the case that we can
> infer usefull ranges out of "VARYING | all-ones".
Yes, this might have advantages on some inspections.
Kai
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-08 17:26 ` Kai Tietz
@ 2011-07-12 17:18 ` Kai Tietz
2011-07-13 11:06 ` Richard Guenther
0 siblings, 1 reply; 18+ messages in thread
From: Kai Tietz @ 2011-07-12 17:18 UTC (permalink / raw)
To: Richard Guenther; +Cc: GCC Patches
Hello,
As discussed on IRC, I reuse here the do_dce flag to choose folding
direction within BB.
Bootstrapped and regression tested for all standard-languages (plus
Ada and Obj-C++) on host x86_64-pc-linux-gnu.
Ok for apply?
Regards,
Kai
ChangeLog gcc/
2011-07-12 Kai Tietz <ktietz@redhat.com>
* tree-ssa-propagate.c (substitute_and_fold):
Only use last to first scanning direction if do_cde
is true.
* tree-vrp.c (extract_range_from_binary_expr): Add
handling for BIT_IOR_EXPR, BIT_AND_EXPR, and BIT_NOT_EXPR.
(register_edge_assert_for_1): Add handling for 1-bit
BIT_IOR_EXPR and BIT_NOT_EXPR.
(register_edge_assert_for): Add handling for 1-bit
BIT_IOR_EXPR.
(ssa_name_get_inner_ssa_name_p): New helper function.
(ssa_name_get_cast_to_p): New helper function.
(simplify_truth_ops_using_ranges): Handle prefixed
cast instruction for result, and add support for one
bit precision BIT_IOR_EXPR, BIT_AND_EXPR, BIT_XOR_EXPR,
and BIT_NOT_EXPR.
(simplify_stmt_using_ranges): Add handling for one bit
precision BIT_IOR_EXPR, BIT_AND_EXPR, BIT_XOR_EXPR,
and BIT_NOT_EXPR.
ChangeLog gcc/testsuite
2011-07-08 Kai Tietz <ktietz@redhat.com>
* gcc.dg/tree-ssa/vrp47.c: Remove dom-output
and adjust testcase for vrp output analysis.
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c
===================================================================
--- gcc.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c 2011-07-12
15:21:23.793440400 +0200
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c 2011-07-12
15:27:11.892259100 +0200
@@ -4,7 +4,7 @@
jumps when evaluating an && condition. VRP is not able to optimize
this. */
/* { dg-do compile { target { ! "mips*-*-* s390*-*-* avr-*-*
mn10300-*-*" } } } */
-/* { dg-options "-O2 -fdump-tree-vrp -fdump-tree-dom" } */
+/* { dg-options "-O2 -fdump-tree-vrp" } */
/* { dg-options "-O2 -fdump-tree-vrp -fdump-tree-dom -march=i586" {
target { i?86-*-* && ilp32 } } } */
int h(int x, int y)
@@ -36,13 +36,10 @@ int f(int x)
0 or 1. */
/* { dg-final { scan-tree-dump-times "\[xy\]\[^ \]* !=" 0 "vrp1" } } */
-/* This one needs more copy propagation that only happens in dom1. */
-/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "dom1" } } */
-/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" { xfail
*-*-* } } } */
+/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" } } */
/* These two are fully simplified by VRP. */
/* { dg-final { scan-tree-dump-times "x\[^ \]* \[|\] y" 1 "vrp1" } } */
/* { dg-final { scan-tree-dump-times "x\[^ \]* \\^ 1" 1 "vrp1" } } */
/* { dg-final { cleanup-tree-dump "vrp\[0-9\]" } } */
-/* { dg-final { cleanup-tree-dump "dom\[0-9\]" } } */
Index: gcc/gcc/tree-ssa-propagate.c
===================================================================
--- gcc.orig/gcc/tree-ssa-propagate.c 2011-07-12 15:21:23.804440400 +0200
+++ gcc/gcc/tree-ssa-propagate.c 2011-07-12 15:28:22.877773100 +0200
@@ -979,6 +979,9 @@ replace_phi_args_in (gimple phi, ssa_pro
DO_DCE is true if trivially dead stmts can be removed.
+ If DO_DCE is true, the statements within a BB are walked from
+ last to first element. Otherwise we scan from first to last element.
+
Return TRUE when something changed. */
bool
@@ -1059,9 +1062,10 @@ substitute_and_fold (ssa_prop_get_value_
for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
replace_phi_args_in (gsi_stmt (i), get_value_fn);
- /* Propagate known values into stmts. Do a backward walk to expose
- more trivially deletable stmts. */
- for (i = gsi_last_bb (bb); !gsi_end_p (i);)
+ /* Propagate known values into stmts. Do a backward walk if
+ do_dce is true. In some case it exposes
+ more trivially deletable stmts to walk backward. */
+ for (i = (do_dce ? gsi_last_bb (bb) : gsi_start_bb (bb));
!gsi_end_p (i);)
{
bool did_replace;
gimple stmt = gsi_stmt (i);
@@ -1070,7 +1074,10 @@ substitute_and_fold (ssa_prop_get_value_
gimple_stmt_iterator oldi;
oldi = i;
- gsi_prev (&i);
+ if (do_dce)
+ gsi_prev (&i);
+ else
+ gsi_next (&i);
/* Ignore ASSERT_EXPRs. They are used by VRP to generate
range information for names and they are discarded
Index: gcc/gcc/tree-vrp.c
===================================================================
--- gcc.orig/gcc/tree-vrp.c 2011-07-12 15:21:23.838440400 +0200
+++ gcc/gcc/tree-vrp.c 2011-07-12 15:27:11.976269800 +0200
@@ -2232,6 +2232,7 @@ extract_range_from_binary_expr (value_ra
some cases. */
if (code != BIT_AND_EXPR
&& code != TRUTH_AND_EXPR
+ && code != BIT_IOR_EXPR
&& code != TRUTH_OR_EXPR
&& code != TRUNC_DIV_EXPR
&& code != FLOOR_DIV_EXPR
@@ -2291,6 +2292,8 @@ extract_range_from_binary_expr (value_ra
else
set_value_range_to_varying (vr);
}
+ else if (code == BIT_IOR_EXPR)
+ set_value_range_to_varying (vr);
else
gcc_unreachable ();
@@ -2300,11 +2303,13 @@ extract_range_from_binary_expr (value_ra
/* For integer ranges, apply the operation to each end of the
range and see what we end up with. */
if (code == TRUTH_AND_EXPR
- || code == TRUTH_OR_EXPR)
+ || code == TRUTH_OR_EXPR
+ || ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+ && TYPE_PRECISION (TREE_TYPE (op1)) == 1))
{
/* If one of the operands is zero, we know that the whole
expression evaluates zero. */
- if (code == TRUTH_AND_EXPR
+ if ((code == TRUTH_AND_EXPR || code == BIT_AND_EXPR)
&& ((vr0.type == VR_RANGE
&& integer_zerop (vr0.min)
&& integer_zerop (vr0.max))
@@ -2317,7 +2322,7 @@ extract_range_from_binary_expr (value_ra
}
/* If one of the operands is one, we know that the whole
expression evaluates one. */
- else if (code == TRUTH_OR_EXPR
+ else if ((code == TRUTH_OR_EXPR || code == BIT_IOR_EXPR)
&& ((vr0.type == VR_RANGE
&& integer_onep (vr0.min)
&& integer_onep (vr0.max))
@@ -2809,7 +2814,7 @@ extract_range_from_unary_expr (value_ran
cannot easily determine a resulting range. */
if (code == FIX_TRUNC_EXPR
|| code == FLOAT_EXPR
- || code == BIT_NOT_EXPR
+ || (code == BIT_NOT_EXPR && TYPE_PRECISION (type) != 1)
|| code == CONJ_EXPR)
{
/* We can still do constant propagation here. */
@@ -3976,7 +3981,9 @@ build_assert_expr_for (tree cond, tree v
tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
assertion = gimple_build_assign (n, a);
}
- else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
+ else if (TREE_CODE (cond) == TRUTH_NOT_EXPR
+ || (TREE_CODE (cond) == BIT_NOT_EXPR
+ && TYPE_PRECISION (TREE_TYPE (cond)) == 1))
{
/* Given !V, build the assignment N = false. */
tree op0 = TREE_OPERAND (cond, 0);
@@ -4531,7 +4538,9 @@ register_edge_assert_for_1 (tree op, enu
retval |= register_edge_assert_for_1 (gimple_assign_rhs2 (op_def),
code, e, bsi);
}
- else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR)
+ else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR
+ || (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
+ && TYPE_PRECISION (TREE_TYPE (op)) == 1))
{
/* Recurse, flipping CODE. */
code = invert_tree_comparison (code, false);
@@ -4617,6 +4626,9 @@ register_edge_assert_for (tree name, edg
if (is_gimple_assign (def_stmt)
&& (gimple_assign_rhs_code (def_stmt) == TRUTH_OR_EXPR
+ || (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR
+ && INTEGRAL_TYPE_P (TREE_TYPE (name))
+ && TYPE_PRECISION (TREE_TYPE (name)) == 1)
/* For BIT_IOR_EXPR only if NAME == 0 both operands have
necessarily zero value. */
|| (comp_code == EQ_EXPR
@@ -6747,19 +6759,96 @@ varying:
return SSA_PROP_VARYING;
}
+/* Returns operand1 of ssa-name with SSA_NAME as code, Otherwise it
+ returns NULL_TREE. */
+static tree
+ssa_name_get_inner_ssa_name_p (tree op)
+{
+ gimple stmt;
+
+ if (TREE_CODE (op) != SSA_NAME
+ || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
+ return NULL_TREE;
+ stmt = SSA_NAME_DEF_STMT (op);
+ if (gimple_assign_rhs_code (stmt) != SSA_NAME)
+ return NULL_TREE;
+ return gimple_assign_rhs1 (stmt);
+}
+
+/* Returns operand of cast operation, if OP is a type-conversion. Otherwise
+ return NULL_TREE. */
+static tree
+ssa_name_get_cast_to_p (tree op)
+{
+ gimple stmt;
+
+ if (TREE_CODE (op) != SSA_NAME
+ || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
+ return NULL_TREE;
+ stmt = SSA_NAME_DEF_STMT (op);
+ if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
+ return NULL_TREE;
+ return gimple_assign_rhs1 (stmt);
+}
+
/* Simplify boolean operations if the source is known
to be already a boolean. */
static bool
simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
{
enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+ gimple stmt2 = stmt;
tree val = NULL;
- tree op0, op1;
+ tree op0, op1, cop0, cop1;
value_range_t *vr;
bool sop = false;
bool need_conversion;
+ location_t loc = gimple_location (stmt);
op0 = gimple_assign_rhs1 (stmt);
+ op1 = NULL_TREE;
+
+ /* Handle cases with prefixed type-cast. */
+ if (CONVERT_EXPR_CODE_P (rhs_code)
+ && INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ && TREE_CODE (op0) == SSA_NAME
+ && is_gimple_assign (SSA_NAME_DEF_STMT (op0))
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
+ {
+ stmt2 = SSA_NAME_DEF_STMT (op0);
+ op0 = gimple_assign_rhs1 (stmt2);
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)))
+ return false;
+ rhs_code = gimple_assign_rhs_code (stmt2);
+ if (rhs_code != BIT_NOT_EXPR && rhs_code != TRUTH_NOT_EXPR
+ && rhs_code != TRUTH_AND_EXPR && rhs_code != BIT_AND_EXPR
+ && rhs_code != TRUTH_OR_EXPR && rhs_code != BIT_IOR_EXPR
+ && rhs_code != TRUTH_XOR_EXPR && rhs_code != BIT_XOR_EXPR
+ && rhs_code != NE_EXPR && rhs_code != EQ_EXPR)
+ return false;
+ if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
+ || rhs_code == BIT_XOR_EXPR || rhs_code == TRUTH_AND_EXPR
+ || rhs_code == TRUTH_OR_EXPR || rhs_code == TRUTH_XOR_EXPR
+ || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
+ op1 = gimple_assign_rhs2 (stmt2);
+ if (gimple_has_location (stmt2))
+ loc = gimple_location (stmt2);
+ }
+ else if (CONVERT_EXPR_CODE_P (rhs_code))
+ return false;
+ else if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
+ || rhs_code == BIT_XOR_EXPR || rhs_code == TRUTH_AND_EXPR
+ || rhs_code == TRUTH_OR_EXPR || rhs_code == TRUTH_XOR_EXPR
+ || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
+ op1 = gimple_assign_rhs2 (stmt);
+
+ /* ~X is only equivalent of !X, if type-precision is one and X has
+ an integral type. */
+ if (rhs_code == BIT_NOT_EXPR
+ && (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ || TYPE_PRECISION (TREE_TYPE (op0)) != 1))
+ return false;
+
if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
{
if (TREE_CODE (op0) != SSA_NAME)
@@ -6775,22 +6864,100 @@ simplify_truth_ops_using_ranges (gimple_
return false;
}
- if (rhs_code == TRUTH_NOT_EXPR)
+ if (op1 && TREE_CODE (op1) != INTEGER_CST
+ && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
+ {
+ vr = get_value_range (op1);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+
+ need_conversion =
+ !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
+ TREE_TYPE (op0));
+
+ /* As comparisons X != 0 getting folded by prior pass to (bool) X,
+ but X == 0 might be not folded for none boolean type of X
+ to (bool) (X ^ 1).
+ So for bitwise-binary operations we have three cases to handle:
+ a) ((bool) X) op ((bool) Y)
+ b) ((bool) X) op (Y == 0) OR (X == 0) op ((bool) Y)
+ c) (X == 0) op (Y == 0)
+ The later two cases can't be handled for now, as vr tables
+ would need to be adjusted. */
+ if (need_conversion
+ && (rhs_code == BIT_XOR_EXPR
+ || rhs_code == BIT_AND_EXPR
+ || rhs_code == BIT_IOR_EXPR)
+ && TREE_CODE (op1) == SSA_NAME && TREE_CODE (op0) == SSA_NAME)
+ {
+ cop0 = ssa_name_get_cast_to_p (op0);
+ cop1 = ssa_name_get_cast_to_p (op1);
+ if (!cop0 || !cop1)
+ /* We would need an new statment for cases b and c, and we can't
+ due vr table, so bail out. */
+ return false;
+
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (cop0))
+ || !types_compatible_p (TREE_TYPE (cop0), TREE_TYPE (cop1)))
+ return false;
+ need_conversion =
+ !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
+ TREE_TYPE (cop0));
+ if (need_conversion)
+ return false;
+ op0 = cop0;
+ op1 = cop1;
+
+ /* We need to re-check if value ranges for new operands
+ for 1-bit precision/range. */
+ if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
+ {
+ if (TREE_CODE (op0) != SSA_NAME)
+ return false;
+ vr = get_value_range (op0);
+
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+
+ if (op1 && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
+ {
+ vr = get_value_range (op1);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+ }
+ else if (rhs_code == TRUTH_NOT_EXPR || rhs_code == BIT_NOT_EXPR)
{
rhs_code = NE_EXPR;
op1 = build_int_cst (TREE_TYPE (op0), 1);
}
else
{
- op1 = gimple_assign_rhs2 (stmt);
-
/* Reduce number of cases to handle. */
if (is_gimple_min_invariant (op1))
{
/* Exclude anything that should have been already folded. */
if (rhs_code != EQ_EXPR
&& rhs_code != NE_EXPR
- && rhs_code != TRUTH_XOR_EXPR)
+ && rhs_code != TRUTH_XOR_EXPR
+ && rhs_code != BIT_XOR_EXPR)
return false;
if (!integer_zerop (op1)
@@ -6810,18 +6977,6 @@ simplify_truth_ops_using_ranges (gimple_
/* Punt on A == B as there is no BIT_XNOR_EXPR. */
if (rhs_code == EQ_EXPR)
return false;
-
- if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
- {
- vr = get_value_range (op1);
- val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
- if (!val || !integer_onep (val))
- return false;
-
- val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
- if (!val || !integer_onep (val))
- return false;
- }
}
}
@@ -6838,7 +6993,8 @@ simplify_truth_ops_using_ranges (gimple_
warning_at (location, OPT_Wstrict_overflow,
_("assuming signed overflow does not occur when "
"simplifying && or || to & or |"));
- else
+ else if (rhs_code != BIT_AND_EXPR && rhs_code != BIT_IOR_EXPR
+ && rhs_code != BIT_XOR_EXPR)
warning_at (location, OPT_Wstrict_overflow,
_("assuming signed overflow does not occur when "
"simplifying ==, != or ! to identity or ^"));
@@ -6859,16 +7015,21 @@ simplify_truth_ops_using_ranges (gimple_
case TRUTH_AND_EXPR:
rhs_code = BIT_AND_EXPR;
break;
+ case BIT_AND_EXPR:
+ break;
case TRUTH_OR_EXPR:
rhs_code = BIT_IOR_EXPR;
+ case BIT_IOR_EXPR:
break;
case TRUTH_XOR_EXPR:
+ case BIT_XOR_EXPR:
case NE_EXPR:
if (integer_zerop (op1))
{
gimple_assign_set_rhs_with_ops (gsi,
need_conversion ? NOP_EXPR : SSA_NAME,
op0, NULL);
+ gimple_set_location (stmt, loc);
update_stmt (gsi_stmt (*gsi));
return true;
}
@@ -6879,10 +7040,20 @@ simplify_truth_ops_using_ranges (gimple_
gcc_unreachable ();
}
+ /* We can't insert here new expression as otherwise
+ tracked vr tables getting out of bounds. */
if (need_conversion)
return false;
+ /* Reduce here SSA_NAME -> SSA_NAME. */
+ while ((cop0 = ssa_name_get_inner_ssa_name_p (op0)) != NULL_TREE)
+ op0 = cop0;
+
+ while ((cop1 = ssa_name_get_inner_ssa_name_p (op1)) != NULL_TREE)
+ op1 = cop1;
+
gimple_assign_set_rhs_with_ops (gsi, rhs_code, op0, op1);
+ gimple_set_location (stmt, loc);
update_stmt (gsi_stmt (*gsi));
return true;
}
@@ -7415,6 +7586,7 @@ simplify_stmt_using_ranges (gimple_stmt_
{
case EQ_EXPR:
case NE_EXPR:
+ case BIT_NOT_EXPR:
case TRUTH_NOT_EXPR:
case TRUTH_AND_EXPR:
case TRUTH_OR_EXPR:
@@ -7450,13 +7622,21 @@ simplify_stmt_using_ranges (gimple_stmt_
if all the bits being cleared are already cleared or
all the bits being set are already set. */
if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
- return simplify_bit_ops_using_ranges (gsi, stmt);
+ {
+ if (simplify_truth_ops_using_ranges (gsi, stmt))
+ return true;
+ return simplify_bit_ops_using_ranges (gsi, stmt);
+ }
break;
CASE_CONVERT:
if (TREE_CODE (rhs1) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
- return simplify_conversion_using_ranges (stmt);
+ {
+ if (simplify_truth_ops_using_ranges (gsi, stmt))
+ return true;
+ return simplify_conversion_using_ranges (stmt);
+ }
break;
default:
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-12 17:18 ` Kai Tietz
@ 2011-07-13 11:06 ` Richard Guenther
2011-07-15 7:59 ` Kai Tietz
0 siblings, 1 reply; 18+ messages in thread
From: Richard Guenther @ 2011-07-13 11:06 UTC (permalink / raw)
To: Kai Tietz; +Cc: GCC Patches
On Tue, Jul 12, 2011 at 6:55 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Hello,
>
> As discussed on IRC, I reuse here the do_dce flag to choose folding
> direction within BB.
>
> Bootstrapped and regression tested for all standard-languages (plus
> Ada and Obj-C++) on host x86_64-pc-linux-gnu.
>
> Ok for apply?
The tree-ssa-propagate.c change is ok on its own.
For the tree-vrp.c changes you didn't follow the advise of removing
the TRUTH_ op support and instead generalizing the BIT_ op support
properly. There should be no "1-bit type" thing left.
Richard.
> Regards,
> Kai
>
> ChangeLog gcc/
>
> 2011-07-12 Kai Tietz <ktietz@redhat.com>
>
> * tree-ssa-propagate.c (substitute_and_fold):
> Only use last to first scanning direction if do_cde
> is true.
> * tree-vrp.c (extract_range_from_binary_expr): Add
> handling for BIT_IOR_EXPR, BIT_AND_EXPR, and BIT_NOT_EXPR.
> (register_edge_assert_for_1): Add handling for 1-bit
> BIT_IOR_EXPR and BIT_NOT_EXPR.
> (register_edge_assert_for): Add handling for 1-bit
> BIT_IOR_EXPR.
> (ssa_name_get_inner_ssa_name_p): New helper function.
> (ssa_name_get_cast_to_p): New helper function.
> (simplify_truth_ops_using_ranges): Handle prefixed
> cast instruction for result, and add support for one
> bit precision BIT_IOR_EXPR, BIT_AND_EXPR, BIT_XOR_EXPR,
> and BIT_NOT_EXPR.
> (simplify_stmt_using_ranges): Add handling for one bit
> precision BIT_IOR_EXPR, BIT_AND_EXPR, BIT_XOR_EXPR,
> and BIT_NOT_EXPR.
>
> ChangeLog gcc/testsuite
>
> 2011-07-08 Kai Tietz <ktietz@redhat.com>
>
> * gcc.dg/tree-ssa/vrp47.c: Remove dom-output
> and adjust testcase for vrp output analysis.
>
> Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c
> ===================================================================
> --- gcc.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c 2011-07-12
> 15:21:23.793440400 +0200
> +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c 2011-07-12
> 15:27:11.892259100 +0200
> @@ -4,7 +4,7 @@
> jumps when evaluating an && condition. VRP is not able to optimize
> this. */
> /* { dg-do compile { target { ! "mips*-*-* s390*-*-* avr-*-*
> mn10300-*-*" } } } */
> -/* { dg-options "-O2 -fdump-tree-vrp -fdump-tree-dom" } */
> +/* { dg-options "-O2 -fdump-tree-vrp" } */
> /* { dg-options "-O2 -fdump-tree-vrp -fdump-tree-dom -march=i586" {
> target { i?86-*-* && ilp32 } } } */
>
> int h(int x, int y)
> @@ -36,13 +36,10 @@ int f(int x)
> 0 or 1. */
> /* { dg-final { scan-tree-dump-times "\[xy\]\[^ \]* !=" 0 "vrp1" } } */
>
> -/* This one needs more copy propagation that only happens in dom1. */
> -/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "dom1" } } */
> -/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" { xfail
> *-*-* } } } */
> +/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" } } */
>
> /* These two are fully simplified by VRP. */
> /* { dg-final { scan-tree-dump-times "x\[^ \]* \[|\] y" 1 "vrp1" } } */
> /* { dg-final { scan-tree-dump-times "x\[^ \]* \\^ 1" 1 "vrp1" } } */
>
> /* { dg-final { cleanup-tree-dump "vrp\[0-9\]" } } */
> -/* { dg-final { cleanup-tree-dump "dom\[0-9\]" } } */
> Index: gcc/gcc/tree-ssa-propagate.c
> ===================================================================
> --- gcc.orig/gcc/tree-ssa-propagate.c 2011-07-12 15:21:23.804440400 +0200
> +++ gcc/gcc/tree-ssa-propagate.c 2011-07-12 15:28:22.877773100 +0200
> @@ -979,6 +979,9 @@ replace_phi_args_in (gimple phi, ssa_pro
>
> DO_DCE is true if trivially dead stmts can be removed.
>
> + If DO_DCE is true, the statements within a BB are walked from
> + last to first element. Otherwise we scan from first to last element.
> +
> Return TRUE when something changed. */
>
> bool
> @@ -1059,9 +1062,10 @@ substitute_and_fold (ssa_prop_get_value_
> for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
> replace_phi_args_in (gsi_stmt (i), get_value_fn);
>
> - /* Propagate known values into stmts. Do a backward walk to expose
> - more trivially deletable stmts. */
> - for (i = gsi_last_bb (bb); !gsi_end_p (i);)
> + /* Propagate known values into stmts. Do a backward walk if
> + do_dce is true. In some case it exposes
> + more trivially deletable stmts to walk backward. */
> + for (i = (do_dce ? gsi_last_bb (bb) : gsi_start_bb (bb));
> !gsi_end_p (i);)
> {
> bool did_replace;
> gimple stmt = gsi_stmt (i);
> @@ -1070,7 +1074,10 @@ substitute_and_fold (ssa_prop_get_value_
> gimple_stmt_iterator oldi;
>
> oldi = i;
> - gsi_prev (&i);
> + if (do_dce)
> + gsi_prev (&i);
> + else
> + gsi_next (&i);
>
> /* Ignore ASSERT_EXPRs. They are used by VRP to generate
> range information for names and they are discarded
> Index: gcc/gcc/tree-vrp.c
> ===================================================================
> --- gcc.orig/gcc/tree-vrp.c 2011-07-12 15:21:23.838440400 +0200
> +++ gcc/gcc/tree-vrp.c 2011-07-12 15:27:11.976269800 +0200
> @@ -2232,6 +2232,7 @@ extract_range_from_binary_expr (value_ra
> some cases. */
> if (code != BIT_AND_EXPR
> && code != TRUTH_AND_EXPR
> + && code != BIT_IOR_EXPR
> && code != TRUTH_OR_EXPR
> && code != TRUNC_DIV_EXPR
> && code != FLOOR_DIV_EXPR
> @@ -2291,6 +2292,8 @@ extract_range_from_binary_expr (value_ra
> else
> set_value_range_to_varying (vr);
> }
> + else if (code == BIT_IOR_EXPR)
> + set_value_range_to_varying (vr);
> else
> gcc_unreachable ();
>
> @@ -2300,11 +2303,13 @@ extract_range_from_binary_expr (value_ra
> /* For integer ranges, apply the operation to each end of the
> range and see what we end up with. */
> if (code == TRUTH_AND_EXPR
> - || code == TRUTH_OR_EXPR)
> + || code == TRUTH_OR_EXPR
> + || ((code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
> + && TYPE_PRECISION (TREE_TYPE (op1)) == 1))
> {
> /* If one of the operands is zero, we know that the whole
> expression evaluates zero. */
> - if (code == TRUTH_AND_EXPR
> + if ((code == TRUTH_AND_EXPR || code == BIT_AND_EXPR)
> && ((vr0.type == VR_RANGE
> && integer_zerop (vr0.min)
> && integer_zerop (vr0.max))
> @@ -2317,7 +2322,7 @@ extract_range_from_binary_expr (value_ra
> }
> /* If one of the operands is one, we know that the whole
> expression evaluates one. */
> - else if (code == TRUTH_OR_EXPR
> + else if ((code == TRUTH_OR_EXPR || code == BIT_IOR_EXPR)
> && ((vr0.type == VR_RANGE
> && integer_onep (vr0.min)
> && integer_onep (vr0.max))
> @@ -2809,7 +2814,7 @@ extract_range_from_unary_expr (value_ran
> cannot easily determine a resulting range. */
> if (code == FIX_TRUNC_EXPR
> || code == FLOAT_EXPR
> - || code == BIT_NOT_EXPR
> + || (code == BIT_NOT_EXPR && TYPE_PRECISION (type) != 1)
> || code == CONJ_EXPR)
> {
> /* We can still do constant propagation here. */
> @@ -3976,7 +3981,9 @@ build_assert_expr_for (tree cond, tree v
> tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
> assertion = gimple_build_assign (n, a);
> }
> - else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
> + else if (TREE_CODE (cond) == TRUTH_NOT_EXPR
> + || (TREE_CODE (cond) == BIT_NOT_EXPR
> + && TYPE_PRECISION (TREE_TYPE (cond)) == 1))
> {
> /* Given !V, build the assignment N = false. */
> tree op0 = TREE_OPERAND (cond, 0);
> @@ -4531,7 +4538,9 @@ register_edge_assert_for_1 (tree op, enu
> retval |= register_edge_assert_for_1 (gimple_assign_rhs2 (op_def),
> code, e, bsi);
> }
> - else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR)
> + else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR
> + || (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
> + && TYPE_PRECISION (TREE_TYPE (op)) == 1))
> {
> /* Recurse, flipping CODE. */
> code = invert_tree_comparison (code, false);
> @@ -4617,6 +4626,9 @@ register_edge_assert_for (tree name, edg
>
> if (is_gimple_assign (def_stmt)
> && (gimple_assign_rhs_code (def_stmt) == TRUTH_OR_EXPR
> + || (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR
> + && INTEGRAL_TYPE_P (TREE_TYPE (name))
> + && TYPE_PRECISION (TREE_TYPE (name)) == 1)
> /* For BIT_IOR_EXPR only if NAME == 0 both operands have
> necessarily zero value. */
> || (comp_code == EQ_EXPR
> @@ -6747,19 +6759,96 @@ varying:
> return SSA_PROP_VARYING;
> }
>
> +/* Returns operand1 of ssa-name with SSA_NAME as code, Otherwise it
> + returns NULL_TREE. */
> +static tree
> +ssa_name_get_inner_ssa_name_p (tree op)
> +{
> + gimple stmt;
> +
> + if (TREE_CODE (op) != SSA_NAME
> + || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
> + return NULL_TREE;
> + stmt = SSA_NAME_DEF_STMT (op);
> + if (gimple_assign_rhs_code (stmt) != SSA_NAME)
> + return NULL_TREE;
> + return gimple_assign_rhs1 (stmt);
> +}
> +
> +/* Returns operand of cast operation, if OP is a type-conversion. Otherwise
> + return NULL_TREE. */
> +static tree
> +ssa_name_get_cast_to_p (tree op)
> +{
> + gimple stmt;
> +
> + if (TREE_CODE (op) != SSA_NAME
> + || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
> + return NULL_TREE;
> + stmt = SSA_NAME_DEF_STMT (op);
> + if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
> + return NULL_TREE;
> + return gimple_assign_rhs1 (stmt);
> +}
> +
> /* Simplify boolean operations if the source is known
> to be already a boolean. */
> static bool
> simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
> {
> enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
> + gimple stmt2 = stmt;
> tree val = NULL;
> - tree op0, op1;
> + tree op0, op1, cop0, cop1;
> value_range_t *vr;
> bool sop = false;
> bool need_conversion;
> + location_t loc = gimple_location (stmt);
>
> op0 = gimple_assign_rhs1 (stmt);
> + op1 = NULL_TREE;
> +
> + /* Handle cases with prefixed type-cast. */
> + if (CONVERT_EXPR_CODE_P (rhs_code)
> + && INTEGRAL_TYPE_P (TREE_TYPE (op0))
> + && TREE_CODE (op0) == SSA_NAME
> + && is_gimple_assign (SSA_NAME_DEF_STMT (op0))
> + && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
> + {
> + stmt2 = SSA_NAME_DEF_STMT (op0);
> + op0 = gimple_assign_rhs1 (stmt2);
> + if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)))
> + return false;
> + rhs_code = gimple_assign_rhs_code (stmt2);
> + if (rhs_code != BIT_NOT_EXPR && rhs_code != TRUTH_NOT_EXPR
> + && rhs_code != TRUTH_AND_EXPR && rhs_code != BIT_AND_EXPR
> + && rhs_code != TRUTH_OR_EXPR && rhs_code != BIT_IOR_EXPR
> + && rhs_code != TRUTH_XOR_EXPR && rhs_code != BIT_XOR_EXPR
> + && rhs_code != NE_EXPR && rhs_code != EQ_EXPR)
> + return false;
> + if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
> + || rhs_code == BIT_XOR_EXPR || rhs_code == TRUTH_AND_EXPR
> + || rhs_code == TRUTH_OR_EXPR || rhs_code == TRUTH_XOR_EXPR
> + || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
> + op1 = gimple_assign_rhs2 (stmt2);
> + if (gimple_has_location (stmt2))
> + loc = gimple_location (stmt2);
> + }
> + else if (CONVERT_EXPR_CODE_P (rhs_code))
> + return false;
> + else if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
> + || rhs_code == BIT_XOR_EXPR || rhs_code == TRUTH_AND_EXPR
> + || rhs_code == TRUTH_OR_EXPR || rhs_code == TRUTH_XOR_EXPR
> + || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
> + op1 = gimple_assign_rhs2 (stmt);
> +
> + /* ~X is only equivalent of !X, if type-precision is one and X has
> + an integral type. */
> + if (rhs_code == BIT_NOT_EXPR
> + && (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
> + || TYPE_PRECISION (TREE_TYPE (op0)) != 1))
> + return false;
> +
> if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
> {
> if (TREE_CODE (op0) != SSA_NAME)
> @@ -6775,22 +6864,100 @@ simplify_truth_ops_using_ranges (gimple_
> return false;
> }
>
> - if (rhs_code == TRUTH_NOT_EXPR)
> + if (op1 && TREE_CODE (op1) != INTEGER_CST
> + && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
> + {
> + vr = get_value_range (op1);
> + val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> +
> + val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> + }
> +
> + need_conversion =
> + !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
> + TREE_TYPE (op0));
> +
> + /* As comparisons X != 0 getting folded by prior pass to (bool) X,
> + but X == 0 might be not folded for none boolean type of X
> + to (bool) (X ^ 1).
> + So for bitwise-binary operations we have three cases to handle:
> + a) ((bool) X) op ((bool) Y)
> + b) ((bool) X) op (Y == 0) OR (X == 0) op ((bool) Y)
> + c) (X == 0) op (Y == 0)
> + The later two cases can't be handled for now, as vr tables
> + would need to be adjusted. */
> + if (need_conversion
> + && (rhs_code == BIT_XOR_EXPR
> + || rhs_code == BIT_AND_EXPR
> + || rhs_code == BIT_IOR_EXPR)
> + && TREE_CODE (op1) == SSA_NAME && TREE_CODE (op0) == SSA_NAME)
> + {
> + cop0 = ssa_name_get_cast_to_p (op0);
> + cop1 = ssa_name_get_cast_to_p (op1);
> + if (!cop0 || !cop1)
> + /* We would need an new statment for cases b and c, and we can't
> + due vr table, so bail out. */
> + return false;
> +
> + if (!INTEGRAL_TYPE_P (TREE_TYPE (cop0))
> + || !types_compatible_p (TREE_TYPE (cop0), TREE_TYPE (cop1)))
> + return false;
> + need_conversion =
> + !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
> + TREE_TYPE (cop0));
> + if (need_conversion)
> + return false;
> + op0 = cop0;
> + op1 = cop1;
> +
> + /* We need to re-check if value ranges for new operands
> + for 1-bit precision/range. */
> + if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
> + {
> + if (TREE_CODE (op0) != SSA_NAME)
> + return false;
> + vr = get_value_range (op0);
> +
> + val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> +
> + val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> + }
> +
> + if (op1 && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
> + {
> + vr = get_value_range (op1);
> + val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> +
> + val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> + }
> + }
> + else if (rhs_code == TRUTH_NOT_EXPR || rhs_code == BIT_NOT_EXPR)
> {
> rhs_code = NE_EXPR;
> op1 = build_int_cst (TREE_TYPE (op0), 1);
> }
> else
> {
> - op1 = gimple_assign_rhs2 (stmt);
> -
> /* Reduce number of cases to handle. */
> if (is_gimple_min_invariant (op1))
> {
> /* Exclude anything that should have been already folded. */
> if (rhs_code != EQ_EXPR
> && rhs_code != NE_EXPR
> - && rhs_code != TRUTH_XOR_EXPR)
> + && rhs_code != TRUTH_XOR_EXPR
> + && rhs_code != BIT_XOR_EXPR)
> return false;
>
> if (!integer_zerop (op1)
> @@ -6810,18 +6977,6 @@ simplify_truth_ops_using_ranges (gimple_
> /* Punt on A == B as there is no BIT_XNOR_EXPR. */
> if (rhs_code == EQ_EXPR)
> return false;
> -
> - if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
> - {
> - vr = get_value_range (op1);
> - val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> - if (!val || !integer_onep (val))
> - return false;
> -
> - val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> - if (!val || !integer_onep (val))
> - return false;
> - }
> }
> }
>
> @@ -6838,7 +6993,8 @@ simplify_truth_ops_using_ranges (gimple_
> warning_at (location, OPT_Wstrict_overflow,
> _("assuming signed overflow does not occur when "
> "simplifying && or || to & or |"));
> - else
> + else if (rhs_code != BIT_AND_EXPR && rhs_code != BIT_IOR_EXPR
> + && rhs_code != BIT_XOR_EXPR)
> warning_at (location, OPT_Wstrict_overflow,
> _("assuming signed overflow does not occur when "
> "simplifying ==, != or ! to identity or ^"));
> @@ -6859,16 +7015,21 @@ simplify_truth_ops_using_ranges (gimple_
> case TRUTH_AND_EXPR:
> rhs_code = BIT_AND_EXPR;
> break;
> + case BIT_AND_EXPR:
> + break;
> case TRUTH_OR_EXPR:
> rhs_code = BIT_IOR_EXPR;
> + case BIT_IOR_EXPR:
> break;
> case TRUTH_XOR_EXPR:
> + case BIT_XOR_EXPR:
> case NE_EXPR:
> if (integer_zerop (op1))
> {
> gimple_assign_set_rhs_with_ops (gsi,
> need_conversion ? NOP_EXPR : SSA_NAME,
> op0, NULL);
> + gimple_set_location (stmt, loc);
> update_stmt (gsi_stmt (*gsi));
> return true;
> }
> @@ -6879,10 +7040,20 @@ simplify_truth_ops_using_ranges (gimple_
> gcc_unreachable ();
> }
>
> + /* We can't insert here new expression as otherwise
> + tracked vr tables getting out of bounds. */
> if (need_conversion)
> return false;
>
> + /* Reduce here SSA_NAME -> SSA_NAME. */
> + while ((cop0 = ssa_name_get_inner_ssa_name_p (op0)) != NULL_TREE)
> + op0 = cop0;
> +
> + while ((cop1 = ssa_name_get_inner_ssa_name_p (op1)) != NULL_TREE)
> + op1 = cop1;
> +
> gimple_assign_set_rhs_with_ops (gsi, rhs_code, op0, op1);
> + gimple_set_location (stmt, loc);
> update_stmt (gsi_stmt (*gsi));
> return true;
> }
> @@ -7415,6 +7586,7 @@ simplify_stmt_using_ranges (gimple_stmt_
> {
> case EQ_EXPR:
> case NE_EXPR:
> + case BIT_NOT_EXPR:
> case TRUTH_NOT_EXPR:
> case TRUTH_AND_EXPR:
> case TRUTH_OR_EXPR:
> @@ -7450,13 +7622,21 @@ simplify_stmt_using_ranges (gimple_stmt_
> if all the bits being cleared are already cleared or
> all the bits being set are already set. */
> if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
> - return simplify_bit_ops_using_ranges (gsi, stmt);
> + {
> + if (simplify_truth_ops_using_ranges (gsi, stmt))
> + return true;
> + return simplify_bit_ops_using_ranges (gsi, stmt);
> + }
> break;
>
> CASE_CONVERT:
> if (TREE_CODE (rhs1) == SSA_NAME
> && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
> - return simplify_conversion_using_ranges (stmt);
> + {
> + if (simplify_truth_ops_using_ranges (gsi, stmt))
> + return true;
> + return simplify_conversion_using_ranges (stmt);
> + }
> break;
>
> default:
>
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-13 11:06 ` Richard Guenther
@ 2011-07-15 7:59 ` Kai Tietz
2011-07-19 12:24 ` Richard Guenther
0 siblings, 1 reply; 18+ messages in thread
From: Kai Tietz @ 2011-07-15 7:59 UTC (permalink / raw)
To: Richard Guenther; +Cc: GCC Patches
Hello,
This patch removes from tree-vrp the use of TRUTH-bitwise expression codes. Also
it merges the handling for boolean compatible and non-boolean typed
bitwise-binary
expressions.
Additional it adds primitive checks for bitwise-not expression on
boolean-compatible
types.
In substitute_and_fold the scan-direction of statements within a BB is
controlled now
by its do_dce flag. This provides better results in vrp-pass.
ChangeLog gcc
2011-07-15 Kai Tietz <ktietz@redhat.com>
* tree-ssa-propagate.c (substitute_and_fold): Use
do_dce flag to deside, if BB's statements are scanned
in last to first, or first to last order.
* tree-vrp.c (extract_range_from_binary_expr):
Remove TRUTH-binary checks. And unify bitwise-binary
cases.
(register_edge_assert_for_1): Add handling boolean-compatible
typed BIT_IOR_EXPR and BIT_NOT_EXPR.
(extract_range_from_unary_expr): Add support for 1-bit
integral typed BIT_NOT_EXPR expression.
(extract_range_from_assignment): Remove TRUTH-binary checks.
Add handling for 1-bit integral typed BIT_NOT_EXPR expression.
(build_assert_expr_for): Likewise.
(register_edge_assert_for_1): Likewise.
(simplify_stmt_using_ranges): Likewise.
(ssa_name_get_inner_ssa_name_p): New helper function.
(ssa_name_get_cast_to_p): New helper function.
(simplify_truth_ops_using_ranges): Handle prefixed
cast instruction for result. Remove TRUTH-binary checks.
Add handling for 1-bit integral typed BIT_NOT_EXPR expression.
and BIT_NOT_EXPR.
Add handling for one bit
ChangeLog gcc/testsuite
2011-07-15 Kai Tietz <ktietz@redhat.com>
* gcc.dg/tree-ssa/vrp47.c: Test no longer needs
dom dump.
Bootstrapped and regression tested for all standard languages (plus
Ada & Obj-C++) on x86_64-pc-linux-gnu. Ok for apply?
Regards,
Kai
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c
===================================================================
--- gcc.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c 2011-07-13
12:57:46.869620200 +0200
+++ gcc/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c 2011-07-13
22:29:53.221967000 +0200
@@ -4,7 +4,7 @@
jumps when evaluating an && condition. VRP is not able to optimize
this. */
/* { dg-do compile { target { ! "mips*-*-* s390*-*-* avr-*-*
mn10300-*-*" } } } */
-/* { dg-options "-O2 -fdump-tree-vrp -fdump-tree-dom" } */
+/* { dg-options "-O2 -fdump-tree-vrp" } */
/* { dg-options "-O2 -fdump-tree-vrp -fdump-tree-dom -march=i586" {
target { i?86-*-* && ilp32 } } } */
int h(int x, int y)
@@ -36,13 +36,10 @@ int f(int x)
0 or 1. */
/* { dg-final { scan-tree-dump-times "\[xy\]\[^ \]* !=" 0 "vrp1" } } */
-/* This one needs more copy propagation that only happens in dom1. */
-/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "dom1" } } */
-/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" { xfail
*-*-* } } } */
+/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" } } */
/* These two are fully simplified by VRP. */
/* { dg-final { scan-tree-dump-times "x\[^ \]* \[|\] y" 1 "vrp1" } } */
/* { dg-final { scan-tree-dump-times "x\[^ \]* \\^ 1" 1 "vrp1" } } */
/* { dg-final { cleanup-tree-dump "vrp\[0-9\]" } } */
-/* { dg-final { cleanup-tree-dump "dom\[0-9\]" } } */
Index: gcc/gcc/tree-ssa-propagate.c
===================================================================
--- gcc.orig/gcc/tree-ssa-propagate.c 2011-07-13 12:57:46.870620200 +0200
+++ gcc/gcc/tree-ssa-propagate.c 2011-07-13 22:29:53.253971100 +0200
@@ -979,6 +979,9 @@ replace_phi_args_in (gimple phi, ssa_pro
DO_DCE is true if trivially dead stmts can be removed.
+ If DO_DCE is true, the statements within a BB are walked from
+ last to first element. Otherwise we scan from first to last element.
+
Return TRUE when something changed. */
bool
@@ -1059,9 +1062,10 @@ substitute_and_fold (ssa_prop_get_value_
for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
replace_phi_args_in (gsi_stmt (i), get_value_fn);
- /* Propagate known values into stmts. Do a backward walk to expose
- more trivially deletable stmts. */
- for (i = gsi_last_bb (bb); !gsi_end_p (i);)
+ /* Propagate known values into stmts. Do a backward walk if
+ do_dce is true. In some case it exposes
+ more trivially deletable stmts to walk backward. */
+ for (i = (do_dce ? gsi_last_bb (bb) : gsi_start_bb (bb));
!gsi_end_p (i);)
{
bool did_replace;
gimple stmt = gsi_stmt (i);
@@ -1070,7 +1074,10 @@ substitute_and_fold (ssa_prop_get_value_
gimple_stmt_iterator oldi;
oldi = i;
- gsi_prev (&i);
+ if (do_dce)
+ gsi_prev (&i);
+ else
+ gsi_next (&i);
/* Ignore ASSERT_EXPRs. They are used by VRP to generate
range information for names and they are discarded
Index: gcc/gcc/tree-vrp.c
===================================================================
--- gcc.orig/gcc/tree-vrp.c 2011-07-13 22:25:14.690598100 +0200
+++ gcc/gcc/tree-vrp.c 2011-07-15 08:53:21.086266100 +0200
@@ -2174,9 +2174,7 @@ extract_range_from_binary_expr (value_ra
&& code != MIN_EXPR
&& code != MAX_EXPR
&& code != BIT_AND_EXPR
- && code != BIT_IOR_EXPR
- && code != TRUTH_AND_EXPR
- && code != TRUTH_OR_EXPR)
+ && code != BIT_IOR_EXPR)
{
/* We can still do constant propagation here. */
tree const_op0 = op_with_constant_singleton_value_range (op0);
@@ -2231,8 +2229,7 @@ extract_range_from_binary_expr (value_ra
divisions. TODO, we may be able to derive anti-ranges in
some cases. */
if (code != BIT_AND_EXPR
- && code != TRUTH_AND_EXPR
- && code != TRUTH_OR_EXPR
+ && code != BIT_IOR_EXPR
&& code != TRUNC_DIV_EXPR
&& code != FLOOR_DIV_EXPR
&& code != CEIL_DIV_EXPR
@@ -2291,6 +2288,8 @@ extract_range_from_binary_expr (value_ra
else
set_value_range_to_varying (vr);
}
+ else if (code == BIT_IOR_EXPR)
+ set_value_range_to_varying (vr);
else
gcc_unreachable ();
@@ -2299,55 +2298,7 @@ extract_range_from_binary_expr (value_ra
/* For integer ranges, apply the operation to each end of the
range and see what we end up with. */
- if (code == TRUTH_AND_EXPR
- || code == TRUTH_OR_EXPR)
- {
- /* If one of the operands is zero, we know that the whole
- expression evaluates zero. */
- if (code == TRUTH_AND_EXPR
- && ((vr0.type == VR_RANGE
- && integer_zerop (vr0.min)
- && integer_zerop (vr0.max))
- || (vr1.type == VR_RANGE
- && integer_zerop (vr1.min)
- && integer_zerop (vr1.max))))
- {
- type = VR_RANGE;
- min = max = build_int_cst (expr_type, 0);
- }
- /* If one of the operands is one, we know that the whole
- expression evaluates one. */
- else if (code == TRUTH_OR_EXPR
- && ((vr0.type == VR_RANGE
- && integer_onep (vr0.min)
- && integer_onep (vr0.max))
- || (vr1.type == VR_RANGE
- && integer_onep (vr1.min)
- && integer_onep (vr1.max))))
- {
- type = VR_RANGE;
- min = max = build_int_cst (expr_type, 1);
- }
- else if (vr0.type != VR_VARYING
- && vr1.type != VR_VARYING
- && vr0.type == vr1.type
- && !symbolic_range_p (&vr0)
- && !overflow_infinity_range_p (&vr0)
- && !symbolic_range_p (&vr1)
- && !overflow_infinity_range_p (&vr1))
- {
- /* Boolean expressions cannot be folded with int_const_binop. */
- min = fold_binary (code, expr_type, vr0.min, vr1.min);
- max = fold_binary (code, expr_type, vr0.max, vr1.max);
- }
- else
- {
- /* The result of a TRUTH_*_EXPR is always true or false. */
- set_value_range_to_truthvalue (vr, expr_type);
- return;
- }
- }
- else if (code == PLUS_EXPR
+ if (code == PLUS_EXPR
|| code == MIN_EXPR
|| code == MAX_EXPR)
{
@@ -2682,71 +2633,125 @@ extract_range_from_binary_expr (value_ra
double_int may_be_nonzero0, may_be_nonzero1;
double_int must_be_nonzero0, must_be_nonzero1;
- vr0_int_cst_singleton_p = range_int_cst_singleton_p (&vr0);
- vr1_int_cst_singleton_p = range_int_cst_singleton_p (&vr1);
- int_cst_range0 = zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0,
- &must_be_nonzero0);
- int_cst_range1 = zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1,
- &must_be_nonzero1);
-
- type = VR_RANGE;
- if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
- min = max = int_const_binop (code, vr0.max, vr1.max);
- else if (!int_cst_range0 && !int_cst_range1)
+ /* If one of the operands is zero, we know that the whole
+ expression evaluates zero. */
+ if (code == BIT_AND_EXPR
+ && ((vr0.type == VR_RANGE
+ && integer_zerop (vr0.min)
+ && integer_zerop (vr0.max))
+ || (vr1.type == VR_RANGE
+ && integer_zerop (vr1.min)
+ && integer_zerop (vr1.max))))
{
- set_value_range_to_varying (vr);
- return;
+ type = VR_RANGE;
+ min = max = build_int_cst (expr_type, 0);
}
- else if (code == BIT_AND_EXPR)
+ /* If one of the operands has all bits set to one, we know
+ that the whole expression evaluates to this one. */
+ else if (code == BIT_IOR_EXPR
+ && (vr0.type == VR_RANGE
+ && integer_all_onesp (vr0.min)
+ && integer_all_onesp (vr0.max)))
{
- min = double_int_to_tree (expr_type,
- double_int_and (must_be_nonzero0,
- must_be_nonzero1));
- max = double_int_to_tree (expr_type,
- double_int_and (may_be_nonzero0,
- may_be_nonzero1));
- if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
- min = NULL_TREE;
- if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
- max = NULL_TREE;
- if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
- {
- if (min == NULL_TREE)
- min = build_int_cst (expr_type, 0);
- if (max == NULL_TREE || tree_int_cst_lt (vr0.max, max))
- max = vr0.max;
+ type = VR_RANGE;
+ min = max = fold_convert (expr_type, vr0.min);
+ }
+ else if (code == BIT_IOR_EXPR
+ && (vr1.type == VR_RANGE
+ && integer_all_onesp (vr1.min)
+ && integer_all_onesp (vr1.max)))
+ {
+ type = VR_RANGE;
+ min = max = fold_convert (expr_type, vr1.min);
+ }
+ else if (TYPE_PRECISION (TREE_TYPE (op1)) == 1)
+ {
+ if (vr0.type != VR_VARYING
+ && vr1.type != VR_VARYING
+ && vr0.type == vr1.type
+ && !symbolic_range_p (&vr0)
+ && !overflow_infinity_range_p (&vr0)
+ && !symbolic_range_p (&vr1)
+ && !overflow_infinity_range_p (&vr1))
+ {
+ /* Boolean expressions cannot be folded with int_const_binop. */
+ min = fold_binary (code, expr_type, vr0.min, vr1.min);
+ max = fold_binary (code, expr_type, vr0.max, vr1.max);
}
- if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
+ else
{
- if (min == NULL_TREE)
- min = build_int_cst (expr_type, 0);
- if (max == NULL_TREE || tree_int_cst_lt (vr1.max, max))
- max = vr1.max;
+ set_value_range_to_varying (vr);
+ return;
}
}
- else if (!int_cst_range0
- || !int_cst_range1
- || tree_int_cst_sgn (vr0.min) < 0
- || tree_int_cst_sgn (vr1.min) < 0)
- {
- set_value_range_to_varying (vr);
- return;
- }
else
- {
- min = double_int_to_tree (expr_type,
- double_int_ior (must_be_nonzero0,
- must_be_nonzero1));
- max = double_int_to_tree (expr_type,
- double_int_ior (may_be_nonzero0,
- may_be_nonzero1));
- if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
- min = vr0.min;
+ {
+ vr0_int_cst_singleton_p = range_int_cst_singleton_p (&vr0);
+ vr1_int_cst_singleton_p = range_int_cst_singleton_p (&vr1);
+ int_cst_range0 = zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0,
+ &must_be_nonzero0);
+ int_cst_range1 = zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1,
+ &must_be_nonzero1);
+
+ type = VR_RANGE;
+ if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
+ min = max = int_const_binop (code, vr0.max, vr1.max);
+ else if (!int_cst_range0 && !int_cst_range1)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ else if (code == BIT_AND_EXPR)
+ {
+ min = double_int_to_tree (expr_type,
+ double_int_and (must_be_nonzero0,
+ must_be_nonzero1));
+ max = double_int_to_tree (expr_type,
+ double_int_and (may_be_nonzero0,
+ may_be_nonzero1));
+ if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
+ min = NULL_TREE;
+ if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
+ max = NULL_TREE;
+ if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
+ {
+ if (min == NULL_TREE)
+ min = build_int_cst (expr_type, 0);
+ if (max == NULL_TREE || tree_int_cst_lt (vr0.max, max))
+ max = vr0.max;
+ }
+ if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
+ {
+ if (min == NULL_TREE)
+ min = build_int_cst (expr_type, 0);
+ if (max == NULL_TREE || tree_int_cst_lt (vr1.max, max))
+ max = vr1.max;
+ }
+ }
+ else if (!int_cst_range0
+ || !int_cst_range1
+ || tree_int_cst_sgn (vr0.min) < 0
+ || tree_int_cst_sgn (vr1.min) < 0)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
else
- min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
- if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
- max = NULL_TREE;
- min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
+ {
+ min = double_int_to_tree (expr_type,
+ double_int_ior (must_be_nonzero0,
+ must_be_nonzero1));
+ max = double_int_to_tree (expr_type,
+ double_int_ior (may_be_nonzero0,
+ may_be_nonzero1));
+ if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
+ min = vr0.min;
+ else
+ min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
+ if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
+ max = NULL_TREE;
+ min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
+ }
}
}
else
@@ -2809,7 +2814,7 @@ extract_range_from_unary_expr (value_ran
cannot easily determine a resulting range. */
if (code == FIX_TRUNC_EXPR
|| code == FLOAT_EXPR
- || code == BIT_NOT_EXPR
+ || (code == BIT_NOT_EXPR && TYPE_PRECISION (type) != 1)
|| code == CONJ_EXPR)
{
/* We can still do constant propagation here. */
@@ -3303,10 +3308,7 @@ extract_range_from_assignment (value_ran
extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
else if (code == SSA_NAME)
extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
- else if (TREE_CODE_CLASS (code) == tcc_binary
- || code == TRUTH_AND_EXPR
- || code == TRUTH_OR_EXPR
- || code == TRUTH_XOR_EXPR)
+ else if (TREE_CODE_CLASS (code) == tcc_binary)
extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt),
gimple_expr_type (stmt),
gimple_assign_rhs1 (stmt),
@@ -3976,7 +3978,9 @@ build_assert_expr_for (tree cond, tree v
tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
assertion = gimple_build_assign (n, a);
}
- else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
+ else if (TREE_CODE (cond) == TRUTH_NOT_EXPR
+ || (TREE_CODE (cond) == BIT_NOT_EXPR
+ && TYPE_PRECISION (TREE_TYPE (cond)) == 1))
{
/* Given !V, build the assignment N = false. */
tree op0 = TREE_OPERAND (cond, 0);
@@ -4519,11 +4523,9 @@ register_edge_assert_for_1 (tree op, enu
invert);
}
else if ((code == NE_EXPR
- && (gimple_assign_rhs_code (op_def) == TRUTH_AND_EXPR
- || gimple_assign_rhs_code (op_def) == BIT_AND_EXPR))
+ && gimple_assign_rhs_code (op_def) == BIT_AND_EXPR)
|| (code == EQ_EXPR
- && (gimple_assign_rhs_code (op_def) == TRUTH_OR_EXPR
- || gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR)))
+ && gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR))
{
/* Recurse on each operand. */
retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
@@ -4531,7 +4533,9 @@ register_edge_assert_for_1 (tree op, enu
retval |= register_edge_assert_for_1 (gimple_assign_rhs2 (op_def),
code, e, bsi);
}
- else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR)
+ else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR
+ || (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
+ && TYPE_PRECISION (TREE_TYPE (op)) == 1))
{
/* Recurse, flipping CODE. */
code = invert_tree_comparison (code, false);
@@ -4588,8 +4592,8 @@ register_edge_assert_for (tree name, edg
the value zero or one, then we may be able to assert values
for SSA_NAMEs which flow into COND. */
- /* In the case of NAME == 1 or NAME != 0, for TRUTH_AND_EXPR defining
- statement of NAME we can assert both operands of the TRUTH_AND_EXPR
+ /* In the case of NAME == 1 or NAME != 0, for BIT_AND_EXPR defining
+ statement of NAME we can assert both operands of the BIT_AND_EXPR
have nonzero value. */
if (((comp_code == EQ_EXPR && integer_onep (val))
|| (comp_code == NE_EXPR && integer_zerop (val))))
@@ -4597,8 +4601,7 @@ register_edge_assert_for (tree name, edg
gimple def_stmt = SSA_NAME_DEF_STMT (name);
if (is_gimple_assign (def_stmt)
- && (gimple_assign_rhs_code (def_stmt) == TRUTH_AND_EXPR
- || gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR))
+ && gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR)
{
tree op0 = gimple_assign_rhs1 (def_stmt);
tree op1 = gimple_assign_rhs2 (def_stmt);
@@ -4607,8 +4610,8 @@ register_edge_assert_for (tree name, edg
}
}
- /* In the case of NAME == 0 or NAME != 1, for TRUTH_OR_EXPR defining
- statement of NAME we can assert both operands of the TRUTH_OR_EXPR
+ /* In the case of NAME == 0 or NAME != 1, for BIT_IOR_EXPR defining
+ statement of NAME we can assert both operands of the BIT_IOR_EXPR
have zero value. */
if (((comp_code == EQ_EXPR && integer_zerop (val))
|| (comp_code == NE_EXPR && integer_onep (val))))
@@ -4616,11 +4619,12 @@ register_edge_assert_for (tree name, edg
gimple def_stmt = SSA_NAME_DEF_STMT (name);
if (is_gimple_assign (def_stmt)
- && (gimple_assign_rhs_code (def_stmt) == TRUTH_OR_EXPR
+ && ((gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR
+ && TYPE_PRECISION (TREE_TYPE (name)) == 1)
/* For BIT_IOR_EXPR only if NAME == 0 both operands have
necessarily zero value. */
|| (comp_code == EQ_EXPR
- && (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR))))
+ && gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)))
{
tree op0 = gimple_assign_rhs1 (def_stmt);
tree op1 = gimple_assign_rhs2 (def_stmt);
@@ -6747,19 +6751,95 @@ varying:
return SSA_PROP_VARYING;
}
+/* Returns operand1 of ssa-name with SSA_NAME as code, Otherwise it
+ returns NULL_TREE. */
+static tree
+ssa_name_get_inner_ssa_name_p (tree op)
+{
+ gimple stmt;
+
+ if (TREE_CODE (op) != SSA_NAME
+ || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
+ return NULL_TREE;
+ stmt = SSA_NAME_DEF_STMT (op);
+ if (gimple_assign_rhs_code (stmt) != SSA_NAME)
+ return NULL_TREE;
+ return gimple_assign_rhs1 (stmt);
+}
+
+/* Returns operand of cast operation, if OP is a type-conversion. Otherwise
+ return NULL_TREE. */
+static tree
+ssa_name_get_cast_to_p (tree op)
+{
+ gimple stmt;
+
+ if (TREE_CODE (op) != SSA_NAME
+ || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
+ return NULL_TREE;
+ stmt = SSA_NAME_DEF_STMT (op);
+ if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
+ return NULL_TREE;
+ return gimple_assign_rhs1 (stmt);
+}
+
/* Simplify boolean operations if the source is known
to be already a boolean. */
static bool
simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
{
enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+ gimple stmt2 = stmt;
tree val = NULL;
- tree op0, op1;
+ tree op0, op1, cop0, cop1;
value_range_t *vr;
bool sop = false;
bool need_conversion;
+ location_t loc = gimple_location (stmt);
op0 = gimple_assign_rhs1 (stmt);
+ op1 = NULL_TREE;
+
+ /* Handle cases with prefixed type-cast. */
+ if (CONVERT_EXPR_CODE_P (rhs_code)
+ && INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ && TREE_CODE (op0) == SSA_NAME
+ && is_gimple_assign (SSA_NAME_DEF_STMT (op0))
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
+ {
+ stmt2 = SSA_NAME_DEF_STMT (op0);
+ op0 = gimple_assign_rhs1 (stmt2);
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)))
+ return false;
+ rhs_code = gimple_assign_rhs_code (stmt2);
+ if (rhs_code != BIT_NOT_EXPR
+ && rhs_code != TRUTH_NOT_EXPR
+ && rhs_code != BIT_AND_EXPR
+ && rhs_code != BIT_IOR_EXPR
+ && rhs_code != BIT_XOR_EXPR
+ && rhs_code != NE_EXPR && rhs_code != EQ_EXPR)
+ return false;
+ if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
+ || rhs_code == BIT_XOR_EXPR
+ || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
+ op1 = gimple_assign_rhs2 (stmt2);
+ if (gimple_has_location (stmt2))
+ loc = gimple_location (stmt2);
+ }
+ else if (CONVERT_EXPR_CODE_P (rhs_code))
+ return false;
+ else if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
+ || rhs_code == BIT_XOR_EXPR
+ || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
+ op1 = gimple_assign_rhs2 (stmt);
+
+ /* ~X is only equivalent of !X, if type-precision is one and X has
+ an integral type. */
+ if (rhs_code == BIT_NOT_EXPR
+ && (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ || TYPE_PRECISION (TREE_TYPE (op0)) != 1))
+ return false;
+
if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
{
if (TREE_CODE (op0) != SSA_NAME)
@@ -6775,22 +6855,100 @@ simplify_truth_ops_using_ranges (gimple_
return false;
}
- if (rhs_code == TRUTH_NOT_EXPR)
+ if (op1 && TREE_CODE (op1) != INTEGER_CST
+ && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
+ {
+ vr = get_value_range (op1);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+
+ need_conversion =
+ !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
+ TREE_TYPE (op0));
+
+ /* As comparisons X != 0 getting folded by prior pass to (bool) X,
+ but X == 0 might be not folded for none boolean type of X
+ to (bool) (X ^ 1).
+ So for bitwise-binary operations we have three cases to handle:
+ a) ((bool) X) op ((bool) Y)
+ b) ((bool) X) op (Y == 0) OR (X == 0) op ((bool) Y)
+ c) (X == 0) op (Y == 0)
+ The later two cases can't be handled for now, as vr tables
+ would need to be adjusted. */
+ if (need_conversion
+ && (rhs_code == BIT_XOR_EXPR
+ || rhs_code == BIT_AND_EXPR
+ || rhs_code == BIT_IOR_EXPR)
+ && TREE_CODE (op1) == SSA_NAME && TREE_CODE (op0) == SSA_NAME)
+ {
+ cop0 = ssa_name_get_cast_to_p (op0);
+ cop1 = ssa_name_get_cast_to_p (op1);
+ if (!cop0 || !cop1)
+ /* We would need an new statment for cases b and c, and we can't
+ due vr table, so bail out. */
+ return false;
+
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (cop0))
+ || !types_compatible_p (TREE_TYPE (cop0), TREE_TYPE (cop1)))
+ return false;
+ need_conversion =
+ !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
+ TREE_TYPE (cop0));
+ if (need_conversion)
+ return false;
+ op0 = cop0;
+ op1 = cop1;
+
+ /* We need to re-check if value ranges for new operands
+ for 1-bit precision/range. */
+ if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
+ {
+ if (TREE_CODE (op0) != SSA_NAME)
+ return false;
+ vr = get_value_range (op0);
+
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+
+ if (op1 && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
+ {
+ vr = get_value_range (op1);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+ }
+ else if (rhs_code == TRUTH_NOT_EXPR
+ || rhs_code == BIT_NOT_EXPR)
{
rhs_code = NE_EXPR;
op1 = build_int_cst (TREE_TYPE (op0), 1);
}
else
{
- op1 = gimple_assign_rhs2 (stmt);
-
/* Reduce number of cases to handle. */
if (is_gimple_min_invariant (op1))
{
/* Exclude anything that should have been already folded. */
if (rhs_code != EQ_EXPR
&& rhs_code != NE_EXPR
- && rhs_code != TRUTH_XOR_EXPR)
+ && rhs_code != BIT_XOR_EXPR)
return false;
if (!integer_zerop (op1)
@@ -6810,18 +6968,6 @@ simplify_truth_ops_using_ranges (gimple_
/* Punt on A == B as there is no BIT_XNOR_EXPR. */
if (rhs_code == EQ_EXPR)
return false;
-
- if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
- {
- vr = get_value_range (op1);
- val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
- if (!val || !integer_onep (val))
- return false;
-
- val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
- if (!val || !integer_onep (val))
- return false;
- }
}
}
@@ -6834,11 +6980,8 @@ simplify_truth_ops_using_ranges (gimple_
else
location = gimple_location (stmt);
- if (rhs_code == TRUTH_AND_EXPR || rhs_code == TRUTH_OR_EXPR)
- warning_at (location, OPT_Wstrict_overflow,
- _("assuming signed overflow does not occur when "
- "simplifying && or || to & or |"));
- else
+ if (rhs_code != BIT_AND_EXPR && rhs_code != BIT_IOR_EXPR
+ && rhs_code != BIT_XOR_EXPR)
warning_at (location, OPT_Wstrict_overflow,
_("assuming signed overflow does not occur when "
"simplifying ==, != or ! to identity or ^"));
@@ -6856,19 +6999,17 @@ simplify_truth_ops_using_ranges (gimple_
switch (rhs_code)
{
- case TRUTH_AND_EXPR:
- rhs_code = BIT_AND_EXPR;
- break;
- case TRUTH_OR_EXPR:
- rhs_code = BIT_IOR_EXPR;
+ case BIT_AND_EXPR:
+ case BIT_IOR_EXPR:
break;
- case TRUTH_XOR_EXPR:
+ case BIT_XOR_EXPR:
case NE_EXPR:
if (integer_zerop (op1))
{
gimple_assign_set_rhs_with_ops (gsi,
need_conversion ? NOP_EXPR : SSA_NAME,
op0, NULL);
+ gimple_set_location (stmt, loc);
update_stmt (gsi_stmt (*gsi));
return true;
}
@@ -6879,10 +7020,20 @@ simplify_truth_ops_using_ranges (gimple_
gcc_unreachable ();
}
+ /* We can't insert here new expression as otherwise
+ tracked vr tables getting out of bounds. */
if (need_conversion)
return false;
+ /* Reduce here SSA_NAME -> SSA_NAME. */
+ while ((cop0 = ssa_name_get_inner_ssa_name_p (op0)) != NULL_TREE)
+ op0 = cop0;
+
+ while ((cop1 = ssa_name_get_inner_ssa_name_p (op1)) != NULL_TREE)
+ op1 = cop1;
+
gimple_assign_set_rhs_with_ops (gsi, rhs_code, op0, op1);
+ gimple_set_location (stmt, loc);
update_stmt (gsi_stmt (*gsi));
return true;
}
@@ -7417,10 +7568,8 @@ simplify_stmt_using_ranges (gimple_stmt_
{
case EQ_EXPR:
case NE_EXPR:
+ case BIT_NOT_EXPR:
case TRUTH_NOT_EXPR:
- case TRUTH_AND_EXPR:
- case TRUTH_OR_EXPR:
- case TRUTH_XOR_EXPR:
/* Transform EQ_EXPR, NE_EXPR, TRUTH_NOT_EXPR into BIT_XOR_EXPR
or identity if the RHS is zero or one, and the LHS are known
to be boolean values. Transform all TRUTH_*_EXPR into
@@ -7452,13 +7601,21 @@ simplify_stmt_using_ranges (gimple_stmt_
if all the bits being cleared are already cleared or
all the bits being set are already set. */
if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
- return simplify_bit_ops_using_ranges (gsi, stmt);
+ {
+ if (simplify_truth_ops_using_ranges (gsi, stmt))
+ return true;
+ return simplify_bit_ops_using_ranges (gsi, stmt);
+ }
break;
CASE_CONVERT:
if (TREE_CODE (rhs1) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
- return simplify_conversion_using_ranges (stmt);
+ {
+ if (simplify_truth_ops_using_ranges (gsi, stmt))
+ return true;
+ return simplify_conversion_using_ranges (stmt);
+ }
break;
default:
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [patch tree-optimization]: [3 of 3]: Boolify compares & more
2011-07-15 7:59 ` Kai Tietz
@ 2011-07-19 12:24 ` Richard Guenther
0 siblings, 0 replies; 18+ messages in thread
From: Richard Guenther @ 2011-07-19 12:24 UTC (permalink / raw)
To: Kai Tietz; +Cc: GCC Patches
On Fri, Jul 15, 2011 at 9:42 AM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Hello,
>
> This patch removes from tree-vrp the use of TRUTH-bitwise expression codes. Also
> it merges the handling for boolean compatible and non-boolean typed
> bitwise-binary
> expressions.
> Additional it adds primitive checks for bitwise-not expression on
> boolean-compatible
> types.
> In substitute_and_fold the scan-direction of statements within a BB is
> controlled now
> by its do_dce flag. This provides better results in vrp-pass.
>
> ChangeLog gcc
>
> 2011-07-15 Kai Tietz <ktietz@redhat.com>
>
> * tree-ssa-propagate.c (substitute_and_fold): Use
> do_dce flag to deside, if BB's statements are scanned
> in last to first, or first to last order.
> * tree-vrp.c (extract_range_from_binary_expr):
> Remove TRUTH-binary checks. And unify bitwise-binary
> cases.
> (register_edge_assert_for_1): Add handling boolean-compatible
> typed BIT_IOR_EXPR and BIT_NOT_EXPR.
> (extract_range_from_unary_expr): Add support for 1-bit
> integral typed BIT_NOT_EXPR expression.
> (extract_range_from_assignment): Remove TRUTH-binary checks.
> Add handling for 1-bit integral typed BIT_NOT_EXPR expression.
> (build_assert_expr_for): Likewise.
> (register_edge_assert_for_1): Likewise.
> (simplify_stmt_using_ranges): Likewise.
> (ssa_name_get_inner_ssa_name_p): New helper function.
> (ssa_name_get_cast_to_p): New helper function.
> (simplify_truth_ops_using_ranges): Handle prefixed
> cast instruction for result. Remove TRUTH-binary checks.
> Add handling for 1-bit integral typed BIT_NOT_EXPR expression.
> and BIT_NOT_EXPR.
> Add handling for one bit
>
> ChangeLog gcc/testsuite
>
> 2011-07-15 Kai Tietz <ktietz@redhat.com>
>
> * gcc.dg/tree-ssa/vrp47.c: Test no longer needs
> dom dump.
>
> Bootstrapped and regression tested for all standard languages (plus
> Ada & Obj-C++) on x86_64-pc-linux-gnu. Ok for apply?
>
> Regards,
> Kai
>
> Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c
> ===================================================================
> --- gcc.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c 2011-07-13
> 12:57:46.869620200 +0200
> +++ gcc/gcc/testsuite/gcc.dg/tree-ssa/vrp47.c 2011-07-13
> 22:29:53.221967000 +0200
> @@ -4,7 +4,7 @@
> jumps when evaluating an && condition. VRP is not able to optimize
> this. */
> /* { dg-do compile { target { ! "mips*-*-* s390*-*-* avr-*-*
> mn10300-*-*" } } } */
> -/* { dg-options "-O2 -fdump-tree-vrp -fdump-tree-dom" } */
> +/* { dg-options "-O2 -fdump-tree-vrp" } */
> /* { dg-options "-O2 -fdump-tree-vrp -fdump-tree-dom -march=i586" {
> target { i?86-*-* && ilp32 } } } */
>
> int h(int x, int y)
> @@ -36,13 +36,10 @@ int f(int x)
> 0 or 1. */
> /* { dg-final { scan-tree-dump-times "\[xy\]\[^ \]* !=" 0 "vrp1" } } */
>
> -/* This one needs more copy propagation that only happens in dom1. */
> -/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "dom1" } } */
> -/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" { xfail
> *-*-* } } } */
> +/* { dg-final { scan-tree-dump-times "x\[^ \]* & y" 1 "vrp1" } } */
>
> /* These two are fully simplified by VRP. */
> /* { dg-final { scan-tree-dump-times "x\[^ \]* \[|\] y" 1 "vrp1" } } */
> /* { dg-final { scan-tree-dump-times "x\[^ \]* \\^ 1" 1 "vrp1" } } */
>
> /* { dg-final { cleanup-tree-dump "vrp\[0-9\]" } } */
> -/* { dg-final { cleanup-tree-dump "dom\[0-9\]" } } */
> Index: gcc/gcc/tree-ssa-propagate.c
> ===================================================================
> --- gcc.orig/gcc/tree-ssa-propagate.c 2011-07-13 12:57:46.870620200 +0200
> +++ gcc/gcc/tree-ssa-propagate.c 2011-07-13 22:29:53.253971100 +0200
> @@ -979,6 +979,9 @@ replace_phi_args_in (gimple phi, ssa_pro
>
> DO_DCE is true if trivially dead stmts can be removed.
>
> + If DO_DCE is true, the statements within a BB are walked from
> + last to first element. Otherwise we scan from first to last element.
> +
> Return TRUE when something changed. */
>
> bool
> @@ -1059,9 +1062,10 @@ substitute_and_fold (ssa_prop_get_value_
> for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
> replace_phi_args_in (gsi_stmt (i), get_value_fn);
>
> - /* Propagate known values into stmts. Do a backward walk to expose
> - more trivially deletable stmts. */
> - for (i = gsi_last_bb (bb); !gsi_end_p (i);)
> + /* Propagate known values into stmts. Do a backward walk if
> + do_dce is true. In some case it exposes
> + more trivially deletable stmts to walk backward. */
> + for (i = (do_dce ? gsi_last_bb (bb) : gsi_start_bb (bb));
> !gsi_end_p (i);)
> {
> bool did_replace;
> gimple stmt = gsi_stmt (i);
> @@ -1070,7 +1074,10 @@ substitute_and_fold (ssa_prop_get_value_
> gimple_stmt_iterator oldi;
>
> oldi = i;
> - gsi_prev (&i);
> + if (do_dce)
> + gsi_prev (&i);
> + else
> + gsi_next (&i);
>
> /* Ignore ASSERT_EXPRs. They are used by VRP to generate
> range information for names and they are discarded
The tree-ssa-propagate.c change is ok to apply separately.
> Index: gcc/gcc/tree-vrp.c
> ===================================================================
> --- gcc.orig/gcc/tree-vrp.c 2011-07-13 22:25:14.690598100 +0200
> +++ gcc/gcc/tree-vrp.c 2011-07-15 08:53:21.086266100 +0200
> @@ -2174,9 +2174,7 @@ extract_range_from_binary_expr (value_ra
> && code != MIN_EXPR
> && code != MAX_EXPR
> && code != BIT_AND_EXPR
> - && code != BIT_IOR_EXPR
> - && code != TRUTH_AND_EXPR
> - && code != TRUTH_OR_EXPR)
> + && code != BIT_IOR_EXPR)
> {
> /* We can still do constant propagation here. */
> tree const_op0 = op_with_constant_singleton_value_range (op0);
> @@ -2231,8 +2229,7 @@ extract_range_from_binary_expr (value_ra
> divisions. TODO, we may be able to derive anti-ranges in
> some cases. */
> if (code != BIT_AND_EXPR
> - && code != TRUTH_AND_EXPR
> - && code != TRUTH_OR_EXPR
> + && code != BIT_IOR_EXPR
> && code != TRUNC_DIV_EXPR
> && code != FLOOR_DIV_EXPR
> && code != CEIL_DIV_EXPR
> @@ -2291,6 +2288,8 @@ extract_range_from_binary_expr (value_ra
> else
> set_value_range_to_varying (vr);
> }
> + else if (code == BIT_IOR_EXPR)
> + set_value_range_to_varying (vr);
Again, how do we arrive with a BIT_IOR_EXPR with pointer type here?
We're not supposed to have that (well, in theory, nothing verifies that).
> else
> gcc_unreachable ();
>
> @@ -2299,55 +2298,7 @@ extract_range_from_binary_expr (value_ra
>
> /* For integer ranges, apply the operation to each end of the
> range and see what we end up with. */
> - if (code == TRUTH_AND_EXPR
> - || code == TRUTH_OR_EXPR)
> - {
> - /* If one of the operands is zero, we know that the whole
> - expression evaluates zero. */
> - if (code == TRUTH_AND_EXPR
> - && ((vr0.type == VR_RANGE
> - && integer_zerop (vr0.min)
> - && integer_zerop (vr0.max))
> - || (vr1.type == VR_RANGE
> - && integer_zerop (vr1.min)
> - && integer_zerop (vr1.max))))
> - {
> - type = VR_RANGE;
> - min = max = build_int_cst (expr_type, 0);
> - }
> - /* If one of the operands is one, we know that the whole
> - expression evaluates one. */
> - else if (code == TRUTH_OR_EXPR
> - && ((vr0.type == VR_RANGE
> - && integer_onep (vr0.min)
> - && integer_onep (vr0.max))
> - || (vr1.type == VR_RANGE
> - && integer_onep (vr1.min)
> - && integer_onep (vr1.max))))
> - {
> - type = VR_RANGE;
> - min = max = build_int_cst (expr_type, 1);
> - }
> - else if (vr0.type != VR_VARYING
> - && vr1.type != VR_VARYING
> - && vr0.type == vr1.type
> - && !symbolic_range_p (&vr0)
> - && !overflow_infinity_range_p (&vr0)
> - && !symbolic_range_p (&vr1)
> - && !overflow_infinity_range_p (&vr1))
> - {
> - /* Boolean expressions cannot be folded with int_const_binop. */
> - min = fold_binary (code, expr_type, vr0.min, vr1.min);
> - max = fold_binary (code, expr_type, vr0.max, vr1.max);
> - }
> - else
> - {
> - /* The result of a TRUTH_*_EXPR is always true or false. */
> - set_value_range_to_truthvalue (vr, expr_type);
> - return;
> - }
> - }
> - else if (code == PLUS_EXPR
> + if (code == PLUS_EXPR
> || code == MIN_EXPR
> || code == MAX_EXPR)
> {
> @@ -2682,71 +2633,125 @@ extract_range_from_binary_expr (value_ra
> double_int may_be_nonzero0, may_be_nonzero1;
> double_int must_be_nonzero0, must_be_nonzero1;
>
> - vr0_int_cst_singleton_p = range_int_cst_singleton_p (&vr0);
> - vr1_int_cst_singleton_p = range_int_cst_singleton_p (&vr1);
> - int_cst_range0 = zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0,
> - &must_be_nonzero0);
> - int_cst_range1 = zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1,
> - &must_be_nonzero1);
> -
> - type = VR_RANGE;
> - if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
> - min = max = int_const_binop (code, vr0.max, vr1.max);
> - else if (!int_cst_range0 && !int_cst_range1)
> + /* If one of the operands is zero, we know that the whole
> + expression evaluates zero. */
context diffs help ... now I have to wade through +- mess :/
> + if (code == BIT_AND_EXPR
> + && ((vr0.type == VR_RANGE
> + && integer_zerop (vr0.min)
> + && integer_zerop (vr0.max))
> + || (vr1.type == VR_RANGE
> + && integer_zerop (vr1.min)
> + && integer_zerop (vr1.max))))
if you wrap all this in
if (vr0_int_cst_singleton_p || vr1_int_cst_singleton_p)
it becomes much simpler.
> {
> - set_value_range_to_varying (vr);
> - return;
> + type = VR_RANGE;
> + min = max = build_int_cst (expr_type, 0);
this can also be handled better via improving the existing
if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
min = max = int_const_binop (code, vr0.max, vr1.max);
handling to include the 0 and all-1s cases for AND/IOR instead
of trying to move the TRUTH_* code here.
> }
> - else if (code == BIT_AND_EXPR)
> + /* If one of the operands has all bits set to one, we know
> + that the whole expression evaluates to this one. */
> + else if (code == BIT_IOR_EXPR
> + && (vr0.type == VR_RANGE
> + && integer_all_onesp (vr0.min)
> + && integer_all_onesp (vr0.max)))
> {
> - min = double_int_to_tree (expr_type,
> - double_int_and (must_be_nonzero0,
> - must_be_nonzero1));
> - max = double_int_to_tree (expr_type,
> - double_int_and (may_be_nonzero0,
> - may_be_nonzero1));
> - if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
> - min = NULL_TREE;
> - if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
> - max = NULL_TREE;
> - if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
> - {
> - if (min == NULL_TREE)
> - min = build_int_cst (expr_type, 0);
> - if (max == NULL_TREE || tree_int_cst_lt (vr0.max, max))
> - max = vr0.max;
> + type = VR_RANGE;
> + min = max = fold_convert (expr_type, vr0.min);
> + }
> + else if (code == BIT_IOR_EXPR
> + && (vr1.type == VR_RANGE
> + && integer_all_onesp (vr1.min)
> + && integer_all_onesp (vr1.max)))
> + {
> + type = VR_RANGE;
> + min = max = fold_convert (expr_type, vr1.min);
> + }
> + else if (TYPE_PRECISION (TREE_TYPE (op1)) == 1)
> + {
> + if (vr0.type != VR_VARYING
> + && vr1.type != VR_VARYING
> + && vr0.type == vr1.type
> + && !symbolic_range_p (&vr0)
> + && !overflow_infinity_range_p (&vr0)
> + && !symbolic_range_p (&vr1)
> + && !overflow_infinity_range_p (&vr1))
> + {
> + /* Boolean expressions cannot be folded with int_const_binop. */
> + min = fold_binary (code, expr_type, vr0.min, vr1.min);
> + max = fold_binary (code, expr_type, vr0.max, vr1.max);
> }
> - if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
> + else
> {
> - if (min == NULL_TREE)
> - min = build_int_cst (expr_type, 0);
> - if (max == NULL_TREE || tree_int_cst_lt (vr1.max, max))
> - max = vr1.max;
> + set_value_range_to_varying (vr);
> + return;
> }
> }
> - else if (!int_cst_range0
> - || !int_cst_range1
> - || tree_int_cst_sgn (vr0.min) < 0
> - || tree_int_cst_sgn (vr1.min) < 0)
> - {
> - set_value_range_to_varying (vr);
> - return;
> - }
> else
> - {
> - min = double_int_to_tree (expr_type,
> - double_int_ior (must_be_nonzero0,
> - must_be_nonzero1));
> - max = double_int_to_tree (expr_type,
> - double_int_ior (may_be_nonzero0,
> - may_be_nonzero1));
> - if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
> - min = vr0.min;
> + {
> + vr0_int_cst_singleton_p = range_int_cst_singleton_p (&vr0);
> + vr1_int_cst_singleton_p = range_int_cst_singleton_p (&vr1);
> + int_cst_range0 = zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0,
> + &must_be_nonzero0);
> + int_cst_range1 = zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1,
> + &must_be_nonzero1);
> +
> + type = VR_RANGE;
> + if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
> + min = max = int_const_binop (code, vr0.max, vr1.max);
> + else if (!int_cst_range0 && !int_cst_range1)
> + {
> + set_value_range_to_varying (vr);
> + return;
> + }
> + else if (code == BIT_AND_EXPR)
> + {
> + min = double_int_to_tree (expr_type,
> + double_int_and (must_be_nonzero0,
> + must_be_nonzero1));
> + max = double_int_to_tree (expr_type,
> + double_int_and (may_be_nonzero0,
> + may_be_nonzero1));
> + if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
> + min = NULL_TREE;
> + if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
> + max = NULL_TREE;
> + if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
> + {
> + if (min == NULL_TREE)
> + min = build_int_cst (expr_type, 0);
> + if (max == NULL_TREE || tree_int_cst_lt (vr0.max, max))
> + max = vr0.max;
> + }
> + if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
> + {
> + if (min == NULL_TREE)
> + min = build_int_cst (expr_type, 0);
> + if (max == NULL_TREE || tree_int_cst_lt (vr1.max, max))
> + max = vr1.max;
> + }
> + }
> + else if (!int_cst_range0
> + || !int_cst_range1
> + || tree_int_cst_sgn (vr0.min) < 0
> + || tree_int_cst_sgn (vr1.min) < 0)
> + {
> + set_value_range_to_varying (vr);
> + return;
> + }
> else
> - min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
> - if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
> - max = NULL_TREE;
> - min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
> + {
> + min = double_int_to_tree (expr_type,
> + double_int_ior (must_be_nonzero0,
> + must_be_nonzero1));
> + max = double_int_to_tree (expr_type,
> + double_int_ior (may_be_nonzero0,
> + may_be_nonzero1));
> + if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
> + min = vr0.min;
> + else
> + min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
> + if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
> + max = NULL_TREE;
> + min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
> + }
> }
> }
> else
> @@ -2809,7 +2814,7 @@ extract_range_from_unary_expr (value_ran
> cannot easily determine a resulting range. */
> if (code == FIX_TRUNC_EXPR
> || code == FLOAT_EXPR
> - || code == BIT_NOT_EXPR
> + || (code == BIT_NOT_EXPR && TYPE_PRECISION (type) != 1)
Huh? That doesn't look worthwhile. Please instead provide true support
for BIT_NOT_EXPR, as a separate patch.
> || code == CONJ_EXPR)
> {
> /* We can still do constant propagation here. */
> @@ -3303,10 +3308,7 @@ extract_range_from_assignment (value_ran
> extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
> else if (code == SSA_NAME)
> extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
> - else if (TREE_CODE_CLASS (code) == tcc_binary
> - || code == TRUTH_AND_EXPR
> - || code == TRUTH_OR_EXPR
> - || code == TRUTH_XOR_EXPR)
> + else if (TREE_CODE_CLASS (code) == tcc_binary)
> extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt),
> gimple_expr_type (stmt),
> gimple_assign_rhs1 (stmt),
> @@ -3976,7 +3978,9 @@ build_assert_expr_for (tree cond, tree v
> tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
> assertion = gimple_build_assign (n, a);
> }
> - else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
> + else if (TREE_CODE (cond) == TRUTH_NOT_EXPR
> + || (TREE_CODE (cond) == BIT_NOT_EXPR
> + && TYPE_PRECISION (TREE_TYPE (cond)) == 1))
I dont' think we arrive with TRUTH_NOT_EXPR here either - look at the
single caller please.
> {
> /* Given !V, build the assignment N = false. */
> tree op0 = TREE_OPERAND (cond, 0);
> @@ -4519,11 +4523,9 @@ register_edge_assert_for_1 (tree op, enu
> invert);
> }
> else if ((code == NE_EXPR
> - && (gimple_assign_rhs_code (op_def) == TRUTH_AND_EXPR
> - || gimple_assign_rhs_code (op_def) == BIT_AND_EXPR))
> + && gimple_assign_rhs_code (op_def) == BIT_AND_EXPR)
> || (code == EQ_EXPR
> - && (gimple_assign_rhs_code (op_def) == TRUTH_OR_EXPR
> - || gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR)))
> + && gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR))
> {
> /* Recurse on each operand. */
> retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
> @@ -4531,7 +4533,9 @@ register_edge_assert_for_1 (tree op, enu
> retval |= register_edge_assert_for_1 (gimple_assign_rhs2 (op_def),
> code, e, bsi);
> }
> - else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR)
> + else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR
> + || (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
> + && TYPE_PRECISION (TREE_TYPE (op)) == 1))
Now without the TRUTH_NOT_EXPR handling. Also elsewhere I guess.
> {
> /* Recurse, flipping CODE. */
> code = invert_tree_comparison (code, false);
> @@ -4588,8 +4592,8 @@ register_edge_assert_for (tree name, edg
> the value zero or one, then we may be able to assert values
> for SSA_NAMEs which flow into COND. */
>
> - /* In the case of NAME == 1 or NAME != 0, for TRUTH_AND_EXPR defining
> - statement of NAME we can assert both operands of the TRUTH_AND_EXPR
> + /* In the case of NAME == 1 or NAME != 0, for BIT_AND_EXPR defining
> + statement of NAME we can assert both operands of the BIT_AND_EXPR
> have nonzero value. */
> if (((comp_code == EQ_EXPR && integer_onep (val))
> || (comp_code == NE_EXPR && integer_zerop (val))))
> @@ -4597,8 +4601,7 @@ register_edge_assert_for (tree name, edg
> gimple def_stmt = SSA_NAME_DEF_STMT (name);
>
> if (is_gimple_assign (def_stmt)
> - && (gimple_assign_rhs_code (def_stmt) == TRUTH_AND_EXPR
> - || gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR))
> + && gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR)
> {
> tree op0 = gimple_assign_rhs1 (def_stmt);
> tree op1 = gimple_assign_rhs2 (def_stmt);
> @@ -4607,8 +4610,8 @@ register_edge_assert_for (tree name, edg
> }
> }
>
> - /* In the case of NAME == 0 or NAME != 1, for TRUTH_OR_EXPR defining
> - statement of NAME we can assert both operands of the TRUTH_OR_EXPR
> + /* In the case of NAME == 0 or NAME != 1, for BIT_IOR_EXPR defining
> + statement of NAME we can assert both operands of the BIT_IOR_EXPR
> have zero value. */
> if (((comp_code == EQ_EXPR && integer_zerop (val))
> || (comp_code == NE_EXPR && integer_onep (val))))
> @@ -4616,11 +4619,12 @@ register_edge_assert_for (tree name, edg
> gimple def_stmt = SSA_NAME_DEF_STMT (name);
>
> if (is_gimple_assign (def_stmt)
> - && (gimple_assign_rhs_code (def_stmt) == TRUTH_OR_EXPR
> + && ((gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR
> + && TYPE_PRECISION (TREE_TYPE (name)) == 1)
> /* For BIT_IOR_EXPR only if NAME == 0 both operands have
> necessarily zero value. */
The comment needs updating and the condition wants to be re-structured.
> || (comp_code == EQ_EXPR
> - && (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR))))
> + && gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)))
> {
> tree op0 = gimple_assign_rhs1 (def_stmt);
> tree op1 = gimple_assign_rhs2 (def_stmt);
> @@ -6747,19 +6751,95 @@ varying:
> return SSA_PROP_VARYING;
> }
>
> +/* Returns operand1 of ssa-name with SSA_NAME as code, Otherwise it
> + returns NULL_TREE. */
> +static tree
> +ssa_name_get_inner_ssa_name_p (tree op)
> +{
> + gimple stmt;
> +
> + if (TREE_CODE (op) != SSA_NAME
> + || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
> + return NULL_TREE;
> + stmt = SSA_NAME_DEF_STMT (op);
> + if (gimple_assign_rhs_code (stmt) != SSA_NAME)
> + return NULL_TREE;
> + return gimple_assign_rhs1 (stmt);
> +}
This and the following should be all a separate patch. Please.
> +/* Returns operand of cast operation, if OP is a type-conversion. Otherwise
> + return NULL_TREE. */
> +static tree
> +ssa_name_get_cast_to_p (tree op)
> +{
> + gimple stmt;
> +
> + if (TREE_CODE (op) != SSA_NAME
> + || !is_gimple_assign (SSA_NAME_DEF_STMT (op)))
> + return NULL_TREE;
> + stmt = SSA_NAME_DEF_STMT (op);
> + if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
> + return NULL_TREE;
> + return gimple_assign_rhs1 (stmt);
> +}
> +
> /* Simplify boolean operations if the source is known
> to be already a boolean. */
> static bool
> simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
> {
> enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
> + gimple stmt2 = stmt;
> tree val = NULL;
> - tree op0, op1;
> + tree op0, op1, cop0, cop1;
> value_range_t *vr;
> bool sop = false;
> bool need_conversion;
> + location_t loc = gimple_location (stmt);
>
> op0 = gimple_assign_rhs1 (stmt);
> + op1 = NULL_TREE;
> +
> + /* Handle cases with prefixed type-cast. */
What's a 'prefixed type-cast'?
Isn't most of simplify_truth(!)_ops_using_ranges obsolete now?
> + if (CONVERT_EXPR_CODE_P (rhs_code)
> + && INTEGRAL_TYPE_P (TREE_TYPE (op0))
> + && TREE_CODE (op0) == SSA_NAME
> + && is_gimple_assign (SSA_NAME_DEF_STMT (op0))
> + && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
> + {
> + stmt2 = SSA_NAME_DEF_STMT (op0);
> + op0 = gimple_assign_rhs1 (stmt2);
> + if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)))
> + return false;
> + rhs_code = gimple_assign_rhs_code (stmt2);
> + if (rhs_code != BIT_NOT_EXPR
> + && rhs_code != TRUTH_NOT_EXPR
> + && rhs_code != BIT_AND_EXPR
> + && rhs_code != BIT_IOR_EXPR
> + && rhs_code != BIT_XOR_EXPR
> + && rhs_code != NE_EXPR && rhs_code != EQ_EXPR)
> + return false;
> + if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
> + || rhs_code == BIT_XOR_EXPR
> + || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
> + op1 = gimple_assign_rhs2 (stmt2);
> + if (gimple_has_location (stmt2))
> + loc = gimple_location (stmt2);
> + }
> + else if (CONVERT_EXPR_CODE_P (rhs_code))
> + return false;
> + else if (rhs_code == BIT_AND_EXPR || rhs_code == BIT_IOR_EXPR
> + || rhs_code == BIT_XOR_EXPR
> + || rhs_code == NE_EXPR || rhs_code == EQ_EXPR)
> + op1 = gimple_assign_rhs2 (stmt);
> +
> + /* ~X is only equivalent of !X, if type-precision is one and X has
> + an integral type. */
> + if (rhs_code == BIT_NOT_EXPR
> + && (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
> + || TYPE_PRECISION (TREE_TYPE (op0)) != 1))
> + return false;
> +
> if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
> {
> if (TREE_CODE (op0) != SSA_NAME)
> @@ -6775,22 +6855,100 @@ simplify_truth_ops_using_ranges (gimple_
> return false;
> }
>
> - if (rhs_code == TRUTH_NOT_EXPR)
> + if (op1 && TREE_CODE (op1) != INTEGER_CST
> + && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
> + {
> + vr = get_value_range (op1);
> + val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> +
> + val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> + }
> +
> + need_conversion =
> + !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
> + TREE_TYPE (op0));
> +
> + /* As comparisons X != 0 getting folded by prior pass to (bool) X,
> + but X == 0 might be not folded for none boolean type of X
> + to (bool) (X ^ 1).
> + So for bitwise-binary operations we have three cases to handle:
> + a) ((bool) X) op ((bool) Y)
> + b) ((bool) X) op (Y == 0) OR (X == 0) op ((bool) Y)
> + c) (X == 0) op (Y == 0)
> + The later two cases can't be handled for now, as vr tables
> + would need to be adjusted. */
> + if (need_conversion
> + && (rhs_code == BIT_XOR_EXPR
> + || rhs_code == BIT_AND_EXPR
> + || rhs_code == BIT_IOR_EXPR)
> + && TREE_CODE (op1) == SSA_NAME && TREE_CODE (op0) == SSA_NAME)
> + {
> + cop0 = ssa_name_get_cast_to_p (op0);
> + cop1 = ssa_name_get_cast_to_p (op1);
> + if (!cop0 || !cop1)
> + /* We would need an new statment for cases b and c, and we can't
> + due vr table, so bail out. */
> + return false;
> +
> + if (!INTEGRAL_TYPE_P (TREE_TYPE (cop0))
> + || !types_compatible_p (TREE_TYPE (cop0), TREE_TYPE (cop1)))
> + return false;
> + need_conversion =
> + !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
> + TREE_TYPE (cop0));
> + if (need_conversion)
> + return false;
> + op0 = cop0;
> + op1 = cop1;
> +
> + /* We need to re-check if value ranges for new operands
> + for 1-bit precision/range. */
> + if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
> + {
> + if (TREE_CODE (op0) != SSA_NAME)
> + return false;
> + vr = get_value_range (op0);
> +
> + val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> +
> + val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> + }
> +
> + if (op1 && TYPE_PRECISION (TREE_TYPE (op1)) != 1)
> + {
> + vr = get_value_range (op1);
> + val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> +
> + val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> + if (!val || !integer_onep (val))
> + return false;
> + }
> + }
> + else if (rhs_code == TRUTH_NOT_EXPR
> + || rhs_code == BIT_NOT_EXPR)
> {
> rhs_code = NE_EXPR;
> op1 = build_int_cst (TREE_TYPE (op0), 1);
> }
> else
> {
> - op1 = gimple_assign_rhs2 (stmt);
> -
> /* Reduce number of cases to handle. */
> if (is_gimple_min_invariant (op1))
> {
> /* Exclude anything that should have been already folded. */
> if (rhs_code != EQ_EXPR
> && rhs_code != NE_EXPR
> - && rhs_code != TRUTH_XOR_EXPR)
> + && rhs_code != BIT_XOR_EXPR)
> return false;
>
> if (!integer_zerop (op1)
> @@ -6810,18 +6968,6 @@ simplify_truth_ops_using_ranges (gimple_
> /* Punt on A == B as there is no BIT_XNOR_EXPR. */
> if (rhs_code == EQ_EXPR)
> return false;
> -
> - if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
> - {
> - vr = get_value_range (op1);
> - val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> - if (!val || !integer_onep (val))
> - return false;
> -
> - val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> - if (!val || !integer_onep (val))
> - return false;
> - }
> }
> }
>
> @@ -6834,11 +6980,8 @@ simplify_truth_ops_using_ranges (gimple_
> else
> location = gimple_location (stmt);
>
> - if (rhs_code == TRUTH_AND_EXPR || rhs_code == TRUTH_OR_EXPR)
> - warning_at (location, OPT_Wstrict_overflow,
> - _("assuming signed overflow does not occur when "
> - "simplifying && or || to & or |"));
> - else
> + if (rhs_code != BIT_AND_EXPR && rhs_code != BIT_IOR_EXPR
> + && rhs_code != BIT_XOR_EXPR)
> warning_at (location, OPT_Wstrict_overflow,
> _("assuming signed overflow does not occur when "
> "simplifying ==, != or ! to identity or ^"));
> @@ -6856,19 +6999,17 @@ simplify_truth_ops_using_ranges (gimple_
>
> switch (rhs_code)
> {
> - case TRUTH_AND_EXPR:
> - rhs_code = BIT_AND_EXPR;
> - break;
> - case TRUTH_OR_EXPR:
> - rhs_code = BIT_IOR_EXPR;
> + case BIT_AND_EXPR:
> + case BIT_IOR_EXPR:
> break;
> - case TRUTH_XOR_EXPR:
> + case BIT_XOR_EXPR:
> case NE_EXPR:
> if (integer_zerop (op1))
> {
> gimple_assign_set_rhs_with_ops (gsi,
> need_conversion ? NOP_EXPR : SSA_NAME,
> op0, NULL);
> + gimple_set_location (stmt, loc);
> update_stmt (gsi_stmt (*gsi));
> return true;
> }
> @@ -6879,10 +7020,20 @@ simplify_truth_ops_using_ranges (gimple_
> gcc_unreachable ();
> }
>
> + /* We can't insert here new expression as otherwise
> + tracked vr tables getting out of bounds. */
> if (need_conversion)
> return false;
>
> + /* Reduce here SSA_NAME -> SSA_NAME. */
> + while ((cop0 = ssa_name_get_inner_ssa_name_p (op0)) != NULL_TREE)
> + op0 = cop0;
> +
> + while ((cop1 = ssa_name_get_inner_ssa_name_p (op1)) != NULL_TREE)
> + op1 = cop1;
> +
??
> gimple_assign_set_rhs_with_ops (gsi, rhs_code, op0, op1);
> + gimple_set_location (stmt, loc);
> update_stmt (gsi_stmt (*gsi));
> return true;
Well, at least previously the function was readable and now it looks
like spaghetti.
> }
> @@ -7417,10 +7568,8 @@ simplify_stmt_using_ranges (gimple_stmt_
> {
> case EQ_EXPR:
> case NE_EXPR:
> + case BIT_NOT_EXPR:
> case TRUTH_NOT_EXPR:
> - case TRUTH_AND_EXPR:
> - case TRUTH_OR_EXPR:
> - case TRUTH_XOR_EXPR:
> /* Transform EQ_EXPR, NE_EXPR, TRUTH_NOT_EXPR into BIT_XOR_EXPR
> or identity if the RHS is zero or one, and the LHS are known
> to be boolean values. Transform all TRUTH_*_EXPR into
> @@ -7452,13 +7601,21 @@ simplify_stmt_using_ranges (gimple_stmt_
> if all the bits being cleared are already cleared or
> all the bits being set are already set. */
> if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
> - return simplify_bit_ops_using_ranges (gsi, stmt);
> + {
> + if (simplify_truth_ops_using_ranges (gsi, stmt))
> + return true;
> + return simplify_bit_ops_using_ranges (gsi, stmt);
> + }
> break;
>
> CASE_CONVERT:
> if (TREE_CODE (rhs1) == SSA_NAME
> && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
> - return simplify_conversion_using_ranges (stmt);
> + {
> + if (simplify_truth_ops_using_ranges (gsi, stmt))
> + return true;
> + return simplify_conversion_using_ranges (stmt);
> + }
> break;
>
> default:
>
^ permalink raw reply [flat|nested] 18+ messages in thread
end of thread, other threads:[~2011-07-19 12:08 UTC | newest]
Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-07-07 16:14 [patch tree-optimization]: [3 of 3]: Boolify compares & more Kai Tietz
2011-07-07 16:19 ` Paolo Bonzini
2011-07-07 16:28 ` Kai Tietz
2011-07-08 9:45 ` Richard Guenther
2011-07-08 10:59 ` Kai Tietz
2011-07-08 11:08 ` Kai Tietz
2011-07-08 14:40 ` Kai Tietz
2011-07-08 14:57 ` Richard Guenther
2011-07-08 15:05 ` Kai Tietz
2011-07-08 9:39 ` Richard Guenther
2011-07-08 15:49 ` Kai Tietz
2011-07-08 16:31 ` Kai Tietz
2011-07-08 16:45 ` Michael Matz
2011-07-08 17:26 ` Kai Tietz
2011-07-12 17:18 ` Kai Tietz
2011-07-13 11:06 ` Richard Guenther
2011-07-15 7:59 ` Kai Tietz
2011-07-19 12:24 ` Richard Guenther
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).