contrib/llvm/include/llvm/IR/PatternMatch.h

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