LLVM API Documentation
00001 //===-- llvm/Support/PatternMatch.h - Match on the LLVM IR ------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // 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 it allows you to 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 /// m_Value() - Match an arbitrary value and ignore it. 00050 inline leaf_ty<Value> m_Value() { return leaf_ty<Value>(); } 00051 /// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it. 00052 inline leaf_ty<ConstantInt> m_ConstantInt() { return leaf_ty<ConstantInt>(); } 00053 00054 template<int64_t Val> 00055 struct constantint_ty { 00056 template<typename ITy> 00057 bool match(ITy *V) { 00058 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 00059 const APInt &CIV = CI->getValue(); 00060 if (Val >= 0) 00061 return CIV == Val; 00062 // If Val is negative, and CI is shorter than it, truncate to the right 00063 // number of bits. If it is larger, then we have to sign extend. Just 00064 // compare their negated values. 00065 return -CIV == -Val; 00066 } 00067 return false; 00068 } 00069 }; 00070 00071 /// m_ConstantInt(int64_t) - Match a ConstantInt with a specific value 00072 /// and ignore it. 00073 template<int64_t Val> 00074 inline constantint_ty<Val> m_ConstantInt() { 00075 return constantint_ty<Val>(); 00076 } 00077 00078 struct zero_ty { 00079 template<typename ITy> 00080 bool match(ITy *V) { 00081 if (const Constant *C = dyn_cast<Constant>(V)) 00082 return C->isNullValue(); 00083 return false; 00084 } 00085 }; 00086 00087 /// m_Zero() - Match an arbitrary zero/null constant. 00088 inline zero_ty m_Zero() { return zero_ty(); } 00089 00090 00091 template<typename Class> 00092 struct bind_ty { 00093 Class *&VR; 00094 bind_ty(Class *&V) : VR(V) {} 00095 00096 template<typename ITy> 00097 bool match(ITy *V) { 00098 if (Class *CV = dyn_cast<Class>(V)) { 00099 VR = CV; 00100 return true; 00101 } 00102 return false; 00103 } 00104 }; 00105 00106 /// m_Value - Match a value, capturing it if we match. 00107 inline bind_ty<Value> m_Value(Value *&V) { return V; } 00108 00109 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match. 00110 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; } 00111 00112 /// specificval_ty - Match a specified Value*. 00113 struct specificval_ty { 00114 const Value *Val; 00115 specificval_ty(const Value *V) : Val(V) {} 00116 00117 template<typename ITy> 00118 bool match(ITy *V) { 00119 return V == Val; 00120 } 00121 }; 00122 00123 /// m_Specific - Match if we have a specific specified value. 00124 inline specificval_ty m_Specific(const Value *V) { return V; } 00125 00126 00127 //===----------------------------------------------------------------------===// 00128 // Matchers for specific binary operators. 00129 // 00130 00131 template<typename LHS_t, typename RHS_t, 00132 unsigned Opcode, typename ConcreteTy = BinaryOperator> 00133 struct BinaryOp_match { 00134 LHS_t L; 00135 RHS_t R; 00136 00137 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 00138 00139 template<typename OpTy> 00140 bool match(OpTy *V) { 00141 if (V->getValueID() == Value::InstructionVal + Opcode) { 00142 ConcreteTy *I = cast<ConcreteTy>(V); 00143 return I->getOpcode() == Opcode && L.match(I->getOperand(0)) && 00144 R.match(I->getOperand(1)); 00145 } 00146 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00147 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) && 00148 R.match(CE->getOperand(1)); 00149 return false; 00150 } 00151 }; 00152 00153 template<typename LHS, typename RHS> 00154 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L, 00155 const RHS &R) { 00156 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R); 00157 } 00158 00159 template<typename LHS, typename RHS> 00160 inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L, 00161 const RHS &R) { 00162 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R); 00163 } 00164 00165 template<typename LHS, typename RHS> 00166 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L, 00167 const RHS &R) { 00168 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R); 00169 } 00170 00171 template<typename LHS, typename RHS> 00172 inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L, 00173 const RHS &R) { 00174 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R); 00175 } 00176 00177 template<typename LHS, typename RHS> 00178 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L, 00179 const RHS &R) { 00180 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R); 00181 } 00182 00183 template<typename LHS, typename RHS> 00184 inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L, 00185 const RHS &R) { 00186 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R); 00187 } 00188 00189 template<typename LHS, typename RHS> 00190 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L, 00191 const RHS &R) { 00192 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R); 00193 } 00194 00195 template<typename LHS, typename RHS> 00196 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L, 00197 const RHS &R) { 00198 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R); 00199 } 00200 00201 template<typename LHS, typename RHS> 00202 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L, 00203 const RHS &R) { 00204 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R); 00205 } 00206 00207 template<typename LHS, typename RHS> 00208 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L, 00209 const RHS &R) { 00210 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R); 00211 } 00212 00213 template<typename LHS, typename RHS> 00214 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L, 00215 const RHS &R) { 00216 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R); 00217 } 00218 00219 template<typename LHS, typename RHS> 00220 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L, 00221 const RHS &R) { 00222 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R); 00223 } 00224 00225 template<typename LHS, typename RHS> 00226 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L, 00227 const RHS &R) { 00228 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R); 00229 } 00230 00231 template<typename LHS, typename RHS> 00232 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L, 00233 const RHS &R) { 00234 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R); 00235 } 00236 00237 template<typename LHS, typename RHS> 00238 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L, 00239 const RHS &R) { 00240 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R); 00241 } 00242 00243 template<typename LHS, typename RHS> 00244 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L, 00245 const RHS &R) { 00246 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R); 00247 } 00248 00249 template<typename LHS, typename RHS> 00250 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L, 00251 const RHS &R) { 00252 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R); 00253 } 00254 00255 template<typename LHS, typename RHS> 00256 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L, 00257 const RHS &R) { 00258 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R); 00259 } 00260 00261 //===----------------------------------------------------------------------===// 00262 // Matchers for either AShr or LShr .. for convenience 00263 // 00264 template<typename LHS_t, typename RHS_t, typename ConcreteTy = BinaryOperator> 00265 struct Shr_match { 00266 LHS_t L; 00267 RHS_t R; 00268 00269 Shr_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 00270 00271 template<typename OpTy> 00272 bool match(OpTy *V) { 00273 if (V->getValueID() == Value::InstructionVal + Instruction::LShr || 00274 V->getValueID() == Value::InstructionVal + Instruction::AShr) { 00275 ConcreteTy *I = cast<ConcreteTy>(V); 00276 return (I->getOpcode() == Instruction::AShr || 00277 I->getOpcode() == Instruction::LShr) && 00278 L.match(I->getOperand(0)) && 00279 R.match(I->getOperand(1)); 00280 } 00281 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00282 return (CE->getOpcode() == Instruction::LShr || 00283 CE->getOpcode() == Instruction::AShr) && 00284 L.match(CE->getOperand(0)) && 00285 R.match(CE->getOperand(1)); 00286 return false; 00287 } 00288 }; 00289 00290 template<typename LHS, typename RHS> 00291 inline Shr_match<LHS, RHS> m_Shr(const LHS &L, const RHS &R) { 00292 return Shr_match<LHS, RHS>(L, R); 00293 } 00294 00295 //===----------------------------------------------------------------------===// 00296 // Matchers for binary classes 00297 // 00298 00299 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType> 00300 struct BinaryOpClass_match { 00301 OpcType *Opcode; 00302 LHS_t L; 00303 RHS_t R; 00304 00305 BinaryOpClass_match(OpcType &Op, const LHS_t &LHS, 00306 const RHS_t &RHS) 00307 : Opcode(&Op), L(LHS), R(RHS) {} 00308 BinaryOpClass_match(const LHS_t &LHS, const RHS_t &RHS) 00309 : Opcode(0), L(LHS), R(RHS) {} 00310 00311 template<typename OpTy> 00312 bool match(OpTy *V) { 00313 if (Class *I = dyn_cast<Class>(V)) 00314 if (L.match(I->getOperand(0)) && 00315 R.match(I->getOperand(1))) { 00316 if (Opcode) 00317 *Opcode = I->getOpcode(); 00318 return true; 00319 } 00320 #if 0 // Doesn't handle constantexprs yet! 00321 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00322 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) && 00323 R.match(CE->getOperand(1)); 00324 #endif 00325 return false; 00326 } 00327 }; 00328 00329 template<typename LHS, typename RHS> 00330 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps> 00331 m_Shift(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) { 00332 return BinaryOpClass_match<LHS, RHS, 00333 BinaryOperator, Instruction::BinaryOps>(Op, L, R); 00334 } 00335 00336 template<typename LHS, typename RHS> 00337 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps> 00338 m_Shift(const LHS &L, const RHS &R) { 00339 return BinaryOpClass_match<LHS, RHS, 00340 BinaryOperator, Instruction::BinaryOps>(L, R); 00341 } 00342 00343 //===----------------------------------------------------------------------===// 00344 // Matchers for CmpInst classes 00345 // 00346 00347 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy> 00348 struct CmpClass_match { 00349 PredicateTy &Predicate; 00350 LHS_t L; 00351 RHS_t R; 00352 00353 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, 00354 const RHS_t &RHS) 00355 : Predicate(Pred), L(LHS), R(RHS) {} 00356 00357 template<typename OpTy> 00358 bool match(OpTy *V) { 00359 if (Class *I = dyn_cast<Class>(V)) 00360 if (L.match(I->getOperand(0)) && 00361 R.match(I->getOperand(1))) { 00362 Predicate = I->getPredicate(); 00363 return true; 00364 } 00365 return false; 00366 } 00367 }; 00368 00369 template<typename LHS, typename RHS> 00370 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate> 00371 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 00372 return CmpClass_match<LHS, RHS, 00373 ICmpInst, ICmpInst::Predicate>(Pred, L, R); 00374 } 00375 00376 template<typename LHS, typename RHS> 00377 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate> 00378 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 00379 return CmpClass_match<LHS, RHS, 00380 FCmpInst, FCmpInst::Predicate>(Pred, L, R); 00381 } 00382 00383 //===----------------------------------------------------------------------===// 00384 // Matchers for SelectInst classes 00385 // 00386 00387 template<typename Cond_t, typename LHS_t, typename RHS_t> 00388 struct SelectClass_match { 00389 Cond_t C; 00390 LHS_t L; 00391 RHS_t R; 00392 00393 SelectClass_match(const Cond_t &Cond, const LHS_t &LHS, 00394 const RHS_t &RHS) 00395 : C(Cond), L(LHS), R(RHS) {} 00396 00397 template<typename OpTy> 00398 bool match(OpTy *V) { 00399 if (SelectInst *I = dyn_cast<SelectInst>(V)) 00400 return C.match(I->getOperand(0)) && 00401 L.match(I->getOperand(1)) && 00402 R.match(I->getOperand(2)); 00403 return false; 00404 } 00405 }; 00406 00407 template<typename Cond, typename LHS, typename RHS> 00408 inline SelectClass_match<Cond, LHS, RHS> 00409 m_Select(const Cond &C, const LHS &L, const RHS &R) { 00410 return SelectClass_match<Cond, LHS, RHS>(C, L, R); 00411 } 00412 00413 /// m_SelectCst - This matches a select of two constants, e.g.: 00414 /// m_SelectCst(m_Value(V), -1, 0) 00415 template<int64_t L, int64_t R, typename Cond> 00416 inline SelectClass_match<Cond, constantint_ty<L>, constantint_ty<R> > 00417 m_SelectCst(const Cond &C) { 00418 return SelectClass_match<Cond, constantint_ty<L>, 00419 constantint_ty<R> >(C, m_ConstantInt<L>(), 00420 m_ConstantInt<R>()); 00421 } 00422 00423 00424 //===----------------------------------------------------------------------===// 00425 // Matchers for CastInst classes 00426 // 00427 00428 template<typename Op_t, typename Class> 00429 struct CastClass_match { 00430 Op_t Op; 00431 00432 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {} 00433 00434 template<typename OpTy> 00435 bool match(OpTy *V) { 00436 if (Class *I = dyn_cast<Class>(V)) 00437 return Op.match(I->getOperand(0)); 00438 return false; 00439 } 00440 }; 00441 00442 template<typename Class, typename OpTy> 00443 inline CastClass_match<OpTy, Class> m_Cast(const OpTy &Op) { 00444 return CastClass_match<OpTy, Class>(Op); 00445 } 00446 00447 00448 //===----------------------------------------------------------------------===// 00449 // Matchers for unary operators 00450 // 00451 00452 template<typename LHS_t> 00453 struct not_match { 00454 LHS_t L; 00455 00456 not_match(const LHS_t &LHS) : L(LHS) {} 00457 00458 template<typename OpTy> 00459 bool match(OpTy *V) { 00460 if (Instruction *I = dyn_cast<Instruction>(V)) 00461 if (I->getOpcode() == Instruction::Xor) 00462 return matchIfNot(I->getOperand(0), I->getOperand(1)); 00463 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00464 if (CE->getOpcode() == Instruction::Xor) 00465 return matchIfNot(CE->getOperand(0), CE->getOperand(1)); 00466 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 00467 return L.match(ConstantExpr::getNot(CI)); 00468 return false; 00469 } 00470 private: 00471 bool matchIfNot(Value *LHS, Value *RHS) { 00472 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) 00473 return CI->isAllOnesValue() && L.match(LHS); 00474 if (ConstantInt *CI = dyn_cast<ConstantInt>(LHS)) 00475 return CI->isAllOnesValue() && L.match(RHS); 00476 if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS)) 00477 return CV->isAllOnesValue() && L.match(LHS); 00478 if (ConstantVector *CV = dyn_cast<ConstantVector>(LHS)) 00479 return CV->isAllOnesValue() && L.match(RHS); 00480 return false; 00481 } 00482 }; 00483 00484 template<typename LHS> 00485 inline not_match<LHS> m_Not(const LHS &L) { return L; } 00486 00487 00488 template<typename LHS_t> 00489 struct neg_match { 00490 LHS_t L; 00491 00492 neg_match(const LHS_t &LHS) : L(LHS) {} 00493 00494 template<typename OpTy> 00495 bool match(OpTy *V) { 00496 if (Instruction *I = dyn_cast<Instruction>(V)) 00497 if (I->getOpcode() == Instruction::Sub) 00498 return matchIfNeg(I->getOperand(0), I->getOperand(1)); 00499 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00500 if (CE->getOpcode() == Instruction::Sub) 00501 return matchIfNeg(CE->getOperand(0), CE->getOperand(1)); 00502 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 00503 return L.match(ConstantExpr::getNeg(CI)); 00504 return false; 00505 } 00506 private: 00507 bool matchIfNeg(Value *LHS, Value *RHS) { 00508 return LHS == ConstantFP::getZeroValueForNegation(LHS->getType()) && 00509 L.match(RHS); 00510 } 00511 }; 00512 00513 template<typename LHS> 00514 inline neg_match<LHS> m_Neg(const LHS &L) { return L; } 00515 00516 00517 template<typename LHS_t> 00518 struct fneg_match { 00519 LHS_t L; 00520 00521 fneg_match(const LHS_t &LHS) : L(LHS) {} 00522 00523 template<typename OpTy> 00524 bool match(OpTy *V) { 00525 if (Instruction *I = dyn_cast<Instruction>(V)) 00526 if (I->getOpcode() == Instruction::FSub) 00527 return matchIfFNeg(I->getOperand(0), I->getOperand(1)); 00528 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00529 if (CE->getOpcode() == Instruction::FSub) 00530 return matchIfFNeg(CE->getOperand(0), CE->getOperand(1)); 00531 if (ConstantFP *CF = dyn_cast<ConstantFP>(V)) 00532 return L.match(ConstantExpr::getFNeg(CF)); 00533 return false; 00534 } 00535 private: 00536 bool matchIfFNeg(Value *LHS, Value *RHS) { 00537 return LHS == ConstantFP::getZeroValueForNegation(LHS->getType()) && 00538 L.match(RHS); 00539 } 00540 }; 00541 00542 template<typename LHS> 00543 inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; } 00544 00545 00546 //===----------------------------------------------------------------------===// 00547 // Matchers for control flow 00548 // 00549 00550 template<typename Cond_t> 00551 struct brc_match { 00552 Cond_t Cond; 00553 BasicBlock *&T, *&F; 00554 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f) 00555 : Cond(C), T(t), F(f) { 00556 } 00557 00558 template<typename OpTy> 00559 bool match(OpTy *V) { 00560 if (BranchInst *BI = dyn_cast<BranchInst>(V)) 00561 if (BI->isConditional()) { 00562 if (Cond.match(BI->getCondition())) { 00563 T = BI->getSuccessor(0); 00564 F = BI->getSuccessor(1); 00565 return true; 00566 } 00567 } 00568 return false; 00569 } 00570 }; 00571 00572 template<typename Cond_t> 00573 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) { 00574 return brc_match<Cond_t>(C, T, F); 00575 } 00576 00577 } // end namespace PatternMatch 00578 } // end namespace llvm 00579 00580 #endif