Patchwork Fold integer divisions to arithmetic shifts

login
register
mail settings
Submitter Dmitry Melnik
Date Oct. 19, 2010, 9:43 a.m.
Message ID <4CBD684C.9020208@ispras.ru>
Download mbox | patch
Permalink /patch/68294/
State New
Headers show

Comments

Dmitry Melnik - Oct. 19, 2010, 9:43 a.m.
On 10/14/2010 08:32 PM, Jakub Jelinek wrote:

 > Consider
 > long long x = foo ();
 > x = (x & -0x200000000LL) / 0x200000000LL;
 > The above code would optimize this as
 > x = x >> -1;
 > on 32-bit HWI targets.  Also, I think checking that arg1 is actually
 > INTEGER_CST would be desirable too (integer_pow2p can return true
 > even for COMPLEX_CST and then tree_int_cst_sgn accesses something the
 > COMPLEX_CST doesn't have).

I've modified the patch similarly to 
http://gcc.gnu.org/ml/gcc-patches/2010-10/msg01282.html, added
check for INTEGER_CST, and modified test to check for shift operation in 
'optimized' dump.
Bootstrapped and regtested on x86_64 and i686.
Ok now?

--
Best regards,
   Dmitry
Richard Henderson - Oct. 19, 2010, 5:11 p.m.
On 10/19/2010 02:43 AM, Dmitry Melnik wrote:
> On 10/14/2010 08:32 PM, Jakub Jelinek wrote:
> 
>> Consider
>> long long x = foo ();
>> x = (x & -0x200000000LL) / 0x200000000LL;
>> The above code would optimize this as
>> x = x >> -1;
>> on 32-bit HWI targets.  Also, I think checking that arg1 is actually
>> INTEGER_CST would be desirable too (integer_pow2p can return true
>> even for COMPLEX_CST and then tree_int_cst_sgn accesses something the
>> COMPLEX_CST doesn't have).
> 
> I've modified the patch similarly to http://gcc.gnu.org/ml/gcc-patches/2010-10/msg01282.html, added
> check for INTEGER_CST, and modified test to check for shift operation in 'optimized' dump.
> Bootstrapped and regtested on x86_64 and i686.
> Ok now?

Yes, this is ok.


r~

Patch

2010-10-13  Dmitry Melnik  <dm@ispras.ru>

gcc/
	* fold-const.c (fold_binary_loc): New transformation.

gcc/testsuite/
	* gcc.dg/20101013-1.c: New test.

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 8146920..80fb248 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -11599,6 +11599,31 @@  fold_binary_loc (location_t loc,
       return NULL_TREE;
 
     case TRUNC_DIV_EXPR:
+      /* Optimize (X & (-A)) / A where A is a power of 2,
+	 to X >> log2(A) */
+      if (TREE_CODE (arg0) == BIT_AND_EXPR
+	  && !TYPE_UNSIGNED (type) && TREE_CODE (arg1) == INTEGER_CST
+	  && integer_pow2p (arg1) && tree_int_cst_sgn (arg1) > 0)
+	{
+	  tree sum = fold_binary_loc (loc, PLUS_EXPR, TREE_TYPE (arg1),
+				      arg1, TREE_OPERAND (arg0, 1));
+	  if (sum && integer_zerop (sum)) {
+	    unsigned long pow2;
+
+	    if (TREE_INT_CST_LOW (arg1))
+	      pow2 = exact_log2 (TREE_INT_CST_LOW (arg1));
+	    else
+	      pow2 = exact_log2 (TREE_INT_CST_HIGH (arg1))
+		      + HOST_BITS_PER_WIDE_INT;
+
+	    return fold_build2_loc (loc, RSHIFT_EXPR, type,
+			  TREE_OPERAND (arg0, 0),
+			  build_int_cst (NULL_TREE, pow2));
+	  }
+	}
+
+      /* Fall thru */
+      
     case FLOOR_DIV_EXPR:
       /* Simplify A / (B << N) where A and B are positive and B is
 	 a power of 2, to A >> (N + log2(B)).  */
diff --git a/gcc/testsuite/gcc.dg/20101013-1.c b/gcc/testsuite/gcc.dg/20101013-1.c
new file mode 100644
index 0000000..b5bd3a7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/20101013-1.c
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int foo(int a)
+{
+  int x = (a & (~15)) / 16;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump ">>" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */