17#define DEBUG_TYPE "outlined-hash-tree"
22 EdgeCallbackFn CallbackEdge,
23 bool SortedWalk)
const {
27 while (!Stack.empty()) {
28 const auto *Current = Stack.pop_back_val();
30 CallbackNode(Current);
32 auto HandleNext = [&](
const HashNode *Next) {
34 CallbackEdge(Current, Next);
35 Stack.emplace_back(Next);
39 for (
const auto &[Hash,
Successor] : Current->Successors)
42 for (
const auto &
P : SortedSuccessors)
45 for (
const auto &
P : Current->Successors)
46 HandleNext(
P.second.get());
54 Size += (
N && (!GetTerminalCountOnly ||
N->Terminals));
65 size_t Depth = DepthMap[Src];
66 DepthMap[Dst] =
Depth + 1;
72 auto &[Sequence, Count] = SequencePair;
78 std::unique_ptr<HashNode> Next = std::make_unique<HashNode>();
80 NextPtr->
Hash = StableHash;
81 Current->
Successors.emplace(StableHash, std::move(Next));
84 Current =
I->second.get();
94 Stack.emplace_back(Dst, Src);
96 while (!Stack.empty()) {
97 auto [DstNode, SrcNode] = Stack.pop_back_val();
100 if (SrcNode->Terminals)
102 (DstNode->Terminals ? *DstNode->Terminals : 0) + *SrcNode->Terminals;
103 for (
auto &[Hash, NextSrcNode] : SrcNode->Successors) {
105 auto I = DstNode->Successors.find(Hash);
106 if (
I == DstNode->Successors.end()) {
107 auto NextDst = std::make_unique<HashNode>();
108 NextDstNode = NextDst.get();
109 NextDstNode->
Hash = Hash;
110 DstNode->Successors.emplace(Hash, std::move(NextDst));
112 NextDstNode =
I->second.get();
114 Stack.emplace_back(NextDstNode, NextSrcNode.get());
119std::optional<unsigned>
123 const auto I = Current->
Successors.find(StableHash);
126 Current =
I->second.get();
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
void walkGraph(NodeCallbackFn CallbackNode, EdgeCallbackFn CallbackEdge=nullptr, bool SortedWalk=false) const
Walks every edge and node in the OutlinedHashTree and calls CallbackEdge for the edges and CallbackNo...
std::optional< unsigned > find(const HashSequence &Sequence) const
const HashNode * getRoot() const
void merge(const OutlinedHashTree *OtherTree)
Merge a OtherTree into this Tree.
void insert(const HashSequencePair &SequencePair)
Inserts a Sequence into the this tree.
size_t size(bool GetTerminalCountOnly=false) const
reference emplace_back(ArgTypes &&... Args)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This is an optimization pass for GlobalISel generic memory operations.
void sort(IteratorTy Start, IteratorTy End)
A HashNode is an entry in an OutlinedHashTree, holding a hash value and a collection of Successors (o...
std::unordered_map< stable_hash, std::unique_ptr< HashNode > > Successors
The successors of this node.
std::optional< unsigned > Terminals
The number of terminals in the sequence ending at this node.
stable_hash Hash
The hash value of the node.