1//===- PatternParser.cpp ----------------------------------------*- 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#include "Common/GlobalISel/PatternParser.h"
10#include "Basic/CodeGenIntrinsics.h"
11#include "Common/CodeGenTarget.h"
12#include "Common/GlobalISel/CombinerUtils.h"
13#include "Common/GlobalISel/Patterns.h"
14#include "llvm/ADT/StringRef.h"
15#include "llvm/Support/PrettyStackTrace.h"
16#include "llvm/Support/SaveAndRestore.h"
17#include "llvm/TableGen/Error.h"
18#include "llvm/TableGen/Record.h"
19
20namespace llvm {
21namespace gi {
22static constexpr StringLiteral MIFlagsEnumClassName = "MIFlagEnum";
23
24namespace {
25class PrettyStackTraceParse : public PrettyStackTraceEntry {
26 const Record &Def;
27
28public:
29 PrettyStackTraceParse(const Record &Def) : Def(Def) {}
30
31 void print(raw_ostream &OS) const override {
32 if (Def.isSubClassOf(Name: "GICombineRule"))
33 OS << "Parsing GICombineRule '" << Def.getName() << '\'';
34 else if (Def.isSubClassOf(Name: PatFrag::ClassName))
35 OS << "Parsing " << PatFrag::ClassName << " '" << Def.getName() << '\'';
36 else
37 OS << "Parsing '" << Def.getName() << '\'';
38 OS << '\n';
39 }
40};
41} // namespace
42
43bool PatternParser::parsePatternList(
44 const DagInit &List,
45 function_ref<bool(std::unique_ptr<Pattern>)> ParseAction,
46 StringRef Operator, StringRef AnonPatNamePrefix) {
47 if (List.getOperatorAsDef(Loc: DiagLoc)->getName() != Operator) {
48 PrintError(ErrorLoc: DiagLoc, Msg: "Expected " + Operator + " operator");
49 return false;
50 }
51
52 if (List.getNumArgs() == 0) {
53 PrintError(ErrorLoc: DiagLoc, Msg: Operator + " pattern list is empty");
54 return false;
55 }
56
57 // The match section consists of a list of matchers and predicates. Parse each
58 // one and add the equivalent GIMatchDag nodes, predicates, and edges.
59 for (unsigned I = 0; I < List.getNumArgs(); ++I) {
60 Init *Arg = List.getArg(Num: I);
61 std::string Name = List.getArgName(Num: I)
62 ? List.getArgName(Num: I)->getValue().str()
63 : ("__" + AnonPatNamePrefix + "_" + Twine(I)).str();
64
65 if (auto Pat = parseInstructionPattern(Arg: *Arg, PatName: Name)) {
66 if (!ParseAction(std::move(Pat)))
67 return false;
68 continue;
69 }
70
71 if (auto Pat = parseWipMatchOpcodeMatcher(Arg: *Arg, PatName: Name)) {
72 if (!ParseAction(std::move(Pat)))
73 return false;
74 continue;
75 }
76
77 // Parse arbitrary C++ code
78 if (const auto *StringI = dyn_cast<StringInit>(Val: Arg)) {
79 auto CXXPat = std::make_unique<CXXPattern>(args: *StringI, args: insertStrRef(S: Name));
80 if (!ParseAction(std::move(CXXPat)))
81 return false;
82 continue;
83 }
84
85 PrintError(ErrorLoc: DiagLoc,
86 Msg: "Failed to parse pattern: '" + Arg->getAsString() + '\'');
87 return false;
88 }
89
90 return true;
91}
92
93static const CodeGenInstruction &
94getInstrForIntrinsic(const CodeGenTarget &CGT, const CodeGenIntrinsic *I) {
95 StringRef Opc;
96 if (I->isConvergent) {
97 Opc = I->hasSideEffects ? "G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS"
98 : "G_INTRINSIC_CONVERGENT";
99 } else {
100 Opc = I->hasSideEffects ? "G_INTRINSIC_W_SIDE_EFFECTS" : "G_INTRINSIC";
101 }
102
103 RecordKeeper &RK = I->TheDef->getRecords();
104 return CGT.getInstruction(InstRec: RK.getDef(Name: Opc));
105}
106
107static const CodeGenIntrinsic *getCodeGenIntrinsic(Record *R) {
108 // Intrinsics need to have a static lifetime because the match table keeps
109 // references to CodeGenIntrinsic objects.
110 static DenseMap<const Record *, std::unique_ptr<CodeGenIntrinsic>>
111 AllIntrinsics;
112
113 auto &Ptr = AllIntrinsics[R];
114 if (!Ptr)
115 Ptr = std::make_unique<CodeGenIntrinsic>(args&: R, args: std::vector<Record *>());
116 return Ptr.get();
117}
118
119std::unique_ptr<Pattern>
120PatternParser::parseInstructionPattern(const Init &Arg, StringRef Name) {
121 const DagInit *DagPat = dyn_cast<DagInit>(Val: &Arg);
122 if (!DagPat)
123 return nullptr;
124
125 std::unique_ptr<InstructionPattern> Pat;
126 if (const DagInit *IP = getDagWithOperatorOfSubClass(N: Arg, Cls: "Instruction")) {
127 auto &Instr = CGT.getInstruction(InstRec: IP->getOperatorAsDef(Loc: DiagLoc));
128 Pat =
129 std::make_unique<CodeGenInstructionPattern>(args&: Instr, args: insertStrRef(S: Name));
130 } else if (const DagInit *IP =
131 getDagWithOperatorOfSubClass(N: Arg, Cls: "Intrinsic")) {
132 Record *TheDef = IP->getOperatorAsDef(Loc: DiagLoc);
133 const CodeGenIntrinsic *Intrin = getCodeGenIntrinsic(R: TheDef);
134 const CodeGenInstruction &Instr = getInstrForIntrinsic(CGT, I: Intrin);
135 Pat =
136 std::make_unique<CodeGenInstructionPattern>(args: Instr, args: insertStrRef(S: Name));
137 cast<CodeGenInstructionPattern>(Val&: *Pat).setIntrinsic(Intrin);
138 } else if (const DagInit *PFP =
139 getDagWithOperatorOfSubClass(N: Arg, Cls: PatFrag::ClassName)) {
140 const Record *Def = PFP->getOperatorAsDef(Loc: DiagLoc);
141 const PatFrag *PF = parsePatFrag(Def);
142 if (!PF)
143 return nullptr; // Already diagnosed by parsePatFrag
144 Pat = std::make_unique<PatFragPattern>(args: *PF, args: insertStrRef(S: Name));
145 } else if (const DagInit *BP =
146 getDagWithOperatorOfSubClass(N: Arg, Cls: BuiltinPattern::ClassName)) {
147 Pat = std::make_unique<BuiltinPattern>(args&: *BP->getOperatorAsDef(Loc: DiagLoc),
148 args: insertStrRef(S: Name));
149 } else
150 return nullptr;
151
152 for (unsigned K = 0; K < DagPat->getNumArgs(); ++K) {
153 Init *Arg = DagPat->getArg(Num: K);
154 if (auto *DagArg = getDagWithSpecificOperator(N: *Arg, Name: "MIFlags")) {
155 if (!parseInstructionPatternMIFlags(IP&: *Pat, Op: DagArg))
156 return nullptr;
157 continue;
158 }
159
160 if (!parseInstructionPatternOperand(IP&: *Pat, OpInit: Arg, OpName: DagPat->getArgName(Num: K)))
161 return nullptr;
162 }
163
164 if (!Pat->checkSemantics(Loc: DiagLoc))
165 return nullptr;
166
167 return std::move(Pat);
168}
169
170std::unique_ptr<Pattern>
171PatternParser::parseWipMatchOpcodeMatcher(const Init &Arg, StringRef Name) {
172 const DagInit *Matcher = getDagWithSpecificOperator(N: Arg, Name: "wip_match_opcode");
173 if (!Matcher)
174 return nullptr;
175
176 if (Matcher->getNumArgs() == 0) {
177 PrintError(ErrorLoc: DiagLoc, Msg: "Empty wip_match_opcode");
178 return nullptr;
179 }
180
181 // Each argument is an opcode that can match.
182 auto Result = std::make_unique<AnyOpcodePattern>(args: insertStrRef(S: Name));
183 for (const auto &Arg : Matcher->getArgs()) {
184 Record *OpcodeDef = getDefOfSubClass(N: *Arg, Cls: "Instruction");
185 if (OpcodeDef) {
186 Result->addOpcode(I: &CGT.getInstruction(InstRec: OpcodeDef));
187 continue;
188 }
189
190 PrintError(ErrorLoc: DiagLoc, Msg: "Arguments to wip_match_opcode must be instructions");
191 return nullptr;
192 }
193
194 return std::move(Result);
195}
196
197bool PatternParser::parseInstructionPatternOperand(InstructionPattern &IP,
198 const Init *OpInit,
199 const StringInit *OpName) {
200 const auto ParseErr = [&]() {
201 PrintError(ErrorLoc: DiagLoc,
202 Msg: "cannot parse operand '" + OpInit->getAsUnquotedString() + "' ");
203 if (OpName)
204 PrintNote(NoteLoc: DiagLoc,
205 Msg: "operand name is '" + OpName->getAsUnquotedString() + '\'');
206 return false;
207 };
208
209 // untyped immediate, e.g. 0
210 if (const auto *IntImm = dyn_cast<IntInit>(Val: OpInit)) {
211 std::string Name = OpName ? OpName->getAsUnquotedString() : "";
212 IP.addOperand(Init: IntImm->getValue(), Init: insertStrRef(S: Name), Init: PatternType());
213 return true;
214 }
215
216 // typed immediate, e.g. (i32 0)
217 if (const auto *DagOp = dyn_cast<DagInit>(Val: OpInit)) {
218 if (DagOp->getNumArgs() != 1)
219 return ParseErr();
220
221 const Record *TyDef = DagOp->getOperatorAsDef(Loc: DiagLoc);
222 auto ImmTy = PatternType::get(DiagLoc, R: TyDef,
223 DiagCtx: "cannot parse immediate '" +
224 DagOp->getAsUnquotedString() + '\'');
225 if (!ImmTy)
226 return false;
227
228 if (!IP.hasAllDefs()) {
229 PrintError(ErrorLoc: DiagLoc, Msg: "out operand of '" + IP.getInstName() +
230 "' cannot be an immediate");
231 return false;
232 }
233
234 const auto *Val = dyn_cast<IntInit>(Val: DagOp->getArg(Num: 0));
235 if (!Val)
236 return ParseErr();
237
238 std::string Name = OpName ? OpName->getAsUnquotedString() : "";
239 IP.addOperand(Init: Val->getValue(), Init: insertStrRef(S: Name), Init&: *ImmTy);
240 return true;
241 }
242
243 // Typed operand e.g. $x/$z in (G_FNEG $x, $z)
244 if (auto *DefI = dyn_cast<DefInit>(Val: OpInit)) {
245 if (!OpName) {
246 PrintError(ErrorLoc: DiagLoc, Msg: "expected an operand name after '" +
247 OpInit->getAsString() + '\'');
248 return false;
249 }
250 const Record *Def = DefI->getDef();
251 auto Ty = PatternType::get(DiagLoc, R: Def, DiagCtx: "cannot parse operand type");
252 if (!Ty)
253 return false;
254 IP.addOperand(Init: insertStrRef(S: OpName->getAsUnquotedString()), Init&: *Ty);
255 return true;
256 }
257
258 // Untyped operand e.g. $x/$z in (G_FNEG $x, $z)
259 if (isa<UnsetInit>(Val: OpInit)) {
260 assert(OpName && "Unset w/ no OpName?");
261 IP.addOperand(Init: insertStrRef(S: OpName->getAsUnquotedString()), Init: PatternType());
262 return true;
263 }
264
265 return ParseErr();
266}
267
268bool PatternParser::parseInstructionPatternMIFlags(InstructionPattern &IP,
269 const DagInit *Op) {
270 auto *CGIP = dyn_cast<CodeGenInstructionPattern>(Val: &IP);
271 if (!CGIP) {
272 PrintError(ErrorLoc: DiagLoc,
273 Msg: "matching/writing MIFlags is only allowed on CodeGenInstruction "
274 "patterns");
275 return false;
276 }
277
278 const auto CheckFlagEnum = [&](const Record *R) {
279 if (!R->isSubClassOf(Name: MIFlagsEnumClassName)) {
280 PrintError(ErrorLoc: DiagLoc, Msg: "'" + R->getName() + "' is not a subclass of '" +
281 MIFlagsEnumClassName + "'");
282 return false;
283 }
284
285 return true;
286 };
287
288 if (CGIP->getMIFlagsInfo()) {
289 PrintError(ErrorLoc: DiagLoc, Msg: "MIFlags can only be present once on an instruction");
290 return false;
291 }
292
293 auto &FI = CGIP->getOrCreateMIFlagsInfo();
294 for (unsigned K = 0; K < Op->getNumArgs(); ++K) {
295 const Init *Arg = Op->getArg(Num: K);
296
297 // Match/set a flag: (MIFlags FmNoNans)
298 if (const auto *Def = dyn_cast<DefInit>(Val: Arg)) {
299 const Record *R = Def->getDef();
300 if (!CheckFlagEnum(R))
301 return false;
302
303 FI.addSetFlag(R);
304 continue;
305 }
306
307 // Do not match a flag/unset a flag: (MIFlags (not FmNoNans))
308 if (const DagInit *NotDag = getDagWithSpecificOperator(N: *Arg, Name: "not")) {
309 for (const Init *NotArg : NotDag->getArgs()) {
310 const DefInit *DefArg = dyn_cast<DefInit>(Val: NotArg);
311 if (!DefArg) {
312 PrintError(ErrorLoc: DiagLoc, Msg: "cannot parse '" + NotArg->getAsUnquotedString() +
313 "': expected a '" + MIFlagsEnumClassName +
314 "'");
315 return false;
316 }
317
318 const Record *R = DefArg->getDef();
319 if (!CheckFlagEnum(R))
320 return false;
321
322 FI.addUnsetFlag(R);
323 continue;
324 }
325
326 continue;
327 }
328
329 // Copy flags from a matched instruction: (MIFlags $mi)
330 if (isa<UnsetInit>(Val: Arg)) {
331 FI.addCopyFlag(InstName: insertStrRef(S: Op->getArgName(Num: K)->getAsUnquotedString()));
332 continue;
333 }
334 }
335
336 return true;
337}
338
339std::unique_ptr<PatFrag> PatternParser::parsePatFragImpl(const Record *Def) {
340 auto StackTrace = PrettyStackTraceParse(*Def);
341 if (!Def->isSubClassOf(Name: PatFrag::ClassName))
342 return nullptr;
343
344 const DagInit *Ins = Def->getValueAsDag(FieldName: "InOperands");
345 if (Ins->getOperatorAsDef(Loc: Def->getLoc())->getName() != "ins") {
346 PrintError(Rec: Def, Msg: "expected 'ins' operator for " + PatFrag::ClassName +
347 " in operands list");
348 return nullptr;
349 }
350
351 const DagInit *Outs = Def->getValueAsDag(FieldName: "OutOperands");
352 if (Outs->getOperatorAsDef(Loc: Def->getLoc())->getName() != "outs") {
353 PrintError(Rec: Def, Msg: "expected 'outs' operator for " + PatFrag::ClassName +
354 " out operands list");
355 return nullptr;
356 }
357
358 auto Result = std::make_unique<PatFrag>(args: *Def);
359 if (!parsePatFragParamList(OpsList: *Outs, ParseAction: [&](StringRef Name, unsigned Kind) {
360 Result->addOutParam(Name: insertStrRef(S: Name), Kind: (PatFrag::ParamKind)Kind);
361 return true;
362 }))
363 return nullptr;
364
365 if (!parsePatFragParamList(OpsList: *Ins, ParseAction: [&](StringRef Name, unsigned Kind) {
366 Result->addInParam(Name: insertStrRef(S: Name), Kind: (PatFrag::ParamKind)Kind);
367 return true;
368 }))
369 return nullptr;
370
371 const ListInit *Alts = Def->getValueAsListInit(FieldName: "Alternatives");
372 unsigned AltIdx = 0;
373 for (const Init *Alt : *Alts) {
374 const auto *PatDag = dyn_cast<DagInit>(Val: Alt);
375 if (!PatDag) {
376 PrintError(Rec: Def, Msg: "expected dag init for PatFrag pattern alternative");
377 return nullptr;
378 }
379
380 PatFrag::Alternative &A = Result->addAlternative();
381 const auto AddPat = [&](std::unique_ptr<Pattern> Pat) {
382 A.Pats.push_back(Elt: std::move(Pat));
383 return true;
384 };
385
386 SaveAndRestore<ArrayRef<SMLoc>> DiagLocSAR(DiagLoc, Def->getLoc());
387 if (!parsePatternList(
388 List: *PatDag, ParseAction: AddPat, Operator: "pattern",
389 /*AnonPatPrefix*/
390 AnonPatNamePrefix: (Def->getName() + "_alt" + Twine(AltIdx++) + "_pattern").str()))
391 return nullptr;
392 }
393
394 if (!Result->buildOperandsTables() || !Result->checkSemantics())
395 return nullptr;
396
397 return Result;
398}
399
400bool PatternParser::parsePatFragParamList(
401 const DagInit &OpsList,
402 function_ref<bool(StringRef, unsigned)> ParseAction) {
403 for (unsigned K = 0; K < OpsList.getNumArgs(); ++K) {
404 const StringInit *Name = OpsList.getArgName(Num: K);
405 const Init *Ty = OpsList.getArg(Num: K);
406
407 if (!Name) {
408 PrintError(ErrorLoc: DiagLoc, Msg: "all operands must be named'");
409 return false;
410 }
411 const std::string NameStr = Name->getAsUnquotedString();
412
413 PatFrag::ParamKind OpKind;
414 if (isSpecificDef(N: *Ty, Def: "gi_imm"))
415 OpKind = PatFrag::PK_Imm;
416 else if (isSpecificDef(N: *Ty, Def: "root"))
417 OpKind = PatFrag::PK_Root;
418 else if (isa<UnsetInit>(Val: Ty) ||
419 isSpecificDef(N: *Ty, Def: "gi_mo")) // no type = gi_mo.
420 OpKind = PatFrag::PK_MachineOperand;
421 else {
422 PrintError(
423 ErrorLoc: DiagLoc,
424 Msg: '\'' + NameStr +
425 "' operand type was expected to be 'root', 'gi_imm' or 'gi_mo'");
426 return false;
427 }
428
429 if (!ParseAction(NameStr, (unsigned)OpKind))
430 return false;
431 }
432
433 return true;
434}
435
436const PatFrag *PatternParser::parsePatFrag(const Record *Def) {
437 // Cache already parsed PatFrags to avoid doing extra work.
438 static DenseMap<const Record *, std::unique_ptr<PatFrag>> ParsedPatFrags;
439
440 auto It = ParsedPatFrags.find(Val: Def);
441 if (It != ParsedPatFrags.end()) {
442 SeenPatFrags.insert(Ptr: It->second.get());
443 return It->second.get();
444 }
445
446 std::unique_ptr<PatFrag> NewPatFrag = parsePatFragImpl(Def);
447 if (!NewPatFrag) {
448 PrintError(Rec: Def, Msg: "Could not parse " + PatFrag::ClassName + " '" +
449 Def->getName() + "'");
450 // Put a nullptr in the map so we don't attempt parsing this again.
451 ParsedPatFrags[Def] = nullptr;
452 return nullptr;
453 }
454
455 const auto *Res = NewPatFrag.get();
456 ParsedPatFrags[Def] = std::move(NewPatFrag);
457 SeenPatFrags.insert(Ptr: Res);
458 return Res;
459}
460
461} // namespace gi
462} // namespace llvm
463