Added a new transformation " (sub (or A, B) (and A, B)) --> (xor A, B) "

[sonamkumari]

Summary

Hi All,

The patch does the following transformation :

(sub (or A, B) (and A, B)) --> (xor A, B)

Z3 Link : http://rise4fun.com/Z3/oeyxv

Please help in reviewing it.

Regards,
Sonam.

[silvas]

Where did you see this pattern come up?

[sonamkumari]

Hi Sean,

Thanks for reviewing the patch.Similar kind of pattern optimizations have been added in visitAdd().

Regards,
Sonam.

[sonamkumari]

Gentle Ping !

[sonamkumari]

Gentle Ping!

The patch won't take much time.

Regards,
Sonam.

[asl]

You still have not answered to Sean's question, namely, which
applications would benefit from this transformation.

[sonamkumari]

Hi Anton,

Thanks for your comments.
While I was going through other patches, I came across D5719 patch and the discussions over these kind of patches.
So, I guess such expressions can be included.

Kindly provide your feedback.

Regards,
Sonam.

[asl]

The question still applies (and actually is very in-line with Hal's comments in D5719) - you need to provide some evidence that such pattern indeed happens in practice (why it's so hard to count how many times it happens in test-suite? after more than month?). And it's not some random stuff which you simple want to commit in due to some reason you do not want to share with us.

[hfinkel]

• Original Message -----

From: "Anton Korobeynikov" <[e-mail]>
To: "sonam kumari" <[e-mail]>, "suyog sarda" <[e-mail]>, "david majnemer"
<[e-mail]>, [e-mail], [e-mail]
Cc: [e-mail], [e-mail], [e-mail]
Sent: Friday, November 7, 2014 12:54:49 AM
Subject: Re: [PATCH] Added a new transformation " (sub (or A, B) (and A, B)) --> (xor A, B) "

The question still applies (and actually is very in-line with Hal's
comments in D5719

Just to be clear, I think these (three nodes -> one node) transformations, which don't rely on calls to ValueTracking, should all be added (because, in my experience working on a superoptimizer, they essentially all happen eventually and lacking them leads to surprising behavior in combination with other optimizations).

However, that having been said, it is a perfectly reasonable question to ask what motivated this particular patch? How did you see this? The answer to this question might motivate other work, allow us to better understand the results of other optimizations, etc. and so I still believe that understanding the motivation is important.

Thanks again,
Hal

) - you need to provide some evidence that such
pattern indeed happens in practice (why it's so hard to count how
many times it happens in test-suite? after more than month?). And
it's not some random stuff which you simple want to commit in due to
some reason you do not want to share with us.

http://reviews.llvm.org/D5720

[silvas]

Upthread Suyog mentions a "similar" transformation in visitAdd, which was
added in r155674 referencing a rdar. I'm not sure how Suyog got from that
transformation to this one though (a script? seems difficult to deduce).

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) ||
         match(Op1, m_Add(m_Value(Y), m_Specific(Op0))))
       return BinaryOperator::CreateNeg(Y);
 
     // (X-Y)-X == -Y
     if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
       return BinaryOperator::CreateNeg(Y);
   }
 
+  // (sub (or A, B) (and A, B)) --> (xor A, B)
+  {
+    Value *A = nullptr, *B = nullptr;
+    if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
+        (match(Op0, m_Or(m_Specific(A), m_Specific(B))) ||
+         match(Op0, m_Or(m_Specific(B), m_Specific(A)))))
+      return BinaryOperator::CreateXor(A, B);
+  }
+
   if (Op1->hasOneUse()) {
     Value *X = nullptr, *Y = nullptr, *Z = nullptr;
     Constant *C = nullptr;
     Constant *CI = nullptr;
 
     // (X - (Y - Z))  -->  (X + (Z - Y)).
     if (match(Op1, m_Sub(m_Value(Y), m_Value(Z))))
       return BinaryOperator::CreateAdd(Op0,

test/Transforms/InstCombine/sub.ll

 
 define i32 @test44(i32 %x) {
   %sub = sub nsw i32 %x, 32768
   ret i32 %sub
 ; CHECK-LABEL: @test44(
 ; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 %x, -32768
 ; CHECK: ret i32 [[ADD]]
 }
+
+define i32 @test45(i32 %x, i32 %y) {
+ %or = or i32 %x, %y
+ %and = and i32 %x, %y
+ %sub = sub i32 %or, %and
+ ret i32 %sub
+; CHECK-LABEL: @test45(
+; CHECK-NEXT: %sub = xor i32 %x, %y
+; CHECK:ret i32 %sub
+}