[PatternMatch] create and use matcher for 'not' that excludes undef elements

[spatel]

Summary

We needed a stricter version of m_Not for D114462, but I wasn't sure if that was going to be required anywhere else, so I didn't bother to make that reusable.

It turns out we have one more existing simplification that needs this (currently miscompiles):
https://alive2.llvm.org/ce/z/9-nTKi

And there's at least one more fold in that family that we could add.

I copied from existing code to implement this, but I'm definitely open to suggestions if there's a better way. I don't know C++ template magic well at all.

[lebedev.ri]

llvm/include/llvm/IR/PatternMatch.h

2295–2298

?

[spatel]

llvm/include/llvm/IR/PatternMatch.h

2295–2298

That's how I originally implemented it. :)

But that mismatched on the unit test that I created. In that test, the other operand is a zero constant with no undefs. So the commutative matcher matched the zero constant in that example as C and then failed the subsequent isAllOnes check.

It seems unlikely that we'd see something like that (should get constant-folded before we see it) in the optimizer, but it's still possible in general usage?

[lebedev.ri]

LG

[rampitec]

LGTM. Comment about commuted xor would be handy.

llvm/include/llvm/IR/PatternMatch.h

2295–2298

Sounds like a good thing to leave comment here. I also thought about m_c_Xor.

[spatel]

Added code comment to explain commutable corner case and block comment for the matcher.

llvm/include/llvm/IR/PatternMatch.h

 
 /// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
 template <typename ValTy>
 inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true>
 m_Not(const ValTy &V) {
   return m_c_Xor(V, m_AllOnes());
 }
 
+template <typename ValTy> struct NotForbidUndef_match {
+  ValTy Val;
+  NotForbidUndef_match(const ValTy &V) : Val(V) {}
+
+  template <typename OpTy> bool match(OpTy *V) {
+    // We do not use m_c_Xor because that could match an arbitrary APInt that is
+    // not -1 as C and then fail to match the other operand if it is -1.
+    // This code should still work even when both operands are constants.
+    Value *X;
+    const APInt *C;
+    if (m_Xor(m_Value(X), m_APIntForbidUndef(C)).match(V) && C->isAllOnes())
+      return Val.match(X);
+    if (m_Xor(m_APIntForbidUndef(C), m_Value(X)).match(V) && C->isAllOnes())
+      return Val.match(X);
+    return false;
+  }
+};
+
+/// Matches a bitwise 'not' as 'xor V, -1' or 'xor -1, V'. For vectors, the
+/// constant value must be composed of only -1 scalar elements.
+template <typename ValTy>
+inline NotForbidUndef_match<ValTy> m_NotForbidUndef(const ValTy &V) {
+  return NotForbidUndef_match<ValTy>(V);
+}
+
 /// Matches an SMin with LHS and RHS in either order.
 template <typename LHS, typename RHS>
 inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>
 m_c_SMin(const LHS &L, const RHS &R) {
   return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R);
 }
 /// Matches an SMax with LHS and RHS in either order.
 template <typename LHS, typename RHS>

llvm/lib/Analysis/InstructionSimplify.cpp

auto foldAndOrNot = [](Value *X, Value *Y) -> Value * {
     if (match(X, m_c_And(m_Not(m_Value(A)), m_Value(B))) &&
         match(Y, m_c_Or(m_Specific(A), m_Specific(B))))
       return A;
 
     // (~A | B) ^ (A & B) --> ~A -- There are 8 commuted variants.
     // The 'not' op must contain a complete -1 operand (no undef elements for
     // vector) for the transform to be safe.
     Value *NotA;
-    const APInt *C;
-    if (match(X, m_c_Or(m_CombineAnd(m_Xor(m_Value(A), m_APIntForbidUndef(C)),
-                                     m_Value(NotA)),
-                        m_Value(B))) &&
-        match(Y, m_c_And(m_Specific(A), m_Specific(B))) && C->isAllOnes())
+    if (match(X,
+              m_c_Or(m_CombineAnd(m_NotForbidUndef(m_Value(A)), m_Value(NotA)),
+        match(Y, m_c_And(m_Specific(A), m_Specific(B))))
       return NotA;
 
     return nullptr;
   };
   if (Value *R = foldAndOrNot(Op0, Op1))
     return R;
   if (Value *R = foldAndOrNot(Op1, Op0))
     return R;

llvm/unittests/IR/PatternMatch.cpp

TEST_F(PatternMatchTest, VScale) {
   Value *NullPtrVec2 = Constant::getNullValue(VecTy2->getPointerTo());
   Value *BitCast = IRB.CreateBitCast(NullPtrVec2, VecPtrTy);
   Value *GEP2 = IRB.CreateGEP(VecTy, BitCast, IRB.getInt64(1));
   Value *PtrToInt2 =
       IRB.CreatePtrToInt(GEP2, DL.getIntPtrType(GEP2->getType()));
   EXPECT_FALSE(match(PtrToInt2, m_VScale(DL)));
 }
 
+TEST_F(PatternMatchTest, NotForbidUndef) {
+  Type *ScalarTy = IRB.getInt8Ty();
+  Type *VectorTy = FixedVectorType::get(ScalarTy, 3);
+  Constant *ScalarUndef = UndefValue::get(ScalarTy);
+  Constant *ScalarOnes = Constant::getAllOnesValue(ScalarTy);
+  Constant *VectorZero = Constant::getNullValue(VectorTy);
+  Constant *VectorOnes = Constant::getAllOnesValue(VectorTy);
+
+  SmallVector<Constant *, 3> MixedElems;
+  MixedElems.push_back(ScalarOnes);
+  MixedElems.push_back(ScalarOnes);
+  MixedElems.push_back(ScalarUndef);
+  Constant *VectorMixed = ConstantVector::get(MixedElems);
+
+  Value *Not = IRB.CreateXor(VectorZero, VectorOnes);
+  Value *X;
+  EXPECT_TRUE(match(Not, m_Not(m_Value())));
+  EXPECT_TRUE(match(Not, m_NotForbidUndef(m_Value(X))));
+  EXPECT_TRUE(match(X, m_Zero()));
+
+  Value *NotCommute = IRB.CreateXor(VectorOnes, VectorZero);
+  Value *Y;
+  EXPECT_TRUE(match(NotCommute, m_Not(m_Value())));
+  EXPECT_TRUE(match(NotCommute, m_NotForbidUndef(m_Value(Y))));
+  EXPECT_TRUE(match(Y, m_Zero()));
+
+  Value *NotWithUndefs = IRB.CreateXor(VectorZero, VectorMixed);
+  EXPECT_TRUE(match(NotWithUndefs, m_Not(m_Value())));
+  EXPECT_FALSE(match(NotWithUndefs, m_NotForbidUndef(m_Value())));
+
+  Value *NotWithUndefsCommute = IRB.CreateXor(VectorMixed, VectorZero);
+  EXPECT_TRUE(match(NotWithUndefsCommute, m_Not(m_Value())));
+  EXPECT_FALSE(match(NotWithUndefsCommute, m_NotForbidUndef(m_Value(X))));
+}
+
 template <typename T> struct MutableConstTest : PatternMatchTest { };
 
 typedef ::testing::Types<std::tuple<Value*, Instruction*>,
                          std::tuple<const Value*, const Instruction *>>
     MutableConstTestTypes;
 TYPED_TEST_SUITE(MutableConstTest, MutableConstTestTypes, );
 
 TYPED_TEST(MutableConstTest, ICmp) {