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"bolt/Utils/CommandLineOpts.h"
#include"llvm/Support/CommandLine.h"
#include<atomic>
#include<mutex>
#include<numeric>
#include<vector>

#defineDEBUG_TYPE"bolt-opts"

usingnamespacellvm;
usingnamespacebolt;

staticconstchar *dynoStatsOptName(const bolt::DynoStats::Category C) {
assert(C > bolt::DynoStats::FIRST_DYNO_STAT &&
 C < DynoStats::LAST_DYNO_STAT && "Unexpected dyno stat category.");

static std::string OptNames[bolt::DynoStats::LAST_DYNO_STAT + 1];

 OptNames[C] = bolt::DynoStats::Description(C);

std::replace(OptNames[C].begin(), OptNames[C].end(), '', '-');

return OptNames[C].c_str();
}

namespaceopts {

extern cl::OptionCategory BoltCategory;
extern cl::OptionCategory BoltOptCategory;

extern cl::opt<unsigned> Verbosity;
extern cl::opt<bool> EnableBAT;
extern cl::opt<unsigned> ExecutionCountThreshold;
extern cl::opt<bool> UpdateDebugSections;
extern cl::opt<bolt::ReorderFunctions::ReorderType> ReorderFunctions;

enum DynoStatsSortOrder : char {
 Ascending,
 Descending
};

static cl::opt<DynoStatsSortOrder> DynoStatsSortOrderOpt(
"print-sorted-by-order",
cl::desc("use ascending or descending order when printing functions "
"ordered by dyno stats"),
 cl::init(DynoStatsSortOrder::Descending), cl::cat(BoltOptCategory));

cl::list<std::string>
HotTextMoveSections("hot-text-move-sections",
cl::desc("list of sections containing functions used for hugifying hot text. "
"BOLT makes sure these functions are not placed on the same page as "
"the hot text. (default=\'.stub,.mover\')."),
 cl::value_desc("sec1,sec2,sec3,..."),
 cl::CommaSeparated,
 cl::ZeroOrMore,
 cl::cat(BoltCategory));

boolisHotTextMover(const BinaryFunction &Function) {
for (std::string &SectionName : opts::HotTextMoveSections) {
if (Function.getOriginSectionName() &&
 *Function.getOriginSectionName() == SectionName)
returntrue;
 }

returnfalse;
}

static cl::opt<bool> MinBranchClusters(
"min-branch-clusters",
cl::desc("use a modified clustering algorithm geared towards minimizing "
"branches"),
 cl::Hidden, cl::cat(BoltOptCategory));

static cl::list<Peepholes::PeepholeOpts> Peepholes(
"peepholes", cl::CommaSeparated, cl::desc("enable peephole optimizations"),
 cl::value_desc("opt1,opt2,opt3,..."),
 cl::values(clEnumValN(Peepholes::PEEP_NONE, "none", "disable peepholes"),
 clEnumValN(Peepholes::PEEP_DOUBLE_JUMPS, "double-jumps",
"remove double jumps when able"),
 clEnumValN(Peepholes::PEEP_TAILCALL_TRAPS, "tailcall-traps",
"insert tail call traps"),
 clEnumValN(Peepholes::PEEP_USELESS_BRANCHES, "useless-branches",
"remove useless conditional branches"),
 clEnumValN(Peepholes::PEEP_ALL, "all",
"enable all peephole optimizations")),
 cl::ZeroOrMore, cl::cat(BoltOptCategory));

static cl::opt<unsigned>
PrintFuncStat("print-function-statistics",
cl::desc("print statistics about basic block ordering"),
 cl::init(0), cl::cat(BoltOptCategory));

static cl::opt<bool> PrintLargeFunctions(
"print-large-functions",
cl::desc("print functions that could not be overwritten due to excessive "
"size"),
 cl::init(false), cl::cat(BoltOptCategory));

static cl::list<bolt::DynoStats::Category>
PrintSortedBy("print-sorted-by", cl::CommaSeparated,
cl::desc("print functions sorted by order of dyno stats"),
 cl::value_desc("key1,key2,key3,..."),
 cl::values(
#defineD(name, description, ...) \
clEnumValN(bolt::DynoStats::name, dynoStatsOptName(bolt::DynoStats::name), \
 description),
 REAL_DYNO_STATS
#undef D
clEnumValN(bolt::DynoStats::LAST_DYNO_STAT, "all",
"sorted by all names")),
 cl::ZeroOrMore, cl::cat(BoltOptCategory));

static cl::opt<bool>
PrintUnknown("print-unknown",
cl::desc("print names of functions with unknown control flow"),
 cl::cat(BoltCategory), cl::Hidden);

static cl::opt<bool>
PrintUnknownCFG("print-unknown-cfg",
cl::desc("dump CFG of functions with unknown control flow"),
 cl::cat(BoltCategory), cl::ReallyHidden);

// Please MSVC19 with a forward declaration: otherwise it reports an error about
// an undeclared variable inside a callback.
extern cl::opt<bolt::ReorderBasicBlocks::LayoutType> ReorderBlocks;
cl::opt<bolt::ReorderBasicBlocks::LayoutType> ReorderBlocks(
"reorder-blocks", cl::desc("change layout of basic blocks in a function"),
 cl::init(bolt::ReorderBasicBlocks::LT_NONE),
 cl::values(
clEnumValN(bolt::ReorderBasicBlocks::LT_NONE, "none",
"do not reorder basic blocks"),
 clEnumValN(bolt::ReorderBasicBlocks::LT_REVERSE, "reverse",
"layout blocks in reverse order"),
 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE, "normal",
"perform optimal layout based on profile"),
 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE_BRANCH,
"branch-predictor",
"perform optimal layout prioritizing branch "
"predictions"),
 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE_CACHE, "cache",
"perform optimal layout prioritizing I-cache "
"behavior"),
 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE_CACHE_PLUS, "cache+",
"perform layout optimizing I-cache behavior"),
 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE_EXT_TSP, "ext-tsp",
"perform layout optimizing I-cache behavior"),
 clEnumValN(bolt::ReorderBasicBlocks::LT_OPTIMIZE_SHUFFLE,
"cluster-shuffle", "perform random layout of clusters")),
 cl::ZeroOrMore, cl::cat(BoltOptCategory),
 cl::callback([](const bolt::ReorderBasicBlocks::LayoutType &option) {
if (option == bolt::ReorderBasicBlocks::LT_OPTIMIZE_CACHE_PLUS) {
errs() << "BOLT-WARNING: '-reorder-blocks=cache+' is deprecated, please"
 << " use '-reorder-blocks=ext-tsp' instead\n";
 ReorderBlocks = bolt::ReorderBasicBlocks::LT_OPTIMIZE_EXT_TSP;
 }
 }));

static cl::opt<unsigned> ReportBadLayout(
"report-bad-layout",
cl::desc("print top <uint> functions with suboptimal code layout on input"),
 cl::init(0), cl::Hidden, cl::cat(BoltOptCategory));

static cl::opt<bool>
ReportStaleFuncs("report-stale",
cl::desc("print the list of functions with stale profile"),
 cl::Hidden, cl::cat(BoltOptCategory));

enum SctcModes : char {
 SctcAlways,
 SctcPreserveDirection,
 SctcHeuristic
};

static cl::opt<SctcModes>
SctcMode("sctc-mode",
cl::desc("mode for simplify conditional tail calls"),
 cl::init(SctcAlways),
 cl::values(clEnumValN(SctcAlways, "always", "always perform sctc"),
 clEnumValN(SctcPreserveDirection,
"preserve",
"only perform sctc when branch direction is "
"preserved"),
 clEnumValN(SctcHeuristic,
"heuristic",
"use branch prediction data to control sctc")),
 cl::ZeroOrMore,
 cl::cat(BoltOptCategory));

static cl::opt<unsigned>
StaleThreshold("stale-threshold",
cl::desc(
"maximum percentage of stale functions to tolerate (default: 100)"),
 cl::init(100),
 cl::Hidden,
 cl::cat(BoltOptCategory));

static cl::opt<unsigned> TSPThreshold(
"tsp-threshold",
cl::desc(
"maximum number of hot basic blocks in a function for which to use "
"a precise TSP solution while re-ordering basic blocks"),
 cl::init(10), cl::Hidden, cl::cat(BoltOptCategory));

static cl::opt<unsigned> TopCalledLimit(
"top-called-limit",
cl::desc("maximum number of functions to print in top called "
"functions section"),
 cl::init(100), cl::Hidden, cl::cat(BoltCategory));

// Profile density options, synced with llvm-profgen/ProfileGenerator.cpp
static cl::opt<int> ProfileDensityCutOffHot(
"profile-density-cutoff-hot", cl::init(990000),
 cl::desc("Total samples cutoff for functions used to calculate "
"profile density."));

static cl::opt<double> ProfileDensityThreshold(
"profile-density-threshold", cl::init(60),
 cl::desc("If the profile density is below the given threshold, it "
"will be suggested to increase the sampling rate."),
 cl::Optional);

} // namespace opts

namespacellvm {
namespacebolt {

boolBinaryFunctionPass::shouldOptimize(const BinaryFunction &BF) const {
return BF.isSimple() && BF.getState() == BinaryFunction::State::CFG &&
 !BF.isIgnored();
}

boolBinaryFunctionPass::shouldPrint(const BinaryFunction &BF) const {
return BF.isSimple() && !BF.isIgnored();
}

voidNormalizeCFG::runOnFunction(BinaryFunction &BF) {
uint64_t NumRemoved = 0;
uint64_t NumDuplicateEdges = 0;
uint64_t NeedsFixBranches = 0;
for (BinaryBasicBlock &BB : BF) {
if (!BB.empty())
continue;

if (BB.isEntryPoint() || BB.isLandingPad())
continue;

// Handle a dangling empty block.
if (BB.succ_size() == 0) {
// If an empty dangling basic block has a predecessor, it could be a
// result of codegen for __builtin_unreachable. In such case, do not
// remove the block.
if (BB.pred_size() == 0) {
 BB.markValid(false);
 ++NumRemoved;
 }
continue;
 }

// The block should have just one successor.
 BinaryBasicBlock *Successor = BB.getSuccessor();
assert(Successor && "invalid CFG encountered");

// Redirect all predecessors to the successor block.
while (!BB.pred_empty()) {
 BinaryBasicBlock *Predecessor = *BB.pred_begin();
if (Predecessor->hasJumpTable())
break;

if (Predecessor == Successor)
break;

 BinaryBasicBlock::BinaryBranchInfo &BI = Predecessor->getBranchInfo(BB);
 Predecessor->replaceSuccessor(&BB, Successor, BI.Count,
 BI.MispredictedCount);
// We need to fix branches even if we failed to replace all successors
// and remove the block.
 NeedsFixBranches = true;
 }

if (BB.pred_empty()) {
 BB.removeAllSuccessors();
 BB.markValid(false);
 ++NumRemoved;
 }
 }

if (NumRemoved)
 BF.eraseInvalidBBs();

// Check for duplicate successors. Do it after the empty block elimination as
// we can get more duplicate successors.
for (BinaryBasicBlock &BB : BF)
if (!BB.hasJumpTable() && BB.succ_size() == 2 &&
 BB.getConditionalSuccessor(false) == BB.getConditionalSuccessor(true))
 ++NumDuplicateEdges;

// fixBranches() will get rid of duplicate edges and update jump instructions.
if (NumDuplicateEdges || NeedsFixBranches)
 BF.fixBranches();

 NumDuplicateEdgesMerged += NumDuplicateEdges;
 NumBlocksRemoved += NumRemoved;
}

Error NormalizeCFG::runOnFunctions(BinaryContext &BC) {
ParallelUtilities::runOnEachFunction(
 BC, ParallelUtilities::SchedulingPolicy::SP_BB_LINEAR,
 [&](BinaryFunction &BF) { runOnFunction(BF); },
 [&](const BinaryFunction &BF) { return !shouldOptimize(BF); },
"NormalizeCFG");
if (NumBlocksRemoved)
 BC.outs() << "BOLT-INFO: removed " << NumBlocksRemoved << " empty block"
 << (NumBlocksRemoved == 1 ? "" : "s") << '\n';
if (NumDuplicateEdgesMerged)
 BC.outs() << "BOLT-INFO: merged " << NumDuplicateEdgesMerged
 << " duplicate CFG edge"
 << (NumDuplicateEdgesMerged == 1 ? "" : "s") << '\n';
returnError::success();
}

voidEliminateUnreachableBlocks::runOnFunction(BinaryFunction &Function) {
 BinaryContext &BC = Function.getBinaryContext();
unsigned Count;
uint64_t Bytes;
 Function.markUnreachableBlocks();
LLVM_DEBUG({
for (BinaryBasicBlock &BB : Function) {
if (!BB.isValid()) {
dbgs() << "BOLT-INFO: UCE found unreachable block " << BB.getName()
 << " in function " << Function << "\n";
 Function.dump();
 }
 }
 });
 BinaryContext::IndependentCodeEmitter Emitter =
 BC.createIndependentMCCodeEmitter();
std::tie(Count, Bytes) = Function.eraseInvalidBBs(Emitter.MCE.get());
 DeletedBlocks += Count;
 DeletedBytes += Bytes;
if (Count) {
auto L = BC.scopeLock();
 Modified.insert(&Function);
if (opts::Verbosity > 0)
 BC.outs() << "BOLT-INFO: removed " << Count
 << " dead basic block(s) accounting for " << Bytes
 << " bytes in function " << Function << '\n';
 }
}

Error EliminateUnreachableBlocks::runOnFunctions(BinaryContext &BC) {
 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
runOnFunction(BF);
 };

 ParallelUtilities::PredicateTy SkipPredicate = [&](const BinaryFunction &BF) {
return !shouldOptimize(BF) || BF.getLayout().block_empty();
 };

ParallelUtilities::runOnEachFunction(
 BC, ParallelUtilities::SchedulingPolicy::SP_CONSTANT, WorkFun,
 SkipPredicate, "elimininate-unreachable");

if (DeletedBlocks)
 BC.outs() << "BOLT-INFO: UCE removed " << DeletedBlocks << " blocks and "
 << DeletedBytes << " bytes of code\n";
returnError::success();
}

boolReorderBasicBlocks::shouldPrint(const BinaryFunction &BF) const {
return (BinaryFunctionPass::shouldPrint(BF) &&
 opts::ReorderBlocks != ReorderBasicBlocks::LT_NONE);
}

boolReorderBasicBlocks::shouldOptimize(const BinaryFunction &BF) const {
// Apply execution count threshold
if (BF.getKnownExecutionCount() < opts::ExecutionCountThreshold)
returnfalse;

returnBinaryFunctionPass::shouldOptimize(BF);
}

Error ReorderBasicBlocks::runOnFunctions(BinaryContext &BC) {
if (opts::ReorderBlocks == ReorderBasicBlocks::LT_NONE)
returnError::success();

 std::atomic_uint64_tModifiedFuncCount(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));

constbool LayoutChanged =
modifyFunctionLayout(BF, opts::ReorderBlocks, opts::MinBranchClusters);
if (LayoutChanged) {
 ModifiedFuncCount.fetch_add(1, std::memory_order_relaxed);
if (opts::PrintFuncStat > 0) {
constuint64_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");
constsize_t NumAllProfiledFunctions =
 BC.NumProfiledFuncs + BC.NumStaleProfileFuncs;

 BC.outs() << "BOLT-INFO: basic block reordering modified layout of "
 << format(
"%zu functions (%.2lf%% of profiled, %.2lf%% of total)\n",
 ModifiedFuncCount.load(std::memory_order_relaxed),
100.0 * ModifiedFuncCount.load(std::memory_order_relaxed) /
 NumAllProfiledFunctions,
100.0 * ModifiedFuncCount.load(std::memory_order_relaxed) /
 BC.getBinaryFunctions().size());

if (opts::PrintFuncStat > 0) {
 raw_ostream &OS = BC.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(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: "
 << FunctionEditDistance.lookup(&Function) << "\n\n";
 }
 }
returnError::success();
}

boolReorderBasicBlocks::modifyFunctionLayout(BinaryFunction &BF,
 LayoutType Type,
bool MinBranchClusters) const {
if (BF.size() == 0 || Type == LT_NONE)
returnfalse;

 BinaryFunction::BasicBlockOrderType NewLayout;
 std::unique_ptr<ReorderAlgorithm> Algo;

// Cannot do optimal layout without profile.
if (Type != LT_REVERSE && !BF.hasValidProfile())
returnfalse;

if (Type == LT_REVERSE) {
 Algo.reset(newReverseReorderAlgorithm());
 } elseif (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(newTSPReorderAlgorithm());
 } else {
LLVM_DEBUG(dbgs() << "running block layout heuristics on " << BF << "\n");

 std::unique_ptr<ClusterAlgorithm> CAlgo;
if (MinBranchClusters)
 CAlgo.reset(newMinBranchGreedyClusterAlgorithm());
else
 CAlgo.reset(newPHGreedyClusterAlgorithm());

switch (Type) {
case LT_OPTIMIZE:
 Algo.reset(newOptimizeReorderAlgorithm(std::move(CAlgo)));
break;

case LT_OPTIMIZE_BRANCH:
 Algo.reset(newOptimizeBranchReorderAlgorithm(std::move(CAlgo)));
break;

case LT_OPTIMIZE_CACHE:
 Algo.reset(newOptimizeCacheReorderAlgorithm(std::move(CAlgo)));
break;

case LT_OPTIMIZE_EXT_TSP:
 Algo.reset(newExtTSPReorderAlgorithm());
break;

case LT_OPTIMIZE_SHUFFLE:
 Algo.reset(newRandomClusterReorderAlgorithm(std::move(CAlgo)));
break;

default:
llvm_unreachable("unexpected layout type");
 }
 }

 Algo->reorderBasicBlocks(BF, NewLayout);

return BF.getLayout().update(NewLayout);
}

Error FixupBranches::runOnFunctions(BinaryContext &BC) {
for (auto &It : BC.getBinaryFunctions()) {
 BinaryFunction &Function = It.second;
if (!BC.shouldEmit(Function) || !Function.isSimple())
continue;

 Function.fixBranches();
 }
returnError::success();
}

Error FinalizeFunctions::runOnFunctions(BinaryContext &BC) {
 std::atomic<bool> HasFatal{false};
 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
if (!BF.finalizeCFIState()) {
if (BC.HasRelocations) {
 BC.errs() << "BOLT-ERROR: unable to fix CFI state for function " << BF
 << ". Exiting.\n";
 HasFatal = true;
return;
 }
 BF.setSimple(false);
return;
 }

 BF.setFinalized();

// Update exception handling information.
 BF.updateEHRanges();
 };

 ParallelUtilities::PredicateTy SkipPredicate = [&](const BinaryFunction &BF) {
return !BC.shouldEmit(BF);
 };

ParallelUtilities::runOnEachFunction(
 BC, ParallelUtilities::SchedulingPolicy::SP_CONSTANT, WorkFun,
 SkipPredicate, "FinalizeFunctions");
if (HasFatal)
returncreateFatalBOLTError("finalize CFI state failure");
returnError::success();
}

Error CheckLargeFunctions::runOnFunctions(BinaryContext &BC) {
if (BC.HasRelocations)
returnError::success();

// If the function wouldn't fit, mark it as non-simple. Otherwise, we may emit
// incorrect meta data.
 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
uint64_t HotSize, ColdSize;
std::tie(HotSize, ColdSize) =
 BC.calculateEmittedSize(BF, /*FixBranches=*/false);
uint64_t MainFragmentSize = HotSize;
if (BF.hasIslandsInfo()) {
 MainFragmentSize +=
offsetToAlignment(BF.getAddress() + MainFragmentSize,
Align(BF.getConstantIslandAlignment()));
 MainFragmentSize += BF.estimateConstantIslandSize();
 }
if (MainFragmentSize > BF.getMaxSize()) {
if (opts::PrintLargeFunctions)
 BC.outs() << "BOLT-INFO: " << BF << " size of " << MainFragmentSize
 << " bytes exceeds allocated space by "
 << (MainFragmentSize - BF.getMaxSize()) << " bytes\n";
 BF.setSimple(false);
 }
 };

 ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
return !shouldOptimize(BF);
 };

ParallelUtilities::runOnEachFunction(
 BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR, WorkFun,
 SkipFunc, "CheckLargeFunctions");

returnError::success();
}

boolCheckLargeFunctions::shouldOptimize(const BinaryFunction &BF) const {
// Unlike other passes, allow functions in non-CFG state.
return BF.isSimple() && !BF.isIgnored();
}

Error LowerAnnotations::runOnFunctions(BinaryContext &BC) {
// Convert GnuArgsSize annotations into CFIs.
for (BinaryFunction *BF : BC.getAllBinaryFunctions()) {
for (FunctionFragment &FF : BF->getLayout().fragments()) {
// Reset at the start of the new fragment.
int64_t CurrentGnuArgsSize = 0;

for (BinaryBasicBlock *const BB : FF) {
for (auto II = BB->begin(); II != BB->end(); ++II) {
if (!BF->usesGnuArgsSize() || !BC.MIB->isInvoke(*II))
continue;

constint64_t NewGnuArgsSize = BC.MIB->getGnuArgsSize(*II);
assert(NewGnuArgsSize >= 0 && "Expected non-negative GNU_args_size.");
if (NewGnuArgsSize == CurrentGnuArgsSize)
continue;

auto InsertII = BF->addCFIInstruction(
 BB, II,
MCCFIInstruction::createGnuArgsSize(nullptr, NewGnuArgsSize));
 CurrentGnuArgsSize = NewGnuArgsSize;
 II = std::next(InsertII);
 }
 }
 }
 }
returnError::success();
}

// Check for dirty state in MCSymbol objects that might be a consequence
// of running calculateEmittedSize() in parallel, during split functions
// pass. If an inconsistent state is found (symbol already registered or
// already defined), clean it.
Error CleanMCState::runOnFunctions(BinaryContext &BC) {
 MCContext &Ctx = *BC.Ctx;
for (constauto &SymMapEntry : Ctx.getSymbols()) {
const MCSymbol *S = SymMapEntry.getValue().Symbol;
if (!S)
continue;
if (S->isDefined()) {
LLVM_DEBUG(dbgs() << "BOLT-DEBUG: Symbol \"" << S->getName()
 << "\" is already defined\n");
const_cast<MCSymbol *>(S)->setUndefined();
 }
if (S->isRegistered()) {
LLVM_DEBUG(dbgs() << "BOLT-DEBUG: Symbol \"" << S->getName()
 << "\" is already registered\n");
const_cast<MCSymbol *>(S)->setIsRegistered(false);
 }
LLVM_DEBUG(if (S->isVariable()) {
dbgs() << "BOLT-DEBUG: Symbol \"" << S->getName() << "\" is variable\n";
 });
 }
returnError::success();
}

// This peephole fixes jump instructions that jump to another basic
// block with a single jump instruction, e.g.
//
// B0: ...
// jmp B1 (or jcc B1)
//
// B1: jmp B2
//
// ->
//
// B0: ...
// jmp B2 (or jcc B2)
//
staticuint64_tfixDoubleJumps(BinaryFunction &Function, bool MarkInvalid) {
uint64_t NumDoubleJumps = 0;

 MCContext *Ctx = Function.getBinaryContext().Ctx.get();
 MCPlusBuilder *MIB = Function.getBinaryContext().MIB.get();
for (BinaryBasicBlock &BB : Function) {
auto checkAndPatch = [&](BinaryBasicBlock *Pred, BinaryBasicBlock *Succ,
const MCSymbol *SuccSym,
 std::optional<uint32_t> Offset) {
// Ignore infinite loop jumps or fallthrough tail jumps.
if (Pred == Succ || Succ == &BB)
returnfalse;

if (Succ) {
const MCSymbol *TBB = nullptr;
const MCSymbol *FBB = nullptr;
 MCInst *CondBranch = nullptr;
 MCInst *UncondBranch = nullptr;
bool Res = Pred->analyzeBranch(TBB, FBB, CondBranch, UncondBranch);
if (!Res) {
LLVM_DEBUG(dbgs() << "analyzeBranch failed in peepholes in block:\n";
 Pred->dump());
returnfalse;
 }
 Pred->replaceSuccessor(&BB, Succ);

// We must patch up any existing branch instructions to match up
// with the new successor.
assert((CondBranch || (!CondBranch && Pred->succ_size() == 1)) &&
"Predecessor block has inconsistent number of successors");
if (CondBranch && MIB->getTargetSymbol(*CondBranch) == BB.getLabel()) {
 MIB->replaceBranchTarget(*CondBranch, Succ->getLabel(), Ctx);
 } elseif (UncondBranch &&
 MIB->getTargetSymbol(*UncondBranch) == BB.getLabel()) {
 MIB->replaceBranchTarget(*UncondBranch, Succ->getLabel(), Ctx);
 } elseif (!UncondBranch) {
assert(Function.getLayout().getBasicBlockAfter(Pred, false) != Succ &&
"Don't add an explicit jump to a fallthrough block.");
 Pred->addBranchInstruction(Succ);
 }
 } else {
// Succ will be null in the tail call case. In this case we
// need to explicitly add a tail call instruction.
 MCInst *Branch = Pred->getLastNonPseudoInstr();
if (Branch && MIB->isUnconditionalBranch(*Branch)) {
assert(MIB->getTargetSymbol(*Branch) == BB.getLabel());
 Pred->removeSuccessor(&BB);
 Pred->eraseInstruction(Pred->findInstruction(Branch));
 Pred->addTailCallInstruction(SuccSym);
if (Offset) {
 MCInst *TailCall = Pred->getLastNonPseudoInstr();
assert(TailCall);
 MIB->setOffset(*TailCall, *Offset);
 }
 } else {
returnfalse;
 }
 }

 ++NumDoubleJumps;
LLVM_DEBUG(dbgs() << "Removed double jump in " << Function << " from "
 << Pred->getName() << " -> " << BB.getName() << " to "
 << Pred->getName() << " -> " << SuccSym->getName()
 << (!Succ ? " (tail)\n" : "\n"));

returntrue;
 };

if (BB.getNumNonPseudos() != 1 || BB.isLandingPad())
continue;

 MCInst *Inst = BB.getFirstNonPseudoInstr();
constbool IsTailCall = MIB->isTailCall(*Inst);

if (!MIB->isUnconditionalBranch(*Inst) && !IsTailCall)
continue;

// If we operate after SCTC make sure it's not a conditional tail call.
if (IsTailCall && MIB->isConditionalBranch(*Inst))
continue;

const MCSymbol *SuccSym = MIB->getTargetSymbol(*Inst);
 BinaryBasicBlock *Succ = BB.getSuccessor();

if (((!Succ || &BB == Succ) && !IsTailCall) || (IsTailCall && !SuccSym))
continue;

 std::vector<BinaryBasicBlock *> Preds = {BB.pred_begin(), BB.pred_end()};

for (BinaryBasicBlock *Pred : Preds) {
if (Pred->isLandingPad())
continue;

if (Pred->getSuccessor() == &BB ||
 (Pred->getConditionalSuccessor(true) == &BB && !IsTailCall) ||
 Pred->getConditionalSuccessor(false) == &BB)
if (checkAndPatch(Pred, Succ, SuccSym, MIB->getOffset(*Inst)) &&
 MarkInvalid)
 BB.markValid(BB.pred_size() != 0 || BB.isLandingPad() ||
 BB.isEntryPoint());
 }
 }

return NumDoubleJumps;
}

boolSimplifyConditionalTailCalls::shouldRewriteBranch(
const BinaryBasicBlock *PredBB, const MCInst &CondBranch,
const BinaryBasicBlock *BB, constbool DirectionFlag) {
if (BeenOptimized.count(PredBB))
returnfalse;

constbool IsForward = BinaryFunction::isForwardBranch(PredBB, BB);

if (IsForward)
 ++NumOrigForwardBranches;
else
 ++NumOrigBackwardBranches;

if (opts::SctcMode == opts::SctcAlways)
returntrue;

if (opts::SctcMode == opts::SctcPreserveDirection)
return IsForward == DirectionFlag;

const ErrorOr<std::pair<double, double>> Frequency =
 PredBB->getBranchStats(BB);

// It's ok to rewrite the conditional branch if the new target will be
// a backward branch.

// If no data available for these branches, then it should be ok to
// do the optimization since it will reduce code size.
if (Frequency.getError())
returntrue;

// TODO: should this use misprediction frequency instead?
constbool Result = (IsForward && Frequency.get().first >= 0.5) ||
 (!IsForward && Frequency.get().first <= 0.5);

return Result == DirectionFlag;
}

uint64_tSimplifyConditionalTailCalls::fixTailCalls(BinaryFunction &BF) {
// Need updated indices to correctly detect branch' direction.
 BF.getLayout().updateLayoutIndices();
 BF.markUnreachableBlocks();

 MCPlusBuilder *MIB = BF.getBinaryContext().MIB.get();
 MCContext *Ctx = BF.getBinaryContext().Ctx.get();
uint64_t NumLocalCTCCandidates = 0;
uint64_t NumLocalCTCs = 0;
uint64_t LocalCTCTakenCount = 0;
uint64_t LocalCTCExecCount = 0;
 std::vector<std::pair<BinaryBasicBlock *, const BinaryBasicBlock *>>
 NeedsUncondBranch;

// Will block be deleted by UCE?
auto isValid = [](const BinaryBasicBlock *BB) {
return (BB->pred_size() != 0 || BB->isLandingPad() || BB->isEntryPoint());
 };

for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
// Locate BB with a single direct tail-call instruction.
if (BB->getNumNonPseudos() != 1)
continue;

 MCInst *Instr = BB->getFirstNonPseudoInstr();
if (!MIB->isTailCall(*Instr) || MIB->isConditionalBranch(*Instr))
continue;

const MCSymbol *CalleeSymbol = MIB->getTargetSymbol(*Instr);
if (!CalleeSymbol)
continue;

// Detect direction of the possible conditional tail call.
constbool IsForwardCTC = BF.isForwardCall(CalleeSymbol);

// Iterate through all predecessors.
for (BinaryBasicBlock *PredBB : BB->predecessors()) {
 BinaryBasicBlock *CondSucc = PredBB->getConditionalSuccessor(true);
if (!CondSucc)
continue;

 ++NumLocalCTCCandidates;

const MCSymbol *TBB = nullptr;
const MCSymbol *FBB = nullptr;
 MCInst *CondBranch = nullptr;
 MCInst *UncondBranch = nullptr;
bool Result = PredBB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch);

// analyzeBranch() can fail due to unusual branch instructions, e.g. jrcxz
if (!Result) {
LLVM_DEBUG(dbgs() << "analyzeBranch failed in SCTC in block:\n";
 PredBB->dump());
continue;
 }

assert(Result && "internal error analyzing conditional branch");
assert(CondBranch && "conditional branch expected");

// Skip dynamic branches for now.
if (BF.getBinaryContext().MIB->isDynamicBranch(*CondBranch))
continue;

// It's possible that PredBB is also a successor to BB that may have
// been processed by a previous iteration of the SCTC loop, in which
// case it may have been marked invalid. We should skip rewriting in
// this case.
if (!PredBB->isValid()) {
assert(PredBB->isSuccessor(BB) &&
"PredBB should be valid if it is not a successor to BB");
continue;
 }

// We don't want to reverse direction of the branch in new order
// without further profile analysis.
constbool DirectionFlag = CondSucc == BB ? IsForwardCTC : !IsForwardCTC;
if (!shouldRewriteBranch(PredBB, *CondBranch, BB, DirectionFlag))
continue;

// Record this block so that we don't try to optimize it twice.
 BeenOptimized.insert(PredBB);

uint64_t Count = 0;
if (CondSucc != BB) {
// Patch the new target address into the conditional branch.
 MIB->reverseBranchCondition(*CondBranch, CalleeSymbol, Ctx);
// Since we reversed the condition on the branch we need to change
// the target for the unconditional branch or add a unconditional
// branch to the old target. This has to be done manually since
// fixupBranches is not called after SCTC.
 NeedsUncondBranch.emplace_back(PredBB, CondSucc);
 Count = PredBB->getFallthroughBranchInfo().Count;
 } else {
// Change destination of the conditional branch.
 MIB->replaceBranchTarget(*CondBranch, CalleeSymbol, Ctx);
 Count = PredBB->getTakenBranchInfo().Count;
 }
constuint64_t CTCTakenFreq =
 Count == BinaryBasicBlock::COUNT_NO_PROFILE ? 0 : Count;

// Annotate it, so "isCall" returns true for this jcc
 MIB->setConditionalTailCall(*CondBranch);
// Add info about the conditional tail call frequency, otherwise this
// info will be lost when we delete the associated BranchInfo entry
auto &CTCAnnotation =
 MIB->getOrCreateAnnotationAs<uint64_t>(*CondBranch, "CTCTakenCount");
 CTCAnnotation = CTCTakenFreq;
// Preserve Offset annotation, used in BAT.
// Instr is a direct tail call instruction that was created when CTCs are
// first expanded, and has the original CTC offset set.
if (std::optional<uint32_t> Offset = MIB->getOffset(*Instr))
 MIB->setOffset(*CondBranch, *Offset);

// Remove the unused successor which may be eliminated later
// if there are no other users.
 PredBB->removeSuccessor(BB);
// Update BB execution count
if (CTCTakenFreq && CTCTakenFreq <= BB->getKnownExecutionCount())
 BB->setExecutionCount(BB->getExecutionCount() - CTCTakenFreq);
elseif (CTCTakenFreq > BB->getKnownExecutionCount())
 BB->setExecutionCount(0);

 ++NumLocalCTCs;
 LocalCTCTakenCount += CTCTakenFreq;
 LocalCTCExecCount += PredBB->getKnownExecutionCount();
 }

// Remove the block from CFG if all predecessors were removed.
 BB->markValid(isValid(BB));
 }

// Add unconditional branches at the end of BBs to new successors
// as long as the successor is not a fallthrough.
for (auto &Entry : NeedsUncondBranch) {
 BinaryBasicBlock *PredBB = Entry.first;
const BinaryBasicBlock *CondSucc = Entry.second;

const MCSymbol *TBB = nullptr;
const MCSymbol *FBB = nullptr;
 MCInst *CondBranch = nullptr;
 MCInst *UncondBranch = nullptr;
 PredBB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch);

// Find the next valid block. Invalid blocks will be deleted
// so they shouldn't be considered fallthrough targets.
const BinaryBasicBlock *NextBlock =
 BF.getLayout().getBasicBlockAfter(PredBB, false);
while (NextBlock && !isValid(NextBlock))
 NextBlock = BF.getLayout().getBasicBlockAfter(NextBlock, false);

// Get the unconditional successor to this block.
const BinaryBasicBlock *PredSucc = PredBB->getSuccessor();
assert(PredSucc && "The other branch should be a tail call");

constbool HasFallthrough = (NextBlock && PredSucc == NextBlock);

if (UncondBranch) {
if (HasFallthrough)
 PredBB->eraseInstruction(PredBB->findInstruction(UncondBranch));
else
 MIB->replaceBranchTarget(*UncondBranch, CondSucc->getLabel(), Ctx);
 } elseif (!HasFallthrough) {
 MCInst Branch;
 MIB->createUncondBranch(Branch, CondSucc->getLabel(), Ctx);
 PredBB->addInstruction(Branch);
 }