include/llvm/Support/PatternMatch.h

   1 //===-- llvm/Support/PatternMatch.h - Match on the LLVM IR ------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file provides a simple and efficient mechanism for performing general
  11 // tree-based pattern matches on the LLVM IR.  The power of these routines is
  12 // that it allows you to write concise patterns that are expressive and easy to
  13 // understand.  The other major advantage of this is that is allows to you
  14 // trivially capture/bind elements in the pattern to variables.  For example,
  15 // you can do something like this:
  16 //
  17 //  Value *Exp = ...
  18 //  Value *X, *Y;  ConstantInt *C1, *C2;      // (X & C1) | (Y & C2)
  19 //  if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
  20 //                      m_And(m_Value(Y), m_ConstantInt(C2))))) {
  21 //    ... Pattern is matched and variables are bound ...
  22 //  }
  23 //
  24 // This is primarily useful to things like the instruction combiner, but can
  25 // also be useful for static analysis tools or code generators.
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #ifndef LLVM_SUPPORT_PATTERNMATCH_H
  30 #define LLVM_SUPPORT_PATTERNMATCH_H
  31
  32 #include "llvm/Constants.h"
  33 #include "llvm/Instructions.h"
  34
  35 namespace llvm {
  36 namespace PatternMatch {
  37
  38 template<typename Val, typename Pattern>
  39 bool match(Val *V, const Pattern &P) {
  40   return const_cast<Pattern&>(P).match(V);
  41 }
  42
  43 template<typename Class>
  44 struct leaf_ty {
  45   template<typename ITy>
  46   bool match(ITy *V) { return isa<Class>(V); }
  47 };
  48
  49 inline leaf_ty<Value> m_Value() { return leaf_ty<Value>(); }
  50 inline leaf_ty<ConstantInt> m_ConstantInt() { return leaf_ty<ConstantInt>(); }
  51
  52 template<typename Class>
  53 struct bind_ty {
  54   Class *&VR;
  55   bind_ty(Class *&V) : VR(V) {}
  56
  57   template<typename ITy>
  58   bool match(ITy *V) {
  59     if (Class *CV = dyn_cast<Class>(V)) {
  60       VR = CV;
  61       return true;
  62     }
  63     return false;
  64   }
  65 };
  66
  67 inline bind_ty<Value> m_Value(Value *&V) { return V; }
  68 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
  69
  70 //===----------------------------------------------------------------------===//
  71 // Matchers for specific binary operators
  72 //
  73
  74 template<typename LHS_t, typename RHS_t, unsigned Opcode>
  75 struct BinaryOp_match {
  76   LHS_t L;
  77   RHS_t R;
  78
  79   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
  80
  81   template<typename OpTy>
  82   bool match(OpTy *V) {
  83     if (Instruction *I = dyn_cast<Instruction>(V))
  84       return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
  85              R.match(I->getOperand(1));
  86     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
  87       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
  88              R.match(CE->getOperand(1));
  89     return false;
  90   }
  91 };
  92
  93 template<typename LHS, typename RHS>
  94 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
  95                                                         const RHS &R) {
  96   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
  97 }
  98
  99 template<typename LHS, typename RHS>
 100 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
 101                                                         const RHS &R) {
 102   return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
 103 }
 104
 105 template<typename LHS, typename RHS>
 106 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
 107                                                         const RHS &R) {
 108   return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
 109 }
 110
 111 template<typename LHS, typename RHS>
 112 inline BinaryOp_match<LHS, RHS, Instruction::Div> m_Div(const LHS &L,
 113                                                         const RHS &R) {
 114   return BinaryOp_match<LHS, RHS, Instruction::Div>(L, R);
 115 }
 116
 117 template<typename LHS, typename RHS>
 118 inline BinaryOp_match<LHS, RHS, Instruction::Rem> m_Rem(const LHS &L,
 119                                                         const RHS &R) {
 120   return BinaryOp_match<LHS, RHS, Instruction::Rem>(L, R);
 121 }
 122
 123 template<typename LHS, typename RHS>
 124 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
 125                                                         const RHS &R) {
 126   return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
 127 }
 128
 129 template<typename LHS, typename RHS>
 130 inline BinaryOp_match<LHS, RHS, Instruction::Rem> m_Or(const LHS &L,
 131                                                        const RHS &R) {
 132   return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
 133 }
 134
 135 template<typename LHS, typename RHS>
 136 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
 137                                                         const RHS &R) {
 138   return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
 139 }
 140
 141 template<typename LHS, typename RHS>
 142 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
 143                                                         const RHS &R) {
 144   return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
 145 }
 146
 147 template<typename LHS, typename RHS>
 148 inline BinaryOp_match<LHS, RHS, Instruction::Shr> m_Shr(const LHS &L,
 149                                                         const RHS &R) {
 150   return BinaryOp_match<LHS, RHS, Instruction::Shr>(L, R);
 151 }
 152
 153 //===----------------------------------------------------------------------===//
 154 // Matchers for binary classes
 155 //
 156
 157 template<typename LHS_t, typename RHS_t, typename Class>
 158 struct BinaryOpClass_match {
 159   Instruction::BinaryOps &Opcode;
 160   LHS_t L;
 161   RHS_t R;
 162
 163   BinaryOpClass_match(Instruction::BinaryOps &Op, const LHS_t &LHS,
 164                       const RHS_t &RHS)
 165     : Opcode(Op), L(LHS), R(RHS) {}
 166
 167   template<typename OpTy>
 168   bool match(OpTy *V) {
 169     if (Class *I = dyn_cast<Class>(V))
 170       if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
 171         Opcode = I->getOpcode();
 172         return true;
 173       }
 174 #if 0  // Doesn't handle constantexprs yet!
 175     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 176       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
 177              R.match(CE->getOperand(1));
 178 #endif
 179     return false;
 180   }
 181 };
 182
 183 template<typename LHS, typename RHS>
 184 inline BinaryOpClass_match<LHS, RHS, SetCondInst>
 185 m_SetCond(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
 186   return BinaryOpClass_match<LHS, RHS, SetCondInst>(Op, L, R);
 187 }
 188
 189
 190 //===----------------------------------------------------------------------===//
 191 // Matchers for unary operators
 192 //
 193
 194 template<typename LHS_t>
 195 struct neg_match {
 196   LHS_t L;
 197
 198   neg_match(const LHS_t &LHS) : L(LHS) {}
 199
 200   template<typename OpTy>
 201   bool match(OpTy *V) {
 202     if (Instruction *I = dyn_cast<Instruction>(V))
 203       if (I->getOpcode() == Instruction::Sub)
 204         return matchIfNeg(I->getOperand(0), I->getOperand(1));
 205     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 206       if (CE->getOpcode() == Instruction::Sub)
 207         return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
 208     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
 209       return L.match(ConstantExpr::getNeg(CI));
 210     return false;
 211   }
 212 private:
 213   bool matchIfNeg(Value *LHS, Value *RHS) {
 214     if (!LHS->getType()->isFloatingPoint())
 215       return LHS == Constant::getNullValue(LHS->getType()) && L.match(RHS);
 216     else
 217       return LHS == ConstantFP::get(LHS->getType(), -0.0) && L.match(RHS);
 218   }
 219 };
 220
 221 template<typename LHS>
 222 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
 223
 224
 225 template<typename LHS_t>
 226 struct not_match {
 227   LHS_t L;
 228
 229   not_match(const LHS_t &LHS) : L(LHS) {}
 230
 231   template<typename OpTy>
 232   bool match(OpTy *V) {
 233     if (Instruction *I = dyn_cast<Instruction>(V))
 234       if (I->getOpcode() == Instruction::Xor)
 235         return matchIfNot(I->getOperand(0), I->getOperand(1));
 236     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 237       if (CE->getOpcode() == Instruction::Xor)
 238         return matchIfNot(CE->getOperand(0), CE->getOperand(1));
 239     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
 240       return L.match(ConstantExpr::getNot(CI));
 241     return false;
 242   }
 243 private:
 244   bool matchIfNot(Value *LHS, Value *RHS) {
 245     if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(RHS))
 246       return CI->isAllOnesValue() && L.match(LHS);
 247     else if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(LHS))
 248       return CI->isAllOnesValue() && L.match(RHS);
 249     return false;
 250   }
 251 };
 252
 253 template<typename LHS>
 254 inline not_match<LHS> m_Not(const LHS &L) { return L; }
 255
 256 //===----------------------------------------------------------------------===//
 257 // Matchers for control flow
 258 //
 259
 260 template<typename Cond_t>
 261 struct brc_match {
 262   Cond_t Cond;
 263   BasicBlock *&T, *&F;
 264   brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
 265     : Cond(C), T(t), F(f) {
 266   }
 267
 268   template<typename OpTy>
 269   bool match(OpTy *V) {
 270     if (BranchInst *BI = dyn_cast<BranchInst>(V))
 271       if (BI->isConditional()) {
 272         if (Cond.match(BI->getCondition())) {
 273           T = BI->getSuccessor(0);
 274           F = BI->getSuccessor(1);
 275           return true;
 276         }
 277       }
 278     return false;
 279   }
 280 };
 281
 282 template<typename Cond_t>
 283 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){
 284   return brc_match<Cond_t>(C, T, F);
 285 }
 286
 287
 288 }} // end llvm::match
 289
 290
 291 #endif
 292