IndirectCallPromotion.cpp

//===- bolt/Passes/IndirectCallPromotion.cpp ------------------------------===//
//
// 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 the IndirectCallPromotion class.
//
//===----------------------------------------------------------------------===//

#include"bolt/Passes/IndirectCallPromotion.h"
#include"bolt/Core/BinaryFunctionCallGraph.h"
#include"bolt/Passes/DataflowInfoManager.h"
#include"bolt/Passes/Inliner.h"
#include"llvm/ADT/STLExtras.h"
#include"llvm/Support/CommandLine.h"
#include<iterator>

#defineDEBUG_TYPE"ICP"
#defineDEBUG_VERBOSE(Level, X) \
if (opts::Verbosity >= (Level)) { \
 X; \
 }

usingnamespacellvm;
usingnamespacebolt;

namespaceopts {

extern cl::OptionCategory BoltOptCategory;

extern cl::opt<IndirectCallPromotionType> ICP;
extern cl::opt<unsigned> Verbosity;
extern cl::opt<unsigned> ExecutionCountThreshold;

static cl::opt<unsigned> ICPJTRemainingPercentThreshold(
"icp-jt-remaining-percent-threshold",
cl::desc("The percentage threshold against remaining unpromoted indirect "
"call count for the promotion for jump tables"),
 cl::init(30), cl::ZeroOrMore, cl::Hidden, cl::cat(BoltOptCategory));

static cl::opt<unsigned> ICPJTTotalPercentThreshold(
"icp-jt-total-percent-threshold",
cl::desc(
"The percentage threshold against total count for the promotion for "
"jump tables"),
 cl::init(5), cl::Hidden, cl::cat(BoltOptCategory));

static cl::opt<unsigned> ICPCallsRemainingPercentThreshold(
"icp-calls-remaining-percent-threshold",
cl::desc("The percentage threshold against remaining unpromoted indirect "
"call count for the promotion for calls"),
 cl::init(50), cl::Hidden, cl::cat(BoltOptCategory));

static cl::opt<unsigned> ICPCallsTotalPercentThreshold(
"icp-calls-total-percent-threshold",
cl::desc(
"The percentage threshold against total count for the promotion for "
"calls"),
 cl::init(30), cl::Hidden, cl::cat(BoltOptCategory));

static cl::opt<unsigned> ICPMispredictThreshold(
"indirect-call-promotion-mispredict-threshold",
cl::desc("misprediction threshold for skipping ICP on an "
"indirect call"),
 cl::init(0), cl::cat(BoltOptCategory));

static cl::alias ICPMispredictThresholdAlias(
"icp-mp-threshold",
cl::desc("alias for --indirect-call-promotion-mispredict-threshold"),
 cl::aliasopt(ICPMispredictThreshold));

static cl::opt<bool> ICPUseMispredicts(
"indirect-call-promotion-use-mispredicts",
cl::desc("use misprediction frequency for determining whether or not ICP "
"should be applied at a callsite. The "
"-indirect-call-promotion-mispredict-threshold value will be used "
"by this heuristic"),
 cl::cat(BoltOptCategory));

static cl::alias ICPUseMispredictsAlias(
"icp-use-mp",
cl::desc("alias for --indirect-call-promotion-use-mispredicts"),
 cl::aliasopt(ICPUseMispredicts));

static cl::opt<unsigned>
ICPTopN("indirect-call-promotion-topn",
cl::desc("limit number of targets to consider when doing indirect "
"call promotion. 0 = no limit"),
 cl::init(3), cl::cat(BoltOptCategory));

static cl::alias
ICPTopNAlias("icp-topn",
cl::desc("alias for --indirect-call-promotion-topn"),
 cl::aliasopt(ICPTopN));

static cl::opt<unsigned> ICPCallsTopN(
"indirect-call-promotion-calls-topn",
cl::desc("limit number of targets to consider when doing indirect "
"call promotion on calls. 0 = no limit"),
 cl::init(0), cl::cat(BoltOptCategory));

static cl::alias ICPCallsTopNAlias(
"icp-calls-topn",
cl::desc("alias for --indirect-call-promotion-calls-topn"),
 cl::aliasopt(ICPCallsTopN));

static cl::opt<unsigned> ICPJumpTablesTopN(
"indirect-call-promotion-jump-tables-topn",
cl::desc("limit number of targets to consider when doing indirect "
"call promotion on jump tables. 0 = no limit"),
 cl::init(0), cl::cat(BoltOptCategory));

static cl::alias ICPJumpTablesTopNAlias(
"icp-jt-topn",
cl::desc("alias for --indirect-call-promotion-jump-tables-topn"),
 cl::aliasopt(ICPJumpTablesTopN));

static cl::opt<bool> EliminateLoads(
"icp-eliminate-loads",
cl::desc("enable load elimination using memory profiling data when "
"performing ICP"),
 cl::init(true), cl::cat(BoltOptCategory));

static cl::opt<unsigned> ICPTopCallsites(
"icp-top-callsites",
cl::desc("optimize hottest calls until at least this percentage of all "
"indirect calls frequency is covered. 0 = all callsites"),
 cl::init(99), cl::Hidden, cl::cat(BoltOptCategory));

static cl::list<std::string>
ICPFuncsList("icp-funcs", cl::CommaSeparated,
cl::desc("list of functions to enable ICP for"),
 cl::value_desc("func1,func2,func3,..."), cl::Hidden,
 cl::cat(BoltOptCategory));

static cl::opt<bool>
ICPOldCodeSequence("icp-old-code-sequence",
cl::desc("use old code sequence for promoted calls"),
 cl::Hidden, cl::cat(BoltOptCategory));

static cl::opt<bool> ICPJumpTablesByTarget(
"icp-jump-tables-targets",
cl::desc(
"for jump tables, optimize indirect jmp targets instead of indices"),
 cl::Hidden, cl::cat(BoltOptCategory));

static cl::alias
ICPJumpTablesByTargetAlias("icp-jt-targets",
cl::desc("alias for --icp-jump-tables-targets"),
 cl::aliasopt(ICPJumpTablesByTarget));

static cl::opt<bool> ICPPeelForInline(
"icp-inline", cl::desc("only promote call targets eligible for inlining"),
 cl::Hidden, cl::cat(BoltOptCategory));

} // namespace opts

#ifndef NDEBUG
staticboolverifyProfile(std::map<uint64_t, BinaryFunction> &BFs) {
bool IsValid = true;
for (auto &BFI : BFs) {
 BinaryFunction &BF = BFI.second;
if (!BF.isSimple())
continue;
for (const BinaryBasicBlock &BB : BF) {
auto BI = BB.branch_info_begin();
for (BinaryBasicBlock *SuccBB : BB.successors()) {
if (BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE && BI->Count > 0) {
if (BB.getKnownExecutionCount() == 0 ||
 SuccBB->getKnownExecutionCount() == 0) {
 BF.getBinaryContext().errs()
 << "BOLT-WARNING: profile verification failed after ICP for "
"function "
 << BF << '\n';
 IsValid = false;
 }
 }
 ++BI;
 }
 }
 }
return IsValid;
}
#endif

namespacellvm {
namespacebolt {

IndirectCallPromotion::Callsite::Callsite(BinaryFunction &BF,
const IndirectCallProfile &ICP)
 : From(BF.getSymbol()), To(ICP.Offset), Mispreds(ICP.Mispreds),
Branches(ICP.Count) {
if (ICP.Symbol) {
 To.Sym = ICP.Symbol;
 To.Addr = 0;
 }
}

voidIndirectCallPromotion::printDecision(
 llvm::raw_ostream &OS,
 std::vector<IndirectCallPromotion::Callsite> &Targets, unsigned N) const {
uint64_t TotalCount = 0;
uint64_t TotalMispreds = 0;
for (const Callsite &S : Targets) {
 TotalCount += S.Branches;
 TotalMispreds += S.Mispreds;
 }
if (!TotalCount)
 TotalCount = 1;
if (!TotalMispreds)
 TotalMispreds = 1;

 OS << "BOLT-INFO: ICP decision for call site with " << Targets.size()
 << " targets, Count = " << TotalCount << ", Mispreds = " << TotalMispreds
 << "\n";

size_t I = 0;
for (const Callsite &S : Targets) {
 OS << "Count = " << S.Branches << ", "
 << format("%.1f", (100.0 * S.Branches) / TotalCount) << ", "
 << "Mispreds = " << S.Mispreds << ", "
 << format("%.1f", (100.0 * S.Mispreds) / TotalMispreds);
if (I < N)
 OS << " * to be optimized *";
if (!S.JTIndices.empty()) {
 OS << " Indices:";
for (constuint64_t Idx : S.JTIndices)
 OS << "" << Idx;
 }
 OS << "\n";
 I += S.JTIndices.empty() ? 1 : S.JTIndices.size();
 }
}

// Get list of targets for a given call sorted by most frequently
// called first.
std::vector<IndirectCallPromotion::Callsite>
IndirectCallPromotion::getCallTargets(BinaryBasicBlock &BB,
const MCInst &Inst) const {
 BinaryFunction &BF = *BB.getFunction();
const BinaryContext &BC = BF.getBinaryContext();
 std::vector<Callsite> Targets;

if (const JumpTable *JT = BF.getJumpTable(Inst)) {
// Don't support PIC jump tables for now
if (!opts::ICPJumpTablesByTarget && JT->Type == JumpTable::JTT_PIC)
return Targets;
const Location From(BF.getSymbol());
const std::pair<size_t, size_t> Range =
 JT->getEntriesForAddress(BC.MIB->getJumpTable(Inst));
assert(JT->Counts.empty() || JT->Counts.size() >= Range.second);
 JumpTable::JumpInfo DefaultJI;
const JumpTable::JumpInfo *JI =
 JT->Counts.empty() ? &DefaultJI : &JT->Counts[Range.first];
constsize_t JIAdj = JT->Counts.empty() ? 0 : 1;
assert(JT->Type == JumpTable::JTT_PIC ||
 JT->EntrySize == BC.AsmInfo->getCodePointerSize());
for (size_t I = Range.first; I < Range.second; ++I, JI += JIAdj) {
 MCSymbol *Entry = JT->Entries[I];
const BinaryBasicBlock *ToBB = BF.getBasicBlockForLabel(Entry);
assert(ToBB || Entry == BF.getFunctionEndLabel() ||
 Entry == BF.getFunctionEndLabel(FragmentNum::cold()));
if (Entry == BF.getFunctionEndLabel() ||
 Entry == BF.getFunctionEndLabel(FragmentNum::cold()))
continue;
const Location To(Entry);
const BinaryBasicBlock::BinaryBranchInfo &BI = BB.getBranchInfo(*ToBB);
 Targets.emplace_back(From, To, BI.MispredictedCount, BI.Count,
 I - Range.first);
 }

// Sort by symbol then addr.
llvm::sort(Targets, [](const Callsite &A, const Callsite &B) {
if (A.To.Sym && B.To.Sym)
return A.To.Sym < B.To.Sym;
elseif (A.To.Sym && !B.To.Sym)
returntrue;
elseif (!A.To.Sym && B.To.Sym)
returnfalse;
else
return A.To.Addr < B.To.Addr;
 });

// Targets may contain multiple entries to the same target, but using
// different indices. Their profile will report the same number of branches
// for different indices if the target is the same. That's because we don't
// profile the index value, but only the target via LBR.
auto First = Targets.begin();
auto Last = Targets.end();
auto Result = First;
while (++First != Last) {
 Callsite &A = *Result;
const Callsite &B = *First;
if (A.To.Sym && B.To.Sym && A.To.Sym == B.To.Sym)
 A.JTIndices.insert(A.JTIndices.end(), B.JTIndices.begin(),
 B.JTIndices.end());
else
 *(++Result) = *First;
 }
 ++Result;

LLVM_DEBUG(if (Targets.end() - Result > 0) {
dbgs() << "BOLT-INFO: ICP: " << (Targets.end() - Result)
 << " duplicate targets removed\n";
 });

 Targets.erase(Result, Targets.end());
 } else {
// Don't try to optimize PC relative indirect calls.
if (Inst.getOperand(0).isReg() &&
 Inst.getOperand(0).getReg() == BC.MRI->getProgramCounter())
return Targets;

constauto ICSP = BC.MIB->tryGetAnnotationAs<IndirectCallSiteProfile>(
 Inst, "CallProfile");
if (ICSP) {
for (const IndirectCallProfile &CSP : ICSP.get()) {
 Callsite Site(BF, CSP);
if (Site.isValid())
 Targets.emplace_back(std::move(Site));
 }
 }
 }

// Sort by target count, number of indices in case of jump table, and
// mispredicts. We prioritize targets with high count, small number of indices
// and high mispredicts. Break ties by selecting targets with lower addresses.
llvm::stable_sort(Targets, [](const Callsite &A, const Callsite &B) {
if (A.Branches != B.Branches)
return A.Branches > B.Branches;
if (A.JTIndices.size() != B.JTIndices.size())
return A.JTIndices.size() < B.JTIndices.size();
if (A.Mispreds != B.Mispreds)
return A.Mispreds > B.Mispreds;
return A.To.Addr < B.To.Addr;
 });

// Remove non-symbol targets
llvm::erase_if(Targets, [](const Callsite &CS) { return !CS.To.Sym; });

LLVM_DEBUG(if (BF.getJumpTable(Inst)) {
uint64_t TotalCount = 0;
uint64_t TotalMispreds = 0;
for (const Callsite &S : Targets) {
 TotalCount += S.Branches;
 TotalMispreds += S.Mispreds;
 }
if (!TotalCount)
 TotalCount = 1;
if (!TotalMispreds)
 TotalMispreds = 1;

dbgs() << "BOLT-INFO: ICP: jump table size = " << Targets.size()
 << ", Count = " << TotalCount << ", Mispreds = " << TotalMispreds
 << "\n";

size_t I = 0;
for (const Callsite &S : Targets) {
dbgs() << "Count[" << I << "] = " << S.Branches << ", "
 << format("%.1f", (100.0 * S.Branches) / TotalCount) << ", "
 << "Mispreds[" << I << "] = " << S.Mispreds << ", "
 << format("%.1f", (100.0 * S.Mispreds) / TotalMispreds) << "\n";
 ++I;
 }
 });

return Targets;
}

IndirectCallPromotion::JumpTableInfoType
IndirectCallPromotion::maybeGetHotJumpTableTargets(BinaryBasicBlock &BB,
 MCInst &CallInst,
 MCInst *&TargetFetchInst,
const JumpTable *JT) const {
assert(JT && "Can't get jump table addrs for non-jump tables.");

 BinaryFunction &Function = *BB.getFunction();
 BinaryContext &BC = Function.getBinaryContext();

if (!Function.hasMemoryProfile() || !opts::EliminateLoads)
returnJumpTableInfoType();

 JumpTableInfoType HotTargets;
 MCInst *MemLocInstr;
 MCInst *PCRelBaseOut;
 MCInst *FixedEntryLoadInstr;
unsigned BaseReg, IndexReg;
int64_t DispValue;
const MCExpr *DispExpr;
 MutableArrayRef<MCInst> Insts(&BB.front(), &CallInst);
const IndirectBranchType Type = BC.MIB->analyzeIndirectBranch(
 CallInst, Insts.begin(), Insts.end(), BC.AsmInfo->getCodePointerSize(),
 MemLocInstr, BaseReg, IndexReg, DispValue, DispExpr, PCRelBaseOut,
 FixedEntryLoadInstr);

assert(MemLocInstr && "There should always be a load for jump tables");
if (!MemLocInstr)
returnJumpTableInfoType();

LLVM_DEBUG({
dbgs() << "BOLT-INFO: ICP attempting to find memory profiling data for "
 << "jump table in " << Function << " at @ "
 << (&CallInst - &BB.front()) << "\n"
 << "BOLT-INFO: ICP target fetch instructions:\n";
 BC.printInstruction(dbgs(), *MemLocInstr, 0, &Function);
if (MemLocInstr != &CallInst)
 BC.printInstruction(dbgs(), CallInst, 0, &Function);
 });

DEBUG_VERBOSE(1, {
dbgs() << "Jmp info: Type = " << (unsigned)Type << ", "
 << "BaseReg = " << BC.MRI->getName(BaseReg) << ", "
 << "IndexReg = " << BC.MRI->getName(IndexReg) << ", "
 << "DispValue = " << Twine::utohexstr(DispValue) << ", "
 << "DispExpr = " << DispExpr << ", "
 << "MemLocInstr = ";
 BC.printInstruction(dbgs(), *MemLocInstr, 0, &Function);
dbgs() << "\n";
 });

 ++TotalIndexBasedCandidates;

auto ErrorOrMemAccessProfile =
 BC.MIB->tryGetAnnotationAs<MemoryAccessProfile>(*MemLocInstr,
"MemoryAccessProfile");
if (!ErrorOrMemAccessProfile) {
DEBUG_VERBOSE(1, dbgs()
 << "BOLT-INFO: ICP no memory profiling data found\n");
returnJumpTableInfoType();
 }
 MemoryAccessProfile &MemAccessProfile = ErrorOrMemAccessProfile.get();

uint64_t ArrayStart;
if (DispExpr) {
 ErrorOr<uint64_t> DispValueOrError =
 BC.getSymbolValue(*BC.MIB->getTargetSymbol(DispExpr));
assert(DispValueOrError && "global symbol needs a value");
 ArrayStart = *DispValueOrError;
 } else {
 ArrayStart = static_cast<uint64_t>(DispValue);
 }

if (BaseReg == BC.MRI->getProgramCounter())
 ArrayStart += Function.getAddress() + MemAccessProfile.NextInstrOffset;

// This is a map of [symbol] -> [count, index] and is used to combine indices
// into the jump table since there may be multiple addresses that all have the
// same entry.
 std::map<MCSymbol *, std::pair<uint64_t, uint64_t>> HotTargetMap;
const std::pair<size_t, size_t> Range = JT->getEntriesForAddress(ArrayStart);

for (const AddressAccess &AccessInfo : MemAccessProfile.AddressAccessInfo) {
size_t Index;
// Mem data occasionally includes nullprs, ignore them.
if (!AccessInfo.MemoryObject && !AccessInfo.Offset)
continue;

if (AccessInfo.Offset % JT->EntrySize != 0) // ignore bogus data
returnJumpTableInfoType();

if (AccessInfo.MemoryObject) {
// Deal with bad/stale data
if (!AccessInfo.MemoryObject->getName().starts_with(
"JUMP_TABLE/" + Function.getOneName().str()))
returnJumpTableInfoType();
 Index =
 (AccessInfo.Offset - (ArrayStart - JT->getAddress())) / JT->EntrySize;
 } else {
 Index = (AccessInfo.Offset - ArrayStart) / JT->EntrySize;
 }

// If Index is out of range it probably means the memory profiling data is
// wrong for this instruction, bail out.
if (Index >= Range.second) {
LLVM_DEBUG(dbgs() << "BOLT-INFO: Index out of range of " << Range.first
 << ", " << Range.second << "\n");
returnJumpTableInfoType();
 }

// Make sure the hot index points at a legal label corresponding to a BB,
// e.g. not the end of function (unreachable) label.
if (!Function.getBasicBlockForLabel(JT->Entries[Index + Range.first])) {
LLVM_DEBUG({
dbgs() << "BOLT-INFO: hot index " << Index << " pointing at bogus "
 << "label " << JT->Entries[Index + Range.first]->getName()
 << " in jump table:\n";
 JT->print(dbgs());
dbgs() << "HotTargetMap:\n";
for (std::pair<MCSymbol *const, std::pair<uint64_t, uint64_t>> &HT :
 HotTargetMap)
dbgs() << "BOLT-INFO: " << HT.first->getName()
 << " = (count=" << HT.second.first
 << ", index=" << HT.second.second << ")\n";
 });
returnJumpTableInfoType();
 }

 std::pair<uint64_t, uint64_t> &HotTarget =
 HotTargetMap[JT->Entries[Index + Range.first]];
 HotTarget.first += AccessInfo.Count;
 HotTarget.second = Index;
 }

llvm::copy(llvm::make_second_range(HotTargetMap),
std::back_inserter(HotTargets));

// Sort with highest counts first.
llvm::sort(reverse(HotTargets));

LLVM_DEBUG({
dbgs() << "BOLT-INFO: ICP jump table hot targets:\n";
for (const std::pair<uint64_t, uint64_t> &Target : HotTargets)
dbgs() << "BOLT-INFO: Idx = " << Target.second << ", "
 << "Count = " << Target.first << "\n";
 });

 BC.MIB->getOrCreateAnnotationAs<uint16_t>(CallInst, "JTIndexReg") = IndexReg;

 TargetFetchInst = MemLocInstr;

return HotTargets;
}

IndirectCallPromotion::SymTargetsType
IndirectCallPromotion::findCallTargetSymbols(std::vector<Callsite> &Targets,
size_t &N, BinaryBasicBlock &BB,
 MCInst &CallInst,
 MCInst *&TargetFetchInst) const {
const BinaryContext &BC = BB.getFunction()->getBinaryContext();
const JumpTable *JT = BB.getFunction()->getJumpTable(CallInst);
 SymTargetsType SymTargets;

if (!JT) {
for (size_t I = 0; I < N; ++I) {
assert(Targets[I].To.Sym && "All ICP targets must be to known symbols");
assert(Targets[I].JTIndices.empty() &&
"Can't have jump table indices for non-jump tables");
 SymTargets.emplace_back(Targets[I].To.Sym, 0);
 }
return SymTargets;
 }

// Use memory profile to select hot targets.
 JumpTableInfoType HotTargets =
maybeGetHotJumpTableTargets(BB, CallInst, TargetFetchInst, JT);

auto findTargetsIndex = [&](uint64_t JTIndex) {
for (size_t I = 0; I < Targets.size(); ++I)
if (llvm::is_contained(Targets[I].JTIndices, JTIndex))
return I;
LLVM_DEBUG(dbgs() << "BOLT-ERROR: Unable to find target index for hot jump "
 << " table entry in " << *BB.getFunction() << "\n");
llvm_unreachable("Hot indices must be referred to by at least one "
"callsite");
 };

if (!HotTargets.empty()) {
if (opts::Verbosity >= 1)
for (size_t I = 0; I < HotTargets.size(); ++I)
 BC.outs() << "BOLT-INFO: HotTarget[" << I << "] = ("
 << HotTargets[I].first << ", " << HotTargets[I].second
 << ")\n";

// Recompute hottest targets, now discriminating which index is hot
// NOTE: This is a tradeoff. On one hand, we get index information. On the
// other hand, info coming from the memory profile is much less accurate
// than LBRs. So we may actually end up working with more coarse
// profile granularity in exchange for information about indices.
 std::vector<Callsite> NewTargets;
 std::map<const MCSymbol *, uint32_t> IndicesPerTarget;
uint64_t TotalMemAccesses = 0;
for (size_t I = 0; I < HotTargets.size(); ++I) {
constuint64_t TargetIndex = findTargetsIndex(HotTargets[I].second);
 ++IndicesPerTarget[Targets[TargetIndex].To.Sym];
 TotalMemAccesses += HotTargets[I].first;
 }
uint64_t RemainingMemAccesses = TotalMemAccesses;
constsize_t TopN =
 opts::ICPJumpTablesTopN ? opts::ICPJumpTablesTopN : opts::ICPTopN;
size_t I = 0;
for (; I < HotTargets.size(); ++I) {
constuint64_t MemAccesses = HotTargets[I].first;
if (100 * MemAccesses <
 TotalMemAccesses * opts::ICPJTTotalPercentThreshold)
break;
if (100 * MemAccesses <
 RemainingMemAccesses * opts::ICPJTRemainingPercentThreshold)
break;
if (TopN && I >= TopN)
break;
 RemainingMemAccesses -= MemAccesses;

constuint64_t JTIndex = HotTargets[I].second;
 Callsite &Target = Targets[findTargetsIndex(JTIndex)];

 NewTargets.push_back(Target);
 std::vector<uint64_t>({JTIndex}).swap(NewTargets.back().JTIndices);
llvm::erase(Target.JTIndices, JTIndex);

// Keep fixCFG counts sane if more indices use this same target later
assert(IndicesPerTarget[Target.To.Sym] > 0 && "wrong map");
 NewTargets.back().Branches =
 Target.Branches / IndicesPerTarget[Target.To.Sym];
 NewTargets.back().Mispreds =
 Target.Mispreds / IndicesPerTarget[Target.To.Sym];
assert(Target.Branches >= NewTargets.back().Branches);
assert(Target.Mispreds >= NewTargets.back().Mispreds);
 Target.Branches -= NewTargets.back().Branches;
 Target.Mispreds -= NewTargets.back().Mispreds;
 }
llvm::copy(Targets, std::back_inserter(NewTargets));
std::swap(NewTargets, Targets);
 N = I;

if (N == 0 && opts::Verbosity >= 1) {
 BC.outs() << "BOLT-INFO: ICP failed in " << *BB.getFunction() << " in "
 << BB.getName() << ": failed to meet thresholds after memory "
 << "profile data was loaded.\n";
return SymTargets;
 }
 }

for (size_t I = 0, TgtIdx = 0; I < N; ++TgtIdx) {
 Callsite &Target = Targets[TgtIdx];
assert(Target.To.Sym && "All ICP targets must be to known symbols");
assert(!Target.JTIndices.empty() && "Jump tables must have indices");
for (uint64_t Idx : Target.JTIndices) {
 SymTargets.emplace_back(Target.To.Sym, Idx);
 ++I;
 }
 }

return SymTargets;
}

IndirectCallPromotion::MethodInfoType IndirectCallPromotion::maybeGetVtableSyms(
 BinaryBasicBlock &BB, MCInst &Inst,
const SymTargetsType &SymTargets) const {
 BinaryFunction &Function = *BB.getFunction();
 BinaryContext &BC = Function.getBinaryContext();
 std::vector<std::pair<MCSymbol *, uint64_t>> VtableSyms;
 std::vector<MCInst *> MethodFetchInsns;
unsigned VtableReg, MethodReg;
uint64_t MethodOffset;

assert(!Function.getJumpTable(Inst) &&
"Can't get vtable addrs for jump tables.");

if (!Function.hasMemoryProfile() || !opts::EliminateLoads)
returnMethodInfoType();

 MutableArrayRef<MCInst> Insts(&BB.front(), &Inst + 1);
if (!BC.MIB->analyzeVirtualMethodCall(Insts.begin(), Insts.end(),
 MethodFetchInsns, VtableReg, MethodReg,
 MethodOffset)) {
DEBUG_VERBOSE(
1, dbgs() << "BOLT-INFO: ICP unable to analyze method call in "
 << Function << " at @ " << (&Inst - &BB.front()) << "\n");
returnMethodInfoType();
 }

 ++TotalMethodLoadEliminationCandidates;

DEBUG_VERBOSE(1, {
dbgs() << "BOLT-INFO: ICP found virtual method call in " << Function
 << " at @ " << (&Inst - &BB.front()) << "\n";
dbgs() << "BOLT-INFO: ICP method fetch instructions:\n";
for (MCInst *Inst : MethodFetchInsns)
 BC.printInstruction(dbgs(), *Inst, 0, &Function);

if (MethodFetchInsns.back() != &Inst)
 BC.printInstruction(dbgs(), Inst, 0, &Function);
 });

// Try to get value profiling data for the method load instruction.
auto ErrorOrMemAccessProfile =
 BC.MIB->tryGetAnnotationAs<MemoryAccessProfile>(*MethodFetchInsns.back(),
"MemoryAccessProfile");
if (!ErrorOrMemAccessProfile) {
DEBUG_VERBOSE(1, dbgs()
 << "BOLT-INFO: ICP no memory profiling data found\n");
returnMethodInfoType();
 }
 MemoryAccessProfile &MemAccessProfile = ErrorOrMemAccessProfile.get();

// Find the vtable that each method belongs to.
 std::map<const MCSymbol *, uint64_t> MethodToVtable;

for (const AddressAccess &AccessInfo : MemAccessProfile.AddressAccessInfo) {
uint64_t Address = AccessInfo.Offset;
if (AccessInfo.MemoryObject)
 Address += AccessInfo.MemoryObject->getAddress();

// Ignore bogus data.
if (!Address)
continue;

constuint64_t VtableBase = Address - MethodOffset;

DEBUG_VERBOSE(1, dbgs() << "BOLT-INFO: ICP vtable = "
 << Twine::utohexstr(VtableBase) << "+"
 << MethodOffset << "/" << AccessInfo.Count << "\n");

if (ErrorOr<uint64_t> MethodAddr = BC.getPointerAtAddress(Address)) {
 BinaryData *MethodBD = BC.getBinaryDataAtAddress(MethodAddr.get());
if (!MethodBD) // skip unknown methods
continue;
 MCSymbol *MethodSym = MethodBD->getSymbol();
 MethodToVtable[MethodSym] = VtableBase;
DEBUG_VERBOSE(1, {
const BinaryFunction *Method = BC.getFunctionForSymbol(MethodSym);
dbgs() << "BOLT-INFO: ICP found method = "
 << Twine::utohexstr(MethodAddr.get()) << "/"
 << (Method ? Method->getPrintName() : "") << "\n";
 });
 }
 }

// Find the vtable for each target symbol.
for (size_t I = 0; I < SymTargets.size(); ++I) {
auto Itr = MethodToVtable.find(SymTargets[I].first);
if (Itr != MethodToVtable.end()) {
if (BinaryData *BD = BC.getBinaryDataContainingAddress(Itr->second)) {
constuint64_t Addend = Itr->second - BD->getAddress();
 VtableSyms.emplace_back(BD->getSymbol(), Addend);
continue;
 }
 }
// Give up if we can't find the vtable for a method.
DEBUG_VERBOSE(1, dbgs() << "BOLT-INFO: ICP can't find vtable for "
 << SymTargets[I].first->getName() << "\n");
returnMethodInfoType();
 }

// Make sure the vtable reg is not clobbered by the argument passing code
if (VtableReg != MethodReg) {
for (MCInst *CurInst = MethodFetchInsns.front(); CurInst < &Inst;
 ++CurInst) {
const MCInstrDesc &InstrInfo = BC.MII->get(CurInst->getOpcode());
if (InstrInfo.hasDefOfPhysReg(*CurInst, VtableReg, *BC.MRI))
returnMethodInfoType();
 }
 }

returnMethodInfoType(VtableSyms, MethodFetchInsns);
}

std::vector<std::unique_ptr<BinaryBasicBlock>>
IndirectCallPromotion::rewriteCall(
 BinaryBasicBlock &IndCallBlock, const MCInst &CallInst,
 MCPlusBuilder::BlocksVectorTy &&ICPcode,
const std::vector<MCInst *> &MethodFetchInsns) const {
 BinaryFunction &Function = *IndCallBlock.getFunction();
 MCPlusBuilder *MIB = Function.getBinaryContext().MIB.get();

// Create new basic blocks with correct code in each one first.
 std::vector<std::unique_ptr<BinaryBasicBlock>> NewBBs;
constbool IsTailCallOrJT =
 (MIB->isTailCall(CallInst) || Function.getJumpTable(CallInst));

// If we are tracking the indirect call/jump address, propagate the address to
// the ICP code.
const std::optional<uint32_t> IndirectInstrOffset = MIB->getOffset(CallInst);
if (IndirectInstrOffset) {
for (auto &[Symbol, Instructions] : ICPcode)
for (MCInst &Inst : Instructions)
 MIB->setOffset(Inst, *IndirectInstrOffset);
 }

// Move instructions from the tail of the original call block
// to the merge block.

// Remember any pseudo instructions following a tail call. These
// must be preserved and moved to the original block.
 InstructionListType TailInsts;
const MCInst *TailInst = &CallInst;
if (IsTailCallOrJT)
while (TailInst + 1 < &(*IndCallBlock.end()) &&
 MIB->isPseudo(*(TailInst + 1)))
 TailInsts.push_back(*++TailInst);

 InstructionListType MovedInst = IndCallBlock.splitInstructions(&CallInst);
// Link new BBs to the original input offset of the indirect call site or its
// containing BB, so we can map samples recorded in new BBs back to the
// original BB seen in the input binary (if using BAT).
constuint32_t OrigOffset = IndirectInstrOffset
 ? *IndirectInstrOffset
 : IndCallBlock.getInputOffset();

 IndCallBlock.eraseInstructions(MethodFetchInsns.begin(),
 MethodFetchInsns.end());
if (IndCallBlock.empty() ||
 (!MethodFetchInsns.empty() && MethodFetchInsns.back() == &CallInst))
 IndCallBlock.addInstructions(ICPcode.front().second.begin(),
 ICPcode.front().second.end());
else
 IndCallBlock.replaceInstruction(std::prev(IndCallBlock.end()),
 ICPcode.front().second);
 IndCallBlock.addInstructions(TailInsts.begin(), TailInsts.end());

for (auto Itr = ICPcode.begin() + 1; Itr != ICPcode.end(); ++Itr) {
 MCSymbol *&Sym = Itr->first;
 InstructionListType &Insts = Itr->second;
assert(Sym);
 std::unique_ptr<BinaryBasicBlock> TBB = Function.createBasicBlock(Sym);
 TBB->setOffset(OrigOffset);
for (MCInst &Inst : Insts) // sanitize new instructions.
if (MIB->isCall(Inst))
 MIB->removeAnnotation(Inst, "CallProfile");
 TBB->addInstructions(Insts.begin(), Insts.end());
 NewBBs.emplace_back(std::move(TBB));
 }

// Move tail of instructions from after the original call to
// the merge block.
if (!IsTailCallOrJT)
 NewBBs.back()->addInstructions(MovedInst.begin(), MovedInst.end());

return NewBBs;
}

BinaryBasicBlock *
IndirectCallPromotion::fixCFG(BinaryBasicBlock &IndCallBlock,
constbool IsTailCall, constbool IsJumpTable,
 IndirectCallPromotion::BasicBlocksVector &&NewBBs,
const std::vector<Callsite> &Targets) const {
 BinaryFunction &Function = *IndCallBlock.getFunction();
using BinaryBranchInfo = BinaryBasicBlock::BinaryBranchInfo;
 BinaryBasicBlock *MergeBlock = nullptr;

// Scale indirect call counts to the execution count of the original
// basic block containing the indirect call.
uint64_t TotalCount = IndCallBlock.getKnownExecutionCount();
uint64_t TotalIndirectBranches = 0;
for (const Callsite &Target : Targets)
 TotalIndirectBranches += Target.Branches;
if (TotalIndirectBranches == 0)
 TotalIndirectBranches = 1;
 BinaryBasicBlock::BranchInfoType BBI;
 BinaryBasicBlock::BranchInfoType ScaledBBI;
for (const Callsite &Target : Targets) {
constsize_t NumEntries =
std::max(static_cast<std::size_t>(1UL), Target.JTIndices.size());
for (size_t I = 0; I < NumEntries; ++I) {
 BBI.push_back(
 BinaryBranchInfo{(Target.Branches + NumEntries - 1) / NumEntries,
 (Target.Mispreds + NumEntries - 1) / NumEntries});
 ScaledBBI.push_back(
 BinaryBranchInfo{uint64_t(TotalCount * Target.Branches /
 (NumEntries * TotalIndirectBranches)),
uint64_t(TotalCount * Target.Mispreds /
 (NumEntries * TotalIndirectBranches))});
 }
 }

if (IsJumpTable) {
 BinaryBasicBlock *NewIndCallBlock = NewBBs.back().get();
 IndCallBlock.moveAllSuccessorsTo(NewIndCallBlock);

 std::vector<MCSymbol *> SymTargets;
for (const Callsite &Target : Targets) {
constsize_t NumEntries =
std::max(static_cast<std::size_t>(1UL), Target.JTIndices.size());
for (size_t I = 0; I < NumEntries; ++I)
 SymTargets.push_back(Target.To.Sym);
 }
assert(SymTargets.size() > NewBBs.size() - 1 &&
"There must be a target symbol associated with each new BB.");

for (uint64_t I = 0; I < NewBBs.size(); ++I) {
 BinaryBasicBlock *SourceBB = I ? NewBBs[I - 1].get() : &IndCallBlock;
 SourceBB->setExecutionCount(TotalCount);

 BinaryBasicBlock *TargetBB =
 Function.getBasicBlockForLabel(SymTargets[I]);
 SourceBB->addSuccessor(TargetBB, ScaledBBI[I]); // taken

 TotalCount -= ScaledBBI[I].Count;
 SourceBB->addSuccessor(NewBBs[I].get(), TotalCount); // fall-through

// Update branch info for the indirect jump.
 BinaryBasicBlock::BinaryBranchInfo &BranchInfo =
 NewIndCallBlock->getBranchInfo(*TargetBB);
if (BranchInfo.Count > BBI[I].Count)
 BranchInfo.Count -= BBI[I].Count;
else
 BranchInfo.Count = 0;

if (BranchInfo.MispredictedCount > BBI[I].MispredictedCount)
 BranchInfo.MispredictedCount -= BBI[I].MispredictedCount;
else
 BranchInfo.MispredictedCount = 0;
 }
 } else {
assert(NewBBs.size() >= 2);
assert(NewBBs.size() % 2 == 1 || IndCallBlock.succ_empty());
assert(NewBBs.size() % 2 == 1 || IsTailCall);

auto ScaledBI = ScaledBBI.begin();
auto updateCurrentBranchInfo = [&] {
assert(ScaledBI != ScaledBBI.end());
 TotalCount -= ScaledBI->Count;
 ++ScaledBI;
 };

if (!IsTailCall) {
 MergeBlock = NewBBs.back().get();
 IndCallBlock.moveAllSuccessorsTo(MergeBlock);
 }

// Fix up successors and execution counts.
updateCurrentBranchInfo();
 IndCallBlock.addSuccessor(NewBBs[1].get(), TotalCount);
 IndCallBlock.addSuccessor(NewBBs[0].get(), ScaledBBI[0]);

constsize_t Adj = IsTailCall ? 1 : 2;
for (size_t I = 0; I < NewBBs.size() - Adj; ++I) {
assert(TotalCount <= IndCallBlock.getExecutionCount() ||
 TotalCount <= uint64_t(TotalIndirectBranches));
uint64_t ExecCount = ScaledBBI[(I + 1) / 2].Count;
if (I % 2 == 0) {
if (MergeBlock)
 NewBBs[I]->addSuccessor(MergeBlock, ScaledBBI[(I + 1) / 2].Count);
 } else {
assert(I + 2 < NewBBs.size());
updateCurrentBranchInfo();
 NewBBs[I]->addSuccessor(NewBBs[I + 2].get(), TotalCount);
 NewBBs[I]->addSuccessor(NewBBs[I + 1].get(), ScaledBBI[(I + 1) / 2]);
 ExecCount += TotalCount;
 }
 NewBBs[I]->setExecutionCount(ExecCount);
 }

if (MergeBlock) {
// Arrange for the MergeBlock to be the fallthrough for the first
// promoted call block.
 std::unique_ptr<BinaryBasicBlock> MBPtr;
std::swap(MBPtr, NewBBs.back());
 NewBBs.pop_back();
 NewBBs.emplace(NewBBs.begin() + 1, std::move(MBPtr));
// TODO: is COUNT_FALLTHROUGH_EDGE the right thing here?
 NewBBs.back()->addSuccessor(MergeBlock, TotalCount); // uncond branch
 }
 }

// Update the execution count.
 NewBBs.back()->setExecutionCount(TotalCount);

// Update BB and BB layout.
 Function.insertBasicBlocks(&IndCallBlock, std::move(NewBBs));
assert(Function.validateCFG());

return MergeBlock;
}

size_tIndirectCallPromotion::canPromoteCallsite(
const BinaryBasicBlock &BB, const MCInst &Inst,
const std::vector<Callsite> &Targets, uint64_t NumCalls) {
 BinaryFunction *BF = BB.getFunction();
const BinaryContext &BC = BF->getBinaryContext();

if (BB.getKnownExecutionCount() < opts::ExecutionCountThreshold)
return0;

constbool IsJumpTable = BF->getJumpTable(Inst);

auto computeStats = [&](size_t N) {
for (size_t I = 0; I < N; ++I)
if (IsJumpTable)
 TotalNumFrequentJmps += Targets[I].Branches;
else
 TotalNumFrequentCalls += Targets[I].Branches;
 };

// If we have no targets (or no calls), skip this callsite.
if (Targets.empty() || !NumCalls) {
if (opts::Verbosity >= 1) {
constptrdiff_t InstIdx = &Inst - &(*BB.begin());
 BC.outs() << "BOLT-INFO: ICP failed in " << *BF << " @ " << InstIdx
 << " in " << BB.getName() << ", calls = " << NumCalls
 << ", targets empty or NumCalls == 0.\n";
 }
return0;
 }

size_t TopN = opts::ICPTopN;
if (IsJumpTable)
 TopN = opts::ICPJumpTablesTopN ? opts::ICPJumpTablesTopN : TopN;
else
 TopN = opts::ICPCallsTopN ? opts::ICPCallsTopN : TopN;

constsize_t TrialN = TopN ? std::min(TopN, Targets.size()) : Targets.size();

if (opts::ICPTopCallsites && !BC.MIB->hasAnnotation(Inst, "DoICP"))
return0;

// Pick the top N targets.