LCOV - code coverage report
Current view: top level - include/llvm/IR - PatternMatch.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 193 193 100.0 %
Date: 2018-05-20 00:06:23 Functions: 581 653 89.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13