include/llvm/IR/PatternMatch.h

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