[AArch64] Sink operands for faster bitselect vector instructions

[MaskRay]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14357

plain array or std::array if Ands doesn't get new elements.

14359

Pre-increment

https://llvm.org/docs/CodingStandards.html#prefer-preincrement

14362

14376

[pranavk]

This has been superseded by https://reviews.llvm.org/D147266

I forgot to update the link in the final commit here (https://github.com/llvm/llvm-project/commit/726785b1594c6b567c5c8ddd59075aee726590c6)

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

if (areExtractShuffleVectors(Ext1->getOperand(0), Ext2->getOperand(0))) {
       Ops.push_back(&Ext2->getOperandUse(0));
     }
 
     Ops.push_back(&I->getOperandUse(0));
     Ops.push_back(&I->getOperandUse(1));
 
     return true;
   }
+  case Instruction::And: {
+    // If Or(And(A, maskValue), And(B, ~maskValue)), sink ~maskValue
+    // where ~maskValue = xor maskValue, -1
+    // This is to select more performant bitselect instruction in the backend.
+
+    // We start checking for this code sequence from AND instruction containing
+    // ~maskValue because operands are sunk just before the Instruction* I
+    // passed to this function. Starting pattern matching with any other
+    // instruction (such as Or) would lead to malformed IR
+
+    // Check if this AND instruction is part of bigger tree rooted at Or.
+    if (I->getNumUses() == 1) {
+      Use &U = *(I->use_begin());
+      Instruction *OI = cast<Instruction>(U.getUser());
+      Value *And0_Op0 = nullptr, *And0_Op1 = nullptr, *And1_Op0 = nullptr,
+            *And1_Op1 = nullptr;
+      if (!OI ||
+          !match(OI, m_Or(m_And(m_Value(And0_Op0), m_Value(And0_Op1)),
+                          m_And(m_Value(And1_Op0), m_Value(And1_Op1)))) ||
+          !all_of(OI->operands(), [](Value *V) { return V->hasOneUser(); }))
+        return false;
+
+      SmallVector<SmallVector<Value *, 2>, 2> Ands = {{And0_Op0, And0_Op1},
+                                                      {And1_Op0, And1_Op1}};
+      for (unsigned AndIndex = 0; AndIndex < Ands.size(); AndIndex++) {
+        const unsigned OtherAndIndex = (AndIndex + 1) % 2;
+
+        // Iterate operands of selected And
+        for (unsigned AndOpIndex = 0; AndOpIndex < 2; AndOpIndex++) {
+          if (const Instruction *XI =
+                  dyn_cast<Instruction>(Ands[AndIndex][AndOpIndex]);
+              XI && XI->getOpcode() == Instruction::Xor) {
+            Constant *MaskConst;
+            Value *MaskValue;
+            if (!match(XI, m_Xor(m_Value(MaskValue), m_Constant(MaskConst))) &&
+                !match(XI, m_Xor(m_Constant(MaskConst), m_Value(MaskValue))))
+              return false;
+
+            if (!MaskConst->isAllOnesValue())
+              return false;
+
+            // one of the operands of other AND should be MaskValue
+            if (!any_of(Ands[OtherAndIndex],
+                        [&MaskValue](Value *V) { return V == MaskValue; }))
+              return false;
+
+            auto TI = cast<Instruction>(OI->getOperand(AndIndex));
+            Ops.push_back(&TI->getOperandUse(AndOpIndex));
+            return true;
+          }
+        }
+      }
+    }
+    return false;
+  }
   case Instruction::Mul: {
     int NumZExts = 0, NumSExts = 0;
     for (auto &Op : I->operands()) {
       // Make sure we are not already sinking this operand
       if (any_of(Ops, [&](Use *U) { return U->get() == Op; }))
         continue;
 
       if (match(&Op, m_SExt(m_Value()))) {