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

Generated by: LCOV version 1.13