LLVM 20.0.0git
OutlinedHashTree.cpp
Go to the documentation of this file.
1//===-- OutlinedHashTree.cpp ----------------------------------------------===//
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// An OutlinedHashTree is a Trie that contains sequences of stable hash values
10// of instructions that have been outlined. This OutlinedHashTree can be used
11// to understand the outlined instruction sequences collected across modules.
12//
13//===----------------------------------------------------------------------===//
14
16
17#define DEBUG_TYPE "outlined-hash-tree"
18
19using namespace llvm;
20
21void OutlinedHashTree::walkGraph(NodeCallbackFn CallbackNode,
22 EdgeCallbackFn CallbackEdge,
23 bool SortedWalk) const {
25 Stack.emplace_back(getRoot());
26
27 while (!Stack.empty()) {
28 const auto *Current = Stack.pop_back_val();
29 if (CallbackNode)
30 CallbackNode(Current);
31
32 auto HandleNext = [&](const HashNode *Next) {
33 if (CallbackEdge)
34 CallbackEdge(Current, Next);
35 Stack.emplace_back(Next);
36 };
37 if (SortedWalk) {
39 for (const auto &[Hash, Successor] : Current->Successors)
40 SortedSuccessors.emplace_back(Hash, Successor.get());
41 llvm::sort(SortedSuccessors);
42 for (const auto &P : SortedSuccessors)
43 HandleNext(P.second);
44 } else {
45 for (const auto &P : Current->Successors)
46 HandleNext(P.second.get());
47 }
48 }
49}
50
51size_t OutlinedHashTree::size(bool GetTerminalCountOnly) const {
52 size_t Size = 0;
53 walkGraph([&Size, GetTerminalCountOnly](const HashNode *N) {
54 Size += (N && (!GetTerminalCountOnly || N->Terminals));
55 });
56 return Size;
57}
58
60 size_t Size = 0;
62 walkGraph([&Size, &DepthMap](
63 const HashNode *N) { Size = std::max(Size, DepthMap[N]); },
64 [&DepthMap](const HashNode *Src, const HashNode *Dst) {
65 size_t Depth = DepthMap[Src];
66 DepthMap[Dst] = Depth + 1;
67 });
68 return Size;
69}
70
71void OutlinedHashTree::insert(const HashSequencePair &SequencePair) {
72 auto &[Sequence, Count] = SequencePair;
73 HashNode *Current = getRoot();
74
75 for (stable_hash StableHash : Sequence) {
76 auto I = Current->Successors.find(StableHash);
77 if (I == Current->Successors.end()) {
78 std::unique_ptr<HashNode> Next = std::make_unique<HashNode>();
79 HashNode *NextPtr = Next.get();
80 NextPtr->Hash = StableHash;
81 Current->Successors.emplace(StableHash, std::move(Next));
82 Current = NextPtr;
83 } else
84 Current = I->second.get();
85 }
86 if (Count)
87 Current->Terminals = Current->Terminals.value_or(0) + Count;
88}
89
91 HashNode *Dst = getRoot();
92 const HashNode *Src = Tree->getRoot();
94 Stack.emplace_back(Dst, Src);
95
96 while (!Stack.empty()) {
97 auto [DstNode, SrcNode] = Stack.pop_back_val();
98 if (!SrcNode)
99 continue;
100 if (SrcNode->Terminals)
101 DstNode->Terminals = DstNode->Terminals.value_or(0) + *SrcNode->Terminals;
102 for (auto &[Hash, NextSrcNode] : SrcNode->Successors) {
103 HashNode *NextDstNode;
104 auto I = DstNode->Successors.find(Hash);
105 if (I == DstNode->Successors.end()) {
106 auto NextDst = std::make_unique<HashNode>();
107 NextDstNode = NextDst.get();
108 NextDstNode->Hash = Hash;
109 DstNode->Successors.emplace(Hash, std::move(NextDst));
110 } else
111 NextDstNode = I->second.get();
112
113 Stack.emplace_back(NextDstNode, NextSrcNode.get());
114 }
115 }
116}
117
118std::optional<unsigned>
119OutlinedHashTree::find(const HashSequence &Sequence) const {
120 const HashNode *Current = getRoot();
121 for (stable_hash StableHash : Sequence) {
122 const auto I = Current->Successors.find(StableHash);
123 if (I == Current->Successors.end())
124 return 0;
125 Current = I->second.get();
126 }
127 return Current->Terminals;
128}
uint64_t Size
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
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)
Definition: SmallVector.h:937
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1664
#define N
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.