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
15 #include "llvm/CodeGenData/OutlinedHashTree.h"
16
17 #define DEBUG_TYPE "outlined-hash-tree"
18
19 using namespace llvm;
20
walkGraph(NodeCallbackFn CallbackNode,EdgeCallbackFn CallbackEdge,bool SortedWalk) const21 void OutlinedHashTree::walkGraph(NodeCallbackFn CallbackNode,
22 EdgeCallbackFn CallbackEdge,
23 bool SortedWalk) const {
24 SmallVector<const HashNode *> Stack;
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) {
38 SmallVector<std::pair<stable_hash, const HashNode *>> SortedSuccessors;
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
size(bool GetTerminalCountOnly) const51 size_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
depth() const59 size_t OutlinedHashTree::depth() const {
60 size_t Size = 0;
61 DenseMap<const HashNode *, size_t> DepthMap;
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
insert(const HashSequencePair & SequencePair)71 void 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 ? *Current->Terminals : 0) + Count;
88 }
89
merge(const OutlinedHashTree * Tree)90 void OutlinedHashTree::merge(const OutlinedHashTree *Tree) {
91 HashNode *Dst = getRoot();
92 const HashNode *Src = Tree->getRoot();
93 SmallVector<std::pair<HashNode *, const HashNode *>> Stack;
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 =
102 (DstNode->Terminals ? *DstNode->Terminals : 0) + *SrcNode->Terminals;
103 for (auto &[Hash, NextSrcNode] : SrcNode->Successors) {
104 HashNode *NextDstNode;
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));
111 } else
112 NextDstNode = I->second.get();
113
114 Stack.emplace_back(NextDstNode, NextSrcNode.get());
115 }
116 }
117 }
118
119 std::optional<unsigned>
find(const HashSequence & Sequence) const120 OutlinedHashTree::find(const HashSequence &Sequence) const {
121 const HashNode *Current = getRoot();
122 for (stable_hash StableHash : Sequence) {
123 const auto I = Current->Successors.find(StableHash);
124 if (I == Current->Successors.end())
125 return 0;
126 Current = I->second.get();
127 }
128 return Current->Terminals;
129 }
130