[IR] Implement commutable matchers without using combineOr

[craig.topper]

Summary

Turns out creating matchers with combineOr isn't very efficient as we have to build matcher objects for both sides of the OR. Those objects aren't free, the trees usually contain several objects that contain a reference to a Value *, ConstantInt *, APInt * or some such thing. The compiler isn't always willing to inline all the matcher code to get rid of these member variables. Thus we end up loads and stores of these variables.

Using combineOR ends up creating two complete copies of the tree and the associated stores. I believe we're also paying for the opcode check twice.

This patch adds a commutable mode to several of the matcher objects as a bool template parameter that can be used to enable commutable support directly in the match functions of the corresponding objects. This avoids the duplicate object creation and the opcode checks.

This shows about an ~7-8k reduction in the opt binary size on my local build.

[majnemer]

LGTM

include/llvm/IR/PatternMatch.h

 
 /// \brief 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; }
 
 //===----------------------------------------------------------------------===//
 // Matcher for any binary operator.
 //
-template <typename LHS_t, typename RHS_t> struct AnyBinaryOp_match {
+template <typename LHS_t, typename RHS_t, bool Commutable = false>
+struct AnyBinaryOp_match {
   LHS_t L;
   RHS_t R;
 
   AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *I = dyn_cast<BinaryOperator>(V))
-      return L.match(I->getOperand(0)) && R.match(I->getOperand(1));
+      return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
+             (Commutable && L.match(I->getOperand(0)) &&
+              R.match(I->getOperand(1)));
     return false;
   }
 };
 
 template <typename LHS, typename RHS>
 inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
   return AnyBinaryOp_match<LHS, RHS>(L, R);
 }
 
 //===----------------------------------------------------------------------===//
 // Matchers for specific binary operators.
 //
 
-template <typename LHS_t, typename RHS_t, unsigned Opcode>
+template <typename LHS_t, typename RHS_t, unsigned Opcode,
+          bool Commutable = false>
 struct BinaryOp_match {
   LHS_t L;
   RHS_t R;
 
   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (V->getValueID() == Value::InstructionVal + Opcode) {
       auto *I = cast<BinaryOperator>(V);
-      return L.match(I->getOperand(0)) && R.match(I->getOperand(1));
+      return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
+             (Commutable && R.match(I->getOperand(0)) &&
+              L.match(I->getOperand(1)));
     }
     if (auto *CE = dyn_cast<ConstantExpr>(V))
-      return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
-             R.match(CE->getOperand(1));
+      return CE->getOpcode() == Opcode &&
+             ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
+              (Commutable && L.match(CE->getOperand(0)) &&
+               R.match(CE->getOperand(1))));
     return false;
   }
 };
 
 template <typename LHS, typename RHS>
 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
                                                         const RHS &R) {
   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);

 template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
   return SubPattern;
 }
 
 //===----------------------------------------------------------------------===//
 // Matchers for CmpInst classes
 //
 
-template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
+template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
+          bool Commutable = false>
 struct CmpClass_match {
   PredicateTy &Predicate;
   LHS_t L;
   RHS_t R;
 
   CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
       : Predicate(Pred), L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *I = dyn_cast<Class>(V))
-      if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
+      if ((L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
+          (Commutable && R.match(I->getOperand(0)) &&
+           L.match(I->getOperand(1)))) {
         Predicate = I->getPredicate();
         return true;
       }
     return false;
   }
 };
 
 template <typename LHS, typename RHS>

 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
   return brc_match<Cond_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>
+template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
+          bool Commutable = false>
 struct MaxMin_match {
   LHS_t L;
   RHS_t R;
 
   MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
if ((TrueVal != LHS || FalseVal != RHS) &&
         (TrueVal != RHS || FalseVal != LHS))
       return false;
     typename CmpInst_t::Predicate Pred =
         LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
     // Does "(x pred y) ? x : y" represent the desired max/min operation?
     if (!Pred_t::match(Pred))
       return false;
     // It does!  Bind the operands.
-    return L.match(LHS) && R.match(RHS);
+    return (L.match(LHS) && R.match(RHS)) ||
+           (Commutable && R.match(LHS) && L.match(RHS));
   }
 };
 
 /// \brief Helper class for identifying signed max predicates.
 struct smax_pred_ty {
   static bool match(ICmpInst::Predicate Pred) {
     return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
   }
template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
   return Signum_match<Val_t>(V);
 }
 
 //===----------------------------------------------------------------------===//
 // Matchers for two-operands operators with the operators in either order
 //
 
 /// \brief Matches a BinaryOperator with LHS and RHS in either order.
-template<typename LHS, typename RHS>
-inline match_combine_or<AnyBinaryOp_match<LHS, RHS>,
-                        AnyBinaryOp_match<RHS, LHS>>
-m_c_BinOp(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_BinOp(L, R), m_BinOp(R, L));
+template <typename LHS, typename RHS>
+inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
+  return AnyBinaryOp_match<LHS, RHS, true>(L, R);
 }
 
 /// \brief Matches an ICmp with a predicate over LHS and RHS in either order.
 /// Does not swap the predicate.
-template<typename LHS, typename RHS>
-inline match_combine_or<CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>,
-                        CmpClass_match<RHS, LHS, ICmpInst, ICmpInst::Predicate>>
+template <typename LHS, typename RHS>
+inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
 m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
-  return m_CombineOr(m_ICmp(Pred, L, R), m_ICmp(Pred, R, L));
+  return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
+                                                                       R);
 }
 
 /// \brief Matches a Add with LHS and RHS in either order.
-template<typename LHS, typename RHS>
-inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Add>,
-                        BinaryOp_match<RHS, LHS, Instruction::Add>>
-m_c_Add(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_Add(L, R), m_Add(R, L));
+template <typename LHS, typename RHS>
+inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L,
+                                                                const RHS &R) {
+  return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R);
 }
 
 /// \brief Matches a Mul with LHS and RHS in either order.
-template<typename LHS, typename RHS>
-inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Mul>,
-                        BinaryOp_match<RHS, LHS, Instruction::Mul>>
-m_c_Mul(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_Mul(L, R), m_Mul(R, L));
+template <typename LHS, typename RHS>
+inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L,
+                                                                const RHS &R) {
+  return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R);
 }
 
 /// \brief Matches an And with LHS and RHS in either order.
-template<typename LHS, typename RHS>
-inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::And>,
-                        BinaryOp_match<RHS, LHS, Instruction::And>>
-m_c_And(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_And(L, R), m_And(R, L));
+template <typename LHS, typename RHS>
+inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L,
+                                                                const RHS &R) {
+  return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R);
 }
 
 /// \brief Matches an Or with LHS and RHS in either order.
-template<typename LHS, typename RHS>
-inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Or>,
-                        BinaryOp_match<RHS, LHS, Instruction::Or>>
-m_c_Or(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_Or(L, R), m_Or(R, L));
+template <typename LHS, typename RHS>
+inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L,
+                                                              const RHS &R) {
+  return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R);
 }
 
 /// \brief Matches an Xor with LHS and RHS in either order.
-template<typename LHS, typename RHS>
-inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Xor>,
-                        BinaryOp_match<RHS, LHS, Instruction::Xor>>
-m_c_Xor(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_Xor(L, R), m_Xor(R, L));
+template <typename LHS, typename RHS>
+inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L,
+                                                                const RHS &R) {
+  return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R);
 }
 
 /// Matches an SMin with LHS and RHS in either order.
 template <typename LHS, typename RHS>
-inline match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>,
-                        MaxMin_match<ICmpInst, RHS, LHS, smin_pred_ty>>
+inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>
 m_c_SMin(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_SMin(L, R), m_SMin(R, L));
+  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>
-inline match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>,
-                        MaxMin_match<ICmpInst, RHS, LHS, smax_pred_ty>>
+inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>
 m_c_SMax(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_SMax(L, R), m_SMax(R, L));
+  return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R);
 }
 /// Matches a UMin with LHS and RHS in either order.
 template <typename LHS, typename RHS>
-inline match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>,
-                        MaxMin_match<ICmpInst, RHS, LHS, umin_pred_ty>>
+inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>
 m_c_UMin(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_UMin(L, R), m_UMin(R, L));
+  return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R);
 }
 /// Matches a UMax with LHS and RHS in either order.
 template <typename LHS, typename RHS>
-inline match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>,
-                        MaxMin_match<ICmpInst, RHS, LHS, umax_pred_ty>>
+inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>
 m_c_UMax(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_UMax(L, R), m_UMax(R, L));
+  return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R);
 }
 
 } // end namespace PatternMatch
 } // end namespace llvm
 
 #endif // LLVM_IR_PATTERNMATCH_H