[InstCombineAddSub] Added the transformation - "sub (or A B) (xor A B) -> (and A B)"

[ankur29.garg]

Summary

Hi,
The following patch implements the tranformation sub (or A B) (xor A B) -> (and A B). It is similar to the one added in visitAdd()

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

Please help in reviewing it.

Thanks.
Ankur

[ankur29.garg]

Gentle Ping!

[majnemer]

This canonicalization seems unlikely to ever fire on code in the wild.

[ankur29.garg]

Hi David,

Actually, similar tranformation is already present in the VisitAdd() function for add operation.

[majnemer]

InstCombine is not supposed to handle every possible just because it is theoretically possible case. It's engineered to be a series of engineering tradeoffs. I don't know what the history of the similar transform is in VisitAdd, it's possible that it wasn't added in a principled way.

If we were to arbitrarily add patterns, we would eventually make InstCombine cripplingly slow.

[ankur29.garg]

Hi David,

Thanks for the comments.
You are right. I think I should run LLVM test suite and find out how many times, does this case actually arise.

Thanks.

[hfinkel]

• Original Message -----

From: "David Majnemer" <[e-mail]>
To: "ankur29 garg" <[e-mail]>, [e-mail], "suyog sarda" <[e-mail]>, "david
majnemer" <[e-mail]>
Cc: [e-mail]
Sent: Saturday, October 18, 2014 4:47:12 AM
Subject: Re: [PATCH] [InstCombineAddSub] Added the transformation - "sub (or A B) (xor A B) -> (and A B)"

InstCombine is not supposed to handle every possible just because it
is theoretically possible case. It's engineered to be a series of
engineering tradeoffs. I don't know what the history of the similar
transform is in VisitAdd, it's possible that it wasn't added in a
principled way.

If we were to arbitrarily add patterns, we would eventually make
InstCombine cripplingly slow.

To be honest, I think this position is unhelpful. A few thoughts:

• In my experience (derived from my work on an instruction-level superoptimizer), it is really hard to predict what patterns will occur in practice -- and given knowledge of certain bits from switch statements, enums (range metadata), etc. combined with LLVM's canonicalization in terms of large integers, and several other factors, lead to many patterns that I would consider strange, and not-uncommonly in performance-sensitive regions of code.
• We (obviously) should not engage in premature optimization -- I've seen no evidence that matching these kinds of patterns in InstCombine contributes a significant portion of its running time. And until such evidence is presented, we should not make statements about expense (there is no complexity argument here). In any case, looking at combinations of three binary operators, are there any more than a few hundred that could simplify in any reasonable sense? Probably not even that many. I see no reason we should not handle them all.
• For simplifications that require certain bits to be known, calls into ValueTracking can be expensive, but making duplicate calls into ValueTracking is a separate issue that can be fixed if it becomes important.
• I feel that, in the past, the real engineering tradeoff was slightly different: it used to be difficult to prove the transformations correct. As a result, there was a significant possibility of bugs being introduced by each of these transformations, and it made more sense to limit them. As you know, this is no longer anywhere near as true as it was: we now have good tools to verify these transformations.

Thanks again,
Hal

http://reviews.llvm.org/D5719

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[hfinkel]

• Original Message -----

From: "Hal Finkel" <[e-mail]>
To: [e-mail]
Cc: "ankur29 garg" <[e-mail]>, "suyog sarda" <[e-mail]>, [e-mail]
Sent: Saturday, October 18, 2014 11:37:40 PM
Subject: Re: [PATCH] [InstCombineAddSub] Added the transformation - "sub (or A B) (xor A B) -> (and A B)"

• Original Message -----

From: "David Majnemer" <[e-mail]>
To: "ankur29 garg" <[e-mail]>,
[e-mail], "suyog sarda" <[e-mail]>,
"david
majnemer" <[e-mail]>
Cc: [e-mail]
Sent: Saturday, October 18, 2014 4:47:12 AM
Subject: Re: [PATCH] [InstCombineAddSub] Added the transformation -
"sub (or A B) (xor A B) -> (and A B)"

InstCombine is not supposed to handle every possible just because
it
is theoretically possible case. It's engineered to be a series of
engineering tradeoffs. I don't know what the history of the
similar
transform is in VisitAdd, it's possible that it wasn't added in a
principled way.

If we were to arbitrarily add patterns, we would eventually make
InstCombine cripplingly slow.

To be honest, I think this position is unhelpful. A few thoughts:

• In my experience (derived from my work on an instruction-level superoptimizer), it is really hard to predict what patterns will occur in practice -- and given knowledge of certain bits from switch statements, enums (range metadata), etc. combined with LLVM's canonicalization in terms of large integers, and several other factors, lead to many patterns that I would consider strange, and not-uncommonly in performance-sensitive regions of code.

To add another anecdote, just when I thought I had classified the kinds of patterns that were occurring in practice, I started looking at instrumented code (address sanitizer, etc.), and I learned that I had a lot left to do.

-Hal

• We (obviously) should not engage in premature optimization -- I've seen no evidence that matching these kinds of patterns in InstCombine contributes a significant portion of its running time. And until such evidence is presented, we should not make statements about expense (there is no complexity argument here). In any case, looking at combinations of three binary operators, are there any more than a few hundred that could simplify in any reasonable sense? Probably not even that many. I see no reason we should not handle them all.
• For simplifications that require certain bits to be known, calls into ValueTracking can be expensive, but making duplicate calls into ValueTracking is a separate issue that can be fixed if it becomes important.
• I feel that, in the past, the real engineering tradeoff was slightly different: it used to be difficult to prove the transformations correct. As a result, there was a significant possibility of bugs being introduced by each of these transformations, and it made more sense to limit them. As you know, this is no longer anywhere near as true as it was: we now have good tools to verify these transformations.

Thanks again,
Hal

http://reviews.llvm.org/D5719

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[majnemer]

LGTM

[majnemer]

Commited as rL220162.

[ankur29.garg]

Hi David,
Thanks for reviewing the patch.

Although, the link to the commit rL220162 seems to be of another patch. Please update it.

Thanks.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(LHS, m_Select(m_Value(C1), m_Value(A1), m_Value(B1))) &&
       if (C1 == C2) {
         Constant *Z1=nullptr, *Z2=nullptr;
         Value *A, *B, *C=C1;
         if (match(A1, m_AnyZero()) && match(B2, m_AnyZero())) {
             Z1 = dyn_cast<Constant>(A1); A = A2;
             Z2 = dyn_cast<Constant>(B2); B = B1;
         } else if (match(B1, m_AnyZero()) && match(A2, m_AnyZero())) {
             Z1 = dyn_cast<Constant>(B1); B = B2;
-            Z2 = dyn_cast<Constant>(A2); A = A1; 
+            Z2 = dyn_cast<Constant>(A2); A = A1;
         }
-        
-        if (Z1 && Z2 && 
-            (I.hasNoSignedZeros() || 
+        if (Z1 && Z2 &&
+            (I.hasNoSignedZeros() ||
              (Z1->isNegativeZeroValue() && Z2->isNegativeZeroValue()))) {
           return SelectInst::Create(C, A, B);
         }
       }
     }
   }
 
   if (I.hasUnsafeAlgebra()) {
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) (xor A, B)) --> (and A, B)
+  {
+    Value *A = nullptr, *B = nullptr;
+    if (match(Op1, m_Xor(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::CreateAnd(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
+  %xor = xor i32 %x, %y
+  %sub = sub i32 %or, %xor
+  ret i32 %sub
+; CHECK-LABEL: @test45(
+; CHECK-NEXT: %sub = and i32 %x, %y
+; CHECK: ret i32 %sub
+}