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