39#ifndef LLVM_SUPPORT_BALANCED_PARTITIONING_H
40#define LLVM_SUPPORT_BALANCED_PARTITIONING_H
47#include <condition_variable>
54class ThreadPoolInterface;
106 LLVM_ABI void run(std::vector<BPFunctionNode> &Nodes)
const;
109 struct UtilitySignature;
118 struct BPThreadPool {
121 std::condition_variable cv;
123 std::atomic<int> NumActiveThreads = 0;
125 bool IsFinishedSpawning =
false;
127 template <
typename Func>
void async(Func &&
F);
133 : TheThreadPool(TheThreadPool) {}
142 unsigned RootBucket,
unsigned Offset,
143 std::optional<BPThreadPool> &TP)
const;
147 unsigned RightBucket, std::mt19937 &RNG)
const;
153 std::mt19937 &RNG)
const;
159 std::mt19937 &RNG)
const;
167 float logCost(
unsigned X,
unsigned Y)
const;
169 float log2Cached(
unsigned i)
const;
174 static constexpr unsigned LOG_CACHE_SIZE = 16384;
175 float Log2Cache[LOG_CACHE_SIZE];
179 struct UtilitySignature {
181 unsigned LeftCount = 0;
183 unsigned RightCount = 0;
191 bool CachedGainIsValid =
false;
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
static const FuncProtoTy Signatures[]
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
A function with a set of utility nodes where it is beneficial to order two functions close together i...
IDT Id
The ID of this node.
friend class BPFunctionNodeTest_Basic_Test
BPFunctionNode(IDT Id, ArrayRef< UtilityNodeT > UtilityNodes)
friend class BalancedPartitioningTest_Large_Test
SmallVector< UtilityNodeT, 4 > UtilityNodes
The list of utility nodes associated with this node.
uint64_t InputOrderIndex
The index of the input order of the FunctionNodes.
friend class BalancedPartitioningTest_Basic_Test
std::optional< unsigned > Bucket
The bucket assigned by balanced partitioning.
LLVM_ABI void dump(raw_ostream &OS) const
static LLVM_ABI float moveGain(const BPFunctionNode &N, bool FromLeftToRight, const SignaturesT &Signatures)
Compute the move gain for uniform log-gap cost.
LLVM_ABI void run(std::vector< BPFunctionNode > &Nodes) const
Run recursive graph partitioning that optimizes a given objective.
friend class BalancedPartitioningTest_MoveGain_Test
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This defines the abstract base interface for a ThreadPool allowing asynchronous parallel execution on...
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
This is an optimization pass for GlobalISel generic memory operations.
Algorithm parameters; default values are tuned on real-world binaries.
unsigned SplitDepth
The depth of the recursive bisection.
float SkipProbability
The probability for a vertex to skip a move from its current bucket to another bucket; it often helps...
unsigned TaskSplitDepth
Recursive subtasks up to the given depth are added to the queue and distributed among threads by Thre...
unsigned IterationsPerSplit
The maximum number of bp iterations per split.