llvm/lib/CGData/OutlinedHashTree.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-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
  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.value_or(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 = 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       } else
 111         NextDstNode = I->second.get();
 112
 113       Stack.emplace_back(NextDstNode, NextSrcNode.get());
 114     }
 115   }
 116 }
 117
 118 std::optional<unsigned>
 119 OutlinedHashTree::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 }