diff --git a/bolt/include/bolt/Core/FunctionLayout.h b/bolt/include/bolt/Core/FunctionLayout.h
--- a/bolt/include/bolt/Core/FunctionLayout.h
+++ b/bolt/include/bolt/Core/FunctionLayout.h
@@ -145,8 +145,6 @@
/// `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.
@@ -174,12 +172,9 @@
/// 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();
@@ -196,7 +191,8 @@
/// 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
diff --git a/bolt/include/bolt/Passes/BinaryPasses.h b/bolt/include/bolt/Passes/BinaryPasses.h
--- a/bolt/include/bolt/Passes/BinaryPasses.h
+++ b/bolt/include/bolt/Passes/BinaryPasses.h
@@ -152,7 +152,9 @@
};
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:
diff --git a/bolt/lib/Core/FunctionLayout.cpp b/bolt/lib/Core/FunctionLayout.cpp
--- a/bolt/lib/Core/FunctionLayout.cpp
+++ b/bolt/lib/Core/FunctionLayout.cpp
@@ -76,18 +76,22 @@
}
}
-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();
@@ -106,19 +110,12 @@
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,
@@ -144,8 +141,9 @@
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
diff --git a/bolt/lib/Passes/BinaryPasses.cpp b/bolt/lib/Passes/BinaryPasses.cpp
--- a/bolt/lib/Passes/BinaryPasses.cpp
+++ b/bolt/lib/Passes/BinaryPasses.cpp
@@ -11,11 +11,13 @@
//===----------------------------------------------------------------------===//
#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>
@@ -388,12 +390,25 @@
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) {
- modifyFunctionLayout(BF, opts::ReorderBlocks, opts::MinBranchClusters);
- if (BF.getLayout().hasLayoutChanged())
- ++ModifiedFuncCount;
+ 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 (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) {
@@ -405,8 +420,9 @@
"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) {
@@ -421,7 +437,7 @@
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";
@@ -439,23 +455,23 @@
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());
@@ -500,7 +516,7 @@
Algo->reorderBasicBlocks(BF, NewLayout);
- BF.getLayout().update(NewLayout);
+ return BF.getLayout().update(NewLayout);
}
void FixupBranches::runOnFunctions(BinaryContext &BC) {