1//===- 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_IR_PATTERNMATCH_H 30#define LLVM_IR_PATTERNMATCH_H 31 32#include "llvm/IR/CallSite.h" 33#include "llvm/IR/Constants.h" 34#include "llvm/IR/Instructions.h" 35#include "llvm/IR/Intrinsics.h" 36#include "llvm/IR/Operator.h" 37 38namespace llvm { 39namespace PatternMatch { 40 41template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) { 42 return const_cast<Pattern &>(P).match(V); 43} 44 45template <typename SubPattern_t> struct OneUse_match { 46 SubPattern_t SubPattern; 47 48 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {} 49 50 template <typename OpTy> bool match(OpTy *V) { 51 return V->hasOneUse() && SubPattern.match(V); 52 } 53}; 54 55template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) { 56 return SubPattern; 57} 58 59template <typename Class> struct class_match { 60 template <typename ITy> bool match(ITy *V) { return isa<Class>(V); } 61}; 62 63/// \brief Match an arbitrary value and ignore it. 64inline class_match<Value> m_Value() { return class_match<Value>(); } 65 66/// \brief Match an arbitrary binary operation and ignore it. 67inline class_match<BinaryOperator> m_BinOp() { 68 return class_match<BinaryOperator>(); 69} 70 71/// \brief Matches any compare instruction and ignore it. 72inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); } 73 74/// \brief Match an arbitrary ConstantInt and ignore it. 75inline class_match<ConstantInt> m_ConstantInt() { 76 return class_match<ConstantInt>(); 77} 78 79/// \brief Match an arbitrary undef constant. 80inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); } 81 82/// \brief Match an arbitrary Constant and ignore it. 83inline class_match<Constant> m_Constant() { return class_match<Constant>(); } 84 85/// Matching combinators 86template <typename LTy, typename RTy> struct match_combine_or { 87 LTy L; 88 RTy R; 89 90 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {} 91 92 template <typename ITy> bool match(ITy *V) { 93 if (L.match(V)) 94 return true; 95 if (R.match(V)) 96 return true; 97 return false; 98 } 99}; 100 101template <typename LTy, typename RTy> struct match_combine_and { 102 LTy L; 103 RTy R; 104 105 match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {} 106 107 template <typename ITy> bool match(ITy *V) { 108 if (L.match(V)) 109 if (R.match(V)) 110 return true; 111 return false; 112 } 113}; 114 115/// Combine two pattern matchers matching L || R 116template <typename LTy, typename RTy> 117inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) { 118 return match_combine_or<LTy, RTy>(L, R); 119} 120 121/// Combine two pattern matchers matching L && R 122template <typename LTy, typename RTy> 123inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) { 124 return match_combine_and<LTy, RTy>(L, R); 125} 126 127struct match_zero { 128 template <typename ITy> bool match(ITy *V) { 129 if (const auto *C = dyn_cast<Constant>(V)) 130 return C->isNullValue(); 131 return false; 132 } 133}; 134 135/// \brief 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> bool match(ITy *V) { 141 if (const auto *C = dyn_cast<Constant>(V)) 142 return C->isNegativeZeroValue(); 143 return false; 144 } 145}; 146 147/// \brief Match an arbitrary zero/null constant. This includes 148/// zero_initializer for vectors and ConstantPointerNull for pointers. For 149/// floating point constants, this will match negative zero but not positive 150/// zero 151inline match_neg_zero m_NegZero() { return match_neg_zero(); } 152 153/// \brief - Match an arbitrary zero/null constant. This includes 154/// zero_initializer for vectors and ConstantPointerNull for pointers. For 155/// floating point constants, this will match negative zero and positive zero 156inline match_combine_or<match_zero, match_neg_zero> m_AnyZero() { 157 return m_CombineOr(m_Zero(), m_NegZero()); 158} 159 160struct apint_match { 161 const APInt *&Res; 162 apint_match(const APInt *&R) : Res(R) {} 163 template <typename ITy> bool match(ITy *V) { 164 if (auto *CI = dyn_cast<ConstantInt>(V)) { 165 Res = &CI->getValue(); 166 return true; 167 } 168 if (V->getType()->isVectorTy()) 169 if (const auto *C = dyn_cast<Constant>(V)) 170 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) { 171 Res = &CI->getValue(); 172 return true; 173 } 174 return false; 175 } 176}; 177 178/// \brief Match a ConstantInt or splatted ConstantVector, binding the 179/// specified pointer to the contained APInt. 180inline apint_match m_APInt(const APInt *&Res) { return Res; } 181 182template <int64_t Val> struct constantint_match { 183 template <typename ITy> bool match(ITy *V) { 184 if (const auto *CI = dyn_cast<ConstantInt>(V)) { 185 const APInt &CIV = CI->getValue(); 186 if (Val >= 0) 187 return CIV == static_cast<uint64_t>(Val); 188 // If Val is negative, and CI is shorter than it, truncate to the right 189 // number of bits. If it is larger, then we have to sign extend. Just 190 // compare their negated values. 191 return -CIV == -Val; 192 } 193 return false; 194 } 195}; 196 197/// \brief Match a ConstantInt with a specific value. 198template <int64_t Val> inline constantint_match<Val> m_ConstantInt() { 199 return constantint_match<Val>(); 200} 201 202/// \brief This helper class is used to match scalar and vector constants that 203/// satisfy a specified predicate. 204template <typename Predicate> struct cst_pred_ty : public Predicate { 205 template <typename ITy> bool match(ITy *V) { 206 if (const auto *CI = dyn_cast<ConstantInt>(V)) 207 return this->isValue(CI->getValue()); 208 if (V->getType()->isVectorTy()) 209 if (const auto *C = dyn_cast<Constant>(V)) 210 if (const auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) 211 return this->isValue(CI->getValue()); 212 return false; 213 } 214}; 215 216/// \brief This helper class is used to match scalar and vector constants that 217/// satisfy a specified predicate, and bind them to an APInt. 218template <typename Predicate> struct api_pred_ty : public Predicate { 219 const APInt *&Res; 220 api_pred_ty(const APInt *&R) : Res(R) {} 221 template <typename ITy> bool match(ITy *V) { 222 if (const auto *CI = dyn_cast<ConstantInt>(V)) 223 if (this->isValue(CI->getValue())) { 224 Res = &CI->getValue(); 225 return true; 226 } 227 if (V->getType()->isVectorTy()) 228 if (const auto *C = dyn_cast<Constant>(V)) 229 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) 230 if (this->isValue(CI->getValue())) { 231 Res = &CI->getValue(); 232 return true; 233 } 234 235 return false; 236 } 237}; 238 239struct is_one { 240 bool isValue(const APInt &C) { return C == 1; } 241}; 242 243/// \brief Match an integer 1 or a vector with all elements equal to 1. 244inline cst_pred_ty<is_one> m_One() { return cst_pred_ty<is_one>(); } 245inline api_pred_ty<is_one> m_One(const APInt *&V) { return V; } 246 247struct is_all_ones { 248 bool isValue(const APInt &C) { return C.isAllOnesValue(); } 249}; 250 251/// \brief Match an integer or vector with all bits set to true. 252inline cst_pred_ty<is_all_ones> m_AllOnes() { 253 return cst_pred_ty<is_all_ones>(); 254} 255inline api_pred_ty<is_all_ones> m_AllOnes(const APInt *&V) { return V; } 256 257struct is_sign_bit { 258 bool isValue(const APInt &C) { return C.isSignBit(); } 259}; 260 261/// \brief Match an integer or vector with only the sign bit(s) set. 262inline cst_pred_ty<is_sign_bit> m_SignBit() { 263 return cst_pred_ty<is_sign_bit>(); 264} 265inline api_pred_ty<is_sign_bit> m_SignBit(const APInt *&V) { return V; } 266 267struct is_power2 { 268 bool isValue(const APInt &C) { return C.isPowerOf2(); } 269}; 270 271/// \brief Match an integer or vector power of 2. 272inline cst_pred_ty<is_power2> m_Power2() { return cst_pred_ty<is_power2>(); } 273inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { return V; } 274 275struct is_maxsignedvalue { 276 bool isValue(const APInt &C) { return C.isMaxSignedValue(); } 277}; 278 279inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() { return cst_pred_ty<is_maxsignedvalue>(); } 280inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) { return V; } 281 282template <typename Class> struct bind_ty { 283 Class *&VR; 284 bind_ty(Class *&V) : VR(V) {} 285 286 template <typename ITy> bool match(ITy *V) { 287 if (auto *CV = dyn_cast<Class>(V)) { 288 VR = CV; 289 return true; 290 } 291 return false; 292 } 293}; 294 295/// \brief Match a value, capturing it if we match. 296inline bind_ty<Value> m_Value(Value *&V) { return V; } 297 298/// \brief Match an instruction, capturing it if we match. 299inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; } 300 301/// \brief Match a binary operator, capturing it if we match. 302inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; } 303 304/// \brief Match a ConstantInt, capturing the value if we match. 305inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; } 306 307/// \brief Match a Constant, capturing the value if we match. 308inline bind_ty<Constant> m_Constant(Constant *&C) { return C; } 309 310/// \brief Match a ConstantFP, capturing the value if we match. 311inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; } 312 313/// \brief Match a specified Value*. 314struct specificval_ty { 315 const Value *Val; 316 specificval_ty(const Value *V) : Val(V) {} 317 318 template <typename ITy> bool match(ITy *V) { return V == Val; } 319}; 320 321/// \brief Match if we have a specific specified value. 322inline specificval_ty m_Specific(const Value *V) { return V; } 323 324/// \brief Match a specified floating point value or vector of all elements of 325/// that value. 326struct specific_fpval { 327 double Val; 328 specific_fpval(double V) : Val(V) {} 329 330 template <typename ITy> bool match(ITy *V) { 331 if (const auto *CFP = dyn_cast<ConstantFP>(V)) 332 return CFP->isExactlyValue(Val); 333 if (V->getType()->isVectorTy()) 334 if (const auto *C = dyn_cast<Constant>(V)) 335 if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue())) 336 return CFP->isExactlyValue(Val); 337 return false; 338 } 339}; 340 341/// \brief Match a specific floating point value or vector with all elements 342/// equal to the value. 343inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); } 344 345/// \brief Match a float 1.0 or vector with all elements equal to 1.0. 346inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); } 347 348struct bind_const_intval_ty { 349 uint64_t &VR; 350 bind_const_intval_ty(uint64_t &V) : VR(V) {} 351 352 template <typename ITy> bool match(ITy *V) { 353 if (const auto *CV = dyn_cast<ConstantInt>(V)) 354 if (CV->getBitWidth() <= 64) { 355 VR = CV->getZExtValue(); 356 return true; 357 } 358 return false; 359 } 360}; 361 362/// \brief Match a specified integer value or vector of all elements of that 363// value. 364struct specific_intval { 365 uint64_t Val; 366 specific_intval(uint64_t V) : Val(V) {} 367 368 template <typename ITy> bool match(ITy *V) { 369 const auto *CI = dyn_cast<ConstantInt>(V); 370 if (!CI && V->getType()->isVectorTy()) 371 if (const auto *C = dyn_cast<Constant>(V)) 372 CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()); 373 374 if (CI && CI->getBitWidth() <= 64) 375 return CI->getZExtValue() == Val; 376 377 return false; 378 } 379}; 380 381/// \brief Match a specific integer value or vector with all elements equal to 382/// the value. 383inline specific_intval m_SpecificInt(uint64_t V) { return specific_intval(V); } 384 385/// \brief Match a ConstantInt and bind to its value. This does not match 386/// ConstantInts wider than 64-bits. 387inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; } 388 389//===----------------------------------------------------------------------===// 390// Matcher for any binary operator. 391// 392template <typename LHS_t, typename RHS_t> struct AnyBinaryOp_match { 393 LHS_t L; 394 RHS_t R; 395 396 AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 397 398 template <typename OpTy> bool match(OpTy *V) { 399 if (auto *I = dyn_cast<BinaryOperator>(V)) 400 return L.match(I->getOperand(0)) && R.match(I->getOperand(1)); 401 return false; 402 } 403}; 404 405template <typename LHS, typename RHS> 406inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) { 407 return AnyBinaryOp_match<LHS, RHS>(L, R); 408} 409 410//===----------------------------------------------------------------------===// 411// Matchers for specific binary operators. 412// 413 414template <typename LHS_t, typename RHS_t, unsigned Opcode> 415struct BinaryOp_match { 416 LHS_t L; 417 RHS_t R; 418 419 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 420 421 template <typename OpTy> bool match(OpTy *V) { 422 if (V->getValueID() == Value::InstructionVal + Opcode) { 423 auto *I = cast<BinaryOperator>(V); 424 return L.match(I->getOperand(0)) && R.match(I->getOperand(1)); 425 } 426 if (auto *CE = dyn_cast<ConstantExpr>(V)) 427 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) && 428 R.match(CE->getOperand(1)); 429 return false; 430 } 431}; 432 433template <typename LHS, typename RHS> 434inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L, 435 const RHS &R) { 436 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R); 437} 438 439template <typename LHS, typename RHS> 440inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L, 441 const RHS &R) { 442 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R); 443} 444 445template <typename LHS, typename RHS> 446inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L, 447 const RHS &R) { 448 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R); 449} 450 451template <typename LHS, typename RHS> 452inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L, 453 const RHS &R) { 454 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R); 455} 456 457template <typename LHS, typename RHS> 458inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L, 459 const RHS &R) { 460 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R); 461} 462 463template <typename LHS, typename RHS> 464inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L, 465 const RHS &R) { 466 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R); 467} 468 469template <typename LHS, typename RHS> 470inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L, 471 const RHS &R) { 472 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R); 473} 474 475template <typename LHS, typename RHS> 476inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L, 477 const RHS &R) { 478 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R); 479} 480 481template <typename LHS, typename RHS> 482inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L, 483 const RHS &R) { 484 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R); 485} 486 487template <typename LHS, typename RHS> 488inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L, 489 const RHS &R) { 490 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R); 491} 492 493template <typename LHS, typename RHS> 494inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L, 495 const RHS &R) { 496 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R); 497} 498 499template <typename LHS, typename RHS> 500inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L, 501 const RHS &R) { 502 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R); 503} 504 505template <typename LHS, typename RHS> 506inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L, 507 const RHS &R) { 508 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R); 509} 510 511template <typename LHS, typename RHS> 512inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L, 513 const RHS &R) { 514 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R); 515} 516 517template <typename LHS, typename RHS> 518inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L, 519 const RHS &R) { 520 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R); 521} 522 523template <typename LHS, typename RHS> 524inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L, 525 const RHS &R) { 526 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R); 527} 528 529template <typename LHS, typename RHS> 530inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L, 531 const RHS &R) { 532 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R); 533} 534 535template <typename LHS, typename RHS> 536inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L, 537 const RHS &R) { 538 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R); 539} 540 541template <typename LHS_t, typename RHS_t, unsigned Opcode, 542 unsigned WrapFlags = 0> 543struct OverflowingBinaryOp_match { 544 LHS_t L; 545 RHS_t R; 546 547 OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) 548 : L(LHS), R(RHS) {} 549 550 template <typename OpTy> bool match(OpTy *V) { 551 if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) { 552 if (Op->getOpcode() != Opcode) 553 return false; 554 if (WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap && 555 !Op->hasNoUnsignedWrap()) 556 return false; 557 if (WrapFlags & OverflowingBinaryOperator::NoSignedWrap && 558 !Op->hasNoSignedWrap()) 559 return false; 560 return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1)); 561 } 562 return false; 563 } 564}; 565 566template <typename LHS, typename RHS> 567inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 568 OverflowingBinaryOperator::NoSignedWrap> 569m_NSWAdd(const LHS &L, const RHS &R) { 570 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 571 OverflowingBinaryOperator::NoSignedWrap>( 572 L, R); 573} 574template <typename LHS, typename RHS> 575inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 576 OverflowingBinaryOperator::NoSignedWrap> 577m_NSWSub(const LHS &L, const RHS &R) { 578 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 579 OverflowingBinaryOperator::NoSignedWrap>( 580 L, R); 581} 582template <typename LHS, typename RHS> 583inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 584 OverflowingBinaryOperator::NoSignedWrap> 585m_NSWMul(const LHS &L, const RHS &R) { 586 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 587 OverflowingBinaryOperator::NoSignedWrap>( 588 L, R); 589} 590template <typename LHS, typename RHS> 591inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 592 OverflowingBinaryOperator::NoSignedWrap> 593m_NSWShl(const LHS &L, const RHS &R) { 594 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 595 OverflowingBinaryOperator::NoSignedWrap>( 596 L, R); 597} 598 599template <typename LHS, typename RHS> 600inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 601 OverflowingBinaryOperator::NoUnsignedWrap> 602m_NUWAdd(const LHS &L, const RHS &R) { 603 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 604 OverflowingBinaryOperator::NoUnsignedWrap>( 605 L, R); 606} 607template <typename LHS, typename RHS> 608inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 609 OverflowingBinaryOperator::NoUnsignedWrap> 610m_NUWSub(const LHS &L, const RHS &R) { 611 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 612 OverflowingBinaryOperator::NoUnsignedWrap>( 613 L, R); 614} 615template <typename LHS, typename RHS> 616inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 617 OverflowingBinaryOperator::NoUnsignedWrap> 618m_NUWMul(const LHS &L, const RHS &R) { 619 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 620 OverflowingBinaryOperator::NoUnsignedWrap>( 621 L, R); 622} 623template <typename LHS, typename RHS> 624inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 625 OverflowingBinaryOperator::NoUnsignedWrap> 626m_NUWShl(const LHS &L, const RHS &R) { 627 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 628 OverflowingBinaryOperator::NoUnsignedWrap>( 629 L, R); 630} 631 632//===----------------------------------------------------------------------===// 633// Class that matches two different binary ops. 634// 635template <typename LHS_t, typename RHS_t, unsigned Opc1, unsigned Opc2> 636struct BinOp2_match { 637 LHS_t L; 638 RHS_t R; 639 640 BinOp2_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 641 642 template <typename OpTy> bool match(OpTy *V) { 643 if (V->getValueID() == Value::InstructionVal + Opc1 || 644 V->getValueID() == Value::InstructionVal + Opc2) { 645 auto *I = cast<BinaryOperator>(V); 646 return L.match(I->getOperand(0)) && R.match(I->getOperand(1)); 647 } 648 if (auto *CE = dyn_cast<ConstantExpr>(V)) 649 return (CE->getOpcode() == Opc1 || CE->getOpcode() == Opc2) && 650 L.match(CE->getOperand(0)) && R.match(CE->getOperand(1)); 651 return false; 652 } 653}; 654 655/// \brief Matches LShr or AShr. 656template <typename LHS, typename RHS> 657inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr> 658m_Shr(const LHS &L, const RHS &R) { 659 return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr>(L, R); 660} 661 662/// \brief Matches LShr or Shl. 663template <typename LHS, typename RHS> 664inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl> 665m_LogicalShift(const LHS &L, const RHS &R) { 666 return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl>(L, R); 667} 668 669/// \brief Matches UDiv and SDiv. 670template <typename LHS, typename RHS> 671inline BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv> 672m_IDiv(const LHS &L, const RHS &R) { 673 return BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv>(L, R); 674} 675 676//===----------------------------------------------------------------------===// 677// Class that matches exact binary ops. 678// 679template <typename SubPattern_t> struct Exact_match { 680 SubPattern_t SubPattern; 681 682 Exact_match(const SubPattern_t &SP) : SubPattern(SP) {} 683 684 template <typename OpTy> bool match(OpTy *V) { 685 if (PossiblyExactOperator *PEO = dyn_cast<PossiblyExactOperator>(V)) 686 return PEO->isExact() && SubPattern.match(V); 687 return false; 688 } 689}; 690 691template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) { 692 return SubPattern; 693} 694 695//===----------------------------------------------------------------------===// 696// Matchers for CmpInst classes 697// 698 699template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy> 700struct CmpClass_match { 701 PredicateTy &Predicate; 702 LHS_t L; 703 RHS_t R; 704 705 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS) 706 : Predicate(Pred), L(LHS), R(RHS) {} 707 708 template <typename OpTy> bool match(OpTy *V) { 709 if (Class *I = dyn_cast<Class>(V)) 710 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) { 711 Predicate = I->getPredicate(); 712 return true; 713 } 714 return false; 715 } 716}; 717 718template <typename LHS, typename RHS> 719inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate> 720m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 721 return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R); 722} 723 724template <typename LHS, typename RHS> 725inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate> 726m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 727 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R); 728} 729 730template <typename LHS, typename RHS> 731inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate> 732m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 733 return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R); 734} 735 736//===----------------------------------------------------------------------===// 737// Matchers for SelectInst classes 738// 739 740template <typename Cond_t, typename LHS_t, typename RHS_t> 741struct SelectClass_match { 742 Cond_t C; 743 LHS_t L; 744 RHS_t R; 745 746 SelectClass_match(const Cond_t &Cond, const LHS_t &LHS, const RHS_t &RHS) 747 : C(Cond), L(LHS), R(RHS) {} 748 749 template <typename OpTy> bool match(OpTy *V) { 750 if (auto *I = dyn_cast<SelectInst>(V)) 751 return C.match(I->getOperand(0)) && L.match(I->getOperand(1)) && 752 R.match(I->getOperand(2)); 753 return false; 754 } 755}; 756 757template <typename Cond, typename LHS, typename RHS> 758inline SelectClass_match<Cond, LHS, RHS> m_Select(const Cond &C, const LHS &L, 759 const RHS &R) { 760 return SelectClass_match<Cond, LHS, RHS>(C, L, R); 761} 762 763/// \brief This matches a select of two constants, e.g.: 764/// m_SelectCst<-1, 0>(m_Value(V)) 765template <int64_t L, int64_t R, typename Cond> 766inline SelectClass_match<Cond, constantint_match<L>, constantint_match<R>> 767m_SelectCst(const Cond &C) { 768 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>()); 769} 770 771//===----------------------------------------------------------------------===// 772// Matchers for CastInst classes 773// 774 775template <typename Op_t, unsigned Opcode> struct CastClass_match { 776 Op_t Op; 777 778 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {} 779 780 template <typename OpTy> bool match(OpTy *V) { 781 if (auto *O = dyn_cast<Operator>(V)) 782 return O->getOpcode() == Opcode && Op.match(O->getOperand(0)); 783 return false; 784 } 785}; 786 787/// \brief Matches BitCast. 788template <typename OpTy> 789inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) { 790 return CastClass_match<OpTy, Instruction::BitCast>(Op); 791} 792 793/// \brief Matches PtrToInt. 794template <typename OpTy> 795inline CastClass_match<OpTy, Instruction::PtrToInt> m_PtrToInt(const OpTy &Op) { 796 return CastClass_match<OpTy, Instruction::PtrToInt>(Op); 797} 798 799/// \brief Matches Trunc. 800template <typename OpTy> 801inline CastClass_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) { 802 return CastClass_match<OpTy, Instruction::Trunc>(Op); 803} 804 805/// \brief Matches SExt. 806template <typename OpTy> 807inline CastClass_match<OpTy, Instruction::SExt> m_SExt(const OpTy &Op) { 808 return CastClass_match<OpTy, Instruction::SExt>(Op); 809} 810 811/// \brief Matches ZExt. 812template <typename OpTy> 813inline CastClass_match<OpTy, Instruction::ZExt> m_ZExt(const OpTy &Op) { 814 return CastClass_match<OpTy, Instruction::ZExt>(Op); 815} 816 817/// \brief Matches UIToFP. 818template <typename OpTy> 819inline CastClass_match<OpTy, Instruction::UIToFP> m_UIToFP(const OpTy &Op) { 820 return CastClass_match<OpTy, Instruction::UIToFP>(Op); 821} 822 823/// \brief Matches SIToFP. 824template <typename OpTy> 825inline CastClass_match<OpTy, Instruction::SIToFP> m_SIToFP(const OpTy &Op) { 826 return CastClass_match<OpTy, Instruction::SIToFP>(Op); 827} 828 829//===----------------------------------------------------------------------===// 830// Matchers for unary operators 831// 832 833template <typename LHS_t> struct not_match { 834 LHS_t L; 835 836 not_match(const LHS_t &LHS) : L(LHS) {} 837 838 template <typename OpTy> bool match(OpTy *V) { 839 if (auto *O = dyn_cast<Operator>(V)) 840 if (O->getOpcode() == Instruction::Xor) 841 return matchIfNot(O->getOperand(0), O->getOperand(1)); 842 return false; 843 } 844 845private: 846 bool matchIfNot(Value *LHS, Value *RHS) { 847 return (isa<ConstantInt>(RHS) || isa<ConstantDataVector>(RHS) || 848 // FIXME: Remove CV. 849 isa<ConstantVector>(RHS)) && 850 cast<Constant>(RHS)->isAllOnesValue() && L.match(LHS); 851 } 852}; 853 854template <typename LHS> inline not_match<LHS> m_Not(const LHS &L) { return L; } 855 856template <typename LHS_t> struct neg_match { 857 LHS_t L; 858 859 neg_match(const LHS_t &LHS) : L(LHS) {} 860 861 template <typename OpTy> bool match(OpTy *V) { 862 if (auto *O = dyn_cast<Operator>(V)) 863 if (O->getOpcode() == Instruction::Sub) 864 return matchIfNeg(O->getOperand(0), O->getOperand(1)); 865 return false; 866 } 867 868private: 869 bool matchIfNeg(Value *LHS, Value *RHS) { 870 return ((isa<ConstantInt>(LHS) && cast<ConstantInt>(LHS)->isZero()) || 871 isa<ConstantAggregateZero>(LHS)) && 872 L.match(RHS); 873 } 874}; 875 876/// \brief Match an integer negate. 877template <typename LHS> inline neg_match<LHS> m_Neg(const LHS &L) { return L; } 878 879template <typename LHS_t> struct fneg_match { 880 LHS_t L; 881 882 fneg_match(const LHS_t &LHS) : L(LHS) {} 883 884 template <typename OpTy> bool match(OpTy *V) { 885 if (auto *O = dyn_cast<Operator>(V)) 886 if (O->getOpcode() == Instruction::FSub) 887 return matchIfFNeg(O->getOperand(0), O->getOperand(1)); 888 return false; 889 } 890 891private: 892 bool matchIfFNeg(Value *LHS, Value *RHS) { 893 if (const auto *C = dyn_cast<ConstantFP>(LHS)) 894 return C->isNegativeZeroValue() && L.match(RHS); 895 return false; 896 } 897}; 898 899/// \brief Match a floating point negate. 900template <typename LHS> inline fneg_match<LHS> m_FNeg(const LHS &L) { 901 return L; 902} 903 904//===----------------------------------------------------------------------===// 905// Matchers for control flow. 906// 907 908struct br_match { 909 BasicBlock *&Succ; 910 br_match(BasicBlock *&Succ) : Succ(Succ) {} 911 912 template <typename OpTy> bool match(OpTy *V) { 913 if (auto *BI = dyn_cast<BranchInst>(V)) 914 if (BI->isUnconditional()) { 915 Succ = BI->getSuccessor(0); 916 return true; 917 } 918 return false; 919 } 920}; 921 922inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); } 923 924template <typename Cond_t> struct brc_match { 925 Cond_t Cond; 926 BasicBlock *&T, *&F; 927 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f) 928 : Cond(C), T(t), F(f) {} 929 930 template <typename OpTy> bool match(OpTy *V) { 931 if (auto *BI = dyn_cast<BranchInst>(V)) 932 if (BI->isConditional() && Cond.match(BI->getCondition())) { 933 T = BI->getSuccessor(0); 934 F = BI->getSuccessor(1); 935 return true; 936 } 937 return false; 938 } 939}; 940 941template <typename Cond_t> 942inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) { 943 return brc_match<Cond_t>(C, T, F); 944} 945 946//===----------------------------------------------------------------------===// 947// Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y). 948// 949 950template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t> 951struct MaxMin_match { 952 LHS_t L; 953 RHS_t R; 954 955 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 956 957 template <typename OpTy> bool match(OpTy *V) { 958 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x". 959 auto *SI = dyn_cast<SelectInst>(V); 960 if (!SI) 961 return false; 962 auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition()); 963 if (!Cmp) 964 return false; 965 // At this point we have a select conditioned on a comparison. Check that 966 // it is the values returned by the select that are being compared. 967 Value *TrueVal = SI->getTrueValue(); 968 Value *FalseVal = SI->getFalseValue(); 969 Value *LHS = Cmp->getOperand(0); 970 Value *RHS = Cmp->getOperand(1); 971 if ((TrueVal != LHS || FalseVal != RHS) && 972 (TrueVal != RHS || FalseVal != LHS)) 973 return false; 974 typename CmpInst_t::Predicate Pred = 975 LHS == TrueVal ? Cmp->getPredicate() : Cmp->getSwappedPredicate(); 976 // Does "(x pred y) ? x : y" represent the desired max/min operation? 977 if (!Pred_t::match(Pred)) 978 return false; 979 // It does! Bind the operands. 980 return L.match(LHS) && R.match(RHS); 981 } 982}; 983 984/// \brief Helper class for identifying signed max predicates. 985struct smax_pred_ty { 986 static bool match(ICmpInst::Predicate Pred) { 987 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE; 988 } 989}; 990 991/// \brief Helper class for identifying signed min predicates. 992struct smin_pred_ty { 993 static bool match(ICmpInst::Predicate Pred) { 994 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE; 995 } 996}; 997 998/// \brief Helper class for identifying unsigned max predicates. 999struct umax_pred_ty { 1000 static bool match(ICmpInst::Predicate Pred) { 1001 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE; 1002 } 1003}; 1004 1005/// \brief Helper class for identifying unsigned min predicates. 1006struct umin_pred_ty { 1007 static bool match(ICmpInst::Predicate Pred) { 1008 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE; 1009 } 1010}; 1011 1012/// \brief Helper class for identifying ordered max predicates. 1013struct ofmax_pred_ty { 1014 static bool match(FCmpInst::Predicate Pred) { 1015 return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE; 1016 } 1017}; 1018 1019/// \brief Helper class for identifying ordered min predicates. 1020struct ofmin_pred_ty { 1021 static bool match(FCmpInst::Predicate Pred) { 1022 return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE; 1023 } 1024}; 1025 1026/// \brief Helper class for identifying unordered max predicates. 1027struct ufmax_pred_ty { 1028 static bool match(FCmpInst::Predicate Pred) { 1029 return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE; 1030 } 1031}; 1032 1033/// \brief Helper class for identifying unordered min predicates. 1034struct ufmin_pred_ty { 1035 static bool match(FCmpInst::Predicate Pred) { 1036 return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE; 1037 } 1038}; 1039 1040template <typename LHS, typename RHS> 1041inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L, 1042 const RHS &R) { 1043 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R); 1044} 1045 1046template <typename LHS, typename RHS> 1047inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L, 1048 const RHS &R) { 1049 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R); 1050} 1051 1052template <typename LHS, typename RHS> 1053inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L, 1054 const RHS &R) { 1055 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R); 1056} 1057 1058template <typename LHS, typename RHS> 1059inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L, 1060 const RHS &R) { 1061 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R); 1062} 1063 1064/// \brief Match an 'ordered' floating point maximum function. 1065/// Floating point has one special value 'NaN'. Therefore, there is no total 1066/// order. However, if we can ignore the 'NaN' value (for example, because of a 1067/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum' 1068/// semantics. In the presence of 'NaN' we have to preserve the original 1069/// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate. 1070/// 1071/// max(L, R) iff L and R are not NaN 1072/// m_OrdFMax(L, R) = R iff L or R are NaN 1073template <typename LHS, typename RHS> 1074inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L, 1075 const RHS &R) { 1076 return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R); 1077} 1078 1079/// \brief Match an 'ordered' floating point minimum function. 1080/// Floating point has one special value 'NaN'. Therefore, there is no total 1081/// order. However, if we can ignore the 'NaN' value (for example, because of a 1082/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum' 1083/// semantics. In the presence of 'NaN' we have to preserve the original 1084/// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate. 1085/// 1086/// max(L, R) iff L and R are not NaN 1087/// m_OrdFMin(L, R) = R iff L or R are NaN 1088template <typename LHS, typename RHS> 1089inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L, 1090 const RHS &R) { 1091 return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R); 1092} 1093 1094/// \brief Match an 'unordered' floating point maximum function. 1095/// Floating point has one special value 'NaN'. Therefore, there is no total 1096/// order. However, if we can ignore the 'NaN' value (for example, because of a 1097/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum' 1098/// semantics. In the presence of 'NaN' we have to preserve the original 1099/// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate. 1100/// 1101/// max(L, R) iff L and R are not NaN 1102/// m_UnordFMin(L, R) = L iff L or R are NaN 1103template <typename LHS, typename RHS> 1104inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty> 1105m_UnordFMax(const LHS &L, const RHS &R) { 1106 return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R); 1107} 1108 1109//===----------------------------------------------------------------------===// 1110// Matchers for overflow check patterns: e.g. (a + b) u< a 1111// 1112 1113template <typename LHS_t, typename RHS_t, typename Sum_t> 1114struct UAddWithOverflow_match { 1115 LHS_t L; 1116 RHS_t R; 1117 Sum_t S; 1118 1119 UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S) 1120 : L(L), R(R), S(S) {} 1121 1122 template <typename OpTy> bool match(OpTy *V) { 1123 Value *ICmpLHS, *ICmpRHS; 1124 ICmpInst::Predicate Pred; 1125 if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V)) 1126 return false; 1127 1128 Value *AddLHS, *AddRHS; 1129 auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS)); 1130 1131 // (a + b) u< a, (a + b) u< b 1132 if (Pred == ICmpInst::ICMP_ULT) 1133 if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS)) 1134 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS); 1135 1136 // a >u (a + b), b >u (a + b) 1137 if (Pred == ICmpInst::ICMP_UGT) 1138 if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS)) 1139 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS); 1140 1141 return false; 1142 } 1143}; 1144 1145/// \brief Match an icmp instruction checking for unsigned overflow on addition. 1146/// 1147/// S is matched to the addition whose result is being checked for overflow, and 1148/// L and R are matched to the LHS and RHS of S. 1149template <typename LHS_t, typename RHS_t, typename Sum_t> 1150UAddWithOverflow_match<LHS_t, RHS_t, Sum_t> 1151m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) { 1152 return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S); 1153} 1154 1155/// \brief Match an 'unordered' floating point minimum function. 1156/// Floating point has one special value 'NaN'. Therefore, there is no total 1157/// order. However, if we can ignore the 'NaN' value (for example, because of a 1158/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum' 1159/// semantics. In the presence of 'NaN' we have to preserve the original 1160/// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate. 1161/// 1162/// max(L, R) iff L and R are not NaN 1163/// m_UnordFMin(L, R) = L iff L or R are NaN 1164template <typename LHS, typename RHS> 1165inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty> 1166m_UnordFMin(const LHS &L, const RHS &R) { 1167 return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R); 1168} 1169 1170template <typename Opnd_t> struct Argument_match { 1171 unsigned OpI; 1172 Opnd_t Val; 1173 Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {} 1174 1175 template <typename OpTy> bool match(OpTy *V) { 1176 CallSite CS(V); 1177 return CS.isCall() && Val.match(CS.getArgument(OpI)); 1178 } 1179}; 1180 1181/// \brief Match an argument. 1182template <unsigned OpI, typename Opnd_t> 1183inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) { 1184 return Argument_match<Opnd_t>(OpI, Op); 1185} 1186 1187/// \brief Intrinsic matchers. 1188struct IntrinsicID_match { 1189 unsigned ID; 1190 IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {} 1191 1192 template <typename OpTy> bool match(OpTy *V) { 1193 if (const auto *CI = dyn_cast<CallInst>(V)) 1194 if (const auto *F = CI->getCalledFunction()) 1195 return F->getIntrinsicID() == ID; 1196 return false; 1197 } 1198}; 1199 1200/// Intrinsic matches are combinations of ID matchers, and argument 1201/// matchers. Higher arity matcher are defined recursively in terms of and-ing 1202/// them with lower arity matchers. Here's some convenient typedefs for up to 1203/// several arguments, and more can be added as needed 1204template <typename T0 = void, typename T1 = void, typename T2 = void, 1205 typename T3 = void, typename T4 = void, typename T5 = void, 1206 typename T6 = void, typename T7 = void, typename T8 = void, 1207 typename T9 = void, typename T10 = void> 1208struct m_Intrinsic_Ty; 1209template <typename T0> struct m_Intrinsic_Ty<T0> { 1210 typedef match_combine_and<IntrinsicID_match, Argument_match<T0>> Ty; 1211}; 1212template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> { 1213 typedef match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>> 1214 Ty; 1215}; 1216template <typename T0, typename T1, typename T2> 1217struct m_Intrinsic_Ty<T0, T1, T2> { 1218 typedef match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty, 1219 Argument_match<T2>> Ty; 1220}; 1221template <typename T0, typename T1, typename T2, typename T3> 1222struct m_Intrinsic_Ty<T0, T1, T2, T3> { 1223 typedef match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty, 1224 Argument_match<T3>> Ty; 1225}; 1226 1227/// \brief Match intrinsic calls like this: 1228/// m_Intrinsic<Intrinsic::fabs>(m_Value(X)) 1229template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() { 1230 return IntrinsicID_match(IntrID); 1231} 1232 1233template <Intrinsic::ID IntrID, typename T0> 1234inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) { 1235 return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0)); 1236} 1237 1238template <Intrinsic::ID IntrID, typename T0, typename T1> 1239inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0, 1240 const T1 &Op1) { 1241 return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1)); 1242} 1243 1244template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2> 1245inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty 1246m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) { 1247 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2)); 1248} 1249 1250template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2, 1251 typename T3> 1252inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty 1253m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) { 1254 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3)); 1255} 1256 1257// Helper intrinsic matching specializations. 1258template <typename Opnd0> 1259inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) { 1260 return m_Intrinsic<Intrinsic::bswap>(Op0); 1261} 1262 1263template <typename Opnd0, typename Opnd1> 1264inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0, 1265 const Opnd1 &Op1) { 1266 return m_Intrinsic<Intrinsic::minnum>(Op0, Op1); 1267} 1268 1269template <typename Opnd0, typename Opnd1> 1270inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0, 1271 const Opnd1 &Op1) { 1272 return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1); 1273} 1274 1275template <typename Opnd_t> struct Signum_match { 1276 Opnd_t Val; 1277 Signum_match(const Opnd_t &V) : Val(V) {} 1278 1279 template <typename OpTy> bool match(OpTy *V) { 1280 unsigned TypeSize = V->getType()->getScalarSizeInBits(); 1281 if (TypeSize == 0) 1282 return false; 1283 1284 unsigned ShiftWidth = TypeSize - 1; 1285 Value *OpL = nullptr, *OpR = nullptr; 1286 1287 // This is the representation of signum we match: 1288 // 1289 // signum(x) == (x >> 63) | (-x >>u 63) 1290 // 1291 // An i1 value is its own signum, so it's correct to match 1292 // 1293 // signum(x) == (x >> 0) | (-x >>u 0) 1294 // 1295 // for i1 values. 1296 1297 auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth)); 1298 auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth)); 1299 auto Signum = m_Or(LHS, RHS); 1300 1301 return Signum.match(V) && OpL == OpR && Val.match(OpL); 1302 } 1303}; 1304 1305/// \brief Matches a signum pattern. 1306/// 1307/// signum(x) = 1308/// x > 0 -> 1 1309/// x == 0 -> 0 1310/// x < 0 -> -1 1311template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) { 1312 return Signum_match<Val_t>(V); 1313} 1314 1315//===----------------------------------------------------------------------===// 1316// Matchers for two-operands operators with the operators in either order 1317// 1318 1319/// \brief Matches an ICmp with a predicate over LHS and RHS in either order. 1320/// Does not swap the predicate. 1321template<typename LHS, typename RHS> 1322inline match_combine_or<CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>, 1323 CmpClass_match<RHS, LHS, ICmpInst, ICmpInst::Predicate>> 1324m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 1325 return m_CombineOr(m_ICmp(Pred, L, R), m_ICmp(Pred, R, L)); 1326} 1327 1328/// \brief Matches an And with LHS and RHS in either order. 1329template<typename LHS, typename RHS> 1330inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::And>, 1331 BinaryOp_match<RHS, LHS, Instruction::And>> 1332m_c_And(const LHS &L, const RHS &R) { 1333 return m_CombineOr(m_And(L, R), m_And(R, L)); 1334} 1335 1336/// \brief Matches an Or with LHS and RHS in either order. 1337template<typename LHS, typename RHS> 1338inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Or>, 1339 BinaryOp_match<RHS, LHS, Instruction::Or>> 1340m_c_Or(const LHS &L, const RHS &R) { 1341 return m_CombineOr(m_Or(L, R), m_Or(R, L)); 1342} 1343 1344/// \brief Matches an Xor with LHS and RHS in either order. 1345template<typename LHS, typename RHS> 1346inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Xor>, 1347 BinaryOp_match<RHS, LHS, Instruction::Xor>> 1348m_c_Xor(const LHS &L, const RHS &R) { 1349 return m_CombineOr(m_Xor(L, R), m_Xor(R, L)); 1350} 1351 1352} // end namespace PatternMatch 1353} // end namespace llvm 1354 1355#endif 1356