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/STLExtras.h"
18 #include "llvm/CodeGen/SelectionDAG.h"
19 #include "llvm/CodeGen/SelectionDAGNodes.h"
20 #include "llvm/CodeGen/TargetLowering.h"
21
22 namespace llvm {
23 namespace SDPatternMatch {
24
25 /// MatchContext can repurpose existing patterns to behave differently under
26 /// a certain context. For instance, `m_Opc(ISD::ADD)` matches plain ADD nodes
27 /// in normal circumstances, but matches VP_ADD nodes under a custom
28 /// VPMatchContext. This design is meant to facilitate code / pattern reusing.
29 class BasicMatchContext {
30 const SelectionDAG *DAG;
31 const TargetLowering *TLI;
32
33 public:
BasicMatchContext(const SelectionDAG * DAG)34 explicit BasicMatchContext(const SelectionDAG *DAG)
35 : DAG(DAG), TLI(DAG ? &DAG->getTargetLoweringInfo() : nullptr) {}
36
BasicMatchContext(const TargetLowering * TLI)37 explicit BasicMatchContext(const TargetLowering *TLI)
38 : DAG(nullptr), TLI(TLI) {}
39
40 // A valid MatchContext has to implement the following functions.
41
getDAG()42 const SelectionDAG *getDAG() const { return DAG; }
43
getTLI()44 const TargetLowering *getTLI() const { return TLI; }
45
46 /// Return true if N effectively has opcode Opcode.
match(SDValue N,unsigned Opcode)47 bool match(SDValue N, unsigned Opcode) const {
48 return N->getOpcode() == Opcode;
49 }
50 };
51
52 template <typename Pattern, typename MatchContext>
sd_context_match(SDValue N,const MatchContext & Ctx,Pattern && P)53 [[nodiscard]] bool sd_context_match(SDValue N, const MatchContext &Ctx,
54 Pattern &&P) {
55 return P.match(Ctx, N);
56 }
57
58 template <typename Pattern, typename MatchContext>
sd_context_match(SDNode * N,const MatchContext & Ctx,Pattern && P)59 [[nodiscard]] bool sd_context_match(SDNode *N, const MatchContext &Ctx,
60 Pattern &&P) {
61 return sd_context_match(SDValue(N, 0), Ctx, P);
62 }
63
64 template <typename Pattern>
sd_match(SDNode * N,const SelectionDAG * DAG,Pattern && P)65 [[nodiscard]] bool sd_match(SDNode *N, const SelectionDAG *DAG, Pattern &&P) {
66 return sd_context_match(N, BasicMatchContext(DAG), P);
67 }
68
69 template <typename Pattern>
sd_match(SDValue N,const SelectionDAG * DAG,Pattern && P)70 [[nodiscard]] bool sd_match(SDValue N, const SelectionDAG *DAG, Pattern &&P) {
71 return sd_context_match(N, BasicMatchContext(DAG), P);
72 }
73
74 template <typename Pattern>
sd_match(SDNode * N,Pattern && P)75 [[nodiscard]] bool sd_match(SDNode *N, Pattern &&P) {
76 return sd_match(N, nullptr, P);
77 }
78
79 template <typename Pattern>
sd_match(SDValue N,Pattern && P)80 [[nodiscard]] bool sd_match(SDValue N, Pattern &&P) {
81 return sd_match(N, nullptr, P);
82 }
83
84 // === Utilities ===
85 struct Value_match {
86 SDValue MatchVal;
87
88 Value_match() = default;
89
Value_matchValue_match90 explicit Value_match(SDValue Match) : MatchVal(Match) {}
91
matchValue_match92 template <typename MatchContext> bool match(const MatchContext &, SDValue N) {
93 if (MatchVal)
94 return MatchVal == N;
95 return N.getNode();
96 }
97 };
98
99 /// Match any valid SDValue.
m_Value()100 inline Value_match m_Value() { return Value_match(); }
101
m_Specific(SDValue N)102 inline Value_match m_Specific(SDValue N) {
103 assert(N);
104 return Value_match(N);
105 }
106
107 struct DeferredValue_match {
108 SDValue &MatchVal;
109
DeferredValue_matchDeferredValue_match110 explicit DeferredValue_match(SDValue &Match) : MatchVal(Match) {}
111
matchDeferredValue_match112 template <typename MatchContext> bool match(const MatchContext &, SDValue N) {
113 return N == MatchVal;
114 }
115 };
116
117 /// Similar to m_Specific, but the specific value to match is determined by
118 /// another sub-pattern in the same sd_match() expression. For instance,
119 /// We cannot match `(add V, V)` with `m_Add(m_Value(X), m_Specific(X))` since
120 /// `X` is not initialized at the time it got copied into `m_Specific`. Instead,
121 /// we should use `m_Add(m_Value(X), m_Deferred(X))`.
m_Deferred(SDValue & V)122 inline DeferredValue_match m_Deferred(SDValue &V) {
123 return DeferredValue_match(V);
124 }
125
126 struct Opcode_match {
127 unsigned Opcode;
128
Opcode_matchOpcode_match129 explicit Opcode_match(unsigned Opc) : Opcode(Opc) {}
130
131 template <typename MatchContext>
matchOpcode_match132 bool match(const MatchContext &Ctx, SDValue N) {
133 return Ctx.match(N, Opcode);
134 }
135 };
136
m_Opc(unsigned Opcode)137 inline Opcode_match m_Opc(unsigned Opcode) { return Opcode_match(Opcode); }
138
139 template <unsigned NumUses, typename Pattern> struct NUses_match {
140 Pattern P;
141
NUses_matchNUses_match142 explicit NUses_match(const Pattern &P) : P(P) {}
143
144 template <typename MatchContext>
matchNUses_match145 bool match(const MatchContext &Ctx, SDValue N) {
146 // SDNode::hasNUsesOfValue is pretty expensive when the SDNode produces
147 // multiple results, hence we check the subsequent pattern here before
148 // checking the number of value users.
149 return P.match(Ctx, N) && N->hasNUsesOfValue(NumUses, N.getResNo());
150 }
151 };
152
153 template <typename Pattern>
m_OneUse(const Pattern & P)154 inline NUses_match<1, Pattern> m_OneUse(const Pattern &P) {
155 return NUses_match<1, Pattern>(P);
156 }
157 template <unsigned N, typename Pattern>
m_NUses(const Pattern & P)158 inline NUses_match<N, Pattern> m_NUses(const Pattern &P) {
159 return NUses_match<N, Pattern>(P);
160 }
161
m_OneUse()162 inline NUses_match<1, Value_match> m_OneUse() {
163 return NUses_match<1, Value_match>(m_Value());
164 }
m_NUses()165 template <unsigned N> inline NUses_match<N, Value_match> m_NUses() {
166 return NUses_match<N, Value_match>(m_Value());
167 }
168
169 struct Value_bind {
170 SDValue &BindVal;
171
Value_bindValue_bind172 explicit Value_bind(SDValue &N) : BindVal(N) {}
173
matchValue_bind174 template <typename MatchContext> bool match(const MatchContext &, SDValue N) {
175 BindVal = N;
176 return true;
177 }
178 };
179
m_Value(SDValue & N)180 inline Value_bind m_Value(SDValue &N) { return Value_bind(N); }
181
182 template <typename Pattern, typename PredFuncT> struct TLI_pred_match {
183 Pattern P;
184 PredFuncT PredFunc;
185
TLI_pred_matchTLI_pred_match186 TLI_pred_match(const PredFuncT &Pred, const Pattern &P)
187 : P(P), PredFunc(Pred) {}
188
189 template <typename MatchContext>
matchTLI_pred_match190 bool match(const MatchContext &Ctx, SDValue N) {
191 assert(Ctx.getTLI() && "TargetLowering is required for this pattern.");
192 return PredFunc(*Ctx.getTLI(), N) && P.match(Ctx, N);
193 }
194 };
195
196 // Explicit deduction guide.
197 template <typename PredFuncT, typename Pattern>
198 TLI_pred_match(const PredFuncT &Pred, const Pattern &P)
199 -> TLI_pred_match<Pattern, PredFuncT>;
200
201 /// Match legal SDNodes based on the information provided by TargetLowering.
m_LegalOp(const Pattern & P)202 template <typename Pattern> inline auto m_LegalOp(const Pattern &P) {
203 return TLI_pred_match{[](const TargetLowering &TLI, SDValue N) {
204 return TLI.isOperationLegal(N->getOpcode(),
205 N.getValueType());
206 },
207 P};
208 }
209
210 /// Switch to a different MatchContext for subsequent patterns.
211 template <typename NewMatchContext, typename Pattern> struct SwitchContext {
212 const NewMatchContext &Ctx;
213 Pattern P;
214
215 template <typename OrigMatchContext>
matchSwitchContext216 bool match(const OrigMatchContext &, SDValue N) {
217 return P.match(Ctx, N);
218 }
219 };
220
221 template <typename MatchContext, typename Pattern>
m_Context(const MatchContext & Ctx,Pattern && P)222 inline SwitchContext<MatchContext, Pattern> m_Context(const MatchContext &Ctx,
223 Pattern &&P) {
224 return SwitchContext<MatchContext, Pattern>{Ctx, std::move(P)};
225 }
226
227 // === Value type ===
228 struct ValueType_bind {
229 EVT &BindVT;
230
ValueType_bindValueType_bind231 explicit ValueType_bind(EVT &Bind) : BindVT(Bind) {}
232
matchValueType_bind233 template <typename MatchContext> bool match(const MatchContext &, SDValue N) {
234 BindVT = N.getValueType();
235 return true;
236 }
237 };
238
239 /// Retreive the ValueType of the current SDValue.
m_VT(EVT & VT)240 inline ValueType_bind m_VT(EVT &VT) { return ValueType_bind(VT); }
241
242 template <typename Pattern, typename PredFuncT> struct ValueType_match {
243 PredFuncT PredFunc;
244 Pattern P;
245
ValueType_matchValueType_match246 ValueType_match(const PredFuncT &Pred, const Pattern &P)
247 : PredFunc(Pred), P(P) {}
248
249 template <typename MatchContext>
matchValueType_match250 bool match(const MatchContext &Ctx, SDValue N) {
251 return PredFunc(N.getValueType()) && P.match(Ctx, N);
252 }
253 };
254
255 // Explicit deduction guide.
256 template <typename PredFuncT, typename Pattern>
257 ValueType_match(const PredFuncT &Pred, const Pattern &P)
258 -> ValueType_match<Pattern, PredFuncT>;
259
260 /// Match a specific ValueType.
261 template <typename Pattern>
m_SpecificVT(EVT RefVT,const Pattern & P)262 inline auto m_SpecificVT(EVT RefVT, const Pattern &P) {
263 return ValueType_match{[=](EVT VT) { return VT == RefVT; }, P};
264 }
m_SpecificVT(EVT RefVT)265 inline auto m_SpecificVT(EVT RefVT) {
266 return ValueType_match{[=](EVT VT) { return VT == RefVT; }, m_Value()};
267 }
268
m_Glue()269 inline auto m_Glue() { return m_SpecificVT(MVT::Glue); }
m_OtherVT()270 inline auto m_OtherVT() { return m_SpecificVT(MVT::Other); }
271
272 /// Match any integer ValueTypes.
m_IntegerVT(const Pattern & P)273 template <typename Pattern> inline auto m_IntegerVT(const Pattern &P) {
274 return ValueType_match{[](EVT VT) { return VT.isInteger(); }, P};
275 }
m_IntegerVT()276 inline auto m_IntegerVT() {
277 return ValueType_match{[](EVT VT) { return VT.isInteger(); }, m_Value()};
278 }
279
280 /// Match any floating point ValueTypes.
m_FloatingPointVT(const Pattern & P)281 template <typename Pattern> inline auto m_FloatingPointVT(const Pattern &P) {
282 return ValueType_match{[](EVT VT) { return VT.isFloatingPoint(); }, P};
283 }
m_FloatingPointVT()284 inline auto m_FloatingPointVT() {
285 return ValueType_match{[](EVT VT) { return VT.isFloatingPoint(); },
286 m_Value()};
287 }
288
289 /// Match any vector ValueTypes.
m_VectorVT(const Pattern & P)290 template <typename Pattern> inline auto m_VectorVT(const Pattern &P) {
291 return ValueType_match{[](EVT VT) { return VT.isVector(); }, P};
292 }
m_VectorVT()293 inline auto m_VectorVT() {
294 return ValueType_match{[](EVT VT) { return VT.isVector(); }, m_Value()};
295 }
296
297 /// Match fixed-length vector ValueTypes.
m_FixedVectorVT(const Pattern & P)298 template <typename Pattern> inline auto m_FixedVectorVT(const Pattern &P) {
299 return ValueType_match{[](EVT VT) { return VT.isFixedLengthVector(); }, P};
300 }
m_FixedVectorVT()301 inline auto m_FixedVectorVT() {
302 return ValueType_match{[](EVT VT) { return VT.isFixedLengthVector(); },
303 m_Value()};
304 }
305
306 /// Match scalable vector ValueTypes.
m_ScalableVectorVT(const Pattern & P)307 template <typename Pattern> inline auto m_ScalableVectorVT(const Pattern &P) {
308 return ValueType_match{[](EVT VT) { return VT.isScalableVector(); }, P};
309 }
m_ScalableVectorVT()310 inline auto m_ScalableVectorVT() {
311 return ValueType_match{[](EVT VT) { return VT.isScalableVector(); },
312 m_Value()};
313 }
314
315 /// Match legal ValueTypes based on the information provided by TargetLowering.
m_LegalType(const Pattern & P)316 template <typename Pattern> inline auto m_LegalType(const Pattern &P) {
317 return TLI_pred_match{[](const TargetLowering &TLI, SDValue N) {
318 return TLI.isTypeLegal(N.getValueType());
319 },
320 P};
321 }
322
323 // === Patterns combinators ===
324 template <typename... Preds> struct And {
matchAnd325 template <typename MatchContext> bool match(const MatchContext &, SDValue N) {
326 return true;
327 }
328 };
329
330 template <typename Pred, typename... Preds>
331 struct And<Pred, Preds...> : And<Preds...> {
332 Pred P;
333 And(const Pred &p, const Preds &...preds) : And<Preds...>(preds...), P(p) {}
334
335 template <typename MatchContext>
336 bool match(const MatchContext &Ctx, SDValue N) {
337 return P.match(Ctx, N) && And<Preds...>::match(Ctx, N);
338 }
339 };
340
341 template <typename... Preds> struct Or {
342 template <typename MatchContext> bool match(const MatchContext &, SDValue N) {
343 return false;
344 }
345 };
346
347 template <typename Pred, typename... Preds>
348 struct Or<Pred, Preds...> : Or<Preds...> {
349 Pred P;
350 Or(const Pred &p, const Preds &...preds) : Or<Preds...>(preds...), P(p) {}
351
352 template <typename MatchContext>
353 bool match(const MatchContext &Ctx, SDValue N) {
354 return P.match(Ctx, N) || Or<Preds...>::match(Ctx, N);
355 }
356 };
357
358 template <typename Pred> struct Not {
359 Pred P;
360
361 explicit Not(const Pred &P) : P(P) {}
362
363 template <typename MatchContext>
364 bool match(const MatchContext &Ctx, SDValue N) {
365 return !P.match(Ctx, N);
366 }
367 };
368 // Explicit deduction guide.
369 template <typename Pred> Not(const Pred &P) -> Not<Pred>;
370
371 /// Match if the inner pattern does NOT match.
372 template <typename Pred> inline Not<Pred> m_Unless(const Pred &P) {
373 return Not{P};
374 }
375
376 template <typename... Preds> And<Preds...> m_AllOf(const Preds &...preds) {
377 return And<Preds...>(preds...);
378 }
379
380 template <typename... Preds> Or<Preds...> m_AnyOf(const Preds &...preds) {
381 return Or<Preds...>(preds...);
382 }
383
384 template <typename... Preds> auto m_NoneOf(const Preds &...preds) {
385 return m_Unless(m_AnyOf(preds...));
386 }
387
388 // === Generic node matching ===
389 template <unsigned OpIdx, typename... OpndPreds> struct Operands_match {
390 template <typename MatchContext>
391 bool match(const MatchContext &Ctx, SDValue N) {
392 // Returns false if there are more operands than predicates;
393 return N->getNumOperands() == OpIdx;
394 }
395 };
396
397 template <unsigned OpIdx, typename OpndPred, typename... OpndPreds>
398 struct Operands_match<OpIdx, OpndPred, OpndPreds...>
399 : Operands_match<OpIdx + 1, OpndPreds...> {
400 OpndPred P;
401
402 Operands_match(const OpndPred &p, const OpndPreds &...preds)
403 : Operands_match<OpIdx + 1, OpndPreds...>(preds...), P(p) {}
404
405 template <typename MatchContext>
406 bool match(const MatchContext &Ctx, SDValue N) {
407 if (OpIdx < N->getNumOperands())
408 return P.match(Ctx, N->getOperand(OpIdx)) &&
409 Operands_match<OpIdx + 1, OpndPreds...>::match(Ctx, N);
410
411 // This is the case where there are more predicates than operands.
412 return false;
413 }
414 };
415
416 template <typename... OpndPreds>
417 auto m_Node(unsigned Opcode, const OpndPreds &...preds) {
418 return m_AllOf(m_Opc(Opcode), Operands_match<0, OpndPreds...>(preds...));
419 }
420
421 /// Provide number of operands that are not chain or glue, as well as the first
422 /// index of such operand.
423 template <bool ExcludeChain> struct EffectiveOperands {
424 unsigned Size = 0;
425 unsigned FirstIndex = 0;
426
427 explicit EffectiveOperands(SDValue N) {
428 const unsigned TotalNumOps = N->getNumOperands();
429 FirstIndex = TotalNumOps;
430 for (unsigned I = 0; I < TotalNumOps; ++I) {
431 // Count the number of non-chain and non-glue nodes (we ignore chain
432 // and glue by default) and retreive the operand index offset.
433 EVT VT = N->getOperand(I).getValueType();
434 if (VT != MVT::Glue && VT != MVT::Other) {
435 ++Size;
436 if (FirstIndex == TotalNumOps)
437 FirstIndex = I;
438 }
439 }
440 }
441 };
442
443 template <> struct EffectiveOperands<false> {
444 unsigned Size = 0;
445 unsigned FirstIndex = 0;
446
447 explicit EffectiveOperands(SDValue N) : Size(N->getNumOperands()) {}
448 };
449
450 // === Ternary operations ===
451 template <typename T0_P, typename T1_P, typename T2_P, bool Commutable = false,
452 bool ExcludeChain = false>
453 struct TernaryOpc_match {
454 unsigned Opcode;
455 T0_P Op0;
456 T1_P Op1;
457 T2_P Op2;
458
459 TernaryOpc_match(unsigned Opc, const T0_P &Op0, const T1_P &Op1,
460 const T2_P &Op2)
461 : Opcode(Opc), Op0(Op0), Op1(Op1), Op2(Op2) {}
462
463 template <typename MatchContext>
464 bool match(const MatchContext &Ctx, SDValue N) {
465 if (sd_context_match(N, Ctx, m_Opc(Opcode))) {
466 EffectiveOperands<ExcludeChain> EO(N);
467 assert(EO.Size == 3);
468 return ((Op0.match(Ctx, N->getOperand(EO.FirstIndex)) &&
469 Op1.match(Ctx, N->getOperand(EO.FirstIndex + 1))) ||
470 (Commutable && Op0.match(Ctx, N->getOperand(EO.FirstIndex + 1)) &&
471 Op1.match(Ctx, N->getOperand(EO.FirstIndex)))) &&
472 Op2.match(Ctx, N->getOperand(EO.FirstIndex + 2));
473 }
474
475 return false;
476 }
477 };
478
479 template <typename T0_P, typename T1_P, typename T2_P>
480 inline TernaryOpc_match<T0_P, T1_P, T2_P, false, false>
481 m_SetCC(const T0_P &LHS, const T1_P &RHS, const T2_P &CC) {
482 return TernaryOpc_match<T0_P, T1_P, T2_P, false, false>(ISD::SETCC, LHS, RHS,
483 CC);
484 }
485
486 template <typename T0_P, typename T1_P, typename T2_P>
487 inline TernaryOpc_match<T0_P, T1_P, T2_P, true, false>
488 m_c_SetCC(const T0_P &LHS, const T1_P &RHS, const T2_P &CC) {
489 return TernaryOpc_match<T0_P, T1_P, T2_P, true, false>(ISD::SETCC, LHS, RHS,
490 CC);
491 }
492
493 // === Binary operations ===
494 template <typename LHS_P, typename RHS_P, bool Commutable = false,
495 bool ExcludeChain = false>
496 struct BinaryOpc_match {
497 unsigned Opcode;
498 LHS_P LHS;
499 RHS_P RHS;
500
501 BinaryOpc_match(unsigned Opc, const LHS_P &L, const RHS_P &R)
502 : Opcode(Opc), LHS(L), RHS(R) {}
503
504 template <typename MatchContext>
505 bool match(const MatchContext &Ctx, SDValue N) {
506 if (sd_context_match(N, Ctx, m_Opc(Opcode))) {
507 EffectiveOperands<ExcludeChain> EO(N);
508 assert(EO.Size == 2);
509 return (LHS.match(Ctx, N->getOperand(EO.FirstIndex)) &&
510 RHS.match(Ctx, N->getOperand(EO.FirstIndex + 1))) ||
511 (Commutable && LHS.match(Ctx, N->getOperand(EO.FirstIndex + 1)) &&
512 RHS.match(Ctx, N->getOperand(EO.FirstIndex)));
513 }
514
515 return false;
516 }
517 };
518
519 template <typename LHS, typename RHS>
520 inline BinaryOpc_match<LHS, RHS, false> m_BinOp(unsigned Opc, const LHS &L,
521 const RHS &R) {
522 return BinaryOpc_match<LHS, RHS, false>(Opc, L, R);
523 }
524 template <typename LHS, typename RHS>
525 inline BinaryOpc_match<LHS, RHS, true> m_c_BinOp(unsigned Opc, const LHS &L,
526 const RHS &R) {
527 return BinaryOpc_match<LHS, RHS, true>(Opc, L, R);
528 }
529
530 template <typename LHS, typename RHS>
531 inline BinaryOpc_match<LHS, RHS, false, true>
532 m_ChainedBinOp(unsigned Opc, const LHS &L, const RHS &R) {
533 return BinaryOpc_match<LHS, RHS, false, true>(Opc, L, R);
534 }
535 template <typename LHS, typename RHS>
536 inline BinaryOpc_match<LHS, RHS, true, true>
537 m_c_ChainedBinOp(unsigned Opc, const LHS &L, const RHS &R) {
538 return BinaryOpc_match<LHS, RHS, true, true>(Opc, L, R);
539 }
540
541 // Common binary operations
542 template <typename LHS, typename RHS>
543 inline BinaryOpc_match<LHS, RHS, true> m_Add(const LHS &L, const RHS &R) {
544 return BinaryOpc_match<LHS, RHS, true>(ISD::ADD, L, R);
545 }
546
547 template <typename LHS, typename RHS>
548 inline BinaryOpc_match<LHS, RHS, false> m_Sub(const LHS &L, const RHS &R) {
549 return BinaryOpc_match<LHS, RHS, false>(ISD::SUB, L, R);
550 }
551
552 template <typename LHS, typename RHS>
553 inline BinaryOpc_match<LHS, RHS, true> m_Mul(const LHS &L, const RHS &R) {
554 return BinaryOpc_match<LHS, RHS, true>(ISD::MUL, L, R);
555 }
556
557 template <typename LHS, typename RHS>
558 inline BinaryOpc_match<LHS, RHS, true> m_And(const LHS &L, const RHS &R) {
559 return BinaryOpc_match<LHS, RHS, true>(ISD::AND, L, R);
560 }
561
562 template <typename LHS, typename RHS>
563 inline BinaryOpc_match<LHS, RHS, true> m_Or(const LHS &L, const RHS &R) {
564 return BinaryOpc_match<LHS, RHS, true>(ISD::OR, L, R);
565 }
566
567 template <typename LHS, typename RHS>
568 inline BinaryOpc_match<LHS, RHS, true> m_Xor(const LHS &L, const RHS &R) {
569 return BinaryOpc_match<LHS, RHS, true>(ISD::XOR, L, R);
570 }
571
572 template <typename LHS, typename RHS>
573 inline BinaryOpc_match<LHS, RHS, true> m_SMin(const LHS &L, const RHS &R) {
574 return BinaryOpc_match<LHS, RHS, true>(ISD::SMIN, L, R);
575 }
576
577 template <typename LHS, typename RHS>
578 inline BinaryOpc_match<LHS, RHS, true> m_SMax(const LHS &L, const RHS &R) {
579 return BinaryOpc_match<LHS, RHS, true>(ISD::SMAX, L, R);
580 }
581
582 template <typename LHS, typename RHS>
583 inline BinaryOpc_match<LHS, RHS, true> m_UMin(const LHS &L, const RHS &R) {
584 return BinaryOpc_match<LHS, RHS, true>(ISD::UMIN, L, R);
585 }
586
587 template <typename LHS, typename RHS>
588 inline BinaryOpc_match<LHS, RHS, true> m_UMax(const LHS &L, const RHS &R) {
589 return BinaryOpc_match<LHS, RHS, true>(ISD::UMAX, L, R);
590 }
591
592 template <typename LHS, typename RHS>
593 inline BinaryOpc_match<LHS, RHS, false> m_UDiv(const LHS &L, const RHS &R) {
594 return BinaryOpc_match<LHS, RHS, false>(ISD::UDIV, L, R);
595 }
596 template <typename LHS, typename RHS>
597 inline BinaryOpc_match<LHS, RHS, false> m_SDiv(const LHS &L, const RHS &R) {
598 return BinaryOpc_match<LHS, RHS, false>(ISD::SDIV, L, R);
599 }
600
601 template <typename LHS, typename RHS>
602 inline BinaryOpc_match<LHS, RHS, false> m_URem(const LHS &L, const RHS &R) {
603 return BinaryOpc_match<LHS, RHS, false>(ISD::UREM, L, R);
604 }
605 template <typename LHS, typename RHS>
606 inline BinaryOpc_match<LHS, RHS, false> m_SRem(const LHS &L, const RHS &R) {
607 return BinaryOpc_match<LHS, RHS, false>(ISD::SREM, L, R);
608 }
609
610 template <typename LHS, typename RHS>
611 inline BinaryOpc_match<LHS, RHS, false> m_Shl(const LHS &L, const RHS &R) {
612 return BinaryOpc_match<LHS, RHS, false>(ISD::SHL, L, R);
613 }
614
615 template <typename LHS, typename RHS>
616 inline BinaryOpc_match<LHS, RHS, false> m_Sra(const LHS &L, const RHS &R) {
617 return BinaryOpc_match<LHS, RHS, false>(ISD::SRA, L, R);
618 }
619 template <typename LHS, typename RHS>
620 inline BinaryOpc_match<LHS, RHS, false> m_Srl(const LHS &L, const RHS &R) {
621 return BinaryOpc_match<LHS, RHS, false>(ISD::SRL, L, R);
622 }
623
624 template <typename LHS, typename RHS>
625 inline BinaryOpc_match<LHS, RHS, true> m_FAdd(const LHS &L, const RHS &R) {
626 return BinaryOpc_match<LHS, RHS, true>(ISD::FADD, L, R);
627 }
628
629 template <typename LHS, typename RHS>
630 inline BinaryOpc_match<LHS, RHS, false> m_FSub(const LHS &L, const RHS &R) {
631 return BinaryOpc_match<LHS, RHS, false>(ISD::FSUB, L, R);
632 }
633
634 template <typename LHS, typename RHS>
635 inline BinaryOpc_match<LHS, RHS, true> m_FMul(const LHS &L, const RHS &R) {
636 return BinaryOpc_match<LHS, RHS, true>(ISD::FMUL, L, R);
637 }
638
639 template <typename LHS, typename RHS>
640 inline BinaryOpc_match<LHS, RHS, false> m_FDiv(const LHS &L, const RHS &R) {
641 return BinaryOpc_match<LHS, RHS, false>(ISD::FDIV, L, R);
642 }
643
644 template <typename LHS, typename RHS>
645 inline BinaryOpc_match<LHS, RHS, false> m_FRem(const LHS &L, const RHS &R) {
646 return BinaryOpc_match<LHS, RHS, false>(ISD::FREM, L, R);
647 }
648
649 // === Unary operations ===
650 template <typename Opnd_P, bool ExcludeChain = false> struct UnaryOpc_match {
651 unsigned Opcode;
652 Opnd_P Opnd;
653
654 UnaryOpc_match(unsigned Opc, const Opnd_P &Op) : Opcode(Opc), Opnd(Op) {}
655
656 template <typename MatchContext>
657 bool match(const MatchContext &Ctx, SDValue N) {
658 if (sd_context_match(N, Ctx, m_Opc(Opcode))) {
659 EffectiveOperands<ExcludeChain> EO(N);
660 assert(EO.Size == 1);
661 return Opnd.match(Ctx, N->getOperand(EO.FirstIndex));
662 }
663
664 return false;
665 }
666 };
667
668 template <typename Opnd>
669 inline UnaryOpc_match<Opnd> m_UnaryOp(unsigned Opc, const Opnd &Op) {
670 return UnaryOpc_match<Opnd>(Opc, Op);
671 }
672 template <typename Opnd>
673 inline UnaryOpc_match<Opnd, true> m_ChainedUnaryOp(unsigned Opc,
674 const Opnd &Op) {
675 return UnaryOpc_match<Opnd, true>(Opc, Op);
676 }
677
678 template <typename Opnd>
679 inline UnaryOpc_match<Opnd> m_BitReverse(const Opnd &Op) {
680 return UnaryOpc_match<Opnd>(ISD::BITREVERSE, Op);
681 }
682
683 template <typename Opnd> inline UnaryOpc_match<Opnd> m_ZExt(const Opnd &Op) {
684 return UnaryOpc_match<Opnd>(ISD::ZERO_EXTEND, Op);
685 }
686
687 template <typename Opnd> inline auto m_SExt(const Opnd &Op) {
688 return UnaryOpc_match<Opnd>(ISD::SIGN_EXTEND, Op);
689 }
690
691 template <typename Opnd> inline UnaryOpc_match<Opnd> m_AnyExt(const Opnd &Op) {
692 return UnaryOpc_match<Opnd>(ISD::ANY_EXTEND, Op);
693 }
694
695 template <typename Opnd> inline UnaryOpc_match<Opnd> m_Trunc(const Opnd &Op) {
696 return UnaryOpc_match<Opnd>(ISD::TRUNCATE, Op);
697 }
698
699 /// Match a zext or identity
700 /// Allows to peek through optional extensions
701 template <typename Opnd> inline auto m_ZExtOrSelf(const Opnd &Op) {
702 return m_AnyOf(m_ZExt(Op), Op);
703 }
704
705 /// Match a sext or identity
706 /// Allows to peek through optional extensions
707 template <typename Opnd> inline auto m_SExtOrSelf(const Opnd &Op) {
708 return m_AnyOf(m_SExt(Op), Op);
709 }
710
711 /// Match a aext or identity
712 /// Allows to peek through optional extensions
713 template <typename Opnd>
714 inline Or<UnaryOpc_match<Opnd>, Opnd> m_AExtOrSelf(const Opnd &Op) {
715 return Or<UnaryOpc_match<Opnd>, Opnd>(m_AnyExt(Op), Op);
716 }
717
718 /// Match a trunc or identity
719 /// Allows to peek through optional truncations
720 template <typename Opnd>
721 inline Or<UnaryOpc_match<Opnd>, Opnd> m_TruncOrSelf(const Opnd &Op) {
722 return Or<UnaryOpc_match<Opnd>, Opnd>(m_Trunc(Op), Op);
723 }
724
725 // === Constants ===
726 struct ConstantInt_match {
727 APInt *BindVal;
728
729 explicit ConstantInt_match(APInt *V) : BindVal(V) {}
730
731 template <typename MatchContext> bool match(const MatchContext &, SDValue N) {
732 // The logics here are similar to that in
733 // SelectionDAG::isConstantIntBuildVectorOrConstantInt, but the latter also
734 // treats GlobalAddressSDNode as a constant, which is difficult to turn into
735 // APInt.
736 if (auto *C = dyn_cast_or_null<ConstantSDNode>(N.getNode())) {
737 if (BindVal)
738 *BindVal = C->getAPIntValue();
739 return true;
740 }
741
742 APInt Discard;
743 return ISD::isConstantSplatVector(N.getNode(),
744 BindVal ? *BindVal : Discard);
745 }
746 };
747 /// Match any interger constants or splat of an integer constant.
748 inline ConstantInt_match m_ConstInt() { return ConstantInt_match(nullptr); }
749 /// Match any interger constants or splat of an integer constant; return the
750 /// specific constant or constant splat value.
751 inline ConstantInt_match m_ConstInt(APInt &V) { return ConstantInt_match(&V); }
752
753 struct SpecificInt_match {
754 APInt IntVal;
755
756 explicit SpecificInt_match(APInt APV) : IntVal(std::move(APV)) {}
757
758 template <typename MatchContext>
759 bool match(const MatchContext &Ctx, SDValue N) {
760 APInt ConstInt;
761 if (sd_context_match(N, Ctx, m_ConstInt(ConstInt)))
762 return APInt::isSameValue(IntVal, ConstInt);
763 return false;
764 }
765 };
766
767 /// Match a specific integer constant or constant splat value.
768 inline SpecificInt_match m_SpecificInt(APInt V) {
769 return SpecificInt_match(std::move(V));
770 }
771 inline SpecificInt_match m_SpecificInt(uint64_t V) {
772 return SpecificInt_match(APInt(64, V));
773 }
774
775 inline SpecificInt_match m_Zero() { return m_SpecificInt(0U); }
776 inline SpecificInt_match m_One() { return m_SpecificInt(1U); }
777
778 struct AllOnes_match {
779
780 AllOnes_match() = default;
781
782 template <typename MatchContext> bool match(const MatchContext &, SDValue N) {
783 return isAllOnesOrAllOnesSplat(N);
784 }
785 };
786
787 inline AllOnes_match m_AllOnes() { return AllOnes_match(); }
788
789 /// Match true boolean value based on the information provided by
790 /// TargetLowering.
791 inline auto m_True() {
792 return TLI_pred_match{
793 [](const TargetLowering &TLI, SDValue N) {
794 APInt ConstVal;
795 if (sd_match(N, m_ConstInt(ConstVal)))
796 switch (TLI.getBooleanContents(N.getValueType())) {
797 case TargetLowering::ZeroOrOneBooleanContent:
798 return ConstVal.isOne();
799 case TargetLowering::ZeroOrNegativeOneBooleanContent:
800 return ConstVal.isAllOnes();
801 case TargetLowering::UndefinedBooleanContent:
802 return (ConstVal & 0x01) == 1;
803 }
804
805 return false;
806 },
807 m_Value()};
808 }
809 /// Match false boolean value based on the information provided by
810 /// TargetLowering.
811 inline auto m_False() {
812 return TLI_pred_match{
813 [](const TargetLowering &TLI, SDValue N) {
814 APInt ConstVal;
815 if (sd_match(N, m_ConstInt(ConstVal)))
816 switch (TLI.getBooleanContents(N.getValueType())) {
817 case TargetLowering::ZeroOrOneBooleanContent:
818 case TargetLowering::ZeroOrNegativeOneBooleanContent:
819 return ConstVal.isZero();
820 case TargetLowering::UndefinedBooleanContent:
821 return (ConstVal & 0x01) == 0;
822 }
823
824 return false;
825 },
826 m_Value()};
827 }
828
829 struct CondCode_match {
830 std::optional<ISD::CondCode> CCToMatch;
831 ISD::CondCode *BindCC = nullptr;
832
833 explicit CondCode_match(ISD::CondCode CC) : CCToMatch(CC) {}
834
835 explicit CondCode_match(ISD::CondCode *CC) : BindCC(CC) {}
836
837 template <typename MatchContext> bool match(const MatchContext &, SDValue N) {
838 if (auto *CC = dyn_cast<CondCodeSDNode>(N.getNode())) {
839 if (CCToMatch && *CCToMatch != CC->get())
840 return false;
841
842 if (BindCC)
843 *BindCC = CC->get();
844 return true;
845 }
846
847 return false;
848 }
849 };
850
851 /// Match any conditional code SDNode.
852 inline CondCode_match m_CondCode() { return CondCode_match(nullptr); }
853 /// Match any conditional code SDNode and return its ISD::CondCode value.
854 inline CondCode_match m_CondCode(ISD::CondCode &CC) {
855 return CondCode_match(&CC);
856 }
857 /// Match a conditional code SDNode with a specific ISD::CondCode.
858 inline CondCode_match m_SpecificCondCode(ISD::CondCode CC) {
859 return CondCode_match(CC);
860 }
861
862 /// Match a negate as a sub(0, v)
863 template <typename ValTy>
864 inline BinaryOpc_match<SpecificInt_match, ValTy> m_Neg(const ValTy &V) {
865 return m_Sub(m_Zero(), V);
866 }
867
868 /// Match a Not as a xor(v, -1) or xor(-1, v)
869 template <typename ValTy>
870 inline BinaryOpc_match<ValTy, AllOnes_match, true> m_Not(const ValTy &V) {
871 return m_Xor(V, m_AllOnes());
872 }
873
874 } // namespace SDPatternMatch
875 } // namespace llvm
876 #endif
877