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>
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;
30   OneUse_match(const SubPatternT &SP) : SubPat(SP) {}
31 
32   bool match(const MachineRegisterInfo &MRI, Register Reg) {
33     return MRI.hasOneUse(Reg) && SubPat.match(MRI, Reg);
34   }
35 };
36 
37 template <typename SubPat>
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;
44   OneNonDBGUse_match(const SubPatternT &SP) : SubPat(SP) {}
45 
46   bool match(const MachineRegisterInfo &MRI, Register Reg) {
47     return MRI.hasOneNonDBGUse(Reg) && SubPat.match(MRI, Reg);
48   }
49 };
50 
51 template <typename SubPat>
52 inline OneNonDBGUse_match<SubPat> m_OneNonDBGUse(const SubPat &SP) {
53   return SP;
54 }
55 
56 struct ConstantMatch {
57   int64_t &CR;
58   ConstantMatch(int64_t &C) : CR(C) {}
59   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 
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;
73   SpecificConstantMatch(int64_t RequestedVal) : RequestedVal(RequestedVal) {}
74   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.
81 inline SpecificConstantMatch m_SpecificICst(int64_t RequestedValue) {
82   return SpecificConstantMatch(RequestedValue);
83 }
84 
85 ///{
86 /// Convenience matchers for specific integer values.
87 inline SpecificConstantMatch m_ZeroInt() { return SpecificConstantMatch(0); }
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 {
99   bool match(const MachineRegisterInfo &MRI, Register Reg) { return true; }
100   bool match(const MachineRegisterInfo &MRI, MachineOperand *MO) {
101     return MO->isReg();
102   }
103 };
104 
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>
110   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