utils/TableGen/GICombinerEmitter.cpp

   1 //===- GlobalCombinerEmitter.cpp - Generate a combiner --------------------===//
   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 /// \file Generate a combiner implementation for GlobalISel from a declarative
  10 /// syntax
  11 ///
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/ADT/Statistic.h"
  15 #include "llvm/Support/CommandLine.h"
  16 #include "llvm/Support/Timer.h"
  17 #include "llvm/TableGen/Error.h"
  18 #include "llvm/TableGen/StringMatcher.h"
  19 #include "llvm/TableGen/TableGenBackend.h"
  20 #include "CodeGenTarget.h"
  21 #include "GlobalISel/CodeExpander.h"
  22 #include "GlobalISel/CodeExpansions.h"
  23
  24 using namespace llvm;
  25
  26 #define DEBUG_TYPE "gicombiner-emitter"
  27
  28 // FIXME: Use ALWAYS_ENABLED_STATISTIC once it's available.
  29 unsigned NumPatternTotal = 0;
  30 STATISTIC(NumPatternTotalStatistic, "Total number of patterns");
  31
  32 cl::OptionCategory
  33     GICombinerEmitterCat("Options for -gen-global-isel-combiner");
  34 static cl::list<std::string>
  35     SelectedCombiners("combiners", cl::desc("Emit the specified combiners"),
  36                       cl::cat(GICombinerEmitterCat), cl::CommaSeparated);
  37 static cl::opt<bool> ShowExpansions(
  38     "gicombiner-show-expansions",
  39     cl::desc("Use C++ comments to indicate occurence of code expansion"),
  40     cl::cat(GICombinerEmitterCat));
  41
  42 namespace {
  43 typedef uint64_t RuleID;
  44
  45 class RootInfo {
  46   StringRef PatternSymbol;
  47
  48 public:
  49   RootInfo(StringRef PatternSymbol) : PatternSymbol(PatternSymbol) {}
  50
  51   StringRef getPatternSymbol() const { return PatternSymbol; }
  52 };
  53
  54 class CombineRule {
  55 protected:
  56   /// A unique ID for this rule
  57   /// ID's are used for debugging and run-time disabling of rules among other
  58   /// things.
  59   RuleID ID;
  60
  61   /// The record defining this rule.
  62   const Record &TheDef;
  63
  64   /// The roots of a match. These are the leaves of the DAG that are closest to
  65   /// the end of the function. I.e. the nodes that are encountered without
  66   /// following any edges of the DAG described by the pattern as we work our way
  67   /// from the bottom of the function to the top.
  68   std::vector<RootInfo> Roots;
  69
  70   /// A block of arbitrary C++ to finish testing the match.
  71   /// FIXME: This is a temporary measure until we have actual pattern matching
  72   const CodeInit *MatchingFixupCode = nullptr;
  73 public:
  74   CombineRule(const CodeGenTarget &Target, RuleID ID, const Record &R)
  75       : ID(ID), TheDef(R) {}
  76   bool parseDefs();
  77   bool parseMatcher(const CodeGenTarget &Target);
  78
  79   RuleID getID() const { return ID; }
  80   StringRef getName() const { return TheDef.getName(); }
  81   const Record &getDef() const { return TheDef; }
  82   const CodeInit *getMatchingFixupCode() const { return MatchingFixupCode; }
  83   size_t getNumRoots() const { return Roots.size(); }
  84
  85   using const_root_iterator = std::vector<RootInfo>::const_iterator;
  86   const_root_iterator roots_begin() const { return Roots.begin(); }
  87   const_root_iterator roots_end() const { return Roots.end(); }
  88   iterator_range<const_root_iterator> roots() const {
  89     return llvm::make_range(Roots.begin(), Roots.end());
  90   }
  91 };
  92
  93 /// A convenience function to check that an Init refers to a specific def. This
  94 /// is primarily useful for testing for defs and similar in DagInit's since
  95 /// DagInit's support any type inside them.
  96 static bool isSpecificDef(const Init &N, StringRef Def) {
  97   if (const DefInit *OpI = dyn_cast<DefInit>(&N))
  98     if (OpI->getDef()->getName() == Def)
  99       return true;
 100   return false;
 101 }
 102
 103 /// A convenience function to check that an Init refers to a def that is a
 104 /// subclass of the given class and coerce it to a def if it is. This is
 105 /// primarily useful for testing for subclasses of GIMatchKind and similar in
 106 /// DagInit's since DagInit's support any type inside them.
 107 static Record *getDefOfSubClass(const Init &N, StringRef Cls) {
 108   if (const DefInit *OpI = dyn_cast<DefInit>(&N))
 109     if (OpI->getDef()->isSubClassOf(Cls))
 110       return OpI->getDef();
 111   return nullptr;
 112 }
 113
 114 bool CombineRule::parseDefs() {
 115   NamedRegionTimer T("parseDefs", "Time spent parsing the defs", "Rule Parsing",
 116                      "Time spent on rule parsing", TimeRegions);
 117   DagInit *Defs = TheDef.getValueAsDag("Defs");
 118
 119   if (Defs->getOperatorAsDef(TheDef.getLoc())->getName() != "defs") {
 120     PrintError(TheDef.getLoc(), "Expected defs operator");
 121     return false;
 122   }
 123
 124   for (unsigned I = 0, E = Defs->getNumArgs(); I < E; ++I) {
 125     // Roots should be collected into Roots
 126     if (isSpecificDef(*Defs->getArg(I), "root")) {
 127       Roots.emplace_back(Defs->getArgNameStr(I));
 128       continue;
 129     }
 130
 131     // Otherwise emit an appropriate error message.
 132     if (getDefOfSubClass(*Defs->getArg(I), "GIDefKind"))
 133       PrintError(TheDef.getLoc(),
 134                  "This GIDefKind not implemented in tablegen");
 135     else if (getDefOfSubClass(*Defs->getArg(I), "GIDefKindWithArgs"))
 136       PrintError(TheDef.getLoc(),
 137                  "This GIDefKindWithArgs not implemented in tablegen");
 138     else
 139       PrintError(TheDef.getLoc(),
 140                  "Expected a subclass of GIDefKind or a sub-dag whose "
 141                  "operator is of type GIDefKindWithArgs");
 142     return false;
 143   }
 144
 145   if (Roots.empty()) {
 146     PrintError(TheDef.getLoc(), "Combine rules must have at least one root");
 147     return false;
 148   }
 149   return true;
 150 }
 151
 152 bool CombineRule::parseMatcher(const CodeGenTarget &Target) {
 153   NamedRegionTimer T("parseMatcher", "Time spent parsing the matcher",
 154                      "Rule Parsing", "Time spent on rule parsing", TimeRegions);
 155   DagInit *Matchers = TheDef.getValueAsDag("Match");
 156
 157   if (Matchers->getOperatorAsDef(TheDef.getLoc())->getName() != "match") {
 158     PrintError(TheDef.getLoc(), "Expected match operator");
 159     return false;
 160   }
 161
 162   if (Matchers->getNumArgs() == 0) {
 163     PrintError(TheDef.getLoc(), "Matcher is empty");
 164     return false;
 165   }
 166
 167   // The match section consists of a list of matchers and predicates. Parse each
 168   // one and add the equivalent GIMatchDag nodes, predicates, and edges.
 169   for (unsigned I = 0; I < Matchers->getNumArgs(); ++I) {
 170
 171     // Parse arbitrary C++ code we have in lieu of supporting MIR matching
 172     if (const CodeInit *CodeI = dyn_cast<CodeInit>(Matchers->getArg(I))) {
 173       assert(!MatchingFixupCode &&
 174              "Only one block of arbitrary code is currently permitted");
 175       MatchingFixupCode = CodeI;
 176       continue;
 177     }
 178
 179     PrintError(TheDef.getLoc(),
 180                "Expected a subclass of GIMatchKind or a sub-dag whose "
 181                "operator is either of a GIMatchKindWithArgs or Instruction");
 182     PrintNote("Pattern was `" + Matchers->getArg(I)->getAsString() + "'");
 183     return false;
 184   }
 185   return true;
 186 }
 187
 188 class GICombinerEmitter {
 189   StringRef Name;
 190   const CodeGenTarget &Target;
 191   Record *Combiner;
 192   std::vector<std::unique_ptr<CombineRule>> Rules;
 193   std::unique_ptr<CombineRule> makeCombineRule(const Record &R);
 194
 195   void gatherRules(std::vector<std::unique_ptr<CombineRule>> &ActiveRules,
 196                    const std::vector<Record *> &&RulesAndGroups);
 197
 198 public:
 199   explicit GICombinerEmitter(RecordKeeper &RK, const CodeGenTarget &Target,
 200                              StringRef Name, Record *Combiner);
 201   ~GICombinerEmitter() {}
 202
 203   StringRef getClassName() const {
 204     return Combiner->getValueAsString("Classname");
 205   }
 206   void run(raw_ostream &OS);
 207
 208   /// Emit the name matcher (guarded by #ifndef NDEBUG) used to disable rules in
 209   /// response to the generated cl::opt.
 210   void emitNameMatcher(raw_ostream &OS) const;
 211   void generateCodeForRule(raw_ostream &OS, const CombineRule *Rule,
 212                            StringRef Indent) const;
 213 };
 214
 215 GICombinerEmitter::GICombinerEmitter(RecordKeeper &RK,
 216                                      const CodeGenTarget &Target,
 217                                      StringRef Name, Record *Combiner)
 218     : Name(Name), Target(Target), Combiner(Combiner) {}
 219
 220 void GICombinerEmitter::emitNameMatcher(raw_ostream &OS) const {
 221   std::vector<std::pair<std::string, std::string>> Cases;
 222   Cases.reserve(Rules.size());
 223
 224   for (const CombineRule &EnumeratedRule : make_pointee_range(Rules)) {
 225     std::string Code;
 226     raw_string_ostream SS(Code);
 227     SS << "return " << EnumeratedRule.getID() << ";\n";
 228     Cases.push_back(std::make_pair(EnumeratedRule.getName(), SS.str()));
 229   }
 230
 231   OS << "static Optional<uint64_t> getRuleIdxForIdentifier(StringRef "
 232         "RuleIdentifier) {\n"
 233      << "  uint64_t I;\n"
 234      << "  // getAtInteger(...) returns false on success\n"
 235      << "  bool Parsed = !RuleIdentifier.getAsInteger(0, I);\n"
 236      << "  if (Parsed)\n"
 237      << "    return I;\n\n"
 238      << "#ifndef NDEBUG\n";
 239   StringMatcher Matcher("RuleIdentifier", Cases, OS);
 240   Matcher.Emit();
 241   OS << "#endif // ifndef NDEBUG\n\n"
 242      << "  return None;\n"
 243      << "}\n";
 244 }
 245
 246 std::unique_ptr<CombineRule>
 247 GICombinerEmitter::makeCombineRule(const Record &TheDef) {
 248   std::unique_ptr<CombineRule> Rule =
 249       std::make_unique<CombineRule>(Target, NumPatternTotal, TheDef);
 250
 251   if (!Rule->parseDefs())
 252     return nullptr;
 253   if (!Rule->parseMatcher(Target))
 254     return nullptr;
 255   // For now, don't support multi-root rules. We'll come back to this later
 256   // once we have the algorithm changes to support it.
 257   if (Rule->getNumRoots() > 1) {
 258     PrintError(TheDef.getLoc(), "Multi-root matches are not supported (yet)");
 259     return nullptr;
 260   }
 261   return Rule;
 262 }
 263
 264 /// Recurse into GICombineGroup's and flatten the ruleset into a simple list.
 265 void GICombinerEmitter::gatherRules(
 266     std::vector<std::unique_ptr<CombineRule>> &ActiveRules,
 267     const std::vector<Record *> &&RulesAndGroups) {
 268   for (Record *R : RulesAndGroups) {
 269     if (R->isValueUnset("Rules")) {
 270       std::unique_ptr<CombineRule> Rule = makeCombineRule(*R);
 271       if (Rule == nullptr) {
 272         PrintError(R->getLoc(), "Failed to parse rule");
 273         continue;
 274       }
 275       ActiveRules.emplace_back(std::move(Rule));
 276       ++NumPatternTotal;
 277     } else
 278       gatherRules(ActiveRules, R->getValueAsListOfDefs("Rules"));
 279   }
 280 }
 281
 282 void GICombinerEmitter::generateCodeForRule(raw_ostream &OS,
 283                                             const CombineRule *Rule,
 284                                             StringRef Indent) const {
 285   {
 286     const Record &RuleDef = Rule->getDef();
 287
 288     OS << Indent << "// Rule: " << RuleDef.getName() << "\n"
 289        << Indent << "if (!isRuleDisabled(" << Rule->getID() << ")) {\n";
 290
 291     CodeExpansions Expansions;
 292     for (const RootInfo &Root : Rule->roots()) {
 293       Expansions.declare(Root.getPatternSymbol(), "MI");
 294     }
 295     DagInit *Applyer = RuleDef.getValueAsDag("Apply");
 296     if (Applyer->getOperatorAsDef(RuleDef.getLoc())->getName() !=
 297         "apply") {
 298       PrintError(RuleDef.getLoc(), "Expected apply operator");
 299       return;
 300     }
 301
 302     OS << Indent << "  if (1\n";
 303
 304     if (Rule->getMatchingFixupCode() &&
 305         !Rule->getMatchingFixupCode()->getValue().empty()) {
 306       // FIXME: Single-use lambda's like this are a serious compile-time
 307       // performance and memory issue. It's convenient for this early stage to
 308       // defer some work to successive patches but we need to eliminate this
 309       // before the ruleset grows to small-moderate size. Last time, it became
 310       // a big problem for low-mem systems around the 500 rule mark but by the
 311       // time we grow that large we should have merged the ISel match table
 312       // mechanism with the Combiner.
 313       OS << Indent << "      && [&]() {\n"
 314          << Indent << "      "
 315          << CodeExpander(Rule->getMatchingFixupCode()->getValue(), Expansions,
 316                          Rule->getMatchingFixupCode()->getLoc(), ShowExpansions)
 317          << "\n"
 318          << Indent << "      return true;\n"
 319          << Indent << "  }()";
 320     }
 321     OS << ") {\n" << Indent << "   ";
 322
 323     if (const CodeInit *Code = dyn_cast<CodeInit>(Applyer->getArg(0))) {
 324       OS << CodeExpander(Code->getAsUnquotedString(), Expansions,
 325                          Code->getLoc(), ShowExpansions)
 326          << "\n"
 327          << Indent << "    return true;\n"
 328          << Indent << "  }\n";
 329     } else {
 330       PrintError(RuleDef.getLoc(), "Expected apply code block");
 331       return;
 332     }
 333
 334     OS << Indent << "}\n";
 335   }
 336 }
 337
 338 void GICombinerEmitter::run(raw_ostream &OS) {
 339   gatherRules(Rules, Combiner->getValueAsListOfDefs("Rules"));
 340   NamedRegionTimer T("Emit", "Time spent emitting the combiner",
 341                      "Code Generation", "Time spent generating code",
 342                      TimeRegions);
 343   OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_DEPS\n"
 344      << "#include \"llvm/ADT/SparseBitVector.h\"\n"
 345      << "namespace llvm {\n"
 346      << "extern cl::OptionCategory GICombinerOptionCategory;\n"
 347      << "} // end namespace llvm\n"
 348      << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_DEPS\n\n";
 349
 350   OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_H\n"
 351      << "class " << getClassName() << " {\n"
 352      << "  SparseBitVector<> DisabledRules;\n"
 353      << "\n"
 354      << "public:\n"
 355      << "  bool parseCommandLineOption();\n"
 356      << "  bool isRuleDisabled(unsigned ID) const;\n"
 357      << "  bool setRuleDisabled(StringRef RuleIdentifier);\n"
 358      << "\n"
 359      << "  bool tryCombineAll(\n"
 360      << "    GISelChangeObserver &Observer,\n"
 361      << "    MachineInstr &MI,\n"
 362      << "    MachineIRBuilder &B) const;\n"
 363      << "};\n\n";
 364
 365   emitNameMatcher(OS);
 366
 367   OS << "bool " << getClassName()
 368      << "::setRuleDisabled(StringRef RuleIdentifier) {\n"
 369      << "  std::pair<StringRef, StringRef> RangePair = "
 370         "RuleIdentifier.split('-');\n"
 371      << "  if (!RangePair.second.empty()) {\n"
 372      << "    const auto First = getRuleIdxForIdentifier(RangePair.first);\n"
 373      << "    const auto Last = getRuleIdxForIdentifier(RangePair.second);\n"
 374      << "    if (!First.hasValue() || !Last.hasValue())\n"
 375      << "      return false;\n"
 376      << "    if (First >= Last)\n"
 377      << "      report_fatal_error(\"Beginning of range should be before end of "
 378         "range\");\n"
 379      << "    for (auto I = First.getValue(); I < Last.getValue(); ++I)\n"
 380      << "      DisabledRules.set(I);\n"
 381      << "    return true;\n"
 382      << "  } else {\n"
 383      << "    const auto I = getRuleIdxForIdentifier(RangePair.first);\n"
 384      << "    if (!I.hasValue())\n"
 385      << "      return false;\n"
 386      << "    DisabledRules.set(I.getValue());\n"
 387      << "    return true;\n"
 388      << "  }\n"
 389      << "  return false;\n"
 390      << "}\n";
 391
 392   OS << "bool " << getClassName()
 393      << "::isRuleDisabled(unsigned RuleID) const {\n"
 394      << "  return DisabledRules.test(RuleID);\n"
 395      << "}\n";
 396   OS << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_H\n\n";
 397
 398   OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n"
 399      << "\n"
 400      << "cl::list<std::string> " << Name << "Option(\n"
 401      << "    \"" << Name.lower() << "-disable-rule\",\n"
 402      << "    cl::desc(\"Disable one or more combiner rules temporarily in "
 403      << "the " << Name << " pass\"),\n"
 404      << "    cl::CommaSeparated,\n"
 405      << "    cl::Hidden,\n"
 406      << "    cl::cat(GICombinerOptionCategory));\n"
 407      << "\n"
 408      << "bool " << getClassName() << "::parseCommandLineOption() {\n"
 409      << "  for (const auto &Identifier : " << Name << "Option)\n"
 410      << "    if (!setRuleDisabled(Identifier))\n"
 411      << "      return false;\n"
 412      << "  return true;\n"
 413      << "}\n\n";
 414
 415   OS << "bool " << getClassName() << "::tryCombineAll(\n"
 416      << "    GISelChangeObserver &Observer,\n"
 417      << "    MachineInstr &MI,\n"
 418      << "    MachineIRBuilder &B) const {\n"
 419      << "  CombinerHelper Helper(Observer, B);\n"
 420      << "  MachineBasicBlock *MBB = MI.getParent();\n"
 421      << "  MachineFunction *MF = MBB->getParent();\n"
 422      << "  MachineRegisterInfo &MRI = MF->getRegInfo();\n"
 423      << "  (void)MBB; (void)MF; (void)MRI;\n\n";
 424
 425   for (const auto &Rule : Rules)
 426     generateCodeForRule(OS, Rule.get(), "  ");
 427   OS << "\n  return false;\n"
 428      << "}\n"
 429      << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n";
 430 }
 431
 432 } // end anonymous namespace
 433
 434 //===----------------------------------------------------------------------===//
 435
 436 namespace llvm {
 437 void EmitGICombiner(RecordKeeper &RK, raw_ostream &OS) {
 438   CodeGenTarget Target(RK);
 439   emitSourceFileHeader("Global Combiner", OS);
 440
 441   if (SelectedCombiners.empty())
 442     PrintFatalError("No combiners selected with -combiners");
 443   for (const auto &Combiner : SelectedCombiners) {
 444     Record *CombinerDef = RK.getDef(Combiner);
 445     if (!CombinerDef)
 446       PrintFatalError("Could not find " + Combiner);
 447     GICombinerEmitter(RK, Target, Combiner, CombinerDef).run(OS);
 448   }
 449   NumPatternTotalStatistic = NumPatternTotal;
 450 }
 451
 452 } // namespace llvm