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