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 21 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 51 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 59 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 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 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> 120 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