1//===-- llvm/Support/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_SUPPORT_PATTERNMATCH_H 30#define LLVM_SUPPORT_PATTERNMATCH_H 31 32#include "llvm/Constants.h" 33#include "llvm/Instructions.h" 34#include "llvm/Operator.h" 35 36namespace llvm { 37namespace PatternMatch { 38 39template<typename Val, typename Pattern> 40bool match(Val *V, const Pattern &P) { 41 return const_cast<Pattern&>(P).match(V); 42} 43 44 45template<typename SubPattern_t> 46struct OneUse_match { 47 SubPattern_t SubPattern; 48 49 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {} 50 51 template<typename OpTy> 52 bool match(OpTy *V) { 53 return V->hasOneUse() && SubPattern.match(V); 54 } 55}; 56 57template<typename T> 58inline OneUse_match<T> m_OneUse(const T &SubPattern) { return SubPattern; } 59 60 61template<typename Class> 62struct class_match { 63 template<typename ITy> 64 bool match(ITy *V) { return isa<Class>(V); } 65}; 66 67/// m_Value() - Match an arbitrary value and ignore it. 68inline class_match<Value> m_Value() { return class_match<Value>(); } 69/// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it. 70inline class_match<ConstantInt> m_ConstantInt() { 71 return class_match<ConstantInt>(); 72} 73/// m_Undef() - Match an arbitrary undef constant. 74inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); } 75 76inline class_match<Constant> m_Constant() { return class_match<Constant>(); } 77 78struct match_zero { 79 template<typename ITy> 80 bool match(ITy *V) { 81 if (const Constant *C = dyn_cast<Constant>(V)) 82 return C->isNullValue(); 83 return false; 84 } 85}; 86 87/// m_Zero() - Match an arbitrary zero/null constant. This includes 88/// zero_initializer for vectors and ConstantPointerNull for pointers. 89inline match_zero m_Zero() { return match_zero(); } 90 91 92struct apint_match { 93 const APInt *&Res; 94 apint_match(const APInt *&R) : Res(R) {} 95 template<typename ITy> 96 bool match(ITy *V) { 97 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 98 Res = &CI->getValue(); 99 return true; 100 } 101 // FIXME: Remove this. 102 if (ConstantVector *CV = dyn_cast<ConstantVector>(V)) 103 if (ConstantInt *CI = 104 dyn_cast_or_null<ConstantInt>(CV->getSplatValue())) { 105 Res = &CI->getValue(); 106 return true; 107 } 108 if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(V)) 109 if (ConstantInt *CI = 110 dyn_cast_or_null<ConstantInt>(CV->getSplatValue())) { 111 Res = &CI->getValue(); 112 return true; 113 } 114 return false; 115 } 116}; 117 118/// m_APInt - Match a ConstantInt or splatted ConstantVector, binding the 119/// specified pointer to the contained APInt. 120inline apint_match m_APInt(const APInt *&Res) { return Res; } 121 122 123template<int64_t Val> 124struct constantint_match { 125 template<typename ITy> 126 bool match(ITy *V) { 127 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 128 const APInt &CIV = CI->getValue(); 129 if (Val >= 0) 130 return CIV == static_cast<uint64_t>(Val); 131 // If Val is negative, and CI is shorter than it, truncate to the right 132 // number of bits. If it is larger, then we have to sign extend. Just 133 // compare their negated values. 134 return -CIV == -Val; 135 } 136 return false; 137 } 138}; 139 140/// m_ConstantInt<int64_t> - Match a ConstantInt with a specific value. 141template<int64_t Val> 142inline constantint_match<Val> m_ConstantInt() { 143 return constantint_match<Val>(); 144} 145 146/// cst_pred_ty - This helper class is used to match scalar and vector constants 147/// that satisfy a specified predicate. 148template<typename Predicate> 149struct cst_pred_ty : public Predicate { 150 template<typename ITy> 151 bool match(ITy *V) { 152 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) 153 return this->isValue(CI->getValue()); 154 // FIXME: Remove this. 155 if (const ConstantVector *CV = dyn_cast<ConstantVector>(V)) 156 if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue())) 157 return this->isValue(CI->getValue()); 158 if (const ConstantDataVector *CV = dyn_cast<ConstantDataVector>(V)) 159 if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue())) 160 return this->isValue(CI->getValue()); 161 return false; 162 } 163}; 164 165/// api_pred_ty - This helper class is used to match scalar and vector constants 166/// that satisfy a specified predicate, and bind them to an APInt. 167template<typename Predicate> 168struct api_pred_ty : public Predicate { 169 const APInt *&Res; 170 api_pred_ty(const APInt *&R) : Res(R) {} 171 template<typename ITy> 172 bool match(ITy *V) { 173 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) 174 if (this->isValue(CI->getValue())) { 175 Res = &CI->getValue(); 176 return true; 177 } 178 179 // FIXME: remove. 180 if (const ConstantVector *CV = dyn_cast<ConstantVector>(V)) 181 if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue())) 182 if (this->isValue(CI->getValue())) { 183 Res = &CI->getValue(); 184 return true; 185 } 186 187 if (const ConstantDataVector *CV = dyn_cast<ConstantDataVector>(V)) 188 if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue())) 189 if (this->isValue(CI->getValue())) { 190 Res = &CI->getValue(); 191 return true; 192 } 193 194 return false; 195 } 196}; 197 198 199struct is_one { 200 bool isValue(const APInt &C) { return C == 1; } 201}; 202 203/// m_One() - Match an integer 1 or a vector with all elements equal to 1. 204inline cst_pred_ty<is_one> m_One() { return cst_pred_ty<is_one>(); } 205inline api_pred_ty<is_one> m_One(const APInt *&V) { return V; } 206 207struct is_all_ones { 208 bool isValue(const APInt &C) { return C.isAllOnesValue(); } 209}; 210 211/// m_AllOnes() - Match an integer or vector with all bits set to true. 212inline cst_pred_ty<is_all_ones> m_AllOnes() {return cst_pred_ty<is_all_ones>();} 213inline api_pred_ty<is_all_ones> m_AllOnes(const APInt *&V) { return V; } 214 215struct is_sign_bit { 216 bool isValue(const APInt &C) { return C.isSignBit(); } 217}; 218 219/// m_SignBit() - Match an integer or vector with only the sign bit(s) set. 220inline cst_pred_ty<is_sign_bit> m_SignBit() {return cst_pred_ty<is_sign_bit>();} 221inline api_pred_ty<is_sign_bit> m_SignBit(const APInt *&V) { return V; } 222 223struct is_power2 { 224 bool isValue(const APInt &C) { return C.isPowerOf2(); } 225}; 226 227/// m_Power2() - Match an integer or vector power of 2. 228inline cst_pred_ty<is_power2> m_Power2() { return cst_pred_ty<is_power2>(); } 229inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { return V; } 230 231template<typename Class> 232struct bind_ty { 233 Class *&VR; 234 bind_ty(Class *&V) : VR(V) {} 235 236 template<typename ITy> 237 bool match(ITy *V) { 238 if (Class *CV = dyn_cast<Class>(V)) { 239 VR = CV; 240 return true; 241 } 242 return false; 243 } 244}; 245 246/// m_Value - Match a value, capturing it if we match. 247inline bind_ty<Value> m_Value(Value *&V) { return V; } 248 249/// m_ConstantInt - Match a ConstantInt, capturing the value if we match. 250inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; } 251 252/// m_Constant - Match a Constant, capturing the value if we match. 253inline bind_ty<Constant> m_Constant(Constant *&C) { return C; } 254 255/// specificval_ty - Match a specified Value*. 256struct specificval_ty { 257 const Value *Val; 258 specificval_ty(const Value *V) : Val(V) {} 259 260 template<typename ITy> 261 bool match(ITy *V) { 262 return V == Val; 263 } 264}; 265 266/// m_Specific - Match if we have a specific specified value. 267inline specificval_ty m_Specific(const Value *V) { return V; } 268 269struct bind_const_intval_ty { 270 uint64_t &VR; 271 bind_const_intval_ty(uint64_t &V) : VR(V) {} 272 273 template<typename ITy> 274 bool match(ITy *V) { 275 if (ConstantInt *CV = dyn_cast<ConstantInt>(V)) 276 if (CV->getBitWidth() <= 64) { 277 VR = CV->getZExtValue(); 278 return true; 279 } 280 return false; 281 } 282}; 283 284/// m_ConstantInt - Match a ConstantInt and bind to its value. This does not 285/// match ConstantInts wider than 64-bits. 286inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; } 287 288//===----------------------------------------------------------------------===// 289// Matchers for specific binary operators. 290// 291 292template<typename LHS_t, typename RHS_t, unsigned Opcode> 293struct BinaryOp_match { 294 LHS_t L; 295 RHS_t R; 296 297 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 298 299 template<typename OpTy> 300 bool match(OpTy *V) { 301 if (V->getValueID() == Value::InstructionVal + Opcode) { 302 BinaryOperator *I = cast<BinaryOperator>(V); 303 return L.match(I->getOperand(0)) && R.match(I->getOperand(1)); 304 } 305 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 306 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) && 307 R.match(CE->getOperand(1)); 308 return false; 309 } 310}; 311 312template<typename LHS, typename RHS> 313inline BinaryOp_match<LHS, RHS, Instruction::Add> 314m_Add(const LHS &L, const RHS &R) { 315 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R); 316} 317 318template<typename LHS, typename RHS> 319inline BinaryOp_match<LHS, RHS, Instruction::FAdd> 320m_FAdd(const LHS &L, const RHS &R) { 321 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R); 322} 323 324template<typename LHS, typename RHS> 325inline BinaryOp_match<LHS, RHS, Instruction::Sub> 326m_Sub(const LHS &L, const RHS &R) { 327 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R); 328} 329 330template<typename LHS, typename RHS> 331inline BinaryOp_match<LHS, RHS, Instruction::FSub> 332m_FSub(const LHS &L, const RHS &R) { 333 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R); 334} 335 336template<typename LHS, typename RHS> 337inline BinaryOp_match<LHS, RHS, Instruction::Mul> 338m_Mul(const LHS &L, const RHS &R) { 339 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R); 340} 341 342template<typename LHS, typename RHS> 343inline BinaryOp_match<LHS, RHS, Instruction::FMul> 344m_FMul(const LHS &L, const RHS &R) { 345 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R); 346} 347 348template<typename LHS, typename RHS> 349inline BinaryOp_match<LHS, RHS, Instruction::UDiv> 350m_UDiv(const LHS &L, const RHS &R) { 351 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R); 352} 353 354template<typename LHS, typename RHS> 355inline BinaryOp_match<LHS, RHS, Instruction::SDiv> 356m_SDiv(const LHS &L, const RHS &R) { 357 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R); 358} 359 360template<typename LHS, typename RHS> 361inline BinaryOp_match<LHS, RHS, Instruction::FDiv> 362m_FDiv(const LHS &L, const RHS &R) { 363 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R); 364} 365 366template<typename LHS, typename RHS> 367inline BinaryOp_match<LHS, RHS, Instruction::URem> 368m_URem(const LHS &L, const RHS &R) { 369 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R); 370} 371 372template<typename LHS, typename RHS> 373inline BinaryOp_match<LHS, RHS, Instruction::SRem> 374m_SRem(const LHS &L, const RHS &R) { 375 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R); 376} 377 378template<typename LHS, typename RHS> 379inline BinaryOp_match<LHS, RHS, Instruction::FRem> 380m_FRem(const LHS &L, const RHS &R) { 381 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R); 382} 383 384template<typename LHS, typename RHS> 385inline BinaryOp_match<LHS, RHS, Instruction::And> 386m_And(const LHS &L, const RHS &R) { 387 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R); 388} 389 390template<typename LHS, typename RHS> 391inline BinaryOp_match<LHS, RHS, Instruction::Or> 392m_Or(const LHS &L, const RHS &R) { 393 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R); 394} 395 396template<typename LHS, typename RHS> 397inline BinaryOp_match<LHS, RHS, Instruction::Xor> 398m_Xor(const LHS &L, const RHS &R) { 399 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R); 400} 401 402template<typename LHS, typename RHS> 403inline BinaryOp_match<LHS, RHS, Instruction::Shl> 404m_Shl(const LHS &L, const RHS &R) { 405 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R); 406} 407 408template<typename LHS, typename RHS> 409inline BinaryOp_match<LHS, RHS, Instruction::LShr> 410m_LShr(const LHS &L, const RHS &R) { 411 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R); 412} 413 414template<typename LHS, typename RHS> 415inline BinaryOp_match<LHS, RHS, Instruction::AShr> 416m_AShr(const LHS &L, const RHS &R) { 417 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R); 418} 419 420//===----------------------------------------------------------------------===// 421// Class that matches two different binary ops. 422// 423template<typename LHS_t, typename RHS_t, unsigned Opc1, unsigned Opc2> 424struct BinOp2_match { 425 LHS_t L; 426 RHS_t R; 427 428 BinOp2_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} 429 430 template<typename OpTy> 431 bool match(OpTy *V) { 432 if (V->getValueID() == Value::InstructionVal + Opc1 || 433 V->getValueID() == Value::InstructionVal + Opc2) { 434 BinaryOperator *I = cast<BinaryOperator>(V); 435 return L.match(I->getOperand(0)) && R.match(I->getOperand(1)); 436 } 437 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 438 return (CE->getOpcode() == Opc1 || CE->getOpcode() == Opc2) && 439 L.match(CE->getOperand(0)) && R.match(CE->getOperand(1)); 440 return false; 441 } 442}; 443 444/// m_Shr - Matches LShr or AShr. 445template<typename LHS, typename RHS> 446inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr> 447m_Shr(const LHS &L, const RHS &R) { 448 return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr>(L, R); 449} 450 451/// m_LogicalShift - Matches LShr or Shl. 452template<typename LHS, typename RHS> 453inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl> 454m_LogicalShift(const LHS &L, const RHS &R) { 455 return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl>(L, R); 456} 457 458/// m_IDiv - Matches UDiv and SDiv. 459template<typename LHS, typename RHS> 460inline BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv> 461m_IDiv(const LHS &L, const RHS &R) { 462 return BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv>(L, R); 463} 464 465//===----------------------------------------------------------------------===// 466// Class that matches exact binary ops. 467// 468template<typename SubPattern_t> 469struct Exact_match { 470 SubPattern_t SubPattern; 471 472 Exact_match(const SubPattern_t &SP) : SubPattern(SP) {} 473 474 template<typename OpTy> 475 bool match(OpTy *V) { 476 if (PossiblyExactOperator *PEO = dyn_cast<PossiblyExactOperator>(V)) 477 return PEO->isExact() && SubPattern.match(V); 478 return false; 479 } 480}; 481 482template<typename T> 483inline Exact_match<T> m_Exact(const T &SubPattern) { return SubPattern; } 484 485//===----------------------------------------------------------------------===// 486// Matchers for CmpInst classes 487// 488 489template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy> 490struct CmpClass_match { 491 PredicateTy &Predicate; 492 LHS_t L; 493 RHS_t R; 494 495 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS) 496 : Predicate(Pred), L(LHS), R(RHS) {} 497 498 template<typename OpTy> 499 bool match(OpTy *V) { 500 if (Class *I = dyn_cast<Class>(V)) 501 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) { 502 Predicate = I->getPredicate(); 503 return true; 504 } 505 return false; 506 } 507}; 508 509template<typename LHS, typename RHS> 510inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate> 511m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 512 return CmpClass_match<LHS, RHS, 513 ICmpInst, ICmpInst::Predicate>(Pred, L, R); 514} 515 516template<typename LHS, typename RHS> 517inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate> 518m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) { 519 return CmpClass_match<LHS, RHS, 520 FCmpInst, FCmpInst::Predicate>(Pred, L, R); 521} 522 523//===----------------------------------------------------------------------===// 524// Matchers for SelectInst classes 525// 526 527template<typename Cond_t, typename LHS_t, typename RHS_t> 528struct SelectClass_match { 529 Cond_t C; 530 LHS_t L; 531 RHS_t R; 532 533 SelectClass_match(const Cond_t &Cond, const LHS_t &LHS, 534 const RHS_t &RHS) 535 : C(Cond), L(LHS), R(RHS) {} 536 537 template<typename OpTy> 538 bool match(OpTy *V) { 539 if (SelectInst *I = dyn_cast<SelectInst>(V)) 540 return C.match(I->getOperand(0)) && 541 L.match(I->getOperand(1)) && 542 R.match(I->getOperand(2)); 543 return false; 544 } 545}; 546 547template<typename Cond, typename LHS, typename RHS> 548inline SelectClass_match<Cond, LHS, RHS> 549m_Select(const Cond &C, const LHS &L, const RHS &R) { 550 return SelectClass_match<Cond, LHS, RHS>(C, L, R); 551} 552 553/// m_SelectCst - This matches a select of two constants, e.g.: 554/// m_SelectCst<-1, 0>(m_Value(V)) 555template<int64_t L, int64_t R, typename Cond> 556inline SelectClass_match<Cond, constantint_match<L>, constantint_match<R> > 557m_SelectCst(const Cond &C) { 558 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>()); 559} 560 561 562//===----------------------------------------------------------------------===// 563// Matchers for CastInst classes 564// 565 566template<typename Op_t, unsigned Opcode> 567struct CastClass_match { 568 Op_t Op; 569 570 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {} 571 572 template<typename OpTy> 573 bool match(OpTy *V) { 574 if (Operator *O = dyn_cast<Operator>(V)) 575 return O->getOpcode() == Opcode && Op.match(O->getOperand(0)); 576 return false; 577 } 578}; 579 580/// m_BitCast 581template<typename OpTy> 582inline CastClass_match<OpTy, Instruction::BitCast> 583m_BitCast(const OpTy &Op) { 584 return CastClass_match<OpTy, Instruction::BitCast>(Op); 585} 586 587/// m_PtrToInt 588template<typename OpTy> 589inline CastClass_match<OpTy, Instruction::PtrToInt> 590m_PtrToInt(const OpTy &Op) { 591 return CastClass_match<OpTy, Instruction::PtrToInt>(Op); 592} 593 594/// m_Trunc 595template<typename OpTy> 596inline CastClass_match<OpTy, Instruction::Trunc> 597m_Trunc(const OpTy &Op) { 598 return CastClass_match<OpTy, Instruction::Trunc>(Op); 599} 600 601/// m_SExt 602template<typename OpTy> 603inline CastClass_match<OpTy, Instruction::SExt> 604m_SExt(const OpTy &Op) { 605 return CastClass_match<OpTy, Instruction::SExt>(Op); 606} 607 608/// m_ZExt 609template<typename OpTy> 610inline CastClass_match<OpTy, Instruction::ZExt> 611m_ZExt(const OpTy &Op) { 612 return CastClass_match<OpTy, Instruction::ZExt>(Op); 613} 614 615 616//===----------------------------------------------------------------------===// 617// Matchers for unary operators 618// 619 620template<typename LHS_t> 621struct not_match { 622 LHS_t L; 623 624 not_match(const LHS_t &LHS) : L(LHS) {} 625 626 template<typename OpTy> 627 bool match(OpTy *V) { 628 if (Operator *O = dyn_cast<Operator>(V)) 629 if (O->getOpcode() == Instruction::Xor) 630 return matchIfNot(O->getOperand(0), O->getOperand(1)); 631 return false; 632 } 633private: 634 bool matchIfNot(Value *LHS, Value *RHS) { 635 return (isa<ConstantInt>(RHS) || isa<ConstantDataVector>(RHS) || 636 // FIXME: Remove CV. 637 isa<ConstantVector>(RHS)) && 638 cast<Constant>(RHS)->isAllOnesValue() && 639 L.match(LHS); 640 } 641}; 642 643template<typename LHS> 644inline not_match<LHS> m_Not(const LHS &L) { return L; } 645 646 647template<typename LHS_t> 648struct neg_match { 649 LHS_t L; 650 651 neg_match(const LHS_t &LHS) : L(LHS) {} 652 653 template<typename OpTy> 654 bool match(OpTy *V) { 655 if (Operator *O = dyn_cast<Operator>(V)) 656 if (O->getOpcode() == Instruction::Sub) 657 return matchIfNeg(O->getOperand(0), O->getOperand(1)); 658 return false; 659 } 660private: 661 bool matchIfNeg(Value *LHS, Value *RHS) { 662 return ((isa<ConstantInt>(LHS) && cast<ConstantInt>(LHS)->isZero()) || 663 isa<ConstantAggregateZero>(LHS)) && 664 L.match(RHS); 665 } 666}; 667 668/// m_Neg - Match an integer negate. 669template<typename LHS> 670inline neg_match<LHS> m_Neg(const LHS &L) { return L; } 671 672 673template<typename LHS_t> 674struct fneg_match { 675 LHS_t L; 676 677 fneg_match(const LHS_t &LHS) : L(LHS) {} 678 679 template<typename OpTy> 680 bool match(OpTy *V) { 681 if (Operator *O = dyn_cast<Operator>(V)) 682 if (O->getOpcode() == Instruction::FSub) 683 return matchIfFNeg(O->getOperand(0), O->getOperand(1)); 684 return false; 685 } 686private: 687 bool matchIfFNeg(Value *LHS, Value *RHS) { 688 if (ConstantFP *C = dyn_cast<ConstantFP>(LHS)) 689 return C->isNegativeZeroValue() && L.match(RHS); 690 return false; 691 } 692}; 693 694/// m_FNeg - Match a floating point negate. 695template<typename LHS> 696inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; } 697 698 699//===----------------------------------------------------------------------===// 700// Matchers for control flow. 701// 702 703template<typename Cond_t> 704struct brc_match { 705 Cond_t Cond; 706 BasicBlock *&T, *&F; 707 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f) 708 : Cond(C), T(t), F(f) { 709 } 710 711 template<typename OpTy> 712 bool match(OpTy *V) { 713 if (BranchInst *BI = dyn_cast<BranchInst>(V)) 714 if (BI->isConditional() && Cond.match(BI->getCondition())) { 715 T = BI->getSuccessor(0); 716 F = BI->getSuccessor(1); 717 return true; 718 } 719 return false; 720 } 721}; 722 723template<typename Cond_t> 724inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) { 725 return brc_match<Cond_t>(C, T, F); 726} 727 728 729//===----------------------------------------------------------------------===// 730// Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y). 731// 732 733template<typename LHS_t, typename RHS_t, typename Pred_t> 734struct MaxMin_match { 735 LHS_t L; 736 RHS_t R; 737 738 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) 739 : L(LHS), R(RHS) {} 740 741 template<typename OpTy> 742 bool match(OpTy *V) { 743 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x". 744 SelectInst *SI = dyn_cast<SelectInst>(V); 745 if (!SI) 746 return false; 747 ICmpInst *Cmp = dyn_cast<ICmpInst>(SI->getCondition()); 748 if (!Cmp) 749 return false; 750 // At this point we have a select conditioned on a comparison. Check that 751 // it is the values returned by the select that are being compared. 752 Value *TrueVal = SI->getTrueValue(); 753 Value *FalseVal = SI->getFalseValue(); 754 Value *LHS = Cmp->getOperand(0); 755 Value *RHS = Cmp->getOperand(1); 756 if ((TrueVal != LHS || FalseVal != RHS) && 757 (TrueVal != RHS || FalseVal != LHS)) 758 return false; 759 ICmpInst::Predicate Pred = LHS == TrueVal ? 760 Cmp->getPredicate() : Cmp->getSwappedPredicate(); 761 // Does "(x pred y) ? x : y" represent the desired max/min operation? 762 if (!Pred_t::match(Pred)) 763 return false; 764 // It does! Bind the operands. 765 return L.match(LHS) && R.match(RHS); 766 } 767}; 768 769/// smax_pred_ty - Helper class for identifying signed max predicates. 770struct smax_pred_ty { 771 static bool match(ICmpInst::Predicate Pred) { 772 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE; 773 } 774}; 775 776/// smin_pred_ty - Helper class for identifying signed min predicates. 777struct smin_pred_ty { 778 static bool match(ICmpInst::Predicate Pred) { 779 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE; 780 } 781}; 782 783/// umax_pred_ty - Helper class for identifying unsigned max predicates. 784struct umax_pred_ty { 785 static bool match(ICmpInst::Predicate Pred) { 786 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE; 787 } 788}; 789 790/// umin_pred_ty - Helper class for identifying unsigned min predicates. 791struct umin_pred_ty { 792 static bool match(ICmpInst::Predicate Pred) { 793 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE; 794 } 795}; 796 797template<typename LHS, typename RHS> 798inline MaxMin_match<LHS, RHS, smax_pred_ty> 799m_SMax(const LHS &L, const RHS &R) { 800 return MaxMin_match<LHS, RHS, smax_pred_ty>(L, R); 801} 802 803template<typename LHS, typename RHS> 804inline MaxMin_match<LHS, RHS, smin_pred_ty> 805m_SMin(const LHS &L, const RHS &R) { 806 return MaxMin_match<LHS, RHS, smin_pred_ty>(L, R); 807} 808 809template<typename LHS, typename RHS> 810inline MaxMin_match<LHS, RHS, umax_pred_ty> 811m_UMax(const LHS &L, const RHS &R) { 812 return MaxMin_match<LHS, RHS, umax_pred_ty>(L, R); 813} 814 815template<typename LHS, typename RHS> 816inline MaxMin_match<LHS, RHS, umin_pred_ty> 817m_UMin(const LHS &L, const RHS &R) { 818 return MaxMin_match<LHS, RHS, umin_pred_ty>(L, R); 819} 820 821} // end namespace PatternMatch 822} // end namespace llvm 823 824#endif 825