llvm/CGData/OutlinedHashTree.h

0001 //===- OutlinedHashTree.h --------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===---------------------------------------------------------------------===//
0008 //
0009 // This defines the OutlinedHashTree class. It contains sequences of stable
0010 // hash values of instructions that have been outlined. This OutlinedHashTree
0011 // can be used to track the outlined instruction sequences across modules.
0012 //
0013 //===---------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_CGDATA_OUTLINEDHASHTREE_H
0016 #define LLVM_CGDATA_OUTLINEDHASHTREE_H
0017
0018 #include "llvm/ADT/DenseMap.h"
0019 #include "llvm/ADT/StableHashing.h"
0020 #include "llvm/ObjectYAML/YAML.h"
0021 #include "llvm/Support/raw_ostream.h"
0022
0023 #include <unordered_map>
0024 #include <vector>
0025
0026 namespace llvm {
0027
0028 /// A HashNode is an entry in an OutlinedHashTree, holding a hash value
0029 /// and a collection of Successors (other HashNodes). If a HashNode has
0030 /// a positive terminal value (Terminals > 0), it signifies the end of
0031 /// a hash sequence with that occurrence count.
0032 struct HashNode {
0033   /// The hash value of the node.
0034   stable_hash Hash = 0;
0035   /// The number of terminals in the sequence ending at this node.
0036   std::optional<unsigned> Terminals;
0037   /// The successors of this node.
0038   /// We don't use DenseMap as a stable_hash value can be tombstone.
0039   std::unordered_map<stable_hash, std::unique_ptr<HashNode>> Successors;
0040 };
0041
0042 class OutlinedHashTree {
0043
0044   using EdgeCallbackFn =
0045       std::function<void(const HashNode *, const HashNode *)>;
0046   using NodeCallbackFn = std::function<void(const HashNode *)>;
0047
0048   using HashSequence = SmallVector<stable_hash>;
0049   using HashSequencePair = std::pair<HashSequence, unsigned>;
0050
0051 public:
0052   /// Walks every edge and node in the OutlinedHashTree and calls CallbackEdge
0053   /// for the edges and CallbackNode for the nodes with the stable_hash for
0054   /// the source and the stable_hash of the sink for an edge. These generic
0055   /// callbacks can be used to traverse a OutlinedHashTree for the purpose of
0056   /// print debugging or serializing it.
0057   void walkGraph(NodeCallbackFn CallbackNode,
0058                  EdgeCallbackFn CallbackEdge = nullptr,
0059                  bool SortedWalk = false) const;
0060
0061   /// Release all hash nodes except the root hash node.
0062   void clear() {
0063     assert(getRoot()->Hash == 0 && !getRoot()->Terminals);
0064     getRoot()->Successors.clear();
0065   }
0066
0067   /// \returns true if the hash tree has only the root node.
0068   bool empty() { return size() == 1; }
0069
0070   /// \returns the size of a OutlinedHashTree by traversing it. If
0071   /// \p GetTerminalCountOnly is true, it only counts the terminal nodes
0072   /// (meaning it returns the the number of hash sequences in the
0073   /// OutlinedHashTree).
0074   size_t size(bool GetTerminalCountOnly = false) const;
0075
0076   /// \returns the depth of a OutlinedHashTree by traversing it.
0077   size_t depth() const;
0078
0079   /// \returns the root hash node of a OutlinedHashTree.
0080   const HashNode *getRoot() const { return &Root; }
0081   HashNode *getRoot() { return &Root; }
0082
0083   /// Inserts a \p Sequence into the this tree. The last node in the sequence
0084   /// will increase Terminals.
0085   void insert(const HashSequencePair &SequencePair);
0086
0087   /// Merge a \p OtherTree into this Tree.
0088   void merge(const OutlinedHashTree *OtherTree);
0089
0090   /// \returns the matching count if \p Sequence exists in the OutlinedHashTree.
0091   std::optional<unsigned> find(const HashSequence &Sequence) const;
0092
0093 private:
0094   HashNode Root;
0095 };
0096
0097 } // namespace llvm
0098
0099 #endif