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/CGData/OutlinedHashTree.h"
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 {
24 SmallVector<const HashNode *> Stack;
25 Stack.emplace_back(Args: 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(Args&: 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(Args: Hash, Args: Successor.get());
41 llvm::sort(C&: 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(CallbackNode: [&Size, GetTerminalCountOnly](const HashNode *N) {
54 Size += (N && (!GetTerminalCountOnly || N->Terminals));
55 });
56 return Size;
57}
58
59size_t OutlinedHashTree::depth() const {
60 size_t Size = 0;
61 DenseMap<const HashNode *, size_t> DepthMap;
62 walkGraph(CallbackNode: [&Size, &DepthMap](
63 const HashNode *N) { Size = std::max(a: Size, b: DepthMap[N]); },
64 CallbackEdge: [&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(x: 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(args&: StableHash, args: std::move(Next));
82 Current = NextPtr;
83 } else
84 Current = I->second.get();
85 }
86 if (Count)
87 Current->Terminals = Current->Terminals.value_or(u: 0) + Count;
88}
89
90void 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(Args&: Dst, Args&: 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(u: 0) + *SrcNode->Terminals;
102 for (auto &[Hash, NextSrcNode] : SrcNode->Successors) {
103 HashNode *NextDstNode;
104 auto I = DstNode->Successors.find(x: 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(args: Hash, args: std::move(NextDst));
110 } else
111 NextDstNode = I->second.get();
112
113 Stack.emplace_back(Args&: NextDstNode, Args: 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(x: StableHash);
123 if (I == Current->Successors.end())
124 return 0;
125 Current = I->second.get();
126 }
127 return Current->Terminals;
128}
129