1//==--------------- llvm/CodeGen/SDPatternMatch.h ---------------*- 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/// \file
9/// Contains matchers for matching SelectionDAG nodes and values.
10///
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CODEGEN_SDPATTERNMATCH_H
14#define LLVM_CODEGEN_SDPATTERNMATCH_H
15
16#include "llvm/ADT/APInt.h"
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallBitVector.h"
20#include "llvm/ADT/bit.h"
21#include "llvm/CodeGen/SelectionDAG.h"
22#include "llvm/CodeGen/SelectionDAGNodes.h"
23#include "llvm/CodeGen/TargetLowering.h"
24#include "llvm/Support/KnownBits.h"
25#include "llvm/Support/TypeSize.h"
26
27#include <type_traits>
28
29namespace llvm {
30namespace SDPatternMatch {
31
32template <typename Pattern>
33[[nodiscard]] bool sd_match(SDValue N, Pattern &&P) {
34 return P.match(N);
35}
36
37template <typename Pattern>
38[[nodiscard]] bool sd_match(SDNode *N, Pattern &&P) {
39 return sd_match(SDValue(N, 0), P);
40}
41
42// === Utilities ===
43struct Value_match {
44 SDValue MatchVal;
45
46 Value_match() = default;
47
48 explicit Value_match(SDValue Match) : MatchVal(Match) {}
49
50 bool match(SDValue N) {
51 if (MatchVal)
52 return MatchVal == N;
53 return N.getNode();
54 }
55};
56
57/// Match any valid SDValue.
58inline Value_match m_Value() { return Value_match(); }
59
60inline Value_match m_Specific(SDValue N) {
61 assert(N);
62 return Value_match(N);
63}
64
65template <unsigned ResNo, typename Pattern> struct Result_match {
66 Pattern P;
67
68 explicit Result_match(const Pattern &P) : P(P) {}
69
70 bool match(SDValue N) { return N.getResNo() == ResNo && P.match(N); }
71};
72
73/// Match only if the SDValue is a certain result at ResNo.
74template <unsigned ResNo, typename Pattern>
75inline Result_match<ResNo, Pattern> m_Result(const Pattern &P) {
76 return Result_match<ResNo, Pattern>(P);
77}
78
79struct DeferredValue_match {
80 SDValue &MatchVal;
81
82 explicit DeferredValue_match(SDValue &Match) : MatchVal(Match) {}
83
84 bool match(SDValue N) { return N == MatchVal; }
85};
86
87/// Similar to m_Specific, but the specific value to match is determined by
88/// another sub-pattern in the same sd_match() expression. For instance,
89/// We cannot match `(add V, V)` with `m_Add(m_Value(X), m_Specific(X))` since
90/// `X` is not initialized at the time it got copied into `m_Specific`. Instead,
91/// we should use `m_Add(m_Value(X), m_Deferred(X))`.
92inline DeferredValue_match m_Deferred(SDValue &V) {
93 return DeferredValue_match(V);
94}
95
96struct Opcode_match {
97 unsigned Opcode;
98
99 explicit Opcode_match(unsigned Opc) : Opcode(Opc) {}
100
101 bool match(SDValue N) { return N->getOpcode() == Opcode; }
102};
103
104template <unsigned Opcode> struct FixedOpcode_match {
105 bool match(SDValue N) { return N->getOpcode() == Opcode; }
106};
107
108// === Patterns combinators ===
109template <typename... Preds> struct And {
110 bool match(SDValue N) { return true; }
111};
112
113template <typename Pred, typename... Preds>
114struct And<Pred, Preds...> : And<Preds...> {
115 Pred P;
116 And(const Pred &p, const Preds &...preds) : And<Preds...>(preds...), P(p) {}
117
118 bool match(SDValue N) { return P.match(N) && And<Preds...>::match(N); }
119};
120
121template <typename... Preds> struct Or {
122 bool match(SDValue N) { return false; }
123};
124
125template <typename Pred, typename... Preds>
126struct Or<Pred, Preds...> : Or<Preds...> {
127 Pred P;
128 Or(const Pred &p, const Preds &...preds) : Or<Preds...>(preds...), P(p) {}
129
130 bool match(SDValue N) { return P.match(N) || Or<Preds...>::match(N); }
131};
132
133template <typename Pred> struct Not {
134 Pred P;
135
136 explicit Not(const Pred &P) : P(P) {}
137
138 bool match(SDValue N) { return !P.match(N); }
139};
140// Explicit deduction guide.
141template <typename Pred> Not(const Pred &P) -> Not<Pred>;
142
143/// Match if the inner pattern does NOT match.
144template <typename Pred> inline Not<Pred> m_Unless(const Pred &P) {
145 return Not{P};
146}
147
148template <typename... Preds> And<Preds...> m_AllOf(const Preds &...preds) {
149 return And<Preds...>(preds...);
150}
151
152template <typename... Preds> Or<Preds...> m_AnyOf(const Preds &...preds) {
153 return Or<Preds...>(preds...);
154}
155
156template <typename... Preds> auto m_NoneOf(const Preds &...preds) {
157 return m_Unless(m_AnyOf(preds...));
158}
159
160template <unsigned Opcode> inline auto m_SpecificOpc() {
161 return FixedOpcode_match<Opcode>();
162}
163
164inline Opcode_match m_SpecificOpc(unsigned Opcode) {
165 return Opcode_match(Opcode);
166}
167
168inline auto m_Undef() {
169 return m_AnyOf(preds: Opcode_match(ISD::UNDEF), preds: Opcode_match(ISD::POISON));
170}
171
172inline Opcode_match m_Poison() { return Opcode_match(ISD::POISON); }
173
174template <unsigned NumUses, typename Pattern> struct NUses_match {
175 Pattern P;
176
177 explicit NUses_match(const Pattern &P) : P(P) {}
178
179 bool match(SDValue N) {
180 // SDNode::hasNUsesOfValue is pretty expensive when the SDNode produces
181 // multiple results, hence we check the subsequent pattern here before
182 // checking the number of value users.
183 return P.match(N) && N->hasNUsesOfValue(NUses: NumUses, Value: N.getResNo());
184 }
185};
186
187template <typename Pattern>
188inline NUses_match<1, Pattern> m_OneUse(const Pattern &P) {
189 return NUses_match<1, Pattern>(P);
190}
191template <unsigned N, typename Pattern>
192inline NUses_match<N, Pattern> m_NUses(const Pattern &P) {
193 return NUses_match<N, Pattern>(P);
194}
195
196inline NUses_match<1, Value_match> m_OneUse() {
197 return NUses_match<1, Value_match>(m_Value());
198}
199template <unsigned N> inline NUses_match<N, Value_match> m_NUses() {
200 return NUses_match<N, Value_match>(m_Value());
201}
202
203struct Value_bind {
204 SDValue &BindVal;
205
206 Value_bind(SDValue &N) : BindVal(N) {}
207
208 bool match(SDValue N) {
209 BindVal = N;
210 return true;
211 }
212};
213
214inline auto m_Value(SDValue &N) { return Value_bind(N); }
215/// Conditionally bind an SDValue based on the predicate.
216template <typename PredPattern>
217inline auto m_Value(SDValue &N, const PredPattern &P) {
218 return m_AllOf(P, Value_bind(N));
219}
220
221template <typename Pattern, typename PredFuncT> struct TLI_pred_match {
222 Pattern P;
223 PredFuncT PredFunc;
224
225 TLI_pred_match(const PredFuncT &Pred, const Pattern &P)
226 : P(P), PredFunc(Pred) {}
227
228 bool match(SDValue N) { return PredFunc(N) && P.match(N); }
229};
230
231// Explicit deduction guide.
232template <typename PredFuncT, typename Pattern>
233TLI_pred_match(const PredFuncT &Pred, const Pattern &P)
234 -> TLI_pred_match<Pattern, PredFuncT>;
235
236/// Match legal SDNodes based on the information provided by TargetLowering.
237template <typename Pattern>
238inline auto m_LegalOp(const SelectionDAG &DAG, const Pattern &P) {
239 return TLI_pred_match{[&DAG](SDValue N) {
240 return DAG.getTargetLoweringInfo().isOperationLegal(
241 Op: N->getOpcode(), VT: N.getValueType());
242 },
243 P};
244}
245
246// === Value type ===
247
248template <typename Pattern> struct ValueType_bind {
249 EVT &BindVT;
250 Pattern P;
251
252 explicit ValueType_bind(EVT &Bind, const Pattern &P) : BindVT(Bind), P(P) {}
253
254 bool match(SDValue N) {
255 BindVT = N.getValueType();
256 return P.match(N);
257 }
258};
259
260template <typename Pattern>
261ValueType_bind(const Pattern &P) -> ValueType_bind<Pattern>;
262
263/// Retreive the ValueType of the current SDValue.
264inline auto m_VT(EVT &VT) { return ValueType_bind(VT, m_Value()); }
265
266template <typename Pattern> inline auto m_VT(EVT &VT, const Pattern &P) {
267 return ValueType_bind(VT, P);
268}
269
270template <typename Pattern, typename PredFuncT> struct ValueType_match {
271 PredFuncT PredFunc;
272 Pattern P;
273
274 ValueType_match(const PredFuncT &Pred, const Pattern &P)
275 : PredFunc(Pred), P(P) {}
276
277 bool match(SDValue N) { return PredFunc(N.getValueType()) && P.match(N); }
278};
279
280// Explicit deduction guide.
281template <typename PredFuncT, typename Pattern>
282ValueType_match(const PredFuncT &Pred, const Pattern &P)
283 -> ValueType_match<Pattern, PredFuncT>;
284
285/// Match a specific ValueType.
286template <typename Pattern>
287inline auto m_SpecificVT(EVT RefVT, const Pattern &P) {
288 return ValueType_match{[=](EVT VT) { return VT == RefVT; }, P};
289}
290inline auto m_SpecificVT(EVT RefVT) {
291 return ValueType_match{[=](EVT VT) { return VT == RefVT; }, m_Value()};
292}
293
294inline auto m_Glue() { return m_SpecificVT(RefVT: MVT::Glue); }
295inline auto m_OtherVT() { return m_SpecificVT(RefVT: MVT::Other); }
296
297/// Match a scalar ValueType.
298template <typename Pattern>
299inline auto m_SpecificScalarVT(EVT RefVT, const Pattern &P) {
300 return ValueType_match{[=](EVT VT) { return VT.getScalarType() == RefVT; },
301 P};
302}
303inline auto m_SpecificScalarVT(EVT RefVT) {
304 return ValueType_match{[=](EVT VT) { return VT.getScalarType() == RefVT; },
305 m_Value()};
306}
307
308/// Match a vector ValueType.
309template <typename Pattern>
310inline auto m_SpecificVectorElementVT(EVT RefVT, const Pattern &P) {
311 return ValueType_match{[=](EVT VT) {
312 return VT.isVector() &&
313 VT.getVectorElementType() == RefVT;
314 },
315 P};
316}
317inline auto m_SpecificVectorElementVT(EVT RefVT) {
318 return ValueType_match{[=](EVT VT) {
319 return VT.isVector() &&
320 VT.getVectorElementType() == RefVT;
321 },
322 m_Value()};
323}
324
325/// Match any integer ValueTypes.
326template <typename Pattern> inline auto m_IntegerVT(const Pattern &P) {
327 return ValueType_match{[](EVT VT) { return VT.isInteger(); }, P};
328}
329inline auto m_IntegerVT() {
330 return ValueType_match{[](EVT VT) { return VT.isInteger(); }, m_Value()};
331}
332
333/// Match any floating point ValueTypes.
334template <typename Pattern> inline auto m_FloatingPointVT(const Pattern &P) {
335 return ValueType_match{[](EVT VT) { return VT.isFloatingPoint(); }, P};
336}
337inline auto m_FloatingPointVT() {
338 return ValueType_match{[](EVT VT) { return VT.isFloatingPoint(); },
339 m_Value()};
340}
341
342/// Match any vector ValueTypes.
343template <typename Pattern> inline auto m_VectorVT(const Pattern &P) {
344 return ValueType_match{[](EVT VT) { return VT.isVector(); }, P};
345}
346inline auto m_VectorVT() {
347 return ValueType_match{[](EVT VT) { return VT.isVector(); }, m_Value()};
348}
349
350/// Match fixed-length vector ValueTypes.
351template <typename Pattern> inline auto m_FixedVectorVT(const Pattern &P) {
352 return ValueType_match{[](EVT VT) { return VT.isFixedLengthVector(); }, P};
353}
354inline auto m_FixedVectorVT() {
355 return ValueType_match{[](EVT VT) { return VT.isFixedLengthVector(); },
356 m_Value()};
357}
358
359/// Match scalable vector ValueTypes.
360template <typename Pattern> inline auto m_ScalableVectorVT(const Pattern &P) {
361 return ValueType_match{[](EVT VT) { return VT.isScalableVector(); }, P};
362}
363inline auto m_ScalableVectorVT() {
364 return ValueType_match{[](EVT VT) { return VT.isScalableVector(); },
365 m_Value()};
366}
367
368/// Match legal ValueTypes based on the information provided by TargetLowering.
369template <typename Pattern>
370inline auto m_LegalType(const SelectionDAG &DAG, const Pattern &P) {
371 return TLI_pred_match{[&DAG](SDValue N) {
372 return DAG.getTargetLoweringInfo().isTypeLegal(
373 VT: N.getValueType());
374 },
375 P};
376}
377
378// === Generic node matching ===
379template <unsigned OpIdx, typename... OpndPreds> struct Operands_match {
380 bool match(SDValue N) {
381 // Returns false if there are more operands than predicates;
382 return N->getNumOperands() == OpIdx;
383 }
384};
385
386template <unsigned OpIdx, typename OpndPred, typename... OpndPreds>
387struct Operands_match<OpIdx, OpndPred, OpndPreds...>
388 : Operands_match<OpIdx + 1, OpndPreds...> {
389 OpndPred P;
390
391 Operands_match(const OpndPred &p, const OpndPreds &...preds)
392 : Operands_match<OpIdx + 1, OpndPreds...>(preds...), P(p) {}
393
394 bool match(SDValue N) {
395 if (OpIdx < N->getNumOperands())
396 return P.match(N->getOperand(Num: OpIdx)) &&
397 Operands_match<OpIdx + 1, OpndPreds...>::match(N);
398
399 // This is the case where there are more predicates than operands.
400 return false;
401 }
402};
403
404template <unsigned Opcode, typename... OpndPreds>
405auto m_Node(const OpndPreds &...Preds) {
406 return m_AllOf(m_SpecificOpc<Opcode>(),
407 Operands_match<0, OpndPreds...>(Preds...));
408}
409
410template <typename... OpndPreds>
411auto m_Node(unsigned Opcode, const OpndPreds &...preds) {
412 return m_AllOf(m_SpecificOpc(Opcode),
413 Operands_match<0, OpndPreds...>(preds...));
414}
415
416/// Provide number of operands that are not chain or glue, as well as the first
417/// index of such operand.
418template <bool ExcludeChain> struct EffectiveOperands {
419 unsigned Size = 0;
420 unsigned FirstIndex = 0;
421
422 explicit EffectiveOperands(SDValue N) : Size(N->getNumOperands()) {
423 if (ExcludeChain) {
424 // Glue if present, is the last operand.
425 if (Size != 0 && N->getOperand(Num: Size - 1).getValueType() == MVT::Glue)
426 --Size;
427 // Chain if present, is the first operand.
428 if (Size != 0 && N->getOperand(Num: 0).getValueType() == MVT::Other) {
429 ++FirstIndex;
430 --Size;
431 }
432 }
433 }
434};
435
436// === Ternary operations ===
437template <typename T0_P, typename T1_P, typename T2_P, bool Commutable = false,
438 bool ExcludeChain = false>
439struct TernaryOpc_match {
440 unsigned Opcode;
441 T0_P Op0;
442 T1_P Op1;
443 T2_P Op2;
444
445 TernaryOpc_match(unsigned Opc, const T0_P &Op0, const T1_P &Op1,
446 const T2_P &Op2)
447 : Opcode(Opc), Op0(Op0), Op1(Op1), Op2(Op2) {}
448
449 bool match(SDValue N) {
450 if (sd_match(N, P: m_SpecificOpc(Opcode))) {
451 EffectiveOperands<ExcludeChain> EO(N);
452 assert(EO.Size == 3);
453 return ((Op0.match(N->getOperand(Num: EO.FirstIndex)) &&
454 Op1.match(N->getOperand(Num: EO.FirstIndex + 1))) ||
455 (Commutable && Op0.match(N->getOperand(Num: EO.FirstIndex + 1)) &&
456 Op1.match(N->getOperand(Num: EO.FirstIndex)))) &&
457 Op2.match(N->getOperand(Num: EO.FirstIndex + 2));
458 }
459
460 return false;
461 }
462};
463
464struct CondCode_match {
465 std::optional<ISD::CondCode> CCToMatch;
466 ISD::CondCode *BindCC = nullptr;
467
468 explicit CondCode_match(ISD::CondCode CC) : CCToMatch(CC) {}
469
470 explicit CondCode_match(ISD::CondCode *CC) : BindCC(CC) {}
471
472 bool match(SDValue N) {
473 if (auto *CC = dyn_cast<CondCodeSDNode>(Val: N.getNode())) {
474 if (CCToMatch && *CCToMatch != CC->get())
475 return false;
476
477 if (BindCC)
478 *BindCC = CC->get();
479 return true;
480 }
481
482 return false;
483 }
484};
485
486/// Match any conditional code SDNode.
487inline CondCode_match m_CondCode() { return CondCode_match(nullptr); }
488/// Match any conditional code SDNode and return its ISD::CondCode value.
489inline CondCode_match m_CondCode(ISD::CondCode &CC) {
490 return CondCode_match(&CC);
491}
492/// Match a conditional code SDNode with a specific ISD::CondCode.
493inline CondCode_match m_SpecificCondCode(ISD::CondCode CC) {
494 return CondCode_match(CC);
495}
496
497/// Match a SETCC with any condition code.
498template <typename T0_P, typename T1_P>
499inline TernaryOpc_match<T0_P, T1_P, CondCode_match> m_SetCC(const T0_P &LHS,
500 const T1_P &RHS) {
501 return TernaryOpc_match<T0_P, T1_P, CondCode_match>(ISD::SETCC, LHS, RHS,
502 m_CondCode());
503}
504
505/// Match a SETCC with any condition code and bind the condition code to CC.
506template <typename T0_P, typename T1_P>
507inline TernaryOpc_match<T0_P, T1_P, CondCode_match>
508m_SetCC(ISD::CondCode &CC, const T0_P &LHS, const T1_P &RHS) {
509 return TernaryOpc_match<T0_P, T1_P, CondCode_match>(ISD::SETCC, LHS, RHS,
510 m_CondCode(CC));
511}
512
513/// Match a SETCC with a specific condition code.
514template <typename T0_P, typename T1_P>
515inline TernaryOpc_match<T0_P, T1_P, CondCode_match>
516m_SpecificSetCC(ISD::CondCode CC, const T0_P &LHS, const T1_P &RHS) {
517 return TernaryOpc_match<T0_P, T1_P, CondCode_match>(ISD::SETCC, LHS, RHS,
518 m_SpecificCondCode(CC));
519}
520
521/// Match a SETCC with any condition code, allowing the operands to be
522/// commuted.
523template <typename T0_P, typename T1_P>
524inline TernaryOpc_match<T0_P, T1_P, CondCode_match, true, false>
525m_c_SetCC(const T0_P &LHS, const T1_P &RHS) {
526 return TernaryOpc_match<T0_P, T1_P, CondCode_match, true, false>(
527 ISD::SETCC, LHS, RHS, m_CondCode());
528}
529
530/// Match a SETCC with any condition code, allowing the operands to be
531/// commuted, and bind the condition code to CC.
532template <typename T0_P, typename T1_P>
533inline TernaryOpc_match<T0_P, T1_P, CondCode_match, true, false>
534m_c_SetCC(ISD::CondCode &CC, const T0_P &LHS, const T1_P &RHS) {
535 return TernaryOpc_match<T0_P, T1_P, CondCode_match, true, false>(
536 ISD::SETCC, LHS, RHS, m_CondCode(CC));
537}
538
539/// Match a SETCC with a specific condition code, allowing the operands to be
540/// commuted.
541template <typename T0_P, typename T1_P>
542inline TernaryOpc_match<T0_P, T1_P, CondCode_match, true, false>
543m_c_SpecificSetCC(ISD::CondCode CC, const T0_P &LHS, const T1_P &RHS) {
544 return TernaryOpc_match<T0_P, T1_P, CondCode_match, true, false>(
545 ISD::SETCC, LHS, RHS, m_SpecificCondCode(CC));
546}
547
548template <typename T0_P, typename T1_P, typename T2_P>
549inline TernaryOpc_match<T0_P, T1_P, T2_P>
550m_Select(const T0_P &Cond, const T1_P &T, const T2_P &F) {
551 return TernaryOpc_match<T0_P, T1_P, T2_P>(ISD::SELECT, Cond, T, F);
552}
553
554template <typename T0_P, typename T1_P, typename T2_P>
555inline TernaryOpc_match<T0_P, T1_P, T2_P>
556m_VSelect(const T0_P &Cond, const T1_P &T, const T2_P &F) {
557 return TernaryOpc_match<T0_P, T1_P, T2_P>(ISD::VSELECT, Cond, T, F);
558}
559
560template <typename T0_P, typename T1_P, typename T2_P>
561inline auto m_SelectLike(const T0_P &Cond, const T1_P &T, const T2_P &F) {
562 return m_AnyOf(m_Select(Cond, T, F), m_VSelect(Cond, T, F));
563}
564
565template <typename T0_P, typename T1_P, typename T2_P>
566inline Result_match<0, TernaryOpc_match<T0_P, T1_P, T2_P>>
567m_Load(const T0_P &Ch, const T1_P &Ptr, const T2_P &Offset) {
568 return m_Result<0>(
569 TernaryOpc_match<T0_P, T1_P, T2_P>(ISD::LOAD, Ch, Ptr, Offset));
570}
571
572template <typename T0_P, typename T1_P, typename T2_P>
573inline TernaryOpc_match<T0_P, T1_P, T2_P>
574m_InsertElt(const T0_P &Vec, const T1_P &Val, const T2_P &Idx) {
575 return TernaryOpc_match<T0_P, T1_P, T2_P>(ISD::INSERT_VECTOR_ELT, Vec, Val,
576 Idx);
577}
578
579template <typename LHS, typename RHS, typename IDX>
580inline TernaryOpc_match<LHS, RHS, IDX>
581m_InsertSubvector(const LHS &Base, const RHS &Sub, const IDX &Idx) {
582 return TernaryOpc_match<LHS, RHS, IDX>(ISD::INSERT_SUBVECTOR, Base, Sub, Idx);
583}
584
585template <typename T0_P, typename T1_P, typename T2_P>
586inline TernaryOpc_match<T0_P, T1_P, T2_P>
587m_SpliceRight(const T0_P &V1, const T1_P &V2, const T2_P &Offset) {
588 return TernaryOpc_match<T0_P, T1_P, T2_P>(ISD::VECTOR_SPLICE_RIGHT, V1, V2,
589 Offset);
590}
591
592template <typename T0_P, typename T1_P, typename T2_P>
593inline TernaryOpc_match<T0_P, T1_P, T2_P>
594m_TernaryOp(unsigned Opc, const T0_P &Op0, const T1_P &Op1, const T2_P &Op2) {
595 return TernaryOpc_match<T0_P, T1_P, T2_P>(Opc, Op0, Op1, Op2);
596}
597
598template <typename T0_P, typename T1_P, typename T2_P>
599inline TernaryOpc_match<T0_P, T1_P, T2_P, true>
600m_c_TernaryOp(unsigned Opc, const T0_P &Op0, const T1_P &Op1, const T2_P &Op2) {
601 return TernaryOpc_match<T0_P, T1_P, T2_P, true>(Opc, Op0, Op1, Op2);
602}
603
604/// Match a SELECT_CC with any condition code.
605template <typename LTy, typename RTy, typename TTy, typename FTy>
606inline auto m_SelectCC(const LTy &L, const RTy &R, const TTy &T, const FTy &F) {
607 return m_Node(ISD::SELECT_CC, L, R, T, F, m_CondCode());
608}
609
610/// Match a SELECT_CC with any condition code and bind the condition code to
611/// CC.
612template <typename LTy, typename RTy, typename TTy, typename FTy>
613inline auto m_SelectCC(ISD::CondCode &CC, const LTy &L, const RTy &R,
614 const TTy &T, const FTy &F) {
615 return m_Node(ISD::SELECT_CC, L, R, T, F, m_CondCode(CC));
616}
617
618/// Match a SELECT_CC with a specific condition code.
619template <typename LTy, typename RTy, typename TTy, typename FTy>
620inline auto m_SpecificSelectCC(ISD::CondCode CC, const LTy &L, const RTy &R,
621 const TTy &T, const FTy &F) {
622 return m_Node(ISD::SELECT_CC, L, R, T, F, m_SpecificCondCode(CC));
623}
624
625/// Match a SELECT of a SETCC or a SELECT_CC with any condition code.
626template <typename LTy, typename RTy, typename TTy, typename FTy>
627inline auto m_SelectCCLike(const LTy &L, const RTy &R, const TTy &T,
628 const FTy &F) {
629 return m_AnyOf(m_Select(m_SetCC(L, R), T, F), m_SelectCC(L, R, T, F));
630}
631
632/// Match a SELECT of a SETCC or a SELECT_CC with any condition code and bind
633/// the condition code to CC.
634template <typename LTy, typename RTy, typename TTy, typename FTy>
635inline auto m_SelectCCLike(ISD::CondCode &CC, const LTy &L, const RTy &R,
636 const TTy &T, const FTy &F) {
637 return m_AnyOf(m_Select(m_SetCC(CC, L, R), T, F), m_SelectCC(CC, L, R, T, F));
638}
639
640/// Match a SELECT of a SETCC or a SELECT_CC with a specific condition code.
641template <typename LTy, typename RTy, typename TTy, typename FTy>
642inline auto m_SpecificSelectCCLike(ISD::CondCode CC, const LTy &L, const RTy &R,
643 const TTy &T, const FTy &F) {
644 return m_AnyOf(m_Select(m_SpecificSetCC(CC, L, R), T, F),
645 m_SpecificSelectCC(CC, L, R, T, F));
646}
647
648// === Binary operations ===
649template <typename LHS_P, typename RHS_P, bool Commutable = false,
650 bool ExcludeChain = false>
651struct BinaryOpc_match {
652 unsigned Opcode;
653 LHS_P LHS;
654 RHS_P RHS;
655 SDNodeFlags Flags;
656 BinaryOpc_match(unsigned Opc, const LHS_P &L, const RHS_P &R,
657 SDNodeFlags Flgs = SDNodeFlags())
658 : Opcode(Opc), LHS(L), RHS(R), Flags(Flgs) {}
659
660 bool match(SDValue N) {
661 if (sd_match(N, P: m_SpecificOpc(Opcode))) {
662 EffectiveOperands<ExcludeChain> EO(N);
663 assert(EO.Size == 2);
664 if (!((LHS.match(N->getOperand(Num: EO.FirstIndex)) &&
665 RHS.match(N->getOperand(Num: EO.FirstIndex + 1))) ||
666 (Commutable && LHS.match(N->getOperand(Num: EO.FirstIndex + 1)) &&
667 RHS.match(N->getOperand(Num: EO.FirstIndex)))))
668 return false;
669
670 return (Flags & N->getFlags()) == Flags;
671 }
672
673 return false;
674 }
675};
676
677/// Matching while capturing mask
678template <typename T0, typename T1, typename T2> struct SDShuffle_match {
679 T0 Op1;
680 T1 Op2;
681 T2 Mask;
682
683 SDShuffle_match(const T0 &Op1, const T1 &Op2, const T2 &Mask)
684 : Op1(Op1), Op2(Op2), Mask(Mask) {}
685
686 bool match(SDValue N) {
687 if (auto *I = dyn_cast<ShuffleVectorSDNode>(Val&: N)) {
688 return Op1.match(I->getOperand(Num: 0)) && Op2.match(I->getOperand(Num: 1)) &&
689 Mask.match(I->getMask());
690 }
691 return false;
692 }
693};
694struct m_Mask {
695 ArrayRef<int> &MaskRef;
696 m_Mask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
697 bool match(ArrayRef<int> Mask) {
698 MaskRef = Mask;
699 return true;
700 }
701};
702
703struct m_SpecificMask {
704 ArrayRef<int> MaskRef;
705 m_SpecificMask(ArrayRef<int> MaskRef) : MaskRef(MaskRef) {}
706 bool match(ArrayRef<int> Mask) { return MaskRef == Mask; }
707};
708
709template <typename LHS_P, typename RHS_P, typename Pred_t,
710 bool Commutable = false>
711struct MaxMin_match {
712 using PredType = Pred_t;
713 LHS_P LHS;
714 RHS_P RHS;
715
716 MaxMin_match(const LHS_P &L, const RHS_P &R) : LHS(L), RHS(R) {}
717
718 bool match(SDValue N) {
719 auto MatchMinMax = [&](SDValue L, SDValue R, SDValue TrueValue,
720 SDValue FalseValue, ISD::CondCode CC) {
721 if ((TrueValue != L || FalseValue != R) &&
722 (TrueValue != R || FalseValue != L))
723 return false;
724
725 ISD::CondCode Cond =
726 TrueValue == L ? CC : getSetCCInverse(Operation: CC, Type: L.getValueType());
727 if (!Pred_t::match(Cond))
728 return false;
729
730 return (LHS.match(L) && RHS.match(R)) ||
731 (Commutable && LHS.match(R) && RHS.match(L));
732 };
733
734 if (N.getOpcode() == ISD::SELECT || N.getOpcode() == ISD::VSELECT) {
735 assert(N.getNumOperands() == 3);
736 SDValue Cond = N.getOperand(i: 0);
737 SDValue TrueValue = N.getOperand(i: 1);
738 SDValue FalseValue = N.getOperand(i: 2);
739
740 if (Cond.getOpcode() == ISD::SETCC) {
741 assert(Cond.getNumOperands() == 3);
742 SDValue L = Cond.getOperand(i: 0);
743 SDValue R = Cond.getOperand(i: 1);
744 ISD::CondCode CC = Cond.getOperandCondCode(i: 2);
745 return MatchMinMax(L, R, TrueValue, FalseValue, CC);
746 }
747 }
748
749 if (N.getOpcode() == ISD::SELECT_CC) {
750 assert(N.getNumOperands() == 5);
751 SDValue L = N.getOperand(i: 0);
752 SDValue R = N.getOperand(i: 1);
753 SDValue TrueValue = N.getOperand(i: 2);
754 SDValue FalseValue = N.getOperand(i: 3);
755 ISD::CondCode CC = N->getOperandCondCode(Num: 4);
756 return MatchMinMax(L, R, TrueValue, FalseValue, CC);
757 }
758
759 return false;
760 }
761};
762
763// Helper class for identifying signed max predicates.
764struct smax_pred_ty {
765 static bool match(ISD::CondCode Cond) {
766 return Cond == ISD::CondCode::SETGT || Cond == ISD::CondCode::SETGE;
767 }
768};
769
770// Helper class for identifying unsigned max predicates.
771struct umax_pred_ty {
772 static bool match(ISD::CondCode Cond) {
773 return Cond == ISD::CondCode::SETUGT || Cond == ISD::CondCode::SETUGE;
774 }
775};
776
777// Helper class for identifying signed min predicates.
778struct smin_pred_ty {
779 static bool match(ISD::CondCode Cond) {
780 return Cond == ISD::CondCode::SETLT || Cond == ISD::CondCode::SETLE;
781 }
782};
783
784// Helper class for identifying unsigned min predicates.
785struct umin_pred_ty {
786 static bool match(ISD::CondCode Cond) {
787 return Cond == ISD::CondCode::SETULT || Cond == ISD::CondCode::SETULE;
788 }
789};
790
791template <typename LHS, typename RHS>
792inline BinaryOpc_match<LHS, RHS> m_BinOp(unsigned Opc, const LHS &L,
793 const RHS &R,
794 SDNodeFlags Flgs = SDNodeFlags()) {
795 return BinaryOpc_match<LHS, RHS>(Opc, L, R, Flgs);
796}
797template <typename LHS, typename RHS>
798inline BinaryOpc_match<LHS, RHS, true>
799m_c_BinOp(unsigned Opc, const LHS &L, const RHS &R,
800 SDNodeFlags Flgs = SDNodeFlags()) {
801 return BinaryOpc_match<LHS, RHS, true>(Opc, L, R, Flgs);
802}
803
804template <typename LHS, typename RHS>
805inline BinaryOpc_match<LHS, RHS, false, true>
806m_ChainedBinOp(unsigned Opc, const LHS &L, const RHS &R) {
807 return BinaryOpc_match<LHS, RHS, false, true>(Opc, L, R);
808}
809template <typename LHS, typename RHS>
810inline BinaryOpc_match<LHS, RHS, true, true>
811m_c_ChainedBinOp(unsigned Opc, const LHS &L, const RHS &R) {
812 return BinaryOpc_match<LHS, RHS, true, true>(Opc, L, R);
813}
814
815// Common binary operations
816template <typename LHS, typename RHS>
817inline BinaryOpc_match<LHS, RHS, true> m_Add(const LHS &L, const RHS &R) {
818 return BinaryOpc_match<LHS, RHS, true>(ISD::ADD, L, R);
819}
820
821template <typename LHS, typename RHS>
822inline auto m_NUWAdd(const LHS &L, const RHS &R) {
823 return BinaryOpc_match<LHS, RHS, true>(ISD::ADD, L, R,
824 SDNodeFlags::NoUnsignedWrap);
825}
826
827template <typename LHS, typename RHS>
828inline auto m_NSWAdd(const LHS &L, const RHS &R) {
829 return BinaryOpc_match<LHS, RHS, true>(ISD::ADD, L, R,
830 SDNodeFlags::NoSignedWrap);
831}
832
833template <typename LHS, typename RHS>
834inline BinaryOpc_match<LHS, RHS> m_Sub(const LHS &L, const RHS &R) {
835 return BinaryOpc_match<LHS, RHS>(ISD::SUB, L, R);
836}
837
838template <typename LHS, typename RHS>
839inline BinaryOpc_match<LHS, RHS, true> m_Mul(const LHS &L, const RHS &R) {
840 return BinaryOpc_match<LHS, RHS, true>(ISD::MUL, L, R);
841}
842
843template <typename LHS, typename RHS>
844inline BinaryOpc_match<LHS, RHS, true> m_And(const LHS &L, const RHS &R) {
845 return BinaryOpc_match<LHS, RHS, true>(ISD::AND, L, R);
846}
847
848template <typename LHS, typename RHS>
849inline BinaryOpc_match<LHS, RHS, true> m_Or(const LHS &L, const RHS &R) {
850 return BinaryOpc_match<LHS, RHS, true>(ISD::OR, L, R);
851}
852
853template <typename LHS, typename RHS>
854inline BinaryOpc_match<LHS, RHS, true> m_DisjointOr(const LHS &L,
855 const RHS &R) {
856 return BinaryOpc_match<LHS, RHS, true>(ISD::OR, L, R, SDNodeFlags::Disjoint);
857}
858
859template <typename LHS, typename RHS>
860inline auto m_AddLike(const LHS &L, const RHS &R) {
861 return m_AnyOf(m_Add(L, R), m_DisjointOr(L, R));
862}
863
864template <typename LHS, typename RHS>
865inline auto m_NSWAddLike(const LHS &L, const RHS &R) {
866 return m_AnyOf(m_NSWAdd(L, R), m_DisjointOr(L, R));
867}
868
869template <typename LHS, typename RHS>
870inline auto m_NUWAddLike(const LHS &L, const RHS &R) {
871 return m_AnyOf(m_NUWAdd(L, R), m_DisjointOr(L, R));
872}
873
874template <typename LHS, typename RHS>
875inline BinaryOpc_match<LHS, RHS, true> m_Xor(const LHS &L, const RHS &R) {
876 return BinaryOpc_match<LHS, RHS, true>(ISD::XOR, L, R);
877}
878
879template <typename LHS, typename RHS>
880inline auto m_BitwiseLogic(const LHS &L, const RHS &R) {
881 return m_AnyOf(m_And(L, R), m_Or(L, R), m_Xor(L, R));
882}
883
884template <unsigned Opc, typename Pred, typename LHS, typename RHS>
885inline auto m_MaxMinLike(const LHS &L, const RHS &R) {
886 return m_AnyOf(BinaryOpc_match<LHS, RHS, true>(Opc, L, R),
887 MaxMin_match<LHS, RHS, Pred, true>(L, R));
888}
889
890template <typename LHS, typename RHS>
891inline BinaryOpc_match<LHS, RHS, true> m_SMin(const LHS &L, const RHS &R) {
892 return BinaryOpc_match<LHS, RHS, true>(ISD::SMIN, L, R);
893}
894
895template <typename LHS, typename RHS>
896inline auto m_SMinLike(const LHS &L, const RHS &R) {
897 return m_MaxMinLike<ISD::SMIN, smin_pred_ty>(L, R);
898}
899
900template <typename LHS, typename RHS>
901inline BinaryOpc_match<LHS, RHS, true> m_SMax(const LHS &L, const RHS &R) {
902 return BinaryOpc_match<LHS, RHS, true>(ISD::SMAX, L, R);
903}
904
905template <typename LHS, typename RHS>
906inline auto m_SMaxLike(const LHS &L, const RHS &R) {
907 return m_MaxMinLike<ISD::SMAX, smax_pred_ty>(L, R);
908}
909
910template <typename LHS, typename RHS>
911inline BinaryOpc_match<LHS, RHS, true> m_UMin(const LHS &L, const RHS &R) {
912 return BinaryOpc_match<LHS, RHS, true>(ISD::UMIN, L, R);
913}
914
915template <typename LHS, typename RHS>
916inline auto m_UMinLike(const LHS &L, const RHS &R) {
917 return m_MaxMinLike<ISD::UMIN, umin_pred_ty>(L, R);
918}
919
920template <typename LHS, typename RHS>
921inline BinaryOpc_match<LHS, RHS, true> m_UMax(const LHS &L, const RHS &R) {
922 return BinaryOpc_match<LHS, RHS, true>(ISD::UMAX, L, R);
923}
924
925template <typename LHS, typename RHS>
926inline auto m_UMaxLike(const LHS &L, const RHS &R) {
927 return m_MaxMinLike<ISD::UMAX, umax_pred_ty>(L, R);
928}
929
930template <typename LHS, typename RHS>
931inline BinaryOpc_match<LHS, RHS> m_UDiv(const LHS &L, const RHS &R) {
932 return BinaryOpc_match<LHS, RHS>(ISD::UDIV, L, R);
933}
934template <typename LHS, typename RHS>
935inline BinaryOpc_match<LHS, RHS> m_SDiv(const LHS &L, const RHS &R) {
936 return BinaryOpc_match<LHS, RHS>(ISD::SDIV, L, R);
937}
938
939template <typename LHS, typename RHS>
940inline BinaryOpc_match<LHS, RHS> m_URem(const LHS &L, const RHS &R) {
941 return BinaryOpc_match<LHS, RHS>(ISD::UREM, L, R);
942}
943template <typename LHS, typename RHS>
944inline BinaryOpc_match<LHS, RHS> m_SRem(const LHS &L, const RHS &R) {
945 return BinaryOpc_match<LHS, RHS>(ISD::SREM, L, R);
946}
947
948template <typename LHS, typename RHS>
949inline BinaryOpc_match<LHS, RHS> m_Shl(const LHS &L, const RHS &R) {
950 return BinaryOpc_match<LHS, RHS>(ISD::SHL, L, R);
951}
952
953template <typename LHS, typename RHS>
954inline BinaryOpc_match<LHS, RHS> m_Sra(const LHS &L, const RHS &R) {
955 return BinaryOpc_match<LHS, RHS>(ISD::SRA, L, R);
956}
957template <typename LHS, typename RHS>
958inline BinaryOpc_match<LHS, RHS> m_Srl(const LHS &L, const RHS &R) {
959 return BinaryOpc_match<LHS, RHS>(ISD::SRL, L, R);
960}
961template <typename LHS, typename RHS>
962inline auto m_ExactSr(const LHS &L, const RHS &R) {
963 return m_AnyOf(BinaryOpc_match<LHS, RHS>(ISD::SRA, L, R, SDNodeFlags::Exact),
964 BinaryOpc_match<LHS, RHS>(ISD::SRL, L, R, SDNodeFlags::Exact));
965}
966
967template <typename LHS, typename RHS>
968inline BinaryOpc_match<LHS, RHS> m_Rotl(const LHS &L, const RHS &R) {
969 return BinaryOpc_match<LHS, RHS>(ISD::ROTL, L, R);
970}
971
972template <typename LHS, typename RHS>
973inline BinaryOpc_match<LHS, RHS> m_Rotr(const LHS &L, const RHS &R) {
974 return BinaryOpc_match<LHS, RHS>(ISD::ROTR, L, R);
975}
976
977template <typename T0_P, typename T1_P, typename T2_P>
978inline TernaryOpc_match<T0_P, T1_P, T2_P>
979m_FShL(const T0_P &Op0, const T1_P &Op1, const T2_P &Op2) {
980 return m_TernaryOp(ISD::FSHL, Op0, Op1, Op2);
981}
982
983template <typename T0_P, typename T1_P, typename T2_P>
984inline TernaryOpc_match<T0_P, T1_P, T2_P>
985m_FShR(const T0_P &Op0, const T1_P &Op1, const T2_P &Op2) {
986 return m_TernaryOp(ISD::FSHR, Op0, Op1, Op2);
987}
988
989template <typename T0_P, typename T1_P, typename T2_P, bool Left>
990struct FunnelShiftLike_match {
991 T0_P Op0;
992 T1_P Op1;
993 T2_P Op2;
994
995 FunnelShiftLike_match(const T0_P &Op0, const T1_P &Op1, const T2_P &Op2)
996 : Op0(Op0), Op1(Op1), Op2(Op2) {}
997
998 static bool hasComplementaryConstantShifts(const APInt &ShlV,
999 const APInt &SrlV,
1000 unsigned BitWidth) {
1001 unsigned SumWidth = std::max(a: ShlV.getBitWidth(), b: SrlV.getBitWidth()) + 1;
1002 unsigned BitWidthBits = llvm::bit_width(Value: BitWidth);
1003 if (BitWidthBits > SumWidth)
1004 return false;
1005
1006 return ShlV.zext(width: SumWidth) + SrlV.zext(width: SumWidth) ==
1007 APInt(SumWidth, BitWidth);
1008 }
1009
1010 bool matchOperands(SDValue X, SDValue Y, SDValue Z) {
1011 return Op0.match(X) && Op1.match(Y) && Op2.match(Z);
1012 }
1013
1014 bool matchShiftOr(SDValue N, unsigned BitWidth);
1015
1016 bool match(SDValue N) {
1017 if (sd_match(N, Left ? m_FShL(Op0, Op1, Op2) : m_FShR(Op0, Op1, Op2)))
1018 return true;
1019
1020 SDValue X, Z;
1021 if (sd_match(N, P: Left ? m_Rotl(L: m_Value(N&: X), R: m_Value(N&: Z))
1022 : m_Rotr(L: m_Value(N&: X), R: m_Value(N&: Z))))
1023 return matchOperands(X, Y: X, Z);
1024
1025 return matchShiftOr(N, BitWidth: N.getValueType().getScalarSizeInBits());
1026 }
1027};
1028
1029template <typename T0_P, typename T1_P, typename T2_P>
1030inline FunnelShiftLike_match<T0_P, T1_P, T2_P, true>
1031m_FShLLike(const T0_P &Op0, const T1_P &Op1, const T2_P &Op2) {
1032 return FunnelShiftLike_match<T0_P, T1_P, T2_P, true>(Op0, Op1, Op2);
1033}
1034
1035template <typename T0_P, typename T1_P, typename T2_P>
1036inline FunnelShiftLike_match<T0_P, T1_P, T2_P, false>
1037m_FShRLike(const T0_P &Op0, const T1_P &Op1, const T2_P &Op2) {
1038 return FunnelShiftLike_match<T0_P, T1_P, T2_P, false>(Op0, Op1, Op2);
1039}
1040
1041template <typename LHS, typename RHS>
1042inline BinaryOpc_match<LHS, RHS, true> m_Clmul(const LHS &L, const RHS &R) {
1043 return BinaryOpc_match<LHS, RHS, true>(ISD::CLMUL, L, R);
1044}
1045
1046template <typename LHS, typename RHS>
1047inline BinaryOpc_match<LHS, RHS, true> m_FAdd(const LHS &L, const RHS &R) {
1048 return BinaryOpc_match<LHS, RHS, true>(ISD::FADD, L, R);
1049}
1050
1051template <typename LHS, typename RHS>
1052inline BinaryOpc_match<LHS, RHS> m_FSub(const LHS &L, const RHS &R) {
1053 return BinaryOpc_match<LHS, RHS>(ISD::FSUB, L, R);
1054}
1055
1056template <typename LHS, typename RHS>
1057inline BinaryOpc_match<LHS, RHS, true> m_FMul(const LHS &L, const RHS &R) {
1058 return BinaryOpc_match<LHS, RHS, true>(ISD::FMUL, L, R);
1059}
1060
1061template <typename LHS, typename RHS>
1062inline BinaryOpc_match<LHS, RHS> m_FDiv(const LHS &L, const RHS &R) {
1063 return BinaryOpc_match<LHS, RHS>(ISD::FDIV, L, R);
1064}
1065
1066template <typename LHS, typename RHS>
1067inline BinaryOpc_match<LHS, RHS> m_FRem(const LHS &L, const RHS &R) {
1068 return BinaryOpc_match<LHS, RHS>(ISD::FREM, L, R);
1069}
1070
1071template <typename V1_t, typename V2_t>
1072inline BinaryOpc_match<V1_t, V2_t> m_Shuffle(const V1_t &v1, const V2_t &v2) {
1073 return BinaryOpc_match<V1_t, V2_t>(ISD::VECTOR_SHUFFLE, v1, v2);
1074}
1075
1076template <typename V1_t, typename V2_t, typename Mask_t>
1077inline SDShuffle_match<V1_t, V2_t, Mask_t>
1078m_Shuffle(const V1_t &v1, const V2_t &v2, const Mask_t &mask) {
1079 return SDShuffle_match<V1_t, V2_t, Mask_t>(v1, v2, mask);
1080}
1081
1082template <typename LHS, typename RHS>
1083inline BinaryOpc_match<LHS, RHS> m_ExtractElt(const LHS &Vec, const RHS &Idx) {
1084 return BinaryOpc_match<LHS, RHS>(ISD::EXTRACT_VECTOR_ELT, Vec, Idx);
1085}
1086
1087template <typename LHS, typename RHS>
1088inline BinaryOpc_match<LHS, RHS> m_ExtractSubvector(const LHS &Vec,
1089 const RHS &Idx) {
1090 return BinaryOpc_match<LHS, RHS>(ISD::EXTRACT_SUBVECTOR, Vec, Idx);
1091}
1092
1093// === Unary operations ===
1094template <typename Opnd_P, bool ExcludeChain = false> struct UnaryOpc_match {
1095 unsigned Opcode;
1096 Opnd_P Opnd;
1097 SDNodeFlags Flags;
1098 UnaryOpc_match(unsigned Opc, const Opnd_P &Op,
1099 SDNodeFlags Flgs = SDNodeFlags())
1100 : Opcode(Opc), Opnd(Op), Flags(Flgs) {}
1101
1102 bool match(SDValue N) {
1103 if (sd_match(N, P: m_SpecificOpc(Opcode))) {
1104 EffectiveOperands<ExcludeChain> EO(N);
1105 assert(EO.Size == 1);
1106 if (!Opnd.match(N->getOperand(Num: EO.FirstIndex)))
1107 return false;
1108
1109 return (Flags & N->getFlags()) == Flags;
1110 }
1111
1112 return false;
1113 }
1114};
1115
1116template <typename Opnd>
1117inline UnaryOpc_match<Opnd> m_UnaryOp(unsigned Opc, const Opnd &Op) {
1118 return UnaryOpc_match<Opnd>(Opc, Op);
1119}
1120template <typename Opnd>
1121inline UnaryOpc_match<Opnd, true> m_ChainedUnaryOp(unsigned Opc,
1122 const Opnd &Op) {
1123 return UnaryOpc_match<Opnd, true>(Opc, Op);
1124}
1125
1126template <typename Opnd> inline UnaryOpc_match<Opnd> m_BitCast(const Opnd &Op) {
1127 return UnaryOpc_match<Opnd>(ISD::BITCAST, Op);
1128}
1129
1130template <typename Opnd>
1131inline UnaryOpc_match<Opnd> m_BSwap(const Opnd &Op) {
1132 return UnaryOpc_match<Opnd>(ISD::BSWAP, Op);
1133}
1134
1135template <typename Opnd>
1136inline UnaryOpc_match<Opnd> m_BitReverse(const Opnd &Op) {
1137 return UnaryOpc_match<Opnd>(ISD::BITREVERSE, Op);
1138}
1139
1140template <typename Opnd> inline UnaryOpc_match<Opnd> m_ZExt(const Opnd &Op) {
1141 return UnaryOpc_match<Opnd>(ISD::ZERO_EXTEND, Op);
1142}
1143
1144template <typename Opnd>
1145inline UnaryOpc_match<Opnd> m_NNegZExt(const Opnd &Op) {
1146 return UnaryOpc_match<Opnd>(ISD::ZERO_EXTEND, Op, SDNodeFlags::NonNeg);
1147}
1148
1149template <typename Opnd> inline auto m_SExt(const Opnd &Op) {
1150 return UnaryOpc_match<Opnd>(ISD::SIGN_EXTEND, Op);
1151}
1152
1153template <typename Opnd> inline UnaryOpc_match<Opnd> m_AnyExt(const Opnd &Op) {
1154 return UnaryOpc_match<Opnd>(ISD::ANY_EXTEND, Op);
1155}
1156
1157template <typename Opnd> inline UnaryOpc_match<Opnd> m_Trunc(const Opnd &Op) {
1158 return UnaryOpc_match<Opnd>(ISD::TRUNCATE, Op);
1159}
1160
1161template <typename Opnd> inline auto m_Abs(const Opnd &Op) {
1162 return m_AnyOf(UnaryOpc_match<Opnd>(ISD::ABS, Op),
1163 UnaryOpc_match<Opnd>(ISD::ABS_MIN_POISON, Op));
1164}
1165
1166template <typename Opnd> inline UnaryOpc_match<Opnd> m_FAbs(const Opnd &Op) {
1167 return UnaryOpc_match<Opnd>(ISD::FABS, Op);
1168}
1169
1170/// Match a zext or identity
1171/// Allows to peek through optional extensions
1172template <typename Opnd> inline auto m_ZExtOrSelf(const Opnd &Op) {
1173 return m_AnyOf(m_ZExt(Op), Op);
1174}
1175
1176/// Match a sext or identity
1177/// Allows to peek through optional extensions
1178template <typename Opnd> inline auto m_SExtOrSelf(const Opnd &Op) {
1179 return m_AnyOf(m_SExt(Op), Op);
1180}
1181
1182template <typename Opnd> inline auto m_SExtLike(const Opnd &Op) {
1183 return m_AnyOf(m_SExt(Op), m_NNegZExt(Op));
1184}
1185
1186/// Match a zext or sext
1187template <typename Opnd> inline auto m_ZExtOrSExt(const Opnd &Op) {
1188 return m_AnyOf(m_ZExt(Op), m_SExt(Op));
1189}
1190
1191/// Match a aext or identity
1192/// Allows to peek through optional extensions
1193template <typename Opnd>
1194inline Or<UnaryOpc_match<Opnd>, Opnd> m_AExtOrSelf(const Opnd &Op) {
1195 return Or<UnaryOpc_match<Opnd>, Opnd>(m_AnyExt(Op), Op);
1196}
1197
1198/// Match a trunc or identity
1199/// Allows to peek through optional truncations
1200template <typename Opnd>
1201inline Or<UnaryOpc_match<Opnd>, Opnd> m_TruncOrSelf(const Opnd &Op) {
1202 return Or<UnaryOpc_match<Opnd>, Opnd>(m_Trunc(Op), Op);
1203}
1204
1205template <typename Opnd> inline UnaryOpc_match<Opnd> m_VScale(const Opnd &Op) {
1206 return UnaryOpc_match<Opnd>(ISD::VSCALE, Op);
1207}
1208
1209template <typename Opnd> inline UnaryOpc_match<Opnd> m_FPToUI(const Opnd &Op) {
1210 return UnaryOpc_match<Opnd>(ISD::FP_TO_UINT, Op);
1211}
1212
1213template <typename Opnd> inline UnaryOpc_match<Opnd> m_FPToSI(const Opnd &Op) {
1214 return UnaryOpc_match<Opnd>(ISD::FP_TO_SINT, Op);
1215}
1216
1217template <typename Opnd> inline UnaryOpc_match<Opnd> m_Ctpop(const Opnd &Op) {
1218 return UnaryOpc_match<Opnd>(ISD::CTPOP, Op);
1219}
1220
1221template <typename Opnd> inline UnaryOpc_match<Opnd> m_Ctlz(const Opnd &Op) {
1222 return UnaryOpc_match<Opnd>(ISD::CTLZ, Op);
1223}
1224
1225template <typename Opnd> inline UnaryOpc_match<Opnd> m_Cttz(const Opnd &Op) {
1226 return UnaryOpc_match<Opnd>(ISD::CTTZ, Op);
1227}
1228
1229template <typename Opnd> inline UnaryOpc_match<Opnd> m_FNeg(const Opnd &Op) {
1230 return UnaryOpc_match<Opnd>(ISD::FNEG, Op);
1231}
1232
1233template <typename Opnd>
1234inline UnaryOpc_match<Opnd> m_VectorReverse(const Opnd &Op) {
1235 return UnaryOpc_match<Opnd>(ISD::VECTOR_REVERSE, Op);
1236}
1237
1238// === Constants ===
1239struct ConstantInt_match {
1240 APInt *BindVal;
1241
1242 explicit ConstantInt_match(APInt *V) : BindVal(V) {}
1243
1244 bool match(SDValue N) {
1245 // The logics here are similar to that in
1246 // SelectionDAG::isConstantIntBuildVectorOrConstantInt, but the latter also
1247 // treats GlobalAddressSDNode as a constant, which is difficult to turn into
1248 // APInt.
1249 if (auto *C = dyn_cast_or_null<ConstantSDNode>(Val: N.getNode())) {
1250 if (BindVal)
1251 *BindVal = C->getAPIntValue();
1252 return true;
1253 }
1254
1255 APInt Discard;
1256 return ISD::isConstantSplatVector(V: N, SplatValue&: BindVal ? *BindVal : Discard);
1257 }
1258};
1259
1260template <typename T> struct Constant64_match {
1261 static_assert(sizeof(T) == 8, "T must be 64 bits wide");
1262
1263 T &BindVal;
1264
1265 explicit Constant64_match(T &V) : BindVal(V) {}
1266
1267 bool match(SDValue N) {
1268 APInt V;
1269 if (!ConstantInt_match(&V).match(N))
1270 return false;
1271
1272 if constexpr (std::is_signed_v<T>) {
1273 if (std::optional<int64_t> TrySExt = V.trySExtValue()) {
1274 BindVal = *TrySExt;
1275 return true;
1276 }
1277 }
1278
1279 if constexpr (std::is_unsigned_v<T>) {
1280 if (std::optional<uint64_t> TryZExt = V.tryZExtValue()) {
1281 BindVal = *TryZExt;
1282 return true;
1283 }
1284 }
1285
1286 return false;
1287 }
1288};
1289
1290/// Match any integer constants or splat of an integer constant.
1291inline ConstantInt_match m_ConstInt() { return ConstantInt_match(nullptr); }
1292/// Match any integer constants or splat of an integer constant; return the
1293/// specific constant or constant splat value.
1294inline ConstantInt_match m_ConstInt(APInt &V) { return ConstantInt_match(&V); }
1295/// Match any integer constants or splat of an integer constant that can fit in
1296/// 64 bits; return the specific constant or constant splat value, zero-extended
1297/// to 64 bits.
1298inline Constant64_match<uint64_t> m_ConstInt(uint64_t &V) {
1299 return Constant64_match<uint64_t>(V);
1300}
1301/// Match any integer constants or splat of an integer constant that can fit in
1302/// 64 bits; return the specific constant or constant splat value, sign-extended
1303/// to 64 bits.
1304inline Constant64_match<int64_t> m_ConstInt(int64_t &V) {
1305 return Constant64_match<int64_t>(V);
1306}
1307
1308template <typename T0_P, typename T1_P, typename T2_P, bool Left>
1309bool FunnelShiftLike_match<T0_P, T1_P, T2_P, Left>::matchShiftOr(
1310 SDValue N, unsigned BitWidth) {
1311 SDValue X, Y, ShlAmt, SrlAmt;
1312 APInt ShlConst, SrlConst;
1313 if (!sd_match(
1314 N, P: m_Or(L: m_Shl(L: m_Value(N&: X), R: m_Value(N&: ShlAmt, P: m_ConstInt(V&: ShlConst))),
1315 R: m_Srl(L: m_Value(N&: Y), R: m_Value(N&: SrlAmt, P: m_ConstInt(V&: SrlConst))))) ||
1316 !hasComplementaryConstantShifts(ShlV: ShlConst, SrlV: SrlConst, BitWidth))
1317 return false;
1318
1319 return matchOperands(X, Y, Z: Left ? ShlAmt : SrlAmt);
1320}
1321
1322struct SpecificInt_match {
1323 APInt IntVal;
1324
1325 explicit SpecificInt_match(APInt APV) : IntVal(std::move(APV)) {}
1326
1327 bool match(SDValue N) {
1328 APInt ConstInt;
1329 if (sd_match(N, P: m_ConstInt(V&: ConstInt)))
1330 return APInt::isSameValue(I1: IntVal, I2: ConstInt);
1331 return false;
1332 }
1333};
1334
1335/// Match a specific integer constant or constant splat value.
1336inline SpecificInt_match m_SpecificInt(APInt V) {
1337 return SpecificInt_match(std::move(V));
1338}
1339inline SpecificInt_match m_SpecificInt(uint64_t V) {
1340 return SpecificInt_match(APInt(64, V));
1341}
1342
1343struct SpecificFP_match {
1344 APFloat Val;
1345
1346 explicit SpecificFP_match(APFloat V) : Val(V) {}
1347
1348 bool match(SDValue V) {
1349 if (const auto *CFP = dyn_cast<ConstantFPSDNode>(Val: V.getNode()))
1350 return CFP->isExactlyValue(V: Val);
1351 if (ConstantFPSDNode *C = isConstOrConstSplatFP(N: V, /*AllowUndefs=*/AllowUndefs: true))
1352 return C->getValueAPF().compare(RHS: Val) == APFloat::cmpEqual;
1353 return false;
1354 }
1355};
1356
1357/// Match a specific float constant.
1358inline SpecificFP_match m_SpecificFP(APFloat V) { return SpecificFP_match(V); }
1359
1360inline SpecificFP_match m_SpecificFP(double V) {
1361 return SpecificFP_match(APFloat(V));
1362}
1363
1364struct AnyZeroFP_match {
1365 bool match(SDValue N) {
1366 if (ConstantFPSDNode *C = isConstOrConstSplatFP(N))
1367 return C->isZero();
1368 return false;
1369 }
1370};
1371
1372/// Match a floating-point +0.0 or -0.0 constant or splat.
1373inline AnyZeroFP_match m_AnyZeroFP() { return AnyZeroFP_match(); }
1374
1375struct Zero_match {
1376 bool AllowUndefs;
1377
1378 explicit Zero_match(bool AllowUndefs) : AllowUndefs(AllowUndefs) {}
1379
1380 bool match(SDValue N) const { return isZeroOrZeroSplat(N, AllowUndefs); }
1381};
1382
1383struct One_match {
1384 bool AllowUndefs;
1385
1386 One_match(bool AllowUndefs) : AllowUndefs(AllowUndefs) {}
1387
1388 bool match(SDValue N) { return isOneOrOneSplat(V: N, AllowUndefs); }
1389};
1390
1391struct AllOnes_match {
1392 bool AllowUndefs;
1393
1394 AllOnes_match(bool AllowUndefs) : AllowUndefs(AllowUndefs) {}
1395
1396 bool match(SDValue N) { return isAllOnesOrAllOnesSplat(V: N, AllowUndefs); }
1397};
1398
1399inline One_match m_One(bool AllowUndefs = false) {
1400 return One_match(AllowUndefs);
1401}
1402inline Zero_match m_Zero(bool AllowUndefs = false) {
1403 return Zero_match(AllowUndefs);
1404}
1405inline AllOnes_match m_AllOnes(bool AllowUndefs = false) {
1406 return AllOnes_match(AllowUndefs);
1407}
1408
1409template <bool Expected> struct Bool_match {
1410 const SelectionDAG &DAG;
1411
1412 Bool_match(const SelectionDAG &DAG) : DAG(DAG) {}
1413
1414 bool match(SDValue N) {
1415 auto Res = DAG.isBoolConstant(N);
1416 return Res && *Res == Expected;
1417 }
1418};
1419
1420/// Match true boolean value based on the information provided by
1421/// TargetLowering.
1422inline auto m_True(const SelectionDAG &DAG) { return Bool_match<true>(DAG); }
1423
1424/// Match false boolean value based on the information provided by
1425/// TargetLowering.
1426inline auto m_False(const SelectionDAG &DAG) { return Bool_match<false>(DAG); }
1427
1428/// Match a negate as a sub(0, v)
1429template <typename ValTy>
1430inline BinaryOpc_match<Zero_match, ValTy, false> m_Neg(const ValTy &V) {
1431 return m_Sub(m_Zero(), V);
1432}
1433
1434/// Match a Not as a xor(v, -1) or xor(-1, v)
1435template <typename ValTy>
1436inline BinaryOpc_match<ValTy, AllOnes_match, true> m_Not(const ValTy &V) {
1437 return m_Xor(V, m_AllOnes());
1438}
1439
1440template <typename TS> struct TypeSize_match {
1441 TS &BindVal;
1442
1443 explicit TypeSize_match(TS &V) : BindVal(V) {}
1444
1445 bool match(SDValue N) {
1446 bool Scalable;
1447 APInt KnownMin;
1448
1449 if (sd_match(N, P: m_VScale(Op: m_ConstInt(V&: KnownMin))))
1450 Scalable = true;
1451 else if (sd_match(N, P: m_ConstInt(V&: KnownMin)))
1452 Scalable = false;
1453 else
1454 return false;
1455
1456 if (KnownMin.isNegative() ||
1457 !KnownMin.isIntN(N: std::numeric_limits<typename TS::ScalarTy>::digits))
1458 return false;
1459
1460 BindVal = TS::get(KnownMin.getZExtValue(), Scalable);
1461 return true;
1462 }
1463};
1464
1465/// Match any integer constant or constant multiple of VSCALE that can be
1466/// represented using ElementCount.
1467inline TypeSize_match<ElementCount> m_ElementCount(ElementCount &V) {
1468 return TypeSize_match<ElementCount>(V);
1469}
1470
1471template <unsigned IntrinsicId, typename... OpndPreds>
1472inline auto m_IntrinsicWOChain(const OpndPreds &...Opnds) {
1473 return m_Node(ISD::INTRINSIC_WO_CHAIN, m_SpecificInt(V: IntrinsicId), Opnds...);
1474}
1475
1476struct SpecificNeg_match {
1477 SDValue V;
1478
1479 explicit SpecificNeg_match(SDValue V) : V(V) {}
1480
1481 bool match(SDValue N) {
1482 if (sd_match(N, P: m_Neg(V: m_Specific(N: V))))
1483 return true;
1484
1485 return ISD::matchBinaryPredicate(
1486 LHS: V, RHS: N, Match: [](ConstantSDNode *LHS, ConstantSDNode *RHS) {
1487 return LHS->getAPIntValue() == -RHS->getAPIntValue();
1488 });
1489 }
1490};
1491
1492/// Match a negation of a specific value V, either as sub(0, V) or as
1493/// constant(s) that are the negation of V's constant(s).
1494inline SpecificNeg_match m_SpecificNeg(SDValue V) {
1495 return SpecificNeg_match(V);
1496}
1497
1498template <typename... PatternTs> struct ReassociatableOpc_match {
1499 unsigned Opcode;
1500 std::tuple<PatternTs...> Patterns;
1501 constexpr static size_t NumPatterns =
1502 std::tuple_size_v<std::tuple<PatternTs...>>;
1503
1504 SDNodeFlags Flags;
1505
1506 ReassociatableOpc_match(unsigned Opcode, const PatternTs &...Patterns)
1507 : Opcode(Opcode), Patterns(Patterns...) {}
1508
1509 ReassociatableOpc_match(unsigned Opcode, SDNodeFlags Flags,
1510 const PatternTs &...Patterns)
1511 : Opcode(Opcode), Patterns(Patterns...), Flags(Flags) {}
1512
1513 bool match(SDValue N) {
1514 std::array<SDValue, NumPatterns> Leaves;
1515 size_t LeavesIdx = 0;
1516 if (!(collectLeaves(V: N, Leaves, LeafIdx&: LeavesIdx) && (LeavesIdx == NumPatterns)))
1517 return false;
1518
1519 Bitset<NumPatterns> Used;
1520 return std::apply(
1521 [&](auto &...P) -> bool {
1522 return reassociatableMatchHelper(Leaves, Used, P...);
1523 },
1524 Patterns);
1525 }
1526
1527 bool collectLeaves(SDValue V, std::array<SDValue, NumPatterns> &Leaves,
1528 std::size_t &LeafIdx) {
1529 if (V->getOpcode() == Opcode && (Flags & V->getFlags()) == Flags) {
1530 for (size_t I = 0, N = V->getNumOperands(); I < N; I++)
1531 if ((LeafIdx == NumPatterns) ||
1532 !collectLeaves(V: V->getOperand(Num: I), Leaves, LeafIdx))
1533 return false;
1534 } else {
1535 Leaves[LeafIdx] = V;
1536 LeafIdx++;
1537 }
1538 return true;
1539 }
1540
1541 // Searchs for a matching leaf for every sub-pattern.
1542 template <typename PatternHd, typename... PatternTl>
1543 [[nodiscard]] inline bool
1544 reassociatableMatchHelper(ArrayRef<SDValue> Leaves, Bitset<NumPatterns> &Used,
1545 PatternHd &HeadPattern,
1546 PatternTl &...TailPatterns) {
1547 for (size_t Match = 0, N = Used.size(); Match < N; Match++) {
1548 if (Used[Match] || !(sd_match(Leaves[Match], HeadPattern)))
1549 continue;
1550 Used.set(Match);
1551 if (reassociatableMatchHelper(Leaves, Used, TailPatterns...))
1552 return true;
1553 Used.reset(Match);
1554 }
1555 return false;
1556 }
1557
1558 [[nodiscard]] inline bool
1559 reassociatableMatchHelper(ArrayRef<SDValue> Leaves,
1560 Bitset<NumPatterns> &Used) {
1561 return true;
1562 }
1563};
1564
1565template <typename... PatternTs>
1566inline ReassociatableOpc_match<PatternTs...>
1567m_ReassociatableAdd(const PatternTs &...Patterns) {
1568 return ReassociatableOpc_match<PatternTs...>(ISD::ADD, Patterns...);
1569}
1570
1571template <typename... PatternTs>
1572inline ReassociatableOpc_match<PatternTs...>
1573m_ReassociatableOr(const PatternTs &...Patterns) {
1574 return ReassociatableOpc_match<PatternTs...>(ISD::OR, Patterns...);
1575}
1576
1577template <typename... PatternTs>
1578inline ReassociatableOpc_match<PatternTs...>
1579m_ReassociatableAnd(const PatternTs &...Patterns) {
1580 return ReassociatableOpc_match<PatternTs...>(ISD::AND, Patterns...);
1581}
1582
1583template <typename... PatternTs>
1584inline ReassociatableOpc_match<PatternTs...>
1585m_ReassociatableMul(const PatternTs &...Patterns) {
1586 return ReassociatableOpc_match<PatternTs...>(ISD::MUL, Patterns...);
1587}
1588
1589template <typename... PatternTs>
1590inline ReassociatableOpc_match<PatternTs...>
1591m_ReassociatableNSWAdd(const PatternTs &...Patterns) {
1592 return ReassociatableOpc_match<PatternTs...>(
1593 ISD::ADD, SDNodeFlags::NoSignedWrap, Patterns...);
1594}
1595
1596template <typename... PatternTs>
1597inline ReassociatableOpc_match<PatternTs...>
1598m_ReassociatableNUWAdd(const PatternTs &...Patterns) {
1599 return ReassociatableOpc_match<PatternTs...>(
1600 ISD::ADD, SDNodeFlags::NoUnsignedWrap, Patterns...);
1601}
1602
1603} // namespace SDPatternMatch
1604} // namespace llvm
1605#endif
1606