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