llvm/llvm/lib/Support/BalancedPartitioning.cpp

//===- BalancedPartitioning.cpp -------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements BalancedPartitioning, a recursive balanced graph
// partitioning algorithm.
//
//===----------------------------------------------------------------------===//

#include "llvm/Support/BalancedPartitioning.h"
#include "llvm/Config/llvm-config.h" // for LLVM_ENABLE_THREADS
#include "llvm/Support/Debug.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/Support/ThreadPool.h"

usingnamespacellvm;
#define DEBUG_TYPE …

void BPFunctionNode::dump(raw_ostream &OS) const { … }

template <typename Func>
void BalancedPartitioning::BPThreadPool::async(Func &&F) { … }

void BalancedPartitioning::BPThreadPool::wait() { … }

BalancedPartitioning::BalancedPartitioning(
    const BalancedPartitioningConfig &Config)
    : … { … }

void BalancedPartitioning::run(std::vector<BPFunctionNode> &Nodes) const { … }

void BalancedPartitioning::bisect(const FunctionNodeRange Nodes,
                                  unsigned RecDepth, unsigned RootBucket,
                                  unsigned Offset,
                                  std::optional<BPThreadPool> &TP) const { … }

void BalancedPartitioning::runIterations(const FunctionNodeRange Nodes,
                                         unsigned LeftBucket,
                                         unsigned RightBucket,
                                         std::mt19937 &RNG) const { … }

unsigned BalancedPartitioning::runIteration(const FunctionNodeRange Nodes,
                                            unsigned LeftBucket,
                                            unsigned RightBucket,
                                            SignaturesT &Signatures,
                                            std::mt19937 &RNG) const { … }

bool BalancedPartitioning::moveFunctionNode(BPFunctionNode &N,
                                            unsigned LeftBucket,
                                            unsigned RightBucket,
                                            SignaturesT &Signatures,
                                            std::mt19937 &RNG) const { … }

void BalancedPartitioning::split(const FunctionNodeRange Nodes,
                                 unsigned StartBucket) const { … }

float BalancedPartitioning::moveGain(const BPFunctionNode &N,
                                     bool FromLeftToRight,
                                     const SignaturesT &Signatures) { … }

float BalancedPartitioning::logCost(unsigned X, unsigned Y) const { … }

float BalancedPartitioning::log2Cached(unsigned i) const { … }