contrib/llvm-project/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp

   1 //===- GIMatchTree.cpp - A decision tree to match GIMatchDag's ------------===//
   2 //
   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
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "GIMatchTree.h"
  10
  11 #include "../CodeGenInstruction.h"
  12
  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"
  18
  19 #define DEBUG_TYPE "gimatchtree"
  20
  21 using namespace llvm;
  22
  23 void GIMatchTree::writeDOTGraph(raw_ostream &OS) const {
  24   OS << "digraph \"matchtree\" {\n";
  25   writeDOTGraphNode(OS);
  26   OS << "}\n";
  27 }
  28
  29 void GIMatchTree::writeDOTGraphNode(raw_ostream &OS) const {
  30   OS << format("  Node%p", this) << " [shape=record,label=\"{";
  31   if (Partitioner) {
  32     Partitioner->emitDescription(OS);
  33     OS << "|" << Partitioner->getNumPartitions() << " partitions|";
  34   } else
  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();
  41     Separator = ",";
  42     if (!Leaf.isFullyTraversed())
  43       IsFullyTraversed = false;
  44     if (!Leaf.isFullyTested())
  45       IsFullyTested = false;
  46   }
  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())
  54           continue;
  55         OS << "\\n" << Leaf.getName() << ": " << &Leaf;
  56         for (const GIMatchDagPredicate *P : Leaf.untested_predicates())
  57           OS << *P;
  58       }
  59     }
  60   }
  61   OS << "}\"";
  62   if (!Partitioner &&
  63       (!IsFullyTraversed || !IsFullyTested || PossibleLeaves.size() > 1))
  64     OS << ",color=red";
  65   OS << "]\n";
  66   for (const auto &C : Children)
  67     C.writeDOTGraphNode(OS);
  68   writeDOTGraphEdges(OS);
  69 }
  70
  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());
  76     OS << "\"]\n";
  77   }
  78 }
  79
  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),
  84       InstrNodeToInfo(),
  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()));
  93   }
  94
  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()));
  99   }
 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());
 105   }
 106 }
 107
 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));
 113
 114   if (Instr == nullptr)
 115     return;
 116
 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);
 121
 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);
 128
 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
 131   // are traversable.
 132
 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
 136   // satisfied.
 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());
 144       }
 145     }
 146   }
 147 }
 148
 149 void GIMatchTreeBuilderLeafInfo::declareOperand(unsigned InstrID,
 150                                                 unsigned OpIdx) {
 151   const GIMatchDagInstr *Instr = InstrIDToInfo.lookup(InstrID)->getInstrNode();
 152
 153   OperandIDToInfo.insert(std::make_pair(
 154       std::make_pair(InstrID, OpIdx),
 155       GIMatchTreeOperandInfo(Instr, OpIdx)));
 156
 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
 159   // instruction.
 160   for (auto &E : enumerate(MatchDag.edges())) {
 161     if (E.value()->getFromMI() == Instr &&
 162         E.value()->getFromMO()->getIdx() == OpIdx) {
 163       TraversableEdges.set(E.index());
 164     }
 165   }
 166
 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
 170   // satisfied.
 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());
 178       }
 179     }
 180   }
 181 }
 182
 183 void GIMatchTreeBuilder::addPartitionersForInstr(unsigned InstrIdx) {
 184   // Find the partitioners that can be used now that this node is
 185   // uncovered. Our choices are:
 186   // - Test the opcode
 187   addPartitioner(std::make_unique<GIMatchTreeOpcodePartitioner>(InstrIdx));
 188 }
 189
 190 void GIMatchTreeBuilder::addPartitionersForOperand(unsigned InstrID,
 191                                                    unsigned OpIdx) {
 192   LLVM_DEBUG(dbgs() << "Add partitioners for Instrs[" << InstrID
 193                     << "].getOperand(" << OpIdx << ")\n");
 194   addPartitioner(
 195       std::make_unique<GIMatchTreeVRegDefPartitioner>(InstrID, OpIdx));
 196 }
 197
 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.
 206 }
 207
 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()));
 215   }
 216 }
 217
 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());
 225   }
 226
 227   LLVM_DEBUG(dbgs() << "  Partitioners available at this node:\n");
 228 #ifndef NDEBUG
 229   for (const auto &Partitioner : Partitioners)
 230     LLVM_DEBUG(dbgs() << "    "; Partitioner->emitDescription(dbgs());
 231                dbgs() << "\n");
 232 #endif // ifndef NDEBUG
 233
 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
 238   //       reachable.
 239   {
 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");
 249       }
 250     }
 251   }
 252
 253   LLVM_DEBUG(dbgs() << "  Eliminating redundant partitioners:\n");
 254   filterRedundantPartitioners();
 255   LLVM_DEBUG(dbgs() << "  Partitioners remaining:\n");
 256 #ifndef NDEBUG
 257   for (const auto &Partitioner : Partitioners)
 258     LLVM_DEBUG(dbgs() << "    "; Partitioner->emitDescription(dbgs());
 259                dbgs() << "\n");
 260 #endif // ifndef NDEBUG
 261
 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();
 272                        });
 273       if (FirstFullyTested != Leaves.end())
 274         FirstFullyTested++;
 275
 276 #ifndef NDEBUG
 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));
 284     }
 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");
 289         Leaf.dump(errs());
 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)));
 294       }
 295     }
 296
 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));
 305     }
 306     return;
 307   }
 308
 309   LLVM_DEBUG(dbgs() << "  Weighing up partitioners:\n");
 310   evaluatePartitioners();
 311
 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();
 328       });
 329
 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");
 338
 339   assert(Partitioner->getNumPartitions() > 0 &&
 340          "Must always partition into at least one partition");
 341
 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());
 346   }
 347
 348   TreeNode->setPartitioner(std::move(Partitioner));
 349
 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();
 356   }
 357 }
 358
 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
 362   // partitioners.
 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);
 368   }
 369
 370   addPartitionersForInstr(NewInstrID);
 371
 372   std::unique_ptr<GIMatchTree> TreeRoot = std::make_unique<GIMatchTree>();
 373   TreeNode = TreeRoot.get();
 374   runStep();
 375
 376   return TreeRoot;
 377 }
 378
 379 void GIMatchTreeOpcodePartitioner::emitPartitionName(raw_ostream &OS, unsigned Idx) const {
 380   if (PartitionToInstr[Idx] == nullptr) {
 381     OS << "* or nullptr";
 382     return;
 383   }
 384   OS << PartitionToInstr[Idx]->Namespace
 385      << "::" << PartitionToInstr[Idx]->TheDef->getName();
 386 }
 387
 388 void GIMatchTreeOpcodePartitioner::repartition(
 389     GIMatchTreeBuilder::LeafVec &Leaves) {
 390   Partitions.clear();
 391   InstrToPartition.clear();
 392   PartitionToInstr.clear();
 393   TestedPredicates.clear();
 394
 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());
 400
 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.
 404     if (!InstrInfo) {
 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);
 409       continue;
 410     }
 411
 412     // If the opcode is available to test then any opcode predicates will have
 413     // been enabled too.
 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;
 425             break;
 426           }
 427         }
 428         if (!IsThisPredicate)
 429           continue;
 430
 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
 433         // impossible.
 434         assert(AllOpcodes && "Conflicting opcode predicates");
 435         const CodeGenInstruction *Expected = OpcodeP->getInstr();
 436         OpcodesForThisPredicate.push_back(Expected);
 437       }
 438
 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;
 448             break;
 449           }
 450         }
 451         if (!IsThisPredicate)
 452           continue;
 453
 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
 456         // impossible.
 457         assert(AllOpcodes && "Conflicting opcode predicates");
 458         for (const CodeGenInstruction *Expected : OpcodeP->getInstrs())
 459           OpcodesForThisPredicate.push_back(Expected);
 460       }
 461
 462       for (const CodeGenInstruction *Expected : OpcodesForThisPredicate) {
 463         // Mark this predicate as one we're testing.
 464         TestedPredicatesForLeaf.set(PIdx);
 465
 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
 468         // lack one ...
 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()))
 474                           .first;
 475           PartitionToInstr.push_back(Expected);
 476           Partitions.insert(std::make_pair(Partitions.size(), Contents));
 477         }
 478         // ... and mark this leaf as being in that partition.
 479         Partitions.find(Partition->second)->second.set(Leaf.index());
 480         AllOpcodes = false;
 481         LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
 482                           << " is in partition " << Partition->second << "\n");
 483       }
 484
 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.
 488     }
 489
 490     // If we never check the opcode, add it to every partition.
 491     if (AllOpcodes) {
 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));
 497       }
 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());
 502     }
 503
 504     assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates());
 505     TestedPredicates.push_back(TestedPredicatesForLeaf);
 506   }
 507
 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));
 514     }
 515   }
 516
 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);
 520     if (!InstrInfo) {
 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));
 526       }
 527       for (auto &Partition : Partitions)
 528         Partition.second.set(Leaf.index());
 529     }
 530   }
 531
 532 }
 533
 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];
 538
 539   BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
 540   // Consume any predicates we handled.
 541   for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
 542     if (!PossibleLeaves[EnumeratedLeaf.index()])
 543       continue;
 544
 545     auto &Leaf = EnumeratedLeaf.value();
 546     const auto &TestedPredicatesForLeaf =
 547         TestedPredicates[EnumeratedLeaf.index()];
 548
 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);
 555     }
 556     SubBuilder.addLeaf(Leaf);
 557   }
 558
 559   // Nothing to do, we don't know anything about this instruction as a result
 560   // of this partitioner.
 561   if (CGI == nullptr)
 562     return;
 563
 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.
 573     if (!InstrInfo)
 574       continue;
 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());
 581       }
 582     }
 583   }
 584   for (auto &Leaf : NewLeaves) {
 585     for (unsigned OpIdx : ReferencedOperands.set_bits()) {
 586       Leaf.declareOperand(InstrID, OpIdx);
 587     }
 588   }
 589   for (unsigned OpIdx : ReferencedOperands.set_bits()) {
 590     SubBuilder.addPartitionersForOperand(InstrID, OpIdx);
 591   }
 592 }
 593
 594 void GIMatchTreeOpcodePartitioner::emitPartitionResults(
 595     raw_ostream &OS) const {
 596   OS << "Partitioning by opcode would produce " << Partitions.size()
 597      << " partitions\n";
 598   for (const auto &Partition : InstrToPartition) {
 599     if (Partition.first == nullptr)
 600       OS << "Default: ";
 601     else
 602       OS << Partition.first->TheDef->getName() << ": ";
 603     StringRef Separator = "";
 604     for (unsigned I : Partitions.find(Partition.second)->second.set_bits()) {
 605       OS << Separator << I;
 606       Separator = ", ";
 607     }
 608     OS << "\n";
 609   }
 610 }
 611
 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:";
 619     else
 620       OS << Indent << "case " << EnumInstr.value()->Namespace
 621          << "::" << EnumInstr.value()->TheDef->getName() << ":";
 622     OS << " Partition = " << EnumInstr.index() << "; break;\n";
 623   }
 624   OS << Indent << "}\n"
 625      << Indent
 626      << "// Default case but without conflicting with potential default case "
 627         "in selection.\n"
 628      << Indent << "if (Partition == -1) return false;\n";
 629 }
 630
 631 void GIMatchTreeVRegDefPartitioner::addToPartition(bool Result,
 632                                                    unsigned LeafIdx) {
 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);
 637   }
 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);
 644 }
 645
 646 void GIMatchTreeVRegDefPartitioner::repartition(
 647     GIMatchTreeBuilder::LeafVec &Leaves) {
 648   Partitions.clear();
 649
 650   for (const auto &Leaf : enumerate(Leaves)) {
 651     GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
 652     BitVector TraversedEdgesForLeaf(Leaf.value().getMatchDag().getNumEdges());
 653
 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.
 657     if (!InstrInfo) {
 658       TraversedEdges.push_back(TraversedEdgesForLeaf);
 659       continue;
 660     }
 661
 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())
 669         continue;
 670
 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);
 675       WantsEdge = true;
 676     }
 677
 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());
 688     }
 689
 690     TraversedEdges.push_back(TraversedEdgesForLeaf);
 691   }
 692
 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);
 696     if (!InstrInfo)
 697       for (auto &Partition : Partitions)
 698         Partition.second.set(Leaf.index());
 699   }
 700 }
 701
 702 void GIMatchTreeVRegDefPartitioner::applyForPartition(
 703     unsigned PartitionIdx, GIMatchTreeBuilder &Builder,
 704     GIMatchTreeBuilder &SubBuilder) {
 705   BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
 706
 707   std::vector<BitVector> TraversedEdgesByNewLeaves;
 708   // Consume any edges we handled.
 709   for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
 710     if (!PossibleLeaves[EnumeratedLeaf.index()])
 711       continue;
 712
 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);
 719   }
 720
 721   // Nothing to do. The only thing we know is that it isn't a vreg-def.
 722   if (PartitionToResult[PartitionIdx] == false)
 723     return;
 724
 725   NewInstrID = SubBuilder.allocInstrID();
 726
 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.
 733     if (!InstrInfo)
 734       continue;
 735     for (unsigned EIdx : TraversedEdgesForLeaf.set_bits()) {
 736       const GIMatchDagEdge *E = Leaf.getEdge(EIdx);
 737       Leaf.declareInstr(E->getToMI(), NewInstrID);
 738     }
 739   }
 740   SubBuilder.addPartitionersForInstr(NewInstrID);
 741 }
 742
 743 void GIMatchTreeVRegDefPartitioner::emitPartitionResults(
 744     raw_ostream &OS) const {
 745   OS << "Partitioning by vreg-def would produce " << Partitions.size()
 746      << " partitions\n";
 747   for (const auto &Partition : Partitions) {
 748     OS << Partition.first << " (";
 749     emitPartitionName(OS, Partition.first);
 750     OS << "): ";
 751     StringRef Separator = "";
 752     for (unsigned I : Partition.second.set_bits()) {
 753       OS << Separator << I;
 754       Separator = ", ";
 755     }
 756     OS << "\n";
 757   }
 758 }
 759
 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
 766      << ").isReg()))\n"
 767      << Indent << "  MIs[" << NewInstrID << "] = MRI.getVRegDef(MIs[" << InstrID
 768      << "].getOperand(" << OpIdx << ").getReg()));\n";
 769
 770   for (const auto &Pair : ResultToPartition)
 771     OS << Indent << "if (MIs[" << NewInstrID << "] "
 772        << (Pair.first ? "==" : "!=")
 773        << " nullptr) Partition = " << Pair.second << ";\n";
 774
 775   OS << Indent << "if (Partition == -1) return false;\n";
 776 }
 777