include/llvm/IR/PatternMatch.h

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