LLVM API Documentation

PatternMatch.h

Go to the documentation of this file.
00001 //===-- llvm/Support/PatternMatch.h - Match on the LLVM IR ------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file provides a simple and efficient mechanism for performing general
00011 // tree-based pattern matches on the LLVM IR.  The power of these routines is
00012 // that it allows you to write concise patterns that are expressive and easy to
00013 // understand.  The other major advantage of this is that is allows to you
00014 // trivially capture/bind elements in the pattern to variables.  For example,
00015 // you can do something like this:
00016 //
00017 //  Value *Exp = ...
00018 //  Value *X, *Y;  ConstantInt *C1, *C2;      // (X & C1) | (Y & C2)
00019 //  if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
00020 //                      m_And(m_Value(Y), m_ConstantInt(C2))))) {
00021 //    ... Pattern is matched and variables are bound ...
00022 //  }
00023 //
00024 // This is primarily useful to things like the instruction combiner, but can
00025 // also be useful for static analysis tools or code generators.
00026 //
00027 //===----------------------------------------------------------------------===//
00028 
00029 #ifndef LLVM_SUPPORT_PATTERNMATCH_H
00030 #define LLVM_SUPPORT_PATTERNMATCH_H
00031 
00032 #include "llvm/Constants.h"
00033 #include "llvm/Instructions.h"
00034 
00035 namespace llvm {
00036 namespace PatternMatch {
00037 
00038 template<typename Val, typename Pattern>
00039 bool match(Val *V, const Pattern &P) {
00040   return const_cast<Pattern&>(P).match(V);
00041 }
00042 
00043 template<typename Class>
00044 struct leaf_ty {
00045   template<typename ITy>
00046   bool match(ITy *V) { return isa<Class>(V); }
00047 };
00048 
00049 inline leaf_ty<Value> m_Value() { return leaf_ty<Value>(); }
00050 inline leaf_ty<ConstantInt> m_ConstantInt() { return leaf_ty<ConstantInt>(); }
00051 
00052 template<typename Class>
00053 struct bind_ty {
00054   Class *&VR;
00055   bind_ty(Class *&V) : VR(V) {}
00056 
00057   template<typename ITy>
00058   bool match(ITy *V) {
00059     if (Class *CV = dyn_cast<Class>(V)) {
00060       VR = CV;
00061       return true;
00062     }
00063     return false;
00064   }
00065 };
00066 
00067 inline bind_ty<Value> m_Value(Value *&V) { return V; }
00068 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
00069 
00070 //===----------------------------------------------------------------------===//
00071 // Matchers for specific binary operators.
00072 //
00073 
00074 template<typename LHS_t, typename RHS_t, 
00075          unsigned Opcode, typename ConcreteTy = BinaryOperator>
00076 struct BinaryOp_match {
00077   LHS_t L;
00078   RHS_t R;
00079 
00080   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
00081 
00082   template<typename OpTy>
00083   bool match(OpTy *V) {
00084     if (V->getValueType() == Value::InstructionVal + Opcode) {
00085       ConcreteTy *I = cast<ConcreteTy>(V);
00086       return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
00087              R.match(I->getOperand(1));
00088     }
00089     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
00090       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
00091              R.match(CE->getOperand(1));
00092     return false;
00093   }
00094 };
00095 
00096 template<typename LHS, typename RHS>
00097 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
00098                                                         const RHS &R) {
00099   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
00100 }
00101 
00102 template<typename LHS, typename RHS>
00103 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
00104                                                         const RHS &R) {
00105   return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
00106 }
00107 
00108 template<typename LHS, typename RHS>
00109 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
00110                                                         const RHS &R) {
00111   return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
00112 }
00113 
00114 template<typename LHS, typename RHS>
00115 inline BinaryOp_match<LHS, RHS, Instruction::Div> m_Div(const LHS &L,
00116                                                         const RHS &R) {
00117   return BinaryOp_match<LHS, RHS, Instruction::Div>(L, R);
00118 }
00119 
00120 template<typename LHS, typename RHS>
00121 inline BinaryOp_match<LHS, RHS, Instruction::Rem> m_Rem(const LHS &L,
00122                                                         const RHS &R) {
00123   return BinaryOp_match<LHS, RHS, Instruction::Rem>(L, R);
00124 }
00125 
00126 template<typename LHS, typename RHS>
00127 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
00128                                                         const RHS &R) {
00129   return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
00130 }
00131 
00132 template<typename LHS, typename RHS>
00133 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
00134                                                       const RHS &R) {
00135   return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
00136 }
00137 
00138 template<typename LHS, typename RHS>
00139 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
00140                                                         const RHS &R) {
00141   return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
00142 }
00143 
00144 template<typename LHS, typename RHS>
00145 inline BinaryOp_match<LHS, RHS, Instruction::Shl, 
00146                       ShiftInst> m_Shl(const LHS &L, const RHS &R) {
00147   return BinaryOp_match<LHS, RHS, Instruction::Shl, ShiftInst>(L, R);
00148 }
00149 
00150 template<typename LHS, typename RHS>
00151 inline BinaryOp_match<LHS, RHS, Instruction::Shr, 
00152                       ShiftInst> m_Shr(const LHS &L, const RHS &R) {
00153   return BinaryOp_match<LHS, RHS, Instruction::Shr, ShiftInst>(L, R);
00154 }
00155 
00156 //===----------------------------------------------------------------------===//
00157 // Matchers for binary classes
00158 //
00159 
00160 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
00161 struct BinaryOpClass_match {
00162   OpcType &Opcode;
00163   LHS_t L;
00164   RHS_t R;
00165 
00166   BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
00167                       const RHS_t &RHS)
00168     : Opcode(Op), L(LHS), R(RHS) {}
00169 
00170   template<typename OpTy>
00171   bool match(OpTy *V) {
00172     if (Class *I = dyn_cast<Class>(V))
00173       if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
00174         Opcode = I->getOpcode();
00175         return true;
00176       }
00177 #if 0  // Doesn't handle constantexprs yet!
00178     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
00179       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
00180              R.match(CE->getOperand(1));
00181 #endif
00182     return false;
00183   }
00184 };
00185 
00186 template<typename LHS, typename RHS>
00187 inline BinaryOpClass_match<LHS, RHS, SetCondInst, Instruction::BinaryOps>
00188 m_SetCond(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
00189   return BinaryOpClass_match<LHS, RHS, 
00190                              SetCondInst, Instruction::BinaryOps>(Op, L, R);
00191 }
00192 
00193 template<typename LHS, typename RHS>
00194 inline BinaryOpClass_match<LHS, RHS, ShiftInst, Instruction::OtherOps>
00195 m_Shift(Instruction::OtherOps &Op, const LHS &L, const RHS &R) {
00196   return BinaryOpClass_match<LHS, RHS, 
00197                              ShiftInst, Instruction::OtherOps>(Op, L, R);
00198 }
00199 
00200 template<typename LHS, typename RHS>
00201 inline BinaryOpClass_match<LHS, RHS, ShiftInst, Instruction::OtherOps>
00202 m_Shift(const LHS &L, const RHS &R) {
00203   Instruction::OtherOps Op; 
00204   return BinaryOpClass_match<LHS, RHS, 
00205                              ShiftInst, Instruction::OtherOps>(Op, L, R);
00206 }
00207 
00208 //===----------------------------------------------------------------------===//
00209 // Matchers for unary operators
00210 //
00211 
00212 template<typename LHS_t>
00213 struct neg_match {
00214   LHS_t L;
00215 
00216   neg_match(const LHS_t &LHS) : L(LHS) {}
00217 
00218   template<typename OpTy>
00219   bool match(OpTy *V) {
00220     if (Instruction *I = dyn_cast<Instruction>(V))
00221       if (I->getOpcode() == Instruction::Sub)
00222         return matchIfNeg(I->getOperand(0), I->getOperand(1));
00223     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
00224       if (CE->getOpcode() == Instruction::Sub)
00225         return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
00226     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
00227       return L.match(ConstantExpr::getNeg(CI));
00228     return false;
00229   }
00230 private:
00231   bool matchIfNeg(Value *LHS, Value *RHS) {
00232     if (!LHS->getType()->isFloatingPoint())
00233       return LHS == Constant::getNullValue(LHS->getType()) && L.match(RHS);
00234     else
00235       return LHS == ConstantFP::get(LHS->getType(), -0.0) && L.match(RHS);
00236   }
00237 };
00238 
00239 template<typename LHS>
00240 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
00241 
00242 
00243 template<typename LHS_t>
00244 struct not_match {
00245   LHS_t L;
00246 
00247   not_match(const LHS_t &LHS) : L(LHS) {}
00248 
00249   template<typename OpTy>
00250   bool match(OpTy *V) {
00251     if (Instruction *I = dyn_cast<Instruction>(V))
00252       if (I->getOpcode() == Instruction::Xor)
00253         return matchIfNot(I->getOperand(0), I->getOperand(1));
00254     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
00255       if (CE->getOpcode() == Instruction::Xor)
00256         return matchIfNot(CE->getOperand(0), CE->getOperand(1));
00257     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
00258       return L.match(ConstantExpr::getNot(CI));
00259     return false;
00260   }
00261 private:
00262   bool matchIfNot(Value *LHS, Value *RHS) {
00263     if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(RHS))
00264       return CI->isAllOnesValue() && L.match(LHS);
00265     else if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(LHS))
00266       return CI->isAllOnesValue() && L.match(RHS);
00267     return false;
00268   }
00269 };
00270 
00271 template<typename LHS>
00272 inline not_match<LHS> m_Not(const LHS &L) { return L; }
00273 
00274 //===----------------------------------------------------------------------===//
00275 // Matchers for control flow
00276 //
00277 
00278 template<typename Cond_t>
00279 struct brc_match {
00280   Cond_t Cond;
00281   BasicBlock *&T, *&F;
00282   brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
00283     : Cond(C), T(t), F(f) {
00284   }
00285 
00286   template<typename OpTy>
00287   bool match(OpTy *V) {
00288     if (BranchInst *BI = dyn_cast<BranchInst>(V))
00289       if (BI->isConditional()) {
00290         if (Cond.match(BI->getCondition())) {
00291           T = BI->getSuccessor(0);
00292           F = BI->getSuccessor(1);
00293           return true;
00294         }
00295       }
00296     return false;
00297   }
00298 };
00299 
00300 template<typename Cond_t>
00301 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){
00302   return brc_match<Cond_t>(C, T, F);
00303 }
00304 
00305 
00306 }} // end llvm::match
00307 
00308 
00309 #endif
00310