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