[IR][PatternMatch] introduce m_Unless() matcher

[lebedev.ri]

Summary

I don't think it already exists? I don't see it at least.
It is important to have it because else we'll do some checks after match(),
and that may result in missed folds in commutative nodes.

[RKSimon]

Do you have a specific usecase in mind?

[lebedev.ri]

In D64037#1566190, @RKSimon wrote:

Do you have a specific usecase in mind?

Yes, absolutely. I don't submit patches otherwise.

[RKSimon]

In D64037#1566201, @lebedev.ri wrote:

In D64037#1566190, @RKSimon wrote:

Do you have a specific usecase in mind?

Yes, absolutely. I don't submit patches otherwise.

Please can you update the dependency on this patch to point to the usecases?

[lebedev.ri]

This comment was removed by lebedev.ri.

[lebedev.ri]

In D64037#1566247, @RKSimon wrote:

In D64037#1566201, @lebedev.ri wrote:

In D64037#1566190, @RKSimon wrote:

Do you have a specific usecase in mind?

Yes, absolutely. I don't submit patches otherwise.

Please can you update the dependency on this patch to point to the usecases?

I didn't post that patch yet. It comes up when fixing PR42466
We have icmp eq/ne (and (shl X, Y), Z), 0, and if X is not a constant we want to turn it into icmp eq/ne (and (lshr Z, Y), X), 0.
But the problem is that if we do the obvious thing and directly patternmatch that, and *then* check that X is not a constant (and not fold if it is),
we then won't check whether Z is also a (shl Q, W) with Q not being a constant, and this we have missed commutative case..

[RKSimon]

In D64037#1566278, @lebedev.ri wrote:

In D64037#1566247, @RKSimon wrote:

In D64037#1566201, @lebedev.ri wrote:

In D64037#1566190, @RKSimon wrote:

Do you have a specific usecase in mind?

Yes, absolutely. I don't submit patches otherwise.

Please can you update the dependency on this patch to point to the usecases?

I didn't post that patch yet. It comes up when fixing PR42466
We have icmp eq/ne (and (shl X, Y), Z), 0, and if X is not a constant we want to turn it into icmp eq/ne (and (lshr Z, Y), X), 0.
But the problem is that if we do the obvious thing and directly patternmatch that, and *then* check that X is not a constant (and not fold if it is),
we then won't check whether Z is also a (shl Q, W) with Q not being a constant, and this we have missed commutative case..

OK I'm convinced, does anyone else have any comments?

[spatel]

LGTM

unittests/IR/PatternMatch.cpp

89 ↗

(On Diff #207410)

Better to call this value 'X' or some other non-overlapping name - easy to misread 'm_One' and 'One' below here.

[lebedev.ri]

Thanks for the review!

[lebedev.ri]

Rebased, NFC.

llvm/include/llvm/IR/PatternMatch.h

 }
 
 /// Match an arbitrary undef constant.
 inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); }
 
 /// Match an arbitrary Constant and ignore it.
 inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
 
+/// Inverting matcher
+template <typename Ty> struct match_unless {
+  Ty M;
+
+  match_unless(const Ty &Matcher) : M(Matcher) {}
+
+  template <typename ITy> bool match(ITy *V) { return !M.match(V); }
+};
+
+/// Match if the inner matcher does *NOT* match.
+template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
+  return match_unless<Ty>(M);
+}
+
 /// Matching combinators
 template <typename LTy, typename RTy> struct match_combine_or {
   LTy L;
   RTy R;
 
   match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
 
   template <typename ITy> bool match(ITy *V) {

llvm/unittests/IR/PatternMatch.cpp

TEST_F(PatternMatchTest, SpecificIntSLE) {
   EXPECT_FALSE(
       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLE, APInt(BitWidth, -1))
           .match(One));
   EXPECT_TRUE(
       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLE, APInt(BitWidth, -1))
           .match(NegOne));
 }
 
+TEST_F(PatternMatchTest, Unless) {
+  Value *X = IRB.CreateAdd(IRB.getInt32(1), IRB.getInt32(0));
+
+  EXPECT_TRUE(m_Add(m_One(), m_Zero()).match(X));
+  EXPECT_FALSE(m_Add(m_Zero(), m_One()).match(X));
+
+  EXPECT_FALSE(m_Unless(m_Add(m_One(), m_Zero())).match(X));
+  EXPECT_TRUE(m_Unless(m_Add(m_Zero(), m_One())).match(X));
+
+  EXPECT_TRUE(m_c_Add(m_One(), m_Zero()).match(X));
+  EXPECT_TRUE(m_c_Add(m_Zero(), m_One()).match(X));
+
+  EXPECT_FALSE(m_Unless(m_c_Add(m_One(), m_Zero())).match(X));
+  EXPECT_FALSE(m_Unless(m_c_Add(m_Zero(), m_One())).match(X));
+}
+
 TEST_F(PatternMatchTest, CommutativeDeferredValue) {
   Value *X = IRB.getInt32(1);
   Value *Y = IRB.getInt32(2);
 
   {
     Value *tX = X;
     EXPECT_TRUE(match(X, m_Deferred(tX)));
     EXPECT_FALSE(match(Y, m_Deferred(tX)));