Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. //
  9. // This file provides a simple and efficient mechanism for performing general
  10. // tree-based pattern matches on the LLVM IR. The power of these routines is
  11. // that it allows you to write concise patterns that are expressive and easy to
  12. // understand. The other major advantage of this is that it allows you to
  13. // trivially capture/bind elements in the pattern to variables. For example,
  14. // you can do something like this:
  15. //
  16. //  Value *Exp = ...
  17. //  Value *X, *Y;  ConstantInt *C1, *C2;      // (X & C1) | (Y & C2)
  18. //  if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
  19. //                      m_And(m_Value(Y), m_ConstantInt(C2))))) {
  20. //    ... Pattern is matched and variables are bound ...
  21. //  }
  22. //
  23. // This is primarily useful to things like the instruction combiner, but can
  24. // also be useful for static analysis tools or code generators.
  25. //
  26. //===----------------------------------------------------------------------===//
  27.  
  28. #ifndef LLVM_IR_PATTERNMATCH_H
  29. #define LLVM_IR_PATTERNMATCH_H
  30.  
  31. #include "llvm/ADT/APFloat.h"
  32. #include "llvm/ADT/APInt.h"
  33. #include "llvm/IR/Constant.h"
  34. #include "llvm/IR/Constants.h"
  35. #include "llvm/IR/DataLayout.h"
  36. #include "llvm/IR/InstrTypes.h"
  37. #include "llvm/IR/Instruction.h"
  38. #include "llvm/IR/Instructions.h"
  39. #include "llvm/IR/IntrinsicInst.h"
  40. #include "llvm/IR/Intrinsics.h"
  41. #include "llvm/IR/Operator.h"
  42. #include "llvm/IR/Value.h"
  43. #include "llvm/Support/Casting.h"
  44. #include <cstdint>
  45.  
  46. namespace llvm {
  47. namespace PatternMatch {
  48.  
  49. template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
  50.   return const_cast<Pattern &>(P).match(V);
  51. }
  52.  
  53. template <typename Pattern> bool match(ArrayRef<int> Mask, const Pattern &P) {
  54.   return const_cast<Pattern &>(P).match(Mask);
  55. }
  56.  
  57. template <typename SubPattern_t> struct OneUse_match {
  58.   SubPattern_t SubPattern;
  59.  
  60.   OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
  61.  
  62.   template <typename OpTy> bool match(OpTy *V) {
  63.     return V->hasOneUse() && SubPattern.match(V);
  64.   }
  65. };
  66.  
  67. template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
  68.   return SubPattern;
  69. }
  70.  
  71. template <typename Class> struct class_match {
  72.   template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
  73. };
  74.  
  75. /// Match an arbitrary value and ignore it.
  76. inline class_match<Value> m_Value() { return class_match<Value>(); }
  77.  
  78. /// Match an arbitrary unary operation and ignore it.
  79. inline class_match<UnaryOperator> m_UnOp() {
  80.   return class_match<UnaryOperator>();
  81. }
  82.  
  83. /// Match an arbitrary binary operation and ignore it.
  84. inline class_match<BinaryOperator> m_BinOp() {
  85.   return class_match<BinaryOperator>();
  86. }
  87.  
  88. /// Matches any compare instruction and ignore it.
  89. inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); }
  90.  
  91. struct undef_match {
  92.   static bool check(const Value *V) {
  93.     if (isa<UndefValue>(V))
  94.       return true;
  95.  
  96.     const auto *CA = dyn_cast<ConstantAggregate>(V);
  97.     if (!CA)
  98.       return false;
  99.  
  100.     SmallPtrSet<const ConstantAggregate *, 8> Seen;
  101.     SmallVector<const ConstantAggregate *, 8> Worklist;
  102.  
  103.     // Either UndefValue, PoisonValue, or an aggregate that only contains
  104.     // these is accepted by matcher.
  105.     // CheckValue returns false if CA cannot satisfy this constraint.
  106.     auto CheckValue = [&](const ConstantAggregate *CA) {
  107.       for (const Value *Op : CA->operand_values()) {
  108.         if (isa<UndefValue>(Op))
  109.           continue;
  110.  
  111.         const auto *CA = dyn_cast<ConstantAggregate>(Op);
  112.         if (!CA)
  113.           return false;
  114.         if (Seen.insert(CA).second)
  115.           Worklist.emplace_back(CA);
  116.       }
  117.  
  118.       return true;
  119.     };
  120.  
  121.     if (!CheckValue(CA))
  122.       return false;
  123.  
  124.     while (!Worklist.empty()) {
  125.       if (!CheckValue(Worklist.pop_back_val()))
  126.         return false;
  127.     }
  128.     return true;
  129.   }
  130.   template <typename ITy> bool match(ITy *V) { return check(V); }
  131. };
  132.  
  133. /// Match an arbitrary undef constant. This matches poison as well.
  134. /// If this is an aggregate and contains a non-aggregate element that is
  135. /// neither undef nor poison, the aggregate is not matched.
  136. inline auto m_Undef() { return undef_match(); }
  137.  
  138. /// Match an arbitrary poison constant.
  139. inline class_match<PoisonValue> m_Poison() {
  140.   return class_match<PoisonValue>();
  141. }
  142.  
  143. /// Match an arbitrary Constant and ignore it.
  144. inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
  145.  
  146. /// Match an arbitrary ConstantInt and ignore it.
  147. inline class_match<ConstantInt> m_ConstantInt() {
  148.   return class_match<ConstantInt>();
  149. }
  150.  
  151. /// Match an arbitrary ConstantFP and ignore it.
  152. inline class_match<ConstantFP> m_ConstantFP() {
  153.   return class_match<ConstantFP>();
  154. }
  155.  
  156. struct constantexpr_match {
  157.   template <typename ITy> bool match(ITy *V) {
  158.     auto *C = dyn_cast<Constant>(V);
  159.     return C && (isa<ConstantExpr>(C) || C->containsConstantExpression());
  160.   }
  161. };
  162.  
  163. /// Match a constant expression or a constant that contains a constant
  164. /// expression.
  165. inline constantexpr_match m_ConstantExpr() { return constantexpr_match(); }
  166.  
  167. /// Match an arbitrary basic block value and ignore it.
  168. inline class_match<BasicBlock> m_BasicBlock() {
  169.   return class_match<BasicBlock>();
  170. }
  171.  
  172. /// Inverting matcher
  173. template <typename Ty> struct match_unless {
  174.   Ty M;
  175.  
  176.   match_unless(const Ty &Matcher) : M(Matcher) {}
  177.  
  178.   template <typename ITy> bool match(ITy *V) { return !M.match(V); }
  179. };
  180.  
  181. /// Match if the inner matcher does *NOT* match.
  182. template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
  183.   return match_unless<Ty>(M);
  184. }
  185.  
  186. /// Matching combinators
  187. template <typename LTy, typename RTy> struct match_combine_or {
  188.   LTy L;
  189.   RTy R;
  190.  
  191.   match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
  192.  
  193.   template <typename ITy> bool match(ITy *V) {
  194.     if (L.match(V))
  195.       return true;
  196.     if (R.match(V))
  197.       return true;
  198.     return false;
  199.   }
  200. };
  201.  
  202. template <typename LTy, typename RTy> struct match_combine_and {
  203.   LTy L;
  204.   RTy R;
  205.  
  206.   match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
  207.  
  208.   template <typename ITy> bool match(ITy *V) {
  209.     if (L.match(V))
  210.       if (R.match(V))
  211.         return true;
  212.     return false;
  213.   }
  214. };
  215.  
  216. /// Combine two pattern matchers matching L || R
  217. template <typename LTy, typename RTy>
  218. inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
  219.   return match_combine_or<LTy, RTy>(L, R);
  220. }
  221.  
  222. /// Combine two pattern matchers matching L && R
  223. template <typename LTy, typename RTy>
  224. inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
  225.   return match_combine_and<LTy, RTy>(L, R);
  226. }
  227.  
  228. struct apint_match {
  229.   const APInt *&Res;
  230.   bool AllowUndef;
  231.  
  232.   apint_match(const APInt *&Res, bool AllowUndef)
  233.       : Res(Res), AllowUndef(AllowUndef) {}
  234.  
  235.   template <typename ITy> bool match(ITy *V) {
  236.     if (auto *CI = dyn_cast<ConstantInt>(V)) {
  237.       Res = &CI->getValue();
  238.       return true;
  239.     }
  240.     if (V->getType()->isVectorTy())
  241.       if (const auto *C = dyn_cast<Constant>(V))
  242.         if (auto *CI =
  243.                 dyn_cast_or_null<ConstantInt>(C->getSplatValue(AllowUndef))) {
  244.           Res = &CI->getValue();
  245.           return true;
  246.         }
  247.     return false;
  248.   }
  249. };
  250. // Either constexpr if or renaming ConstantFP::getValueAPF to
  251. // ConstantFP::getValue is needed to do it via single template
  252. // function for both apint/apfloat.
  253. struct apfloat_match {
  254.   const APFloat *&Res;
  255.   bool AllowUndef;
  256.  
  257.   apfloat_match(const APFloat *&Res, bool AllowUndef)
  258.       : Res(Res), AllowUndef(AllowUndef) {}
  259.  
  260.   template <typename ITy> bool match(ITy *V) {
  261.     if (auto *CI = dyn_cast<ConstantFP>(V)) {
  262.       Res = &CI->getValueAPF();
  263.       return true;
  264.     }
  265.     if (V->getType()->isVectorTy())
  266.       if (const auto *C = dyn_cast<Constant>(V))
  267.         if (auto *CI =
  268.                 dyn_cast_or_null<ConstantFP>(C->getSplatValue(AllowUndef))) {
  269.           Res = &CI->getValueAPF();
  270.           return true;
  271.         }
  272.     return false;
  273.   }
  274. };
  275.  
  276. /// Match a ConstantInt or splatted ConstantVector, binding the
  277. /// specified pointer to the contained APInt.
  278. inline apint_match m_APInt(const APInt *&Res) {
  279.   // Forbid undefs by default to maintain previous behavior.
  280.   return apint_match(Res, /* AllowUndef */ false);
  281. }
  282.  
  283. /// Match APInt while allowing undefs in splat vector constants.
  284. inline apint_match m_APIntAllowUndef(const APInt *&Res) {
  285.   return apint_match(Res, /* AllowUndef */ true);
  286. }
  287.  
  288. /// Match APInt while forbidding undefs in splat vector constants.
  289. inline apint_match m_APIntForbidUndef(const APInt *&Res) {
  290.   return apint_match(Res, /* AllowUndef */ false);
  291. }
  292.  
  293. /// Match a ConstantFP or splatted ConstantVector, binding the
  294. /// specified pointer to the contained APFloat.
  295. inline apfloat_match m_APFloat(const APFloat *&Res) {
  296.   // Forbid undefs by default to maintain previous behavior.
  297.   return apfloat_match(Res, /* AllowUndef */ false);
  298. }
  299.  
  300. /// Match APFloat while allowing undefs in splat vector constants.
  301. inline apfloat_match m_APFloatAllowUndef(const APFloat *&Res) {
  302.   return apfloat_match(Res, /* AllowUndef */ true);
  303. }
  304.  
  305. /// Match APFloat while forbidding undefs in splat vector constants.
  306. inline apfloat_match m_APFloatForbidUndef(const APFloat *&Res) {
  307.   return apfloat_match(Res, /* AllowUndef */ false);
  308. }
  309.  
  310. template <int64_t Val> struct constantint_match {
  311.   template <typename ITy> bool match(ITy *V) {
  312.     if (const auto *CI = dyn_cast<ConstantInt>(V)) {
  313.       const APInt &CIV = CI->getValue();
  314.       if (Val >= 0)
  315.         return CIV == static_cast<uint64_t>(Val);
  316.       // If Val is negative, and CI is shorter than it, truncate to the right
  317.       // number of bits.  If it is larger, then we have to sign extend.  Just
  318.       // compare their negated values.
  319.       return -CIV == -Val;
  320.     }
  321.     return false;
  322.   }
  323. };
  324.  
  325. /// Match a ConstantInt with a specific value.
  326. template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
  327.   return constantint_match<Val>();
  328. }
  329.  
  330. /// This helper class is used to match constant scalars, vector splats,
  331. /// and fixed width vectors that satisfy a specified predicate.
  332. /// For fixed width vector constants, undefined elements are ignored.
  333. template <typename Predicate, typename ConstantVal>
  334. struct cstval_pred_ty : public Predicate {
  335.   template <typename ITy> bool match(ITy *V) {
  336.     if (const auto *CV = dyn_cast<ConstantVal>(V))
  337.       return this->isValue(CV->getValue());
  338.     if (const auto *VTy = dyn_cast<VectorType>(V->getType())) {
  339.       if (const auto *C = dyn_cast<Constant>(V)) {
  340.         if (const auto *CV = dyn_cast_or_null<ConstantVal>(C->getSplatValue()))
  341.           return this->isValue(CV->getValue());
  342.  
  343.         // Number of elements of a scalable vector unknown at compile time
  344.         auto *FVTy = dyn_cast<FixedVectorType>(VTy);
  345.         if (!FVTy)
  346.           return false;
  347.  
  348.         // Non-splat vector constant: check each element for a match.
  349.         unsigned NumElts = FVTy->getNumElements();
  350.         assert(NumElts != 0 && "Constant vector with no elements?");
  351.         bool HasNonUndefElements = false;
  352.         for (unsigned i = 0; i != NumElts; ++i) {
  353.           Constant *Elt = C->getAggregateElement(i);
  354.           if (!Elt)
  355.             return false;
  356.           if (isa<UndefValue>(Elt))
  357.             continue;
  358.           auto *CV = dyn_cast<ConstantVal>(Elt);
  359.           if (!CV || !this->isValue(CV->getValue()))
  360.             return false;
  361.           HasNonUndefElements = true;
  362.         }
  363.         return HasNonUndefElements;
  364.       }
  365.     }
  366.     return false;
  367.   }
  368. };
  369.  
  370. /// specialization of cstval_pred_ty for ConstantInt
  371. template <typename Predicate>
  372. using cst_pred_ty = cstval_pred_ty<Predicate, ConstantInt>;
  373.  
  374. /// specialization of cstval_pred_ty for ConstantFP
  375. template <typename Predicate>
  376. using cstfp_pred_ty = cstval_pred_ty<Predicate, ConstantFP>;
  377.  
  378. /// This helper class is used to match scalar and vector constants that
  379. /// satisfy a specified predicate, and bind them to an APInt.
  380. template <typename Predicate> struct api_pred_ty : public Predicate {
  381.   const APInt *&Res;
  382.  
  383.   api_pred_ty(const APInt *&R) : Res(R) {}
  384.  
  385.   template <typename ITy> bool match(ITy *V) {
  386.     if (const auto *CI = dyn_cast<ConstantInt>(V))
  387.       if (this->isValue(CI->getValue())) {
  388.         Res = &CI->getValue();
  389.         return true;
  390.       }
  391.     if (V->getType()->isVectorTy())
  392.       if (const auto *C = dyn_cast<Constant>(V))
  393.         if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
  394.           if (this->isValue(CI->getValue())) {
  395.             Res = &CI->getValue();
  396.             return true;
  397.           }
  398.  
  399.     return false;
  400.   }
  401. };
  402.  
  403. /// This helper class is used to match scalar and vector constants that
  404. /// satisfy a specified predicate, and bind them to an APFloat.
  405. /// Undefs are allowed in splat vector constants.
  406. template <typename Predicate> struct apf_pred_ty : public Predicate {
  407.   const APFloat *&Res;
  408.  
  409.   apf_pred_ty(const APFloat *&R) : Res(R) {}
  410.  
  411.   template <typename ITy> bool match(ITy *V) {
  412.     if (const auto *CI = dyn_cast<ConstantFP>(V))
  413.       if (this->isValue(CI->getValue())) {
  414.         Res = &CI->getValue();
  415.         return true;
  416.       }
  417.     if (V->getType()->isVectorTy())
  418.       if (const auto *C = dyn_cast<Constant>(V))
  419.         if (auto *CI = dyn_cast_or_null<ConstantFP>(
  420.                 C->getSplatValue(/* AllowUndef */ true)))
  421.           if (this->isValue(CI->getValue())) {
  422.             Res = &CI->getValue();
  423.             return true;
  424.           }
  425.  
  426.     return false;
  427.   }
  428. };
  429.  
  430. ///////////////////////////////////////////////////////////////////////////////
  431. //
  432. // Encapsulate constant value queries for use in templated predicate matchers.
  433. // This allows checking if constants match using compound predicates and works
  434. // with vector constants, possibly with relaxed constraints. For example, ignore
  435. // undef values.
  436. //
  437. ///////////////////////////////////////////////////////////////////////////////
  438.  
  439. struct is_any_apint {
  440.   bool isValue(const APInt &C) { return true; }
  441. };
  442. /// Match an integer or vector with any integral constant.
  443. /// For vectors, this includes constants with undefined elements.
  444. inline cst_pred_ty<is_any_apint> m_AnyIntegralConstant() {
  445.   return cst_pred_ty<is_any_apint>();
  446. }
  447.  
  448. struct is_all_ones {
  449.   bool isValue(const APInt &C) { return C.isAllOnes(); }
  450. };
  451. /// Match an integer or vector with all bits set.
  452. /// For vectors, this includes constants with undefined elements.
  453. inline cst_pred_ty<is_all_ones> m_AllOnes() {
  454.   return cst_pred_ty<is_all_ones>();
  455. }
  456.  
  457. struct is_maxsignedvalue {
  458.   bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
  459. };
  460. /// Match an integer or vector with values having all bits except for the high
  461. /// bit set (0x7f...).
  462. /// For vectors, this includes constants with undefined elements.
  463. inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() {
  464.   return cst_pred_ty<is_maxsignedvalue>();
  465. }
  466. inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) {
  467.   return V;
  468. }
  469.  
  470. struct is_negative {
  471.   bool isValue(const APInt &C) { return C.isNegative(); }
  472. };
  473. /// Match an integer or vector of negative values.
  474. /// For vectors, this includes constants with undefined elements.
  475. inline cst_pred_ty<is_negative> m_Negative() {
  476.   return cst_pred_ty<is_negative>();
  477. }
  478. inline api_pred_ty<is_negative> m_Negative(const APInt *&V) { return V; }
  479.  
  480. struct is_nonnegative {
  481.   bool isValue(const APInt &C) { return C.isNonNegative(); }
  482. };
  483. /// Match an integer or vector of non-negative values.
  484. /// For vectors, this includes constants with undefined elements.
  485. inline cst_pred_ty<is_nonnegative> m_NonNegative() {
  486.   return cst_pred_ty<is_nonnegative>();
  487. }
  488. inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) { return V; }
  489.  
  490. struct is_strictlypositive {
  491.   bool isValue(const APInt &C) { return C.isStrictlyPositive(); }
  492. };
  493. /// Match an integer or vector of strictly positive values.
  494. /// For vectors, this includes constants with undefined elements.
  495. inline cst_pred_ty<is_strictlypositive> m_StrictlyPositive() {
  496.   return cst_pred_ty<is_strictlypositive>();
  497. }
  498. inline api_pred_ty<is_strictlypositive> m_StrictlyPositive(const APInt *&V) {
  499.   return V;
  500. }
  501.  
  502. struct is_nonpositive {
  503.   bool isValue(const APInt &C) { return C.isNonPositive(); }
  504. };
  505. /// Match an integer or vector of non-positive values.
  506. /// For vectors, this includes constants with undefined elements.
  507. inline cst_pred_ty<is_nonpositive> m_NonPositive() {
  508.   return cst_pred_ty<is_nonpositive>();
  509. }
  510. inline api_pred_ty<is_nonpositive> m_NonPositive(const APInt *&V) { return V; }
  511.  
  512. struct is_one {
  513.   bool isValue(const APInt &C) { return C.isOne(); }
  514. };
  515. /// Match an integer 1 or a vector with all elements equal to 1.
  516. /// For vectors, this includes constants with undefined elements.
  517. inline cst_pred_ty<is_one> m_One() { return cst_pred_ty<is_one>(); }
  518.  
  519. struct is_zero_int {
  520.   bool isValue(const APInt &C) { return C.isZero(); }
  521. };
  522. /// Match an integer 0 or a vector with all elements equal to 0.
  523. /// For vectors, this includes constants with undefined elements.
  524. inline cst_pred_ty<is_zero_int> m_ZeroInt() {
  525.   return cst_pred_ty<is_zero_int>();
  526. }
  527.  
  528. struct is_zero {
  529.   template <typename ITy> bool match(ITy *V) {
  530.     auto *C = dyn_cast<Constant>(V);
  531.     // FIXME: this should be able to do something for scalable vectors
  532.     return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
  533.   }
  534. };
  535. /// Match any null constant or a vector with all elements equal to 0.
  536. /// For vectors, this includes constants with undefined elements.
  537. inline is_zero m_Zero() { return is_zero(); }
  538.  
  539. struct is_power2 {
  540.   bool isValue(const APInt &C) { return C.isPowerOf2(); }
  541. };
  542. /// Match an integer or vector power-of-2.
  543. /// For vectors, this includes constants with undefined elements.
  544. inline cst_pred_ty<is_power2> m_Power2() { return cst_pred_ty<is_power2>(); }
  545. inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { return V; }
  546.  
  547. struct is_negated_power2 {
  548.   bool isValue(const APInt &C) { return C.isNegatedPowerOf2(); }
  549. };
  550. /// Match a integer or vector negated power-of-2.
  551. /// For vectors, this includes constants with undefined elements.
  552. inline cst_pred_ty<is_negated_power2> m_NegatedPower2() {
  553.   return cst_pred_ty<is_negated_power2>();
  554. }
  555. inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) {
  556.   return V;
  557. }
  558.  
  559. struct is_power2_or_zero {
  560.   bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
  561. };
  562. /// Match an integer or vector of 0 or power-of-2 values.
  563. /// For vectors, this includes constants with undefined elements.
  564. inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() {
  565.   return cst_pred_ty<is_power2_or_zero>();
  566. }
  567. inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) {
  568.   return V;
  569. }
  570.  
  571. struct is_sign_mask {
  572.   bool isValue(const APInt &C) { return C.isSignMask(); }
  573. };
  574. /// Match an integer or vector with only the sign bit(s) set.
  575. /// For vectors, this includes constants with undefined elements.
  576. inline cst_pred_ty<is_sign_mask> m_SignMask() {
  577.   return cst_pred_ty<is_sign_mask>();
  578. }
  579.  
  580. struct is_lowbit_mask {
  581.   bool isValue(const APInt &C) { return C.isMask(); }
  582. };
  583. /// Match an integer or vector with only the low bit(s) set.
  584. /// For vectors, this includes constants with undefined elements.
  585. inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
  586.   return cst_pred_ty<is_lowbit_mask>();
  587. }
  588. inline api_pred_ty<is_lowbit_mask> m_LowBitMask(const APInt *&V) { return V; }
  589.  
  590. struct icmp_pred_with_threshold {
  591.   ICmpInst::Predicate Pred;
  592.   const APInt *Thr;
  593.   bool isValue(const APInt &C) { return ICmpInst::compare(C, *Thr, Pred); }
  594. };
  595. /// Match an integer or vector with every element comparing 'pred' (eg/ne/...)
  596. /// to Threshold. For vectors, this includes constants with undefined elements.
  597. inline cst_pred_ty<icmp_pred_with_threshold>
  598. m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold) {
  599.   cst_pred_ty<icmp_pred_with_threshold> P;
  600.   P.Pred = Predicate;
  601.   P.Thr = &Threshold;
  602.   return P;
  603. }
  604.  
  605. struct is_nan {
  606.   bool isValue(const APFloat &C) { return C.isNaN(); }
  607. };
  608. /// Match an arbitrary NaN constant. This includes quiet and signalling nans.
  609. /// For vectors, this includes constants with undefined elements.
  610. inline cstfp_pred_ty<is_nan> m_NaN() { return cstfp_pred_ty<is_nan>(); }
  611.  
  612. struct is_nonnan {
  613.   bool isValue(const APFloat &C) { return !C.isNaN(); }
  614. };
  615. /// Match a non-NaN FP constant.
  616. /// For vectors, this includes constants with undefined elements.
  617. inline cstfp_pred_ty<is_nonnan> m_NonNaN() {
  618.   return cstfp_pred_ty<is_nonnan>();
  619. }
  620.  
  621. struct is_inf {
  622.   bool isValue(const APFloat &C) { return C.isInfinity(); }
  623. };
  624. /// Match a positive or negative infinity FP constant.
  625. /// For vectors, this includes constants with undefined elements.
  626. inline cstfp_pred_ty<is_inf> m_Inf() { return cstfp_pred_ty<is_inf>(); }
  627.  
  628. struct is_noninf {
  629.   bool isValue(const APFloat &C) { return !C.isInfinity(); }
  630. };
  631. /// Match a non-infinity FP constant, i.e. finite or NaN.
  632. /// For vectors, this includes constants with undefined elements.
  633. inline cstfp_pred_ty<is_noninf> m_NonInf() {
  634.   return cstfp_pred_ty<is_noninf>();
  635. }
  636.  
  637. struct is_finite {
  638.   bool isValue(const APFloat &C) { return C.isFinite(); }
  639. };
  640. /// Match a finite FP constant, i.e. not infinity or NaN.
  641. /// For vectors, this includes constants with undefined elements.
  642. inline cstfp_pred_ty<is_finite> m_Finite() {
  643.   return cstfp_pred_ty<is_finite>();
  644. }
  645. inline apf_pred_ty<is_finite> m_Finite(const APFloat *&V) { return V; }
  646.  
  647. struct is_finitenonzero {
  648.   bool isValue(const APFloat &C) { return C.isFiniteNonZero(); }
  649. };
  650. /// Match a finite non-zero FP constant.
  651. /// For vectors, this includes constants with undefined elements.
  652. inline cstfp_pred_ty<is_finitenonzero> m_FiniteNonZero() {
  653.   return cstfp_pred_ty<is_finitenonzero>();
  654. }
  655. inline apf_pred_ty<is_finitenonzero> m_FiniteNonZero(const APFloat *&V) {
  656.   return V;
  657. }
  658.  
  659. struct is_any_zero_fp {
  660.   bool isValue(const APFloat &C) { return C.isZero(); }
  661. };
  662. /// Match a floating-point negative zero or positive zero.
  663. /// For vectors, this includes constants with undefined elements.
  664. inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() {
  665.   return cstfp_pred_ty<is_any_zero_fp>();
  666. }
  667.  
  668. struct is_pos_zero_fp {
  669.   bool isValue(const APFloat &C) { return C.isPosZero(); }
  670. };
  671. /// Match a floating-point positive zero.
  672. /// For vectors, this includes constants with undefined elements.
  673. inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() {
  674.   return cstfp_pred_ty<is_pos_zero_fp>();
  675. }
  676.  
  677. struct is_neg_zero_fp {
  678.   bool isValue(const APFloat &C) { return C.isNegZero(); }
  679. };
  680. /// Match a floating-point negative zero.
  681. /// For vectors, this includes constants with undefined elements.
  682. inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() {
  683.   return cstfp_pred_ty<is_neg_zero_fp>();
  684. }
  685.  
  686. struct is_non_zero_fp {
  687.   bool isValue(const APFloat &C) { return C.isNonZero(); }
  688. };
  689. /// Match a floating-point non-zero.
  690. /// For vectors, this includes constants with undefined elements.
  691. inline cstfp_pred_ty<is_non_zero_fp> m_NonZeroFP() {
  692.   return cstfp_pred_ty<is_non_zero_fp>();
  693. }
  694.  
  695. ///////////////////////////////////////////////////////////////////////////////
  696.  
  697. template <typename Class> struct bind_ty {
  698.   Class *&VR;
  699.  
  700.   bind_ty(Class *&V) : VR(V) {}
  701.  
  702.   template <typename ITy> bool match(ITy *V) {
  703.     if (auto *CV = dyn_cast<Class>(V)) {
  704.       VR = CV;
  705.       return true;
  706.     }
  707.     return false;
  708.   }
  709. };
  710.  
  711. /// Match a value, capturing it if we match.
  712. inline bind_ty<Value> m_Value(Value *&V) { return V; }
  713. inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
  714.  
  715. /// Match an instruction, capturing it if we match.
  716. inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
  717. /// Match a unary operator, capturing it if we match.
  718. inline bind_ty<UnaryOperator> m_UnOp(UnaryOperator *&I) { return I; }
  719. /// Match a binary operator, capturing it if we match.
  720. inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
  721. /// Match a with overflow intrinsic, capturing it if we match.
  722. inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) {
  723.   return I;
  724. }
  725. inline bind_ty<const WithOverflowInst>
  726. m_WithOverflowInst(const WithOverflowInst *&I) {
  727.   return I;
  728. }
  729.  
  730. /// Match a Constant, capturing the value if we match.
  731. inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
  732.  
  733. /// Match a ConstantInt, capturing the value if we match.
  734. inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
  735.  
  736. /// Match a ConstantFP, capturing the value if we match.
  737. inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; }
  738.  
  739. /// Match a ConstantExpr, capturing the value if we match.
  740. inline bind_ty<ConstantExpr> m_ConstantExpr(ConstantExpr *&C) { return C; }
  741.  
  742. /// Match a basic block value, capturing it if we match.
  743. inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
  744. inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) {
  745.   return V;
  746. }
  747.  
  748. /// Match an arbitrary immediate Constant and ignore it.
  749. inline match_combine_and<class_match<Constant>,
  750.                          match_unless<constantexpr_match>>
  751. m_ImmConstant() {
  752.   return m_CombineAnd(m_Constant(), m_Unless(m_ConstantExpr()));
  753. }
  754.  
  755. /// Match an immediate Constant, capturing the value if we match.
  756. inline match_combine_and<bind_ty<Constant>,
  757.                          match_unless<constantexpr_match>>
  758. m_ImmConstant(Constant *&C) {
  759.   return m_CombineAnd(m_Constant(C), m_Unless(m_ConstantExpr()));
  760. }
  761.  
  762. /// Match a specified Value*.
  763. struct specificval_ty {
  764.   const Value *Val;
  765.  
  766.   specificval_ty(const Value *V) : Val(V) {}
  767.  
  768.   template <typename ITy> bool match(ITy *V) { return V == Val; }
  769. };
  770.  
  771. /// Match if we have a specific specified value.
  772. inline specificval_ty m_Specific(const Value *V) { return V; }
  773.  
  774. /// Stores a reference to the Value *, not the Value * itself,
  775. /// thus can be used in commutative matchers.
  776. template <typename Class> struct deferredval_ty {
  777.   Class *const &Val;
  778.  
  779.   deferredval_ty(Class *const &V) : Val(V) {}
  780.  
  781.   template <typename ITy> bool match(ITy *const V) { return V == Val; }
  782. };
  783.  
  784. /// Like m_Specific(), but works if the specific value to match is determined
  785. /// as part of the same match() expression. For example:
  786. /// m_Add(m_Value(X), m_Specific(X)) is incorrect, because m_Specific() will
  787. /// bind X before the pattern match starts.
  788. /// m_Add(m_Value(X), m_Deferred(X)) is correct, and will check against
  789. /// whichever value m_Value(X) populated.
  790. inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
  791. inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
  792.   return V;
  793. }
  794.  
  795. /// Match a specified floating point value or vector of all elements of
  796. /// that value.
  797. struct specific_fpval {
  798.   double Val;
  799.  
  800.   specific_fpval(double V) : Val(V) {}
  801.  
  802.   template <typename ITy> bool match(ITy *V) {
  803.     if (const auto *CFP = dyn_cast<ConstantFP>(V))
  804.       return CFP->isExactlyValue(Val);
  805.     if (V->getType()->isVectorTy())
  806.       if (const auto *C = dyn_cast<Constant>(V))
  807.         if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
  808.           return CFP->isExactlyValue(Val);
  809.     return false;
  810.   }
  811. };
  812.  
  813. /// Match a specific floating point value or vector with all elements
  814. /// equal to the value.
  815. inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
  816.  
  817. /// Match a float 1.0 or vector with all elements equal to 1.0.
  818. inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
  819.  
  820. struct bind_const_intval_ty {
  821.   uint64_t &VR;
  822.  
  823.   bind_const_intval_ty(uint64_t &V) : VR(V) {}
  824.  
  825.   template <typename ITy> bool match(ITy *V) {
  826.     if (const auto *CV = dyn_cast<ConstantInt>(V))
  827.       if (CV->getValue().ule(UINT64_MAX)) {
  828.         VR = CV->getZExtValue();
  829.         return true;
  830.       }
  831.     return false;
  832.   }
  833. };
  834.  
  835. /// Match a specified integer value or vector of all elements of that
  836. /// value.
  837. template <bool AllowUndefs> struct specific_intval {
  838.   APInt Val;
  839.  
  840.   specific_intval(APInt V) : Val(std::move(V)) {}
  841.  
  842.   template <typename ITy> bool match(ITy *V) {
  843.     const auto *CI = dyn_cast<ConstantInt>(V);
  844.     if (!CI && V->getType()->isVectorTy())
  845.       if (const auto *C = dyn_cast<Constant>(V))
  846.         CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue(AllowUndefs));
  847.  
  848.     return CI && APInt::isSameValue(CI->getValue(), Val);
  849.   }
  850. };
  851.  
  852. /// Match a specific integer value or vector with all elements equal to
  853. /// the value.
  854. inline specific_intval<false> m_SpecificInt(APInt V) {
  855.   return specific_intval<false>(std::move(V));
  856. }
  857.  
  858. inline specific_intval<false> m_SpecificInt(uint64_t V) {
  859.   return m_SpecificInt(APInt(64, V));
  860. }
  861.  
  862. inline specific_intval<true> m_SpecificIntAllowUndef(APInt V) {
  863.   return specific_intval<true>(std::move(V));
  864. }
  865.  
  866. inline specific_intval<true> m_SpecificIntAllowUndef(uint64_t V) {
  867.   return m_SpecificIntAllowUndef(APInt(64, V));
  868. }
  869.  
  870. /// Match a ConstantInt and bind to its value.  This does not match
  871. /// ConstantInts wider than 64-bits.
  872. inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
  873.  
  874. /// Match a specified basic block value.
  875. struct specific_bbval {
  876.   BasicBlock *Val;
  877.  
  878.   specific_bbval(BasicBlock *Val) : Val(Val) {}
  879.  
  880.   template <typename ITy> bool match(ITy *V) {
  881.     const auto *BB = dyn_cast<BasicBlock>(V);
  882.     return BB && BB == Val;
  883.   }
  884. };
  885.  
  886. /// Match a specific basic block value.
  887. inline specific_bbval m_SpecificBB(BasicBlock *BB) {
  888.   return specific_bbval(BB);
  889. }
  890.  
  891. /// A commutative-friendly version of m_Specific().
  892. inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) {
  893.   return BB;
  894. }
  895. inline deferredval_ty<const BasicBlock>
  896. m_Deferred(const BasicBlock *const &BB) {
  897.   return BB;
  898. }
  899.  
  900. //===----------------------------------------------------------------------===//
  901. // Matcher for any binary operator.
  902. //
  903. template <typename LHS_t, typename RHS_t, bool Commutable = false>
  904. struct AnyBinaryOp_match {
  905.   LHS_t L;
  906.   RHS_t R;
  907.  
  908.   // The evaluation order is always stable, regardless of Commutability.
  909.   // The LHS is always matched first.
  910.   AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
  911.  
  912.   template <typename OpTy> bool match(OpTy *V) {
  913.     if (auto *I = dyn_cast<BinaryOperator>(V))
  914.       return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
  915.              (Commutable && L.match(I->getOperand(1)) &&
  916.               R.match(I->getOperand(0)));
  917.     return false;
  918.   }
  919. };
  920.  
  921. template <typename LHS, typename RHS>
  922. inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
  923.   return AnyBinaryOp_match<LHS, RHS>(L, R);
  924. }
  925.  
  926. //===----------------------------------------------------------------------===//
  927. // Matcher for any unary operator.
  928. // TODO fuse unary, binary matcher into n-ary matcher
  929. //
  930. template <typename OP_t> struct AnyUnaryOp_match {
  931.   OP_t X;
  932.  
  933.   AnyUnaryOp_match(const OP_t &X) : X(X) {}
  934.  
  935.   template <typename OpTy> bool match(OpTy *V) {
  936.     if (auto *I = dyn_cast<UnaryOperator>(V))
  937.       return X.match(I->getOperand(0));
  938.     return false;
  939.   }
  940. };
  941.  
  942. template <typename OP_t> inline AnyUnaryOp_match<OP_t> m_UnOp(const OP_t &X) {
  943.   return AnyUnaryOp_match<OP_t>(X);
  944. }
  945.  
  946. //===----------------------------------------------------------------------===//
  947. // Matchers for specific binary operators.
  948. //
  949.  
  950. template <typename LHS_t, typename RHS_t, unsigned Opcode,
  951.           bool Commutable = false>
  952. struct BinaryOp_match {
  953.   LHS_t L;
  954.   RHS_t R;
  955.  
  956.   // The evaluation order is always stable, regardless of Commutability.
  957.   // The LHS is always matched first.
  958.   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
  959.  
  960.   template <typename OpTy> inline bool match(unsigned Opc, OpTy *V) {
  961.     if (V->getValueID() == Value::InstructionVal + Opc) {
  962.       auto *I = cast<BinaryOperator>(V);
  963.       return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
  964.              (Commutable && L.match(I->getOperand(1)) &&
  965.               R.match(I->getOperand(0)));
  966.     }
  967.     if (auto *CE = dyn_cast<ConstantExpr>(V))
  968.       return CE->getOpcode() == Opc &&
  969.              ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
  970.               (Commutable && L.match(CE->getOperand(1)) &&
  971.                R.match(CE->getOperand(0))));
  972.     return false;
  973.   }
  974.  
  975.   template <typename OpTy> bool match(OpTy *V) { return match(Opcode, V); }
  976. };
  977.  
  978. template <typename LHS, typename RHS>
  979. inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
  980.                                                         const RHS &R) {
  981.   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
  982. }
  983.  
  984. template <typename LHS, typename RHS>
  985. inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
  986.                                                           const RHS &R) {
  987.   return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
  988. }
  989.  
  990. template <typename LHS, typename RHS>
  991. inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
  992.                                                         const RHS &R) {
  993.   return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
  994. }
  995.  
  996. template <typename LHS, typename RHS>
  997. inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
  998.                                                           const RHS &R) {
  999.   return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
  1000. }
  1001.  
  1002. template <typename Op_t> struct FNeg_match {
  1003.   Op_t X;
  1004.  
  1005.   FNeg_match(const Op_t &Op) : X(Op) {}
  1006.   template <typename OpTy> bool match(OpTy *V) {
  1007.     auto *FPMO = dyn_cast<FPMathOperator>(V);
  1008.     if (!FPMO)
  1009.       return false;
  1010.  
  1011.     if (FPMO->getOpcode() == Instruction::FNeg)
  1012.       return X.match(FPMO->getOperand(0));
  1013.  
  1014.     if (FPMO->getOpcode() == Instruction::FSub) {
  1015.       if (FPMO->hasNoSignedZeros()) {
  1016.         // With 'nsz', any zero goes.
  1017.         if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0)))
  1018.           return false;
  1019.       } else {
  1020.         // Without 'nsz', we need fsub -0.0, X exactly.
  1021.         if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0)))
  1022.           return false;
  1023.       }
  1024.  
  1025.       return X.match(FPMO->getOperand(1));
  1026.     }
  1027.  
  1028.     return false;
  1029.   }
  1030. };
  1031.  
  1032. /// Match 'fneg X' as 'fsub -0.0, X'.
  1033. template <typename OpTy> inline FNeg_match<OpTy> m_FNeg(const OpTy &X) {
  1034.   return FNeg_match<OpTy>(X);
  1035. }
  1036.  
  1037. /// Match 'fneg X' as 'fsub +-0.0, X'.
  1038. template <typename RHS>
  1039. inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub>
  1040. m_FNegNSZ(const RHS &X) {
  1041.   return m_FSub(m_AnyZeroFP(), X);
  1042. }
  1043.  
  1044. template <typename LHS, typename RHS>
  1045. inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
  1046.                                                         const RHS &R) {
  1047.   return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
  1048. }
  1049.  
  1050. template <typename LHS, typename RHS>
  1051. inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
  1052.                                                           const RHS &R) {
  1053.   return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
  1054. }
  1055.  
  1056. template <typename LHS, typename RHS>
  1057. inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
  1058.                                                           const RHS &R) {
  1059.   return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
  1060. }
  1061.  
  1062. template <typename LHS, typename RHS>
  1063. inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
  1064.                                                           const RHS &R) {
  1065.   return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
  1066. }
  1067.  
  1068. template <typename LHS, typename RHS>
  1069. inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
  1070.                                                           const RHS &R) {
  1071.   return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
  1072. }
  1073.  
  1074. template <typename LHS, typename RHS>
  1075. inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
  1076.                                                           const RHS &R) {
  1077.   return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
  1078. }
  1079.  
  1080. template <typename LHS, typename RHS>
  1081. inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
  1082.                                                           const RHS &R) {
  1083.   return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
  1084. }
  1085.  
  1086. template <typename LHS, typename RHS>
  1087. inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
  1088.                                                           const RHS &R) {
  1089.   return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
  1090. }
  1091.  
  1092. template <typename LHS, typename RHS>
  1093. inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
  1094.                                                         const RHS &R) {
  1095.   return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
  1096. }
  1097.  
  1098. template <typename LHS, typename RHS>
  1099. inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
  1100.                                                       const RHS &R) {
  1101.   return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
  1102. }
  1103.  
  1104. template <typename LHS, typename RHS>
  1105. inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
  1106.                                                         const RHS &R) {
  1107.   return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
  1108. }
  1109.  
  1110. template <typename LHS, typename RHS>
  1111. inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
  1112.                                                         const RHS &R) {
  1113.   return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
  1114. }
  1115.  
  1116. template <typename LHS, typename RHS>
  1117. inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
  1118.                                                           const RHS &R) {
  1119.   return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
  1120. }
  1121.  
  1122. template <typename LHS, typename RHS>
  1123. inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
  1124.                                                           const RHS &R) {
  1125.   return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
  1126. }
  1127.  
  1128. template <typename LHS_t, typename RHS_t, unsigned Opcode,
  1129.           unsigned WrapFlags = 0>
  1130. struct OverflowingBinaryOp_match {
  1131.   LHS_t L;
  1132.   RHS_t R;
  1133.  
  1134.   OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
  1135.       : L(LHS), R(RHS) {}
  1136.  
  1137.   template <typename OpTy> bool match(OpTy *V) {
  1138.     if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
  1139.       if (Op->getOpcode() != Opcode)
  1140.         return false;
  1141.       if ((WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap) &&
  1142.           !Op->hasNoUnsignedWrap())
  1143.         return false;
  1144.       if ((WrapFlags & OverflowingBinaryOperator::NoSignedWrap) &&
  1145.           !Op->hasNoSignedWrap())
  1146.         return false;
  1147.       return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
  1148.     }
  1149.     return false;
  1150.   }
  1151. };
  1152.  
  1153. template <typename LHS, typename RHS>
  1154. inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
  1155.                                  OverflowingBinaryOperator::NoSignedWrap>
  1156. m_NSWAdd(const LHS &L, const RHS &R) {
  1157.   return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
  1158.                                    OverflowingBinaryOperator::NoSignedWrap>(L,
  1159.                                                                             R);
  1160. }
  1161. template <typename LHS, typename RHS>
  1162. inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
  1163.                                  OverflowingBinaryOperator::NoSignedWrap>
  1164. m_NSWSub(const LHS &L, const RHS &R) {
  1165.   return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
  1166.                                    OverflowingBinaryOperator::NoSignedWrap>(L,
  1167.                                                                             R);
  1168. }
  1169. template <typename LHS, typename RHS>
  1170. inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
  1171.                                  OverflowingBinaryOperator::NoSignedWrap>
  1172. m_NSWMul(const LHS &L, const RHS &R) {
  1173.   return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
  1174.                                    OverflowingBinaryOperator::NoSignedWrap>(L,
  1175.                                                                             R);
  1176. }
  1177. template <typename LHS, typename RHS>
  1178. inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
  1179.                                  OverflowingBinaryOperator::NoSignedWrap>
  1180. m_NSWShl(const LHS &L, const RHS &R) {
  1181.   return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
  1182.                                    OverflowingBinaryOperator::NoSignedWrap>(L,
  1183.                                                                             R);
  1184. }
  1185.  
  1186. template <typename LHS, typename RHS>
  1187. inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
  1188.                                  OverflowingBinaryOperator::NoUnsignedWrap>
  1189. m_NUWAdd(const LHS &L, const RHS &R) {
  1190.   return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
  1191.                                    OverflowingBinaryOperator::NoUnsignedWrap>(
  1192.       L, R);
  1193. }
  1194. template <typename LHS, typename RHS>
  1195. inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
  1196.                                  OverflowingBinaryOperator::NoUnsignedWrap>
  1197. m_NUWSub(const LHS &L, const RHS &R) {
  1198.   return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
  1199.                                    OverflowingBinaryOperator::NoUnsignedWrap>(
  1200.       L, R);
  1201. }
  1202. template <typename LHS, typename RHS>
  1203. inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
  1204.                                  OverflowingBinaryOperator::NoUnsignedWrap>
  1205. m_NUWMul(const LHS &L, const RHS &R) {
  1206.   return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
  1207.                                    OverflowingBinaryOperator::NoUnsignedWrap>(
  1208.       L, R);
  1209. }
  1210. template <typename LHS, typename RHS>
  1211. inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
  1212.                                  OverflowingBinaryOperator::NoUnsignedWrap>
  1213. m_NUWShl(const LHS &L, const RHS &R) {
  1214.   return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
  1215.                                    OverflowingBinaryOperator::NoUnsignedWrap>(
  1216.       L, R);
  1217. }
  1218.  
  1219. template <typename LHS_t, typename RHS_t, bool Commutable = false>
  1220. struct SpecificBinaryOp_match
  1221.     : public BinaryOp_match<LHS_t, RHS_t, 0, Commutable> {
  1222.   unsigned Opcode;
  1223.  
  1224.   SpecificBinaryOp_match(unsigned Opcode, const LHS_t &LHS, const RHS_t &RHS)
  1225.       : BinaryOp_match<LHS_t, RHS_t, 0, Commutable>(LHS, RHS), Opcode(Opcode) {}
  1226.  
  1227.   template <typename OpTy> bool match(OpTy *V) {
  1228.     return BinaryOp_match<LHS_t, RHS_t, 0, Commutable>::match(Opcode, V);
  1229.   }
  1230. };
  1231.  
  1232. /// Matches a specific opcode.
  1233. template <typename LHS, typename RHS>
  1234. inline SpecificBinaryOp_match<LHS, RHS> m_BinOp(unsigned Opcode, const LHS &L,
  1235.                                                 const RHS &R) {
  1236.   return SpecificBinaryOp_match<LHS, RHS>(Opcode, L, R);
  1237. }
  1238.  
  1239. //===----------------------------------------------------------------------===//
  1240. // Class that matches a group of binary opcodes.
  1241. //
  1242. template <typename LHS_t, typename RHS_t, typename Predicate>
  1243. struct BinOpPred_match : Predicate {
  1244.   LHS_t L;
  1245.   RHS_t R;
  1246.  
  1247.   BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
  1248.  
  1249.   template <typename OpTy> bool match(OpTy *V) {
  1250.     if (auto *I = dyn_cast<Instruction>(V))
  1251.       return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
  1252.              R.match(I->getOperand(1));
  1253.     if (auto *CE = dyn_cast<ConstantExpr>(V))
  1254.       return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
  1255.              R.match(CE->getOperand(1));
  1256.     return false;
  1257.   }
  1258. };
  1259.  
  1260. struct is_shift_op {
  1261.   bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
  1262. };
  1263.  
  1264. struct is_right_shift_op {
  1265.   bool isOpType(unsigned Opcode) {
  1266.     return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
  1267.   }
  1268. };
  1269.  
  1270. struct is_logical_shift_op {
  1271.   bool isOpType(unsigned Opcode) {
  1272.     return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
  1273.   }
  1274. };
  1275.  
  1276. struct is_bitwiselogic_op {
  1277.   bool isOpType(unsigned Opcode) {
  1278.     return Instruction::isBitwiseLogicOp(Opcode);
  1279.   }
  1280. };
  1281.  
  1282. struct is_idiv_op {
  1283.   bool isOpType(unsigned Opcode) {
  1284.     return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
  1285.   }
  1286. };
  1287.  
  1288. struct is_irem_op {
  1289.   bool isOpType(unsigned Opcode) {
  1290.     return Opcode == Instruction::SRem || Opcode == Instruction::URem;
  1291.   }
  1292. };
  1293.  
  1294. /// Matches shift operations.
  1295. template <typename LHS, typename RHS>
  1296. inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L,
  1297.                                                       const RHS &R) {
  1298.   return BinOpPred_match<LHS, RHS, is_shift_op>(L, R);
  1299. }
  1300.  
  1301. /// Matches logical shift operations.
  1302. template <typename LHS, typename RHS>
  1303. inline BinOpPred_match<LHS, RHS, is_right_shift_op> m_Shr(const LHS &L,
  1304.                                                           const RHS &R) {
  1305.   return BinOpPred_match<LHS, RHS, is_right_shift_op>(L, R);
  1306. }
  1307.  
  1308. /// Matches logical shift operations.
  1309. template <typename LHS, typename RHS>
  1310. inline BinOpPred_match<LHS, RHS, is_logical_shift_op>
  1311. m_LogicalShift(const LHS &L, const RHS &R) {
  1312.   return BinOpPred_match<LHS, RHS, is_logical_shift_op>(L, R);
  1313. }
  1314.  
  1315. /// Matches bitwise logic operations.
  1316. template <typename LHS, typename RHS>
  1317. inline BinOpPred_match<LHS, RHS, is_bitwiselogic_op>
  1318. m_BitwiseLogic(const LHS &L, const RHS &R) {
  1319.   return BinOpPred_match<LHS, RHS, is_bitwiselogic_op>(L, R);
  1320. }
  1321.  
  1322. /// Matches integer division operations.
  1323. template <typename LHS, typename RHS>
  1324. inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L,
  1325.                                                     const RHS &R) {
  1326.   return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R);
  1327. }
  1328.  
  1329. /// Matches integer remainder operations.
  1330. template <typename LHS, typename RHS>
  1331. inline BinOpPred_match<LHS, RHS, is_irem_op> m_IRem(const LHS &L,
  1332.                                                     const RHS &R) {
  1333.   return BinOpPred_match<LHS, RHS, is_irem_op>(L, R);
  1334. }
  1335.  
  1336. //===----------------------------------------------------------------------===//
  1337. // Class that matches exact binary ops.
  1338. //
  1339. template <typename SubPattern_t> struct Exact_match {
  1340.   SubPattern_t SubPattern;
  1341.  
  1342.   Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
  1343.  
  1344.   template <typename OpTy> bool match(OpTy *V) {
  1345.     if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
  1346.       return PEO->isExact() && SubPattern.match(V);
  1347.     return false;
  1348.   }
  1349. };
  1350.  
  1351. template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
  1352.   return SubPattern;
  1353. }
  1354.  
  1355. //===----------------------------------------------------------------------===//
  1356. // Matchers for CmpInst classes
  1357. //
  1358.  
  1359. template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
  1360.           bool Commutable = false>
  1361. struct CmpClass_match {
  1362.   PredicateTy &Predicate;
  1363.   LHS_t L;
  1364.   RHS_t R;
  1365.  
  1366.   // The evaluation order is always stable, regardless of Commutability.
  1367.   // The LHS is always matched first.
  1368.   CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
  1369.       : Predicate(Pred), L(LHS), R(RHS) {}
  1370.  
  1371.   template <typename OpTy> bool match(OpTy *V) {
  1372.     if (auto *I = dyn_cast<Class>(V)) {
  1373.       if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
  1374.         Predicate = I->getPredicate();
  1375.         return true;
  1376.       } else if (Commutable && L.match(I->getOperand(1)) &&
  1377.                  R.match(I->getOperand(0))) {
  1378.         Predicate = I->getSwappedPredicate();
  1379.         return true;
  1380.       }
  1381.     }
  1382.     return false;
  1383.   }
  1384. };
  1385.  
  1386. template <typename LHS, typename RHS>
  1387. inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>
  1388. m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
  1389.   return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R);
  1390. }
  1391.  
  1392. template <typename LHS, typename RHS>
  1393. inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
  1394. m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
  1395.   return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R);
  1396. }
  1397.  
  1398. template <typename LHS, typename RHS>
  1399. inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
  1400. m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
  1401.   return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R);
  1402. }
  1403.  
  1404. //===----------------------------------------------------------------------===//
  1405. // Matchers for instructions with a given opcode and number of operands.
  1406. //
  1407.  
  1408. /// Matches instructions with Opcode and three operands.
  1409. template <typename T0, unsigned Opcode> struct OneOps_match {
  1410.   T0 Op1;
  1411.  
  1412.   OneOps_match(const T0 &Op1) : Op1(Op1) {}
  1413.  
  1414.   template <typename OpTy> bool match(OpTy *V) {
  1415.     if (V->getValueID() == Value::InstructionVal + Opcode) {
  1416.       auto *I = cast<Instruction>(V);
  1417.       return Op1.match(I->getOperand(0));
  1418.     }
  1419.     return false;
  1420.   }
  1421. };
  1422.  
  1423. /// Matches instructions with Opcode and three operands.
  1424. template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
  1425.   T0 Op1;
  1426.   T1 Op2;
  1427.  
  1428.   TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
  1429.  
  1430.   template <typename OpTy> bool match(OpTy *V) {
  1431.     if (V->getValueID() == Value::InstructionVal + Opcode) {
  1432.       auto *I = cast<Instruction>(V);
  1433.       return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
  1434.     }
  1435.     return false;
  1436.   }
  1437. };
  1438.  
  1439. /// Matches instructions with Opcode and three operands.
  1440. template <typename T0, typename T1, typename T2, unsigned Opcode>
  1441. struct ThreeOps_match {
  1442.   T0 Op1;
  1443.   T1 Op2;
  1444.   T2 Op3;
  1445.  
  1446.   ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
  1447.       : Op1(Op1), Op2(Op2), Op3(Op3) {}
  1448.  
  1449.   template <typename OpTy> bool match(OpTy *V) {
  1450.     if (V->getValueID() == Value::InstructionVal + Opcode) {
  1451.       auto *I = cast<Instruction>(V);
  1452.       return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
  1453.              Op3.match(I->getOperand(2));
  1454.     }
  1455.     return false;
  1456.   }
  1457. };
  1458.  
  1459. /// Matches SelectInst.
  1460. template <typename Cond, typename LHS, typename RHS>
  1461. inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select>
  1462. m_Select(const Cond &C, const LHS &L, const RHS &R) {
  1463.   return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R);
  1464. }
  1465.  
  1466. /// This matches a select of two constants, e.g.:
  1467. /// m_SelectCst<-1, 0>(m_Value(V))
  1468. template <int64_t L, int64_t R, typename Cond>
  1469. inline ThreeOps_match<Cond, constantint_match<L>, constantint_match<R>,
  1470.                       Instruction::Select>
  1471. m_SelectCst(const Cond &C) {
  1472.   return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
  1473. }
  1474.  
  1475. /// Matches FreezeInst.
  1476. template <typename OpTy>
  1477. inline OneOps_match<OpTy, Instruction::Freeze> m_Freeze(const OpTy &Op) {
  1478.   return OneOps_match<OpTy, Instruction::Freeze>(Op);
  1479. }
  1480.  
  1481. /// Matches InsertElementInst.
  1482. template <typename Val_t, typename Elt_t, typename Idx_t>
  1483. inline ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>
  1484. m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) {
  1485.   return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>(
  1486.       Val, Elt, Idx);
  1487. }
  1488.  
  1489. /// Matches ExtractElementInst.
  1490. template <typename Val_t, typename Idx_t>
  1491. inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>
  1492. m_ExtractElt(const Val_t &Val, const Idx_t &Idx) {
  1493.   return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx);
  1494. }
  1495.  
  1496. /// Matches shuffle.
  1497. template <typename T0, typename T1, typename T2> struct Shuffle_match {
  1498.   T0 Op1;
  1499.   T1 Op2;
  1500.   T2 Mask;
  1501.  
  1502.   Shuffle_match(const T0 &Op1, const T1 &Op2, const T2 &Mask)
  1503.       : Op1(Op1), Op2(Op2), Mask(Mask) {}
  1504.  
  1505.   template <typename OpTy> bool match(OpTy *V) {
  1506.     if (auto *I = dyn_cast<ShuffleVectorInst>(V)) {
  1507.       return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
  1508.              Mask.match(I->getShuffleMask());
  1509.     }
  1510.     return false;
  1511.   }
  1512. };
  1513.  
  1514. struct m_Mask {
  1515.   ArrayRef<int> &MaskRef;
  1516.   m_Mask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
  1517.   bool match(ArrayRef<int> Mask) {
  1518.     MaskRef = Mask;
  1519.     return true;
  1520.   }
  1521. };
  1522.  
  1523. struct m_ZeroMask {
  1524.   bool match(ArrayRef<int> Mask) {
  1525.     return all_of(Mask, [](int Elem) { return Elem == 0 || Elem == -1; });
  1526.   }
  1527. };
  1528.  
  1529. struct m_SpecificMask {
  1530.   ArrayRef<int> &MaskRef;
  1531.   m_SpecificMask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
  1532.   bool match(ArrayRef<int> Mask) { return MaskRef == Mask; }
  1533. };
  1534.  
  1535. struct m_SplatOrUndefMask {
  1536.   int &SplatIndex;
  1537.   m_SplatOrUndefMask(int &SplatIndex) : SplatIndex(SplatIndex) {}
  1538.   bool match(ArrayRef<int> Mask) {
  1539.     auto First = find_if(Mask, [](int Elem) { return Elem != -1; });
  1540.     if (First == Mask.end())
  1541.       return false;
  1542.     SplatIndex = *First;
  1543.     return all_of(Mask,
  1544.                   [First](int Elem) { return Elem == *First || Elem == -1; });
  1545.   }
  1546. };
  1547.  
  1548. /// Matches ShuffleVectorInst independently of mask value.
  1549. template <typename V1_t, typename V2_t>
  1550. inline TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>
  1551. m_Shuffle(const V1_t &v1, const V2_t &v2) {
  1552.   return TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>(v1, v2);
  1553. }
  1554.  
  1555. template <typename V1_t, typename V2_t, typename Mask_t>
  1556. inline Shuffle_match<V1_t, V2_t, Mask_t>
  1557. m_Shuffle(const V1_t &v1, const V2_t &v2, const Mask_t &mask) {
  1558.   return Shuffle_match<V1_t, V2_t, Mask_t>(v1, v2, mask);
  1559. }
  1560.  
  1561. /// Matches LoadInst.
  1562. template <typename OpTy>
  1563. inline OneOps_match<OpTy, Instruction::Load> m_Load(const OpTy &Op) {
  1564.   return OneOps_match<OpTy, Instruction::Load>(Op);
  1565. }
  1566.  
  1567. /// Matches StoreInst.
  1568. template <typename ValueOpTy, typename PointerOpTy>
  1569. inline TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>
  1570. m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) {
  1571.   return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp,
  1572.                                                                   PointerOp);
  1573. }
  1574.  
  1575. //===----------------------------------------------------------------------===//
  1576. // Matchers for CastInst classes
  1577. //
  1578.  
  1579. template <typename Op_t, unsigned Opcode> struct CastClass_match {
  1580.   Op_t Op;
  1581.  
  1582.   CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
  1583.  
  1584.   template <typename OpTy> bool match(OpTy *V) {
  1585.     if (auto *O = dyn_cast<Operator>(V))
  1586.       return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
  1587.     return false;
  1588.   }
  1589. };
  1590.  
  1591. /// Matches BitCast.
  1592. template <typename OpTy>
  1593. inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) {
  1594.   return CastClass_match<OpTy, Instruction::BitCast>(Op);
  1595. }
  1596.  
  1597. /// Matches PtrToInt.
  1598. template <typename OpTy>
  1599. inline CastClass_match<OpTy, Instruction::PtrToInt> m_PtrToInt(const OpTy &Op) {
  1600.   return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
  1601. }
  1602.  
  1603. /// Matches IntToPtr.
  1604. template <typename OpTy>
  1605. inline CastClass_match<OpTy, Instruction::IntToPtr> m_IntToPtr(const OpTy &Op) {
  1606.   return CastClass_match<OpTy, Instruction::IntToPtr>(Op);
  1607. }
  1608.  
  1609. /// Matches Trunc.
  1610. template <typename OpTy>
  1611. inline CastClass_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) {
  1612.   return CastClass_match<OpTy, Instruction::Trunc>(Op);
  1613. }
  1614.  
  1615. template <typename OpTy>
  1616. inline match_combine_or<CastClass_match<OpTy, Instruction::Trunc>, OpTy>
  1617. m_TruncOrSelf(const OpTy &Op) {
  1618.   return m_CombineOr(m_Trunc(Op), Op);
  1619. }
  1620.  
  1621. /// Matches SExt.
  1622. template <typename OpTy>
  1623. inline CastClass_match<OpTy, Instruction::SExt> m_SExt(const OpTy &Op) {
  1624.   return CastClass_match<OpTy, Instruction::SExt>(Op);
  1625. }
  1626.  
  1627. /// Matches ZExt.
  1628. template <typename OpTy>
  1629. inline CastClass_match<OpTy, Instruction::ZExt> m_ZExt(const OpTy &Op) {
  1630.   return CastClass_match<OpTy, Instruction::ZExt>(Op);
  1631. }
  1632.  
  1633. template <typename OpTy>
  1634. inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, OpTy>
  1635. m_ZExtOrSelf(const OpTy &Op) {
  1636.   return m_CombineOr(m_ZExt(Op), Op);
  1637. }
  1638.  
  1639. template <typename OpTy>
  1640. inline match_combine_or<CastClass_match<OpTy, Instruction::SExt>, OpTy>
  1641. m_SExtOrSelf(const OpTy &Op) {
  1642.   return m_CombineOr(m_SExt(Op), Op);
  1643. }
  1644.  
  1645. template <typename OpTy>
  1646. inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
  1647.                         CastClass_match<OpTy, Instruction::SExt>>
  1648. m_ZExtOrSExt(const OpTy &Op) {
  1649.   return m_CombineOr(m_ZExt(Op), m_SExt(Op));
  1650. }
  1651.  
  1652. template <typename OpTy>
  1653. inline match_combine_or<
  1654.     match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
  1655.                      CastClass_match<OpTy, Instruction::SExt>>,
  1656.     OpTy>
  1657. m_ZExtOrSExtOrSelf(const OpTy &Op) {
  1658.   return m_CombineOr(m_ZExtOrSExt(Op), Op);
  1659. }
  1660.  
  1661. template <typename OpTy>
  1662. inline CastClass_match<OpTy, Instruction::UIToFP> m_UIToFP(const OpTy &Op) {
  1663.   return CastClass_match<OpTy, Instruction::UIToFP>(Op);
  1664. }
  1665.  
  1666. template <typename OpTy>
  1667. inline CastClass_match<OpTy, Instruction::SIToFP> m_SIToFP(const OpTy &Op) {
  1668.   return CastClass_match<OpTy, Instruction::SIToFP>(Op);
  1669. }
  1670.  
  1671. template <typename OpTy>
  1672. inline CastClass_match<OpTy, Instruction::FPToUI> m_FPToUI(const OpTy &Op) {
  1673.   return CastClass_match<OpTy, Instruction::FPToUI>(Op);
  1674. }
  1675.  
  1676. template <typename OpTy>
  1677. inline CastClass_match<OpTy, Instruction::FPToSI> m_FPToSI(const OpTy &Op) {
  1678.   return CastClass_match<OpTy, Instruction::FPToSI>(Op);
  1679. }
  1680.  
  1681. template <typename OpTy>
  1682. inline CastClass_match<OpTy, Instruction::FPTrunc> m_FPTrunc(const OpTy &Op) {
  1683.   return CastClass_match<OpTy, Instruction::FPTrunc>(Op);
  1684. }
  1685.  
  1686. template <typename OpTy>
  1687. inline CastClass_match<OpTy, Instruction::FPExt> m_FPExt(const OpTy &Op) {
  1688.   return CastClass_match<OpTy, Instruction::FPExt>(Op);
  1689. }
  1690.  
  1691. //===----------------------------------------------------------------------===//
  1692. // Matchers for control flow.
  1693. //
  1694.  
  1695. struct br_match {
  1696.   BasicBlock *&Succ;
  1697.  
  1698.   br_match(BasicBlock *&Succ) : Succ(Succ) {}
  1699.  
  1700.   template <typename OpTy> bool match(OpTy *V) {
  1701.     if (auto *BI = dyn_cast<BranchInst>(V))
  1702.       if (BI->isUnconditional()) {
  1703.         Succ = BI->getSuccessor(0);
  1704.         return true;
  1705.       }
  1706.     return false;
  1707.   }
  1708. };
  1709.  
  1710. inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
  1711.  
  1712. template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
  1713. struct brc_match {
  1714.   Cond_t Cond;
  1715.   TrueBlock_t T;
  1716.   FalseBlock_t F;
  1717.  
  1718.   brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
  1719.       : Cond(C), T(t), F(f) {}
  1720.  
  1721.   template <typename OpTy> bool match(OpTy *V) {
  1722.     if (auto *BI = dyn_cast<BranchInst>(V))
  1723.       if (BI->isConditional() && Cond.match(BI->getCondition()))
  1724.         return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1));
  1725.     return false;
  1726.   }
  1727. };
  1728.  
  1729. template <typename Cond_t>
  1730. inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>
  1731. m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
  1732.   return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>(
  1733.       C, m_BasicBlock(T), m_BasicBlock(F));
  1734. }
  1735.  
  1736. template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
  1737. inline brc_match<Cond_t, TrueBlock_t, FalseBlock_t>
  1738. m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) {
  1739.   return brc_match<Cond_t, TrueBlock_t, FalseBlock_t>(C, T, F);
  1740. }
  1741.  
  1742. //===----------------------------------------------------------------------===//
  1743. // Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
  1744. //
  1745.  
  1746. template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
  1747.           bool Commutable = false>
  1748. struct MaxMin_match {
  1749.   using PredType = Pred_t;
  1750.   LHS_t L;
  1751.   RHS_t R;
  1752.  
  1753.   // The evaluation order is always stable, regardless of Commutability.
  1754.   // The LHS is always matched first.
  1755.   MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
  1756.  
  1757.   template <typename OpTy> bool match(OpTy *V) {
  1758.     if (auto *II = dyn_cast<IntrinsicInst>(V)) {
  1759.       Intrinsic::ID IID = II->getIntrinsicID();
  1760.       if ((IID == Intrinsic::smax && Pred_t::match(ICmpInst::ICMP_SGT)) ||
  1761.           (IID == Intrinsic::smin && Pred_t::match(ICmpInst::ICMP_SLT)) ||
  1762.           (IID == Intrinsic::umax && Pred_t::match(ICmpInst::ICMP_UGT)) ||
  1763.           (IID == Intrinsic::umin && Pred_t::match(ICmpInst::ICMP_ULT))) {
  1764.         Value *LHS = II->getOperand(0), *RHS = II->getOperand(1);
  1765.         return (L.match(LHS) && R.match(RHS)) ||
  1766.                (Commutable && L.match(RHS) && R.match(LHS));
  1767.       }
  1768.     }
  1769.     // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
  1770.     auto *SI = dyn_cast<SelectInst>(V);
  1771.     if (!SI)
  1772.       return false;
  1773.     auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
  1774.     if (!Cmp)
  1775.       return false;
  1776.     // At this point we have a select conditioned on a comparison.  Check that
  1777.     // it is the values returned by the select that are being compared.
  1778.     auto *TrueVal = SI->getTrueValue();
  1779.     auto *FalseVal = SI->getFalseValue();
  1780.     auto *LHS = Cmp->getOperand(0);
  1781.     auto *RHS = Cmp->getOperand(1);
  1782.     if ((TrueVal != LHS || FalseVal != RHS) &&
  1783.         (TrueVal != RHS || FalseVal != LHS))
  1784.       return false;
  1785.     typename CmpInst_t::Predicate Pred =
  1786.         LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
  1787.     // Does "(x pred y) ? x : y" represent the desired max/min operation?
  1788.     if (!Pred_t::match(Pred))
  1789.       return false;
  1790.     // It does!  Bind the operands.
  1791.     return (L.match(LHS) && R.match(RHS)) ||
  1792.            (Commutable && L.match(RHS) && R.match(LHS));
  1793.   }
  1794. };
  1795.  
  1796. /// Helper class for identifying signed max predicates.
  1797. struct smax_pred_ty {
  1798.   static bool match(ICmpInst::Predicate Pred) {
  1799.     return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
  1800.   }
  1801. };
  1802.  
  1803. /// Helper class for identifying signed min predicates.
  1804. struct smin_pred_ty {
  1805.   static bool match(ICmpInst::Predicate Pred) {
  1806.     return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
  1807.   }
  1808. };
  1809.  
  1810. /// Helper class for identifying unsigned max predicates.
  1811. struct umax_pred_ty {
  1812.   static bool match(ICmpInst::Predicate Pred) {
  1813.     return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
  1814.   }
  1815. };
  1816.  
  1817. /// Helper class for identifying unsigned min predicates.
  1818. struct umin_pred_ty {
  1819.   static bool match(ICmpInst::Predicate Pred) {
  1820.     return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
  1821.   }
  1822. };
  1823.  
  1824. /// Helper class for identifying ordered max predicates.
  1825. struct ofmax_pred_ty {
  1826.   static bool match(FCmpInst::Predicate Pred) {
  1827.     return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
  1828.   }
  1829. };
  1830.  
  1831. /// Helper class for identifying ordered min predicates.
  1832. struct ofmin_pred_ty {
  1833.   static bool match(FCmpInst::Predicate Pred) {
  1834.     return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
  1835.   }
  1836. };
  1837.  
  1838. /// Helper class for identifying unordered max predicates.
  1839. struct ufmax_pred_ty {
  1840.   static bool match(FCmpInst::Predicate Pred) {
  1841.     return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
  1842.   }
  1843. };
  1844.  
  1845. /// Helper class for identifying unordered min predicates.
  1846. struct ufmin_pred_ty {
  1847.   static bool match(FCmpInst::Predicate Pred) {
  1848.     return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
  1849.   }
  1850. };
  1851.  
  1852. template <typename LHS, typename RHS>
  1853. inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L,
  1854.                                                              const RHS &R) {
  1855.   return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R);
  1856. }
  1857.  
  1858. template <typename LHS, typename RHS>
  1859. inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L,
  1860.                                                              const RHS &R) {
  1861.   return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R);
  1862. }
  1863.  
  1864. template <typename LHS, typename RHS>
  1865. inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L,
  1866.                                                              const RHS &R) {
  1867.   return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R);
  1868. }
  1869.  
  1870. template <typename LHS, typename RHS>
  1871. inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L,
  1872.                                                              const RHS &R) {
  1873.   return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R);
  1874. }
  1875.  
  1876. template <typename LHS, typename RHS>
  1877. inline match_combine_or<
  1878.     match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>,
  1879.                      MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>>,
  1880.     match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>,
  1881.                      MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>>>
  1882. m_MaxOrMin(const LHS &L, const RHS &R) {
  1883.   return m_CombineOr(m_CombineOr(m_SMax(L, R), m_SMin(L, R)),
  1884.                      m_CombineOr(m_UMax(L, R), m_UMin(L, R)));
  1885. }
  1886.  
  1887. /// Match an 'ordered' floating point maximum function.
  1888. /// Floating point has one special value 'NaN'. Therefore, there is no total
  1889. /// order. However, if we can ignore the 'NaN' value (for example, because of a
  1890. /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
  1891. /// semantics. In the presence of 'NaN' we have to preserve the original
  1892. /// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
  1893. ///
  1894. ///                         max(L, R)  iff L and R are not NaN
  1895. ///  m_OrdFMax(L, R) =      R          iff L or R are NaN
  1896. template <typename LHS, typename RHS>
  1897. inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L,
  1898.                                                                  const RHS &R) {
  1899.   return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R);
  1900. }
  1901.  
  1902. /// Match an 'ordered' floating point minimum function.
  1903. /// Floating point has one special value 'NaN'. Therefore, there is no total
  1904. /// order. However, if we can ignore the 'NaN' value (for example, because of a
  1905. /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
  1906. /// semantics. In the presence of 'NaN' we have to preserve the original
  1907. /// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
  1908. ///
  1909. ///                         min(L, R)  iff L and R are not NaN
  1910. ///  m_OrdFMin(L, R) =      R          iff L or R are NaN
  1911. template <typename LHS, typename RHS>
  1912. inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L,
  1913.                                                                  const RHS &R) {
  1914.   return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R);
  1915. }
  1916.  
  1917. /// Match an 'unordered' floating point maximum function.
  1918. /// Floating point has one special value 'NaN'. Therefore, there is no total
  1919. /// order. However, if we can ignore the 'NaN' value (for example, because of a
  1920. /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
  1921. /// semantics. In the presence of 'NaN' we have to preserve the original
  1922. /// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
  1923. ///
  1924. ///                         max(L, R)  iff L and R are not NaN
  1925. ///  m_UnordFMax(L, R) =    L          iff L or R are NaN
  1926. template <typename LHS, typename RHS>
  1927. inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>
  1928. m_UnordFMax(const LHS &L, const RHS &R) {
  1929.   return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R);
  1930. }
  1931.  
  1932. /// Match an 'unordered' floating point minimum function.
  1933. /// Floating point has one special value 'NaN'. Therefore, there is no total
  1934. /// order. However, if we can ignore the 'NaN' value (for example, because of a
  1935. /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
  1936. /// semantics. In the presence of 'NaN' we have to preserve the original
  1937. /// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
  1938. ///
  1939. ///                          min(L, R)  iff L and R are not NaN
  1940. ///  m_UnordFMin(L, R) =     L          iff L or R are NaN
  1941. template <typename LHS, typename RHS>
  1942. inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>
  1943. m_UnordFMin(const LHS &L, const RHS &R) {
  1944.   return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R);
  1945. }
  1946.  
  1947. //===----------------------------------------------------------------------===//
  1948. // Matchers for overflow check patterns: e.g. (a + b) u< a, (a ^ -1) <u b
  1949. // Note that S might be matched to other instructions than AddInst.
  1950. //
  1951.  
  1952. template <typename LHS_t, typename RHS_t, typename Sum_t>
  1953. struct UAddWithOverflow_match {
  1954.   LHS_t L;
  1955.   RHS_t R;
  1956.   Sum_t S;
  1957.  
  1958.   UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
  1959.       : L(L), R(R), S(S) {}
  1960.  
  1961.   template <typename OpTy> bool match(OpTy *V) {
  1962.     Value *ICmpLHS, *ICmpRHS;
  1963.     ICmpInst::Predicate Pred;
  1964.     if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
  1965.       return false;
  1966.  
  1967.     Value *AddLHS, *AddRHS;
  1968.     auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
  1969.  
  1970.     // (a + b) u< a, (a + b) u< b
  1971.     if (Pred == ICmpInst::ICMP_ULT)
  1972.       if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
  1973.         return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
  1974.  
  1975.     // a >u (a + b), b >u (a + b)
  1976.     if (Pred == ICmpInst::ICMP_UGT)
  1977.       if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
  1978.         return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
  1979.  
  1980.     Value *Op1;
  1981.     auto XorExpr = m_OneUse(m_Xor(m_Value(Op1), m_AllOnes()));
  1982.     // (a ^ -1) <u b
  1983.     if (Pred == ICmpInst::ICMP_ULT) {
  1984.       if (XorExpr.match(ICmpLHS))
  1985.         return L.match(Op1) && R.match(ICmpRHS) && S.match(ICmpLHS);
  1986.     }
  1987.     //  b > u (a ^ -1)
  1988.     if (Pred == ICmpInst::ICMP_UGT) {
  1989.       if (XorExpr.match(ICmpRHS))
  1990.         return L.match(Op1) && R.match(ICmpLHS) && S.match(ICmpRHS);
  1991.     }
  1992.  
  1993.     // Match special-case for increment-by-1.
  1994.     if (Pred == ICmpInst::ICMP_EQ) {
  1995.       // (a + 1) == 0
  1996.       // (1 + a) == 0
  1997.       if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) &&
  1998.           (m_One().match(AddLHS) || m_One().match(AddRHS)))
  1999.         return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
  2000.       // 0 == (a + 1)
  2001.       // 0 == (1 + a)
  2002.       if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) &&
  2003.           (m_One().match(AddLHS) || m_One().match(AddRHS)))
  2004.         return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
  2005.     }
  2006.  
  2007.     return false;
  2008.   }
  2009. };
  2010.  
  2011. /// Match an icmp instruction checking for unsigned overflow on addition.
  2012. ///
  2013. /// S is matched to the addition whose result is being checked for overflow, and
  2014. /// L and R are matched to the LHS and RHS of S.
  2015. template <typename LHS_t, typename RHS_t, typename Sum_t>
  2016. UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>
  2017. m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
  2018.   return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S);
  2019. }
  2020.  
  2021. template <typename Opnd_t> struct Argument_match {
  2022.   unsigned OpI;
  2023.   Opnd_t Val;
  2024.  
  2025.   Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
  2026.  
  2027.   template <typename OpTy> bool match(OpTy *V) {
  2028.     // FIXME: Should likely be switched to use `CallBase`.
  2029.     if (const auto *CI = dyn_cast<CallInst>(V))
  2030.       return Val.match(CI->getArgOperand(OpI));
  2031.     return false;
  2032.   }
  2033. };
  2034.  
  2035. /// Match an argument.
  2036. template <unsigned OpI, typename Opnd_t>
  2037. inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
  2038.   return Argument_match<Opnd_t>(OpI, Op);
  2039. }
  2040.  
  2041. /// Intrinsic matchers.
  2042. struct IntrinsicID_match {
  2043.   unsigned ID;
  2044.  
  2045.   IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
  2046.  
  2047.   template <typename OpTy> bool match(OpTy *V) {
  2048.     if (const auto *CI = dyn_cast<CallInst>(V))
  2049.       if (const auto *F = CI->getCalledFunction())
  2050.         return F->getIntrinsicID() == ID;
  2051.     return false;
  2052.   }
  2053. };
  2054.  
  2055. /// Intrinsic matches are combinations of ID matchers, and argument
  2056. /// matchers. Higher arity matcher are defined recursively in terms of and-ing
  2057. /// them with lower arity matchers. Here's some convenient typedefs for up to
  2058. /// several arguments, and more can be added as needed
  2059. template <typename T0 = void, typename T1 = void, typename T2 = void,
  2060.           typename T3 = void, typename T4 = void, typename T5 = void,
  2061.           typename T6 = void, typename T7 = void, typename T8 = void,
  2062.           typename T9 = void, typename T10 = void>
  2063. struct m_Intrinsic_Ty;
  2064. template <typename T0> struct m_Intrinsic_Ty<T0> {
  2065.   using Ty = match_combine_and<IntrinsicID_match, Argument_match<T0>>;
  2066. };
  2067. template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
  2068.   using Ty =
  2069.       match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>>;
  2070. };
  2071. template <typename T0, typename T1, typename T2>
  2072. struct m_Intrinsic_Ty<T0, T1, T2> {
  2073.   using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty,
  2074.                                Argument_match<T2>>;
  2075. };
  2076. template <typename T0, typename T1, typename T2, typename T3>
  2077. struct m_Intrinsic_Ty<T0, T1, T2, T3> {
  2078.   using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty,
  2079.                                Argument_match<T3>>;
  2080. };
  2081.  
  2082. template <typename T0, typename T1, typename T2, typename T3, typename T4>
  2083. struct m_Intrinsic_Ty<T0, T1, T2, T3, T4> {
  2084.   using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty,
  2085.                                Argument_match<T4>>;
  2086. };
  2087.  
  2088. template <typename T0, typename T1, typename T2, typename T3, typename T4,
  2089.           typename T5>
  2090. struct m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5> {
  2091.   using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty,
  2092.                                Argument_match<T5>>;
  2093. };
  2094.  
  2095. /// Match intrinsic calls like this:
  2096. /// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
  2097. template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
  2098.   return IntrinsicID_match(IntrID);
  2099. }
  2100.  
  2101. /// Matches MaskedLoad Intrinsic.
  2102. template <typename Opnd0, typename Opnd1, typename Opnd2, typename Opnd3>
  2103. inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2, Opnd3>::Ty
  2104. m_MaskedLoad(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2,
  2105.              const Opnd3 &Op3) {
  2106.   return m_Intrinsic<Intrinsic::masked_load>(Op0, Op1, Op2, Op3);
  2107. }
  2108.  
  2109. /// Matches MaskedGather Intrinsic.
  2110. template <typename Opnd0, typename Opnd1, typename Opnd2, typename Opnd3>
  2111. inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2, Opnd3>::Ty
  2112. m_MaskedGather(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2,
  2113.                const Opnd3 &Op3) {
  2114.   return m_Intrinsic<Intrinsic::masked_gather>(Op0, Op1, Op2, Op3);
  2115. }
  2116.  
  2117. template <Intrinsic::ID IntrID, typename T0>
  2118. inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
  2119.   return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
  2120. }
  2121.  
  2122. template <Intrinsic::ID IntrID, typename T0, typename T1>
  2123. inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
  2124.                                                        const T1 &Op1) {
  2125.   return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
  2126. }
  2127.  
  2128. template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
  2129. inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
  2130. m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
  2131.   return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
  2132. }
  2133.  
  2134. template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
  2135.           typename T3>
  2136. inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
  2137. m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
  2138.   return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
  2139. }
  2140.  
  2141. template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
  2142.           typename T3, typename T4>
  2143. inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty
  2144. m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
  2145.             const T4 &Op4) {
  2146.   return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3),
  2147.                       m_Argument<4>(Op4));
  2148. }
  2149.  
  2150. template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
  2151.           typename T3, typename T4, typename T5>
  2152. inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5>::Ty
  2153. m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
  2154.             const T4 &Op4, const T5 &Op5) {
  2155.   return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3, Op4),
  2156.                       m_Argument<5>(Op5));
  2157. }
  2158.  
  2159. // Helper intrinsic matching specializations.
  2160. template <typename Opnd0>
  2161. inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
  2162.   return m_Intrinsic<Intrinsic::bitreverse>(Op0);
  2163. }
  2164.  
  2165. template <typename Opnd0>
  2166. inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
  2167.   return m_Intrinsic<Intrinsic::bswap>(Op0);
  2168. }
  2169.  
  2170. template <typename Opnd0>
  2171. inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) {
  2172.   return m_Intrinsic<Intrinsic::fabs>(Op0);
  2173. }
  2174.  
  2175. template <typename Opnd0>
  2176. inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) {
  2177.   return m_Intrinsic<Intrinsic::canonicalize>(Op0);
  2178. }
  2179.  
  2180. template <typename Opnd0, typename Opnd1>
  2181. inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
  2182.                                                         const Opnd1 &Op1) {
  2183.   return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
  2184. }
  2185.  
  2186. template <typename Opnd0, typename Opnd1>
  2187. inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
  2188.                                                         const Opnd1 &Op1) {
  2189.   return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
  2190. }
  2191.  
  2192. template <typename Opnd0, typename Opnd1, typename Opnd2>
  2193. inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty
  2194. m_FShl(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) {
  2195.   return m_Intrinsic<Intrinsic::fshl>(Op0, Op1, Op2);
  2196. }
  2197.  
  2198. template <typename Opnd0, typename Opnd1, typename Opnd2>
  2199. inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty
  2200. m_FShr(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) {
  2201.   return m_Intrinsic<Intrinsic::fshr>(Op0, Op1, Op2);
  2202. }
  2203.  
  2204. template <typename Opnd0>
  2205. inline typename m_Intrinsic_Ty<Opnd0>::Ty m_Sqrt(const Opnd0 &Op0) {
  2206.   return m_Intrinsic<Intrinsic::sqrt>(Op0);
  2207. }
  2208.  
  2209. template <typename Opnd0, typename Opnd1>
  2210. inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_CopySign(const Opnd0 &Op0,
  2211.                                                             const Opnd1 &Op1) {
  2212.   return m_Intrinsic<Intrinsic::copysign>(Op0, Op1);
  2213. }
  2214.  
  2215. template <typename Opnd0>
  2216. inline typename m_Intrinsic_Ty<Opnd0>::Ty m_VecReverse(const Opnd0 &Op0) {
  2217.   return m_Intrinsic<Intrinsic::experimental_vector_reverse>(Op0);
  2218. }
  2219.  
  2220. //===----------------------------------------------------------------------===//
  2221. // Matchers for two-operands operators with the operators in either order
  2222. //
  2223.  
  2224. /// Matches a BinaryOperator with LHS and RHS in either order.
  2225. template <typename LHS, typename RHS>
  2226. inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
  2227.   return AnyBinaryOp_match<LHS, RHS, true>(L, R);
  2228. }
  2229.  
  2230. /// Matches an ICmp with a predicate over LHS and RHS in either order.
  2231. /// Swaps the predicate if operands are commuted.
  2232. template <typename LHS, typename RHS>
  2233. inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
  2234. m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
  2235.   return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
  2236.                                                                        R);
  2237. }
  2238.  
  2239. /// Matches a specific opcode with LHS and RHS in either order.
  2240. template <typename LHS, typename RHS>
  2241. inline SpecificBinaryOp_match<LHS, RHS, true>
  2242. m_c_BinOp(unsigned Opcode, const LHS &L, const RHS &R) {
  2243.   return SpecificBinaryOp_match<LHS, RHS, true>(Opcode, L, R);
  2244. }
  2245.  
  2246. /// Matches a Add with LHS and RHS in either order.
  2247. template <typename LHS, typename RHS>
  2248. inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L,
  2249.                                                                 const RHS &R) {
  2250.   return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R);
  2251. }
  2252.  
  2253. /// Matches a Mul with LHS and RHS in either order.
  2254. template <typename LHS, typename RHS>
  2255. inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L,
  2256.                                                                 const RHS &R) {
  2257.   return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R);
  2258. }
  2259.  
  2260. /// Matches an And with LHS and RHS in either order.
  2261. template <typename LHS, typename RHS>
  2262. inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L,
  2263.                                                                 const RHS &R) {
  2264.   return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R);
  2265. }
  2266.  
  2267. /// Matches an Or with LHS and RHS in either order.
  2268. template <typename LHS, typename RHS>
  2269. inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L,
  2270.                                                               const RHS &R) {
  2271.   return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R);
  2272. }
  2273.  
  2274. /// Matches an Xor with LHS and RHS in either order.
  2275. template <typename LHS, typename RHS>
  2276. inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L,
  2277.                                                                 const RHS &R) {
  2278.   return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R);
  2279. }
  2280.  
  2281. /// Matches a 'Neg' as 'sub 0, V'.
  2282. template <typename ValTy>
  2283. inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub>
  2284. m_Neg(const ValTy &V) {
  2285.   return m_Sub(m_ZeroInt(), V);
  2286. }
  2287.  
  2288. /// Matches a 'Neg' as 'sub nsw 0, V'.
  2289. template <typename ValTy>
  2290. inline OverflowingBinaryOp_match<cst_pred_ty<is_zero_int>, ValTy,
  2291.                                  Instruction::Sub,
  2292.                                  OverflowingBinaryOperator::NoSignedWrap>
  2293. m_NSWNeg(const ValTy &V) {
  2294.   return m_NSWSub(m_ZeroInt(), V);
  2295. }
  2296.  
  2297. /// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
  2298. /// NOTE: we first match the 'Not' (by matching '-1'),
  2299. /// and only then match the inner matcher!
  2300. template <typename ValTy>
  2301. inline BinaryOp_match<cst_pred_ty<is_all_ones>, ValTy, Instruction::Xor, true>
  2302. m_Not(const ValTy &V) {
  2303.   return m_c_Xor(m_AllOnes(), V);
  2304. }
  2305.  
  2306. template <typename ValTy> struct NotForbidUndef_match {
  2307.   ValTy Val;
  2308.   NotForbidUndef_match(const ValTy &V) : Val(V) {}
  2309.  
  2310.   template <typename OpTy> bool match(OpTy *V) {
  2311.     // We do not use m_c_Xor because that could match an arbitrary APInt that is
  2312.     // not -1 as C and then fail to match the other operand if it is -1.
  2313.     // This code should still work even when both operands are constants.
  2314.     Value *X;
  2315.     const APInt *C;
  2316.     if (m_Xor(m_Value(X), m_APIntForbidUndef(C)).match(V) && C->isAllOnes())
  2317.       return Val.match(X);
  2318.     if (m_Xor(m_APIntForbidUndef(C), m_Value(X)).match(V) && C->isAllOnes())
  2319.       return Val.match(X);
  2320.     return false;
  2321.   }
  2322. };
  2323.  
  2324. /// Matches a bitwise 'not' as 'xor V, -1' or 'xor -1, V'. For vectors, the
  2325. /// constant value must be composed of only -1 scalar elements.
  2326. template <typename ValTy>
  2327. inline NotForbidUndef_match<ValTy> m_NotForbidUndef(const ValTy &V) {
  2328.   return NotForbidUndef_match<ValTy>(V);
  2329. }
  2330.  
  2331. /// Matches an SMin with LHS and RHS in either order.
  2332. template <typename LHS, typename RHS>
  2333. inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>
  2334. m_c_SMin(const LHS &L, const RHS &R) {
  2335.   return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R);
  2336. }
  2337. /// Matches an SMax with LHS and RHS in either order.
  2338. template <typename LHS, typename RHS>
  2339. inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>
  2340. m_c_SMax(const LHS &L, const RHS &R) {
  2341.   return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R);
  2342. }
  2343. /// Matches a UMin with LHS and RHS in either order.
  2344. template <typename LHS, typename RHS>
  2345. inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>
  2346. m_c_UMin(const LHS &L, const RHS &R) {
  2347.   return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R);
  2348. }
  2349. /// Matches a UMax with LHS and RHS in either order.
  2350. template <typename LHS, typename RHS>
  2351. inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>
  2352. m_c_UMax(const LHS &L, const RHS &R) {
  2353.   return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R);
  2354. }
  2355.  
  2356. template <typename LHS, typename RHS>
  2357. inline match_combine_or<
  2358.     match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>,
  2359.                      MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>>,
  2360.     match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>,
  2361.                      MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>>>
  2362. m_c_MaxOrMin(const LHS &L, const RHS &R) {
  2363.   return m_CombineOr(m_CombineOr(m_c_SMax(L, R), m_c_SMin(L, R)),
  2364.                      m_CombineOr(m_c_UMax(L, R), m_c_UMin(L, R)));
  2365. }
  2366.  
  2367. /// Matches FAdd with LHS and RHS in either order.
  2368. template <typename LHS, typename RHS>
  2369. inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true>
  2370. m_c_FAdd(const LHS &L, const RHS &R) {
  2371.   return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R);
  2372. }
  2373.  
  2374. /// Matches FMul with LHS and RHS in either order.
  2375. template <typename LHS, typename RHS>
  2376. inline BinaryOp_match<LHS, RHS, Instruction::FMul, true>
  2377. m_c_FMul(const LHS &L, const RHS &R) {
  2378.   return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R);
  2379. }
  2380.  
  2381. template <typename Opnd_t> struct Signum_match {
  2382.   Opnd_t Val;
  2383.   Signum_match(const Opnd_t &V) : Val(V) {}
  2384.  
  2385.   template <typename OpTy> bool match(OpTy *V) {
  2386.     unsigned TypeSize = V->getType()->getScalarSizeInBits();
  2387.     if (TypeSize == 0)
  2388.       return false;
  2389.  
  2390.     unsigned ShiftWidth = TypeSize - 1;
  2391.     Value *OpL = nullptr, *OpR = nullptr;
  2392.  
  2393.     // This is the representation of signum we match:
  2394.     //
  2395.     //  signum(x) == (x >> 63) | (-x >>u 63)
  2396.     //
  2397.     // An i1 value is its own signum, so it's correct to match
  2398.     //
  2399.     //  signum(x) == (x >> 0)  | (-x >>u 0)
  2400.     //
  2401.     // for i1 values.
  2402.  
  2403.     auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
  2404.     auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
  2405.     auto Signum = m_Or(LHS, RHS);
  2406.  
  2407.     return Signum.match(V) && OpL == OpR && Val.match(OpL);
  2408.   }
  2409. };
  2410.  
  2411. /// Matches a signum pattern.
  2412. ///
  2413. /// signum(x) =
  2414. ///      x >  0  ->  1
  2415. ///      x == 0  ->  0
  2416. ///      x <  0  -> -1
  2417. template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
  2418.   return Signum_match<Val_t>(V);
  2419. }
  2420.  
  2421. template <int Ind, typename Opnd_t> struct ExtractValue_match {
  2422.   Opnd_t Val;
  2423.   ExtractValue_match(const Opnd_t &V) : Val(V) {}
  2424.  
  2425.   template <typename OpTy> bool match(OpTy *V) {
  2426.     if (auto *I = dyn_cast<ExtractValueInst>(V)) {
  2427.       // If Ind is -1, don't inspect indices
  2428.       if (Ind != -1 &&
  2429.           !(I->getNumIndices() == 1 && I->getIndices()[0] == (unsigned)Ind))
  2430.         return false;
  2431.       return Val.match(I->getAggregateOperand());
  2432.     }
  2433.     return false;
  2434.   }
  2435. };
  2436.  
  2437. /// Match a single index ExtractValue instruction.
  2438. /// For example m_ExtractValue<1>(...)
  2439. template <int Ind, typename Val_t>
  2440. inline ExtractValue_match<Ind, Val_t> m_ExtractValue(const Val_t &V) {
  2441.   return ExtractValue_match<Ind, Val_t>(V);
  2442. }
  2443.  
  2444. /// Match an ExtractValue instruction with any index.
  2445. /// For example m_ExtractValue(...)
  2446. template <typename Val_t>
  2447. inline ExtractValue_match<-1, Val_t> m_ExtractValue(const Val_t &V) {
  2448.   return ExtractValue_match<-1, Val_t>(V);
  2449. }
  2450.  
  2451. /// Matcher for a single index InsertValue instruction.
  2452. template <int Ind, typename T0, typename T1> struct InsertValue_match {
  2453.   T0 Op0;
  2454.   T1 Op1;
  2455.  
  2456.   InsertValue_match(const T0 &Op0, const T1 &Op1) : Op0(Op0), Op1(Op1) {}
  2457.  
  2458.   template <typename OpTy> bool match(OpTy *V) {
  2459.     if (auto *I = dyn_cast<InsertValueInst>(V)) {
  2460.       return Op0.match(I->getOperand(0)) && Op1.match(I->getOperand(1)) &&
  2461.              I->getNumIndices() == 1 && Ind == I->getIndices()[0];
  2462.     }
  2463.     return false;
  2464.   }
  2465. };
  2466.  
  2467. /// Matches a single index InsertValue instruction.
  2468. template <int Ind, typename Val_t, typename Elt_t>
  2469. inline InsertValue_match<Ind, Val_t, Elt_t> m_InsertValue(const Val_t &Val,
  2470.                                                           const Elt_t &Elt) {
  2471.   return InsertValue_match<Ind, Val_t, Elt_t>(Val, Elt);
  2472. }
  2473.  
  2474. /// Matches patterns for `vscale`. This can either be a call to `llvm.vscale` or
  2475. /// the constant expression
  2476. ///  `ptrtoint(gep <vscale x 1 x i8>, <vscale x 1 x i8>* null, i32 1>`
  2477. /// under the right conditions determined by DataLayout.
  2478. struct VScaleVal_match {
  2479.   const DataLayout &DL;
  2480.   VScaleVal_match(const DataLayout &DL) : DL(DL) {}
  2481.  
  2482.   template <typename ITy> bool match(ITy *V) {
  2483.     if (m_Intrinsic<Intrinsic::vscale>().match(V))
  2484.       return true;
  2485.  
  2486.     Value *Ptr;
  2487.     if (m_PtrToInt(m_Value(Ptr)).match(V)) {
  2488.       if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
  2489.         auto *DerefTy = GEP->getSourceElementType();
  2490.         if (GEP->getNumIndices() == 1 && isa<ScalableVectorType>(DerefTy) &&
  2491.             m_Zero().match(GEP->getPointerOperand()) &&
  2492.             m_SpecificInt(1).match(GEP->idx_begin()->get()) &&
  2493.             DL.getTypeAllocSizeInBits(DerefTy).getKnownMinValue() == 8)
  2494.           return true;
  2495.       }
  2496.     }
  2497.  
  2498.     return false;
  2499.   }
  2500. };
  2501.  
  2502. inline VScaleVal_match m_VScale(const DataLayout &DL) {
  2503.   return VScaleVal_match(DL);
  2504. }
  2505.  
  2506. template <typename LHS, typename RHS, unsigned Opcode, bool Commutable = false>
  2507. struct LogicalOp_match {
  2508.   LHS L;
  2509.   RHS R;
  2510.  
  2511.   LogicalOp_match(const LHS &L, const RHS &R) : L(L), R(R) {}
  2512.  
  2513.   template <typename T> bool match(T *V) {
  2514.     auto *I = dyn_cast<Instruction>(V);
  2515.     if (!I || !I->getType()->isIntOrIntVectorTy(1))
  2516.       return false;
  2517.  
  2518.     if (I->getOpcode() == Opcode) {
  2519.       auto *Op0 = I->getOperand(0);
  2520.       auto *Op1 = I->getOperand(1);
  2521.       return (L.match(Op0) && R.match(Op1)) ||
  2522.              (Commutable && L.match(Op1) && R.match(Op0));
  2523.     }
  2524.  
  2525.     if (auto *Select = dyn_cast<SelectInst>(I)) {
  2526.       auto *Cond = Select->getCondition();
  2527.       auto *TVal = Select->getTrueValue();
  2528.       auto *FVal = Select->getFalseValue();
  2529.  
  2530.       // Don't match a scalar select of bool vectors.
  2531.       // Transforms expect a single type for operands if this matches.
  2532.       if (Cond->getType() != Select->getType())
  2533.         return false;
  2534.  
  2535.       if (Opcode == Instruction::And) {
  2536.         auto *C = dyn_cast<Constant>(FVal);
  2537.         if (C && C->isNullValue())
  2538.           return (L.match(Cond) && R.match(TVal)) ||
  2539.                  (Commutable && L.match(TVal) && R.match(Cond));
  2540.       } else {
  2541.         assert(Opcode == Instruction::Or);
  2542.         auto *C = dyn_cast<Constant>(TVal);
  2543.         if (C && C->isOneValue())
  2544.           return (L.match(Cond) && R.match(FVal)) ||
  2545.                  (Commutable && L.match(FVal) && R.match(Cond));
  2546.       }
  2547.     }
  2548.  
  2549.     return false;
  2550.   }
  2551. };
  2552.  
  2553. /// Matches L && R either in the form of L & R or L ? R : false.
  2554. /// Note that the latter form is poison-blocking.
  2555. template <typename LHS, typename RHS>
  2556. inline LogicalOp_match<LHS, RHS, Instruction::And> m_LogicalAnd(const LHS &L,
  2557.                                                                 const RHS &R) {
  2558.   return LogicalOp_match<LHS, RHS, Instruction::And>(L, R);
  2559. }
  2560.  
  2561. /// Matches L && R where L and R are arbitrary values.
  2562. inline auto m_LogicalAnd() { return m_LogicalAnd(m_Value(), m_Value()); }
  2563.  
  2564. /// Matches L && R with LHS and RHS in either order.
  2565. template <typename LHS, typename RHS>
  2566. inline LogicalOp_match<LHS, RHS, Instruction::And, true>
  2567. m_c_LogicalAnd(const LHS &L, const RHS &R) {
  2568.   return LogicalOp_match<LHS, RHS, Instruction::And, true>(L, R);
  2569. }
  2570.  
  2571. /// Matches L || R either in the form of L | R or L ? true : R.
  2572. /// Note that the latter form is poison-blocking.
  2573. template <typename LHS, typename RHS>
  2574. inline LogicalOp_match<LHS, RHS, Instruction::Or> m_LogicalOr(const LHS &L,
  2575.                                                               const RHS &R) {
  2576.   return LogicalOp_match<LHS, RHS, Instruction::Or>(L, R);
  2577. }
  2578.  
  2579. /// Matches L || R where L and R are arbitrary values.
  2580. inline auto m_LogicalOr() { return m_LogicalOr(m_Value(), m_Value()); }
  2581.  
  2582. /// Matches L || R with LHS and RHS in either order.
  2583. template <typename LHS, typename RHS>
  2584. inline LogicalOp_match<LHS, RHS, Instruction::Or, true>
  2585. m_c_LogicalOr(const LHS &L, const RHS &R) {
  2586.   return LogicalOp_match<LHS, RHS, Instruction::Or, true>(L, R);
  2587. }
  2588.  
  2589. /// Matches either L && R or L || R,
  2590. /// either one being in the either binary or logical form.
  2591. /// Note that the latter form is poison-blocking.
  2592. template <typename LHS, typename RHS, bool Commutable = false>
  2593. inline auto m_LogicalOp(const LHS &L, const RHS &R) {
  2594.   return m_CombineOr(
  2595.       LogicalOp_match<LHS, RHS, Instruction::And, Commutable>(L, R),
  2596.       LogicalOp_match<LHS, RHS, Instruction::Or, Commutable>(L, R));
  2597. }
  2598.  
  2599. /// Matches either L && R or L || R where L and R are arbitrary values.
  2600. inline auto m_LogicalOp() { return m_LogicalOp(m_Value(), m_Value()); }
  2601.  
  2602. /// Matches either L && R or L || R with LHS and RHS in either order.
  2603. template <typename LHS, typename RHS>
  2604. inline auto m_c_LogicalOp(const LHS &L, const RHS &R) {
  2605.   return m_LogicalOp<LHS, RHS, /*Commutable=*/true>(L, R);
  2606. }
  2607.  
  2608. } // end namespace PatternMatch
  2609. } // end namespace llvm
  2610.  
  2611. #endif // LLVM_IR_PATTERNMATCH_H
  2612.