LLVM 20.0.0git
OutlinedHashTree.h
Go to the documentation of this file.
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"
22
23#include <unordered_map>
24#include <vector>
25
26namespace 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.
32struct HashNode {
33 /// The hash value of the node.
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
43
44 using EdgeCallbackFn =
45 std::function<void(const HashNode *, const HashNode *)>;
46 using NodeCallbackFn = std::function<void(const HashNode *)>;
47
49 using HashSequencePair = std::pair<HashSequence, unsigned>;
50
51public:
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.
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.
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.
80 const HashNode *getRoot() const { return &Root; }
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
93private:
94 HashNode Root;
95};
96
97} // namespace llvm
98
99#endif
This file defines the DenseMap class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void clear()
Release all hash nodes except the root hash node.
void walkGraph(NodeCallbackFn CallbackNode, EdgeCallbackFn CallbackEdge=nullptr, bool SortedWalk=false) const
Walks every edge and node in the OutlinedHashTree and calls CallbackEdge for the edges and CallbackNo...
std::optional< unsigned > find(const HashSequence &Sequence) const
const HashNode * getRoot() const
void merge(const OutlinedHashTree *OtherTree)
Merge a OtherTree into this Tree.
void insert(const HashSequencePair &SequencePair)
Inserts a Sequence into the this tree.
size_t size(bool GetTerminalCountOnly=false) const
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
A HashNode is an entry in an OutlinedHashTree, holding a hash value and a collection of Successors (o...
std::unordered_map< stable_hash, std::unique_ptr< HashNode > > Successors
The successors of this node.
std::optional< unsigned > Terminals
The number of terminals in the sequence ending at this node.
stable_hash Hash
The hash value of the node.