diff --git a/llvm/include/llvm/Target/GlobalISel/Combine.td b/llvm/include/llvm/Target/GlobalISel/Combine.td --- a/llvm/include/llvm/Target/GlobalISel/Combine.td +++ b/llvm/include/llvm/Target/GlobalISel/Combine.td @@ -89,6 +89,10 @@ class GIMatchKind; class GIMatchKindWithArgs; +/// In lieu of having proper macro support. Trivial one-off opcode checks can be +/// performed with this. +def wip_match_opcode : GIMatchKindWithArgs; + /// The operator at the root of a GICombineRule.Apply dag. def apply; /// All arguments of the apply operator must be subclasses of GIApplyKind, or @@ -99,26 +103,30 @@ def copy_prop : GICombineRule< (defs root:$d), - (match [{ return Helper.matchCombineCopy(${d}); }]), - (apply [{ Helper.applyCombineCopy(${d}); }])>; + (match (COPY $d, $s):$mi, + [{ return Helper.matchCombineCopy(*${mi}); }]), + (apply [{ Helper.applyCombineCopy(*${mi}); }])>; def trivial_combines : GICombineGroup<[copy_prop]>; def extending_loads : GICombineRule< (defs root:$root, extending_load_matchdata:$matchinfo), - (match [{ return Helper.matchCombineExtendingLoads(${root}, ${matchinfo}); }]), - (apply [{ Helper.applyCombineExtendingLoads(${root}, ${matchinfo}); }])>; + (match (wip_match_opcode G_LOAD, G_SEXTLOAD, G_ZEXTLOAD):$root, + [{ return Helper.matchCombineExtendingLoads(*${root}, ${matchinfo}); }]), + (apply [{ Helper.applyCombineExtendingLoads(*${root}, ${matchinfo}); }])>; def combines_for_extload: GICombineGroup<[extending_loads]>; def combine_indexed_load_store : GICombineRule< (defs root:$root, indexed_load_store_matchdata:$matchinfo), - (match [{ return Helper.matchCombineIndexedLoadStore(${root}, ${matchinfo}); }]), - (apply [{ Helper.applyCombineIndexedLoadStore(${root}, ${matchinfo}); }])>; + (match (wip_match_opcode G_LOAD, G_SEXTLOAD, G_ZEXTLOAD, G_STORE):$root, + [{ return Helper.matchCombineIndexedLoadStore(*${root}, ${matchinfo}); }]), + (apply [{ Helper.applyCombineIndexedLoadStore(*${root}, ${matchinfo}); }])>; // FIXME: Is there a reason this wasn't in tryCombine? I've left it out of // all_combines because it wasn't there. def elide_br_by_inverting_cond : GICombineRule< - (defs root:$d), - (match [{ return Helper.matchElideBrByInvertingCond(${d}); }]), - (apply [{ Helper.applyElideBrByInvertingCond(${d}); }])>; + (defs root:$root), + (match (wip_match_opcode G_BR):$root, + [{ return Helper.matchElideBrByInvertingCond(*${root}); }]), + (apply [{ Helper.applyElideBrByInvertingCond(*${root}); }])>; def all_combines : GICombineGroup<[trivial_combines, combines_for_extload, combine_indexed_load_store]>; diff --git a/llvm/test/TableGen/GICombinerEmitter/match-tree.td b/llvm/test/TableGen/GICombinerEmitter/match-tree.td new file mode 100644 --- /dev/null +++ b/llvm/test/TableGen/GICombinerEmitter/match-tree.td @@ -0,0 +1,142 @@ +// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ +// RUN: -combiners=MyCombinerHelper -gicombiner-stop-after-build %s \ +// RUN: -o %t.inc | FileCheck %s + +include "llvm/Target/Target.td" +include "llvm/Target/GlobalISel/Combine.td" + +def MyTargetISA : InstrInfo; +def MyTarget : Target { let InstructionSet = MyTargetISA; } + +def dummy; + +def R0 : Register<"r0"> { let Namespace = "MyTarget"; } +def GPR32 : RegisterClass<"MyTarget", [i32], 32, (add R0)>; +class I Pat> + : Instruction { + let Namespace = "MyTarget"; + let OutOperandList = OOps; + let InOperandList = IOps; + let Pattern = Pat; +} +def MOV : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; +def ADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>; +def SUB : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>; +def MUL : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>; +def TRUNC : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; +def SEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; +def ZEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; + +def Rule0 : GICombineRule< + (defs root:$d), + (match (MUL $t, $s1, $s2), + (SUB $d, $t, $s3)), + (apply [{ APPLY }])>; + +def Rule1 : GICombineRule< + (defs root:$d), + (match (MOV $s1, $s2), + (MOV $d, $s1)), + (apply [{ APPLY }])>; + +def Rule2 : GICombineRule< + (defs root:$d), + (match (MOV $d, $s)), + (apply [{ APPLY }])>; + +def Rule3 : GICombineRule< + (defs root:$d), + (match (MUL $t, $s1, $s2), + (ADD $d, $t, $s3), [{ A }]), + (apply [{ APPLY }])>; + +def Rule4 : GICombineRule< + (defs root:$d), + (match (ADD $d, $s1, $s2)), + (apply [{ APPLY }])>; + +def Rule5 : GICombineRule< + (defs root:$d), + (match (SUB $d, $s1, $s2)), + (apply [{ APPLY }])>; + +def Rule6 : GICombineRule< + (defs root:$d), + (match (SEXT $t, $s1), + (TRUNC $d, $t)), + (apply [{ APPLY }])>; + +def Rule7 : GICombineRule< + (defs root:$d), + (match (ZEXT $t, $s1), + (TRUNC $d, $t)), + (apply [{ APPLY }])>; + +def MyCombinerHelper: GICombinerHelper<"GenMyCombinerHelper", [ + Rule0, + Rule1, + Rule2, + Rule3, + Rule4, + Rule5, + Rule6, + Rule7 +]>; + +// CHECK-LABEL: digraph "matchtree" { +// CHECK-DAG: Node[[N0:0x[0-9a-f]+]] [shape=record,label="{MI[0].getOpcode()|4 partitions|Rule0,Rule1,Rule2,Rule3,Rule4,Rule5,Rule6,Rule7}"] +// CHECK-DAG: Node[[N1:0x[0-9a-f]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule0,Rule5}"] +// CHECK-DAG: Node[[N2:0x[0-9a-f]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule0,Rule5}"] +// CHECK-DAG: Node[[N3:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule0}"] +// CHECK-DAG: Node[[N4:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule5}"] +// CHECK-DAG: Node[[N5:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule5}"] +// CHECK-DAG: Node[[N6:0x[0-9a-f]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule1,Rule2}"] +// CHECK-DAG: Node[[N7:0x[0-9a-f]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule1,Rule2}"] +// CHECK-DAG: Node[[N8:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule1}"] +// CHECK-DAG: Node[[N9:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule2}"] +// CHECK-DAG: Node[[N10:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule2}"] +// CHECK-DAG: Node[[N11:0x[0-9a-f]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule3,Rule4}"] +// CHECK-DAG: Node[[N12:0x[0-9a-f]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule3,Rule4}"] +// CHECK-DAG: Node[[N13:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule3,Rule4}",color=red] +// CHECK-DAG: Node[[N14:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule4}"] +// CHECK-DAG: Node[[N15:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule4}"] +// CHECK-DAG: Node[[N16:0x[0-9a-f]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|1 partitions|Rule6,Rule7}"] +// CHECK-DAG: Node[[N17:0x[0-9a-f]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule6,Rule7}"] +// CHECK-DAG: Node[[N18:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule6}"] +// CHECK-DAG: Node[[N19:0x[0-9a-f]+]] [shape=record,label="{No partitioner|Rule7}"] + +// The most important partitioner is on the first opcode: +// CHECK-DAG: Node[[N0]] -> Node[[N1]] [label="#0 MyTarget::SUB"] +// CHECK-DAG: Node[[N0]] -> Node[[N6]] [label="#1 MyTarget::MOV"] +// CHECK-DAG: Node[[N0]] -> Node[[N11]] [label="#2 MyTarget::ADD"] +// CHECK-DAG: Node[[N0]] -> Node[[N16]] [label="#3 MyTarget::TRUNC"] + +// For, MI[0].getOpcode() == SUB, then has to determine whether it has a reg +// operand and follow that link. If it can't then Rule5 is the only choice as +// that rule is not constrained to a reg. +// CHECK-DAG: Node[[N1]] -> Node[[N2]] [label="#0 true"] +// CHECK-DAG: Node[[N1]] -> Node[[N5]] [label="#1 false"] + +// For, MI[0].getOpcode() == SUB && MI[0].getOperand(1).isReg(), if MI[1] is a +// MUL then it must be either Rule0 or Rule5. Rule0 is fully tested so Rule5 is +// unreachable. If it's not MUL then it must be Rule5. +// CHECK-DAG: Node[[N2]] -> Node[[N3]] [label="#0 MyTarget::MUL"] +// CHECK-DAG: Node[[N2]] -> Node[[N4]] [label="#1 * or nullptr"] + +// CHECK-DAG: Node[[N6]] -> Node[[N7]] [label="#0 true"] +// CHECK-DAG: Node[[N6]] -> Node[[N10]] [label="#1 false"] + +// CHECK-DAG: Node[[N7]] -> Node[[N8]] [label="#0 MyTarget::MOV"] +// CHECK-DAG: Node[[N7]] -> Node[[N9]] [label="#1 * or nullptr"] + +// CHECK-DAG: Node[[N11]] -> Node[[N12]] [label="#0 true"] +// CHECK-DAG: Node[[N11]] -> Node[[N15]] [label="#1 false"] + +// CHECK-DAG: Node[[N12]] -> Node[[N13]] [label="#0 MyTarget::MUL"] +// CHECK-DAG: Node[[N12]] -> Node[[N14]] [label="#1 * or nullptr"] + +// CHECK-DAG: Node[[N16]] -> Node[[N17]] [label="#0 true"] + +// CHECK-DAG: Node[[N17]] -> Node[[N18]] [label="#0 MyTarget::SEXT"] +// CHECK-DAG: Node[[N17]] -> Node[[N19]] [label="#1 MyTarget::ZEXT"] +// CHECK-LABEL: {{^}$}} diff --git a/llvm/utils/TableGen/GICombinerEmitter.cpp b/llvm/utils/TableGen/GICombinerEmitter.cpp --- a/llvm/utils/TableGen/GICombinerEmitter.cpp +++ b/llvm/utils/TableGen/GICombinerEmitter.cpp @@ -24,6 +24,7 @@ #include "GlobalISel/CodeExpander.h" #include "GlobalISel/CodeExpansions.h" #include "GlobalISel/GIMatchDag.h" +#include "GlobalISel/GIMatchTree.h" #include using namespace llvm; @@ -47,6 +48,10 @@ "gicombiner-stop-after-parse", cl::desc("Stop processing after parsing rules and dump state"), cl::cat(GICombinerEmitterCat)); +static cl::opt StopAfterBuild( + "gicombiner-stop-after-build", + cl::desc("Stop processing after building the match tree"), + cl::cat(GICombinerEmitterCat)); namespace { typedef uint64_t RuleID; @@ -62,6 +67,22 @@ return StrTab.insert(S).first->first(); } +class format_partition_name { + const GIMatchTree &Tree; + unsigned Idx; + +public: + format_partition_name(const GIMatchTree &Tree, unsigned Idx) + : Tree(Tree), Idx(Idx) {} + void print(raw_ostream &OS) const { + Tree.getPartitioner()->emitPartitionName(OS, Idx); + } +}; +raw_ostream &operator<<(raw_ostream &OS, const format_partition_name &Fmt) { + Fmt.print(OS); + return OS; +} + /// Declares data that is passed from the match stage to the apply stage. class MatchDataInfo { /// The symbol used in the tablegen patterns @@ -162,6 +183,8 @@ const Init &Arg, StringMap> &NamedEdgeDefs, StringMap> &NamedEdgeUses); + bool parseWipMatchOpcodeMatcher(const CodeGenTarget &Target, + StringInit *ArgName, const Init &Arg); public: CombineRule(const CodeGenTarget &Target, GIMatchDagContext &Ctx, RuleID ID, @@ -276,6 +299,20 @@ } /// A convenience function to check that an Init refers to a dag whose operator +/// is a specific def and coerce it to a dag if it is. This is primarily useful +/// for testing for subclasses of GIMatchKind and similar in DagInit's since +/// DagInit's support any type inside them. +static const DagInit *getDagWithSpecificOperator(const Init &N, + StringRef Name) { + if (const DagInit *I = dyn_cast(&N)) + if (I->getNumArgs() > 0) + if (const DefInit *OpI = dyn_cast(I->getOperator())) + if (OpI->getDef()->getName() == Name) + return I; + return nullptr; +} + +/// A convenience function to check that an Init refers to a dag whose operator /// is a def that is a subclass of the given class and coerce it to a dag if it /// is. This is primarily useful for testing for subclasses of GIMatchKind and /// similar in DagInit's since DagInit's support any type inside them. @@ -412,6 +449,44 @@ return false; } +// Parse the wip_match_opcode placeholder that's temporarily present in lieu of +// implementing macros or choices between two matchers. +bool CombineRule::parseWipMatchOpcodeMatcher(const CodeGenTarget &Target, + StringInit *ArgName, + const Init &Arg) { + if (const DagInit *Matcher = + getDagWithSpecificOperator(Arg, "wip_match_opcode")) { + StringRef Name = ArgName ? ArgName->getValue() : ""; + + GIMatchDagInstr *N = + MatchDag.addInstrNode(makeDebugName(*this, Name), insertStrTab(Name), + MatchDag.getContext().makeEmptyOperandList()); + + if (find_if(Roots, [&](const RootInfo &X) { + return ArgName && X.getPatternSymbol() == ArgName->getValue(); + }) != Roots.end()) { + N->setMatchRoot(); + } + + const auto &P = MatchDag.addPredicateNode( + makeNameForAnonPredicate(*this)); + MatchDag.addPredicateDependency(N, nullptr, P, &P->getOperandInfo()["mi"]); + // Each argument is an opcode that will pass this predicate. Add them all to + // the predicate implementation + for (const auto &Arg : Matcher->getArgs()) { + Record *OpcodeDef = getDefOfSubClass(*Arg, "Instruction"); + if (OpcodeDef) { + P->addOpcode(&Target.getInstruction(OpcodeDef)); + continue; + } + PrintError(TheDef.getLoc(), + "Arguments to wip_match_opcode must be instructions"); + return false; + } + return true; + } + return false; +} bool CombineRule::parseMatcher(const CodeGenTarget &Target) { NamedRegionTimer T("parseMatcher", "Time spent parsing the matcher", "Rule Parsing", "Time spent on rule parsing", TimeRegions); @@ -437,12 +512,17 @@ NamedEdgeUses)) continue; + if (parseWipMatchOpcodeMatcher(Target, Matchers->getArgName(I), + *Matchers->getArg(I))) + continue; + // Parse arbitrary C++ code we have in lieu of supporting MIR matching if (const CodeInit *CodeI = dyn_cast(Matchers->getArg(I))) { assert(!MatchingFixupCode && "Only one block of arbitrary code is currently permitted"); MatchingFixupCode = CodeI; + MatchDag.setHasPostMatchPredicate(true); continue; } @@ -537,7 +617,9 @@ /// Emit the name matcher (guarded by #ifndef NDEBUG) used to disable rules in /// response to the generated cl::opt. void emitNameMatcher(raw_ostream &OS) const; - void generateCodeForRule(raw_ostream &OS, const CombineRule *Rule, + + void generateDeclarationsCodeForTree(raw_ostream &OS, const GIMatchTree &Tree) const; + void generateCodeForTree(raw_ostream &OS, const GIMatchTree &Tree, StringRef Indent) const; }; @@ -592,6 +674,25 @@ if (StopAfterParse) return Rule; + // For now, don't support traversing from def to use. We'll come back to + // this later once we have the algorithm changes to support it. + bool EmittedDefToUseError = false; + for (const auto &E : Rule->getMatchDag().edges()) { + if (E->isDefToUse()) { + if (!EmittedDefToUseError) { + PrintError( + TheDef.getLoc(), + "Generated state machine cannot lookup uses from a def (yet)"); + EmittedDefToUseError = true; + } + PrintNote("Node " + to_string(*E->getFromMI())); + PrintNote("Node " + to_string(*E->getToMI())); + PrintNote("Edge " + to_string(*E)); + } + } + if (EmittedDefToUseError) + return nullptr; + // For now, don't support multi-root rules. We'll come back to this later // once we have the algorithm changes to support it. if (Rule->getNumRoots() > 1) { @@ -619,18 +720,40 @@ } } -void GICombinerEmitter::generateCodeForRule(raw_ostream &OS, - const CombineRule *Rule, +void GICombinerEmitter::generateCodeForTree(raw_ostream &OS, + const GIMatchTree &Tree, StringRef Indent) const { - { + if (Tree.getPartitioner() != nullptr) { + Tree.getPartitioner()->generatePartitionSelectorCode(OS, Indent); + for (const auto &EnumChildren : enumerate(Tree.children())) { + OS << Indent << "if (Partition == " << EnumChildren.index() << " /* " + << format_partition_name(Tree, EnumChildren.index()) << " */) {\n"; + generateCodeForTree(OS, EnumChildren.value(), (Indent + " ").str()); + OS << Indent << "}\n"; + } + return; + } + + bool AnyFullyTested = false; + for (const auto &Leaf : Tree.possible_leaves()) { + OS << Indent << "// Leaf name: " << Leaf.getName() << "\n"; + + const CombineRule *Rule = Leaf.getTargetData(); const Record &RuleDef = Rule->getDef(); OS << Indent << "// Rule: " << RuleDef.getName() << "\n" << Indent << "if (!isRuleDisabled(" << Rule->getID() << ")) {\n"; CodeExpansions Expansions; - for (const RootInfo &Root : Rule->roots()) { - Expansions.declare(Root.getPatternSymbol(), "MI"); + for (const auto &VarBinding : Leaf.var_bindings()) { + if (VarBinding.isInstr()) + Expansions.declare(VarBinding.getName(), + "MIs[" + to_string(VarBinding.getInstrID()) + "]"); + else + Expansions.declare(VarBinding.getName(), + "MIs[" + to_string(VarBinding.getInstrID()) + + "]->getOperand(" + + to_string(VarBinding.getOpIdx()) + ")"); } Rule->declareExpansions(Expansions); @@ -643,6 +766,29 @@ OS << Indent << " if (1\n"; + // Attempt to emit code for any untested predicates left over. Note that + // isFullyTested() will remain false even if we succeed here and therefore + // combine rule elision will not be performed. This is because we do not + // know if there's any connection between the predicates for each leaf and + // therefore can't tell if one makes another unreachable. Ideally, the + // partitioner(s) would be sufficiently complete to prevent us from having + // untested predicates left over. + for (const GIMatchDagPredicate *Predicate : Leaf.untested_predicates()) { + if (Predicate->generateCheckCode(OS, (Indent + " ").str(), + Expansions)) + continue; + PrintError(RuleDef.getLoc(), + "Unable to test predicate used in rule"); + PrintNote(SMLoc(), + "This indicates an incomplete implementation in tablegen"); + Predicate->print(errs()); + errs() << "\n"; + OS << Indent + << "llvm_unreachable(\"TableGen did not emit complete code for this " + "path\");\n"; + break; + } + if (Rule->getMatchingFixupCode() && !Rule->getMatchingFixupCode()->getValue().empty()) { // FIXME: Single-use lambda's like this are a serious compile-time @@ -674,7 +820,24 @@ } OS << Indent << "}\n"; + + assert(Leaf.isFullyTraversed()); + + // If we didn't have any predicates left over and we're not using the + // trap-door we have to support arbitrary C++ code while we're migrating to + // the declarative style then we know that subsequent leaves are + // unreachable. + if (Leaf.isFullyTested() && + (!Rule->getMatchingFixupCode() || + Rule->getMatchingFixupCode()->getValue().empty())) { + AnyFullyTested = true; + OS << Indent + << "llvm_unreachable(\"Combine rule elision was incorrect\");\n" + << Indent << "return false;\n"; + } } + if (!AnyFullyTested) + OS << Indent << "return false;\n"; } void GICombinerEmitter::run(raw_ostream &OS) { @@ -687,6 +850,33 @@ } if (ErrorsPrinted) PrintFatalError(Combiner->getLoc(), "Failed to parse one or more rules"); + LLVM_DEBUG(dbgs() << "Optimizing tree for " << Rules.size() << " rules\n"); + std::unique_ptr Tree; + { + NamedRegionTimer T("Optimize", "Time spent optimizing the combiner", + "Code Generation", "Time spent generating code", + TimeRegions); + + GIMatchTreeBuilder TreeBuilder(0); + for (const auto &Rule : Rules) { + bool HadARoot = false; + for (const auto &Root : enumerate(Rule->getMatchDag().roots())) { + TreeBuilder.addLeaf(Rule->getName(), Root.index(), Rule->getMatchDag(), + Rule.get()); + HadARoot = true; + } + if (!HadARoot) + PrintFatalError(Rule->getDef().getLoc(), "All rules must have a root"); + } + + Tree = TreeBuilder.run(); + } + if (StopAfterBuild) { + Tree->writeDOTGraph(outs()); + PrintNote(Combiner->getLoc(), + "Terminating due to -gicombiner-stop-after-build"); + return; + } NamedRegionTimer T("Emit", "Time spent emitting the combiner", "Code Generation", "Time spent generating code", @@ -772,6 +962,7 @@ << " MachineBasicBlock *MBB = MI.getParent();\n" << " MachineFunction *MF = MBB->getParent();\n" << " MachineRegisterInfo &MRI = MF->getRegInfo();\n" + << " SmallVector MIs = { &MI };\n\n" << " (void)MBB; (void)MF; (void)MRI;\n\n"; OS << " // Match data\n"; @@ -780,8 +971,8 @@ OS << " " << I.getType() << " " << I.getVariableName() << ";\n"; OS << "\n"; - for (const auto &Rule : Rules) - generateCodeForRule(OS, Rule.get(), " "); + OS << " int Partition = -1;\n"; + generateCodeForTree(OS, *Tree, " "); OS << "\n return false;\n" << "}\n" << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n"; diff --git a/llvm/utils/TableGen/GlobalISel/CMakeLists.txt b/llvm/utils/TableGen/GlobalISel/CMakeLists.txt --- a/llvm/utils/TableGen/GlobalISel/CMakeLists.txt +++ b/llvm/utils/TableGen/GlobalISel/CMakeLists.txt @@ -10,4 +10,5 @@ GIMatchDagOperands.cpp GIMatchDagPredicate.cpp GIMatchDagPredicateDependencyEdge.cpp + GIMatchTree.cpp ) diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDag.h b/llvm/utils/TableGen/GlobalISel/GIMatchDag.h --- a/llvm/utils/TableGen/GlobalISel/GIMatchDag.h +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDag.h @@ -52,14 +52,25 @@ class GIMatchDag { public: using InstrNodesVec = std::vector>; + using instr_node_iterator = raw_pointer_iterator; + using const_instr_node_iterator = + raw_pointer_iterator; + using EdgesVec = std::vector>; using edge_iterator = raw_pointer_iterator; using const_edge_iterator = raw_pointer_iterator; using PredicateNodesVec = std::vector>; + using predicate_iterator = raw_pointer_iterator; + using const_predicate_iterator = + raw_pointer_iterator; using PredicateDependencyEdgesVec = std::vector>; + using predicate_edge_iterator = + raw_pointer_iterator; + using const_predicate_edge_iterator = + raw_pointer_iterator; protected: GIMatchDagContext &Ctx; @@ -68,6 +79,9 @@ EdgesVec Edges; PredicateDependencyEdgesVec PredicateDependencies; std::vector MatchRoots; + // FIXME: This is a temporary measure while we still accept arbitrary code + // blocks to fix up the matcher while it's being developed. + bool HasPostMatchPredicate = false; public: GIMatchDag(GIMatchDagContext &Ctx) @@ -101,6 +115,71 @@ return make_range(MatchRoots.begin(), MatchRoots.end()); } + instr_node_iterator instr_nodes_begin() { + return raw_pointer_iterator(InstrNodes.begin()); + } + instr_node_iterator instr_nodes_end() { + return raw_pointer_iterator(InstrNodes.end()); + } + const_instr_node_iterator instr_nodes_begin() const { + return raw_pointer_iterator( + InstrNodes.begin()); + } + const_instr_node_iterator instr_nodes_end() const { + return raw_pointer_iterator( + InstrNodes.end()); + } + iterator_range instr_nodes() { + return make_range(instr_nodes_begin(), instr_nodes_end()); + } + iterator_range instr_nodes() const { + return make_range(instr_nodes_begin(), instr_nodes_end()); + } + predicate_edge_iterator predicate_edges_begin() { + return raw_pointer_iterator( + PredicateDependencies.begin()); + } + predicate_edge_iterator predicate_edges_end() { + return raw_pointer_iterator( + PredicateDependencies.end()); + } + const_predicate_edge_iterator predicate_edges_begin() const { + return raw_pointer_iterator( + PredicateDependencies.begin()); + } + const_predicate_edge_iterator predicate_edges_end() const { + return raw_pointer_iterator( + PredicateDependencies.end()); + } + iterator_range predicate_edges() { + return make_range(predicate_edges_begin(), predicate_edges_end()); + } + iterator_range predicate_edges() const { + return make_range(predicate_edges_begin(), predicate_edges_end()); + } + predicate_iterator predicates_begin() { + return raw_pointer_iterator( + PredicateNodes.begin()); + } + predicate_iterator predicates_end() { + return raw_pointer_iterator( + PredicateNodes.end()); + } + const_predicate_iterator predicates_begin() const { + return raw_pointer_iterator( + PredicateNodes.begin()); + } + const_predicate_iterator predicates_end() const { + return raw_pointer_iterator( + PredicateNodes.end()); + } + iterator_range predicates() { + return make_range(predicates_begin(), predicates_end()); + } + iterator_range predicates() const { + return make_range(predicates_begin(), predicates_end()); + } + template GIMatchDagInstr *addInstrNode(Args &&... args) { auto Obj = std::make_unique(*this, std::forward(args)...); @@ -133,6 +212,19 @@ return ObjRaw; } + size_t getInstrNodeIdx(instr_node_iterator I) { + return std::distance(instr_nodes_begin(), I); + } + size_t getInstrNodeIdx(const_instr_node_iterator I) const { + return std::distance(instr_nodes_begin(), I); + } + size_t getNumInstrNodes() const { return InstrNodes.size(); } + size_t getNumEdges() const { return Edges.size(); } + size_t getNumPredicates() const { return PredicateNodes.size(); } + + void setHasPostMatchPredicate(bool V) { HasPostMatchPredicate = V; } + bool hasPostMatchPredicate() const { return HasPostMatchPredicate; } + void addMatchRoot(GIMatchDagInstr *N) { MatchRoots.push_back(N); } LLVM_DUMP_METHOD void print(raw_ostream &OS) const; diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h @@ -54,6 +54,9 @@ /// Flip the direction of the edge. void reverse(); + /// Does this edge run from a def to (one of many) uses? + bool isDefToUse() const; + LLVM_DUMP_METHOD void print(raw_ostream &OS) const; #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp @@ -18,8 +18,21 @@ << "]"; } +bool GIMatchDagEdge::isDefToUse() const { + // Def -> Def is invalid so we only need to check FromMO. + return FromMO->isDef(); +} + void GIMatchDagEdge::reverse() { std::swap(FromMI, ToMI); std::swap(FromMO, ToMO); } +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD void GIMatchDagEdge::dump() const { print(errs()); } +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + +raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDagEdge &E) { + E.print(OS); + return OS; +} diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h @@ -74,6 +74,7 @@ const GIMatchDagOperandList &getOperandInfo() const { return OperandInfo; } StringRef getName() const { return Name; } + StringRef getUserAssignedName() const { return UserAssignedName; } void assignNameToOperand(unsigned Idx, StringRef Name) { assert(UserAssignedNamesForOperands[Idx].empty() && "Cannot assign twice"); UserAssignedNamesForOperands[Idx] = Name; diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h @@ -11,7 +11,9 @@ #include "llvm/ADT/StringRef.h" #include "GIMatchDag.h" + namespace llvm { +class CodeExpansions; class CodeGenInstruction; class GIMatchDagOperandList; class GIMatchDagContext; @@ -26,6 +28,7 @@ public: enum GIMatchDagPredicateKind { GIMatchDagPredicateKind_Opcode, + GIMatchDagPredicateKind_OneOfOpcodes, GIMatchDagPredicateKind_SameMO, }; @@ -55,6 +58,16 @@ StringRef getName() const { return Name; } const GIMatchDagOperandList &getOperandInfo() const { return OperandInfo; } + // Generate C++ code to check this predicate. If a partitioner has already + // tested this predicate then this function won't be called. If this function + // is called, it must emit code and return true to indicate that it did so. If + // it ever returns false, then the caller will abort due to an untested + // predicate. + virtual bool generateCheckCode(raw_ostream &OS, StringRef Indent, + const CodeExpansions &Expansions) const { + return false; + } + virtual void print(raw_ostream &OS) const; virtual void printDescription(raw_ostream &OS) const; @@ -83,6 +96,29 @@ #endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) }; +class GIMatchDagOneOfOpcodesPredicate : public GIMatchDagPredicate { + SmallVector Instrs; + +public: + GIMatchDagOneOfOpcodesPredicate(GIMatchDagContext &Ctx, StringRef Name); + + void addOpcode(const CodeGenInstruction *Instr) { Instrs.push_back(Instr); } + + static bool classof(const GIMatchDagPredicate *P) { + return P->getKind() == GIMatchDagPredicateKind_OneOfOpcodes; + } + + const SmallVectorImpl &getInstrs() const { + return Instrs; + } + + void printDescription(raw_ostream &OS) const override; + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + virtual LLVM_DUMP_METHOD void dump() const override { print(errs()); } +#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +}; + class GIMatchDagSameMOPredicate : public GIMatchDagPredicate { public: GIMatchDagSameMOPredicate(GIMatchDagContext &Ctx, StringRef Name); diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "GIMatchDagPredicate.h" + #include "llvm/TableGen/Record.h" #include "GIMatchDagOperands.h" @@ -32,6 +33,21 @@ OS << "$mi.getOpcode() == " << Instr.TheDef->getName(); } +GIMatchDagOneOfOpcodesPredicate::GIMatchDagOneOfOpcodesPredicate( + GIMatchDagContext &Ctx, StringRef Name) + : GIMatchDagPredicate(GIMatchDagPredicateKind_OneOfOpcodes, Name, + Ctx.makeMIPredicateOperandList()) {} + +void GIMatchDagOneOfOpcodesPredicate::printDescription(raw_ostream &OS) const { + OS << "$mi.getOpcode() == oneof("; + StringRef Separator = ""; + for (const CodeGenInstruction *Instr : Instrs) { + OS << Separator << Instr->TheDef->getName(); + Separator = ","; + } + OS << ")"; +} + GIMatchDagSameMOPredicate::GIMatchDagSameMOPredicate(GIMatchDagContext &Ctx, StringRef Name) : GIMatchDagPredicate(GIMatchDagPredicateKind_SameMO, Name, diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp --- a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp +++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp @@ -11,6 +11,8 @@ #include "GIMatchDagInstr.h" #include "GIMatchDagPredicate.h" +#include "llvm/Support/raw_ostream.h" + using namespace llvm; LLVM_DUMP_METHOD void diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchTree.h b/llvm/utils/TableGen/GlobalISel/GIMatchTree.h new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchTree.h @@ -0,0 +1,629 @@ +//===- GIMatchTree.h - A decision tree to match GIMatchDag's --------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H +#define LLVM_UTILS_TABLEGEN_GIMATCHTREE_H + +#include "GIMatchDag.h" +#include "llvm/ADT/BitVector.h" + +namespace llvm { +class raw_ostream; + +class GIMatchTreeBuilder; +class GIMatchTreePartitioner; + +/// Describes the binding of a variable to the matched MIR +class GIMatchTreeVariableBinding { + /// The name of the variable described by this binding. + StringRef Name; + // The matched instruction it is bound to. + unsigned InstrID; + // The matched operand (if appropriate) it is bound to. + Optional OpIdx; + +public: + GIMatchTreeVariableBinding(StringRef Name, unsigned InstrID, + Optional OpIdx = None) + : Name(Name), InstrID(InstrID), OpIdx(OpIdx) {} + + bool isInstr() const { return !OpIdx.hasValue(); } + StringRef getName() const { return Name; } + unsigned getInstrID() const { return InstrID; } + unsigned getOpIdx() const { + assert(OpIdx.hasValue() && "Is not an operand binding"); + return *OpIdx; + } +}; + +/// Associates a matchable with a leaf of the decision tree. +class GIMatchTreeLeafInfo { +public: + using const_var_binding_iterator = + std::vector::const_iterator; + using UntestedPredicatesTy = SmallVector; + using const_untested_predicates_iterator = UntestedPredicatesTy::const_iterator; + +protected: + /// A name for the matchable. This is primarily for debugging. + StringRef Name; + /// Where rules have multiple roots, this is which root we're starting from. + unsigned RootIdx; + /// Opaque data the caller of the tree building code understands. + void *Data; + /// Has the decision tree covered every edge traversal? If it hasn't then this + /// is an unrecoverable error indicating there's something wrong with the + /// partitioners. + bool IsFullyTraversed; + /// Has the decision tree covered every predicate test? If it has, then + /// subsequent matchables on the same leaf are unreachable. If it hasn't, the + /// code that requested the GIMatchTree is responsible for finishing off any + /// remaining predicates. + bool IsFullyTested; + /// The variable bindings associated with this leaf so far. + std::vector VarBindings; + /// Any predicates left untested by the time we reach this leaf. + UntestedPredicatesTy UntestedPredicates; + +public: + GIMatchTreeLeafInfo() { llvm_unreachable("Cannot default-construct"); } + GIMatchTreeLeafInfo(StringRef Name, unsigned RootIdx, void *Data) + : Name(Name), RootIdx(RootIdx), Data(Data), IsFullyTraversed(false), + IsFullyTested(false) {} + + StringRef getName() const { return Name; } + unsigned getRootIdx() const { return RootIdx; } + template Ty *getTargetData() const { + return static_cast(Data); + } + bool isFullyTraversed() const { return IsFullyTraversed; } + void setIsFullyTraversed(bool V) { IsFullyTraversed = V; } + bool isFullyTested() const { return IsFullyTested; } + void setIsFullyTested(bool V) { IsFullyTested = V; } + + void bindInstrVariable(StringRef Name, unsigned InstrID) { + VarBindings.emplace_back(Name, InstrID); + } + void bindOperandVariable(StringRef Name, unsigned InstrID, unsigned OpIdx) { + VarBindings.emplace_back(Name, InstrID, OpIdx); + } + + const_var_binding_iterator var_bindings_begin() const { + return VarBindings.begin(); + } + const_var_binding_iterator var_bindings_end() const { + return VarBindings.end(); + } + iterator_range var_bindings() const { + return make_range(VarBindings.begin(), VarBindings.end()); + } + iterator_range untested_predicates() const { + return make_range(UntestedPredicates.begin(), UntestedPredicates.end()); + } + void addUntestedPredicate(const GIMatchDagPredicate *P) { + UntestedPredicates.push_back(P); + } +}; + +/// The nodes of a decision tree used to perform the match. +/// This will be used to generate the C++ code or state machine equivalent. +/// +/// It should be noted that some nodes of this tree (most notably nodes handling +/// def -> use edges) will need to iterate over several possible matches. As +/// such, code generated from this will sometimes need to support backtracking. +class GIMatchTree { + using LeafVector = std::vector; + + /// The partitioner that has been chosen for this node. This may be nullptr if + /// a partitioner hasn't been chosen yet or if the node is a leaf. + std::unique_ptr Partitioner; + /// All the leaves that are possible for this node of the tree. + /// Note: This should be emptied after the tree is built when there are + /// children but this currently isn't done to aid debuggability of the DOT + /// graph for the decision tree. + LeafVector PossibleLeaves; + /// The children of this node. The index into this array must match the index + /// chosen by the partitioner. + std::vector Children; + + void writeDOTGraphNode(raw_ostream &OS) const; + void writeDOTGraphEdges(raw_ostream &OS) const; + +public: + void writeDOTGraph(raw_ostream &OS) const; + + void setNumChildren(unsigned Num) { Children.resize(Num); } + void addPossibleLeaf(const GIMatchTreeLeafInfo &V, bool IsFullyTraversed, + bool IsFullyTested) { + PossibleLeaves.push_back(V); + PossibleLeaves.back().setIsFullyTraversed(IsFullyTraversed); + PossibleLeaves.back().setIsFullyTested(IsFullyTested); + } + void dropLeavesAfter(size_t Length) { + if (PossibleLeaves.size() > Length) + PossibleLeaves.resize(Length); + } + void setPartitioner(std::unique_ptr &&V) { + Partitioner = std::move(V); + } + GIMatchTreePartitioner *getPartitioner() const { return Partitioner.get(); } + + std::vector::iterator children_begin() { + return Children.begin(); + } + std::vector::iterator children_end() { return Children.end(); } + iterator_range::iterator> children() { + return make_range(children_begin(), children_end()); + } + std::vector::const_iterator children_begin() const { + return Children.begin(); + } + std::vector::const_iterator children_end() const { + return Children.end(); + } + iterator_range::const_iterator> children() const { + return make_range(children_begin(), children_end()); + } + + LeafVector::const_iterator possible_leaves_begin() const { + return PossibleLeaves.begin(); + } + LeafVector::const_iterator possible_leaves_end() const { + return PossibleLeaves.end(); + } + iterator_range + possible_leaves() const { + return make_range(possible_leaves_begin(), possible_leaves_end()); + } + LeafVector::iterator possible_leaves_begin() { + return PossibleLeaves.begin(); + } + LeafVector::iterator possible_leaves_end() { + return PossibleLeaves.end(); + } + iterator_range possible_leaves() { + return make_range(possible_leaves_begin(), possible_leaves_end()); + } +}; + +/// Record information that is known about the instruction bound to this ID and +/// GIMatchDagInstrNode. Every rule gets its own set of +/// GIMatchTreeInstrInfo to bind the shared IDs to an instr node in its +/// DAG. +/// +/// For example, if we know that there are 3 operands. We can record it here to +/// elide duplicate checks. +class GIMatchTreeInstrInfo { + /// The instruction ID for the matched instruction. + unsigned ID; + /// The corresponding instruction node in the MatchDAG. + const GIMatchDagInstr *InstrNode; + +public: + GIMatchTreeInstrInfo(unsigned ID, const GIMatchDagInstr *InstrNode) + : ID(ID), InstrNode(InstrNode) {} + + unsigned getID() const { return ID; } + const GIMatchDagInstr *getInstrNode() const { return InstrNode; } +}; + +/// Record information that is known about the operand bound to this ID, OpIdx, +/// and GIMatchDagInstrNode. Every rule gets its own set of +/// GIMatchTreeOperandInfo to bind the shared IDs to an operand of an +/// instr node from its DAG. +/// +/// For example, if we know that there the operand is a register. We can record +/// it here to elide duplicate checks. +class GIMatchTreeOperandInfo { + /// The corresponding instruction node in the MatchDAG that the operand + /// belongs to. + const GIMatchDagInstr *InstrNode; + unsigned OpIdx; + +public: + GIMatchTreeOperandInfo(const GIMatchDagInstr *InstrNode, unsigned OpIdx) + : InstrNode(InstrNode), OpIdx(OpIdx) {} + + const GIMatchDagInstr *getInstrNode() const { return InstrNode; } + unsigned getOpIdx() const { return OpIdx; } +}; + +/// Represent a leaf of the match tree and any working data we need to build the +/// tree. +/// +/// It's important to note that each rule can have multiple +/// GIMatchTreeBuilderLeafInfo's since the partitioners do not always partition +/// into mutually-exclusive partitions. For example: +/// R1: (FOO ..., ...) +/// R2: (oneof(FOO, BAR) ..., ...) +/// will partition by opcode into two partitions FOO=>[R1, R2], and BAR=>[R2] +/// +/// As an optimization, all instructions, edges, and predicates in the DAGs are +/// numbered and tracked in BitVectors. As such, the GIMatchDAG must not be +/// modified once construction of the tree has begun. +class GIMatchTreeBuilderLeafInfo { +protected: + GIMatchTreeBuilder &Builder; + GIMatchTreeLeafInfo Info; + const GIMatchDag &MatchDag; + /// The association between GIMatchDagInstr* and GIMatchTreeInstrInfo. + /// The primary reason for this members existence is to allow the use of + /// InstrIDToInfo.lookup() since that requires that the value is + /// default-constructible. + DenseMap InstrNodeToInfo; + /// The instruction information for a given ID in the context of this + /// particular leaf. + DenseMap InstrIDToInfo; + /// The operand information for a given ID and OpIdx in the context of this + /// particular leaf. + DenseMap, GIMatchTreeOperandInfo> + OperandIDToInfo; + +public: + /// The remaining instrs/edges/predicates to visit + BitVector RemainingInstrNodes; + BitVector RemainingEdges; + BitVector RemainingPredicates; + + // The remaining predicate dependencies for each predicate + std::vector UnsatisfiedPredDepsForPred; + + /// The edges/predicates we can visit as a result of the declare*() calls we + /// have already made. We don't need an instrs version since edges imply the + /// instr. + BitVector TraversableEdges; + BitVector TestablePredicates; + + /// Map predicates from the DAG to their position in the DAG predicate + /// iterators. + DenseMap PredicateIDs; + /// Map predicate dependency edges from the DAG to their position in the DAG + /// predicate dependency iterators. + DenseMap PredicateDepIDs; + +public: + GIMatchTreeBuilderLeafInfo(GIMatchTreeBuilder &Builder, StringRef Name, + unsigned RootIdx, const GIMatchDag &MatchDag, + void *Data); + + StringRef getName() const { return Info.getName(); } + GIMatchTreeLeafInfo &getInfo() { return Info; } + const GIMatchTreeLeafInfo &getInfo() const { return Info; } + const GIMatchDag &getMatchDag() const { return MatchDag; } + unsigned getRootIdx() const { return Info.getRootIdx(); } + + /// Has this DAG been fully traversed. This must be true by the time the tree + /// builder finishes. + bool isFullyTraversed() const { + // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates + // can't be all-zero without satisfying all the dependencies. The same is + // almost true for Edges and Instrs but it's possible to have Instrs without + // Edges. + return RemainingInstrNodes.none() && RemainingEdges.none(); + } + + /// Has this DAG been fully tested. This hould be true by the time the tree + /// builder finishes but clients can finish any untested predicates left over + /// if it's not true. + bool isFullyTested() const { + // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates + // can't be all-zero without satisfying all the dependencies. The same is + // almost true for Edges and Instrs but it's possible to have Instrs without + // Edges. + return RemainingInstrNodes.none() && RemainingEdges.none() && + RemainingPredicates.none(); + } + + const GIMatchDagInstr *getInstr(unsigned Idx) const { + return *(MatchDag.instr_nodes_begin() + Idx); + } + const GIMatchDagEdge *getEdge(unsigned Idx) const { + return *(MatchDag.edges_begin() + Idx); + } + GIMatchDagEdge *getEdge(unsigned Idx) { + return *(MatchDag.edges_begin() + Idx); + } + const GIMatchDagPredicate *getPredicate(unsigned Idx) const { + return *(MatchDag.predicates_begin() + Idx); + } + iterator_range + untested_instrs() const { + return RemainingInstrNodes.set_bits(); + } + iterator_range + untested_edges() const { + return RemainingEdges.set_bits(); + } + iterator_range + untested_predicates() const { + return RemainingPredicates.set_bits(); + } + + /// Bind an instr node to the given ID and clear any blocking dependencies + /// that were waiting for it. + void declareInstr(const GIMatchDagInstr *Instr, unsigned ID); + + /// Bind an operand to the given ID and OpIdx and clear any blocking + /// dependencies that were waiting for it. + void declareOperand(unsigned InstrID, unsigned OpIdx); + + GIMatchTreeInstrInfo *getInstrInfo(unsigned ID) const { + auto I = InstrIDToInfo.find(ID); + if (I != InstrIDToInfo.end()) + return I->second; + return nullptr; + } + + void dump(raw_ostream &OS) const { + OS << "Leaf " << getName() << " for root #" << getRootIdx() << "\n"; + MatchDag.print(OS); + for (const auto &I : InstrIDToInfo) + OS << "Declared Instr #" << I.first << "\n"; + for (const auto &I : OperandIDToInfo) + OS << "Declared Instr #" << I.first.first << ", Op #" << I.first.second + << "\n"; + OS << RemainingInstrNodes.count() << " untested instrs of " + << RemainingInstrNodes.size() << "\n"; + OS << RemainingEdges.count() << " untested edges of " + << RemainingEdges.size() << "\n"; + OS << RemainingPredicates.count() << " untested predicates of " + << RemainingPredicates.size() << "\n"; + + OS << TraversableEdges.count() << " edges could be traversed\n"; + OS << TestablePredicates.count() << " predicates could be tested\n"; + } +}; + +/// The tree builder has a fairly tough job. It's purpose is to merge all the +/// DAGs from the ruleset into a decision tree that walks all of them +/// simultaneously and identifies the rule that was matched. In addition to +/// that, it also needs to find the most efficient order to make decisions +/// without violating any dependencies and ensure that every DAG covers every +/// instr/edge/predicate. +class GIMatchTreeBuilder { +public: + using LeafVec = std::vector; + +protected: + /// The leaves that the resulting decision tree will distinguish. + LeafVec Leaves; + /// The tree node being constructed. + GIMatchTree *TreeNode; + /// The builders for each subtree resulting from the current decision. + std::vector SubtreeBuilders; + /// The possible partitioners we could apply right now. + std::vector> Partitioners; + /// The next instruction ID to allocate when requested by the chosen + /// Partitioner. + unsigned NextInstrID; + + /// Use any context we have stored to cull partitioners that only test things + /// we already know. At the time of writing, there's no need to do anything + /// here but it will become important once, for example, there is a + /// num-operands and an opcode partitioner. This is because applying an opcode + /// partitioner (usually) makes the number of operands known which makes + /// additional checking pointless. + void filterRedundantPartitioners(); + + /// Evaluate the available partioners and select the best one at the moment. + void evaluatePartitioners(); + + /// Construct the current tree node. + void runStep(); + +public: + GIMatchTreeBuilder(unsigned NextInstrID) : NextInstrID(NextInstrID) {} + GIMatchTreeBuilder(GIMatchTree *TreeNode, unsigned NextInstrID) + : TreeNode(TreeNode), NextInstrID(NextInstrID) {} + + void addLeaf(StringRef Name, unsigned RootIdx, const GIMatchDag &MatchDag, + void *Data) { + Leaves.emplace_back(*this, Name, RootIdx, MatchDag, Data); + } + void addLeaf(const GIMatchTreeBuilderLeafInfo &L) { Leaves.push_back(L); } + void addPartitioner(std::unique_ptr P) { + Partitioners.push_back(std::move(P)); + } + void addPartitionersForInstr(unsigned InstrIdx); + void addPartitionersForOperand(unsigned InstrID, unsigned OpIdx); + + LeafVec &getPossibleLeaves() { return Leaves; } + + unsigned allocInstrID() { return NextInstrID++; } + + /// Construct the decision tree. + std::unique_ptr run(); +}; + +/// Partitioners are the core of the tree builder and are unfortunately rather +/// tricky to write. +class GIMatchTreePartitioner { +protected: + /// The partitions resulting from applying the partitioner to the possible + /// leaves. The keys must be consecutive integers starting from 0. This can + /// lead to some unfortunate situations where partitioners test a predicate + /// and use 0 for success and 1 for failure if the ruleset encounters a + /// success case first but is necessary to assign the partition to one of the + /// tree nodes children. As a result, you usually need some kind of + /// indirection to map the natural keys (e.g. ptrs/bools) to this linear + /// sequence. The values are a bitvector indicating which leaves belong to + /// this partition. + DenseMap Partitions; + +public: + virtual ~GIMatchTreePartitioner() {} + virtual std::unique_ptr clone() const = 0; + + /// Determines which partitions the given leaves belong to. A leaf may belong + /// to multiple partitions in which case it will be duplicated during + /// applyForPartition(). + /// + /// This function can be rather complicated. A few particular things to be + /// aware of include: + /// * One leaf can be assigned to multiple partitions when there's some + /// ambiguity. + /// * Not all DAG's for the leaves may be able to perform the test. For + /// example, the opcode partitiioner must account for one DAG being a + /// superset of another such as [(ADD ..., ..., ...)], and [(MUL t, ..., + /// ...), (ADD ..., t, ...)] + /// * Attaching meaning to a particular partition index will generally not + /// work due to the '0, 1, ..., n' requirement. You might encounter cases + /// where only partition 1 is seen, leaving a missing 0. + /// * Finding a specific predicate such as the opcode predicate for a specific + /// instruction is non-trivial. It's often O(NumPredicates), leading to + /// O(NumPredicates*NumRules) when applied to the whole ruleset. The good + /// news there is that n is typically small thanks to predicate dependencies + /// limiting how many are testable at once. Also, with opcode and type + /// predicates being so frequent the value of m drops very fast too. It + /// wouldn't be terribly surprising to see a 10k ruleset drop down to an + /// average of 100 leaves per partition after a single opcode partitioner. + /// * The same goes for finding specific edges. The need to traverse them in + /// dependency order dramatically limits the search space at any given + /// moment. + /// * If you need to add a leaf to all partitions, make sure you don't forget + /// them when adding partitions later. + virtual void repartition(GIMatchTreeBuilder::LeafVec &Leaves) = 0; + + /// Delegate the leaves for a given partition to the corresponding subbuilder, + /// update any recorded context for this partition (e.g. allocate instr id's + /// for instrs recorder by the current node), and clear any blocking + /// dependencies this partitioner resolved. + virtual void applyForPartition(unsigned PartitionIdx, + GIMatchTreeBuilder &Builder, + GIMatchTreeBuilder &SubBuilder) = 0; + + /// Return a BitVector indicating which leaves should be transferred to the + /// specified partition. Note that the same leaf can be indicated for multiple + /// partitions. + BitVector getPossibleLeavesForPartition(unsigned Idx) { + const auto &I = Partitions.find(Idx); + assert(I != Partitions.end() && "Requested non-existant partition"); + return I->second; + } + + size_t getNumPartitions() const { return Partitions.size(); } + size_t getNumLeavesWithDupes() const { + size_t S = 0; + for (const auto &P : Partitions) + S += P.second.size(); + return S; + } + + /// Emit a brief description of the partitioner suitable for debug printing or + /// use in a DOT graph. + virtual void emitDescription(raw_ostream &OS) const = 0; + /// Emit a label for the given partition suitable for debug printing or use in + /// a DOT graph. + virtual void emitPartitionName(raw_ostream &OS, unsigned Idx) const = 0; + + /// Emit a long description of how the partitioner partitions the leaves. + virtual void emitPartitionResults(raw_ostream &OS) const = 0; + + /// Generate code to select between partitions based on the MIR being matched. + /// This is typically a switch statement that picks a partition index. + virtual void generatePartitionSelectorCode(raw_ostream &OS, + StringRef Indent) const = 0; +}; + +/// Partition according to the opcode of the instruction. +/// +/// Numbers CodeGenInstr ptrs for use as partition ID's. One special partition, +/// nullptr, represents the case where the instruction isn't known. +/// +/// * If the opcode can be tested and is a single opcode, create the partition +/// for that opcode and assign the leaf to it. This partition no longer needs +/// to test the opcode, and many details about the instruction will usually +/// become known (e.g. number of operands for non-variadic instrs) via the +/// CodeGenInstr ptr. +/// * (not implemented yet) If the opcode can be tested and is a choice of +/// opcodes, then the leaf can be treated like the single-opcode case but must +/// be added to all relevant partitions and not quite as much becomes known as +/// a result. That said, multiple-choice opcodes are likely similar enough +/// (because if they aren't then handling them together makes little sense) +/// that plenty still becomes known. The main implementation issue with this +/// is having a description to represent the commonality between instructions. +/// * If the opcode is not tested, the leaf must be added to all partitions +/// including the wildcard nullptr partition. What becomes known as a result +/// varies between partitions. +/// * If the instruction to be tested is not declared then add the leaf to all +/// partitions. This occurs when we encounter one rule that is a superset of +/// the other and we are still matching the remainder of the superset. The +/// result is that the cases that don't match the superset will match the +/// subset rule, while the ones that do match the superset will match either +/// (which one is algorithm dependent but will usually be the superset). +class GIMatchTreeOpcodePartitioner : public GIMatchTreePartitioner { + unsigned InstrID; + DenseMap InstrToPartition; + std::vector PartitionToInstr; + std::vector TestedPredicates; + +public: + GIMatchTreeOpcodePartitioner(unsigned InstrID) : InstrID(InstrID) {} + + std::unique_ptr clone() const override { + return std::make_unique(*this); + } + + void emitDescription(raw_ostream &OS) const override { + OS << "MI[" << InstrID << "].getOpcode()"; + } + + void emitPartitionName(raw_ostream &OS, unsigned Idx) const override; + + void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override; + void applyForPartition(unsigned Idx, GIMatchTreeBuilder &SubBuilder, + GIMatchTreeBuilder &Builder) override; + + void emitPartitionResults(raw_ostream &OS) const override; + + void generatePartitionSelectorCode(raw_ostream &OS, + StringRef Indent) const override; +}; + +class GIMatchTreeVRegDefPartitioner : public GIMatchTreePartitioner { + unsigned NewInstrID = -1; + unsigned InstrID; + unsigned OpIdx; + std::vector TraversedEdges; + DenseMap ResultToPartition; + std::vector PartitionToResult; + + void addToPartition(bool Result, unsigned LeafIdx); + +public: + GIMatchTreeVRegDefPartitioner(unsigned InstrID, unsigned OpIdx) + : InstrID(InstrID), OpIdx(OpIdx) {} + + std::unique_ptr clone() const override { + return std::make_unique(*this); + } + + void emitDescription(raw_ostream &OS) const override { + OS << "MI[" << NewInstrID << "] = getVRegDef(MI[" << InstrID + << "].getOperand(" << OpIdx << "))"; + } + + void emitPartitionName(raw_ostream &OS, unsigned Idx) const override { + bool Result = PartitionToResult[Idx]; + if (Result) + OS << "true"; + else + OS << "false"; + } + + void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override; + void applyForPartition(unsigned PartitionIdx, GIMatchTreeBuilder &Builder, + GIMatchTreeBuilder &SubBuilder) override; + void emitPartitionResults(raw_ostream &OS) const override; + + void generatePartitionSelectorCode(raw_ostream &OS, + StringRef Indent) const override; +}; + +} // end namespace llvm +#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp @@ -0,0 +1,777 @@ +//===- GIMatchTree.cpp - A decision tree to match GIMatchDag's ------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "GIMatchTree.h" + +#include "../CodeGenInstruction.h" + +#include "llvm/Support/Format.h" +#include "llvm/Support/ScopedPrinter.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/TableGen/Error.h" +#include "llvm/TableGen/Record.h" + +#define DEBUG_TYPE "gimatchtree" + +using namespace llvm; + +void GIMatchTree::writeDOTGraph(raw_ostream &OS) const { + OS << "digraph \"matchtree\" {\n"; + writeDOTGraphNode(OS); + OS << "}\n"; +} + +void GIMatchTree::writeDOTGraphNode(raw_ostream &OS) const { + OS << format(" Node%p", this) << " [shape=record,label=\"{"; + if (Partitioner) { + Partitioner->emitDescription(OS); + OS << "|" << Partitioner->getNumPartitions() << " partitions|"; + } else + OS << "No partitioner|"; + bool IsFullyTraversed = true; + bool IsFullyTested = true; + StringRef Separator = ""; + for (const auto &Leaf : PossibleLeaves) { + OS << Separator << Leaf.getName(); + Separator = ","; + if (!Leaf.isFullyTraversed()) + IsFullyTraversed = false; + if (!Leaf.isFullyTested()) + IsFullyTested = false; + } + if (!Partitioner && !IsFullyTraversed) + OS << "|Not fully traversed"; + if (!Partitioner && !IsFullyTested) { + OS << "|Not fully tested"; + if (IsFullyTraversed) { + for (const GIMatchTreeLeafInfo &Leaf : PossibleLeaves) { + if (Leaf.isFullyTested()) + continue; + OS << "\\n" << Leaf.getName() << ": " << &Leaf; + for (const GIMatchDagPredicate *P : Leaf.untested_predicates()) + OS << *P; + } + } + } + OS << "}\""; + if (!Partitioner && + (!IsFullyTraversed || !IsFullyTested || PossibleLeaves.size() > 1)) + OS << ",color=red"; + OS << "]\n"; + for (const auto &C : Children) + C.writeDOTGraphNode(OS); + writeDOTGraphEdges(OS); +} + +void GIMatchTree::writeDOTGraphEdges(raw_ostream &OS) const { + for (const auto &Child : enumerate(Children)) { + OS << format(" Node%p", this) << " -> " << format("Node%p", &Child.value()) + << " [label=\"#" << Child.index() << " "; + Partitioner->emitPartitionName(OS, Child.index()); + OS << "\"]\n"; + } +} + +GIMatchTreeBuilderLeafInfo::GIMatchTreeBuilderLeafInfo( + GIMatchTreeBuilder &Builder, StringRef Name, unsigned RootIdx, + const GIMatchDag &MatchDag, void *Data) + : Builder(Builder), Info(Name, RootIdx, Data), MatchDag(MatchDag), + InstrNodeToInfo(), + RemainingInstrNodes(BitVector(MatchDag.getNumInstrNodes(), true)), + RemainingEdges(BitVector(MatchDag.getNumEdges(), true)), + RemainingPredicates(BitVector(MatchDag.getNumPredicates(), true)), + TraversableEdges(MatchDag.getNumEdges()), + TestablePredicates(MatchDag.getNumPredicates()) { + // Number all the predicates in this DAG + for (auto &P : enumerate(MatchDag.predicates())) { + PredicateIDs.insert(std::make_pair(P.value(), P.index())); + } + + // Number all the predicate dependencies in this DAG and set up a bitvector + // for each predicate indicating the unsatisfied dependencies. + for (auto &Dep : enumerate(MatchDag.predicate_edges())) { + PredicateDepIDs.insert(std::make_pair(Dep.value(), Dep.index())); + } + UnsatisfiedPredDepsForPred.resize(MatchDag.getNumPredicates(), + BitVector(PredicateDepIDs.size())); + for (auto &Dep : enumerate(MatchDag.predicate_edges())) { + unsigned ID = PredicateIDs.lookup(Dep.value()->getPredicate()); + UnsatisfiedPredDepsForPred[ID].set(Dep.index()); + } +} + +void GIMatchTreeBuilderLeafInfo::declareInstr(const GIMatchDagInstr *Instr, unsigned ID) { + // Record the assignment of this instr to the given ID. + auto InfoI = InstrNodeToInfo.insert(std::make_pair( + Instr, GIMatchTreeInstrInfo(ID, Instr))); + InstrIDToInfo.insert(std::make_pair(ID, &InfoI.first->second)); + + if (Instr == nullptr) + return; + + if (!Instr->getUserAssignedName().empty()) + Info.bindInstrVariable(Instr->getUserAssignedName(), ID); + for (const auto &VarBinding : Instr->user_assigned_operand_names()) + Info.bindOperandVariable(VarBinding.second, ID, VarBinding.first); + + // Clear the bit indicating we haven't visited this instr. + const auto &NodeI = std::find(MatchDag.instr_nodes_begin(), + MatchDag.instr_nodes_end(), Instr); + assert(NodeI != MatchDag.instr_nodes_end() && "Instr isn't in this DAG"); + unsigned InstrIdx = MatchDag.getInstrNodeIdx(NodeI); + RemainingInstrNodes.reset(InstrIdx); + + // When we declare an instruction, we don't expose any traversable edges just + // yet. A partitioner has to check they exist and are registers before they + // are traversable. + + // When we declare an instruction, we potentially activate some predicates. + // Mark the dependencies that are now satisfied as a result of this + // instruction and mark any predicates whose dependencies are fully + // satisfied. + for (auto &Dep : enumerate(MatchDag.predicate_edges())) { + if (Dep.value()->getRequiredMI() == Instr && + Dep.value()->getRequiredMO() == nullptr) { + for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) { + DepsFor.value().reset(Dep.index()); + if (DepsFor.value().none()) + TestablePredicates.set(DepsFor.index()); + } + } + } +} + +void GIMatchTreeBuilderLeafInfo::declareOperand(unsigned InstrID, + unsigned OpIdx) { + const GIMatchDagInstr *Instr = InstrIDToInfo.lookup(InstrID)->getInstrNode(); + + OperandIDToInfo.insert(std::make_pair( + std::make_pair(InstrID, OpIdx), + GIMatchTreeOperandInfo(Instr, OpIdx))); + + // When an operand becomes reachable, we potentially activate some traversals. + // Record the edges that can now be followed as a result of this + // instruction. + for (auto &E : enumerate(MatchDag.edges())) { + if (E.value()->getFromMI() == Instr && + E.value()->getFromMO()->getIdx() == OpIdx) { + TraversableEdges.set(E.index()); + } + } + + // When an operand becomes reachable, we potentially activate some predicates. + // Clear the dependencies that are now satisfied as a result of this + // operand and activate any predicates whose dependencies are fully + // satisfied. + for (auto &Dep : enumerate(MatchDag.predicate_edges())) { + if (Dep.value()->getRequiredMI() == Instr && Dep.value()->getRequiredMO() && + Dep.value()->getRequiredMO()->getIdx() == OpIdx) { + for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) { + DepsFor.value().reset(Dep.index()); + if (DepsFor.value().none()) + TestablePredicates.set(DepsFor.index()); + } + } + } +} + +void GIMatchTreeBuilder::addPartitionersForInstr(unsigned InstrIdx) { + // Find the partitioners that can be used now that this node is + // uncovered. Our choices are: + // - Test the opcode + addPartitioner(std::make_unique(InstrIdx)); +} + +void GIMatchTreeBuilder::addPartitionersForOperand(unsigned InstrID, + unsigned OpIdx) { + LLVM_DEBUG(dbgs() << "Add partitioners for Instrs[" << InstrID + << "].getOperand(" << OpIdx << ")\n"); + addPartitioner( + std::make_unique(InstrID, OpIdx)); +} + +void GIMatchTreeBuilder::filterRedundantPartitioners() { + // TODO: Filter partitioners for facts that are already known + // - If we know the opcode, we can elide the num operand check so long as + // the instruction has a fixed number of operands. + // - If we know an exact number of operands then we can elide further number + // of operand checks. + // - If the current min number of operands exceeds the one we want to check + // then we can elide it. +} + +void GIMatchTreeBuilder::evaluatePartitioners() { + // Determine the partitioning the partitioner would produce + for (auto &Partitioner : Partitioners) { + LLVM_DEBUG(dbgs() << " Weighing up "; + Partitioner->emitDescription(dbgs()); dbgs() << "\n"); + Partitioner->repartition(Leaves); + LLVM_DEBUG(Partitioner->emitPartitionResults(dbgs())); + } +} + +void GIMatchTreeBuilder::runStep() { + LLVM_DEBUG(dbgs() << "Building match tree node for " << TreeNode << "\n"); + LLVM_DEBUG(dbgs() << " Rules reachable at this node:\n"); + for (const auto &Leaf : Leaves) { + LLVM_DEBUG(dbgs() << " " << Leaf.getName() << " (" << &Leaf.getInfo() << "\n"); + TreeNode->addPossibleLeaf(Leaf.getInfo(), Leaf.isFullyTraversed(), + Leaf.isFullyTested()); + } + + LLVM_DEBUG(dbgs() << " Partitioners available at this node:\n"); +#ifndef NDEBUG + for (const auto &Partitioner : Partitioners) + LLVM_DEBUG(dbgs() << " "; Partitioner->emitDescription(dbgs()); + dbgs() << "\n"); +#endif // ifndef NDEBUG + + // Check for unreachable rules. Rules are unreachable if they are preceeded by + // a fully tested rule. + // Note: This is only true for the current algorithm, if we allow the + // algorithm to compare equally valid rules then they will become + // reachable. + { + auto FullyTestedLeafI = Leaves.end(); + for (auto LeafI = Leaves.begin(), LeafE = Leaves.end(); + LeafI != LeafE; ++LeafI) { + if (LeafI->isFullyTraversed() && LeafI->isFullyTested()) + FullyTestedLeafI = LeafI; + else if (FullyTestedLeafI != Leaves.end()) { + PrintError("Leaf " + LeafI->getName() + " is unreachable"); + PrintNote("Leaf " + FullyTestedLeafI->getName() + + " will have already matched"); + } + } + } + + LLVM_DEBUG(dbgs() << " Eliminating redundant partitioners:\n"); + filterRedundantPartitioners(); + LLVM_DEBUG(dbgs() << " Partitioners remaining:\n"); +#ifndef NDEBUG + for (const auto &Partitioner : Partitioners) + LLVM_DEBUG(dbgs() << " "; Partitioner->emitDescription(dbgs()); + dbgs() << "\n"); +#endif // ifndef NDEBUG + + if (Partitioners.empty()) { + // Nothing left to do but check we really did identify a single rule. + if (Leaves.size() > 1) { + LLVM_DEBUG(dbgs() << "Leaf contains multiple rules, drop after the first " + "fully tested rule\n"); + auto FirstFullyTested = + std::find_if(Leaves.begin(), Leaves.end(), + [](const GIMatchTreeBuilderLeafInfo &X) { + return X.isFullyTraversed() && X.isFullyTested() && + !X.getMatchDag().hasPostMatchPredicate(); + }); + if (FirstFullyTested != Leaves.end()) + FirstFullyTested++; + +#ifndef NDEBUG + for (auto &Leaf : make_range(Leaves.begin(), FirstFullyTested)) + LLVM_DEBUG(dbgs() << " Kept " << Leaf.getName() << "\n"); + for (const auto &Leaf : make_range(FirstFullyTested, Leaves.end())) + LLVM_DEBUG(dbgs() << " Dropped " << Leaf.getName() << "\n"); +#endif // ifndef NDEBUG + TreeNode->dropLeavesAfter( + std::distance(Leaves.begin(), FirstFullyTested)); + } + for (const auto &Leaf : Leaves) { + if (!Leaf.isFullyTraversed()) { + PrintError("Leaf " + Leaf.getName() + " is not fully traversed"); + PrintNote("This indicates a missing partitioner within tblgen"); + Leaf.dump(errs()); + for (unsigned InstrIdx : Leaf.untested_instrs()) + PrintNote("Instr " + llvm::to_string(*Leaf.getInstr(InstrIdx))); + for (unsigned EdgeIdx : Leaf.untested_edges()) + PrintNote("Edge " + llvm::to_string(*Leaf.getEdge(EdgeIdx))); + } + } + + // Copy out information about untested predicates so the user of the tree + // can deal with them. + for (auto LeafPair : zip(Leaves, TreeNode->possible_leaves())) { + const GIMatchTreeBuilderLeafInfo &BuilderLeaf = std::get<0>(LeafPair); + GIMatchTreeLeafInfo &TreeLeaf = std::get<1>(LeafPair); + if (!BuilderLeaf.isFullyTested()) + for (unsigned PredicateIdx : BuilderLeaf.untested_predicates()) + TreeLeaf.addUntestedPredicate(BuilderLeaf.getPredicate(PredicateIdx)); + } + return; + } + + LLVM_DEBUG(dbgs() << " Weighing up partitioners:\n"); + evaluatePartitioners(); + + // Select the best partitioner by its ability to partition + // - Prefer partitioners that don't distinguish between partitions. This + // is to fail early on decisions that must go a single way. + auto PartitionerI = std::max_element( + Partitioners.begin(), Partitioners.end(), + [](const std::unique_ptr &A, + const std::unique_ptr &B) { + // We generally want partitioners that subdivide the + // ruleset as much as possible since these take fewer + // checks to converge on a particular rule. However, + // it's important to note that one leaf can end up in + // multiple partitions if the check isn't mutually + // exclusive (e.g. getVRegDef() vs isReg()). + // We therefore minimize average leaves per partition. + return (double)A->getNumLeavesWithDupes() / A->getNumPartitions() > + (double)B->getNumLeavesWithDupes() / B->getNumPartitions(); + }); + + // Select a partitioner and partition the ruleset + // Note that it's possible for a single rule to end up in multiple + // partitions. For example, an opcode test on a rule without an opcode + // predicate will result in it being passed to all partitions. + std::unique_ptr Partitioner = std::move(*PartitionerI); + Partitioners.erase(PartitionerI); + LLVM_DEBUG(dbgs() << " Selected partitioner: "; + Partitioner->emitDescription(dbgs()); dbgs() << "\n"); + + assert(Partitioner->getNumPartitions() > 0 && + "Must always partition into at least one partition"); + + TreeNode->setNumChildren(Partitioner->getNumPartitions()); + for (auto &C : enumerate(TreeNode->children())) { + SubtreeBuilders.emplace_back(&C.value(), NextInstrID); + Partitioner->applyForPartition(C.index(), *this, SubtreeBuilders.back()); + } + + TreeNode->setPartitioner(std::move(Partitioner)); + + // Recurse into the subtree builders. Each one must get a copy of the + // remaining partitioners as each path has to check everything. + for (auto &SubtreeBuilder : SubtreeBuilders) { + for (const auto &Partitioner : Partitioners) + SubtreeBuilder.addPartitioner(Partitioner->clone()); + SubtreeBuilder.runStep(); + } +} + +std::unique_ptr GIMatchTreeBuilder::run() { + unsigned NewInstrID = allocInstrID(); + // Start by recording the root instruction as instr #0 and set up the initial + // partitioners. + for (auto &Leaf : Leaves) { + LLVM_DEBUG(Leaf.getMatchDag().writeDOTGraph(dbgs(), Leaf.getName())); + GIMatchDagInstr *Root = + *(Leaf.getMatchDag().roots().begin() + Leaf.getRootIdx()); + Leaf.declareInstr(Root, NewInstrID); + } + + addPartitionersForInstr(NewInstrID); + + std::unique_ptr TreeRoot = std::make_unique(); + TreeNode = TreeRoot.get(); + runStep(); + + return TreeRoot; +} + +void GIMatchTreeOpcodePartitioner::emitPartitionName(raw_ostream &OS, unsigned Idx) const { + if (PartitionToInstr[Idx] == nullptr) { + OS << "* or nullptr"; + return; + } + OS << PartitionToInstr[Idx]->Namespace + << "::" << PartitionToInstr[Idx]->TheDef->getName(); +} + +void GIMatchTreeOpcodePartitioner::repartition( + GIMatchTreeBuilder::LeafVec &Leaves) { + Partitions.clear(); + InstrToPartition.clear(); + PartitionToInstr.clear(); + TestedPredicates.clear(); + + for (const auto &Leaf : enumerate(Leaves)) { + bool AllOpcodes = true; + GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); + BitVector TestedPredicatesForLeaf( + Leaf.value().getMatchDag().getNumPredicates()); + + // If the instruction isn't declared then we don't care about it. Ignore + // it for now and add it to all partitions later once we know what + // partitions we have. + if (!InstrInfo) { + LLVM_DEBUG(dbgs() << " " << Leaf.value().getName() + << " doesn't care about Instr[" << InstrID << "]\n"); + assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates()); + TestedPredicates.push_back(TestedPredicatesForLeaf); + continue; + } + + // If the opcode is available to test then any opcode predicates will have + // been enabled too. + for (const auto &PIdx : Leaf.value().TestablePredicates.set_bits()) { + const auto &P = Leaf.value().getPredicate(PIdx); + SmallVector OpcodesForThisPredicate; + if (const auto *OpcodeP = dyn_cast(P)) { + // We've found _an_ opcode predicate, but we don't know if it's + // checking this instruction yet. + bool IsThisPredicate = false; + for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) { + if (PDep->getRequiredMI() == InstrInfo->getInstrNode() && + PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) { + IsThisPredicate = true; + break; + } + } + if (!IsThisPredicate) + continue; + + // If we get here twice then we've somehow ended up with two opcode + // predicates for one instruction in the same DAG. That should be + // impossible. + assert(AllOpcodes && "Conflicting opcode predicates"); + const CodeGenInstruction *Expected = OpcodeP->getInstr(); + OpcodesForThisPredicate.push_back(Expected); + } + + if (const auto *OpcodeP = + dyn_cast(P)) { + // We've found _an_ oneof(opcodes) predicate, but we don't know if it's + // checking this instruction yet. + bool IsThisPredicate = false; + for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) { + if (PDep->getRequiredMI() == InstrInfo->getInstrNode() && + PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) { + IsThisPredicate = true; + break; + } + } + if (!IsThisPredicate) + continue; + + // If we get here twice then we've somehow ended up with two opcode + // predicates for one instruction in the same DAG. That should be + // impossible. + assert(AllOpcodes && "Conflicting opcode predicates"); + for (const CodeGenInstruction *Expected : OpcodeP->getInstrs()) + OpcodesForThisPredicate.push_back(Expected); + } + + for (const CodeGenInstruction *Expected : OpcodesForThisPredicate) { + // Mark this predicate as one we're testing. + TestedPredicatesForLeaf.set(PIdx); + + // Partitions must be numbered 0, 1, .., N but instructions don't meet + // that requirement. Assign a partition number to each opcode if we + // lack one ... + auto Partition = InstrToPartition.find(Expected); + if (Partition == InstrToPartition.end()) { + BitVector Contents(Leaves.size()); + Partition = InstrToPartition + .insert(std::make_pair(Expected, Partitions.size())) + .first; + PartitionToInstr.push_back(Expected); + Partitions.insert(std::make_pair(Partitions.size(), Contents)); + } + // ... and mark this leaf as being in that partition. + Partitions.find(Partition->second)->second.set(Leaf.index()); + AllOpcodes = false; + LLVM_DEBUG(dbgs() << " " << Leaf.value().getName() + << " is in partition " << Partition->second << "\n"); + } + + // TODO: This is where we would handle multiple choices of opcode + // the end result will be that this leaf ends up in multiple + // partitions similarly to AllOpcodes. + } + + // If we never check the opcode, add it to every partition. + if (AllOpcodes) { + // Add a partition for the default case if we don't already have one. + if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) { + PartitionToInstr.push_back(nullptr); + BitVector Contents(Leaves.size()); + Partitions.insert(std::make_pair(Partitions.size(), Contents)); + } + LLVM_DEBUG(dbgs() << " " << Leaf.value().getName() + << " is in all partitions (opcode not checked)\n"); + for (auto &Partition : Partitions) + Partition.second.set(Leaf.index()); + } + + assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates()); + TestedPredicates.push_back(TestedPredicatesForLeaf); + } + + if (Partitions.size() == 0) { + // Add a partition for the default case if we don't already have one. + if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) { + PartitionToInstr.push_back(nullptr); + BitVector Contents(Leaves.size()); + Partitions.insert(std::make_pair(Partitions.size(), Contents)); + } + } + + // Add any leaves that don't care about this instruction to all partitions. + for (const auto &Leaf : enumerate(Leaves)) { + GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); + if (!InstrInfo) { + // Add a partition for the default case if we don't already have one. + if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) { + PartitionToInstr.push_back(nullptr); + BitVector Contents(Leaves.size()); + Partitions.insert(std::make_pair(Partitions.size(), Contents)); + } + for (auto &Partition : Partitions) + Partition.second.set(Leaf.index()); + } + } + +} + +void GIMatchTreeOpcodePartitioner::applyForPartition( + unsigned PartitionIdx, GIMatchTreeBuilder &Builder, GIMatchTreeBuilder &SubBuilder) { + LLVM_DEBUG(dbgs() << " Making partition " << PartitionIdx << "\n"); + const CodeGenInstruction *CGI = PartitionToInstr[PartitionIdx]; + + BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx); + // Consume any predicates we handled. + for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) { + if (!PossibleLeaves[EnumeratedLeaf.index()]) + continue; + + auto &Leaf = EnumeratedLeaf.value(); + const auto &TestedPredicatesForLeaf = + TestedPredicates[EnumeratedLeaf.index()]; + + for (unsigned PredIdx : TestedPredicatesForLeaf.set_bits()) { + LLVM_DEBUG(dbgs() << " " << Leaf.getName() << " tested predicate #" + << PredIdx << " of " << TestedPredicatesForLeaf.size() + << " " << *Leaf.getPredicate(PredIdx) << "\n"); + Leaf.RemainingPredicates.reset(PredIdx); + Leaf.TestablePredicates.reset(PredIdx); + } + SubBuilder.addLeaf(Leaf); + } + + // Nothing to do, we don't know anything about this instruction as a result + // of this partitioner. + if (CGI == nullptr) + return; + + GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves(); + // Find all the operands we know to exist and are referenced. This will + // usually be all the referenced operands but there are some cases where + // instructions are variadic. Such operands must be handled by partitioners + // that check the number of operands. + BitVector ReferencedOperands(1); + for (auto &Leaf : NewLeaves) { + GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID); + // Skip any leaves that don't care about this instruction. + if (!InstrInfo) + continue; + const GIMatchDagInstr *Instr = InstrInfo->getInstrNode(); + for (auto &E : enumerate(Leaf.getMatchDag().edges())) { + if (E.value()->getFromMI() == Instr && + E.value()->getFromMO()->getIdx() < CGI->Operands.size()) { + ReferencedOperands.resize(E.value()->getFromMO()->getIdx() + 1); + ReferencedOperands.set(E.value()->getFromMO()->getIdx()); + } + } + } + for (auto &Leaf : NewLeaves) { + for (unsigned OpIdx : ReferencedOperands.set_bits()) { + Leaf.declareOperand(InstrID, OpIdx); + } + } + for (unsigned OpIdx : ReferencedOperands.set_bits()) { + SubBuilder.addPartitionersForOperand(InstrID, OpIdx); + } +} + +void GIMatchTreeOpcodePartitioner::emitPartitionResults( + raw_ostream &OS) const { + OS << "Partitioning by opcode would produce " << Partitions.size() + << " partitions\n"; + for (const auto &Partition : InstrToPartition) { + if (Partition.first == nullptr) + OS << "Default: "; + else + OS << Partition.first->TheDef->getName() << ": "; + StringRef Separator = ""; + for (unsigned I : Partitions.find(Partition.second)->second.set_bits()) { + OS << Separator << I; + Separator = ", "; + } + OS << "\n"; + } +} + +void GIMatchTreeOpcodePartitioner::generatePartitionSelectorCode( + raw_ostream &OS, StringRef Indent) const { + OS << Indent << "Partition = -1;\n" + << Indent << "switch (MIs[" << InstrID << "]->getOpcode()) {\n"; + for (const auto &EnumInstr : enumerate(PartitionToInstr)) { + if (EnumInstr.value() == nullptr) + OS << Indent << "default:"; + else + OS << Indent << "case " << EnumInstr.value()->Namespace + << "::" << EnumInstr.value()->TheDef->getName() << ":"; + OS << " Partition = " << EnumInstr.index() << "; break;\n"; + } + OS << Indent << "}\n" + << Indent + << "// Default case but without conflicting with potential default case " + "in selection.\n" + << Indent << "if (Partition == -1) return false;\n"; +} + +void GIMatchTreeVRegDefPartitioner::addToPartition(bool Result, + unsigned LeafIdx) { + auto I = ResultToPartition.find(Result); + if (I == ResultToPartition.end()) { + ResultToPartition.insert(std::make_pair(Result, PartitionToResult.size())); + PartitionToResult.push_back(Result); + } + I = ResultToPartition.find(Result); + auto P = Partitions.find(I->second); + if (P == Partitions.end()) + P = Partitions.insert(std::make_pair(I->second, BitVector())).first; + P->second.resize(LeafIdx + 1); + P->second.set(LeafIdx); +}; + +void GIMatchTreeVRegDefPartitioner::repartition( + GIMatchTreeBuilder::LeafVec &Leaves) { + Partitions.clear(); + + for (const auto &Leaf : enumerate(Leaves)) { + GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); + BitVector TraversedEdgesForLeaf(Leaf.value().getMatchDag().getNumEdges()); + + // If the instruction isn't declared then we don't care about it. Ignore + // it for now and add it to all partitions later once we know what + // partitions we have. + if (!InstrInfo) { + TraversedEdges.push_back(TraversedEdgesForLeaf); + continue; + } + + // If this node has an use -> def edge from this operand then this + // instruction must be in partition 1 (isVRegDef()). + bool WantsEdge = false; + for (const auto &EIdx : Leaf.value().TraversableEdges.set_bits()) { + const auto &E = Leaf.value().getEdge(EIdx); + if (E->getFromMI() != InstrInfo->getInstrNode() || + E->getFromMO()->getIdx() != OpIdx || E->isDefToUse()) + continue; + + // We're looking at the right edge. This leaf wants a vreg def so we'll + // put it in partition 1. + addToPartition(true, Leaf.index()); + TraversedEdgesForLeaf.set(EIdx); + WantsEdge = true; + } + + bool isNotReg = false; + if (!WantsEdge && isNotReg) { + // If this leaf doesn't have an edge and we _don't_ want a register, + // then add it to partition 0. + addToPartition(false, Leaf.index()); + } else if (!WantsEdge) { + // If this leaf doesn't have an edge and we don't know what we want, + // then add it to partition 0 and 1. + addToPartition(false, Leaf.index()); + addToPartition(true, Leaf.index()); + } + + TraversedEdges.push_back(TraversedEdgesForLeaf); + } + + // Add any leaves that don't care about this instruction to all partitions. + for (const auto &Leaf : enumerate(Leaves)) { + GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); + if (!InstrInfo) + for (auto &Partition : Partitions) + Partition.second.set(Leaf.index()); + } +} + +void GIMatchTreeVRegDefPartitioner::applyForPartition( + unsigned PartitionIdx, GIMatchTreeBuilder &Builder, + GIMatchTreeBuilder &SubBuilder) { + BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx); + + std::vector TraversedEdgesByNewLeaves; + // Consume any edges we handled. + for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) { + if (!PossibleLeaves[EnumeratedLeaf.index()]) + continue; + + auto &Leaf = EnumeratedLeaf.value(); + const auto &TraversedEdgesForLeaf = TraversedEdges[EnumeratedLeaf.index()]; + TraversedEdgesByNewLeaves.push_back(TraversedEdgesForLeaf); + Leaf.RemainingEdges.reset(TraversedEdgesForLeaf); + Leaf.TraversableEdges.reset(TraversedEdgesForLeaf); + SubBuilder.addLeaf(Leaf); + } + + // Nothing to do. The only thing we know is that it isn't a vreg-def. + if (PartitionToResult[PartitionIdx] == false) + return; + + NewInstrID = SubBuilder.allocInstrID(); + + GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves(); + for (const auto &I : zip(NewLeaves, TraversedEdgesByNewLeaves)) { + auto &Leaf = std::get<0>(I); + auto &TraversedEdgesForLeaf = std::get<1>(I); + GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID); + // Skip any leaves that don't care about this instruction. + if (!InstrInfo) + continue; + for (const auto &EIdx : TraversedEdgesForLeaf.set_bits()) { + const GIMatchDagEdge *E = Leaf.getEdge(EIdx); + Leaf.declareInstr(E->getToMI(), NewInstrID); + } + } + SubBuilder.addPartitionersForInstr(NewInstrID); +} + +void GIMatchTreeVRegDefPartitioner::emitPartitionResults( + raw_ostream &OS) const { + OS << "Partitioning by vreg-def would produce " << Partitions.size() + << " partitions\n"; + for (const auto &Partition : Partitions) { + OS << Partition.first << " ("; + emitPartitionName(OS, Partition.first); + OS << "): "; + StringRef Separator = ""; + for (unsigned I : Partition.second.set_bits()) { + OS << Separator << I; + Separator = ", "; + } + OS << "\n"; + } +} + +void GIMatchTreeVRegDefPartitioner::generatePartitionSelectorCode( + raw_ostream &OS, StringRef Indent) const { + OS << Indent << "Partition = -1\n" + << Indent << "if (MIs.size() <= NewInstrID) MIs.resize(NewInstrID + 1);\n" + << Indent << "MIs[" << NewInstrID << "] = nullptr;\n" + << Indent << "if (MIs[" << InstrID << "].getOperand(" << OpIdx + << ").isReg()))\n" + << Indent << " MIs[" << NewInstrID << "] = MRI.getVRegDef(MIs[" << InstrID + << "].getOperand(" << OpIdx << ").getReg()));\n"; + + for (const auto &Pair : ResultToPartition) + OS << Indent << "if (MIs[" << NewInstrID << "] " + << (Pair.first ? "==" : "!=") + << " nullptr) Partition = " << Pair.second << ";\n"; + + OS << Indent << "if (Partition == -1) return false;\n"; +} +