bolt/lib/Passes/LongJmp.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the LongJmpPass class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "bolt/Passes/LongJmp.h"
  14
  15 #define DEBUG_TYPE "longjmp"
  16
  17 using namespace llvm;
  18
  19 namespace opts {
  20 extern cl::OptionCategory BoltOptCategory;
  21 extern llvm::cl::opt<unsigned> AlignText;
  22 extern cl::opt<unsigned> AlignFunctions;
  23 extern cl::opt<bool> UseOldText;
  24 extern cl::opt<bool> HotFunctionsAtEnd;
  25
  26 static cl::opt<bool> GroupStubs("group-stubs",
  27                                 cl::desc("share stubs across functions"),
  28                                 cl::init(true), cl::cat(BoltOptCategory));
  29 }
  30
  31 namespace llvm {
  32 namespace bolt {
  33
  34 constexpr unsigned ColdFragAlign = 16;
  35
  36 static void relaxStubToShortJmp(BinaryBasicBlock &StubBB, const MCSymbol *Tgt) {
  37   const BinaryContext &BC = StubBB.getFunction()->getBinaryContext();
  38   InstructionListType Seq;
  39   BC.MIB->createShortJmp(Seq, Tgt, BC.Ctx.get());
  40   StubBB.clear();
  41   StubBB.addInstructions(Seq.begin(), Seq.end());
  42 }
  43
  44 static void relaxStubToLongJmp(BinaryBasicBlock &StubBB, const MCSymbol *Tgt) {
  45   const BinaryContext &BC = StubBB.getFunction()->getBinaryContext();
  46   InstructionListType Seq;
  47   BC.MIB->createLongJmp(Seq, Tgt, BC.Ctx.get());
  48   StubBB.clear();
  49   StubBB.addInstructions(Seq.begin(), Seq.end());
  50 }
  51
  52 static BinaryBasicBlock *getBBAtHotColdSplitPoint(BinaryFunction &Func) {
  53   if (!Func.isSplit() || Func.empty())
  54     return nullptr;
  55
  56   assert(!(*Func.begin()).isCold() && "Entry cannot be cold");
  57   for (auto I = Func.getLayout().block_begin(),
  58             E = Func.getLayout().block_end();
  59        I != E; ++I) {
  60     auto Next = std::next(I);
  61     if (Next != E && (*Next)->isCold())
  62       return *I;
  63   }
  64   llvm_unreachable("No hot-colt split point found");
  65 }
  66
  67 static bool shouldInsertStub(const BinaryContext &BC, const MCInst &Inst) {
  68   return (BC.MIB->isBranch(Inst) || BC.MIB->isCall(Inst)) &&
  69          !BC.MIB->isIndirectBranch(Inst) && !BC.MIB->isIndirectCall(Inst);
  70 }
  71
  72 std::pair<std::unique_ptr<BinaryBasicBlock>, MCSymbol *>
  73 LongJmpPass::createNewStub(BinaryBasicBlock &SourceBB, const MCSymbol *TgtSym,
  74                            bool TgtIsFunc, uint64_t AtAddress) {
  75   BinaryFunction &Func = *SourceBB.getFunction();
  76   const BinaryContext &BC = Func.getBinaryContext();
  77   const bool IsCold = SourceBB.isCold();
  78   MCSymbol *StubSym = BC.Ctx->createNamedTempSymbol("Stub");
  79   std::unique_ptr<BinaryBasicBlock> StubBB = Func.createBasicBlock(StubSym);
  80   MCInst Inst;
  81   BC.MIB->createUncondBranch(Inst, TgtSym, BC.Ctx.get());
  82   if (TgtIsFunc)
  83     BC.MIB->convertJmpToTailCall(Inst);
  84   StubBB->addInstruction(Inst);
  85   StubBB->setExecutionCount(0);
  86
  87   // Register this in stubs maps
  88   auto registerInMap = [&](StubGroupsTy &Map) {
  89     StubGroupTy &StubGroup = Map[TgtSym];
  90     StubGroup.insert(
  91         llvm::lower_bound(
  92             StubGroup, std::make_pair(AtAddress, nullptr),
  93             [&](const std::pair<uint64_t, BinaryBasicBlock *> &LHS,
  94                 const std::pair<uint64_t, BinaryBasicBlock *> &RHS) {
  95               return LHS.first < RHS.first;
  96             }),
  97         std::make_pair(AtAddress, StubBB.get()));
  98   };
  99
 100   Stubs[&Func].insert(StubBB.get());
 101   StubBits[StubBB.get()] = BC.MIB->getUncondBranchEncodingSize();
 102   if (IsCold) {
 103     registerInMap(ColdLocalStubs[&Func]);
 104     if (opts::GroupStubs && TgtIsFunc)
 105       registerInMap(ColdStubGroups);
 106     ++NumColdStubs;
 107   } else {
 108     registerInMap(HotLocalStubs[&Func]);
 109     if (opts::GroupStubs && TgtIsFunc)
 110       registerInMap(HotStubGroups);
 111     ++NumHotStubs;
 112   }
 113
 114   return std::make_pair(std::move(StubBB), StubSym);
 115 }
 116
 117 BinaryBasicBlock *LongJmpPass::lookupStubFromGroup(
 118     const StubGroupsTy &StubGroups, const BinaryFunction &Func,
 119     const MCInst &Inst, const MCSymbol *TgtSym, uint64_t DotAddress) const {
 120   const BinaryContext &BC = Func.getBinaryContext();
 121   auto CandidatesIter = StubGroups.find(TgtSym);
 122   if (CandidatesIter == StubGroups.end())
 123     return nullptr;
 124   const StubGroupTy &Candidates = CandidatesIter->second;
 125   if (Candidates.empty())
 126     return nullptr;
 127   auto Cand = llvm::lower_bound(
 128       Candidates, std::make_pair(DotAddress, nullptr),
 129       [&](const std::pair<uint64_t, BinaryBasicBlock *> &LHS,
 130           const std::pair<uint64_t, BinaryBasicBlock *> &RHS) {
 131         return LHS.first < RHS.first;
 132       });
 133   if (Cand == Candidates.end())
 134     return nullptr;
 135   if (Cand != Candidates.begin()) {
 136     const StubTy *LeftCand = std::prev(Cand);
 137     if (Cand->first - DotAddress > DotAddress - LeftCand->first)
 138       Cand = LeftCand;
 139   }
 140   int BitsAvail = BC.MIB->getPCRelEncodingSize(Inst) - 1;
 141   assert(BitsAvail < 63 && "PCRelEncodingSize is too large to use int64_t to"
 142                            "check for out-of-bounds.");
 143   int64_t MaxVal = (1ULL << BitsAvail) - 1;
 144   int64_t MinVal = -(1ULL << BitsAvail);
 145   uint64_t PCRelTgtAddress = Cand->first;
 146   int64_t PCOffset = (int64_t)(PCRelTgtAddress - DotAddress);
 147
 148   LLVM_DEBUG({
 149     if (Candidates.size() > 1)
 150       dbgs() << "Considering stub group with " << Candidates.size()
 151              << " candidates. DotAddress is " << Twine::utohexstr(DotAddress)
 152              << ", chosen candidate address is "
 153              << Twine::utohexstr(Cand->first) << "\n";
 154   });
 155   return (PCOffset < MinVal || PCOffset > MaxVal) ? nullptr : Cand->second;
 156 }
 157
 158 BinaryBasicBlock *
 159 LongJmpPass::lookupGlobalStub(const BinaryBasicBlock &SourceBB,
 160                               const MCInst &Inst, const MCSymbol *TgtSym,
 161                               uint64_t DotAddress) const {
 162   const BinaryFunction &Func = *SourceBB.getFunction();
 163   const StubGroupsTy &StubGroups =
 164       SourceBB.isCold() ? ColdStubGroups : HotStubGroups;
 165   return lookupStubFromGroup(StubGroups, Func, Inst, TgtSym, DotAddress);
 166 }
 167
 168 BinaryBasicBlock *LongJmpPass::lookupLocalStub(const BinaryBasicBlock &SourceBB,
 169                                                const MCInst &Inst,
 170                                                const MCSymbol *TgtSym,
 171                                                uint64_t DotAddress) const {
 172   const BinaryFunction &Func = *SourceBB.getFunction();
 173   const DenseMap<const BinaryFunction *, StubGroupsTy> &StubGroups =
 174       SourceBB.isCold() ? ColdLocalStubs : HotLocalStubs;
 175   const auto Iter = StubGroups.find(&Func);
 176   if (Iter == StubGroups.end())
 177     return nullptr;
 178   return lookupStubFromGroup(Iter->second, Func, Inst, TgtSym, DotAddress);
 179 }
 180
 181 std::unique_ptr<BinaryBasicBlock>
 182 LongJmpPass::replaceTargetWithStub(BinaryBasicBlock &BB, MCInst &Inst,
 183                                    uint64_t DotAddress,
 184                                    uint64_t StubCreationAddress) {
 185   const BinaryFunction &Func = *BB.getFunction();
 186   const BinaryContext &BC = Func.getBinaryContext();
 187   std::unique_ptr<BinaryBasicBlock> NewBB;
 188   const MCSymbol *TgtSym = BC.MIB->getTargetSymbol(Inst);
 189   assert(TgtSym && "getTargetSymbol failed");
 190
 191   BinaryBasicBlock::BinaryBranchInfo BI{0, 0};
 192   BinaryBasicBlock *TgtBB = BB.getSuccessor(TgtSym, BI);
 193   auto LocalStubsIter = Stubs.find(&Func);
 194
 195   // If already using stub and the stub is from another function, create a local
 196   // stub, since the foreign stub is now out of range
 197   if (!TgtBB) {
 198     auto SSIter = SharedStubs.find(TgtSym);
 199     if (SSIter != SharedStubs.end()) {
 200       TgtSym = BC.MIB->getTargetSymbol(*SSIter->second->begin());
 201       --NumSharedStubs;
 202     }
 203   } else if (LocalStubsIter != Stubs.end() &&
 204              LocalStubsIter->second.count(TgtBB)) {
 205     // If we are replacing a local stub (because it is now out of range),
 206     // use its target instead of creating a stub to jump to another stub
 207     TgtSym = BC.MIB->getTargetSymbol(*TgtBB->begin());
 208     TgtBB = BB.getSuccessor(TgtSym, BI);
 209   }
 210
 211   BinaryBasicBlock *StubBB = lookupLocalStub(BB, Inst, TgtSym, DotAddress);
 212   // If not found, look it up in globally shared stub maps if it is a function
 213   // call (TgtBB is not set)
 214   if (!StubBB && !TgtBB) {
 215     StubBB = lookupGlobalStub(BB, Inst, TgtSym, DotAddress);
 216     if (StubBB) {
 217       SharedStubs[StubBB->getLabel()] = StubBB;
 218       ++NumSharedStubs;
 219     }
 220   }
 221   MCSymbol *StubSymbol = StubBB ? StubBB->getLabel() : nullptr;
 222
 223   if (!StubBB) {
 224     std::tie(NewBB, StubSymbol) =
 225         createNewStub(BB, TgtSym, /*is func?*/ !TgtBB, StubCreationAddress);
 226     StubBB = NewBB.get();
 227   }
 228
 229   // Local branch
 230   if (TgtBB) {
 231     uint64_t OrigCount = BI.Count;
 232     uint64_t OrigMispreds = BI.MispredictedCount;
 233     BB.replaceSuccessor(TgtBB, StubBB, OrigCount, OrigMispreds);
 234     StubBB->setExecutionCount(StubBB->getExecutionCount() + OrigCount);
 235     if (NewBB) {
 236       StubBB->addSuccessor(TgtBB, OrigCount, OrigMispreds);
 237       StubBB->setIsCold(BB.isCold());
 238     }
 239     // Call / tail call
 240   } else {
 241     StubBB->setExecutionCount(StubBB->getExecutionCount() +
 242                               BB.getExecutionCount());
 243     if (NewBB) {
 244       assert(TgtBB == nullptr);
 245       StubBB->setIsCold(BB.isCold());
 246       // Set as entry point because this block is valid but we have no preds
 247       StubBB->getFunction()->addEntryPoint(*StubBB);
 248     }
 249   }
 250   BC.MIB->replaceBranchTarget(Inst, StubSymbol, BC.Ctx.get());
 251
 252   return NewBB;
 253 }
 254
 255 void LongJmpPass::updateStubGroups() {
 256   auto update = [&](StubGroupsTy &StubGroups) {
 257     for (auto &KeyVal : StubGroups) {
 258       for (StubTy &Elem : KeyVal.second)
 259         Elem.first = BBAddresses[Elem.second];
 260       llvm::sort(KeyVal.second, llvm::less_first());
 261     }
 262   };
 263
 264   for (auto &KeyVal : HotLocalStubs)
 265     update(KeyVal.second);
 266   for (auto &KeyVal : ColdLocalStubs)
 267     update(KeyVal.second);
 268   update(HotStubGroups);
 269   update(ColdStubGroups);
 270 }
 271
 272 void LongJmpPass::tentativeBBLayout(const BinaryFunction &Func) {
 273   const BinaryContext &BC = Func.getBinaryContext();
 274   uint64_t HotDot = HotAddresses[&Func];
 275   uint64_t ColdDot = ColdAddresses[&Func];
 276   bool Cold = false;
 277   for (const BinaryBasicBlock *BB : Func.getLayout().blocks()) {
 278     if (Cold || BB->isCold()) {
 279       Cold = true;
 280       BBAddresses[BB] = ColdDot;
 281       ColdDot += BC.computeCodeSize(BB->begin(), BB->end());
 282     } else {
 283       BBAddresses[BB] = HotDot;
 284       HotDot += BC.computeCodeSize(BB->begin(), BB->end());
 285     }
 286   }
 287 }
 288
 289 uint64_t LongJmpPass::tentativeLayoutRelocColdPart(
 290     const BinaryContext &BC, std::vector<BinaryFunction *> &SortedFunctions,
 291     uint64_t DotAddress) {
 292   DotAddress = alignTo(DotAddress, llvm::Align(opts::AlignFunctions));
 293   for (BinaryFunction *Func : SortedFunctions) {
 294     if (!Func->isSplit())
 295       continue;
 296     DotAddress = alignTo(DotAddress, Func->getMinAlignment());
 297     uint64_t Pad =
 298         offsetToAlignment(DotAddress, llvm::Align(Func->getAlignment()));
 299     if (Pad <= Func->getMaxColdAlignmentBytes())
 300       DotAddress += Pad;
 301     ColdAddresses[Func] = DotAddress;
 302     LLVM_DEBUG(dbgs() << Func->getPrintName() << " cold tentative: "
 303                       << Twine::utohexstr(DotAddress) << "\n");
 304     DotAddress += Func->estimateColdSize();
 305     DotAddress = alignTo(DotAddress, Func->getConstantIslandAlignment());
 306     DotAddress += Func->estimateConstantIslandSize();
 307   }
 308   return DotAddress;
 309 }
 310
 311 uint64_t LongJmpPass::tentativeLayoutRelocMode(
 312     const BinaryContext &BC, std::vector<BinaryFunction *> &SortedFunctions,
 313     uint64_t DotAddress) {
 314
 315   // Compute hot cold frontier
 316   uint32_t LastHotIndex = -1u;
 317   uint32_t CurrentIndex = 0;
 318   if (opts::HotFunctionsAtEnd) {
 319     for (BinaryFunction *BF : SortedFunctions) {
 320       if (BF->hasValidIndex()) {
 321         LastHotIndex = CurrentIndex;
 322         break;
 323       }
 324
 325       ++CurrentIndex;
 326     }
 327   } else {
 328     for (BinaryFunction *BF : SortedFunctions) {
 329       if (!BF->hasValidIndex()) {
 330         LastHotIndex = CurrentIndex;
 331         break;
 332       }
 333
 334       ++CurrentIndex;
 335     }
 336   }
 337
 338   // Hot
 339   CurrentIndex = 0;
 340   bool ColdLayoutDone = false;
 341   for (BinaryFunction *Func : SortedFunctions) {
 342     if (!BC.shouldEmit(*Func)) {
 343       HotAddresses[Func] = Func->getAddress();
 344       continue;
 345     }
 346
 347     if (!ColdLayoutDone && CurrentIndex >= LastHotIndex) {
 348       DotAddress =
 349           tentativeLayoutRelocColdPart(BC, SortedFunctions, DotAddress);
 350       ColdLayoutDone = true;
 351       if (opts::HotFunctionsAtEnd)
 352         DotAddress = alignTo(DotAddress, opts::AlignText);
 353     }
 354
 355     DotAddress = alignTo(DotAddress, Func->getMinAlignment());
 356     uint64_t Pad =
 357         offsetToAlignment(DotAddress, llvm::Align(Func->getAlignment()));
 358     if (Pad <= Func->getMaxAlignmentBytes())
 359       DotAddress += Pad;
 360     HotAddresses[Func] = DotAddress;
 361     LLVM_DEBUG(dbgs() << Func->getPrintName() << " tentative: "
 362                       << Twine::utohexstr(DotAddress) << "\n");
 363     if (!Func->isSplit())
 364       DotAddress += Func->estimateSize();
 365     else
 366       DotAddress += Func->estimateHotSize();
 367
 368     DotAddress = alignTo(DotAddress, Func->getConstantIslandAlignment());
 369     DotAddress += Func->estimateConstantIslandSize();
 370     ++CurrentIndex;
 371   }
 372   // BBs
 373   for (BinaryFunction *Func : SortedFunctions)
 374     tentativeBBLayout(*Func);
 375
 376   return DotAddress;
 377 }
 378
 379 void LongJmpPass::tentativeLayout(
 380     const BinaryContext &BC, std::vector<BinaryFunction *> &SortedFunctions) {
 381   uint64_t DotAddress = BC.LayoutStartAddress;
 382
 383   if (!BC.HasRelocations) {
 384     for (BinaryFunction *Func : SortedFunctions) {
 385       HotAddresses[Func] = Func->getAddress();
 386       DotAddress = alignTo(DotAddress, ColdFragAlign);
 387       ColdAddresses[Func] = DotAddress;
 388       if (Func->isSplit())
 389         DotAddress += Func->estimateColdSize();
 390       tentativeBBLayout(*Func);
 391     }
 392
 393     return;
 394   }
 395
 396   // Relocation mode
 397   uint64_t EstimatedTextSize = 0;
 398   if (opts::UseOldText) {
 399     EstimatedTextSize = tentativeLayoutRelocMode(BC, SortedFunctions, 0);
 400
 401     // Initial padding
 402     if (EstimatedTextSize <= BC.OldTextSectionSize) {
 403       DotAddress = BC.OldTextSectionAddress;
 404       uint64_t Pad =
 405           offsetToAlignment(DotAddress, llvm::Align(opts::AlignText));
 406       if (Pad + EstimatedTextSize <= BC.OldTextSectionSize) {
 407         DotAddress += Pad;
 408       }
 409     }
 410   }
 411
 412   if (!EstimatedTextSize || EstimatedTextSize > BC.OldTextSectionSize)
 413     DotAddress = alignTo(BC.LayoutStartAddress, opts::AlignText);
 414
 415   tentativeLayoutRelocMode(BC, SortedFunctions, DotAddress);
 416 }
 417
 418 bool LongJmpPass::usesStub(const BinaryFunction &Func,
 419                            const MCInst &Inst) const {
 420   const MCSymbol *TgtSym = Func.getBinaryContext().MIB->getTargetSymbol(Inst);
 421   const BinaryBasicBlock *TgtBB = Func.getBasicBlockForLabel(TgtSym);
 422   auto Iter = Stubs.find(&Func);
 423   if (Iter != Stubs.end())
 424     return Iter->second.count(TgtBB);
 425   return false;
 426 }
 427
 428 uint64_t LongJmpPass::getSymbolAddress(const BinaryContext &BC,
 429                                        const MCSymbol *Target,
 430                                        const BinaryBasicBlock *TgtBB) const {
 431   if (TgtBB) {
 432     auto Iter = BBAddresses.find(TgtBB);
 433     assert(Iter != BBAddresses.end() && "Unrecognized BB");
 434     return Iter->second;
 435   }
 436   uint64_t EntryID = 0;
 437   const BinaryFunction *TargetFunc = BC.getFunctionForSymbol(Target, &EntryID);
 438   auto Iter = HotAddresses.find(TargetFunc);
 439   if (Iter == HotAddresses.end() || (TargetFunc && EntryID)) {
 440     // Look at BinaryContext's resolution for this symbol - this is a symbol not
 441     // mapped to a BinaryFunction
 442     ErrorOr<uint64_t> ValueOrError = BC.getSymbolValue(*Target);
 443     assert(ValueOrError && "Unrecognized symbol");
 444     return *ValueOrError;
 445   }
 446   return Iter->second;
 447 }
 448
 449 bool LongJmpPass::relaxStub(BinaryBasicBlock &StubBB) {
 450   const BinaryFunction &Func = *StubBB.getFunction();
 451   const BinaryContext &BC = Func.getBinaryContext();
 452   const int Bits = StubBits[&StubBB];
 453   // Already working with the largest range?
 454   if (Bits == static_cast<int>(BC.AsmInfo->getCodePointerSize() * 8))
 455     return false;
 456
 457   const static int RangeShortJmp = BC.MIB->getShortJmpEncodingSize();
 458   const static int RangeSingleInstr = BC.MIB->getUncondBranchEncodingSize();
 459   const static uint64_t ShortJmpMask = ~((1ULL << RangeShortJmp) - 1);
 460   const static uint64_t SingleInstrMask =
 461       ~((1ULL << (RangeSingleInstr - 1)) - 1);
 462
 463   const MCSymbol *RealTargetSym = BC.MIB->getTargetSymbol(*StubBB.begin());
 464   const BinaryBasicBlock *TgtBB = Func.getBasicBlockForLabel(RealTargetSym);
 465   uint64_t TgtAddress = getSymbolAddress(BC, RealTargetSym, TgtBB);
 466   uint64_t DotAddress = BBAddresses[&StubBB];
 467   uint64_t PCRelTgtAddress = DotAddress > TgtAddress ? DotAddress - TgtAddress
 468                                                      : TgtAddress - DotAddress;
 469   // If it fits in one instruction, do not relax
 470   if (!(PCRelTgtAddress & SingleInstrMask))
 471     return false;
 472
 473   // Fits short jmp
 474   if (!(PCRelTgtAddress & ShortJmpMask)) {
 475     if (Bits >= RangeShortJmp)
 476       return false;
 477
 478     LLVM_DEBUG(dbgs() << "Relaxing stub to short jump. PCRelTgtAddress = "
 479                       << Twine::utohexstr(PCRelTgtAddress)
 480                       << " RealTargetSym = " << RealTargetSym->getName()
 481                       << "\n");
 482     relaxStubToShortJmp(StubBB, RealTargetSym);
 483     StubBits[&StubBB] = RangeShortJmp;
 484     return true;
 485   }
 486
 487   // The long jmp uses absolute address on AArch64
 488   // So we could not use it for PIC binaries
 489   if (BC.isAArch64() && !BC.HasFixedLoadAddress) {
 490     errs() << "BOLT-ERROR: Unable to relax stub for PIC binary\n";
 491     exit(1);
 492   }
 493
 494   LLVM_DEBUG(dbgs() << "Relaxing stub to long jump. PCRelTgtAddress = "
 495                     << Twine::utohexstr(PCRelTgtAddress)
 496                     << " RealTargetSym = " << RealTargetSym->getName() << "\n");
 497   relaxStubToLongJmp(StubBB, RealTargetSym);
 498   StubBits[&StubBB] = static_cast<int>(BC.AsmInfo->getCodePointerSize() * 8);
 499   return true;
 500 }
 501
 502 bool LongJmpPass::needsStub(const BinaryBasicBlock &BB, const MCInst &Inst,
 503                             uint64_t DotAddress) const {
 504   const BinaryFunction &Func = *BB.getFunction();
 505   const BinaryContext &BC = Func.getBinaryContext();
 506   const MCSymbol *TgtSym = BC.MIB->getTargetSymbol(Inst);
 507   assert(TgtSym && "getTargetSymbol failed");
 508
 509   const BinaryBasicBlock *TgtBB = Func.getBasicBlockForLabel(TgtSym);
 510   // Check for shared stubs from foreign functions
 511   if (!TgtBB) {
 512     auto SSIter = SharedStubs.find(TgtSym);
 513     if (SSIter != SharedStubs.end())
 514       TgtBB = SSIter->second;
 515   }
 516
 517   int BitsAvail = BC.MIB->getPCRelEncodingSize(Inst) - 1;
 518   assert(BitsAvail < 63 && "PCRelEncodingSize is too large to use int64_t to"
 519                            "check for out-of-bounds.");
 520   int64_t MaxVal = (1ULL << BitsAvail) - 1;
 521   int64_t MinVal = -(1ULL << BitsAvail);
 522
 523   uint64_t PCRelTgtAddress = getSymbolAddress(BC, TgtSym, TgtBB);
 524   int64_t PCOffset = (int64_t)(PCRelTgtAddress - DotAddress);
 525
 526   return PCOffset < MinVal || PCOffset > MaxVal;
 527 }
 528
 529 bool LongJmpPass::relax(BinaryFunction &Func) {
 530   const BinaryContext &BC = Func.getBinaryContext();
 531   bool Modified = false;
 532
 533   assert(BC.isAArch64() && "Unsupported arch");
 534   constexpr int InsnSize = 4; // AArch64
 535   std::vector<std::pair<BinaryBasicBlock *, std::unique_ptr<BinaryBasicBlock>>>
 536       Insertions;
 537
 538   BinaryBasicBlock *Frontier = getBBAtHotColdSplitPoint(Func);
 539   uint64_t FrontierAddress = Frontier ? BBAddresses[Frontier] : 0;
 540   if (FrontierAddress)
 541     FrontierAddress += Frontier->getNumNonPseudos() * InsnSize;
 542
 543   // Add necessary stubs for branch targets we know we can't fit in the
 544   // instruction
 545   for (BinaryBasicBlock &BB : Func) {
 546     uint64_t DotAddress = BBAddresses[&BB];
 547     // Stubs themselves are relaxed on the next loop
 548     if (Stubs[&Func].count(&BB))
 549       continue;
 550
 551     for (MCInst &Inst : BB) {
 552       if (BC.MIB->isPseudo(Inst))
 553         continue;
 554
 555       if (!shouldInsertStub(BC, Inst)) {
 556         DotAddress += InsnSize;
 557         continue;
 558       }
 559
 560       // Check and relax direct branch or call
 561       if (!needsStub(BB, Inst, DotAddress)) {
 562         DotAddress += InsnSize;
 563         continue;
 564       }
 565       Modified = true;
 566
 567       // Insert stubs close to the patched BB if call, but far away from the
 568       // hot path if a branch, since this branch target is the cold region
 569       // (but first check that the far away stub will be in range).
 570       BinaryBasicBlock *InsertionPoint = &BB;
 571       if (Func.isSimple() && !BC.MIB->isCall(Inst) && FrontierAddress &&
 572           !BB.isCold()) {
 573         int BitsAvail = BC.MIB->getPCRelEncodingSize(Inst) - 1;
 574         uint64_t Mask = ~((1ULL << BitsAvail) - 1);
 575         assert(FrontierAddress > DotAddress &&
 576                "Hot code should be before the frontier");
 577         uint64_t PCRelTgt = FrontierAddress - DotAddress;
 578         if (!(PCRelTgt & Mask))
 579           InsertionPoint = Frontier;
 580       }
 581       // Always put stubs at the end of the function if non-simple. We can't
 582       // change the layout of non-simple functions because it has jump tables
 583       // that we do not control.
 584       if (!Func.isSimple())
 585         InsertionPoint = &*std::prev(Func.end());
 586
 587       // Create a stub to handle a far-away target
 588       Insertions.emplace_back(InsertionPoint,
 589                               replaceTargetWithStub(BB, Inst, DotAddress,
 590                                                     InsertionPoint == Frontier
 591                                                         ? FrontierAddress
 592                                                         : DotAddress));
 593
 594       DotAddress += InsnSize;
 595     }
 596   }
 597
 598   // Relax stubs if necessary
 599   for (BinaryBasicBlock &BB : Func) {
 600     if (!Stubs[&Func].count(&BB) || !BB.isValid())
 601       continue;
 602
 603     Modified |= relaxStub(BB);
 604   }
 605
 606   for (std::pair<BinaryBasicBlock *, std::unique_ptr<BinaryBasicBlock>> &Elmt :
 607        Insertions) {
 608     if (!Elmt.second)
 609       continue;
 610     std::vector<std::unique_ptr<BinaryBasicBlock>> NewBBs;
 611     NewBBs.emplace_back(std::move(Elmt.second));
 612     Func.insertBasicBlocks(Elmt.first, std::move(NewBBs), true);
 613   }
 614
 615   return Modified;
 616 }
 617
 618 void LongJmpPass::runOnFunctions(BinaryContext &BC) {
 619   outs() << "BOLT-INFO: Starting stub-insertion pass\n";
 620   std::vector<BinaryFunction *> Sorted = BC.getSortedFunctions();
 621   bool Modified;
 622   uint32_t Iterations = 0;
 623   do {
 624     ++Iterations;
 625     Modified = false;
 626     tentativeLayout(BC, Sorted);
 627     updateStubGroups();
 628     for (BinaryFunction *Func : Sorted) {
 629       if (relax(*Func)) {
 630         // Don't ruin non-simple functions, they can't afford to have the layout
 631         // changed.
 632         if (Func->isSimple())
 633           Func->fixBranches();
 634         Modified = true;
 635       }
 636     }
 637   } while (Modified);
 638   outs() << "BOLT-INFO: Inserted " << NumHotStubs
 639          << " stubs in the hot area and " << NumColdStubs
 640          << " stubs in the cold area. Shared " << NumSharedStubs
 641          << " times, iterated " << Iterations << " times.\n";
 642 }
 643 } // namespace bolt
 644 } // namespace llvm