llvm/utils/TableGen/Common/GlobalISel/Patterns.cpp

   1 //===- Patterns.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 "Patterns.h"
  10 #include "Basic/CodeGenIntrinsics.h"
  11 #include "CXXPredicates.h"
  12 #include "CodeExpander.h"
  13 #include "CodeExpansions.h"
  14 #include "Common/CodeGenInstruction.h"
  15 #include "llvm/ADT/StringSet.h"
  16 #include "llvm/Support/Debug.h"
  17 #include "llvm/Support/raw_ostream.h"
  18 #include "llvm/TableGen/Error.h"
  19 #include "llvm/TableGen/Record.h"
  20
  21 namespace llvm {
  22 namespace gi {
  23
  24 //===- PatternType --------------------------------------------------------===//
  25
  26 std::optional<PatternType> PatternType::get(ArrayRef<SMLoc> DiagLoc,
  27                                             const Record *R, Twine DiagCtx) {
  28   assert(R);
  29   if (R->isSubClassOf("ValueType")) {
  30     PatternType PT(PT_ValueType);
  31     PT.Data.Def = R;
  32     return PT;
  33   }
  34
  35   if (R->isSubClassOf(TypeOfClassName)) {
  36     auto RawOpName = R->getValueAsString("OpName");
  37     if (!RawOpName.starts_with("$")) {
  38       PrintError(DiagLoc, DiagCtx + ": invalid operand name format '" +
  39                               RawOpName + "' in " + TypeOfClassName +
  40                               ": expected '$' followed by an operand name");
  41       return std::nullopt;
  42     }
  43
  44     PatternType PT(PT_TypeOf);
  45     PT.Data.Str = RawOpName.drop_front(1);
  46     return PT;
  47   }
  48
  49   if (R->isSubClassOf(VariadicClassName)) {
  50     const int64_t Min = R->getValueAsInt("MinArgs");
  51     const int64_t Max = R->getValueAsInt("MaxArgs");
  52
  53     if (Min == 0) {
  54       PrintError(
  55           DiagLoc,
  56           DiagCtx +
  57               ": minimum number of arguments must be greater than zero in " +
  58               VariadicClassName);
  59       return std::nullopt;
  60     }
  61
  62     if (Max <= Min && Max != 0) {
  63       PrintError(DiagLoc, DiagCtx + ": maximum number of arguments (" +
  64                               Twine(Max) +
  65                               ") must be zero, or greater "
  66                               "than the minimum number of arguments (" +
  67                               Twine(Min) + ") in " + VariadicClassName);
  68       return std::nullopt;
  69     }
  70
  71     PatternType PT(PT_VariadicPack);
  72     PT.Data.VPTI = {unsigned(Min), unsigned(Max)};
  73     return PT;
  74   }
  75
  76   PrintError(DiagLoc, DiagCtx + ": unknown type '" + R->getName() + "'");
  77   return std::nullopt;
  78 }
  79
  80 PatternType PatternType::getTypeOf(StringRef OpName) {
  81   PatternType PT(PT_TypeOf);
  82   PT.Data.Str = OpName;
  83   return PT;
  84 }
  85
  86 StringRef PatternType::getTypeOfOpName() const {
  87   assert(isTypeOf());
  88   return Data.Str;
  89 }
  90
  91 const Record *PatternType::getLLTRecord() const {
  92   assert(isLLT());
  93   return Data.Def;
  94 }
  95
  96 VariadicPackTypeInfo PatternType::getVariadicPackTypeInfo() const {
  97   assert(isVariadicPack());
  98   return Data.VPTI;
  99 }
 100
 101 bool PatternType::operator==(const PatternType &Other) const {
 102   if (Kind != Other.Kind)
 103     return false;
 104
 105   switch (Kind) {
 106   case PT_None:
 107     return true;
 108   case PT_ValueType:
 109     return Data.Def == Other.Data.Def;
 110   case PT_TypeOf:
 111     return Data.Str == Other.Data.Str;
 112   case PT_VariadicPack:
 113     return Data.VPTI == Other.Data.VPTI;
 114   }
 115
 116   llvm_unreachable("Unknown Type Kind");
 117 }
 118
 119 std::string PatternType::str() const {
 120   switch (Kind) {
 121   case PT_None:
 122     return "";
 123   case PT_ValueType:
 124     return Data.Def->getName().str();
 125   case PT_TypeOf:
 126     return (TypeOfClassName + "<$" + getTypeOfOpName() + ">").str();
 127   case PT_VariadicPack:
 128     return (VariadicClassName + "<" + Twine(Data.VPTI.Min) + "," +
 129             Twine(Data.VPTI.Max) + ">")
 130         .str();
 131   }
 132
 133   llvm_unreachable("Unknown type!");
 134 }
 135
 136 //===- Pattern ------------------------------------------------------------===//
 137
 138 void Pattern::dump() const { return print(dbgs()); }
 139
 140 const char *Pattern::getKindName() const {
 141   switch (Kind) {
 142   case K_AnyOpcode:
 143     return "AnyOpcodePattern";
 144   case K_CXX:
 145     return "CXXPattern";
 146   case K_CodeGenInstruction:
 147     return "CodeGenInstructionPattern";
 148   case K_PatFrag:
 149     return "PatFragPattern";
 150   case K_Builtin:
 151     return "BuiltinPattern";
 152   }
 153
 154   llvm_unreachable("unknown pattern kind!");
 155 }
 156
 157 void Pattern::printImpl(raw_ostream &OS, bool PrintName,
 158                         function_ref<void()> ContentPrinter) const {
 159   OS << "(" << getKindName() << " ";
 160   if (PrintName)
 161     OS << "name:" << getName() << " ";
 162   ContentPrinter();
 163   OS << ")";
 164 }
 165
 166 //===- AnyOpcodePattern ---------------------------------------------------===//
 167
 168 void AnyOpcodePattern::print(raw_ostream &OS, bool PrintName) const {
 169   printImpl(OS, PrintName, [&OS, this]() {
 170     OS << "["
 171        << join(map_range(Insts,
 172                          [](const auto *I) { return I->TheDef->getName(); }),
 173                ", ")
 174        << "]";
 175   });
 176 }
 177
 178 //===- CXXPattern ---------------------------------------------------------===//
 179
 180 CXXPattern::CXXPattern(const StringInit &Code, StringRef Name)
 181     : CXXPattern(Code.getAsUnquotedString(), Name) {}
 182
 183 const CXXPredicateCode &
 184 CXXPattern::expandCode(const CodeExpansions &CE, ArrayRef<SMLoc> Locs,
 185                        function_ref<void(raw_ostream &)> AddComment) const {
 186   assert(!IsApply && "'apply' CXX patterns should be handled differently!");
 187
 188   std::string Result;
 189   raw_string_ostream OS(Result);
 190
 191   if (AddComment)
 192     AddComment(OS);
 193
 194   CodeExpander Expander(RawCode, CE, Locs, /*ShowExpansions*/ false);
 195   Expander.emit(OS);
 196   return CXXPredicateCode::getMatchCode(std::move(Result));
 197 }
 198
 199 void CXXPattern::print(raw_ostream &OS, bool PrintName) const {
 200   printImpl(OS, PrintName, [&OS, this] {
 201     OS << (IsApply ? "apply" : "match") << " code:\"";
 202     printEscapedString(getRawCode(), OS);
 203     OS << "\"";
 204   });
 205 }
 206
 207 //===- InstructionOperand -------------------------------------------------===//
 208
 209 std::string InstructionOperand::describe() const {
 210   if (!hasImmValue())
 211     return "MachineOperand $" + getOperandName().str() + "";
 212   std::string Str = "imm " + std::to_string(getImmValue());
 213   if (isNamedImmediate())
 214     Str += ":$" + getOperandName().str() + "";
 215   return Str;
 216 }
 217
 218 void InstructionOperand::print(raw_ostream &OS) const {
 219   if (isDef())
 220     OS << "<def>";
 221
 222   bool NeedsColon = true;
 223   if (Type) {
 224     if (hasImmValue())
 225       OS << "(" << Type.str() << " " << getImmValue() << ")";
 226     else
 227       OS << Type.str();
 228   } else if (hasImmValue())
 229     OS << getImmValue();
 230   else
 231     NeedsColon = false;
 232
 233   if (isNamedOperand())
 234     OS << (NeedsColon ? ":" : "") << "$" << getOperandName();
 235 }
 236
 237 void InstructionOperand::dump() const { return print(dbgs()); }
 238
 239 //===- InstructionPattern -------------------------------------------------===//
 240
 241 bool InstructionPattern::diagnoseAllSpecialTypes(ArrayRef<SMLoc> Loc,
 242                                                  Twine Msg) const {
 243   bool HasDiag = false;
 244   for (const auto &[Idx, Op] : enumerate(operands())) {
 245     if (Op.getType().isSpecial()) {
 246       PrintError(Loc, Msg);
 247       PrintNote(Loc, "operand " + Twine(Idx) + " of '" + getName() +
 248                          "' has type '" + Op.getType().str() + "'");
 249       HasDiag = true;
 250     }
 251   }
 252   return HasDiag;
 253 }
 254
 255 void InstructionPattern::reportUnreachable(ArrayRef<SMLoc> Locs) const {
 256   PrintError(Locs, "pattern '" + getName() + "' ('" + getInstName() +
 257                        "') is unreachable from the pattern root!");
 258 }
 259
 260 bool InstructionPattern::checkSemantics(ArrayRef<SMLoc> Loc) {
 261   unsigned NumExpectedOperands = getNumInstOperands();
 262
 263   if (isVariadic()) {
 264     if (Operands.size() < NumExpectedOperands) {
 265       PrintError(Loc, +"'" + getInstName() + "' expected at least " +
 266                           Twine(NumExpectedOperands) + " operands, got " +
 267                           Twine(Operands.size()));
 268       return false;
 269     }
 270   } else if (NumExpectedOperands != Operands.size()) {
 271     PrintError(Loc, +"'" + getInstName() + "' expected " +
 272                         Twine(NumExpectedOperands) + " operands, got " +
 273                         Twine(Operands.size()));
 274     return false;
 275   }
 276
 277   unsigned OpIdx = 0;
 278   unsigned NumDefs = getNumInstDefs();
 279   for (auto &Op : Operands)
 280     Op.setIsDef(OpIdx++ < NumDefs);
 281
 282   return true;
 283 }
 284
 285 void InstructionPattern::print(raw_ostream &OS, bool PrintName) const {
 286   printImpl(OS, PrintName, [&OS, this] {
 287     OS << getInstName() << " operands:[";
 288     StringRef Sep;
 289     for (const auto &Op : Operands) {
 290       OS << Sep;
 291       Op.print(OS);
 292       Sep = ", ";
 293     }
 294     OS << "]";
 295
 296     printExtras(OS);
 297   });
 298 }
 299
 300 //===- OperandTable -------------------------------------------------------===//
 301
 302 bool OperandTable::addPattern(InstructionPattern *P,
 303                               function_ref<void(StringRef)> DiagnoseRedef) {
 304   for (const auto &Op : P->named_operands()) {
 305     StringRef OpName = Op.getOperandName();
 306
 307     // We always create an entry in the OperandTable, even for uses.
 308     // Uses of operands that don't have a def (= live-ins) will remain with a
 309     // nullptr as the Def.
 310     //
 311     // This allows us tell whether an operand exists in a pattern or not. If
 312     // there is no entry for it, it doesn't exist, if there is an entry, it's
 313     // used/def'd at least once.
 314     auto &Def = Table[OpName];
 315
 316     if (!Op.isDef())
 317       continue;
 318
 319     if (Def) {
 320       DiagnoseRedef(OpName);
 321       return false;
 322     }
 323
 324     Def = P;
 325   }
 326
 327   return true;
 328 }
 329
 330 void OperandTable::print(raw_ostream &OS, StringRef Name,
 331                          StringRef Indent) const {
 332   OS << Indent << "(OperandTable ";
 333   if (!Name.empty())
 334     OS << Name << " ";
 335   if (Table.empty()) {
 336     OS << "<empty>)\n";
 337     return;
 338   }
 339
 340   SmallVector<StringRef, 0> Keys(Table.keys());
 341   sort(Keys);
 342
 343   OS << '\n';
 344   for (const auto &Key : Keys) {
 345     const auto *Def = Table.at(Key);
 346     OS << Indent << "  " << Key << " -> "
 347        << (Def ? Def->getName() : "<live-in>") << '\n';
 348   }
 349   OS << Indent << ")\n";
 350 }
 351
 352 void OperandTable::dump() const { print(dbgs()); }
 353
 354 //===- MIFlagsInfo --------------------------------------------------------===//
 355
 356 void MIFlagsInfo::addSetFlag(const Record *R) {
 357   SetF.insert(R->getValueAsString("EnumName"));
 358 }
 359
 360 void MIFlagsInfo::addUnsetFlag(const Record *R) {
 361   UnsetF.insert(R->getValueAsString("EnumName"));
 362 }
 363
 364 void MIFlagsInfo::addCopyFlag(StringRef InstName) { CopyF.insert(InstName); }
 365
 366 //===- CodeGenInstructionPattern ------------------------------------------===//
 367
 368 bool CodeGenInstructionPattern::is(StringRef OpcodeName) const {
 369   return I.TheDef->getName() == OpcodeName;
 370 }
 371
 372 bool CodeGenInstructionPattern::isVariadic() const {
 373   return !isIntrinsic() && I.Operands.isVariadic;
 374 }
 375
 376 bool CodeGenInstructionPattern::hasVariadicDefs() const {
 377   // Note: we cannot use variadicOpsAreDefs, it's not set for
 378   // GenericInstructions.
 379   if (!isVariadic())
 380     return false;
 381
 382   if (I.variadicOpsAreDefs)
 383     return true;
 384
 385   const DagInit *OutOps = I.TheDef->getValueAsDag("OutOperandList");
 386   if (OutOps->arg_empty())
 387     return false;
 388
 389   auto *LastArgTy = dyn_cast<DefInit>(OutOps->getArg(OutOps->arg_size() - 1));
 390   return LastArgTy && LastArgTy->getDef()->getName() == "variable_ops";
 391 }
 392
 393 unsigned CodeGenInstructionPattern::getNumInstDefs() const {
 394   if (isIntrinsic())
 395     return IntrinInfo->IS.RetTys.size();
 396
 397   if (!isVariadic() || !hasVariadicDefs())
 398     return I.Operands.NumDefs;
 399   unsigned NumOuts = I.Operands.size() - I.Operands.NumDefs;
 400   assert(Operands.size() > NumOuts);
 401   return std::max<unsigned>(I.Operands.NumDefs, Operands.size() - NumOuts);
 402 }
 403
 404 unsigned CodeGenInstructionPattern::getNumInstOperands() const {
 405   if (isIntrinsic())
 406     return IntrinInfo->IS.RetTys.size() + IntrinInfo->IS.ParamTys.size();
 407
 408   unsigned NumCGIOps = I.Operands.size();
 409   return isVariadic() ? std::max<unsigned>(NumCGIOps, Operands.size())
 410                       : NumCGIOps;
 411 }
 412
 413 MIFlagsInfo &CodeGenInstructionPattern::getOrCreateMIFlagsInfo() {
 414   if (!FI)
 415     FI = std::make_unique<MIFlagsInfo>();
 416   return *FI;
 417 }
 418
 419 StringRef CodeGenInstructionPattern::getInstName() const {
 420   return I.TheDef->getName();
 421 }
 422
 423 void CodeGenInstructionPattern::printExtras(raw_ostream &OS) const {
 424   if (isIntrinsic())
 425     OS << " intrinsic(@" << IntrinInfo->Name << ")";
 426
 427   if (!FI)
 428     return;
 429
 430   OS << " (MIFlags";
 431   if (!FI->set_flags().empty())
 432     OS << " (set " << join(FI->set_flags(), ", ") << ")";
 433   if (!FI->unset_flags().empty())
 434     OS << " (unset " << join(FI->unset_flags(), ", ") << ")";
 435   if (!FI->copy_flags().empty())
 436     OS << " (copy " << join(FI->copy_flags(), ", ") << ")";
 437   OS << ')';
 438 }
 439
 440 //===- OperandTypeChecker -------------------------------------------------===//
 441
 442 bool OperandTypeChecker::check(
 443     InstructionPattern &P,
 444     std::function<bool(const PatternType &)> VerifyTypeOfOperand) {
 445   Pats.push_back(&P);
 446
 447   for (auto &Op : P.operands()) {
 448     const auto Ty = Op.getType();
 449     if (!Ty)
 450       continue;
 451
 452     if (Ty.isTypeOf() && !VerifyTypeOfOperand(Ty))
 453       return false;
 454
 455     if (!Op.isNamedOperand())
 456       continue;
 457
 458     StringRef OpName = Op.getOperandName();
 459     auto &Info = Types[OpName];
 460     if (!Info.Type) {
 461       Info.Type = Ty;
 462       Info.PrintTypeSrcNote = [this, OpName, Ty, &P]() {
 463         PrintSeenWithTypeIn(P, OpName, Ty);
 464       };
 465       continue;
 466     }
 467
 468     if (Info.Type != Ty) {
 469       PrintError(DiagLoc, "conflicting types for operand '" +
 470                               Op.getOperandName() + "': '" + Info.Type.str() +
 471                               "' vs '" + Ty.str() + "'");
 472       PrintSeenWithTypeIn(P, OpName, Ty);
 473       Info.PrintTypeSrcNote();
 474       return false;
 475     }
 476   }
 477
 478   return true;
 479 }
 480
 481 void OperandTypeChecker::propagateTypes() {
 482   for (auto *Pat : Pats) {
 483     for (auto &Op : Pat->named_operands()) {
 484       if (auto &Info = Types[Op.getOperandName()]; Info.Type)
 485         Op.setType(Info.Type);
 486     }
 487   }
 488 }
 489
 490 void OperandTypeChecker::PrintSeenWithTypeIn(InstructionPattern &P,
 491                                              StringRef OpName,
 492                                              PatternType Ty) const {
 493   PrintNote(DiagLoc, "'" + OpName + "' seen with type '" + Ty.str() + "' in '" +
 494                          P.getName() + "'");
 495 }
 496
 497 StringRef PatFrag::getParamKindStr(ParamKind OK) {
 498   switch (OK) {
 499   case PK_Root:
 500     return "root";
 501   case PK_MachineOperand:
 502     return "machine_operand";
 503   case PK_Imm:
 504     return "imm";
 505   }
 506
 507   llvm_unreachable("Unknown operand kind!");
 508 }
 509
 510 //===- PatFrag -----------------------------------------------------------===//
 511
 512 PatFrag::PatFrag(const Record &Def) : Def(Def) {
 513   assert(Def.isSubClassOf(ClassName));
 514 }
 515
 516 StringRef PatFrag::getName() const { return Def.getName(); }
 517
 518 ArrayRef<SMLoc> PatFrag::getLoc() const { return Def.getLoc(); }
 519
 520 void PatFrag::addInParam(StringRef Name, ParamKind Kind) {
 521   Params.emplace_back(Param{Name, Kind});
 522 }
 523
 524 iterator_range<PatFrag::ParamIt> PatFrag::in_params() const {
 525   return {Params.begin() + NumOutParams, Params.end()};
 526 }
 527
 528 void PatFrag::addOutParam(StringRef Name, ParamKind Kind) {
 529   assert(NumOutParams == Params.size() &&
 530          "Adding out-param after an in-param!");
 531   Params.emplace_back(Param{Name, Kind});
 532   ++NumOutParams;
 533 }
 534
 535 iterator_range<PatFrag::ParamIt> PatFrag::out_params() const {
 536   return {Params.begin(), Params.begin() + NumOutParams};
 537 }
 538
 539 unsigned PatFrag::num_roots() const {
 540   return count_if(out_params(),
 541                   [&](const auto &P) { return P.Kind == PK_Root; });
 542 }
 543
 544 unsigned PatFrag::getParamIdx(StringRef Name) const {
 545   for (const auto &[Idx, Op] : enumerate(Params)) {
 546     if (Op.Name == Name)
 547       return Idx;
 548   }
 549
 550   return -1;
 551 }
 552
 553 bool PatFrag::checkSemantics() {
 554   for (const auto &Alt : Alts) {
 555     for (const auto &Pat : Alt.Pats) {
 556       switch (Pat->getKind()) {
 557       case Pattern::K_AnyOpcode:
 558         PrintError("wip_match_opcode cannot be used in " + ClassName);
 559         return false;
 560       case Pattern::K_Builtin:
 561         PrintError("Builtin instructions cannot be used in " + ClassName);
 562         return false;
 563       case Pattern::K_CXX:
 564         continue;
 565       case Pattern::K_CodeGenInstruction:
 566         // TODO: Allow VarArgs?
 567         if (cast<CodeGenInstructionPattern>(Pat.get())->diagnoseAllSpecialTypes(
 568                 Def.getLoc(), PatternType::SpecialTyClassName +
 569                                   " is not supported in " + ClassName))
 570           return false;
 571         continue;
 572       case Pattern::K_PatFrag:
 573         // TODO: It's just that the emitter doesn't handle it but technically
 574         // there is no reason why we can't. We just have to be careful with
 575         // operand mappings, it could get complex.
 576         PrintError("nested " + ClassName + " are not supported");
 577         return false;
 578       }
 579     }
 580   }
 581
 582   StringSet<> SeenOps;
 583   for (const auto &Op : in_params()) {
 584     if (SeenOps.count(Op.Name)) {
 585       PrintError("duplicate parameter '" + Op.Name + "'");
 586       return false;
 587     }
 588
 589     // Check this operand is NOT defined in any alternative's patterns.
 590     for (const auto &Alt : Alts) {
 591       if (Alt.OpTable.lookup(Op.Name).Def) {
 592         PrintError("input parameter '" + Op.Name + "' cannot be redefined!");
 593         return false;
 594       }
 595     }
 596
 597     if (Op.Kind == PK_Root) {
 598       PrintError("input parameterr '" + Op.Name + "' cannot be a root!");
 599       return false;
 600     }
 601
 602     SeenOps.insert(Op.Name);
 603   }
 604
 605   for (const auto &Op : out_params()) {
 606     if (Op.Kind != PK_Root && Op.Kind != PK_MachineOperand) {
 607       PrintError("output parameter '" + Op.Name +
 608                  "' must be 'root' or 'gi_mo'");
 609       return false;
 610     }
 611
 612     if (SeenOps.count(Op.Name)) {
 613       PrintError("duplicate parameter '" + Op.Name + "'");
 614       return false;
 615     }
 616
 617     // Check this operand is defined in all alternative's patterns.
 618     for (const auto &Alt : Alts) {
 619       const auto *OpDef = Alt.OpTable.getDef(Op.Name);
 620       if (!OpDef) {
 621         PrintError("output parameter '" + Op.Name +
 622                    "' must be defined by all alternative patterns in '" +
 623                    Def.getName() + "'");
 624         return false;
 625       }
 626
 627       if (Op.Kind == PK_Root && OpDef->getNumInstDefs() != 1) {
 628         // The instruction that defines the root must have a single def.
 629         // Otherwise we'd need to support multiple roots and it gets messy.
 630         //
 631         // e.g. this is not supported:
 632         //   (pattern (G_UNMERGE_VALUES $x, $root, $vec))
 633         PrintError("all instructions that define root '" + Op.Name + "' in '" +
 634                    Def.getName() + "' can only have a single output operand");
 635         return false;
 636       }
 637     }
 638
 639     SeenOps.insert(Op.Name);
 640   }
 641
 642   if (num_out_params() != 0 && num_roots() == 0) {
 643     PrintError(ClassName + " must have one root in its 'out' operands");
 644     return false;
 645   }
 646
 647   if (num_roots() > 1) {
 648     PrintError(ClassName + " can only have one root");
 649     return false;
 650   }
 651
 652   // TODO: find unused params
 653
 654   const auto CheckTypeOf = [&](const PatternType &) -> bool {
 655     llvm_unreachable("GITypeOf should have been rejected earlier!");
 656   };
 657
 658   // Now, typecheck all alternatives.
 659   for (auto &Alt : Alts) {
 660     OperandTypeChecker OTC(Def.getLoc());
 661     for (auto &Pat : Alt.Pats) {
 662       if (auto *IP = dyn_cast<InstructionPattern>(Pat.get())) {
 663         if (!OTC.check(*IP, CheckTypeOf))
 664           return false;
 665       }
 666     }
 667     OTC.propagateTypes();
 668   }
 669
 670   return true;
 671 }
 672
 673 bool PatFrag::handleUnboundInParam(StringRef ParamName, StringRef ArgName,
 674                                    ArrayRef<SMLoc> DiagLoc) const {
 675   // The parameter must be a live-in of all alternatives for this to work.
 676   // Otherwise, we risk having unbound parameters being used (= crashes).
 677   //
 678   // Examples:
 679   //
 680   // in (ins $y), (patterns (G_FNEG $dst, $y), "return matchFnegOp(${y})")
 681   //    even if $y is unbound, we'll lazily bind it when emitting the G_FNEG.
 682   //
 683   // in (ins $y), (patterns "return matchFnegOp(${y})")
 684   //    if $y is unbound when this fragment is emitted, C++ code expansion will
 685   //    fail.
 686   for (const auto &Alt : Alts) {
 687     auto &OT = Alt.OpTable;
 688     if (!OT.lookup(ParamName).Found) {
 689       llvm::PrintError(DiagLoc, "operand '" + ArgName + "' (for parameter '" +
 690                                     ParamName + "' of '" + getName() +
 691                                     "') cannot be unbound");
 692       PrintNote(
 693           DiagLoc,
 694           "one or more alternatives of '" + getName() + "' do not bind '" +
 695               ParamName +
 696               "' to an instruction operand; either use a bound operand or "
 697               "ensure '" +
 698               Def.getName() + "' binds '" + ParamName +
 699               "' in all alternatives");
 700       return false;
 701     }
 702   }
 703
 704   return true;
 705 }
 706
 707 bool PatFrag::buildOperandsTables() {
 708   // enumerate(...) doesn't seem to allow lvalues so we need to count the old
 709   // way.
 710   unsigned Idx = 0;
 711
 712   const auto DiagnoseRedef = [this, &Idx](StringRef OpName) {
 713     PrintError("Operand '" + OpName +
 714                "' is defined multiple times in patterns of alternative #" +
 715                std::to_string(Idx));
 716   };
 717
 718   for (auto &Alt : Alts) {
 719     for (auto &Pat : Alt.Pats) {
 720       auto *IP = dyn_cast<InstructionPattern>(Pat.get());
 721       if (!IP)
 722         continue;
 723
 724       if (!Alt.OpTable.addPattern(IP, DiagnoseRedef))
 725         return false;
 726     }
 727
 728     ++Idx;
 729   }
 730
 731   return true;
 732 }
 733
 734 void PatFrag::print(raw_ostream &OS, StringRef Indent) const {
 735   OS << Indent << "(PatFrag name:" << getName() << '\n';
 736   if (!in_params().empty()) {
 737     OS << Indent << "  (ins ";
 738     printParamsList(OS, in_params());
 739     OS << ")\n";
 740   }
 741
 742   if (!out_params().empty()) {
 743     OS << Indent << "  (outs ";
 744     printParamsList(OS, out_params());
 745     OS << ")\n";
 746   }
 747
 748   // TODO: Dump OperandTable as well.
 749   OS << Indent << "  (alternatives [\n";
 750   for (const auto &Alt : Alts) {
 751     OS << Indent << "    [\n";
 752     for (const auto &Pat : Alt.Pats) {
 753       OS << Indent << "      ";
 754       Pat->print(OS, /*PrintName=*/true);
 755       OS << ",\n";
 756     }
 757     OS << Indent << "    ],\n";
 758   }
 759   OS << Indent << "  ])\n";
 760
 761   OS << Indent << ')';
 762 }
 763
 764 void PatFrag::dump() const { print(dbgs()); }
 765
 766 void PatFrag::printParamsList(raw_ostream &OS, iterator_range<ParamIt> Params) {
 767   OS << '['
 768      << join(map_range(Params,
 769                        [](auto &O) {
 770                          return (O.Name + ":" + getParamKindStr(O.Kind)).str();
 771                        }),
 772              ", ")
 773      << ']';
 774 }
 775
 776 void PatFrag::PrintError(Twine Msg) const { llvm::PrintError(&Def, Msg); }
 777
 778 ArrayRef<InstructionOperand> PatFragPattern::getApplyDefsNeeded() const {
 779   assert(PF.num_roots() == 1);
 780   // Only roots need to be redef.
 781   for (auto [Idx, Param] : enumerate(PF.out_params())) {
 782     if (Param.Kind == PatFrag::PK_Root)
 783       return getOperand(Idx);
 784   }
 785   llvm_unreachable("root not found!");
 786 }
 787
 788 //===- PatFragPattern -----------------------------------------------------===//
 789
 790 bool PatFragPattern::checkSemantics(ArrayRef<SMLoc> DiagLoc) {
 791   if (!InstructionPattern::checkSemantics(DiagLoc))
 792     return false;
 793
 794   for (const auto &[Idx, Op] : enumerate(Operands)) {
 795     switch (PF.getParam(Idx).Kind) {
 796     case PatFrag::PK_Imm:
 797       if (!Op.hasImmValue()) {
 798         PrintError(DiagLoc, "expected operand " + std::to_string(Idx) +
 799                                 " of '" + getInstName() +
 800                                 "' to be an immediate; got " + Op.describe());
 801         return false;
 802       }
 803       if (Op.isNamedImmediate()) {
 804         PrintError(DiagLoc, "operand " + std::to_string(Idx) + " of '" +
 805                                 getInstName() +
 806                                 "' cannot be a named immediate");
 807         return false;
 808       }
 809       break;
 810     case PatFrag::PK_Root:
 811     case PatFrag::PK_MachineOperand:
 812       if (!Op.isNamedOperand() || Op.isNamedImmediate()) {
 813         PrintError(DiagLoc, "expected operand " + std::to_string(Idx) +
 814                                 " of '" + getInstName() +
 815                                 "' to be a MachineOperand; got " +
 816                                 Op.describe());
 817         return false;
 818       }
 819       break;
 820     }
 821   }
 822
 823   return true;
 824 }
 825
 826 bool PatFragPattern::mapInputCodeExpansions(const CodeExpansions &ParentCEs,
 827                                             CodeExpansions &PatFragCEs,
 828                                             ArrayRef<SMLoc> DiagLoc) const {
 829   for (const auto &[Idx, Op] : enumerate(operands())) {
 830     StringRef ParamName = PF.getParam(Idx).Name;
 831
 832     // Operands to a PFP can only be named, or be an immediate, but not a named
 833     // immediate.
 834     assert(!Op.isNamedImmediate());
 835
 836     if (Op.isNamedOperand()) {
 837       StringRef ArgName = Op.getOperandName();
 838       // Map it only if it's been defined.
 839       auto It = ParentCEs.find(ArgName);
 840       if (It == ParentCEs.end()) {
 841         if (!PF.handleUnboundInParam(ParamName, ArgName, DiagLoc))
 842           return false;
 843       } else
 844         PatFragCEs.declare(ParamName, It->second);
 845       continue;
 846     }
 847
 848     if (Op.hasImmValue()) {
 849       PatFragCEs.declare(ParamName, std::to_string(Op.getImmValue()));
 850       continue;
 851     }
 852
 853     llvm_unreachable("Unknown Operand Type!");
 854   }
 855
 856   return true;
 857 }
 858
 859 //===- BuiltinPattern -----------------------------------------------------===//
 860
 861 BuiltinPattern::BuiltinInfo BuiltinPattern::getBuiltinInfo(const Record &Def) {
 862   assert(Def.isSubClassOf(ClassName));
 863
 864   StringRef Name = Def.getName();
 865   for (const auto &KBI : KnownBuiltins) {
 866     if (KBI.DefName == Name)
 867       return KBI;
 868   }
 869
 870   PrintFatalError(Def.getLoc(),
 871                   "Unimplemented " + ClassName + " def '" + Name + "'");
 872 }
 873
 874 bool BuiltinPattern::checkSemantics(ArrayRef<SMLoc> Loc) {
 875   if (!InstructionPattern::checkSemantics(Loc))
 876     return false;
 877
 878   // For now all builtins just take names, no immediates.
 879   for (const auto &[Idx, Op] : enumerate(operands())) {
 880     if (!Op.isNamedOperand() || Op.isNamedImmediate()) {
 881       PrintError(Loc, "expected operand " + std::to_string(Idx) + " of '" +
 882                           getInstName() + "' to be a name");
 883       return false;
 884     }
 885   }
 886
 887   return true;
 888 }
 889
 890 } // namespace gi
 891 } // namespace llvm