Re: [patch] Fix wrong code for boolean negation in condition at -O
> Umm, did you look at ssa_name_has_boolean_range? Isn't the problem that > Ada's BOOLEAN_TYPE has a wider range than [0..1] and thus this is the > wrong bit of code: > > /* Boolean types always have a range [0..1]. */ > if (TREE_CODE (TREE_TYPE (op)) == BOOLEAN_TYPE) > return true; You seem to be discovering that boolean types can have a precision > 1; that's the case in Ada and Fortran. They are indeed a bit delicate to handle but the invariant is that the 0-or-1 value must be preserved for them too, i.e. you cannot create another value out of thin air. > IIRC there are other places that have similar logic and rely on > ssa_name_has_boolean_range to filter out anything undesirable. The other places are more careful, i.e. they explicitly test for 0 or 1. -- Eric Botcazou
Re: [patch] Fix wrong code for boolean negation in condition at -O
On 2/25/19 2:07 AM, Eric Botcazou wrote:
> Hi,
>
> this is a regression present on the mainline and 8 branch, introduced by the
> new code in edge_info::derive_equivalences dealing with BIT_AND_EXPR for SSA
> names with boolean range:
>
> /* If either operand has a boolean range, then we
>know its value must be one, otherwise we just know it
>is nonzero. The former is clearly useful, I haven't
>seen cases where the latter is helpful yet. */
> if (TREE_CODE (rhs1) == SSA_NAME)
> {
> if (ssa_name_has_boolean_range (rhs1))
> {
> value = build_one_cst (TREE_TYPE (rhs1));
> derive_equivalences (rhs1, value, recursion_limit - 1);
> }
> }
> if (TREE_CODE (rhs2) == SSA_NAME)
> {
> if (ssa_name_has_boolean_range (rhs2))
> {
> value = build_one_cst (TREE_TYPE (rhs2));
> derive_equivalences (rhs2, value, recursion_limit - 1);
> }
> }
>
> and visible on the attached Ada testcase at -O1 or above.
>
> The sequence of events is as follows: for boolean types with precision > 1
> (the normal boolean types in Ada), the gimplifier turns a TRUTH_NOT_EXPR into
> a BIT_XOR_EXPR with 1 in order to preserve the 0-or-1-value invariant:
>
> /* The parsers are careful to generate TRUTH_NOT_EXPR
> only with operands that are always zero or one.
> We do not fold here but handle the only interesting case
> manually, as fold may re-introduce the TRUTH_NOT_EXPR. */
> *expr_p = gimple_boolify (*expr_p);
> if (TYPE_PRECISION (TREE_TYPE (*expr_p)) == 1)
> *expr_p = build1_loc (input_location, BIT_NOT_EXPR,
> TREE_TYPE (*expr_p),
> TREE_OPERAND (*expr_p, 0));
> else
> *expr_p = build2_loc (input_location, BIT_XOR_EXPR,
> TREE_TYPE (*expr_p),
> TREE_OPERAND (*expr_p, 0),
> build_int_cst (TREE_TYPE (*expr_p), 1));
>
> Now this TRUTH_NOT_EXPR is part of a conjunction which has been turned into a
> BIT_AND_EXPR by the folder, so this gives BIT_AND_EXPR >.
>
> After some optimization passes, the second operand of the BIT_AND_EXPR is
> also
> folded into 1 and, consequently, the following match.pd pattern kicks in:
>
> /* Fold (X & Y) ^ Y and (X ^ Y) & Y as ~X & Y. */
> (for opo (bit_and bit_xor)
> opi (bit_xor bit_and)
> (simplify
> (opo:c (opi:c @0 @1) @1)
> (bit_and (bit_not @0) @1)))
>
> and yields BIT_AND_EXPR . This is still correct, in the
> sense that the 0-or-1-value invariant is preserved.
>
> Then the new code in edge_info::derive_equivalences above deduces from this
> that the BIT_NOT_EXPR has value 1 on one of the edges. But the same function
> also handles the BIT_NOT_EXPR itself and further deduces that its operand has
> value ~1 or 254 (the precision of boolean types is 8) on this edge, which
> breaks the 0-or-1-value invariant and leads to wrong code downstream.
>
> Given the new code for BIT_AND_EXPR in edge_info::derive_equivalences for
> boolean types, I think that the same special treatment must be added for
> boolean types in the BIT_NOT_EXPR case to preserve the 0-or-1-value invariant.
>
> Bootstrapped/regtested on x86_64-suse-linux, OK for mainline and 8 branch?
>
>
> 2019-02-25 Eric Botcazou
>
> * tree-ssa-dom.c (edge_info::derive_equivalences) : Fix
> and move around comment.
> : Likewise.
> : Add specific handling for boolean types.
>
>
> 2019-02-25 Eric Botcazou
>
> * gnat.dg/opt77.adb: New test.
> * gnat.dg/opt77_pkg.ad[sb]: Likewise.
Umm, did you look at ssa_name_has_boolean_range? Isn't the problem that
Ada's BOOLEAN_TYPE has a wider range than [0..1] and thus this is the
wrong bit of code:
/* Boolean types always have a range [0..1]. */
if (TREE_CODE (TREE_TYPE (op)) == BOOLEAN_TYPE)
return true;
IIRC there are other places that have similar logic and rely on
ssa_name_has_boolean_range to filter out anything undesirable.
jeff
Re: [patch] Fix wrong code for boolean negation in condition at -O
> The BIT_AND_EXPR case is clearly correct for all possible values. The code > says that if the result of BIT_AND_EXPR is known to be a non-zero constant, > and one or both of the BIT_AND_EXPR arguments have known value ranges [0,1] > (or boolean or precision 1, not talking about those now), then that value > with the [0,1] range actually had to be 1, otherwise BIT_AND_EXPR result > would be 0. > > The BIT_NOT_EXPR case is different, ~0 is -1 and ~1 is -2. If an SSA_NAME > has [0,1] range, then BIT_NOT_EXPR of that will be [-2,-1]. If value is one > of those two, then with your today's patch the assumption will be correct, > 1 or 0. If value is some other one, which should hopefully happen only in > dead code that we haven't been able to optimize, then we'd replace > different values though. I don't understand the last sentence: we'll precisely replace a bogus value, which we know is impossible given the [0, 1] range, by 0 or 1. -- Eric Botcazou
Re: [patch] Fix wrong code for boolean negation in condition at -O
On Fri, Mar 01, 2019 at 12:19:36AM +0100, Eric Botcazou wrote: > > I know Eric has committed a tweak here, but I view this magic handling as > > something meant for boolean types only (if it is correct at all and the > > right fix wouldn't be avoid the BIT_NOT_EXPR for the prec > 1 booleans, I > > believe the expansion of BIT_NOT_EXPR doesn't have any special case for > > BOOLEAN_TYPE). This patch just restores previous behavior for non-boolean > > types (basically inlines the first two cases from ssa_name_has_boolean_range > > while leaving the problematic third one out, normal integral types with > > just known value range of [0,1]). > > IMO you haven't justified why this is problematic in the BIT_NOT_EXPR case > and > not in the BIT_AND_EXPR case... The BIT_AND_EXPR case is clearly correct for all possible values. The code says that if the result of BIT_AND_EXPR is known to be a non-zero constant, and one or both of the BIT_AND_EXPR arguments have known value ranges [0,1] (or boolean or precision 1, not talking about those now), then that value with the [0,1] range actually had to be 1, otherwise BIT_AND_EXPR result would be 0. The BIT_NOT_EXPR case is different, ~0 is -1 and ~1 is -2. If an SSA_NAME has [0,1] range, then BIT_NOT_EXPR of that will be [-2,-1]. If value is one of those two, then with your today's patch the assumption will be correct, 1 or 0. If value is some other one, which should hopefully happen only in dead code that we haven't been able to optimize, then we'd replace different values though. Jakub
Re: [patch] Fix wrong code for boolean negation in condition at -O
> I know Eric has committed a tweak here, but I view this magic handling as > something meant for boolean types only (if it is correct at all and the > right fix wouldn't be avoid the BIT_NOT_EXPR for the prec > 1 booleans, I > believe the expansion of BIT_NOT_EXPR doesn't have any special case for > BOOLEAN_TYPE). This patch just restores previous behavior for non-boolean > types (basically inlines the first two cases from ssa_name_has_boolean_range > while leaving the problematic third one out, normal integral types with > just known value range of [0,1]). IMO you haven't justified why this is problematic in the BIT_NOT_EXPR case and not in the BIT_AND_EXPR case... -- Eric Botcazou
Re: [patch] Fix wrong code for boolean negation in condition at -O
On Mon, Feb 25, 2019 at 10:07:10AM +0100, Eric Botcazou wrote:
> 2019-02-25 Eric Botcazou
>
> * tree-ssa-dom.c (edge_info::derive_equivalences) : Fix
> and move around comment.
> : Likewise.
> : Add specific handling for boolean types.
This broke the following testcase, as mentioned in the PR we have
expected value of the BIT_NOT_EXPR -2 and because that is not zero, the
code assumed that it must be zero, when it actually must be ~-2, i.e. 1.
I know Eric has committed a tweak here, but I view this magic handling as
something meant for boolean types only (if it is correct at all and the
right fix wouldn't be avoid the BIT_NOT_EXPR for the prec > 1 booleans, I
believe the expansion of BIT_NOT_EXPR doesn't have any special case for
BOOLEAN_TYPE). This patch just restores previous behavior for non-boolean
types (basically inlines the first two cases from ssa_name_has_boolean_range
while leaving the problematic third one out, normal integral types with just
known value range of [0,1]).
2019-02-28 Jakub Jelinek
PR tree-optimization/89536
* tree-ssa-dom.c (edge_info::derive_equivalences) :
Don't use ssa_name_has_boolean_range here, check only for boolean type
or unsigned integral type with precision 1.
* gcc.c-torture/execute/pr89536.c: New test.
--- gcc/tree-ssa-dom.c.jj 2019-02-26 14:13:08.296824100 +0100
+++ gcc/tree-ssa-dom.c 2019-02-28 15:52:08.737369799 +0100
@@ -346,7 +346,14 @@ edge_info::derive_equivalences (tree nam
boolean types with precision > 1. */
if (code == BIT_NOT_EXPR
&& TREE_CODE (rhs) == SSA_NAME
- && ssa_name_has_boolean_range (rhs))
+ /* Don't call ssa_name_has_boolean_range here, that returns
+ true for the following condition, but also when VRP
+ determines [0, 1] range on anything else. BIT_NOT_EXPR
+ of such numbers is [-2, -1] or [-2U, -1U] though. */
+ && (TREE_CODE (TREE_TYPE (rhs)) == BOOLEAN_TYPE
+ || (INTEGRAL_TYPE_P (TREE_TYPE (rhs))
+ && TYPE_UNSIGNED (TREE_TYPE (rhs))
+ && TYPE_PRECISION (TREE_TYPE (rhs)) == 1)))
{
if (integer_zerop (value))
res = build_one_cst (TREE_TYPE (rhs));
--- gcc/testsuite/gcc.c-torture/execute/pr89536.c.jj2019-02-28
15:53:37.792924793 +0100
+++ gcc/testsuite/gcc.c-torture/execute/pr89536.c 2019-02-28
15:53:08.357402412 +0100
@@ -0,0 +1,14 @@
+/* PR tree-optimization/89536 */
+
+int a = 1;
+
+int
+main ()
+{
+ a = ~(a && 1);
+ if (a < -1)
+a = ~a;
+ if (!a)
+__builtin_abort ();
+ return 0;
+}
Jakub
Re: [patch] Fix wrong code for boolean negation in condition at -O
> > Given the new code for BIT_AND_EXPR in edge_info::derive_equivalences for
> > boolean types, I think that the same special treatment must be added for
> > boolean types in the BIT_NOT_EXPR case to preserve the 0-or-1-value
> > invariant.
> >
> > Bootstrapped/regtested on x86_64-suse-linux, OK for mainline and 8 branch?
>
> OK.
Thanks. However, as reported under PR tree-opt/89536, there is an annoying
oversight in the reasoning: the predicate to be used is not integer_zerop but
whether bit #0 is 0 or 1. I have applied the attached fixlet as obviously
more correct than the current code, but Jakub has a different opinion on the
whole change so this will probably be revisited in the near future.
PR tree-optimization/89536
* tree-ssa-dom.c (edge_info::derive_equivalences) : Test
only whether bit #0 of the value is 0 instead of the entire value.
* gcc.c-torture/execute/20190228-1.c: New test.
--
Eric Botcazou/* PR tree-optimization/89536 */
/* Testcase by Zhendong Su */
int a = 1;
int main (void)
{
a = ~(a && 1);
if (a < -1)
a = ~a;
if (!a)
__builtin_abort ();
return 0;
}
Index: tree-ssa-dom.c
===
--- tree-ssa-dom.c (revision 269211)
+++ tree-ssa-dom.c (working copy)
@@ -348,7 +348,7 @@ edge_info::derive_equivalences (tree nam
&& TREE_CODE (rhs) == SSA_NAME
&& ssa_name_has_boolean_range (rhs))
{
- if (integer_zerop (value))
+ if ((TREE_INT_CST_LOW (value) & 1) == 0)
res = build_one_cst (TREE_TYPE (rhs));
else
res = build_zero_cst (TREE_TYPE (rhs));
Re: [patch] Fix wrong code for boolean negation in condition at -O
On Mon, Feb 25, 2019 at 10:09 AM Eric Botcazou wrote:
>
> Hi,
>
> this is a regression present on the mainline and 8 branch, introduced by the
> new code in edge_info::derive_equivalences dealing with BIT_AND_EXPR for SSA
> names with boolean range:
>
> /* If either operand has a boolean range, then we
> know its value must be one, otherwise we just know it
> is nonzero. The former is clearly useful, I haven't
> seen cases where the latter is helpful yet. */
> if (TREE_CODE (rhs1) == SSA_NAME)
> {
> if (ssa_name_has_boolean_range (rhs1))
> {
> value = build_one_cst (TREE_TYPE (rhs1));
> derive_equivalences (rhs1, value, recursion_limit - 1);
> }
> }
> if (TREE_CODE (rhs2) == SSA_NAME)
> {
> if (ssa_name_has_boolean_range (rhs2))
> {
> value = build_one_cst (TREE_TYPE (rhs2));
> derive_equivalences (rhs2, value, recursion_limit - 1);
> }
> }
>
> and visible on the attached Ada testcase at -O1 or above.
>
> The sequence of events is as follows: for boolean types with precision > 1
> (the normal boolean types in Ada), the gimplifier turns a TRUTH_NOT_EXPR into
> a BIT_XOR_EXPR with 1 in order to preserve the 0-or-1-value invariant:
>
> /* The parsers are careful to generate TRUTH_NOT_EXPR
>only with operands that are always zero or one.
>We do not fold here but handle the only interesting case
>manually, as fold may re-introduce the TRUTH_NOT_EXPR. */
> *expr_p = gimple_boolify (*expr_p);
> if (TYPE_PRECISION (TREE_TYPE (*expr_p)) == 1)
> *expr_p = build1_loc (input_location, BIT_NOT_EXPR,
> TREE_TYPE (*expr_p),
> TREE_OPERAND (*expr_p, 0));
> else
> *expr_p = build2_loc (input_location, BIT_XOR_EXPR,
> TREE_TYPE (*expr_p),
> TREE_OPERAND (*expr_p, 0),
> build_int_cst (TREE_TYPE (*expr_p), 1));
>
> Now this TRUTH_NOT_EXPR is part of a conjunction which has been turned into a
> BIT_AND_EXPR by the folder, so this gives BIT_AND_EXPR >.
>
> After some optimization passes, the second operand of the BIT_AND_EXPR is also
> folded into 1 and, consequently, the following match.pd pattern kicks in:
>
> /* Fold (X & Y) ^ Y and (X ^ Y) & Y as ~X & Y. */
> (for opo (bit_and bit_xor)
> opi (bit_xor bit_and)
> (simplify
> (opo:c (opi:c @0 @1) @1)
> (bit_and (bit_not @0) @1)))
>
> and yields BIT_AND_EXPR . This is still correct, in the
> sense that the 0-or-1-value invariant is preserved.
>
> Then the new code in edge_info::derive_equivalences above deduces from this
> that the BIT_NOT_EXPR has value 1 on one of the edges. But the same function
> also handles the BIT_NOT_EXPR itself and further deduces that its operand has
> value ~1 or 254 (the precision of boolean types is 8) on this edge, which
> breaks the 0-or-1-value invariant and leads to wrong code downstream.
>
> Given the new code for BIT_AND_EXPR in edge_info::derive_equivalences for
> boolean types, I think that the same special treatment must be added for
> boolean types in the BIT_NOT_EXPR case to preserve the 0-or-1-value invariant.
>
> Bootstrapped/regtested on x86_64-suse-linux, OK for mainline and 8 branch?
OK.
Richard.
>
> 2019-02-25 Eric Botcazou
>
> * tree-ssa-dom.c (edge_info::derive_equivalences) : Fix
> and move around comment.
> : Likewise.
> : Add specific handling for boolean types.
>
>
> 2019-02-25 Eric Botcazou
>
> * gnat.dg/opt77.adb: New test.
> * gnat.dg/opt77_pkg.ad[sb]: Likewise.
>
> --
> Eric Botcazou
[patch] Fix wrong code for boolean negation in condition at -O
Hi,
this is a regression present on the mainline and 8 branch, introduced by the
new code in edge_info::derive_equivalences dealing with BIT_AND_EXPR for SSA
names with boolean range:
/* If either operand has a boolean range, then we
know its value must be one, otherwise we just know it
is nonzero. The former is clearly useful, I haven't
seen cases where the latter is helpful yet. */
if (TREE_CODE (rhs1) == SSA_NAME)
{
if (ssa_name_has_boolean_range (rhs1))
{
value = build_one_cst (TREE_TYPE (rhs1));
derive_equivalences (rhs1, value, recursion_limit - 1);
}
}
if (TREE_CODE (rhs2) == SSA_NAME)
{
if (ssa_name_has_boolean_range (rhs2))
{
value = build_one_cst (TREE_TYPE (rhs2));
derive_equivalences (rhs2, value, recursion_limit - 1);
}
}
and visible on the attached Ada testcase at -O1 or above.
The sequence of events is as follows: for boolean types with precision > 1
(the normal boolean types in Ada), the gimplifier turns a TRUTH_NOT_EXPR into
a BIT_XOR_EXPR with 1 in order to preserve the 0-or-1-value invariant:
/* The parsers are careful to generate TRUTH_NOT_EXPR
only with operands that are always zero or one.
We do not fold here but handle the only interesting case
manually, as fold may re-introduce the TRUTH_NOT_EXPR. */
*expr_p = gimple_boolify (*expr_p);
if (TYPE_PRECISION (TREE_TYPE (*expr_p)) == 1)
*expr_p = build1_loc (input_location, BIT_NOT_EXPR,
TREE_TYPE (*expr_p),
TREE_OPERAND (*expr_p, 0));
else
*expr_p = build2_loc (input_location, BIT_XOR_EXPR,
TREE_TYPE (*expr_p),
TREE_OPERAND (*expr_p, 0),
build_int_cst (TREE_TYPE (*expr_p), 1));
Now this TRUTH_NOT_EXPR is part of a conjunction which has been turned into a
BIT_AND_EXPR by the folder, so this gives BIT_AND_EXPR >.
After some optimization passes, the second operand of the BIT_AND_EXPR is also
folded into 1 and, consequently, the following match.pd pattern kicks in:
/* Fold (X & Y) ^ Y and (X ^ Y) & Y as ~X & Y. */
(for opo (bit_and bit_xor)
opi (bit_xor bit_and)
(simplify
(opo:c (opi:c @0 @1) @1)
(bit_and (bit_not @0) @1)))
and yields BIT_AND_EXPR . This is still correct, in the
sense that the 0-or-1-value invariant is preserved.
Then the new code in edge_info::derive_equivalences above deduces from this
that the BIT_NOT_EXPR has value 1 on one of the edges. But the same function
also handles the BIT_NOT_EXPR itself and further deduces that its operand has
value ~1 or 254 (the precision of boolean types is 8) on this edge, which
breaks the 0-or-1-value invariant and leads to wrong code downstream.
Given the new code for BIT_AND_EXPR in edge_info::derive_equivalences for
boolean types, I think that the same special treatment must be added for
boolean types in the BIT_NOT_EXPR case to preserve the 0-or-1-value invariant.
Bootstrapped/regtested on x86_64-suse-linux, OK for mainline and 8 branch?
2019-02-25 Eric Botcazou
* tree-ssa-dom.c (edge_info::derive_equivalences) : Fix
and move around comment.
: Likewise.
: Add specific handling for boolean types.
2019-02-25 Eric Botcazou
* gnat.dg/opt77.adb: New test.
* gnat.dg/opt77_pkg.ad[sb]: Likewise.
--
Eric BotcazouIndex: tree-ssa-dom.c
===
--- tree-ssa-dom.c (revision 268994)
+++ tree-ssa-dom.c (working copy)
@@ -170,11 +170,10 @@ edge_info::derive_equivalences (tree nam
gimple *def_stmt = SSA_NAME_DEF_STMT (name);
if (is_gimple_assign (def_stmt))
{
- /* We know the result of DEF_STMT was zero. See if that allows
- us to deduce anything about the SSA_NAMEs used on the RHS. */
enum tree_code code = gimple_assign_rhs_code (def_stmt);
switch (code)
{
+ /* If the result of an OR is zero, then its operands are, too. */
case BIT_IOR_EXPR:
if (integer_zerop (value))
{
@@ -188,8 +187,7 @@ edge_info::derive_equivalences (tree nam
}
break;
- /* We know the result of DEF_STMT was one. See if that allows
- us to deduce anything about the SSA_NAMEs used on the RHS. */
+ /* If the result of an AND is nonzero, then its operands are, too. */
case BIT_AND_EXPR:
if (!integer_zerop (value))
{
@@ -296,7 +294,6 @@ edge_info::derive_equivalences (tree nam
break;
}
-
case EQ_EXPR:
case NE_EXPR:
{
@@
