[PatternMatch] Make m_Br more flexible, add matchers for BB values.

[fhahn]

Summary

Currently m_Br only takes references to BasicBlock*, which limits its
flexibility. For example, you have to declare a variable, even if you
ignore the result or you have to have additional checks to make sure the
matched BB matches an expected one.

This patch adds m_BasicBlock and m_SpecificBB matchers, which can be
used like the existing matchers for constants or values.

I also had a look at the existing uses and updated a few. IMO it makes
the code a bit more explicit.

[lebedev.ri]

llvm/include/llvm/IR/PatternMatch.h

682–686 ↗

(On Diff #221707)

Should m_DeferredBB() be added at the same time?

[fhahn]

Add m_Deferred overload for BasicBlock & test.

[fhahn]

llvm/include/llvm/IR/PatternMatch.h

682–686 ↗

(On Diff #221707)

Nice, I did not know about m_Deferred!

I've added an overloaded version for BasicBlock, not sure if there's a benefit for including BB in the name, as we also don't include Value in the Value variant name. I've also added a test.

[lebedev.ri]

llvm/include/llvm/IR/PatternMatch.h

682–683 ↗

(On Diff #221718)

This comment seems outdated.

1375–1379 ↗

(On Diff #221718)

Precommit

[fhahn]

Fix comment and split off suggested changes for precommit (once the patch is accepted).

[fhahn]

Move another bit to precommit.

[fhahn]

llvm/include/llvm/IR/PatternMatch.h

682–683 ↗

(On Diff #221718)

Thanks, updated!

1375–1379 ↗

(On Diff #221718)

Done, split off to a separate commit, to be committed once this one is accepted.

[lebedev.ri]

Looks good to me.

llvm/include/llvm/IR/PatternMatch.h

1403 ↗

(On Diff #221743)

Should there be m_c_Br ?

[fhahn]

Thanks!

llvm/include/llvm/IR/PatternMatch.h

1403 ↗

(On Diff #221743)

I am not entirely sure. I think for most use cases with branches, matching commuted targets is not too common, but if there are cases it should be a straight forward follow-up.

llvm/trunk/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>(); }
 
+/// Match an arbitrary basic block value and ignore it.
+inline class_match<BasicBlock> m_BasicBlock() {
+  return class_match<BasicBlock>();
+}
+
 /// 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); }
 };

 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
 
 /// Match a Constant, capturing the value if we match.
 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
 
 /// Match a ConstantFP, capturing the value if we match.
 inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; }
 
+/// Match a basic block value, capturing it if we match.
+inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
+inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) {
+  return V;
+}
+
 /// Match a specified Value*.
 struct specificval_ty {
   const Value *Val;
 
   specificval_ty(const Value *V) : Val(V) {}
 
   template <typename ITy> bool match(ITy *V) { return V == Val; }
 };

 /// Match a specific integer value or vector with all elements equal to
 /// the value.
 inline specific_intval m_SpecificInt(uint64_t V) { return specific_intval(V); }
 
 /// Match a ConstantInt and bind to its value.  This does not match
 /// ConstantInts wider than 64-bits.
 inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
 
+/// Match a specified basic block value.
+struct specific_bbval {
+  BasicBlock *Val;
+
+  specific_bbval(BasicBlock *Val) : Val(Val) {}
+
+  template <typename ITy> bool match(ITy *V) {
+    const auto *BB = dyn_cast<BasicBlock>(V);
+    return BB && BB == Val;
+  }
+};
+
+/// Match a specific basic block value.
+inline specific_bbval m_SpecificBB(BasicBlock *BB) {
+  return specific_bbval(BB);
+}
+
+/// A commutative-friendly version of m_Specific().
+inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) {
+  return BB;
+}
+inline deferredval_ty<const BasicBlock>
+m_Deferred(const BasicBlock *const &BB) {
+  return BB;
+}
+
 //===----------------------------------------------------------------------===//
 // Matcher for any binary operator.
 //
 template <typename LHS_t, typename RHS_t, bool Commutable = false>
 struct AnyBinaryOp_match {
   LHS_t L;
   RHS_t R;
 
struct brc_match {
   TrueBlock_t T;
   FalseBlock_t F;
 
   brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
       : Cond(C), T(t), F(f) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *BI = dyn_cast<BranchInst>(V))
-      if (BI->isConditional() && Cond.match(BI->getCondition())) {
-        T = BI->getSuccessor(0);
-        F = BI->getSuccessor(1);
-        return true;
-      }
+      if (BI->isConditional() && Cond.match(BI->getCondition()))
+        return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1));
     return false;
   }
 };
 
 template <typename Cond_t>
-inline brc_match<Cond_t, BasicBlock *&, BasicBlock *&>
+inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>
 m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
-  return brc_match<Cond_t, BasicBlock *&, BasicBlock *&>(C, T, F);
+  return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>(
+      C, m_BasicBlock(T), m_BasicBlock(F));
+}
+
+template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
+inline brc_match<Cond_t, TrueBlock_t, FalseBlock_t>
+m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) {
+  return brc_match<Cond_t, TrueBlock_t, FalseBlock_t>(C, T, F);
 }
 
 //===----------------------------------------------------------------------===//
 // Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
 //
 
 template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
           bool Commutable = false>

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At,
 
   SmallVector<BasicBlock *, 4> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
   // Look for suitable value in simple conditions at the loop exits.
   for (BasicBlock *BB : ExitingBlocks) {
     ICmpInst::Predicate Pred;
     Instruction *LHS, *RHS;
-    BasicBlock *TrueBB, *FalseBB;
 
     if (!match(BB->getTerminator(),
                m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
-                    TrueBB, FalseBB)))
+                    m_BasicBlock(), m_BasicBlock())))
       continue;
 
     if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
       return ScalarEvolution::ValueOffsetPair(LHS, nullptr);
 
     if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
       return ScalarEvolution::ValueOffsetPair(RHS, nullptr);
   }

llvm/trunk/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

static bool foldGuardedRotateToFunnelShift(Instruction &I) {
   }
 
   // The incoming block with our source operand must be the "guard" block.
   // That must contain a cmp+branch to avoid the rotate when the shift amount
   // is equal to 0. The other incoming block is the block with the rotate.
   BasicBlock *GuardBB = Phi.getIncomingBlock(RotSrc == P1);
   BasicBlock *RotBB = Phi.getIncomingBlock(RotSrc != P1);
   Instruction *TermI = GuardBB->getTerminator();
-  BasicBlock *TrueBB, *FalseBB;
   ICmpInst::Predicate Pred;
-  if (!match(TermI, m_Br(m_ICmp(Pred, m_Specific(RotAmt), m_ZeroInt()), TrueBB,
-                         FalseBB)))
+  BasicBlock *PhiBB = Phi.getParent();
+  if (!match(TermI, m_Br(m_ICmp(Pred, m_Specific(RotAmt), m_ZeroInt()),
+                         m_SpecificBB(PhiBB), m_SpecificBB(RotBB))))
     return false;
 
-  BasicBlock *PhiBB = Phi.getParent();
-  if (Pred != CmpInst::ICMP_EQ || TrueBB != PhiBB || FalseBB != RotBB)
+  if (Pred != CmpInst::ICMP_EQ)
     return false;
 
   // We matched a variation of this IR pattern:
   // GuardBB:
   //   %cmp = icmp eq i32 %RotAmt, 0
   //   br i1 %cmp, label %PhiBB, label %RotBB
   // RotBB:
   //   %sub = sub i32 32, %RotAmt

llvm/trunk/lib/Transforms/InstCombine/InstructionCombining.cpp

if (Known.isConstant())
     RI.setOperand(0, Constant::getIntegerValue(VTy, Known.getConstant()));
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
   // Change br (not X), label True, label False to: br X, label False, True
   Value *X = nullptr;
-  BasicBlock *TrueDest;
-  BasicBlock *FalseDest;
-  if (match(&BI, m_Br(m_Not(m_Value(X)), TrueDest, FalseDest)) &&
+  if (match(&BI, m_Br(m_Not(m_Value(X)), m_BasicBlock(), m_BasicBlock())) &&
       !isa<Constant>(X)) {
     // Swap Destinations and condition...
     BI.setCondition(X);
     BI.swapSuccessors();
     return &BI;
   }
 
   // If the condition is irrelevant, remove the use so that other
   // transforms on the condition become more effective.
   if (BI.isConditional() && !isa<ConstantInt>(BI.getCondition()) &&
       BI.getSuccessor(0) == BI.getSuccessor(1)) {
     BI.setCondition(ConstantInt::getFalse(BI.getCondition()->getType()));
     return &BI;
   }
 
   // Canonicalize, for example, icmp_ne -> icmp_eq or fcmp_one -> fcmp_oeq.
   CmpInst::Predicate Pred;
-  if (match(&BI, m_Br(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), TrueDest,
-                      FalseDest)) &&
+  if (match(&BI, m_Br(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())),
+                      m_BasicBlock(), m_BasicBlock())) &&
       !isCanonicalPredicate(Pred)) {
     // Swap destinations and condition.
     CmpInst *Cond = cast<CmpInst>(BI.getCondition());
     Cond->setPredicate(CmpInst::getInversePredicate(Pred));
     BI.swapSuccessors();
     Worklist.Add(Cond);
     return &BI;
   }

llvm/trunk/unittests/IR/PatternMatch.cpp

TEST_F(PatternMatchTest, FloatingPointFNeg) {
   cast<Instruction>(V2)->setHasNoSignedZeros(true);
   EXPECT_TRUE(match(V2, m_FNeg(m_Value(Match))));
   EXPECT_EQ(One, Match);
 
   // Test FAdd(-0.0, 1.0)
   EXPECT_FALSE(match(V3, m_FNeg(m_Value(Match))));
 }
 
+TEST_F(PatternMatchTest, CondBranchTest) {
+  BasicBlock *TrueBB = BasicBlock::Create(Ctx, "TrueBB", F);
+  BasicBlock *FalseBB = BasicBlock::Create(Ctx, "FalseBB", F);
+  Value *Br1 = IRB.CreateCondBr(IRB.getTrue(), TrueBB, FalseBB);
+
+  EXPECT_TRUE(match(Br1, m_Br(m_Value(), m_BasicBlock(), m_BasicBlock())));
+
+  BasicBlock *A, *B;
+  EXPECT_TRUE(match(Br1, m_Br(m_Value(), m_BasicBlock(A), m_BasicBlock(B))));
+  EXPECT_EQ(TrueBB, A);
+  EXPECT_EQ(FalseBB, B);
+
+  EXPECT_FALSE(
+      match(Br1, m_Br(m_Value(), m_SpecificBB(FalseBB), m_BasicBlock())));
+  EXPECT_FALSE(
+      match(Br1, m_Br(m_Value(), m_BasicBlock(), m_SpecificBB(TrueBB))));
+  EXPECT_FALSE(
+      match(Br1, m_Br(m_Value(), m_SpecificBB(FalseBB), m_BasicBlock(TrueBB))));
+  EXPECT_TRUE(
+      match(Br1, m_Br(m_Value(), m_SpecificBB(TrueBB), m_BasicBlock(FalseBB))));
+
+  // Check we can use m_Deferred with branches.
+  EXPECT_FALSE(match(Br1, m_Br(m_Value(), m_BasicBlock(A), m_Deferred(A))));
+  Value *Br2 = IRB.CreateCondBr(IRB.getTrue(), TrueBB, TrueBB);
+  A = nullptr;
+  EXPECT_TRUE(match(Br2, m_Br(m_Value(), m_BasicBlock(A), m_Deferred(A))));
+}
+
 template <typename T> struct MutableConstTest : PatternMatchTest { };
 
 typedef ::testing::Types<std::tuple<Value*, Instruction*>,
                          std::tuple<const Value*, const Instruction *>>
     MutableConstTestTypes;
 TYPED_TEST_CASE(MutableConstTest, MutableConstTestTypes);
 
 TYPED_TEST(MutableConstTest, ICmp) {