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