1 //===- GIMatchTree.h - A decision tree to match GIMatchDag's --------------===//
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
7 //===----------------------------------------------------------------------===//
9 #ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H
10 #define LLVM_UTILS_TABLEGEN_GIMATCHTREE_H
12 #include "GIMatchDag.h"
13 #include "llvm/ADT/BitVector.h"
18 class GIMatchTreeBuilder;
19 class GIMatchTreePartitioner;
21 /// Describes the binding of a variable to the matched MIR
22 class GIMatchTreeVariableBinding {
23 /// The name of the variable described by this binding.
25 // The matched instruction it is bound to.
27 // The matched operand (if appropriate) it is bound to.
28 Optional<unsigned> OpIdx;
31 GIMatchTreeVariableBinding(StringRef Name, unsigned InstrID,
32 Optional<unsigned> OpIdx = None)
33 : Name(Name), InstrID(InstrID), OpIdx(OpIdx) {}
35 bool isInstr() const { return !OpIdx.hasValue(); }
36 StringRef getName() const { return Name; }
37 unsigned getInstrID() const { return InstrID; }
38 unsigned getOpIdx() const {
39 assert(OpIdx.hasValue() && "Is not an operand binding");
44 /// Associates a matchable with a leaf of the decision tree.
45 class GIMatchTreeLeafInfo {
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;
53 /// A name for the matchable. This is primarily for debugging.
55 /// Where rules have multiple roots, this is which root we're starting from.
57 /// Opaque data the caller of the tree building code understands.
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
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.
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;
74 GIMatchTreeLeafInfo() { llvm_unreachable("Cannot default-construct"); }
75 GIMatchTreeLeafInfo(StringRef Name, unsigned RootIdx, void *Data)
76 : Name(Name), RootIdx(RootIdx), Data(Data), IsFullyTraversed(false),
77 IsFullyTested(false) {}
79 StringRef getName() const { return Name; }
80 unsigned getRootIdx() const { return RootIdx; }
81 template <class Ty> Ty *getTargetData() const {
82 return static_cast<Ty *>(Data);
84 bool isFullyTraversed() const { return IsFullyTraversed; }
85 void setIsFullyTraversed(bool V) { IsFullyTraversed = V; }
86 bool isFullyTested() const { return IsFullyTested; }
87 void setIsFullyTested(bool V) { IsFullyTested = V; }
89 void bindInstrVariable(StringRef Name, unsigned InstrID) {
90 VarBindings.emplace_back(Name, InstrID);
92 void bindOperandVariable(StringRef Name, unsigned InstrID, unsigned OpIdx) {
93 VarBindings.emplace_back(Name, InstrID, OpIdx);
96 const_var_binding_iterator var_bindings_begin() const {
97 return VarBindings.begin();
99 const_var_binding_iterator var_bindings_end() const {
100 return VarBindings.end();
102 iterator_range<const_var_binding_iterator> var_bindings() const {
103 return make_range(VarBindings.begin(), VarBindings.end());
105 iterator_range<const_untested_predicates_iterator> untested_predicates() const {
106 return make_range(UntestedPredicates.begin(), UntestedPredicates.end());
108 void addUntestedPredicate(const GIMatchDagPredicate *P) {
109 UntestedPredicates.push_back(P);
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.
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.
120 using LeafVector = std::vector<GIMatchTreeLeafInfo>;
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;
134 void writeDOTGraphNode(raw_ostream &OS) const;
135 void writeDOTGraphEdges(raw_ostream &OS) const;
138 void writeDOTGraph(raw_ostream &OS) const;
140 void setNumChildren(unsigned Num) { Children.resize(Num); }
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);
147 void dropLeavesAfter(size_t Length) {
148 if (PossibleLeaves.size() > Length)
149 PossibleLeaves.resize(Length);
151 void setPartitioner(std::unique_ptr<GIMatchTreePartitioner> &&V) {
152 Partitioner = std::move(V);
154 GIMatchTreePartitioner *getPartitioner() const { return Partitioner.get(); }
156 std::vector<GIMatchTree>::iterator children_begin() {
157 return Children.begin();
159 std::vector<GIMatchTree>::iterator children_end() { return Children.end(); }
160 iterator_range<std::vector<GIMatchTree>::iterator> children() {
161 return make_range(children_begin(), children_end());
163 std::vector<GIMatchTree>::const_iterator children_begin() const {
164 return Children.begin();
166 std::vector<GIMatchTree>::const_iterator children_end() const {
167 return Children.end();
169 iterator_range<std::vector<GIMatchTree>::const_iterator> children() const {
170 return make_range(children_begin(), children_end());
173 LeafVector::const_iterator possible_leaves_begin() const {
174 return PossibleLeaves.begin();
176 LeafVector::const_iterator possible_leaves_end() const {
177 return PossibleLeaves.end();
179 iterator_range<LeafVector::const_iterator>
180 possible_leaves() const {
181 return make_range(possible_leaves_begin(), possible_leaves_end());
183 LeafVector::iterator possible_leaves_begin() {
184 return PossibleLeaves.begin();
186 LeafVector::iterator possible_leaves_end() {
187 return PossibleLeaves.end();
189 iterator_range<LeafVector::iterator> possible_leaves() {
190 return make_range(possible_leaves_begin(), possible_leaves_end());
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
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.
204 /// The corresponding instruction node in the MatchDAG.
205 const GIMatchDagInstr *InstrNode;
208 GIMatchTreeInstrInfo(unsigned ID, const GIMatchDagInstr *InstrNode)
209 : ID(ID), InstrNode(InstrNode) {}
211 unsigned getID() const { return ID; }
212 const GIMatchDagInstr *getInstrNode() const { return InstrNode; }
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.
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
225 const GIMatchDagInstr *InstrNode;
229 GIMatchTreeOperandInfo(const GIMatchDagInstr *InstrNode, unsigned OpIdx)
230 : InstrNode(InstrNode), OpIdx(OpIdx) {}
232 const GIMatchDagInstr *getInstrNode() const { return InstrNode; }
233 unsigned getOpIdx() const { return OpIdx; }
236 /// Represent a leaf of the match tree and any working data we need to build the
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]
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 {
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
261 DenseMap<unsigned, GIMatchTreeInstrInfo *> InstrIDToInfo;
262 /// The operand information for a given ID and OpIdx in the context of this
264 DenseMap<std::pair<unsigned, unsigned>, GIMatchTreeOperandInfo>
268 /// The remaining instrs/edges/predicates to visit
269 BitVector RemainingInstrNodes;
270 BitVector RemainingEdges;
271 BitVector RemainingPredicates;
273 // The remaining predicate dependencies for each predicate
274 std::vector<BitVector> UnsatisfiedPredDepsForPred;
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
279 BitVector TraversableEdges;
280 BitVector TestablePredicates;
282 /// Map predicates from the DAG to their position in the DAG predicate
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;
290 GIMatchTreeBuilderLeafInfo(GIMatchTreeBuilder &Builder, StringRef Name,
291 unsigned RootIdx, const GIMatchDag &MatchDag,
294 StringRef getName() const { return Info.getName(); }
295 GIMatchTreeLeafInfo &getInfo() { return Info; }
296 const GIMatchTreeLeafInfo &getInfo() const { return Info; }
297 const GIMatchDag &getMatchDag() const { return MatchDag; }
298 unsigned getRootIdx() const { return Info.getRootIdx(); }
300 /// Has this DAG been fully traversed. This must be true by the time the tree
301 /// builder finishes.
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
307 return RemainingInstrNodes.none() && RemainingEdges.none();
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.
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
318 return RemainingInstrNodes.none() && RemainingEdges.none() &&
319 RemainingPredicates.none();
322 const GIMatchDagInstr *getInstr(unsigned Idx) const {
323 return *(MatchDag.instr_nodes_begin() + Idx);
325 const GIMatchDagEdge *getEdge(unsigned Idx) const {
326 return *(MatchDag.edges_begin() + Idx);
328 GIMatchDagEdge *getEdge(unsigned Idx) {
329 return *(MatchDag.edges_begin() + Idx);
331 const GIMatchDagPredicate *getPredicate(unsigned Idx) const {
332 return *(MatchDag.predicates_begin() + Idx);
334 iterator_range<llvm::BitVector::const_set_bits_iterator>
335 untested_instrs() const {
336 return RemainingInstrNodes.set_bits();
338 iterator_range<llvm::BitVector::const_set_bits_iterator>
339 untested_edges() const {
340 return RemainingEdges.set_bits();
342 iterator_range<llvm::BitVector::const_set_bits_iterator>
343 untested_predicates() const {
344 return RemainingPredicates.set_bits();
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);
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);
355 GIMatchTreeInstrInfo *getInstrInfo(unsigned ID) const {
356 auto I = InstrIDToInfo.find(ID);
357 if (I != InstrIDToInfo.end())
362 void dump(raw_ostream &OS) const {
363 OS << "Leaf " << getName() << " for root #" << getRootIdx() << "\n";
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
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";
377 OS << TraversableEdges.count() << " edges could be traversed\n";
378 OS << TestablePredicates.count() << " predicates could be tested\n";
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 {
390 using LeafVec = std::vector<GIMatchTreeBuilderLeafInfo>;
393 /// The leaves that the resulting decision tree will distinguish.
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
403 unsigned NextInstrID;
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();
413 /// Evaluate the available partioners and select the best one at the moment.
414 void evaluatePartitioners();
416 /// Construct the current tree node.
420 GIMatchTreeBuilder(unsigned NextInstrID) : NextInstrID(NextInstrID) {}
421 GIMatchTreeBuilder(GIMatchTree *TreeNode, unsigned NextInstrID)
422 : TreeNode(TreeNode), NextInstrID(NextInstrID) {}
424 void addLeaf(StringRef Name, unsigned RootIdx, const GIMatchDag &MatchDag,
426 Leaves.emplace_back(*this, Name, RootIdx, MatchDag, Data);
428 void addLeaf(const GIMatchTreeBuilderLeafInfo &L) { Leaves.push_back(L); }
429 void addPartitioner(std::unique_ptr<GIMatchTreePartitioner> P) {
430 Partitioners.push_back(std::move(P));
432 void addPartitionersForInstr(unsigned InstrIdx);
433 void addPartitionersForOperand(unsigned InstrID, unsigned OpIdx);
435 LeafVec &getPossibleLeaves() { return Leaves; }
437 unsigned allocInstrID() { return NextInstrID++; }
439 /// Construct the decision tree.
440 std::unique_ptr<GIMatchTree> run();
443 /// Partitioners are the core of the tree builder and are unfortunately rather
445 class GIMatchTreePartitioner {
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
456 DenseMap<unsigned, BitVector> Partitions;
459 virtual ~GIMatchTreePartitioner() {}
460 virtual std::unique_ptr<GIMatchTreePartitioner> clone() const = 0;
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().
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
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
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;
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;
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
503 BitVector getPossibleLeavesForPartition(unsigned Idx) {
504 const auto &I = Partitions.find(Idx);
505 assert(I != Partitions.end() && "Requested non-existant partition");
509 size_t getNumPartitions() const { return Partitions.size(); }
510 size_t getNumLeavesWithDupes() const {
512 for (const auto &P : Partitions)
513 S += P.second.size();
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
522 virtual void emitPartitionName(raw_ostream &OS, unsigned Idx) const = 0;
524 /// Emit a long description of how the partitioner partitions the leaves.
525 virtual void emitPartitionResults(raw_ostream &OS) const = 0;
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;
533 /// Partition according to the opcode of the instruction.
535 /// Numbers CodeGenInstr ptrs for use as partition ID's. One special partition,
536 /// nullptr, represents the case where the instruction isn't known.
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 {
561 DenseMap<const CodeGenInstruction *, unsigned> InstrToPartition;
562 std::vector<const CodeGenInstruction *> PartitionToInstr;
563 std::vector<BitVector> TestedPredicates;
566 GIMatchTreeOpcodePartitioner(unsigned InstrID) : InstrID(InstrID) {}
568 std::unique_ptr<GIMatchTreePartitioner> clone() const override {
569 return std::make_unique<GIMatchTreeOpcodePartitioner>(*this);
572 void emitDescription(raw_ostream &OS) const override {
573 OS << "MI[" << InstrID << "].getOpcode()";
576 void emitPartitionName(raw_ostream &OS, unsigned Idx) const override;
578 void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override;
579 void applyForPartition(unsigned Idx, GIMatchTreeBuilder &SubBuilder,
580 GIMatchTreeBuilder &Builder) override;
582 void emitPartitionResults(raw_ostream &OS) const override;
584 void generatePartitionSelectorCode(raw_ostream &OS,
585 StringRef Indent) const override;
588 class GIMatchTreeVRegDefPartitioner : public GIMatchTreePartitioner {
589 unsigned NewInstrID = -1;
592 std::vector<BitVector> TraversedEdges;
593 DenseMap<unsigned, unsigned> ResultToPartition;
594 std::vector<bool> PartitionToResult;
596 void addToPartition(bool Result, unsigned LeafIdx);
599 GIMatchTreeVRegDefPartitioner(unsigned InstrID, unsigned OpIdx)
600 : InstrID(InstrID), OpIdx(OpIdx) {}
602 std::unique_ptr<GIMatchTreePartitioner> clone() const override {
603 return std::make_unique<GIMatchTreeVRegDefPartitioner>(*this);
606 void emitDescription(raw_ostream &OS) const override {
607 OS << "MI[" << NewInstrID << "] = getVRegDef(MI[" << InstrID
608 << "].getOperand(" << OpIdx << "))";
611 void emitPartitionName(raw_ostream &OS, unsigned Idx) const override {
612 bool Result = PartitionToResult[Idx];
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;
624 void generatePartitionSelectorCode(raw_ostream &OS,
625 StringRef Indent) const override;
628 } // end namespace llvm
629 #endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H