1483 lines · cpp
1//===- bolt/Passes/IndirectCallPromotion.cpp ------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the IndirectCallPromotion class.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Passes/IndirectCallPromotion.h"14#include "bolt/Core/BinaryFunctionCallGraph.h"15#include "bolt/Passes/DataflowInfoManager.h"16#include "bolt/Passes/Inliner.h"17#include "llvm/ADT/STLExtras.h"18#include "llvm/Support/CommandLine.h"19#include <iterator>20 21#define DEBUG_TYPE "ICP"22#define DEBUG_VERBOSE(Level, X) \23 if (opts::Verbosity >= (Level)) { \24 X; \25 }26 27using namespace llvm;28using namespace bolt;29 30namespace opts {31 32extern cl::OptionCategory BoltOptCategory;33 34extern cl::opt<IndirectCallPromotionType> ICP;35extern cl::opt<unsigned> Verbosity;36extern cl::opt<unsigned> ExecutionCountThreshold;37 38static cl::opt<unsigned> ICPJTRemainingPercentThreshold(39 "icp-jt-remaining-percent-threshold",40 cl::desc("The percentage threshold against remaining unpromoted indirect "41 "call count for the promotion for jump tables"),42 cl::init(30), cl::ZeroOrMore, cl::Hidden, cl::cat(BoltOptCategory));43 44static cl::opt<unsigned> ICPJTTotalPercentThreshold(45 "icp-jt-total-percent-threshold",46 cl::desc(47 "The percentage threshold against total count for the promotion for "48 "jump tables"),49 cl::init(5), cl::Hidden, cl::cat(BoltOptCategory));50 51static cl::opt<unsigned> ICPCallsRemainingPercentThreshold(52 "icp-calls-remaining-percent-threshold",53 cl::desc("The percentage threshold against remaining unpromoted indirect "54 "call count for the promotion for calls"),55 cl::init(50), cl::Hidden, cl::cat(BoltOptCategory));56 57static cl::opt<unsigned> ICPCallsTotalPercentThreshold(58 "icp-calls-total-percent-threshold",59 cl::desc(60 "The percentage threshold against total count for the promotion for "61 "calls"),62 cl::init(30), cl::Hidden, cl::cat(BoltOptCategory));63 64static cl::opt<unsigned> ICPMispredictThreshold(65 "indirect-call-promotion-mispredict-threshold",66 cl::desc("misprediction threshold for skipping ICP on an "67 "indirect call"),68 cl::init(0), cl::cat(BoltOptCategory));69 70static cl::alias ICPMispredictThresholdAlias(71 "icp-mp-threshold",72 cl::desc("alias for --indirect-call-promotion-mispredict-threshold"),73 cl::aliasopt(ICPMispredictThreshold));74 75static cl::opt<bool> ICPUseMispredicts(76 "indirect-call-promotion-use-mispredicts",77 cl::desc("use misprediction frequency for determining whether or not ICP "78 "should be applied at a callsite. The "79 "-indirect-call-promotion-mispredict-threshold value will be used "80 "by this heuristic"),81 cl::cat(BoltOptCategory));82 83static cl::alias ICPUseMispredictsAlias(84 "icp-use-mp",85 cl::desc("alias for --indirect-call-promotion-use-mispredicts"),86 cl::aliasopt(ICPUseMispredicts));87 88static cl::opt<unsigned>89 ICPTopN("indirect-call-promotion-topn",90 cl::desc("limit number of targets to consider when doing indirect "91 "call promotion. 0 = no limit"),92 cl::init(3), cl::cat(BoltOptCategory));93 94static cl::alias95 ICPTopNAlias("icp-topn",96 cl::desc("alias for --indirect-call-promotion-topn"),97 cl::aliasopt(ICPTopN));98 99static cl::opt<unsigned> ICPCallsTopN(100 "indirect-call-promotion-calls-topn",101 cl::desc("limit number of targets to consider when doing indirect "102 "call promotion on calls. 0 = no limit"),103 cl::init(0), cl::cat(BoltOptCategory));104 105static cl::alias ICPCallsTopNAlias(106 "icp-calls-topn",107 cl::desc("alias for --indirect-call-promotion-calls-topn"),108 cl::aliasopt(ICPCallsTopN));109 110static cl::opt<unsigned> ICPJumpTablesTopN(111 "indirect-call-promotion-jump-tables-topn",112 cl::desc("limit number of targets to consider when doing indirect "113 "call promotion on jump tables. 0 = no limit"),114 cl::init(0), cl::cat(BoltOptCategory));115 116static cl::alias ICPJumpTablesTopNAlias(117 "icp-jt-topn",118 cl::desc("alias for --indirect-call-promotion-jump-tables-topn"),119 cl::aliasopt(ICPJumpTablesTopN));120 121static cl::opt<bool> EliminateLoads(122 "icp-eliminate-loads",123 cl::desc("enable load elimination using memory profiling data when "124 "performing ICP"),125 cl::init(true), cl::cat(BoltOptCategory));126 127static cl::opt<unsigned> ICPTopCallsites(128 "icp-top-callsites",129 cl::desc("optimize hottest calls until at least this percentage of all "130 "indirect calls frequency is covered. 0 = all callsites"),131 cl::init(99), cl::Hidden, cl::cat(BoltOptCategory));132 133static cl::list<std::string>134 ICPFuncsList("icp-funcs", cl::CommaSeparated,135 cl::desc("list of functions to enable ICP for"),136 cl::value_desc("func1,func2,func3,..."), cl::Hidden,137 cl::cat(BoltOptCategory));138 139static cl::opt<bool>140 ICPOldCodeSequence("icp-old-code-sequence",141 cl::desc("use old code sequence for promoted calls"),142 cl::Hidden, cl::cat(BoltOptCategory));143 144static cl::opt<bool> ICPJumpTablesByTarget(145 "icp-jump-tables-targets",146 cl::desc(147 "for jump tables, optimize indirect jmp targets instead of indices"),148 cl::Hidden, cl::cat(BoltOptCategory));149 150static cl::alias151 ICPJumpTablesByTargetAlias("icp-jt-targets",152 cl::desc("alias for --icp-jump-tables-targets"),153 cl::aliasopt(ICPJumpTablesByTarget));154 155static cl::opt<bool> ICPPeelForInline(156 "icp-inline", cl::desc("only promote call targets eligible for inlining"),157 cl::Hidden, cl::cat(BoltOptCategory));158 159} // namespace opts160 161#ifndef NDEBUG162static bool verifyProfile(std::map<uint64_t, BinaryFunction> &BFs) {163 bool IsValid = true;164 for (auto &BFI : BFs) {165 BinaryFunction &BF = BFI.second;166 if (!BF.isSimple())167 continue;168 for (const BinaryBasicBlock &BB : BF) {169 auto BI = BB.branch_info_begin();170 for (BinaryBasicBlock *SuccBB : BB.successors()) {171 if (BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE && BI->Count > 0) {172 if (BB.getKnownExecutionCount() == 0 ||173 SuccBB->getKnownExecutionCount() == 0) {174 BF.getBinaryContext().errs()175 << "BOLT-WARNING: profile verification failed after ICP for "176 "function "177 << BF << '\n';178 IsValid = false;179 }180 }181 ++BI;182 }183 }184 }185 return IsValid;186}187#endif188 189namespace llvm {190namespace bolt {191 192IndirectCallPromotion::Callsite::Callsite(BinaryFunction &BF,193 const IndirectCallProfile &ICP)194 : From(BF.getSymbol()), To(ICP.Offset), Mispreds(ICP.Mispreds),195 Branches(ICP.Count) {196 if (ICP.Symbol) {197 To.Sym = ICP.Symbol;198 To.Addr = 0;199 }200}201 202void IndirectCallPromotion::printDecision(203 llvm::raw_ostream &OS,204 std::vector<IndirectCallPromotion::Callsite> &Targets, unsigned N) const {205 uint64_t TotalCount = 0;206 uint64_t TotalMispreds = 0;207 for (const Callsite &S : Targets) {208 TotalCount += S.Branches;209 TotalMispreds += S.Mispreds;210 }211 if (!TotalCount)212 TotalCount = 1;213 if (!TotalMispreds)214 TotalMispreds = 1;215 216 OS << "BOLT-INFO: ICP decision for call site with " << Targets.size()217 << " targets, Count = " << TotalCount << ", Mispreds = " << TotalMispreds218 << "\n";219 220 size_t I = 0;221 for (const Callsite &S : Targets) {222 OS << "Count = " << S.Branches << ", "223 << format("%.1f", (100.0 * S.Branches) / TotalCount) << ", "224 << "Mispreds = " << S.Mispreds << ", "225 << format("%.1f", (100.0 * S.Mispreds) / TotalMispreds);226 if (I < N)227 OS << " * to be optimized *";228 if (!S.JTIndices.empty()) {229 OS << " Indices:";230 for (const uint64_t Idx : S.JTIndices)231 OS << " " << Idx;232 }233 OS << "\n";234 I += S.JTIndices.empty() ? 1 : S.JTIndices.size();235 }236}237 238// Get list of targets for a given call sorted by most frequently239// called first.240std::vector<IndirectCallPromotion::Callsite>241IndirectCallPromotion::getCallTargets(BinaryBasicBlock &BB,242 const MCInst &Inst) const {243 BinaryFunction &BF = *BB.getFunction();244 const BinaryContext &BC = BF.getBinaryContext();245 std::vector<Callsite> Targets;246 247 if (const JumpTable *JT = BF.getJumpTable(Inst)) {248 // Don't support PIC jump tables for now249 if (!opts::ICPJumpTablesByTarget && JT->Type == JumpTable::JTT_PIC)250 return Targets;251 const Location From(BF.getSymbol());252 const std::pair<size_t, size_t> Range =253 JT->getEntriesForAddress(BC.MIB->getJumpTable(Inst));254 assert(JT->Counts.empty() || JT->Counts.size() >= Range.second);255 JumpTable::JumpInfo DefaultJI;256 const JumpTable::JumpInfo *JI =257 JT->Counts.empty() ? &DefaultJI : &JT->Counts[Range.first];258 const size_t JIAdj = JT->Counts.empty() ? 0 : 1;259 assert(JT->Type == JumpTable::JTT_PIC ||260 JT->EntrySize == BC.AsmInfo->getCodePointerSize());261 for (size_t I = Range.first; I < Range.second; ++I, JI += JIAdj) {262 MCSymbol *Entry = JT->Entries[I];263 const BinaryBasicBlock *ToBB = BF.getBasicBlockForLabel(Entry);264 if (!ToBB)265 continue;266 const Location To(Entry);267 const BinaryBasicBlock::BinaryBranchInfo &BI = BB.getBranchInfo(*ToBB);268 Targets.emplace_back(From, To, BI.MispredictedCount, BI.Count,269 I - Range.first);270 }271 272 // Sort by symbol then addr.273 llvm::sort(Targets, [](const Callsite &A, const Callsite &B) {274 if (A.To.Sym && B.To.Sym)275 return A.To.Sym < B.To.Sym;276 else if (A.To.Sym && !B.To.Sym)277 return true;278 else if (!A.To.Sym && B.To.Sym)279 return false;280 else281 return A.To.Addr < B.To.Addr;282 });283 284 // Targets may contain multiple entries to the same target, but using285 // different indices. Their profile will report the same number of branches286 // for different indices if the target is the same. That's because we don't287 // profile the index value, but only the target via LBR.288 auto First = Targets.begin();289 auto Last = Targets.end();290 auto Result = First;291 while (++First != Last) {292 Callsite &A = *Result;293 const Callsite &B = *First;294 if (A.To.Sym && B.To.Sym && A.To.Sym == B.To.Sym)295 A.JTIndices.insert(A.JTIndices.end(), B.JTIndices.begin(),296 B.JTIndices.end());297 else298 *(++Result) = *First;299 }300 ++Result;301 302 LLVM_DEBUG(if (Targets.end() - Result > 0) {303 dbgs() << "BOLT-INFO: ICP: " << (Targets.end() - Result)304 << " duplicate targets removed\n";305 });306 307 Targets.erase(Result, Targets.end());308 } else {309 // Don't try to optimize PC relative indirect calls.310 if (Inst.getOperand(0).isReg() &&311 Inst.getOperand(0).getReg() == BC.MRI->getProgramCounter())312 return Targets;313 314 const auto ICSP = BC.MIB->tryGetAnnotationAs<IndirectCallSiteProfile>(315 Inst, "CallProfile");316 if (ICSP) {317 for (const IndirectCallProfile &CSP : ICSP.get()) {318 Callsite Site(BF, CSP);319 if (Site.isValid())320 Targets.emplace_back(std::move(Site));321 }322 }323 }324 325 // Sort by target count, number of indices in case of jump table, and326 // mispredicts. We prioritize targets with high count, small number of indices327 // and high mispredicts. Break ties by selecting targets with lower addresses.328 llvm::stable_sort(Targets, [](const Callsite &A, const Callsite &B) {329 if (A.Branches != B.Branches)330 return A.Branches > B.Branches;331 if (A.JTIndices.size() != B.JTIndices.size())332 return A.JTIndices.size() < B.JTIndices.size();333 if (A.Mispreds != B.Mispreds)334 return A.Mispreds > B.Mispreds;335 return A.To.Addr < B.To.Addr;336 });337 338 // Remove non-symbol targets339 llvm::erase_if(Targets, [](const Callsite &CS) { return !CS.To.Sym; });340 341 LLVM_DEBUG(if (BF.getJumpTable(Inst)) {342 uint64_t TotalCount = 0;343 uint64_t TotalMispreds = 0;344 for (const Callsite &S : Targets) {345 TotalCount += S.Branches;346 TotalMispreds += S.Mispreds;347 }348 if (!TotalCount)349 TotalCount = 1;350 if (!TotalMispreds)351 TotalMispreds = 1;352 353 dbgs() << "BOLT-INFO: ICP: jump table size = " << Targets.size()354 << ", Count = " << TotalCount << ", Mispreds = " << TotalMispreds355 << "\n";356 357 size_t I = 0;358 for (const Callsite &S : Targets) {359 dbgs() << "Count[" << I << "] = " << S.Branches << ", "360 << format("%.1f", (100.0 * S.Branches) / TotalCount) << ", "361 << "Mispreds[" << I << "] = " << S.Mispreds << ", "362 << format("%.1f", (100.0 * S.Mispreds) / TotalMispreds) << "\n";363 ++I;364 }365 });366 367 return Targets;368}369 370IndirectCallPromotion::JumpTableInfoType371IndirectCallPromotion::maybeGetHotJumpTableTargets(BinaryBasicBlock &BB,372 MCInst &CallInst,373 MCInst *&TargetFetchInst,374 const JumpTable *JT) const {375 assert(JT && "Can't get jump table addrs for non-jump tables.");376 377 BinaryFunction &Function = *BB.getFunction();378 BinaryContext &BC = Function.getBinaryContext();379 380 if (!Function.hasMemoryProfile() || !opts::EliminateLoads)381 return JumpTableInfoType();382 383 JumpTableInfoType HotTargets;384 MCInst *MemLocInstr;385 MCInst *PCRelBaseOut;386 MCInst *FixedEntryLoadInstr;387 unsigned BaseReg, IndexReg;388 int64_t DispValue;389 const MCExpr *DispExpr;390 MutableArrayRef<MCInst> Insts(&BB.front(), &CallInst);391 const IndirectBranchType Type = BC.MIB->analyzeIndirectBranch(392 CallInst, Insts.begin(), Insts.end(), BC.AsmInfo->getCodePointerSize(),393 MemLocInstr, BaseReg, IndexReg, DispValue, DispExpr, PCRelBaseOut,394 FixedEntryLoadInstr);395 396 assert(MemLocInstr && "There should always be a load for jump tables");397 if (!MemLocInstr)398 return JumpTableInfoType();399 400 LLVM_DEBUG({401 dbgs() << "BOLT-INFO: ICP attempting to find memory profiling data for "402 << "jump table in " << Function << " at @ "403 << (&CallInst - &BB.front()) << "\n"404 << "BOLT-INFO: ICP target fetch instructions:\n";405 BC.printInstruction(dbgs(), *MemLocInstr, 0, &Function);406 if (MemLocInstr != &CallInst)407 BC.printInstruction(dbgs(), CallInst, 0, &Function);408 });409 410 DEBUG_VERBOSE(1, {411 dbgs() << "Jmp info: Type = " << (unsigned)Type << ", "412 << "BaseReg = " << BC.MRI->getName(BaseReg) << ", "413 << "IndexReg = " << BC.MRI->getName(IndexReg) << ", "414 << "DispValue = " << Twine::utohexstr(DispValue) << ", "415 << "DispExpr = " << DispExpr << ", "416 << "MemLocInstr = ";417 BC.printInstruction(dbgs(), *MemLocInstr, 0, &Function);418 dbgs() << "\n";419 });420 421 ++TotalIndexBasedCandidates;422 423 auto ErrorOrMemAccessProfile =424 BC.MIB->tryGetAnnotationAs<MemoryAccessProfile>(*MemLocInstr,425 "MemoryAccessProfile");426 if (!ErrorOrMemAccessProfile) {427 DEBUG_VERBOSE(1, dbgs()428 << "BOLT-INFO: ICP no memory profiling data found\n");429 return JumpTableInfoType();430 }431 MemoryAccessProfile &MemAccessProfile = ErrorOrMemAccessProfile.get();432 433 uint64_t ArrayStart;434 if (DispExpr) {435 ErrorOr<uint64_t> DispValueOrError =436 BC.getSymbolValue(*BC.MIB->getTargetSymbol(DispExpr));437 assert(DispValueOrError && "global symbol needs a value");438 ArrayStart = *DispValueOrError;439 } else {440 ArrayStart = static_cast<uint64_t>(DispValue);441 }442 443 if (BaseReg == BC.MRI->getProgramCounter())444 ArrayStart += Function.getAddress() + MemAccessProfile.NextInstrOffset;445 446 // This is a map of [symbol] -> [count, index] and is used to combine indices447 // into the jump table since there may be multiple addresses that all have the448 // same entry.449 std::map<MCSymbol *, std::pair<uint64_t, uint64_t>> HotTargetMap;450 const std::pair<size_t, size_t> Range = JT->getEntriesForAddress(ArrayStart);451 452 for (const AddressAccess &AccessInfo : MemAccessProfile.AddressAccessInfo) {453 size_t Index;454 // Mem data occasionally includes nullprs, ignore them.455 if (!AccessInfo.MemoryObject && !AccessInfo.Offset)456 continue;457 458 if (AccessInfo.Offset % JT->EntrySize != 0) // ignore bogus data459 return JumpTableInfoType();460 461 if (AccessInfo.MemoryObject) {462 // Deal with bad/stale data463 if (!AccessInfo.MemoryObject->getName().starts_with(464 "JUMP_TABLE/" + Function.getOneName().str()))465 return JumpTableInfoType();466 Index =467 (AccessInfo.Offset - (ArrayStart - JT->getAddress())) / JT->EntrySize;468 } else {469 Index = (AccessInfo.Offset - ArrayStart) / JT->EntrySize;470 }471 472 // If Index is out of range it probably means the memory profiling data is473 // wrong for this instruction, bail out.474 if (Index >= Range.second) {475 LLVM_DEBUG(dbgs() << "BOLT-INFO: Index out of range of " << Range.first476 << ", " << Range.second << "\n");477 return JumpTableInfoType();478 }479 480 // Make sure the hot index points at a legal label corresponding to a BB,481 // e.g. not the end of function (unreachable) label.482 if (!Function.getBasicBlockForLabel(JT->Entries[Index + Range.first])) {483 LLVM_DEBUG({484 dbgs() << "BOLT-INFO: hot index " << Index << " pointing at bogus "485 << "label " << JT->Entries[Index + Range.first]->getName()486 << " in jump table:\n";487 JT->print(dbgs());488 dbgs() << "HotTargetMap:\n";489 for (std::pair<MCSymbol *const, std::pair<uint64_t, uint64_t>> &HT :490 HotTargetMap)491 dbgs() << "BOLT-INFO: " << HT.first->getName()492 << " = (count=" << HT.second.first493 << ", index=" << HT.second.second << ")\n";494 });495 return JumpTableInfoType();496 }497 498 std::pair<uint64_t, uint64_t> &HotTarget =499 HotTargetMap[JT->Entries[Index + Range.first]];500 HotTarget.first += AccessInfo.Count;501 HotTarget.second = Index;502 }503 504 llvm::copy(llvm::make_second_range(HotTargetMap),505 std::back_inserter(HotTargets));506 507 // Sort with highest counts first.508 llvm::sort(reverse(HotTargets));509 510 LLVM_DEBUG({511 dbgs() << "BOLT-INFO: ICP jump table hot targets:\n";512 for (const std::pair<uint64_t, uint64_t> &Target : HotTargets)513 dbgs() << "BOLT-INFO: Idx = " << Target.second << ", "514 << "Count = " << Target.first << "\n";515 });516 517 BC.MIB->getOrCreateAnnotationAs<uint16_t>(CallInst, "JTIndexReg") = IndexReg;518 519 TargetFetchInst = MemLocInstr;520 521 return HotTargets;522}523 524IndirectCallPromotion::SymTargetsType525IndirectCallPromotion::findCallTargetSymbols(std::vector<Callsite> &Targets,526 size_t &N, BinaryBasicBlock &BB,527 MCInst &CallInst,528 MCInst *&TargetFetchInst) const {529 const BinaryContext &BC = BB.getFunction()->getBinaryContext();530 const JumpTable *JT = BB.getFunction()->getJumpTable(CallInst);531 SymTargetsType SymTargets;532 533 if (!JT) {534 for (size_t I = 0; I < N; ++I) {535 assert(Targets[I].To.Sym && "All ICP targets must be to known symbols");536 assert(Targets[I].JTIndices.empty() &&537 "Can't have jump table indices for non-jump tables");538 SymTargets.emplace_back(Targets[I].To.Sym, 0);539 }540 return SymTargets;541 }542 543 // Use memory profile to select hot targets.544 JumpTableInfoType HotTargets =545 maybeGetHotJumpTableTargets(BB, CallInst, TargetFetchInst, JT);546 547 auto findTargetsIndex = [&](uint64_t JTIndex) {548 for (size_t I = 0; I < Targets.size(); ++I)549 if (llvm::is_contained(Targets[I].JTIndices, JTIndex))550 return I;551 LLVM_DEBUG(dbgs() << "BOLT-ERROR: Unable to find target index for hot jump "552 << " table entry in " << *BB.getFunction() << "\n");553 llvm_unreachable("Hot indices must be referred to by at least one "554 "callsite");555 };556 557 if (!HotTargets.empty()) {558 if (opts::Verbosity >= 1)559 for (size_t I = 0; I < HotTargets.size(); ++I)560 BC.outs() << "BOLT-INFO: HotTarget[" << I << "] = ("561 << HotTargets[I].first << ", " << HotTargets[I].second562 << ")\n";563 564 // Recompute hottest targets, now discriminating which index is hot565 // NOTE: This is a tradeoff. On one hand, we get index information. On the566 // other hand, info coming from the memory profile is much less accurate567 // than LBRs. So we may actually end up working with more coarse568 // profile granularity in exchange for information about indices.569 std::vector<Callsite> NewTargets;570 std::map<const MCSymbol *, uint32_t> IndicesPerTarget;571 uint64_t TotalMemAccesses = 0;572 for (size_t I = 0; I < HotTargets.size(); ++I) {573 const uint64_t TargetIndex = findTargetsIndex(HotTargets[I].second);574 ++IndicesPerTarget[Targets[TargetIndex].To.Sym];575 TotalMemAccesses += HotTargets[I].first;576 }577 uint64_t RemainingMemAccesses = TotalMemAccesses;578 const size_t TopN =579 opts::ICPJumpTablesTopN ? opts::ICPJumpTablesTopN : opts::ICPTopN;580 size_t I = 0;581 for (; I < HotTargets.size(); ++I) {582 const uint64_t MemAccesses = HotTargets[I].first;583 if (100 * MemAccesses <584 TotalMemAccesses * opts::ICPJTTotalPercentThreshold)585 break;586 if (100 * MemAccesses <587 RemainingMemAccesses * opts::ICPJTRemainingPercentThreshold)588 break;589 if (TopN && I >= TopN)590 break;591 RemainingMemAccesses -= MemAccesses;592 593 const uint64_t JTIndex = HotTargets[I].second;594 Callsite &Target = Targets[findTargetsIndex(JTIndex)];595 596 NewTargets.push_back(Target);597 std::vector<uint64_t>({JTIndex}).swap(NewTargets.back().JTIndices);598 llvm::erase(Target.JTIndices, JTIndex);599 600 // Keep fixCFG counts sane if more indices use this same target later601 assert(IndicesPerTarget[Target.To.Sym] > 0 && "wrong map");602 NewTargets.back().Branches =603 Target.Branches / IndicesPerTarget[Target.To.Sym];604 NewTargets.back().Mispreds =605 Target.Mispreds / IndicesPerTarget[Target.To.Sym];606 assert(Target.Branches >= NewTargets.back().Branches);607 assert(Target.Mispreds >= NewTargets.back().Mispreds);608 Target.Branches -= NewTargets.back().Branches;609 Target.Mispreds -= NewTargets.back().Mispreds;610 }611 llvm::copy(Targets, std::back_inserter(NewTargets));612 std::swap(NewTargets, Targets);613 N = I;614 615 if (N == 0 && opts::Verbosity >= 1) {616 BC.outs() << "BOLT-INFO: ICP failed in " << *BB.getFunction() << " in "617 << BB.getName() << ": failed to meet thresholds after memory "618 << "profile data was loaded.\n";619 return SymTargets;620 }621 }622 623 for (size_t I = 0, TgtIdx = 0; I < N; ++TgtIdx) {624 Callsite &Target = Targets[TgtIdx];625 assert(Target.To.Sym && "All ICP targets must be to known symbols");626 assert(!Target.JTIndices.empty() && "Jump tables must have indices");627 for (uint64_t Idx : Target.JTIndices) {628 SymTargets.emplace_back(Target.To.Sym, Idx);629 ++I;630 }631 }632 633 return SymTargets;634}635 636IndirectCallPromotion::MethodInfoType IndirectCallPromotion::maybeGetVtableSyms(637 BinaryBasicBlock &BB, MCInst &Inst,638 const SymTargetsType &SymTargets) const {639 BinaryFunction &Function = *BB.getFunction();640 BinaryContext &BC = Function.getBinaryContext();641 std::vector<std::pair<MCSymbol *, uint64_t>> VtableSyms;642 std::vector<MCInst *> MethodFetchInsns;643 unsigned VtableReg, MethodReg;644 uint64_t MethodOffset;645 646 assert(!Function.getJumpTable(Inst) &&647 "Can't get vtable addrs for jump tables.");648 649 if (!Function.hasMemoryProfile() || !opts::EliminateLoads)650 return MethodInfoType();651 652 MutableArrayRef<MCInst> Insts(&BB.front(), &Inst + 1);653 if (!BC.MIB->analyzeVirtualMethodCall(Insts.begin(), Insts.end(),654 MethodFetchInsns, VtableReg, MethodReg,655 MethodOffset)) {656 DEBUG_VERBOSE(657 1, dbgs() << "BOLT-INFO: ICP unable to analyze method call in "658 << Function << " at @ " << (&Inst - &BB.front()) << "\n");659 return MethodInfoType();660 }661 662 ++TotalMethodLoadEliminationCandidates;663 664 DEBUG_VERBOSE(1, {665 dbgs() << "BOLT-INFO: ICP found virtual method call in " << Function666 << " at @ " << (&Inst - &BB.front()) << "\n";667 dbgs() << "BOLT-INFO: ICP method fetch instructions:\n";668 for (MCInst *Inst : MethodFetchInsns)669 BC.printInstruction(dbgs(), *Inst, 0, &Function);670 671 if (MethodFetchInsns.back() != &Inst)672 BC.printInstruction(dbgs(), Inst, 0, &Function);673 });674 675 // Try to get value profiling data for the method load instruction.676 auto ErrorOrMemAccessProfile =677 BC.MIB->tryGetAnnotationAs<MemoryAccessProfile>(*MethodFetchInsns.back(),678 "MemoryAccessProfile");679 if (!ErrorOrMemAccessProfile) {680 DEBUG_VERBOSE(1, dbgs()681 << "BOLT-INFO: ICP no memory profiling data found\n");682 return MethodInfoType();683 }684 MemoryAccessProfile &MemAccessProfile = ErrorOrMemAccessProfile.get();685 686 // Find the vtable that each method belongs to.687 std::map<const MCSymbol *, uint64_t> MethodToVtable;688 689 for (const AddressAccess &AccessInfo : MemAccessProfile.AddressAccessInfo) {690 uint64_t Address = AccessInfo.Offset;691 if (AccessInfo.MemoryObject)692 Address += AccessInfo.MemoryObject->getAddress();693 694 // Ignore bogus data.695 if (!Address)696 continue;697 698 const uint64_t VtableBase = Address - MethodOffset;699 700 DEBUG_VERBOSE(1, dbgs() << "BOLT-INFO: ICP vtable = "701 << Twine::utohexstr(VtableBase) << "+"702 << MethodOffset << "/" << AccessInfo.Count << "\n");703 704 if (ErrorOr<uint64_t> MethodAddr = BC.getPointerAtAddress(Address)) {705 BinaryData *MethodBD = BC.getBinaryDataAtAddress(MethodAddr.get());706 if (!MethodBD) // skip unknown methods707 continue;708 MCSymbol *MethodSym = MethodBD->getSymbol();709 MethodToVtable[MethodSym] = VtableBase;710 DEBUG_VERBOSE(1, {711 const BinaryFunction *Method = BC.getFunctionForSymbol(MethodSym);712 dbgs() << "BOLT-INFO: ICP found method = "713 << Twine::utohexstr(MethodAddr.get()) << "/"714 << (Method ? Method->getPrintName() : "") << "\n";715 });716 }717 }718 719 // Find the vtable for each target symbol.720 for (size_t I = 0; I < SymTargets.size(); ++I) {721 auto Itr = MethodToVtable.find(SymTargets[I].first);722 if (Itr != MethodToVtable.end()) {723 if (BinaryData *BD = BC.getBinaryDataContainingAddress(Itr->second)) {724 const uint64_t Addend = Itr->second - BD->getAddress();725 VtableSyms.emplace_back(BD->getSymbol(), Addend);726 continue;727 }728 }729 // Give up if we can't find the vtable for a method.730 DEBUG_VERBOSE(1, dbgs() << "BOLT-INFO: ICP can't find vtable for "731 << SymTargets[I].first->getName() << "\n");732 return MethodInfoType();733 }734 735 // Make sure the vtable reg is not clobbered by the argument passing code736 if (VtableReg != MethodReg) {737 for (MCInst *CurInst = MethodFetchInsns.front(); CurInst < &Inst;738 ++CurInst) {739 const MCInstrDesc &InstrInfo = BC.MII->get(CurInst->getOpcode());740 if (InstrInfo.hasDefOfPhysReg(*CurInst, VtableReg, *BC.MRI))741 return MethodInfoType();742 }743 }744 745 return MethodInfoType(VtableSyms, MethodFetchInsns);746}747 748std::vector<std::unique_ptr<BinaryBasicBlock>>749IndirectCallPromotion::rewriteCall(750 BinaryBasicBlock &IndCallBlock, const MCInst &CallInst,751 MCPlusBuilder::BlocksVectorTy &&ICPcode,752 const std::vector<MCInst *> &MethodFetchInsns) const {753 BinaryFunction &Function = *IndCallBlock.getFunction();754 MCPlusBuilder *MIB = Function.getBinaryContext().MIB.get();755 756 // Create new basic blocks with correct code in each one first.757 std::vector<std::unique_ptr<BinaryBasicBlock>> NewBBs;758 const bool IsTailCallOrJT =759 (MIB->isTailCall(CallInst) || Function.getJumpTable(CallInst));760 761 // If we are tracking the indirect call/jump address, propagate the address to762 // the ICP code.763 const std::optional<uint32_t> IndirectInstrOffset = MIB->getOffset(CallInst);764 if (IndirectInstrOffset) {765 for (auto &[Symbol, Instructions] : ICPcode)766 for (MCInst &Inst : Instructions)767 MIB->setOffset(Inst, *IndirectInstrOffset);768 }769 770 // Move instructions from the tail of the original call block771 // to the merge block.772 773 // Remember any pseudo instructions following a tail call. These774 // must be preserved and moved to the original block.775 InstructionListType TailInsts;776 const MCInst *TailInst = &CallInst;777 if (IsTailCallOrJT)778 while (TailInst + 1 < &(*IndCallBlock.end()) &&779 MIB->isPseudo(*(TailInst + 1)))780 TailInsts.push_back(*++TailInst);781 782 InstructionListType MovedInst = IndCallBlock.splitInstructions(&CallInst);783 // Link new BBs to the original input offset of the indirect call site or its784 // containing BB, so we can map samples recorded in new BBs back to the785 // original BB seen in the input binary (if using BAT).786 const uint32_t OrigOffset = IndirectInstrOffset787 ? *IndirectInstrOffset788 : IndCallBlock.getInputOffset();789 790 IndCallBlock.eraseInstructions(MethodFetchInsns.begin(),791 MethodFetchInsns.end());792 if (IndCallBlock.empty() ||793 (!MethodFetchInsns.empty() && MethodFetchInsns.back() == &CallInst))794 IndCallBlock.addInstructions(ICPcode.front().second.begin(),795 ICPcode.front().second.end());796 else797 IndCallBlock.replaceInstruction(std::prev(IndCallBlock.end()),798 ICPcode.front().second);799 IndCallBlock.addInstructions(TailInsts.begin(), TailInsts.end());800 801 for (auto Itr = ICPcode.begin() + 1; Itr != ICPcode.end(); ++Itr) {802 MCSymbol *&Sym = Itr->first;803 InstructionListType &Insts = Itr->second;804 assert(Sym);805 std::unique_ptr<BinaryBasicBlock> TBB = Function.createBasicBlock(Sym);806 TBB->setOffset(OrigOffset);807 for (MCInst &Inst : Insts) // sanitize new instructions.808 if (MIB->isCall(Inst))809 MIB->removeAnnotation(Inst, "CallProfile");810 TBB->addInstructions(Insts.begin(), Insts.end());811 NewBBs.emplace_back(std::move(TBB));812 }813 814 // Move tail of instructions from after the original call to815 // the merge block.816 if (!IsTailCallOrJT)817 NewBBs.back()->addInstructions(MovedInst.begin(), MovedInst.end());818 819 return NewBBs;820}821 822BinaryBasicBlock *823IndirectCallPromotion::fixCFG(BinaryBasicBlock &IndCallBlock,824 const bool IsTailCall, const bool IsJumpTable,825 IndirectCallPromotion::BasicBlocksVector &&NewBBs,826 const std::vector<Callsite> &Targets) const {827 BinaryFunction &Function = *IndCallBlock.getFunction();828 using BinaryBranchInfo = BinaryBasicBlock::BinaryBranchInfo;829 BinaryBasicBlock *MergeBlock = nullptr;830 831 // Scale indirect call counts to the execution count of the original832 // basic block containing the indirect call.833 uint64_t TotalCount = IndCallBlock.getKnownExecutionCount();834 uint64_t TotalIndirectBranches = 0;835 for (const Callsite &Target : Targets)836 TotalIndirectBranches += Target.Branches;837 if (TotalIndirectBranches == 0)838 TotalIndirectBranches = 1;839 BinaryBasicBlock::BranchInfoType BBI;840 BinaryBasicBlock::BranchInfoType ScaledBBI;841 for (const Callsite &Target : Targets) {842 const size_t NumEntries =843 std::max(static_cast<std::size_t>(1UL), Target.JTIndices.size());844 for (size_t I = 0; I < NumEntries; ++I) {845 BBI.push_back(846 BinaryBranchInfo{(Target.Branches + NumEntries - 1) / NumEntries,847 (Target.Mispreds + NumEntries - 1) / NumEntries});848 ScaledBBI.push_back(849 BinaryBranchInfo{uint64_t(TotalCount * Target.Branches /850 (NumEntries * TotalIndirectBranches)),851 uint64_t(TotalCount * Target.Mispreds /852 (NumEntries * TotalIndirectBranches))});853 }854 }855 856 if (IsJumpTable) {857 BinaryBasicBlock *NewIndCallBlock = NewBBs.back().get();858 IndCallBlock.moveAllSuccessorsTo(NewIndCallBlock);859 860 std::vector<MCSymbol *> SymTargets;861 for (const Callsite &Target : Targets) {862 const size_t NumEntries =863 std::max(static_cast<std::size_t>(1UL), Target.JTIndices.size());864 for (size_t I = 0; I < NumEntries; ++I)865 SymTargets.push_back(Target.To.Sym);866 }867 assert(SymTargets.size() > NewBBs.size() - 1 &&868 "There must be a target symbol associated with each new BB.");869 870 for (uint64_t I = 0; I < NewBBs.size(); ++I) {871 BinaryBasicBlock *SourceBB = I ? NewBBs[I - 1].get() : &IndCallBlock;872 SourceBB->setExecutionCount(TotalCount);873 874 BinaryBasicBlock *TargetBB =875 Function.getBasicBlockForLabel(SymTargets[I]);876 SourceBB->addSuccessor(TargetBB, ScaledBBI[I]); // taken877 878 TotalCount -= ScaledBBI[I].Count;879 SourceBB->addSuccessor(NewBBs[I].get(), TotalCount); // fall-through880 881 // Update branch info for the indirect jump.882 BinaryBasicBlock::BinaryBranchInfo &BranchInfo =883 NewIndCallBlock->getBranchInfo(*TargetBB);884 if (BranchInfo.Count > BBI[I].Count)885 BranchInfo.Count -= BBI[I].Count;886 else887 BranchInfo.Count = 0;888 889 if (BranchInfo.MispredictedCount > BBI[I].MispredictedCount)890 BranchInfo.MispredictedCount -= BBI[I].MispredictedCount;891 else892 BranchInfo.MispredictedCount = 0;893 }894 } else {895 assert(NewBBs.size() >= 2);896 assert(NewBBs.size() % 2 == 1 || IndCallBlock.succ_empty());897 assert(NewBBs.size() % 2 == 1 || IsTailCall);898 899 auto ScaledBI = ScaledBBI.begin();900 auto updateCurrentBranchInfo = [&] {901 assert(ScaledBI != ScaledBBI.end());902 TotalCount -= ScaledBI->Count;903 ++ScaledBI;904 };905 906 if (!IsTailCall) {907 MergeBlock = NewBBs.back().get();908 IndCallBlock.moveAllSuccessorsTo(MergeBlock);909 }910 911 // Fix up successors and execution counts.912 updateCurrentBranchInfo();913 IndCallBlock.addSuccessor(NewBBs[1].get(), TotalCount);914 IndCallBlock.addSuccessor(NewBBs[0].get(), ScaledBBI[0]);915 916 const size_t Adj = IsTailCall ? 1 : 2;917 for (size_t I = 0; I < NewBBs.size() - Adj; ++I) {918 assert(TotalCount <= IndCallBlock.getExecutionCount() ||919 TotalCount <= uint64_t(TotalIndirectBranches));920 uint64_t ExecCount = ScaledBBI[(I + 1) / 2].Count;921 if (I % 2 == 0) {922 if (MergeBlock)923 NewBBs[I]->addSuccessor(MergeBlock, ScaledBBI[(I + 1) / 2].Count);924 } else {925 assert(I + 2 < NewBBs.size());926 updateCurrentBranchInfo();927 NewBBs[I]->addSuccessor(NewBBs[I + 2].get(), TotalCount);928 NewBBs[I]->addSuccessor(NewBBs[I + 1].get(), ScaledBBI[(I + 1) / 2]);929 ExecCount += TotalCount;930 }931 NewBBs[I]->setExecutionCount(ExecCount);932 }933 934 if (MergeBlock) {935 // Arrange for the MergeBlock to be the fallthrough for the first936 // promoted call block.937 std::unique_ptr<BinaryBasicBlock> MBPtr;938 std::swap(MBPtr, NewBBs.back());939 NewBBs.pop_back();940 NewBBs.emplace(NewBBs.begin() + 1, std::move(MBPtr));941 // TODO: is COUNT_FALLTHROUGH_EDGE the right thing here?942 NewBBs.back()->addSuccessor(MergeBlock, TotalCount); // uncond branch943 }944 }945 946 // Update the execution count.947 NewBBs.back()->setExecutionCount(TotalCount);948 949 // Update BB and BB layout.950 Function.insertBasicBlocks(&IndCallBlock, std::move(NewBBs));951 assert(Function.validateCFG());952 953 return MergeBlock;954}955 956size_t IndirectCallPromotion::canPromoteCallsite(957 const BinaryBasicBlock &BB, const MCInst &Inst,958 const std::vector<Callsite> &Targets, uint64_t NumCalls) {959 BinaryFunction *BF = BB.getFunction();960 const BinaryContext &BC = BF->getBinaryContext();961 962 if (BB.getKnownExecutionCount() < opts::ExecutionCountThreshold)963 return 0;964 965 const bool IsJumpTable = BF->getJumpTable(Inst);966 967 auto computeStats = [&](size_t N) {968 for (size_t I = 0; I < N; ++I)969 if (IsJumpTable)970 TotalNumFrequentJmps += Targets[I].Branches;971 else972 TotalNumFrequentCalls += Targets[I].Branches;973 };974 975 // If we have no targets (or no calls), skip this callsite.976 if (Targets.empty() || !NumCalls) {977 if (opts::Verbosity >= 1) {978 const ptrdiff_t InstIdx = &Inst - &(*BB.begin());979 BC.outs() << "BOLT-INFO: ICP failed in " << *BF << " @ " << InstIdx980 << " in " << BB.getName() << ", calls = " << NumCalls981 << ", targets empty or NumCalls == 0.\n";982 }983 return 0;984 }985 986 size_t TopN = opts::ICPTopN;987 if (IsJumpTable)988 TopN = opts::ICPJumpTablesTopN ? opts::ICPJumpTablesTopN : TopN;989 else990 TopN = opts::ICPCallsTopN ? opts::ICPCallsTopN : TopN;991 992 const size_t TrialN = TopN ? std::min(TopN, Targets.size()) : Targets.size();993 994 if (opts::ICPTopCallsites && !BC.MIB->hasAnnotation(Inst, "DoICP"))995 return 0;996 997 // Pick the top N targets.998 uint64_t TotalMispredictsTopN = 0;999 size_t N = 0;1000 1001 if (opts::ICPUseMispredicts &&1002 (!IsJumpTable || opts::ICPJumpTablesByTarget)) {1003 // Count total number of mispredictions for (at most) the top N targets.1004 // We may choose a smaller N (TrialN vs. N) if the frequency threshold1005 // is exceeded by fewer targets.1006 double Threshold = double(opts::ICPMispredictThreshold);1007 for (size_t I = 0; I < TrialN && Threshold > 0; ++I, ++N) {1008 Threshold -= (100.0 * Targets[I].Mispreds) / NumCalls;1009 TotalMispredictsTopN += Targets[I].Mispreds;1010 }1011 computeStats(N);1012 1013 // Compute the misprediction frequency of the top N call targets. If this1014 // frequency is greater than the threshold, we should try ICP on this1015 // callsite.1016 const double TopNFrequency = (100.0 * TotalMispredictsTopN) / NumCalls;1017 if (TopNFrequency == 0 || TopNFrequency < opts::ICPMispredictThreshold) {1018 if (opts::Verbosity >= 1) {1019 const ptrdiff_t InstIdx = &Inst - &(*BB.begin());1020 BC.outs() << "BOLT-INFO: ICP failed in " << *BF << " @ " << InstIdx1021 << " in " << BB.getName() << ", calls = " << NumCalls1022 << ", top N mis. frequency " << format("%.1f", TopNFrequency)1023 << "% < " << opts::ICPMispredictThreshold << "%\n";1024 }1025 return 0;1026 }1027 } else {1028 size_t MaxTargets = 0;1029 1030 // Count total number of calls for (at most) the top N targets.1031 // We may choose a smaller N (TrialN vs. N) if the frequency threshold1032 // is exceeded by fewer targets.1033 const unsigned TotalThreshold = IsJumpTable1034 ? opts::ICPJTTotalPercentThreshold1035 : opts::ICPCallsTotalPercentThreshold;1036 const unsigned RemainingThreshold =1037 IsJumpTable ? opts::ICPJTRemainingPercentThreshold1038 : opts::ICPCallsRemainingPercentThreshold;1039 uint64_t NumRemainingCalls = NumCalls;1040 for (size_t I = 0; I < TrialN; ++I, ++MaxTargets) {1041 if (100 * Targets[I].Branches < NumCalls * TotalThreshold)1042 break;1043 if (100 * Targets[I].Branches < NumRemainingCalls * RemainingThreshold)1044 break;1045 if (N + (Targets[I].JTIndices.empty() ? 1 : Targets[I].JTIndices.size()) >1046 TrialN)1047 break;1048 TotalMispredictsTopN += Targets[I].Mispreds;1049 NumRemainingCalls -= Targets[I].Branches;1050 N += Targets[I].JTIndices.empty() ? 1 : Targets[I].JTIndices.size();1051 }1052 computeStats(MaxTargets);1053 1054 // Don't check misprediction frequency for jump tables -- we don't really1055 // care as long as we are saving loads from the jump table.1056 if (!IsJumpTable || opts::ICPJumpTablesByTarget) {1057 // Compute the misprediction frequency of the top N call targets. If1058 // this frequency is less than the threshold, we should skip ICP at1059 // this callsite.1060 const double TopNMispredictFrequency =1061 (100.0 * TotalMispredictsTopN) / NumCalls;1062 1063 if (TopNMispredictFrequency < opts::ICPMispredictThreshold) {1064 if (opts::Verbosity >= 1) {1065 const ptrdiff_t InstIdx = &Inst - &(*BB.begin());1066 BC.outs() << "BOLT-INFO: ICP failed in " << *BF << " @ " << InstIdx1067 << " in " << BB.getName() << ", calls = " << NumCalls1068 << ", top N mispredict frequency "1069 << format("%.1f", TopNMispredictFrequency) << "% < "1070 << opts::ICPMispredictThreshold << "%\n";1071 }1072 return 0;1073 }1074 }1075 }1076 1077 // Filter by inline-ability of target functions, stop at first target that1078 // can't be inlined.1079 if (!IsJumpTable && opts::ICPPeelForInline) {1080 for (size_t I = 0; I < N; ++I) {1081 const MCSymbol *TargetSym = Targets[I].To.Sym;1082 const BinaryFunction *TargetBF = BC.getFunctionForSymbol(TargetSym);1083 if (!TargetBF || !BinaryFunctionPass::shouldOptimize(*TargetBF) ||1084 getInliningInfo(*TargetBF).Type == InliningType::INL_NONE) {1085 N = I;1086 break;1087 }1088 }1089 }1090 1091 // Filter functions that can have ICP applied (for debugging)1092 if (!opts::ICPFuncsList.empty()) {1093 for (std::string &Name : opts::ICPFuncsList)1094 if (BF->hasName(Name))1095 return N;1096 return 0;1097 }1098 1099 return N;1100}1101 1102void IndirectCallPromotion::printCallsiteInfo(1103 const BinaryBasicBlock &BB, const MCInst &Inst,1104 const std::vector<Callsite> &Targets, const size_t N,1105 uint64_t NumCalls) const {1106 BinaryContext &BC = BB.getFunction()->getBinaryContext();1107 const bool IsTailCall = BC.MIB->isTailCall(Inst);1108 const bool IsJumpTable = BB.getFunction()->getJumpTable(Inst);1109 const ptrdiff_t InstIdx = &Inst - &(*BB.begin());1110 1111 BC.outs() << "BOLT-INFO: ICP candidate branch info: " << *BB.getFunction()1112 << " @ " << InstIdx << " in " << BB.getName()1113 << " -> calls = " << NumCalls1114 << (IsTailCall ? " (tail)" : (IsJumpTable ? " (jump table)" : ""))1115 << "\n";1116 for (size_t I = 0; I < N; I++) {1117 const double Frequency = 100.0 * Targets[I].Branches / NumCalls;1118 const double MisFrequency = 100.0 * Targets[I].Mispreds / NumCalls;1119 BC.outs() << "BOLT-INFO: ";1120 if (Targets[I].To.Sym)1121 BC.outs() << Targets[I].To.Sym->getName();1122 else1123 BC.outs() << Targets[I].To.Addr;1124 BC.outs() << ", calls = " << Targets[I].Branches1125 << ", mispreds = " << Targets[I].Mispreds1126 << ", taken freq = " << format("%.1f", Frequency) << "%"1127 << ", mis. freq = " << format("%.1f", MisFrequency) << "%";1128 bool First = true;1129 for (uint64_t JTIndex : Targets[I].JTIndices) {1130 BC.outs() << (First ? ", indices = " : ", ") << JTIndex;1131 First = false;1132 }1133 BC.outs() << "\n";1134 }1135 1136 LLVM_DEBUG({1137 dbgs() << "BOLT-INFO: ICP original call instruction:";1138 BC.printInstruction(dbgs(), Inst, Targets[0].From.Addr, nullptr, true);1139 });1140}1141 1142Error IndirectCallPromotion::runOnFunctions(BinaryContext &BC) {1143 if (opts::ICP == ICP_NONE)1144 return Error::success();1145 1146 auto &BFs = BC.getBinaryFunctions();1147 1148 const bool OptimizeCalls = (opts::ICP == ICP_CALLS || opts::ICP == ICP_ALL);1149 const bool OptimizeJumpTables =1150 (opts::ICP == ICP_JUMP_TABLES || opts::ICP == ICP_ALL);1151 1152 std::unique_ptr<RegAnalysis> RA;1153 std::unique_ptr<BinaryFunctionCallGraph> CG;1154 if (OptimizeJumpTables) {1155 CG.reset(new BinaryFunctionCallGraph(buildCallGraph(BC)));1156 RA.reset(new RegAnalysis(BC, &BFs, &*CG));1157 }1158 1159 // If icp-top-callsites is enabled, compute the total number of indirect1160 // calls and then optimize the hottest callsites that contribute to that1161 // total.1162 SetVector<BinaryFunction *> Functions;1163 if (opts::ICPTopCallsites == 0) {1164 for (auto &KV : BFs)1165 Functions.insert(&KV.second);1166 } else {1167 using IndirectCallsite = std::tuple<uint64_t, MCInst *, BinaryFunction *>;1168 std::vector<IndirectCallsite> IndirectCalls;1169 size_t TotalIndirectCalls = 0;1170 1171 // Find all the indirect callsites.1172 for (auto &BFIt : BFs) {1173 BinaryFunction &Function = BFIt.second;1174 1175 if (!shouldOptimize(Function))1176 continue;1177 1178 const bool HasLayout = !Function.getLayout().block_empty();1179 1180 for (BinaryBasicBlock &BB : Function) {1181 if (HasLayout && Function.isSplit() && BB.isCold())1182 continue;1183 1184 for (MCInst &Inst : BB) {1185 const bool IsJumpTable = Function.getJumpTable(Inst);1186 const bool HasIndirectCallProfile =1187 BC.MIB->hasAnnotation(Inst, "CallProfile");1188 const bool IsDirectCall =1189 (BC.MIB->isCall(Inst) && BC.MIB->getTargetSymbol(Inst, 0));1190 1191 if (!IsDirectCall &&1192 ((HasIndirectCallProfile && !IsJumpTable && OptimizeCalls) ||1193 (IsJumpTable && OptimizeJumpTables))) {1194 uint64_t NumCalls = 0;1195 for (const Callsite &BInfo : getCallTargets(BB, Inst))1196 NumCalls += BInfo.Branches;1197 IndirectCalls.push_back(1198 std::make_tuple(NumCalls, &Inst, &Function));1199 TotalIndirectCalls += NumCalls;1200 }1201 }1202 }1203 }1204 1205 // Sort callsites by execution count.1206 llvm::sort(reverse(IndirectCalls));1207 1208 // Find callsites that contribute to the top "opts::ICPTopCallsites"%1209 // number of calls.1210 const float TopPerc = opts::ICPTopCallsites / 100.0f;1211 int64_t MaxCalls = TotalIndirectCalls * TopPerc;1212 uint64_t LastFreq = std::numeric_limits<uint64_t>::max();1213 size_t Num = 0;1214 for (const IndirectCallsite &IC : IndirectCalls) {1215 const uint64_t CurFreq = std::get<0>(IC);1216 // Once we decide to stop, include at least all branches that share the1217 // same frequency of the last one to avoid non-deterministic behavior1218 // (e.g. turning on/off ICP depending on the order of functions)1219 if (MaxCalls <= 0 && CurFreq != LastFreq)1220 break;1221 MaxCalls -= CurFreq;1222 LastFreq = CurFreq;1223 BC.MIB->addAnnotation(*std::get<1>(IC), "DoICP", true);1224 Functions.insert(std::get<2>(IC));1225 ++Num;1226 }1227 BC.outs() << "BOLT-INFO: ICP Total indirect calls = " << TotalIndirectCalls1228 << ", " << Num << " callsites cover " << opts::ICPTopCallsites1229 << "% of all indirect calls\n";1230 }1231 1232 for (BinaryFunction *FuncPtr : Functions) {1233 BinaryFunction &Function = *FuncPtr;1234 1235 if (!shouldOptimize(Function))1236 continue;1237 1238 const bool HasLayout = !Function.getLayout().block_empty();1239 1240 // Total number of indirect calls issued from the current Function.1241 // (a fraction of TotalIndirectCalls)1242 uint64_t FuncTotalIndirectCalls = 0;1243 uint64_t FuncTotalIndirectJmps = 0;1244 1245 std::vector<BinaryBasicBlock *> BBs;1246 for (BinaryBasicBlock &BB : Function) {1247 // Skip indirect calls in cold blocks.1248 if (!HasLayout || !Function.isSplit() || !BB.isCold())1249 BBs.push_back(&BB);1250 }1251 if (BBs.empty())1252 continue;1253 1254 DataflowInfoManager Info(Function, RA.get(), nullptr);1255 while (!BBs.empty()) {1256 BinaryBasicBlock *BB = BBs.back();1257 BBs.pop_back();1258 1259 for (unsigned Idx = 0; Idx < BB->size(); ++Idx) {1260 MCInst &Inst = BB->getInstructionAtIndex(Idx);1261 const ptrdiff_t InstIdx = &Inst - &(*BB->begin());1262 const bool IsTailCall = BC.MIB->isTailCall(Inst);1263 const bool HasIndirectCallProfile =1264 BC.MIB->hasAnnotation(Inst, "CallProfile");1265 const bool IsJumpTable = Function.getJumpTable(Inst);1266 1267 if (BC.MIB->isCall(Inst))1268 TotalCalls += BB->getKnownExecutionCount();1269 1270 if (IsJumpTable && !OptimizeJumpTables)1271 continue;1272 1273 if (!IsJumpTable && (!HasIndirectCallProfile || !OptimizeCalls))1274 continue;1275 1276 // Ignore direct calls.1277 if (BC.MIB->isCall(Inst) && BC.MIB->getTargetSymbol(Inst, 0))1278 continue;1279 1280 assert((BC.MIB->isCall(Inst) || BC.MIB->isIndirectBranch(Inst)) &&1281 "expected a call or an indirect jump instruction");1282 1283 if (IsJumpTable)1284 ++TotalJumpTableCallsites;1285 else1286 ++TotalIndirectCallsites;1287 1288 std::vector<Callsite> Targets = getCallTargets(*BB, Inst);1289 1290 // Compute the total number of calls from this particular callsite.1291 uint64_t NumCalls = 0;1292 for (const Callsite &BInfo : Targets)1293 NumCalls += BInfo.Branches;1294 if (!IsJumpTable)1295 FuncTotalIndirectCalls += NumCalls;1296 else1297 FuncTotalIndirectJmps += NumCalls;1298 1299 // If FLAGS regs is alive after this jmp site, do not try1300 // promoting because we will clobber FLAGS.1301 if (IsJumpTable) {1302 ErrorOr<const BitVector &> State =1303 Info.getLivenessAnalysis().getStateBefore(Inst);1304 if (!State || (State && (*State)[BC.MIB->getFlagsReg()])) {1305 if (opts::Verbosity >= 1)1306 BC.outs() << "BOLT-INFO: ICP failed in " << Function << " @ "1307 << InstIdx << " in " << BB->getName()1308 << ", calls = " << NumCalls1309 << (State ? ", cannot clobber flags reg.\n"1310 : ", no liveness data available.\n");1311 continue;1312 }1313 }1314 1315 // Should this callsite be optimized? Return the number of targets1316 // to use when promoting this call. A value of zero means to skip1317 // this callsite.1318 size_t N = canPromoteCallsite(*BB, Inst, Targets, NumCalls);1319 1320 // If it is a jump table and it failed to meet our initial threshold,1321 // proceed to findCallTargetSymbols -- it may reevaluate N if1322 // memory profile is present1323 if (!N && !IsJumpTable)1324 continue;1325 1326 if (opts::Verbosity >= 1)1327 printCallsiteInfo(*BB, Inst, Targets, N, NumCalls);1328 1329 // Find MCSymbols or absolute addresses for each call target.1330 MCInst *TargetFetchInst = nullptr;1331 const SymTargetsType SymTargets =1332 findCallTargetSymbols(Targets, N, *BB, Inst, TargetFetchInst);1333 1334 // findCallTargetSymbols may have changed N if mem profile is available1335 // for jump tables1336 if (!N)1337 continue;1338 1339 LLVM_DEBUG(printDecision(dbgs(), Targets, N));1340 1341 // If we can't resolve any of the target symbols, punt on this callsite.1342 // TODO: can this ever happen?1343 if (SymTargets.size() < N) {1344 const size_t LastTarget = SymTargets.size();1345 if (opts::Verbosity >= 1)1346 BC.outs() << "BOLT-INFO: ICP failed in " << Function << " @ "1347 << InstIdx << " in " << BB->getName()1348 << ", calls = " << NumCalls1349 << ", ICP failed to find target symbol for "1350 << Targets[LastTarget].To.Sym->getName() << "\n";1351 continue;1352 }1353 1354 MethodInfoType MethodInfo;1355 1356 if (!IsJumpTable) {1357 MethodInfo = maybeGetVtableSyms(*BB, Inst, SymTargets);1358 TotalMethodLoadsEliminated += MethodInfo.first.empty() ? 0 : 1;1359 LLVM_DEBUG(dbgs()1360 << "BOLT-INFO: ICP "1361 << (!MethodInfo.first.empty() ? "found" : "did not find")1362 << " vtables for all methods.\n");1363 } else if (TargetFetchInst) {1364 ++TotalIndexBasedJumps;1365 MethodInfo.second.push_back(TargetFetchInst);1366 }1367 1368 // Generate new promoted call code for this callsite.1369 MCPlusBuilder::BlocksVectorTy ICPcode =1370 (IsJumpTable && !opts::ICPJumpTablesByTarget)1371 ? BC.MIB->jumpTablePromotion(Inst, SymTargets,1372 MethodInfo.second, BC.Ctx.get())1373 : BC.MIB->indirectCallPromotion(1374 Inst, SymTargets, MethodInfo.first, MethodInfo.second,1375 opts::ICPOldCodeSequence, BC.Ctx.get());1376 1377 if (ICPcode.empty()) {1378 if (opts::Verbosity >= 1)1379 BC.outs() << "BOLT-INFO: ICP failed in " << Function << " @ "1380 << InstIdx << " in " << BB->getName()1381 << ", calls = " << NumCalls1382 << ", unable to generate promoted call code.\n";1383 continue;1384 }1385 1386 LLVM_DEBUG({1387 uint64_t Offset = Targets[0].From.Addr;1388 dbgs() << "BOLT-INFO: ICP indirect call code:\n";1389 for (const auto &entry : ICPcode) {1390 const MCSymbol *const &Sym = entry.first;1391 const InstructionListType &Insts = entry.second;1392 if (Sym)1393 dbgs() << Sym->getName() << ":\n";1394 Offset = BC.printInstructions(dbgs(), Insts.begin(), Insts.end(),1395 Offset);1396 }1397 dbgs() << "---------------------------------------------------\n";1398 });1399 1400 // Rewrite the CFG with the newly generated ICP code.1401 std::vector<std::unique_ptr<BinaryBasicBlock>> NewBBs =1402 rewriteCall(*BB, Inst, std::move(ICPcode), MethodInfo.second);1403 1404 // Fix the CFG after inserting the new basic blocks.1405 BinaryBasicBlock *MergeBlock =1406 fixCFG(*BB, IsTailCall, IsJumpTable, std::move(NewBBs), Targets);1407 1408 // Since the tail of the original block was split off and it may contain1409 // additional indirect calls, we must add the merge block to the set of1410 // blocks to process.1411 if (MergeBlock)1412 BBs.push_back(MergeBlock);1413 1414 if (opts::Verbosity >= 1)1415 BC.outs() << "BOLT-INFO: ICP succeeded in " << Function << " @ "1416 << InstIdx << " in " << BB->getName()1417 << " -> calls = " << NumCalls << "\n";1418 1419 if (IsJumpTable)1420 ++TotalOptimizedJumpTableCallsites;1421 else1422 ++TotalOptimizedIndirectCallsites;1423 1424 Modified.insert(&Function);1425 }1426 }1427 TotalIndirectCalls += FuncTotalIndirectCalls;1428 TotalIndirectJmps += FuncTotalIndirectJmps;1429 }1430 1431 BC.outs()1432 << "BOLT-INFO: ICP total indirect callsites with profile = "1433 << TotalIndirectCallsites << "\n"1434 << "BOLT-INFO: ICP total jump table callsites = "1435 << TotalJumpTableCallsites << "\n"1436 << "BOLT-INFO: ICP total number of calls = " << TotalCalls << "\n"1437 << "BOLT-INFO: ICP percentage of calls that are indirect = "1438 << format("%.1f", (100.0 * TotalIndirectCalls) / TotalCalls) << "%\n"1439 << "BOLT-INFO: ICP percentage of indirect calls that can be "1440 "optimized = "1441 << format("%.1f", (100.0 * TotalNumFrequentCalls) /1442 std::max<size_t>(TotalIndirectCalls, 1))1443 << "%\n"1444 << "BOLT-INFO: ICP percentage of indirect callsites that are "1445 "optimized = "1446 << format("%.1f", (100.0 * TotalOptimizedIndirectCallsites) /1447 std::max<uint64_t>(TotalIndirectCallsites, 1))1448 << "%\n"1449 << "BOLT-INFO: ICP number of method load elimination candidates = "1450 << TotalMethodLoadEliminationCandidates << "\n"1451 << "BOLT-INFO: ICP percentage of method calls candidates that have "1452 "loads eliminated = "1453 << format("%.1f",1454 (100.0 * TotalMethodLoadsEliminated) /1455 std::max<uint64_t>(TotalMethodLoadEliminationCandidates, 1))1456 << "%\n"1457 << "BOLT-INFO: ICP percentage of indirect branches that are "1458 "optimized = "1459 << format("%.1f", (100.0 * TotalNumFrequentJmps) /1460 std::max<uint64_t>(TotalIndirectJmps, 1))1461 << "%\n"1462 << "BOLT-INFO: ICP percentage of jump table callsites that are "1463 << "optimized = "1464 << format("%.1f", (100.0 * TotalOptimizedJumpTableCallsites) /1465 std::max<uint64_t>(TotalJumpTableCallsites, 1))1466 << "%\n"1467 << "BOLT-INFO: ICP number of jump table callsites that can use hot "1468 << "indices = " << TotalIndexBasedCandidates << "\n"1469 << "BOLT-INFO: ICP percentage of jump table callsites that use hot "1470 "indices = "1471 << format("%.1f", (100.0 * TotalIndexBasedJumps) /1472 std::max<uint64_t>(TotalIndexBasedCandidates, 1))1473 << "%\n";1474 1475#ifndef NDEBUG1476 verifyProfile(BFs);1477#endif1478 return Error::success();1479}1480 1481} // namespace bolt1482} // namespace llvm1483