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