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