LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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