1356843Sdim//===- GIMatchTree.cpp - A decision tree to match GIMatchDag's ------------===// 2356843Sdim// 3356843Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4356843Sdim// See https://llvm.org/LICENSE.txt for license information. 5356843Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6356843Sdim// 7356843Sdim//===----------------------------------------------------------------------===// 8356843Sdim 9356843Sdim#include "GIMatchTree.h" 10356843Sdim 11356843Sdim#include "../CodeGenInstruction.h" 12356843Sdim 13356843Sdim#include "llvm/Support/Format.h" 14356843Sdim#include "llvm/Support/ScopedPrinter.h" 15356843Sdim#include "llvm/Support/raw_ostream.h" 16356843Sdim#include "llvm/TableGen/Error.h" 17356843Sdim#include "llvm/TableGen/Record.h" 18356843Sdim 19356843Sdim#define DEBUG_TYPE "gimatchtree" 20356843Sdim 21356843Sdimusing namespace llvm; 22356843Sdim 23356843Sdimvoid GIMatchTree::writeDOTGraph(raw_ostream &OS) const { 24356843Sdim OS << "digraph \"matchtree\" {\n"; 25356843Sdim writeDOTGraphNode(OS); 26356843Sdim OS << "}\n"; 27356843Sdim} 28356843Sdim 29356843Sdimvoid GIMatchTree::writeDOTGraphNode(raw_ostream &OS) const { 30356843Sdim OS << format(" Node%p", this) << " [shape=record,label=\"{"; 31356843Sdim if (Partitioner) { 32356843Sdim Partitioner->emitDescription(OS); 33356843Sdim OS << "|" << Partitioner->getNumPartitions() << " partitions|"; 34356843Sdim } else 35356843Sdim OS << "No partitioner|"; 36356843Sdim bool IsFullyTraversed = true; 37356843Sdim bool IsFullyTested = true; 38356843Sdim StringRef Separator = ""; 39356843Sdim for (const auto &Leaf : PossibleLeaves) { 40356843Sdim OS << Separator << Leaf.getName(); 41356843Sdim Separator = ","; 42356843Sdim if (!Leaf.isFullyTraversed()) 43356843Sdim IsFullyTraversed = false; 44356843Sdim if (!Leaf.isFullyTested()) 45356843Sdim IsFullyTested = false; 46356843Sdim } 47356843Sdim if (!Partitioner && !IsFullyTraversed) 48356843Sdim OS << "|Not fully traversed"; 49356843Sdim if (!Partitioner && !IsFullyTested) { 50356843Sdim OS << "|Not fully tested"; 51356843Sdim if (IsFullyTraversed) { 52356843Sdim for (const GIMatchTreeLeafInfo &Leaf : PossibleLeaves) { 53356843Sdim if (Leaf.isFullyTested()) 54356843Sdim continue; 55356843Sdim OS << "\\n" << Leaf.getName() << ": " << &Leaf; 56356843Sdim for (const GIMatchDagPredicate *P : Leaf.untested_predicates()) 57356843Sdim OS << *P; 58356843Sdim } 59356843Sdim } 60356843Sdim } 61356843Sdim OS << "}\""; 62356843Sdim if (!Partitioner && 63356843Sdim (!IsFullyTraversed || !IsFullyTested || PossibleLeaves.size() > 1)) 64356843Sdim OS << ",color=red"; 65356843Sdim OS << "]\n"; 66356843Sdim for (const auto &C : Children) 67356843Sdim C.writeDOTGraphNode(OS); 68356843Sdim writeDOTGraphEdges(OS); 69356843Sdim} 70356843Sdim 71356843Sdimvoid GIMatchTree::writeDOTGraphEdges(raw_ostream &OS) const { 72356843Sdim for (const auto &Child : enumerate(Children)) { 73356843Sdim OS << format(" Node%p", this) << " -> " << format("Node%p", &Child.value()) 74356843Sdim << " [label=\"#" << Child.index() << " "; 75356843Sdim Partitioner->emitPartitionName(OS, Child.index()); 76356843Sdim OS << "\"]\n"; 77356843Sdim } 78356843Sdim} 79356843Sdim 80356843SdimGIMatchTreeBuilderLeafInfo::GIMatchTreeBuilderLeafInfo( 81356843Sdim GIMatchTreeBuilder &Builder, StringRef Name, unsigned RootIdx, 82356843Sdim const GIMatchDag &MatchDag, void *Data) 83356843Sdim : Builder(Builder), Info(Name, RootIdx, Data), MatchDag(MatchDag), 84356843Sdim InstrNodeToInfo(), 85356843Sdim RemainingInstrNodes(BitVector(MatchDag.getNumInstrNodes(), true)), 86356843Sdim RemainingEdges(BitVector(MatchDag.getNumEdges(), true)), 87356843Sdim RemainingPredicates(BitVector(MatchDag.getNumPredicates(), true)), 88356843Sdim TraversableEdges(MatchDag.getNumEdges()), 89356843Sdim TestablePredicates(MatchDag.getNumPredicates()) { 90356843Sdim // Number all the predicates in this DAG 91356843Sdim for (auto &P : enumerate(MatchDag.predicates())) { 92356843Sdim PredicateIDs.insert(std::make_pair(P.value(), P.index())); 93356843Sdim } 94356843Sdim 95356843Sdim // Number all the predicate dependencies in this DAG and set up a bitvector 96356843Sdim // for each predicate indicating the unsatisfied dependencies. 97356843Sdim for (auto &Dep : enumerate(MatchDag.predicate_edges())) { 98356843Sdim PredicateDepIDs.insert(std::make_pair(Dep.value(), Dep.index())); 99356843Sdim } 100356843Sdim UnsatisfiedPredDepsForPred.resize(MatchDag.getNumPredicates(), 101356843Sdim BitVector(PredicateDepIDs.size())); 102356843Sdim for (auto &Dep : enumerate(MatchDag.predicate_edges())) { 103356843Sdim unsigned ID = PredicateIDs.lookup(Dep.value()->getPredicate()); 104356843Sdim UnsatisfiedPredDepsForPred[ID].set(Dep.index()); 105356843Sdim } 106356843Sdim} 107356843Sdim 108356843Sdimvoid GIMatchTreeBuilderLeafInfo::declareInstr(const GIMatchDagInstr *Instr, unsigned ID) { 109356843Sdim // Record the assignment of this instr to the given ID. 110356843Sdim auto InfoI = InstrNodeToInfo.insert(std::make_pair( 111356843Sdim Instr, GIMatchTreeInstrInfo(ID, Instr))); 112356843Sdim InstrIDToInfo.insert(std::make_pair(ID, &InfoI.first->second)); 113356843Sdim 114356843Sdim if (Instr == nullptr) 115356843Sdim return; 116356843Sdim 117356843Sdim if (!Instr->getUserAssignedName().empty()) 118356843Sdim Info.bindInstrVariable(Instr->getUserAssignedName(), ID); 119356843Sdim for (const auto &VarBinding : Instr->user_assigned_operand_names()) 120356843Sdim Info.bindOperandVariable(VarBinding.second, ID, VarBinding.first); 121356843Sdim 122356843Sdim // Clear the bit indicating we haven't visited this instr. 123356843Sdim const auto &NodeI = std::find(MatchDag.instr_nodes_begin(), 124356843Sdim MatchDag.instr_nodes_end(), Instr); 125356843Sdim assert(NodeI != MatchDag.instr_nodes_end() && "Instr isn't in this DAG"); 126356843Sdim unsigned InstrIdx = MatchDag.getInstrNodeIdx(NodeI); 127356843Sdim RemainingInstrNodes.reset(InstrIdx); 128356843Sdim 129356843Sdim // When we declare an instruction, we don't expose any traversable edges just 130356843Sdim // yet. A partitioner has to check they exist and are registers before they 131356843Sdim // are traversable. 132356843Sdim 133356843Sdim // When we declare an instruction, we potentially activate some predicates. 134356843Sdim // Mark the dependencies that are now satisfied as a result of this 135356843Sdim // instruction and mark any predicates whose dependencies are fully 136356843Sdim // satisfied. 137356843Sdim for (auto &Dep : enumerate(MatchDag.predicate_edges())) { 138356843Sdim if (Dep.value()->getRequiredMI() == Instr && 139356843Sdim Dep.value()->getRequiredMO() == nullptr) { 140356843Sdim for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) { 141356843Sdim DepsFor.value().reset(Dep.index()); 142356843Sdim if (DepsFor.value().none()) 143356843Sdim TestablePredicates.set(DepsFor.index()); 144356843Sdim } 145356843Sdim } 146356843Sdim } 147356843Sdim} 148356843Sdim 149356843Sdimvoid GIMatchTreeBuilderLeafInfo::declareOperand(unsigned InstrID, 150356843Sdim unsigned OpIdx) { 151356843Sdim const GIMatchDagInstr *Instr = InstrIDToInfo.lookup(InstrID)->getInstrNode(); 152356843Sdim 153356843Sdim OperandIDToInfo.insert(std::make_pair( 154356843Sdim std::make_pair(InstrID, OpIdx), 155356843Sdim GIMatchTreeOperandInfo(Instr, OpIdx))); 156356843Sdim 157356843Sdim // When an operand becomes reachable, we potentially activate some traversals. 158356843Sdim // Record the edges that can now be followed as a result of this 159356843Sdim // instruction. 160356843Sdim for (auto &E : enumerate(MatchDag.edges())) { 161356843Sdim if (E.value()->getFromMI() == Instr && 162356843Sdim E.value()->getFromMO()->getIdx() == OpIdx) { 163356843Sdim TraversableEdges.set(E.index()); 164356843Sdim } 165356843Sdim } 166356843Sdim 167356843Sdim // When an operand becomes reachable, we potentially activate some predicates. 168356843Sdim // Clear the dependencies that are now satisfied as a result of this 169356843Sdim // operand and activate any predicates whose dependencies are fully 170356843Sdim // satisfied. 171356843Sdim for (auto &Dep : enumerate(MatchDag.predicate_edges())) { 172356843Sdim if (Dep.value()->getRequiredMI() == Instr && Dep.value()->getRequiredMO() && 173356843Sdim Dep.value()->getRequiredMO()->getIdx() == OpIdx) { 174356843Sdim for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) { 175356843Sdim DepsFor.value().reset(Dep.index()); 176356843Sdim if (DepsFor.value().none()) 177356843Sdim TestablePredicates.set(DepsFor.index()); 178356843Sdim } 179356843Sdim } 180356843Sdim } 181356843Sdim} 182356843Sdim 183356843Sdimvoid GIMatchTreeBuilder::addPartitionersForInstr(unsigned InstrIdx) { 184356843Sdim // Find the partitioners that can be used now that this node is 185356843Sdim // uncovered. Our choices are: 186356843Sdim // - Test the opcode 187356843Sdim addPartitioner(std::make_unique<GIMatchTreeOpcodePartitioner>(InstrIdx)); 188356843Sdim} 189356843Sdim 190356843Sdimvoid GIMatchTreeBuilder::addPartitionersForOperand(unsigned InstrID, 191356843Sdim unsigned OpIdx) { 192356843Sdim LLVM_DEBUG(dbgs() << "Add partitioners for Instrs[" << InstrID 193356843Sdim << "].getOperand(" << OpIdx << ")\n"); 194356843Sdim addPartitioner( 195356843Sdim std::make_unique<GIMatchTreeVRegDefPartitioner>(InstrID, OpIdx)); 196356843Sdim} 197356843Sdim 198356843Sdimvoid GIMatchTreeBuilder::filterRedundantPartitioners() { 199356843Sdim // TODO: Filter partitioners for facts that are already known 200356843Sdim // - If we know the opcode, we can elide the num operand check so long as 201356843Sdim // the instruction has a fixed number of operands. 202356843Sdim // - If we know an exact number of operands then we can elide further number 203356843Sdim // of operand checks. 204356843Sdim // - If the current min number of operands exceeds the one we want to check 205356843Sdim // then we can elide it. 206356843Sdim} 207356843Sdim 208356843Sdimvoid GIMatchTreeBuilder::evaluatePartitioners() { 209356843Sdim // Determine the partitioning the partitioner would produce 210356843Sdim for (auto &Partitioner : Partitioners) { 211356843Sdim LLVM_DEBUG(dbgs() << " Weighing up "; 212356843Sdim Partitioner->emitDescription(dbgs()); dbgs() << "\n"); 213356843Sdim Partitioner->repartition(Leaves); 214356843Sdim LLVM_DEBUG(Partitioner->emitPartitionResults(dbgs())); 215356843Sdim } 216356843Sdim} 217356843Sdim 218356843Sdimvoid GIMatchTreeBuilder::runStep() { 219356843Sdim LLVM_DEBUG(dbgs() << "Building match tree node for " << TreeNode << "\n"); 220356843Sdim LLVM_DEBUG(dbgs() << " Rules reachable at this node:\n"); 221356843Sdim for (const auto &Leaf : Leaves) { 222356843Sdim LLVM_DEBUG(dbgs() << " " << Leaf.getName() << " (" << &Leaf.getInfo() << "\n"); 223356843Sdim TreeNode->addPossibleLeaf(Leaf.getInfo(), Leaf.isFullyTraversed(), 224356843Sdim Leaf.isFullyTested()); 225356843Sdim } 226356843Sdim 227356843Sdim LLVM_DEBUG(dbgs() << " Partitioners available at this node:\n"); 228356843Sdim#ifndef NDEBUG 229356843Sdim for (const auto &Partitioner : Partitioners) 230356843Sdim LLVM_DEBUG(dbgs() << " "; Partitioner->emitDescription(dbgs()); 231356843Sdim dbgs() << "\n"); 232356843Sdim#endif // ifndef NDEBUG 233356843Sdim 234356843Sdim // Check for unreachable rules. Rules are unreachable if they are preceeded by 235356843Sdim // a fully tested rule. 236356843Sdim // Note: This is only true for the current algorithm, if we allow the 237356843Sdim // algorithm to compare equally valid rules then they will become 238356843Sdim // reachable. 239356843Sdim { 240356843Sdim auto FullyTestedLeafI = Leaves.end(); 241356843Sdim for (auto LeafI = Leaves.begin(), LeafE = Leaves.end(); 242356843Sdim LeafI != LeafE; ++LeafI) { 243356843Sdim if (LeafI->isFullyTraversed() && LeafI->isFullyTested()) 244356843Sdim FullyTestedLeafI = LeafI; 245356843Sdim else if (FullyTestedLeafI != Leaves.end()) { 246356843Sdim PrintError("Leaf " + LeafI->getName() + " is unreachable"); 247356843Sdim PrintNote("Leaf " + FullyTestedLeafI->getName() + 248356843Sdim " will have already matched"); 249356843Sdim } 250356843Sdim } 251356843Sdim } 252356843Sdim 253356843Sdim LLVM_DEBUG(dbgs() << " Eliminating redundant partitioners:\n"); 254356843Sdim filterRedundantPartitioners(); 255356843Sdim LLVM_DEBUG(dbgs() << " Partitioners remaining:\n"); 256356843Sdim#ifndef NDEBUG 257356843Sdim for (const auto &Partitioner : Partitioners) 258356843Sdim LLVM_DEBUG(dbgs() << " "; Partitioner->emitDescription(dbgs()); 259356843Sdim dbgs() << "\n"); 260356843Sdim#endif // ifndef NDEBUG 261356843Sdim 262356843Sdim if (Partitioners.empty()) { 263356843Sdim // Nothing left to do but check we really did identify a single rule. 264356843Sdim if (Leaves.size() > 1) { 265356843Sdim LLVM_DEBUG(dbgs() << "Leaf contains multiple rules, drop after the first " 266356843Sdim "fully tested rule\n"); 267356843Sdim auto FirstFullyTested = 268356843Sdim std::find_if(Leaves.begin(), Leaves.end(), 269356843Sdim [](const GIMatchTreeBuilderLeafInfo &X) { 270356843Sdim return X.isFullyTraversed() && X.isFullyTested() && 271356843Sdim !X.getMatchDag().hasPostMatchPredicate(); 272356843Sdim }); 273356843Sdim if (FirstFullyTested != Leaves.end()) 274356843Sdim FirstFullyTested++; 275356843Sdim 276356843Sdim#ifndef NDEBUG 277356843Sdim for (auto &Leaf : make_range(Leaves.begin(), FirstFullyTested)) 278356843Sdim LLVM_DEBUG(dbgs() << " Kept " << Leaf.getName() << "\n"); 279356843Sdim for (const auto &Leaf : make_range(FirstFullyTested, Leaves.end())) 280356843Sdim LLVM_DEBUG(dbgs() << " Dropped " << Leaf.getName() << "\n"); 281356843Sdim#endif // ifndef NDEBUG 282356843Sdim TreeNode->dropLeavesAfter( 283356843Sdim std::distance(Leaves.begin(), FirstFullyTested)); 284356843Sdim } 285356843Sdim for (const auto &Leaf : Leaves) { 286356843Sdim if (!Leaf.isFullyTraversed()) { 287356843Sdim PrintError("Leaf " + Leaf.getName() + " is not fully traversed"); 288356843Sdim PrintNote("This indicates a missing partitioner within tblgen"); 289356843Sdim Leaf.dump(errs()); 290356843Sdim for (unsigned InstrIdx : Leaf.untested_instrs()) 291356843Sdim PrintNote("Instr " + llvm::to_string(*Leaf.getInstr(InstrIdx))); 292356843Sdim for (unsigned EdgeIdx : Leaf.untested_edges()) 293356843Sdim PrintNote("Edge " + llvm::to_string(*Leaf.getEdge(EdgeIdx))); 294356843Sdim } 295356843Sdim } 296356843Sdim 297356843Sdim // Copy out information about untested predicates so the user of the tree 298356843Sdim // can deal with them. 299356843Sdim for (auto LeafPair : zip(Leaves, TreeNode->possible_leaves())) { 300356843Sdim const GIMatchTreeBuilderLeafInfo &BuilderLeaf = std::get<0>(LeafPair); 301356843Sdim GIMatchTreeLeafInfo &TreeLeaf = std::get<1>(LeafPair); 302356843Sdim if (!BuilderLeaf.isFullyTested()) 303356843Sdim for (unsigned PredicateIdx : BuilderLeaf.untested_predicates()) 304356843Sdim TreeLeaf.addUntestedPredicate(BuilderLeaf.getPredicate(PredicateIdx)); 305356843Sdim } 306356843Sdim return; 307356843Sdim } 308356843Sdim 309356843Sdim LLVM_DEBUG(dbgs() << " Weighing up partitioners:\n"); 310356843Sdim evaluatePartitioners(); 311356843Sdim 312356843Sdim // Select the best partitioner by its ability to partition 313356843Sdim // - Prefer partitioners that don't distinguish between partitions. This 314356843Sdim // is to fail early on decisions that must go a single way. 315356843Sdim auto PartitionerI = std::max_element( 316356843Sdim Partitioners.begin(), Partitioners.end(), 317356843Sdim [](const std::unique_ptr<GIMatchTreePartitioner> &A, 318356843Sdim const std::unique_ptr<GIMatchTreePartitioner> &B) { 319356843Sdim // We generally want partitioners that subdivide the 320356843Sdim // ruleset as much as possible since these take fewer 321356843Sdim // checks to converge on a particular rule. However, 322356843Sdim // it's important to note that one leaf can end up in 323356843Sdim // multiple partitions if the check isn't mutually 324356843Sdim // exclusive (e.g. getVRegDef() vs isReg()). 325356843Sdim // We therefore minimize average leaves per partition. 326356843Sdim return (double)A->getNumLeavesWithDupes() / A->getNumPartitions() > 327356843Sdim (double)B->getNumLeavesWithDupes() / B->getNumPartitions(); 328356843Sdim }); 329356843Sdim 330356843Sdim // Select a partitioner and partition the ruleset 331356843Sdim // Note that it's possible for a single rule to end up in multiple 332356843Sdim // partitions. For example, an opcode test on a rule without an opcode 333356843Sdim // predicate will result in it being passed to all partitions. 334356843Sdim std::unique_ptr<GIMatchTreePartitioner> Partitioner = std::move(*PartitionerI); 335356843Sdim Partitioners.erase(PartitionerI); 336356843Sdim LLVM_DEBUG(dbgs() << " Selected partitioner: "; 337356843Sdim Partitioner->emitDescription(dbgs()); dbgs() << "\n"); 338356843Sdim 339356843Sdim assert(Partitioner->getNumPartitions() > 0 && 340356843Sdim "Must always partition into at least one partition"); 341356843Sdim 342356843Sdim TreeNode->setNumChildren(Partitioner->getNumPartitions()); 343356843Sdim for (auto &C : enumerate(TreeNode->children())) { 344356843Sdim SubtreeBuilders.emplace_back(&C.value(), NextInstrID); 345356843Sdim Partitioner->applyForPartition(C.index(), *this, SubtreeBuilders.back()); 346356843Sdim } 347356843Sdim 348356843Sdim TreeNode->setPartitioner(std::move(Partitioner)); 349356843Sdim 350356843Sdim // Recurse into the subtree builders. Each one must get a copy of the 351356843Sdim // remaining partitioners as each path has to check everything. 352356843Sdim for (auto &SubtreeBuilder : SubtreeBuilders) { 353356843Sdim for (const auto &Partitioner : Partitioners) 354356843Sdim SubtreeBuilder.addPartitioner(Partitioner->clone()); 355356843Sdim SubtreeBuilder.runStep(); 356356843Sdim } 357356843Sdim} 358356843Sdim 359356843Sdimstd::unique_ptr<GIMatchTree> GIMatchTreeBuilder::run() { 360356843Sdim unsigned NewInstrID = allocInstrID(); 361356843Sdim // Start by recording the root instruction as instr #0 and set up the initial 362356843Sdim // partitioners. 363356843Sdim for (auto &Leaf : Leaves) { 364356843Sdim LLVM_DEBUG(Leaf.getMatchDag().writeDOTGraph(dbgs(), Leaf.getName())); 365356843Sdim GIMatchDagInstr *Root = 366356843Sdim *(Leaf.getMatchDag().roots().begin() + Leaf.getRootIdx()); 367356843Sdim Leaf.declareInstr(Root, NewInstrID); 368356843Sdim } 369356843Sdim 370356843Sdim addPartitionersForInstr(NewInstrID); 371356843Sdim 372356843Sdim std::unique_ptr<GIMatchTree> TreeRoot = std::make_unique<GIMatchTree>(); 373356843Sdim TreeNode = TreeRoot.get(); 374356843Sdim runStep(); 375356843Sdim 376356843Sdim return TreeRoot; 377356843Sdim} 378356843Sdim 379356843Sdimvoid GIMatchTreeOpcodePartitioner::emitPartitionName(raw_ostream &OS, unsigned Idx) const { 380356843Sdim if (PartitionToInstr[Idx] == nullptr) { 381356843Sdim OS << "* or nullptr"; 382356843Sdim return; 383356843Sdim } 384356843Sdim OS << PartitionToInstr[Idx]->Namespace 385356843Sdim << "::" << PartitionToInstr[Idx]->TheDef->getName(); 386356843Sdim} 387356843Sdim 388356843Sdimvoid GIMatchTreeOpcodePartitioner::repartition( 389356843Sdim GIMatchTreeBuilder::LeafVec &Leaves) { 390356843Sdim Partitions.clear(); 391356843Sdim InstrToPartition.clear(); 392356843Sdim PartitionToInstr.clear(); 393356843Sdim TestedPredicates.clear(); 394356843Sdim 395356843Sdim for (const auto &Leaf : enumerate(Leaves)) { 396356843Sdim bool AllOpcodes = true; 397356843Sdim GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); 398356843Sdim BitVector TestedPredicatesForLeaf( 399356843Sdim Leaf.value().getMatchDag().getNumPredicates()); 400356843Sdim 401356843Sdim // If the instruction isn't declared then we don't care about it. Ignore 402356843Sdim // it for now and add it to all partitions later once we know what 403356843Sdim // partitions we have. 404356843Sdim if (!InstrInfo) { 405356843Sdim LLVM_DEBUG(dbgs() << " " << Leaf.value().getName() 406356843Sdim << " doesn't care about Instr[" << InstrID << "]\n"); 407356843Sdim assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates()); 408356843Sdim TestedPredicates.push_back(TestedPredicatesForLeaf); 409356843Sdim continue; 410356843Sdim } 411356843Sdim 412356843Sdim // If the opcode is available to test then any opcode predicates will have 413356843Sdim // been enabled too. 414356843Sdim for (unsigned PIdx : Leaf.value().TestablePredicates.set_bits()) { 415356843Sdim const auto &P = Leaf.value().getPredicate(PIdx); 416356843Sdim SmallVector<const CodeGenInstruction *, 1> OpcodesForThisPredicate; 417356843Sdim if (const auto *OpcodeP = dyn_cast<const GIMatchDagOpcodePredicate>(P)) { 418356843Sdim // We've found _an_ opcode predicate, but we don't know if it's 419356843Sdim // checking this instruction yet. 420356843Sdim bool IsThisPredicate = false; 421356843Sdim for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) { 422356843Sdim if (PDep->getRequiredMI() == InstrInfo->getInstrNode() && 423356843Sdim PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) { 424356843Sdim IsThisPredicate = true; 425356843Sdim break; 426356843Sdim } 427356843Sdim } 428356843Sdim if (!IsThisPredicate) 429356843Sdim continue; 430356843Sdim 431356843Sdim // If we get here twice then we've somehow ended up with two opcode 432356843Sdim // predicates for one instruction in the same DAG. That should be 433356843Sdim // impossible. 434356843Sdim assert(AllOpcodes && "Conflicting opcode predicates"); 435356843Sdim const CodeGenInstruction *Expected = OpcodeP->getInstr(); 436356843Sdim OpcodesForThisPredicate.push_back(Expected); 437356843Sdim } 438356843Sdim 439356843Sdim if (const auto *OpcodeP = 440356843Sdim dyn_cast<const GIMatchDagOneOfOpcodesPredicate>(P)) { 441356843Sdim // We've found _an_ oneof(opcodes) predicate, but we don't know if it's 442356843Sdim // checking this instruction yet. 443356843Sdim bool IsThisPredicate = false; 444356843Sdim for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) { 445356843Sdim if (PDep->getRequiredMI() == InstrInfo->getInstrNode() && 446356843Sdim PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) { 447356843Sdim IsThisPredicate = true; 448356843Sdim break; 449356843Sdim } 450356843Sdim } 451356843Sdim if (!IsThisPredicate) 452356843Sdim continue; 453356843Sdim 454356843Sdim // If we get here twice then we've somehow ended up with two opcode 455356843Sdim // predicates for one instruction in the same DAG. That should be 456356843Sdim // impossible. 457356843Sdim assert(AllOpcodes && "Conflicting opcode predicates"); 458356843Sdim for (const CodeGenInstruction *Expected : OpcodeP->getInstrs()) 459356843Sdim OpcodesForThisPredicate.push_back(Expected); 460356843Sdim } 461356843Sdim 462356843Sdim for (const CodeGenInstruction *Expected : OpcodesForThisPredicate) { 463356843Sdim // Mark this predicate as one we're testing. 464356843Sdim TestedPredicatesForLeaf.set(PIdx); 465356843Sdim 466356843Sdim // Partitions must be numbered 0, 1, .., N but instructions don't meet 467356843Sdim // that requirement. Assign a partition number to each opcode if we 468356843Sdim // lack one ... 469356843Sdim auto Partition = InstrToPartition.find(Expected); 470356843Sdim if (Partition == InstrToPartition.end()) { 471356843Sdim BitVector Contents(Leaves.size()); 472356843Sdim Partition = InstrToPartition 473356843Sdim .insert(std::make_pair(Expected, Partitions.size())) 474356843Sdim .first; 475356843Sdim PartitionToInstr.push_back(Expected); 476356843Sdim Partitions.insert(std::make_pair(Partitions.size(), Contents)); 477356843Sdim } 478356843Sdim // ... and mark this leaf as being in that partition. 479356843Sdim Partitions.find(Partition->second)->second.set(Leaf.index()); 480356843Sdim AllOpcodes = false; 481356843Sdim LLVM_DEBUG(dbgs() << " " << Leaf.value().getName() 482356843Sdim << " is in partition " << Partition->second << "\n"); 483356843Sdim } 484356843Sdim 485356843Sdim // TODO: This is where we would handle multiple choices of opcode 486356843Sdim // the end result will be that this leaf ends up in multiple 487356843Sdim // partitions similarly to AllOpcodes. 488356843Sdim } 489356843Sdim 490356843Sdim // If we never check the opcode, add it to every partition. 491356843Sdim if (AllOpcodes) { 492356843Sdim // Add a partition for the default case if we don't already have one. 493356843Sdim if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) { 494356843Sdim PartitionToInstr.push_back(nullptr); 495356843Sdim BitVector Contents(Leaves.size()); 496356843Sdim Partitions.insert(std::make_pair(Partitions.size(), Contents)); 497356843Sdim } 498356843Sdim LLVM_DEBUG(dbgs() << " " << Leaf.value().getName() 499356843Sdim << " is in all partitions (opcode not checked)\n"); 500356843Sdim for (auto &Partition : Partitions) 501356843Sdim Partition.second.set(Leaf.index()); 502356843Sdim } 503356843Sdim 504356843Sdim assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates()); 505356843Sdim TestedPredicates.push_back(TestedPredicatesForLeaf); 506356843Sdim } 507356843Sdim 508356843Sdim if (Partitions.size() == 0) { 509356843Sdim // Add a partition for the default case if we don't already have one. 510356843Sdim if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) { 511356843Sdim PartitionToInstr.push_back(nullptr); 512356843Sdim BitVector Contents(Leaves.size()); 513356843Sdim Partitions.insert(std::make_pair(Partitions.size(), Contents)); 514356843Sdim } 515356843Sdim } 516356843Sdim 517356843Sdim // Add any leaves that don't care about this instruction to all partitions. 518356843Sdim for (const auto &Leaf : enumerate(Leaves)) { 519356843Sdim GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); 520356843Sdim if (!InstrInfo) { 521356843Sdim // Add a partition for the default case if we don't already have one. 522356843Sdim if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) { 523356843Sdim PartitionToInstr.push_back(nullptr); 524356843Sdim BitVector Contents(Leaves.size()); 525356843Sdim Partitions.insert(std::make_pair(Partitions.size(), Contents)); 526356843Sdim } 527356843Sdim for (auto &Partition : Partitions) 528356843Sdim Partition.second.set(Leaf.index()); 529356843Sdim } 530356843Sdim } 531356843Sdim 532356843Sdim} 533356843Sdim 534356843Sdimvoid GIMatchTreeOpcodePartitioner::applyForPartition( 535356843Sdim unsigned PartitionIdx, GIMatchTreeBuilder &Builder, GIMatchTreeBuilder &SubBuilder) { 536356843Sdim LLVM_DEBUG(dbgs() << " Making partition " << PartitionIdx << "\n"); 537356843Sdim const CodeGenInstruction *CGI = PartitionToInstr[PartitionIdx]; 538356843Sdim 539356843Sdim BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx); 540356843Sdim // Consume any predicates we handled. 541356843Sdim for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) { 542356843Sdim if (!PossibleLeaves[EnumeratedLeaf.index()]) 543356843Sdim continue; 544356843Sdim 545356843Sdim auto &Leaf = EnumeratedLeaf.value(); 546356843Sdim const auto &TestedPredicatesForLeaf = 547356843Sdim TestedPredicates[EnumeratedLeaf.index()]; 548356843Sdim 549356843Sdim for (unsigned PredIdx : TestedPredicatesForLeaf.set_bits()) { 550356843Sdim LLVM_DEBUG(dbgs() << " " << Leaf.getName() << " tested predicate #" 551356843Sdim << PredIdx << " of " << TestedPredicatesForLeaf.size() 552356843Sdim << " " << *Leaf.getPredicate(PredIdx) << "\n"); 553356843Sdim Leaf.RemainingPredicates.reset(PredIdx); 554356843Sdim Leaf.TestablePredicates.reset(PredIdx); 555356843Sdim } 556356843Sdim SubBuilder.addLeaf(Leaf); 557356843Sdim } 558356843Sdim 559356843Sdim // Nothing to do, we don't know anything about this instruction as a result 560356843Sdim // of this partitioner. 561356843Sdim if (CGI == nullptr) 562356843Sdim return; 563356843Sdim 564356843Sdim GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves(); 565356843Sdim // Find all the operands we know to exist and are referenced. This will 566356843Sdim // usually be all the referenced operands but there are some cases where 567356843Sdim // instructions are variadic. Such operands must be handled by partitioners 568356843Sdim // that check the number of operands. 569356843Sdim BitVector ReferencedOperands(1); 570356843Sdim for (auto &Leaf : NewLeaves) { 571356843Sdim GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID); 572356843Sdim // Skip any leaves that don't care about this instruction. 573356843Sdim if (!InstrInfo) 574356843Sdim continue; 575356843Sdim const GIMatchDagInstr *Instr = InstrInfo->getInstrNode(); 576356843Sdim for (auto &E : enumerate(Leaf.getMatchDag().edges())) { 577356843Sdim if (E.value()->getFromMI() == Instr && 578356843Sdim E.value()->getFromMO()->getIdx() < CGI->Operands.size()) { 579356843Sdim ReferencedOperands.resize(E.value()->getFromMO()->getIdx() + 1); 580356843Sdim ReferencedOperands.set(E.value()->getFromMO()->getIdx()); 581356843Sdim } 582356843Sdim } 583356843Sdim } 584356843Sdim for (auto &Leaf : NewLeaves) { 585356843Sdim for (unsigned OpIdx : ReferencedOperands.set_bits()) { 586356843Sdim Leaf.declareOperand(InstrID, OpIdx); 587356843Sdim } 588356843Sdim } 589356843Sdim for (unsigned OpIdx : ReferencedOperands.set_bits()) { 590356843Sdim SubBuilder.addPartitionersForOperand(InstrID, OpIdx); 591356843Sdim } 592356843Sdim} 593356843Sdim 594356843Sdimvoid GIMatchTreeOpcodePartitioner::emitPartitionResults( 595356843Sdim raw_ostream &OS) const { 596356843Sdim OS << "Partitioning by opcode would produce " << Partitions.size() 597356843Sdim << " partitions\n"; 598356843Sdim for (const auto &Partition : InstrToPartition) { 599356843Sdim if (Partition.first == nullptr) 600356843Sdim OS << "Default: "; 601356843Sdim else 602356843Sdim OS << Partition.first->TheDef->getName() << ": "; 603356843Sdim StringRef Separator = ""; 604356843Sdim for (unsigned I : Partitions.find(Partition.second)->second.set_bits()) { 605356843Sdim OS << Separator << I; 606356843Sdim Separator = ", "; 607356843Sdim } 608356843Sdim OS << "\n"; 609356843Sdim } 610356843Sdim} 611356843Sdim 612356843Sdimvoid GIMatchTreeOpcodePartitioner::generatePartitionSelectorCode( 613356843Sdim raw_ostream &OS, StringRef Indent) const { 614356843Sdim OS << Indent << "Partition = -1;\n" 615356843Sdim << Indent << "switch (MIs[" << InstrID << "]->getOpcode()) {\n"; 616356843Sdim for (const auto &EnumInstr : enumerate(PartitionToInstr)) { 617356843Sdim if (EnumInstr.value() == nullptr) 618356843Sdim OS << Indent << "default:"; 619356843Sdim else 620356843Sdim OS << Indent << "case " << EnumInstr.value()->Namespace 621356843Sdim << "::" << EnumInstr.value()->TheDef->getName() << ":"; 622356843Sdim OS << " Partition = " << EnumInstr.index() << "; break;\n"; 623356843Sdim } 624356843Sdim OS << Indent << "}\n" 625356843Sdim << Indent 626356843Sdim << "// Default case but without conflicting with potential default case " 627356843Sdim "in selection.\n" 628356843Sdim << Indent << "if (Partition == -1) return false;\n"; 629356843Sdim} 630356843Sdim 631356843Sdimvoid GIMatchTreeVRegDefPartitioner::addToPartition(bool Result, 632356843Sdim unsigned LeafIdx) { 633356843Sdim auto I = ResultToPartition.find(Result); 634356843Sdim if (I == ResultToPartition.end()) { 635356843Sdim ResultToPartition.insert(std::make_pair(Result, PartitionToResult.size())); 636356843Sdim PartitionToResult.push_back(Result); 637356843Sdim } 638356843Sdim I = ResultToPartition.find(Result); 639356843Sdim auto P = Partitions.find(I->second); 640356843Sdim if (P == Partitions.end()) 641356843Sdim P = Partitions.insert(std::make_pair(I->second, BitVector())).first; 642356843Sdim P->second.resize(LeafIdx + 1); 643356843Sdim P->second.set(LeafIdx); 644356843Sdim} 645356843Sdim 646356843Sdimvoid GIMatchTreeVRegDefPartitioner::repartition( 647356843Sdim GIMatchTreeBuilder::LeafVec &Leaves) { 648356843Sdim Partitions.clear(); 649356843Sdim 650356843Sdim for (const auto &Leaf : enumerate(Leaves)) { 651356843Sdim GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); 652356843Sdim BitVector TraversedEdgesForLeaf(Leaf.value().getMatchDag().getNumEdges()); 653356843Sdim 654356843Sdim // If the instruction isn't declared then we don't care about it. Ignore 655356843Sdim // it for now and add it to all partitions later once we know what 656356843Sdim // partitions we have. 657356843Sdim if (!InstrInfo) { 658356843Sdim TraversedEdges.push_back(TraversedEdgesForLeaf); 659356843Sdim continue; 660356843Sdim } 661356843Sdim 662356843Sdim // If this node has an use -> def edge from this operand then this 663356843Sdim // instruction must be in partition 1 (isVRegDef()). 664356843Sdim bool WantsEdge = false; 665356843Sdim for (unsigned EIdx : Leaf.value().TraversableEdges.set_bits()) { 666356843Sdim const auto &E = Leaf.value().getEdge(EIdx); 667356843Sdim if (E->getFromMI() != InstrInfo->getInstrNode() || 668356843Sdim E->getFromMO()->getIdx() != OpIdx || E->isDefToUse()) 669356843Sdim continue; 670356843Sdim 671356843Sdim // We're looking at the right edge. This leaf wants a vreg def so we'll 672356843Sdim // put it in partition 1. 673356843Sdim addToPartition(true, Leaf.index()); 674356843Sdim TraversedEdgesForLeaf.set(EIdx); 675356843Sdim WantsEdge = true; 676356843Sdim } 677356843Sdim 678356843Sdim bool isNotReg = false; 679356843Sdim if (!WantsEdge && isNotReg) { 680356843Sdim // If this leaf doesn't have an edge and we _don't_ want a register, 681356843Sdim // then add it to partition 0. 682356843Sdim addToPartition(false, Leaf.index()); 683356843Sdim } else if (!WantsEdge) { 684356843Sdim // If this leaf doesn't have an edge and we don't know what we want, 685356843Sdim // then add it to partition 0 and 1. 686356843Sdim addToPartition(false, Leaf.index()); 687356843Sdim addToPartition(true, Leaf.index()); 688356843Sdim } 689356843Sdim 690356843Sdim TraversedEdges.push_back(TraversedEdgesForLeaf); 691356843Sdim } 692356843Sdim 693356843Sdim // Add any leaves that don't care about this instruction to all partitions. 694356843Sdim for (const auto &Leaf : enumerate(Leaves)) { 695356843Sdim GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID); 696356843Sdim if (!InstrInfo) 697356843Sdim for (auto &Partition : Partitions) 698356843Sdim Partition.second.set(Leaf.index()); 699356843Sdim } 700356843Sdim} 701356843Sdim 702356843Sdimvoid GIMatchTreeVRegDefPartitioner::applyForPartition( 703356843Sdim unsigned PartitionIdx, GIMatchTreeBuilder &Builder, 704356843Sdim GIMatchTreeBuilder &SubBuilder) { 705356843Sdim BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx); 706356843Sdim 707356843Sdim std::vector<BitVector> TraversedEdgesByNewLeaves; 708356843Sdim // Consume any edges we handled. 709356843Sdim for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) { 710356843Sdim if (!PossibleLeaves[EnumeratedLeaf.index()]) 711356843Sdim continue; 712356843Sdim 713356843Sdim auto &Leaf = EnumeratedLeaf.value(); 714356843Sdim const auto &TraversedEdgesForLeaf = TraversedEdges[EnumeratedLeaf.index()]; 715356843Sdim TraversedEdgesByNewLeaves.push_back(TraversedEdgesForLeaf); 716356843Sdim Leaf.RemainingEdges.reset(TraversedEdgesForLeaf); 717356843Sdim Leaf.TraversableEdges.reset(TraversedEdgesForLeaf); 718356843Sdim SubBuilder.addLeaf(Leaf); 719356843Sdim } 720356843Sdim 721356843Sdim // Nothing to do. The only thing we know is that it isn't a vreg-def. 722356843Sdim if (PartitionToResult[PartitionIdx] == false) 723356843Sdim return; 724356843Sdim 725356843Sdim NewInstrID = SubBuilder.allocInstrID(); 726356843Sdim 727356843Sdim GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves(); 728356843Sdim for (const auto I : zip(NewLeaves, TraversedEdgesByNewLeaves)) { 729356843Sdim auto &Leaf = std::get<0>(I); 730356843Sdim auto &TraversedEdgesForLeaf = std::get<1>(I); 731356843Sdim GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID); 732356843Sdim // Skip any leaves that don't care about this instruction. 733356843Sdim if (!InstrInfo) 734356843Sdim continue; 735356843Sdim for (unsigned EIdx : TraversedEdgesForLeaf.set_bits()) { 736356843Sdim const GIMatchDagEdge *E = Leaf.getEdge(EIdx); 737356843Sdim Leaf.declareInstr(E->getToMI(), NewInstrID); 738356843Sdim } 739356843Sdim } 740356843Sdim SubBuilder.addPartitionersForInstr(NewInstrID); 741356843Sdim} 742356843Sdim 743356843Sdimvoid GIMatchTreeVRegDefPartitioner::emitPartitionResults( 744356843Sdim raw_ostream &OS) const { 745356843Sdim OS << "Partitioning by vreg-def would produce " << Partitions.size() 746356843Sdim << " partitions\n"; 747356843Sdim for (const auto &Partition : Partitions) { 748356843Sdim OS << Partition.first << " ("; 749356843Sdim emitPartitionName(OS, Partition.first); 750356843Sdim OS << "): "; 751356843Sdim StringRef Separator = ""; 752356843Sdim for (unsigned I : Partition.second.set_bits()) { 753356843Sdim OS << Separator << I; 754356843Sdim Separator = ", "; 755356843Sdim } 756356843Sdim OS << "\n"; 757356843Sdim } 758356843Sdim} 759356843Sdim 760356843Sdimvoid GIMatchTreeVRegDefPartitioner::generatePartitionSelectorCode( 761356843Sdim raw_ostream &OS, StringRef Indent) const { 762356843Sdim OS << Indent << "Partition = -1\n" 763356843Sdim << Indent << "if (MIs.size() <= NewInstrID) MIs.resize(NewInstrID + 1);\n" 764356843Sdim << Indent << "MIs[" << NewInstrID << "] = nullptr;\n" 765356843Sdim << Indent << "if (MIs[" << InstrID << "].getOperand(" << OpIdx 766356843Sdim << ").isReg()))\n" 767356843Sdim << Indent << " MIs[" << NewInstrID << "] = MRI.getVRegDef(MIs[" << InstrID 768356843Sdim << "].getOperand(" << OpIdx << ").getReg()));\n"; 769356843Sdim 770356843Sdim for (const auto &Pair : ResultToPartition) 771356843Sdim OS << Indent << "if (MIs[" << NewInstrID << "] " 772356843Sdim << (Pair.first ? "==" : "!=") 773356843Sdim << " nullptr) Partition = " << Pair.second << ";\n"; 774356843Sdim 775356843Sdim OS << Indent << "if (Partition == -1) return false;\n"; 776356843Sdim} 777356843Sdim 778