//===- BalancedPartitioning.h ---------------------------------------------===// // // 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. // // The algorithm is used to find an ordering of FunctionNodes while optimizing // a specified objective. The algorithm uses recursive bisection; it starts // with a collection of unordered FunctionNodes and tries to split them into // two sets (buckets) of equal cardinality. Each bisection step is comprised of // iterations that greedily swap the FunctionNodes between the two buckets while // there is an improvement of the objective. Once the process converges, the // problem is divided into two sub-problems of half the size, which are // recursively applied for the two buckets. The final ordering of the // FunctionNodes is obtained by concatenating the two (recursively computed) // orderings. // // In order to speed up the computation, we limit the depth of the recursive // tree by a specified constant (SplitDepth) and apply at most a constant // number of greedy iterations per split (IterationsPerSplit). The worst-case // time complexity of the implementation is bounded by O(M*log^2 N), where // N is the number of FunctionNodes and M is the number of // FunctionNode-UtilityNode edges; (assuming that any collection of D // FunctionNodes contains O(D) UtilityNodes). Notice that the two different // recursive sub-problems are independent and thus can be efficiently processed // in parallel. // // Reference: // * Optimizing Function Layout for Mobile Applications, // https://arxiv.org/abs/2211.09285 // //===----------------------------------------------------------------------===// #ifndef LLVM_SUPPORT_BALANCED_PARTITIONING_H #define LLVM_SUPPORT_BALANCED_PARTITIONING_H #include "raw_ostream.h" #include "llvm/ADT/ArrayRef.h" #include <atomic> #include <condition_variable> #include <mutex> #include <random> #include <vector> namespace llvm { class ThreadPoolInterface; /// A function with a set of utility nodes where it is beneficial to order two /// functions close together if they have similar utility nodes class BPFunctionNode { … }; /// Algorithm parameters; default values are tuned on real-world binaries struct BalancedPartitioningConfig { … }; class BalancedPartitioning { … }; } // end namespace llvm #endif // LLVM_SUPPORT_BALANCED_PARTITIONING_H