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 36 namespace llvm { 37 namespace PatternMatch { 38 39 template<typename Val, typename Pattern> 40 bool match(Val *V, const Pattern &P) { 41 return const_cast<Pattern&>(P).match(V); 42 } 43 44 45 template<typename SubPattern_t> 46 struct 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 57 template<typename T> 58 inline OneUse_match<T> m_OneUse(const T &SubPattern) { return SubPattern; } 59 60 61 template<typename Class> 62 struct 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. 68 inline class_match<Value> m_Value() { return class_match<Value>(); } 69 /// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it. 70 inline class_match<ConstantInt> m_ConstantInt() { 71 return class_match<ConstantInt>(); 72 } 73 /// m_Undef() - Match an arbitrary undef constant. 74 inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); } 75 76 inline class_match<Constant> m_Constant() { return class_match<Constant>(); } 77 78 struct 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. 89 inline match_zero m_Zero() { return match_zero(); } 90 91 92 struct 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. 120 inline apint_match m_APInt(const APInt *&Res) { return Res; } 121 122 123 template<int64_t Val> 124 struct 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. 141 template<int64_t Val> 142 inline 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. 148 template<typename Predicate> 149 struct 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. 167 template<typename Predicate> 168 struct 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 199 struct 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. 204 inline cst_pred_ty<is_one> m_One() { return cst_pred_ty<is_one>(); } 205 inline api_pred_ty<is_one> m_One(const APInt *&V) { return V; } 206 207 struct 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. 212 inline cst_pred_ty<is_all_ones> m_AllOnes() {return cst_pred_ty<is_all_ones>();} 213 inline api_pred_ty<is_all_ones> m_AllOnes(const APInt *&V) { return V; } 214 215 struct 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. 220 inline cst_pred_ty<is_sign_bit> m_SignBit() {return cst_pred_ty<is_sign_bit>();} 221 inline api_pred_ty<is_sign_bit> m_SignBit(const APInt *&V) { return V; } 222 223 struct is_power2 { 224 bool isValue(const APInt &C) { return C.isPowerOf2(); } 225 }; 226 227 /// m_Power2() - Match an integer or vector power of 2. 228 inline cst_pred_ty<is_power2> m_Power2() { return cst_pred_ty<is_power2>(); } 229 inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { return V; } 230 231 template<typename Class> 232 struct 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. 247 inline bind_ty<Value> m_Value(Value *&V) { return V; } 248 249 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match. 250 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; } 251 252 /// m_Constant - Match a Constant, capturing the value if we match. 253 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; } 254 255 /// specificval_ty - Match a specified Value*. 256 struct 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. 267 inline specificval_ty m_Specific(const Value *V) { return V; } 268 269 struct 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. 286 inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; } 287 288 //===----------------------------------------------------------------------===// 289 // Matchers for specific binary operators. 290 // 291 292 template<typename LHS_t, typename RHS_t, unsigned Opcode> 293 struct 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 312 template<typename LHS, typename RHS> 313 inline BinaryOp_match<LHS, RHS, Instruction::Add> 314 m_Add(const LHS &L, const RHS &R) { 315 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R); 316 } 317 318 template<typename LHS, typename RHS> 319 inline BinaryOp_match<LHS, RHS, Instruction::FAdd> 320 m_FAdd(const LHS &L, const RHS &R) { 321 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R); 322 } 323 324 template<typename LHS, typename RHS> 325 inline BinaryOp_match<LHS, RHS, Instruction::Sub> 326 m_Sub(const LHS &L, const RHS &R) { 327 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R); 328 } 329 330 template<typename LHS, typename RHS> 331 inline BinaryOp_match<LHS, RHS, Instruction::FSub> 332 m_FSub(const LHS &L, const RHS &R) { 333 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R); 334 } 335 336 template<typename LHS, typename RHS> 337 inline BinaryOp_match<LHS, RHS, Instruction::Mul> 338 m_Mul(const LHS &L, const RHS &R) { 339 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R); 340 } 341 342 template<typename LHS, typename RHS> 343 inline BinaryOp_match<LHS, RHS, Instruction::FMul> 344 m_FMul(const LHS &L, const RHS &R) { 345 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R); 346 } 347 348 template<typename LHS, typename RHS> 349 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> 350 m_UDiv(const LHS &L, const RHS &R) { 351 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R); 352 } 353 354 template<typename LHS, typename RHS> 355 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> 356 m_SDiv(const LHS &L, const RHS &R) { 357 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R); 358 } 359 360 template<typename LHS, typename RHS> 361 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> 362 m_FDiv(const LHS &L, const RHS &R) { 363 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R); 364 } 365 366 template<typename LHS, typename RHS> 367 inline BinaryOp_match<LHS, RHS, Instruction::URem> 368 m_URem(const LHS &L, const RHS &R) { 369 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R); 370 } 371 372 template<typename LHS, typename RHS> 373 inline BinaryOp_match<LHS, RHS, Instruction::SRem> 374 m_SRem(const LHS &L, const RHS &R) { 375 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R); 376 } 377 378 template<typename LHS, typename RHS> 379 inline BinaryOp_match<LHS, RHS, Instruction::FRem> 380 m_FRem(const LHS &L, const RHS &R) { 381 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R); 382 } 383 384 template<typename LHS, typename RHS> 385 inline BinaryOp_match<LHS, RHS, Instruction::And> 386 m_And(const LHS &L, const RHS &R) { 387 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R); 388 } 389 390 template<typename LHS, typename RHS> 391 inline BinaryOp_match<LHS, RHS, Instruction::Or> 392 m_Or(const LHS &L, const RHS &R) { 393 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R); 394 } 395 396 template<typename LHS, typename RHS> 397 inline BinaryOp_match<LHS, RHS, Instruction::Xor> 398 m_Xor(const LHS &L, const RHS &R) { 399 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R); 400 } 401 402 template<typename LHS, typename RHS> 403 inline BinaryOp_match<LHS, RHS, Instruction::Shl> 404 m_Shl(const LHS &L, const RHS &R) { 405 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R); 406 } 407 408 template<typename LHS, typename RHS> 409 inline BinaryOp_match<LHS, RHS, Instruction::LShr> 410 m_LShr(const LHS &L, const RHS &R) { 411 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R); 412 } 413 414 template<typename LHS, typename RHS> 415 inline BinaryOp_match<LHS, RHS, Instruction::AShr> 416 m_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 // 423 template<typename LHS_t, typename RHS_t, unsigned Opc1, unsigned Opc2> 424 struct 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. 445 template<typename LHS, typename RHS> 446 inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr> 447 m_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. 452 template<typename LHS, typename RHS> 453 inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl> 454 m_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. 459 template<typename LHS, typename RHS> 460 inline BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv> 461 m_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 // 468 template<typename SubPattern_t> 469 struct 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 482 template<typename T> 483 inline Exact_match<T> m_Exact(const T &SubPattern) { return SubPattern; } 484 485 //===----------------------------------------------------------------------===// 486 // Matchers for CmpInst classes 487 // 488 489 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy> 490 struct 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 509 template<typename LHS, typename RHS> 510 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate> 511 m_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 516 template<typename LHS, typename RHS> 517 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate> 518 m_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 527 template<typename Cond_t, typename LHS_t, typename RHS_t> 528 struct 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 547 template<typename Cond, typename LHS, typename RHS> 548 inline SelectClass_match<Cond, LHS, RHS> 549 m_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)) 555 template<int64_t L, int64_t R, typename Cond> 556 inline SelectClass_match<Cond, constantint_match<L>, constantint_match<R> > 557 m_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 566 template<typename Op_t, unsigned Opcode> 567 struct 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 581 template<typename OpTy> 582 inline CastClass_match<OpTy, Instruction::BitCast> 583 m_BitCast(const OpTy &Op) { 584 return CastClass_match<OpTy, Instruction::BitCast>(Op); 585 } 586 587 /// m_PtrToInt 588 template<typename OpTy> 589 inline CastClass_match<OpTy, Instruction::PtrToInt> 590 m_PtrToInt(const OpTy &Op) { 591 return CastClass_match<OpTy, Instruction::PtrToInt>(Op); 592 } 593 594 /// m_Trunc 595 template<typename OpTy> 596 inline CastClass_match<OpTy, Instruction::Trunc> 597 m_Trunc(const OpTy &Op) { 598 return CastClass_match<OpTy, Instruction::Trunc>(Op); 599 } 600 601 /// m_SExt 602 template<typename OpTy> 603 inline CastClass_match<OpTy, Instruction::SExt> 604 m_SExt(const OpTy &Op) { 605 return CastClass_match<OpTy, Instruction::SExt>(Op); 606 } 607 608 /// m_ZExt 609 template<typename OpTy> 610 inline CastClass_match<OpTy, Instruction::ZExt> 611 m_ZExt(const OpTy &Op) { 612 return CastClass_match<OpTy, Instruction::ZExt>(Op); 613 } 614 615 616 //===----------------------------------------------------------------------===// 617 // Matchers for unary operators 618 // 619 620 template<typename LHS_t> 621 struct 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 } 633 private: 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 643 template<typename LHS> 644 inline not_match<LHS> m_Not(const LHS &L) { return L; } 645 646 647 template<typename LHS_t> 648 struct 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 } 660 private: 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. 669 template<typename LHS> 670 inline neg_match<LHS> m_Neg(const LHS &L) { return L; } 671 672 673 template<typename LHS_t> 674 struct 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 } 686 private: 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. 695 template<typename LHS> 696 inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; } 697 698 699 //===----------------------------------------------------------------------===// 700 // Matchers for control flow. 701 // 702 703 template<typename Cond_t> 704 struct 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 723 template<typename Cond_t> 724 inline 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 733 template<typename LHS_t, typename RHS_t, typename Pred_t> 734 struct 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. 770 struct 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. 777 struct 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. 784 struct 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. 791 struct umin_pred_ty { 792 static bool match(ICmpInst::Predicate Pred) { 793 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE; 794 } 795 }; 796 797 template<typename LHS, typename RHS> 798 inline MaxMin_match<LHS, RHS, smax_pred_ty> 799 m_SMax(const LHS &L, const RHS &R) { 800 return MaxMin_match<LHS, RHS, smax_pred_ty>(L, R); 801 } 802 803 template<typename LHS, typename RHS> 804 inline MaxMin_match<LHS, RHS, smin_pred_ty> 805 m_SMin(const LHS &L, const RHS &R) { 806 return MaxMin_match<LHS, RHS, smin_pred_ty>(L, R); 807 } 808 809 template<typename LHS, typename RHS> 810 inline MaxMin_match<LHS, RHS, umax_pred_ty> 811 m_UMax(const LHS &L, const RHS &R) { 812 return MaxMin_match<LHS, RHS, umax_pred_ty>(L, R); 813 } 814 815 template<typename LHS, typename RHS> 816 inline MaxMin_match<LHS, RHS, umin_pred_ty> 817 m_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
