LLVM API Documentation
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