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>
00161 struct BinaryOpClass_match {
00162   Instruction::BinaryOps &Opcode;
00163   LHS_t L;
00164   RHS_t R;
00165 
00166   BinaryOpClass_match(Instruction::BinaryOps &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>
00188 m_SetCond(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
00189   return BinaryOpClass_match<LHS, RHS, SetCondInst>(Op, L, R);
00190 }
00191 
00192 
00193 //===----------------------------------------------------------------------===//
00194 // Matchers for unary operators
00195 //
00196 
00197 template<typename LHS_t>
00198 struct neg_match {
00199   LHS_t L;
00200 
00201   neg_match(const LHS_t &LHS) : L(LHS) {}
00202 
00203   template<typename OpTy>
00204   bool match(OpTy *V) {
00205     if (Instruction *I = dyn_cast<Instruction>(V))
00206       if (I->getOpcode() == Instruction::Sub)
00207         return matchIfNeg(I->getOperand(0), I->getOperand(1));
00208     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
00209       if (CE->getOpcode() == Instruction::Sub)
00210         return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
00211     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
00212       return L.match(ConstantExpr::getNeg(CI));
00213     return false;
00214   }
00215 private:
00216   bool matchIfNeg(Value *LHS, Value *RHS) {
00217     if (!LHS->getType()->isFloatingPoint())
00218       return LHS == Constant::getNullValue(LHS->getType()) && L.match(RHS);
00219     else
00220       return LHS == ConstantFP::get(LHS->getType(), -0.0) && L.match(RHS);
00221   }
00222 };
00223 
00224 template<typename LHS>
00225 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
00226 
00227 
00228 template<typename LHS_t>
00229 struct not_match {
00230   LHS_t L;
00231 
00232   not_match(const LHS_t &LHS) : L(LHS) {}
00233 
00234   template<typename OpTy>
00235   bool match(OpTy *V) {
00236     if (Instruction *I = dyn_cast<Instruction>(V))
00237       if (I->getOpcode() == Instruction::Xor)
00238         return matchIfNot(I->getOperand(0), I->getOperand(1));
00239     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
00240       if (CE->getOpcode() == Instruction::Xor)
00241         return matchIfNot(CE->getOperand(0), CE->getOperand(1));
00242     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
00243       return L.match(ConstantExpr::getNot(CI));
00244     return false;
00245   }
00246 private:
00247   bool matchIfNot(Value *LHS, Value *RHS) {
00248     if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(RHS))
00249       return CI->isAllOnesValue() && L.match(LHS);
00250     else if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(LHS))
00251       return CI->isAllOnesValue() && L.match(RHS);
00252     return false;
00253   }
00254 };
00255 
00256 template<typename LHS>
00257 inline not_match<LHS> m_Not(const LHS &L) { return L; }
00258 
00259 //===----------------------------------------------------------------------===//
00260 // Matchers for control flow
00261 //
00262 
00263 template<typename Cond_t>
00264 struct brc_match {
00265   Cond_t Cond;
00266   BasicBlock *&T, *&F;
00267   brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
00268     : Cond(C), T(t), F(f) {
00269   }
00270 
00271   template<typename OpTy>
00272   bool match(OpTy *V) {
00273     if (BranchInst *BI = dyn_cast<BranchInst>(V))
00274       if (BI->isConditional()) {
00275         if (Cond.match(BI->getCondition())) {
00276           T = BI->getSuccessor(0);
00277           F = BI->getSuccessor(1);
00278           return true;
00279         }
00280       }
00281     return false;
00282   }
00283 };
00284 
00285 template<typename Cond_t>
00286 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){
00287   return brc_match<Cond_t>(C, T, F);
00288 }
00289 
00290 
00291 }} // end llvm::match
00292 
00293 
00294 #endif
00295