From 96479ada9c059ea5b3d385d87e5f5f548b6e93a2 Mon Sep 17 00:00:00 2001
From: Craig Topper <craig.topper@gmail.com>
Date: Sat, 24 Jun 2017 22:59:10 +0000
Subject: [PATCH] [IR] Implement commutable matchers without using combineOr

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.

Reviewers: spatel, majnemer, davide

Reviewed By: majnemer

Subscribers: llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@306226 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/IR/PatternMatch.h | 114 +++++++++++++++++----------------
 1 file changed, 58 insertions(+), 56 deletions(-)

diff --git a/include/llvm/IR/PatternMatch.h b/include/llvm/IR/PatternMatch.h
index 791dbb8dc86..7a3ba1039e9 100644
--- a/include/llvm/IR/PatternMatch.h
+++ b/include/llvm/IR/PatternMatch.h
@@ -419,7 +419,8 @@ 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;
 
@@ -427,7 +428,9 @@ template <typename LHS_t, typename RHS_t> struct AnyBinaryOp_match {
 
   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 && R.match(I->getOperand(0)) &&
+              L.match(I->getOperand(1)));
     return false;
   }
 };
@@ -441,7 +444,8 @@ inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &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;
@@ -451,11 +455,15 @@ struct BinaryOp_match {
   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 && R.match(CE->getOperand(0)) &&
+               L.match(CE->getOperand(1))));
     return false;
   }
 };
@@ -766,7 +774,8 @@ template <typename T> inline Exact_match<T> m_Exact(const T &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;
@@ -777,7 +786,9 @@ struct CmpClass_match {
 
   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;
       }
@@ -1042,7 +1053,8 @@ inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&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;
@@ -1072,7 +1084,8 @@ struct MaxMin_match {
     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));
   }
 };
 
@@ -1416,89 +1429,78 @@ template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
 //
 
 /// \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
-- 
2.40.0