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: 29 PrettyStackTraceParse(const Record &Def) : Def(Def) {} 30 31 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 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 & 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> 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> 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 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 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 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 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 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