1//===- OutlinedHashTree.h --------------------------------------*- C++ -*-===//
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
7//===---------------------------------------------------------------------===//
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.
13//===---------------------------------------------------------------------===//
15#ifndef LLVM_CGDATA_OUTLINEDHASHTREE_H
16#define LLVM_CGDATA_OUTLINEDHASHTREE_H
24#include <unordered_map>
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.
34 /// The hash value of the node.
36 /// The number of terminals in the sequence ending at this node.
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;
45 using EdgeCallbackFn =
47 using NodeCallbackFn = std::function<void(
const HashNode *)>;
50 using HashSequencePair = std::pair<HashSequence, unsigned>;
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.
59 EdgeCallbackFn CallbackEdge =
nullptr,
60 bool SortedWalk =
false)
const;
62 /// Release all hash nodes except the root hash node.
68 /// \returns true if the hash tree has only the root node.
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;
77 /// \returns the depth of a OutlinedHashTree by traversing it.
80 /// \returns the root hash node of a OutlinedHashTree.
84 /// Inserts a \p Sequence into the this tree. The last node in the sequence
85 /// will increase Terminals.
88 /// Merge a \p OtherTree into this Tree.
91 /// \returns the matching count if \p Sequence exists in the OutlinedHashTree.
92 LLVM_ABI std::optional<unsigned>
find(
const HashSequence &Sequence)
const;
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines the DenseMap class.
void clear()
Release all hash nodes except the root hash node.
LLVM_ABI size_t depth() const
LLVM_ABI 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...
LLVM_ABI std::optional< unsigned > find(const HashSequence &Sequence) const
const HashNode * getRoot() const
LLVM_ABI void merge(const OutlinedHashTree *OtherTree)
Merge a OtherTree into this Tree.
LLVM_ABI void insert(const HashSequencePair &SequencePair)
Inserts a Sequence into the this tree.
LLVM_ABI 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.
This is an optimization pass for GlobalISel generic memory operations.
uint64_t stable_hash
An opaque object representing a stable hash code.
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.