610 lines · cpp
1//===- bolt/Passes/Inliner.cpp - Inlining pass for low-level binary IR ----===//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 Inliner class used for inlining binary functions.10//11// The current inliner has a limited callee support12// (see Inliner::getInliningInfo() for the most up-to-date details):13//14// * No exception handling15// * No jump tables16// * Single entry point17// * CFI update not supported - breaks unwinding18// * Regular Call Sites:19// - only leaf functions (or callees with only tail calls)20// * no invokes (they can't be tail calls)21// - no direct use of %rsp22// * Tail Call Sites:23// - since the stack is unmodified, the regular call limitations are lifted24//25//===----------------------------------------------------------------------===//26 27#include "bolt/Passes/Inliner.h"28#include "bolt/Core/MCPlus.h"29#include "llvm/Support/CommandLine.h"30 31#define DEBUG_TYPE "bolt-inliner"32 33using namespace llvm;34 35namespace opts {36 37extern cl::OptionCategory BoltOptCategory;38 39static cl::opt<bool>40 AdjustProfile("inline-ap",41 cl::desc("adjust function profile after inlining"),42 cl::cat(BoltOptCategory));43 44static cl::list<std::string>45ForceInlineFunctions("force-inline",46 cl::CommaSeparated,47 cl::desc("list of functions to always consider for inlining"),48 cl::value_desc("func1,func2,func3,..."),49 cl::Hidden,50 cl::cat(BoltOptCategory));51 52static cl::list<std::string> SkipInlineFunctions(53 "skip-inline", cl::CommaSeparated,54 cl::desc("list of functions to never consider for inlining"),55 cl::value_desc("func1,func2,func3,..."), cl::Hidden,56 cl::cat(BoltOptCategory));57 58static cl::opt<bool> InlineAll("inline-all", cl::desc("inline all functions"),59 cl::cat(BoltOptCategory));60 61static cl::opt<bool> InlineIgnoreLeafCFI(62 "inline-ignore-leaf-cfi",63 cl::desc("inline leaf functions with CFI programs (can break unwinding)"),64 cl::init(true), cl::ReallyHidden, cl::cat(BoltOptCategory));65 66static cl::opt<bool> InlineIgnoreCFI(67 "inline-ignore-cfi",68 cl::desc(69 "inline functions with CFI programs (can break exception handling)"),70 cl::ReallyHidden, cl::cat(BoltOptCategory));71 72static cl::opt<unsigned>73 InlineLimit("inline-limit",74 cl::desc("maximum number of call sites to inline"), cl::init(0),75 cl::Hidden, cl::cat(BoltOptCategory));76 77static cl::opt<unsigned>78 InlineMaxIters("inline-max-iters",79 cl::desc("maximum number of inline iterations"), cl::init(3),80 cl::Hidden, cl::cat(BoltOptCategory));81 82static cl::opt<bool> InlineSmallFunctions(83 "inline-small-functions",84 cl::desc("inline functions if increase in size is less than defined by "85 "-inline-small-functions-bytes"),86 cl::cat(BoltOptCategory));87 88static cl::opt<unsigned> InlineSmallFunctionsBytes(89 "inline-small-functions-bytes",90 cl::desc("max number of bytes for the function to be considered small for "91 "inlining purposes"),92 cl::init(4), cl::Hidden, cl::cat(BoltOptCategory));93 94static cl::opt<bool> NoInline(95 "no-inline",96 cl::desc("disable all inlining (overrides other inlining options)"),97 cl::cat(BoltOptCategory));98 99/// This function returns true if any of inlining options are specified and the100/// inlining pass should be executed. Whenever a new inlining option is added,101/// this function should reflect the change.102bool inliningEnabled() {103 return !NoInline &&104 (InlineAll || InlineSmallFunctions || !ForceInlineFunctions.empty());105}106 107bool mustConsider(const llvm::bolt::BinaryFunction &Function) {108 for (std::string &Name : opts::ForceInlineFunctions)109 if (Function.hasName(Name))110 return true;111 return false;112}113 114bool mustSkip(const llvm::bolt::BinaryFunction &Function) {115 return llvm::any_of(opts::SkipInlineFunctions, [&](const std::string &Name) {116 return Function.hasName(Name);117 });118}119 120void syncOptions() {121 if (opts::InlineIgnoreCFI)122 opts::InlineIgnoreLeafCFI = true;123 124 if (opts::InlineAll)125 opts::InlineSmallFunctions = true;126}127 128} // namespace opts129 130namespace llvm {131namespace bolt {132 133uint64_t Inliner::SizeOfCallInst;134uint64_t Inliner::SizeOfTailCallInst;135 136uint64_t Inliner::getSizeOfCallInst(const BinaryContext &BC) {137 if (SizeOfCallInst)138 return SizeOfCallInst;139 140 MCInst Inst;141 BC.MIB->createCall(Inst, BC.Ctx->createNamedTempSymbol(), BC.Ctx.get());142 SizeOfCallInst = BC.computeInstructionSize(Inst);143 144 return SizeOfCallInst;145}146 147uint64_t Inliner::getSizeOfTailCallInst(const BinaryContext &BC) {148 if (SizeOfTailCallInst)149 return SizeOfTailCallInst;150 151 MCInst Inst;152 BC.MIB->createTailCall(Inst, BC.Ctx->createNamedTempSymbol(), BC.Ctx.get());153 SizeOfTailCallInst = BC.computeInstructionSize(Inst);154 155 return SizeOfTailCallInst;156}157 158InliningInfo getInliningInfo(const BinaryFunction &BF) {159 const BinaryContext &BC = BF.getBinaryContext();160 bool DirectSP = false;161 bool HasCFI = false;162 bool IsLeaf = true;163 164 // Perform necessary checks unless the option overrides it.165 if (!opts::mustConsider(BF)) {166 if (BF.hasSDTMarker())167 return INL_NONE;168 169 if (BF.hasEHRanges())170 return INL_NONE;171 172 if (BF.isMultiEntry())173 return INL_NONE;174 175 if (BF.hasJumpTables())176 return INL_NONE;177 178 const MCPhysReg SPReg = BC.MIB->getStackPointer();179 for (const BinaryBasicBlock &BB : BF) {180 for (const MCInst &Inst : BB) {181 // Tail calls are marked as implicitly using the stack pointer and they182 // could be inlined.183 if (BC.MIB->isTailCall(Inst))184 break;185 186 if (BC.MIB->isCFI(Inst)) {187 HasCFI = true;188 continue;189 }190 191 if (BC.MIB->isCall(Inst))192 IsLeaf = false;193 194 // Push/pop instructions are straightforward to handle.195 if (BC.MIB->isPush(Inst) || BC.MIB->isPop(Inst))196 continue;197 198 // Pointer signing and authenticatin instructions are used around199 // Push and Pop. These are also straightforward to handle.200 if (BC.isAArch64() &&201 (BC.MIB->isPSignOnLR(Inst) || BC.MIB->isPAuthOnLR(Inst) ||202 BC.MIB->isPAuthAndRet(Inst)))203 continue;204 205 DirectSP |= BC.MIB->hasDefOfPhysReg(Inst, SPReg) ||206 BC.MIB->hasUseOfPhysReg(Inst, SPReg);207 }208 }209 }210 211 if (HasCFI) {212 if (!opts::InlineIgnoreLeafCFI)213 return INL_NONE;214 215 if (!IsLeaf && !opts::InlineIgnoreCFI)216 return INL_NONE;217 }218 219 InliningInfo Info(DirectSP ? INL_TAILCALL : INL_ANY);220 221 size_t Size = BF.estimateSize();222 223 Info.SizeAfterInlining = Size;224 Info.SizeAfterTailCallInlining = Size;225 226 // Handle special case of the known size reduction.227 if (BF.size() == 1) {228 // For a regular call the last return instruction could be removed229 // (or converted to a branch).230 const MCInst *LastInst = BF.back().getLastNonPseudoInstr();231 if (LastInst && BC.MIB->isReturn(*LastInst) &&232 !BC.MIB->isTailCall(*LastInst)) {233 const uint64_t RetInstSize = BC.computeInstructionSize(*LastInst);234 assert(Size >= RetInstSize);235 Info.SizeAfterInlining -= RetInstSize;236 }237 }238 239 return Info;240}241 242void Inliner::findInliningCandidates(BinaryContext &BC) {243 for (const auto &BFI : BC.getBinaryFunctions()) {244 const BinaryFunction &Function = BFI.second;245 if (!shouldOptimize(Function) || opts::mustSkip(Function))246 continue;247 const InliningInfo InlInfo = getInliningInfo(Function);248 if (InlInfo.Type != INL_NONE)249 InliningCandidates[&Function] = InlInfo;250 }251}252 253std::pair<BinaryBasicBlock *, BinaryBasicBlock::iterator>254Inliner::inlineCall(BinaryBasicBlock &CallerBB,255 BinaryBasicBlock::iterator CallInst,256 const BinaryFunction &Callee) {257 BinaryFunction &CallerFunction = *CallerBB.getFunction();258 BinaryContext &BC = CallerFunction.getBinaryContext();259 auto &MIB = *BC.MIB;260 261 assert(MIB.isCall(*CallInst) && "can only inline a call or a tail call");262 assert(!Callee.isMultiEntry() &&263 "cannot inline function with multiple entries");264 assert(!Callee.hasJumpTables() &&265 "cannot inline function with jump table(s)");266 267 // Get information about the call site.268 const bool CSIsInvoke = BC.MIB->isInvoke(*CallInst);269 const bool CSIsTailCall = BC.MIB->isTailCall(*CallInst);270 const int64_t CSGNUArgsSize = BC.MIB->getGnuArgsSize(*CallInst);271 const std::optional<MCPlus::MCLandingPad> CSEHInfo =272 BC.MIB->getEHInfo(*CallInst);273 274 // Split basic block at the call site if there will be more incoming edges275 // coming from the callee.276 BinaryBasicBlock *FirstInlinedBB = &CallerBB;277 if (Callee.front().pred_size() && CallInst != CallerBB.begin()) {278 FirstInlinedBB = CallerBB.splitAt(CallInst);279 CallInst = FirstInlinedBB->begin();280 }281 282 // Split basic block after the call instruction unless the callee is trivial283 // (i.e. consists of a single basic block). If necessary, obtain a basic block284 // for return instructions in the callee to redirect to.285 BinaryBasicBlock *NextBB = nullptr;286 if (Callee.size() > 1) {287 if (std::next(CallInst) != FirstInlinedBB->end())288 NextBB = FirstInlinedBB->splitAt(std::next(CallInst));289 else290 NextBB = FirstInlinedBB->getSuccessor();291 }292 if (NextBB)293 FirstInlinedBB->removeSuccessor(NextBB);294 295 // Remove the call instruction.296 auto InsertII = FirstInlinedBB->eraseInstruction(CallInst);297 298 double ProfileRatio = 0;299 if (uint64_t CalleeExecCount = Callee.getKnownExecutionCount())300 ProfileRatio =301 (double)FirstInlinedBB->getKnownExecutionCount() / CalleeExecCount;302 303 // Save execution count of the first block as we don't want it to change304 // later due to profile adjustment rounding errors.305 const uint64_t FirstInlinedBBCount = FirstInlinedBB->getKnownExecutionCount();306 307 // Copy basic blocks and maintain a map from their origin.308 std::unordered_map<const BinaryBasicBlock *, BinaryBasicBlock *> InlinedBBMap;309 InlinedBBMap[&Callee.front()] = FirstInlinedBB;310 for (const BinaryBasicBlock &BB : llvm::drop_begin(Callee)) {311 BinaryBasicBlock *InlinedBB = CallerFunction.addBasicBlock();312 InlinedBBMap[&BB] = InlinedBB;313 InlinedBB->setCFIState(FirstInlinedBB->getCFIState());314 if (Callee.hasValidProfile())315 InlinedBB->setExecutionCount(BB.getKnownExecutionCount());316 else317 InlinedBB->setExecutionCount(FirstInlinedBBCount);318 }319 320 // Copy over instructions and edges.321 for (const BinaryBasicBlock &BB : Callee) {322 BinaryBasicBlock *InlinedBB = InlinedBBMap[&BB];323 324 if (InlinedBB != FirstInlinedBB)325 InsertII = InlinedBB->begin();326 327 // Copy over instructions making any necessary mods.328 for (MCInst Inst : BB) {329 if (MIB.isPseudo(Inst))330 continue;331 332 MIB.stripAnnotations(Inst, /*KeepTC=*/BC.isX86() || BC.isAArch64());333 334 // Fix branch target. Strictly speaking, we don't have to do this as335 // targets of direct branches will be fixed later and don't matter336 // in the CFG state. However, disassembly may look misleading, and337 // hence we do the fixing.338 if (MIB.isBranch(Inst) && !MIB.isTailCall(Inst)) {339 assert(!MIB.isIndirectBranch(Inst) &&340 "unexpected indirect branch in callee");341 const BinaryBasicBlock *TargetBB =342 Callee.getBasicBlockForLabel(MIB.getTargetSymbol(Inst));343 assert(TargetBB && "cannot find target block in callee");344 MIB.replaceBranchTarget(Inst, InlinedBBMap[TargetBB]->getLabel(),345 BC.Ctx.get());346 }347 348 // Handling fused authentication and return instructions (Armv8.3-A):349 // if the Callee does not end in a tailcall, the return will be removed350 // from the inlined block. If that return is RETA(A|B), we have to keep351 // the authentication part.352 // RETAA -> AUTIASP353 // RETAB -> AUTIBSP354 if (!CSIsTailCall && BC.isAArch64() && BC.MIB->isPAuthAndRet(Inst)) {355 MCInst Auth;356 BC.MIB->createMatchingAuth(Inst, Auth);357 InsertII =358 std::next(InlinedBB->insertInstruction(InsertII, std::move(Auth)));359 }360 if (CSIsTailCall || (!MIB.isCall(Inst) && !MIB.isReturn(Inst))) {361 InsertII =362 std::next(InlinedBB->insertInstruction(InsertII, std::move(Inst)));363 continue;364 }365 366 // Handle special instructions for a non-tail call site.367 if (!MIB.isCall(Inst)) {368 // Returns are removed.369 break;370 }371 372 MIB.convertTailCallToCall(Inst);373 374 // Propagate EH-related info to call instructions.375 if (CSIsInvoke) {376 MIB.addEHInfo(Inst, *CSEHInfo);377 if (CSGNUArgsSize >= 0)378 MIB.addGnuArgsSize(Inst, CSGNUArgsSize);379 }380 381 InsertII =382 std::next(InlinedBB->insertInstruction(InsertII, std::move(Inst)));383 }384 385 // Add CFG edges to the basic blocks of the inlined instance.386 std::vector<BinaryBasicBlock *> Successors(BB.succ_size());387 llvm::transform(BB.successors(), Successors.begin(),388 [&InlinedBBMap](const BinaryBasicBlock *BB) {389 auto It = InlinedBBMap.find(BB);390 assert(It != InlinedBBMap.end());391 return It->second;392 });393 394 if (CallerFunction.hasValidProfile() && Callee.hasValidProfile())395 InlinedBB->addSuccessors(Successors.begin(), Successors.end(),396 BB.branch_info_begin(), BB.branch_info_end());397 else398 InlinedBB->addSuccessors(Successors.begin(), Successors.end());399 400 if (!CSIsTailCall && BB.succ_size() == 0 && NextBB) {401 // Either it's a return block or the last instruction never returns.402 InlinedBB->addSuccessor(NextBB, InlinedBB->getExecutionCount());403 }404 405 // Scale profiling info for blocks and edges after inlining.406 if (CallerFunction.hasValidProfile() && Callee.size() > 1) {407 if (opts::AdjustProfile)408 InlinedBB->adjustExecutionCount(ProfileRatio);409 else410 InlinedBB->setExecutionCount(InlinedBB->getKnownExecutionCount() *411 ProfileRatio);412 }413 }414 415 // Restore the original execution count of the first inlined basic block.416 FirstInlinedBB->setExecutionCount(FirstInlinedBBCount);417 418 CallerFunction.recomputeLandingPads();419 420 if (NextBB)421 return std::make_pair(NextBB, NextBB->begin());422 423 if (Callee.size() == 1)424 return std::make_pair(FirstInlinedBB, InsertII);425 426 return std::make_pair(FirstInlinedBB, FirstInlinedBB->end());427}428 429bool Inliner::inlineCallsInFunction(BinaryFunction &Function) {430 BinaryContext &BC = Function.getBinaryContext();431 std::vector<BinaryBasicBlock *> Blocks(Function.getLayout().block_begin(),432 Function.getLayout().block_end());433 llvm::sort(434 Blocks, [](const BinaryBasicBlock *BB1, const BinaryBasicBlock *BB2) {435 return BB1->getKnownExecutionCount() > BB2->getKnownExecutionCount();436 });437 438 bool DidInlining = false;439 for (BinaryBasicBlock *BB : Blocks) {440 for (auto InstIt = BB->begin(); InstIt != BB->end();) {441 MCInst &Inst = *InstIt;442 if (!BC.MIB->isCall(Inst) || MCPlus::getNumPrimeOperands(Inst) != 1 ||443 !Inst.getOperand(0).isExpr()) {444 ++InstIt;445 continue;446 }447 448 const MCSymbol *TargetSymbol = BC.MIB->getTargetSymbol(Inst);449 assert(TargetSymbol && "target symbol expected for direct call");450 451 // Don't inline calls to a secondary entry point in a target function.452 uint64_t EntryID = 0;453 BinaryFunction *TargetFunction =454 BC.getFunctionForSymbol(TargetSymbol, &EntryID);455 if (!TargetFunction || EntryID != 0) {456 ++InstIt;457 continue;458 }459 460 // Don't do recursive inlining.461 if (TargetFunction == &Function) {462 ++InstIt;463 continue;464 }465 466 auto IInfo = InliningCandidates.find(TargetFunction);467 if (IInfo == InliningCandidates.end()) {468 ++InstIt;469 continue;470 }471 472 const bool IsTailCall = BC.MIB->isTailCall(Inst);473 if (!IsTailCall && IInfo->second.Type == INL_TAILCALL) {474 ++InstIt;475 continue;476 }477 478 int64_t SizeAfterInlining;479 if (IsTailCall)480 SizeAfterInlining =481 IInfo->second.SizeAfterTailCallInlining - getSizeOfTailCallInst(BC);482 else483 SizeAfterInlining =484 IInfo->second.SizeAfterInlining - getSizeOfCallInst(BC);485 486 if (!opts::InlineAll && !opts::mustConsider(*TargetFunction)) {487 if (!opts::InlineSmallFunctions ||488 SizeAfterInlining > opts::InlineSmallFunctionsBytes) {489 ++InstIt;490 continue;491 }492 }493 494 // AArch64 BTI:495 // If the callee has an indirect tailcall (BR), we would transform it to496 // an indirect call (BLR) in InlineCall. Because of this, we would have to497 // update the BTI at the target of the tailcall. However, these targets498 // are not known. Instead, we skip inlining blocks with indirect499 // tailcalls.500 auto HasIndirectTailCall = [&](const BinaryFunction &BF) -> bool {501 for (const auto &BB : BF) {502 for (const auto &II : BB) {503 if (BC.MIB->isIndirectBranch(II) && BC.MIB->isTailCall(II)) {504 return true;505 }506 }507 }508 return false;509 };510 511 if (BC.isAArch64() && BC.usesBTI() &&512 HasIndirectTailCall(*TargetFunction)) {513 ++InstIt;514 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: Skipping inlining block with tailcall"515 << " in " << Function << " : " << BB->getName()516 << " to keep BTIs consistent.\n");517 continue;518 }519 520 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: inlining call to " << *TargetFunction521 << " in " << Function << " : " << BB->getName()522 << ". Count: " << BB->getKnownExecutionCount()523 << ". Size change: " << SizeAfterInlining524 << " bytes.\n");525 526 std::tie(BB, InstIt) = inlineCall(*BB, InstIt, *TargetFunction);527 528 DidInlining = true;529 TotalInlinedBytes += SizeAfterInlining;530 531 ++NumInlinedCallSites;532 NumInlinedDynamicCalls += BB->getExecutionCount();533 534 // Subtract basic block execution count from the callee execution count.535 if (opts::AdjustProfile)536 TargetFunction->adjustExecutionCount(BB->getKnownExecutionCount());537 538 // Check if the caller inlining status has to be adjusted.539 if (IInfo->second.Type == INL_TAILCALL) {540 auto CallerIInfo = InliningCandidates.find(&Function);541 if (CallerIInfo != InliningCandidates.end() &&542 CallerIInfo->second.Type == INL_ANY) {543 LLVM_DEBUG(dbgs() << "adjusting inlining status for function "544 << Function << '\n');545 CallerIInfo->second.Type = INL_TAILCALL;546 }547 }548 549 if (NumInlinedCallSites == opts::InlineLimit)550 return true;551 }552 }553 554 return DidInlining;555}556 557Error Inliner::runOnFunctions(BinaryContext &BC) {558 opts::syncOptions();559 560 if (!opts::inliningEnabled())561 return Error::success();562 563 bool InlinedOnce;564 unsigned NumIters = 0;565 do {566 if (opts::InlineLimit && NumInlinedCallSites >= opts::InlineLimit)567 break;568 569 InlinedOnce = false;570 571 InliningCandidates.clear();572 findInliningCandidates(BC);573 574 std::vector<BinaryFunction *> ConsideredFunctions;575 for (auto &BFI : BC.getBinaryFunctions()) {576 BinaryFunction &Function = BFI.second;577 if (!shouldOptimize(Function))578 continue;579 ConsideredFunctions.push_back(&Function);580 }581 llvm::sort(ConsideredFunctions, [](const BinaryFunction *A,582 const BinaryFunction *B) {583 return B->getKnownExecutionCount() < A->getKnownExecutionCount();584 });585 for (BinaryFunction *Function : ConsideredFunctions) {586 if (opts::InlineLimit && NumInlinedCallSites >= opts::InlineLimit)587 break;588 589 const bool DidInline = inlineCallsInFunction(*Function);590 591 if (DidInline)592 Modified.insert(Function);593 594 InlinedOnce |= DidInline;595 }596 597 ++NumIters;598 } while (InlinedOnce && NumIters < opts::InlineMaxIters);599 600 if (NumInlinedCallSites)601 BC.outs() << "BOLT-INFO: inlined " << NumInlinedDynamicCalls << " calls at "602 << NumInlinedCallSites << " call sites in " << NumIters603 << " iteration(s). Change in binary size: " << TotalInlinedBytes604 << " bytes.\n";605 return Error::success();606}607 608} // namespace bolt609} // namespace llvm610