1 //==------ llvm/CodeGen/GlobalISel/MIPatternMatch.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 //
9 /// Contains matchers for matching SSA Machine Instructions.
10 //
11 //===----------------------------------------------------------------------===//
12 #ifndef LLVM_GMIR_PATTERNMATCH_H
13 #define LLVM_GMIR_PATTERNMATCH_H
14
15 #include "llvm/CodeGen/GlobalISel/Utils.h"
16 #include "llvm/CodeGen/MachineRegisterInfo.h"
17 #include "llvm/IR/InstrTypes.h"
18
19 namespace llvm {
20 namespace MIPatternMatch {
21
22 template <typename Reg, typename Pattern>
mi_match(Reg R,const MachineRegisterInfo & MRI,Pattern && P)23 bool mi_match(Reg R, const MachineRegisterInfo &MRI, Pattern &&P) {
24 return P.match(MRI, R);
25 }
26
27 // TODO: Extend for N use.
28 template <typename SubPatternT> struct OneUse_match {
29 SubPatternT SubPat;
OneUse_matchOneUse_match30 OneUse_match(const SubPatternT &SP) : SubPat(SP) {}
31
matchOneUse_match32 bool match(const MachineRegisterInfo &MRI, Register Reg) {
33 return MRI.hasOneUse(Reg) && SubPat.match(MRI, Reg);
34 }
35 };
36
37 template <typename SubPat>
m_OneUse(const SubPat & SP)38 inline OneUse_match<SubPat> m_OneUse(const SubPat &SP) {
39 return SP;
40 }
41
42 template <typename SubPatternT> struct OneNonDBGUse_match {
43 SubPatternT SubPat;
OneNonDBGUse_matchOneNonDBGUse_match44 OneNonDBGUse_match(const SubPatternT &SP) : SubPat(SP) {}
45
matchOneNonDBGUse_match46 bool match(const MachineRegisterInfo &MRI, Register Reg) {
47 return MRI.hasOneNonDBGUse(Reg) && SubPat.match(MRI, Reg);
48 }
49 };
50
51 template <typename SubPat>
m_OneNonDBGUse(const SubPat & SP)52 inline OneNonDBGUse_match<SubPat> m_OneNonDBGUse(const SubPat &SP) {
53 return SP;
54 }
55
56 struct ConstantMatch {
57 int64_t &CR;
ConstantMatchConstantMatch58 ConstantMatch(int64_t &C) : CR(C) {}
matchConstantMatch59 bool match(const MachineRegisterInfo &MRI, Register Reg) {
60 if (auto MaybeCst = getConstantVRegSExtVal(Reg, MRI)) {
61 CR = *MaybeCst;
62 return true;
63 }
64 return false;
65 }
66 };
67
m_ICst(int64_t & Cst)68 inline ConstantMatch m_ICst(int64_t &Cst) { return ConstantMatch(Cst); }
69
70 /// Matcher for a specific constant value.
71 struct SpecificConstantMatch {
72 int64_t RequestedVal;
SpecificConstantMatchSpecificConstantMatch73 SpecificConstantMatch(int64_t RequestedVal) : RequestedVal(RequestedVal) {}
matchSpecificConstantMatch74 bool match(const MachineRegisterInfo &MRI, Register Reg) {
75 int64_t MatchedVal;
76 return mi_match(Reg, MRI, m_ICst(MatchedVal)) && MatchedVal == RequestedVal;
77 }
78 };
79
80 /// Matches a constant equal to \p RequestedValue.
m_SpecificICst(int64_t RequestedValue)81 inline SpecificConstantMatch m_SpecificICst(int64_t RequestedValue) {
82 return SpecificConstantMatch(RequestedValue);
83 }
84
85 ///{
86 /// Convenience matchers for specific integer values.
m_ZeroInt()87 inline SpecificConstantMatch m_ZeroInt() { return SpecificConstantMatch(0); }
m_AllOnesInt()88 inline SpecificConstantMatch m_AllOnesInt() {
89 return SpecificConstantMatch(-1);
90 }
91 ///}
92
93 // TODO: Rework this for different kinds of MachineOperand.
94 // Currently assumes the Src for a match is a register.
95 // We might want to support taking in some MachineOperands and call getReg on
96 // that.
97
98 struct operand_type_match {
matchoperand_type_match99 bool match(const MachineRegisterInfo &MRI, Register Reg) { return true; }
matchoperand_type_match100 bool match(const MachineRegisterInfo &MRI, MachineOperand *MO) {
101 return MO->isReg();
102 }
103 };
104
m_Reg()105 inline operand_type_match m_Reg() { return operand_type_match(); }
106
107 /// Matching combinators.
108 template <typename... Preds> struct And {
109 template <typename MatchSrc>
matchAnd110 bool match(const MachineRegisterInfo &MRI, MatchSrc &&src) {
111 return true;
112 }
113 };
114
115 template <typename Pred, typename... Preds>
116 struct And<Pred, Preds...> : And<Preds...> {
117 Pred P;
118 And(Pred &&p, Preds &&... preds)
119 : And<Preds...>(std::forward<Preds>(preds)...), P(std::forward<Pred>(p)) {
120 }
121 template <typename MatchSrc>
122 bool match(const MachineRegisterInfo &MRI, MatchSrc &&src) {
123 return P.match(MRI, src) && And<Preds...>::match(MRI, src);
124 }
125 };
126
127 template <typename... Preds> struct Or {
128 template <typename MatchSrc>
129 bool match(const MachineRegisterInfo &MRI, MatchSrc &&src) {
130 return false;
131 }
132 };
133
134 template <typename Pred, typename... Preds>
135 struct Or<Pred, Preds...> : Or<Preds...> {
136 Pred P;
137 Or(Pred &&p, Preds &&... preds)
138 : Or<Preds...>(std::forward<Preds>(preds)...), P(std::forward<Pred>(p)) {}
139 template <typename MatchSrc>
140 bool match(const MachineRegisterInfo &MRI, MatchSrc &&src) {
141 return P.match(MRI, src) || Or<Preds...>::match(MRI, src);
142 }
143 };
144
145 template <typename... Preds> And<Preds...> m_all_of(Preds &&... preds) {
146 return And<Preds...>(std::forward<Preds>(preds)...);
147 }
148
149 template <typename... Preds> Or<Preds...> m_any_of(Preds &&... preds) {
150 return Or<Preds...>(std::forward<Preds>(preds)...);
151 }
152
153 template <typename BindTy> struct bind_helper {
154 static bool bind(const MachineRegisterInfo &MRI, BindTy &VR, BindTy &V) {
155 VR = V;
156 return true;
157 }
158 };
159
160 template <> struct bind_helper<MachineInstr *> {
161 static bool bind(const MachineRegisterInfo &MRI, MachineInstr *&MI,
162 Register Reg) {
163 MI = MRI.getVRegDef(Reg);
164 if (MI)
165 return true;
166 return false;
167 }
168 };
169
170 template <> struct bind_helper<LLT> {
171 static bool bind(const MachineRegisterInfo &MRI, LLT Ty, Register Reg) {
172 Ty = MRI.getType(Reg);
173 if (Ty.isValid())
174 return true;
175 return false;
176 }
177 };
178
179 template <> struct bind_helper<const ConstantFP *> {
180 static bool bind(const MachineRegisterInfo &MRI, const ConstantFP *&F,
181 Register Reg) {
182 F = getConstantFPVRegVal(Reg, MRI);
183 if (F)
184 return true;
185 return false;
186 }
187 };
188
189 template <typename Class> struct bind_ty {
190 Class &VR;
191
192 bind_ty(Class &V) : VR(V) {}
193
194 template <typename ITy> bool match(const MachineRegisterInfo &MRI, ITy &&V) {
195 return bind_helper<Class>::bind(MRI, VR, V);
196 }
197 };
198
199 inline bind_ty<Register> m_Reg(Register &R) { return R; }
200 inline bind_ty<MachineInstr *> m_MInstr(MachineInstr *&MI) { return MI; }
201 inline bind_ty<LLT> m_Type(LLT Ty) { return Ty; }
202 inline bind_ty<CmpInst::Predicate> m_Pred(CmpInst::Predicate &P) { return P; }
203 inline operand_type_match m_Pred() { return operand_type_match(); }
204
205 // Helper for matching G_FCONSTANT
206 inline bind_ty<const ConstantFP *> m_GFCst(const ConstantFP *&C) { return C; }
207
208 // General helper for all the binary generic MI such as G_ADD/G_SUB etc
209 template <typename LHS_P, typename RHS_P, unsigned Opcode,
210 bool Commutable = false>
211 struct BinaryOp_match {
212 LHS_P L;
213 RHS_P R;
214
215 BinaryOp_match(const LHS_P &LHS, const RHS_P &RHS) : L(LHS), R(RHS) {}
216 template <typename OpTy>
217 bool match(const MachineRegisterInfo &MRI, OpTy &&Op) {
218 MachineInstr *TmpMI;
219 if (mi_match(Op, MRI, m_MInstr(TmpMI))) {
220 if (TmpMI->getOpcode() == Opcode && TmpMI->getNumOperands() == 3) {
221 return (L.match(MRI, TmpMI->getOperand(1).getReg()) &&
222 R.match(MRI, TmpMI->getOperand(2).getReg())) ||
223 (Commutable && (R.match(MRI, TmpMI->getOperand(1).getReg()) &&
224 L.match(MRI, TmpMI->getOperand(2).getReg())));
225 }
226 }
227 return false;
228 }
229 };
230
231 template <typename LHS, typename RHS>
232 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_ADD, true>
233 m_GAdd(const LHS &L, const RHS &R) {
234 return BinaryOp_match<LHS, RHS, TargetOpcode::G_ADD, true>(L, R);
235 }
236
237 template <typename LHS, typename RHS>
238 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_PTR_ADD, true>
239 m_GPtrAdd(const LHS &L, const RHS &R) {
240 return BinaryOp_match<LHS, RHS, TargetOpcode::G_PTR_ADD, true>(L, R);
241 }
242
243 template <typename LHS, typename RHS>
244 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_SUB> m_GSub(const LHS &L,
245 const RHS &R) {
246 return BinaryOp_match<LHS, RHS, TargetOpcode::G_SUB>(L, R);
247 }
248
249 template <typename LHS, typename RHS>
250 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_MUL, true>
251 m_GMul(const LHS &L, const RHS &R) {
252 return BinaryOp_match<LHS, RHS, TargetOpcode::G_MUL, true>(L, R);
253 }
254
255 template <typename LHS, typename RHS>
256 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_FADD, true>
257 m_GFAdd(const LHS &L, const RHS &R) {
258 return BinaryOp_match<LHS, RHS, TargetOpcode::G_FADD, true>(L, R);
259 }
260
261 template <typename LHS, typename RHS>
262 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_FMUL, true>
263 m_GFMul(const LHS &L, const RHS &R) {
264 return BinaryOp_match<LHS, RHS, TargetOpcode::G_FMUL, true>(L, R);
265 }
266
267 template <typename LHS, typename RHS>
268 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_FSUB, false>
269 m_GFSub(const LHS &L, const RHS &R) {
270 return BinaryOp_match<LHS, RHS, TargetOpcode::G_FSUB, false>(L, R);
271 }
272
273 template <typename LHS, typename RHS>
274 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_AND, true>
275 m_GAnd(const LHS &L, const RHS &R) {
276 return BinaryOp_match<LHS, RHS, TargetOpcode::G_AND, true>(L, R);
277 }
278
279 template <typename LHS, typename RHS>
280 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_XOR, true>
281 m_GXor(const LHS &L, const RHS &R) {
282 return BinaryOp_match<LHS, RHS, TargetOpcode::G_XOR, true>(L, R);
283 }
284
285 template <typename LHS, typename RHS>
286 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_OR, true> m_GOr(const LHS &L,
287 const RHS &R) {
288 return BinaryOp_match<LHS, RHS, TargetOpcode::G_OR, true>(L, R);
289 }
290
291 template <typename LHS, typename RHS>
292 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_SHL, false>
293 m_GShl(const LHS &L, const RHS &R) {
294 return BinaryOp_match<LHS, RHS, TargetOpcode::G_SHL, false>(L, R);
295 }
296
297 template <typename LHS, typename RHS>
298 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_LSHR, false>
299 m_GLShr(const LHS &L, const RHS &R) {
300 return BinaryOp_match<LHS, RHS, TargetOpcode::G_LSHR, false>(L, R);
301 }
302
303 template <typename LHS, typename RHS>
304 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_ASHR, false>
305 m_GAShr(const LHS &L, const RHS &R) {
306 return BinaryOp_match<LHS, RHS, TargetOpcode::G_ASHR, false>(L, R);
307 }
308
309 // Helper for unary instructions (G_[ZSA]EXT/G_TRUNC) etc
310 template <typename SrcTy, unsigned Opcode> struct UnaryOp_match {
311 SrcTy L;
312
313 UnaryOp_match(const SrcTy &LHS) : L(LHS) {}
314 template <typename OpTy>
315 bool match(const MachineRegisterInfo &MRI, OpTy &&Op) {
316 MachineInstr *TmpMI;
317 if (mi_match(Op, MRI, m_MInstr(TmpMI))) {
318 if (TmpMI->getOpcode() == Opcode && TmpMI->getNumOperands() == 2) {
319 return L.match(MRI, TmpMI->getOperand(1).getReg());
320 }
321 }
322 return false;
323 }
324 };
325
326 template <typename SrcTy>
327 inline UnaryOp_match<SrcTy, TargetOpcode::G_ANYEXT>
328 m_GAnyExt(const SrcTy &Src) {
329 return UnaryOp_match<SrcTy, TargetOpcode::G_ANYEXT>(Src);
330 }
331
332 template <typename SrcTy>
333 inline UnaryOp_match<SrcTy, TargetOpcode::G_SEXT> m_GSExt(const SrcTy &Src) {
334 return UnaryOp_match<SrcTy, TargetOpcode::G_SEXT>(Src);
335 }
336
337 template <typename SrcTy>
338 inline UnaryOp_match<SrcTy, TargetOpcode::G_ZEXT> m_GZExt(const SrcTy &Src) {
339 return UnaryOp_match<SrcTy, TargetOpcode::G_ZEXT>(Src);
340 }
341
342 template <typename SrcTy>
343 inline UnaryOp_match<SrcTy, TargetOpcode::G_FPEXT> m_GFPExt(const SrcTy &Src) {
344 return UnaryOp_match<SrcTy, TargetOpcode::G_FPEXT>(Src);
345 }
346
347 template <typename SrcTy>
348 inline UnaryOp_match<SrcTy, TargetOpcode::G_TRUNC> m_GTrunc(const SrcTy &Src) {
349 return UnaryOp_match<SrcTy, TargetOpcode::G_TRUNC>(Src);
350 }
351
352 template <typename SrcTy>
353 inline UnaryOp_match<SrcTy, TargetOpcode::G_BITCAST>
354 m_GBitcast(const SrcTy &Src) {
355 return UnaryOp_match<SrcTy, TargetOpcode::G_BITCAST>(Src);
356 }
357
358 template <typename SrcTy>
359 inline UnaryOp_match<SrcTy, TargetOpcode::G_PTRTOINT>
360 m_GPtrToInt(const SrcTy &Src) {
361 return UnaryOp_match<SrcTy, TargetOpcode::G_PTRTOINT>(Src);
362 }
363
364 template <typename SrcTy>
365 inline UnaryOp_match<SrcTy, TargetOpcode::G_INTTOPTR>
366 m_GIntToPtr(const SrcTy &Src) {
367 return UnaryOp_match<SrcTy, TargetOpcode::G_INTTOPTR>(Src);
368 }
369
370 template <typename SrcTy>
371 inline UnaryOp_match<SrcTy, TargetOpcode::G_FPTRUNC>
372 m_GFPTrunc(const SrcTy &Src) {
373 return UnaryOp_match<SrcTy, TargetOpcode::G_FPTRUNC>(Src);
374 }
375
376 template <typename SrcTy>
377 inline UnaryOp_match<SrcTy, TargetOpcode::G_FABS> m_GFabs(const SrcTy &Src) {
378 return UnaryOp_match<SrcTy, TargetOpcode::G_FABS>(Src);
379 }
380
381 template <typename SrcTy>
382 inline UnaryOp_match<SrcTy, TargetOpcode::G_FNEG> m_GFNeg(const SrcTy &Src) {
383 return UnaryOp_match<SrcTy, TargetOpcode::G_FNEG>(Src);
384 }
385
386 template <typename SrcTy>
387 inline UnaryOp_match<SrcTy, TargetOpcode::COPY> m_Copy(SrcTy &&Src) {
388 return UnaryOp_match<SrcTy, TargetOpcode::COPY>(std::forward<SrcTy>(Src));
389 }
390
391 // General helper for generic MI compares, i.e. G_ICMP and G_FCMP
392 // TODO: Allow checking a specific predicate.
393 template <typename Pred_P, typename LHS_P, typename RHS_P, unsigned Opcode>
394 struct CompareOp_match {
395 Pred_P P;
396 LHS_P L;
397 RHS_P R;
398
399 CompareOp_match(const Pred_P &Pred, const LHS_P &LHS, const RHS_P &RHS)
400 : P(Pred), L(LHS), R(RHS) {}
401
402 template <typename OpTy>
403 bool match(const MachineRegisterInfo &MRI, OpTy &&Op) {
404 MachineInstr *TmpMI;
405 if (!mi_match(Op, MRI, m_MInstr(TmpMI)) || TmpMI->getOpcode() != Opcode)
406 return false;
407
408 auto TmpPred =
409 static_cast<CmpInst::Predicate>(TmpMI->getOperand(1).getPredicate());
410 if (!P.match(MRI, TmpPred))
411 return false;
412
413 return L.match(MRI, TmpMI->getOperand(2).getReg()) &&
414 R.match(MRI, TmpMI->getOperand(3).getReg());
415 }
416 };
417
418 template <typename Pred, typename LHS, typename RHS>
419 inline CompareOp_match<Pred, LHS, RHS, TargetOpcode::G_ICMP>
420 m_GICmp(const Pred &P, const LHS &L, const RHS &R) {
421 return CompareOp_match<Pred, LHS, RHS, TargetOpcode::G_ICMP>(P, L, R);
422 }
423
424 template <typename Pred, typename LHS, typename RHS>
425 inline CompareOp_match<Pred, LHS, RHS, TargetOpcode::G_FCMP>
426 m_GFCmp(const Pred &P, const LHS &L, const RHS &R) {
427 return CompareOp_match<Pred, LHS, RHS, TargetOpcode::G_FCMP>(P, L, R);
428 }
429
430 // Helper for checking if a Reg is of specific type.
431 struct CheckType {
432 LLT Ty;
433 CheckType(const LLT Ty) : Ty(Ty) {}
434
435 bool match(const MachineRegisterInfo &MRI, Register Reg) {
436 return MRI.getType(Reg) == Ty;
437 }
438 };
439
440 inline CheckType m_SpecificType(LLT Ty) { return Ty; }
441
442 template <typename Src0Ty, typename Src1Ty, typename Src2Ty, unsigned Opcode>
443 struct TernaryOp_match {
444 Src0Ty Src0;
445 Src1Ty Src1;
446 Src2Ty Src2;
447
448 TernaryOp_match(const Src0Ty &Src0, const Src1Ty &Src1, const Src2Ty &Src2)
449 : Src0(Src0), Src1(Src1), Src2(Src2) {}
450 template <typename OpTy>
451 bool match(const MachineRegisterInfo &MRI, OpTy &&Op) {
452 MachineInstr *TmpMI;
453 if (mi_match(Op, MRI, m_MInstr(TmpMI))) {
454 if (TmpMI->getOpcode() == Opcode && TmpMI->getNumOperands() == 4) {
455 return (Src0.match(MRI, TmpMI->getOperand(1).getReg()) &&
456 Src1.match(MRI, TmpMI->getOperand(2).getReg()) &&
457 Src2.match(MRI, TmpMI->getOperand(3).getReg()));
458 }
459 }
460 return false;
461 }
462 };
463 template <typename Src0Ty, typename Src1Ty, typename Src2Ty>
464 inline TernaryOp_match<Src0Ty, Src1Ty, Src2Ty,
465 TargetOpcode::G_INSERT_VECTOR_ELT>
466 m_GInsertVecElt(const Src0Ty &Src0, const Src1Ty &Src1, const Src2Ty &Src2) {
467 return TernaryOp_match<Src0Ty, Src1Ty, Src2Ty,
468 TargetOpcode::G_INSERT_VECTOR_ELT>(Src0, Src1, Src2);
469 }
470
471 /// Matches a register negated by a G_SUB.
472 /// G_SUB 0, %negated_reg
473 template <typename SrcTy>
474 inline BinaryOp_match<SpecificConstantMatch, SrcTy, TargetOpcode::G_SUB>
475 m_Neg(const SrcTy &&Src) {
476 return m_GSub(m_ZeroInt(), Src);
477 }
478
479 /// Matches a register not-ed by a G_XOR.
480 /// G_XOR %not_reg, -1
481 template <typename SrcTy>
482 inline BinaryOp_match<SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true>
483 m_Not(const SrcTy &&Src) {
484 return m_GXor(Src, m_AllOnesInt());
485 }
486
487 } // namespace GMIPatternMatch
488 } // namespace llvm
489
490 #endif
491