| Message ID | 1939418.1pZo4JS8vg@polaris |
|---|---|
| State | New |
| Headers | show |
| Series | Fix wrong code for boolean negation in condition at -O | expand |
On Mon, Feb 25, 2019 at 10:09 AM Eric Botcazou <ebotcazou@adacore.com> 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 <BIT_XOR_EXPR <X, 1>>. > > 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 <BIT_NOT_EXPR, 1>. 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 <ebotcazou@adacore.com> > > * tree-ssa-dom.c (edge_info::derive_equivalences) <BIT_IOR_EXPR>: Fix > and move around comment. > <BIT_AND_EXPR>: Likewise. > <BIT_NOT_EXPR>: Add specific handling for boolean types. > > > 2019-02-25 Eric Botcazou <ebotcazou@adacore.com> > > * gnat.dg/opt77.adb: New test. > * gnat.dg/opt77_pkg.ad[sb]: Likewise. > > -- > Eric Botcazou
> > 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) <BIT_NOT_EXPR>: Test only whether bit #0 of the value is 0 instead of the entire value. * gcc.c-torture/execute/20190228-1.c: New test.
On Mon, Feb 25, 2019 at 10:07:10AM +0100, Eric Botcazou wrote: > 2019-02-25 Eric Botcazou <ebotcazou@adacore.com> > > * tree-ssa-dom.c (edge_info::derive_equivalences) <BIT_IOR_EXPR>: Fix > and move around comment. > <BIT_AND_EXPR>: Likewise. > <BIT_NOT_EXPR>: 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 <jakub@redhat.com> PR tree-optimization/89536 * tree-ssa-dom.c (edge_info::derive_equivalences) <case BIT_NOT_EXPR>: 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.jj 2019-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
> 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...
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
> 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.
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 <BIT_XOR_EXPR <X, 1>>. > > 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 <BIT_NOT_EXPR, 1>. 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 <ebotcazou@adacore.com> > > * tree-ssa-dom.c (edge_info::derive_equivalences) <BIT_IOR_EXPR>: Fix > and move around comment. > <BIT_AND_EXPR>: Likewise. > <BIT_NOT_EXPR>: Add specific handling for boolean types. > > > 2019-02-25 Eric Botcazou <ebotcazou@adacore.com> > > * 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
> 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.
Index: 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: { @@ -336,7 +333,28 @@ edge_info::derive_equivalences (tree nam case NEGATE_EXPR: { tree rhs = gimple_assign_rhs1 (def_stmt); - tree res = fold_build1 (code, TREE_TYPE (rhs), value); + tree res; + /* If this is a NOT and the operand has a boolean range, then we + know its value must be zero or one. We are not supposed to + have a BIT_NOT_EXPR for boolean types with precision > 1 in + the general case, see e.g. the handling of TRUTH_NOT_EXPR in + the gimplifier, but it can be generated by match.pd out of + a BIT_XOR_EXPR wrapped in a BIT_AND_EXPR. Now the handling + of BIT_AND_EXPR above already forces a specific semantics for + boolean types with precision > 1 so we must do the same here, + otherwise we could change the semantics of TRUTH_NOT_EXPR for + boolean types with precision > 1. */ + if (code == BIT_NOT_EXPR + && TREE_CODE (rhs) == SSA_NAME + && ssa_name_has_boolean_range (rhs)) + { + if (integer_zerop (value)) + res = build_one_cst (TREE_TYPE (rhs)); + else + res = build_zero_cst (TREE_TYPE (rhs)); + } + else + res = fold_build1 (code, TREE_TYPE (rhs), value); derive_equivalences (rhs, res, recursion_limit - 1); break; }
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 <BIT_XOR_EXPR <X, 1>>. 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 <BIT_NOT_EXPR, 1>. 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 <ebotcazou@adacore.com> * tree-ssa-dom.c (edge_info::derive_equivalences) <BIT_IOR_EXPR>: Fix and move around comment. <BIT_AND_EXPR>: Likewise. <BIT_NOT_EXPR>: Add specific handling for boolean types. 2019-02-25 Eric Botcazou <ebotcazou@adacore.com> * gnat.dg/opt77.adb: New test. * gnat.dg/opt77_pkg.ad[sb]: Likewise.