Move some bit and binary optimizations in simplify and match

Move some bit and binary optimizations in simplify and match

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 1597 bytes --]

Hi,

Please find attached the patch that moves some more patterns from
fold-const using simplify and match.

Please review the patch and let me know if any modifications are required.

Tested the patch on X86 without any regressions.

Thanks,
Naveen

ChangeLog

2015-10-07  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>

	* fold-const.c (fold_binary_loc) : Move X + (X / CST) * -CST ->
	X % CST to match.pd.
	Move Fold (A & ~B) - (A & B) into (A ^ B) - B to match.pd.
	Move (-A) * (-B) -> A * B to match.pd.
	Move (a * (1 << b)) is (a << b) to match.pd.
	Move convert (C1/X)*C2 into (C1*C2)/X to match.pd.
	Move (X & ~Y) | (~X & Y) is X ^ Y to match.pd.
	Move ~X & X, (X == 0) & X, and !X & X are zero to match.pd.
	Move X & ~X , X & (X == 0), and X & !X are zero to match.pd.
	Move Fold X & (X ^ Y) as X & ~Y to match.pd.
	Move Fold X & (Y ^ X) as ~Y & X to match.pd.

	* match.pd (plus @0 (mult:s (trunc_div:s @0 INTEGER_CST@1)
	(negate @1))): New simplifier.
	(minus (bit_and:s @0 (bit_not:s @1)) (bit_and:s @0 @1)) :
	New simplifier.
	(mult:c @0 (lshift integer_onep@1 @2)): New simplifier.
	(mult:c (plus @0 @0) INTEGER_CST@1): New simplifier.
	(mult (rdiv REAL_CST@0 @1) REAL_CST@2): New simplifier.
	(bit_ior (bit_and:s @0 (bit_not:s @1)) (bit_and:s (bit_not:s @0) @1))
	: New simplifier.
	(bit_and:c @0 (bit_not:s @0)): New simplifier.
	(bit_and:c @0 (eq @0 integer_zerop@1)): New simplifier.
	(bit_and @0 (bit_xor:s @0 @1)): New simplifier.
	(bit_and @0 (bit_xor:s @1 @0)): New simplifier.
	(mult:c (negate @0) (negate @1)): New simplifier.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bit_bin_simplify.patch --]
[-- Type: text/x-patch; name="bit_bin_simplify.patch", Size: 9391 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 7231fd6..ad850f0 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9191,26 +9191,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.
@@ -9651,28 +9631,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.  */
@@ -9762,20 +9720,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.  */
@@ -9789,16 +9733,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
@@ -9841,21 +9775,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))
 	    {
@@ -9972,28 +9891,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;
@@ -10012,22 +9909,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)
@@ -10083,26 +9964,6 @@ fold_binary_loc (location_t loc,
 			      fold_build1_loc (loc, BIT_NOT_EXPR, type, tem),
 			      fold_convert_loc (loc, type, arg1));
 	}
-      /* Fold X & (X ^ Y) as X & ~Y.  */
-      if (TREE_CODE (arg1) == BIT_XOR_EXPR
-	  && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
-	{
-	  tem = fold_convert_loc (loc, type, TREE_OPERAND (arg1, 1));
-	  return fold_build2_loc (loc, BIT_AND_EXPR, type,
-			      fold_convert_loc (loc, type, arg0),
-			      fold_build1_loc (loc, BIT_NOT_EXPR, type, tem));
-	}
-      /* Fold X & (Y ^ X) as ~Y & X.  */
-      if (TREE_CODE (arg1) == BIT_XOR_EXPR
-	  && operand_equal_p (arg0, TREE_OPERAND (arg1, 1), 0)
-	  && reorder_operands_p (arg0, TREE_OPERAND (arg1, 0)))
-	{
-	  tem = fold_convert_loc (loc, type, TREE_OPERAND (arg1, 0));
-	  return fold_build2_loc (loc, BIT_AND_EXPR, type,
-			      fold_build1_loc (loc, BIT_NOT_EXPR, type, tem),
-			      fold_convert_loc (loc, type, arg0));
-	}
-
       /* Fold (X * Y) & -(1 << CST) to X * Y if Y is a constant
          multiple of 1 << CST.  */
       if (TREE_CODE (arg1) == INTEGER_CST)
diff --git a/gcc/match.pd b/gcc/match.pd
index bd5c267..690ea14 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -316,6 +316,56 @@ along with GCC; see the file COPYING3.  If not see
   (coss (op @0))
    (coss @0))))
 
+/* Fold X + (X / CST) * -CST to X % CST.  */
+(simplify
+ (plus @0 (mult:s (trunc_div:s @0 INTEGER_CST@1) (negate @1)))
+  (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+  (trunc_mod @0 @1)))
+
+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:s @0 (bit_not:s @1)) (bit_and:s @0 @1))
+  (if (! FLOAT_TYPE_P (type))
+  (minus (bit_xor @0 @1) @1)))
+
+/* Fold (a * (1 << b)) into (a << b)  */
+(simplify
+ (mult:c @0 (lshift integer_onep@1 @2))
+  (if (! FLOAT_TYPE_P (type))
+  (lshift @0 @2)))
+
+/* Fold (C1/X)*C2 into (C1*C2)/X.  */ 
+(simplify
+ (mult (rdiv REAL_CST@0 @1) REAL_CST@2)
+  (if (FLOAT_TYPE_P (type)
+       && flag_associative_math)
+  (rdiv (mult @0 @2) @1)))
+
+/* Simplify (X & ~Y) | (~X & Y) is X ^ Y.  */
+(simplify
+ (bit_ior (bit_and:s @0 (bit_not:s @1)) (bit_and:s (bit_not:s @0) @1))
+  (bit_xor @0 @1))
+
+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c @0 (bit_not:s @0))
+  { build_zero_cst (type); })
+
+/* Simplify (X == 0) & X as zero.  */
+(simplify
+ (bit_and:c @0 (eq @0 integer_zerop@1))
+  @1)
+
+/* Fold X & (X ^ Y) as X & ~Y.  */
+(simplify
+ (bit_and @0 (bit_xor:s @0 @1))
+  (bit_and @0 (bit_not @1)))
+
+/* Fold X & (Y ^ X) as ~Y & X.  */
+(simplify
+ (bit_and @0 (bit_xor:s @1 @0))
+  (bit_and (bit_not @1) @0))
+
 /* X % Y is smaller than Y.  */
 (for cmp (lt ge)
  (simplify
@@ -549,6 +599,11 @@ along with GCC; see the file COPYING3.  If not see
  (if (!FIXED_POINT_TYPE_P (type))
  (plus @0 (negate @1))))
 
+/* (-A) * (-B) -> A * B  */
+(simplify
+ (mult:c (negate @0) (negate @1))
+  (mult @0 @1))
+
 /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST))
    when profitable.
    For bitwise binary operations apply operand conversions to the

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Wed, Oct 7, 2015 at 11:54 AM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> Hi,
>
> Please find attached the patch that moves some more patterns from
> fold-const using simplify and match.
>
> Please review the patch and let me know if any modifications are required.

+/* Fold X + (X / CST) * -CST to X % CST.  */
+(simplify
+ (plus @0 (mult:s (trunc_div:s @0 INTEGER_CST@1) (negate @1)))

that's a bit too literal -- (negate @1) won't match for -@1

+  (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+  (trunc_mod @0 @1)))

+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:s @0 (bit_not:s @1)) (bit_and:s @0 @1))
+  (if (! FLOAT_TYPE_P (type))
+  (minus (bit_xor @0 @1) @1)))

Likewise the fold code handles both constant and non-constant B.
To mimic this you need a second pattern for the constant case
or add a predicate matching @1 with ~@1.

+/* (-A) * (-B) -> A * B  */
+(simplify
+ (mult:c (negate @0) (negate @1))
+  (mult @0 @1))

the fold-const.c code handles sign-conversions around the negates
so you should add (convert?)s around them and verify useless_type_conversions.

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

Likewise (sign-conversion on the lshift).  Though I'm not sure
this won't trap ubsan for signed left-shift of negative values.

+/* Fold (C1/X)*C2 into (C1*C2)/X.  */
+(simplify
+ (mult (rdiv REAL_CST@0 @1) REAL_CST@2)
+  (if (FLOAT_TYPE_P (type)
+       && flag_associative_math)
+  (rdiv (mult @0 @2) @1)))

the fold-const.c code avoids the transform if @0 * @2 doesn't simplify
(nans/infs and flag combos).  Not sure if we care though.

+/* Simplify (X & ~Y) | (~X & Y) is X ^ Y.  */
+(simplify
+ (bit_ior (bit_and:s @0 (bit_not:s @1)) (bit_and:s (bit_not:s @0) @1))
+  (bit_xor @0 @1))

fold again handles also constants for X and Y.  I suggest to re-use
the matching predicate you need to add for the above ~ pattern.
fold also handles sign-converted bit-ands.

+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c @0 (bit_not:s @0))
+  { build_zero_cst (type); })

I was sure we already have this...  looks I was wrong.  Again fold
handles sign-conversions on @0 resp. the bit_not.

+/* Simplify (X == 0) & X as zero.  */
+(simplify
+ (bit_and:c @0 (eq @0 integer_zerop@1))
+  @1)

I think we have this one see logical_inverted_value and uses:

(simplify
 (bit_and:c @0 (logical_inverted_value @0))
 { build_zero_cst (type); })

+/* Fold X & (X ^ Y) as X & ~Y.  */
+(simplify
+ (bit_and @0 (bit_xor:s @0 @1))
+  (bit_and @0 (bit_not @1)))
+
+/* Fold X & (Y ^ X) as ~Y & X.  */
+(simplify
+ (bit_and @0 (bit_xor:s @1 @0))
+  (bit_and (bit_not @1) @0))

add :c on the bit_and and the bit_xor and then merge the patterns.

Thanks,
Richard.




> Tested the patch on X86 without any regressions.
>
> Thanks,
> Naveen
>
> ChangeLog
>
> 2015-10-07  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>
>
>         * fold-const.c (fold_binary_loc) : Move X + (X / CST) * -CST ->
>         X % CST to match.pd.
>         Move Fold (A & ~B) - (A & B) into (A ^ B) - B to match.pd.
>         Move (-A) * (-B) -> A * B to match.pd.
>         Move (a * (1 << b)) is (a << b) to match.pd.
>         Move convert (C1/X)*C2 into (C1*C2)/X to match.pd.
>         Move (X & ~Y) | (~X & Y) is X ^ Y to match.pd.
>         Move ~X & X, (X == 0) & X, and !X & X are zero to match.pd.
>         Move X & ~X , X & (X == 0), and X & !X are zero to match.pd.
>         Move Fold X & (X ^ Y) as X & ~Y to match.pd.
>         Move Fold X & (Y ^ X) as ~Y & X to match.pd.
>
>         * match.pd (plus @0 (mult:s (trunc_div:s @0 INTEGER_CST@1)
>         (negate @1))): New simplifier.
>         (minus (bit_and:s @0 (bit_not:s @1)) (bit_and:s @0 @1)) :
>         New simplifier.
>         (mult:c @0 (lshift integer_onep@1 @2)): New simplifier.
>         (mult:c (plus @0 @0) INTEGER_CST@1): New simplifier.
>         (mult (rdiv REAL_CST@0 @1) REAL_CST@2): New simplifier.
>         (bit_ior (bit_and:s @0 (bit_not:s @1)) (bit_and:s (bit_not:s @0) @1))
>         : New simplifier.
>         (bit_and:c @0 (bit_not:s @0)): New simplifier.
>         (bit_and:c @0 (eq @0 integer_zerop@1)): New simplifier.
>         (bit_and @0 (bit_xor:s @0 @1)): New simplifier.
>         (bit_and @0 (bit_xor:s @1 @0)): New simplifier.
>         (mult:c (negate @0) (negate @1)): New simplifier.

Re: Move some bit and binary optimizations in simplify and match

[Bernd Schmidt]

On 10/07/2015 11:54 AM, Hurugalawadi, Naveen wrote:
> 	Move Fold X & (X ^ Y) as X & ~Y to match.pd.
> 	Move Fold X & (Y ^ X) as ~Y & X to match.pd.

I wonder if we shouldn't try to autogenerate patterns such as these. I 
did something like that for a different project a long time ago. 
Generate expressions up to a certain level of complexity, identify which 
ones are equivalent, and pick the one with the lowest cost for 
simplifications...


Bernd

Re: Move some bit and binary optimizations in simplify and match

[Joseph Myers]

On Thu, 8 Oct 2015, Bernd Schmidt wrote:

> On 10/07/2015 11:54 AM, Hurugalawadi, Naveen wrote:
> > 	Move Fold X & (X ^ Y) as X & ~Y to match.pd.
> > 	Move Fold X & (Y ^ X) as ~Y & X to match.pd.
> 
> I wonder if we shouldn't try to autogenerate patterns such as these. I did
> something like that for a different project a long time ago. Generate
> expressions up to a certain level of complexity, identify which ones are
> equivalent, and pick the one with the lowest cost for simplifications...

Any bitwise expression whose ultimate operands are X, Y, 0 and -1 
(possibly with conversions among types of the same width) could be 
canonicalized to one of: 0, -1, X, Y, ~X, ~Y, X^Y, X^~Y, A&B or A|B (where 
A is X or ~X and B is Y or ~Y).  I don't guarantee those are the best 
canonical forms, but if you're folding this sort of expression you ought 
to be able to make GCC fold all such expressions down to some such form 
(and fold away all equality comparisons among such expressions with 
constant value).

Now, such canonicalization could be done with a finite number of 
autogenerated patterns (if you can fold ~(A BINOP B), (A BINOP B) BINOP C 
and (A BINOP B) BINOP (C BINOP D), for A, B, C, D from 0, -1, X, Y, ~X, 
~Y, folding for more complicated expressions falls out).  I don't know if 
that's the best way to do such folding or not.

Given such folding, autogenerating expressions of the form ((A BINOP B) 
BINOP (C BINOP D)) == CANONICAL_FORM seems a plausible way of getting 
testsuite coverage for the folding (and for that matter for seeing what 
such folding is missing at present).

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: Move some bit and binary optimizations in simplify and match

[Bernd Schmidt]

On 10/08/2015 08:03 PM, Joseph Myers wrote:
> On Thu, 8 Oct 2015, Bernd Schmidt wrote:
>
>> On 10/07/2015 11:54 AM, Hurugalawadi, Naveen wrote:
>>> 	Move Fold X & (X ^ Y) as X & ~Y to match.pd.
>>> 	Move Fold X & (Y ^ X) as ~Y & X to match.pd.
>>
>> I wonder if we shouldn't try to autogenerate patterns such as these. I did
>> something like that for a different project a long time ago. Generate
>> expressions up to a certain level of complexity, identify which ones are
>> equivalent, and pick the one with the lowest cost for simplifications...
>
> Any bitwise expression whose ultimate operands are X, Y, 0 and -1
> (possibly with conversions among types of the same width) could be
> canonicalized to one of: 0, -1, X, Y, ~X, ~Y, X^Y, X^~Y, A&B or A|B (where
> A is X or ~X and B is Y or ~Y).  I don't guarantee those are the best
> canonical forms, but if you're folding this sort of expression you ought
> to be able to make GCC fold all such expressions down to some such form
> (and fold away all equality comparisons among such expressions with
> constant value).

I was actually thinking of also doing this for more complex expressions 
with more than two different operands.


Bernd

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Thu, Oct 8, 2015 at 8:15 PM, Bernd Schmidt <bschmidt@redhat.com> wrote:
> On 10/08/2015 08:03 PM, Joseph Myers wrote:
>>
>> On Thu, 8 Oct 2015, Bernd Schmidt wrote:
>>
>>> On 10/07/2015 11:54 AM, Hurugalawadi, Naveen wrote:
>>>>
>>>>         Move Fold X & (X ^ Y) as X & ~Y to match.pd.
>>>>         Move Fold X & (Y ^ X) as ~Y & X to match.pd.
>>>
>>>
>>> I wonder if we shouldn't try to autogenerate patterns such as these. I
>>> did
>>> something like that for a different project a long time ago. Generate
>>> expressions up to a certain level of complexity, identify which ones are
>>> equivalent, and pick the one with the lowest cost for simplifications...
>>
>>
>> Any bitwise expression whose ultimate operands are X, Y, 0 and -1
>> (possibly with conversions among types of the same width) could be
>> canonicalized to one of: 0, -1, X, Y, ~X, ~Y, X^Y, X^~Y, A&B or A|B (where
>> A is X or ~X and B is Y or ~Y).  I don't guarantee those are the best
>> canonical forms, but if you're folding this sort of expression you ought
>> to be able to make GCC fold all such expressions down to some such form
>> (and fold away all equality comparisons among such expressions with
>> constant value).
>
>
> I was actually thinking of also doing this for more complex expressions with
> more than two different operands.

Note that the optimization problem in general is more complicated and
involves multiple such expressions which should be associated/optimized
with CSE in mind to result in the minimal number of overall instructions
needed to compute all required values.

But yes, we could auto-generate patterns up to a specific depth or up
to a point where more complex patterns are handled by composition.
Patches welcome ;)

Richard.

>
> Bernd

Re: Move some bit and binary optimizations in simplify and match

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 842 bytes --]

Hi Richard,

Thanks for your review and useful comments.
I will  move the future optimization patterns with all the conditions
present in fold-const or builtins file as per your suggestions.

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

The last pattern has been removed due to the discussions over it
and a regression it caused.
================================================
+/* Fold X & (X ^ Y) as X & ~Y.  */
+(simplify
+ (bit_and:c (convert? @0) (convert? (bit_xor:c @0 @1)))
+  (bit_and (convert @0) (convert (bit_not @1))))
================================================

FAIL: gcc.dg/tree-ssa/vrp47.c scan-tree-dump-times vrp2 " & 1;" 0
FAIL: gcc.dg/tree-ssa/vrp59.c scan-tree-dump-not vrp1 " & 3;"

Thanks,
Naveen

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bit_plus.patch --]
[-- Type: text/x-patch; name="bit_plus.patch", Size: 8425 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 5d8822f..8889c39 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9192,26 +9192,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.
@@ -9652,28 +9632,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.  */
@@ -9763,20 +9721,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.  */
@@ -9790,16 +9734,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
@@ -9842,21 +9776,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))
 	    {
@@ -9973,28 +9892,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;
@@ -10013,22 +9910,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 b87c436..7210dfad 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -316,6 +316,47 @@ along with GCC; see the file COPYING3.  If not see
   (coss (op @0))
    (coss @0))))
 
+/* Fold X + (X / CST) * -CST to X % CST.  */
+(simplify
+ (plus (convert1? @0) (convert2? (mult (trunc_div @0 INTEGER_CST@1) INTEGER_CST@2)))
+  (if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+	&& wi::add (@1, @2) == 0)
+   (trunc_mod (convert @0) (convert @1))))
+
+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @2))
+  (if (! FLOAT_TYPE_P (type)
+       && wi::eq_p (@1, @2))
+   (minus (bit_xor @0 @1) @1)))
+
+/* Fold (a * (1 << b)) into (a << b)  */
+(simplify
+ (mult:c (convert1? @0) (convert2? (lshift integer_onep@1 @2)))
+  (if (! FLOAT_TYPE_P (type))
+   (lshift (convert @0) (convert @2))))
+
+/* Fold (C1/X)*C2 into (C1*C2)/X.  */
+(simplify
+ (mult (rdiv REAL_CST@0 @1) REAL_CST@2)
+  (with
+   { tree tem = const_binop (MULT_EXPR, type, @0, @2); }
+  (if (tem && FLOAT_TYPE_P (type)
+       && flag_associative_math)
+   (rdiv (mult @0 @2) @1))))
+
+/* Simplify (X & ~Y) | (~X & Y) is X ^ Y.  */
+(simplify
+ (bit_ior (bit_and:s @0 (bit_not @1)) (bit_and:s (bit_not @2) @3))
+  (if (wi::eq_p (@0, @2)
+       && wi::eq_p (@1, @3))
+   (bit_xor @0 @3)))
+
+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c (convert? @0) (convert? (bit_not @0)))
+  (convert { build_zero_cst (TREE_TYPE (@0)); }))
+
 /* X % Y is smaller than Y.  */
 (for cmp (lt ge)
  (simplify
@@ -549,6 +590,13 @@ along with GCC; see the file COPYING3.  If not see
  (if (!FIXED_POINT_TYPE_P (type))
  (plus @0 (negate @1))))
 
+/* (-A) * (-B) -> A * B  */
+(simplify
+ (mult:c (convert? (negate @0)) (convert? (negate @1)))
+  (if ((GIMPLE && useless_type_conversion_p (type, TREE_TYPE (@0)))
+       || (GENERIC && type == TREE_TYPE (@0)))
+   (mult (convert @0) (convert @1))))
+
 /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST))
    when profitable.
    For bitwise binary operations apply operand conversions to the

Re: Move some bit and binary optimizations in simplify and match

[Marc Glisse]

On Mon, 12 Oct 2015, Hurugalawadi, Naveen wrote:

+/* Fold X + (X / CST) * -CST to X % CST.  */
+(simplify
+ (plus (convert1? @0) (convert2? (mult (trunc_div @0 INTEGER_CST@1) INTEGER_CST@2)))
+  (if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+	&& wi::add (@1, @2) == 0)
+   (trunc_mod (convert @0) (convert @1))))

With INTEGER_CST above, the test INTEGRAL_TYPE_P might be redundant, and 
VECTOR_INTEGER_TYPE_P can never match.

+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @2))
+  (if (! FLOAT_TYPE_P (type)
+       && wi::eq_p (@1, @2))
+   (minus (bit_xor @0 @1) @1)))

I don't think FLOAT_TYPE_P can ever be true for the result of bit_and.

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

If a and 1 are vectors and b is a scalar...

+/* Simplify (X & ~Y) | (~X & Y) is X ^ Y.  */
+(simplify
+ (bit_ior (bit_and:s @0 (bit_not @1)) (bit_and:s (bit_not @2) @3))
+  (if (wi::eq_p (@0, @2)
+       && wi::eq_p (@1, @3))
+   (bit_xor @0 @3)))

I don't think we need the :s when the result of the transformation is so 
simple.

+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c (convert? @0) (convert? (bit_not @0)))
+  (convert { build_zero_cst (TREE_TYPE (@0)); }))

Can't you build 0 directly in the right type?


-- 
Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Mon, Oct 12, 2015 at 12:22 PM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> Hi Richard,
>
> Thanks for your review and useful comments.
> I will  move the future optimization patterns with all the conditions
> present in fold-const or builtins file as per your suggestions.
>
> Please find attached the patch as per your comments.
> Please review the patch and let me know if any further modifications
> are required.

+/* Fold X + (X / CST) * -CST to X % CST.  */
+(simplify
+ (plus (convert1? @0) (convert2? (mult (trunc_div @0 INTEGER_CST@1)
INTEGER_CST@2)))
+  (if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+       && wi::add (@1, @2) == 0)

when you use convert? to mimic fold-const.c behavior you have to add

        && tree_nop_conversion_p (type, TREE_TYPE (@0))

note that in this case only both or no conversion can occur so please
use convert? in both places.

+   (trunc_mod (convert @0) (convert @1))))

This applies to other uses of convert[12]?, too.

As said for the above pattern fold-const.c also handled X + (X / A) * (-A) with
A not being a constant.  Unfortunately predicate syntax can't capture
both -A and -CST but one can use

(match (xdivamulminusa @X @A)
 (mult (trunc_div @X @A) (negate @X)))
(match (xdivamulminusa @X @A)
 (mult (trunc_div @X INTEGER_CST@A) INTEGER_CST@0)
 (if (wi::add (@A, @0) == 0)))

and then

(simplify
  (plus (convert? @0) (convert? (xdivamulminusa @0 @1)))
  (if (...)
   (trunc_mod (convert @0) (convert @1))))

to avoid duplicating the pattern (though that might be more readable
in this case...)

+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @2))
+  (if (! FLOAT_TYPE_P (type)
+       && wi::eq_p (@1, @2))
+   (minus (bit_xor @0 @1) @1)))

you can't simply use wi::eq_p on random trees.  Same solution like above
can be used (or pattern duplication).

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

the conversion on @0 isn't interesting to capture, only that on
the lshift is.

+/* Fold (C1/X)*C2 into (C1*C2)/X.  */
+(simplify
+ (mult (rdiv REAL_CST@0 @1) REAL_CST@2)
+  (with
+   { tree tem = const_binop (MULT_EXPR, type, @0, @2); }
+  (if (tem && FLOAT_TYPE_P (type)
+       && flag_associative_math)
+   (rdiv (mult @0 @2) @1))))

you comuted 'tem', so use it:

    (rdiv { tem; } @1))))

The FLOAT_TYPE_P check is redundant I think and the flag_associative_math
check should be done before computing tem.

+/* Simplify (X & ~Y) | (~X & Y) is X ^ Y.  */
+(simplify
+ (bit_ior (bit_and:s @0 (bit_not @1)) (bit_and:s (bit_not @2) @3))
+  (if (wi::eq_p (@0, @2)
+       && wi::eq_p (@1, @3))
+   (bit_xor @0 @3)))

See above for handling constants and using wi::eq_p.  Looks like I
really need to make 'match' handle these kind of things.

+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c (convert? @0) (convert? (bit_not @0)))
+  (convert { build_zero_cst (TREE_TYPE (@0)); }))

please simplify to

   { build_zero_cst (type); }

directly.

+/* (-A) * (-B) -> A * B  */
+(simplify
+ (mult:c (convert? (negate @0)) (convert? (negate @1)))
+  (if ((GIMPLE && useless_type_conversion_p (type, TREE_TYPE (@0)))
+       || (GENERIC && type == TREE_TYPE (@0)))
+   (mult (convert @0) (convert @1))))

note that fold-const.c handled multiple ways of negation thus please
use the existing negate_expr_p 'match' like

(simplify
  (mult:c (convert? (negate @0)) (convert? negate_expr_p@1))
  (if ...
    (mult (convert @0) (convert (negate @1)))

also use tree_nop_conversion_p, not the GIMPLE/GENERIC variants.

Thanks,
Richard.


> The last pattern has been removed due to the discussions over it
> and a regression it caused.
> ================================================
> +/* Fold X & (X ^ Y) as X & ~Y.  */
> +(simplify
> + (bit_and:c (convert? @0) (convert? (bit_xor:c @0 @1)))
> +  (bit_and (convert @0) (convert (bit_not @1))))
> ================================================
>
> FAIL: gcc.dg/tree-ssa/vrp47.c scan-tree-dump-times vrp2 " & 1;" 0
> FAIL: gcc.dg/tree-ssa/vrp59.c scan-tree-dump-not vrp1 " & 3;"
>
> Thanks,
> Naveen

Re: Move some bit and binary optimizations in simplify and match

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 911 bytes --]

Hi Richard,

Thanks for the comments. Sorry, I was confused with handling the const and variable 
together part. Have modified them.
Also, considered that both (X & Y) can be const or variable in those cases
for which match patterns have been added.
Please let me know whether its correct or only "Y" should be both const and variable
whereas the "X" should be variable always.

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

Am learning lots of useful stuff while porting these patches. 
Thanks for all the help again.

>> Looks like I really need to make 'match' handle these kind of things.
I assume that its for bit ops, and binary operations like (A & B) and so on.
Should I try doing that part? Also, how do we know which patterns should
be const or variable or supports both?

Thanks,
Naveen

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bit-bin.patch --]
[-- Type: text/x-patch; name="bit-bin.patch", Size: 8948 bytes --]

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 b02dd03..2d73a05 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -316,6 +316,70 @@ along with GCC; see the file COPYING3.  If not see
   (coss (op @0))
    (coss @0))))
 
+/* 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 INTEGER_CST@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 INTEGER_CST@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 (@0)))
+   (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)))
+  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
+  { build_zero_cst (TREE_TYPE (@0)); }))
+
 /* X % Y is smaller than Y.  */
 (for cmp (lt ge)
  (simplify
@@ -535,6 +599,12 @@ 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 (convert? (negate @0)) (convert? negate_expr_p@1))
+  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
+   (mult (convert @0) (convert (negate @1)))))
  
 /* -(A + B) -> (-B) - A.  */
 (simplify

Re: Move some bit and binary optimizations in simplify and match

[Marc Glisse]

On Tue, 13 Oct 2015, Hurugalawadi, Naveen wrote:

> Please find attached the patch as per your comments.

(hmm, maybe you missed the email I sent with other comments?)

+(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))))

Is that true when the conversion changes from signed to unsigned? The 
existing transformation X - (X / Y) * Y appears to be broken as well.

(the version in fold-const is hard to trigger because of canonicalization, 
but it was slightly more general in that it allowed for VECTOR_CST)

+/* 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 (@0)))
+   (lshift @0 (convert @2))))

Wrong test, did you mean TREE_TYPE (@1) maybe?

-- 
Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Tue, Oct 13, 2015 at 12:52 PM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> Hi Richard,
>
> Thanks for the comments. Sorry, I was confused with handling the const and variable
> together part. Have modified them.
> Also, considered that both (X & Y) can be const or variable in those cases
> for which match patterns have been added.

Both can't be constant as (bit_and INTEGER_CST INTEGER_CST) will have been
simplified to a INTEGER_CST already.  Likewise (bit_not INTEGER_CST) will
never appear (that is the problem we are trying to solve!).

> Please let me know whether its correct or only "Y" should be both const and variable
> whereas the "X" should be variable always.
>
> Please find attached the patch as per your comments.
> Please review the patch and let me know if any further modifications
> are required.
>
> Am learning lots of useful stuff while porting these patches.
> Thanks for all the help again.
>
>>> Looks like I really need to make 'match' handle these kind of things.
> I assume that its for bit ops, and binary operations like (A & B) and so on.
> Should I try doing that part? Also, how do we know which patterns should
> be const or variable or supports both?

I was thinking about this for quite a while and didn't find a good solution on
how to implement this reliably other than basically doing the pattern
duplication
in genmatch.  Say, for

/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
(simplify
 (minus (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @1))
  (if (! FLOAT_TYPE_P (type))
   (minus (bit_xor @0 @1) @1)))

generate also

(simplify
 (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
 (if (! FLOAT_TYPE_P (type)
      && wi::eq (const_unop (BIT_NOT_EXPR, @2), @1))
  (minus (bit_xor @0 @1) @1)))

where we'd only target matches and unary ops of depth 1.

The question is whether this is really worth the effort, writing the
above explicitely
isn't too difficult.  So for your case simply do that duplication manually
(not using const_unop of course but wi:: functionality).  Sorry that I misled
you into doing this with (match (xdivamulminusa ..., etc.).  We want to minimize
the number of lines in match.pd and this doesn't really achieve this compared
to duplicating the whole pattern.

Also please take Marcs review comments into account.

+/* 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)))))

this one is ok with :s added on the rdiv

+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c (convert? @0) (convert? (bit_not @0)))
+  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
+  { build_zero_cst (TREE_TYPE (@0)); }))

this one is ok as well.

+/* (-A) * (-B) -> A * B  */
+(simplify
+ (mult:c (convert? (negate @0)) (convert? negate_expr_p@1))
+  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
+   (mult (convert @0) (convert (negate @1)))))

this one is ok with using convert1? and convert2?

Please consider splitting those three patterns out (with the suggested
adjustments and the corresponding fold-const.c changes) and committing
them separately to make the rest of the patch smaller.

Thanks,
Richard.



> Thanks,
> Naveen

Re: Move some bit and binary optimizations in simplify and match

[Marc Glisse]

On Tue, 13 Oct 2015, Richard Biener wrote:

> +/* Simplify ~X & X as zero.  */
> +(simplify
> + (bit_and:c (convert? @0) (convert? (bit_not @0)))
> +  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))

The test seems unnecessary for this specific transformation.

> +  { build_zero_cst (TREE_TYPE (@0)); }))

I'd rather build_zero_cst (type) directly.

> +/* (-A) * (-B) -> A * B  */
> +(simplify
> + (mult:c (convert? (negate @0)) (convert? negate_expr_p@1))
> +  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
> +   (mult (convert @0) (convert (negate @1)))))
>
> this one is ok with using convert1? and convert2?

Is it? Maybe if it also checked tree_nop_conversion_p for @1...

-- 
Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Tue, Oct 13, 2015 at 2:18 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Tue, 13 Oct 2015, Richard Biener wrote:
>
>> +/* Simplify ~X & X as zero.  */
>> +(simplify
>> + (bit_and:c (convert? @0) (convert? (bit_not @0)))
>> +  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
>
>
> The test seems unnecessary for this specific transformation.
>
>> +  { build_zero_cst (TREE_TYPE (@0)); }))
>
>
> I'd rather build_zero_cst (type) directly.
>
>> +/* (-A) * (-B) -> A * B  */
>> +(simplify
>> + (mult:c (convert? (negate @0)) (convert? negate_expr_p@1))
>> +  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
>> +   (mult (convert @0) (convert (negate @1)))))
>>
>> this one is ok with using convert1? and convert2?
>
>
> Is it? Maybe if it also checked tree_nop_conversion_p for @1...

Sorry, your comments are of course correct.  Neveen, please adjust
also according
to these comments.

Richard.

> --
> Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 260 bytes --]

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

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bit-bin1.patch --]
[-- Type: text/x-patch; name="bit-bin1.patch", Size: 8849 bytes --]

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

Re: Move some bit and binary optimizations in simplify and match

[Marc Glisse]

+(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.


-- 
Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

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

Re: Move some bit and binary optimizations in simplify and match

[Marc Glisse]

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.

-- 
Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

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

Re: Move some bit and binary optimizations in simplify and match

[Marc Glisse]

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.

-- 
Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 1291 bytes --]

Hi,

Thanks for all the suggestions.
Please find attached the modified patch as per your suggestions.

I had missed a mail as pointed by Marc Glisse. Now I have implemented
everything suggested.
Please review the patch and let me know if any further modifications are required.

I have some queries regarding the whole discussions along the course of
this patch.
It would be very helpful for my understanding of the code.

>> /* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
>> Likewise the fold code handles both constant and non-constant B.

How do we know that fold code handles both constant and non-constant B
and not A?

>> Fold (a * (1 << b)) into (a << b)
>> So either way I think we should only allow nop conversions
>> here (as fold-const.c did).

How do we recognize from the fold-const code that it allows only nop
conversions.

>> We want to minimize the number of lines in match.pd and this doesn't
>> really achieve this compared to duplicating the whole pattern.

Yes. Even, I have the same question to understand this better.
Is it worth and does it acheive any extra optimization after moving
it using simplify and match?

Should I have the other three patterns duplicated and implemented
or leave it in fold-const code?

Thanks,
Naveen

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bit-bin3.patch --]
[-- Type: text/x-patch; name="bit-bin3.patch", Size: 4656 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index de45a2c..1e7fbb4 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9803,20 +9803,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 +9816,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 +9858,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))
 	    {
@@ -10053,22 +10014,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 655c9ff..2e0b919 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -323,6 +323,27 @@ 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 (a * (1 << b)) into (a << b)  */
+(simplify
+ (mult:c @0 (lshift integer_onep@1 @2))
+  (if (! FLOAT_TYPE_P (type)
+       && tree_nop_conversion_p (type, TREE_TYPE (@1)))
+   (lshift @0 @2)))
+
+/* Fold (C1/X)*C2 into (C1*C2)/X.  */
+(simplify
+ (mult (rdiv:s 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 & 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 +563,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

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Thu, Oct 15, 2015 at 8:11 AM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> Hi,
>
> Thanks for all the suggestions.
> Please find attached the modified patch as per your suggestions.
>
> I had missed a mail as pointed by Marc Glisse. Now I have implemented
> everything suggested.
> Please review the patch and let me know if any further modifications are required.

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

you are missing the convert? on the lshift now, without it the
tree_nop_conversion_p check always evaluates to true.

+/* Fold (C1/X)*C2 into (C1*C2)/X.  */
+(simplify
+ (mult (rdiv:s 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)))))

this looks good.

+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c (convert? @0) (convert? (bit_not @0)))
+  { build_zero_cst (type); })

the pattern as-is is ok but note you are removing

-      /* ~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);

from fold-const.c which handles TRUTH_NOT_EXPR but logical_inverted_value
does not handle it.  I suggest to add

(match (logical_inverted_value @0)
 (truth_not @0))

where the other logical_inverted_value predicates are defined

+/* (-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)))))

this one looks ok now.

> I have some queries regarding the whole discussions along the course of
> this patch.
> It would be very helpful for my understanding of the code.

Sure.

>>> /* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
>>> Likewise the fold code handles both constant and non-constant B.
>
> How do we know that fold code handles both constant and non-constant B
> and not A?

          /* 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))

so it requires equal first operands.  First operand position means
unless the second operands
are constant (in which case the whole BIT_AND would be gone and replaced
by a constant) the first operands are non-constant due to canonicalization
rules for commutative operators.

              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))

this makes sure that mask0 == ~mask1 and thus B == B.  This
works symbolically as fold_build1 will transform (bit_not (bit_not mask0))
to mask0 as well as for constant B as fold_build1 will apply constant
folding here as well and thus the resulting two constants will be
equal.

>>> Fold (a * (1 << b)) into (a << b)
>>> So either way I think we should only allow nop conversions
>>> here (as fold-const.c did).
>
> How do we recognize from the fold-const code that it allows only nop
> conversions.

Because of

tree
fold_binary_loc (location_t loc,
             enum tree_code code, tree type, tree op0, tree op1)
{
...
  arg0 = op0;
  arg1 = op1;

  /* Strip any conversions that don't change the mode.  This is
     safe for every expression, except for a comparison expression
     because its signedness is derived from its operands.  So, in
     the latter case, only strip conversions that don't change the
     signedness.  MIN_EXPR/MAX_EXPR also need signedness of arguments
     preserved.

     Note that this is done as an internal manipulation within the
     constant folder, in order to find the simplest representation
     of the arguments so that their form can be studied.  In any
     cases, the appropriate type conversions should be put back in
     the tree that will get out of the constant folder.  */

  if (kind == tcc_comparison || code == MIN_EXPR || code == MAX_EXPR)
    {
      STRIP_SIGN_NOPS (arg0);
      STRIP_SIGN_NOPS (arg1);
    }
  else
    {
      STRIP_NOPS (arg0);
      STRIP_NOPS (arg1);
    }

STRIP_NOPS exactly does strip nop-conversions (STRIP_SIGN_NOPS as well,
but it preserves the signedness).

So all patterns looking at arg[01] are handling nop-conversions on their
outermost operands while those looking at op[01] do not.

>>> We want to minimize the number of lines in match.pd and this doesn't
>>> really achieve this compared to duplicating the whole pattern.
>
> Yes. Even, I have the same question to understand this better.
> Is it worth and does it acheive any extra optimization after moving
> it using simplify and match?

Yes, the code in fold-const.c only applies to GENERIC which means
expressions literally written in the source while match.pd will also
apply to those expressions appearing after CSE or constant folding.

> Should I have the other three patterns duplicated and implemented
> or leave it in fold-const code?

You should move them to match.pd.  It requires duplication to
handle the const vs. non-const cases the fold-const.c code handled.

Thanks,
Richard.


> Thanks,
> Naveen

Re: Move some bit and binary optimizations in simplify and match

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 673 bytes --]

Hi,

Thanks very much for your detailed explanation regarding the queries.

>> you are missing the convert? on the lshift now, without it the
>> tree_nop_conversion_p check always evaluates to true.
Done.

>> fold-const.c which handles TRUTH_NOT_EXPR but logical_inverted_value
>> does not handle it.  I suggest to add
Done.

Please find attached the modified patch as per your suggestions.

>> You should move them to match.pd.  It requires duplication to
>> handle the const vs. non-const cases the fold-const.c code handled.

Have modified patterns to handle const and non-const cases.
Will test it and post it once finished with it.

Thanks,
Naveen

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bit-bin4.patch --]
[-- Type: text/x-patch; name="bit-bin4.patch", Size: 5214 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index de45a2c..1e7fbb4 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9803,20 +9803,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 +9816,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 +9858,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))
 	    {
@@ -10053,22 +10014,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 f3813d8..1120c59 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -324,6 +324,22 @@ 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 (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 (@1)))
+   (lshift @0 @2)))
+
+/* Fold (C1/X)*C2 into (C1*C2)/X.  */
+(simplify
+ (mult (rdiv:s 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)))))
+
 /* X % Y is smaller than Y.  */
 (for cmp (lt ge)
  (simplify
@@ -543,6 +559,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
@@ -629,6 +652,8 @@ along with GCC; see the file COPYING3.  If not see
   (truth_not @0))
 
 (match (logical_inverted_value @0)
+ (truth_not @0))
+(match (logical_inverted_value @0)
  (bit_not truth_valued_p@0))
 (match (logical_inverted_value @0)
  (eq @0 integer_zerop))
@@ -646,6 +671,10 @@ along with GCC; see the file COPYING3.  If not see
  (simplify
   (op:c truth_valued_p@0 (logical_inverted_value @0))
   { constant_boolean_node (true, type); }))
+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c (convert? truth_valued_p@0) (convert? (logical_inverted_value @0)))
+  { build_zero_cst (type); })
 /* X ==/!= !X is false/true.  */
 (for op (eq ne)
  (simplify

Re: Move some bit and binary optimizations in simplify and match

[Marc Glisse]

+(match (logical_inverted_value @0)
+ (truth_not @0))

That's good.

+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c (convert? truth_valued_p@0) (convert? (logical_inverted_value @0)))
+  { build_zero_cst (type); })

That's not what Richard meant. We already have:

/* X & !X -> 0.  */
(simplify
  (bit_and:c @0 (logical_inverted_value @0))
  { build_zero_cst (type); })

which automatically benefits from your addition to logical_inverted_value 
(we might indeed want to add some convert? there though). But we still 
need what you had in your previous patch:

+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c (convert? @0) (convert? (bit_not @0)))
+  { build_zero_cst (type); })

to simplify the case where X is not a truth value.

(detail: the indentation looks off for (C1/X)*C2)

-- 
Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 252 bytes --]

Hi,

>> That's not what Richard meant. We already have:

Done. As per the comments.

Please find attached the modified patch as per your comments.

Please review them and let me know if any further modifications are required.

Thanks,
Naveen

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bit-bin5.patch --]
[-- Type: text/x-patch; name="bit-bin5.patch", Size: 5365 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index de45a2c..1e7fbb4 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9803,20 +9803,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 +9816,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 +9858,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))
 	    {
@@ -10053,22 +10014,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 f3813d8..04b6138 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -324,6 +324,27 @@ 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 (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 (@1)))
+   (lshift @0 @2)))
+
+/* Fold (C1/X)*C2 into (C1*C2)/X.  */
+(simplify
+ (mult (rdiv:s 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 & 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
@@ -543,6 +564,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
@@ -629,6 +657,8 @@ along with GCC; see the file COPYING3.  If not see
   (truth_not @0))
 
 (match (logical_inverted_value @0)
+ (truth_not @0))
+(match (logical_inverted_value @0)
  (bit_not truth_valued_p@0))
 (match (logical_inverted_value @0)
  (eq @0 integer_zerop))
@@ -637,10 +667,10 @@ along with GCC; see the file COPYING3.  If not see
 (match (logical_inverted_value @0)
  (bit_xor truth_valued_p@0 integer_truep))
 
-/* X & !X -> 0.  */
+/* X & !X or X & ~X -> 0.  */
 (simplify
  (bit_and:c @0 (logical_inverted_value @0))
- { build_zero_cst (type); })
+  { build_zero_cst (type); })
 /* X | !X and X ^ !X -> 1, , if X is truth-valued.  */
 (for op (bit_ior bit_xor)
  (simplify

Re: Move some bit and binary optimizations in simplify and match

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 208 bytes --]

Hi,

Please find attached the modified patch of duplicate patterns which were
posted in the earlier part.

Please review them and let me know if any further modifications are required.

Thanks,
Naveen

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bit-bin6.patch --]
[-- Type: text/x-patch; name="bit-bin6.patch", Size: 5332 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index de45a2c..b36e2f5 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.  */
@@ -10013,28 +9971,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;
diff --git a/gcc/match.pd b/gcc/match.pd
index f3813d8..5ee345e 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -324,6 +324,42 @@ 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.  */
+(simplify
+ (plus (convert? @0) (convert? (mult (trunc_div @0 @1) (negate @1))))
+  (if (INTEGRAL_TYPE_P (type)
+       && tree_nop_conversion_p (type, TREE_TYPE (@0)))
+   (trunc_mod (convert @0) (convert @1))))
+(simplify
+ (plus (convert? @0) (convert? (mult (trunc_div @0 INTEGER_CST@1) INTEGER_CST@2)))
+  (if (tree_nop_conversion_p (type, TREE_TYPE (@0))
+       && wi::add (@1, @2) == 0)
+   (trunc_mod (convert @0) (convert @1))))
+
+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @1))
+  (if (! FLOAT_TYPE_P (type))
+   (minus (bit_xor @0 @1) @1)))
+(simplify
+ (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
+ (if (! FLOAT_TYPE_P (type)
+      && wi::eq_p (const_unop (BIT_NOT_EXPR, TREE_TYPE (type), @2), @1))
+  (minus (bit_xor @0 @1) @1)))
+
+/* Simplify (X & ~Y) | (~X & Y) -> X ^ Y.  */
+(simplify
+ (bit_ior (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
+  (bit_xor @0 @1))
+(simplify
+ (bit_ior (bit_and:c @0 INTEGER_CST@2) (bit_and:c (bit_not @0) INTEGER_CST@1))
+  (if (wi::eq_p (const_unop (BIT_NOT_EXPR, TREE_TYPE (type), @2), @1))
+   (bit_xor @0 @1)))
+(simplify
+ (bit_ior (bit_and:c INTEGER_CST@0 (bit_not @1)) (bit_and:c (bit_not INTEGER_CST@2) @1))
+  (if (wi::eq_p (const_unop (BIT_NOT_EXPR, TREE_TYPE (type), @2), @0))
+   (bit_xor @0 @1)))
+
 /* X % Y is smaller than Y.  */
 (for cmp (lt ge)
  (simplify
@@ -637,10 +673,10 @@ along with GCC; see the file COPYING3.  If not see
 (match (logical_inverted_value @0)
  (bit_xor truth_valued_p@0 integer_truep))
 
-/* X & !X -> 0.  */
+/* X & !X or X & ~X -> 0.  */
 (simplify
  (bit_and:c @0 (logical_inverted_value @0))
- { build_zero_cst (type); })
+  { build_zero_cst (type); })
 /* X | !X and X ^ !X -> 1, , if X is truth-valued.  */
 (for op (bit_ior bit_xor)
  (simplify

Re: Move some bit and binary optimizations in simplify and match

[Marc Glisse]

+/* Fold X + (X / CST) * -CST to X % CST.  */

This one is still wrong. It is extremely similar to X-(X/CST)*CST, and the 
current version of that one in match.pd is broken, we should fix that one 
first.

+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @1))
+  (if (! FLOAT_TYPE_P (type))
+   (minus (bit_xor @0 @1) @1)))

I don't understand the point of the FLOAT_TYPE_P check.

Will we also simplify (A & B) - (A & ~B) into B - (A ^ B) ?

+(simplify
+ (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
+ (if (! FLOAT_TYPE_P (type)
+      && wi::eq_p (const_unop (BIT_NOT_EXPR, TREE_TYPE (type), @2), @1))

TREE_TYPE (type) ???

+  (minus (bit_xor @0 @1) @1)))

(just a random comment, not for your patch)
When we generalize this to vector, should that be:
operand_equal_p (const_unop (BIT_NOT_EXPR, type, @2), @1, OEP_ONLY_CONST)
or maybe
integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1))
?

+/* Simplify (X & ~Y) | (~X & Y) -> X ^ Y.  */
+(simplify
+ (bit_ior (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
+  (bit_xor @0 @1))

:c on bit_ior? It should also allow you to merge the 2 CST versions into 
one.

+ (bit_ior (bit_and:c INTEGER_CST@0 (bit_not @1)) (bit_and:c (bit_not 
INTEGER_CST@2) @1))

gcc always puts the constant last in bit_and, so
(bit_and (bit_not @1) INTEGER_CST@0)

You still have a (bit_not INTEGER_CST@2)...

-/* X & !X -> 0.  */
+/* X & !X or X & ~X -> 0.  */
  (simplify
   (bit_and:c @0 (logical_inverted_value @0))
- { build_zero_cst (type); })
+  { build_zero_cst (type); })
  /* X | !X and X ^ !X -> 1, , if X is truth-valued.  */
  (for op (bit_ior bit_xor)
   (simplify

I think that was already in your other patch, and I am not really in favor 
of the indentation change (or the comment).

-- 
Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Mon, Oct 19, 2015 at 1:14 PM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> Hi,
>
>>> That's not what Richard meant. We already have:
>
> Done. As per the comments.
>
> Please find attached the modified patch as per your comments.
>
> Please review them and let me know if any further modifications are required.

This patch is ok when bootstrapped / tested and with a proper changelog entry.

Thanks,
Richard.

> Thanks,
> Naveen

Re: Move some bit and binary optimizations in simplify and match

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 2685 bytes --]

Hi,

>> +/* Fold X + (X / CST) * -CST to X % CST.  */
>> This one is still wrong
Removed.

>> I don't understand the point of the FLOAT_TYPE_P check.
The check was there in fold-const. So, just had the same check.

>> Will we also simplify (A & B) - (A & ~B) into B - (A ^ B) ?
Done.

>> or maybe integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1))
Done.

>> :c on bit_ior? It should also allow you to merge the 2 CST versions into one.
Had it. But due to the error on "logical_inverted_value"; confused it with
this pattern and had duplicated it. 

>> I am not really in favor of the indentation change (or the comment).
Done.

>> This patch is ok when bootstrapped / tested and with a proper changelog entry.
Regression tested on X86_64 with no extra failures.

2015-10-20  Richard Biener  <rguenther@suse.de>
                     Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>

        * fold-const.c (fold_binary_loc) : Move (-A) * (-B) -> A * B
        to match.pd.
        Move (a * (1 << b)) is (a << b) to match.pd.
        Move convert (C1/X)*C2 into (C1*C2)/X to match.pd.
        Move ~X & X, (X == 0) & X, and !X & X are zero to match.pd.
        Move X & ~X , X & (X == 0), and X & !X are zero to match.pd.

        * match.pd (mult:c @0 (convert? (lshift integer_onep@1 @2))):
        New simplifier.
        (mult (rdiv:s REAL_CST@0 @1) REAL_CST@2): New simplifier.
        (bit_and:c (convert? @0) (convert? (bit_not @0))): New simplifier.
        (bit_ior (bit_and:s @0 (bit_not:s @1)) (bit_and:s (bit_not:s @0) @1))
        : New simplifier.
        (mult:c (convert1? (negate @0)) (convert2? negate_expr_p@1)):
        New simplifier.
        (match (logical_inverted_value @0) (truth_not @0)) : New Predicate.



2015-10-20  Richard Biener  <rguenther@suse.de>
                     Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>

        * fold-const.c (fold_binary_loc) : Move Fold (A & ~B) - (A & B) 
        into (A ^ B) - B to match.pd
        Move (X & ~Y) | (~X & Y) is X ^ Y to match.pd.

        * match.pd (minus (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @1)):
        New simplifier.
        (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1)):
        New simplifier.
        (minus (bit_and:s @0 @1) (bit_and:s @0 (bit_not @1))): New simplifier.
        (minus (bit_and:s @0 INTEGER_CST@1) (bit_and:s @0 INTEGER_CST@2)):
        New simplifier.
        (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1)):
        New simplifier.
        (bit_ior:c (bit_and @0 INTEGER_CST@2) (bit_and (bit_not @0) INTEGER_CST@1)):
        New simplifier.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bit-bin7.patch --]
[-- Type: text/x-patch; name="bit-bin7.patch", Size: 3718 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index de45a2c..3544949 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9692,28 +9692,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.  */
@@ -10013,28 +9991,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;
diff --git a/gcc/match.pd b/gcc/match.pd
index f3813d8..4bb1cc2 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -324,6 +324,33 @@ 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 (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @1))
+  (minus (bit_xor @0 @1) @1))
+(simplify
+ (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
+ (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
+  (minus (bit_xor @0 @1) @1)))
+
+/* Fold (A & B) - (A & ~B) into B - (A ^ B).  */
+(simplify
+ (minus (bit_and:s @0 @1) (bit_and:s @0 (bit_not @1)))
+  (minus @1 (bit_xor @0 @1)))
+(simplify
+ (minus (bit_and:s @0 INTEGER_CST@1) (bit_and:s @0 INTEGER_CST@2))
+ (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
+  (minus @1 (bit_xor @0 @1))))
+
+/* Simplify (X & ~Y) | (~X & Y) -> X ^ Y.  */
+(simplify
+ (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
+  (bit_xor @0 @1))
+(simplify
+ (bit_ior:c (bit_and @0 INTEGER_CST@2) (bit_and (bit_not @0) INTEGER_CST@1))
+  (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
+   (bit_xor @0 @1)))
+
 /* X % Y is smaller than Y.  */
 (for cmp (lt ge)
  (simplify
@@ -543,7 +570,7 @@ 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) -> (-B) - A.  */
 (simplify
  (negate (plus:c @0 negate_expr_p@1))

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Tue, Oct 20, 2015 at 8:46 AM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> Hi,
>
>>> +/* Fold X + (X / CST) * -CST to X % CST.  */
>>> This one is still wrong
> Removed.
>
>>> I don't understand the point of the FLOAT_TYPE_P check.
> The check was there in fold-const. So, just had the same check.
>
>>> Will we also simplify (A & B) - (A & ~B) into B - (A ^ B) ?
> Done.
>
>>> or maybe integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1))
> Done.
>
>>> :c on bit_ior? It should also allow you to merge the 2 CST versions into one.
> Had it. But due to the error on "logical_inverted_value"; confused it with
> this pattern and had duplicated it.
>
>>> I am not really in favor of the indentation change (or the comment).
> Done.
>
>>> This patch is ok when bootstrapped / tested and with a proper changelog entry.
> Regression tested on X86_64 with no extra failures.

+(simplify
+ (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
+ (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
+  (minus (bit_xor @0 @1) @1)))

use if (wi::bit_and (@2, @1) == 0)

and instead of the 2nd group

+/* Fold (A & B) - (A & ~B) into B - (A ^ B).  */
+(simplify
+ (minus (bit_and:s @0 @1) (bit_and:s @0 (bit_not @1)))
+  (minus @1 (bit_xor @0 @1)))
+(simplify
+ (minus (bit_and:s @0 INTEGER_CST@1) (bit_and:s @0 INTEGER_CST@2))
+ (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
+  (minus @1 (bit_xor @0 @1))))

place a :c on the minus of the one not matching INTEGER_CSTs.

+(simplify
+ (bit_ior:c (bit_and @0 INTEGER_CST@2) (bit_and (bit_not @0) INTEGER_CST@1))
+  (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
+   (bit_xor @0 @1)))

see above, use wi::bit_and instead

Otherwise looks ok to me.

RIchard.




> 2015-10-20  Richard Biener  <rguenther@suse.de>
>                      Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>
>
>         * fold-const.c (fold_binary_loc) : Move (-A) * (-B) -> A * B
>         to match.pd.
>         Move (a * (1 << b)) is (a << b) to match.pd.
>         Move convert (C1/X)*C2 into (C1*C2)/X to match.pd.
>         Move ~X & X, (X == 0) & X, and !X & X are zero to match.pd.
>         Move X & ~X , X & (X == 0), and X & !X are zero to match.pd.
>
>         * match.pd (mult:c @0 (convert? (lshift integer_onep@1 @2))):
>         New simplifier.
>         (mult (rdiv:s REAL_CST@0 @1) REAL_CST@2): New simplifier.
>         (bit_and:c (convert? @0) (convert? (bit_not @0))): New simplifier.
>         (bit_ior (bit_and:s @0 (bit_not:s @1)) (bit_and:s (bit_not:s @0) @1))
>         : New simplifier.
>         (mult:c (convert1? (negate @0)) (convert2? negate_expr_p@1)):
>         New simplifier.
>         (match (logical_inverted_value @0) (truth_not @0)) : New Predicate.
>
>
>
> 2015-10-20  Richard Biener  <rguenther@suse.de>
>                      Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>
>
>         * fold-const.c (fold_binary_loc) : Move Fold (A & ~B) - (A & B)
>         into (A ^ B) - B to match.pd
>         Move (X & ~Y) | (~X & Y) is X ^ Y to match.pd.
>
>         * match.pd (minus (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @1)):
>         New simplifier.
>         (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1)):
>         New simplifier.
>         (minus (bit_and:s @0 @1) (bit_and:s @0 (bit_not @1))): New simplifier.
>         (minus (bit_and:s @0 INTEGER_CST@1) (bit_and:s @0 INTEGER_CST@2)):
>         New simplifier.
>         (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1)):
>         New simplifier.
>         (bit_ior:c (bit_and @0 INTEGER_CST@2) (bit_and (bit_not @0) INTEGER_CST@1)):
>         New simplifier.

Re: Move some bit and binary optimizations in simplify and match

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 347 bytes --]

Hi,

>> use if (wi::bit_and (@2, @1) == 0)
Done.

>> and instead of the 2nd group
>> place a :c on the minus of the one not matching INTEGER_CSTs.
Done.
Just curious to know whether ":c" act as commutative operation in the input as
well as output in this case?

Regression tested without any extra failures on X86_64.

Thanks,
Naveen

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bit-bin7.patch --]
[-- Type: text/x-patch; name="bit-bin7.patch", Size: 3318 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index de45a2c..3544949 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9692,28 +9692,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.  */
@@ -10013,28 +9991,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;
diff --git a/gcc/match.pd b/gcc/match.pd
index 98f4b2c..98b8862 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -325,6 +325,24 @@ 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 (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus:c (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @1))
+  (minus (bit_xor @0 @1) @1))
+(simplify
+ (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
+ (if (wi::bit_and (@2, @1) == 0)
+  (minus (bit_xor @0 @1) @1)))
+
+/* Simplify (X & ~Y) | (~X & Y) -> X ^ Y.  */
+(simplify
+ (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
+  (bit_xor @0 @1))
+(simplify
+ (bit_ior:c (bit_and @0 INTEGER_CST@2) (bit_and (bit_not @0) INTEGER_CST@1))
+ (if (wi::bit_and (@2, @1) == 0)
+  (bit_xor @0 @1)))
+
 /* X % Y is smaller than Y.  */
 (for cmp (lt ge)
  (simplify
@@ -544,7 +562,7 @@ 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) -> (-B) - A.  */
 (simplify
  (negate (plus:c @0 negate_expr_p@1))

Re: Move some bit and binary optimizations in simplify and match

[Marc Glisse]

On Tue, 20 Oct 2015, Richard Biener wrote:

> On Tue, Oct 20, 2015 at 8:46 AM, Hurugalawadi, Naveen
> <Naveen.Hurugalawadi@caviumnetworks.com> wrote:
>> Hi,
>>
>>>> +/* Fold X + (X / CST) * -CST to X % CST.  */
>>>> This one is still wrong
>> Removed.
>>
>>>> I don't understand the point of the FLOAT_TYPE_P check.
>> The check was there in fold-const. So, just had the same check.
>>
>>>> Will we also simplify (A & B) - (A & ~B) into B - (A ^ B) ?
>> Done.
>>
>>>> or maybe integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1))
>> Done.
>>
>>>> :c on bit_ior? It should also allow you to merge the 2 CST versions into one.
>> Had it. But due to the error on "logical_inverted_value"; confused it with
>> this pattern and had duplicated it.
>>
>>>> I am not really in favor of the indentation change (or the comment).
>> Done.
>>
>>>> This patch is ok when bootstrapped / tested and with a proper changelog entry.
>> Regression tested on X86_64 with no extra failures.
>
> +(simplify
> + (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
> + (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
> +  (minus (bit_xor @0 @1) @1)))
>
> use if (wi::bit_and (@2, @1) == 0)

I believe the original transformation required @1 and @2 to be bit_not
of each other, so this might not work. He had a suitable test using wi,
it is my fault he changed it (sorry for not being clear enough that my
remark wasn't meant as a patch). The reason was so we could change
INTEGER_CST to CONSTANT_CLASS_P and handle vectors.

> and instead of the 2nd group
>
> +/* Fold (A & B) - (A & ~B) into B - (A ^ B).  */
> +(simplify
> + (minus (bit_and:s @0 @1) (bit_and:s @0 (bit_not @1)))
> +  (minus @1 (bit_xor @0 @1)))
> +(simplify
> + (minus (bit_and:s @0 INTEGER_CST@1) (bit_and:s @0 INTEGER_CST@2))
> + (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
> +  (minus @1 (bit_xor @0 @1))))
>
> place a :c on the minus of the one not matching INTEGER_CSTs.

Will that really work?

-- 
Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Wed, Oct 21, 2015 at 8:48 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Tue, 20 Oct 2015, Richard Biener wrote:
>
>> On Tue, Oct 20, 2015 at 8:46 AM, Hurugalawadi, Naveen
>> <Naveen.Hurugalawadi@caviumnetworks.com> wrote:
>>>
>>> Hi,
>>>
>>>>> +/* Fold X + (X / CST) * -CST to X % CST.  */
>>>>> This one is still wrong
>>>
>>> Removed.
>>>
>>>>> I don't understand the point of the FLOAT_TYPE_P check.
>>>
>>> The check was there in fold-const. So, just had the same check.
>>>
>>>>> Will we also simplify (A & B) - (A & ~B) into B - (A ^ B) ?
>>>
>>> Done.
>>>
>>>>> or maybe integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1))
>>>
>>> Done.
>>>
>>>>> :c on bit_ior? It should also allow you to merge the 2 CST versions
>>>>> into one.
>>>
>>> Had it. But due to the error on "logical_inverted_value"; confused it
>>> with
>>> this pattern and had duplicated it.
>>>
>>>>> I am not really in favor of the indentation change (or the comment).
>>>
>>> Done.
>>>
>>>>> This patch is ok when bootstrapped / tested and with a proper changelog
>>>>> entry.
>>>
>>> Regression tested on X86_64 with no extra failures.
>>
>>
>> +(simplify
>> + (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
>> + (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
>> +  (minus (bit_xor @0 @1) @1)))
>>
>> use if (wi::bit_and (@2, @1) == 0)
>
>
> I believe the original transformation required @1 and @2 to be bit_not
> of each other, so this might not work.

Oh, sorry - indeed.  It fails for @2 == @1 == 0.  So using bit_xor
is required or simply wi::bit_not (@2) == @1.

> He had a suitable test using wi,
> it is my fault he changed it (sorry for not being clear enough that my
> remark wasn't meant as a patch). The reason was so we could change
> INTEGER_CST to CONSTANT_CLASS_P and handle vectors.

I realized that but until that happens we should stick with the faster and
simpler wi:: interface.  The tree interface will allocate extra garbage
for computing the BIT_XOR_EXPR even when no transform is done
thus I believe we'd want a integer_bit_not_of_the_other () function
avoiding extra tree garbage in the end.

>> and instead of the 2nd group
>>
>> +/* Fold (A & B) - (A & ~B) into B - (A ^ B).  */
>> +(simplify
>> + (minus (bit_and:s @0 @1) (bit_and:s @0 (bit_not @1)))
>> +  (minus @1 (bit_xor @0 @1)))
>> +(simplify
>> + (minus (bit_and:s @0 INTEGER_CST@1) (bit_and:s @0 INTEGER_CST@2))
>> + (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
>> +  (minus @1 (bit_xor @0 @1))))
>>
>> place a :c on the minus of the one not matching INTEGER_CSTs.
>
>
> Will that really work?

Yes.  The :c will create a 2nd pattern with the ops of the minus swapped, thus

/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
(simplify
 (minus:c (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @1))
  (minus (bit_xor @0 @1) @1))
(simplify
 (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
 (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
  (minus (bit_xor @0 @1) @1)))

will implicitely add

(simplify
 (minus (bit_and:s @0 @1) (bit_and:s @0 (bit_not @1))
  (minus (bit_xor @0 @1) @1))

hmm, but that isn't correct for @1 == 0?  So the fold-const.c code is incorrect.

Note it doesn't trigger for

int foo (int a, int b)
{
  return (a & ~b) - (a & b);
}

because canonicalization makes it appear as (~b & a) - (a & b) and the
fold-const.c
fails to have a :c on the bit_and with the bit_not (you too).

Note how the fold-const.c code doesn't care about where the ~ is placed (and for
constants there isn't any explicit ~ anyway).

The code triggers on

int foo (int a, int b)
{
  return ((a+1) & ~b) - ((a+1) & b);
}
int bar (int a, int b)
{
  return ((a+1) & b) - ((a+1) & ~b);
}

and correctly it seems.  The key is that it explicitely uses bit_not
of the first
ops b or ~b while the pattern tries to be clever and re-uses the present
bit_not - _this_ doesn't play well with using :c.

Still the duplicate INTEGER_CST pattern is not necessary.

So I suggest to modify your patch to do

+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:cs @0 (bit_not @1)) (bit_and:s @0 @1))
+  (minus (bit_xor @0 @1) @1))
+(simplify
+ (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
+ (if (wi::bit_not (@2) == @1)
+  (minus (bit_xor @0 @1) @1)))
+
+/* Fold (A & B) - (A & ~B) into B - (A ^ B).  */
+(simplify
+ (minus (bit_and:s @0 @1) (bit_and:cs @0 (bit_not @1)))
+  (minus @1 (bit_xor @0 @1)))

Richard.

>
> --
> Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 164 bytes --]

Hi,

>> So I suggest to modify your patch to do
Done.

Please find attached the modified patch.

Regression tested successfully on X86_64.

Thanks,
Naveen

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bit-bin7.patch --]
[-- Type: text/x-patch; name="bit-bin7.patch", Size: 3189 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 1e7fbb4..23c6fa9 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9692,28 +9692,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.  */
@@ -9974,28 +9952,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;
diff --git a/gcc/match.pd b/gcc/match.pd
index 83dc7ad..0fb6115 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -346,6 +346,29 @@ along with GCC; see the file COPYING3.  If not see
  (bit_and:c (convert? @0) (convert? (bit_not @0)))
   { build_zero_cst (type); })
 
+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:cs @0 (bit_not @1)) (bit_and:s @0 @1))
+  (minus (bit_xor @0 @1) @1))
+(simplify
+ (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
+ (if (wi::bit_not (@2) == @1)
+  (minus (bit_xor @0 @1) @1)))
+
+/* Fold (A & B) - (A & ~B) into B - (A ^ B).  */
+(simplify
+ (minus (bit_and:s @0 @1) (bit_and:cs @0 (bit_not @1)))
+  (minus @1 (bit_xor @0 @1)))
+
+/* Simplify (X & ~Y) | (~X & Y) -> X ^ Y.  */
+(simplify
+ (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
+  (bit_xor @0 @1))
+(simplify
+ (bit_ior:c (bit_and @0 INTEGER_CST@2) (bit_and (bit_not @0) INTEGER_CST@1))
+ (if (wi::bit_not (@2) == @1)
+  (bit_xor @0 @1)))
+
 /* X % Y is smaller than Y.  */
 (for cmp (lt ge)
  (simplify

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Fri, Oct 23, 2015 at 6:29 AM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> Hi,
>
>>> So I suggest to modify your patch to do
> Done.
>
> Please find attached the modified patch.
>
> Regression tested successfully on X86_64.

Ok.

Thanks,
Richard.

> Thanks,
> Naveen

Re: Move some bit and binary optimizations in simplify and match

[Marc Glisse]

On Fri, 23 Oct 2015, Hurugalawadi, Naveen wrote:

+ (minus (bit_and:cs @0 (bit_not @1)) (bit_and:s @0 @1))

I am not sure why we have :c on one bit_and but not the other.

+ (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))

Here on the other hand, I believe the :c on bit_ior is redundant.

-- 
Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Sat, Oct 24, 2015 at 11:15 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Fri, 23 Oct 2015, Hurugalawadi, Naveen wrote:
>
> + (minus (bit_and:cs @0 (bit_not @1)) (bit_and:s @0 @1))
>
> I am not sure why we have :c on one bit_and but not the other.

Clearly an omission.

> + (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
>
> Here on the other hand, I believe the :c on bit_ior is redundant.

Yes.  It's somewhat twisty ;)  I wonder why it doesn't get you a genmatch
warning for duplicate patterns though.  A it does:

test.pd:2:3 warning: duplicate pattern
 (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
  ^
test.pd:2:3 warning: previous pattern defined here
 (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
  ^
(BIT_IOR_EXPR (BIT_AND_EXPR (BIT_NOT_EXPR @0) @1) (BIT_AND_EXPR @0
(BIT_NOT_EXPR @1)))

so please watch out for them when building.

Richard.

>
> --
> Marc Glisse

Re: Move some bit and binary optimizations in simplify and match

[Richard Biener]

On Mon, Oct 26, 2015 at 10:26 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Sat, Oct 24, 2015 at 11:15 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> On Fri, 23 Oct 2015, Hurugalawadi, Naveen wrote:
>>
>> + (minus (bit_and:cs @0 (bit_not @1)) (bit_and:s @0 @1))
>>
>> I am not sure why we have :c on one bit_and but not the other.
>
> Clearly an omission.
>
>> + (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
>>
>> Here on the other hand, I believe the :c on bit_ior is redundant.
>
> Yes.  It's somewhat twisty ;)  I wonder why it doesn't get you a genmatch
> warning for duplicate patterns though.  A it does:
>
> test.pd:2:3 warning: duplicate pattern
>  (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
>   ^
> test.pd:2:3 warning: previous pattern defined here
>  (bit_ior:c (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
>   ^
> (BIT_IOR_EXPR (BIT_AND_EXPR (BIT_NOT_EXPR @0) @1) (BIT_AND_EXPR @0
> (BIT_NOT_EXPR @1)))
>
> so please watch out for them when building.

I'm testing a patch to fix both issues.

Richard.

> Richard.
>
>>
>> --
>> Marc Glisse