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, unsigned Opcode> 00075 struct BinaryOp_match { 00076 LHS_t L; 00077 RHS_t R; 00078 00079 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 00080 00081 template<typename OpTy> 00082 bool match(OpTy *V) { 00083 if (Instruction *I = dyn_cast<Instruction>(V)) 00084 return I->getOpcode() == Opcode && L.match(I->getOperand(0)) && 00085 R.match(I->getOperand(1)); 00086 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00087 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) && 00088 R.match(CE->getOperand(1)); 00089 return false; 00090 } 00091 }; 00092 00093 template<typename LHS, typename RHS> 00094 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L, 00095 const RHS &R) { 00096 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R); 00097 } 00098 00099 template<typename LHS, typename RHS> 00100 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L, 00101 const RHS &R) { 00102 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R); 00103 } 00104 00105 template<typename LHS, typename RHS> 00106 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L, 00107 const RHS &R) { 00108 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R); 00109 } 00110 00111 template<typename LHS, typename RHS> 00112 inline BinaryOp_match<LHS, RHS, Instruction::Div> m_Div(const LHS &L, 00113 const RHS &R) { 00114 return BinaryOp_match<LHS, RHS, Instruction::Div>(L, R); 00115 } 00116 00117 template<typename LHS, typename RHS> 00118 inline BinaryOp_match<LHS, RHS, Instruction::Rem> m_Rem(const LHS &L, 00119 const RHS &R) { 00120 return BinaryOp_match<LHS, RHS, Instruction::Rem>(L, R); 00121 } 00122 00123 template<typename LHS, typename RHS> 00124 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L, 00125 const RHS &R) { 00126 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R); 00127 } 00128 00129 template<typename LHS, typename RHS> 00130 inline BinaryOp_match<LHS, RHS, Instruction::Rem> m_Or(const LHS &L, 00131 const RHS &R) { 00132 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R); 00133 } 00134 00135 template<typename LHS, typename RHS> 00136 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L, 00137 const RHS &R) { 00138 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R); 00139 } 00140 00141 template<typename LHS, typename RHS> 00142 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L, 00143 const RHS &R) { 00144 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R); 00145 } 00146 00147 template<typename LHS, typename RHS> 00148 inline BinaryOp_match<LHS, RHS, Instruction::Shr> m_Shr(const LHS &L, 00149 const RHS &R) { 00150 return BinaryOp_match<LHS, RHS, Instruction::Shr>(L, R); 00151 } 00152 00153 //===----------------------------------------------------------------------===// 00154 // Matchers for binary classes 00155 // 00156 00157 template<typename LHS_t, typename RHS_t, typename Class> 00158 struct BinaryOpClass_match { 00159 Instruction::BinaryOps &Opcode; 00160 LHS_t L; 00161 RHS_t R; 00162 00163 BinaryOpClass_match(Instruction::BinaryOps &Op, const LHS_t &LHS, 00164 const RHS_t &RHS) 00165 : Opcode(Op), L(LHS), R(RHS) {} 00166 00167 template<typename OpTy> 00168 bool match(OpTy *V) { 00169 if (Class *I = dyn_cast<Class>(V)) 00170 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) { 00171 Opcode = I->getOpcode(); 00172 return true; 00173 } 00174 #if 0 // Doesn't handle constantexprs yet! 00175 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00176 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) && 00177 R.match(CE->getOperand(1)); 00178 #endif 00179 return false; 00180 } 00181 }; 00182 00183 template<typename LHS, typename RHS> 00184 inline BinaryOpClass_match<LHS, RHS, SetCondInst> 00185 m_SetCond(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) { 00186 return BinaryOpClass_match<LHS, RHS, SetCondInst>(Op, L, R); 00187 } 00188 00189 00190 //===----------------------------------------------------------------------===// 00191 // Matchers for unary operators 00192 // 00193 00194 template<typename LHS_t> 00195 struct neg_match { 00196 LHS_t L; 00197 00198 neg_match(const LHS_t &LHS) : L(LHS) {} 00199 00200 template<typename OpTy> 00201 bool match(OpTy *V) { 00202 if (Instruction *I = dyn_cast<Instruction>(V)) 00203 if (I->getOpcode() == Instruction::Sub) 00204 return matchIfNeg(I->getOperand(0), I->getOperand(1)); 00205 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00206 if (CE->getOpcode() == Instruction::Sub) 00207 return matchIfNeg(CE->getOperand(0), CE->getOperand(1)); 00208 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 00209 return L.match(ConstantExpr::getNeg(CI)); 00210 return false; 00211 } 00212 private: 00213 bool matchIfNeg(Value *LHS, Value *RHS) { 00214 if (!LHS->getType()->isFloatingPoint()) 00215 return LHS == Constant::getNullValue(LHS->getType()) && L.match(RHS); 00216 else 00217 return LHS == ConstantFP::get(LHS->getType(), -0.0) && L.match(RHS); 00218 } 00219 }; 00220 00221 template<typename LHS> 00222 inline neg_match<LHS> m_Neg(const LHS &L) { return L; } 00223 00224 00225 template<typename LHS_t> 00226 struct not_match { 00227 LHS_t L; 00228 00229 not_match(const LHS_t &LHS) : L(LHS) {} 00230 00231 template<typename OpTy> 00232 bool match(OpTy *V) { 00233 if (Instruction *I = dyn_cast<Instruction>(V)) 00234 if (I->getOpcode() == Instruction::Xor) 00235 return matchIfNot(I->getOperand(0), I->getOperand(1)); 00236 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00237 if (CE->getOpcode() == Instruction::Xor) 00238 return matchIfNot(CE->getOperand(0), CE->getOperand(1)); 00239 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 00240 return L.match(ConstantExpr::getNot(CI)); 00241 return false; 00242 } 00243 private: 00244 bool matchIfNot(Value *LHS, Value *RHS) { 00245 if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(RHS)) 00246 return CI->isAllOnesValue() && L.match(LHS); 00247 else if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(LHS)) 00248 return CI->isAllOnesValue() && L.match(RHS); 00249 return false; 00250 } 00251 }; 00252 00253 template<typename LHS> 00254 inline not_match<LHS> m_Not(const LHS &L) { return L; } 00255 00256 //===----------------------------------------------------------------------===// 00257 // Matchers for control flow 00258 // 00259 00260 template<typename Cond_t> 00261 struct brc_match { 00262 Cond_t Cond; 00263 BasicBlock *&T, *&F; 00264 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f) 00265 : Cond(C), T(t), F(f) { 00266 } 00267 00268 template<typename OpTy> 00269 bool match(OpTy *V) { 00270 if (BranchInst *BI = dyn_cast<BranchInst>(V)) 00271 if (BI->isConditional()) { 00272 if (Cond.match(BI->getCondition())) { 00273 T = BI->getSuccessor(0); 00274 F = BI->getSuccessor(1); 00275 return true; 00276 } 00277 } 00278 return false; 00279 } 00280 }; 00281 00282 template<typename Cond_t> 00283 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){ 00284 return brc_match<Cond_t>(C, T, F); 00285 } 00286 00287 00288 }} // end llvm::match 00289 00290 00291 #endif 00292