1 //===- OutlinedHashTree.h --------------------------------------*- C++ -*-===// 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 // This defines the OutlinedHashTree class. It contains sequences of stable 10 // hash values of instructions that have been outlined. This OutlinedHashTree 11 // can be used to track the outlined instruction sequences across modules. 12 // 13 //===---------------------------------------------------------------------===// 14 15 #ifndef LLVM_CODEGENDATA_OUTLINEDHASHTREE_H 16 #define LLVM_CODEGENDATA_OUTLINEDHASHTREE_H 17 18 #include "llvm/ADT/DenseMap.h" 19 #include "llvm/ADT/StableHashing.h" 20 #include "llvm/ObjectYAML/YAML.h" 21 #include "llvm/Support/raw_ostream.h" 22 23 #include <unordered_map> 24 #include <vector> 25 26 namespace llvm { 27 28 /// A HashNode is an entry in an OutlinedHashTree, holding a hash value 29 /// and a collection of Successors (other HashNodes). If a HashNode has 30 /// a positive terminal value (Terminals > 0), it signifies the end of 31 /// a hash sequence with that occurrence count. 32 struct HashNode { 33 /// The hash value of the node. 34 stable_hash Hash = 0; 35 /// The number of terminals in the sequence ending at this node. 36 std::optional<unsigned> Terminals; 37 /// The successors of this node. 38 /// We don't use DenseMap as a stable_hash value can be tombstone. 39 std::unordered_map<stable_hash, std::unique_ptr<HashNode>> Successors; 40 }; 41 42 class OutlinedHashTree { 43 44 using EdgeCallbackFn = 45 std::function<void(const HashNode *, const HashNode *)>; 46 using NodeCallbackFn = std::function<void(const HashNode *)>; 47 48 using HashSequence = SmallVector<stable_hash>; 49 using HashSequencePair = std::pair<HashSequence, unsigned>; 50 51 public: 52 /// Walks every edge and node in the OutlinedHashTree and calls CallbackEdge 53 /// for the edges and CallbackNode for the nodes with the stable_hash for 54 /// the source and the stable_hash of the sink for an edge. These generic 55 /// callbacks can be used to traverse a OutlinedHashTree for the purpose of 56 /// print debugging or serializing it. 57 void walkGraph(NodeCallbackFn CallbackNode, 58 EdgeCallbackFn CallbackEdge = nullptr, 59 bool SortedWalk = false) const; 60 61 /// Release all hash nodes except the root hash node. clear()62 void clear() { 63 assert(getRoot()->Hash == 0 && !getRoot()->Terminals); 64 getRoot()->Successors.clear(); 65 } 66 67 /// \returns true if the hash tree has only the root node. empty()68 bool empty() { return size() == 1; } 69 70 /// \returns the size of a OutlinedHashTree by traversing it. If 71 /// \p GetTerminalCountOnly is true, it only counts the terminal nodes 72 /// (meaning it returns the the number of hash sequences in the 73 /// OutlinedHashTree). 74 size_t size(bool GetTerminalCountOnly = false) const; 75 76 /// \returns the depth of a OutlinedHashTree by traversing it. 77 size_t depth() const; 78 79 /// \returns the root hash node of a OutlinedHashTree. getRoot()80 const HashNode *getRoot() const { return &Root; } getRoot()81 HashNode *getRoot() { return &Root; } 82 83 /// Inserts a \p Sequence into the this tree. The last node in the sequence 84 /// will increase Terminals. 85 void insert(const HashSequencePair &SequencePair); 86 87 /// Merge a \p OtherTree into this Tree. 88 void merge(const OutlinedHashTree *OtherTree); 89 90 /// \returns the matching count if \p Sequence exists in the OutlinedHashTree. 91 std::optional<unsigned> find(const HashSequence &Sequence) const; 92 93 private: 94 HashNode Root; 95 }; 96 97 } // namespace llvm 98 99 #endif 100