129 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// An OutlinedHashTree is a Trie that contains sequences of stable hash values10// of instructions that have been outlined. This OutlinedHashTree can be used11// 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(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 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 59size_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 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 } else84 Current = I->second.get();85 }86 if (Count)87 Current->Terminals = Current->Terminals.value_or(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(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 } else111 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}129