YQ Connector: support managed ClickHouse

Со стороны dqrun можно обратиться к инстансу коннектора, который работает на streaming стенде, и извлечь данные из облачного CH.

1 files changed, 626 insertions, 0 deletions

diff --git a/contrib/libs/llvm16/utils/TableGen/GlobalISel/GIMatchTree.h b/contrib/libs/llvm16/utils/TableGen/GlobalISel/GIMatchTree.h
new file mode 100644
index 0000000000..0ce4060fe7
--- /dev/null
+++ b/contrib/libs/llvm16/utils/TableGen/GlobalISel/GIMatchTree.h
@@ -0,0 +1,626 @@
+//===- GIMatchTree.h - A decision tree to match GIMatchDag's --------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHTREE_H
+
+#include "GIMatchDag.h"
+#include "llvm/ADT/BitVector.h"
+
+namespace llvm {
+class raw_ostream;
+
+class GIMatchTreeBuilder;
+class GIMatchTreePartitioner;
+
+/// Describes the binding of a variable to the matched MIR
+class GIMatchTreeVariableBinding {
+  /// The name of the variable described by this binding.
+  StringRef Name;
+  // The matched instruction it is bound to. 
+  unsigned InstrID;
+  // The matched operand (if appropriate) it is bound to.
+  std::optional<unsigned> OpIdx;
+
+public:
+  GIMatchTreeVariableBinding(StringRef Name, unsigned InstrID,
+                             std::optional<unsigned> OpIdx = std::nullopt)
+      : Name(Name), InstrID(InstrID), OpIdx(OpIdx) {}
+
+  bool isInstr() const { return !OpIdx; }
+  StringRef getName() const { return Name; }
+  unsigned getInstrID() const { return InstrID; }
+  unsigned getOpIdx() const {
+    assert(OpIdx && "Is not an operand binding");
+    return *OpIdx;
+  }
+};
+
+/// Associates a matchable with a leaf of the decision tree.
+class GIMatchTreeLeafInfo {
+public:
+  using const_var_binding_iterator =
+      std::vector<GIMatchTreeVariableBinding>::const_iterator;
+  using UntestedPredicatesTy = SmallVector<const GIMatchDagPredicate *, 1>;
+  using const_untested_predicates_iterator = UntestedPredicatesTy::const_iterator;
+
+protected:
+  /// A name for the matchable. This is primarily for debugging.
+  StringRef Name;
+  /// Where rules have multiple roots, this is which root we're starting from.
+  unsigned RootIdx;
+  /// Opaque data the caller of the tree building code understands.
+  void *Data;
+  /// Has the decision tree covered every edge traversal? If it hasn't then this
+  /// is an unrecoverable error indicating there's something wrong with the
+  /// partitioners.
+  bool IsFullyTraversed;
+  /// Has the decision tree covered every predicate test? If it has, then
+  /// subsequent matchables on the same leaf are unreachable. If it hasn't, the
+  /// code that requested the GIMatchTree is responsible for finishing off any
+  /// remaining predicates.
+  bool IsFullyTested;
+  /// The variable bindings associated with this leaf so far.
+  std::vector<GIMatchTreeVariableBinding> VarBindings;
+  /// Any predicates left untested by the time we reach this leaf.
+  UntestedPredicatesTy UntestedPredicates;
+
+public:
+  GIMatchTreeLeafInfo() { llvm_unreachable("Cannot default-construct"); }
+  GIMatchTreeLeafInfo(StringRef Name, unsigned RootIdx, void *Data)
+      : Name(Name), RootIdx(RootIdx), Data(Data), IsFullyTraversed(false),
+        IsFullyTested(false) {}
+
+  StringRef getName() const { return Name; }
+  unsigned getRootIdx() const { return RootIdx; }
+  template <class Ty> Ty *getTargetData() const {
+    return static_cast<Ty *>(Data);
+  }
+  bool isFullyTraversed() const { return IsFullyTraversed; }
+  void setIsFullyTraversed(bool V) { IsFullyTraversed = V; }
+  bool isFullyTested() const { return IsFullyTested; }
+  void setIsFullyTested(bool V) { IsFullyTested = V; }
+
+  void bindInstrVariable(StringRef Name, unsigned InstrID) {
+    VarBindings.emplace_back(Name, InstrID);
+  }
+  void bindOperandVariable(StringRef Name, unsigned InstrID, unsigned OpIdx) {
+    VarBindings.emplace_back(Name, InstrID, OpIdx);
+  }
+
+  const_var_binding_iterator var_bindings_begin() const {
+    return VarBindings.begin();
+  }
+  const_var_binding_iterator var_bindings_end() const {
+    return VarBindings.end();
+  }
+  iterator_range<const_var_binding_iterator> var_bindings() const {
+    return make_range(VarBindings.begin(), VarBindings.end());
+  }
+  iterator_range<const_untested_predicates_iterator> untested_predicates() const {
+    return make_range(UntestedPredicates.begin(), UntestedPredicates.end());
+  }
+  void addUntestedPredicate(const GIMatchDagPredicate *P) {
+    UntestedPredicates.push_back(P);
+  }
+};
+
+/// The nodes of a decision tree used to perform the match.
+/// This will be used to generate the C++ code or state machine equivalent.
+///
+/// It should be noted that some nodes of this tree (most notably nodes handling
+/// def -> use edges) will need to iterate over several possible matches. As
+/// such, code generated from this will sometimes need to support backtracking.
+class GIMatchTree {
+  using LeafVector = std::vector<GIMatchTreeLeafInfo>;
+
+  /// The partitioner that has been chosen for this node. This may be nullptr if
+  /// a partitioner hasn't been chosen yet or if the node is a leaf.
+  std::unique_ptr<GIMatchTreePartitioner> Partitioner;
+  /// All the leaves that are possible for this node of the tree.
+  /// Note: This should be emptied after the tree is built when there are
+  /// children but this currently isn't done to aid debuggability of the DOT
+  /// graph for the decision tree.
+  LeafVector PossibleLeaves;
+  /// The children of this node. The index into this array must match the index
+  /// chosen by the partitioner.
+  std::vector<GIMatchTree> Children;
+
+  void writeDOTGraphNode(raw_ostream &OS) const;
+  void writeDOTGraphEdges(raw_ostream &OS) const;
+
+public:
+  void writeDOTGraph(raw_ostream &OS) const;
+
+  void setNumChildren(unsigned Num) { Children.resize(Num); }
+  void addPossibleLeaf(const GIMatchTreeLeafInfo &V, bool IsFullyTraversed,
+                       bool IsFullyTested) {
+    PossibleLeaves.push_back(V);
+    PossibleLeaves.back().setIsFullyTraversed(IsFullyTraversed);
+    PossibleLeaves.back().setIsFullyTested(IsFullyTested);
+  }
+  void dropLeavesAfter(size_t Length) {
+    if (PossibleLeaves.size() > Length)
+      PossibleLeaves.resize(Length);
+  }
+  void setPartitioner(std::unique_ptr<GIMatchTreePartitioner> &&V) {
+    Partitioner = std::move(V);
+  }
+  GIMatchTreePartitioner *getPartitioner() const { return Partitioner.get(); }
+
+  std::vector<GIMatchTree>::iterator children_begin() {
+    return Children.begin();
+  }
+  std::vector<GIMatchTree>::iterator children_end() { return Children.end(); }
+  iterator_range<std::vector<GIMatchTree>::iterator> children() {
+    return make_range(children_begin(), children_end());
+  }
+  std::vector<GIMatchTree>::const_iterator children_begin() const {
+    return Children.begin();
+  }
+  std::vector<GIMatchTree>::const_iterator children_end() const {
+    return Children.end();
+  }
+  iterator_range<std::vector<GIMatchTree>::const_iterator> children() const {
+    return make_range(children_begin(), children_end());
+  }
+
+  LeafVector::const_iterator possible_leaves_begin() const {
+    return PossibleLeaves.begin();
+  }
+  LeafVector::const_iterator possible_leaves_end() const {
+    return PossibleLeaves.end();
+  }
+  iterator_range<LeafVector::const_iterator>
+  possible_leaves() const {
+    return make_range(possible_leaves_begin(), possible_leaves_end());
+  }
+  LeafVector::iterator possible_leaves_begin() {
+    return PossibleLeaves.begin();
+  }
+  LeafVector::iterator possible_leaves_end() {
+    return PossibleLeaves.end();
+  }
+  iterator_range<LeafVector::iterator> possible_leaves() {
+    return make_range(possible_leaves_begin(), possible_leaves_end());
+  }
+};
+
+/// Record information that is known about the instruction bound to this ID and
+/// GIMatchDagInstrNode. Every rule gets its own set of
+/// GIMatchTreeInstrInfo to bind the shared IDs to an instr node in its
+/// DAG.
+///
+/// For example, if we know that there are 3 operands. We can record it here to
+/// elide duplicate checks.
+class GIMatchTreeInstrInfo {
+  /// The instruction ID for the matched instruction.
+  unsigned ID;
+  /// The corresponding instruction node in the MatchDAG.
+  const GIMatchDagInstr *InstrNode;
+
+public:
+  GIMatchTreeInstrInfo(unsigned ID, const GIMatchDagInstr *InstrNode)
+      : ID(ID), InstrNode(InstrNode) {}
+
+  unsigned getID() const { return ID; }
+  const GIMatchDagInstr *getInstrNode() const { return InstrNode; }
+};
+
+/// Record information that is known about the operand bound to this ID, OpIdx,
+/// and GIMatchDagInstrNode. Every rule gets its own set of
+/// GIMatchTreeOperandInfo to bind the shared IDs to an operand of an
+/// instr node from its DAG.
+///
+/// For example, if we know that there the operand is a register. We can record
+/// it here to elide duplicate checks.
+class GIMatchTreeOperandInfo {
+  /// The corresponding instruction node in the MatchDAG that the operand
+  /// belongs to.
+  const GIMatchDagInstr *InstrNode;
+  unsigned OpIdx;
+
+public:
+  GIMatchTreeOperandInfo(const GIMatchDagInstr *InstrNode, unsigned OpIdx)
+      : InstrNode(InstrNode), OpIdx(OpIdx) {}
+
+  const GIMatchDagInstr *getInstrNode() const { return InstrNode; }
+  unsigned getOpIdx() const { return OpIdx; }
+};
+
+/// Represent a leaf of the match tree and any working data we need to build the
+/// tree.
+///
+/// It's important to note that each rule can have multiple
+/// GIMatchTreeBuilderLeafInfo's since the partitioners do not always partition
+/// into mutually-exclusive partitions. For example:
+///   R1: (FOO ..., ...)
+///   R2: (oneof(FOO, BAR) ..., ...)
+/// will partition by opcode into two partitions FOO=>[R1, R2], and BAR=>[R2]
+///
+/// As an optimization, all instructions, edges, and predicates in the DAGs are
+/// numbered and tracked in BitVectors. As such, the GIMatchDAG must not be
+/// modified once construction of the tree has begun.
+class GIMatchTreeBuilderLeafInfo {
+protected:
+  GIMatchTreeBuilder &Builder;
+  GIMatchTreeLeafInfo Info;
+  const GIMatchDag &MatchDag;
+  /// The association between GIMatchDagInstr* and GIMatchTreeInstrInfo.
+  /// The primary reason for this members existence is to allow the use of
+  /// InstrIDToInfo.lookup() since that requires that the value is
+  /// default-constructible.
+  DenseMap<const GIMatchDagInstr *, GIMatchTreeInstrInfo> InstrNodeToInfo;
+  /// The instruction information for a given ID in the context of this
+  /// particular leaf.
+  DenseMap<unsigned, GIMatchTreeInstrInfo *> InstrIDToInfo;
+  /// The operand information for a given ID and OpIdx in the context of this
+  /// particular leaf.
+  DenseMap<std::pair<unsigned, unsigned>, GIMatchTreeOperandInfo>
+      OperandIDToInfo;
+
+public:
+  /// The remaining instrs/edges/predicates to visit
+  BitVector RemainingInstrNodes;
+  BitVector RemainingEdges;
+  BitVector RemainingPredicates;
+
+  // The remaining predicate dependencies for each predicate
+  std::vector<BitVector> UnsatisfiedPredDepsForPred;
+
+  /// The edges/predicates we can visit as a result of the declare*() calls we
+  /// have already made. We don't need an instrs version since edges imply the
+  /// instr.
+  BitVector TraversableEdges;
+  BitVector TestablePredicates;
+
+  /// Map predicates from the DAG to their position in the DAG predicate
+  /// iterators.
+  DenseMap<GIMatchDagPredicate *, unsigned> PredicateIDs;
+  /// Map predicate dependency edges from the DAG to their position in the DAG
+  /// predicate dependency iterators.
+  DenseMap<GIMatchDagPredicateDependencyEdge *, unsigned> PredicateDepIDs;
+
+public:
+  GIMatchTreeBuilderLeafInfo(GIMatchTreeBuilder &Builder, StringRef Name,
+                             unsigned RootIdx, const GIMatchDag &MatchDag,
+                             void *Data);
+
+  StringRef getName() const { return Info.getName(); }
+  GIMatchTreeLeafInfo &getInfo() { return Info; }
+  const GIMatchTreeLeafInfo &getInfo() const { return Info; }
+  const GIMatchDag &getMatchDag() const { return MatchDag; }
+  unsigned getRootIdx() const { return Info.getRootIdx(); }
+
+  /// Has this DAG been fully traversed. This must be true by the time the tree
+  /// builder finishes.
+  bool isFullyTraversed() const {
+    // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates
+    // can't be all-zero without satisfying all the dependencies. The same is
+    // almost true for Edges and Instrs but it's possible to have Instrs without
+    // Edges.
+    return RemainingInstrNodes.none() && RemainingEdges.none();
+  }
+
+  /// Has this DAG been fully tested. This hould be true by the time the tree
+  /// builder finishes but clients can finish any untested predicates left over
+  /// if it's not true.
+  bool isFullyTested() const {
+    // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates
+    // can't be all-zero without satisfying all the dependencies. The same is
+    // almost true for Edges and Instrs but it's possible to have Instrs without
+    // Edges.
+    return RemainingInstrNodes.none() && RemainingEdges.none() &&
+           RemainingPredicates.none();
+  }
+
+  const GIMatchDagInstr *getInstr(unsigned Idx) const {
+    return *(MatchDag.instr_nodes_begin() + Idx);
+  }
+  const GIMatchDagEdge *getEdge(unsigned Idx) const {
+    return *(MatchDag.edges_begin() + Idx);
+  }
+  GIMatchDagEdge *getEdge(unsigned Idx) {
+    return *(MatchDag.edges_begin() + Idx);
+  }
+  const GIMatchDagPredicate *getPredicate(unsigned Idx) const {
+    return *(MatchDag.predicates_begin() + Idx);
+  }
+  iterator_range<llvm::BitVector::const_set_bits_iterator>
+  untested_instrs() const {
+    return RemainingInstrNodes.set_bits();
+  }
+  iterator_range<llvm::BitVector::const_set_bits_iterator>
+  untested_edges() const {
+    return RemainingEdges.set_bits();
+  }
+  iterator_range<llvm::BitVector::const_set_bits_iterator>
+  untested_predicates() const {
+    return RemainingPredicates.set_bits();
+  }
+
+  /// Bind an instr node to the given ID and clear any blocking dependencies
+  /// that were waiting for it.
+  void declareInstr(const GIMatchDagInstr *Instr, unsigned ID);
+
+  /// Bind an operand to the given ID and OpIdx and clear any blocking
+  /// dependencies that were waiting for it.
+  void declareOperand(unsigned InstrID, unsigned OpIdx);
+
+  GIMatchTreeInstrInfo *getInstrInfo(unsigned ID) const {
+    return InstrIDToInfo.lookup(ID);
+  }
+
+  void dump(raw_ostream &OS) const {
+    OS << "Leaf " << getName() << " for root #" << getRootIdx() << "\n";
+    MatchDag.print(OS);
+    for (const auto &I : InstrIDToInfo)
+      OS << "Declared Instr #" << I.first << "\n";
+    for (const auto &I : OperandIDToInfo)
+      OS << "Declared Instr #" << I.first.first << ", Op #" << I.first.second
+         << "\n";
+    OS << RemainingInstrNodes.count() << " untested instrs of "
+       << RemainingInstrNodes.size() << "\n";
+    OS << RemainingEdges.count() << " untested edges of "
+       << RemainingEdges.size() << "\n";
+    OS << RemainingPredicates.count() << " untested predicates of "
+       << RemainingPredicates.size() << "\n";
+
+    OS << TraversableEdges.count() << " edges could be traversed\n";
+    OS << TestablePredicates.count() << " predicates could be tested\n";
+  }
+};
+
+/// The tree builder has a fairly tough job. It's purpose is to merge all the
+/// DAGs from the ruleset into a decision tree that walks all of them
+/// simultaneously and identifies the rule that was matched. In addition to
+/// that, it also needs to find the most efficient order to make decisions
+/// without violating any dependencies and ensure that every DAG covers every
+/// instr/edge/predicate.
+class GIMatchTreeBuilder {
+public:
+  using LeafVec = std::vector<GIMatchTreeBuilderLeafInfo>;
+
+protected:
+  /// The leaves that the resulting decision tree will distinguish.
+  LeafVec Leaves;
+  /// The tree node being constructed.
+  GIMatchTree *TreeNode;
+  /// The builders for each subtree resulting from the current decision.
+  std::vector<GIMatchTreeBuilder> SubtreeBuilders;
+  /// The possible partitioners we could apply right now.
+  std::vector<std::unique_ptr<GIMatchTreePartitioner>> Partitioners;
+  /// The next instruction ID to allocate when requested by the chosen
+  /// Partitioner.
+  unsigned NextInstrID;
+
+  /// Use any context we have stored to cull partitioners that only test things
+  /// we already know. At the time of writing, there's no need to do anything
+  /// here but it will become important once, for example, there is a
+  /// num-operands and an opcode partitioner. This is because applying an opcode
+  /// partitioner (usually) makes the number of operands known which makes
+  /// additional checking pointless.
+  void filterRedundantPartitioners();
+
+  /// Evaluate the available partioners and select the best one at the moment.
+  void evaluatePartitioners();
+
+  /// Construct the current tree node.
+  void runStep();
+
+public:
+  GIMatchTreeBuilder(unsigned NextInstrID) : NextInstrID(NextInstrID) {}
+  GIMatchTreeBuilder(GIMatchTree *TreeNode, unsigned NextInstrID)
+      : TreeNode(TreeNode), NextInstrID(NextInstrID) {}
+
+  void addLeaf(StringRef Name, unsigned RootIdx, const GIMatchDag &MatchDag,
+               void *Data) {
+    Leaves.emplace_back(*this, Name, RootIdx, MatchDag, Data);
+  }
+  void addLeaf(const GIMatchTreeBuilderLeafInfo &L) { Leaves.push_back(L); }
+  void addPartitioner(std::unique_ptr<GIMatchTreePartitioner> P) {
+    Partitioners.push_back(std::move(P));
+  }
+  void addPartitionersForInstr(unsigned InstrIdx);
+  void addPartitionersForOperand(unsigned InstrID, unsigned OpIdx);
+
+  LeafVec &getPossibleLeaves() { return Leaves; }
+
+  unsigned allocInstrID() { return NextInstrID++; }
+
+  /// Construct the decision tree.
+  std::unique_ptr<GIMatchTree> run();
+};
+
+/// Partitioners are the core of the tree builder and are unfortunately rather
+/// tricky to write.
+class GIMatchTreePartitioner {
+protected:
+  /// The partitions resulting from applying the partitioner to the possible
+  /// leaves. The keys must be consecutive integers starting from 0. This can
+  /// lead to some unfortunate situations where partitioners test a predicate
+  /// and use 0 for success and 1 for failure if the ruleset encounters a
+  /// success case first but is necessary to assign the partition to one of the
+  /// tree nodes children. As a result, you usually need some kind of
+  /// indirection to map the natural keys (e.g. ptrs/bools) to this linear
+  /// sequence. The values are a bitvector indicating which leaves belong to
+  /// this partition.
+  DenseMap<unsigned, BitVector> Partitions;
+
+public:
+  virtual ~GIMatchTreePartitioner() {}
+  virtual std::unique_ptr<GIMatchTreePartitioner> clone() const = 0;
+
+  /// Determines which partitions the given leaves belong to. A leaf may belong
+  /// to multiple partitions in which case it will be duplicated during
+  /// applyForPartition().
+  ///
+  /// This function can be rather complicated. A few particular things to be
+  /// aware of include:
+  /// * One leaf can be assigned to multiple partitions when there's some
+  ///   ambiguity.
+  /// * Not all DAG's for the leaves may be able to perform the test. For
+  ///   example, the opcode partitiioner must account for one DAG being a
+  ///   superset of another such as [(ADD ..., ..., ...)], and [(MUL t, ...,
+  ///   ...), (ADD ..., t, ...)]
+  /// * Attaching meaning to a particular partition index will generally not
+  ///   work due to the '0, 1, ..., n' requirement. You might encounter cases
+  ///   where only partition 1 is seen, leaving a missing 0.
+  /// * Finding a specific predicate such as the opcode predicate for a specific
+  ///   instruction is non-trivial. It's often O(NumPredicates), leading to
+  ///   O(NumPredicates*NumRules) when applied to the whole ruleset. The good
+  ///   news there is that n is typically small thanks to predicate dependencies
+  ///   limiting how many are testable at once. Also, with opcode and type
+  ///   predicates being so frequent the value of m drops very fast too. It
+  ///   wouldn't be terribly surprising to see a 10k ruleset drop down to an
+  ///   average of 100 leaves per partition after a single opcode partitioner.
+  /// * The same goes for finding specific edges. The need to traverse them in
+  ///   dependency order dramatically limits the search space at any given
+  ///   moment.
+  /// * If you need to add a leaf to all partitions, make sure you don't forget
+  ///   them when adding partitions later.
+  virtual void repartition(GIMatchTreeBuilder::LeafVec &Leaves) = 0;
+
+  /// Delegate the leaves for a given partition to the corresponding subbuilder,
+  /// update any recorded context for this partition (e.g. allocate instr id's
+  /// for instrs recorder by the current node), and clear any blocking
+  /// dependencies this partitioner resolved.
+  virtual void applyForPartition(unsigned PartitionIdx,
+                                 GIMatchTreeBuilder &Builder,
+                                 GIMatchTreeBuilder &SubBuilder) = 0;
+
+  /// Return a BitVector indicating which leaves should be transferred to the
+  /// specified partition. Note that the same leaf can be indicated for multiple
+  /// partitions.
+  BitVector getPossibleLeavesForPartition(unsigned Idx) {
+    const auto &I = Partitions.find(Idx);
+    assert(I != Partitions.end() && "Requested non-existant partition");
+    return I->second;
+  }
+
+  size_t getNumPartitions() const { return Partitions.size(); }
+  size_t getNumLeavesWithDupes() const {
+    size_t S = 0;
+    for (const auto &P : Partitions)
+      S += P.second.size();
+    return S;
+  }
+
+  /// Emit a brief description of the partitioner suitable for debug printing or
+  /// use in a DOT graph.
+  virtual void emitDescription(raw_ostream &OS) const = 0;
+  /// Emit a label for the given partition suitable for debug printing or use in
+  /// a DOT graph.
+  virtual void emitPartitionName(raw_ostream &OS, unsigned Idx) const = 0;
+
+  /// Emit a long description of how the partitioner partitions the leaves.
+  virtual void emitPartitionResults(raw_ostream &OS) const = 0;
+
+  /// Generate code to select between partitions based on the MIR being matched.
+  /// This is typically a switch statement that picks a partition index.
+  virtual void generatePartitionSelectorCode(raw_ostream &OS,
+                                             StringRef Indent) const = 0;
+};
+
+/// Partition according to the opcode of the instruction.
+///
+/// Numbers CodeGenInstr ptrs for use as partition ID's. One special partition,
+/// nullptr, represents the case where the instruction isn't known.
+///
+/// * If the opcode can be tested and is a single opcode, create the partition
+///   for that opcode and assign the leaf to it. This partition no longer needs
+///   to test the opcode, and many details about the instruction will usually
+///   become known (e.g. number of operands for non-variadic instrs) via the
+///   CodeGenInstr ptr.
+/// * (not implemented yet) If the opcode can be tested and is a choice of
+///   opcodes, then the leaf can be treated like the single-opcode case but must
+///   be added to all relevant partitions and not quite as much becomes known as
+///   a result. That said, multiple-choice opcodes are likely similar enough
+///   (because if they aren't then handling them together makes little sense)
+///   that plenty still becomes known. The main implementation issue with this
+///   is having a description to represent the commonality between instructions.
+/// * If the opcode is not tested, the leaf must be added to all partitions
+///   including the wildcard nullptr partition. What becomes known as a result
+///   varies between partitions.
+/// * If the instruction to be tested is not declared then add the leaf to all
+///   partitions. This occurs when we encounter one rule that is a superset of
+///   the other and we are still matching the remainder of the superset. The
+///   result is that the cases that don't match the superset will match the
+///   subset rule, while the ones that do match the superset will match either
+///   (which one is algorithm dependent but will usually be the superset).
+class GIMatchTreeOpcodePartitioner : public GIMatchTreePartitioner {
+  unsigned InstrID;
+  DenseMap<const CodeGenInstruction *, unsigned> InstrToPartition;
+  std::vector<const CodeGenInstruction *> PartitionToInstr;
+  std::vector<BitVector> TestedPredicates;
+
+public:
+  GIMatchTreeOpcodePartitioner(unsigned InstrID) : InstrID(InstrID) {}
+
+  std::unique_ptr<GIMatchTreePartitioner> clone() const override {
+    return std::make_unique<GIMatchTreeOpcodePartitioner>(*this);
+  }
+
+  void emitDescription(raw_ostream &OS) const override {
+    OS << "MI[" << InstrID << "].getOpcode()";
+  }
+
+  void emitPartitionName(raw_ostream &OS, unsigned Idx) const override;
+
+  void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override;
+  void applyForPartition(unsigned Idx, GIMatchTreeBuilder &SubBuilder,
+                         GIMatchTreeBuilder &Builder) override;
+
+  void emitPartitionResults(raw_ostream &OS) const override;
+
+  void generatePartitionSelectorCode(raw_ostream &OS,
+                                     StringRef Indent) const override;
+};
+
+class GIMatchTreeVRegDefPartitioner : public GIMatchTreePartitioner {
+  unsigned NewInstrID = -1;
+  unsigned InstrID;
+  unsigned OpIdx;
+  std::vector<BitVector> TraversedEdges;
+  DenseMap<unsigned, unsigned> ResultToPartition;
+  BitVector PartitionToResult;
+
+  void addToPartition(bool Result, unsigned LeafIdx);
+
+public:
+  GIMatchTreeVRegDefPartitioner(unsigned InstrID, unsigned OpIdx)
+      : InstrID(InstrID), OpIdx(OpIdx) {}
+
+  std::unique_ptr<GIMatchTreePartitioner> clone() const override {
+    return std::make_unique<GIMatchTreeVRegDefPartitioner>(*this);
+  }
+
+  void emitDescription(raw_ostream &OS) const override {
+    OS << "MI[" << NewInstrID << "] = getVRegDef(MI[" << InstrID
+       << "].getOperand(" << OpIdx << "))";
+  }
+
+  void emitPartitionName(raw_ostream &OS, unsigned Idx) const override {
+    bool Result = PartitionToResult[Idx];
+    if (Result)
+      OS << "true";
+    else
+      OS << "false";
+  }
+
+  void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override;
+  void applyForPartition(unsigned PartitionIdx, GIMatchTreeBuilder &Builder,
+                         GIMatchTreeBuilder &SubBuilder) override;
+  void emitPartitionResults(raw_ostream &OS) const override;
+
+  void generatePartitionSelectorCode(raw_ostream &OS,
+                                     StringRef Indent) const override;
+};
+
+} // end namespace llvm
+#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H