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/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 = std::find(MatchDag.instr_nodes_begin(),
 125                             MatchDag.instr_nodes_end(), Instr);
 126   assert(NodeI != MatchDag.instr_nodes_end() && "Instr isn't in this DAG");
 127   unsigned InstrIdx = MatchDag.getInstrNodeIdx(NodeI);
 128   RemainingInstrNodes.reset(InstrIdx);
 129
 130   // When we declare an instruction, we don't expose any traversable edges just
 131   // yet. A partitioner has to check they exist and are registers before they
 132   // are traversable.
 133
 134   // When we declare an instruction, we potentially activate some predicates.
 135   // Mark the dependencies that are now satisfied as a result of this
 136   // instruction and mark any predicates whose dependencies are fully
 137   // satisfied.
 138   for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
 139     if (Dep.value()->getRequiredMI() == Instr &&
 140         Dep.value()->getRequiredMO() == nullptr) {
 141       for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
 142         DepsFor.value().reset(Dep.index());
 143         if (DepsFor.value().none())
 144           TestablePredicates.set(DepsFor.index());
 145       }
 146     }
 147   }
 148 }
 149
 150 void GIMatchTreeBuilderLeafInfo::declareOperand(unsigned InstrID,
 151                                                 unsigned OpIdx) {
 152   const GIMatchDagInstr *Instr = InstrIDToInfo.lookup(InstrID)->getInstrNode();
 153
 154   OperandIDToInfo.insert(std::make_pair(
 155       std::make_pair(InstrID, OpIdx),
 156       GIMatchTreeOperandInfo(Instr, OpIdx)));
 157
 158   // When an operand becomes reachable, we potentially activate some traversals.
 159   // Record the edges that can now be followed as a result of this
 160   // instruction.
 161   for (auto &E : enumerate(MatchDag.edges())) {
 162     if (E.value()->getFromMI() == Instr &&
 163         E.value()->getFromMO()->getIdx() == OpIdx) {
 164       TraversableEdges.set(E.index());
 165     }
 166   }
 167
 168   // When an operand becomes reachable, we potentially activate some predicates.
 169   // Clear the dependencies that are now satisfied as a result of this
 170   // operand and activate any predicates whose dependencies are fully
 171   // satisfied.
 172   for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
 173     if (Dep.value()->getRequiredMI() == Instr && Dep.value()->getRequiredMO() &&
 174         Dep.value()->getRequiredMO()->getIdx() == OpIdx) {
 175       for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
 176         DepsFor.value().reset(Dep.index());
 177         if (DepsFor.value().none())
 178           TestablePredicates.set(DepsFor.index());
 179       }
 180     }
 181   }
 182 }
 183
 184 void GIMatchTreeBuilder::addPartitionersForInstr(unsigned InstrIdx) {
 185   // Find the partitioners that can be used now that this node is
 186   // uncovered. Our choices are:
 187   // - Test the opcode
 188   addPartitioner(std::make_unique<GIMatchTreeOpcodePartitioner>(InstrIdx));
 189 }
 190
 191 void GIMatchTreeBuilder::addPartitionersForOperand(unsigned InstrID,
 192                                                    unsigned OpIdx) {
 193   LLVM_DEBUG(dbgs() << "Add partitioners for Instrs[" << InstrID
 194                     << "].getOperand(" << OpIdx << ")\n");
 195   addPartitioner(
 196       std::make_unique<GIMatchTreeVRegDefPartitioner>(InstrID, OpIdx));
 197 }
 198
 199 void GIMatchTreeBuilder::filterRedundantPartitioners() {
 200   // TODO: Filter partitioners for facts that are already known
 201   // - If we know the opcode, we can elide the num operand check so long as
 202   //   the instruction has a fixed number of operands.
 203   // - If we know an exact number of operands then we can elide further number
 204   //   of operand checks.
 205   // - If the current min number of operands exceeds the one we want to check
 206   //   then we can elide it.
 207 }
 208
 209 void GIMatchTreeBuilder::evaluatePartitioners() {
 210   // Determine the partitioning the partitioner would produce
 211   for (auto &Partitioner : Partitioners) {
 212     LLVM_DEBUG(dbgs() << "    Weighing up ";
 213                Partitioner->emitDescription(dbgs()); dbgs() << "\n");
 214     Partitioner->repartition(Leaves);
 215     LLVM_DEBUG(Partitioner->emitPartitionResults(dbgs()));
 216   }
 217 }
 218
 219 void GIMatchTreeBuilder::runStep() {
 220   LLVM_DEBUG(dbgs() << "Building match tree node for " << TreeNode << "\n");
 221   LLVM_DEBUG(dbgs() << "  Rules reachable at this node:\n");
 222   for (const auto &Leaf : Leaves) {
 223     LLVM_DEBUG(dbgs() << "    " << Leaf.getName() << " (" << &Leaf.getInfo() << "\n");
 224     TreeNode->addPossibleLeaf(Leaf.getInfo(), Leaf.isFullyTraversed(),
 225                               Leaf.isFullyTested());
 226   }
 227
 228   LLVM_DEBUG(dbgs() << "  Partitioners available at this node:\n");
 229 #ifndef NDEBUG
 230   for (const auto &Partitioner : Partitioners)
 231     LLVM_DEBUG(dbgs() << "    "; Partitioner->emitDescription(dbgs());
 232                dbgs() << "\n");
 233 #endif // ifndef NDEBUG
 234
 235   // Check for unreachable rules. Rules are unreachable if they are preceeded by
 236   // a fully tested rule.
 237   // Note: This is only true for the current algorithm, if we allow the
 238   //       algorithm to compare equally valid rules then they will become
 239   //       reachable.
 240   {
 241     auto FullyTestedLeafI = Leaves.end();
 242     for (auto LeafI = Leaves.begin(), LeafE = Leaves.end();
 243          LeafI != LeafE; ++LeafI) {
 244       if (LeafI->isFullyTraversed() && LeafI->isFullyTested())
 245         FullyTestedLeafI = LeafI;
 246       else if (FullyTestedLeafI != Leaves.end()) {
 247         PrintError("Leaf " + LeafI->getName() + " is unreachable");
 248         PrintNote("Leaf " + FullyTestedLeafI->getName() +
 249                   " will have already matched");
 250       }
 251     }
 252   }
 253
 254   LLVM_DEBUG(dbgs() << "  Eliminating redundant partitioners:\n");
 255   filterRedundantPartitioners();
 256   LLVM_DEBUG(dbgs() << "  Partitioners remaining:\n");
 257 #ifndef NDEBUG
 258   for (const auto &Partitioner : Partitioners)
 259     LLVM_DEBUG(dbgs() << "    "; Partitioner->emitDescription(dbgs());
 260                dbgs() << "\n");
 261 #endif // ifndef NDEBUG
 262
 263   if (Partitioners.empty()) {
 264     // Nothing left to do but check we really did identify a single rule.
 265     if (Leaves.size() > 1) {
 266       LLVM_DEBUG(dbgs() << "Leaf contains multiple rules, drop after the first "
 267                            "fully tested rule\n");
 268       auto FirstFullyTested =
 269           std::find_if(Leaves.begin(), Leaves.end(),
 270                        [](const GIMatchTreeBuilderLeafInfo &X) {
 271                          return X.isFullyTraversed() && X.isFullyTested() &&
 272                                 !X.getMatchDag().hasPostMatchPredicate();
 273                        });
 274       if (FirstFullyTested != Leaves.end())
 275         FirstFullyTested++;
 276
 277 #ifndef NDEBUG
 278       for (auto &Leaf : make_range(Leaves.begin(), FirstFullyTested))
 279         LLVM_DEBUG(dbgs() << "  Kept " << Leaf.getName() << "\n");
 280       for (const auto &Leaf : make_range(FirstFullyTested, Leaves.end()))
 281         LLVM_DEBUG(dbgs() << "  Dropped " << Leaf.getName() << "\n");
 282 #endif // ifndef NDEBUG
 283       TreeNode->dropLeavesAfter(
 284           std::distance(Leaves.begin(), FirstFullyTested));
 285     }
 286     for (const auto &Leaf : Leaves) {
 287       if (!Leaf.isFullyTraversed()) {
 288         PrintError("Leaf " + Leaf.getName() + " is not fully traversed");
 289         PrintNote("This indicates a missing partitioner within tblgen");
 290         Leaf.dump(errs());
 291         for (unsigned InstrIdx : Leaf.untested_instrs())
 292           PrintNote("Instr " + llvm::to_string(*Leaf.getInstr(InstrIdx)));
 293         for (unsigned EdgeIdx : Leaf.untested_edges())
 294           PrintNote("Edge " + llvm::to_string(*Leaf.getEdge(EdgeIdx)));
 295       }
 296     }
 297
 298     // Copy out information about untested predicates so the user of the tree
 299     // can deal with them.
 300     for (auto LeafPair : zip(Leaves, TreeNode->possible_leaves())) {
 301       const GIMatchTreeBuilderLeafInfo &BuilderLeaf = std::get<0>(LeafPair);
 302       GIMatchTreeLeafInfo &TreeLeaf = std::get<1>(LeafPair);
 303       if (!BuilderLeaf.isFullyTested())
 304         for (unsigned PredicateIdx : BuilderLeaf.untested_predicates())
 305           TreeLeaf.addUntestedPredicate(BuilderLeaf.getPredicate(PredicateIdx));
 306     }
 307     return;
 308   }
 309
 310   LLVM_DEBUG(dbgs() << "  Weighing up partitioners:\n");
 311   evaluatePartitioners();
 312
 313   // Select the best partitioner by its ability to partition
 314   // - Prefer partitioners that don't distinguish between partitions. This
 315   //   is to fail early on decisions that must go a single way.
 316   auto PartitionerI = std::max_element(
 317       Partitioners.begin(), Partitioners.end(),
 318       [](const std::unique_ptr<GIMatchTreePartitioner> &A,
 319          const std::unique_ptr<GIMatchTreePartitioner> &B) {
 320         // We generally want partitioners that subdivide the
 321         // ruleset as much as possible since these take fewer
 322         // checks to converge on a particular rule. However,
 323         // it's important to note that one leaf can end up in
 324         // multiple partitions if the check isn't mutually
 325         // exclusive (e.g. getVRegDef() vs isReg()).
 326         // We therefore minimize average leaves per partition.
 327         return (double)A->getNumLeavesWithDupes() / A->getNumPartitions() >
 328                (double)B->getNumLeavesWithDupes() / B->getNumPartitions();
 329       });
 330
 331   // Select a partitioner and partition the ruleset
 332   // Note that it's possible for a single rule to end up in multiple
 333   // partitions. For example, an opcode test on a rule without an opcode
 334   // predicate will result in it being passed to all partitions.
 335   std::unique_ptr<GIMatchTreePartitioner> Partitioner = std::move(*PartitionerI);
 336   Partitioners.erase(PartitionerI);
 337   LLVM_DEBUG(dbgs() << "  Selected partitioner: ";
 338              Partitioner->emitDescription(dbgs()); dbgs() << "\n");
 339
 340   assert(Partitioner->getNumPartitions() > 0 &&
 341          "Must always partition into at least one partition");
 342
 343   TreeNode->setNumChildren(Partitioner->getNumPartitions());
 344   for (auto &C : enumerate(TreeNode->children())) {
 345     SubtreeBuilders.emplace_back(&C.value(), NextInstrID);
 346     Partitioner->applyForPartition(C.index(), *this, SubtreeBuilders.back());
 347   }
 348
 349   TreeNode->setPartitioner(std::move(Partitioner));
 350
 351   // Recurse into the subtree builders. Each one must get a copy of the
 352   // remaining partitioners as each path has to check everything.
 353   for (auto &SubtreeBuilder : SubtreeBuilders) {
 354     for (const auto &Partitioner : Partitioners)
 355       SubtreeBuilder.addPartitioner(Partitioner->clone());
 356     SubtreeBuilder.runStep();
 357   }
 358 }
 359
 360 std::unique_ptr<GIMatchTree> GIMatchTreeBuilder::run() {
 361   unsigned NewInstrID = allocInstrID();
 362   // Start by recording the root instruction as instr #0 and set up the initial
 363   // partitioners.
 364   for (auto &Leaf : Leaves) {
 365     LLVM_DEBUG(Leaf.getMatchDag().writeDOTGraph(dbgs(), Leaf.getName()));
 366     GIMatchDagInstr *Root =
 367         *(Leaf.getMatchDag().roots().begin() + Leaf.getRootIdx());
 368     Leaf.declareInstr(Root, NewInstrID);
 369   }
 370
 371   addPartitionersForInstr(NewInstrID);
 372
 373   std::unique_ptr<GIMatchTree> TreeRoot = std::make_unique<GIMatchTree>();
 374   TreeNode = TreeRoot.get();
 375   runStep();
 376
 377   return TreeRoot;
 378 }
 379
 380 void GIMatchTreeOpcodePartitioner::emitPartitionName(raw_ostream &OS, unsigned Idx) const {
 381   if (PartitionToInstr[Idx] == nullptr) {
 382     OS << "* or nullptr";
 383     return;
 384   }
 385   OS << PartitionToInstr[Idx]->Namespace
 386      << "::" << PartitionToInstr[Idx]->TheDef->getName();
 387 }
 388
 389 void GIMatchTreeOpcodePartitioner::repartition(
 390     GIMatchTreeBuilder::LeafVec &Leaves) {
 391   Partitions.clear();
 392   InstrToPartition.clear();
 393   PartitionToInstr.clear();
 394   TestedPredicates.clear();
 395
 396   for (const auto &Leaf : enumerate(Leaves)) {
 397     bool AllOpcodes = true;
 398     GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
 399     BitVector TestedPredicatesForLeaf(
 400         Leaf.value().getMatchDag().getNumPredicates());
 401
 402     // If the instruction isn't declared then we don't care about it. Ignore
 403     // it for now and add it to all partitions later once we know what
 404     // partitions we have.
 405     if (!InstrInfo) {
 406       LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
 407                         << " doesn't care about Instr[" << InstrID << "]\n");
 408       assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates());
 409       TestedPredicates.push_back(TestedPredicatesForLeaf);
 410       continue;
 411     }
 412
 413     // If the opcode is available to test then any opcode predicates will have
 414     // been enabled too.
 415     for (unsigned PIdx : Leaf.value().TestablePredicates.set_bits()) {
 416       const auto &P = Leaf.value().getPredicate(PIdx);
 417       SmallVector<const CodeGenInstruction *, 1> OpcodesForThisPredicate;
 418       if (const auto *OpcodeP = dyn_cast<const GIMatchDagOpcodePredicate>(P)) {
 419         // We've found _an_ opcode predicate, but we don't know if it's
 420         // checking this instruction yet.
 421         bool IsThisPredicate = false;
 422         for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) {
 423           if (PDep->getRequiredMI() == InstrInfo->getInstrNode() &&
 424               PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) {
 425             IsThisPredicate = true;
 426             break;
 427           }
 428         }
 429         if (!IsThisPredicate)
 430           continue;
 431
 432         // If we get here twice then we've somehow ended up with two opcode
 433         // predicates for one instruction in the same DAG. That should be
 434         // impossible.
 435         assert(AllOpcodes && "Conflicting opcode predicates");
 436         const CodeGenInstruction *Expected = OpcodeP->getInstr();
 437         OpcodesForThisPredicate.push_back(Expected);
 438       }
 439
 440       if (const auto *OpcodeP =
 441               dyn_cast<const GIMatchDagOneOfOpcodesPredicate>(P)) {
 442         // We've found _an_ oneof(opcodes) predicate, but we don't know if it's
 443         // checking this instruction yet.
 444         bool IsThisPredicate = false;
 445         for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) {
 446           if (PDep->getRequiredMI() == InstrInfo->getInstrNode() &&
 447               PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) {
 448             IsThisPredicate = true;
 449             break;
 450           }
 451         }
 452         if (!IsThisPredicate)
 453           continue;
 454
 455         // If we get here twice then we've somehow ended up with two opcode
 456         // predicates for one instruction in the same DAG. That should be
 457         // impossible.
 458         assert(AllOpcodes && "Conflicting opcode predicates");
 459         for (const CodeGenInstruction *Expected : OpcodeP->getInstrs())
 460           OpcodesForThisPredicate.push_back(Expected);
 461       }
 462
 463       for (const CodeGenInstruction *Expected : OpcodesForThisPredicate) {
 464         // Mark this predicate as one we're testing.
 465         TestedPredicatesForLeaf.set(PIdx);
 466
 467         // Partitions must be numbered 0, 1, .., N but instructions don't meet
 468         // that requirement. Assign a partition number to each opcode if we
 469         // lack one ...
 470         auto Partition = InstrToPartition.find(Expected);
 471         if (Partition == InstrToPartition.end()) {
 472           BitVector Contents(Leaves.size());
 473           Partition = InstrToPartition
 474                           .insert(std::make_pair(Expected, Partitions.size()))
 475                           .first;
 476           PartitionToInstr.push_back(Expected);
 477           Partitions.insert(std::make_pair(Partitions.size(), Contents));
 478         }
 479         // ... and mark this leaf as being in that partition.
 480         Partitions.find(Partition->second)->second.set(Leaf.index());
 481         AllOpcodes = false;
 482         LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
 483                           << " is in partition " << Partition->second << "\n");
 484       }
 485
 486       // TODO: This is where we would handle multiple choices of opcode
 487       //       the end result will be that this leaf ends up in multiple
 488       //       partitions similarly to AllOpcodes.
 489     }
 490
 491     // If we never check the opcode, add it to every partition.
 492     if (AllOpcodes) {
 493       // Add a partition for the default case if we don't already have one.
 494       if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
 495         PartitionToInstr.push_back(nullptr);
 496         BitVector Contents(Leaves.size());
 497         Partitions.insert(std::make_pair(Partitions.size(), Contents));
 498       }
 499       LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
 500                         << " is in all partitions (opcode not checked)\n");
 501       for (auto &Partition : Partitions)
 502         Partition.second.set(Leaf.index());
 503     }
 504
 505     assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates());
 506     TestedPredicates.push_back(TestedPredicatesForLeaf);
 507   }
 508
 509   if (Partitions.size() == 0) {
 510     // Add a partition for the default case if we don't already have one.
 511     if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
 512       PartitionToInstr.push_back(nullptr);
 513       BitVector Contents(Leaves.size());
 514       Partitions.insert(std::make_pair(Partitions.size(), Contents));
 515     }
 516   }
 517
 518   // Add any leaves that don't care about this instruction to all partitions.
 519   for (const auto &Leaf : enumerate(Leaves)) {
 520     GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
 521     if (!InstrInfo) {
 522       // Add a partition for the default case if we don't already have one.
 523       if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
 524         PartitionToInstr.push_back(nullptr);
 525         BitVector Contents(Leaves.size());
 526         Partitions.insert(std::make_pair(Partitions.size(), Contents));
 527       }
 528       for (auto &Partition : Partitions)
 529         Partition.second.set(Leaf.index());
 530     }
 531   }
 532
 533 }
 534
 535 void GIMatchTreeOpcodePartitioner::applyForPartition(
 536     unsigned PartitionIdx, GIMatchTreeBuilder &Builder, GIMatchTreeBuilder &SubBuilder) {
 537   LLVM_DEBUG(dbgs() << "  Making partition " << PartitionIdx << "\n");
 538   const CodeGenInstruction *CGI = PartitionToInstr[PartitionIdx];
 539
 540   BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
 541   // Consume any predicates we handled.
 542   for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
 543     if (!PossibleLeaves[EnumeratedLeaf.index()])
 544       continue;
 545
 546     auto &Leaf = EnumeratedLeaf.value();
 547     const auto &TestedPredicatesForLeaf =
 548         TestedPredicates[EnumeratedLeaf.index()];
 549
 550     for (unsigned PredIdx : TestedPredicatesForLeaf.set_bits()) {
 551       LLVM_DEBUG(dbgs() << "    " << Leaf.getName() << " tested predicate #"
 552                         << PredIdx << " of " << TestedPredicatesForLeaf.size()
 553                         << " " << *Leaf.getPredicate(PredIdx) << "\n");
 554       Leaf.RemainingPredicates.reset(PredIdx);
 555       Leaf.TestablePredicates.reset(PredIdx);
 556     }
 557     SubBuilder.addLeaf(Leaf);
 558   }
 559
 560   // Nothing to do, we don't know anything about this instruction as a result
 561   // of this partitioner.
 562   if (CGI == nullptr)
 563     return;
 564
 565   GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves();
 566   // Find all the operands we know to exist and are referenced. This will
 567   // usually be all the referenced operands but there are some cases where
 568   // instructions are variadic. Such operands must be handled by partitioners
 569   // that check the number of operands.
 570   BitVector ReferencedOperands(1);
 571   for (auto &Leaf : NewLeaves) {
 572     GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID);
 573     // Skip any leaves that don't care about this instruction.
 574     if (!InstrInfo)
 575       continue;
 576     const GIMatchDagInstr *Instr = InstrInfo->getInstrNode();
 577     for (auto &E : enumerate(Leaf.getMatchDag().edges())) {
 578       if (E.value()->getFromMI() == Instr &&
 579           E.value()->getFromMO()->getIdx() < CGI->Operands.size()) {
 580         ReferencedOperands.resize(E.value()->getFromMO()->getIdx() + 1);
 581         ReferencedOperands.set(E.value()->getFromMO()->getIdx());
 582       }
 583     }
 584   }
 585   for (auto &Leaf : NewLeaves) {
 586     for (unsigned OpIdx : ReferencedOperands.set_bits()) {
 587       Leaf.declareOperand(InstrID, OpIdx);
 588     }
 589   }
 590   for (unsigned OpIdx : ReferencedOperands.set_bits()) {
 591     SubBuilder.addPartitionersForOperand(InstrID, OpIdx);
 592   }
 593 }
 594
 595 void GIMatchTreeOpcodePartitioner::emitPartitionResults(
 596     raw_ostream &OS) const {
 597   OS << "Partitioning by opcode would produce " << Partitions.size()
 598      << " partitions\n";
 599   for (const auto &Partition : InstrToPartition) {
 600     if (Partition.first == nullptr)
 601       OS << "Default: ";
 602     else
 603       OS << Partition.first->TheDef->getName() << ": ";
 604     StringRef Separator = "";
 605     for (unsigned I : Partitions.find(Partition.second)->second.set_bits()) {
 606       OS << Separator << I;
 607       Separator = ", ";
 608     }
 609     OS << "\n";
 610   }
 611 }
 612
 613 void GIMatchTreeOpcodePartitioner::generatePartitionSelectorCode(
 614     raw_ostream &OS, StringRef Indent) const {
 615   // Make sure not to emit empty switch or switch with just default
 616   if (PartitionToInstr.size() == 1 && PartitionToInstr[0] == nullptr) {
 617     OS << Indent << "Partition = 0;\n";
 618   } else if (PartitionToInstr.size()) {
 619     OS << Indent << "Partition = -1;\n"
 620        << Indent << "switch (MIs[" << InstrID << "]->getOpcode()) {\n";
 621     for (const auto &EnumInstr : enumerate(PartitionToInstr)) {
 622       if (EnumInstr.value() == nullptr)
 623         OS << Indent << "default:";
 624       else
 625         OS << Indent << "case " << EnumInstr.value()->Namespace
 626            << "::" << EnumInstr.value()->TheDef->getName() << ":";
 627       OS << " Partition = " << EnumInstr.index() << "; break;\n";
 628     }
 629     OS << Indent << "}\n";
 630   }
 631   OS << Indent
 632      << "// Default case but without conflicting with potential default case "
 633         "in selection.\n"
 634      << Indent << "if (Partition == -1) return false;\n";
 635 }
 636
 637 void GIMatchTreeVRegDefPartitioner::addToPartition(bool Result,
 638                                                    unsigned LeafIdx) {
 639   auto I = ResultToPartition.find(Result);
 640   if (I == ResultToPartition.end()) {
 641     ResultToPartition.insert(std::make_pair(Result, PartitionToResult.size()));
 642     PartitionToResult.push_back(Result);
 643   }
 644   I = ResultToPartition.find(Result);
 645   auto P = Partitions.find(I->second);
 646   if (P == Partitions.end())
 647     P = Partitions.insert(std::make_pair(I->second, BitVector())).first;
 648   P->second.resize(LeafIdx + 1);
 649   P->second.set(LeafIdx);
 650 }
 651
 652 void GIMatchTreeVRegDefPartitioner::repartition(
 653     GIMatchTreeBuilder::LeafVec &Leaves) {
 654   Partitions.clear();
 655
 656   for (const auto &Leaf : enumerate(Leaves)) {
 657     GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
 658     BitVector TraversedEdgesForLeaf(Leaf.value().getMatchDag().getNumEdges());
 659
 660     // If the instruction isn't declared then we don't care about it. Ignore
 661     // it for now and add it to all partitions later once we know what
 662     // partitions we have.
 663     if (!InstrInfo) {
 664       TraversedEdges.push_back(TraversedEdgesForLeaf);
 665       continue;
 666     }
 667
 668     // If this node has an use -> def edge from this operand then this
 669     // instruction must be in partition 1 (isVRegDef()).
 670     bool WantsEdge = false;
 671     for (unsigned EIdx : Leaf.value().TraversableEdges.set_bits()) {
 672       const auto &E = Leaf.value().getEdge(EIdx);
 673       if (E->getFromMI() != InstrInfo->getInstrNode() ||
 674           E->getFromMO()->getIdx() != OpIdx || E->isDefToUse())
 675         continue;
 676
 677       // We're looking at the right edge. This leaf wants a vreg def so we'll
 678       // put it in partition 1.
 679       addToPartition(true, Leaf.index());
 680       TraversedEdgesForLeaf.set(EIdx);
 681       WantsEdge = true;
 682     }
 683
 684     bool isNotReg = false;
 685     if (!WantsEdge && isNotReg) {
 686       // If this leaf doesn't have an edge and we _don't_ want a register,
 687       // then add it to partition 0.
 688       addToPartition(false, Leaf.index());
 689     } else if (!WantsEdge) {
 690       // If this leaf doesn't have an edge and we don't know what we want,
 691       // then add it to partition 0 and 1.
 692       addToPartition(false, Leaf.index());
 693       addToPartition(true, Leaf.index());
 694     }
 695
 696     TraversedEdges.push_back(TraversedEdgesForLeaf);
 697   }
 698
 699   // Add any leaves that don't care about this instruction to all partitions.
 700   for (const auto &Leaf : enumerate(Leaves)) {
 701     GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
 702     if (!InstrInfo)
 703       for (auto &Partition : Partitions)
 704         Partition.second.set(Leaf.index());
 705   }
 706 }
 707
 708 void GIMatchTreeVRegDefPartitioner::applyForPartition(
 709     unsigned PartitionIdx, GIMatchTreeBuilder &Builder,
 710     GIMatchTreeBuilder &SubBuilder) {
 711   BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
 712
 713   std::vector<BitVector> TraversedEdgesByNewLeaves;
 714   // Consume any edges we handled.
 715   for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
 716     if (!PossibleLeaves[EnumeratedLeaf.index()])
 717       continue;
 718
 719     auto &Leaf = EnumeratedLeaf.value();
 720     const auto &TraversedEdgesForLeaf = TraversedEdges[EnumeratedLeaf.index()];
 721     TraversedEdgesByNewLeaves.push_back(TraversedEdgesForLeaf);
 722     Leaf.RemainingEdges.reset(TraversedEdgesForLeaf);
 723     Leaf.TraversableEdges.reset(TraversedEdgesForLeaf);
 724     SubBuilder.addLeaf(Leaf);
 725   }
 726
 727   // Nothing to do. The only thing we know is that it isn't a vreg-def.
 728   if (PartitionToResult[PartitionIdx] == false)
 729     return;
 730
 731   NewInstrID = SubBuilder.allocInstrID();
 732
 733   GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves();
 734   for (const auto I : zip(NewLeaves, TraversedEdgesByNewLeaves)) {
 735     auto &Leaf = std::get<0>(I);
 736     auto &TraversedEdgesForLeaf = std::get<1>(I);
 737     GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID);
 738     // Skip any leaves that don't care about this instruction.
 739     if (!InstrInfo)
 740       continue;
 741     for (unsigned EIdx : TraversedEdgesForLeaf.set_bits()) {
 742       const GIMatchDagEdge *E = Leaf.getEdge(EIdx);
 743       Leaf.declareInstr(E->getToMI(), NewInstrID);
 744     }
 745   }
 746   SubBuilder.addPartitionersForInstr(NewInstrID);
 747 }
 748
 749 void GIMatchTreeVRegDefPartitioner::emitPartitionResults(
 750     raw_ostream &OS) const {
 751   OS << "Partitioning by vreg-def would produce " << Partitions.size()
 752      << " partitions\n";
 753   for (const auto &Partition : Partitions) {
 754     OS << Partition.first << " (";
 755     emitPartitionName(OS, Partition.first);
 756     OS << "): ";
 757     StringRef Separator = "";
 758     for (unsigned I : Partition.second.set_bits()) {
 759       OS << Separator << I;
 760       Separator = ", ";
 761     }
 762     OS << "\n";
 763   }
 764 }
 765
 766 void GIMatchTreeVRegDefPartitioner::generatePartitionSelectorCode(
 767     raw_ostream &OS, StringRef Indent) const {
 768   OS << Indent << "Partition = -1\n"
 769      << Indent << "if (MIs.size() <= NewInstrID) MIs.resize(NewInstrID + 1);\n"
 770      << Indent << "MIs[" << NewInstrID << "] = nullptr;\n"
 771      << Indent << "if (MIs[" << InstrID << "].getOperand(" << OpIdx
 772      << ").isReg()))\n"
 773      << Indent << "  MIs[" << NewInstrID << "] = MRI.getVRegDef(MIs[" << InstrID
 774      << "].getOperand(" << OpIdx << ").getReg()));\n";
 775
 776   for (const auto &Pair : ResultToPartition)
 777     OS << Indent << "if (MIs[" << NewInstrID << "] "
 778        << (Pair.first ? "==" : "!=")
 779        << " nullptr) Partition = " << Pair.second << ";\n";
 780
 781   OS << Indent << "if (Partition == -1) return false;\n";
 782 }