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 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 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 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 NewLayout) { - PreviousBlocks = std::move(Blocks); - PreviousFragments = std::move(Fragments); +bool FunctionLayout::update(const ArrayRef 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(PreviousBlocks, Blocks); +uint64_t FunctionLayout::getEditDistance( + const ArrayRef OldBlockOrder) const { + return ComputeEditDistance(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 +#include #include #include @@ -388,12 +390,25 @@ if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE) return; - std::atomic ModifiedFuncCount{0}; + std::atomic_uint64_t ModifiedFuncCount(0); + std::mutex FunctionEditDistanceMutex; + DenseMap FunctionEditDistance; ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) { - modifyFunctionLayout(BF, opts::ReorderBlocks, opts::MinBranchClusters); - if (BF.getLayout().hasLayoutChanged()) - ++ModifiedFuncCount; + SmallVector 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 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 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) {