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 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