PatternMatch.h revision 360784
1//===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This file provides a simple and efficient mechanism for performing general 10// tree-based pattern matches on the LLVM IR. The power of these routines is 11// that it allows you to write concise patterns that are expressive and easy to 12// understand. The other major advantage of this is that it allows you to 13// trivially capture/bind elements in the pattern to variables. For example, 14// you can do something like this: 15// 16// Value *Exp = ... 17// Value *X, *Y; ConstantInt *C1, *C2; // (X & C1) | (Y & C2) 18// if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)), 19// m_And(m_Value(Y), m_ConstantInt(C2))))) { 20// ... Pattern is matched and variables are bound ... 21// } 22// 23// This is primarily useful to things like the instruction combiner, but can 24// also be useful for static analysis tools or code generators. 25// 26//===----------------------------------------------------------------------===// 27 28#ifndef LLVM_IR_PATTERNMATCH_H 29#define LLVM_IR_PATTERNMATCH_H 30 31#include "llvm/ADT/APFloat.h" 32#include "llvm/ADT/APInt.h" 33#include "llvm/IR/Constant.h" 34#include "llvm/IR/Constants.h" 35#include "llvm/IR/InstrTypes.h" 36#include "llvm/IR/Instruction.h" 37#include "llvm/IR/Instructions.h" 38#include "llvm/IR/IntrinsicInst.h" 39#include "llvm/IR/Intrinsics.h" 40#include "llvm/IR/Operator.h" 41#include "llvm/IR/Value.h" 42#include "llvm/Support/Casting.h" 43#include <cstdint> 44 45namespace llvm { 46namespace PatternMatch { 47 48template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) { 49 return const_cast<Pattern &>(P).match(V); 50} 51 52template <typename SubPattern_t> struct OneUse_match { 53 SubPattern_t SubPattern; 54 55 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {} 56 57 template <typename OpTy> bool match(OpTy *V) { 58 return V->hasOneUse() && SubPattern.match(V); 59 } 60}; 61 62template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) { 63 return SubPattern; 64} 65 66template <typename Class> struct class_match { 67 template <typename ITy> bool match(ITy *V) { return isa<Class>(V); } 68}; 69 70/// Match an arbitrary value and ignore it. 71inline class_match<Value> m_Value() { return class_match<Value>(); } 72 73/// Match an arbitrary binary operation and ignore it. 74inline class_match<BinaryOperator> m_BinOp() { 75 return class_match<BinaryOperator>(); 76} 77 78/// Matches any compare instruction and ignore it. 79inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); } 80 81/// Match an arbitrary ConstantInt and ignore it. 82inline class_match<ConstantInt> m_ConstantInt() { 83 return class_match<ConstantInt>(); 84} 85 86/// Match an arbitrary undef constant. 87inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); } 88 89/// Match an arbitrary Constant and ignore it. 90inline class_match<Constant> m_Constant() { return class_match<Constant>(); } 91 92/// Match an arbitrary basic block value and ignore it. 93inline class_match<BasicBlock> m_BasicBlock() { 94 return class_match<BasicBlock>(); 95} 96 97/// Inverting matcher 98template <typename Ty> struct match_unless { 99 Ty M; 100 101 match_unless(const Ty &Matcher) : M(Matcher) {} 102 103 template <typename ITy> bool match(ITy *V) { return !M.match(V); } 104}; 105 106/// Match if the inner matcher does *NOT* match. 107template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) { 108 return match_unless<Ty>(M); 109} 110 111/// Matching combinators 112template <typename LTy, typename RTy> struct match_combine_or { 113 LTy L; 114 RTy R; 115 116 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {} 117 118 template <typename ITy> bool match(ITy *V) { 119 if (L.match(V)) 120 return true; 121 if (R.match(V)) 122 return true; 123 return false; 124 } 125}; 126 127template <typename LTy, typename RTy> struct match_combine_and { 128 LTy L; 129 RTy R; 130 131 match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {} 132 133 template <typename ITy> bool match(ITy *V) { 134 if (L.match(V)) 135 if (R.match(V)) 136 return true; 137 return false; 138 } 139}; 140 141/// Combine two pattern matchers matching L || R 142template <typename LTy, typename RTy> 143inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) { 144 return match_combine_or<LTy, RTy>(L, R); 145} 146 147/// Combine two pattern matchers matching L && R 148template <typename LTy, typename RTy> 149inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) { 150 return match_combine_and<LTy, RTy>(L, R); 151} 152 153struct apint_match { 154 const APInt *&Res; 155 156 apint_match(const APInt *&R) : Res(R) {} 157 158 template <typename ITy> bool match(ITy *V) { 159 if (auto *CI = dyn_cast<ConstantInt>(V)) { 160 Res = &CI->getValue(); 161 return true; 162 } 163 if (V->getType()->isVectorTy()) 164 if (const auto *C = dyn_cast<Constant>(V)) 165 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) { 166 Res = &CI->getValue(); 167 return true; 168 } 169 return false; 170 } 171}; 172// Either constexpr if or renaming ConstantFP::getValueAPF to 173// ConstantFP::getValue is needed to do it via single template 174// function for both apint/apfloat. 175struct apfloat_match { 176 const APFloat *&Res; 177 apfloat_match(const APFloat *&R) : Res(R) {} 178 template <typename ITy> bool match(ITy *V) { 179 if (auto *CI = dyn_cast<ConstantFP>(V)) { 180 Res = &CI->getValueAPF(); 181 return true; 182 } 183 if (V->getType()->isVectorTy()) 184 if (const auto *C = dyn_cast<Constant>(V)) 185 if (auto *CI = dyn_cast_or_null<ConstantFP>(C->getSplatValue())) { 186 Res = &CI->getValueAPF(); 187 return true; 188 } 189 return false; 190 } 191}; 192 193/// Match a ConstantInt or splatted ConstantVector, binding the 194/// specified pointer to the contained APInt. 195inline apint_match m_APInt(const APInt *&Res) { return Res; } 196 197/// Match a ConstantFP or splatted ConstantVector, binding the 198/// specified pointer to the contained APFloat. 199inline apfloat_match m_APFloat(const APFloat *&Res) { return Res; } 200 201template <int64_t Val> struct constantint_match { 202 template <typename ITy> bool match(ITy *V) { 203 if (const auto *CI = dyn_cast<ConstantInt>(V)) { 204 const APInt &CIV = CI->getValue(); 205 if (Val >= 0) 206 return CIV == static_cast<uint64_t>(Val); 207 // If Val is negative, and CI is shorter than it, truncate to the right 208 // number of bits. If it is larger, then we have to sign extend. Just 209 // compare their negated values. 210 return -CIV == -Val; 211 } 212 return false; 213 } 214}; 215 216/// Match a ConstantInt with a specific value. 217template <int64_t Val> inline constantint_match<Val> m_ConstantInt() { 218 return constantint_match<Val>(); 219} 220 221/// This helper class is used to match scalar and vector integer constants that 222/// satisfy a specified predicate. 223/// For vector constants, undefined elements are ignored. 224template <typename Predicate> struct cst_pred_ty : public Predicate { 225 template <typename ITy> bool match(ITy *V) { 226 if (const auto *CI = dyn_cast<ConstantInt>(V)) 227 return this->isValue(CI->getValue()); 228 if (V->getType()->isVectorTy()) { 229 if (const auto *C = dyn_cast<Constant>(V)) { 230 if (const auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) 231 return this->isValue(CI->getValue()); 232 233 // Non-splat vector constant: check each element for a match. 234 unsigned NumElts = V->getType()->getVectorNumElements(); 235 assert(NumElts != 0 && "Constant vector with no elements?"); 236 bool HasNonUndefElements = false; 237 for (unsigned i = 0; i != NumElts; ++i) { 238 Constant *Elt = C->getAggregateElement(i); 239 if (!Elt) 240 return false; 241 if (isa<UndefValue>(Elt)) 242 continue; 243 auto *CI = dyn_cast<ConstantInt>(Elt); 244 if (!CI || !this->isValue(CI->getValue())) 245 return false; 246 HasNonUndefElements = true; 247 } 248 return HasNonUndefElements; 249 } 250 } 251 return false; 252 } 253}; 254 255/// This helper class is used to match scalar and vector constants that 256/// satisfy a specified predicate, and bind them to an APInt. 257template <typename Predicate> struct api_pred_ty : public Predicate { 258 const APInt *&Res; 259 260 api_pred_ty(const APInt *&R) : Res(R) {} 261 262 template <typename ITy> bool match(ITy *V) { 263 if (const auto *CI = dyn_cast<ConstantInt>(V)) 264 if (this->isValue(CI->getValue())) { 265 Res = &CI->getValue(); 266 return true; 267 } 268 if (V->getType()->isVectorTy()) 269 if (const auto *C = dyn_cast<Constant>(V)) 270 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) 271 if (this->isValue(CI->getValue())) { 272 Res = &CI->getValue(); 273 return true; 274 } 275 276 return false; 277 } 278}; 279 280/// This helper class is used to match scalar and vector floating-point 281/// constants that satisfy a specified predicate. 282/// For vector constants, undefined elements are ignored. 283template <typename Predicate> struct cstfp_pred_ty : public Predicate { 284 template <typename ITy> bool match(ITy *V) { 285 if (const auto *CF = dyn_cast<ConstantFP>(V)) 286 return this->isValue(CF->getValueAPF()); 287 if (V->getType()->isVectorTy()) { 288 if (const auto *C = dyn_cast<Constant>(V)) { 289 if (const auto *CF = dyn_cast_or_null<ConstantFP>(C->getSplatValue())) 290 return this->isValue(CF->getValueAPF()); 291 292 // Non-splat vector constant: check each element for a match. 293 unsigned NumElts = V->getType()->getVectorNumElements(); 294 assert(NumElts != 0 && "Constant vector with no elements?"); 295 bool HasNonUndefElements = false; 296 for (unsigned i = 0; i != NumElts; ++i) { 297 Constant *Elt = C->getAggregateElement(i); 298 if (!Elt) 299 return false; 300 if (isa<UndefValue>(Elt)) 301 continue; 302 auto *CF = dyn_cast<ConstantFP>(Elt); 303 if (!CF || !this->isValue(CF->getValueAPF())) 304 return false; 305 HasNonUndefElements = true; 306 } 307 return HasNonUndefElements; 308 } 309 } 310 return false; 311 } 312}; 313 314/////////////////////////////////////////////////////////////////////////////// 315// 316// Encapsulate constant value queries for use in templated predicate matchers. 317// This allows checking if constants match using compound predicates and works 318// with vector constants, possibly with relaxed constraints. For example, ignore 319// undef values. 320// 321/////////////////////////////////////////////////////////////////////////////// 322 323struct is_any_apint { 324 bool isValue(const APInt &C) { return true; } 325}; 326/// Match an integer or vector with any integral constant. 327/// For vectors, this includes constants with undefined elements. 328inline cst_pred_ty<is_any_apint> m_AnyIntegralConstant() { 329 return cst_pred_ty<is_any_apint>(); 330} 331 332struct is_all_ones { 333 bool isValue(const APInt &C) { return C.isAllOnesValue(); } 334}; 335/// Match an integer or vector with all bits set. 336/// For vectors, this includes constants with undefined elements. 337inline cst_pred_ty<is_all_ones> m_AllOnes() { 338 return cst_pred_ty<is_all_ones>(); 339} 340 341struct is_maxsignedvalue { 342 bool isValue(const APInt &C) { return C.isMaxSignedValue(); } 343}; 344/// Match an integer or vector with values having all bits except for the high 345/// bit set (0x7f...). 346/// For vectors, this includes constants with undefined elements. 347inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() { 348 return cst_pred_ty<is_maxsignedvalue>(); 349} 350inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) { 351 return V; 352} 353 354struct is_negative { 355 bool isValue(const APInt &C) { return C.isNegative(); } 356}; 357/// Match an integer or vector of negative values. 358/// For vectors, this includes constants with undefined elements. 359inline cst_pred_ty<is_negative> m_Negative() { 360 return cst_pred_ty<is_negative>(); 361} 362inline api_pred_ty<is_negative> m_Negative(const APInt *&V) { 363 return V; 364} 365 366struct is_nonnegative { 367 bool isValue(const APInt &C) { return C.isNonNegative(); } 368}; 369/// Match an integer or vector of non-negative values. 370/// For vectors, this includes constants with undefined elements. 371inline cst_pred_ty<is_nonnegative> m_NonNegative() { 372 return cst_pred_ty<is_nonnegative>(); 373} 374inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) { 375 return V; 376} 377 378struct is_strictlypositive { 379 bool isValue(const APInt &C) { return C.isStrictlyPositive(); } 380}; 381/// Match an integer or vector of strictly positive values. 382/// For vectors, this includes constants with undefined elements. 383inline cst_pred_ty<is_strictlypositive> m_StrictlyPositive() { 384 return cst_pred_ty<is_strictlypositive>(); 385} 386inline api_pred_ty<is_strictlypositive> m_StrictlyPositive(const APInt *&V) { 387 return V; 388} 389 390struct is_nonpositive { 391 bool isValue(const APInt &C) { return C.isNonPositive(); } 392}; 393/// Match an integer or vector of non-positive values. 394/// For vectors, this includes constants with undefined elements. 395inline cst_pred_ty<is_nonpositive> m_NonPositive() { 396 return cst_pred_ty<is_nonpositive>(); 397} 398inline api_pred_ty<is_nonpositive> m_NonPositive(const APInt *&V) { return V; } 399 400struct is_one { 401 bool isValue(const APInt &C) { return C.isOneValue(); } 402}; 403/// Match an integer 1 or a vector with all elements equal to 1. 404/// For vectors, this includes constants with undefined elements. 405inline cst_pred_ty<is_one> m_One() { 406 return cst_pred_ty<is_one>(); 407} 408 409struct is_zero_int { 410 bool isValue(const APInt &C) { return C.isNullValue(); } 411}; 412/// Match an integer 0 or a vector with all elements equal to 0. 413/// For vectors, this includes constants with undefined elements. 414inline cst_pred_ty<is_zero_int> m_ZeroInt() { 415 return cst_pred_ty<is_zero_int>(); 416} 417 418struct is_zero { 419 template <typename ITy> bool match(ITy *V) { 420 auto *C = dyn_cast<Constant>(V); 421 return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C)); 422 } 423}; 424/// Match any null constant or a vector with all elements equal to 0. 425/// For vectors, this includes constants with undefined elements. 426inline is_zero m_Zero() { 427 return is_zero(); 428} 429 430struct is_power2 { 431 bool isValue(const APInt &C) { return C.isPowerOf2(); } 432}; 433/// Match an integer or vector power-of-2. 434/// For vectors, this includes constants with undefined elements. 435inline cst_pred_ty<is_power2> m_Power2() { 436 return cst_pred_ty<is_power2>(); 437} 438inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { 439 return V; 440} 441 442struct is_negated_power2 { 443 bool isValue(const APInt &C) { return (-C).isPowerOf2(); } 444}; 445/// Match a integer or vector negated power-of-2. 446/// For vectors, this includes constants with undefined elements. 447inline cst_pred_ty<is_negated_power2> m_NegatedPower2() { 448 return cst_pred_ty<is_negated_power2>(); 449} 450inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) { 451 return V; 452} 453 454struct is_power2_or_zero { 455 bool isValue(const APInt &C) { return !C || C.isPowerOf2(); } 456}; 457/// Match an integer or vector of 0 or power-of-2 values. 458/// For vectors, this includes constants with undefined elements. 459inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() { 460 return cst_pred_ty<is_power2_or_zero>(); 461} 462inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) { 463 return V; 464} 465 466struct is_sign_mask { 467 bool isValue(const APInt &C) { return C.isSignMask(); } 468}; 469/// Match an integer or vector with only the sign bit(s) set. 470/// For vectors, this includes constants with undefined elements. 471inline cst_pred_ty<is_sign_mask> m_SignMask() { 472 return cst_pred_ty<is_sign_mask>(); 473} 474 475struct is_lowbit_mask { 476 bool isValue(const APInt &C) { return C.isMask(); } 477}; 478/// Match an integer or vector with only the low bit(s) set. 479/// For vectors, this includes constants with undefined elements. 480inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() { 481 return cst_pred_ty<is_lowbit_mask>(); 482} 483 484struct icmp_pred_with_threshold { 485 ICmpInst::Predicate Pred; 486 const APInt *Thr; 487 bool isValue(const APInt &C) { 488 switch (Pred) { 489 case ICmpInst::Predicate::ICMP_EQ: 490 return C.eq(*Thr); 491 case ICmpInst::Predicate::ICMP_NE: 492 return C.ne(*Thr); 493 case ICmpInst::Predicate::ICMP_UGT: 494 return C.ugt(*Thr); 495 case ICmpInst::Predicate::ICMP_UGE: 496 return C.uge(*Thr); 497 case ICmpInst::Predicate::ICMP_ULT: 498 return C.ult(*Thr); 499 case ICmpInst::Predicate::ICMP_ULE: 500 return C.ule(*Thr); 501 case ICmpInst::Predicate::ICMP_SGT: 502 return C.sgt(*Thr); 503 case ICmpInst::Predicate::ICMP_SGE: 504 return C.sge(*Thr); 505 case ICmpInst::Predicate::ICMP_SLT: 506 return C.slt(*Thr); 507 case ICmpInst::Predicate::ICMP_SLE: 508 return C.sle(*Thr); 509 default: 510 llvm_unreachable("Unhandled ICmp predicate"); 511 } 512 } 513}; 514/// Match an integer or vector with every element comparing 'pred' (eg/ne/...) 515/// to Threshold. For vectors, this includes constants with undefined elements. 516inline cst_pred_ty<icmp_pred_with_threshold> 517m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold) { 518 cst_pred_ty<icmp_pred_with_threshold> P; 519 P.Pred = Predicate; 520 P.Thr = &Threshold; 521 return P; 522} 523 524struct is_nan { 525 bool isValue(const APFloat &C) { return C.isNaN(); } 526}; 527/// Match an arbitrary NaN constant. This includes quiet and signalling nans. 528/// For vectors, this includes constants with undefined elements. 529inline cstfp_pred_ty<is_nan> m_NaN() { 530 return cstfp_pred_ty<is_nan>(); 531} 532 533struct is_any_zero_fp { 534 bool isValue(const APFloat &C) { return C.isZero(); } 535}; 536/// Match a floating-point negative zero or positive zero. 537/// For vectors, this includes constants with undefined elements. 538inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() { 539 return cstfp_pred_ty<is_any_zero_fp>(); 540} 541 542struct is_pos_zero_fp { 543 bool isValue(const APFloat &C) { return C.isPosZero(); } 544}; 545/// Match a floating-point positive zero. 546/// For vectors, this includes constants with undefined elements. 547inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() { 548 return cstfp_pred_ty<is_pos_zero_fp>(); 549} 550 551struct is_neg_zero_fp { 552 bool isValue(const APFloat &C) { return C.isNegZero(); } 553}; 554/// Match a floating-point negative zero. 555/// For vectors, this includes constants with undefined elements. 556inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() { 557 return cstfp_pred_ty<is_neg_zero_fp>(); 558} 559 560/////////////////////////////////////////////////////////////////////////////// 561 562template <typename Class> struct bind_ty { 563 Class *&VR; 564 565 bind_ty(Class *&V) : VR(V) {} 566 567 template <typename ITy> bool match(ITy *V) { 568 if (auto *CV = dyn_cast<Class>(V)) { 569 VR = CV; 570 return true; 571 } 572 return false; 573 } 574}; 575 576/// Match a value, capturing it if we match. 577inline bind_ty<Value> m_Value(Value *&V) { return V; } 578inline bind_ty<const Value> m_Value(const Value *&V) { return V; } 579 580/// Match an instruction, capturing it if we match. 581inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; } 582/// Match a binary operator, capturing it if we match. 583inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; } 584/// Match a with overflow intrinsic, capturing it if we match. 585inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) { return I; } 586 587/// Match a ConstantInt, capturing the value if we match. 588inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; } 589 590/// Match a Constant, capturing the value if we match. 591inline bind_ty<Constant> m_Constant(Constant *&C) { return C; } 592 593/// Match a ConstantFP, capturing the value if we match. 594inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; } 595 596/// Match a basic block value, capturing it if we match. 597inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; } 598inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) { 599 return V; 600} 601 602/// Match a specified Value*. 603struct specificval_ty { 604 const Value *Val; 605 606 specificval_ty(const Value *V) : Val(V) {} 607 608 template <typename ITy> bool match(ITy *V) { return V == Val; } 609}; 610 611/// Match if we have a specific specified value. 612inline specificval_ty m_Specific(const Value *V) { return V; } 613 614/// Stores a reference to the Value *, not the Value * itself, 615/// thus can be used in commutative matchers. 616template <typename Class> struct deferredval_ty { 617 Class *const &Val; 618 619 deferredval_ty(Class *const &V) : Val(V) {} 620 621 template <typename ITy> bool match(ITy *const V) { return V == Val; } 622}; 623 624/// A commutative-friendly version of m_Specific(). 625inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; } 626inline deferredval_ty<const Value> m_Deferred(const Value *const &V) { 627 return V; 628} 629 630/// Match a specified floating point value or vector of all elements of 631/// that value. 632struct specific_fpval { 633 double Val; 634 635 specific_fpval(double V) : Val(V) {} 636 637 template <typename ITy> bool match(ITy *V) { 638 if (const auto *CFP = dyn_cast<ConstantFP>(V)) 639 return CFP->isExactlyValue(Val); 640 if (V->getType()->isVectorTy()) 641 if (const auto *C = dyn_cast<Constant>(V)) 642 if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue())) 643 return CFP->isExactlyValue(Val); 644 return false; 645 } 646}; 647 648/// Match a specific floating point value or vector with all elements 649/// equal to the value. 650inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); } 651 652/// Match a float 1.0 or vector with all elements equal to 1.0. 653inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); } 654 655struct bind_const_intval_ty { 656 uint64_t &VR; 657 658 bind_const_intval_ty(uint64_t &V) : VR(V) {} 659 660 template <typename ITy> bool match(ITy *V) { 661 if (const auto *CV = dyn_cast<ConstantInt>(V)) 662 if (CV->getValue().ule(UINT64_MAX)) { 663 VR = CV->getZExtValue(); 664 return true; 665 } 666 return false; 667 } 668}; 669 670/// Match a specified integer value or vector of all elements of that 671/// value. 672struct specific_intval { 673 APInt Val; 674 675 specific_intval(APInt V) : Val(std::move(V)) {} 676 677 template <typename ITy> bool match(ITy *V) { 678 const auto *CI = dyn_cast<ConstantInt>(V); 679 if (!CI && V->getType()->isVectorTy()) 680 if (const auto *C = dyn_cast<Constant>(V)) 681 CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()); 682 683 return CI && APInt::isSameValue(CI->getValue(), Val); 684 } 685}; 686 687/// Match a specific integer value or vector with all elements equal to 688/// the value. 689inline specific_intval m_SpecificInt(APInt V) { 690 return specific_intval(std::move(V)); 691} 692 693inline specific_intval m_SpecificInt(uint64_t V) { 694 return m_SpecificInt(APInt(64, V)); 695} 696 697/// Match a ConstantInt and bind to its value. This does not match 698/// ConstantInts wider than 64-bits. 699inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; } 700 701/// Match a specified basic block value. 702struct specific_bbval { 703 BasicBlock *Val; 704 705 specific_bbval(BasicBlock *Val) : Val(Val) {} 706 707 template <typename ITy> bool match(ITy *V) { 708 const auto *BB = dyn_cast<BasicBlock>(V); 709 return BB && BB == Val; 710 } 711}; 712 713/// Match a specific basic block value. 714inline specific_bbval m_SpecificBB(BasicBlock *BB) { 715 return specific_bbval(BB); 716} 717 718/// A commutative-friendly version of m_Specific(). 719inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) { 720 return BB; 721} 722inline deferredval_ty<const BasicBlock> 723m_Deferred(const BasicBlock *const &BB) { 724 return BB; 725} 726 727//===----------------------------------------------------------------------===// 728// Matcher for any binary operator. 729// 730template <typename LHS_t, typename RHS_t, bool Commutable = false> 731struct AnyBinaryOp_match { 732 LHS_t L; 733 RHS_t R; 734 735 // The evaluation order is always stable, regardless of Commutability. 736 // The LHS is always matched first. 737 AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 738 739 template <typename OpTy> bool match(OpTy *V) { 740 if (auto *I = dyn_cast<BinaryOperator>(V)) 741 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) || 742 (Commutable && L.match(I->getOperand(1)) && 743 R.match(I->getOperand(0))); 744 return false; 745 } 746}; 747 748template <typename LHS, typename RHS> 749inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) { 750 return AnyBinaryOp_match<LHS, RHS>(L, R); 751} 752 753//===----------------------------------------------------------------------===// 754// Matchers for specific binary operators. 755// 756 757template <typename LHS_t, typename RHS_t, unsigned Opcode, 758 bool Commutable = false> 759struct BinaryOp_match { 760 LHS_t L; 761 RHS_t R; 762 763 // The evaluation order is always stable, regardless of Commutability. 764 // The LHS is always matched first. 765 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 766 767 template <typename OpTy> bool match(OpTy *V) { 768 if (V->getValueID() == Value::InstructionVal + Opcode) { 769 auto *I = cast<BinaryOperator>(V); 770 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) || 771 (Commutable && L.match(I->getOperand(1)) && 772 R.match(I->getOperand(0))); 773 } 774 if (auto *CE = dyn_cast<ConstantExpr>(V)) 775 return CE->getOpcode() == Opcode && 776 ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) || 777 (Commutable && L.match(CE->getOperand(1)) && 778 R.match(CE->getOperand(0)))); 779 return false; 780 } 781}; 782 783template <typename LHS, typename RHS> 784inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L, 785 const RHS &R) { 786 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R); 787} 788 789template <typename LHS, typename RHS> 790inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L, 791 const RHS &R) { 792 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R); 793} 794 795template <typename LHS, typename RHS> 796inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L, 797 const RHS &R) { 798 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R); 799} 800 801template <typename LHS, typename RHS> 802inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L, 803 const RHS &R) { 804 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R); 805} 806 807template <typename Op_t> struct FNeg_match { 808 Op_t X; 809 810 FNeg_match(const Op_t &Op) : X(Op) {} 811 template <typename OpTy> bool match(OpTy *V) { 812 auto *FPMO = dyn_cast<FPMathOperator>(V); 813 if (!FPMO) return false; 814 815 if (FPMO->getOpcode() == Instruction::FNeg) 816 return X.match(FPMO->getOperand(0)); 817 818 if (FPMO->getOpcode() == Instruction::FSub) { 819 if (FPMO->hasNoSignedZeros()) { 820 // With 'nsz', any zero goes. 821 if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0))) 822 return false; 823 } else { 824 // Without 'nsz', we need fsub -0.0, X exactly. 825 if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0))) 826 return false; 827 } 828 829 return X.match(FPMO->getOperand(1)); 830 } 831 832 return false; 833 } 834}; 835 836/// Match 'fneg X' as 'fsub -0.0, X'. 837template <typename OpTy> 838inline FNeg_match<OpTy> 839m_FNeg(const OpTy &X) { 840 return FNeg_match<OpTy>(X); 841} 842 843/// Match 'fneg X' as 'fsub +-0.0, X'. 844template <typename RHS> 845inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub> 846m_FNegNSZ(const RHS &X) { 847 return m_FSub(m_AnyZeroFP(), X); 848} 849 850template <typename LHS, typename RHS> 851inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L, 852 const RHS &R) { 853 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R); 854} 855 856template <typename LHS, typename RHS> 857inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L, 858 const RHS &R) { 859 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R); 860} 861 862template <typename LHS, typename RHS> 863inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L, 864 const RHS &R) { 865 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R); 866} 867 868template <typename LHS, typename RHS> 869inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L, 870 const RHS &R) { 871 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R); 872} 873 874template <typename LHS, typename RHS> 875inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L, 876 const RHS &R) { 877 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R); 878} 879 880template <typename LHS, typename RHS> 881inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L, 882 const RHS &R) { 883 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R); 884} 885 886template <typename LHS, typename RHS> 887inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L, 888 const RHS &R) { 889 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R); 890} 891 892template <typename LHS, typename RHS> 893inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L, 894 const RHS &R) { 895 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R); 896} 897 898template <typename LHS, typename RHS> 899inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L, 900 const RHS &R) { 901 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R); 902} 903 904template <typename LHS, typename RHS> 905inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L, 906 const RHS &R) { 907 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R); 908} 909 910template <typename LHS, typename RHS> 911inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L, 912 const RHS &R) { 913 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R); 914} 915 916template <typename LHS, typename RHS> 917inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L, 918 const RHS &R) { 919 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R); 920} 921 922template <typename LHS, typename RHS> 923inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L, 924 const RHS &R) { 925 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R); 926} 927 928template <typename LHS, typename RHS> 929inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L, 930 const RHS &R) { 931 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R); 932} 933 934template <typename LHS_t, typename RHS_t, unsigned Opcode, 935 unsigned WrapFlags = 0> 936struct OverflowingBinaryOp_match { 937 LHS_t L; 938 RHS_t R; 939 940 OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) 941 : L(LHS), R(RHS) {} 942 943 template <typename OpTy> bool match(OpTy *V) { 944 if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) { 945 if (Op->getOpcode() != Opcode) 946 return false; 947 if (WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap && 948 !Op->hasNoUnsignedWrap()) 949 return false; 950 if (WrapFlags & OverflowingBinaryOperator::NoSignedWrap && 951 !Op->hasNoSignedWrap()) 952 return false; 953 return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1)); 954 } 955 return false; 956 } 957}; 958 959template <typename LHS, typename RHS> 960inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 961 OverflowingBinaryOperator::NoSignedWrap> 962m_NSWAdd(const LHS &L, const RHS &R) { 963 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 964 OverflowingBinaryOperator::NoSignedWrap>( 965 L, R); 966} 967template <typename LHS, typename RHS> 968inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 969 OverflowingBinaryOperator::NoSignedWrap> 970m_NSWSub(const LHS &L, const RHS &R) { 971 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 972 OverflowingBinaryOperator::NoSignedWrap>( 973 L, R); 974} 975template <typename LHS, typename RHS> 976inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 977 OverflowingBinaryOperator::NoSignedWrap> 978m_NSWMul(const LHS &L, const RHS &R) { 979 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 980 OverflowingBinaryOperator::NoSignedWrap>( 981 L, R); 982} 983template <typename LHS, typename RHS> 984inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 985 OverflowingBinaryOperator::NoSignedWrap> 986m_NSWShl(const LHS &L, const RHS &R) { 987 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 988 OverflowingBinaryOperator::NoSignedWrap>( 989 L, R); 990} 991 992template <typename LHS, typename RHS> 993inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 994 OverflowingBinaryOperator::NoUnsignedWrap> 995m_NUWAdd(const LHS &L, const RHS &R) { 996 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 997 OverflowingBinaryOperator::NoUnsignedWrap>( 998 L, R); 999} 1000template <typename LHS, typename RHS> 1001inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 1002 OverflowingBinaryOperator::NoUnsignedWrap> 1003m_NUWSub(const LHS &L, const RHS &R) { 1004 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 1005 OverflowingBinaryOperator::NoUnsignedWrap>( 1006 L, R); 1007} 1008template <typename LHS, typename RHS> 1009inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 1010 OverflowingBinaryOperator::NoUnsignedWrap> 1011m_NUWMul(const LHS &L, const RHS &R) { 1012 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 1013 OverflowingBinaryOperator::NoUnsignedWrap>( 1014 L, R); 1015} 1016template <typename LHS, typename RHS> 1017inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 1018 OverflowingBinaryOperator::NoUnsignedWrap> 1019m_NUWShl(const LHS &L, const RHS &R) { 1020 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 1021 OverflowingBinaryOperator::NoUnsignedWrap>( 1022 L, R); 1023} 1024 1025//===----------------------------------------------------------------------===// 1026// Class that matches a group of binary opcodes. 1027// 1028template <typename LHS_t, typename RHS_t, typename Predicate> 1029struct BinOpPred_match : Predicate { 1030 LHS_t L; 1031 RHS_t R; 1032 1033 BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 1034 1035 template <typename OpTy> bool match(OpTy *V) { 1036 if (auto *I = dyn_cast<Instruction>(V)) 1037 return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) && 1038 R.match(I->getOperand(1)); 1039 if (auto *CE = dyn_cast<ConstantExpr>(V)) 1040 return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) && 1041 R.match(CE->getOperand(1)); 1042 return false; 1043 } 1044}; 1045 1046struct is_shift_op { 1047 bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); } 1048}; 1049 1050struct is_right_shift_op { 1051 bool isOpType(unsigned Opcode) { 1052 return Opcode == Instruction::LShr || Opcode == Instruction::AShr; 1053 } 1054}; 1055 1056struct is_logical_shift_op { 1057 bool isOpType(unsigned Opcode) { 1058 return Opcode == Instruction::LShr || Opcode == Instruction::Shl; 1059 } 1060}; 1061 1062struct is_bitwiselogic_op { 1063 bool isOpType(unsigned Opcode) { 1064 return Instruction::isBitwiseLogicOp(Opcode); 1065 } 1066}; 1067 1068struct is_idiv_op { 1069 bool isOpType(unsigned Opcode) { 1070 return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv; 1071 } 1072}; 1073 1074struct is_irem_op { 1075 bool isOpType(unsigned Opcode) { 1076 return Opcode == Instruction::SRem || Opcode == Instruction::URem; 1077 } 1078}; 1079 1080/// Matches shift operations. 1081template <typename LHS, typename RHS> 1082inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L, 1083 const RHS &R) { 1084 return BinOpPred_match<LHS, RHS, is_shift_op>(L, R); 1085} 1086 1087/// Matches logical shift operations. 1088template <typename LHS, typename RHS> 1089inline BinOpPred_match<LHS, RHS, is_right_shift_op> m_Shr(const LHS &L, 1090 const RHS &R) { 1091 return BinOpPred_match<LHS, RHS, is_right_shift_op>(L, R); 1092} 1093 1094/// Matches logical shift operations. 1095template <typename LHS, typename RHS> 1096inline BinOpPred_match<LHS, RHS, is_logical_shift_op> 1097m_LogicalShift(const LHS &L, const RHS &R) { 1098 return BinOpPred_match<LHS, RHS, is_logical_shift_op>(L, R); 1099} 1100 1101/// Matches bitwise logic operations. 1102template <typename LHS, typename RHS> 1103inline BinOpPred_match<LHS, RHS, is_bitwiselogic_op> 1104m_BitwiseLogic(const LHS &L, const RHS &R) { 1105 return BinOpPred_match<LHS, RHS, is_bitwiselogic_op>(L, R); 1106} 1107 1108/// Matches integer division operations. 1109template <typename LHS, typename RHS> 1110inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L, 1111 const RHS &R) { 1112 return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R); 1113} 1114 1115/// Matches integer remainder operations. 1116template <typename LHS, typename RHS> 1117inline BinOpPred_match<LHS, RHS, is_irem_op> m_IRem(const LHS &L, 1118 const RHS &R) { 1119 return BinOpPred_match<LHS, RHS, is_irem_op>(L, R); 1120} 1121 1122//===----------------------------------------------------------------------===// 1123// Class that matches exact binary ops. 1124// 1125template <typename SubPattern_t> struct Exact_match { 1126 SubPattern_t SubPattern; 1127 1128 Exact_match(const SubPattern_t &SP) : SubPattern(SP) {} 1129 1130 template <typename OpTy> bool match(OpTy *V) { 1131 if (auto *PEO = dyn_cast<PossiblyExactOperator>(V)) 1132 return PEO->isExact() && SubPattern.match(V); 1133 return false; 1134 } 1135}; 1136 1137template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) { 1138 return SubPattern; 1139} 1140 1141//===----------------------------------------------------------------------===// 1142// Matchers for CmpInst classes 1143// 1144 1145template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy, 1146 bool Commutable = false> 1147struct CmpClass_match { 1148 PredicateTy &Predicate; 1149 LHS_t L; 1150 RHS_t R; 1151 1152 // The evaluation order is always stable, regardless of Commutability. 1153 // The LHS is always matched first. 1154 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS) 1155 : Predicate(Pred), L(LHS), R(RHS) {} 1156 1157 template <typename OpTy> bool match(OpTy *V) { 1158 if (auto *I = dyn_cast<Class>(V)) 1159 if ((L.match(I->getOperand(0)) && R.match(I->getOperand(1))) || 1160 (Commutable && L.match(I->getOperand(1)) && 1161 R.match(I->getOperand(0)))) { 1162 Predicate = I->getPredicate(); 1163 return true; 1164 } 1165 return false; 1166 } 1167}; 1168 1169template <typename LHS, typename RHS> 1170inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate> 1171m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 1172 return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R); 1173} 1174 1175template <typename LHS, typename RHS> 1176inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate> 1177m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 1178 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R); 1179} 1180 1181template <typename LHS, typename RHS> 1182inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate> 1183m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 1184 return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R); 1185} 1186 1187//===----------------------------------------------------------------------===// 1188// Matchers for instructions with a given opcode and number of operands. 1189// 1190 1191/// Matches instructions with Opcode and three operands. 1192template <typename T0, unsigned Opcode> struct OneOps_match { 1193 T0 Op1; 1194 1195 OneOps_match(const T0 &Op1) : Op1(Op1) {} 1196 1197 template <typename OpTy> bool match(OpTy *V) { 1198 if (V->getValueID() == Value::InstructionVal + Opcode) { 1199 auto *I = cast<Instruction>(V); 1200 return Op1.match(I->getOperand(0)); 1201 } 1202 return false; 1203 } 1204}; 1205 1206/// Matches instructions with Opcode and three operands. 1207template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match { 1208 T0 Op1; 1209 T1 Op2; 1210 1211 TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {} 1212 1213 template <typename OpTy> bool match(OpTy *V) { 1214 if (V->getValueID() == Value::InstructionVal + Opcode) { 1215 auto *I = cast<Instruction>(V); 1216 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)); 1217 } 1218 return false; 1219 } 1220}; 1221 1222/// Matches instructions with Opcode and three operands. 1223template <typename T0, typename T1, typename T2, unsigned Opcode> 1224struct ThreeOps_match { 1225 T0 Op1; 1226 T1 Op2; 1227 T2 Op3; 1228 1229 ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3) 1230 : Op1(Op1), Op2(Op2), Op3(Op3) {} 1231 1232 template <typename OpTy> bool match(OpTy *V) { 1233 if (V->getValueID() == Value::InstructionVal + Opcode) { 1234 auto *I = cast<Instruction>(V); 1235 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) && 1236 Op3.match(I->getOperand(2)); 1237 } 1238 return false; 1239 } 1240}; 1241 1242/// Matches SelectInst. 1243template <typename Cond, typename LHS, typename RHS> 1244inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select> 1245m_Select(const Cond &C, const LHS &L, const RHS &R) { 1246 return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R); 1247} 1248 1249/// This matches a select of two constants, e.g.: 1250/// m_SelectCst<-1, 0>(m_Value(V)) 1251template <int64_t L, int64_t R, typename Cond> 1252inline ThreeOps_match<Cond, constantint_match<L>, constantint_match<R>, 1253 Instruction::Select> 1254m_SelectCst(const Cond &C) { 1255 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>()); 1256} 1257 1258/// Matches FreezeInst. 1259template <typename OpTy> 1260inline OneOps_match<OpTy, Instruction::Freeze> m_Freeze(const OpTy &Op) { 1261 return OneOps_match<OpTy, Instruction::Freeze>(Op); 1262} 1263 1264/// Matches InsertElementInst. 1265template <typename Val_t, typename Elt_t, typename Idx_t> 1266inline ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement> 1267m_InsertElement(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) { 1268 return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>( 1269 Val, Elt, Idx); 1270} 1271 1272/// Matches ExtractElementInst. 1273template <typename Val_t, typename Idx_t> 1274inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement> 1275m_ExtractElement(const Val_t &Val, const Idx_t &Idx) { 1276 return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx); 1277} 1278 1279/// Matches ShuffleVectorInst. 1280template <typename V1_t, typename V2_t, typename Mask_t> 1281inline ThreeOps_match<V1_t, V2_t, Mask_t, Instruction::ShuffleVector> 1282m_ShuffleVector(const V1_t &v1, const V2_t &v2, const Mask_t &m) { 1283 return ThreeOps_match<V1_t, V2_t, Mask_t, Instruction::ShuffleVector>(v1, v2, 1284 m); 1285} 1286 1287/// Matches LoadInst. 1288template <typename OpTy> 1289inline OneOps_match<OpTy, Instruction::Load> m_Load(const OpTy &Op) { 1290 return OneOps_match<OpTy, Instruction::Load>(Op); 1291} 1292 1293/// Matches StoreInst. 1294template <typename ValueOpTy, typename PointerOpTy> 1295inline TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store> 1296m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) { 1297 return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp, 1298 PointerOp); 1299} 1300 1301//===----------------------------------------------------------------------===// 1302// Matchers for CastInst classes 1303// 1304 1305template <typename Op_t, unsigned Opcode> struct CastClass_match { 1306 Op_t Op; 1307 1308 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {} 1309 1310 template <typename OpTy> bool match(OpTy *V) { 1311 if (auto *O = dyn_cast<Operator>(V)) 1312 return O->getOpcode() == Opcode && Op.match(O->getOperand(0)); 1313 return false; 1314 } 1315}; 1316 1317/// Matches BitCast. 1318template <typename OpTy> 1319inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) { 1320 return CastClass_match<OpTy, Instruction::BitCast>(Op); 1321} 1322 1323/// Matches PtrToInt. 1324template <typename OpTy> 1325inline CastClass_match<OpTy, Instruction::PtrToInt> m_PtrToInt(const OpTy &Op) { 1326 return CastClass_match<OpTy, Instruction::PtrToInt>(Op); 1327} 1328 1329/// Matches Trunc. 1330template <typename OpTy> 1331inline CastClass_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) { 1332 return CastClass_match<OpTy, Instruction::Trunc>(Op); 1333} 1334 1335template <typename OpTy> 1336inline match_combine_or<CastClass_match<OpTy, Instruction::Trunc>, OpTy> 1337m_TruncOrSelf(const OpTy &Op) { 1338 return m_CombineOr(m_Trunc(Op), Op); 1339} 1340 1341/// Matches SExt. 1342template <typename OpTy> 1343inline CastClass_match<OpTy, Instruction::SExt> m_SExt(const OpTy &Op) { 1344 return CastClass_match<OpTy, Instruction::SExt>(Op); 1345} 1346 1347/// Matches ZExt. 1348template <typename OpTy> 1349inline CastClass_match<OpTy, Instruction::ZExt> m_ZExt(const OpTy &Op) { 1350 return CastClass_match<OpTy, Instruction::ZExt>(Op); 1351} 1352 1353template <typename OpTy> 1354inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, OpTy> 1355m_ZExtOrSelf(const OpTy &Op) { 1356 return m_CombineOr(m_ZExt(Op), Op); 1357} 1358 1359template <typename OpTy> 1360inline match_combine_or<CastClass_match<OpTy, Instruction::SExt>, OpTy> 1361m_SExtOrSelf(const OpTy &Op) { 1362 return m_CombineOr(m_SExt(Op), Op); 1363} 1364 1365template <typename OpTy> 1366inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, 1367 CastClass_match<OpTy, Instruction::SExt>> 1368m_ZExtOrSExt(const OpTy &Op) { 1369 return m_CombineOr(m_ZExt(Op), m_SExt(Op)); 1370} 1371 1372template <typename OpTy> 1373inline match_combine_or< 1374 match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, 1375 CastClass_match<OpTy, Instruction::SExt>>, 1376 OpTy> 1377m_ZExtOrSExtOrSelf(const OpTy &Op) { 1378 return m_CombineOr(m_ZExtOrSExt(Op), Op); 1379} 1380 1381/// Matches UIToFP. 1382template <typename OpTy> 1383inline CastClass_match<OpTy, Instruction::UIToFP> m_UIToFP(const OpTy &Op) { 1384 return CastClass_match<OpTy, Instruction::UIToFP>(Op); 1385} 1386 1387/// Matches SIToFP. 1388template <typename OpTy> 1389inline CastClass_match<OpTy, Instruction::SIToFP> m_SIToFP(const OpTy &Op) { 1390 return CastClass_match<OpTy, Instruction::SIToFP>(Op); 1391} 1392 1393/// Matches FPTrunc 1394template <typename OpTy> 1395inline CastClass_match<OpTy, Instruction::FPTrunc> m_FPTrunc(const OpTy &Op) { 1396 return CastClass_match<OpTy, Instruction::FPTrunc>(Op); 1397} 1398 1399/// Matches FPExt 1400template <typename OpTy> 1401inline CastClass_match<OpTy, Instruction::FPExt> m_FPExt(const OpTy &Op) { 1402 return CastClass_match<OpTy, Instruction::FPExt>(Op); 1403} 1404 1405//===----------------------------------------------------------------------===// 1406// Matchers for control flow. 1407// 1408 1409struct br_match { 1410 BasicBlock *&Succ; 1411 1412 br_match(BasicBlock *&Succ) : Succ(Succ) {} 1413 1414 template <typename OpTy> bool match(OpTy *V) { 1415 if (auto *BI = dyn_cast<BranchInst>(V)) 1416 if (BI->isUnconditional()) { 1417 Succ = BI->getSuccessor(0); 1418 return true; 1419 } 1420 return false; 1421 } 1422}; 1423 1424inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); } 1425 1426template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t> 1427struct brc_match { 1428 Cond_t Cond; 1429 TrueBlock_t T; 1430 FalseBlock_t F; 1431 1432 brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f) 1433 : Cond(C), T(t), F(f) {} 1434 1435 template <typename OpTy> bool match(OpTy *V) { 1436 if (auto *BI = dyn_cast<BranchInst>(V)) 1437 if (BI->isConditional() && Cond.match(BI->getCondition())) 1438 return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1)); 1439 return false; 1440 } 1441}; 1442 1443template <typename Cond_t> 1444inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>> 1445m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) { 1446 return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>( 1447 C, m_BasicBlock(T), m_BasicBlock(F)); 1448} 1449 1450template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t> 1451inline brc_match<Cond_t, TrueBlock_t, FalseBlock_t> 1452m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) { 1453 return brc_match<Cond_t, TrueBlock_t, FalseBlock_t>(C, T, F); 1454} 1455 1456//===----------------------------------------------------------------------===// 1457// Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y). 1458// 1459 1460template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t, 1461 bool Commutable = false> 1462struct MaxMin_match { 1463 LHS_t L; 1464 RHS_t R; 1465 1466 // The evaluation order is always stable, regardless of Commutability. 1467 // The LHS is always matched first. 1468 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 1469 1470 template <typename OpTy> bool match(OpTy *V) { 1471 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x". 1472 auto *SI = dyn_cast<SelectInst>(V); 1473 if (!SI) 1474 return false; 1475 auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition()); 1476 if (!Cmp) 1477 return false; 1478 // At this point we have a select conditioned on a comparison. Check that 1479 // it is the values returned by the select that are being compared. 1480 Value *TrueVal = SI->getTrueValue(); 1481 Value *FalseVal = SI->getFalseValue(); 1482 Value *LHS = Cmp->getOperand(0); 1483 Value *RHS = Cmp->getOperand(1); 1484 if ((TrueVal != LHS || FalseVal != RHS) && 1485 (TrueVal != RHS || FalseVal != LHS)) 1486 return false; 1487 typename CmpInst_t::Predicate Pred = 1488 LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate(); 1489 // Does "(x pred y) ? x : y" represent the desired max/min operation? 1490 if (!Pred_t::match(Pred)) 1491 return false; 1492 // It does! Bind the operands. 1493 return (L.match(LHS) && R.match(RHS)) || 1494 (Commutable && L.match(RHS) && R.match(LHS)); 1495 } 1496}; 1497 1498/// Helper class for identifying signed max predicates. 1499struct smax_pred_ty { 1500 static bool match(ICmpInst::Predicate Pred) { 1501 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE; 1502 } 1503}; 1504 1505/// Helper class for identifying signed min predicates. 1506struct smin_pred_ty { 1507 static bool match(ICmpInst::Predicate Pred) { 1508 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE; 1509 } 1510}; 1511 1512/// Helper class for identifying unsigned max predicates. 1513struct umax_pred_ty { 1514 static bool match(ICmpInst::Predicate Pred) { 1515 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE; 1516 } 1517}; 1518 1519/// Helper class for identifying unsigned min predicates. 1520struct umin_pred_ty { 1521 static bool match(ICmpInst::Predicate Pred) { 1522 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE; 1523 } 1524}; 1525 1526/// Helper class for identifying ordered max predicates. 1527struct ofmax_pred_ty { 1528 static bool match(FCmpInst::Predicate Pred) { 1529 return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE; 1530 } 1531}; 1532 1533/// Helper class for identifying ordered min predicates. 1534struct ofmin_pred_ty { 1535 static bool match(FCmpInst::Predicate Pred) { 1536 return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE; 1537 } 1538}; 1539 1540/// Helper class for identifying unordered max predicates. 1541struct ufmax_pred_ty { 1542 static bool match(FCmpInst::Predicate Pred) { 1543 return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE; 1544 } 1545}; 1546 1547/// Helper class for identifying unordered min predicates. 1548struct ufmin_pred_ty { 1549 static bool match(FCmpInst::Predicate Pred) { 1550 return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE; 1551 } 1552}; 1553 1554template <typename LHS, typename RHS> 1555inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L, 1556 const RHS &R) { 1557 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R); 1558} 1559 1560template <typename LHS, typename RHS> 1561inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L, 1562 const RHS &R) { 1563 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R); 1564} 1565 1566template <typename LHS, typename RHS> 1567inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L, 1568 const RHS &R) { 1569 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R); 1570} 1571 1572template <typename LHS, typename RHS> 1573inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L, 1574 const RHS &R) { 1575 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R); 1576} 1577 1578/// Match an 'ordered' floating point maximum function. 1579/// Floating point has one special value 'NaN'. Therefore, there is no total 1580/// order. However, if we can ignore the 'NaN' value (for example, because of a 1581/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum' 1582/// semantics. In the presence of 'NaN' we have to preserve the original 1583/// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate. 1584/// 1585/// max(L, R) iff L and R are not NaN 1586/// m_OrdFMax(L, R) = R iff L or R are NaN 1587template <typename LHS, typename RHS> 1588inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L, 1589 const RHS &R) { 1590 return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R); 1591} 1592 1593/// Match an 'ordered' floating point minimum function. 1594/// Floating point has one special value 'NaN'. Therefore, there is no total 1595/// order. However, if we can ignore the 'NaN' value (for example, because of a 1596/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum' 1597/// semantics. In the presence of 'NaN' we have to preserve the original 1598/// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate. 1599/// 1600/// min(L, R) iff L and R are not NaN 1601/// m_OrdFMin(L, R) = R iff L or R are NaN 1602template <typename LHS, typename RHS> 1603inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L, 1604 const RHS &R) { 1605 return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R); 1606} 1607 1608/// Match an 'unordered' floating point maximum function. 1609/// Floating point has one special value 'NaN'. Therefore, there is no total 1610/// order. However, if we can ignore the 'NaN' value (for example, because of a 1611/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum' 1612/// semantics. In the presence of 'NaN' we have to preserve the original 1613/// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate. 1614/// 1615/// max(L, R) iff L and R are not NaN 1616/// m_UnordFMax(L, R) = L iff L or R are NaN 1617template <typename LHS, typename RHS> 1618inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty> 1619m_UnordFMax(const LHS &L, const RHS &R) { 1620 return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R); 1621} 1622 1623/// Match an 'unordered' floating point minimum function. 1624/// Floating point has one special value 'NaN'. Therefore, there is no total 1625/// order. However, if we can ignore the 'NaN' value (for example, because of a 1626/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum' 1627/// semantics. In the presence of 'NaN' we have to preserve the original 1628/// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate. 1629/// 1630/// min(L, R) iff L and R are not NaN 1631/// m_UnordFMin(L, R) = L iff L or R are NaN 1632template <typename LHS, typename RHS> 1633inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty> 1634m_UnordFMin(const LHS &L, const RHS &R) { 1635 return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R); 1636} 1637 1638//===----------------------------------------------------------------------===// 1639// Matchers for overflow check patterns: e.g. (a + b) u< a 1640// 1641 1642template <typename LHS_t, typename RHS_t, typename Sum_t> 1643struct UAddWithOverflow_match { 1644 LHS_t L; 1645 RHS_t R; 1646 Sum_t S; 1647 1648 UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S) 1649 : L(L), R(R), S(S) {} 1650 1651 template <typename OpTy> bool match(OpTy *V) { 1652 Value *ICmpLHS, *ICmpRHS; 1653 ICmpInst::Predicate Pred; 1654 if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V)) 1655 return false; 1656 1657 Value *AddLHS, *AddRHS; 1658 auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS)); 1659 1660 // (a + b) u< a, (a + b) u< b 1661 if (Pred == ICmpInst::ICMP_ULT) 1662 if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS)) 1663 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS); 1664 1665 // a >u (a + b), b >u (a + b) 1666 if (Pred == ICmpInst::ICMP_UGT) 1667 if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS)) 1668 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS); 1669 1670 // Match special-case for increment-by-1. 1671 if (Pred == ICmpInst::ICMP_EQ) { 1672 // (a + 1) == 0 1673 // (1 + a) == 0 1674 if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) && 1675 (m_One().match(AddLHS) || m_One().match(AddRHS))) 1676 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS); 1677 // 0 == (a + 1) 1678 // 0 == (1 + a) 1679 if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) && 1680 (m_One().match(AddLHS) || m_One().match(AddRHS))) 1681 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS); 1682 } 1683 1684 return false; 1685 } 1686}; 1687 1688/// Match an icmp instruction checking for unsigned overflow on addition. 1689/// 1690/// S is matched to the addition whose result is being checked for overflow, and 1691/// L and R are matched to the LHS and RHS of S. 1692template <typename LHS_t, typename RHS_t, typename Sum_t> 1693UAddWithOverflow_match<LHS_t, RHS_t, Sum_t> 1694m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) { 1695 return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S); 1696} 1697 1698template <typename Opnd_t> struct Argument_match { 1699 unsigned OpI; 1700 Opnd_t Val; 1701 1702 Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {} 1703 1704 template <typename OpTy> bool match(OpTy *V) { 1705 // FIXME: Should likely be switched to use `CallBase`. 1706 if (const auto *CI = dyn_cast<CallInst>(V)) 1707 return Val.match(CI->getArgOperand(OpI)); 1708 return false; 1709 } 1710}; 1711 1712/// Match an argument. 1713template <unsigned OpI, typename Opnd_t> 1714inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) { 1715 return Argument_match<Opnd_t>(OpI, Op); 1716} 1717 1718/// Intrinsic matchers. 1719struct IntrinsicID_match { 1720 unsigned ID; 1721 1722 IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {} 1723 1724 template <typename OpTy> bool match(OpTy *V) { 1725 if (const auto *CI = dyn_cast<CallInst>(V)) 1726 if (const auto *F = CI->getCalledFunction()) 1727 return F->getIntrinsicID() == ID; 1728 return false; 1729 } 1730}; 1731 1732/// Intrinsic matches are combinations of ID matchers, and argument 1733/// matchers. Higher arity matcher are defined recursively in terms of and-ing 1734/// them with lower arity matchers. Here's some convenient typedefs for up to 1735/// several arguments, and more can be added as needed 1736template <typename T0 = void, typename T1 = void, typename T2 = void, 1737 typename T3 = void, typename T4 = void, typename T5 = void, 1738 typename T6 = void, typename T7 = void, typename T8 = void, 1739 typename T9 = void, typename T10 = void> 1740struct m_Intrinsic_Ty; 1741template <typename T0> struct m_Intrinsic_Ty<T0> { 1742 using Ty = match_combine_and<IntrinsicID_match, Argument_match<T0>>; 1743}; 1744template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> { 1745 using Ty = 1746 match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>>; 1747}; 1748template <typename T0, typename T1, typename T2> 1749struct m_Intrinsic_Ty<T0, T1, T2> { 1750 using Ty = 1751 match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty, 1752 Argument_match<T2>>; 1753}; 1754template <typename T0, typename T1, typename T2, typename T3> 1755struct m_Intrinsic_Ty<T0, T1, T2, T3> { 1756 using Ty = 1757 match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty, 1758 Argument_match<T3>>; 1759}; 1760 1761template <typename T0, typename T1, typename T2, typename T3, typename T4> 1762struct m_Intrinsic_Ty<T0, T1, T2, T3, T4> { 1763 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty, 1764 Argument_match<T4>>; 1765}; 1766 1767/// Match intrinsic calls like this: 1768/// m_Intrinsic<Intrinsic::fabs>(m_Value(X)) 1769template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() { 1770 return IntrinsicID_match(IntrID); 1771} 1772 1773template <Intrinsic::ID IntrID, typename T0> 1774inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) { 1775 return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0)); 1776} 1777 1778template <Intrinsic::ID IntrID, typename T0, typename T1> 1779inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0, 1780 const T1 &Op1) { 1781 return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1)); 1782} 1783 1784template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2> 1785inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty 1786m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) { 1787 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2)); 1788} 1789 1790template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2, 1791 typename T3> 1792inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty 1793m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) { 1794 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3)); 1795} 1796 1797template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2, 1798 typename T3, typename T4> 1799inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty 1800m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3, 1801 const T4 &Op4) { 1802 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3), 1803 m_Argument<4>(Op4)); 1804} 1805 1806// Helper intrinsic matching specializations. 1807template <typename Opnd0> 1808inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) { 1809 return m_Intrinsic<Intrinsic::bitreverse>(Op0); 1810} 1811 1812template <typename Opnd0> 1813inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) { 1814 return m_Intrinsic<Intrinsic::bswap>(Op0); 1815} 1816 1817template <typename Opnd0> 1818inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) { 1819 return m_Intrinsic<Intrinsic::fabs>(Op0); 1820} 1821 1822template <typename Opnd0> 1823inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) { 1824 return m_Intrinsic<Intrinsic::canonicalize>(Op0); 1825} 1826 1827template <typename Opnd0, typename Opnd1> 1828inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0, 1829 const Opnd1 &Op1) { 1830 return m_Intrinsic<Intrinsic::minnum>(Op0, Op1); 1831} 1832 1833template <typename Opnd0, typename Opnd1> 1834inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0, 1835 const Opnd1 &Op1) { 1836 return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1); 1837} 1838 1839//===----------------------------------------------------------------------===// 1840// Matchers for two-operands operators with the operators in either order 1841// 1842 1843/// Matches a BinaryOperator with LHS and RHS in either order. 1844template <typename LHS, typename RHS> 1845inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) { 1846 return AnyBinaryOp_match<LHS, RHS, true>(L, R); 1847} 1848 1849/// Matches an ICmp with a predicate over LHS and RHS in either order. 1850/// Does not swap the predicate. 1851template <typename LHS, typename RHS> 1852inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true> 1853m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 1854 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L, 1855 R); 1856} 1857 1858/// Matches a Add with LHS and RHS in either order. 1859template <typename LHS, typename RHS> 1860inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L, 1861 const RHS &R) { 1862 return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R); 1863} 1864 1865/// Matches a Mul with LHS and RHS in either order. 1866template <typename LHS, typename RHS> 1867inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L, 1868 const RHS &R) { 1869 return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R); 1870} 1871 1872/// Matches an And with LHS and RHS in either order. 1873template <typename LHS, typename RHS> 1874inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L, 1875 const RHS &R) { 1876 return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R); 1877} 1878 1879/// Matches an Or with LHS and RHS in either order. 1880template <typename LHS, typename RHS> 1881inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L, 1882 const RHS &R) { 1883 return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R); 1884} 1885 1886/// Matches an Xor with LHS and RHS in either order. 1887template <typename LHS, typename RHS> 1888inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L, 1889 const RHS &R) { 1890 return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R); 1891} 1892 1893/// Matches a 'Neg' as 'sub 0, V'. 1894template <typename ValTy> 1895inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub> 1896m_Neg(const ValTy &V) { 1897 return m_Sub(m_ZeroInt(), V); 1898} 1899 1900/// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'. 1901template <typename ValTy> 1902inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true> 1903m_Not(const ValTy &V) { 1904 return m_c_Xor(V, m_AllOnes()); 1905} 1906 1907/// Matches an SMin with LHS and RHS in either order. 1908template <typename LHS, typename RHS> 1909inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true> 1910m_c_SMin(const LHS &L, const RHS &R) { 1911 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R); 1912} 1913/// Matches an SMax with LHS and RHS in either order. 1914template <typename LHS, typename RHS> 1915inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true> 1916m_c_SMax(const LHS &L, const RHS &R) { 1917 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R); 1918} 1919/// Matches a UMin with LHS and RHS in either order. 1920template <typename LHS, typename RHS> 1921inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true> 1922m_c_UMin(const LHS &L, const RHS &R) { 1923 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R); 1924} 1925/// Matches a UMax with LHS and RHS in either order. 1926template <typename LHS, typename RHS> 1927inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true> 1928m_c_UMax(const LHS &L, const RHS &R) { 1929 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R); 1930} 1931 1932/// Matches FAdd with LHS and RHS in either order. 1933template <typename LHS, typename RHS> 1934inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true> 1935m_c_FAdd(const LHS &L, const RHS &R) { 1936 return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R); 1937} 1938 1939/// Matches FMul with LHS and RHS in either order. 1940template <typename LHS, typename RHS> 1941inline BinaryOp_match<LHS, RHS, Instruction::FMul, true> 1942m_c_FMul(const LHS &L, const RHS &R) { 1943 return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R); 1944} 1945 1946template <typename Opnd_t> struct Signum_match { 1947 Opnd_t Val; 1948 Signum_match(const Opnd_t &V) : Val(V) {} 1949 1950 template <typename OpTy> bool match(OpTy *V) { 1951 unsigned TypeSize = V->getType()->getScalarSizeInBits(); 1952 if (TypeSize == 0) 1953 return false; 1954 1955 unsigned ShiftWidth = TypeSize - 1; 1956 Value *OpL = nullptr, *OpR = nullptr; 1957 1958 // This is the representation of signum we match: 1959 // 1960 // signum(x) == (x >> 63) | (-x >>u 63) 1961 // 1962 // An i1 value is its own signum, so it's correct to match 1963 // 1964 // signum(x) == (x >> 0) | (-x >>u 0) 1965 // 1966 // for i1 values. 1967 1968 auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth)); 1969 auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth)); 1970 auto Signum = m_Or(LHS, RHS); 1971 1972 return Signum.match(V) && OpL == OpR && Val.match(OpL); 1973 } 1974}; 1975 1976/// Matches a signum pattern. 1977/// 1978/// signum(x) = 1979/// x > 0 -> 1 1980/// x == 0 -> 0 1981/// x < 0 -> -1 1982template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) { 1983 return Signum_match<Val_t>(V); 1984} 1985 1986template <int Ind, typename Opnd_t> struct ExtractValue_match { 1987 Opnd_t Val; 1988 ExtractValue_match(const Opnd_t &V) : Val(V) {} 1989 1990 template <typename OpTy> bool match(OpTy *V) { 1991 if (auto *I = dyn_cast<ExtractValueInst>(V)) 1992 return I->getNumIndices() == 1 && I->getIndices()[0] == Ind && 1993 Val.match(I->getAggregateOperand()); 1994 return false; 1995 } 1996}; 1997 1998/// Match a single index ExtractValue instruction. 1999/// For example m_ExtractValue<1>(...) 2000template <int Ind, typename Val_t> 2001inline ExtractValue_match<Ind, Val_t> m_ExtractValue(const Val_t &V) { 2002 return ExtractValue_match<Ind, Val_t>(V); 2003} 2004 2005} // end namespace PatternMatch 2006} // end namespace llvm 2007 2008#endif // LLVM_IR_PATTERNMATCH_H 2009