PatternMatch.h revision 263508
184442Sbde//===-- llvm/Support/PatternMatch.h - Match on the LLVM IR ------*- C++ -*-===// 287659Sphantom// 383105Sphantom// The LLVM Compiler Infrastructure 483105Sphantom// 583105Sphantom// This file is distributed under the University of Illinois Open Source 683105Sphantom// License. See LICENSE.TXT for details. 783105Sphantom// 883105Sphantom//===----------------------------------------------------------------------===// 983105Sphantom// 1083105Sphantom// This file provides a simple and efficient mechanism for performing general 1183105Sphantom// tree-based pattern matches on the LLVM IR. The power of these routines is 1283105Sphantom// that it allows you to write concise patterns that are expressive and easy to 1383105Sphantom// understand. The other major advantage of this is that it allows you to 1483105Sphantom// trivially capture/bind elements in the pattern to variables. For example, 1583105Sphantom// you can do something like this: 1683105Sphantom// 1783105Sphantom// Value *Exp = ... 1883105Sphantom// Value *X, *Y; ConstantInt *C1, *C2; // (X & C1) | (Y & C2) 1983105Sphantom// if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)), 2083105Sphantom// m_And(m_Value(Y), m_ConstantInt(C2))))) { 2183105Sphantom// ... Pattern is matched and variables are bound ... 2283105Sphantom// } 2383105Sphantom// 2483105Sphantom// This is primarily useful to things like the instruction combiner, but can 2583105Sphantom// also be useful for static analysis tools or code generators. 2683105Sphantom// 2783105Sphantom//===----------------------------------------------------------------------===// 2883105Sphantom 2987744Sphantom#ifndef LLVM_SUPPORT_PATTERNMATCH_H 3087744Sphantom#define LLVM_SUPPORT_PATTERNMATCH_H 3183105Sphantom 3283105Sphantom#include "llvm/IR/Constants.h" 33102227Smike#include "llvm/IR/Instructions.h" 3483105Sphantom#include "llvm/IR/IntrinsicInst.h" 35102227Smike#include "llvm/IR/Operator.h" 36102227Smike#include "llvm/Support/CallSite.h" 37102227Smike 3884441Sbdenamespace llvm { 3984441Sbdenamespace PatternMatch { 40103667Smike 41102227Smiketemplate<typename Val, typename Pattern> 42103667Smikebool match(Val *V, const Pattern &P) { 4384441Sbde return const_cast<Pattern&>(P).match(V); 4484441Sbde} 4583105Sphantom 46103667Smike 4783105Sphantomtemplate<typename SubPattern_t> 4883105Sphantomstruct OneUse_match { 4987744Sphantom 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/// m_UIToFP 697template<typename OpTy> 698inline CastClass_match<OpTy, Instruction::UIToFP> 699m_UIToFP(const OpTy &Op) { 700 return CastClass_match<OpTy, Instruction::UIToFP>(Op); 701} 702 703/// m_SIToFP 704template<typename OpTy> 705inline CastClass_match<OpTy, Instruction::SIToFP> 706m_SIToFP(const OpTy &Op) { 707 return CastClass_match<OpTy, Instruction::SIToFP>(Op); 708} 709 710//===----------------------------------------------------------------------===// 711// Matchers for unary operators 712// 713 714template<typename LHS_t> 715struct not_match { 716 LHS_t L; 717 718 not_match(const LHS_t &LHS) : L(LHS) {} 719 720 template<typename OpTy> 721 bool match(OpTy *V) { 722 if (Operator *O = dyn_cast<Operator>(V)) 723 if (O->getOpcode() == Instruction::Xor) 724 return matchIfNot(O->getOperand(0), O->getOperand(1)); 725 return false; 726 } 727private: 728 bool matchIfNot(Value *LHS, Value *RHS) { 729 return (isa<ConstantInt>(RHS) || isa<ConstantDataVector>(RHS) || 730 // FIXME: Remove CV. 731 isa<ConstantVector>(RHS)) && 732 cast<Constant>(RHS)->isAllOnesValue() && 733 L.match(LHS); 734 } 735}; 736 737template<typename LHS> 738inline not_match<LHS> m_Not(const LHS &L) { return L; } 739 740 741template<typename LHS_t> 742struct neg_match { 743 LHS_t L; 744 745 neg_match(const LHS_t &LHS) : L(LHS) {} 746 747 template<typename OpTy> 748 bool match(OpTy *V) { 749 if (Operator *O = dyn_cast<Operator>(V)) 750 if (O->getOpcode() == Instruction::Sub) 751 return matchIfNeg(O->getOperand(0), O->getOperand(1)); 752 return false; 753 } 754private: 755 bool matchIfNeg(Value *LHS, Value *RHS) { 756 return ((isa<ConstantInt>(LHS) && cast<ConstantInt>(LHS)->isZero()) || 757 isa<ConstantAggregateZero>(LHS)) && 758 L.match(RHS); 759 } 760}; 761 762/// m_Neg - Match an integer negate. 763template<typename LHS> 764inline neg_match<LHS> m_Neg(const LHS &L) { return L; } 765 766 767template<typename LHS_t> 768struct fneg_match { 769 LHS_t L; 770 771 fneg_match(const LHS_t &LHS) : L(LHS) {} 772 773 template<typename OpTy> 774 bool match(OpTy *V) { 775 if (Operator *O = dyn_cast<Operator>(V)) 776 if (O->getOpcode() == Instruction::FSub) 777 return matchIfFNeg(O->getOperand(0), O->getOperand(1)); 778 return false; 779 } 780private: 781 bool matchIfFNeg(Value *LHS, Value *RHS) { 782 if (ConstantFP *C = dyn_cast<ConstantFP>(LHS)) 783 return C->isNegativeZeroValue() && L.match(RHS); 784 return false; 785 } 786}; 787 788/// m_FNeg - Match a floating point negate. 789template<typename LHS> 790inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; } 791 792 793//===----------------------------------------------------------------------===// 794// Matchers for control flow. 795// 796 797struct br_match { 798 BasicBlock *&Succ; 799 br_match(BasicBlock *&Succ) 800 : Succ(Succ) { 801 } 802 803 template<typename OpTy> 804 bool match(OpTy *V) { 805 if (BranchInst *BI = dyn_cast<BranchInst>(V)) 806 if (BI->isUnconditional()) { 807 Succ = BI->getSuccessor(0); 808 return true; 809 } 810 return false; 811 } 812}; 813 814inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); } 815 816template<typename Cond_t> 817struct brc_match { 818 Cond_t Cond; 819 BasicBlock *&T, *&F; 820 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f) 821 : Cond(C), T(t), F(f) { 822 } 823 824 template<typename OpTy> 825 bool match(OpTy *V) { 826 if (BranchInst *BI = dyn_cast<BranchInst>(V)) 827 if (BI->isConditional() && Cond.match(BI->getCondition())) { 828 T = BI->getSuccessor(0); 829 F = BI->getSuccessor(1); 830 return true; 831 } 832 return false; 833 } 834}; 835 836template<typename Cond_t> 837inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) { 838 return brc_match<Cond_t>(C, T, F); 839} 840 841 842//===----------------------------------------------------------------------===// 843// Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y). 844// 845 846template<typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t> 847struct MaxMin_match { 848 LHS_t L; 849 RHS_t R; 850 851 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) 852 : L(LHS), R(RHS) {} 853 854 template<typename OpTy> 855 bool match(OpTy *V) { 856 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x". 857 SelectInst *SI = dyn_cast<SelectInst>(V); 858 if (!SI) 859 return false; 860 CmpInst_t *Cmp = dyn_cast<CmpInst_t>(SI->getCondition()); 861 if (!Cmp) 862 return false; 863 // At this point we have a select conditioned on a comparison. Check that 864 // it is the values returned by the select that are being compared. 865 Value *TrueVal = SI->getTrueValue(); 866 Value *FalseVal = SI->getFalseValue(); 867 Value *LHS = Cmp->getOperand(0); 868 Value *RHS = Cmp->getOperand(1); 869 if ((TrueVal != LHS || FalseVal != RHS) && 870 (TrueVal != RHS || FalseVal != LHS)) 871 return false; 872 typename CmpInst_t::Predicate Pred = LHS == TrueVal ? 873 Cmp->getPredicate() : Cmp->getSwappedPredicate(); 874 // Does "(x pred y) ? x : y" represent the desired max/min operation? 875 if (!Pred_t::match(Pred)) 876 return false; 877 // It does! Bind the operands. 878 return L.match(LHS) && R.match(RHS); 879 } 880}; 881 882/// smax_pred_ty - Helper class for identifying signed max predicates. 883struct smax_pred_ty { 884 static bool match(ICmpInst::Predicate Pred) { 885 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE; 886 } 887}; 888 889/// smin_pred_ty - Helper class for identifying signed min predicates. 890struct smin_pred_ty { 891 static bool match(ICmpInst::Predicate Pred) { 892 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE; 893 } 894}; 895 896/// umax_pred_ty - Helper class for identifying unsigned max predicates. 897struct umax_pred_ty { 898 static bool match(ICmpInst::Predicate Pred) { 899 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE; 900 } 901}; 902 903/// umin_pred_ty - Helper class for identifying unsigned min predicates. 904struct umin_pred_ty { 905 static bool match(ICmpInst::Predicate Pred) { 906 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE; 907 } 908}; 909 910/// ofmax_pred_ty - Helper class for identifying ordered max predicates. 911struct ofmax_pred_ty { 912 static bool match(FCmpInst::Predicate Pred) { 913 return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE; 914 } 915}; 916 917/// ofmin_pred_ty - Helper class for identifying ordered min predicates. 918struct ofmin_pred_ty { 919 static bool match(FCmpInst::Predicate Pred) { 920 return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE; 921 } 922}; 923 924/// ufmax_pred_ty - Helper class for identifying unordered max predicates. 925struct ufmax_pred_ty { 926 static bool match(FCmpInst::Predicate Pred) { 927 return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE; 928 } 929}; 930 931/// ufmin_pred_ty - Helper class for identifying unordered min predicates. 932struct ufmin_pred_ty { 933 static bool match(FCmpInst::Predicate Pred) { 934 return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE; 935 } 936}; 937 938template<typename LHS, typename RHS> 939inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> 940m_SMax(const LHS &L, const RHS &R) { 941 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R); 942} 943 944template<typename LHS, typename RHS> 945inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> 946m_SMin(const LHS &L, const RHS &R) { 947 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R); 948} 949 950template<typename LHS, typename RHS> 951inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> 952m_UMax(const LHS &L, const RHS &R) { 953 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R); 954} 955 956template<typename LHS, typename RHS> 957inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> 958m_UMin(const LHS &L, const RHS &R) { 959 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R); 960} 961 962/// \brief Match an 'ordered' floating point maximum function. 963/// Floating point has one special value 'NaN'. Therefore, there is no total 964/// order. However, if we can ignore the 'NaN' value (for example, because of a 965/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum' 966/// semantics. In the presence of 'NaN' we have to preserve the original 967/// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate. 968/// 969/// max(L, R) iff L and R are not NaN 970/// m_OrdFMax(L, R) = R iff L or R are NaN 971template<typename LHS, typename RHS> 972inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> 973m_OrdFMax(const LHS &L, const RHS &R) { 974 return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R); 975} 976 977/// \brief Match an 'ordered' floating point minimum function. 978/// Floating point has one special value 'NaN'. Therefore, there is no total 979/// order. However, if we can ignore the 'NaN' value (for example, because of a 980/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum' 981/// semantics. In the presence of 'NaN' we have to preserve the original 982/// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate. 983/// 984/// max(L, R) iff L and R are not NaN 985/// m_OrdFMin(L, R) = R iff L or R are NaN 986template<typename LHS, typename RHS> 987inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> 988m_OrdFMin(const LHS &L, const RHS &R) { 989 return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R); 990} 991 992/// \brief Match an 'unordered' floating point maximum function. 993/// Floating point has one special value 'NaN'. Therefore, there is no total 994/// order. However, if we can ignore the 'NaN' value (for example, because of a 995/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum' 996/// semantics. In the presence of 'NaN' we have to preserve the original 997/// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate. 998/// 999/// max(L, R) iff L and R are not NaN 1000/// m_UnordFMin(L, R) = L iff L or R are NaN 1001template<typename LHS, typename RHS> 1002inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty> 1003m_UnordFMax(const LHS &L, const RHS &R) { 1004 return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R); 1005} 1006 1007/// \brief Match an 'unordered' floating point minimum function. 1008/// Floating point has one special value 'NaN'. Therefore, there is no total 1009/// order. However, if we can ignore the 'NaN' value (for example, because of a 1010/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum' 1011/// semantics. In the presence of 'NaN' we have to preserve the original 1012/// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate. 1013/// 1014/// max(L, R) iff L and R are not NaN 1015/// m_UnordFMin(L, R) = L iff L or R are NaN 1016template<typename LHS, typename RHS> 1017inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty> 1018m_UnordFMin(const LHS &L, const RHS &R) { 1019 return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R); 1020} 1021 1022template<typename Opnd_t> 1023struct Argument_match { 1024 unsigned OpI; 1025 Opnd_t Val; 1026 Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) { } 1027 1028 template<typename OpTy> 1029 bool match(OpTy *V) { 1030 CallSite CS(V); 1031 return CS.isCall() && Val.match(CS.getArgument(OpI)); 1032 } 1033}; 1034 1035/// Match an argument 1036template<unsigned OpI, typename Opnd_t> 1037inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) { 1038 return Argument_match<Opnd_t>(OpI, Op); 1039} 1040 1041/// Intrinsic matchers. 1042struct IntrinsicID_match { 1043 unsigned ID; 1044 IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) { } 1045 1046 template<typename OpTy> 1047 bool match(OpTy *V) { 1048 IntrinsicInst *II = dyn_cast<IntrinsicInst>(V); 1049 return II && II->getIntrinsicID() == ID; 1050 } 1051}; 1052 1053/// Intrinsic matches are combinations of ID matchers, and argument 1054/// matchers. Higher arity matcher are defined recursively in terms of and-ing 1055/// them with lower arity matchers. Here's some convenient typedefs for up to 1056/// several arguments, and more can be added as needed 1057template <typename T0 = void, typename T1 = void, typename T2 = void, 1058 typename T3 = void, typename T4 = void, typename T5 = void, 1059 typename T6 = void, typename T7 = void, typename T8 = void, 1060 typename T9 = void, typename T10 = void> struct m_Intrinsic_Ty; 1061template <typename T0> 1062struct m_Intrinsic_Ty<T0> { 1063 typedef match_combine_and<IntrinsicID_match, Argument_match<T0> > Ty; 1064}; 1065template <typename T0, typename T1> 1066struct m_Intrinsic_Ty<T0, T1> { 1067 typedef match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, 1068 Argument_match<T1> > Ty; 1069}; 1070template <typename T0, typename T1, typename T2> 1071struct m_Intrinsic_Ty<T0, T1, T2> { 1072 typedef match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty, 1073 Argument_match<T2> > Ty; 1074}; 1075template <typename T0, typename T1, typename T2, typename T3> 1076struct m_Intrinsic_Ty<T0, T1, T2, T3> { 1077 typedef match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty, 1078 Argument_match<T3> > Ty; 1079}; 1080 1081/// Match intrinsic calls like this: 1082/// m_Intrinsic<Intrinsic::fabs>(m_Value(X)) 1083template <Intrinsic::ID IntrID> 1084inline IntrinsicID_match 1085m_Intrinsic() { return IntrinsicID_match(IntrID); } 1086 1087template<Intrinsic::ID IntrID, typename T0> 1088inline typename m_Intrinsic_Ty<T0>::Ty 1089m_Intrinsic(const T0 &Op0) { 1090 return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0)); 1091} 1092 1093template<Intrinsic::ID IntrID, typename T0, typename T1> 1094inline typename m_Intrinsic_Ty<T0, T1>::Ty 1095m_Intrinsic(const T0 &Op0, const T1 &Op1) { 1096 return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1)); 1097} 1098 1099template<Intrinsic::ID IntrID, typename T0, typename T1, typename T2> 1100inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty 1101m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) { 1102 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2)); 1103} 1104 1105template<Intrinsic::ID IntrID, typename T0, typename T1, typename T2, typename T3> 1106inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty 1107m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) { 1108 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3)); 1109} 1110 1111// Helper intrinsic matching specializations 1112template<typename Opnd0> 1113inline typename m_Intrinsic_Ty<Opnd0>::Ty 1114m_BSwap(const Opnd0 &Op0) { 1115 return m_Intrinsic<Intrinsic::bswap>(Op0); 1116} 1117 1118} // end namespace PatternMatch 1119} // end namespace llvm 1120 1121#endif 1122