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/IR/Constants.h" 33#include "llvm/IR/Instructions.h" 34#include "llvm/IR/IntrinsicInst.h" 35#include "llvm/IR/Operator.h" 36#include "llvm/Support/CallSite.h" 37 38namespace llvm { 39namespace PatternMatch { 40 41template<typename Val, typename Pattern> 42bool match(Val *V, const Pattern &P) { 43 return const_cast<Pattern&>(P).match(V); 44} 45 46 47template<typename SubPattern_t> 48struct OneUse_match { 49 SubPattern_t SubPattern; 50 51 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {} 52 53 template<typename OpTy> 54 bool match(OpTy *V) { 55 return V->hasOneUse() && SubPattern.match(V); 56 } 57}; 58 59template<typename T> 60inline OneUse_match<T> m_OneUse(const T &SubPattern) { return SubPattern; } 61 62 63template<typename Class> 64struct class_match { 65 template<typename ITy> 66 bool match(ITy *V) { return isa<Class>(V); } 67}; 68 69/// m_Value() - Match an arbitrary value and ignore it. 70inline class_match<Value> m_Value() { return class_match<Value>(); } 71/// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it. 72inline class_match<ConstantInt> m_ConstantInt() { 73 return class_match<ConstantInt>(); 74} 75/// m_Undef() - Match an arbitrary undef constant. 76inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); } 77 78inline class_match<Constant> m_Constant() { return class_match<Constant>(); } 79 80/// Matching combinators 81template<typename LTy, typename RTy> 82struct match_combine_or { 83 LTy L; 84 RTy R; 85 86 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) { } 87 88 template<typename ITy> 89 bool match(ITy *V) { 90 if (L.match(V)) 91 return true; 92 if (R.match(V)) 93 return true; 94 return false; 95 } 96}; 97 98template<typename LTy, typename RTy> 99struct match_combine_and { 100 LTy L; 101 RTy R; 102 103 match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) { } 104 105 template<typename ITy> 106 bool match(ITy *V) { 107 if (L.match(V)) 108 if (R.match(V)) 109 return true; 110 return false; 111 } 112}; 113 114/// Combine two pattern matchers matching L || R 115template<typename LTy, typename RTy> 116inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) { 117 return match_combine_or<LTy, RTy>(L, R); 118} 119 120/// Combine two pattern matchers matching L && R 121template<typename LTy, typename RTy> 122inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) { 123 return match_combine_and<LTy, RTy>(L, R); 124} 125 126struct match_zero { 127 template<typename ITy> 128 bool match(ITy *V) { 129 if (const Constant *C = dyn_cast<Constant>(V)) 130 return C->isNullValue(); 131 return false; 132 } 133}; 134 135/// m_Zero() - Match an arbitrary zero/null constant. This includes 136/// zero_initializer for vectors and ConstantPointerNull for pointers. 137inline match_zero m_Zero() { return match_zero(); } 138 139struct match_neg_zero { 140 template<typename ITy> 141 bool match(ITy *V) { 142 if (const Constant *C = dyn_cast<Constant>(V)) 143 return C->isNegativeZeroValue(); 144 return false; 145 } 146}; 147 148/// m_NegZero() - Match an arbitrary zero/null constant. This includes 149/// zero_initializer for vectors and ConstantPointerNull for pointers. For 150/// floating point constants, this will match negative zero but not positive 151/// zero 152inline match_neg_zero m_NegZero() { return match_neg_zero(); } 153 154/// m_AnyZero() - Match an arbitrary zero/null constant. This includes 155/// zero_initializer for vectors and ConstantPointerNull for pointers. For 156/// floating point constants, this will match negative zero and positive zero 157inline match_combine_or<match_zero, match_neg_zero> m_AnyZero() { 158 return m_CombineOr(m_Zero(), m_NegZero()); 159} 160 161struct apint_match { 162 const APInt *&Res; 163 apint_match(const APInt *&R) : Res(R) {} 164 template<typename ITy> 165 bool match(ITy *V) { 166 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 167 Res = &CI->getValue(); 168 return true; 169 } 170 if (V->getType()->isVectorTy()) 171 if (const Constant *C = dyn_cast<Constant>(V)) 172 if (ConstantInt *CI = 173 dyn_cast_or_null<ConstantInt>(C->getSplatValue())) { 174 Res = &CI->getValue(); 175 return true; 176 } 177 return false; 178 } 179}; 180 181/// m_APInt - Match a ConstantInt or splatted ConstantVector, binding the 182/// specified pointer to the contained APInt. 183inline apint_match m_APInt(const APInt *&Res) { return Res; } 184 185 186template<int64_t Val> 187struct constantint_match { 188 template<typename ITy> 189 bool match(ITy *V) { 190 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 191 const APInt &CIV = CI->getValue(); 192 if (Val >= 0) 193 return CIV == static_cast<uint64_t>(Val); 194 // If Val is negative, and CI is shorter than it, truncate to the right 195 // number of bits. If it is larger, then we have to sign extend. Just 196 // compare their negated values. 197 return -CIV == -Val; 198 } 199 return false; 200 } 201}; 202 203/// m_ConstantInt<int64_t> - Match a ConstantInt with a specific value. 204template<int64_t Val> 205inline constantint_match<Val> m_ConstantInt() { 206 return constantint_match<Val>(); 207} 208 209/// cst_pred_ty - This helper class is used to match scalar and vector constants 210/// that satisfy a specified predicate. 211template<typename Predicate> 212struct cst_pred_ty : public Predicate { 213 template<typename ITy> 214 bool match(ITy *V) { 215 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) 216 return this->isValue(CI->getValue()); 217 if (V->getType()->isVectorTy()) 218 if (const Constant *C = dyn_cast<Constant>(V)) 219 if (const ConstantInt *CI = 220 dyn_cast_or_null<ConstantInt>(C->getSplatValue())) 221 return this->isValue(CI->getValue()); 222 return false; 223 } 224}; 225 226/// api_pred_ty - This helper class is used to match scalar and vector constants 227/// that satisfy a specified predicate, and bind them to an APInt. 228template<typename Predicate> 229struct api_pred_ty : public Predicate { 230 const APInt *&Res; 231 api_pred_ty(const APInt *&R) : Res(R) {} 232 template<typename ITy> 233 bool match(ITy *V) { 234 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) 235 if (this->isValue(CI->getValue())) { 236 Res = &CI->getValue(); 237 return true; 238 } 239 if (V->getType()->isVectorTy()) 240 if (const Constant *C = dyn_cast<Constant>(V)) 241 if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) 242 if (this->isValue(CI->getValue())) { 243 Res = &CI->getValue(); 244 return true; 245 } 246 247 return false; 248 } 249}; 250 251 252struct is_one { 253 bool isValue(const APInt &C) { return C == 1; } 254}; 255 256/// m_One() - Match an integer 1 or a vector with all elements equal to 1. 257inline cst_pred_ty<is_one> m_One() { return cst_pred_ty<is_one>(); } 258inline api_pred_ty<is_one> m_One(const APInt *&V) { return V; } 259 260struct is_all_ones { 261 bool isValue(const APInt &C) { return C.isAllOnesValue(); } 262}; 263 264/// m_AllOnes() - Match an integer or vector with all bits set to true. 265inline cst_pred_ty<is_all_ones> m_AllOnes() {return cst_pred_ty<is_all_ones>();} 266inline api_pred_ty<is_all_ones> m_AllOnes(const APInt *&V) { return V; } 267 268struct is_sign_bit { 269 bool isValue(const APInt &C) { return C.isSignBit(); } 270}; 271 272/// m_SignBit() - Match an integer or vector with only the sign bit(s) set. 273inline cst_pred_ty<is_sign_bit> m_SignBit() {return cst_pred_ty<is_sign_bit>();} 274inline api_pred_ty<is_sign_bit> m_SignBit(const APInt *&V) { return V; } 275 276struct is_power2 { 277 bool isValue(const APInt &C) { return C.isPowerOf2(); } 278}; 279 280/// m_Power2() - Match an integer or vector power of 2. 281inline cst_pred_ty<is_power2> m_Power2() { return cst_pred_ty<is_power2>(); } 282inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { return V; } 283 284template<typename Class> 285struct bind_ty { 286 Class *&VR; 287 bind_ty(Class *&V) : VR(V) {} 288 289 template<typename ITy> 290 bool match(ITy *V) { 291 if (Class *CV = dyn_cast<Class>(V)) { 292 VR = CV; 293 return true; 294 } 295 return false; 296 } 297}; 298 299/// m_Value - Match a value, capturing it if we match. 300inline bind_ty<Value> m_Value(Value *&V) { return V; } 301 302/// m_ConstantInt - Match a ConstantInt, capturing the value if we match. 303inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; } 304 305/// m_Constant - Match a Constant, capturing the value if we match. 306inline bind_ty<Constant> m_Constant(Constant *&C) { return C; } 307 308/// m_ConstantFP - Match a ConstantFP, capturing the value if we match. 309inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; } 310 311/// specificval_ty - Match a specified Value*. 312struct specificval_ty { 313 const Value *Val; 314 specificval_ty(const Value *V) : Val(V) {} 315 316 template<typename ITy> 317 bool match(ITy *V) { 318 return V == Val; 319 } 320}; 321 322/// m_Specific - Match if we have a specific specified value. 323inline specificval_ty m_Specific(const Value *V) { return V; } 324 325/// Match a specified floating point value or vector of all elements of that 326/// value. 327struct specific_fpval { 328 double Val; 329 specific_fpval(double V) : Val(V) {} 330 331 template<typename ITy> 332 bool match(ITy *V) { 333 if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) 334 return CFP->isExactlyValue(Val); 335 if (V->getType()->isVectorTy()) 336 if (const Constant *C = dyn_cast<Constant>(V)) 337 if (ConstantFP *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue())) 338 return CFP->isExactlyValue(Val); 339 return false; 340 } 341}; 342 343/// Match a specific floating point value or vector with all elements equal to 344/// the value. 345inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); } 346 347/// Match a float 1.0 or vector with all elements equal to 1.0. 348inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); } 349 350struct bind_const_intval_ty { 351 uint64_t &VR; 352 bind_const_intval_ty(uint64_t &V) : VR(V) {} 353 354 template<typename ITy> 355 bool match(ITy *V) { 356 if (ConstantInt *CV = dyn_cast<ConstantInt>(V)) 357 if (CV->getBitWidth() <= 64) { 358 VR = CV->getZExtValue(); 359 return true; 360 } 361 return false; 362 } 363}; 364 365/// m_ConstantInt - Match a ConstantInt and bind to its value. This does not 366/// match ConstantInts wider than 64-bits. 367inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; } 368 369//===----------------------------------------------------------------------===// 370// Matchers for specific binary operators. 371// 372 373template<typename LHS_t, typename RHS_t, unsigned Opcode> 374struct BinaryOp_match { 375 LHS_t L; 376 RHS_t R; 377 378 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 379 380 template<typename OpTy> 381 bool match(OpTy *V) { 382 if (V->getValueID() == Value::InstructionVal + Opcode) { 383 BinaryOperator *I = cast<BinaryOperator>(V); 384 return L.match(I->getOperand(0)) && R.match(I->getOperand(1)); 385 } 386 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 387 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) && 388 R.match(CE->getOperand(1)); 389 return false; 390 } 391}; 392 393template<typename LHS, typename RHS> 394inline BinaryOp_match<LHS, RHS, Instruction::Add> 395m_Add(const LHS &L, const RHS &R) { 396 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R); 397} 398 399template<typename LHS, typename RHS> 400inline BinaryOp_match<LHS, RHS, Instruction::FAdd> 401m_FAdd(const LHS &L, const RHS &R) { 402 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R); 403} 404 405template<typename LHS, typename RHS> 406inline BinaryOp_match<LHS, RHS, Instruction::Sub> 407m_Sub(const LHS &L, const RHS &R) { 408 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R); 409} 410 411template<typename LHS, typename RHS> 412inline BinaryOp_match<LHS, RHS, Instruction::FSub> 413m_FSub(const LHS &L, const RHS &R) { 414 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R); 415} 416 417template<typename LHS, typename RHS> 418inline BinaryOp_match<LHS, RHS, Instruction::Mul> 419m_Mul(const LHS &L, const RHS &R) { 420 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R); 421} 422 423template<typename LHS, typename RHS> 424inline BinaryOp_match<LHS, RHS, Instruction::FMul> 425m_FMul(const LHS &L, const RHS &R) { 426 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R); 427} 428 429template<typename LHS, typename RHS> 430inline BinaryOp_match<LHS, RHS, Instruction::UDiv> 431m_UDiv(const LHS &L, const RHS &R) { 432 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R); 433} 434 435template<typename LHS, typename RHS> 436inline BinaryOp_match<LHS, RHS, Instruction::SDiv> 437m_SDiv(const LHS &L, const RHS &R) { 438 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R); 439} 440 441template<typename LHS, typename RHS> 442inline BinaryOp_match<LHS, RHS, Instruction::FDiv> 443m_FDiv(const LHS &L, const RHS &R) { 444 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R); 445} 446 447template<typename LHS, typename RHS> 448inline BinaryOp_match<LHS, RHS, Instruction::URem> 449m_URem(const LHS &L, const RHS &R) { 450 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R); 451} 452 453template<typename LHS, typename RHS> 454inline BinaryOp_match<LHS, RHS, Instruction::SRem> 455m_SRem(const LHS &L, const RHS &R) { 456 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R); 457} 458 459template<typename LHS, typename RHS> 460inline BinaryOp_match<LHS, RHS, Instruction::FRem> 461m_FRem(const LHS &L, const RHS &R) { 462 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R); 463} 464 465template<typename LHS, typename RHS> 466inline BinaryOp_match<LHS, RHS, Instruction::And> 467m_And(const LHS &L, const RHS &R) { 468 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R); 469} 470 471template<typename LHS, typename RHS> 472inline BinaryOp_match<LHS, RHS, Instruction::Or> 473m_Or(const LHS &L, const RHS &R) { 474 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R); 475} 476 477template<typename LHS, typename RHS> 478inline BinaryOp_match<LHS, RHS, Instruction::Xor> 479m_Xor(const LHS &L, const RHS &R) { 480 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R); 481} 482 483template<typename LHS, typename RHS> 484inline BinaryOp_match<LHS, RHS, Instruction::Shl> 485m_Shl(const LHS &L, const RHS &R) { 486 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R); 487} 488 489template<typename LHS, typename RHS> 490inline BinaryOp_match<LHS, RHS, Instruction::LShr> 491m_LShr(const LHS &L, const RHS &R) { 492 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R); 493} 494 495template<typename LHS, typename RHS> 496inline BinaryOp_match<LHS, RHS, Instruction::AShr> 497m_AShr(const LHS &L, const RHS &R) { 498 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R); 499} 500 501//===----------------------------------------------------------------------===// 502// Class that matches two different binary ops. 503// 504template<typename LHS_t, typename RHS_t, unsigned Opc1, unsigned Opc2> 505struct BinOp2_match { 506 LHS_t L; 507 RHS_t R; 508 509 BinOp2_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 510 511 template<typename OpTy> 512 bool match(OpTy *V) { 513 if (V->getValueID() == Value::InstructionVal + Opc1 || 514 V->getValueID() == Value::InstructionVal + Opc2) { 515 BinaryOperator *I = cast<BinaryOperator>(V); 516 return L.match(I->getOperand(0)) && R.match(I->getOperand(1)); 517 } 518 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 519 return (CE->getOpcode() == Opc1 || CE->getOpcode() == Opc2) && 520 L.match(CE->getOperand(0)) && R.match(CE->getOperand(1)); 521 return false; 522 } 523}; 524 525/// m_Shr - Matches LShr or AShr. 526template<typename LHS, typename RHS> 527inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr> 528m_Shr(const LHS &L, const RHS &R) { 529 return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr>(L, R); 530} 531 532/// m_LogicalShift - Matches LShr or Shl. 533template<typename LHS, typename RHS> 534inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl> 535m_LogicalShift(const LHS &L, const RHS &R) { 536 return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl>(L, R); 537} 538 539/// m_IDiv - Matches UDiv and SDiv. 540template<typename LHS, typename RHS> 541inline BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv> 542m_IDiv(const LHS &L, const RHS &R) { 543 return BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv>(L, R); 544} 545 546//===----------------------------------------------------------------------===// 547// Class that matches exact binary ops. 548// 549template<typename SubPattern_t> 550struct Exact_match { 551 SubPattern_t SubPattern; 552 553 Exact_match(const SubPattern_t &SP) : SubPattern(SP) {} 554 555 template<typename OpTy> 556 bool match(OpTy *V) { 557 if (PossiblyExactOperator *PEO = dyn_cast<PossiblyExactOperator>(V)) 558 return PEO->isExact() && SubPattern.match(V); 559 return false; 560 } 561}; 562 563template<typename T> 564inline Exact_match<T> m_Exact(const T &SubPattern) { return SubPattern; } 565 566//===----------------------------------------------------------------------===// 567// Matchers for CmpInst classes 568// 569 570template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy> 571struct CmpClass_match { 572 PredicateTy &Predicate; 573 LHS_t L; 574 RHS_t R; 575 576 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS) 577 : Predicate(Pred), L(LHS), R(RHS) {} 578 579 template<typename OpTy> 580 bool match(OpTy *V) { 581 if (Class *I = dyn_cast<Class>(V)) 582 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) { 583 Predicate = I->getPredicate(); 584 return true; 585 } 586 return false; 587 } 588}; 589 590template<typename LHS, typename RHS> 591inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate> 592m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 593 return CmpClass_match<LHS, RHS, 594 ICmpInst, ICmpInst::Predicate>(Pred, L, R); 595} 596 597template<typename LHS, typename RHS> 598inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate> 599m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 600 return CmpClass_match<LHS, RHS, 601 FCmpInst, FCmpInst::Predicate>(Pred, L, R); 602} 603 604//===----------------------------------------------------------------------===// 605// Matchers for SelectInst classes 606// 607 608template<typename Cond_t, typename LHS_t, typename RHS_t> 609struct SelectClass_match { 610 Cond_t C; 611 LHS_t L; 612 RHS_t R; 613 614 SelectClass_match(const Cond_t &Cond, const LHS_t &LHS, 615 const RHS_t &RHS) 616 : C(Cond), L(LHS), R(RHS) {} 617 618 template<typename OpTy> 619 bool match(OpTy *V) { 620 if (SelectInst *I = dyn_cast<SelectInst>(V)) 621 return C.match(I->getOperand(0)) && 622 L.match(I->getOperand(1)) && 623 R.match(I->getOperand(2)); 624 return false; 625 } 626}; 627 628template<typename Cond, typename LHS, typename RHS> 629inline SelectClass_match<Cond, LHS, RHS> 630m_Select(const Cond &C, const LHS &L, const RHS &R) { 631 return SelectClass_match<Cond, LHS, RHS>(C, L, R); 632} 633 634/// m_SelectCst - This matches a select of two constants, e.g.: 635/// m_SelectCst<-1, 0>(m_Value(V)) 636template<int64_t L, int64_t R, typename Cond> 637inline SelectClass_match<Cond, constantint_match<L>, constantint_match<R> > 638m_SelectCst(const Cond &C) { 639 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>()); 640} 641 642 643//===----------------------------------------------------------------------===// 644// Matchers for CastInst classes 645// 646 647template<typename Op_t, unsigned Opcode> 648struct CastClass_match { 649 Op_t Op; 650 651 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {} 652 653 template<typename OpTy> 654 bool match(OpTy *V) { 655 if (Operator *O = dyn_cast<Operator>(V)) 656 return O->getOpcode() == Opcode && Op.match(O->getOperand(0)); 657 return false; 658 } 659}; 660 661/// m_BitCast 662template<typename OpTy> 663inline CastClass_match<OpTy, Instruction::BitCast> 664m_BitCast(const OpTy &Op) { 665 return CastClass_match<OpTy, Instruction::BitCast>(Op); 666} 667 668/// m_PtrToInt 669template<typename OpTy> 670inline CastClass_match<OpTy, Instruction::PtrToInt> 671m_PtrToInt(const OpTy &Op) { 672 return CastClass_match<OpTy, Instruction::PtrToInt>(Op); 673} 674 675/// m_Trunc 676template<typename OpTy> 677inline CastClass_match<OpTy, Instruction::Trunc> 678m_Trunc(const OpTy &Op) { 679 return CastClass_match<OpTy, Instruction::Trunc>(Op); 680} 681 682/// m_SExt 683template<typename OpTy> 684inline CastClass_match<OpTy, Instruction::SExt> 685m_SExt(const OpTy &Op) { 686 return CastClass_match<OpTy, Instruction::SExt>(Op); 687} 688 689/// m_ZExt 690template<typename OpTy> 691inline CastClass_match<OpTy, Instruction::ZExt> 692m_ZExt(const OpTy &Op) { 693 return CastClass_match<OpTy, Instruction::ZExt>(Op); 694} 695 696 697//===----------------------------------------------------------------------===// 698// Matchers for unary operators 699// 700 701template<typename LHS_t> 702struct not_match { 703 LHS_t L; 704 705 not_match(const LHS_t &LHS) : L(LHS) {} 706 707 template<typename OpTy> 708 bool match(OpTy *V) { 709 if (Operator *O = dyn_cast<Operator>(V)) 710 if (O->getOpcode() == Instruction::Xor) 711 return matchIfNot(O->getOperand(0), O->getOperand(1)); 712 return false; 713 } 714private: 715 bool matchIfNot(Value *LHS, Value *RHS) { 716 return (isa<ConstantInt>(RHS) || isa<ConstantDataVector>(RHS) || 717 // FIXME: Remove CV. 718 isa<ConstantVector>(RHS)) && 719 cast<Constant>(RHS)->isAllOnesValue() && 720 L.match(LHS); 721 } 722}; 723 724template<typename LHS> 725inline not_match<LHS> m_Not(const LHS &L) { return L; } 726 727 728template<typename LHS_t> 729struct neg_match { 730 LHS_t L; 731 732 neg_match(const LHS_t &LHS) : L(LHS) {} 733 734 template<typename OpTy> 735 bool match(OpTy *V) { 736 if (Operator *O = dyn_cast<Operator>(V)) 737 if (O->getOpcode() == Instruction::Sub) 738 return matchIfNeg(O->getOperand(0), O->getOperand(1)); 739 return false; 740 } 741private: 742 bool matchIfNeg(Value *LHS, Value *RHS) { 743 return ((isa<ConstantInt>(LHS) && cast<ConstantInt>(LHS)->isZero()) || 744 isa<ConstantAggregateZero>(LHS)) && 745 L.match(RHS); 746 } 747}; 748 749/// m_Neg - Match an integer negate. 750template<typename LHS> 751inline neg_match<LHS> m_Neg(const LHS &L) { return L; } 752 753 754template<typename LHS_t> 755struct fneg_match { 756 LHS_t L; 757 758 fneg_match(const LHS_t &LHS) : L(LHS) {} 759 760 template<typename OpTy> 761 bool match(OpTy *V) { 762 if (Operator *O = dyn_cast<Operator>(V)) 763 if (O->getOpcode() == Instruction::FSub) 764 return matchIfFNeg(O->getOperand(0), O->getOperand(1)); 765 return false; 766 } 767private: 768 bool matchIfFNeg(Value *LHS, Value *RHS) { 769 if (ConstantFP *C = dyn_cast<ConstantFP>(LHS)) 770 return C->isNegativeZeroValue() && L.match(RHS); 771 return false; 772 } 773}; 774 775/// m_FNeg - Match a floating point negate. 776template<typename LHS> 777inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; } 778 779 780//===----------------------------------------------------------------------===// 781// Matchers for control flow. 782// 783 784struct br_match { 785 BasicBlock *&Succ; 786 br_match(BasicBlock *&Succ) 787 : Succ(Succ) { 788 } 789 790 template<typename OpTy> 791 bool match(OpTy *V) { 792 if (BranchInst *BI = dyn_cast<BranchInst>(V)) 793 if (BI->isUnconditional()) { 794 Succ = BI->getSuccessor(0); 795 return true; 796 } 797 return false; 798 } 799}; 800 801inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); } 802 803template<typename Cond_t> 804struct brc_match { 805 Cond_t Cond; 806 BasicBlock *&T, *&F; 807 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f) 808 : Cond(C), T(t), F(f) { 809 } 810 811 template<typename OpTy> 812 bool match(OpTy *V) { 813 if (BranchInst *BI = dyn_cast<BranchInst>(V)) 814 if (BI->isConditional() && Cond.match(BI->getCondition())) { 815 T = BI->getSuccessor(0); 816 F = BI->getSuccessor(1); 817 return true; 818 } 819 return false; 820 } 821}; 822 823template<typename Cond_t> 824inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) { 825 return brc_match<Cond_t>(C, T, F); 826} 827 828 829//===----------------------------------------------------------------------===// 830// Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y). 831// 832 833template<typename LHS_t, typename RHS_t, typename Pred_t> 834struct MaxMin_match { 835 LHS_t L; 836 RHS_t R; 837 838 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) 839 : L(LHS), R(RHS) {} 840 841 template<typename OpTy> 842 bool match(OpTy *V) { 843 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x". 844 SelectInst *SI = dyn_cast<SelectInst>(V); 845 if (!SI) 846 return false; 847 ICmpInst *Cmp = dyn_cast<ICmpInst>(SI->getCondition()); 848 if (!Cmp) 849 return false; 850 // At this point we have a select conditioned on a comparison. Check that 851 // it is the values returned by the select that are being compared. 852 Value *TrueVal = SI->getTrueValue(); 853 Value *FalseVal = SI->getFalseValue(); 854 Value *LHS = Cmp->getOperand(0); 855 Value *RHS = Cmp->getOperand(1); 856 if ((TrueVal != LHS || FalseVal != RHS) && 857 (TrueVal != RHS || FalseVal != LHS)) 858 return false; 859 ICmpInst::Predicate Pred = LHS == TrueVal ? 860 Cmp->getPredicate() : Cmp->getSwappedPredicate(); 861 // Does "(x pred y) ? x : y" represent the desired max/min operation? 862 if (!Pred_t::match(Pred)) 863 return false; 864 // It does! Bind the operands. 865 return L.match(LHS) && R.match(RHS); 866 } 867}; 868 869/// smax_pred_ty - Helper class for identifying signed max predicates. 870struct smax_pred_ty { 871 static bool match(ICmpInst::Predicate Pred) { 872 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE; 873 } 874}; 875 876/// smin_pred_ty - Helper class for identifying signed min predicates. 877struct smin_pred_ty { 878 static bool match(ICmpInst::Predicate Pred) { 879 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE; 880 } 881}; 882 883/// umax_pred_ty - Helper class for identifying unsigned max predicates. 884struct umax_pred_ty { 885 static bool match(ICmpInst::Predicate Pred) { 886 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE; 887 } 888}; 889 890/// umin_pred_ty - Helper class for identifying unsigned min predicates. 891struct umin_pred_ty { 892 static bool match(ICmpInst::Predicate Pred) { 893 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE; 894 } 895}; 896 897template<typename LHS, typename RHS> 898inline MaxMin_match<LHS, RHS, smax_pred_ty> 899m_SMax(const LHS &L, const RHS &R) { 900 return MaxMin_match<LHS, RHS, smax_pred_ty>(L, R); 901} 902 903template<typename LHS, typename RHS> 904inline MaxMin_match<LHS, RHS, smin_pred_ty> 905m_SMin(const LHS &L, const RHS &R) { 906 return MaxMin_match<LHS, RHS, smin_pred_ty>(L, R); 907} 908 909template<typename LHS, typename RHS> 910inline MaxMin_match<LHS, RHS, umax_pred_ty> 911m_UMax(const LHS &L, const RHS &R) { 912 return MaxMin_match<LHS, RHS, umax_pred_ty>(L, R); 913} 914 915template<typename LHS, typename RHS> 916inline MaxMin_match<LHS, RHS, umin_pred_ty> 917m_UMin(const LHS &L, const RHS &R) { 918 return MaxMin_match<LHS, RHS, umin_pred_ty>(L, R); 919} 920 921template<typename Opnd_t> 922struct Argument_match { 923 unsigned OpI; 924 Opnd_t Val; 925 Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) { } 926 927 template<typename OpTy> 928 bool match(OpTy *V) { 929 CallSite CS(V); 930 return CS.isCall() && Val.match(CS.getArgument(OpI)); 931 } 932}; 933 934/// Match an argument 935template<unsigned OpI, typename Opnd_t> 936inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) { 937 return Argument_match<Opnd_t>(OpI, Op); 938} 939 940/// Intrinsic matchers. 941struct IntrinsicID_match { 942 unsigned ID; 943 IntrinsicID_match(unsigned IntrID) : ID(IntrID) { } 944 945 template<typename OpTy> 946 bool match(OpTy *V) { 947 IntrinsicInst *II = dyn_cast<IntrinsicInst>(V); 948 return II && II->getIntrinsicID() == ID; 949 } 950}; 951 952/// Intrinsic matches are combinations of ID matchers, and argument 953/// matchers. Higher arity matcher are defined recursively in terms of and-ing 954/// them with lower arity matchers. Here's some convenient typedefs for up to 955/// several arguments, and more can be added as needed 956template <typename T0 = void, typename T1 = void, typename T2 = void, 957 typename T3 = void, typename T4 = void, typename T5 = void, 958 typename T6 = void, typename T7 = void, typename T8 = void, 959 typename T9 = void, typename T10 = void> struct m_Intrinsic_Ty; 960template <typename T0> 961struct m_Intrinsic_Ty<T0> { 962 typedef match_combine_and<IntrinsicID_match, Argument_match<T0> > Ty; 963}; 964template <typename T0, typename T1> 965struct m_Intrinsic_Ty<T0, T1> { 966 typedef match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, 967 Argument_match<T1> > Ty; 968}; 969template <typename T0, typename T1, typename T2> 970struct m_Intrinsic_Ty<T0, T1, T2> { 971 typedef match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty, 972 Argument_match<T2> > Ty; 973}; 974template <typename T0, typename T1, typename T2, typename T3> 975struct m_Intrinsic_Ty<T0, T1, T2, T3> { 976 typedef match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty, 977 Argument_match<T3> > Ty; 978}; 979 980/// Match intrinsic calls like this: 981/// m_Intrinsic<Intrinsic::fabs>(m_Value(X)) 982template <unsigned IntrID> 983inline IntrinsicID_match 984m_Intrinsic() { return IntrinsicID_match(IntrID); } 985 986template<unsigned IntrID, typename T0> 987inline typename m_Intrinsic_Ty<T0>::Ty 988m_Intrinsic(const T0 &Op0) { 989 return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0)); 990} 991 992template<unsigned IntrID, typename T0, typename T1> 993inline typename m_Intrinsic_Ty<T0, T1>::Ty 994m_Intrinsic(const T0 &Op0, const T1 &Op1) { 995 return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1)); 996} 997 998template<unsigned IntrID, typename T0, typename T1, typename T2> 999inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty 1000m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) { 1001 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2)); 1002} 1003 1004template<unsigned IntrID, typename T0, typename T1, typename T2, typename T3> 1005inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty 1006m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) { 1007 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3)); 1008} 1009 1010// Helper intrinsic matching specializations 1011template<typename Opnd0> 1012inline typename m_Intrinsic_Ty<Opnd0>::Ty 1013m_BSwap(const Opnd0 &Op0) { 1014 return m_Intrinsic<Intrinsic::bswap>(Op0); 1015} 1016 1017} // end namespace PatternMatch 1018} // end namespace llvm 1019 1020#endif 1021