[InstCombine] Fold unfolded masked merge pattern with variable mask!

Summary:
Finally fixes [[ https://bugs.llvm.org/show_bug.cgi?id=6773 | PR6773 ]].

Now that the backend is all done, we can finally fold it!

The canonical unfolded masked merge pattern is
```(x &  m) | (y & ~m)```
There is a second, equivalent variant:
```(x | ~m) & (y |  m)```
Only one of them (the or-of-and's i think) is canonical.
And if the mask is not a constant, we should fold it to:
```((x ^ y) & M) ^ y```

https://rise4fun.com/Alive/ndQw

Reviewers: spatel, craig.topper

Reviewed By: spatel

Subscribers: nicholas, RKSimon, llvm-commits

Differential Revision: https://reviews.llvm.org/D46814

llvm-svn: 333106

1 files changed, 36 insertions, 0 deletions

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
index 22e7b360d0e..f4e1d5adbe0 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -748,6 +748,9 @@ static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
   return nullptr;
 }
 
+static Instruction *foldMaskedMerge(BinaryOperator &I,
+                                    InstCombiner::BuilderTy &Builder);
+
 /// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
 /// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
 /// If \p Inverted is true then the check is for the inverted range, e.g.
@@ -1648,6 +1651,9 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
       A->getType()->isIntOrIntVectorTy(1))
     return SelectInst::Create(A, Op0, Constant::getNullValue(I.getType()));
 
+  if (Instruction *MM = foldMaskedMerge(I, Builder))
+    return MM;
+
   return Changed ? &I : nullptr;
 }
 
@@ -2287,6 +2293,9 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) {
     }
   }
 
+  if (Instruction *MM = foldMaskedMerge(I, Builder))
+    return MM;
+
   return Changed ? &I : nullptr;
 }
 
@@ -2422,6 +2431,33 @@ Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
   return nullptr;
 }
 
+/// Bitwise masked merge (bitwise select) is typically coded as:
+/// (x & m) | (y & ~m)
+/// Another variant is:
+/// (x | ~m) & (y | m)
+/// Canonicalize those to a form with one less IR instruction:
+/// ((x ^ y) & m) ^ y
+static Instruction *foldMaskedMerge(BinaryOperator &I,
+                                    InstCombiner::BuilderTy &Builder) {
+  Value *X, *Y;
+
+  Value *M;
+  if (match(&I, m_c_Or(m_OneUse(m_c_And(m_Value(Y), m_Not(m_Value(M)))),
+                       m_OneUse(m_c_And(m_Value(X), m_Deferred(M))))) ||
+      match(&I, m_c_And(m_OneUse(m_c_Or(m_Value(X), m_Not(m_Value(M)))),
+                        m_OneUse(m_c_Or(m_Value(Y), m_Deferred(M)))))) {
+    assert(!isa<Constant>(M) && "Shouldn't have matched a constant.");
+
+    Value *D = Builder.CreateXor(X, Y);
+    Value *A = Builder.CreateAnd(D, M);
+    return BinaryOperator::CreateXor(A, Y);
+  }
+
+  // FIXME: we still want to canonicalize the patterns with constants somewhat.
+
+  return nullptr;
+}
+
 /// If we have a masked merge, in the canonical form of:
 /// (assuming that A only has one use.)
 ///   |        A  |  |B|