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/Debug.h"
  14 #include "llvm/Support/Format.h"
  15 #include "llvm/Support/ScopedPrinter.h"
  16 #include "llvm/Support/raw_ostream.h"
  17 #include "llvm/TableGen/Error.h"
  18 #include "llvm/TableGen/Record.h"
  19
  20 #define DEBUG_TYPE "gimatchtree"
  21
  22 using namespace llvm;
  23
  24 void GIMatchTree::writeDOTGraph(raw_ostream &OS) const {
  25   OS << "digraph \"matchtree\" {\n";
  26   writeDOTGraphNode(OS);
  27   OS << "}\n";
  28 }
  29
  30 void GIMatchTree::writeDOTGraphNode(raw_ostream &OS) const {
  31   OS << format("  Node%p", this) << " [shape=record,label=\"{";
  32   if (Partitioner) {
  33     Partitioner->emitDescription(OS);
  34     OS << "|" << Partitioner->getNumPartitions() << " partitions|";
  35   } else
  36     OS << "No partitioner|";
  37   bool IsFullyTraversed = true;
  38   bool IsFullyTested = true;
  39   StringRef Separator = "";
  40   for (const auto &Leaf : PossibleLeaves) {
  41     OS << Separator << Leaf.getName();
  42     Separator = ",";
  43     if (!Leaf.isFullyTraversed())
  44       IsFullyTraversed = false;
  45     if (!Leaf.isFullyTested())
  46       IsFullyTested = false;
  47   }
  48   if (!Partitioner && !IsFullyTraversed)
  49     OS << "|Not fully traversed";
  50   if (!Partitioner && !IsFullyTested) {
  51     OS << "|Not fully tested";
  52     if (IsFullyTraversed) {
  53       for (const GIMatchTreeLeafInfo &Leaf : PossibleLeaves) {
  54         if (Leaf.isFullyTested())
  55           continue;
  56         OS << "\\n" << Leaf.getName() << ": " << &Leaf;
  57         for (const GIMatchDagPredicate *P : Leaf.untested_predicates())
  58           OS << *P;
  59       }
  60     }
  61   }
  62   OS << "}\"";
  63   if (!Partitioner &&
  64       (!IsFullyTraversed || !IsFullyTested || PossibleLeaves.size() > 1))
  65     OS << ",color=red";
  66   OS << "]\n";
  67   for (const auto &C : Children)
  68     C.writeDOTGraphNode(OS);
  69   writeDOTGraphEdges(OS);
  70 }
  71
  72 void GIMatchTree::writeDOTGraphEdges(raw_ostream &OS) const {
  73   for (const auto &Child : enumerate(Children)) {
  74     OS << format("  Node%p", this) << " -> " << format("Node%p", &Child.value())
  75        << " [label=\"#" << Child.index() << " ";
  76     Partitioner->emitPartitionName(OS, Child.index());
  77     OS << "\"]\n";
  78   }
  79 }
  80
  81 GIMatchTreeBuilderLeafInfo::GIMatchTreeBuilderLeafInfo(
  82     GIMatchTreeBuilder &Builder, StringRef Name, unsigned RootIdx,
  83     const GIMatchDag &MatchDag, void *Data)
  84     : Builder(Builder), Info(Name, RootIdx, Data), MatchDag(MatchDag),
  85       InstrNodeToInfo(),
  86       RemainingInstrNodes(BitVector(MatchDag.getNumInstrNodes(), true)),
  87       RemainingEdges(BitVector(MatchDag.getNumEdges(), true)),
  88       RemainingPredicates(BitVector(MatchDag.getNumPredicates(), true)),
  89       TraversableEdges(MatchDag.getNumEdges()),
  90       TestablePredicates(MatchDag.getNumPredicates()) {
  91   // Number all the predicates in this DAG
  92   for (auto &P : enumerate(MatchDag.predicates())) {
  93     PredicateIDs.insert(std::make_pair(P.value(), P.index()));
  94   }
  95
  96   // Number all the predicate dependencies in this DAG and set up a bitvector
  97   // for each predicate indicating the unsatisfied dependencies.
  98   for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
  99     PredicateDepIDs.insert(std::make_pair(Dep.value(), Dep.index()));
 100   }
 101   UnsatisfiedPredDepsForPred.resize(MatchDag.getNumPredicates(),
 102                                     BitVector(PredicateDepIDs.size()));
 103   for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
 104     unsigned ID = PredicateIDs.lookup(Dep.value()->getPredicate());
 105     UnsatisfiedPredDepsForPred[ID].set(Dep.index());
 106   }
 107 }
 108
 109 void GIMatchTreeBuilderLeafInfo::declareInstr(const GIMatchDagInstr *Instr, unsigned ID) {
 110   // Record the assignment of this instr to the given ID.
 111   auto InfoI = InstrNodeToInfo.insert(std::make_pair(
 112       Instr, GIMatchTreeInstrInfo(ID, Instr)));
 113   InstrIDToInfo.insert(std::make_pair(ID, &InfoI.first->second));
 114
 115   if (Instr == nullptr)
 116     return;
 117
 118   if (!Instr->getUserAssignedName().empty())
 119     Info.bindInstrVariable(Instr->getUserAssignedName(), ID);
 120   for (const auto &VarBinding : Instr->user_assigned_operand_names())
 121     Info.bindOperandVariable(VarBinding.second, ID, VarBinding.first);
 122
 123   // Clear the bit indicating we haven't visited this instr.
 124   const auto &NodeI = find(MatchDag.instr_nodes(), 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           llvm::find_if(Leaves, [](const GIMatchTreeBuilderLeafInfo &X) {
 269             return X.isFullyTraversed() && X.isFullyTested() &&
 270                    !X.getMatchDag().hasPostMatchPredicate();
 271           });
 272       if (FirstFullyTested != Leaves.end())
 273         FirstFullyTested++;
 274
 275 #ifndef NDEBUG
 276       for (auto &Leaf : make_range(Leaves.begin(), FirstFullyTested))
 277         LLVM_DEBUG(dbgs() << "  Kept " << Leaf.getName() << "\n");
 278       for (const auto &Leaf : make_range(FirstFullyTested, Leaves.end()))
 279         LLVM_DEBUG(dbgs() << "  Dropped " << Leaf.getName() << "\n");
 280 #endif // ifndef NDEBUG
 281       TreeNode->dropLeavesAfter(
 282           std::distance(Leaves.begin(), FirstFullyTested));
 283     }
 284     for (const auto &Leaf : Leaves) {
 285       if (!Leaf.isFullyTraversed()) {
 286         PrintError("Leaf " + Leaf.getName() + " is not fully traversed");
 287         PrintNote("This indicates a missing partitioner within tblgen");
 288         Leaf.dump(errs());
 289         for (unsigned InstrIdx : Leaf.untested_instrs())
 290           PrintNote("Instr " + llvm::to_string(*Leaf.getInstr(InstrIdx)));
 291         for (unsigned EdgeIdx : Leaf.untested_edges())
 292           PrintNote("Edge " + llvm::to_string(*Leaf.getEdge(EdgeIdx)));
 293       }
 294     }
 295
 296     // Copy out information about untested predicates so the user of the tree
 297     // can deal with them.
 298     for (auto LeafPair : zip(Leaves, TreeNode->possible_leaves())) {
 299       const GIMatchTreeBuilderLeafInfo &BuilderLeaf = std::get<0>(LeafPair);
 300       GIMatchTreeLeafInfo &TreeLeaf = std::get<1>(LeafPair);
 301       if (!BuilderLeaf.isFullyTested())
 302         for (unsigned PredicateIdx : BuilderLeaf.untested_predicates())
 303           TreeLeaf.addUntestedPredicate(BuilderLeaf.getPredicate(PredicateIdx));
 304     }
 305     return;
 306   }
 307
 308   LLVM_DEBUG(dbgs() << "  Weighing up partitioners:\n");
 309   evaluatePartitioners();
 310
 311   // Select the best partitioner by its ability to partition
 312   // - Prefer partitioners that don't distinguish between partitions. This
 313   //   is to fail early on decisions that must go a single way.
 314   auto PartitionerI = std::max_element(
 315       Partitioners.begin(), Partitioners.end(),
 316       [](const std::unique_ptr<GIMatchTreePartitioner> &A,
 317          const std::unique_ptr<GIMatchTreePartitioner> &B) {
 318         // We generally want partitioners that subdivide the
 319         // ruleset as much as possible since these take fewer
 320         // checks to converge on a particular rule. However,
 321         // it's important to note that one leaf can end up in
 322         // multiple partitions if the check isn't mutually
 323         // exclusive (e.g. getVRegDef() vs isReg()).
 324         // We therefore minimize average leaves per partition.
 325         return (double)A->getNumLeavesWithDupes() / A->getNumPartitions() >
 326                (double)B->getNumLeavesWithDupes() / B->getNumPartitions();
 327       });
 328
 329   // Select a partitioner and partition the ruleset
 330   // Note that it's possible for a single rule to end up in multiple
 331   // partitions. For example, an opcode test on a rule without an opcode
 332   // predicate will result in it being passed to all partitions.
 333   std::unique_ptr<GIMatchTreePartitioner> Partitioner = std::move(*PartitionerI);
 334   Partitioners.erase(PartitionerI);
 335   LLVM_DEBUG(dbgs() << "  Selected partitioner: ";
 336              Partitioner->emitDescription(dbgs()); dbgs() << "\n");
 337
 338   assert(Partitioner->getNumPartitions() > 0 &&
 339          "Must always partition into at least one partition");
 340
 341   TreeNode->setNumChildren(Partitioner->getNumPartitions());
 342   for (auto &C : enumerate(TreeNode->children())) {
 343     SubtreeBuilders.emplace_back(&C.value(), NextInstrID);
 344     Partitioner->applyForPartition(C.index(), *this, SubtreeBuilders.back());
 345   }
 346
 347   TreeNode->setPartitioner(std::move(Partitioner));
 348
 349   // Recurse into the subtree builders. Each one must get a copy of the
 350   // remaining partitioners as each path has to check everything.
 351   for (auto &SubtreeBuilder : SubtreeBuilders) {
 352     for (const auto &Partitioner : Partitioners)
 353       SubtreeBuilder.addPartitioner(Partitioner->clone());
 354     SubtreeBuilder.runStep();
 355   }
 356 }
 357
 358 std::unique_ptr<GIMatchTree> GIMatchTreeBuilder::run() {
 359   unsigned NewInstrID = allocInstrID();
 360   // Start by recording the root instruction as instr #0 and set up the initial
 361   // partitioners.
 362   for (auto &Leaf : Leaves) {
 363     LLVM_DEBUG(Leaf.getMatchDag().writeDOTGraph(dbgs(), Leaf.getName()));
 364     GIMatchDagInstr *Root =
 365         *(Leaf.getMatchDag().roots().begin() + Leaf.getRootIdx());
 366     Leaf.declareInstr(Root, NewInstrID);
 367   }
 368
 369   addPartitionersForInstr(NewInstrID);
 370
 371   std::unique_ptr<GIMatchTree> TreeRoot = std::make_unique<GIMatchTree>();
 372   TreeNode = TreeRoot.get();
 373   runStep();
 374
 375   return TreeRoot;
 376 }
 377
 378 void GIMatchTreeOpcodePartitioner::emitPartitionName(raw_ostream &OS, unsigned Idx) const {
 379   if (PartitionToInstr[Idx] == nullptr) {
 380     OS << "* or nullptr";
 381     return;
 382   }
 383   OS << PartitionToInstr[Idx]->Namespace
 384      << "::" << PartitionToInstr[Idx]->TheDef->getName();
 385 }
 386
 387 void GIMatchTreeOpcodePartitioner::repartition(
 388     GIMatchTreeBuilder::LeafVec &Leaves) {
 389   Partitions.clear();
 390   InstrToPartition.clear();
 391   PartitionToInstr.clear();
 392   TestedPredicates.clear();
 393
 394   for (const auto &Leaf : enumerate(Leaves)) {
 395     bool AllOpcodes = true;
 396     GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
 397     BitVector TestedPredicatesForLeaf(
 398         Leaf.value().getMatchDag().getNumPredicates());
 399
 400     // If the instruction isn't declared then we don't care about it. Ignore
 401     // it for now and add it to all partitions later once we know what
 402     // partitions we have.
 403     if (!InstrInfo) {
 404       LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
 405                         << " doesn't care about Instr[" << InstrID << "]\n");
 406       assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates());
 407       TestedPredicates.push_back(TestedPredicatesForLeaf);
 408       continue;
 409     }
 410
 411     // If the opcode is available to test then any opcode predicates will have
 412     // been enabled too.
 413     for (unsigned PIdx : Leaf.value().TestablePredicates.set_bits()) {
 414       const auto &P = Leaf.value().getPredicate(PIdx);
 415       SmallVector<const CodeGenInstruction *, 1> OpcodesForThisPredicate;
 416       if (const auto *OpcodeP = dyn_cast<const GIMatchDagOpcodePredicate>(P)) {
 417         // We've found _an_ opcode predicate, but we don't know if it's
 418         // checking this instruction yet.
 419         bool IsThisPredicate = false;
 420         for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) {
 421           if (PDep->getRequiredMI() == InstrInfo->getInstrNode() &&
 422               PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) {
 423             IsThisPredicate = true;
 424             break;
 425           }
 426         }
 427         if (!IsThisPredicate)
 428           continue;
 429
 430         // If we get here twice then we've somehow ended up with two opcode
 431         // predicates for one instruction in the same DAG. That should be
 432         // impossible.
 433         assert(AllOpcodes && "Conflicting opcode predicates");
 434         const CodeGenInstruction *Expected = OpcodeP->getInstr();
 435         OpcodesForThisPredicate.push_back(Expected);
 436       }
 437
 438       if (const auto *OpcodeP =
 439               dyn_cast<const GIMatchDagOneOfOpcodesPredicate>(P)) {
 440         // We've found _an_ oneof(opcodes) predicate, but we don't know if it's
 441         // checking this instruction yet.
 442         bool IsThisPredicate = false;
 443         for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) {
 444           if (PDep->getRequiredMI() == InstrInfo->getInstrNode() &&
 445               PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) {
 446             IsThisPredicate = true;
 447             break;
 448           }
 449         }
 450         if (!IsThisPredicate)
 451           continue;
 452
 453         // If we get here twice then we've somehow ended up with two opcode
 454         // predicates for one instruction in the same DAG. That should be
 455         // impossible.
 456         assert(AllOpcodes && "Conflicting opcode predicates");
 457         append_range(OpcodesForThisPredicate, OpcodeP->getInstrs());
 458       }
 459
 460       for (const CodeGenInstruction *Expected : OpcodesForThisPredicate) {
 461         // Mark this predicate as one we're testing.
 462         TestedPredicatesForLeaf.set(PIdx);
 463
 464         // Partitions must be numbered 0, 1, .., N but instructions don't meet
 465         // that requirement. Assign a partition number to each opcode if we
 466         // lack one ...
 467         auto Partition = InstrToPartition.find(Expected);
 468         if (Partition == InstrToPartition.end()) {
 469           BitVector Contents(Leaves.size());
 470           Partition = InstrToPartition
 471                           .insert(std::make_pair(Expected, Partitions.size()))
 472                           .first;
 473           PartitionToInstr.push_back(Expected);
 474           Partitions.insert(std::make_pair(Partitions.size(), Contents));
 475         }
 476         // ... and mark this leaf as being in that partition.
 477         Partitions.find(Partition->second)->second.set(Leaf.index());
 478         AllOpcodes = false;
 479         LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
 480                           << " is in partition " << Partition->second << "\n");
 481       }
 482
 483       // TODO: This is where we would handle multiple choices of opcode
 484       //       the end result will be that this leaf ends up in multiple
 485       //       partitions similarly to AllOpcodes.
 486     }
 487
 488     // If we never check the opcode, add it to every partition.
 489     if (AllOpcodes) {
 490       // Add a partition for the default case if we don't already have one.
 491       if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
 492         PartitionToInstr.push_back(nullptr);
 493         BitVector Contents(Leaves.size());
 494         Partitions.insert(std::make_pair(Partitions.size(), Contents));
 495       }
 496       LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
 497                         << " is in all partitions (opcode not checked)\n");
 498       for (auto &Partition : Partitions)
 499         Partition.second.set(Leaf.index());
 500     }
 501
 502     assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates());
 503     TestedPredicates.push_back(TestedPredicatesForLeaf);
 504   }
 505
 506   if (Partitions.size() == 0) {
 507     // Add a partition for the default case if we don't already have one.
 508     if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
 509       PartitionToInstr.push_back(nullptr);
 510       BitVector Contents(Leaves.size());
 511       Partitions.insert(std::make_pair(Partitions.size(), Contents));
 512     }
 513   }
 514
 515   // Add any leaves that don't care about this instruction to all partitions.
 516   for (const auto &Leaf : enumerate(Leaves)) {
 517     GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
 518     if (!InstrInfo) {
 519       // Add a partition for the default case if we don't already have one.
 520       if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
 521         PartitionToInstr.push_back(nullptr);
 522         BitVector Contents(Leaves.size());
 523         Partitions.insert(std::make_pair(Partitions.size(), Contents));
 524       }
 525       for (auto &Partition : Partitions)
 526         Partition.second.set(Leaf.index());
 527     }
 528   }
 529
 530 }
 531
 532 void GIMatchTreeOpcodePartitioner::applyForPartition(
 533     unsigned PartitionIdx, GIMatchTreeBuilder &Builder, GIMatchTreeBuilder &SubBuilder) {
 534   LLVM_DEBUG(dbgs() << "  Making partition " << PartitionIdx << "\n");
 535   const CodeGenInstruction *CGI = PartitionToInstr[PartitionIdx];
 536
 537   BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
 538   // Consume any predicates we handled.
 539   for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
 540     if (!PossibleLeaves[EnumeratedLeaf.index()])
 541       continue;
 542
 543     auto &Leaf = EnumeratedLeaf.value();
 544     const auto &TestedPredicatesForLeaf =
 545         TestedPredicates[EnumeratedLeaf.index()];
 546
 547     for (unsigned PredIdx : TestedPredicatesForLeaf.set_bits()) {
 548       LLVM_DEBUG(dbgs() << "    " << Leaf.getName() << " tested predicate #"
 549                         << PredIdx << " of " << TestedPredicatesForLeaf.size()
 550                         << " " << *Leaf.getPredicate(PredIdx) << "\n");
 551       Leaf.RemainingPredicates.reset(PredIdx);
 552       Leaf.TestablePredicates.reset(PredIdx);
 553     }
 554     SubBuilder.addLeaf(Leaf);
 555   }
 556
 557   // Nothing to do, we don't know anything about this instruction as a result
 558   // of this partitioner.
 559   if (CGI == nullptr)
 560     return;
 561
 562   GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves();
 563   // Find all the operands we know to exist and are referenced. This will
 564   // usually be all the referenced operands but there are some cases where
 565   // instructions are variadic. Such operands must be handled by partitioners
 566   // that check the number of operands.
 567   BitVector ReferencedOperands(1);
 568   for (auto &Leaf : NewLeaves) {
 569     GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID);
 570     // Skip any leaves that don't care about this instruction.
 571     if (!InstrInfo)
 572       continue;
 573     const GIMatchDagInstr *Instr = InstrInfo->getInstrNode();
 574     for (auto &E : enumerate(Leaf.getMatchDag().edges())) {
 575       if (E.value()->getFromMI() == Instr &&
 576           E.value()->getFromMO()->getIdx() < CGI->Operands.size()) {
 577         ReferencedOperands.resize(E.value()->getFromMO()->getIdx() + 1);
 578         ReferencedOperands.set(E.value()->getFromMO()->getIdx());
 579       }
 580     }
 581   }
 582   for (auto &Leaf : NewLeaves) {
 583     for (unsigned OpIdx : ReferencedOperands.set_bits()) {
 584       Leaf.declareOperand(InstrID, OpIdx);
 585     }
 586   }
 587   for (unsigned OpIdx : ReferencedOperands.set_bits()) {
 588     SubBuilder.addPartitionersForOperand(InstrID, OpIdx);
 589   }
 590 }
 591
 592 void GIMatchTreeOpcodePartitioner::emitPartitionResults(
 593     raw_ostream &OS) const {
 594   OS << "Partitioning by opcode would produce " << Partitions.size()
 595      << " partitions\n";
 596   for (const auto &Partition : InstrToPartition) {
 597     if (Partition.first == nullptr)
 598       OS << "Default: ";
 599     else
 600       OS << Partition.first->TheDef->getName() << ": ";
 601     StringRef Separator = "";
 602     for (unsigned I : Partitions.find(Partition.second)->second.set_bits()) {
 603       OS << Separator << I;
 604       Separator = ", ";
 605     }
 606     OS << "\n";
 607   }
 608 }
 609
 610 void GIMatchTreeOpcodePartitioner::generatePartitionSelectorCode(
 611     raw_ostream &OS, StringRef Indent) const {
 612   // Make sure not to emit empty switch or switch with just default
 613   if (PartitionToInstr.size() == 1 && PartitionToInstr[0] == nullptr) {
 614     OS << Indent << "Partition = 0;\n";
 615   } else if (PartitionToInstr.size()) {
 616     OS << Indent << "Partition = -1;\n"
 617        << Indent << "switch (MIs[" << InstrID << "]->getOpcode()) {\n";
 618     for (const auto &EnumInstr : enumerate(PartitionToInstr)) {
 619       if (EnumInstr.value() == nullptr)
 620         OS << Indent << "default:";
 621       else
 622         OS << Indent << "case " << EnumInstr.value()->Namespace
 623            << "::" << EnumInstr.value()->TheDef->getName() << ":";
 624       OS << " Partition = " << EnumInstr.index() << "; break;\n";
 625     }
 626     OS << Indent << "}\n";
 627   }
 628   OS << Indent
 629      << "// Default case but without conflicting with potential default case "
 630         "in selection.\n"
 631      << Indent << "if (Partition == -1) return false;\n";
 632 }
 633
 634 void GIMatchTreeVRegDefPartitioner::addToPartition(bool Result,
 635                                                    unsigned LeafIdx) {
 636   auto I = ResultToPartition.find(Result);
 637   if (I == ResultToPartition.end()) {
 638     ResultToPartition.insert(std::make_pair(Result, PartitionToResult.size()));
 639     PartitionToResult.push_back(Result);
 640   }
 641   I = ResultToPartition.find(Result);
 642   auto P = Partitions.find(I->second);
 643   if (P == Partitions.end())
 644     P = Partitions.insert(std::make_pair(I->second, BitVector())).first;
 645   P->second.resize(LeafIdx + 1);
 646   P->second.set(LeafIdx);
 647 }
 648
 649 void GIMatchTreeVRegDefPartitioner::repartition(
 650     GIMatchTreeBuilder::LeafVec &Leaves) {
 651   Partitions.clear();
 652
 653   for (const auto &Leaf : enumerate(Leaves)) {
 654     GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
 655     BitVector TraversedEdgesForLeaf(Leaf.value().getMatchDag().getNumEdges());
 656
 657     // If the instruction isn't declared then we don't care about it. Ignore
 658     // it for now and add it to all partitions later once we know what
 659     // partitions we have.
 660     if (!InstrInfo) {
 661       TraversedEdges.push_back(TraversedEdgesForLeaf);
 662       continue;
 663     }
 664
 665     // If this node has an use -> def edge from this operand then this
 666     // instruction must be in partition 1 (isVRegDef()).
 667     bool WantsEdge = false;
 668     for (unsigned EIdx : Leaf.value().TraversableEdges.set_bits()) {
 669       const auto &E = Leaf.value().getEdge(EIdx);
 670       if (E->getFromMI() != InstrInfo->getInstrNode() ||
 671           E->getFromMO()->getIdx() != OpIdx || E->isDefToUse())
 672         continue;
 673
 674       // We're looking at the right edge. This leaf wants a vreg def so we'll
 675       // put it in partition 1.
 676       addToPartition(true, Leaf.index());
 677       TraversedEdgesForLeaf.set(EIdx);
 678       WantsEdge = true;
 679     }
 680
 681     bool isNotReg = false;
 682     if (!WantsEdge && isNotReg) {
 683       // If this leaf doesn't have an edge and we _don't_ want a register,
 684       // then add it to partition 0.
 685       addToPartition(false, Leaf.index());
 686     } else if (!WantsEdge) {
 687       // If this leaf doesn't have an edge and we don't know what we want,
 688       // then add it to partition 0 and 1.
 689       addToPartition(false, Leaf.index());
 690       addToPartition(true, Leaf.index());
 691     }
 692
 693     TraversedEdges.push_back(TraversedEdgesForLeaf);
 694   }
 695
 696   // Add any leaves that don't care about this instruction to all partitions.
 697   for (const auto &Leaf : enumerate(Leaves)) {
 698     GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
 699     if (!InstrInfo)
 700       for (auto &Partition : Partitions)
 701         Partition.second.set(Leaf.index());
 702   }
 703 }
 704
 705 void GIMatchTreeVRegDefPartitioner::applyForPartition(
 706     unsigned PartitionIdx, GIMatchTreeBuilder &Builder,
 707     GIMatchTreeBuilder &SubBuilder) {
 708   BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
 709
 710   std::vector<BitVector> TraversedEdgesByNewLeaves;
 711   // Consume any edges we handled.
 712   for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
 713     if (!PossibleLeaves[EnumeratedLeaf.index()])
 714       continue;
 715
 716     auto &Leaf = EnumeratedLeaf.value();
 717     const auto &TraversedEdgesForLeaf = TraversedEdges[EnumeratedLeaf.index()];
 718     TraversedEdgesByNewLeaves.push_back(TraversedEdgesForLeaf);
 719     Leaf.RemainingEdges.reset(TraversedEdgesForLeaf);
 720     Leaf.TraversableEdges.reset(TraversedEdgesForLeaf);
 721     SubBuilder.addLeaf(Leaf);
 722   }
 723
 724   // Nothing to do. The only thing we know is that it isn't a vreg-def.
 725   if (PartitionToResult[PartitionIdx] == false)
 726     return;
 727
 728   NewInstrID = SubBuilder.allocInstrID();
 729
 730   GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves();
 731   for (const auto I : zip(NewLeaves, TraversedEdgesByNewLeaves)) {
 732     auto &Leaf = std::get<0>(I);
 733     auto &TraversedEdgesForLeaf = std::get<1>(I);
 734     GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID);
 735     // Skip any leaves that don't care about this instruction.
 736     if (!InstrInfo)
 737       continue;
 738     for (unsigned EIdx : TraversedEdgesForLeaf.set_bits()) {
 739       const GIMatchDagEdge *E = Leaf.getEdge(EIdx);
 740       Leaf.declareInstr(E->getToMI(), NewInstrID);
 741     }
 742   }
 743   SubBuilder.addPartitionersForInstr(NewInstrID);
 744 }
 745
 746 void GIMatchTreeVRegDefPartitioner::emitPartitionResults(
 747     raw_ostream &OS) const {
 748   OS << "Partitioning by vreg-def would produce " << Partitions.size()
 749      << " partitions\n";
 750   for (const auto &Partition : Partitions) {
 751     OS << Partition.first << " (";
 752     emitPartitionName(OS, Partition.first);
 753     OS << "): ";
 754     StringRef Separator = "";
 755     for (unsigned I : Partition.second.set_bits()) {
 756       OS << Separator << I;
 757       Separator = ", ";
 758     }
 759     OS << "\n";
 760   }
 761 }
 762
 763 void GIMatchTreeVRegDefPartitioner::generatePartitionSelectorCode(
 764     raw_ostream &OS, StringRef Indent) const {
 765   OS << Indent << "Partition = -1\n"
 766      << Indent << "if (MIs.size() <= NewInstrID) MIs.resize(NewInstrID + 1);\n"
 767      << Indent << "MIs[" << NewInstrID << "] = nullptr;\n"
 768      << Indent << "if (MIs[" << InstrID << "].getOperand(" << OpIdx
 769      << ").isReg()))\n"
 770      << Indent << "  MIs[" << NewInstrID << "] = MRI.getVRegDef(MIs[" << InstrID
 771      << "].getOperand(" << OpIdx << ").getReg()));\n";
 772
 773   for (const auto &Pair : ResultToPartition)
 774     OS << Indent << "if (MIs[" << NewInstrID << "] "
 775        << (Pair.first ? "==" : "!=")
 776        << " nullptr) Partition = " << Pair.second << ";\n";
 777
 778   OS << Indent << "if (Partition == -1) return false;\n";
 779 }