diff mbox

Move some bit and binary optimizations in simplify and match

Message ID SN2PR0701MB10249F42F47E03257133DAF78E3F0@SN2PR0701MB1024.namprd07.prod.outlook.com
State New
Headers show

Commit Message

Hurugalawadi, Naveen Oct. 14, 2015, 5:13 a.m. UTC 
Hi.

>> please adjust also according to these comments.
Adjusted the patch as per your comments.

Please find attached the patch as per your comments.
Please review the patch and let me know if any further modifications 
are required.

Thanks,
Naveen

Comments

Marc Glisse Oct. 14, 2015, 5:39 a.m. UTC | #1 
+(simplify
+ (plus (convert? @0) (convert? (xdivamulminusa @0 @1)))
+  (if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+	&& tree_nop_conversion_p (type, TREE_TYPE (@0)))
+   (trunc_mod (convert @0) (convert @1))))

See PR 67953.

+(match (abitandnotb @0 @1)
+ (bit_and:c @0 (bit_not INTEGER_CST@1)))

Does that work?

+/* Fold (a * (1 << b)) into (a << b)  */
+(simplify
+ (mult:c @0 (convert? (lshift integer_onep@1 @2)))
+  (if (! FLOAT_TYPE_P (type)
+	 && tree_nop_conversion_p (type, TREE_TYPE (@2)))
+   (lshift @0 (convert @2))))

You don't need/want to convert @2 (fold-const doesn't convert, does it?), 
and you don't need to check for tree_nop_conversion_p.
Richard Biener Oct. 14, 2015, 10:09 a.m. UTC | #2 
On Wed, Oct 14, 2015 at 7:39 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
>
> +(simplify
> + (plus (convert? @0) (convert? (xdivamulminusa @0 @1)))
> +  (if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
> +       && tree_nop_conversion_p (type, TREE_TYPE (@0)))
> +   (trunc_mod (convert @0) (convert @1))))
>
> See PR 67953.

Please drop xdivamulminusa.  It was a bad idea of mine, just add two patterns.

> +(match (abitandnotb @0 @1)
> + (bit_and:c @0 (bit_not INTEGER_CST@1)))
>
> Does that work?

No.  Please drop these helpers and instead duplicate the patterns.

>
> +/* Fold (a * (1 << b)) into (a << b)  */
> +(simplify
> + (mult:c @0 (convert? (lshift integer_onep@1 @2)))
> +  (if (! FLOAT_TYPE_P (type)
> +        && tree_nop_conversion_p (type, TREE_TYPE (@2)))
> +   (lshift @0 (convert @2))))
>
> You don't need/want to convert @2 (fold-const doesn't convert, does it?),
> and you don't need to check for tree_nop_conversion_p.

I think for long x and x * (long)(1u << b) you need to do because the
result for b == 33 would be different.  Indeed you don't need the convert on @2.

Richard.

>
> --
> Marc Glisse
Marc Glisse Oct. 14, 2015, 10:45 a.m. UTC | #3 
On Wed, 14 Oct 2015, Richard Biener wrote:

>> +/* Fold (a * (1 << b)) into (a << b)  */
>> +(simplify
>> + (mult:c @0 (convert? (lshift integer_onep@1 @2)))
>> +  (if (! FLOAT_TYPE_P (type)
>> +        && tree_nop_conversion_p (type, TREE_TYPE (@2)))
>> +   (lshift @0 (convert @2))))
>>
>> You don't need/want to convert @2 (fold-const doesn't convert, does it?),
>> and you don't need to check for tree_nop_conversion_p.
>
> I think for long x and x * (long)(1u << b) you need to do because the
> result for b == 33 would be different.

- that check should be with TREE_TYPE (@1)
- 1u << 33 is undefined, isn't it?

x * (int)(1ul << b), which for b=33 should yield 0, would give the 
undefined x << b so some check does seem needed indeed.
Richard Biener Oct. 14, 2015, 10:53 a.m. UTC | #4 
On Wed, Oct 14, 2015 at 12:45 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Wed, 14 Oct 2015, Richard Biener wrote:
>
>>> +/* Fold (a * (1 << b)) into (a << b)  */
>>> +(simplify
>>> + (mult:c @0 (convert? (lshift integer_onep@1 @2)))
>>> +  (if (! FLOAT_TYPE_P (type)
>>> +        && tree_nop_conversion_p (type, TREE_TYPE (@2)))
>>> +   (lshift @0 (convert @2))))
>>>
>>> You don't need/want to convert @2 (fold-const doesn't convert, does it?),
>>> and you don't need to check for tree_nop_conversion_p.
>>
>>
>> I think for long x and x * (long)(1u << b) you need to do because the
>> result for b == 33 would be different.
>
>
> - that check should be with TREE_TYPE (@1)

of course

> - 1u << 33 is undefined, isn't it?

Is it?  I thought it were fine for unsigned.  Not sure if we should exploit this
undefinedness here.  Btw, if it were a truncating conversion then the
resulting shift could be invalid if @2 is too big (but not too big for the
wider shift).  So either way I think we should only allow nop conversions
here (as fold-const.c did).

Richard.

> x * (int)(1ul << b), which for b=33 should yield 0, would give the undefined
> x << b so some check does seem needed indeed.
>
> --
> Marc Glisse
Marc Glisse Oct. 14, 2015, 11:38 a.m. UTC | #5 
On Wed, 14 Oct 2015, Richard Biener wrote:

> On Wed, Oct 14, 2015 at 12:45 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> On Wed, 14 Oct 2015, Richard Biener wrote:
>>
>>>> +/* Fold (a * (1 << b)) into (a << b)  */
>>>> +(simplify
>>>> + (mult:c @0 (convert? (lshift integer_onep@1 @2)))
>>>> +  (if (! FLOAT_TYPE_P (type)
>>>> +        && tree_nop_conversion_p (type, TREE_TYPE (@2)))
>>>> +   (lshift @0 (convert @2))))
>>>>
>>>> You don't need/want to convert @2 (fold-const doesn't convert, does it?),
>>>> and you don't need to check for tree_nop_conversion_p.
>>>
>>>
>>> I think for long x and x * (long)(1u << b) you need to do because the
>>> result for b == 33 would be different.
>>
>>
>> - that check should be with TREE_TYPE (@1)
>
> of course
>
>> - 1u << 33 is undefined, isn't it?
>
> Is it?  I thought it were fine for unsigned.

Can't be, Intel thinks it is 2u while some other hardware thinks it is 0.

> Not sure if we should exploit this
> undefinedness here.  Btw, if it were a truncating conversion then the
> resulting shift could be invalid if @2 is too big (but not too big for the
> wider shift).

Yes, that was my example below.

> So either way I think we should only allow nop conversions
> here (as fold-const.c did).

I agree that's the safest / easiest for now.

>> x * (int)(1ul << b), which for b=33 should yield 0, would give the undefined
>> x << b so some check does seem needed indeed.
diff mbox

Patch

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index de45a2c..2d81b2c 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9232,26 +9232,6 @@  fold_binary_loc (location_t loc,
       return NULL_TREE;
 
     case PLUS_EXPR:
-      if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
-	{
-	  /* X + (X / CST) * -CST is X % CST.  */
-	  if (TREE_CODE (arg1) == MULT_EXPR
-	      && TREE_CODE (TREE_OPERAND (arg1, 0)) == TRUNC_DIV_EXPR
-	      && operand_equal_p (arg0,
-				  TREE_OPERAND (TREE_OPERAND (arg1, 0), 0), 0))
-	    {
-	      tree cst0 = TREE_OPERAND (TREE_OPERAND (arg1, 0), 1);
-	      tree cst1 = TREE_OPERAND (arg1, 1);
-	      tree sum = fold_binary_loc (loc, PLUS_EXPR, TREE_TYPE (cst1),
-				      cst1, cst0);
-	      if (sum && integer_zerop (sum))
-		return fold_convert_loc (loc, type,
-					 fold_build2_loc (loc, TRUNC_MOD_EXPR,
-						      TREE_TYPE (arg0), arg0,
-						      cst0));
-	    }
-	}
-
       /* Handle (A1 * C1) + (A2 * C2) with A1, A2 or C1, C2 being the same or
 	 one.  Make sure the type is not saturating and has the signedness of
 	 the stripped operands, as fold_plusminus_mult_expr will re-associate.
@@ -9692,28 +9672,6 @@  fold_binary_loc (location_t loc,
 			    fold_convert_loc (loc, type,
 					      TREE_OPERAND (arg0, 0)));
 
-      if (! FLOAT_TYPE_P (type))
-	{
-	  /* Fold (A & ~B) - (A & B) into (A ^ B) - B, where B is
-	     any power of 2 minus 1.  */
-	  if (TREE_CODE (arg0) == BIT_AND_EXPR
-	      && TREE_CODE (arg1) == BIT_AND_EXPR
-	      && operand_equal_p (TREE_OPERAND (arg0, 0),
-				  TREE_OPERAND (arg1, 0), 0))
-	    {
-	      tree mask0 = TREE_OPERAND (arg0, 1);
-	      tree mask1 = TREE_OPERAND (arg1, 1);
-	      tree tem = fold_build1_loc (loc, BIT_NOT_EXPR, type, mask0);
-
-	      if (operand_equal_p (tem, mask1, 0))
-		{
-		  tem = fold_build2_loc (loc, BIT_XOR_EXPR, type,
-				     TREE_OPERAND (arg0, 0), mask1);
-		  return fold_build2_loc (loc, MINUS_EXPR, type, tem, mask1);
-		}
-	    }
-	}
-
       /* Fold __complex__ ( x, 0 ) - __complex__ ( 0, y ) to
 	 __complex__ ( x, -y ).  This is not the same for SNaNs or if
 	 signed zeros are involved.  */
@@ -9803,20 +9761,6 @@  fold_binary_loc (location_t loc,
       goto associate;
 
     case MULT_EXPR:
-      /* (-A) * (-B) -> A * B  */
-      if (TREE_CODE (arg0) == NEGATE_EXPR && negate_expr_p (arg1))
-	return fold_build2_loc (loc, MULT_EXPR, type,
-			    fold_convert_loc (loc, type,
-					      TREE_OPERAND (arg0, 0)),
-			    fold_convert_loc (loc, type,
-					      negate_expr (arg1)));
-      if (TREE_CODE (arg1) == NEGATE_EXPR && negate_expr_p (arg0))
-	return fold_build2_loc (loc, MULT_EXPR, type,
-			    fold_convert_loc (loc, type,
-					      negate_expr (arg0)),
-			    fold_convert_loc (loc, type,
-					      TREE_OPERAND (arg1, 0)));
-
       if (! FLOAT_TYPE_P (type))
 	{
 	  /* Transform x * -C into -x * C if x is easily negatable.  */
@@ -9830,16 +9774,6 @@  fold_binary_loc (location_t loc,
 						  negate_expr (arg0)),
 				tem);
 
-	  /* (a * (1 << b)) is (a << b)  */
-	  if (TREE_CODE (arg1) == LSHIFT_EXPR
-	      && integer_onep (TREE_OPERAND (arg1, 0)))
-	    return fold_build2_loc (loc, LSHIFT_EXPR, type, op0,
-				TREE_OPERAND (arg1, 1));
-	  if (TREE_CODE (arg0) == LSHIFT_EXPR
-	      && integer_onep (TREE_OPERAND (arg0, 0)))
-	    return fold_build2_loc (loc, LSHIFT_EXPR, type, op1,
-				TREE_OPERAND (arg0, 1));
-
 	  /* (A + A) * C -> A * 2 * C  */
 	  if (TREE_CODE (arg0) == PLUS_EXPR
 	      && TREE_CODE (arg1) == INTEGER_CST
@@ -9882,21 +9816,6 @@  fold_binary_loc (location_t loc,
 	}
       else
 	{
-	  /* Convert (C1/X)*C2 into (C1*C2)/X.  This transformation may change
-             the result for floating point types due to rounding so it is applied
-             only if -fassociative-math was specify.  */
-	  if (flag_associative_math
-	      && TREE_CODE (arg0) == RDIV_EXPR
-	      && TREE_CODE (arg1) == REAL_CST
-	      && TREE_CODE (TREE_OPERAND (arg0, 0)) == REAL_CST)
-	    {
-	      tree tem = const_binop (MULT_EXPR, TREE_OPERAND (arg0, 0),
-				      arg1);
-	      if (tem)
-		return fold_build2_loc (loc, RDIV_EXPR, type, tem,
-				    TREE_OPERAND (arg0, 1));
-	    }
-
           /* Strip sign operations from X in X*X, i.e. -Y*-Y -> Y*Y.  */
 	  if (operand_equal_p (arg0, arg1, 0))
 	    {
@@ -10013,28 +9932,6 @@  fold_binary_loc (location_t loc,
 				    arg1);
 	}
 
-      /* (X & ~Y) | (~X & Y) is X ^ Y */
-      if (TREE_CODE (arg0) == BIT_AND_EXPR
-	  && TREE_CODE (arg1) == BIT_AND_EXPR)
-        {
-	  tree a0, a1, l0, l1, n0, n1;
-
-	  a0 = fold_convert_loc (loc, type, TREE_OPERAND (arg1, 0));
-	  a1 = fold_convert_loc (loc, type, TREE_OPERAND (arg1, 1));
-
-	  l0 = fold_convert_loc (loc, type, TREE_OPERAND (arg0, 0));
-	  l1 = fold_convert_loc (loc, type, TREE_OPERAND (arg0, 1));
-	  
-	  n0 = fold_build1_loc (loc, BIT_NOT_EXPR, type, l0);
-	  n1 = fold_build1_loc (loc, BIT_NOT_EXPR, type, l1);
-	  
-	  if ((operand_equal_p (n0, a0, 0)
-	       && operand_equal_p (n1, a1, 0))
-	      || (operand_equal_p (n0, a1, 0)
-		  && operand_equal_p (n1, a0, 0)))
-	    return fold_build2_loc (loc, BIT_XOR_EXPR, type, l0, n1);
-	}
-
       /* See if this can be simplified into a rotate first.  If that
 	 is unsuccessful continue in the association code.  */
       goto bit_rotate;
@@ -10053,22 +9950,6 @@  fold_binary_loc (location_t loc,
       goto bit_rotate;
 
     case BIT_AND_EXPR:
-      /* ~X & X, (X == 0) & X, and !X & X are always zero.  */
-      if ((TREE_CODE (arg0) == BIT_NOT_EXPR
-	   || TREE_CODE (arg0) == TRUTH_NOT_EXPR
-	   || (TREE_CODE (arg0) == EQ_EXPR
-	       && integer_zerop (TREE_OPERAND (arg0, 1))))
-	  && operand_equal_p (TREE_OPERAND (arg0, 0), arg1, 0))
-	return omit_one_operand_loc (loc, type, integer_zero_node, arg1);
-
-      /* X & ~X , X & (X == 0), and X & !X are always zero.  */
-      if ((TREE_CODE (arg1) == BIT_NOT_EXPR
-	   || TREE_CODE (arg1) == TRUTH_NOT_EXPR
-	   || (TREE_CODE (arg1) == EQ_EXPR
-	       && integer_zerop (TREE_OPERAND (arg1, 1))))
-	  && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
-	return omit_one_operand_loc (loc, type, integer_zero_node, arg0);
-
       /* Fold (X ^ 1) & 1 as (X & 1) == 0.  */
       if (TREE_CODE (arg0) == BIT_XOR_EXPR
 	  && INTEGRAL_TYPE_P (type)
diff --git a/gcc/match.pd b/gcc/match.pd
index 6714796..5813bf7 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -323,6 +323,65 @@  along with GCC; see the file COPYING3.  If not see
     (if (real_isinteger (&TREE_REAL_CST (@1), &n) && (n & 1) == 0)
      (pows @0 @1))))))
 
+/* Fold X + (X / CST) * -CST to X % CST.  */
+(match (xdivamulminusa @0 @1)
+ (mult (trunc_div @0 @1) (negate @1)))
+(match (xdivamulminusa @0 @1)
+ (mult (trunc_div @0 INTEGER_CST@1) INTEGER_CST@2)
+  (if (wi::add (@1, @2) == 0)))
+
+(simplify
+ (plus (convert? @0) (convert? (xdivamulminusa @0 @1)))
+  (if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+	&& tree_nop_conversion_p (type, TREE_TYPE (@0)))
+   (trunc_mod (convert @0) (convert @1))))
+
+(match (abitandnotb @0 @1)
+ (bit_and:c @0 (bit_not @1)))
+(match (abitandnotb @0 @1)
+ (bit_and:c INTEGER_CST@0 (bit_not @1)))
+(match (abitandnotb @0 @1)
+ (bit_and:c @0 (bit_not INTEGER_CST@1)))
+
+(match (abitandb @0 @1)
+ (bit_and:c @0 @1))
+(match (abitandb @0 @1)
+ (bit_and:c INTEGER_CST@0 @1))
+(match (abitandb @0 @1)
+ (bit_and:c @0 INTEGER_CST@1))
+
+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (abitandnotb @0 @1) (abitandb @0 @1))
+  (if (! FLOAT_TYPE_P (type))
+   (minus (bit_xor @0 @1) @1)))
+
+/* Fold (a * (1 << b)) into (a << b)  */
+(simplify
+ (mult:c @0 (convert? (lshift integer_onep@1 @2)))
+  (if (! FLOAT_TYPE_P (type)
+	 && tree_nop_conversion_p (type, TREE_TYPE (@2)))
+   (lshift @0 (convert @2))))
+
+/* Fold (C1/X)*C2 into (C1*C2)/X.  */
+(simplify
+ (mult (rdiv REAL_CST@0 @1) REAL_CST@2)
+  (if (flag_associative_math)
+  (with
+   { tree tem = const_binop (MULT_EXPR, type, @0, @2); }
+  (if (tem)
+   (rdiv { tem; } @1)))))
+
+/* Simplify (X & ~Y) | (~X & Y) is X ^ Y.  */
+(simplify
+ (bit_ior (bit_and:cs @0 (bit_not @1)) (abitandnotb @1 @0))
+  (bit_xor @0 @1))
+
+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c (convert? @0) (convert? (bit_not @0)))
+  { build_zero_cst (type); })
+
 /* X % Y is smaller than Y.  */
 (for cmp (lt ge)
  (simplify
@@ -542,6 +601,13 @@  along with GCC; see the file COPYING3.  If not see
 (match negate_expr_p
  VECTOR_CST
  (if (FLOAT_TYPE_P (TREE_TYPE (type)) || TYPE_OVERFLOW_WRAPS (type))))
+
+/* (-A) * (-B) -> A * B  */
+(simplify
+ (mult:c (convert1? (negate @0)) (convert2? negate_expr_p@1))
+  (if (tree_nop_conversion_p (type, TREE_TYPE (@0))
+       && tree_nop_conversion_p (type, TREE_TYPE (@1)))
+   (mult (convert @0) (convert (negate @1)))))
  
 /* -(A + B) -> (-B) - A.  */
 (simplify