Add pagerando binning pass

[rinon]

Summary

The PagerandoBinning pass packs pagerando-compatible functions into page-aligned
bins for loading as position-independent segments. The pass uses a first fit
algorithm to minimize wasted space in bins. Only functions marked with the
pagerando attribute are placed into bins.

Functions are associated with a chosen bin by setting an explicit section prefix
string containing the bin id. Functions in the same bin will then be placed into
the same section when writing the output file.

This patch set (D37580, D37581, D37582, D37583, D37584, D37585, D37586, D37587)
is a first draft of the pagerando implementation described in
http://lists.llvm.org/pipermail/llvm-dev/2017-June/113794.html.

[rinon]

This patch set (D37580, D37581, D37582, D37583, D37584, D37585, D37586, D37587) is a first draft of the pagerando implementation described in http://lists.llvm.org/pipermail/llvm-dev/2017-June/113794.html.

[rinon]

• Fix style nit

[rinon]

Rebase

[rinon]

Rebase

[rinon]

Rebase

[rinon]

• Add profile-guided pagerando binning algorithm
• Rebase

[rinon]

Rebase

[rinon]

Rebase

• Fix first-fit algorithm test after adding PGO binning.

[rinon]

Rebase

include/llvm/CodeGen/PagerandoBinning.h

+//===-- 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 <map>
+
+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<unsigned, unsigned> Bins; // <free space  ->  bin numbers>
+    unsigned BinCount = 1;
+  public:
+    unsigned assignToBin(unsigned FnSize);
+  };
+
+private:
+  Algorithm Algo;
+};
+
+} // end namespace llvm
+
+#endif
 No newline at end of file

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   /// StackMapLiveness - This pass analyses the register live-out set of
   /// stackmap/patchpoint intrinsics and attaches the calculated information to
   /// the intrinsic for later emission to the StackMap.
   extern char &StackMapLivenessID;
 
   /// LiveDebugValues pass
   extern char &LiveDebugValuesID;
 
+  /// PagerandoBinning - This pass assigns MachineFunctions to Pagerando bins.
+  ModulePass *createPagerandoBinningPass();
+
   /// createJumpInstrTables - This pass creates jump-instruction tables.
   ModulePass *createJumpInstrTablesPass();
 
   /// createForwardControlFlowIntegrityPass - This pass adds control-flow
   /// integrity.
   ModulePass *createForwardControlFlowIntegrityPass();
 
   /// InterleavedAccess Pass - This pass identifies and matches interleaved

include/llvm/InitializePasses.h

 void initializeObjCARCAPElimPass(PassRegistry&);
 void initializeObjCARCContractPass(PassRegistry&);
 void initializeObjCARCExpandPass(PassRegistry&);
 void initializeObjCARCOptPass(PassRegistry&);
 void initializeOptimizationRemarkEmitterWrapperPassPass(PassRegistry&);
 void initializeOptimizePHIsPass(PassRegistry&);
 void initializePAEvalPass(PassRegistry&);
 void initializePagerandoWrappersPass(PassRegistry&);
+void initializePagerandoBinningPass(PassRegistry&);
 void initializePEIPass(PassRegistry&);
 void initializePGOIndirectCallPromotionLegacyPassPass(PassRegistry&);
 void initializePGOInstrumentationGenLegacyPassPass(PassRegistry&);
 void initializePGOInstrumentationUseLegacyPassPass(PassRegistry&);
 void initializePGOMemOPSizeOptLegacyPassPass(PassRegistry&);
 void initializePHIEliminationPass(PassRegistry&);
 void initializePartialInlinerLegacyPassPass(PassRegistry&);
 void initializePartiallyInlineLibCallsLegacyPassPass(PassRegistry&);

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   MachineSSAUpdater.cpp
   MachineTraceMetrics.cpp
   MachineVerifier.cpp
   PatchableFunction.cpp
   MIRPrinter.cpp
   MIRPrintingPass.cpp
   MacroFusion.cpp
   OptimizePHIs.cpp
+  PagerandoBinning.cpp
   ParallelCG.cpp
   PeepholeOptimizer.cpp
   PHIElimination.cpp
   PHIEliminationUtils.cpp
   PostRAHazardRecognizer.cpp
   PostRASchedulerList.cpp
   PreISelIntrinsicLowering.cpp
   ProcessImplicitDefs.cpp

lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeMachineOutlinerPass(Registry);
   initializeMachinePipelinerPass(Registry);
   initializeMachinePostDominatorTreePass(Registry);
   initializeMachineRegionInfoPassPass(Registry);
   initializeMachineSchedulerPass(Registry);
   initializeMachineSinkingPass(Registry);
   initializeMachineVerifierPassPass(Registry);
   initializeOptimizePHIsPass(Registry);
+  initializePagerandoBinningPass(Registry);
   initializePEIPass(Registry);
   initializePHIEliminationPass(Registry);
   initializePatchableFunctionPass(Registry);
   initializePeepholeOptimizerPass(Registry);
   initializePostMachineSchedulerPass(Registry);
   initializePostRAHazardRecognizerPass(Registry);
   initializePostRASchedulerPass(Registry);
   initializePreISelIntrinsicLoweringLegacyPassPass(Registry);

lib/CodeGen/PagerandoBinning.cpp

+//===-- 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<MachineModuleInfo>();
+  AU.setPreservesAll();
+  ModulePass::getAnalysisUsage(AU);
+}
+
+bool PagerandoBinning::runOnModule(Module &M) {
+  auto &MMI = getAnalysis<MachineModuleInfo>();
+  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;
+}

lib/CodeGen/TargetPassConfig.cpp

if (getOptLevel() != CodeGenOpt::None) {
     // If the target requests it, assign local variables to stack slots relative
     // to one another and simplify frame index references where possible.
     addPass(&LocalStackSlotAllocationID, false);
   }
 
   if (TM->Options.EnableIPRA)
     addPass(createRegUsageInfoPropPass());
 
+  if (TM->isPagerando())
+    addPass(createPagerandoBinningPass());
+
   // Run pre-ra passes.
   addPreRegAlloc();
 
   // Run register allocation and passes that are tightly coupled with it,
   // including phi elimination and scheduling.
   if (getOptimizeRegAlloc())
     addOptimizedRegAlloc(createRegAllocPass(true));
   else {

unittests/CodeGen/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   AsmPrinter
   CodeGen
   Core
   Support
   )
 
 set(CodeGenSources
   DIEHashTest.cpp
   LowLevelTypeTest.cpp
   MachineInstrBundleIteratorTest.cpp
   MachineOperandTest.cpp
   ScalableVectorMVTsTest.cpp
+  PagerandoBinningTest.cpp
   )
 
 add_llvm_unittest(CodeGenTests
   ${CodeGenSources}
   )
 
 add_subdirectory(GlobalISel)

unittests/CodeGen/PagerandoBinningTest.cpp

+//===-- 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<std::pair<unsigned, unsigned>> 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