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 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 static 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>(R, std::vector<Record *>()); 116 return Ptr.get(); 117 } 118 119 std::unique_ptr<Pattern> 120 PatternParser::parseInstructionPattern(const Init &Arg, StringRef Name) { 121 const DagInit *DagPat = dyn_cast<DagInit>(&Arg); 122 if (!DagPat) 123 return nullptr; 124 125 std::unique_ptr<InstructionPattern> Pat; 126 if (const DagInit *IP = getDagWithOperatorOfSubClass(Arg, "Instruction")) { 127 auto &Instr = CGT.getInstruction(IP->getOperatorAsDef(DiagLoc)); 128 Pat = 129 std::make_unique<CodeGenInstructionPattern>(Instr, insertStrRef(Name)); 130 } else if (const DagInit *IP = 131 getDagWithOperatorOfSubClass(Arg, "Intrinsic")) { 132 Record *TheDef = IP->getOperatorAsDef(DiagLoc); 133 const CodeGenIntrinsic *Intrin = getCodeGenIntrinsic(TheDef); 134 const CodeGenInstruction &Instr = getInstrForIntrinsic(CGT, Intrin); 135 Pat = 136 std::make_unique<CodeGenInstructionPattern>(Instr, insertStrRef(Name)); 137 cast<CodeGenInstructionPattern>(*Pat).setIntrinsic(Intrin); 138 } else if (const DagInit *PFP = 139 getDagWithOperatorOfSubClass(Arg, PatFrag::ClassName)) { 140 const Record *Def = PFP->getOperatorAsDef(DiagLoc); 141 const PatFrag *PF = parsePatFrag(Def); 142 if (!PF) 143 return nullptr; // Already diagnosed by parsePatFrag 144 Pat = std::make_unique<PatFragPattern>(*PF, insertStrRef(Name)); 145 } else if (const DagInit *BP = 146 getDagWithOperatorOfSubClass(Arg, BuiltinPattern::ClassName)) { 147 Pat = std::make_unique<BuiltinPattern>(*BP->getOperatorAsDef(DiagLoc), 148 insertStrRef(Name)); 149 } else 150 return nullptr; 151 152 for (unsigned K = 0; K < DagPat->getNumArgs(); ++K) { 153 Init *Arg = DagPat->getArg(K); 154 if (auto *DagArg = getDagWithSpecificOperator(*Arg, "MIFlags")) { 155 if (!parseInstructionPatternMIFlags(*Pat, DagArg)) 156 return nullptr; 157 continue; 158 } 159 160 if (!parseInstructionPatternOperand(*Pat, Arg, DagPat->getArgName(K))) 161 return nullptr; 162 } 163 164 if (!Pat->checkSemantics(DiagLoc)) 165 return nullptr; 166 167 return std::move(Pat); 168 } 169 170 std::unique_ptr<Pattern> 171 PatternParser::parseWipMatchOpcodeMatcher(const Init &Arg, StringRef Name) { 172 const DagInit *Matcher = getDagWithSpecificOperator(Arg, "wip_match_opcode"); 173 if (!Matcher) 174 return nullptr; 175 176 if (Matcher->getNumArgs() == 0) { 177 PrintError(DiagLoc, "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>(insertStrRef(Name)); 183 for (const auto &Arg : Matcher->getArgs()) { 184 Record *OpcodeDef = getDefOfSubClass(*Arg, "Instruction"); 185 if (OpcodeDef) { 186 Result->addOpcode(&CGT.getInstruction(OpcodeDef)); 187 continue; 188 } 189 190 PrintError(DiagLoc, "Arguments to wip_match_opcode must be instructions"); 191 return nullptr; 192 } 193 194 return std::move(Result); 195 } 196 197 bool PatternParser::parseInstructionPatternOperand(InstructionPattern &IP, 198 const Init *OpInit, 199 const StringInit *OpName) { 200 const auto ParseErr = [&]() { 201 PrintError(DiagLoc, 202 "cannot parse operand '" + OpInit->getAsUnquotedString() + "' "); 203 if (OpName) 204 PrintNote(DiagLoc, 205 "operand name is '" + OpName->getAsUnquotedString() + '\''); 206 return false; 207 }; 208 209 // untyped immediate, e.g. 0 210 if (const auto *IntImm = dyn_cast<IntInit>(OpInit)) { 211 std::string Name = OpName ? OpName->getAsUnquotedString() : ""; 212 IP.addOperand(IntImm->getValue(), insertStrRef(Name), PatternType()); 213 return true; 214 } 215 216 // typed immediate, e.g. (i32 0) 217 if (const auto *DagOp = dyn_cast<DagInit>(OpInit)) { 218 if (DagOp->getNumArgs() != 1) 219 return ParseErr(); 220 221 const Record *TyDef = DagOp->getOperatorAsDef(DiagLoc); 222 auto ImmTy = PatternType::get(DiagLoc, TyDef, 223 "cannot parse immediate '" + 224 DagOp->getAsUnquotedString() + '\''); 225 if (!ImmTy) 226 return false; 227 228 if (!IP.hasAllDefs()) { 229 PrintError(DiagLoc, "out operand of '" + IP.getInstName() + 230 "' cannot be an immediate"); 231 return false; 232 } 233 234 const auto *Val = dyn_cast<IntInit>(DagOp->getArg(0)); 235 if (!Val) 236 return ParseErr(); 237 238 std::string Name = OpName ? OpName->getAsUnquotedString() : ""; 239 IP.addOperand(Val->getValue(), insertStrRef(Name), *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>(OpInit)) { 245 if (!OpName) { 246 PrintError(DiagLoc, "expected an operand name after '" + 247 OpInit->getAsString() + '\''); 248 return false; 249 } 250 const Record *Def = DefI->getDef(); 251 auto Ty = PatternType::get(DiagLoc, Def, "cannot parse operand type"); 252 if (!Ty) 253 return false; 254 IP.addOperand(insertStrRef(OpName->getAsUnquotedString()), *Ty); 255 return true; 256 } 257 258 // Untyped operand e.g. $x/$z in (G_FNEG $x, $z) 259 if (isa<UnsetInit>(OpInit)) { 260 assert(OpName && "Unset w/ no OpName?"); 261 IP.addOperand(insertStrRef(OpName->getAsUnquotedString()), PatternType()); 262 return true; 263 } 264 265 return ParseErr(); 266 } 267 268 bool PatternParser::parseInstructionPatternMIFlags(InstructionPattern &IP, 269 const DagInit *Op) { 270 auto *CGIP = dyn_cast<CodeGenInstructionPattern>(&IP); 271 if (!CGIP) { 272 PrintError(DiagLoc, 273 "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(MIFlagsEnumClassName)) { 280 PrintError(DiagLoc, "'" + 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(DiagLoc, "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(K); 296 297 // Match/set a flag: (MIFlags FmNoNans) 298 if (const auto *Def = dyn_cast<DefInit>(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(*Arg, "not")) { 309 for (const Init *NotArg : NotDag->getArgs()) { 310 const DefInit *DefArg = dyn_cast<DefInit>(NotArg); 311 if (!DefArg) { 312 PrintError(DiagLoc, "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>(Arg)) { 331 FI.addCopyFlag(insertStrRef(Op->getArgName(K)->getAsUnquotedString())); 332 continue; 333 } 334 } 335 336 return true; 337 } 338 339 std::unique_ptr<PatFrag> PatternParser::parsePatFragImpl(const Record *Def) { 340 auto StackTrace = PrettyStackTraceParse(*Def); 341 if (!Def->isSubClassOf(PatFrag::ClassName)) 342 return nullptr; 343 344 const DagInit *Ins = Def->getValueAsDag("InOperands"); 345 if (Ins->getOperatorAsDef(Def->getLoc())->getName() != "ins") { 346 PrintError(Def, "expected 'ins' operator for " + PatFrag::ClassName + 347 " in operands list"); 348 return nullptr; 349 } 350 351 const DagInit *Outs = Def->getValueAsDag("OutOperands"); 352 if (Outs->getOperatorAsDef(Def->getLoc())->getName() != "outs") { 353 PrintError(Def, "expected 'outs' operator for " + PatFrag::ClassName + 354 " out operands list"); 355 return nullptr; 356 } 357 358 auto Result = std::make_unique<PatFrag>(*Def); 359 if (!parsePatFragParamList(*Outs, [&](StringRef Name, unsigned Kind) { 360 Result->addOutParam(insertStrRef(Name), (PatFrag::ParamKind)Kind); 361 return true; 362 })) 363 return nullptr; 364 365 if (!parsePatFragParamList(*Ins, [&](StringRef Name, unsigned Kind) { 366 Result->addInParam(insertStrRef(Name), (PatFrag::ParamKind)Kind); 367 return true; 368 })) 369 return nullptr; 370 371 const ListInit *Alts = Def->getValueAsListInit("Alternatives"); 372 unsigned AltIdx = 0; 373 for (const Init *Alt : *Alts) { 374 const auto *PatDag = dyn_cast<DagInit>(Alt); 375 if (!PatDag) { 376 PrintError(Def, "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(std::move(Pat)); 383 return true; 384 }; 385 386 SaveAndRestore<ArrayRef<SMLoc>> DiagLocSAR(DiagLoc, Def->getLoc()); 387 if (!parsePatternList( 388 *PatDag, AddPat, "pattern", 389 /*AnonPatPrefix*/ 390 (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 400 bool 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(K); 405 const Init *Ty = OpsList.getArg(K); 406 407 if (!Name) { 408 PrintError(DiagLoc, "all operands must be named'"); 409 return false; 410 } 411 const std::string NameStr = Name->getAsUnquotedString(); 412 413 PatFrag::ParamKind OpKind; 414 if (isSpecificDef(*Ty, "gi_imm")) 415 OpKind = PatFrag::PK_Imm; 416 else if (isSpecificDef(*Ty, "root")) 417 OpKind = PatFrag::PK_Root; 418 else if (isa<UnsetInit>(Ty) || 419 isSpecificDef(*Ty, "gi_mo")) // no type = gi_mo. 420 OpKind = PatFrag::PK_MachineOperand; 421 else { 422 PrintError( 423 DiagLoc, 424 '\'' + 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 436 const 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(Def); 441 if (It != ParsedPatFrags.end()) { 442 SeenPatFrags.insert(It->second.get()); 443 return It->second.get(); 444 } 445 446 std::unique_ptr<PatFrag> NewPatFrag = parsePatFragImpl(Def); 447 if (!NewPatFrag) { 448 PrintError(Def, "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(Res); 458 return Res; 459 } 460 461 } // namespace gi 462 } // namespace llvm 463