Index: include/llvm/CodeGen/PagerandoBinning.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/PagerandoBinning.h @@ -0,0 +1,63 @@ +//===-- PagerandoBinning.h - Binning for Pagerando ------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass assigns pagerando-enabled functions to bins. Normal functions +// (and pagerando wrappers) are not assigned to a bin. +// Function sizes are estimated by adding up the size of all instructions +// inside the corresponding MachineFunction. The default bin size is 4KB. +// The current bin allocation strategy is a greedy algorithm that, for every +// function, picks the bin with the smallest remaining free space that still +// accommodates the function. If such a bin does not exist, a new one is +// created. Functions that are larger than the default bin size are assigned to +// a new bin which forces the expansion of said bin. +// Because this pass estimates function sizes it should run as late as possible, +// but before Pagerando optimizer passes (since they rely on bin assignments). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_PAGERANDOBINNING_H +#define LLVM_CODEGEN_PAGERANDOBINNING_H + +#include "llvm/Pass.h" +#include + +namespace llvm { +class MachineFunction; + +class PagerandoBinning : public ModulePass { +public: + static char ID; + static constexpr auto SectionPrefix = ".bin_"; + + explicit PagerandoBinning(); + + bool runOnModule(Module &M) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; + +private: + static constexpr unsigned BinSize = 4096; // one page + static constexpr unsigned MinFnSize = 2; // 'bx lr' on ARM thumb + + unsigned estimateFunctionSize(const MachineFunction &MF); + +public: + class Algorithm { + std::multimap Bins; // bin numbers> + unsigned BinCount = 1; + public: + unsigned assignToBin(unsigned FnSize); + }; + +private: + Algorithm Algo; +}; + +} // end namespace llvm + +#endif \ No newline at end of file Index: include/llvm/CodeGen/Passes.h =================================================================== --- include/llvm/CodeGen/Passes.h +++ include/llvm/CodeGen/Passes.h @@ -352,6 +352,9 @@ /// LiveDebugValues pass extern char &LiveDebugValuesID; + /// PagerandoBinning - This pass assigns MachineFunctions to Pagerando bins. + ModulePass *createPagerandoBinningPass(); + /// createJumpInstrTables - This pass creates jump-instruction tables. ModulePass *createJumpInstrTablesPass(); Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -276,6 +276,7 @@ void initializeOptimizePHIsPass(PassRegistry&); void initializePAEvalPass(PassRegistry&); void initializePagerandoWrappersPass(PassRegistry&); +void initializePagerandoBinningPass(PassRegistry&); void initializePEIPass(PassRegistry&); void initializePGOIndirectCallPromotionLegacyPassPass(PassRegistry&); void initializePGOInstrumentationGenLegacyPassPass(PassRegistry&); Index: lib/CodeGen/CMakeLists.txt =================================================================== --- lib/CodeGen/CMakeLists.txt +++ lib/CodeGen/CMakeLists.txt @@ -94,6 +94,7 @@ MIRPrintingPass.cpp MacroFusion.cpp OptimizePHIs.cpp + PagerandoBinning.cpp ParallelCG.cpp PeepholeOptimizer.cpp PHIElimination.cpp Index: lib/CodeGen/CodeGen.cpp =================================================================== --- lib/CodeGen/CodeGen.cpp +++ lib/CodeGen/CodeGen.cpp @@ -67,6 +67,7 @@ initializeMachineSinkingPass(Registry); initializeMachineVerifierPassPass(Registry); initializeOptimizePHIsPass(Registry); + initializePagerandoBinningPass(Registry); initializePEIPass(Registry); initializePHIEliminationPass(Registry); initializePatchableFunctionPass(Registry); Index: lib/CodeGen/PagerandoBinning.cpp =================================================================== --- /dev/null +++ lib/CodeGen/PagerandoBinning.cpp @@ -0,0 +1,102 @@ +//===-- PagerandoBinning.cpp - Binning for Pagerando ----------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass assigns pagerando-enabled functions to bins. Normal functions +// (and pagerando wrappers) are not assigned to a bin. +// Function sizes are estimated by adding up the size of all instructions +// inside the corresponding MachineFunction. The default bin size is 4KB. +// The current bin allocation strategy is a greedy algorithm that, for every +// function, picks the bin with the smallest remaining free space that still +// accommodates the function. If such a bin does not exist, a new one is +// created. Functions that are larger than the default bin size are assigned to +// a new bin which forces the expansion of said bin. +// Because this pass estimates function sizes it should run as late as possible, +// but before Pagerando optimizer passes (since they rely on bin assignments). +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/PagerandoBinning.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" + +using namespace llvm; + +#define DEBUG_TYPE "pagerando" + +char PagerandoBinning::ID = 0; +INITIALIZE_PASS_BEGIN(PagerandoBinning, "pagerando-binning", + "Pagerando function binning", false, false) +INITIALIZE_PASS_DEPENDENCY(MachineModuleInfo); +INITIALIZE_PASS_END(PagerandoBinning, "pagerando-binning", + "Pagerando function binning", false, false) + +ModulePass *llvm::createPagerandoBinningPass() { + return new PagerandoBinning(); +} + +PagerandoBinning::PagerandoBinning() : ModulePass(ID) { + initializePagerandoBinningPass(*PassRegistry::getPassRegistry()); +} + +void PagerandoBinning::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.setPreservesAll(); + ModulePass::getAnalysisUsage(AU); +} + +bool PagerandoBinning::runOnModule(Module &M) { + auto &MMI = getAnalysis(); + bool Changed = false; + + for (auto &F : M) { + if (F.isPagerando()) { + unsigned FnSize = estimateFunctionSize(*MMI.getMachineFunction(F)); + unsigned Bin = Algo.assignToBin(FnSize); + // Note: overwrites an existing section prefix + F.setSectionPrefix(SectionPrefix + utostr(Bin)); + Changed = true; + } + } + + return Changed; +} + +unsigned PagerandoBinning::estimateFunctionSize(const MachineFunction &MF) { + auto *TII = MF.getSubtarget().getInstrInfo(); + + unsigned Size = 0; + for (auto &MBB : MF) + for (auto &MI : MBB) + Size += TII->getInstSizeInBytes(MI); + + return std::max(Size, MinFnSize+0); +} + +unsigned PagerandoBinning::Algorithm::assignToBin(unsigned FnSize) { + unsigned Bin, FreeSpace; + + auto I = Bins.lower_bound(FnSize); + if (I != Bins.end()) { + std::tie(FreeSpace, Bin) = *I; + FreeSpace -= FnSize; + Bins.erase(I); + } else { // No bin with enough free space + Bin = BinCount++; + auto Size = FnSize % BinSize; + FreeSpace = (Size == 0) ? 0 : (BinSize - Size); + } + + if (FreeSpace >= MinFnSize) + Bins.emplace(FreeSpace, Bin); + + return Bin; +} Index: lib/CodeGen/TargetPassConfig.cpp =================================================================== --- lib/CodeGen/TargetPassConfig.cpp +++ lib/CodeGen/TargetPassConfig.cpp @@ -823,6 +823,9 @@ if (TM->Options.EnableIPRA) addPass(createRegUsageInfoPropPass()); + if (TM->isPagerando()) + addPass(createPagerandoBinningPass()); + // Run pre-ra passes. addPreRegAlloc(); Index: unittests/CodeGen/CMakeLists.txt =================================================================== --- unittests/CodeGen/CMakeLists.txt +++ unittests/CodeGen/CMakeLists.txt @@ -15,6 +15,7 @@ MachineInstrTest.cpp MachineOperandTest.cpp ScalableVectorMVTsTest.cpp + PagerandoBinningTest.cpp ) add_llvm_unittest(CodeGenTests Index: unittests/CodeGen/PagerandoBinningTest.cpp =================================================================== --- /dev/null +++ unittests/CodeGen/PagerandoBinningTest.cpp @@ -0,0 +1,89 @@ +//===-- PagerandoBinningTest.cpp ------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/PagerandoBinning.h" +#include "gtest/gtest.h" + +using namespace llvm; + +namespace { + +// Test fixture +struct PagerandoBinningTest : public testing::Test { + PagerandoBinning::Algorithm Algo; + + void ASSERT_ASSIGNMENTS( + std::initializer_list> Assignments) { + for (auto &A : Assignments) { + unsigned FnSize, ExpectedBin; + std::tie(FnSize, ExpectedBin) = A; + unsigned Bin = Algo.assignToBin(FnSize); + ASSERT_EQ(Bin, ExpectedBin); + } + } +}; + +TEST_F(PagerandoBinningTest, NeverReturnsDefaultBin) { + ASSERT_NE(Algo.assignToBin(100), 0u); +} + +TEST_F(PagerandoBinningTest, UsesGreedyAlgorithm) { + ASSERT_ASSIGNMENTS({ + {3000, 1}, + {3000, 2}, + {1000, 1}, + {1000, 2}, + {1000, 3}, + }); +} + +TEST_F(PagerandoBinningTest, UsesRemainingFreeSpace) { + ASSERT_ASSIGNMENTS({ + {3000, 1}, + {1000, 1}, + { 100, 2}, + { 90, 1}, + { 6, 1}, + { 1, 2}, + }); +} + +TEST_F(PagerandoBinningTest, UsesBinWithLeastFreeSpace) { + ASSERT_ASSIGNMENTS({ + {3000, 1}, + {3001, 2}, + {3000, 3}, + { 100, 2}, + }); +} + +TEST_F(PagerandoBinningTest, FreeSpaceMustBeAtLeastMinFnSize) { + ASSERT_ASSIGNMENTS({ + {4095, 1}, + { 1, 2}, + {4095, 2}, + }); +} + +TEST_F(PagerandoBinningTest, BinSizedFunctionsAlwaysGetTheirOwnBin) { + ASSERT_ASSIGNMENTS({ + {4096, 1}, + {8192, 2}, + { 1, 3}, + }); +} + +TEST_F(PagerandoBinningTest, LargeFunctionsAreStillPacked) { + ASSERT_ASSIGNMENTS({ + {8000, 1}, + { 100, 1}, + }); +} + +} // end anonymous namespace