Fix wrong code for boolean negation in condition at -O

Message ID 1939418.1pZo4JS8vg@polaris
State New
Headers show
Series
  • Fix wrong code for boolean negation in condition at -O
Related show

Commit Message

Eric Botcazou Feb. 25, 2019, 9:07 a.m.
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.

-- 
Eric Botcazou

Comments

Richard Biener Feb. 26, 2019, 9:58 a.m. | #1
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
Eric Botcazou Feb. 28, 2019, 11:06 p.m. | #2
> > 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.

-- 
Eric Botcazou
/* PR tree-optimization/89536 */
/* Testcase by Zhendong Su <su@cs.ucdavis.edu> */

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));
Jakub Jelinek Feb. 28, 2019, 11:10 p.m. | #3
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
Eric Botcazou Feb. 28, 2019, 11:19 p.m. | #4
> 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
Jakub Jelinek Feb. 28, 2019, 11:35 p.m. | #5
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
Eric Botcazou March 1, 2019, 8:35 a.m. | #6
> 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
Jeff Law March 19, 2019, 5:41 p.m. | #7
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
Eric Botcazou March 23, 2019, 10:17 a.m. | #8
> 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

Patch

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;
 	  }