1 //===- GIMatchTree.cpp - A decision tree to match GIMatchDag's ------------===//
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 #include "GIMatchTree.h"
11 #include "../CodeGenInstruction.h"
13 #include "llvm/Support/Format.h"
14 #include "llvm/Support/ScopedPrinter.h"
15 #include "llvm/Support/raw_ostream.h"
16 #include "llvm/TableGen/Error.h"
17 #include "llvm/TableGen/Record.h"
19 #define DEBUG_TYPE "gimatchtree"
23 void GIMatchTree::writeDOTGraph(raw_ostream &OS) const {
24 OS << "digraph \"matchtree\" {\n";
25 writeDOTGraphNode(OS);
29 void GIMatchTree::writeDOTGraphNode(raw_ostream &OS) const {
30 OS << format(" Node%p", this) << " [shape=record,label=\"{";
32 Partitioner->emitDescription(OS);
33 OS << "|" << Partitioner->getNumPartitions() << " partitions|";
35 OS << "No partitioner|";
36 bool IsFullyTraversed = true;
37 bool IsFullyTested = true;
38 StringRef Separator = "";
39 for (const auto &Leaf : PossibleLeaves) {
40 OS << Separator << Leaf.getName();
42 if (!Leaf.isFullyTraversed())
43 IsFullyTraversed = false;
44 if (!Leaf.isFullyTested())
45 IsFullyTested = false;
47 if (!Partitioner && !IsFullyTraversed)
48 OS << "|Not fully traversed";
49 if (!Partitioner && !IsFullyTested) {
50 OS << "|Not fully tested";
51 if (IsFullyTraversed) {
52 for (const GIMatchTreeLeafInfo &Leaf : PossibleLeaves) {
53 if (Leaf.isFullyTested())
55 OS << "\\n" << Leaf.getName() << ": " << &Leaf;
56 for (const GIMatchDagPredicate *P : Leaf.untested_predicates())
63 (!IsFullyTraversed || !IsFullyTested || PossibleLeaves.size() > 1))
66 for (const auto &C : Children)
67 C.writeDOTGraphNode(OS);
68 writeDOTGraphEdges(OS);
71 void GIMatchTree::writeDOTGraphEdges(raw_ostream &OS) const {
72 for (const auto &Child : enumerate(Children)) {
73 OS << format(" Node%p", this) << " -> " << format("Node%p", &Child.value())
74 << " [label=\"#" << Child.index() << " ";
75 Partitioner->emitPartitionName(OS, Child.index());
80 GIMatchTreeBuilderLeafInfo::GIMatchTreeBuilderLeafInfo(
81 GIMatchTreeBuilder &Builder, StringRef Name, unsigned RootIdx,
82 const GIMatchDag &MatchDag, void *Data)
83 : Builder(Builder), Info(Name, RootIdx, Data), MatchDag(MatchDag),
85 RemainingInstrNodes(BitVector(MatchDag.getNumInstrNodes(), true)),
86 RemainingEdges(BitVector(MatchDag.getNumEdges(), true)),
87 RemainingPredicates(BitVector(MatchDag.getNumPredicates(), true)),
88 TraversableEdges(MatchDag.getNumEdges()),
89 TestablePredicates(MatchDag.getNumPredicates()) {
90 // Number all the predicates in this DAG
91 for (auto &P : enumerate(MatchDag.predicates())) {
92 PredicateIDs.insert(std::make_pair(P.value(), P.index()));
95 // Number all the predicate dependencies in this DAG and set up a bitvector
96 // for each predicate indicating the unsatisfied dependencies.
97 for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
98 PredicateDepIDs.insert(std::make_pair(Dep.value(), Dep.index()));
100 UnsatisfiedPredDepsForPred.resize(MatchDag.getNumPredicates(),
101 BitVector(PredicateDepIDs.size()));
102 for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
103 unsigned ID = PredicateIDs.lookup(Dep.value()->getPredicate());
104 UnsatisfiedPredDepsForPred[ID].set(Dep.index());
108 void GIMatchTreeBuilderLeafInfo::declareInstr(const GIMatchDagInstr *Instr, unsigned ID) {
109 // Record the assignment of this instr to the given ID.
110 auto InfoI = InstrNodeToInfo.insert(std::make_pair(
111 Instr, GIMatchTreeInstrInfo(ID, Instr)));
112 InstrIDToInfo.insert(std::make_pair(ID, &InfoI.first->second));
114 if (Instr == nullptr)
117 if (!Instr->getUserAssignedName().empty())
118 Info.bindInstrVariable(Instr->getUserAssignedName(), ID);
119 for (const auto &VarBinding : Instr->user_assigned_operand_names())
120 Info.bindOperandVariable(VarBinding.second, ID, VarBinding.first);
122 // Clear the bit indicating we haven't visited this instr.
123 const auto &NodeI = std::find(MatchDag.instr_nodes_begin(),
124 MatchDag.instr_nodes_end(), Instr);
125 assert(NodeI != MatchDag.instr_nodes_end() && "Instr isn't in this DAG");
126 unsigned InstrIdx = MatchDag.getInstrNodeIdx(NodeI);
127 RemainingInstrNodes.reset(InstrIdx);
129 // When we declare an instruction, we don't expose any traversable edges just
130 // yet. A partitioner has to check they exist and are registers before they
133 // When we declare an instruction, we potentially activate some predicates.
134 // Mark the dependencies that are now satisfied as a result of this
135 // instruction and mark any predicates whose dependencies are fully
137 for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
138 if (Dep.value()->getRequiredMI() == Instr &&
139 Dep.value()->getRequiredMO() == nullptr) {
140 for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
141 DepsFor.value().reset(Dep.index());
142 if (DepsFor.value().none())
143 TestablePredicates.set(DepsFor.index());
149 void GIMatchTreeBuilderLeafInfo::declareOperand(unsigned InstrID,
151 const GIMatchDagInstr *Instr = InstrIDToInfo.lookup(InstrID)->getInstrNode();
153 OperandIDToInfo.insert(std::make_pair(
154 std::make_pair(InstrID, OpIdx),
155 GIMatchTreeOperandInfo(Instr, OpIdx)));
157 // When an operand becomes reachable, we potentially activate some traversals.
158 // Record the edges that can now be followed as a result of this
160 for (auto &E : enumerate(MatchDag.edges())) {
161 if (E.value()->getFromMI() == Instr &&
162 E.value()->getFromMO()->getIdx() == OpIdx) {
163 TraversableEdges.set(E.index());
167 // When an operand becomes reachable, we potentially activate some predicates.
168 // Clear the dependencies that are now satisfied as a result of this
169 // operand and activate any predicates whose dependencies are fully
171 for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
172 if (Dep.value()->getRequiredMI() == Instr && Dep.value()->getRequiredMO() &&
173 Dep.value()->getRequiredMO()->getIdx() == OpIdx) {
174 for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
175 DepsFor.value().reset(Dep.index());
176 if (DepsFor.value().none())
177 TestablePredicates.set(DepsFor.index());
183 void GIMatchTreeBuilder::addPartitionersForInstr(unsigned InstrIdx) {
184 // Find the partitioners that can be used now that this node is
185 // uncovered. Our choices are:
187 addPartitioner(std::make_unique<GIMatchTreeOpcodePartitioner>(InstrIdx));
190 void GIMatchTreeBuilder::addPartitionersForOperand(unsigned InstrID,
192 LLVM_DEBUG(dbgs() << "Add partitioners for Instrs[" << InstrID
193 << "].getOperand(" << OpIdx << ")\n");
195 std::make_unique<GIMatchTreeVRegDefPartitioner>(InstrID, OpIdx));
198 void GIMatchTreeBuilder::filterRedundantPartitioners() {
199 // TODO: Filter partitioners for facts that are already known
200 // - If we know the opcode, we can elide the num operand check so long as
201 // the instruction has a fixed number of operands.
202 // - If we know an exact number of operands then we can elide further number
203 // of operand checks.
204 // - If the current min number of operands exceeds the one we want to check
205 // then we can elide it.
208 void GIMatchTreeBuilder::evaluatePartitioners() {
209 // Determine the partitioning the partitioner would produce
210 for (auto &Partitioner : Partitioners) {
211 LLVM_DEBUG(dbgs() << " Weighing up ";
212 Partitioner->emitDescription(dbgs()); dbgs() << "\n");
213 Partitioner->repartition(Leaves);
214 LLVM_DEBUG(Partitioner->emitPartitionResults(dbgs()));
218 void GIMatchTreeBuilder::runStep() {
219 LLVM_DEBUG(dbgs() << "Building match tree node for " << TreeNode << "\n");
220 LLVM_DEBUG(dbgs() << " Rules reachable at this node:\n");
221 for (const auto &Leaf : Leaves) {
222 LLVM_DEBUG(dbgs() << " " << Leaf.getName() << " (" << &Leaf.getInfo() << "\n");
223 TreeNode->addPossibleLeaf(Leaf.getInfo(), Leaf.isFullyTraversed(),
224 Leaf.isFullyTested());
227 LLVM_DEBUG(dbgs() << " Partitioners available at this node:\n");
229 for (const auto &Partitioner : Partitioners)
230 LLVM_DEBUG(dbgs() << " "; Partitioner->emitDescription(dbgs());
232 #endif // ifndef NDEBUG
234 // Check for unreachable rules. Rules are unreachable if they are preceeded by
235 // a fully tested rule.
236 // Note: This is only true for the current algorithm, if we allow the
237 // algorithm to compare equally valid rules then they will become
240 auto FullyTestedLeafI = Leaves.end();
241 for (auto LeafI = Leaves.begin(), LeafE = Leaves.end();
242 LeafI != LeafE; ++LeafI) {
243 if (LeafI->isFullyTraversed() && LeafI->isFullyTested())
244 FullyTestedLeafI = LeafI;
245 else if (FullyTestedLeafI != Leaves.end()) {
246 PrintError("Leaf " + LeafI->getName() + " is unreachable");
247 PrintNote("Leaf " + FullyTestedLeafI->getName() +
248 " will have already matched");
253 LLVM_DEBUG(dbgs() << " Eliminating redundant partitioners:\n");
254 filterRedundantPartitioners();
255 LLVM_DEBUG(dbgs() << " Partitioners remaining:\n");
257 for (const auto &Partitioner : Partitioners)
258 LLVM_DEBUG(dbgs() << " "; Partitioner->emitDescription(dbgs());
260 #endif // ifndef NDEBUG
262 if (Partitioners.empty()) {
263 // Nothing left to do but check we really did identify a single rule.
264 if (Leaves.size() > 1) {
265 LLVM_DEBUG(dbgs() << "Leaf contains multiple rules, drop after the first "
266 "fully tested rule\n");
267 auto FirstFullyTested =
268 std::find_if(Leaves.begin(), Leaves.end(),
269 [](const GIMatchTreeBuilderLeafInfo &X) {
270 return X.isFullyTraversed() && X.isFullyTested() &&
271 !X.getMatchDag().hasPostMatchPredicate();
273 if (FirstFullyTested != Leaves.end())
277 for (auto &Leaf : make_range(Leaves.begin(), FirstFullyTested))
278 LLVM_DEBUG(dbgs() << " Kept " << Leaf.getName() << "\n");
279 for (const auto &Leaf : make_range(FirstFullyTested, Leaves.end()))
280 LLVM_DEBUG(dbgs() << " Dropped " << Leaf.getName() << "\n");
281 #endif // ifndef NDEBUG
282 TreeNode->dropLeavesAfter(
283 std::distance(Leaves.begin(), FirstFullyTested));
285 for (const auto &Leaf : Leaves) {
286 if (!Leaf.isFullyTraversed()) {
287 PrintError("Leaf " + Leaf.getName() + " is not fully traversed");
288 PrintNote("This indicates a missing partitioner within tblgen");
290 for (unsigned InstrIdx : Leaf.untested_instrs())
291 PrintNote("Instr " + llvm::to_string(*Leaf.getInstr(InstrIdx)));
292 for (unsigned EdgeIdx : Leaf.untested_edges())
293 PrintNote("Edge " + llvm::to_string(*Leaf.getEdge(EdgeIdx)));
297 // Copy out information about untested predicates so the user of the tree
298 // can deal with them.
299 for (auto LeafPair : zip(Leaves, TreeNode->possible_leaves())) {
300 const GIMatchTreeBuilderLeafInfo &BuilderLeaf = std::get<0>(LeafPair);
301 GIMatchTreeLeafInfo &TreeLeaf = std::get<1>(LeafPair);
302 if (!BuilderLeaf.isFullyTested())
303 for (unsigned PredicateIdx : BuilderLeaf.untested_predicates())
304 TreeLeaf.addUntestedPredicate(BuilderLeaf.getPredicate(PredicateIdx));
309 LLVM_DEBUG(dbgs() << " Weighing up partitioners:\n");
310 evaluatePartitioners();
312 // Select the best partitioner by its ability to partition
313 // - Prefer partitioners that don't distinguish between partitions. This
314 // is to fail early on decisions that must go a single way.
315 auto PartitionerI = std::max_element(
316 Partitioners.begin(), Partitioners.end(),
317 [](const std::unique_ptr<GIMatchTreePartitioner> &A,
318 const std::unique_ptr<GIMatchTreePartitioner> &B) {
319 // We generally want partitioners that subdivide the
320 // ruleset as much as possible since these take fewer
321 // checks to converge on a particular rule. However,
322 // it's important to note that one leaf can end up in
323 // multiple partitions if the check isn't mutually
324 // exclusive (e.g. getVRegDef() vs isReg()).
325 // We therefore minimize average leaves per partition.
326 return (double)A->getNumLeavesWithDupes() / A->getNumPartitions() >
327 (double)B->getNumLeavesWithDupes() / B->getNumPartitions();
330 // Select a partitioner and partition the ruleset
331 // Note that it's possible for a single rule to end up in multiple
332 // partitions. For example, an opcode test on a rule without an opcode
333 // predicate will result in it being passed to all partitions.
334 std::unique_ptr<GIMatchTreePartitioner> Partitioner = std::move(*PartitionerI);
335 Partitioners.erase(PartitionerI);
336 LLVM_DEBUG(dbgs() << " Selected partitioner: ";
337 Partitioner->emitDescription(dbgs()); dbgs() << "\n");
339 assert(Partitioner->getNumPartitions() > 0 &&
340 "Must always partition into at least one partition");
342 TreeNode->setNumChildren(Partitioner->getNumPartitions());
343 for (auto &C : enumerate(TreeNode->children())) {
344 SubtreeBuilders.emplace_back(&C.value(), NextInstrID);
345 Partitioner->applyForPartition(C.index(), *this, SubtreeBuilders.back());
348 TreeNode->setPartitioner(std::move(Partitioner));
350 // Recurse into the subtree builders. Each one must get a copy of the
351 // remaining partitioners as each path has to check everything.
352 for (auto &SubtreeBuilder : SubtreeBuilders) {
353 for (const auto &Partitioner : Partitioners)
354 SubtreeBuilder.addPartitioner(Partitioner->clone());
355 SubtreeBuilder.runStep();
359 std::unique_ptr<GIMatchTree> GIMatchTreeBuilder::run() {
360 unsigned NewInstrID = allocInstrID();
361 // Start by recording the root instruction as instr #0 and set up the initial
363 for (auto &Leaf : Leaves) {
364 LLVM_DEBUG(Leaf.getMatchDag().writeDOTGraph(dbgs(), Leaf.getName()));
365 GIMatchDagInstr *Root =
366 *(Leaf.getMatchDag().roots().begin() + Leaf.getRootIdx());
367 Leaf.declareInstr(Root, NewInstrID);
370 addPartitionersForInstr(NewInstrID);
372 std::unique_ptr<GIMatchTree> TreeRoot = std::make_unique<GIMatchTree>();
373 TreeNode = TreeRoot.get();
379 void GIMatchTreeOpcodePartitioner::emitPartitionName(raw_ostream &OS, unsigned Idx) const {
380 if (PartitionToInstr[Idx] == nullptr) {
381 OS << "* or nullptr";
384 OS << PartitionToInstr[Idx]->Namespace
385 << "::" << PartitionToInstr[Idx]->TheDef->getName();
388 void GIMatchTreeOpcodePartitioner::repartition(
389 GIMatchTreeBuilder::LeafVec &Leaves) {
391 InstrToPartition.clear();
392 PartitionToInstr.clear();
393 TestedPredicates.clear();
395 for (const auto &Leaf : enumerate(Leaves)) {
396 bool AllOpcodes = true;
397 GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
398 BitVector TestedPredicatesForLeaf(
399 Leaf.value().getMatchDag().getNumPredicates());
401 // If the instruction isn't declared then we don't care about it. Ignore
402 // it for now and add it to all partitions later once we know what
403 // partitions we have.
405 LLVM_DEBUG(dbgs() << " " << Leaf.value().getName()
406 << " doesn't care about Instr[" << InstrID << "]\n");
407 assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates());
408 TestedPredicates.push_back(TestedPredicatesForLeaf);
412 // If the opcode is available to test then any opcode predicates will have
414 for (unsigned PIdx : Leaf.value().TestablePredicates.set_bits()) {
415 const auto &P = Leaf.value().getPredicate(PIdx);
416 SmallVector<const CodeGenInstruction *, 1> OpcodesForThisPredicate;
417 if (const auto *OpcodeP = dyn_cast<const GIMatchDagOpcodePredicate>(P)) {
418 // We've found _an_ opcode predicate, but we don't know if it's
419 // checking this instruction yet.
420 bool IsThisPredicate = false;
421 for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) {
422 if (PDep->getRequiredMI() == InstrInfo->getInstrNode() &&
423 PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) {
424 IsThisPredicate = true;
428 if (!IsThisPredicate)
431 // If we get here twice then we've somehow ended up with two opcode
432 // predicates for one instruction in the same DAG. That should be
434 assert(AllOpcodes && "Conflicting opcode predicates");
435 const CodeGenInstruction *Expected = OpcodeP->getInstr();
436 OpcodesForThisPredicate.push_back(Expected);
439 if (const auto *OpcodeP =
440 dyn_cast<const GIMatchDagOneOfOpcodesPredicate>(P)) {
441 // We've found _an_ oneof(opcodes) predicate, but we don't know if it's
442 // checking this instruction yet.
443 bool IsThisPredicate = false;
444 for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) {
445 if (PDep->getRequiredMI() == InstrInfo->getInstrNode() &&
446 PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) {
447 IsThisPredicate = true;
451 if (!IsThisPredicate)
454 // If we get here twice then we've somehow ended up with two opcode
455 // predicates for one instruction in the same DAG. That should be
457 assert(AllOpcodes && "Conflicting opcode predicates");
458 for (const CodeGenInstruction *Expected : OpcodeP->getInstrs())
459 OpcodesForThisPredicate.push_back(Expected);
462 for (const CodeGenInstruction *Expected : OpcodesForThisPredicate) {
463 // Mark this predicate as one we're testing.
464 TestedPredicatesForLeaf.set(PIdx);
466 // Partitions must be numbered 0, 1, .., N but instructions don't meet
467 // that requirement. Assign a partition number to each opcode if we
469 auto Partition = InstrToPartition.find(Expected);
470 if (Partition == InstrToPartition.end()) {
471 BitVector Contents(Leaves.size());
472 Partition = InstrToPartition
473 .insert(std::make_pair(Expected, Partitions.size()))
475 PartitionToInstr.push_back(Expected);
476 Partitions.insert(std::make_pair(Partitions.size(), Contents));
478 // ... and mark this leaf as being in that partition.
479 Partitions.find(Partition->second)->second.set(Leaf.index());
481 LLVM_DEBUG(dbgs() << " " << Leaf.value().getName()
482 << " is in partition " << Partition->second << "\n");
485 // TODO: This is where we would handle multiple choices of opcode
486 // the end result will be that this leaf ends up in multiple
487 // partitions similarly to AllOpcodes.
490 // If we never check the opcode, add it to every partition.
492 // Add a partition for the default case if we don't already have one.
493 if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
494 PartitionToInstr.push_back(nullptr);
495 BitVector Contents(Leaves.size());
496 Partitions.insert(std::make_pair(Partitions.size(), Contents));
498 LLVM_DEBUG(dbgs() << " " << Leaf.value().getName()
499 << " is in all partitions (opcode not checked)\n");
500 for (auto &Partition : Partitions)
501 Partition.second.set(Leaf.index());
504 assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates());
505 TestedPredicates.push_back(TestedPredicatesForLeaf);
508 if (Partitions.size() == 0) {
509 // Add a partition for the default case if we don't already have one.
510 if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
511 PartitionToInstr.push_back(nullptr);
512 BitVector Contents(Leaves.size());
513 Partitions.insert(std::make_pair(Partitions.size(), Contents));
517 // Add any leaves that don't care about this instruction to all partitions.
518 for (const auto &Leaf : enumerate(Leaves)) {
519 GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
521 // Add a partition for the default case if we don't already have one.
522 if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
523 PartitionToInstr.push_back(nullptr);
524 BitVector Contents(Leaves.size());
525 Partitions.insert(std::make_pair(Partitions.size(), Contents));
527 for (auto &Partition : Partitions)
528 Partition.second.set(Leaf.index());
534 void GIMatchTreeOpcodePartitioner::applyForPartition(
535 unsigned PartitionIdx, GIMatchTreeBuilder &Builder, GIMatchTreeBuilder &SubBuilder) {
536 LLVM_DEBUG(dbgs() << " Making partition " << PartitionIdx << "\n");
537 const CodeGenInstruction *CGI = PartitionToInstr[PartitionIdx];
539 BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
540 // Consume any predicates we handled.
541 for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
542 if (!PossibleLeaves[EnumeratedLeaf.index()])
545 auto &Leaf = EnumeratedLeaf.value();
546 const auto &TestedPredicatesForLeaf =
547 TestedPredicates[EnumeratedLeaf.index()];
549 for (unsigned PredIdx : TestedPredicatesForLeaf.set_bits()) {
550 LLVM_DEBUG(dbgs() << " " << Leaf.getName() << " tested predicate #"
551 << PredIdx << " of " << TestedPredicatesForLeaf.size()
552 << " " << *Leaf.getPredicate(PredIdx) << "\n");
553 Leaf.RemainingPredicates.reset(PredIdx);
554 Leaf.TestablePredicates.reset(PredIdx);
556 SubBuilder.addLeaf(Leaf);
559 // Nothing to do, we don't know anything about this instruction as a result
560 // of this partitioner.
564 GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves();
565 // Find all the operands we know to exist and are referenced. This will
566 // usually be all the referenced operands but there are some cases where
567 // instructions are variadic. Such operands must be handled by partitioners
568 // that check the number of operands.
569 BitVector ReferencedOperands(1);
570 for (auto &Leaf : NewLeaves) {
571 GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID);
572 // Skip any leaves that don't care about this instruction.
575 const GIMatchDagInstr *Instr = InstrInfo->getInstrNode();
576 for (auto &E : enumerate(Leaf.getMatchDag().edges())) {
577 if (E.value()->getFromMI() == Instr &&
578 E.value()->getFromMO()->getIdx() < CGI->Operands.size()) {
579 ReferencedOperands.resize(E.value()->getFromMO()->getIdx() + 1);
580 ReferencedOperands.set(E.value()->getFromMO()->getIdx());
584 for (auto &Leaf : NewLeaves) {
585 for (unsigned OpIdx : ReferencedOperands.set_bits()) {
586 Leaf.declareOperand(InstrID, OpIdx);
589 for (unsigned OpIdx : ReferencedOperands.set_bits()) {
590 SubBuilder.addPartitionersForOperand(InstrID, OpIdx);
594 void GIMatchTreeOpcodePartitioner::emitPartitionResults(
595 raw_ostream &OS) const {
596 OS << "Partitioning by opcode would produce " << Partitions.size()
598 for (const auto &Partition : InstrToPartition) {
599 if (Partition.first == nullptr)
602 OS << Partition.first->TheDef->getName() << ": ";
603 StringRef Separator = "";
604 for (unsigned I : Partitions.find(Partition.second)->second.set_bits()) {
605 OS << Separator << I;
612 void GIMatchTreeOpcodePartitioner::generatePartitionSelectorCode(
613 raw_ostream &OS, StringRef Indent) const {
614 OS << Indent << "Partition = -1;\n"
615 << Indent << "switch (MIs[" << InstrID << "]->getOpcode()) {\n";
616 for (const auto &EnumInstr : enumerate(PartitionToInstr)) {
617 if (EnumInstr.value() == nullptr)
618 OS << Indent << "default:";
620 OS << Indent << "case " << EnumInstr.value()->Namespace
621 << "::" << EnumInstr.value()->TheDef->getName() << ":";
622 OS << " Partition = " << EnumInstr.index() << "; break;\n";
624 OS << Indent << "}\n"
626 << "// Default case but without conflicting with potential default case "
628 << Indent << "if (Partition == -1) return false;\n";
631 void GIMatchTreeVRegDefPartitioner::addToPartition(bool Result,
633 auto I = ResultToPartition.find(Result);
634 if (I == ResultToPartition.end()) {
635 ResultToPartition.insert(std::make_pair(Result, PartitionToResult.size()));
636 PartitionToResult.push_back(Result);
638 I = ResultToPartition.find(Result);
639 auto P = Partitions.find(I->second);
640 if (P == Partitions.end())
641 P = Partitions.insert(std::make_pair(I->second, BitVector())).first;
642 P->second.resize(LeafIdx + 1);
643 P->second.set(LeafIdx);
646 void GIMatchTreeVRegDefPartitioner::repartition(
647 GIMatchTreeBuilder::LeafVec &Leaves) {
650 for (const auto &Leaf : enumerate(Leaves)) {
651 GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
652 BitVector TraversedEdgesForLeaf(Leaf.value().getMatchDag().getNumEdges());
654 // If the instruction isn't declared then we don't care about it. Ignore
655 // it for now and add it to all partitions later once we know what
656 // partitions we have.
658 TraversedEdges.push_back(TraversedEdgesForLeaf);
662 // If this node has an use -> def edge from this operand then this
663 // instruction must be in partition 1 (isVRegDef()).
664 bool WantsEdge = false;
665 for (unsigned EIdx : Leaf.value().TraversableEdges.set_bits()) {
666 const auto &E = Leaf.value().getEdge(EIdx);
667 if (E->getFromMI() != InstrInfo->getInstrNode() ||
668 E->getFromMO()->getIdx() != OpIdx || E->isDefToUse())
671 // We're looking at the right edge. This leaf wants a vreg def so we'll
672 // put it in partition 1.
673 addToPartition(true, Leaf.index());
674 TraversedEdgesForLeaf.set(EIdx);
678 bool isNotReg = false;
679 if (!WantsEdge && isNotReg) {
680 // If this leaf doesn't have an edge and we _don't_ want a register,
681 // then add it to partition 0.
682 addToPartition(false, Leaf.index());
683 } else if (!WantsEdge) {
684 // If this leaf doesn't have an edge and we don't know what we want,
685 // then add it to partition 0 and 1.
686 addToPartition(false, Leaf.index());
687 addToPartition(true, Leaf.index());
690 TraversedEdges.push_back(TraversedEdgesForLeaf);
693 // Add any leaves that don't care about this instruction to all partitions.
694 for (const auto &Leaf : enumerate(Leaves)) {
695 GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
697 for (auto &Partition : Partitions)
698 Partition.second.set(Leaf.index());
702 void GIMatchTreeVRegDefPartitioner::applyForPartition(
703 unsigned PartitionIdx, GIMatchTreeBuilder &Builder,
704 GIMatchTreeBuilder &SubBuilder) {
705 BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
707 std::vector<BitVector> TraversedEdgesByNewLeaves;
708 // Consume any edges we handled.
709 for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
710 if (!PossibleLeaves[EnumeratedLeaf.index()])
713 auto &Leaf = EnumeratedLeaf.value();
714 const auto &TraversedEdgesForLeaf = TraversedEdges[EnumeratedLeaf.index()];
715 TraversedEdgesByNewLeaves.push_back(TraversedEdgesForLeaf);
716 Leaf.RemainingEdges.reset(TraversedEdgesForLeaf);
717 Leaf.TraversableEdges.reset(TraversedEdgesForLeaf);
718 SubBuilder.addLeaf(Leaf);
721 // Nothing to do. The only thing we know is that it isn't a vreg-def.
722 if (PartitionToResult[PartitionIdx] == false)
725 NewInstrID = SubBuilder.allocInstrID();
727 GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves();
728 for (const auto I : zip(NewLeaves, TraversedEdgesByNewLeaves)) {
729 auto &Leaf = std::get<0>(I);
730 auto &TraversedEdgesForLeaf = std::get<1>(I);
731 GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID);
732 // Skip any leaves that don't care about this instruction.
735 for (unsigned EIdx : TraversedEdgesForLeaf.set_bits()) {
736 const GIMatchDagEdge *E = Leaf.getEdge(EIdx);
737 Leaf.declareInstr(E->getToMI(), NewInstrID);
740 SubBuilder.addPartitionersForInstr(NewInstrID);
743 void GIMatchTreeVRegDefPartitioner::emitPartitionResults(
744 raw_ostream &OS) const {
745 OS << "Partitioning by vreg-def would produce " << Partitions.size()
747 for (const auto &Partition : Partitions) {
748 OS << Partition.first << " (";
749 emitPartitionName(OS, Partition.first);
751 StringRef Separator = "";
752 for (unsigned I : Partition.second.set_bits()) {
753 OS << Separator << I;
760 void GIMatchTreeVRegDefPartitioner::generatePartitionSelectorCode(
761 raw_ostream &OS, StringRef Indent) const {
762 OS << Indent << "Partition = -1\n"
763 << Indent << "if (MIs.size() <= NewInstrID) MIs.resize(NewInstrID + 1);\n"
764 << Indent << "MIs[" << NewInstrID << "] = nullptr;\n"
765 << Indent << "if (MIs[" << InstrID << "].getOperand(" << OpIdx
767 << Indent << " MIs[" << NewInstrID << "] = MRI.getVRegDef(MIs[" << InstrID
768 << "].getOperand(" << OpIdx << ").getReg()));\n";
770 for (const auto &Pair : ResultToPartition)
771 OS << Indent << "if (MIs[" << NewInstrID << "] "
772 << (Pair.first ? "==" : "!=")
773 << " nullptr) Partition = " << Pair.second << ";\n";
775 OS << Indent << "if (Partition == -1) return false;\n";