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