1 //===- GIMatchTree.h - 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 #ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H 10 #define LLVM_UTILS_TABLEGEN_GIMATCHTREE_H 11 12 #include "GIMatchDag.h" 13 #include "llvm/ADT/BitVector.h" 14 15 namespace llvm { 16 class raw_ostream; 17 18 class GIMatchTreeBuilder; 19 class GIMatchTreePartitioner; 20 21 /// Describes the binding of a variable to the matched MIR 22 class GIMatchTreeVariableBinding { 23 /// The name of the variable described by this binding. 24 StringRef Name; 25 // The matched instruction it is bound to. 26 unsigned InstrID; 27 // The matched operand (if appropriate) it is bound to. 28 Optional<unsigned> OpIdx; 29 30 public: 31 GIMatchTreeVariableBinding(StringRef Name, unsigned InstrID, 32 Optional<unsigned> OpIdx = None) Name(Name)33 : Name(Name), InstrID(InstrID), OpIdx(OpIdx) {} 34 isInstr()35 bool isInstr() const { return !OpIdx.hasValue(); } getName()36 StringRef getName() const { return Name; } getInstrID()37 unsigned getInstrID() const { return InstrID; } getOpIdx()38 unsigned getOpIdx() const { 39 assert(OpIdx.hasValue() && "Is not an operand binding"); 40 return *OpIdx; 41 } 42 }; 43 44 /// Associates a matchable with a leaf of the decision tree. 45 class GIMatchTreeLeafInfo { 46 public: 47 using const_var_binding_iterator = 48 std::vector<GIMatchTreeVariableBinding>::const_iterator; 49 using UntestedPredicatesTy = SmallVector<const GIMatchDagPredicate *, 1>; 50 using const_untested_predicates_iterator = UntestedPredicatesTy::const_iterator; 51 52 protected: 53 /// A name for the matchable. This is primarily for debugging. 54 StringRef Name; 55 /// Where rules have multiple roots, this is which root we're starting from. 56 unsigned RootIdx; 57 /// Opaque data the caller of the tree building code understands. 58 void *Data; 59 /// Has the decision tree covered every edge traversal? If it hasn't then this 60 /// is an unrecoverable error indicating there's something wrong with the 61 /// partitioners. 62 bool IsFullyTraversed; 63 /// Has the decision tree covered every predicate test? If it has, then 64 /// subsequent matchables on the same leaf are unreachable. If it hasn't, the 65 /// code that requested the GIMatchTree is responsible for finishing off any 66 /// remaining predicates. 67 bool IsFullyTested; 68 /// The variable bindings associated with this leaf so far. 69 std::vector<GIMatchTreeVariableBinding> VarBindings; 70 /// Any predicates left untested by the time we reach this leaf. 71 UntestedPredicatesTy UntestedPredicates; 72 73 public: GIMatchTreeLeafInfo()74 GIMatchTreeLeafInfo() { llvm_unreachable("Cannot default-construct"); } GIMatchTreeLeafInfo(StringRef Name,unsigned RootIdx,void * Data)75 GIMatchTreeLeafInfo(StringRef Name, unsigned RootIdx, void *Data) 76 : Name(Name), RootIdx(RootIdx), Data(Data), IsFullyTraversed(false), 77 IsFullyTested(false) {} 78 getName()79 StringRef getName() const { return Name; } getRootIdx()80 unsigned getRootIdx() const { return RootIdx; } getTargetData()81 template <class Ty> Ty *getTargetData() const { 82 return static_cast<Ty *>(Data); 83 } isFullyTraversed()84 bool isFullyTraversed() const { return IsFullyTraversed; } setIsFullyTraversed(bool V)85 void setIsFullyTraversed(bool V) { IsFullyTraversed = V; } isFullyTested()86 bool isFullyTested() const { return IsFullyTested; } setIsFullyTested(bool V)87 void setIsFullyTested(bool V) { IsFullyTested = V; } 88 bindInstrVariable(StringRef Name,unsigned InstrID)89 void bindInstrVariable(StringRef Name, unsigned InstrID) { 90 VarBindings.emplace_back(Name, InstrID); 91 } bindOperandVariable(StringRef Name,unsigned InstrID,unsigned OpIdx)92 void bindOperandVariable(StringRef Name, unsigned InstrID, unsigned OpIdx) { 93 VarBindings.emplace_back(Name, InstrID, OpIdx); 94 } 95 var_bindings_begin()96 const_var_binding_iterator var_bindings_begin() const { 97 return VarBindings.begin(); 98 } var_bindings_end()99 const_var_binding_iterator var_bindings_end() const { 100 return VarBindings.end(); 101 } var_bindings()102 iterator_range<const_var_binding_iterator> var_bindings() const { 103 return make_range(VarBindings.begin(), VarBindings.end()); 104 } untested_predicates()105 iterator_range<const_untested_predicates_iterator> untested_predicates() const { 106 return make_range(UntestedPredicates.begin(), UntestedPredicates.end()); 107 } addUntestedPredicate(const GIMatchDagPredicate * P)108 void addUntestedPredicate(const GIMatchDagPredicate *P) { 109 UntestedPredicates.push_back(P); 110 } 111 }; 112 113 /// The nodes of a decision tree used to perform the match. 114 /// This will be used to generate the C++ code or state machine equivalent. 115 /// 116 /// It should be noted that some nodes of this tree (most notably nodes handling 117 /// def -> use edges) will need to iterate over several possible matches. As 118 /// such, code generated from this will sometimes need to support backtracking. 119 class GIMatchTree { 120 using LeafVector = std::vector<GIMatchTreeLeafInfo>; 121 122 /// The partitioner that has been chosen for this node. This may be nullptr if 123 /// a partitioner hasn't been chosen yet or if the node is a leaf. 124 std::unique_ptr<GIMatchTreePartitioner> Partitioner; 125 /// All the leaves that are possible for this node of the tree. 126 /// Note: This should be emptied after the tree is built when there are 127 /// children but this currently isn't done to aid debuggability of the DOT 128 /// graph for the decision tree. 129 LeafVector PossibleLeaves; 130 /// The children of this node. The index into this array must match the index 131 /// chosen by the partitioner. 132 std::vector<GIMatchTree> Children; 133 134 void writeDOTGraphNode(raw_ostream &OS) const; 135 void writeDOTGraphEdges(raw_ostream &OS) const; 136 137 public: 138 void writeDOTGraph(raw_ostream &OS) const; 139 setNumChildren(unsigned Num)140 void setNumChildren(unsigned Num) { Children.resize(Num); } addPossibleLeaf(const GIMatchTreeLeafInfo & V,bool IsFullyTraversed,bool IsFullyTested)141 void addPossibleLeaf(const GIMatchTreeLeafInfo &V, bool IsFullyTraversed, 142 bool IsFullyTested) { 143 PossibleLeaves.push_back(V); 144 PossibleLeaves.back().setIsFullyTraversed(IsFullyTraversed); 145 PossibleLeaves.back().setIsFullyTested(IsFullyTested); 146 } dropLeavesAfter(size_t Length)147 void dropLeavesAfter(size_t Length) { 148 if (PossibleLeaves.size() > Length) 149 PossibleLeaves.resize(Length); 150 } setPartitioner(std::unique_ptr<GIMatchTreePartitioner> && V)151 void setPartitioner(std::unique_ptr<GIMatchTreePartitioner> &&V) { 152 Partitioner = std::move(V); 153 } getPartitioner()154 GIMatchTreePartitioner *getPartitioner() const { return Partitioner.get(); } 155 children_begin()156 std::vector<GIMatchTree>::iterator children_begin() { 157 return Children.begin(); 158 } children_end()159 std::vector<GIMatchTree>::iterator children_end() { return Children.end(); } children()160 iterator_range<std::vector<GIMatchTree>::iterator> children() { 161 return make_range(children_begin(), children_end()); 162 } children_begin()163 std::vector<GIMatchTree>::const_iterator children_begin() const { 164 return Children.begin(); 165 } children_end()166 std::vector<GIMatchTree>::const_iterator children_end() const { 167 return Children.end(); 168 } children()169 iterator_range<std::vector<GIMatchTree>::const_iterator> children() const { 170 return make_range(children_begin(), children_end()); 171 } 172 possible_leaves_begin()173 LeafVector::const_iterator possible_leaves_begin() const { 174 return PossibleLeaves.begin(); 175 } possible_leaves_end()176 LeafVector::const_iterator possible_leaves_end() const { 177 return PossibleLeaves.end(); 178 } 179 iterator_range<LeafVector::const_iterator> possible_leaves()180 possible_leaves() const { 181 return make_range(possible_leaves_begin(), possible_leaves_end()); 182 } possible_leaves_begin()183 LeafVector::iterator possible_leaves_begin() { 184 return PossibleLeaves.begin(); 185 } possible_leaves_end()186 LeafVector::iterator possible_leaves_end() { 187 return PossibleLeaves.end(); 188 } possible_leaves()189 iterator_range<LeafVector::iterator> possible_leaves() { 190 return make_range(possible_leaves_begin(), possible_leaves_end()); 191 } 192 }; 193 194 /// Record information that is known about the instruction bound to this ID and 195 /// GIMatchDagInstrNode. Every rule gets its own set of 196 /// GIMatchTreeInstrInfo to bind the shared IDs to an instr node in its 197 /// DAG. 198 /// 199 /// For example, if we know that there are 3 operands. We can record it here to 200 /// elide duplicate checks. 201 class GIMatchTreeInstrInfo { 202 /// The instruction ID for the matched instruction. 203 unsigned ID; 204 /// The corresponding instruction node in the MatchDAG. 205 const GIMatchDagInstr *InstrNode; 206 207 public: GIMatchTreeInstrInfo(unsigned ID,const GIMatchDagInstr * InstrNode)208 GIMatchTreeInstrInfo(unsigned ID, const GIMatchDagInstr *InstrNode) 209 : ID(ID), InstrNode(InstrNode) {} 210 getID()211 unsigned getID() const { return ID; } getInstrNode()212 const GIMatchDagInstr *getInstrNode() const { return InstrNode; } 213 }; 214 215 /// Record information that is known about the operand bound to this ID, OpIdx, 216 /// and GIMatchDagInstrNode. Every rule gets its own set of 217 /// GIMatchTreeOperandInfo to bind the shared IDs to an operand of an 218 /// instr node from its DAG. 219 /// 220 /// For example, if we know that there the operand is a register. We can record 221 /// it here to elide duplicate checks. 222 class GIMatchTreeOperandInfo { 223 /// The corresponding instruction node in the MatchDAG that the operand 224 /// belongs to. 225 const GIMatchDagInstr *InstrNode; 226 unsigned OpIdx; 227 228 public: GIMatchTreeOperandInfo(const GIMatchDagInstr * InstrNode,unsigned OpIdx)229 GIMatchTreeOperandInfo(const GIMatchDagInstr *InstrNode, unsigned OpIdx) 230 : InstrNode(InstrNode), OpIdx(OpIdx) {} 231 getInstrNode()232 const GIMatchDagInstr *getInstrNode() const { return InstrNode; } getOpIdx()233 unsigned getOpIdx() const { return OpIdx; } 234 }; 235 236 /// Represent a leaf of the match tree and any working data we need to build the 237 /// tree. 238 /// 239 /// It's important to note that each rule can have multiple 240 /// GIMatchTreeBuilderLeafInfo's since the partitioners do not always partition 241 /// into mutually-exclusive partitions. For example: 242 /// R1: (FOO ..., ...) 243 /// R2: (oneof(FOO, BAR) ..., ...) 244 /// will partition by opcode into two partitions FOO=>[R1, R2], and BAR=>[R2] 245 /// 246 /// As an optimization, all instructions, edges, and predicates in the DAGs are 247 /// numbered and tracked in BitVectors. As such, the GIMatchDAG must not be 248 /// modified once construction of the tree has begun. 249 class GIMatchTreeBuilderLeafInfo { 250 protected: 251 GIMatchTreeBuilder &Builder; 252 GIMatchTreeLeafInfo Info; 253 const GIMatchDag &MatchDag; 254 /// The association between GIMatchDagInstr* and GIMatchTreeInstrInfo. 255 /// The primary reason for this members existence is to allow the use of 256 /// InstrIDToInfo.lookup() since that requires that the value is 257 /// default-constructible. 258 DenseMap<const GIMatchDagInstr *, GIMatchTreeInstrInfo> InstrNodeToInfo; 259 /// The instruction information for a given ID in the context of this 260 /// particular leaf. 261 DenseMap<unsigned, GIMatchTreeInstrInfo *> InstrIDToInfo; 262 /// The operand information for a given ID and OpIdx in the context of this 263 /// particular leaf. 264 DenseMap<std::pair<unsigned, unsigned>, GIMatchTreeOperandInfo> 265 OperandIDToInfo; 266 267 public: 268 /// The remaining instrs/edges/predicates to visit 269 BitVector RemainingInstrNodes; 270 BitVector RemainingEdges; 271 BitVector RemainingPredicates; 272 273 // The remaining predicate dependencies for each predicate 274 std::vector<BitVector> UnsatisfiedPredDepsForPred; 275 276 /// The edges/predicates we can visit as a result of the declare*() calls we 277 /// have already made. We don't need an instrs version since edges imply the 278 /// instr. 279 BitVector TraversableEdges; 280 BitVector TestablePredicates; 281 282 /// Map predicates from the DAG to their position in the DAG predicate 283 /// iterators. 284 DenseMap<GIMatchDagPredicate *, unsigned> PredicateIDs; 285 /// Map predicate dependency edges from the DAG to their position in the DAG 286 /// predicate dependency iterators. 287 DenseMap<GIMatchDagPredicateDependencyEdge *, unsigned> PredicateDepIDs; 288 289 public: 290 GIMatchTreeBuilderLeafInfo(GIMatchTreeBuilder &Builder, StringRef Name, 291 unsigned RootIdx, const GIMatchDag &MatchDag, 292 void *Data); 293 getName()294 StringRef getName() const { return Info.getName(); } getInfo()295 GIMatchTreeLeafInfo &getInfo() { return Info; } getInfo()296 const GIMatchTreeLeafInfo &getInfo() const { return Info; } getMatchDag()297 const GIMatchDag &getMatchDag() const { return MatchDag; } getRootIdx()298 unsigned getRootIdx() const { return Info.getRootIdx(); } 299 300 /// Has this DAG been fully traversed. This must be true by the time the tree 301 /// builder finishes. isFullyTraversed()302 bool isFullyTraversed() const { 303 // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates 304 // can't be all-zero without satisfying all the dependencies. The same is 305 // almost true for Edges and Instrs but it's possible to have Instrs without 306 // Edges. 307 return RemainingInstrNodes.none() && RemainingEdges.none(); 308 } 309 310 /// Has this DAG been fully tested. This hould be true by the time the tree 311 /// builder finishes but clients can finish any untested predicates left over 312 /// if it's not true. isFullyTested()313 bool isFullyTested() const { 314 // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates 315 // can't be all-zero without satisfying all the dependencies. The same is 316 // almost true for Edges and Instrs but it's possible to have Instrs without 317 // Edges. 318 return RemainingInstrNodes.none() && RemainingEdges.none() && 319 RemainingPredicates.none(); 320 } 321 getInstr(unsigned Idx)322 const GIMatchDagInstr *getInstr(unsigned Idx) const { 323 return *(MatchDag.instr_nodes_begin() + Idx); 324 } getEdge(unsigned Idx)325 const GIMatchDagEdge *getEdge(unsigned Idx) const { 326 return *(MatchDag.edges_begin() + Idx); 327 } getEdge(unsigned Idx)328 GIMatchDagEdge *getEdge(unsigned Idx) { 329 return *(MatchDag.edges_begin() + Idx); 330 } getPredicate(unsigned Idx)331 const GIMatchDagPredicate *getPredicate(unsigned Idx) const { 332 return *(MatchDag.predicates_begin() + Idx); 333 } 334 iterator_range<llvm::BitVector::const_set_bits_iterator> untested_instrs()335 untested_instrs() const { 336 return RemainingInstrNodes.set_bits(); 337 } 338 iterator_range<llvm::BitVector::const_set_bits_iterator> untested_edges()339 untested_edges() const { 340 return RemainingEdges.set_bits(); 341 } 342 iterator_range<llvm::BitVector::const_set_bits_iterator> untested_predicates()343 untested_predicates() const { 344 return RemainingPredicates.set_bits(); 345 } 346 347 /// Bind an instr node to the given ID and clear any blocking dependencies 348 /// that were waiting for it. 349 void declareInstr(const GIMatchDagInstr *Instr, unsigned ID); 350 351 /// Bind an operand to the given ID and OpIdx and clear any blocking 352 /// dependencies that were waiting for it. 353 void declareOperand(unsigned InstrID, unsigned OpIdx); 354 getInstrInfo(unsigned ID)355 GIMatchTreeInstrInfo *getInstrInfo(unsigned ID) const { 356 auto I = InstrIDToInfo.find(ID); 357 if (I != InstrIDToInfo.end()) 358 return I->second; 359 return nullptr; 360 } 361 dump(raw_ostream & OS)362 void dump(raw_ostream &OS) const { 363 OS << "Leaf " << getName() << " for root #" << getRootIdx() << "\n"; 364 MatchDag.print(OS); 365 for (const auto &I : InstrIDToInfo) 366 OS << "Declared Instr #" << I.first << "\n"; 367 for (const auto &I : OperandIDToInfo) 368 OS << "Declared Instr #" << I.first.first << ", Op #" << I.first.second 369 << "\n"; 370 OS << RemainingInstrNodes.count() << " untested instrs of " 371 << RemainingInstrNodes.size() << "\n"; 372 OS << RemainingEdges.count() << " untested edges of " 373 << RemainingEdges.size() << "\n"; 374 OS << RemainingPredicates.count() << " untested predicates of " 375 << RemainingPredicates.size() << "\n"; 376 377 OS << TraversableEdges.count() << " edges could be traversed\n"; 378 OS << TestablePredicates.count() << " predicates could be tested\n"; 379 } 380 }; 381 382 /// The tree builder has a fairly tough job. It's purpose is to merge all the 383 /// DAGs from the ruleset into a decision tree that walks all of them 384 /// simultaneously and identifies the rule that was matched. In addition to 385 /// that, it also needs to find the most efficient order to make decisions 386 /// without violating any dependencies and ensure that every DAG covers every 387 /// instr/edge/predicate. 388 class GIMatchTreeBuilder { 389 public: 390 using LeafVec = std::vector<GIMatchTreeBuilderLeafInfo>; 391 392 protected: 393 /// The leaves that the resulting decision tree will distinguish. 394 LeafVec Leaves; 395 /// The tree node being constructed. 396 GIMatchTree *TreeNode; 397 /// The builders for each subtree resulting from the current decision. 398 std::vector<GIMatchTreeBuilder> SubtreeBuilders; 399 /// The possible partitioners we could apply right now. 400 std::vector<std::unique_ptr<GIMatchTreePartitioner>> Partitioners; 401 /// The next instruction ID to allocate when requested by the chosen 402 /// Partitioner. 403 unsigned NextInstrID; 404 405 /// Use any context we have stored to cull partitioners that only test things 406 /// we already know. At the time of writing, there's no need to do anything 407 /// here but it will become important once, for example, there is a 408 /// num-operands and an opcode partitioner. This is because applying an opcode 409 /// partitioner (usually) makes the number of operands known which makes 410 /// additional checking pointless. 411 void filterRedundantPartitioners(); 412 413 /// Evaluate the available partioners and select the best one at the moment. 414 void evaluatePartitioners(); 415 416 /// Construct the current tree node. 417 void runStep(); 418 419 public: GIMatchTreeBuilder(unsigned NextInstrID)420 GIMatchTreeBuilder(unsigned NextInstrID) : NextInstrID(NextInstrID) {} GIMatchTreeBuilder(GIMatchTree * TreeNode,unsigned NextInstrID)421 GIMatchTreeBuilder(GIMatchTree *TreeNode, unsigned NextInstrID) 422 : TreeNode(TreeNode), NextInstrID(NextInstrID) {} 423 addLeaf(StringRef Name,unsigned RootIdx,const GIMatchDag & MatchDag,void * Data)424 void addLeaf(StringRef Name, unsigned RootIdx, const GIMatchDag &MatchDag, 425 void *Data) { 426 Leaves.emplace_back(*this, Name, RootIdx, MatchDag, Data); 427 } addLeaf(const GIMatchTreeBuilderLeafInfo & L)428 void addLeaf(const GIMatchTreeBuilderLeafInfo &L) { Leaves.push_back(L); } addPartitioner(std::unique_ptr<GIMatchTreePartitioner> P)429 void addPartitioner(std::unique_ptr<GIMatchTreePartitioner> P) { 430 Partitioners.push_back(std::move(P)); 431 } 432 void addPartitionersForInstr(unsigned InstrIdx); 433 void addPartitionersForOperand(unsigned InstrID, unsigned OpIdx); 434 getPossibleLeaves()435 LeafVec &getPossibleLeaves() { return Leaves; } 436 allocInstrID()437 unsigned allocInstrID() { return NextInstrID++; } 438 439 /// Construct the decision tree. 440 std::unique_ptr<GIMatchTree> run(); 441 }; 442 443 /// Partitioners are the core of the tree builder and are unfortunately rather 444 /// tricky to write. 445 class GIMatchTreePartitioner { 446 protected: 447 /// The partitions resulting from applying the partitioner to the possible 448 /// leaves. The keys must be consecutive integers starting from 0. This can 449 /// lead to some unfortunate situations where partitioners test a predicate 450 /// and use 0 for success and 1 for failure if the ruleset encounters a 451 /// success case first but is necessary to assign the partition to one of the 452 /// tree nodes children. As a result, you usually need some kind of 453 /// indirection to map the natural keys (e.g. ptrs/bools) to this linear 454 /// sequence. The values are a bitvector indicating which leaves belong to 455 /// this partition. 456 DenseMap<unsigned, BitVector> Partitions; 457 458 public: ~GIMatchTreePartitioner()459 virtual ~GIMatchTreePartitioner() {} 460 virtual std::unique_ptr<GIMatchTreePartitioner> clone() const = 0; 461 462 /// Determines which partitions the given leaves belong to. A leaf may belong 463 /// to multiple partitions in which case it will be duplicated during 464 /// applyForPartition(). 465 /// 466 /// This function can be rather complicated. A few particular things to be 467 /// aware of include: 468 /// * One leaf can be assigned to multiple partitions when there's some 469 /// ambiguity. 470 /// * Not all DAG's for the leaves may be able to perform the test. For 471 /// example, the opcode partitiioner must account for one DAG being a 472 /// superset of another such as [(ADD ..., ..., ...)], and [(MUL t, ..., 473 /// ...), (ADD ..., t, ...)] 474 /// * Attaching meaning to a particular partition index will generally not 475 /// work due to the '0, 1, ..., n' requirement. You might encounter cases 476 /// where only partition 1 is seen, leaving a missing 0. 477 /// * Finding a specific predicate such as the opcode predicate for a specific 478 /// instruction is non-trivial. It's often O(NumPredicates), leading to 479 /// O(NumPredicates*NumRules) when applied to the whole ruleset. The good 480 /// news there is that n is typically small thanks to predicate dependencies 481 /// limiting how many are testable at once. Also, with opcode and type 482 /// predicates being so frequent the value of m drops very fast too. It 483 /// wouldn't be terribly surprising to see a 10k ruleset drop down to an 484 /// average of 100 leaves per partition after a single opcode partitioner. 485 /// * The same goes for finding specific edges. The need to traverse them in 486 /// dependency order dramatically limits the search space at any given 487 /// moment. 488 /// * If you need to add a leaf to all partitions, make sure you don't forget 489 /// them when adding partitions later. 490 virtual void repartition(GIMatchTreeBuilder::LeafVec &Leaves) = 0; 491 492 /// Delegate the leaves for a given partition to the corresponding subbuilder, 493 /// update any recorded context for this partition (e.g. allocate instr id's 494 /// for instrs recorder by the current node), and clear any blocking 495 /// dependencies this partitioner resolved. 496 virtual void applyForPartition(unsigned PartitionIdx, 497 GIMatchTreeBuilder &Builder, 498 GIMatchTreeBuilder &SubBuilder) = 0; 499 500 /// Return a BitVector indicating which leaves should be transferred to the 501 /// specified partition. Note that the same leaf can be indicated for multiple 502 /// partitions. getPossibleLeavesForPartition(unsigned Idx)503 BitVector getPossibleLeavesForPartition(unsigned Idx) { 504 const auto &I = Partitions.find(Idx); 505 assert(I != Partitions.end() && "Requested non-existant partition"); 506 return I->second; 507 } 508 getNumPartitions()509 size_t getNumPartitions() const { return Partitions.size(); } getNumLeavesWithDupes()510 size_t getNumLeavesWithDupes() const { 511 size_t S = 0; 512 for (const auto &P : Partitions) 513 S += P.second.size(); 514 return S; 515 } 516 517 /// Emit a brief description of the partitioner suitable for debug printing or 518 /// use in a DOT graph. 519 virtual void emitDescription(raw_ostream &OS) const = 0; 520 /// Emit a label for the given partition suitable for debug printing or use in 521 /// a DOT graph. 522 virtual void emitPartitionName(raw_ostream &OS, unsigned Idx) const = 0; 523 524 /// Emit a long description of how the partitioner partitions the leaves. 525 virtual void emitPartitionResults(raw_ostream &OS) const = 0; 526 527 /// Generate code to select between partitions based on the MIR being matched. 528 /// This is typically a switch statement that picks a partition index. 529 virtual void generatePartitionSelectorCode(raw_ostream &OS, 530 StringRef Indent) const = 0; 531 }; 532 533 /// Partition according to the opcode of the instruction. 534 /// 535 /// Numbers CodeGenInstr ptrs for use as partition ID's. One special partition, 536 /// nullptr, represents the case where the instruction isn't known. 537 /// 538 /// * If the opcode can be tested and is a single opcode, create the partition 539 /// for that opcode and assign the leaf to it. This partition no longer needs 540 /// to test the opcode, and many details about the instruction will usually 541 /// become known (e.g. number of operands for non-variadic instrs) via the 542 /// CodeGenInstr ptr. 543 /// * (not implemented yet) If the opcode can be tested and is a choice of 544 /// opcodes, then the leaf can be treated like the single-opcode case but must 545 /// be added to all relevant partitions and not quite as much becomes known as 546 /// a result. That said, multiple-choice opcodes are likely similar enough 547 /// (because if they aren't then handling them together makes little sense) 548 /// that plenty still becomes known. The main implementation issue with this 549 /// is having a description to represent the commonality between instructions. 550 /// * If the opcode is not tested, the leaf must be added to all partitions 551 /// including the wildcard nullptr partition. What becomes known as a result 552 /// varies between partitions. 553 /// * If the instruction to be tested is not declared then add the leaf to all 554 /// partitions. This occurs when we encounter one rule that is a superset of 555 /// the other and we are still matching the remainder of the superset. The 556 /// result is that the cases that don't match the superset will match the 557 /// subset rule, while the ones that do match the superset will match either 558 /// (which one is algorithm dependent but will usually be the superset). 559 class GIMatchTreeOpcodePartitioner : public GIMatchTreePartitioner { 560 unsigned InstrID; 561 DenseMap<const CodeGenInstruction *, unsigned> InstrToPartition; 562 std::vector<const CodeGenInstruction *> PartitionToInstr; 563 std::vector<BitVector> TestedPredicates; 564 565 public: GIMatchTreeOpcodePartitioner(unsigned InstrID)566 GIMatchTreeOpcodePartitioner(unsigned InstrID) : InstrID(InstrID) {} 567 clone()568 std::unique_ptr<GIMatchTreePartitioner> clone() const override { 569 return std::make_unique<GIMatchTreeOpcodePartitioner>(*this); 570 } 571 emitDescription(raw_ostream & OS)572 void emitDescription(raw_ostream &OS) const override { 573 OS << "MI[" << InstrID << "].getOpcode()"; 574 } 575 576 void emitPartitionName(raw_ostream &OS, unsigned Idx) const override; 577 578 void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override; 579 void applyForPartition(unsigned Idx, GIMatchTreeBuilder &SubBuilder, 580 GIMatchTreeBuilder &Builder) override; 581 582 void emitPartitionResults(raw_ostream &OS) const override; 583 584 void generatePartitionSelectorCode(raw_ostream &OS, 585 StringRef Indent) const override; 586 }; 587 588 class GIMatchTreeVRegDefPartitioner : public GIMatchTreePartitioner { 589 unsigned NewInstrID = -1; 590 unsigned InstrID; 591 unsigned OpIdx; 592 std::vector<BitVector> TraversedEdges; 593 DenseMap<unsigned, unsigned> ResultToPartition; 594 std::vector<bool> PartitionToResult; 595 596 void addToPartition(bool Result, unsigned LeafIdx); 597 598 public: GIMatchTreeVRegDefPartitioner(unsigned InstrID,unsigned OpIdx)599 GIMatchTreeVRegDefPartitioner(unsigned InstrID, unsigned OpIdx) 600 : InstrID(InstrID), OpIdx(OpIdx) {} 601 clone()602 std::unique_ptr<GIMatchTreePartitioner> clone() const override { 603 return std::make_unique<GIMatchTreeVRegDefPartitioner>(*this); 604 } 605 emitDescription(raw_ostream & OS)606 void emitDescription(raw_ostream &OS) const override { 607 OS << "MI[" << NewInstrID << "] = getVRegDef(MI[" << InstrID 608 << "].getOperand(" << OpIdx << "))"; 609 } 610 emitPartitionName(raw_ostream & OS,unsigned Idx)611 void emitPartitionName(raw_ostream &OS, unsigned Idx) const override { 612 bool Result = PartitionToResult[Idx]; 613 if (Result) 614 OS << "true"; 615 else 616 OS << "false"; 617 } 618 619 void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override; 620 void applyForPartition(unsigned PartitionIdx, GIMatchTreeBuilder &Builder, 621 GIMatchTreeBuilder &SubBuilder) override; 622 void emitPartitionResults(raw_ostream &OS) const override; 623 624 void generatePartitionSelectorCode(raw_ostream &OS, 625 StringRef Indent) const override; 626 }; 627 628 } // end namespace llvm 629 #endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H 630