450 lines · cpp
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-exception6//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("GICombineRule"))34 OS << "Parsing GICombineRule '" << Def.getName() << '\'';35 else if (Def.isSubClassOf(PatFrag::ClassName))36 OS << "Parsing " << PatFrag::ClassName << " '" << Def.getName() << '\'';37 else38 OS << "Parsing '" << Def.getName() << '\'';39 OS << '\n';40 }41};42} // namespace43 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(DiagLoc)->getName() != Operator) {49 PrintError(DiagLoc, "Expected " + Operator + " operator");50 return false;51 }52 53 if (List.getNumArgs() == 0) {54 PrintError(DiagLoc, Operator + " pattern list is empty");55 return false;56 }57 58 // The match section consists of a list of matchers and predicates. Parse each59 // 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(I);62 std::string Name = List.getArgName(I)63 ? List.getArgName(I)->getValue().str()64 : ("__" + AnonPatNamePrefix + "_" + Twine(I)).str();65 66 if (auto Pat = parseInstructionPattern(*Arg, Name)) {67 if (!ParseAction(std::move(Pat)))68 return false;69 continue;70 }71 72 if (auto Pat = parseWipMatchOpcodeMatcher(*Arg, Name)) {73 if (!ParseAction(std::move(Pat)))74 return false;75 continue;76 }77 78 // Parse arbitrary C++ code79 if (const auto *StringI = dyn_cast<StringInit>(Arg)) {80 auto CXXPat = std::make_unique<CXXPattern>(*StringI, insertStrRef(Name));81 if (!ParseAction(std::move(CXXPat)))82 return false;83 continue;84 }85 86 PrintError(DiagLoc,87 "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(RK.getDef(Opc));106}107 108std::unique_ptr<Pattern>109PatternParser::parseInstructionPattern(const Init &Arg, StringRef Name) {110 const DagInit *DagPat = dyn_cast<DagInit>(&Arg);111 if (!DagPat)112 return nullptr;113 114 std::unique_ptr<InstructionPattern> Pat;115 if (const DagInit *IP = getDagWithOperatorOfSubClass(Arg, "Instruction")) {116 const CodeGenInstruction &Instr =117 CGT.getInstruction(IP->getOperatorAsDef(DiagLoc));118 Pat =119 std::make_unique<CodeGenInstructionPattern>(Instr, insertStrRef(Name));120 } else if (const DagInit *IP =121 getDagWithOperatorOfSubClass(Arg, "Intrinsic")) {122 const Record *TheDef = IP->getOperatorAsDef(DiagLoc);123 const CodeGenIntrinsic *Intrin = &CGT.getIntrinsic(TheDef);124 const CodeGenInstruction &Instr = getInstrForIntrinsic(CGT, Intrin);125 Pat =126 std::make_unique<CodeGenInstructionPattern>(Instr, insertStrRef(Name));127 cast<CodeGenInstructionPattern>(*Pat).setIntrinsic(Intrin);128 } else if (const DagInit *PFP =129 getDagWithOperatorOfSubClass(Arg, PatFrag::ClassName)) {130 const Record *Def = PFP->getOperatorAsDef(DiagLoc);131 const PatFrag *PF = parsePatFrag(Def);132 if (!PF)133 return nullptr; // Already diagnosed by parsePatFrag134 Pat = std::make_unique<PatFragPattern>(*PF, insertStrRef(Name));135 } else if (const DagInit *BP =136 getDagWithOperatorOfSubClass(Arg, BuiltinPattern::ClassName)) {137 Pat = std::make_unique<BuiltinPattern>(*BP->getOperatorAsDef(DiagLoc),138 insertStrRef(Name));139 } else {140 return nullptr;141 }142 143 for (unsigned K = 0; K < DagPat->getNumArgs(); ++K) {144 const Init *Arg = DagPat->getArg(K);145 if (auto *DagArg = getDagWithSpecificOperator(*Arg, "MIFlags")) {146 if (!parseInstructionPatternMIFlags(*Pat, DagArg))147 return nullptr;148 continue;149 }150 151 if (!parseInstructionPatternOperand(*Pat, Arg, DagPat->getArgName(K)))152 return nullptr;153 }154 155 if (!Pat->checkSemantics(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(Arg, "wip_match_opcode");164 if (!Matcher)165 return nullptr;166 167 if (Matcher->getNumArgs() == 0) {168 PrintError(DiagLoc, "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>(insertStrRef(Name));174 for (const auto &Arg : Matcher->getArgs()) {175 const Record *OpcodeDef = getDefOfSubClass(*Arg, "Instruction");176 if (OpcodeDef) {177 Result->addOpcode(&CGT.getInstruction(OpcodeDef));178 continue;179 }180 181 PrintError(DiagLoc, "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(DiagLoc,193 "cannot parse operand '" + OpInit->getAsUnquotedString() + "' ");194 if (OpName)195 PrintNote(DiagLoc,196 "operand name is '" + OpName->getAsUnquotedString() + '\'');197 return false;198 };199 200 // untyped immediate, e.g. 0201 if (const auto *IntImm = dyn_cast<IntInit>(OpInit)) {202 std::string Name = OpName ? OpName->getAsUnquotedString() : "";203 IP.addOperand(IntImm->getValue(), insertStrRef(Name), PatternType());204 return true;205 }206 207 // typed immediate, e.g. (i32 0)208 if (const auto *DagOp = dyn_cast<DagInit>(OpInit)) {209 if (DagOp->getNumArgs() != 1)210 return ParseErr();211 212 const Record *TyDef = DagOp->getOperatorAsDef(DiagLoc);213 auto ImmTy = PatternType::get(DiagLoc, TyDef,214 "cannot parse immediate '" +215 DagOp->getAsUnquotedString() + '\'');216 if (!ImmTy)217 return false;218 219 if (!IP.hasAllDefs()) {220 PrintError(DiagLoc, "out operand of '" + IP.getInstName() +221 "' cannot be an immediate");222 return false;223 }224 225 const auto *Val = dyn_cast<IntInit>(DagOp->getArg(0));226 if (!Val)227 return ParseErr();228 229 std::string Name = OpName ? OpName->getAsUnquotedString() : "";230 IP.addOperand(Val->getValue(), insertStrRef(Name), *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>(OpInit)) {236 if (!OpName) {237 PrintError(DiagLoc, "expected an operand name after '" +238 OpInit->getAsString() + '\'');239 return false;240 }241 const Record *Def = DefI->getDef();242 auto Ty = PatternType::get(DiagLoc, Def, "cannot parse operand type");243 if (!Ty)244 return false;245 IP.addOperand(insertStrRef(OpName->getAsUnquotedString()), *Ty);246 return true;247 }248 249 // Untyped operand e.g. $x/$z in (G_FNEG $x, $z)250 if (isa<UnsetInit>(OpInit)) {251 assert(OpName && "Unset w/ no OpName?");252 IP.addOperand(insertStrRef(OpName->getAsUnquotedString()), 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>(&IP);262 if (!CGIP) {263 PrintError(DiagLoc,264 "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(MIFlagsEnumClassName)) {271 PrintError(DiagLoc, "'" + 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(DiagLoc, "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(K);287 288 // Match/set a flag: (MIFlags FmNoNans)289 if (const auto *Def = dyn_cast<DefInit>(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(*Arg, "not")) {300 for (const Init *NotArg : NotDag->getArgs()) {301 const DefInit *DefArg = dyn_cast<DefInit>(NotArg);302 if (!DefArg) {303 PrintError(DiagLoc, "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>(Arg)) {321 FI.addCopyFlag(insertStrRef(Op->getArgName(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(PatFrag::ClassName))332 return nullptr;333 334 const DagInit *Ins = Def->getValueAsDag("InOperands");335 if (Ins->getOperatorAsDef(Def->getLoc())->getName() != "ins") {336 PrintError(Def, "expected 'ins' operator for " + PatFrag::ClassName +337 " in operands list");338 return nullptr;339 }340 341 const DagInit *Outs = Def->getValueAsDag("OutOperands");342 if (Outs->getOperatorAsDef(Def->getLoc())->getName() != "outs") {343 PrintError(Def, "expected 'outs' operator for " + PatFrag::ClassName +344 " out operands list");345 return nullptr;346 }347 348 auto Result = std::make_unique<PatFrag>(*Def);349 if (!parsePatFragParamList(*Outs, [&](StringRef Name, unsigned Kind) {350 Result->addOutParam(insertStrRef(Name), (PatFrag::ParamKind)Kind);351 return true;352 }))353 return nullptr;354 355 if (!parsePatFragParamList(*Ins, [&](StringRef Name, unsigned Kind) {356 Result->addInParam(insertStrRef(Name), (PatFrag::ParamKind)Kind);357 return true;358 }))359 return nullptr;360 361 const ListInit *Alts = Def->getValueAsListInit("Alternatives");362 unsigned AltIdx = 0;363 for (const Init *Alt : *Alts) {364 const auto *PatDag = dyn_cast<DagInit>(Alt);365 if (!PatDag) {366 PrintError(Def, "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(std::move(Pat));373 return true;374 };375 376 SaveAndRestore<ArrayRef<SMLoc>> DiagLocSAR(DiagLoc, Def->getLoc());377 if (!parsePatternList(378 *PatDag, AddPat, "pattern",379 /*AnonPatPrefix*/380 (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(K);395 const Init *Ty = OpsList.getArg(K);396 397 if (!Name) {398 PrintError(DiagLoc, "all operands must be named'");399 return false;400 }401 const std::string NameStr = Name->getAsUnquotedString();402 403 PatFrag::ParamKind OpKind;404 if (isSpecificDef(*Ty, "gi_imm"))405 OpKind = PatFrag::PK_Imm;406 else if (isSpecificDef(*Ty, "root"))407 OpKind = PatFrag::PK_Root;408 else if (isa<UnsetInit>(Ty) ||409 isSpecificDef(*Ty, "gi_mo")) // no type = gi_mo.410 OpKind = PatFrag::PK_MachineOperand;411 else {412 PrintError(413 DiagLoc,414 '\'' + 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(Def);431 if (It != ParsedPatFrags.end()) {432 SeenPatFrags.insert(It->second.get());433 return It->second.get();434 }435 436 std::unique_ptr<PatFrag> NewPatFrag = parsePatFragImpl(Def);437 if (!NewPatFrag) {438 PrintError(Def, "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(Res);448 return Res;449}450