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/DataLayout.h" 36 #include "llvm/IR/InstrTypes.h" 37 #include "llvm/IR/Instruction.h" 38 #include "llvm/IR/Instructions.h" 39 #include "llvm/IR/IntrinsicInst.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 Pattern> bool match(ArrayRef<int> Mask, const Pattern &P) { 54 return const_cast<Pattern &>(P).match(Mask); 55 } 56 57 template <typename SubPattern_t> struct OneUse_match { 58 SubPattern_t SubPattern; 59 60 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {} 61 62 template <typename OpTy> bool match(OpTy *V) { 63 return V->hasOneUse() && SubPattern.match(V); 64 } 65 }; 66 67 template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) { 68 return SubPattern; 69 } 70 71 template <typename Class> struct class_match { 72 template <typename ITy> bool match(ITy *V) { return isa<Class>(V); } 73 }; 74 75 /// Match an arbitrary value and ignore it. 76 inline class_match<Value> m_Value() { return class_match<Value>(); } 77 78 /// Match an arbitrary unary operation and ignore it. 79 inline class_match<UnaryOperator> m_UnOp() { 80 return class_match<UnaryOperator>(); 81 } 82 83 /// Match an arbitrary binary operation and ignore it. 84 inline class_match<BinaryOperator> m_BinOp() { 85 return class_match<BinaryOperator>(); 86 } 87 88 /// Matches any compare instruction and ignore it. 89 inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); } 90 91 struct undef_match { 92 static bool check(const Value *V) { 93 if (isa<UndefValue>(V)) 94 return true; 95 96 const auto *CA = dyn_cast<ConstantAggregate>(V); 97 if (!CA) 98 return false; 99 100 SmallPtrSet<const ConstantAggregate *, 8> Seen; 101 SmallVector<const ConstantAggregate *, 8> Worklist; 102 103 // Either UndefValue, PoisonValue, or an aggregate that only contains 104 // these is accepted by matcher. 105 // CheckValue returns false if CA cannot satisfy this constraint. 106 auto CheckValue = [&](const ConstantAggregate *CA) { 107 for (const Value *Op : CA->operand_values()) { 108 if (isa<UndefValue>(Op)) 109 continue; 110 111 const auto *CA = dyn_cast<ConstantAggregate>(Op); 112 if (!CA) 113 return false; 114 if (Seen.insert(CA).second) 115 Worklist.emplace_back(CA); 116 } 117 118 return true; 119 }; 120 121 if (!CheckValue(CA)) 122 return false; 123 124 while (!Worklist.empty()) { 125 if (!CheckValue(Worklist.pop_back_val())) 126 return false; 127 } 128 return true; 129 } 130 template <typename ITy> bool match(ITy *V) { return check(V); } 131 }; 132 133 /// Match an arbitrary undef constant. This matches poison as well. 134 /// If this is an aggregate and contains a non-aggregate element that is 135 /// neither undef nor poison, the aggregate is not matched. 136 inline auto m_Undef() { return undef_match(); } 137 138 /// Match an arbitrary poison constant. 139 inline class_match<PoisonValue> m_Poison() { return class_match<PoisonValue>(); } 140 141 /// Match an arbitrary Constant and ignore it. 142 inline class_match<Constant> m_Constant() { return class_match<Constant>(); } 143 144 /// Match an arbitrary ConstantInt and ignore it. 145 inline class_match<ConstantInt> m_ConstantInt() { 146 return class_match<ConstantInt>(); 147 } 148 149 /// Match an arbitrary ConstantFP and ignore it. 150 inline class_match<ConstantFP> m_ConstantFP() { 151 return class_match<ConstantFP>(); 152 } 153 154 /// Match an arbitrary ConstantExpr and ignore it. 155 inline class_match<ConstantExpr> m_ConstantExpr() { 156 return class_match<ConstantExpr>(); 157 } 158 159 /// Match an arbitrary basic block value and ignore it. 160 inline class_match<BasicBlock> m_BasicBlock() { 161 return class_match<BasicBlock>(); 162 } 163 164 /// Inverting matcher 165 template <typename Ty> struct match_unless { 166 Ty M; 167 168 match_unless(const Ty &Matcher) : M(Matcher) {} 169 170 template <typename ITy> bool match(ITy *V) { return !M.match(V); } 171 }; 172 173 /// Match if the inner matcher does *NOT* match. 174 template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) { 175 return match_unless<Ty>(M); 176 } 177 178 /// Matching combinators 179 template <typename LTy, typename RTy> struct match_combine_or { 180 LTy L; 181 RTy R; 182 183 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {} 184 185 template <typename ITy> bool match(ITy *V) { 186 if (L.match(V)) 187 return true; 188 if (R.match(V)) 189 return true; 190 return false; 191 } 192 }; 193 194 template <typename LTy, typename RTy> struct match_combine_and { 195 LTy L; 196 RTy R; 197 198 match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {} 199 200 template <typename ITy> bool match(ITy *V) { 201 if (L.match(V)) 202 if (R.match(V)) 203 return true; 204 return false; 205 } 206 }; 207 208 /// Combine two pattern matchers matching L || R 209 template <typename LTy, typename RTy> 210 inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) { 211 return match_combine_or<LTy, RTy>(L, R); 212 } 213 214 /// Combine two pattern matchers matching L && R 215 template <typename LTy, typename RTy> 216 inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) { 217 return match_combine_and<LTy, RTy>(L, R); 218 } 219 220 struct apint_match { 221 const APInt *&Res; 222 bool AllowUndef; 223 224 apint_match(const APInt *&Res, bool AllowUndef) 225 : Res(Res), AllowUndef(AllowUndef) {} 226 227 template <typename ITy> bool match(ITy *V) { 228 if (auto *CI = dyn_cast<ConstantInt>(V)) { 229 Res = &CI->getValue(); 230 return true; 231 } 232 if (V->getType()->isVectorTy()) 233 if (const auto *C = dyn_cast<Constant>(V)) 234 if (auto *CI = dyn_cast_or_null<ConstantInt>( 235 C->getSplatValue(AllowUndef))) { 236 Res = &CI->getValue(); 237 return true; 238 } 239 return false; 240 } 241 }; 242 // Either constexpr if or renaming ConstantFP::getValueAPF to 243 // ConstantFP::getValue is needed to do it via single template 244 // function for both apint/apfloat. 245 struct apfloat_match { 246 const APFloat *&Res; 247 bool AllowUndef; 248 249 apfloat_match(const APFloat *&Res, bool AllowUndef) 250 : Res(Res), AllowUndef(AllowUndef) {} 251 252 template <typename ITy> bool match(ITy *V) { 253 if (auto *CI = dyn_cast<ConstantFP>(V)) { 254 Res = &CI->getValueAPF(); 255 return true; 256 } 257 if (V->getType()->isVectorTy()) 258 if (const auto *C = dyn_cast<Constant>(V)) 259 if (auto *CI = dyn_cast_or_null<ConstantFP>( 260 C->getSplatValue(AllowUndef))) { 261 Res = &CI->getValueAPF(); 262 return true; 263 } 264 return false; 265 } 266 }; 267 268 /// Match a ConstantInt or splatted ConstantVector, binding the 269 /// specified pointer to the contained APInt. 270 inline apint_match m_APInt(const APInt *&Res) { 271 // Forbid undefs by default to maintain previous behavior. 272 return apint_match(Res, /* AllowUndef */ false); 273 } 274 275 /// Match APInt while allowing undefs in splat vector constants. 276 inline apint_match m_APIntAllowUndef(const APInt *&Res) { 277 return apint_match(Res, /* AllowUndef */ true); 278 } 279 280 /// Match APInt while forbidding undefs in splat vector constants. 281 inline apint_match m_APIntForbidUndef(const APInt *&Res) { 282 return apint_match(Res, /* AllowUndef */ false); 283 } 284 285 /// Match a ConstantFP or splatted ConstantVector, binding the 286 /// specified pointer to the contained APFloat. 287 inline apfloat_match m_APFloat(const APFloat *&Res) { 288 // Forbid undefs by default to maintain previous behavior. 289 return apfloat_match(Res, /* AllowUndef */ false); 290 } 291 292 /// Match APFloat while allowing undefs in splat vector constants. 293 inline apfloat_match m_APFloatAllowUndef(const APFloat *&Res) { 294 return apfloat_match(Res, /* AllowUndef */ true); 295 } 296 297 /// Match APFloat while forbidding undefs in splat vector constants. 298 inline apfloat_match m_APFloatForbidUndef(const APFloat *&Res) { 299 return apfloat_match(Res, /* AllowUndef */ false); 300 } 301 302 template <int64_t Val> struct constantint_match { 303 template <typename ITy> bool match(ITy *V) { 304 if (const auto *CI = dyn_cast<ConstantInt>(V)) { 305 const APInt &CIV = CI->getValue(); 306 if (Val >= 0) 307 return CIV == static_cast<uint64_t>(Val); 308 // If Val is negative, and CI is shorter than it, truncate to the right 309 // number of bits. If it is larger, then we have to sign extend. Just 310 // compare their negated values. 311 return -CIV == -Val; 312 } 313 return false; 314 } 315 }; 316 317 /// Match a ConstantInt with a specific value. 318 template <int64_t Val> inline constantint_match<Val> m_ConstantInt() { 319 return constantint_match<Val>(); 320 } 321 322 /// This helper class is used to match constant scalars, vector splats, 323 /// and fixed width vectors that satisfy a specified predicate. 324 /// For fixed width vector constants, undefined elements are ignored. 325 template <typename Predicate, typename ConstantVal> 326 struct cstval_pred_ty : public Predicate { 327 template <typename ITy> bool match(ITy *V) { 328 if (const auto *CV = dyn_cast<ConstantVal>(V)) 329 return this->isValue(CV->getValue()); 330 if (const auto *VTy = dyn_cast<VectorType>(V->getType())) { 331 if (const auto *C = dyn_cast<Constant>(V)) { 332 if (const auto *CV = dyn_cast_or_null<ConstantVal>(C->getSplatValue())) 333 return this->isValue(CV->getValue()); 334 335 // Number of elements of a scalable vector unknown at compile time 336 auto *FVTy = dyn_cast<FixedVectorType>(VTy); 337 if (!FVTy) 338 return false; 339 340 // Non-splat vector constant: check each element for a match. 341 unsigned NumElts = FVTy->getNumElements(); 342 assert(NumElts != 0 && "Constant vector with no elements?"); 343 bool HasNonUndefElements = false; 344 for (unsigned i = 0; i != NumElts; ++i) { 345 Constant *Elt = C->getAggregateElement(i); 346 if (!Elt) 347 return false; 348 if (isa<UndefValue>(Elt)) 349 continue; 350 auto *CV = dyn_cast<ConstantVal>(Elt); 351 if (!CV || !this->isValue(CV->getValue())) 352 return false; 353 HasNonUndefElements = true; 354 } 355 return HasNonUndefElements; 356 } 357 } 358 return false; 359 } 360 }; 361 362 /// specialization of cstval_pred_ty for ConstantInt 363 template <typename Predicate> 364 using cst_pred_ty = cstval_pred_ty<Predicate, ConstantInt>; 365 366 /// specialization of cstval_pred_ty for ConstantFP 367 template <typename Predicate> 368 using cstfp_pred_ty = cstval_pred_ty<Predicate, ConstantFP>; 369 370 /// This helper class is used to match scalar and vector constants that 371 /// satisfy a specified predicate, and bind them to an APInt. 372 template <typename Predicate> struct api_pred_ty : public Predicate { 373 const APInt *&Res; 374 375 api_pred_ty(const APInt *&R) : Res(R) {} 376 377 template <typename ITy> bool match(ITy *V) { 378 if (const auto *CI = dyn_cast<ConstantInt>(V)) 379 if (this->isValue(CI->getValue())) { 380 Res = &CI->getValue(); 381 return true; 382 } 383 if (V->getType()->isVectorTy()) 384 if (const auto *C = dyn_cast<Constant>(V)) 385 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) 386 if (this->isValue(CI->getValue())) { 387 Res = &CI->getValue(); 388 return true; 389 } 390 391 return false; 392 } 393 }; 394 395 /// This helper class is used to match scalar and vector constants that 396 /// satisfy a specified predicate, and bind them to an APFloat. 397 /// Undefs are allowed in splat vector constants. 398 template <typename Predicate> struct apf_pred_ty : public Predicate { 399 const APFloat *&Res; 400 401 apf_pred_ty(const APFloat *&R) : Res(R) {} 402 403 template <typename ITy> bool match(ITy *V) { 404 if (const auto *CI = dyn_cast<ConstantFP>(V)) 405 if (this->isValue(CI->getValue())) { 406 Res = &CI->getValue(); 407 return true; 408 } 409 if (V->getType()->isVectorTy()) 410 if (const auto *C = dyn_cast<Constant>(V)) 411 if (auto *CI = dyn_cast_or_null<ConstantFP>( 412 C->getSplatValue(/* AllowUndef */ true))) 413 if (this->isValue(CI->getValue())) { 414 Res = &CI->getValue(); 415 return true; 416 } 417 418 return false; 419 } 420 }; 421 422 /////////////////////////////////////////////////////////////////////////////// 423 // 424 // Encapsulate constant value queries for use in templated predicate matchers. 425 // This allows checking if constants match using compound predicates and works 426 // with vector constants, possibly with relaxed constraints. For example, ignore 427 // undef values. 428 // 429 /////////////////////////////////////////////////////////////////////////////// 430 431 struct is_any_apint { 432 bool isValue(const APInt &C) { return true; } 433 }; 434 /// Match an integer or vector with any integral constant. 435 /// For vectors, this includes constants with undefined elements. 436 inline cst_pred_ty<is_any_apint> m_AnyIntegralConstant() { 437 return cst_pred_ty<is_any_apint>(); 438 } 439 440 struct is_all_ones { 441 bool isValue(const APInt &C) { return C.isAllOnes(); } 442 }; 443 /// Match an integer or vector with all bits set. 444 /// For vectors, this includes constants with undefined elements. 445 inline cst_pred_ty<is_all_ones> m_AllOnes() { 446 return cst_pred_ty<is_all_ones>(); 447 } 448 449 struct is_maxsignedvalue { 450 bool isValue(const APInt &C) { return C.isMaxSignedValue(); } 451 }; 452 /// Match an integer or vector with values having all bits except for the high 453 /// bit set (0x7f...). 454 /// For vectors, this includes constants with undefined elements. 455 inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() { 456 return cst_pred_ty<is_maxsignedvalue>(); 457 } 458 inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) { 459 return V; 460 } 461 462 struct is_negative { 463 bool isValue(const APInt &C) { return C.isNegative(); } 464 }; 465 /// Match an integer or vector of negative values. 466 /// For vectors, this includes constants with undefined elements. 467 inline cst_pred_ty<is_negative> m_Negative() { 468 return cst_pred_ty<is_negative>(); 469 } 470 inline api_pred_ty<is_negative> m_Negative(const APInt *&V) { 471 return V; 472 } 473 474 struct is_nonnegative { 475 bool isValue(const APInt &C) { return C.isNonNegative(); } 476 }; 477 /// Match an integer or vector of non-negative values. 478 /// For vectors, this includes constants with undefined elements. 479 inline cst_pred_ty<is_nonnegative> m_NonNegative() { 480 return cst_pred_ty<is_nonnegative>(); 481 } 482 inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) { 483 return V; 484 } 485 486 struct is_strictlypositive { 487 bool isValue(const APInt &C) { return C.isStrictlyPositive(); } 488 }; 489 /// Match an integer or vector of strictly positive values. 490 /// For vectors, this includes constants with undefined elements. 491 inline cst_pred_ty<is_strictlypositive> m_StrictlyPositive() { 492 return cst_pred_ty<is_strictlypositive>(); 493 } 494 inline api_pred_ty<is_strictlypositive> m_StrictlyPositive(const APInt *&V) { 495 return V; 496 } 497 498 struct is_nonpositive { 499 bool isValue(const APInt &C) { return C.isNonPositive(); } 500 }; 501 /// Match an integer or vector of non-positive values. 502 /// For vectors, this includes constants with undefined elements. 503 inline cst_pred_ty<is_nonpositive> m_NonPositive() { 504 return cst_pred_ty<is_nonpositive>(); 505 } 506 inline api_pred_ty<is_nonpositive> m_NonPositive(const APInt *&V) { return V; } 507 508 struct is_one { 509 bool isValue(const APInt &C) { return C.isOne(); } 510 }; 511 /// Match an integer 1 or a vector with all elements equal to 1. 512 /// For vectors, this includes constants with undefined elements. 513 inline cst_pred_ty<is_one> m_One() { 514 return cst_pred_ty<is_one>(); 515 } 516 517 struct is_zero_int { 518 bool isValue(const APInt &C) { return C.isZero(); } 519 }; 520 /// Match an integer 0 or a vector with all elements equal to 0. 521 /// For vectors, this includes constants with undefined elements. 522 inline cst_pred_ty<is_zero_int> m_ZeroInt() { 523 return cst_pred_ty<is_zero_int>(); 524 } 525 526 struct is_zero { 527 template <typename ITy> bool match(ITy *V) { 528 auto *C = dyn_cast<Constant>(V); 529 // FIXME: this should be able to do something for scalable vectors 530 return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C)); 531 } 532 }; 533 /// Match any null constant or a vector with all elements equal to 0. 534 /// For vectors, this includes constants with undefined elements. 535 inline is_zero m_Zero() { 536 return is_zero(); 537 } 538 539 struct is_power2 { 540 bool isValue(const APInt &C) { return C.isPowerOf2(); } 541 }; 542 /// Match an integer or vector power-of-2. 543 /// For vectors, this includes constants with undefined elements. 544 inline cst_pred_ty<is_power2> m_Power2() { 545 return cst_pred_ty<is_power2>(); 546 } 547 inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { 548 return V; 549 } 550 551 struct is_negated_power2 { 552 bool isValue(const APInt &C) { return C.isNegatedPowerOf2(); } 553 }; 554 /// Match a integer or vector negated power-of-2. 555 /// For vectors, this includes constants with undefined elements. 556 inline cst_pred_ty<is_negated_power2> m_NegatedPower2() { 557 return cst_pred_ty<is_negated_power2>(); 558 } 559 inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) { 560 return V; 561 } 562 563 struct is_power2_or_zero { 564 bool isValue(const APInt &C) { return !C || C.isPowerOf2(); } 565 }; 566 /// Match an integer or vector of 0 or power-of-2 values. 567 /// For vectors, this includes constants with undefined elements. 568 inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() { 569 return cst_pred_ty<is_power2_or_zero>(); 570 } 571 inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) { 572 return V; 573 } 574 575 struct is_sign_mask { 576 bool isValue(const APInt &C) { return C.isSignMask(); } 577 }; 578 /// Match an integer or vector with only the sign bit(s) set. 579 /// For vectors, this includes constants with undefined elements. 580 inline cst_pred_ty<is_sign_mask> m_SignMask() { 581 return cst_pred_ty<is_sign_mask>(); 582 } 583 584 struct is_lowbit_mask { 585 bool isValue(const APInt &C) { return C.isMask(); } 586 }; 587 /// Match an integer or vector with only the low bit(s) set. 588 /// For vectors, this includes constants with undefined elements. 589 inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() { 590 return cst_pred_ty<is_lowbit_mask>(); 591 } 592 inline api_pred_ty<is_lowbit_mask> m_LowBitMask(const APInt *&V) { 593 return V; 594 } 595 596 struct icmp_pred_with_threshold { 597 ICmpInst::Predicate Pred; 598 const APInt *Thr; 599 bool isValue(const APInt &C) { return ICmpInst::compare(C, *Thr, Pred); } 600 }; 601 /// Match an integer or vector with every element comparing 'pred' (eg/ne/...) 602 /// to Threshold. For vectors, this includes constants with undefined elements. 603 inline cst_pred_ty<icmp_pred_with_threshold> 604 m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold) { 605 cst_pred_ty<icmp_pred_with_threshold> P; 606 P.Pred = Predicate; 607 P.Thr = &Threshold; 608 return P; 609 } 610 611 struct is_nan { 612 bool isValue(const APFloat &C) { return C.isNaN(); } 613 }; 614 /// Match an arbitrary NaN constant. This includes quiet and signalling nans. 615 /// For vectors, this includes constants with undefined elements. 616 inline cstfp_pred_ty<is_nan> m_NaN() { 617 return cstfp_pred_ty<is_nan>(); 618 } 619 620 struct is_nonnan { 621 bool isValue(const APFloat &C) { return !C.isNaN(); } 622 }; 623 /// Match a non-NaN FP constant. 624 /// For vectors, this includes constants with undefined elements. 625 inline cstfp_pred_ty<is_nonnan> m_NonNaN() { 626 return cstfp_pred_ty<is_nonnan>(); 627 } 628 629 struct is_inf { 630 bool isValue(const APFloat &C) { return C.isInfinity(); } 631 }; 632 /// Match a positive or negative infinity FP constant. 633 /// For vectors, this includes constants with undefined elements. 634 inline cstfp_pred_ty<is_inf> m_Inf() { 635 return cstfp_pred_ty<is_inf>(); 636 } 637 638 struct is_noninf { 639 bool isValue(const APFloat &C) { return !C.isInfinity(); } 640 }; 641 /// Match a non-infinity FP constant, i.e. finite or NaN. 642 /// For vectors, this includes constants with undefined elements. 643 inline cstfp_pred_ty<is_noninf> m_NonInf() { 644 return cstfp_pred_ty<is_noninf>(); 645 } 646 647 struct is_finite { 648 bool isValue(const APFloat &C) { return C.isFinite(); } 649 }; 650 /// Match a finite FP constant, i.e. not infinity or NaN. 651 /// For vectors, this includes constants with undefined elements. 652 inline cstfp_pred_ty<is_finite> m_Finite() { 653 return cstfp_pred_ty<is_finite>(); 654 } 655 inline apf_pred_ty<is_finite> m_Finite(const APFloat *&V) { return V; } 656 657 struct is_finitenonzero { 658 bool isValue(const APFloat &C) { return C.isFiniteNonZero(); } 659 }; 660 /// Match a finite non-zero FP constant. 661 /// For vectors, this includes constants with undefined elements. 662 inline cstfp_pred_ty<is_finitenonzero> m_FiniteNonZero() { 663 return cstfp_pred_ty<is_finitenonzero>(); 664 } 665 inline apf_pred_ty<is_finitenonzero> m_FiniteNonZero(const APFloat *&V) { 666 return V; 667 } 668 669 struct is_any_zero_fp { 670 bool isValue(const APFloat &C) { return C.isZero(); } 671 }; 672 /// Match a floating-point negative zero or positive zero. 673 /// For vectors, this includes constants with undefined elements. 674 inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() { 675 return cstfp_pred_ty<is_any_zero_fp>(); 676 } 677 678 struct is_pos_zero_fp { 679 bool isValue(const APFloat &C) { return C.isPosZero(); } 680 }; 681 /// Match a floating-point positive zero. 682 /// For vectors, this includes constants with undefined elements. 683 inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() { 684 return cstfp_pred_ty<is_pos_zero_fp>(); 685 } 686 687 struct is_neg_zero_fp { 688 bool isValue(const APFloat &C) { return C.isNegZero(); } 689 }; 690 /// Match a floating-point negative zero. 691 /// For vectors, this includes constants with undefined elements. 692 inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() { 693 return cstfp_pred_ty<is_neg_zero_fp>(); 694 } 695 696 struct is_non_zero_fp { 697 bool isValue(const APFloat &C) { return C.isNonZero(); } 698 }; 699 /// Match a floating-point non-zero. 700 /// For vectors, this includes constants with undefined elements. 701 inline cstfp_pred_ty<is_non_zero_fp> m_NonZeroFP() { 702 return cstfp_pred_ty<is_non_zero_fp>(); 703 } 704 705 /////////////////////////////////////////////////////////////////////////////// 706 707 template <typename Class> struct bind_ty { 708 Class *&VR; 709 710 bind_ty(Class *&V) : VR(V) {} 711 712 template <typename ITy> bool match(ITy *V) { 713 if (auto *CV = dyn_cast<Class>(V)) { 714 VR = CV; 715 return true; 716 } 717 return false; 718 } 719 }; 720 721 /// Match a value, capturing it if we match. 722 inline bind_ty<Value> m_Value(Value *&V) { return V; } 723 inline bind_ty<const Value> m_Value(const Value *&V) { return V; } 724 725 /// Match an instruction, capturing it if we match. 726 inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; } 727 /// Match a unary operator, capturing it if we match. 728 inline bind_ty<UnaryOperator> m_UnOp(UnaryOperator *&I) { return I; } 729 /// Match a binary operator, capturing it if we match. 730 inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; } 731 /// Match a with overflow intrinsic, capturing it if we match. 732 inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) { return I; } 733 inline bind_ty<const WithOverflowInst> 734 m_WithOverflowInst(const WithOverflowInst *&I) { 735 return I; 736 } 737 738 /// Match a Constant, capturing the value if we match. 739 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; } 740 741 /// Match a ConstantInt, capturing the value if we match. 742 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; } 743 744 /// Match a ConstantFP, capturing the value if we match. 745 inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; } 746 747 /// Match a ConstantExpr, capturing the value if we match. 748 inline bind_ty<ConstantExpr> m_ConstantExpr(ConstantExpr *&C) { return C; } 749 750 /// Match a basic block value, capturing it if we match. 751 inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; } 752 inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) { 753 return V; 754 } 755 756 /// Match an arbitrary immediate Constant and ignore it. 757 inline match_combine_and<class_match<Constant>, 758 match_unless<class_match<ConstantExpr>>> 759 m_ImmConstant() { 760 return m_CombineAnd(m_Constant(), m_Unless(m_ConstantExpr())); 761 } 762 763 /// Match an immediate Constant, capturing the value if we match. 764 inline match_combine_and<bind_ty<Constant>, 765 match_unless<class_match<ConstantExpr>>> 766 m_ImmConstant(Constant *&C) { 767 return m_CombineAnd(m_Constant(C), m_Unless(m_ConstantExpr())); 768 } 769 770 /// Match a specified Value*. 771 struct specificval_ty { 772 const Value *Val; 773 774 specificval_ty(const Value *V) : Val(V) {} 775 776 template <typename ITy> bool match(ITy *V) { return V == Val; } 777 }; 778 779 /// Match if we have a specific specified value. 780 inline specificval_ty m_Specific(const Value *V) { return V; } 781 782 /// Stores a reference to the Value *, not the Value * itself, 783 /// thus can be used in commutative matchers. 784 template <typename Class> struct deferredval_ty { 785 Class *const &Val; 786 787 deferredval_ty(Class *const &V) : Val(V) {} 788 789 template <typename ITy> bool match(ITy *const V) { return V == Val; } 790 }; 791 792 /// Like m_Specific(), but works if the specific value to match is determined 793 /// as part of the same match() expression. For example: 794 /// m_Add(m_Value(X), m_Specific(X)) is incorrect, because m_Specific() will 795 /// bind X before the pattern match starts. 796 /// m_Add(m_Value(X), m_Deferred(X)) is correct, and will check against 797 /// whichever value m_Value(X) populated. 798 inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; } 799 inline deferredval_ty<const Value> m_Deferred(const Value *const &V) { 800 return V; 801 } 802 803 /// Match a specified floating point value or vector of all elements of 804 /// that value. 805 struct specific_fpval { 806 double Val; 807 808 specific_fpval(double V) : Val(V) {} 809 810 template <typename ITy> bool match(ITy *V) { 811 if (const auto *CFP = dyn_cast<ConstantFP>(V)) 812 return CFP->isExactlyValue(Val); 813 if (V->getType()->isVectorTy()) 814 if (const auto *C = dyn_cast<Constant>(V)) 815 if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue())) 816 return CFP->isExactlyValue(Val); 817 return false; 818 } 819 }; 820 821 /// Match a specific floating point value or vector with all elements 822 /// equal to the value. 823 inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); } 824 825 /// Match a float 1.0 or vector with all elements equal to 1.0. 826 inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); } 827 828 struct bind_const_intval_ty { 829 uint64_t &VR; 830 831 bind_const_intval_ty(uint64_t &V) : VR(V) {} 832 833 template <typename ITy> bool match(ITy *V) { 834 if (const auto *CV = dyn_cast<ConstantInt>(V)) 835 if (CV->getValue().ule(UINT64_MAX)) { 836 VR = CV->getZExtValue(); 837 return true; 838 } 839 return false; 840 } 841 }; 842 843 /// Match a specified integer value or vector of all elements of that 844 /// value. 845 template <bool AllowUndefs> 846 struct specific_intval { 847 APInt Val; 848 849 specific_intval(APInt V) : Val(std::move(V)) {} 850 851 template <typename ITy> bool match(ITy *V) { 852 const auto *CI = dyn_cast<ConstantInt>(V); 853 if (!CI && V->getType()->isVectorTy()) 854 if (const auto *C = dyn_cast<Constant>(V)) 855 CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue(AllowUndefs)); 856 857 return CI && APInt::isSameValue(CI->getValue(), Val); 858 } 859 }; 860 861 /// Match a specific integer value or vector with all elements equal to 862 /// the value. 863 inline specific_intval<false> m_SpecificInt(APInt V) { 864 return specific_intval<false>(std::move(V)); 865 } 866 867 inline specific_intval<false> m_SpecificInt(uint64_t V) { 868 return m_SpecificInt(APInt(64, V)); 869 } 870 871 inline specific_intval<true> m_SpecificIntAllowUndef(APInt V) { 872 return specific_intval<true>(std::move(V)); 873 } 874 875 inline specific_intval<true> m_SpecificIntAllowUndef(uint64_t V) { 876 return m_SpecificIntAllowUndef(APInt(64, V)); 877 } 878 879 /// Match a ConstantInt and bind to its value. This does not match 880 /// ConstantInts wider than 64-bits. 881 inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; } 882 883 /// Match a specified basic block value. 884 struct specific_bbval { 885 BasicBlock *Val; 886 887 specific_bbval(BasicBlock *Val) : Val(Val) {} 888 889 template <typename ITy> bool match(ITy *V) { 890 const auto *BB = dyn_cast<BasicBlock>(V); 891 return BB && BB == Val; 892 } 893 }; 894 895 /// Match a specific basic block value. 896 inline specific_bbval m_SpecificBB(BasicBlock *BB) { 897 return specific_bbval(BB); 898 } 899 900 /// A commutative-friendly version of m_Specific(). 901 inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) { 902 return BB; 903 } 904 inline deferredval_ty<const BasicBlock> 905 m_Deferred(const BasicBlock *const &BB) { 906 return BB; 907 } 908 909 //===----------------------------------------------------------------------===// 910 // Matcher for any binary operator. 911 // 912 template <typename LHS_t, typename RHS_t, bool Commutable = false> 913 struct AnyBinaryOp_match { 914 LHS_t L; 915 RHS_t R; 916 917 // The evaluation order is always stable, regardless of Commutability. 918 // The LHS is always matched first. 919 AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 920 921 template <typename OpTy> bool match(OpTy *V) { 922 if (auto *I = dyn_cast<BinaryOperator>(V)) 923 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) || 924 (Commutable && L.match(I->getOperand(1)) && 925 R.match(I->getOperand(0))); 926 return false; 927 } 928 }; 929 930 template <typename LHS, typename RHS> 931 inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) { 932 return AnyBinaryOp_match<LHS, RHS>(L, R); 933 } 934 935 //===----------------------------------------------------------------------===// 936 // Matcher for any unary operator. 937 // TODO fuse unary, binary matcher into n-ary matcher 938 // 939 template <typename OP_t> struct AnyUnaryOp_match { 940 OP_t X; 941 942 AnyUnaryOp_match(const OP_t &X) : X(X) {} 943 944 template <typename OpTy> bool match(OpTy *V) { 945 if (auto *I = dyn_cast<UnaryOperator>(V)) 946 return X.match(I->getOperand(0)); 947 return false; 948 } 949 }; 950 951 template <typename OP_t> inline AnyUnaryOp_match<OP_t> m_UnOp(const OP_t &X) { 952 return AnyUnaryOp_match<OP_t>(X); 953 } 954 955 //===----------------------------------------------------------------------===// 956 // Matchers for specific binary operators. 957 // 958 959 template <typename LHS_t, typename RHS_t, unsigned Opcode, 960 bool Commutable = false> 961 struct BinaryOp_match { 962 LHS_t L; 963 RHS_t R; 964 965 // The evaluation order is always stable, regardless of Commutability. 966 // The LHS is always matched first. 967 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 968 969 template <typename OpTy> inline bool match(unsigned Opc, OpTy *V) { 970 if (V->getValueID() == Value::InstructionVal + Opc) { 971 auto *I = cast<BinaryOperator>(V); 972 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) || 973 (Commutable && L.match(I->getOperand(1)) && 974 R.match(I->getOperand(0))); 975 } 976 if (auto *CE = dyn_cast<ConstantExpr>(V)) 977 return CE->getOpcode() == Opc && 978 ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) || 979 (Commutable && L.match(CE->getOperand(1)) && 980 R.match(CE->getOperand(0)))); 981 return false; 982 } 983 984 template <typename OpTy> bool match(OpTy *V) { return match(Opcode, V); } 985 }; 986 987 template <typename LHS, typename RHS> 988 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L, 989 const RHS &R) { 990 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R); 991 } 992 993 template <typename LHS, typename RHS> 994 inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L, 995 const RHS &R) { 996 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R); 997 } 998 999 template <typename LHS, typename RHS> 1000 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L, 1001 const RHS &R) { 1002 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R); 1003 } 1004 1005 template <typename LHS, typename RHS> 1006 inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L, 1007 const RHS &R) { 1008 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R); 1009 } 1010 1011 template <typename Op_t> struct FNeg_match { 1012 Op_t X; 1013 1014 FNeg_match(const Op_t &Op) : X(Op) {} 1015 template <typename OpTy> bool match(OpTy *V) { 1016 auto *FPMO = dyn_cast<FPMathOperator>(V); 1017 if (!FPMO) return false; 1018 1019 if (FPMO->getOpcode() == Instruction::FNeg) 1020 return X.match(FPMO->getOperand(0)); 1021 1022 if (FPMO->getOpcode() == Instruction::FSub) { 1023 if (FPMO->hasNoSignedZeros()) { 1024 // With 'nsz', any zero goes. 1025 if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0))) 1026 return false; 1027 } else { 1028 // Without 'nsz', we need fsub -0.0, X exactly. 1029 if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0))) 1030 return false; 1031 } 1032 1033 return X.match(FPMO->getOperand(1)); 1034 } 1035 1036 return false; 1037 } 1038 }; 1039 1040 /// Match 'fneg X' as 'fsub -0.0, X'. 1041 template <typename OpTy> 1042 inline FNeg_match<OpTy> 1043 m_FNeg(const OpTy &X) { 1044 return FNeg_match<OpTy>(X); 1045 } 1046 1047 /// Match 'fneg X' as 'fsub +-0.0, X'. 1048 template <typename RHS> 1049 inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub> 1050 m_FNegNSZ(const RHS &X) { 1051 return m_FSub(m_AnyZeroFP(), X); 1052 } 1053 1054 template <typename LHS, typename RHS> 1055 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L, 1056 const RHS &R) { 1057 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R); 1058 } 1059 1060 template <typename LHS, typename RHS> 1061 inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L, 1062 const RHS &R) { 1063 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R); 1064 } 1065 1066 template <typename LHS, typename RHS> 1067 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L, 1068 const RHS &R) { 1069 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R); 1070 } 1071 1072 template <typename LHS, typename RHS> 1073 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L, 1074 const RHS &R) { 1075 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R); 1076 } 1077 1078 template <typename LHS, typename RHS> 1079 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L, 1080 const RHS &R) { 1081 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R); 1082 } 1083 1084 template <typename LHS, typename RHS> 1085 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L, 1086 const RHS &R) { 1087 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R); 1088 } 1089 1090 template <typename LHS, typename RHS> 1091 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L, 1092 const RHS &R) { 1093 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R); 1094 } 1095 1096 template <typename LHS, typename RHS> 1097 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L, 1098 const RHS &R) { 1099 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R); 1100 } 1101 1102 template <typename LHS, typename RHS> 1103 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L, 1104 const RHS &R) { 1105 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R); 1106 } 1107 1108 template <typename LHS, typename RHS> 1109 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L, 1110 const RHS &R) { 1111 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R); 1112 } 1113 1114 template <typename LHS, typename RHS> 1115 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L, 1116 const RHS &R) { 1117 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R); 1118 } 1119 1120 template <typename LHS, typename RHS> 1121 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L, 1122 const RHS &R) { 1123 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R); 1124 } 1125 1126 template <typename LHS, typename RHS> 1127 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L, 1128 const RHS &R) { 1129 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R); 1130 } 1131 1132 template <typename LHS, typename RHS> 1133 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L, 1134 const RHS &R) { 1135 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R); 1136 } 1137 1138 template <typename LHS_t, typename RHS_t, unsigned Opcode, 1139 unsigned WrapFlags = 0> 1140 struct OverflowingBinaryOp_match { 1141 LHS_t L; 1142 RHS_t R; 1143 1144 OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) 1145 : L(LHS), R(RHS) {} 1146 1147 template <typename OpTy> bool match(OpTy *V) { 1148 if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) { 1149 if (Op->getOpcode() != Opcode) 1150 return false; 1151 if ((WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap) && 1152 !Op->hasNoUnsignedWrap()) 1153 return false; 1154 if ((WrapFlags & OverflowingBinaryOperator::NoSignedWrap) && 1155 !Op->hasNoSignedWrap()) 1156 return false; 1157 return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1)); 1158 } 1159 return false; 1160 } 1161 }; 1162 1163 template <typename LHS, typename RHS> 1164 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 1165 OverflowingBinaryOperator::NoSignedWrap> 1166 m_NSWAdd(const LHS &L, const RHS &R) { 1167 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 1168 OverflowingBinaryOperator::NoSignedWrap>( 1169 L, R); 1170 } 1171 template <typename LHS, typename RHS> 1172 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 1173 OverflowingBinaryOperator::NoSignedWrap> 1174 m_NSWSub(const LHS &L, const RHS &R) { 1175 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 1176 OverflowingBinaryOperator::NoSignedWrap>( 1177 L, R); 1178 } 1179 template <typename LHS, typename RHS> 1180 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 1181 OverflowingBinaryOperator::NoSignedWrap> 1182 m_NSWMul(const LHS &L, const RHS &R) { 1183 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 1184 OverflowingBinaryOperator::NoSignedWrap>( 1185 L, R); 1186 } 1187 template <typename LHS, typename RHS> 1188 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 1189 OverflowingBinaryOperator::NoSignedWrap> 1190 m_NSWShl(const LHS &L, const RHS &R) { 1191 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 1192 OverflowingBinaryOperator::NoSignedWrap>( 1193 L, R); 1194 } 1195 1196 template <typename LHS, typename RHS> 1197 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 1198 OverflowingBinaryOperator::NoUnsignedWrap> 1199 m_NUWAdd(const LHS &L, const RHS &R) { 1200 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add, 1201 OverflowingBinaryOperator::NoUnsignedWrap>( 1202 L, R); 1203 } 1204 template <typename LHS, typename RHS> 1205 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 1206 OverflowingBinaryOperator::NoUnsignedWrap> 1207 m_NUWSub(const LHS &L, const RHS &R) { 1208 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub, 1209 OverflowingBinaryOperator::NoUnsignedWrap>( 1210 L, R); 1211 } 1212 template <typename LHS, typename RHS> 1213 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 1214 OverflowingBinaryOperator::NoUnsignedWrap> 1215 m_NUWMul(const LHS &L, const RHS &R) { 1216 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul, 1217 OverflowingBinaryOperator::NoUnsignedWrap>( 1218 L, R); 1219 } 1220 template <typename LHS, typename RHS> 1221 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 1222 OverflowingBinaryOperator::NoUnsignedWrap> 1223 m_NUWShl(const LHS &L, const RHS &R) { 1224 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl, 1225 OverflowingBinaryOperator::NoUnsignedWrap>( 1226 L, R); 1227 } 1228 1229 template <typename LHS_t, typename RHS_t, bool Commutable = false> 1230 struct SpecificBinaryOp_match 1231 : public BinaryOp_match<LHS_t, RHS_t, 0, Commutable> { 1232 unsigned Opcode; 1233 1234 SpecificBinaryOp_match(unsigned Opcode, const LHS_t &LHS, const RHS_t &RHS) 1235 : BinaryOp_match<LHS_t, RHS_t, 0, Commutable>(LHS, RHS), Opcode(Opcode) {} 1236 1237 template <typename OpTy> bool match(OpTy *V) { 1238 return BinaryOp_match<LHS_t, RHS_t, 0, Commutable>::match(Opcode, V); 1239 } 1240 }; 1241 1242 /// Matches a specific opcode. 1243 template <typename LHS, typename RHS> 1244 inline SpecificBinaryOp_match<LHS, RHS> m_BinOp(unsigned Opcode, const LHS &L, 1245 const RHS &R) { 1246 return SpecificBinaryOp_match<LHS, RHS>(Opcode, L, R); 1247 } 1248 1249 //===----------------------------------------------------------------------===// 1250 // Class that matches a group of binary opcodes. 1251 // 1252 template <typename LHS_t, typename RHS_t, typename Predicate> 1253 struct BinOpPred_match : Predicate { 1254 LHS_t L; 1255 RHS_t R; 1256 1257 BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 1258 1259 template <typename OpTy> bool match(OpTy *V) { 1260 if (auto *I = dyn_cast<Instruction>(V)) 1261 return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) && 1262 R.match(I->getOperand(1)); 1263 if (auto *CE = dyn_cast<ConstantExpr>(V)) 1264 return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) && 1265 R.match(CE->getOperand(1)); 1266 return false; 1267 } 1268 }; 1269 1270 struct is_shift_op { 1271 bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); } 1272 }; 1273 1274 struct is_right_shift_op { 1275 bool isOpType(unsigned Opcode) { 1276 return Opcode == Instruction::LShr || Opcode == Instruction::AShr; 1277 } 1278 }; 1279 1280 struct is_logical_shift_op { 1281 bool isOpType(unsigned Opcode) { 1282 return Opcode == Instruction::LShr || Opcode == Instruction::Shl; 1283 } 1284 }; 1285 1286 struct is_bitwiselogic_op { 1287 bool isOpType(unsigned Opcode) { 1288 return Instruction::isBitwiseLogicOp(Opcode); 1289 } 1290 }; 1291 1292 struct is_idiv_op { 1293 bool isOpType(unsigned Opcode) { 1294 return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv; 1295 } 1296 }; 1297 1298 struct is_irem_op { 1299 bool isOpType(unsigned Opcode) { 1300 return Opcode == Instruction::SRem || Opcode == Instruction::URem; 1301 } 1302 }; 1303 1304 /// Matches shift operations. 1305 template <typename LHS, typename RHS> 1306 inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L, 1307 const RHS &R) { 1308 return BinOpPred_match<LHS, RHS, is_shift_op>(L, R); 1309 } 1310 1311 /// Matches logical shift operations. 1312 template <typename LHS, typename RHS> 1313 inline BinOpPred_match<LHS, RHS, is_right_shift_op> m_Shr(const LHS &L, 1314 const RHS &R) { 1315 return BinOpPred_match<LHS, RHS, is_right_shift_op>(L, R); 1316 } 1317 1318 /// Matches logical shift operations. 1319 template <typename LHS, typename RHS> 1320 inline BinOpPred_match<LHS, RHS, is_logical_shift_op> 1321 m_LogicalShift(const LHS &L, const RHS &R) { 1322 return BinOpPred_match<LHS, RHS, is_logical_shift_op>(L, R); 1323 } 1324 1325 /// Matches bitwise logic operations. 1326 template <typename LHS, typename RHS> 1327 inline BinOpPred_match<LHS, RHS, is_bitwiselogic_op> 1328 m_BitwiseLogic(const LHS &L, const RHS &R) { 1329 return BinOpPred_match<LHS, RHS, is_bitwiselogic_op>(L, R); 1330 } 1331 1332 /// Matches integer division operations. 1333 template <typename LHS, typename RHS> 1334 inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L, 1335 const RHS &R) { 1336 return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R); 1337 } 1338 1339 /// Matches integer remainder operations. 1340 template <typename LHS, typename RHS> 1341 inline BinOpPred_match<LHS, RHS, is_irem_op> m_IRem(const LHS &L, 1342 const RHS &R) { 1343 return BinOpPred_match<LHS, RHS, is_irem_op>(L, R); 1344 } 1345 1346 //===----------------------------------------------------------------------===// 1347 // Class that matches exact binary ops. 1348 // 1349 template <typename SubPattern_t> struct Exact_match { 1350 SubPattern_t SubPattern; 1351 1352 Exact_match(const SubPattern_t &SP) : SubPattern(SP) {} 1353 1354 template <typename OpTy> bool match(OpTy *V) { 1355 if (auto *PEO = dyn_cast<PossiblyExactOperator>(V)) 1356 return PEO->isExact() && SubPattern.match(V); 1357 return false; 1358 } 1359 }; 1360 1361 template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) { 1362 return SubPattern; 1363 } 1364 1365 //===----------------------------------------------------------------------===// 1366 // Matchers for CmpInst classes 1367 // 1368 1369 template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy, 1370 bool Commutable = false> 1371 struct CmpClass_match { 1372 PredicateTy &Predicate; 1373 LHS_t L; 1374 RHS_t R; 1375 1376 // The evaluation order is always stable, regardless of Commutability. 1377 // The LHS is always matched first. 1378 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS) 1379 : Predicate(Pred), L(LHS), R(RHS) {} 1380 1381 template <typename OpTy> bool match(OpTy *V) { 1382 if (auto *I = dyn_cast<Class>(V)) { 1383 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) { 1384 Predicate = I->getPredicate(); 1385 return true; 1386 } else if (Commutable && L.match(I->getOperand(1)) && 1387 R.match(I->getOperand(0))) { 1388 Predicate = I->getSwappedPredicate(); 1389 return true; 1390 } 1391 } 1392 return false; 1393 } 1394 }; 1395 1396 template <typename LHS, typename RHS> 1397 inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate> 1398 m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 1399 return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R); 1400 } 1401 1402 template <typename LHS, typename RHS> 1403 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate> 1404 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 1405 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R); 1406 } 1407 1408 template <typename LHS, typename RHS> 1409 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate> 1410 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 1411 return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R); 1412 } 1413 1414 //===----------------------------------------------------------------------===// 1415 // Matchers for instructions with a given opcode and number of operands. 1416 // 1417 1418 /// Matches instructions with Opcode and three operands. 1419 template <typename T0, unsigned Opcode> struct OneOps_match { 1420 T0 Op1; 1421 1422 OneOps_match(const T0 &Op1) : Op1(Op1) {} 1423 1424 template <typename OpTy> bool match(OpTy *V) { 1425 if (V->getValueID() == Value::InstructionVal + Opcode) { 1426 auto *I = cast<Instruction>(V); 1427 return Op1.match(I->getOperand(0)); 1428 } 1429 return false; 1430 } 1431 }; 1432 1433 /// Matches instructions with Opcode and three operands. 1434 template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match { 1435 T0 Op1; 1436 T1 Op2; 1437 1438 TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {} 1439 1440 template <typename OpTy> bool match(OpTy *V) { 1441 if (V->getValueID() == Value::InstructionVal + Opcode) { 1442 auto *I = cast<Instruction>(V); 1443 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)); 1444 } 1445 return false; 1446 } 1447 }; 1448 1449 /// Matches instructions with Opcode and three operands. 1450 template <typename T0, typename T1, typename T2, unsigned Opcode> 1451 struct ThreeOps_match { 1452 T0 Op1; 1453 T1 Op2; 1454 T2 Op3; 1455 1456 ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3) 1457 : Op1(Op1), Op2(Op2), Op3(Op3) {} 1458 1459 template <typename OpTy> bool match(OpTy *V) { 1460 if (V->getValueID() == Value::InstructionVal + Opcode) { 1461 auto *I = cast<Instruction>(V); 1462 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) && 1463 Op3.match(I->getOperand(2)); 1464 } 1465 return false; 1466 } 1467 }; 1468 1469 /// Matches SelectInst. 1470 template <typename Cond, typename LHS, typename RHS> 1471 inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select> 1472 m_Select(const Cond &C, const LHS &L, const RHS &R) { 1473 return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R); 1474 } 1475 1476 /// This matches a select of two constants, e.g.: 1477 /// m_SelectCst<-1, 0>(m_Value(V)) 1478 template <int64_t L, int64_t R, typename Cond> 1479 inline ThreeOps_match<Cond, constantint_match<L>, constantint_match<R>, 1480 Instruction::Select> 1481 m_SelectCst(const Cond &C) { 1482 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>()); 1483 } 1484 1485 /// Matches FreezeInst. 1486 template <typename OpTy> 1487 inline OneOps_match<OpTy, Instruction::Freeze> m_Freeze(const OpTy &Op) { 1488 return OneOps_match<OpTy, Instruction::Freeze>(Op); 1489 } 1490 1491 /// Matches InsertElementInst. 1492 template <typename Val_t, typename Elt_t, typename Idx_t> 1493 inline ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement> 1494 m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) { 1495 return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>( 1496 Val, Elt, Idx); 1497 } 1498 1499 /// Matches ExtractElementInst. 1500 template <typename Val_t, typename Idx_t> 1501 inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement> 1502 m_ExtractElt(const Val_t &Val, const Idx_t &Idx) { 1503 return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx); 1504 } 1505 1506 /// Matches shuffle. 1507 template <typename T0, typename T1, typename T2> struct Shuffle_match { 1508 T0 Op1; 1509 T1 Op2; 1510 T2 Mask; 1511 1512 Shuffle_match(const T0 &Op1, const T1 &Op2, const T2 &Mask) 1513 : Op1(Op1), Op2(Op2), Mask(Mask) {} 1514 1515 template <typename OpTy> bool match(OpTy *V) { 1516 if (auto *I = dyn_cast<ShuffleVectorInst>(V)) { 1517 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) && 1518 Mask.match(I->getShuffleMask()); 1519 } 1520 return false; 1521 } 1522 }; 1523 1524 struct m_Mask { 1525 ArrayRef<int> &MaskRef; 1526 m_Mask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {} 1527 bool match(ArrayRef<int> Mask) { 1528 MaskRef = Mask; 1529 return true; 1530 } 1531 }; 1532 1533 struct m_ZeroMask { 1534 bool match(ArrayRef<int> Mask) { 1535 return all_of(Mask, [](int Elem) { return Elem == 0 || Elem == -1; }); 1536 } 1537 }; 1538 1539 struct m_SpecificMask { 1540 ArrayRef<int> &MaskRef; 1541 m_SpecificMask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {} 1542 bool match(ArrayRef<int> Mask) { return MaskRef == Mask; } 1543 }; 1544 1545 struct m_SplatOrUndefMask { 1546 int &SplatIndex; 1547 m_SplatOrUndefMask(int &SplatIndex) : SplatIndex(SplatIndex) {} 1548 bool match(ArrayRef<int> Mask) { 1549 auto First = find_if(Mask, [](int Elem) { return Elem != -1; }); 1550 if (First == Mask.end()) 1551 return false; 1552 SplatIndex = *First; 1553 return all_of(Mask, 1554 [First](int Elem) { return Elem == *First || Elem == -1; }); 1555 } 1556 }; 1557 1558 /// Matches ShuffleVectorInst independently of mask value. 1559 template <typename V1_t, typename V2_t> 1560 inline TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector> 1561 m_Shuffle(const V1_t &v1, const V2_t &v2) { 1562 return TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>(v1, v2); 1563 } 1564 1565 template <typename V1_t, typename V2_t, typename Mask_t> 1566 inline Shuffle_match<V1_t, V2_t, Mask_t> 1567 m_Shuffle(const V1_t &v1, const V2_t &v2, const Mask_t &mask) { 1568 return Shuffle_match<V1_t, V2_t, Mask_t>(v1, v2, mask); 1569 } 1570 1571 /// Matches LoadInst. 1572 template <typename OpTy> 1573 inline OneOps_match<OpTy, Instruction::Load> m_Load(const OpTy &Op) { 1574 return OneOps_match<OpTy, Instruction::Load>(Op); 1575 } 1576 1577 /// Matches StoreInst. 1578 template <typename ValueOpTy, typename PointerOpTy> 1579 inline TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store> 1580 m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) { 1581 return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp, 1582 PointerOp); 1583 } 1584 1585 //===----------------------------------------------------------------------===// 1586 // Matchers for CastInst classes 1587 // 1588 1589 template <typename Op_t, unsigned Opcode> struct CastClass_match { 1590 Op_t Op; 1591 1592 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {} 1593 1594 template <typename OpTy> bool match(OpTy *V) { 1595 if (auto *O = dyn_cast<Operator>(V)) 1596 return O->getOpcode() == Opcode && Op.match(O->getOperand(0)); 1597 return false; 1598 } 1599 }; 1600 1601 /// Matches BitCast. 1602 template <typename OpTy> 1603 inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) { 1604 return CastClass_match<OpTy, Instruction::BitCast>(Op); 1605 } 1606 1607 /// Matches PtrToInt. 1608 template <typename OpTy> 1609 inline CastClass_match<OpTy, Instruction::PtrToInt> m_PtrToInt(const OpTy &Op) { 1610 return CastClass_match<OpTy, Instruction::PtrToInt>(Op); 1611 } 1612 1613 /// Matches IntToPtr. 1614 template <typename OpTy> 1615 inline CastClass_match<OpTy, Instruction::IntToPtr> m_IntToPtr(const OpTy &Op) { 1616 return CastClass_match<OpTy, Instruction::IntToPtr>(Op); 1617 } 1618 1619 /// Matches Trunc. 1620 template <typename OpTy> 1621 inline CastClass_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) { 1622 return CastClass_match<OpTy, Instruction::Trunc>(Op); 1623 } 1624 1625 template <typename OpTy> 1626 inline match_combine_or<CastClass_match<OpTy, Instruction::Trunc>, OpTy> 1627 m_TruncOrSelf(const OpTy &Op) { 1628 return m_CombineOr(m_Trunc(Op), Op); 1629 } 1630 1631 /// Matches SExt. 1632 template <typename OpTy> 1633 inline CastClass_match<OpTy, Instruction::SExt> m_SExt(const OpTy &Op) { 1634 return CastClass_match<OpTy, Instruction::SExt>(Op); 1635 } 1636 1637 /// Matches ZExt. 1638 template <typename OpTy> 1639 inline CastClass_match<OpTy, Instruction::ZExt> m_ZExt(const OpTy &Op) { 1640 return CastClass_match<OpTy, Instruction::ZExt>(Op); 1641 } 1642 1643 template <typename OpTy> 1644 inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, OpTy> 1645 m_ZExtOrSelf(const OpTy &Op) { 1646 return m_CombineOr(m_ZExt(Op), Op); 1647 } 1648 1649 template <typename OpTy> 1650 inline match_combine_or<CastClass_match<OpTy, Instruction::SExt>, OpTy> 1651 m_SExtOrSelf(const OpTy &Op) { 1652 return m_CombineOr(m_SExt(Op), Op); 1653 } 1654 1655 template <typename OpTy> 1656 inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, 1657 CastClass_match<OpTy, Instruction::SExt>> 1658 m_ZExtOrSExt(const OpTy &Op) { 1659 return m_CombineOr(m_ZExt(Op), m_SExt(Op)); 1660 } 1661 1662 template <typename OpTy> 1663 inline match_combine_or< 1664 match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, 1665 CastClass_match<OpTy, Instruction::SExt>>, 1666 OpTy> 1667 m_ZExtOrSExtOrSelf(const OpTy &Op) { 1668 return m_CombineOr(m_ZExtOrSExt(Op), Op); 1669 } 1670 1671 template <typename OpTy> 1672 inline CastClass_match<OpTy, Instruction::UIToFP> m_UIToFP(const OpTy &Op) { 1673 return CastClass_match<OpTy, Instruction::UIToFP>(Op); 1674 } 1675 1676 template <typename OpTy> 1677 inline CastClass_match<OpTy, Instruction::SIToFP> m_SIToFP(const OpTy &Op) { 1678 return CastClass_match<OpTy, Instruction::SIToFP>(Op); 1679 } 1680 1681 template <typename OpTy> 1682 inline CastClass_match<OpTy, Instruction::FPToUI> m_FPToUI(const OpTy &Op) { 1683 return CastClass_match<OpTy, Instruction::FPToUI>(Op); 1684 } 1685 1686 template <typename OpTy> 1687 inline CastClass_match<OpTy, Instruction::FPToSI> m_FPToSI(const OpTy &Op) { 1688 return CastClass_match<OpTy, Instruction::FPToSI>(Op); 1689 } 1690 1691 template <typename OpTy> 1692 inline CastClass_match<OpTy, Instruction::FPTrunc> m_FPTrunc(const OpTy &Op) { 1693 return CastClass_match<OpTy, Instruction::FPTrunc>(Op); 1694 } 1695 1696 template <typename OpTy> 1697 inline CastClass_match<OpTy, Instruction::FPExt> m_FPExt(const OpTy &Op) { 1698 return CastClass_match<OpTy, Instruction::FPExt>(Op); 1699 } 1700 1701 //===----------------------------------------------------------------------===// 1702 // Matchers for control flow. 1703 // 1704 1705 struct br_match { 1706 BasicBlock *&Succ; 1707 1708 br_match(BasicBlock *&Succ) : Succ(Succ) {} 1709 1710 template <typename OpTy> bool match(OpTy *V) { 1711 if (auto *BI = dyn_cast<BranchInst>(V)) 1712 if (BI->isUnconditional()) { 1713 Succ = BI->getSuccessor(0); 1714 return true; 1715 } 1716 return false; 1717 } 1718 }; 1719 1720 inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); } 1721 1722 template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t> 1723 struct brc_match { 1724 Cond_t Cond; 1725 TrueBlock_t T; 1726 FalseBlock_t F; 1727 1728 brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f) 1729 : Cond(C), T(t), F(f) {} 1730 1731 template <typename OpTy> bool match(OpTy *V) { 1732 if (auto *BI = dyn_cast<BranchInst>(V)) 1733 if (BI->isConditional() && Cond.match(BI->getCondition())) 1734 return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1)); 1735 return false; 1736 } 1737 }; 1738 1739 template <typename Cond_t> 1740 inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>> 1741 m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) { 1742 return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>( 1743 C, m_BasicBlock(T), m_BasicBlock(F)); 1744 } 1745 1746 template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t> 1747 inline brc_match<Cond_t, TrueBlock_t, FalseBlock_t> 1748 m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) { 1749 return brc_match<Cond_t, TrueBlock_t, FalseBlock_t>(C, T, F); 1750 } 1751 1752 //===----------------------------------------------------------------------===// 1753 // Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y). 1754 // 1755 1756 template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t, 1757 bool Commutable = false> 1758 struct MaxMin_match { 1759 using PredType = Pred_t; 1760 LHS_t L; 1761 RHS_t R; 1762 1763 // The evaluation order is always stable, regardless of Commutability. 1764 // The LHS is always matched first. 1765 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 1766 1767 template <typename OpTy> bool match(OpTy *V) { 1768 if (auto *II = dyn_cast<IntrinsicInst>(V)) { 1769 Intrinsic::ID IID = II->getIntrinsicID(); 1770 if ((IID == Intrinsic::smax && Pred_t::match(ICmpInst::ICMP_SGT)) || 1771 (IID == Intrinsic::smin && Pred_t::match(ICmpInst::ICMP_SLT)) || 1772 (IID == Intrinsic::umax && Pred_t::match(ICmpInst::ICMP_UGT)) || 1773 (IID == Intrinsic::umin && Pred_t::match(ICmpInst::ICMP_ULT))) { 1774 Value *LHS = II->getOperand(0), *RHS = II->getOperand(1); 1775 return (L.match(LHS) && R.match(RHS)) || 1776 (Commutable && L.match(RHS) && R.match(LHS)); 1777 } 1778 } 1779 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x". 1780 auto *SI = dyn_cast<SelectInst>(V); 1781 if (!SI) 1782 return false; 1783 auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition()); 1784 if (!Cmp) 1785 return false; 1786 // At this point we have a select conditioned on a comparison. Check that 1787 // it is the values returned by the select that are being compared. 1788 auto *TrueVal = SI->getTrueValue(); 1789 auto *FalseVal = SI->getFalseValue(); 1790 auto *LHS = Cmp->getOperand(0); 1791 auto *RHS = Cmp->getOperand(1); 1792 if ((TrueVal != LHS || FalseVal != RHS) && 1793 (TrueVal != RHS || FalseVal != LHS)) 1794 return false; 1795 typename CmpInst_t::Predicate Pred = 1796 LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate(); 1797 // Does "(x pred y) ? x : y" represent the desired max/min operation? 1798 if (!Pred_t::match(Pred)) 1799 return false; 1800 // It does! Bind the operands. 1801 return (L.match(LHS) && R.match(RHS)) || 1802 (Commutable && L.match(RHS) && R.match(LHS)); 1803 } 1804 }; 1805 1806 /// Helper class for identifying signed max predicates. 1807 struct smax_pred_ty { 1808 static bool match(ICmpInst::Predicate Pred) { 1809 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE; 1810 } 1811 }; 1812 1813 /// Helper class for identifying signed min predicates. 1814 struct smin_pred_ty { 1815 static bool match(ICmpInst::Predicate Pred) { 1816 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE; 1817 } 1818 }; 1819 1820 /// Helper class for identifying unsigned max predicates. 1821 struct umax_pred_ty { 1822 static bool match(ICmpInst::Predicate Pred) { 1823 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE; 1824 } 1825 }; 1826 1827 /// Helper class for identifying unsigned min predicates. 1828 struct umin_pred_ty { 1829 static bool match(ICmpInst::Predicate Pred) { 1830 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE; 1831 } 1832 }; 1833 1834 /// Helper class for identifying ordered max predicates. 1835 struct ofmax_pred_ty { 1836 static bool match(FCmpInst::Predicate Pred) { 1837 return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE; 1838 } 1839 }; 1840 1841 /// Helper class for identifying ordered min predicates. 1842 struct ofmin_pred_ty { 1843 static bool match(FCmpInst::Predicate Pred) { 1844 return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE; 1845 } 1846 }; 1847 1848 /// Helper class for identifying unordered max predicates. 1849 struct ufmax_pred_ty { 1850 static bool match(FCmpInst::Predicate Pred) { 1851 return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE; 1852 } 1853 }; 1854 1855 /// Helper class for identifying unordered min predicates. 1856 struct ufmin_pred_ty { 1857 static bool match(FCmpInst::Predicate Pred) { 1858 return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE; 1859 } 1860 }; 1861 1862 template <typename LHS, typename RHS> 1863 inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L, 1864 const RHS &R) { 1865 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R); 1866 } 1867 1868 template <typename LHS, typename RHS> 1869 inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L, 1870 const RHS &R) { 1871 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R); 1872 } 1873 1874 template <typename LHS, typename RHS> 1875 inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L, 1876 const RHS &R) { 1877 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R); 1878 } 1879 1880 template <typename LHS, typename RHS> 1881 inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L, 1882 const RHS &R) { 1883 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R); 1884 } 1885 1886 template <typename LHS, typename RHS> 1887 inline match_combine_or< 1888 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>, 1889 MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>>, 1890 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>, 1891 MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>>> 1892 m_MaxOrMin(const LHS &L, const RHS &R) { 1893 return m_CombineOr(m_CombineOr(m_SMax(L, R), m_SMin(L, R)), 1894 m_CombineOr(m_UMax(L, R), m_UMin(L, R))); 1895 } 1896 1897 /// Match an 'ordered' floating point maximum function. 1898 /// Floating point has one special value 'NaN'. Therefore, there is no total 1899 /// order. However, if we can ignore the 'NaN' value (for example, because of a 1900 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum' 1901 /// semantics. In the presence of 'NaN' we have to preserve the original 1902 /// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate. 1903 /// 1904 /// max(L, R) iff L and R are not NaN 1905 /// m_OrdFMax(L, R) = R iff L or R are NaN 1906 template <typename LHS, typename RHS> 1907 inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L, 1908 const RHS &R) { 1909 return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R); 1910 } 1911 1912 /// Match an 'ordered' floating point minimum function. 1913 /// Floating point has one special value 'NaN'. Therefore, there is no total 1914 /// order. However, if we can ignore the 'NaN' value (for example, because of a 1915 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum' 1916 /// semantics. In the presence of 'NaN' we have to preserve the original 1917 /// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate. 1918 /// 1919 /// min(L, R) iff L and R are not NaN 1920 /// m_OrdFMin(L, R) = R iff L or R are NaN 1921 template <typename LHS, typename RHS> 1922 inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L, 1923 const RHS &R) { 1924 return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R); 1925 } 1926 1927 /// Match an 'unordered' floating point maximum function. 1928 /// Floating point has one special value 'NaN'. Therefore, there is no total 1929 /// order. However, if we can ignore the 'NaN' value (for example, because of a 1930 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum' 1931 /// semantics. In the presence of 'NaN' we have to preserve the original 1932 /// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate. 1933 /// 1934 /// max(L, R) iff L and R are not NaN 1935 /// m_UnordFMax(L, R) = L iff L or R are NaN 1936 template <typename LHS, typename RHS> 1937 inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty> 1938 m_UnordFMax(const LHS &L, const RHS &R) { 1939 return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R); 1940 } 1941 1942 /// Match an 'unordered' floating point minimum function. 1943 /// Floating point has one special value 'NaN'. Therefore, there is no total 1944 /// order. However, if we can ignore the 'NaN' value (for example, because of a 1945 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum' 1946 /// semantics. In the presence of 'NaN' we have to preserve the original 1947 /// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate. 1948 /// 1949 /// min(L, R) iff L and R are not NaN 1950 /// m_UnordFMin(L, R) = L iff L or R are NaN 1951 template <typename LHS, typename RHS> 1952 inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty> 1953 m_UnordFMin(const LHS &L, const RHS &R) { 1954 return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R); 1955 } 1956 1957 //===----------------------------------------------------------------------===// 1958 // Matchers for overflow check patterns: e.g. (a + b) u< a, (a ^ -1) <u b 1959 // Note that S might be matched to other instructions than AddInst. 1960 // 1961 1962 template <typename LHS_t, typename RHS_t, typename Sum_t> 1963 struct UAddWithOverflow_match { 1964 LHS_t L; 1965 RHS_t R; 1966 Sum_t S; 1967 1968 UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S) 1969 : L(L), R(R), S(S) {} 1970 1971 template <typename OpTy> bool match(OpTy *V) { 1972 Value *ICmpLHS, *ICmpRHS; 1973 ICmpInst::Predicate Pred; 1974 if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V)) 1975 return false; 1976 1977 Value *AddLHS, *AddRHS; 1978 auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS)); 1979 1980 // (a + b) u< a, (a + b) u< b 1981 if (Pred == ICmpInst::ICMP_ULT) 1982 if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS)) 1983 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS); 1984 1985 // a >u (a + b), b >u (a + b) 1986 if (Pred == ICmpInst::ICMP_UGT) 1987 if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS)) 1988 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS); 1989 1990 Value *Op1; 1991 auto XorExpr = m_OneUse(m_Xor(m_Value(Op1), m_AllOnes())); 1992 // (a ^ -1) <u b 1993 if (Pred == ICmpInst::ICMP_ULT) { 1994 if (XorExpr.match(ICmpLHS)) 1995 return L.match(Op1) && R.match(ICmpRHS) && S.match(ICmpLHS); 1996 } 1997 // b > u (a ^ -1) 1998 if (Pred == ICmpInst::ICMP_UGT) { 1999 if (XorExpr.match(ICmpRHS)) 2000 return L.match(Op1) && R.match(ICmpLHS) && S.match(ICmpRHS); 2001 } 2002 2003 // Match special-case for increment-by-1. 2004 if (Pred == ICmpInst::ICMP_EQ) { 2005 // (a + 1) == 0 2006 // (1 + a) == 0 2007 if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) && 2008 (m_One().match(AddLHS) || m_One().match(AddRHS))) 2009 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS); 2010 // 0 == (a + 1) 2011 // 0 == (1 + a) 2012 if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) && 2013 (m_One().match(AddLHS) || m_One().match(AddRHS))) 2014 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS); 2015 } 2016 2017 return false; 2018 } 2019 }; 2020 2021 /// Match an icmp instruction checking for unsigned overflow on addition. 2022 /// 2023 /// S is matched to the addition whose result is being checked for overflow, and 2024 /// L and R are matched to the LHS and RHS of S. 2025 template <typename LHS_t, typename RHS_t, typename Sum_t> 2026 UAddWithOverflow_match<LHS_t, RHS_t, Sum_t> 2027 m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) { 2028 return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S); 2029 } 2030 2031 template <typename Opnd_t> struct Argument_match { 2032 unsigned OpI; 2033 Opnd_t Val; 2034 2035 Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {} 2036 2037 template <typename OpTy> bool match(OpTy *V) { 2038 // FIXME: Should likely be switched to use `CallBase`. 2039 if (const auto *CI = dyn_cast<CallInst>(V)) 2040 return Val.match(CI->getArgOperand(OpI)); 2041 return false; 2042 } 2043 }; 2044 2045 /// Match an argument. 2046 template <unsigned OpI, typename Opnd_t> 2047 inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) { 2048 return Argument_match<Opnd_t>(OpI, Op); 2049 } 2050 2051 /// Intrinsic matchers. 2052 struct IntrinsicID_match { 2053 unsigned ID; 2054 2055 IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {} 2056 2057 template <typename OpTy> bool match(OpTy *V) { 2058 if (const auto *CI = dyn_cast<CallInst>(V)) 2059 if (const auto *F = CI->getCalledFunction()) 2060 return F->getIntrinsicID() == ID; 2061 return false; 2062 } 2063 }; 2064 2065 /// Intrinsic matches are combinations of ID matchers, and argument 2066 /// matchers. Higher arity matcher are defined recursively in terms of and-ing 2067 /// them with lower arity matchers. Here's some convenient typedefs for up to 2068 /// several arguments, and more can be added as needed 2069 template <typename T0 = void, typename T1 = void, typename T2 = void, 2070 typename T3 = void, typename T4 = void, typename T5 = void, 2071 typename T6 = void, typename T7 = void, typename T8 = void, 2072 typename T9 = void, typename T10 = void> 2073 struct m_Intrinsic_Ty; 2074 template <typename T0> struct m_Intrinsic_Ty<T0> { 2075 using Ty = match_combine_and<IntrinsicID_match, Argument_match<T0>>; 2076 }; 2077 template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> { 2078 using Ty = 2079 match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>>; 2080 }; 2081 template <typename T0, typename T1, typename T2> 2082 struct m_Intrinsic_Ty<T0, T1, T2> { 2083 using Ty = 2084 match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty, 2085 Argument_match<T2>>; 2086 }; 2087 template <typename T0, typename T1, typename T2, typename T3> 2088 struct m_Intrinsic_Ty<T0, T1, T2, T3> { 2089 using Ty = 2090 match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty, 2091 Argument_match<T3>>; 2092 }; 2093 2094 template <typename T0, typename T1, typename T2, typename T3, typename T4> 2095 struct m_Intrinsic_Ty<T0, T1, T2, T3, T4> { 2096 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty, 2097 Argument_match<T4>>; 2098 }; 2099 2100 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> 2101 struct m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5> { 2102 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty, 2103 Argument_match<T5>>; 2104 }; 2105 2106 /// Match intrinsic calls like this: 2107 /// m_Intrinsic<Intrinsic::fabs>(m_Value(X)) 2108 template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() { 2109 return IntrinsicID_match(IntrID); 2110 } 2111 2112 /// Matches MaskedLoad Intrinsic. 2113 template <typename Opnd0, typename Opnd1, typename Opnd2, typename Opnd3> 2114 inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2, Opnd3>::Ty 2115 m_MaskedLoad(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2, 2116 const Opnd3 &Op3) { 2117 return m_Intrinsic<Intrinsic::masked_load>(Op0, Op1, Op2, Op3); 2118 } 2119 2120 template <Intrinsic::ID IntrID, typename T0> 2121 inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) { 2122 return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0)); 2123 } 2124 2125 template <Intrinsic::ID IntrID, typename T0, typename T1> 2126 inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0, 2127 const T1 &Op1) { 2128 return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1)); 2129 } 2130 2131 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2> 2132 inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty 2133 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) { 2134 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2)); 2135 } 2136 2137 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2, 2138 typename T3> 2139 inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty 2140 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) { 2141 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3)); 2142 } 2143 2144 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2, 2145 typename T3, typename T4> 2146 inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty 2147 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3, 2148 const T4 &Op4) { 2149 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3), 2150 m_Argument<4>(Op4)); 2151 } 2152 2153 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2, 2154 typename T3, typename T4, typename T5> 2155 inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5>::Ty 2156 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3, 2157 const T4 &Op4, const T5 &Op5) { 2158 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3, Op4), 2159 m_Argument<5>(Op5)); 2160 } 2161 2162 // Helper intrinsic matching specializations. 2163 template <typename Opnd0> 2164 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) { 2165 return m_Intrinsic<Intrinsic::bitreverse>(Op0); 2166 } 2167 2168 template <typename Opnd0> 2169 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) { 2170 return m_Intrinsic<Intrinsic::bswap>(Op0); 2171 } 2172 2173 template <typename Opnd0> 2174 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) { 2175 return m_Intrinsic<Intrinsic::fabs>(Op0); 2176 } 2177 2178 template <typename Opnd0> 2179 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) { 2180 return m_Intrinsic<Intrinsic::canonicalize>(Op0); 2181 } 2182 2183 template <typename Opnd0, typename Opnd1> 2184 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0, 2185 const Opnd1 &Op1) { 2186 return m_Intrinsic<Intrinsic::minnum>(Op0, Op1); 2187 } 2188 2189 template <typename Opnd0, typename Opnd1> 2190 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0, 2191 const Opnd1 &Op1) { 2192 return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1); 2193 } 2194 2195 template <typename Opnd0, typename Opnd1, typename Opnd2> 2196 inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty 2197 m_FShl(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) { 2198 return m_Intrinsic<Intrinsic::fshl>(Op0, Op1, Op2); 2199 } 2200 2201 template <typename Opnd0, typename Opnd1, typename Opnd2> 2202 inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty 2203 m_FShr(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) { 2204 return m_Intrinsic<Intrinsic::fshr>(Op0, Op1, Op2); 2205 } 2206 2207 //===----------------------------------------------------------------------===// 2208 // Matchers for two-operands operators with the operators in either order 2209 // 2210 2211 /// Matches a BinaryOperator with LHS and RHS in either order. 2212 template <typename LHS, typename RHS> 2213 inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) { 2214 return AnyBinaryOp_match<LHS, RHS, true>(L, R); 2215 } 2216 2217 /// Matches an ICmp with a predicate over LHS and RHS in either order. 2218 /// Swaps the predicate if operands are commuted. 2219 template <typename LHS, typename RHS> 2220 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true> 2221 m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 2222 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L, 2223 R); 2224 } 2225 2226 /// Matches a specific opcode with LHS and RHS in either order. 2227 template <typename LHS, typename RHS> 2228 inline SpecificBinaryOp_match<LHS, RHS, true> 2229 m_c_BinOp(unsigned Opcode, const LHS &L, const RHS &R) { 2230 return SpecificBinaryOp_match<LHS, RHS, true>(Opcode, L, R); 2231 } 2232 2233 /// Matches a Add with LHS and RHS in either order. 2234 template <typename LHS, typename RHS> 2235 inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L, 2236 const RHS &R) { 2237 return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R); 2238 } 2239 2240 /// Matches a Mul with LHS and RHS in either order. 2241 template <typename LHS, typename RHS> 2242 inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L, 2243 const RHS &R) { 2244 return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R); 2245 } 2246 2247 /// Matches an And with LHS and RHS in either order. 2248 template <typename LHS, typename RHS> 2249 inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L, 2250 const RHS &R) { 2251 return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R); 2252 } 2253 2254 /// Matches an Or with LHS and RHS in either order. 2255 template <typename LHS, typename RHS> 2256 inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L, 2257 const RHS &R) { 2258 return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R); 2259 } 2260 2261 /// Matches an Xor with LHS and RHS in either order. 2262 template <typename LHS, typename RHS> 2263 inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L, 2264 const RHS &R) { 2265 return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R); 2266 } 2267 2268 /// Matches a 'Neg' as 'sub 0, V'. 2269 template <typename ValTy> 2270 inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub> 2271 m_Neg(const ValTy &V) { 2272 return m_Sub(m_ZeroInt(), V); 2273 } 2274 2275 /// Matches a 'Neg' as 'sub nsw 0, V'. 2276 template <typename ValTy> 2277 inline OverflowingBinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, 2278 Instruction::Sub, 2279 OverflowingBinaryOperator::NoSignedWrap> 2280 m_NSWNeg(const ValTy &V) { 2281 return m_NSWSub(m_ZeroInt(), V); 2282 } 2283 2284 /// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'. 2285 template <typename ValTy> 2286 inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true> 2287 m_Not(const ValTy &V) { 2288 return m_c_Xor(V, m_AllOnes()); 2289 } 2290 2291 template <typename ValTy> struct NotForbidUndef_match { 2292 ValTy Val; 2293 NotForbidUndef_match(const ValTy &V) : Val(V) {} 2294 2295 template <typename OpTy> bool match(OpTy *V) { 2296 // We do not use m_c_Xor because that could match an arbitrary APInt that is 2297 // not -1 as C and then fail to match the other operand if it is -1. 2298 // This code should still work even when both operands are constants. 2299 Value *X; 2300 const APInt *C; 2301 if (m_Xor(m_Value(X), m_APIntForbidUndef(C)).match(V) && C->isAllOnes()) 2302 return Val.match(X); 2303 if (m_Xor(m_APIntForbidUndef(C), m_Value(X)).match(V) && C->isAllOnes()) 2304 return Val.match(X); 2305 return false; 2306 } 2307 }; 2308 2309 /// Matches a bitwise 'not' as 'xor V, -1' or 'xor -1, V'. For vectors, the 2310 /// constant value must be composed of only -1 scalar elements. 2311 template <typename ValTy> 2312 inline NotForbidUndef_match<ValTy> m_NotForbidUndef(const ValTy &V) { 2313 return NotForbidUndef_match<ValTy>(V); 2314 } 2315 2316 /// Matches an SMin with LHS and RHS in either order. 2317 template <typename LHS, typename RHS> 2318 inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true> 2319 m_c_SMin(const LHS &L, const RHS &R) { 2320 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R); 2321 } 2322 /// Matches an SMax with LHS and RHS in either order. 2323 template <typename LHS, typename RHS> 2324 inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true> 2325 m_c_SMax(const LHS &L, const RHS &R) { 2326 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R); 2327 } 2328 /// Matches a UMin with LHS and RHS in either order. 2329 template <typename LHS, typename RHS> 2330 inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true> 2331 m_c_UMin(const LHS &L, const RHS &R) { 2332 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R); 2333 } 2334 /// Matches a UMax with LHS and RHS in either order. 2335 template <typename LHS, typename RHS> 2336 inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true> 2337 m_c_UMax(const LHS &L, const RHS &R) { 2338 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R); 2339 } 2340 2341 template <typename LHS, typename RHS> 2342 inline match_combine_or< 2343 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>, 2344 MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>>, 2345 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>, 2346 MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>>> 2347 m_c_MaxOrMin(const LHS &L, const RHS &R) { 2348 return m_CombineOr(m_CombineOr(m_c_SMax(L, R), m_c_SMin(L, R)), 2349 m_CombineOr(m_c_UMax(L, R), m_c_UMin(L, R))); 2350 } 2351 2352 /// Matches FAdd with LHS and RHS in either order. 2353 template <typename LHS, typename RHS> 2354 inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true> 2355 m_c_FAdd(const LHS &L, const RHS &R) { 2356 return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R); 2357 } 2358 2359 /// Matches FMul with LHS and RHS in either order. 2360 template <typename LHS, typename RHS> 2361 inline BinaryOp_match<LHS, RHS, Instruction::FMul, true> 2362 m_c_FMul(const LHS &L, const RHS &R) { 2363 return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R); 2364 } 2365 2366 template <typename Opnd_t> struct Signum_match { 2367 Opnd_t Val; 2368 Signum_match(const Opnd_t &V) : Val(V) {} 2369 2370 template <typename OpTy> bool match(OpTy *V) { 2371 unsigned TypeSize = V->getType()->getScalarSizeInBits(); 2372 if (TypeSize == 0) 2373 return false; 2374 2375 unsigned ShiftWidth = TypeSize - 1; 2376 Value *OpL = nullptr, *OpR = nullptr; 2377 2378 // This is the representation of signum we match: 2379 // 2380 // signum(x) == (x >> 63) | (-x >>u 63) 2381 // 2382 // An i1 value is its own signum, so it's correct to match 2383 // 2384 // signum(x) == (x >> 0) | (-x >>u 0) 2385 // 2386 // for i1 values. 2387 2388 auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth)); 2389 auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth)); 2390 auto Signum = m_Or(LHS, RHS); 2391 2392 return Signum.match(V) && OpL == OpR && Val.match(OpL); 2393 } 2394 }; 2395 2396 /// Matches a signum pattern. 2397 /// 2398 /// signum(x) = 2399 /// x > 0 -> 1 2400 /// x == 0 -> 0 2401 /// x < 0 -> -1 2402 template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) { 2403 return Signum_match<Val_t>(V); 2404 } 2405 2406 template <int Ind, typename Opnd_t> struct ExtractValue_match { 2407 Opnd_t Val; 2408 ExtractValue_match(const Opnd_t &V) : Val(V) {} 2409 2410 template <typename OpTy> bool match(OpTy *V) { 2411 if (auto *I = dyn_cast<ExtractValueInst>(V)) { 2412 // If Ind is -1, don't inspect indices 2413 if (Ind != -1 && 2414 !(I->getNumIndices() == 1 && I->getIndices()[0] == (unsigned)Ind)) 2415 return false; 2416 return Val.match(I->getAggregateOperand()); 2417 } 2418 return false; 2419 } 2420 }; 2421 2422 /// Match a single index ExtractValue instruction. 2423 /// For example m_ExtractValue<1>(...) 2424 template <int Ind, typename Val_t> 2425 inline ExtractValue_match<Ind, Val_t> m_ExtractValue(const Val_t &V) { 2426 return ExtractValue_match<Ind, Val_t>(V); 2427 } 2428 2429 /// Match an ExtractValue instruction with any index. 2430 /// For example m_ExtractValue(...) 2431 template <typename Val_t> 2432 inline ExtractValue_match<-1, Val_t> m_ExtractValue(const Val_t &V) { 2433 return ExtractValue_match<-1, Val_t>(V); 2434 } 2435 2436 /// Matcher for a single index InsertValue instruction. 2437 template <int Ind, typename T0, typename T1> struct InsertValue_match { 2438 T0 Op0; 2439 T1 Op1; 2440 2441 InsertValue_match(const T0 &Op0, const T1 &Op1) : Op0(Op0), Op1(Op1) {} 2442 2443 template <typename OpTy> bool match(OpTy *V) { 2444 if (auto *I = dyn_cast<InsertValueInst>(V)) { 2445 return Op0.match(I->getOperand(0)) && Op1.match(I->getOperand(1)) && 2446 I->getNumIndices() == 1 && Ind == I->getIndices()[0]; 2447 } 2448 return false; 2449 } 2450 }; 2451 2452 /// Matches a single index InsertValue instruction. 2453 template <int Ind, typename Val_t, typename Elt_t> 2454 inline InsertValue_match<Ind, Val_t, Elt_t> m_InsertValue(const Val_t &Val, 2455 const Elt_t &Elt) { 2456 return InsertValue_match<Ind, Val_t, Elt_t>(Val, Elt); 2457 } 2458 2459 /// Matches patterns for `vscale`. This can either be a call to `llvm.vscale` or 2460 /// the constant expression 2461 /// `ptrtoint(gep <vscale x 1 x i8>, <vscale x 1 x i8>* null, i32 1>` 2462 /// under the right conditions determined by DataLayout. 2463 struct VScaleVal_match { 2464 const DataLayout &DL; 2465 VScaleVal_match(const DataLayout &DL) : DL(DL) {} 2466 2467 template <typename ITy> bool match(ITy *V) { 2468 if (m_Intrinsic<Intrinsic::vscale>().match(V)) 2469 return true; 2470 2471 Value *Ptr; 2472 if (m_PtrToInt(m_Value(Ptr)).match(V)) { 2473 if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) { 2474 auto *DerefTy = GEP->getSourceElementType(); 2475 if (GEP->getNumIndices() == 1 && isa<ScalableVectorType>(DerefTy) && 2476 m_Zero().match(GEP->getPointerOperand()) && 2477 m_SpecificInt(1).match(GEP->idx_begin()->get()) && 2478 DL.getTypeAllocSizeInBits(DerefTy).getKnownMinSize() == 8) 2479 return true; 2480 } 2481 } 2482 2483 return false; 2484 } 2485 }; 2486 2487 inline VScaleVal_match m_VScale(const DataLayout &DL) { 2488 return VScaleVal_match(DL); 2489 } 2490 2491 template <typename LHS, typename RHS, unsigned Opcode, bool Commutable = false> 2492 struct LogicalOp_match { 2493 LHS L; 2494 RHS R; 2495 2496 LogicalOp_match(const LHS &L, const RHS &R) : L(L), R(R) {} 2497 2498 template <typename T> bool match(T *V) { 2499 auto *I = dyn_cast<Instruction>(V); 2500 if (!I || !I->getType()->isIntOrIntVectorTy(1)) 2501 return false; 2502 2503 if (I->getOpcode() == Opcode) { 2504 auto *Op0 = I->getOperand(0); 2505 auto *Op1 = I->getOperand(1); 2506 return (L.match(Op0) && R.match(Op1)) || 2507 (Commutable && L.match(Op1) && R.match(Op0)); 2508 } 2509 2510 if (auto *Select = dyn_cast<SelectInst>(I)) { 2511 auto *Cond = Select->getCondition(); 2512 auto *TVal = Select->getTrueValue(); 2513 auto *FVal = Select->getFalseValue(); 2514 if (Opcode == Instruction::And) { 2515 auto *C = dyn_cast<Constant>(FVal); 2516 if (C && C->isNullValue()) 2517 return (L.match(Cond) && R.match(TVal)) || 2518 (Commutable && L.match(TVal) && R.match(Cond)); 2519 } else { 2520 assert(Opcode == Instruction::Or); 2521 auto *C = dyn_cast<Constant>(TVal); 2522 if (C && C->isOneValue()) 2523 return (L.match(Cond) && R.match(FVal)) || 2524 (Commutable && L.match(FVal) && R.match(Cond)); 2525 } 2526 } 2527 2528 return false; 2529 } 2530 }; 2531 2532 /// Matches L && R either in the form of L & R or L ? R : false. 2533 /// Note that the latter form is poison-blocking. 2534 template <typename LHS, typename RHS> 2535 inline LogicalOp_match<LHS, RHS, Instruction::And> 2536 m_LogicalAnd(const LHS &L, const RHS &R) { 2537 return LogicalOp_match<LHS, RHS, Instruction::And>(L, R); 2538 } 2539 2540 /// Matches L && R where L and R are arbitrary values. 2541 inline auto m_LogicalAnd() { return m_LogicalAnd(m_Value(), m_Value()); } 2542 2543 /// Matches L && R with LHS and RHS in either order. 2544 template <typename LHS, typename RHS> 2545 inline LogicalOp_match<LHS, RHS, Instruction::And, true> 2546 m_c_LogicalAnd(const LHS &L, const RHS &R) { 2547 return LogicalOp_match<LHS, RHS, Instruction::And, true>(L, R); 2548 } 2549 2550 /// Matches L || R either in the form of L | R or L ? true : R. 2551 /// Note that the latter form is poison-blocking. 2552 template <typename LHS, typename RHS> 2553 inline LogicalOp_match<LHS, RHS, Instruction::Or> 2554 m_LogicalOr(const LHS &L, const RHS &R) { 2555 return LogicalOp_match<LHS, RHS, Instruction::Or>(L, R); 2556 } 2557 2558 /// Matches L || R where L and R are arbitrary values. 2559 inline auto m_LogicalOr() { return m_LogicalOr(m_Value(), m_Value()); } 2560 2561 /// Matches L || R with LHS and RHS in either order. 2562 template <typename LHS, typename RHS> 2563 inline LogicalOp_match<LHS, RHS, Instruction::Or, true> 2564 m_c_LogicalOr(const LHS &L, const RHS &R) { 2565 return LogicalOp_match<LHS, RHS, Instruction::Or, true>(L, R); 2566 } 2567 2568 } // end namespace PatternMatch 2569 } // end namespace llvm 2570 2571 #endif // LLVM_IR_PATTERNMATCH_H 2572