LLVM: lib/CGData/OutlinedHashTree.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
16
17#define DEBUG_TYPE "outlined-hash-tree"
18
19using namespace llvm;
20
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
33 if (CallbackEdge)
34 CallbackEdge(Current, Next);
35 Stack.emplace_back(Next);
36 };
37 if (SortedWalk) {
39 for (const auto &[Hash, Successor] : Current->Successors)
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
52 size_t Size = 0;
54 Size += (N && (!GetTerminalCountOnly || N->Terminals));
55 });
57}
58
60 size_t Size = 0;
65 size_t Depth = DepthMap[Src];
66 DepthMap[Dst] = Depth + 1;
67 });
69}
70
72 auto &[Sequence, Count] = SequencePair;
74
76 auto I = Current->Successors.find(StableHash);
78 std::unique_ptr Next = std::make_unique();
80 NextPtr->Hash = StableHash;
81 Current->Successors.emplace(StableHash, std::move(Next));
82 Current = NextPtr;
83 } else
84 Current = I->second.get();
85 }
88}
89
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) {
104 auto I = DstNode->Successors.find(Hash);
105 if (I == DstNode->Successors.end()) {
106 auto NextDst = std::make_unique();
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
121 for (stable_hash StableHash : Sequence) {
122 const auto I = Current->Successors.find(StableHash);
124 return 0;
125 Current = I->second.get();
126 }
128}
LLVM_ABI size_t depth() const
Definition OutlinedHashTree.cpp:59
LLVM_ABI 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...
Definition OutlinedHashTree.cpp:21
LLVM_ABI std::optional< unsigned > find(const HashSequence &Sequence) const
Definition OutlinedHashTree.cpp:119
const HashNode * getRoot() const
LLVM_ABI void merge(const OutlinedHashTree *OtherTree)
Merge a OtherTree into this Tree.
Definition OutlinedHashTree.cpp:90
LLVM_ABI void insert(const HashSequencePair &SequencePair)
Inserts a Sequence into the this tree.
Definition OutlinedHashTree.cpp:71
LLVM_ABI size_t size(bool GetTerminalCountOnly=false) const
Definition OutlinedHashTree.cpp:51
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.
uint64_t stable_hash
An opaque object representing a stable hash code.
void sort(IteratorTy Start, IteratorTy End)
FunctionAddr VTableAddr Count
FunctionAddr VTableAddr Next
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.