Patchwork Optimize (X >> N) {>,>=,<,<=} C in the combiner (PR tree-optimization/20517)

login
register
mail settings
Submitter Jakub Jelinek
Date Sept. 10, 2010, 11:37 a.m.
Message ID <20100910113748.GV1269@tyan-ft48-01.lab.bos.redhat.com>
Download mbox | patch
Permalink /patch/64379/
State New
Headers show

Comments

Jakub Jelinek - Sept. 10, 2010, 11:37 a.m.
On Fri, Sep 10, 2010 at 10:00:27AM +0200, Eric Botcazou wrote:
> > 2010-09-09  Jakub Jelinek  <jakub@redhat.com>
> >
> > 	PR tree-optimization/20517
> > 	* combine.c (simplify_comparison): Optimize (X >> N) {>,>=,<,<+} C
> > 	even if low N bits of X aren't known to be zero.
> 
> OK on principle, but can we avoid the code duplication by ORing the comparison 
> on low bits with !equality_comparison_p and setting the low order bits in the 
> shifted constant only for the appropriate codes?

Like this?  The reason I haven't done this initially was that
a) I was afraid of LTGT and UN* codes, but those shouldn't be present for
   MODE_INT op0 which is checked earlier
b) I want to prefer C << N over ((C + 1) << N) - 1 when possible (when low
   bits are known to be zero), because the former might be a cheaper
   constant and I didn't want to call nonzero_bits twice.  In the patch
   below that is handled by adding the low_bits temporary.

2010-09-10  Jakub Jelinek  <jakub@redhat.com>

	PR rtl-optimization/45617
	* combine.c (simplify_comparison): Optimize (X >> N) {>,>=,<,<=} C
	even if low N bits of X aren't known to be zero.

	* gcc.target/i386/pr45617.c: New test.



	Jakub
Eric Botcazou - Sept. 10, 2010, 4:09 p.m.
> Like this?  The reason I haven't done this initially was that
> a) I was afraid of LTGT and UN* codes, but those shouldn't be present for
>    MODE_INT op0 which is checked earlier

I thought of this...

> b) I want to prefer C << N over ((C + 1) << N) - 1 when possible (when low
>    bits are known to be zero), because the former might be a cheaper
>    constant and I didn't want to call nonzero_bits twice.  In the patch
>    below that is handled by adding the low_bits temporary.

but not of that. :-)

> 2010-09-10  Jakub Jelinek  <jakub@redhat.com>
>
> 	PR rtl-optimization/45617
> 	* combine.c (simplify_comparison): Optimize (X >> N) {>,>=,<,<=} C
> 	even if low N bits of X aren't known to be zero.
>
> 	* gcc.target/i386/pr45617.c: New test.

OK, modulo:

+	      HOST_WIDE_INT low_bits
+		= (nonzero_bits (XEXP (op0, 0), mode)
+		   & (((HOST_WIDE_INT) 1 << INTVAL (XEXP (op0, 1))) - 1));

unsigned HOST_WIDE_INT

+		  if (low_bits != 0
+		      && (code == GT || code == GTU || code == LE || code == LEU))

long line

Thanks.

Patch

--- gcc/combine.c.jj	2010-09-09 08:40:37.676409513 +0200
+++ gcc/combine.c	2010-09-10 13:24:30.019646880 +0200
@@ -11773,13 +11773,14 @@  simplify_comparison (enum rtx_code code,
 	  /* If we have (compare (xshiftrt FOO N) (const_int C)) and
 	     the low order N bits of FOO are known to be zero, we can do this
 	     by comparing FOO with C shifted left N bits so long as no
-	     overflow occurs.  */
+	     overflow occurs.  Even if the low order N bits of FOO aren't known
+	     to be zero, if the comparison is >= or < we can use the same
+	     optimization and for > or <= by setting all the low
+	     order N bits in the comparison constant.  */
 	  if (CONST_INT_P (XEXP (op0, 1))
-	      && INTVAL (XEXP (op0, 1)) >= 0
+	      && INTVAL (XEXP (op0, 1)) > 0
 	      && INTVAL (XEXP (op0, 1)) < HOST_BITS_PER_WIDE_INT
 	      && mode_width <= HOST_BITS_PER_WIDE_INT
-	      && (nonzero_bits (XEXP (op0, 0), mode)
-		  & (((HOST_WIDE_INT) 1 << INTVAL (XEXP (op0, 1))) - 1)) == 0
 	      && (((unsigned HOST_WIDE_INT) const_op
 		   + (GET_CODE (op0) != LSHIFTRT
 		      ? ((GET_MODE_MASK (mode) >> INTVAL (XEXP (op0, 1)) >> 1)
@@ -11787,15 +11788,25 @@  simplify_comparison (enum rtx_code code,
 		      : 0))
 		  <= GET_MODE_MASK (mode) >> INTVAL (XEXP (op0, 1))))
 	    {
-	      /* If the shift was logical, then we must make the condition
-		 unsigned.  */
-	      if (GET_CODE (op0) == LSHIFTRT)
-		code = unsigned_condition (code);
-
-	      const_op <<= INTVAL (XEXP (op0, 1));
-	      op1 = GEN_INT (const_op);
-	      op0 = XEXP (op0, 0);
-	      continue;
+	      HOST_WIDE_INT low_bits
+		= (nonzero_bits (XEXP (op0, 0), mode)
+		   & (((HOST_WIDE_INT) 1 << INTVAL (XEXP (op0, 1))) - 1));
+	      if (low_bits == 0 || !equality_comparison_p)
+		{
+		  /* If the shift was logical, then we must make the condition
+		     unsigned.  */
+		  if (GET_CODE (op0) == LSHIFTRT)
+		    code = unsigned_condition (code);
+
+		  const_op <<= INTVAL (XEXP (op0, 1));
+		  if (low_bits != 0
+		      && (code == GT || code == GTU || code == LE || code == LEU))
+		    const_op
+		      |= (((HOST_WIDE_INT) 1 << INTVAL (XEXP (op0, 1))) - 1);
+		  op1 = GEN_INT (const_op);
+		  op0 = XEXP (op0, 0);
+		  continue;
+		}
 	    }
 
 	  /* If we are using this shift to extract just the sign bit, we
--- gcc/testsuite/gcc.target/i386/pr45617.c.jj	2010-09-10 13:20:41.868771521 +0200
+++ gcc/testsuite/gcc.target/i386/pr45617.c	2010-09-10 13:20:41.868771521 +0200
@@ -0,0 +1,22 @@ 
+/* PR rtl-optimization/45617 */
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+int f1 (int x)
+{
+  return (x >> 23) > 12;
+}
+int f2 (int x)
+{
+  return x > ((13 << 23) - 1);
+}
+int f3 (int x)
+{
+  return (x >> 23) >= 12;
+}
+int f4 (int x)
+{
+  return x >= (12 << 23);
+}
+
+/* { dg-final { scan-assembler-not "sarl" } } */