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