This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[Committed] PR21137: Fold ((X>>1)&4) != 0 as (X&8) != 0
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Cc: "James A. Morrison" <phython at gcc dot gnu dot org>
- Date: Sun, 26 Feb 2006 08:32:37 -0700 (MST)
- Subject: [Committed] PR21137: Fold ((X>>1)&4) != 0 as (X&8) != 0
The following patch resolves PR middle-end/21137 by implementing
some constant folding transformations of ((X >> C1) & C2) eq/ne 0
where C2 is a single bit, i.e. a power of two. My thanks to Jim
Morrison for his previous attempt at the PR; the patch below fixes
the problems identified in the review of his patch.
The first difficulty is that the test for equality/inequality is
vital in this transformation. "if ((x >> 2) & 1)" is equivalent
to "if (x & 4)", but "y = ((x >> 2) & 1)" isn't the same as
"y = (x & 4)". The other refinement is that "if ((x >> 31) & 4)"
needs to be implemented as "if (x < 0)" or "if (0)" depending
upon whether x is signed (an arithmetic shift), or unsigned
(a logical shift) respectively.
The following patch has been tested on x86_64-unknown-linux-gnu
with a full "make bootstrap", all default languages, and regression
tested with a top-level "make -k check" with no new failures.
Committed to mainline as revision 111453.
2006-02-26 Roger Sayle <roger@eyesopen.com>
James A. Morrison <phython@gcc.gnu.org>
PR middle-end/21137
* fold-const.c (fold_binary) <EQ_EXPR>: Fold ((X>>C1)&C2) eq/ne 0,
when C2 is a power of two, as either (X&(C2<<C1)) eq/ne 0 if the
new constant C2<<C1, or as (X<0) or (X,false) depending upon the
signedness of the shift operation.
* gcc.dg/fold-eqandshift-1.c: New test case.
Index: fold-const.c
===================================================================
*** fold-const.c (revision 111428)
--- fold-const.c (working copy)
*************** fold_binary (enum tree_code code, tree t
*** 9653,9658 ****
--- 9653,9704 ----
fold_convert (newtype, arg1));
}
+ /* Fold ((X >> C1) & C2) == 0 and ((X >> C1) & C2) != 0 where
+ C1 is a valid shift constant, and C2 is a power of two, i.e.
+ a single bit. */
+ if (TREE_CODE (arg0) == BIT_AND_EXPR
+ && TREE_CODE (TREE_OPERAND (arg0, 0)) == RSHIFT_EXPR
+ && TREE_CODE (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1))
+ == INTEGER_CST
+ && integer_pow2p (TREE_OPERAND (arg0, 1))
+ && integer_zerop (arg1))
+ {
+ tree itype = TREE_TYPE (arg0);
+ unsigned HOST_WIDE_INT prec = TYPE_PRECISION (itype);
+ tree arg001 = TREE_OPERAND (TREE_OPERAND (arg0, 0), 1);
+
+ /* Check for a valid shift count. */
+ if (TREE_INT_CST_HIGH (arg001) == 0
+ && TREE_INT_CST_LOW (arg001) < prec)
+ {
+ tree arg01 = TREE_OPERAND (arg0, 1);
+ tree arg000 = TREE_OPERAND (TREE_OPERAND (arg0, 0), 0);
+ unsigned HOST_WIDE_INT log2 = tree_log2 (arg01);
+ /* If (C2 << C1) doesn't overflow, then ((X >> C1) & C2) != 0
+ can be rewritten as (X & (C2 << C1)) != 0. */
+ if ((log2 + TREE_INT_CST_LOW (arg01)) < prec)
+ {
+ tem = fold_build2 (LSHIFT_EXPR, itype, arg01, arg001);
+ tem = fold_build2 (BIT_AND_EXPR, itype, arg000, tem);
+ return fold_build2 (code, type, tem, arg1);
+ }
+ /* Otherwise, for signed (arithmetic) shifts,
+ ((X >> C1) & C2) != 0 is rewritten as X < 0, and
+ ((X >> C1) & C2) == 0 is rewritten as X >= 0. */
+ else if (!TYPE_UNSIGNED (itype))
+ return fold_build2 (code == EQ_EXPR ? GE_EXPR : LT_EXPR, type,
+ arg000, build_int_cst (itype, 0));
+ /* Otherwise, of unsigned (logical) shifts,
+ ((X >> C1) & C2) != 0 is rewritten as (X,false), and
+ ((X >> C1) & C2) == 0 is rewritten as (X,true). */
+ else
+ return omit_one_operand (type,
+ code == EQ_EXPR ? integer_one_node
+ : integer_zero_node,
+ arg000);
+ }
+ }
+
/* If this is an NE comparison of zero with an AND of one, remove the
comparison since the AND will give the correct value. */
if (code == NE_EXPR
/* PR middle-end/21137 */
/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-original" } */
extern void foo();
void test1(int a)
{
if ((a >> 3) & 1)
foo ();
}
void test2(int b)
{
if ((b >> 3) & 4)
foo ();
}
int test3(int c)
{
return (c >> 3) & 1;
}
int test4(int d)
{
return (d >> 3) & 4;
}
#if 0
void test5(int e)
{
if ((e >> 31) & 64)
foo();
}
void test6(unsigned int f)
{
if ((f >> 31) & 64)
foo();
}
#endif
/* { dg-final { scan-tree-dump-times "\\(a \& 8\\) != 0" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "\\(b \& 32\\) != 0" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "c >> 3 \& 1" 1 "original" } } */
/* { dg-final { scan-tree-dump-times "d >> 3 \& 4" 1 "original" } } */
/* { dg-final { cleanup-tree-dump "original" } } */
Roger
--