1 //===- GlobalCombinerEmitter.cpp - Generate a combiner --------------------===//
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
7 //===----------------------------------------------------------------------===//
9 /// \file Generate a combiner implementation for GlobalISel from a declarative
12 //===----------------------------------------------------------------------===//
14 #include "llvm/ADT/SmallSet.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/ADT/StringSet.h"
17 #include "llvm/Support/CommandLine.h"
18 #include "llvm/Support/ScopedPrinter.h"
19 #include "llvm/Support/Timer.h"
20 #include "llvm/TableGen/Error.h"
21 #include "llvm/TableGen/StringMatcher.h"
22 #include "llvm/TableGen/TableGenBackend.h"
23 #include "CodeGenTarget.h"
24 #include "GlobalISel/CodeExpander.h"
25 #include "GlobalISel/CodeExpansions.h"
26 #include "GlobalISel/GIMatchDag.h"
27 #include "GlobalISel/GIMatchTree.h"
32 #define DEBUG_TYPE "gicombiner-emitter"
34 // FIXME: Use ALWAYS_ENABLED_STATISTIC once it's available.
35 unsigned NumPatternTotal = 0;
36 STATISTIC(NumPatternTotalStatistic, "Total number of patterns");
39 GICombinerEmitterCat("Options for -gen-global-isel-combiner");
40 static cl::list<std::string>
41 SelectedCombiners("combiners", cl::desc("Emit the specified combiners"),
42 cl::cat(GICombinerEmitterCat), cl::CommaSeparated);
43 static cl::opt<bool> ShowExpansions(
44 "gicombiner-show-expansions",
45 cl::desc("Use C++ comments to indicate occurence of code expansion"),
46 cl::cat(GICombinerEmitterCat));
47 static cl::opt<bool> StopAfterParse(
48 "gicombiner-stop-after-parse",
49 cl::desc("Stop processing after parsing rules and dump state"),
50 cl::cat(GICombinerEmitterCat));
51 static cl::opt<bool> StopAfterBuild(
52 "gicombiner-stop-after-build",
53 cl::desc("Stop processing after building the match tree"),
54 cl::cat(GICombinerEmitterCat));
57 typedef uint64_t RuleID;
59 // We're going to be referencing the same small strings quite a lot for operand
60 // names and the like. Make their lifetime management simple with a global
64 StringRef insertStrTab(StringRef S) {
67 return StrTab.insert(S).first->first();
70 class format_partition_name {
71 const GIMatchTree &Tree;
75 format_partition_name(const GIMatchTree &Tree, unsigned Idx)
76 : Tree(Tree), Idx(Idx) {}
77 void print(raw_ostream &OS) const {
78 Tree.getPartitioner()->emitPartitionName(OS, Idx);
81 raw_ostream &operator<<(raw_ostream &OS, const format_partition_name &Fmt) {
86 /// Declares data that is passed from the match stage to the apply stage.
88 /// The symbol used in the tablegen patterns
89 StringRef PatternSymbol;
90 /// The data type for the variable
92 /// The name of the variable as declared in the generated matcher.
93 std::string VariableName;
96 MatchDataInfo(StringRef PatternSymbol, StringRef Type, StringRef VariableName)
97 : PatternSymbol(PatternSymbol), Type(Type), VariableName(VariableName) {}
99 StringRef getPatternSymbol() const { return PatternSymbol; };
100 StringRef getType() const { return Type; };
101 StringRef getVariableName() const { return VariableName; };
105 StringRef PatternSymbol;
108 RootInfo(StringRef PatternSymbol) : PatternSymbol(PatternSymbol) {}
110 StringRef getPatternSymbol() const { return PatternSymbol; }
116 using const_matchdata_iterator = std::vector<MatchDataInfo>::const_iterator;
119 const GIMatchDagInstr *N;
120 const GIMatchDagOperand *Op;
121 const DagInit *Matcher;
124 VarInfo(const GIMatchDagInstr *N, const GIMatchDagOperand *Op,
125 const DagInit *Matcher)
126 : N(N), Op(Op), Matcher(Matcher) {}
130 /// A unique ID for this rule
131 /// ID's are used for debugging and run-time disabling of rules among other
135 /// A unique ID that can be used for anonymous objects belonging to this rule.
136 /// Used to create unique names in makeNameForAnon*() without making tests
140 /// The record defining this rule.
141 const Record &TheDef;
143 /// The roots of a match. These are the leaves of the DAG that are closest to
144 /// the end of the function. I.e. the nodes that are encountered without
145 /// following any edges of the DAG described by the pattern as we work our way
146 /// from the bottom of the function to the top.
147 std::vector<RootInfo> Roots;
151 /// A block of arbitrary C++ to finish testing the match.
152 /// FIXME: This is a temporary measure until we have actual pattern matching
153 const CodeInit *MatchingFixupCode = nullptr;
155 /// The MatchData defined by the match stage and required by the apply stage.
156 /// This allows the plumbing of arbitrary data from C++ predicates between the
159 /// For example, suppose you have:
160 /// %A = <some-constant-expr>
161 /// %0 = G_ADD %1, %A
162 /// you could define a GIMatchPredicate that walks %A, constant folds as much
163 /// as possible and returns an APInt containing the discovered constant. You
164 /// could then declare:
165 /// def apint : GIDefMatchData<"APInt">;
166 /// add it to the rule with:
167 /// (defs root:$root, apint:$constant)
168 /// evaluate it in the pattern with a C++ function that takes a
169 /// MachineOperand& and an APInt& with:
170 /// (match [{MIR %root = G_ADD %0, %A }],
171 /// (constantfold operand:$A, apint:$constant))
172 /// and finally use it in the apply stage with:
173 /// (apply (create_operand
174 /// [{ MachineOperand::CreateImm(${constant}.getZExtValue());
175 /// ]}, apint:$constant),
176 /// [{MIR %root = FOO %0, %constant }])
177 std::vector<MatchDataInfo> MatchDataDecls;
179 void declareMatchData(StringRef PatternSymbol, StringRef Type,
182 bool parseInstructionMatcher(const CodeGenTarget &Target, StringInit *ArgName,
184 StringMap<std::vector<VarInfo>> &NamedEdgeDefs,
185 StringMap<std::vector<VarInfo>> &NamedEdgeUses);
186 bool parseWipMatchOpcodeMatcher(const CodeGenTarget &Target,
187 StringInit *ArgName, const Init &Arg);
190 CombineRule(const CodeGenTarget &Target, GIMatchDagContext &Ctx, RuleID ID,
192 : ID(ID), TheDef(R), MatchDag(Ctx) {}
193 CombineRule(const CombineRule &) = delete;
196 bool parseMatcher(const CodeGenTarget &Target);
198 RuleID getID() const { return ID; }
199 unsigned allocUID() { return UID++; }
200 StringRef getName() const { return TheDef.getName(); }
201 const Record &getDef() const { return TheDef; }
202 const CodeInit *getMatchingFixupCode() const { return MatchingFixupCode; }
203 size_t getNumRoots() const { return Roots.size(); }
205 GIMatchDag &getMatchDag() { return MatchDag; }
206 const GIMatchDag &getMatchDag() const { return MatchDag; }
208 using const_root_iterator = std::vector<RootInfo>::const_iterator;
209 const_root_iterator roots_begin() const { return Roots.begin(); }
210 const_root_iterator roots_end() const { return Roots.end(); }
211 iterator_range<const_root_iterator> roots() const {
212 return llvm::make_range(Roots.begin(), Roots.end());
215 iterator_range<const_matchdata_iterator> matchdata_decls() const {
216 return make_range(MatchDataDecls.begin(), MatchDataDecls.end());
219 /// Export expansions for this rule
220 void declareExpansions(CodeExpansions &Expansions) const {
221 for (const auto &I : matchdata_decls())
222 Expansions.declare(I.getPatternSymbol(), I.getVariableName());
225 /// The matcher will begin from the roots and will perform the match by
226 /// traversing the edges to cover the whole DAG. This function reverses DAG
227 /// edges such that everything is reachable from a root. This is part of the
228 /// preparation work for flattening the DAG into a tree.
229 void reorientToRoots() {
230 SmallSet<const GIMatchDagInstr *, 5> Roots;
231 SmallSet<const GIMatchDagInstr *, 5> Visited;
232 SmallSet<GIMatchDagEdge *, 20> EdgesRemaining;
234 for (auto &I : MatchDag.roots()) {
238 for (auto &I : MatchDag.edges())
239 EdgesRemaining.insert(I);
241 bool Progressed = false;
242 SmallSet<GIMatchDagEdge *, 20> EdgesToRemove;
243 while (!EdgesRemaining.empty()) {
244 for (auto EI = EdgesRemaining.begin(), EE = EdgesRemaining.end();
246 if (Visited.count((*EI)->getFromMI())) {
247 if (Roots.count((*EI)->getToMI()))
248 PrintError(TheDef.getLoc(), "One or more roots are unnecessary");
249 Visited.insert((*EI)->getToMI());
250 EdgesToRemove.insert(*EI);
254 for (GIMatchDagEdge *ToRemove : EdgesToRemove)
255 EdgesRemaining.erase(ToRemove);
256 EdgesToRemove.clear();
258 for (auto EI = EdgesRemaining.begin(), EE = EdgesRemaining.end();
260 if (Visited.count((*EI)->getToMI())) {
262 Visited.insert((*EI)->getToMI());
263 EdgesToRemove.insert(*EI);
266 for (GIMatchDagEdge *ToRemove : EdgesToRemove)
267 EdgesRemaining.erase(ToRemove);
268 EdgesToRemove.clear();
272 LLVM_DEBUG(dbgs() << "No progress\n");
280 /// A convenience function to check that an Init refers to a specific def. This
281 /// is primarily useful for testing for defs and similar in DagInit's since
282 /// DagInit's support any type inside them.
283 static bool isSpecificDef(const Init &N, StringRef Def) {
284 if (const DefInit *OpI = dyn_cast<DefInit>(&N))
285 if (OpI->getDef()->getName() == Def)
290 /// A convenience function to check that an Init refers to a def that is a
291 /// subclass of the given class and coerce it to a def if it is. This is
292 /// primarily useful for testing for subclasses of GIMatchKind and similar in
293 /// DagInit's since DagInit's support any type inside them.
294 static Record *getDefOfSubClass(const Init &N, StringRef Cls) {
295 if (const DefInit *OpI = dyn_cast<DefInit>(&N))
296 if (OpI->getDef()->isSubClassOf(Cls))
297 return OpI->getDef();
301 /// A convenience function to check that an Init refers to a dag whose operator
302 /// is a specific def and coerce it to a dag if it is. This is primarily useful
303 /// for testing for subclasses of GIMatchKind and similar in DagInit's since
304 /// DagInit's support any type inside them.
305 static const DagInit *getDagWithSpecificOperator(const Init &N,
307 if (const DagInit *I = dyn_cast<DagInit>(&N))
308 if (I->getNumArgs() > 0)
309 if (const DefInit *OpI = dyn_cast<DefInit>(I->getOperator()))
310 if (OpI->getDef()->getName() == Name)
315 /// A convenience function to check that an Init refers to a dag whose operator
316 /// is a def that is a subclass of the given class and coerce it to a dag if it
317 /// is. This is primarily useful for testing for subclasses of GIMatchKind and
318 /// similar in DagInit's since DagInit's support any type inside them.
319 static const DagInit *getDagWithOperatorOfSubClass(const Init &N,
321 if (const DagInit *I = dyn_cast<DagInit>(&N))
322 if (I->getNumArgs() > 0)
323 if (const DefInit *OpI = dyn_cast<DefInit>(I->getOperator()))
324 if (OpI->getDef()->isSubClassOf(Cls))
329 StringRef makeNameForAnonInstr(CombineRule &Rule) {
330 return insertStrTab(to_string(
331 format("__anon%" PRIu64 "_%u", Rule.getID(), Rule.allocUID())));
334 StringRef makeDebugName(CombineRule &Rule, StringRef Name) {
335 return insertStrTab(Name.empty() ? makeNameForAnonInstr(Rule) : StringRef(Name));
338 StringRef makeNameForAnonPredicate(CombineRule &Rule) {
339 return insertStrTab(to_string(
340 format("__anonpred%" PRIu64 "_%u", Rule.getID(), Rule.allocUID())));
343 void CombineRule::declareMatchData(StringRef PatternSymbol, StringRef Type,
345 MatchDataDecls.emplace_back(PatternSymbol, Type, VarName);
348 bool CombineRule::parseDefs() {
349 NamedRegionTimer T("parseDefs", "Time spent parsing the defs", "Rule Parsing",
350 "Time spent on rule parsing", TimeRegions);
351 DagInit *Defs = TheDef.getValueAsDag("Defs");
353 if (Defs->getOperatorAsDef(TheDef.getLoc())->getName() != "defs") {
354 PrintError(TheDef.getLoc(), "Expected defs operator");
358 for (unsigned I = 0, E = Defs->getNumArgs(); I < E; ++I) {
359 // Roots should be collected into Roots
360 if (isSpecificDef(*Defs->getArg(I), "root")) {
361 Roots.emplace_back(Defs->getArgNameStr(I));
365 // Subclasses of GIDefMatchData should declare that this rule needs to pass
366 // data from the match stage to the apply stage, and ensure that the
367 // generated matcher has a suitable variable for it to do so.
368 if (Record *MatchDataRec =
369 getDefOfSubClass(*Defs->getArg(I), "GIDefMatchData")) {
370 declareMatchData(Defs->getArgNameStr(I),
371 MatchDataRec->getValueAsString("Type"),
372 llvm::to_string(llvm::format("MatchData%" PRIu64, ID)));
376 // Otherwise emit an appropriate error message.
377 if (getDefOfSubClass(*Defs->getArg(I), "GIDefKind"))
378 PrintError(TheDef.getLoc(),
379 "This GIDefKind not implemented in tablegen");
380 else if (getDefOfSubClass(*Defs->getArg(I), "GIDefKindWithArgs"))
381 PrintError(TheDef.getLoc(),
382 "This GIDefKindWithArgs not implemented in tablegen");
384 PrintError(TheDef.getLoc(),
385 "Expected a subclass of GIDefKind or a sub-dag whose "
386 "operator is of type GIDefKindWithArgs");
391 PrintError(TheDef.getLoc(), "Combine rules must have at least one root");
397 // Parse an (Instruction $a:Arg1, $b:Arg2, ...) matcher. Edges are formed
398 // between matching operand names between different matchers.
399 bool CombineRule::parseInstructionMatcher(
400 const CodeGenTarget &Target, StringInit *ArgName, const Init &Arg,
401 StringMap<std::vector<VarInfo>> &NamedEdgeDefs,
402 StringMap<std::vector<VarInfo>> &NamedEdgeUses) {
403 if (const DagInit *Matcher =
404 getDagWithOperatorOfSubClass(Arg, "Instruction")) {
406 Target.getInstruction(Matcher->getOperatorAsDef(TheDef.getLoc()));
408 StringRef Name = ArgName ? ArgName->getValue() : "";
411 MatchDag.addInstrNode(makeDebugName(*this, Name), insertStrTab(Name),
412 MatchDag.getContext().makeOperandList(Instr));
414 N->setOpcodeAnnotation(&Instr);
415 const auto &P = MatchDag.addPredicateNode<GIMatchDagOpcodePredicate>(
416 makeNameForAnonPredicate(*this), Instr);
417 MatchDag.addPredicateDependency(N, nullptr, P, &P->getOperandInfo()["mi"]);
419 for (const auto &NameInit : Matcher->getArgNames()) {
420 StringRef Name = insertStrTab(NameInit->getAsUnquotedString());
423 N->assignNameToOperand(OpIdx, Name);
425 // Record the endpoints of any named edges. We'll add the cartesian
426 // product of edges later.
427 const auto &InstrOperand = N->getOperandInfo()[OpIdx];
428 if (InstrOperand.isDef()) {
429 NamedEdgeDefs.try_emplace(Name);
430 NamedEdgeDefs[Name].emplace_back(N, &InstrOperand, Matcher);
432 NamedEdgeUses.try_emplace(Name);
433 NamedEdgeUses[Name].emplace_back(N, &InstrOperand, Matcher);
436 if (InstrOperand.isDef()) {
437 if (find_if(Roots, [&](const RootInfo &X) {
438 return X.getPatternSymbol() == Name;
452 // Parse the wip_match_opcode placeholder that's temporarily present in lieu of
453 // implementing macros or choices between two matchers.
454 bool CombineRule::parseWipMatchOpcodeMatcher(const CodeGenTarget &Target,
457 if (const DagInit *Matcher =
458 getDagWithSpecificOperator(Arg, "wip_match_opcode")) {
459 StringRef Name = ArgName ? ArgName->getValue() : "";
462 MatchDag.addInstrNode(makeDebugName(*this, Name), insertStrTab(Name),
463 MatchDag.getContext().makeEmptyOperandList());
465 if (find_if(Roots, [&](const RootInfo &X) {
466 return ArgName && X.getPatternSymbol() == ArgName->getValue();
471 const auto &P = MatchDag.addPredicateNode<GIMatchDagOneOfOpcodesPredicate>(
472 makeNameForAnonPredicate(*this));
473 MatchDag.addPredicateDependency(N, nullptr, P, &P->getOperandInfo()["mi"]);
474 // Each argument is an opcode that will pass this predicate. Add them all to
475 // the predicate implementation
476 for (const auto &Arg : Matcher->getArgs()) {
477 Record *OpcodeDef = getDefOfSubClass(*Arg, "Instruction");
479 P->addOpcode(&Target.getInstruction(OpcodeDef));
482 PrintError(TheDef.getLoc(),
483 "Arguments to wip_match_opcode must be instructions");
490 bool CombineRule::parseMatcher(const CodeGenTarget &Target) {
491 NamedRegionTimer T("parseMatcher", "Time spent parsing the matcher",
492 "Rule Parsing", "Time spent on rule parsing", TimeRegions);
493 StringMap<std::vector<VarInfo>> NamedEdgeDefs;
494 StringMap<std::vector<VarInfo>> NamedEdgeUses;
495 DagInit *Matchers = TheDef.getValueAsDag("Match");
497 if (Matchers->getOperatorAsDef(TheDef.getLoc())->getName() != "match") {
498 PrintError(TheDef.getLoc(), "Expected match operator");
502 if (Matchers->getNumArgs() == 0) {
503 PrintError(TheDef.getLoc(), "Matcher is empty");
507 // The match section consists of a list of matchers and predicates. Parse each
508 // one and add the equivalent GIMatchDag nodes, predicates, and edges.
509 for (unsigned I = 0; I < Matchers->getNumArgs(); ++I) {
510 if (parseInstructionMatcher(Target, Matchers->getArgName(I),
511 *Matchers->getArg(I), NamedEdgeDefs,
515 if (parseWipMatchOpcodeMatcher(Target, Matchers->getArgName(I),
516 *Matchers->getArg(I)))
520 // Parse arbitrary C++ code we have in lieu of supporting MIR matching
521 if (const CodeInit *CodeI = dyn_cast<CodeInit>(Matchers->getArg(I))) {
522 assert(!MatchingFixupCode &&
523 "Only one block of arbitrary code is currently permitted");
524 MatchingFixupCode = CodeI;
525 MatchDag.setHasPostMatchPredicate(true);
529 PrintError(TheDef.getLoc(),
530 "Expected a subclass of GIMatchKind or a sub-dag whose "
531 "operator is either of a GIMatchKindWithArgs or Instruction");
532 PrintNote("Pattern was `" + Matchers->getArg(I)->getAsString() + "'");
536 // Add the cartesian product of use -> def edges.
537 bool FailedToAddEdges = false;
538 for (const auto &NameAndDefs : NamedEdgeDefs) {
539 if (NameAndDefs.getValue().size() > 1) {
540 PrintError(TheDef.getLoc(),
541 "Two different MachineInstrs cannot def the same vreg");
542 for (const auto &NameAndDefOp : NameAndDefs.getValue())
543 PrintNote("in " + to_string(*NameAndDefOp.N) + " created from " +
544 to_string(*NameAndDefOp.Matcher) + "");
545 FailedToAddEdges = true;
547 const auto &Uses = NamedEdgeUses[NameAndDefs.getKey()];
548 for (const VarInfo &DefVar : NameAndDefs.getValue()) {
549 for (const VarInfo &UseVar : Uses) {
550 MatchDag.addEdge(insertStrTab(NameAndDefs.getKey()), UseVar.N, UseVar.Op,
551 DefVar.N, DefVar.Op);
555 if (FailedToAddEdges)
558 // If a variable is referenced in multiple use contexts then we need a
559 // predicate to confirm they are the same operand. We can elide this if it's
560 // also referenced in a def context and we're traversing the def-use chain
561 // from the def to the uses but we can't know which direction we're going
562 // until after reorientToRoots().
563 for (const auto &NameAndUses : NamedEdgeUses) {
564 const auto &Uses = NameAndUses.getValue();
565 if (Uses.size() > 1) {
566 const auto &LeadingVar = Uses.front();
567 for (const auto &Var : ArrayRef<VarInfo>(Uses).drop_front()) {
568 // Add a predicate for each pair until we've covered the whole
569 // equivalence set. We could test the whole set in a single predicate
570 // but that means we can't test any equivalence until all the MO's are
571 // available which can lead to wasted work matching the DAG when this
572 // predicate can already be seen to have failed.
574 // We have a similar problem due to the need to wait for a particular MO
575 // before being able to test any of them. However, that is mitigated by
576 // the order in which we build the DAG. We build from the roots outwards
577 // so by using the first recorded use in all the predicates, we are
578 // making the dependency on one of the earliest visited references in
579 // the DAG. It's not guaranteed once the generated matcher is optimized
580 // (because the factoring the common portions of rules might change the
581 // visit order) but this should mean that these predicates depend on the
582 // first MO to become available.
583 const auto &P = MatchDag.addPredicateNode<GIMatchDagSameMOPredicate>(
584 makeNameForAnonPredicate(*this));
585 MatchDag.addPredicateDependency(LeadingVar.N, LeadingVar.Op, P,
586 &P->getOperandInfo()["mi0"]);
587 MatchDag.addPredicateDependency(Var.N, Var.Op, P,
588 &P->getOperandInfo()["mi1"]);
595 class GICombinerEmitter {
597 const CodeGenTarget &Target;
599 std::vector<std::unique_ptr<CombineRule>> Rules;
600 GIMatchDagContext MatchDagCtx;
602 std::unique_ptr<CombineRule> makeCombineRule(const Record &R);
604 void gatherRules(std::vector<std::unique_ptr<CombineRule>> &ActiveRules,
605 const std::vector<Record *> &&RulesAndGroups);
608 explicit GICombinerEmitter(RecordKeeper &RK, const CodeGenTarget &Target,
609 StringRef Name, Record *Combiner);
610 ~GICombinerEmitter() {}
612 StringRef getClassName() const {
613 return Combiner->getValueAsString("Classname");
615 void run(raw_ostream &OS);
617 /// Emit the name matcher (guarded by #ifndef NDEBUG) used to disable rules in
618 /// response to the generated cl::opt.
619 void emitNameMatcher(raw_ostream &OS) const;
621 void generateDeclarationsCodeForTree(raw_ostream &OS, const GIMatchTree &Tree) const;
622 void generateCodeForTree(raw_ostream &OS, const GIMatchTree &Tree,
623 StringRef Indent) const;
626 GICombinerEmitter::GICombinerEmitter(RecordKeeper &RK,
627 const CodeGenTarget &Target,
628 StringRef Name, Record *Combiner)
629 : Name(Name), Target(Target), Combiner(Combiner) {}
631 void GICombinerEmitter::emitNameMatcher(raw_ostream &OS) const {
632 std::vector<std::pair<std::string, std::string>> Cases;
633 Cases.reserve(Rules.size());
635 for (const CombineRule &EnumeratedRule : make_pointee_range(Rules)) {
637 raw_string_ostream SS(Code);
638 SS << "return " << EnumeratedRule.getID() << ";\n";
639 Cases.push_back(std::make_pair(EnumeratedRule.getName(), SS.str()));
642 OS << "static Optional<uint64_t> getRuleIdxForIdentifier(StringRef "
643 "RuleIdentifier) {\n"
645 << " // getAtInteger(...) returns false on success\n"
646 << " bool Parsed = !RuleIdentifier.getAsInteger(0, I);\n"
649 << "#ifndef NDEBUG\n";
650 StringMatcher Matcher("RuleIdentifier", Cases, OS);
652 OS << "#endif // ifndef NDEBUG\n\n"
657 std::unique_ptr<CombineRule>
658 GICombinerEmitter::makeCombineRule(const Record &TheDef) {
659 std::unique_ptr<CombineRule> Rule =
660 std::make_unique<CombineRule>(Target, MatchDagCtx, NumPatternTotal, TheDef);
662 if (!Rule->parseDefs())
664 if (!Rule->parseMatcher(Target))
667 Rule->reorientToRoots();
670 dbgs() << "Parsed rule defs/match for '" << Rule->getName() << "'\n";
671 Rule->getMatchDag().dump();
672 Rule->getMatchDag().writeDOTGraph(dbgs(), Rule->getName());
677 // For now, don't support traversing from def to use. We'll come back to
678 // this later once we have the algorithm changes to support it.
679 bool EmittedDefToUseError = false;
680 for (const auto &E : Rule->getMatchDag().edges()) {
681 if (E->isDefToUse()) {
682 if (!EmittedDefToUseError) {
685 "Generated state machine cannot lookup uses from a def (yet)");
686 EmittedDefToUseError = true;
688 PrintNote("Node " + to_string(*E->getFromMI()));
689 PrintNote("Node " + to_string(*E->getToMI()));
690 PrintNote("Edge " + to_string(*E));
693 if (EmittedDefToUseError)
696 // For now, don't support multi-root rules. We'll come back to this later
697 // once we have the algorithm changes to support it.
698 if (Rule->getNumRoots() > 1) {
699 PrintError(TheDef.getLoc(), "Multi-root matches are not supported (yet)");
705 /// Recurse into GICombineGroup's and flatten the ruleset into a simple list.
706 void GICombinerEmitter::gatherRules(
707 std::vector<std::unique_ptr<CombineRule>> &ActiveRules,
708 const std::vector<Record *> &&RulesAndGroups) {
709 for (Record *R : RulesAndGroups) {
710 if (R->isValueUnset("Rules")) {
711 std::unique_ptr<CombineRule> Rule = makeCombineRule(*R);
712 if (Rule == nullptr) {
713 PrintError(R->getLoc(), "Failed to parse rule");
716 ActiveRules.emplace_back(std::move(Rule));
719 gatherRules(ActiveRules, R->getValueAsListOfDefs("Rules"));
723 void GICombinerEmitter::generateCodeForTree(raw_ostream &OS,
724 const GIMatchTree &Tree,
725 StringRef Indent) const {
726 if (Tree.getPartitioner() != nullptr) {
727 Tree.getPartitioner()->generatePartitionSelectorCode(OS, Indent);
728 for (const auto &EnumChildren : enumerate(Tree.children())) {
729 OS << Indent << "if (Partition == " << EnumChildren.index() << " /* "
730 << format_partition_name(Tree, EnumChildren.index()) << " */) {\n";
731 generateCodeForTree(OS, EnumChildren.value(), (Indent + " ").str());
732 OS << Indent << "}\n";
737 bool AnyFullyTested = false;
738 for (const auto &Leaf : Tree.possible_leaves()) {
739 OS << Indent << "// Leaf name: " << Leaf.getName() << "\n";
741 const CombineRule *Rule = Leaf.getTargetData<CombineRule>();
742 const Record &RuleDef = Rule->getDef();
744 OS << Indent << "// Rule: " << RuleDef.getName() << "\n"
745 << Indent << "if (!isRuleDisabled(" << Rule->getID() << ")) {\n";
747 CodeExpansions Expansions;
748 for (const auto &VarBinding : Leaf.var_bindings()) {
749 if (VarBinding.isInstr())
750 Expansions.declare(VarBinding.getName(),
751 "MIs[" + to_string(VarBinding.getInstrID()) + "]");
753 Expansions.declare(VarBinding.getName(),
754 "MIs[" + to_string(VarBinding.getInstrID()) +
756 to_string(VarBinding.getOpIdx()) + ")");
758 Rule->declareExpansions(Expansions);
760 DagInit *Applyer = RuleDef.getValueAsDag("Apply");
761 if (Applyer->getOperatorAsDef(RuleDef.getLoc())->getName() !=
763 PrintError(RuleDef.getLoc(), "Expected apply operator");
767 OS << Indent << " if (1\n";
769 // Attempt to emit code for any untested predicates left over. Note that
770 // isFullyTested() will remain false even if we succeed here and therefore
771 // combine rule elision will not be performed. This is because we do not
772 // know if there's any connection between the predicates for each leaf and
773 // therefore can't tell if one makes another unreachable. Ideally, the
774 // partitioner(s) would be sufficiently complete to prevent us from having
775 // untested predicates left over.
776 for (const GIMatchDagPredicate *Predicate : Leaf.untested_predicates()) {
777 if (Predicate->generateCheckCode(OS, (Indent + " ").str(),
780 PrintError(RuleDef.getLoc(),
781 "Unable to test predicate used in rule");
783 "This indicates an incomplete implementation in tablegen");
784 Predicate->print(errs());
787 << "llvm_unreachable(\"TableGen did not emit complete code for this "
792 if (Rule->getMatchingFixupCode() &&
793 !Rule->getMatchingFixupCode()->getValue().empty()) {
794 // FIXME: Single-use lambda's like this are a serious compile-time
795 // performance and memory issue. It's convenient for this early stage to
796 // defer some work to successive patches but we need to eliminate this
797 // before the ruleset grows to small-moderate size. Last time, it became
798 // a big problem for low-mem systems around the 500 rule mark but by the
799 // time we grow that large we should have merged the ISel match table
800 // mechanism with the Combiner.
801 OS << Indent << " && [&]() {\n"
803 << CodeExpander(Rule->getMatchingFixupCode()->getValue(), Expansions,
804 Rule->getMatchingFixupCode()->getLoc(), ShowExpansions)
806 << Indent << " return true;\n"
809 OS << ") {\n" << Indent << " ";
811 if (const CodeInit *Code = dyn_cast<CodeInit>(Applyer->getArg(0))) {
812 OS << CodeExpander(Code->getAsUnquotedString(), Expansions,
813 Code->getLoc(), ShowExpansions)
815 << Indent << " return true;\n"
818 PrintError(RuleDef.getLoc(), "Expected apply code block");
822 OS << Indent << "}\n";
824 assert(Leaf.isFullyTraversed());
826 // If we didn't have any predicates left over and we're not using the
827 // trap-door we have to support arbitrary C++ code while we're migrating to
828 // the declarative style then we know that subsequent leaves are
830 if (Leaf.isFullyTested() &&
831 (!Rule->getMatchingFixupCode() ||
832 Rule->getMatchingFixupCode()->getValue().empty())) {
833 AnyFullyTested = true;
835 << "llvm_unreachable(\"Combine rule elision was incorrect\");\n"
836 << Indent << "return false;\n";
840 OS << Indent << "return false;\n";
843 void GICombinerEmitter::run(raw_ostream &OS) {
844 gatherRules(Rules, Combiner->getValueAsListOfDefs("Rules"));
845 if (StopAfterParse) {
846 MatchDagCtx.print(errs());
847 PrintNote(Combiner->getLoc(),
848 "Terminating due to -gicombiner-stop-after-parse");
852 PrintFatalError(Combiner->getLoc(), "Failed to parse one or more rules");
853 LLVM_DEBUG(dbgs() << "Optimizing tree for " << Rules.size() << " rules\n");
854 std::unique_ptr<GIMatchTree> Tree;
856 NamedRegionTimer T("Optimize", "Time spent optimizing the combiner",
857 "Code Generation", "Time spent generating code",
860 GIMatchTreeBuilder TreeBuilder(0);
861 for (const auto &Rule : Rules) {
862 bool HadARoot = false;
863 for (const auto &Root : enumerate(Rule->getMatchDag().roots())) {
864 TreeBuilder.addLeaf(Rule->getName(), Root.index(), Rule->getMatchDag(),
869 PrintFatalError(Rule->getDef().getLoc(), "All rules must have a root");
872 Tree = TreeBuilder.run();
874 if (StopAfterBuild) {
875 Tree->writeDOTGraph(outs());
876 PrintNote(Combiner->getLoc(),
877 "Terminating due to -gicombiner-stop-after-build");
881 NamedRegionTimer T("Emit", "Time spent emitting the combiner",
882 "Code Generation", "Time spent generating code",
884 OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_DEPS\n"
885 << "#include \"llvm/ADT/SparseBitVector.h\"\n"
886 << "namespace llvm {\n"
887 << "extern cl::OptionCategory GICombinerOptionCategory;\n"
888 << "} // end namespace llvm\n"
889 << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_DEPS\n\n";
891 OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_H\n"
892 << "class " << getClassName() << " {\n"
893 << " SparseBitVector<> DisabledRules;\n"
896 << " bool parseCommandLineOption();\n"
897 << " bool isRuleDisabled(unsigned ID) const;\n"
898 << " bool setRuleDisabled(StringRef RuleIdentifier);\n"
900 << " bool tryCombineAll(\n"
901 << " GISelChangeObserver &Observer,\n"
902 << " MachineInstr &MI,\n"
903 << " MachineIRBuilder &B,\n"
904 << " CombinerHelper &Helper) const;\n"
909 OS << "bool " << getClassName()
910 << "::setRuleDisabled(StringRef RuleIdentifier) {\n"
911 << " std::pair<StringRef, StringRef> RangePair = "
912 "RuleIdentifier.split('-');\n"
913 << " if (!RangePair.second.empty()) {\n"
914 << " const auto First = getRuleIdxForIdentifier(RangePair.first);\n"
915 << " const auto Last = getRuleIdxForIdentifier(RangePair.second);\n"
916 << " if (!First.hasValue() || !Last.hasValue())\n"
917 << " return false;\n"
918 << " if (First >= Last)\n"
919 << " report_fatal_error(\"Beginning of range should be before end of "
921 << " for (auto I = First.getValue(); I < Last.getValue(); ++I)\n"
922 << " DisabledRules.set(I);\n"
925 << " const auto I = getRuleIdxForIdentifier(RangePair.first);\n"
926 << " if (!I.hasValue())\n"
927 << " return false;\n"
928 << " DisabledRules.set(I.getValue());\n"
931 << " return false;\n"
934 OS << "bool " << getClassName()
935 << "::isRuleDisabled(unsigned RuleID) const {\n"
936 << " return DisabledRules.test(RuleID);\n"
938 OS << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_H\n\n";
940 OS << "#ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n"
942 << "cl::list<std::string> " << Name << "Option(\n"
943 << " \"" << Name.lower() << "-disable-rule\",\n"
944 << " cl::desc(\"Disable one or more combiner rules temporarily in "
945 << "the " << Name << " pass\"),\n"
946 << " cl::CommaSeparated,\n"
948 << " cl::cat(GICombinerOptionCategory));\n"
950 << "bool " << getClassName() << "::parseCommandLineOption() {\n"
951 << " for (const auto &Identifier : " << Name << "Option)\n"
952 << " if (!setRuleDisabled(Identifier))\n"
953 << " return false;\n"
957 OS << "bool " << getClassName() << "::tryCombineAll(\n"
958 << " GISelChangeObserver &Observer,\n"
959 << " MachineInstr &MI,\n"
960 << " MachineIRBuilder &B,\n"
961 << " CombinerHelper &Helper) const {\n"
962 << " MachineBasicBlock *MBB = MI.getParent();\n"
963 << " MachineFunction *MF = MBB->getParent();\n"
964 << " MachineRegisterInfo &MRI = MF->getRegInfo();\n"
965 << " SmallVector<MachineInstr *, 8> MIs = { &MI };\n\n"
966 << " (void)MBB; (void)MF; (void)MRI;\n\n";
968 OS << " // Match data\n";
969 for (const auto &Rule : Rules)
970 for (const auto &I : Rule->matchdata_decls())
971 OS << " " << I.getType() << " " << I.getVariableName() << ";\n";
974 OS << " int Partition = -1;\n";
975 generateCodeForTree(OS, *Tree, " ");
976 OS << "\n return false;\n"
978 << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n";
981 } // end anonymous namespace
983 //===----------------------------------------------------------------------===//
986 void EmitGICombiner(RecordKeeper &RK, raw_ostream &OS) {
987 CodeGenTarget Target(RK);
988 emitSourceFileHeader("Global Combiner", OS);
990 if (SelectedCombiners.empty())
991 PrintFatalError("No combiners selected with -combiners");
992 for (const auto &Combiner : SelectedCombiners) {
993 Record *CombinerDef = RK.getDef(Combiner);
995 PrintFatalError("Could not find " + Combiner);
996 GICombinerEmitter(RK, Target, Combiner, CombinerDef).run(OS);
998 NumPatternTotalStatistic = NumPatternTotal;