| //===- 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/Debug.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 = find(MatchDag.instr_nodes(), 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<GIMatchTreeOpcodePartitioner>(InstrIdx)); |
| } |
| |
| void GIMatchTreeBuilder::addPartitionersForOperand(unsigned InstrID, |
| unsigned OpIdx) { |
| LLVM_DEBUG(dbgs() << "Add partitioners for Instrs[" << InstrID |
| << "].getOperand(" << OpIdx << ")\n"); |
| addPartitioner( |
| std::make_unique<GIMatchTreeVRegDefPartitioner>(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 = |
| llvm::find_if(Leaves, [](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<GIMatchTreePartitioner> &A, |
| const std::unique_ptr<GIMatchTreePartitioner> &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<GIMatchTreePartitioner> 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<GIMatchTree> 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<GIMatchTree> TreeRoot = std::make_unique<GIMatchTree>(); |
| 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 (unsigned PIdx : Leaf.value().TestablePredicates.set_bits()) { |
| const auto &P = Leaf.value().getPredicate(PIdx); |
| SmallVector<const CodeGenInstruction *, 1> OpcodesForThisPredicate; |
| if (const auto *OpcodeP = dyn_cast<const GIMatchDagOpcodePredicate>(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<const GIMatchDagOneOfOpcodesPredicate>(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"); |
| append_range(OpcodesForThisPredicate, OpcodeP->getInstrs()); |
| } |
| |
| 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 { |
| // Make sure not to emit empty switch or switch with just default |
| if (PartitionToInstr.size() == 1 && PartitionToInstr[0] == nullptr) { |
| OS << Indent << "Partition = 0;\n"; |
| } else if (PartitionToInstr.size()) { |
| 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"; |
| } |
| OS << 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 (unsigned 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<BitVector> 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 (unsigned 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"; |
| } |
