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 is distributed under the University of Illinois Open Source
   6 // 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 it allows you to
  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 /// m_Value() - Match an arbitrary value and ignore it.
  50 inline leaf_ty<Value> m_Value() { return leaf_ty<Value>(); }
  51 /// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it.
  52 inline leaf_ty<ConstantInt> m_ConstantInt() { return leaf_ty<ConstantInt>(); }
  53
  54 struct zero_ty {
  55   template<typename ITy>
  56   bool match(ITy *V) {
  57     if (const Constant *C = dyn_cast<Constant>(V))
  58       return C->isNullValue();
  59     return false;
  60   }
  61 };
  62
  63 /// m_Zero() - Match an arbitrary zero/null constant.
  64 inline zero_ty m_Zero() { return zero_ty(); }
  65
  66
  67 template<typename Class>
  68 struct bind_ty {
  69   Class *&VR;
  70   bind_ty(Class *&V) : VR(V) {}
  71
  72   template<typename ITy>
  73   bool match(ITy *V) {
  74     if (Class *CV = dyn_cast<Class>(V)) {
  75       VR = CV;
  76       return true;
  77     }
  78     return false;
  79   }
  80 };
  81
  82 /// m_Value - Match a value, capturing it if we match.
  83 inline bind_ty<Value> m_Value(Value *&V) { return V; }
  84
  85 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
  86 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
  87
  88 //===----------------------------------------------------------------------===//
  89 // Matchers for specific binary operators.
  90 //
  91
  92 template<typename LHS_t, typename RHS_t,
  93          unsigned Opcode, typename ConcreteTy = BinaryOperator>
  94 struct BinaryOp_match {
  95   LHS_t L;
  96   RHS_t R;
  97
  98   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
  99
 100   template<typename OpTy>
 101   bool match(OpTy *V) {
 102     if (V->getValueID() == Value::InstructionVal + Opcode) {
 103       ConcreteTy *I = cast<ConcreteTy>(V);
 104       return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
 105              R.match(I->getOperand(1));
 106     }
 107     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 108       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
 109              R.match(CE->getOperand(1));
 110     return false;
 111   }
 112 };
 113
 114 template<typename LHS, typename RHS>
 115 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
 116                                                         const RHS &R) {
 117   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
 118 }
 119
 120 template<typename LHS, typename RHS>
 121 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
 122                                                         const RHS &R) {
 123   return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
 124 }
 125
 126 template<typename LHS, typename RHS>
 127 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
 128                                                         const RHS &R) {
 129   return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
 130 }
 131
 132 template<typename LHS, typename RHS>
 133 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
 134                                                         const RHS &R) {
 135   return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
 136 }
 137
 138 template<typename LHS, typename RHS>
 139 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
 140                                                         const RHS &R) {
 141   return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
 142 }
 143
 144 template<typename LHS, typename RHS>
 145 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
 146                                                         const RHS &R) {
 147   return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
 148 }
 149
 150 template<typename LHS, typename RHS>
 151 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
 152                                                           const RHS &R) {
 153   return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
 154 }
 155
 156 template<typename LHS, typename RHS>
 157 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
 158                                                           const RHS &R) {
 159   return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
 160 }
 161
 162 template<typename LHS, typename RHS>
 163 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
 164                                                         const RHS &R) {
 165   return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
 166 }
 167
 168 template<typename LHS, typename RHS>
 169 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
 170                                                         const RHS &R) {
 171   return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
 172 }
 173
 174 template<typename LHS, typename RHS>
 175 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
 176                                                       const RHS &R) {
 177   return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
 178 }
 179
 180 template<typename LHS, typename RHS>
 181 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
 182                                                         const RHS &R) {
 183   return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
 184 }
 185
 186 template<typename LHS, typename RHS>
 187 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
 188                                                         const RHS &R) {
 189   return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
 190 }
 191
 192 template<typename LHS, typename RHS>
 193 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
 194                                                           const RHS &R) {
 195   return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
 196 }
 197
 198 template<typename LHS, typename RHS>
 199 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
 200                                                           const RHS &R) {
 201   return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
 202 }
 203
 204 //===----------------------------------------------------------------------===//
 205 // Matchers for either AShr or LShr .. for convenience
 206 //
 207 template<typename LHS_t, typename RHS_t, typename ConcreteTy = BinaryOperator>
 208 struct Shr_match {
 209   LHS_t L;
 210   RHS_t R;
 211
 212   Shr_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 213
 214   template<typename OpTy>
 215   bool match(OpTy *V) {
 216     if (V->getValueID() == Value::InstructionVal + Instruction::LShr ||
 217         V->getValueID() == Value::InstructionVal + Instruction::AShr) {
 218       ConcreteTy *I = cast<ConcreteTy>(V);
 219       return (I->getOpcode() == Instruction::AShr ||
 220               I->getOpcode() == Instruction::LShr) &&
 221              L.match(I->getOperand(0)) &&
 222              R.match(I->getOperand(1));
 223     }
 224     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 225       return (CE->getOpcode() == Instruction::LShr ||
 226               CE->getOpcode() == Instruction::AShr) &&
 227              L.match(CE->getOperand(0)) &&
 228              R.match(CE->getOperand(1));
 229     return false;
 230   }
 231 };
 232
 233 template<typename LHS, typename RHS>
 234 inline Shr_match<LHS, RHS> m_Shr(const LHS &L, const RHS &R) {
 235   return Shr_match<LHS, RHS>(L, R);
 236 }
 237
 238 //===----------------------------------------------------------------------===//
 239 // Matchers for binary classes
 240 //
 241
 242 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
 243 struct BinaryOpClass_match {
 244   OpcType *Opcode;
 245   LHS_t L;
 246   RHS_t R;
 247
 248   BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
 249                       const RHS_t &RHS)
 250     : Opcode(&Op), L(LHS), R(RHS) {}
 251   BinaryOpClass_match(const LHS_t &LHS, const RHS_t &RHS)
 252     : Opcode(0), L(LHS), R(RHS) {}
 253
 254   template<typename OpTy>
 255   bool match(OpTy *V) {
 256     if (Class *I = dyn_cast<Class>(V))
 257       if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
 258         if (Opcode)
 259           *Opcode = I->getOpcode();
 260         return true;
 261       }
 262 #if 0  // Doesn't handle constantexprs yet!
 263     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 264       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
 265              R.match(CE->getOperand(1));
 266 #endif
 267     return false;
 268   }
 269 };
 270
 271 template<typename LHS, typename RHS>
 272 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
 273 m_Shift(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
 274   return BinaryOpClass_match<LHS, RHS,
 275                              BinaryOperator, Instruction::BinaryOps>(Op, L, R);
 276 }
 277
 278 template<typename LHS, typename RHS>
 279 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
 280 m_Shift(const LHS &L, const RHS &R) {
 281   return BinaryOpClass_match<LHS, RHS,
 282                              BinaryOperator, Instruction::BinaryOps>(L, R);
 283 }
 284
 285 //===----------------------------------------------------------------------===//
 286 // Matchers for CmpInst classes
 287 //
 288
 289 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
 290 struct CmpClass_match {
 291   PredicateTy &Predicate;
 292   LHS_t L;
 293   RHS_t R;
 294
 295   CmpClass_match(PredicateTy &Pred, const LHS_t &LHS,
 296                  const RHS_t &RHS)
 297     : Predicate(Pred), L(LHS), R(RHS) {}
 298
 299   template<typename OpTy>
 300   bool match(OpTy *V) {
 301     if (Class *I = dyn_cast<Class>(V))
 302       if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
 303         Predicate = I->getPredicate();
 304         return true;
 305       }
 306     return false;
 307   }
 308 };
 309
 310 template<typename LHS, typename RHS>
 311 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
 312 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
 313   return CmpClass_match<LHS, RHS,
 314                         ICmpInst, ICmpInst::Predicate>(Pred, L, R);
 315 }
 316
 317 template<typename LHS, typename RHS>
 318 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
 319 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
 320   return CmpClass_match<LHS, RHS,
 321                         FCmpInst, FCmpInst::Predicate>(Pred, L, R);
 322 }
 323
 324 //===----------------------------------------------------------------------===//
 325 // Matchers for unary operators
 326 //
 327
 328 template<typename LHS_t>
 329 struct not_match {
 330   LHS_t L;
 331
 332   not_match(const LHS_t &LHS) : L(LHS) {}
 333
 334   template<typename OpTy>
 335   bool match(OpTy *V) {
 336     if (Instruction *I = dyn_cast<Instruction>(V))
 337       if (I->getOpcode() == Instruction::Xor)
 338         return matchIfNot(I->getOperand(0), I->getOperand(1));
 339     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 340       if (CE->getOpcode() == Instruction::Xor)
 341         return matchIfNot(CE->getOperand(0), CE->getOperand(1));
 342     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
 343       return L.match(ConstantExpr::getNot(CI));
 344     return false;
 345   }
 346 private:
 347   bool matchIfNot(Value *LHS, Value *RHS) {
 348     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
 349       return CI->isAllOnesValue() && L.match(LHS);
 350     if (ConstantInt *CI = dyn_cast<ConstantInt>(LHS))
 351       return CI->isAllOnesValue() && L.match(RHS);
 352     if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
 353       return CV->isAllOnesValue() && L.match(LHS);
 354     if (ConstantVector *CV = dyn_cast<ConstantVector>(LHS))
 355       return CV->isAllOnesValue() && L.match(RHS);
 356     return false;
 357   }
 358 };
 359
 360 template<typename LHS>
 361 inline not_match<LHS> m_Not(const LHS &L) { return L; }
 362
 363
 364 //===----------------------------------------------------------------------===//
 365 // Matchers for control flow
 366 //
 367
 368 template<typename Cond_t>
 369 struct brc_match {
 370   Cond_t Cond;
 371   BasicBlock *&T, *&F;
 372   brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
 373     : Cond(C), T(t), F(f) {
 374   }
 375
 376   template<typename OpTy>
 377   bool match(OpTy *V) {
 378     if (BranchInst *BI = dyn_cast<BranchInst>(V))
 379       if (BI->isConditional()) {
 380         if (Cond.match(BI->getCondition())) {
 381           T = BI->getSuccessor(0);
 382           F = BI->getSuccessor(1);
 383           return true;
 384         }
 385       }
 386     return false;
 387   }
 388 };
 389
 390 template<typename Cond_t>
 391 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){
 392   return brc_match<Cond_t>(C, T, F);
 393 }
 394
 395
 396 }} // end llvm::match
 397
 398
 399 #endif
 400