[Instcombine/InstSimplify] Move optimization from instcombine to instsimplify

[rahul.jain]

Summary

Hi all,

This patch moves the following optimization from visitOr to SimplifyOrInst.
(A & C1)|(B & C2)
If we have: ((V + N) & C1) | (V & C2)
.. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0.

This follows the statement that: InstComb optimization which do not create new instructions should
be moved to InstructionSimplify.

Suyog and myself have planned to come up with more such refactoring patches as and when we
encounter possible cases in InstComb which should be moved to InstSimplify.

Any suggestions/help/pointers on the same will be very much appreciated.

Please help review this patch.

Thanks,
Rahul

[rahul.jain]

gentle ping.

Inputs on this would be helpful. Is this heading in the
right direction?

Thanks,
Rahul

[nicholas]

This needs a test to show what it does. There is a change in behaviour to be tested, opt -instsimplify will start doing something it didn't use to and opt -instcombine should stay the same.

lib/Analysis/InstructionSimplify.cpp

1630

Please sink this down to where they're first assigned (lines 1634, 1635).

1640

Fold this into the if-statement on line 1636 to reduce indentation one level.

[rahul.jain]

Hi Nick,

Thanks a lot for the review.
Updated patch as per your comment.

1. Sinked variable declarations next to their usage.
2. Folded if statements.
3. Added testcase.

Please help review the same.
If it looks good to you, please commit it for me.
Soon will ask for commit access.

Thanks,
Rahul

[nlewycky]

I made a few adjustments:

+ ConstantInt *C1 = nullptr, *C2 = nullptr;
+ C1 = dyn_cast<ConstantInt>(C);
+ C2 = dyn_cast<ConstantInt>(D);
became
+ ConstantInt *C1 = dyn_cast<ConstantInt>(C);
+ ConstantInt *C2 = dyn_cast<ConstantInt>(D);

I removed the dead initialization of V1 and V2 to nullptr. They aren't used
unless they match succeeds.

Your test had @test1 and @test3, renamed @test3 to @test2.

Changed test to use FileCheck instead of grep. I'm aware this is what
InstCombine/apint-or{1,2}.ll does, but it's an older style and FileCheck is
preferred.

Moved the whole-file comments that apply to each function ("the first
test..." and "the second test...") next to the functions they apply to.

Committed in r211252. Thanks!

Nick

[rahul.jain]

Committed as r211252 by Nick.

Thanks!

lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q,
 
   // If the operation is with the result of a select instruction, check whether
   // operating on either branch of the select always yields the same value.
   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q,
                                          MaxRecurse))
       return V;
 
+  // (A & C)|(B & D)
+  Value *C = nullptr, *D = nullptr;
+  if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
+      match(Op1, m_And(m_Value(B), m_Value(D)))) {
+    ConstantInt *C1 = nullptr, *C2 = nullptr;
+    C1 = dyn_cast<ConstantInt>(C);
+    C2 = dyn_cast<ConstantInt>(D);
+    if (C1 && C2 && (C1->getValue() == ~C2->getValue())) {
+      // (A & C1)|(B & C2)
+      // If we have: ((V + N) & C1) | (V & C2)
+      // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0
+      // replace with V+N.
+      Value *V1 = nullptr, *V2 = nullptr;
+      if ((C2->getValue() & (C2->getValue() + 1)) == 0 && // C2 == 0+1+
+          match(A, m_Add(m_Value(V1), m_Value(V2)))) {
+        // Add commutes, try both ways.
+        if (V1 == B && MaskedValueIsZero(V2, C2->getValue()))
+          return A;
+        if (V2 == B && MaskedValueIsZero(V1, C2->getValue()))
+          return A;
+      }
+      // Or commutes, try both ways.
+      if ((C1->getValue() & (C1->getValue() + 1)) == 0 &&
+          match(B, m_Add(m_Value(V1), m_Value(V2)))) {
+        // Add commutes, try both ways.
+        if (V1 == A && MaskedValueIsZero(V2, C1->getValue()))
+          return B;
+        if (V2 == A && MaskedValueIsZero(V1, C1->getValue()))
+          return B;
+      }
+    }
+  }
+
   // If the operation is with the result of a phi instruction, check whether
   // operating on all incoming values of the phi always yields the same value.
   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
     if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse))
       return V;
 
   return nullptr;
 }

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombiner::visitOr(BinaryOperator &I) {
   // (A & C)|(B & D)
   Value *C = nullptr, *D = nullptr;
   if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
       match(Op1, m_And(m_Value(B), m_Value(D)))) {
     Value *V1 = nullptr, *V2 = nullptr;
     C1 = dyn_cast<ConstantInt>(C);
     C2 = dyn_cast<ConstantInt>(D);
     if (C1 && C2) {  // (A & C1)|(B & C2)
-      // If we have: ((V + N) & C1) | (V & C2)
-      // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0
-      // replace with V+N.
-      if (C1->getValue() == ~C2->getValue()) {
-        if ((C2->getValue() & (C2->getValue()+1)) == 0 && // C2 == 0+1+
-            match(A, m_Add(m_Value(V1), m_Value(V2)))) {
-          // Add commutes, try both ways.
-          if (V1 == B && MaskedValueIsZero(V2, C2->getValue()))
-            return ReplaceInstUsesWith(I, A);
-          if (V2 == B && MaskedValueIsZero(V1, C2->getValue()))
-            return ReplaceInstUsesWith(I, A);
-        }
-        // Or commutes, try both ways.
-        if ((C1->getValue() & (C1->getValue()+1)) == 0 &&
-            match(B, m_Add(m_Value(V1), m_Value(V2)))) {
-          // Add commutes, try both ways.
-          if (V1 == A && MaskedValueIsZero(V2, C1->getValue()))
-            return ReplaceInstUsesWith(I, B);
-          if (V2 == A && MaskedValueIsZero(V1, C1->getValue()))
-            return ReplaceInstUsesWith(I, B);
-        }
-      }
-
       if ((C1->getValue() & C2->getValue()) == 0) {
         // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2)
         // iff (C1&C2) == 0 and (N&~C1) == 0
         if (match(A, m_Or(m_Value(V1), m_Value(V2))) &&
             ((V1 == B && MaskedValueIsZero(V2, ~C1->getValue())) ||  // (V|N)
              (V2 == B && MaskedValueIsZero(V1, ~C1->getValue()))))   // (N|V)
           return BinaryOperator::CreateAnd(A,
                                 Builder->getInt(C1->getValue()|C2->getValue()));

test/Transforms/InstSimplify/apint-or.ll

+; This test makes sure that or instructions are properly eliminated.
+; The first test is for Integer BitWidth <= 64 && BitWidth % 2 != 0.
+; The second test is for Integer BitWidth > 64 && BitWidth <= 1024. 
+
+; RUN: opt < %s -instsimplify -S | not grep or
+
+
+define i39 @test1(i39 %V, i39 %M) {
+    ;; If we have: ((V + N) & C1) | (V & C2)
+    ;; .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0
+    ;; replace with V+N.
+    %C1 = xor i39 274877906943, -1 ;; C2 = 274877906943
+    %N = and i39 %M, 274877906944
+    %A = add i39 %V, %N
+    %B = and i39 %A, %C1
+    %D = and i39 %V, 274877906943
+    %R = or i39 %B, %D
+    ret i39 %R
+}
+
+define i399 @test3(i399 %V, i399 %M) {
+    ;; If we have: ((V + N) & C1) | (V & C2)
+    ;; .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0
+    ;; replace with V+N.
+    %C1 = xor i399 274877906943, -1 ;; C2 = 274877906943
+    %N = and i399 %M, 18446742974197923840
+    %A = add i399 %V, %N
+    %B = and i399 %A, %C1
+    %D = and i399 %V, 274877906943
+    %R = or i399 %B, %D
+    ret i399 %R
+}