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