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