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