948 lines · cpp
1//===- bolt/Passes/LongJmp.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 LongJmpPass class.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Passes/LongJmp.h"14#include "bolt/Core/ParallelUtilities.h"15#include "bolt/Utils/CommandLineOpts.h"16#include "llvm/Support/MathExtras.h"17 18#define DEBUG_TYPE "longjmp"19 20using namespace llvm;21 22namespace opts {23extern cl::OptionCategory BoltCategory;24extern cl::OptionCategory BoltOptCategory;25extern llvm::cl::opt<unsigned> AlignText;26extern cl::opt<unsigned> AlignFunctions;27extern cl::opt<bool> UseOldText;28extern cl::opt<bool> HotFunctionsAtEnd;29 30static cl::opt<bool> GroupStubs("group-stubs",31 cl::desc("share stubs across functions"),32 cl::init(true), cl::cat(BoltOptCategory));33}34 35namespace llvm {36namespace bolt {37 38constexpr unsigned ColdFragAlign = 16;39 40static void relaxStubToShortJmp(BinaryBasicBlock &StubBB, const MCSymbol *Tgt) {41 const BinaryContext &BC = StubBB.getFunction()->getBinaryContext();42 InstructionListType Seq;43 BC.MIB->createShortJmp(Seq, Tgt, BC.Ctx.get());44 StubBB.clear();45 StubBB.addInstructions(Seq.begin(), Seq.end());46}47 48static void relaxStubToLongJmp(BinaryBasicBlock &StubBB, const MCSymbol *Tgt) {49 const BinaryContext &BC = StubBB.getFunction()->getBinaryContext();50 InstructionListType Seq;51 BC.MIB->createLongJmp(Seq, Tgt, BC.Ctx.get());52 StubBB.clear();53 StubBB.addInstructions(Seq.begin(), Seq.end());54}55 56static BinaryBasicBlock *getBBAtHotColdSplitPoint(BinaryFunction &Func) {57 if (!Func.isSplit() || Func.empty())58 return nullptr;59 60 assert(!(*Func.begin()).isCold() && "Entry cannot be cold");61 for (auto I = Func.getLayout().block_begin(),62 E = Func.getLayout().block_end();63 I != E; ++I) {64 auto Next = std::next(I);65 if (Next != E && (*Next)->isCold())66 return *I;67 }68 llvm_unreachable("No hot-cold split point found");69}70 71static bool mayNeedStub(const BinaryContext &BC, const MCInst &Inst) {72 return (BC.MIB->isBranch(Inst) || BC.MIB->isCall(Inst)) &&73 !BC.MIB->isIndirectBranch(Inst) && !BC.MIB->isIndirectCall(Inst);74}75 76std::pair<std::unique_ptr<BinaryBasicBlock>, MCSymbol *>77LongJmpPass::createNewStub(BinaryBasicBlock &SourceBB, const MCSymbol *TgtSym,78 bool TgtIsFunc, uint64_t AtAddress) {79 BinaryFunction &Func = *SourceBB.getFunction();80 const BinaryContext &BC = Func.getBinaryContext();81 const bool IsCold = SourceBB.isCold();82 MCSymbol *StubSym = BC.Ctx->createNamedTempSymbol("Stub");83 std::unique_ptr<BinaryBasicBlock> StubBB = Func.createBasicBlock(StubSym);84 MCInst Inst;85 BC.MIB->createUncondBranch(Inst, TgtSym, BC.Ctx.get());86 if (TgtIsFunc)87 BC.MIB->convertJmpToTailCall(Inst);88 StubBB->addInstruction(Inst);89 StubBB->setExecutionCount(0);90 91 // Register this in stubs maps92 auto registerInMap = [&](StubGroupsTy &Map) {93 StubGroupTy &StubGroup = Map[TgtSym];94 StubGroup.insert(95 llvm::lower_bound(96 StubGroup, std::make_pair(AtAddress, nullptr),97 [&](const std::pair<uint64_t, BinaryBasicBlock *> &LHS,98 const std::pair<uint64_t, BinaryBasicBlock *> &RHS) {99 return LHS.first < RHS.first;100 }),101 std::make_pair(AtAddress, StubBB.get()));102 };103 104 Stubs[&Func].insert(StubBB.get());105 StubBits[StubBB.get()] = BC.MIB->getUncondBranchEncodingSize();106 if (IsCold) {107 registerInMap(ColdLocalStubs[&Func]);108 if (opts::GroupStubs && TgtIsFunc)109 registerInMap(ColdStubGroups);110 ++NumColdStubs;111 } else {112 registerInMap(HotLocalStubs[&Func]);113 if (opts::GroupStubs && TgtIsFunc)114 registerInMap(HotStubGroups);115 ++NumHotStubs;116 }117 118 return std::make_pair(std::move(StubBB), StubSym);119}120 121BinaryBasicBlock *LongJmpPass::lookupStubFromGroup(122 const StubGroupsTy &StubGroups, const BinaryFunction &Func,123 const MCInst &Inst, const MCSymbol *TgtSym, uint64_t DotAddress) const {124 const BinaryContext &BC = Func.getBinaryContext();125 auto CandidatesIter = StubGroups.find(TgtSym);126 if (CandidatesIter == StubGroups.end())127 return nullptr;128 const StubGroupTy &Candidates = CandidatesIter->second;129 if (Candidates.empty())130 return nullptr;131 auto Cand = llvm::lower_bound(132 Candidates, std::make_pair(DotAddress, nullptr),133 [&](const std::pair<uint64_t, BinaryBasicBlock *> &LHS,134 const std::pair<uint64_t, BinaryBasicBlock *> &RHS) {135 return LHS.first < RHS.first;136 });137 if (Cand == Candidates.end()) {138 Cand = std::prev(Cand);139 } else if (Cand != Candidates.begin()) {140 const StubTy *LeftCand = std::prev(Cand);141 if (Cand->first - DotAddress > DotAddress - LeftCand->first)142 Cand = LeftCand;143 }144 int BitsAvail = BC.MIB->getPCRelEncodingSize(Inst) - 1;145 assert(BitsAvail < 63 && "PCRelEncodingSize is too large to use int64_t to"146 "check for out-of-bounds.");147 int64_t MaxVal = (1ULL << BitsAvail) - 1;148 int64_t MinVal = -(1ULL << BitsAvail);149 uint64_t PCRelTgtAddress = Cand->first;150 int64_t PCOffset = (int64_t)(PCRelTgtAddress - DotAddress);151 152 LLVM_DEBUG({153 if (Candidates.size() > 1)154 dbgs() << "Considering stub group with " << Candidates.size()155 << " candidates. DotAddress is " << Twine::utohexstr(DotAddress)156 << ", chosen candidate address is "157 << Twine::utohexstr(Cand->first) << "\n";158 });159 return (PCOffset < MinVal || PCOffset > MaxVal) ? nullptr : Cand->second;160}161 162BinaryBasicBlock *163LongJmpPass::lookupGlobalStub(const BinaryBasicBlock &SourceBB,164 const MCInst &Inst, const MCSymbol *TgtSym,165 uint64_t DotAddress) const {166 const BinaryFunction &Func = *SourceBB.getFunction();167 const StubGroupsTy &StubGroups =168 SourceBB.isCold() ? ColdStubGroups : HotStubGroups;169 return lookupStubFromGroup(StubGroups, Func, Inst, TgtSym, DotAddress);170}171 172BinaryBasicBlock *LongJmpPass::lookupLocalStub(const BinaryBasicBlock &SourceBB,173 const MCInst &Inst,174 const MCSymbol *TgtSym,175 uint64_t DotAddress) const {176 const BinaryFunction &Func = *SourceBB.getFunction();177 const DenseMap<const BinaryFunction *, StubGroupsTy> &StubGroups =178 SourceBB.isCold() ? ColdLocalStubs : HotLocalStubs;179 const auto Iter = StubGroups.find(&Func);180 if (Iter == StubGroups.end())181 return nullptr;182 return lookupStubFromGroup(Iter->second, Func, Inst, TgtSym, DotAddress);183}184 185std::unique_ptr<BinaryBasicBlock>186LongJmpPass::replaceTargetWithStub(BinaryBasicBlock &BB, MCInst &Inst,187 uint64_t DotAddress,188 uint64_t StubCreationAddress) {189 const BinaryFunction &Func = *BB.getFunction();190 const BinaryContext &BC = Func.getBinaryContext();191 std::unique_ptr<BinaryBasicBlock> NewBB;192 const MCSymbol *TgtSym = BC.MIB->getTargetSymbol(Inst);193 assert(TgtSym && "getTargetSymbol failed");194 195 BinaryBasicBlock::BinaryBranchInfo BI{0, 0};196 BinaryBasicBlock *TgtBB = BB.getSuccessor(TgtSym, BI);197 auto LocalStubsIter = Stubs.find(&Func);198 199 // If already using stub and the stub is from another function, create a local200 // stub, since the foreign stub is now out of range201 if (!TgtBB) {202 auto SSIter = SharedStubs.find(TgtSym);203 if (SSIter != SharedStubs.end()) {204 TgtSym = BC.MIB->getTargetSymbol(*SSIter->second->begin());205 --NumSharedStubs;206 }207 } else if (LocalStubsIter != Stubs.end() &&208 LocalStubsIter->second.count(TgtBB)) {209 // The TgtBB and TgtSym now are the local out-of-range stub and its label.210 // So, we are attempting to restore BB to its previous state without using211 // this stub.212 TgtSym = BC.MIB->getTargetSymbol(*TgtBB->begin());213 assert(TgtSym &&214 "First instruction is expected to contain a target symbol.");215 BinaryBasicBlock *TgtBBSucc = TgtBB->getSuccessor(TgtSym, BI);216 217 // TgtBB might have no successor. e.g. a stub for a function call.218 if (TgtBBSucc) {219 BB.replaceSuccessor(TgtBB, TgtBBSucc, BI.Count, BI.MispredictedCount);220 assert(TgtBB->getExecutionCount() >= BI.Count &&221 "At least equal or greater than the branch count.");222 TgtBB->setExecutionCount(TgtBB->getExecutionCount() - BI.Count);223 }224 225 TgtBB = TgtBBSucc;226 }227 228 BinaryBasicBlock *StubBB = lookupLocalStub(BB, Inst, TgtSym, DotAddress);229 // If not found, look it up in globally shared stub maps if it is a function230 // call (TgtBB is not set)231 if (!StubBB && !TgtBB) {232 StubBB = lookupGlobalStub(BB, Inst, TgtSym, DotAddress);233 if (StubBB) {234 SharedStubs[StubBB->getLabel()] = StubBB;235 ++NumSharedStubs;236 }237 }238 MCSymbol *StubSymbol = StubBB ? StubBB->getLabel() : nullptr;239 240 if (!StubBB) {241 std::tie(NewBB, StubSymbol) =242 createNewStub(BB, TgtSym, /*is func?*/ !TgtBB, StubCreationAddress);243 StubBB = NewBB.get();244 }245 246 // Local branch247 if (TgtBB) {248 uint64_t OrigCount = BI.Count;249 uint64_t OrigMispreds = BI.MispredictedCount;250 BB.replaceSuccessor(TgtBB, StubBB, OrigCount, OrigMispreds);251 StubBB->setExecutionCount(StubBB->getExecutionCount() + OrigCount);252 if (NewBB) {253 StubBB->addSuccessor(TgtBB, OrigCount, OrigMispreds);254 StubBB->setIsCold(BB.isCold());255 }256 // Call / tail call257 } else {258 StubBB->setExecutionCount(StubBB->getExecutionCount() +259 BB.getExecutionCount());260 if (NewBB) {261 assert(TgtBB == nullptr);262 StubBB->setIsCold(BB.isCold());263 // Set as entry point because this block is valid but we have no preds264 StubBB->getFunction()->addEntryPoint(*StubBB);265 }266 }267 BC.MIB->replaceBranchTarget(Inst, StubSymbol, BC.Ctx.get());268 269 return NewBB;270}271 272void LongJmpPass::updateStubGroups() {273 auto update = [&](StubGroupsTy &StubGroups) {274 for (auto &KeyVal : StubGroups) {275 for (StubTy &Elem : KeyVal.second)276 Elem.first = BBAddresses[Elem.second];277 llvm::sort(KeyVal.second, llvm::less_first());278 }279 };280 281 for (auto &KeyVal : HotLocalStubs)282 update(KeyVal.second);283 for (auto &KeyVal : ColdLocalStubs)284 update(KeyVal.second);285 update(HotStubGroups);286 update(ColdStubGroups);287}288 289void LongJmpPass::tentativeBBLayout(const BinaryFunction &Func) {290 const BinaryContext &BC = Func.getBinaryContext();291 uint64_t HotDot = HotAddresses[&Func];292 uint64_t ColdDot = ColdAddresses[&Func];293 bool Cold = false;294 for (const BinaryBasicBlock *BB : Func.getLayout().blocks()) {295 if (Cold || BB->isCold()) {296 Cold = true;297 BBAddresses[BB] = ColdDot;298 ColdDot += BC.computeCodeSize(BB->begin(), BB->end());299 } else {300 BBAddresses[BB] = HotDot;301 HotDot += BC.computeCodeSize(BB->begin(), BB->end());302 }303 }304}305 306uint64_t LongJmpPass::tentativeLayoutRelocColdPart(307 const BinaryContext &BC, std::vector<BinaryFunction *> &SortedFunctions,308 uint64_t DotAddress) {309 DotAddress = alignTo(DotAddress, llvm::Align(opts::AlignFunctions));310 for (BinaryFunction *Func : SortedFunctions) {311 if (!Func->isSplit())312 continue;313 DotAddress = alignTo(DotAddress, Func->getMinAlignment());314 uint64_t Pad =315 offsetToAlignment(DotAddress, llvm::Align(Func->getAlignment()));316 if (Pad <= Func->getMaxColdAlignmentBytes())317 DotAddress += Pad;318 ColdAddresses[Func] = DotAddress;319 LLVM_DEBUG(dbgs() << Func->getPrintName() << " cold tentative: "320 << Twine::utohexstr(DotAddress) << "\n");321 DotAddress += Func->estimateColdSize();322 DotAddress = alignTo(DotAddress, Func->getConstantIslandAlignment());323 DotAddress += Func->estimateConstantIslandSize();324 }325 return DotAddress;326}327 328uint64_t LongJmpPass::tentativeLayoutRelocMode(329 const BinaryContext &BC, std::vector<BinaryFunction *> &SortedFunctions,330 uint64_t DotAddress) {331 // Compute hot cold frontier332 int64_t LastHotIndex = -1u;333 uint32_t CurrentIndex = 0;334 if (opts::HotFunctionsAtEnd) {335 for (BinaryFunction *BF : SortedFunctions) {336 if (BF->hasValidIndex()) {337 LastHotIndex = CurrentIndex;338 break;339 }340 341 ++CurrentIndex;342 }343 } else {344 for (BinaryFunction *BF : SortedFunctions) {345 if (!BF->hasValidIndex()) {346 LastHotIndex = CurrentIndex;347 break;348 }349 350 ++CurrentIndex;351 }352 }353 354 // Hot355 CurrentIndex = 0;356 bool ColdLayoutDone = false;357 auto runColdLayout = [&]() {358 DotAddress = tentativeLayoutRelocColdPart(BC, SortedFunctions, DotAddress);359 ColdLayoutDone = true;360 if (opts::HotFunctionsAtEnd)361 DotAddress = alignTo(DotAddress, opts::AlignText);362 };363 for (BinaryFunction *Func : SortedFunctions) {364 if (!BC.shouldEmit(*Func)) {365 HotAddresses[Func] = Func->getAddress();366 continue;367 }368 369 if (!ColdLayoutDone && CurrentIndex >= LastHotIndex)370 runColdLayout();371 372 DotAddress = alignTo(DotAddress, Func->getMinAlignment());373 uint64_t Pad =374 offsetToAlignment(DotAddress, llvm::Align(Func->getAlignment()));375 if (Pad <= Func->getMaxAlignmentBytes())376 DotAddress += Pad;377 HotAddresses[Func] = DotAddress;378 LLVM_DEBUG(dbgs() << Func->getPrintName() << " tentative: "379 << Twine::utohexstr(DotAddress) << "\n");380 if (!Func->isSplit())381 DotAddress += Func->estimateSize();382 else383 DotAddress += Func->estimateHotSize();384 385 DotAddress = alignTo(DotAddress, Func->getConstantIslandAlignment());386 DotAddress += Func->estimateConstantIslandSize();387 ++CurrentIndex;388 }389 390 // Ensure that tentative code layout always runs for cold blocks.391 if (!ColdLayoutDone)392 runColdLayout();393 394 // BBs395 for (BinaryFunction *Func : SortedFunctions)396 tentativeBBLayout(*Func);397 398 return DotAddress;399}400 401void LongJmpPass::tentativeLayout(402 const BinaryContext &BC, std::vector<BinaryFunction *> &SortedFunctions) {403 uint64_t DotAddress = BC.LayoutStartAddress;404 405 if (!BC.HasRelocations) {406 for (BinaryFunction *Func : SortedFunctions) {407 HotAddresses[Func] = Func->getAddress();408 DotAddress = alignTo(DotAddress, ColdFragAlign);409 ColdAddresses[Func] = DotAddress;410 if (Func->isSplit())411 DotAddress += Func->estimateColdSize();412 tentativeBBLayout(*Func);413 }414 415 return;416 }417 418 // Relocation mode419 uint64_t EstimatedTextSize = 0;420 if (opts::UseOldText) {421 EstimatedTextSize = tentativeLayoutRelocMode(BC, SortedFunctions, 0);422 423 // Initial padding424 if (EstimatedTextSize <= BC.OldTextSectionSize) {425 DotAddress = BC.OldTextSectionAddress;426 uint64_t Pad =427 offsetToAlignment(DotAddress, llvm::Align(opts::AlignText));428 if (Pad + EstimatedTextSize <= BC.OldTextSectionSize) {429 DotAddress += Pad;430 }431 }432 }433 434 if (!EstimatedTextSize || EstimatedTextSize > BC.OldTextSectionSize)435 DotAddress = alignTo(BC.LayoutStartAddress, opts::AlignText);436 437 tentativeLayoutRelocMode(BC, SortedFunctions, DotAddress);438}439 440bool LongJmpPass::usesStub(const BinaryFunction &Func,441 const MCInst &Inst) const {442 const MCSymbol *TgtSym = Func.getBinaryContext().MIB->getTargetSymbol(Inst);443 const BinaryBasicBlock *TgtBB = Func.getBasicBlockForLabel(TgtSym);444 auto Iter = Stubs.find(&Func);445 if (Iter != Stubs.end())446 return Iter->second.count(TgtBB);447 return false;448}449 450uint64_t LongJmpPass::getSymbolAddress(const BinaryContext &BC,451 const MCSymbol *Target,452 const BinaryBasicBlock *TgtBB) const {453 if (TgtBB) {454 auto Iter = BBAddresses.find(TgtBB);455 assert(Iter != BBAddresses.end() && "Unrecognized BB");456 return Iter->second;457 }458 uint64_t EntryID = 0;459 const BinaryFunction *TargetFunc = BC.getFunctionForSymbol(Target, &EntryID);460 auto Iter = HotAddresses.find(TargetFunc);461 if (Iter == HotAddresses.end() || (TargetFunc && EntryID)) {462 // Look at BinaryContext's resolution for this symbol - this is a symbol not463 // mapped to a BinaryFunction464 ErrorOr<uint64_t> ValueOrError = BC.getSymbolValue(*Target);465 assert(ValueOrError && "Unrecognized symbol");466 return *ValueOrError;467 }468 return Iter->second;469}470 471Error LongJmpPass::relaxStub(BinaryBasicBlock &StubBB, bool &Modified) {472 const BinaryFunction &Func = *StubBB.getFunction();473 const BinaryContext &BC = Func.getBinaryContext();474 const int Bits = StubBits[&StubBB];475 // Already working with the largest range?476 if (Bits == static_cast<int>(BC.AsmInfo->getCodePointerSize() * 8))477 return Error::success();478 479 const static int RangeShortJmp = BC.MIB->getShortJmpEncodingSize();480 const static int RangeSingleInstr = BC.MIB->getUncondBranchEncodingSize();481 const static uint64_t ShortJmpMask = ~((1ULL << RangeShortJmp) - 1);482 const static uint64_t SingleInstrMask =483 ~((1ULL << (RangeSingleInstr - 1)) - 1);484 485 const MCSymbol *RealTargetSym = BC.MIB->getTargetSymbol(*StubBB.begin());486 const BinaryBasicBlock *TgtBB = Func.getBasicBlockForLabel(RealTargetSym);487 uint64_t TgtAddress = getSymbolAddress(BC, RealTargetSym, TgtBB);488 uint64_t DotAddress = BBAddresses[&StubBB];489 uint64_t PCRelTgtAddress = DotAddress > TgtAddress ? DotAddress - TgtAddress490 : TgtAddress - DotAddress;491 // If it fits in one instruction, do not relax492 if (!(PCRelTgtAddress & SingleInstrMask))493 return Error::success();494 495 // Fits short jmp496 if (!(PCRelTgtAddress & ShortJmpMask)) {497 if (Bits >= RangeShortJmp)498 return Error::success();499 500 LLVM_DEBUG(dbgs() << "Relaxing stub to short jump. PCRelTgtAddress = "501 << Twine::utohexstr(PCRelTgtAddress)502 << " RealTargetSym = " << RealTargetSym->getName()503 << "\n");504 relaxStubToShortJmp(StubBB, RealTargetSym);505 StubBits[&StubBB] = RangeShortJmp;506 Modified = true;507 return Error::success();508 }509 510 // The long jmp uses absolute address on AArch64511 // So we could not use it for PIC binaries512 if (BC.isAArch64() && !BC.HasFixedLoadAddress)513 return createFatalBOLTError(514 "BOLT-ERROR: Unable to relax stub for PIC binary\n");515 516 LLVM_DEBUG(dbgs() << "Relaxing stub to long jump. PCRelTgtAddress = "517 << Twine::utohexstr(PCRelTgtAddress)518 << " RealTargetSym = " << RealTargetSym->getName() << "\n");519 relaxStubToLongJmp(StubBB, RealTargetSym);520 StubBits[&StubBB] = static_cast<int>(BC.AsmInfo->getCodePointerSize() * 8);521 Modified = true;522 return Error::success();523}524 525bool LongJmpPass::needsStub(const BinaryBasicBlock &BB, const MCInst &Inst,526 uint64_t DotAddress) const {527 const BinaryFunction &Func = *BB.getFunction();528 const BinaryContext &BC = Func.getBinaryContext();529 const MCSymbol *TgtSym = BC.MIB->getTargetSymbol(Inst);530 assert(TgtSym && "getTargetSymbol failed");531 532 const BinaryBasicBlock *TgtBB = Func.getBasicBlockForLabel(TgtSym);533 // Check for shared stubs from foreign functions534 if (!TgtBB) {535 auto SSIter = SharedStubs.find(TgtSym);536 if (SSIter != SharedStubs.end())537 TgtBB = SSIter->second;538 }539 540 int BitsAvail = BC.MIB->getPCRelEncodingSize(Inst) - 1;541 assert(BitsAvail < 63 && "PCRelEncodingSize is too large to use int64_t to"542 "check for out-of-bounds.");543 int64_t MaxVal = (1ULL << BitsAvail) - 1;544 int64_t MinVal = -(1ULL << BitsAvail);545 546 uint64_t PCRelTgtAddress = getSymbolAddress(BC, TgtSym, TgtBB);547 int64_t PCOffset = (int64_t)(PCRelTgtAddress - DotAddress);548 549 return PCOffset < MinVal || PCOffset > MaxVal;550}551 552Error LongJmpPass::relax(BinaryFunction &Func, bool &Modified) {553 const BinaryContext &BC = Func.getBinaryContext();554 555 assert(BC.isAArch64() && "Unsupported arch");556 constexpr int InsnSize = 4; // AArch64557 std::vector<std::pair<BinaryBasicBlock *, std::unique_ptr<BinaryBasicBlock>>>558 Insertions;559 560 BinaryBasicBlock *Frontier = getBBAtHotColdSplitPoint(Func);561 uint64_t FrontierAddress = Frontier ? BBAddresses[Frontier] : 0;562 if (FrontierAddress)563 FrontierAddress += Frontier->getNumNonPseudos() * InsnSize;564 565 // Add necessary stubs for branch targets we know we can't fit in the566 // instruction567 for (BinaryBasicBlock &BB : Func) {568 uint64_t DotAddress = BBAddresses[&BB];569 // Stubs themselves are relaxed on the next loop570 if (Stubs[&Func].count(&BB))571 continue;572 573 for (MCInst &Inst : BB) {574 if (BC.MIB->isPseudo(Inst))575 continue;576 577 if (!mayNeedStub(BC, Inst)) {578 DotAddress += InsnSize;579 continue;580 }581 582 // Check and relax direct branch or call583 if (!needsStub(BB, Inst, DotAddress)) {584 DotAddress += InsnSize;585 continue;586 }587 Modified = true;588 589 // Insert stubs close to the patched BB if call, but far away from the590 // hot path if a branch, since this branch target is the cold region591 // (but first check that the far away stub will be in range).592 BinaryBasicBlock *InsertionPoint = &BB;593 if (Func.isSimple() && !BC.MIB->isCall(Inst) && FrontierAddress &&594 !BB.isCold()) {595 int BitsAvail = BC.MIB->getPCRelEncodingSize(Inst) - 1;596 uint64_t Mask = ~((1ULL << BitsAvail) - 1);597 assert(FrontierAddress > DotAddress &&598 "Hot code should be before the frontier");599 uint64_t PCRelTgt = FrontierAddress - DotAddress;600 if (!(PCRelTgt & Mask))601 InsertionPoint = Frontier;602 }603 // Always put stubs at the end of the function if non-simple. We can't604 // change the layout of non-simple functions because it has jump tables605 // that we do not control.606 if (!Func.isSimple())607 InsertionPoint = &*std::prev(Func.end());608 609 // Create a stub to handle a far-away target610 Insertions.emplace_back(InsertionPoint,611 replaceTargetWithStub(BB, Inst, DotAddress,612 InsertionPoint == Frontier613 ? FrontierAddress614 : DotAddress));615 616 DotAddress += InsnSize;617 }618 }619 620 // Relax stubs if necessary621 for (BinaryBasicBlock &BB : Func) {622 if (!Stubs[&Func].count(&BB) || !BB.isValid())623 continue;624 625 if (auto E = relaxStub(BB, Modified))626 return Error(std::move(E));627 }628 629 for (std::pair<BinaryBasicBlock *, std::unique_ptr<BinaryBasicBlock>> &Elmt :630 Insertions) {631 if (!Elmt.second)632 continue;633 std::vector<std::unique_ptr<BinaryBasicBlock>> NewBBs;634 NewBBs.emplace_back(std::move(Elmt.second));635 Func.insertBasicBlocks(Elmt.first, std::move(NewBBs), true);636 }637 638 return Error::success();639}640 641void LongJmpPass::relaxLocalBranches(BinaryFunction &BF) {642 BinaryContext &BC = BF.getBinaryContext();643 auto &MIB = BC.MIB;644 645 // Quick path.646 if (!BF.isSplit() && BF.estimateSize() < ShortestJumpSpan)647 return;648 649 auto isBranchOffsetInRange = [&](const MCInst &Inst, int64_t Offset) {650 const unsigned Bits = MIB->getPCRelEncodingSize(Inst);651 return isIntN(Bits, Offset);652 };653 654 auto isBlockInRange = [&](const MCInst &Inst, uint64_t InstAddress,655 const BinaryBasicBlock &BB) {656 const int64_t Offset = BB.getOutputStartAddress() - InstAddress;657 return isBranchOffsetInRange(Inst, Offset);658 };659 660 // Keep track of *all* function trampolines that are going to be added to the661 // function layout at the end of relaxation.662 std::vector<std::pair<BinaryBasicBlock *, std::unique_ptr<BinaryBasicBlock>>>663 FunctionTrampolines;664 665 // Function fragments are relaxed independently.666 for (FunctionFragment &FF : BF.getLayout().fragments()) {667 // Fill out code size estimation for the fragment. Use output BB address668 // ranges to store offsets from the start of the function fragment.669 uint64_t CodeSize = 0;670 for (BinaryBasicBlock *BB : FF) {671 BB->setOutputStartAddress(CodeSize);672 CodeSize += BB->estimateSize();673 BB->setOutputEndAddress(CodeSize);674 }675 676 // Dynamically-updated size of the fragment.677 uint64_t FragmentSize = CodeSize;678 679 // Size of the trampoline in bytes.680 constexpr uint64_t TrampolineSize = 4;681 682 // Trampolines created for the fragment. DestinationBB -> TrampolineBB.683 // NB: here we store only the first trampoline created for DestinationBB.684 DenseMap<const BinaryBasicBlock *, BinaryBasicBlock *> FragmentTrampolines;685 686 // Create a trampoline code after \p BB or at the end of the fragment if BB687 // is nullptr. If \p UpdateOffsets is true, update FragmentSize and offsets688 // for basic blocks affected by the insertion of the trampoline.689 auto addTrampolineAfter = [&](BinaryBasicBlock *BB,690 BinaryBasicBlock *TargetBB, uint64_t Count,691 bool UpdateOffsets = true) {692 FunctionTrampolines.emplace_back(BB ? BB : FF.back(),693 BF.createBasicBlock());694 BinaryBasicBlock *TrampolineBB = FunctionTrampolines.back().second.get();695 696 MCInst Inst;697 {698 auto L = BC.scopeLock();699 MIB->createUncondBranch(Inst, TargetBB->getLabel(), BC.Ctx.get());700 }701 TrampolineBB->addInstruction(Inst);702 TrampolineBB->addSuccessor(TargetBB, Count);703 TrampolineBB->setExecutionCount(Count);704 const uint64_t TrampolineAddress =705 BB ? BB->getOutputEndAddress() : FragmentSize;706 TrampolineBB->setOutputStartAddress(TrampolineAddress);707 TrampolineBB->setOutputEndAddress(TrampolineAddress + TrampolineSize);708 TrampolineBB->setFragmentNum(FF.getFragmentNum());709 710 if (!FragmentTrampolines.lookup(TargetBB))711 FragmentTrampolines[TargetBB] = TrampolineBB;712 713 if (!UpdateOffsets)714 return TrampolineBB;715 716 FragmentSize += TrampolineSize;717 718 // If the trampoline was added at the end of the fragment, offsets of719 // other fragments should stay intact.720 if (!BB)721 return TrampolineBB;722 723 // Update offsets for blocks after BB.724 for (BinaryBasicBlock *IBB : FF) {725 if (IBB->getOutputStartAddress() >= TrampolineAddress) {726 IBB->setOutputStartAddress(IBB->getOutputStartAddress() +727 TrampolineSize);728 IBB->setOutputEndAddress(IBB->getOutputEndAddress() + TrampolineSize);729 }730 }731 732 // Update offsets for trampolines in this fragment that are placed after733 // the new trampoline. Note that trampoline blocks are not part of the734 // function/fragment layout until we add them right before the return735 // from relaxLocalBranches().736 for (auto &Pair : FunctionTrampolines) {737 BinaryBasicBlock *IBB = Pair.second.get();738 if (IBB->getFragmentNum() != TrampolineBB->getFragmentNum())739 continue;740 if (IBB == TrampolineBB)741 continue;742 if (IBB->getOutputStartAddress() >= TrampolineAddress) {743 IBB->setOutputStartAddress(IBB->getOutputStartAddress() +744 TrampolineSize);745 IBB->setOutputEndAddress(IBB->getOutputEndAddress() + TrampolineSize);746 }747 }748 749 return TrampolineBB;750 };751 752 // Pre-populate trampolines by splitting unconditional branches from the753 // containing basic block.754 for (BinaryBasicBlock *BB : FF) {755 MCInst *Inst = BB->getLastNonPseudoInstr();756 if (!Inst || !MIB->isUnconditionalBranch(*Inst))757 continue;758 759 const MCSymbol *TargetSymbol = MIB->getTargetSymbol(*Inst);760 BB->eraseInstruction(BB->findInstruction(Inst));761 BB->setOutputEndAddress(BB->getOutputEndAddress() - TrampolineSize);762 763 BinaryBasicBlock::BinaryBranchInfo BI;764 BinaryBasicBlock *TargetBB = BB->getSuccessor(TargetSymbol, BI);765 766 BinaryBasicBlock *TrampolineBB =767 addTrampolineAfter(BB, TargetBB, BI.Count, /*UpdateOffsets*/ false);768 BB->replaceSuccessor(TargetBB, TrampolineBB, BI.Count);769 }770 771 /// Relax the branch \p Inst in basic block \p BB that targets \p TargetBB.772 /// \p InstAddress contains offset of the branch from the start of the773 /// containing function fragment.774 auto relaxBranch = [&](BinaryBasicBlock *BB, MCInst &Inst,775 uint64_t InstAddress, BinaryBasicBlock *TargetBB) {776 BinaryFunction *BF = BB->getParent();777 778 // Use branch taken count for optimal relaxation.779 const uint64_t Count = BB->getBranchInfo(*TargetBB).Count;780 assert(Count != BinaryBasicBlock::COUNT_NO_PROFILE &&781 "Expected valid branch execution count");782 783 // Try to reuse an existing trampoline without introducing any new code.784 BinaryBasicBlock *TrampolineBB = FragmentTrampolines.lookup(TargetBB);785 if (TrampolineBB && isBlockInRange(Inst, InstAddress, *TrampolineBB)) {786 BB->replaceSuccessor(TargetBB, TrampolineBB, Count);787 TrampolineBB->setExecutionCount(TrampolineBB->getExecutionCount() +788 Count);789 auto L = BC.scopeLock();790 MIB->replaceBranchTarget(Inst, TrampolineBB->getLabel(), BC.Ctx.get());791 return;792 }793 794 // For cold branches, check if we can introduce a trampoline at the end795 // of the fragment that is within the branch reach. Note that such796 // trampoline may change address later and become unreachable in which797 // case we will need further relaxation.798 const int64_t OffsetToEnd = FragmentSize - InstAddress;799 if (Count == 0 && isBranchOffsetInRange(Inst, OffsetToEnd)) {800 TrampolineBB = addTrampolineAfter(nullptr, TargetBB, Count);801 BB->replaceSuccessor(TargetBB, TrampolineBB, Count);802 auto L = BC.scopeLock();803 MIB->replaceBranchTarget(Inst, TrampolineBB->getLabel(), BC.Ctx.get());804 805 return;806 }807 808 // Insert a new block after the current one and use it as a trampoline.809 TrampolineBB = addTrampolineAfter(BB, TargetBB, Count);810 811 // If the other successor is a fall-through, invert the condition code.812 const BinaryBasicBlock *const NextBB =813 BF->getLayout().getBasicBlockAfter(BB, /*IgnoreSplits*/ false);814 if (BB->getConditionalSuccessor(false) == NextBB) {815 BB->swapConditionalSuccessors();816 auto L = BC.scopeLock();817 MIB->reverseBranchCondition(Inst, NextBB->getLabel(), BC.Ctx.get());818 } else {819 auto L = BC.scopeLock();820 MIB->replaceBranchTarget(Inst, TrampolineBB->getLabel(), BC.Ctx.get());821 }822 BB->replaceSuccessor(TargetBB, TrampolineBB, Count);823 };824 825 bool MayNeedRelaxation;826 uint64_t NumIterations = 0;827 do {828 MayNeedRelaxation = false;829 ++NumIterations;830 for (auto BBI = FF.begin(); BBI != FF.end(); ++BBI) {831 BinaryBasicBlock *BB = *BBI;832 uint64_t NextInstOffset = BB->getOutputStartAddress();833 for (MCInst &Inst : *BB) {834 const size_t InstAddress = NextInstOffset;835 if (!MIB->isPseudo(Inst))836 NextInstOffset += 4;837 838 if (!mayNeedStub(BF.getBinaryContext(), Inst))839 continue;840 841 const size_t BitsAvailable = MIB->getPCRelEncodingSize(Inst);842 843 // Span of +/-128MB.844 if (BitsAvailable == LongestJumpBits)845 continue;846 847 const MCSymbol *TargetSymbol = MIB->getTargetSymbol(Inst);848 BinaryBasicBlock *TargetBB = BB->getSuccessor(TargetSymbol);849 assert(TargetBB &&850 "Basic block target expected for conditional branch.");851 852 // Check if the relaxation is needed.853 if (TargetBB->getFragmentNum() == FF.getFragmentNum() &&854 isBlockInRange(Inst, InstAddress, *TargetBB))855 continue;856 857 relaxBranch(BB, Inst, InstAddress, TargetBB);858 859 MayNeedRelaxation = true;860 }861 }862 863 // We may have added new instructions, but the whole fragment is less than864 // the minimum branch span.865 if (FragmentSize < ShortestJumpSpan)866 MayNeedRelaxation = false;867 868 } while (MayNeedRelaxation);869 870 LLVM_DEBUG({871 if (NumIterations > 2) {872 dbgs() << "BOLT-DEBUG: relaxed fragment " << FF.getFragmentNum().get()873 << " of " << BF << " in " << NumIterations << " iterations\n";874 }875 });876 (void)NumIterations;877 }878 879 // Add trampoline blocks from all fragments to the layout.880 DenseMap<BinaryBasicBlock *, std::vector<std::unique_ptr<BinaryBasicBlock>>>881 Insertions;882 for (std::pair<BinaryBasicBlock *, std::unique_ptr<BinaryBasicBlock>> &Pair :883 FunctionTrampolines) {884 if (!Pair.second)885 continue;886 Insertions[Pair.first].emplace_back(std::move(Pair.second));887 }888 889 for (auto &Pair : Insertions) {890 BF.insertBasicBlocks(Pair.first, std::move(Pair.second),891 /*UpdateLayout*/ true, /*UpdateCFI*/ true,892 /*RecomputeLPs*/ false);893 }894}895 896Error LongJmpPass::runOnFunctions(BinaryContext &BC) {897 898 assert((opts::CompactCodeModel ||899 opts::SplitStrategy != opts::SplitFunctionsStrategy::CDSplit) &&900 "LongJmp cannot work with functions split in more than two fragments");901 902 if (opts::CompactCodeModel) {903 BC.outs()904 << "BOLT-INFO: relaxing branches for compact code model (<128MB)\n";905 906 ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {907 relaxLocalBranches(BF);908 };909 910 ParallelUtilities::PredicateTy SkipPredicate =911 [&](const BinaryFunction &BF) {912 return !BC.shouldEmit(BF) || !BF.isSimple();913 };914 915 ParallelUtilities::runOnEachFunction(916 BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR, WorkFun,917 SkipPredicate, "RelaxLocalBranches");918 919 return Error::success();920 }921 922 BC.outs() << "BOLT-INFO: Starting stub-insertion pass\n";923 std::vector<BinaryFunction *> Sorted = BC.getSortedFunctions();924 bool Modified;925 uint32_t Iterations = 0;926 do {927 ++Iterations;928 Modified = false;929 tentativeLayout(BC, Sorted);930 updateStubGroups();931 for (BinaryFunction *Func : Sorted) {932 if (auto E = relax(*Func, Modified))933 return Error(std::move(E));934 // Don't ruin non-simple functions, they can't afford to have the layout935 // changed.936 if (Modified && Func->isSimple())937 Func->fixBranches();938 }939 } while (Modified);940 BC.outs() << "BOLT-INFO: Inserted " << NumHotStubs941 << " stubs in the hot area and " << NumColdStubs942 << " stubs in the cold area. Shared " << NumSharedStubs943 << " times, iterated " << Iterations << " times.\n";944 return Error::success();945}946} // namespace bolt947} // namespace llvm948