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