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 constantint_ty {
  55   int64_t Val;
  56   explicit constantint_ty(int64_t val) : Val(val) {}
  57
  58   template<typename ITy>
  59   bool match(ITy *V) {
  60     return isa<ConstantInt>(V) && cast<ConstantInt>(V)->getSExtValue() == Val;
  61   }
  62 };
  63
  64 /// m_ConstantInt(int64_t) - Match a ConstantInt with a specific value
  65 /// and ignore it.
  66 inline constantint_ty m_ConstantInt(int64_t Val) {
  67   return constantint_ty(Val);
  68 }
  69
  70 struct zero_ty {
  71   template<typename ITy>
  72   bool match(ITy *V) {
  73     if (const Constant *C = dyn_cast<Constant>(V))
  74       return C->isNullValue();
  75     return false;
  76   }
  77 };
  78
  79 /// m_Zero() - Match an arbitrary zero/null constant.
  80 inline zero_ty m_Zero() { return zero_ty(); }
  81
  82
  83 template<typename Class>
  84 struct bind_ty {
  85   Class *&VR;
  86   bind_ty(Class *&V) : VR(V) {}
  87
  88   template<typename ITy>
  89   bool match(ITy *V) {
  90     if (Class *CV = dyn_cast<Class>(V)) {
  91       VR = CV;
  92       return true;
  93     }
  94     return false;
  95   }
  96 };
  97
  98 /// m_Value - Match a value, capturing it if we match.
  99 inline bind_ty<Value> m_Value(Value *&V) { return V; }
 100
 101 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
 102 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
 103
 104 //===----------------------------------------------------------------------===//
 105 // Matchers for specific binary operators.
 106 //
 107
 108 template<typename LHS_t, typename RHS_t,
 109          unsigned Opcode, typename ConcreteTy = BinaryOperator>
 110 struct BinaryOp_match {
 111   LHS_t L;
 112   RHS_t R;
 113
 114   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 115
 116   template<typename OpTy>
 117   bool match(OpTy *V) {
 118     if (V->getValueID() == Value::InstructionVal + Opcode) {
 119       ConcreteTy *I = cast<ConcreteTy>(V);
 120       return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
 121              R.match(I->getOperand(1));
 122     }
 123     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 124       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
 125              R.match(CE->getOperand(1));
 126     return false;
 127   }
 128 };
 129
 130 template<typename LHS, typename RHS>
 131 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
 132                                                         const RHS &R) {
 133   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
 134 }
 135
 136 template<typename LHS, typename RHS>
 137 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
 138                                                         const RHS &R) {
 139   return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
 140 }
 141
 142 template<typename LHS, typename RHS>
 143 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
 144                                                         const RHS &R) {
 145   return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
 146 }
 147
 148 template<typename LHS, typename RHS>
 149 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
 150                                                         const RHS &R) {
 151   return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
 152 }
 153
 154 template<typename LHS, typename RHS>
 155 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
 156                                                         const RHS &R) {
 157   return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
 158 }
 159
 160 template<typename LHS, typename RHS>
 161 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
 162                                                         const RHS &R) {
 163   return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
 164 }
 165
 166 template<typename LHS, typename RHS>
 167 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
 168                                                           const RHS &R) {
 169   return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
 170 }
 171
 172 template<typename LHS, typename RHS>
 173 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
 174                                                           const RHS &R) {
 175   return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
 176 }
 177
 178 template<typename LHS, typename RHS>
 179 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
 180                                                         const RHS &R) {
 181   return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
 182 }
 183
 184 template<typename LHS, typename RHS>
 185 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
 186                                                         const RHS &R) {
 187   return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
 188 }
 189
 190 template<typename LHS, typename RHS>
 191 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
 192                                                       const RHS &R) {
 193   return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
 194 }
 195
 196 template<typename LHS, typename RHS>
 197 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
 198                                                         const RHS &R) {
 199   return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
 200 }
 201
 202 template<typename LHS, typename RHS>
 203 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
 204                                                         const RHS &R) {
 205   return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
 206 }
 207
 208 template<typename LHS, typename RHS>
 209 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
 210                                                           const RHS &R) {
 211   return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
 212 }
 213
 214 template<typename LHS, typename RHS>
 215 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
 216                                                           const RHS &R) {
 217   return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
 218 }
 219
 220 //===----------------------------------------------------------------------===//
 221 // Matchers for either AShr or LShr .. for convenience
 222 //
 223 template<typename LHS_t, typename RHS_t, typename ConcreteTy = BinaryOperator>
 224 struct Shr_match {
 225   LHS_t L;
 226   RHS_t R;
 227
 228   Shr_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 229
 230   template<typename OpTy>
 231   bool match(OpTy *V) {
 232     if (V->getValueID() == Value::InstructionVal + Instruction::LShr ||
 233         V->getValueID() == Value::InstructionVal + Instruction::AShr) {
 234       ConcreteTy *I = cast<ConcreteTy>(V);
 235       return (I->getOpcode() == Instruction::AShr ||
 236               I->getOpcode() == Instruction::LShr) &&
 237              L.match(I->getOperand(0)) &&
 238              R.match(I->getOperand(1));
 239     }
 240     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 241       return (CE->getOpcode() == Instruction::LShr ||
 242               CE->getOpcode() == Instruction::AShr) &&
 243              L.match(CE->getOperand(0)) &&
 244              R.match(CE->getOperand(1));
 245     return false;
 246   }
 247 };
 248
 249 template<typename LHS, typename RHS>
 250 inline Shr_match<LHS, RHS> m_Shr(const LHS &L, const RHS &R) {
 251   return Shr_match<LHS, RHS>(L, R);
 252 }
 253
 254 //===----------------------------------------------------------------------===//
 255 // Matchers for binary classes
 256 //
 257
 258 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
 259 struct BinaryOpClass_match {
 260   OpcType *Opcode;
 261   LHS_t L;
 262   RHS_t R;
 263
 264   BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
 265                       const RHS_t &RHS)
 266     : Opcode(&Op), L(LHS), R(RHS) {}
 267   BinaryOpClass_match(const LHS_t &LHS, const RHS_t &RHS)
 268     : Opcode(0), L(LHS), R(RHS) {}
 269
 270   template<typename OpTy>
 271   bool match(OpTy *V) {
 272     if (Class *I = dyn_cast<Class>(V))
 273       if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
 274         if (Opcode)
 275           *Opcode = I->getOpcode();
 276         return true;
 277       }
 278 #if 0  // Doesn't handle constantexprs yet!
 279     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 280       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
 281              R.match(CE->getOperand(1));
 282 #endif
 283     return false;
 284   }
 285 };
 286
 287 template<typename LHS, typename RHS>
 288 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
 289 m_Shift(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
 290   return BinaryOpClass_match<LHS, RHS,
 291                              BinaryOperator, Instruction::BinaryOps>(Op, L, R);
 292 }
 293
 294 template<typename LHS, typename RHS>
 295 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
 296 m_Shift(const LHS &L, const RHS &R) {
 297   return BinaryOpClass_match<LHS, RHS,
 298                              BinaryOperator, Instruction::BinaryOps>(L, R);
 299 }
 300
 301 //===----------------------------------------------------------------------===//
 302 // Matchers for CmpInst classes
 303 //
 304
 305 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
 306 struct CmpClass_match {
 307   PredicateTy &Predicate;
 308   LHS_t L;
 309   RHS_t R;
 310
 311   CmpClass_match(PredicateTy &Pred, const LHS_t &LHS,
 312                  const RHS_t &RHS)
 313     : Predicate(Pred), L(LHS), R(RHS) {}
 314
 315   template<typename OpTy>
 316   bool match(OpTy *V) {
 317     if (Class *I = dyn_cast<Class>(V))
 318       if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
 319         Predicate = I->getPredicate();
 320         return true;
 321       }
 322     return false;
 323   }
 324 };
 325
 326 template<typename LHS, typename RHS>
 327 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
 328 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
 329   return CmpClass_match<LHS, RHS,
 330                         ICmpInst, ICmpInst::Predicate>(Pred, L, R);
 331 }
 332
 333 template<typename LHS, typename RHS>
 334 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
 335 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
 336   return CmpClass_match<LHS, RHS,
 337                         FCmpInst, FCmpInst::Predicate>(Pred, L, R);
 338 }
 339
 340 //===----------------------------------------------------------------------===//
 341 // Matchers for SelectInst classes
 342 //
 343
 344 template<typename Cond_t, typename LHS_t, typename RHS_t>
 345 struct SelectClass_match {
 346   Cond_t C;
 347   LHS_t L;
 348   RHS_t R;
 349
 350   SelectClass_match(const Cond_t &Cond, const LHS_t &LHS,
 351                     const RHS_t &RHS)
 352     : C(Cond), L(LHS), R(RHS) {}
 353
 354   template<typename OpTy>
 355   bool match(OpTy *V) {
 356     if (SelectInst *I = dyn_cast<SelectInst>(V))
 357       return C.match(I->getOperand(0)) &&
 358              L.match(I->getOperand(1)) &&
 359              R.match(I->getOperand(2));
 360     return false;
 361   }
 362 };
 363
 364 template<typename Cond, typename LHS, typename RHS>
 365 inline SelectClass_match<Cond, RHS, LHS>
 366 m_Select(const Cond &C, const LHS &L, const RHS &R) {
 367   return SelectClass_match<Cond, LHS, RHS>(C, L, R);
 368 }
 369
 370 /// m_SelectCst - This matches a select of two constants, e.g.:
 371 ///    m_SelectCst(m_Value(V), -1, 0)
 372 template<typename Cond>
 373 inline SelectClass_match<Cond, constantint_ty, constantint_ty>
 374 m_SelectCst(const Cond &C, int64_t L, int64_t R) {
 375   return SelectClass_match<Cond, constantint_ty,
 376                            constantint_ty>(C, m_ConstantInt(L),
 377                                            m_ConstantInt(R));
 378 }
 379
 380
 381 //===----------------------------------------------------------------------===//
 382 // Matchers for CastInst classes
 383 //
 384
 385 template<typename Op_t, typename Class>
 386 struct CastClass_match {
 387   Op_t Op;
 388
 389   CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
 390
 391   template<typename OpTy>
 392   bool match(OpTy *V) {
 393     if (Class *I = dyn_cast<Class>(V))
 394       return Op.match(I->getOperand(0));
 395     return false;
 396   }
 397 };
 398
 399 template<typename Class, typename OpTy>
 400 inline CastClass_match<OpTy, Class> m_Cast(const OpTy &Op) {
 401   return CastClass_match<OpTy, Class>(Op);
 402 }
 403
 404
 405 //===----------------------------------------------------------------------===//
 406 // Matchers for unary operators
 407 //
 408
 409 template<typename LHS_t>
 410 struct not_match {
 411   LHS_t L;
 412
 413   not_match(const LHS_t &LHS) : L(LHS) {}
 414
 415   template<typename OpTy>
 416   bool match(OpTy *V) {
 417     if (Instruction *I = dyn_cast<Instruction>(V))
 418       if (I->getOpcode() == Instruction::Xor)
 419         return matchIfNot(I->getOperand(0), I->getOperand(1));
 420     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 421       if (CE->getOpcode() == Instruction::Xor)
 422         return matchIfNot(CE->getOperand(0), CE->getOperand(1));
 423     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
 424       return L.match(ConstantExpr::getNot(CI));
 425     return false;
 426   }
 427 private:
 428   bool matchIfNot(Value *LHS, Value *RHS) {
 429     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
 430       return CI->isAllOnesValue() && L.match(LHS);
 431     if (ConstantInt *CI = dyn_cast<ConstantInt>(LHS))
 432       return CI->isAllOnesValue() && L.match(RHS);
 433     if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
 434       return CV->isAllOnesValue() && L.match(LHS);
 435     if (ConstantVector *CV = dyn_cast<ConstantVector>(LHS))
 436       return CV->isAllOnesValue() && L.match(RHS);
 437     return false;
 438   }
 439 };
 440
 441 template<typename LHS>
 442 inline not_match<LHS> m_Not(const LHS &L) { return L; }
 443
 444
 445 template<typename LHS_t>
 446 struct neg_match {
 447   LHS_t L;
 448
 449   neg_match(const LHS_t &LHS) : L(LHS) {}
 450
 451   template<typename OpTy>
 452   bool match(OpTy *V) {
 453     if (Instruction *I = dyn_cast<Instruction>(V))
 454       if (I->getOpcode() == Instruction::Sub)
 455         return matchIfNeg(I->getOperand(0), I->getOperand(1));
 456     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 457       if (CE->getOpcode() == Instruction::Sub)
 458         return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
 459     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
 460       return L.match(ConstantExpr::getNeg(CI));
 461     return false;
 462   }
 463 private:
 464   bool matchIfNeg(Value *LHS, Value *RHS) {
 465     return LHS == ConstantExpr::getZeroValueForNegationExpr(LHS->getType()) &&
 466            L.match(RHS);
 467   }
 468 };
 469
 470 template<typename LHS>
 471 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
 472
 473
 474 //===----------------------------------------------------------------------===//
 475 // Matchers for control flow
 476 //
 477
 478 template<typename Cond_t>
 479 struct brc_match {
 480   Cond_t Cond;
 481   BasicBlock *&T, *&F;
 482   brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
 483     : Cond(C), T(t), F(f) {
 484   }
 485
 486   template<typename OpTy>
 487   bool match(OpTy *V) {
 488     if (BranchInst *BI = dyn_cast<BranchInst>(V))
 489       if (BI->isConditional()) {
 490         if (Cond.match(BI->getCondition())) {
 491           T = BI->getSuccessor(0);
 492           F = BI->getSuccessor(1);
 493           return true;
 494         }
 495       }
 496     return false;
 497   }
 498 };
 499
 500 template<typename Cond_t>
 501 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){
 502   return brc_match<Cond_t>(C, T, F);
 503 }
 504
 505
 506 }} // end llvm::match
 507
 508
 509 #endif
 510