[BOLT] Remove old layout from function layout

[FPar]

Summary

To track whether a function's new layout is different from its old
layout when updating it, the old layout would be kept around in memory
indefinitely (if the new layout is different). This was used only for
debugging/logging purposes. This patch forces the caller of function
layout's update method to copy the old layout into a temporary if they
need it by removing the old layout fields.

[FPar]

clang-format

[FPar]

Cleanup

[rafauler]

Nice cleanup, thanks! LGTM

[rafauler]

Because this diff involves reduction in RSS, you might want to measure that to claim reduced memory footprint wins.

[FPar]

In D131413#3727433, @rafauler wrote:

Because this diff involves reduction in RSS, you might want to measure that to claim reduced memory footprint wins.

It does not have to seem any impact on max RSS.

bolt/include/bolt/Core/FunctionLayout.h

 
 private:
   BasicBlockListType Blocks;
   /// List of indices dividing block list into fragments. To simplify iteration,
   /// we have `Fragments.back()` equals `Blocks.size()`. Hence,
   /// `Fragments.size()` equals `this->size() + 1`. Always contains at least one
   /// fragment.
   FragmentListType Fragments = {0, 0};
-  BasicBlockListType PreviousBlocks;
-  FragmentListType PreviousFragments;
 
 public:
   /// Add an empty fragment.
   FunctionFragment addFragment();
 
   /// Return the fragment identified by Num.
   FunctionFragment getFragment(FragmentNum Num) const;
 
public:
   /// Erase all blocks from the layout that are in ToErase.
   void eraseBasicBlocks(const DenseSet<const BinaryBasicBlock *> ToErase);
 
   /// Make sure fragments' and basic blocks' indices match the current layout.
   void updateLayoutIndices() const;
 
   /// Replace the current layout with NewLayout. Uses the block's
   /// self-identifying fragment number to assign blocks to infer function
-  /// fragments.
-  void update(const ArrayRef<BinaryBasicBlock *> NewLayout);
-
-  /// Return true if the layout has been changed by basic block reordering,
-  /// false otherwise.
-  bool hasLayoutChanged() const { return !PreviousBlocks.empty(); }
+  /// fragments. Returns `true` if the new layout is different from the current
+  /// layout.
+  bool update(ArrayRef<BinaryBasicBlock *> NewLayout);
 
   /// Clear layout releasing memory.
   void clear();
 
   BinaryBasicBlock *getBlock(unsigned Index) const { return Blocks[Index]; }
 
   /// Returns the basic block after the given basic block in the layout or
   /// nullptr if the last basic block is given.
   BinaryBasicBlock *getBasicBlockAfter(const BinaryBasicBlock *BB,
                                        bool IgnoreSplits = true) const;
 
   /// True if the layout contains at least two non-empty fragments.
   bool isSplit() const;
 
   /// Get the edit distance of the new layout with respect to the previous
   /// layout after basic block reordering.
-  uint64_t getEditDistance() const;
+  uint64_t
+  getEditDistance(ArrayRef<const BinaryBasicBlock *> OldBlockOrder) const;
 
   /// True if the function is split into at most 2 fragments. Mostly used for
   /// checking whether a function can be processed in places that do not support
   /// multiple fragments yet.
   bool isHotColdSplit() const { return fragment_size() <= 2; }
 
   size_t fragment_size() const {
     assert(Fragments.size() >= 2 &&

bolt/include/bolt/Passes/BinaryPasses.h

enum LayoutType : char {
     LT_OPTIMIZE_CACHE_PLUS,
     /// Block reordering guided by the extended TSP metric.
     LT_OPTIMIZE_EXT_TSP,
     /// Create clusters and use random order for them.
     LT_OPTIMIZE_SHUFFLE,
   };
 
 private:
-  void modifyFunctionLayout(BinaryFunction &Function, LayoutType Type,
+  /// Run the specified layout algorithm on the given function. Returns `true`
+  /// if the order of blocks was changed.
+  bool modifyFunctionLayout(BinaryFunction &Function, LayoutType Type,
                             bool MinBranchClusters) const;
 
 public:
   explicit ReorderBasicBlocks(const cl::opt<bool> &PrintPass)
       : BinaryFunctionPass(PrintPass) {}
 
   bool shouldOptimize(const BinaryFunction &BF) const override;
 

bolt/lib/Core/FunctionLayout.cpp

 void FunctionLayout::updateLayoutIndices() const {
   unsigned BlockIndex = 0;
   for (const FunctionFragment FF : fragments()) {
     for (BinaryBasicBlock *const BB : FF)
       BB->setLayoutIndex(BlockIndex++);
   }
 }
 
-void FunctionLayout::update(const ArrayRef<BinaryBasicBlock *> NewLayout) {
-  PreviousBlocks = std::move(Blocks);
-  PreviousFragments = std::move(Fragments);
+bool FunctionLayout::update(const ArrayRef<BinaryBasicBlock *> NewLayout) {
+  const bool EqualBlockOrder = llvm::equal(Blocks, NewLayout);
+  if (EqualBlockOrder) {
+    const bool EqualPartitioning =
+        llvm::all_of(fragments(), [](const FunctionFragment FF) {
+          return llvm::all_of(FF, [&](const BinaryBasicBlock *const BB) {
+            return FF.Num == BB->getFragmentNum();
+          });
+        });
+    if (EqualPartitioning)
+      return false;
+  }
 
-  Blocks.clear();
+  Blocks = BasicBlockListType(NewLayout.begin(), NewLayout.end());
   Fragments = {0, 0};
 
-  if (NewLayout.empty())
-    return;
-
-  copy(NewLayout, std::back_inserter(Blocks));
-
   // Generate fragments
   for (const auto &BB : enumerate(Blocks)) {
     unsigned FragmentNum = BB.value()->getFragmentNum().get();
 
     assert(FragmentNum >= fragment_size() - 1 &&
            "Blocks must be arranged such that fragments are monotonically "
            "increasing.");
 
     // Add empty fragments if necessary
     for (unsigned I = fragment_size(); I <= FragmentNum; ++I) {
       addFragment();
       Fragments[I] = BB.index();
     }
 
     // Set the next fragment to point one past the current BB
     Fragments[FragmentNum + 1] = BB.index() + 1;
   }
 
-  if (PreviousBlocks == Blocks && PreviousFragments == Fragments) {
-    // If new layout is the same as previous layout, clear previous layout so
-    // hasLayoutChanged() returns false.
-    PreviousBlocks = {};
-    PreviousFragments = {};
-  }
+  return true;
 }
 
 void FunctionLayout::clear() {
   Blocks = {};
   Fragments = {0, 0};
-  PreviousBlocks = {};
-  PreviousFragments = {0, 0};
 }
 
 BinaryBasicBlock *FunctionLayout::getBasicBlockAfter(const BinaryBasicBlock *BB,
                                                      bool IgnoreSplits) const {
   const block_const_iterator BBPos = find(Blocks, BB);
   if (BBPos == Blocks.end())
     return nullptr;
 

 }
 
 bool FunctionLayout::isSplit() const {
   unsigned NonEmptyFragCount = llvm::count_if(
       fragments(), [](const FunctionFragment &FF) { return !FF.empty(); });
   return NonEmptyFragCount >= 2;
 }
 
-uint64_t FunctionLayout::getEditDistance() const {
-  return ComputeEditDistance<BinaryBasicBlock *>(PreviousBlocks, Blocks);
+uint64_t FunctionLayout::getEditDistance(
+    const ArrayRef<const BinaryBasicBlock *> OldBlockOrder) const {
+  return ComputeEditDistance<const BinaryBasicBlock *>(OldBlockOrder, Blocks);
 }
 
 FunctionLayout::block_const_iterator
 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) const {
   return find(Blocks, BB);
 }
 
 FunctionLayout::block_iterator
 FunctionLayout::findBasicBlockPos(const BinaryBasicBlock *BB) {
   return find(Blocks, BB);
 }

bolt/lib/Passes/BinaryPasses.cpp

 //===- bolt/Passes/BinaryPasses.cpp - Binary-level passes -----------------===//
 //
 // 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 multiple passes for binary optimization and analysis.
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/BinaryPasses.h"
+#include "bolt/Core/FunctionLayout.h"
 #include "bolt/Core/ParallelUtilities.h"
 #include "bolt/Passes/ReorderAlgorithm.h"
 #include "bolt/Passes/ReorderFunctions.h"
 #include "llvm/Support/CommandLine.h"
-
+#include <atomic>
+#include <mutex>
 #include <numeric>
 #include <vector>
 
 #define DEBUG_TYPE "bolt-opts"
 
 using namespace llvm;
 using namespace bolt;
 
bool ReorderBasicBlocks::shouldOptimize(const BinaryFunction &BF) const {
 
   return BinaryFunctionPass::shouldOptimize(BF);
 }
 
 void ReorderBasicBlocks::runOnFunctions(BinaryContext &BC) {
   if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE)
     return;
 
-  std::atomic<uint64_t> ModifiedFuncCount{0};
+  std::atomic_uint64_t ModifiedFuncCount(0);
+  std::mutex FunctionEditDistanceMutex;
+  DenseMap<const BinaryFunction *, uint64_t> FunctionEditDistance;
 
   ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
+    SmallVector<const BinaryBasicBlock *, 0> OldBlockOrder;
+    if (opts::PrintFuncStat > 0)
+      llvm::copy(BF.getLayout().blocks(), std::back_inserter(OldBlockOrder));
+
+    const bool LayoutChanged =
         modifyFunctionLayout(BF, opts::ReorderBlocks, opts::MinBranchClusters);
-    if (BF.getLayout().hasLayoutChanged())
-      ++ModifiedFuncCount;
+    if (LayoutChanged) {
+      ModifiedFuncCount.fetch_add(1, std::memory_order_relaxed);
+      if (opts::PrintFuncStat > 0) {
+        const uint64_t Distance = BF.getLayout().getEditDistance(OldBlockOrder);
+        std::lock_guard<std::mutex> Lock(FunctionEditDistanceMutex);
+        FunctionEditDistance[&BF] = Distance;
+      }
+    }
   };
 
   ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
     return !shouldOptimize(BF);
   };
 
   ParallelUtilities::runOnEachFunction(
       BC, ParallelUtilities::SchedulingPolicy::SP_BB_LINEAR, WorkFun, SkipFunc,
       "ReorderBasicBlocks");
 
   outs() << "BOLT-INFO: basic block reordering modified layout of "
-         << format("%zu (%.2lf%%) functions\n", ModifiedFuncCount.load(),
-                   100.0 * ModifiedFuncCount.load() /
+         << format("%zu (%.2lf%%) functions\n",
+                   ModifiedFuncCount.load(std::memory_order_relaxed),
+                   100.0 * ModifiedFuncCount.load(std::memory_order_relaxed) /
                        BC.getBinaryFunctions().size());
 
   if (opts::PrintFuncStat > 0) {
     raw_ostream &OS = outs();
     // Copy all the values into vector in order to sort them
     std::map<uint64_t, BinaryFunction &> ScoreMap;
     auto &BFs = BC.getBinaryFunctions();
     for (auto It = BFs.begin(); It != BFs.end(); ++It)
       ScoreMap.insert(std::pair<uint64_t, BinaryFunction &>(
           It->second.getFunctionScore(), It->second));
 
     OS << "\nBOLT-INFO: Printing Function Statistics:\n\n";
     OS << "           There are " << BFs.size() << " functions in total. \n";
     OS << "           Number of functions being modified: "
-       << ModifiedFuncCount.load() << "\n";
+       << ModifiedFuncCount.load(std::memory_order_relaxed) << "\n";
     OS << "           User asks for detailed information on top "
        << opts::PrintFuncStat << " functions. (Ranked by function score)"
        << "\n\n";
     uint64_t I = 0;
     for (std::map<uint64_t, BinaryFunction &>::reverse_iterator Rit =
              ScoreMap.rbegin();
          Rit != ScoreMap.rend() && I < opts::PrintFuncStat; ++Rit, ++I) {
       BinaryFunction &Function = Rit->second;
 
       OS << "           Information for function of top: " << (I + 1) << ": \n";
       OS << "             Function Score is: " << Function.getFunctionScore()
          << "\n";
       OS << "             There are " << Function.size()
          << " number of blocks in this function.\n";
       OS << "             There are " << Function.getInstructionCount()
          << " number of instructions in this function.\n";
       OS << "             The edit distance for this function is: "
-         << Function.getLayout().getEditDistance() << "\n\n";
+         << FunctionEditDistance.lookup(&Function) << "\n\n";
     }
   }
 }
 
-void ReorderBasicBlocks::modifyFunctionLayout(BinaryFunction &BF,
+bool ReorderBasicBlocks::modifyFunctionLayout(BinaryFunction &BF,
                                               LayoutType Type,
                                               bool MinBranchClusters) const {
   if (BF.size() == 0 || Type == LT_NONE)
-    return;
+    return false;
 
   BinaryFunction::BasicBlockOrderType NewLayout;
   std::unique_ptr<ReorderAlgorithm> Algo;
 
   // Cannot do optimal layout without profile.
   if (Type != LT_REVERSE && !BF.hasValidProfile())
-    return;
+    return false;
 
   if (Type == LT_REVERSE) {
     Algo.reset(new ReverseReorderAlgorithm());
   } else if (BF.size() <= opts::TSPThreshold && Type != LT_OPTIMIZE_SHUFFLE) {
     // Work on optimal solution if problem is small enough
     LLVM_DEBUG(dbgs() << "finding optimal block layout for " << BF << "\n");
     Algo.reset(new TSPReorderAlgorithm());
   } else {
if (Type == LT_REVERSE) {
 
     default:
       llvm_unreachable("unexpected layout type");
     }
   }
 
   Algo->reorderBasicBlocks(BF, NewLayout);
 
-  BF.getLayout().update(NewLayout);
+  return BF.getLayout().update(NewLayout);
 }
 
 void FixupBranches::runOnFunctions(BinaryContext &BC) {
   for (auto &It : BC.getBinaryFunctions()) {
     BinaryFunction &Function = It.second;
     if (!BC.shouldEmit(Function) || !Function.isSimple())
       continue;