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