1 //===- bolt/Passes/LongJmp.h ------------------------------------*- C++ -*-===// 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 #ifndef BOLT_PASSES_LONGJMP_H 10 #define BOLT_PASSES_LONGJMP_H 11 12 #include "bolt/Passes/BinaryPasses.h" 13 14 namespace llvm { 15 namespace bolt { 16 17 /// LongJmp is veneer-insertion pass originally written for AArch64 that 18 /// compensates for its short-range branches, typically done during linking. We 19 /// pull this pass inside BOLT because here we can do a better job at stub 20 /// inserting by manipulating the CFG, something linkers can't do. 21 /// 22 /// We iteratively repeat the following until no modification is done: we do a 23 /// tentative layout with the current function sizes; then we add stubs for 24 /// branches that we know are out of range or we expand smaller stubs (28-bit) 25 /// to a large one if necessary (32 or 64). 26 /// 27 /// This expansion inserts the equivalent of "linker stubs", small 28 /// blocks of code that load a 64-bit address into a pre-allocated register and 29 // then executes an unconditional indirect branch on this register. By using a 30 /// 64-bit range, we guarantee it can reach any code location. 31 /// 32 class LongJmpPass : public BinaryFunctionPass { 33 /// Used to implement stub grouping (re-using a stub from one function into 34 /// another) 35 using StubTy = std::pair<uint64_t, BinaryBasicBlock *>; 36 using StubGroupTy = SmallVector<StubTy, 4>; 37 using StubGroupsTy = DenseMap<const MCSymbol *, StubGroupTy>; 38 StubGroupsTy HotStubGroups; 39 StubGroupsTy ColdStubGroups; 40 DenseMap<const MCSymbol *, BinaryBasicBlock *> SharedStubs; 41 42 /// Stubs that are local to a function. This will be the primary lookup 43 /// before resorting to stubs located in foreign functions. 44 using StubMapTy = DenseMap<const BinaryFunction *, StubGroupsTy>; 45 /// Used to quickly fetch stubs based on the target they jump to 46 StubMapTy HotLocalStubs; 47 StubMapTy ColdLocalStubs; 48 49 /// Used to quickly identify whether a BB is a stub, sharded by function 50 DenseMap<const BinaryFunction *, std::set<const BinaryBasicBlock *>> Stubs; 51 52 using FuncAddressesMapTy = DenseMap<const BinaryFunction *, uint64_t>; 53 /// Hold tentative addresses 54 FuncAddressesMapTy HotAddresses; 55 FuncAddressesMapTy ColdAddresses; 56 DenseMap<const BinaryBasicBlock *, uint64_t> BBAddresses; 57 58 /// Used to identify the stub size 59 DenseMap<const BinaryBasicBlock *, int> StubBits; 60 61 /// Stats about number of stubs inserted 62 uint32_t NumHotStubs{0}; 63 uint32_t NumColdStubs{0}; 64 uint32_t NumSharedStubs{0}; 65 66 /// -- Layout estimation methods -- 67 /// Try to do layout before running the emitter, by looking at BinaryFunctions 68 /// and MCInsts -- this is an estimation. To be correct for longjmp inserter 69 /// purposes, we need to do a size worst-case estimation. Real layout is done 70 /// by RewriteInstance::mapFileSections() 71 void tentativeLayout(const BinaryContext &BC, 72 std::vector<BinaryFunction *> &SortedFunctions); 73 uint64_t 74 tentativeLayoutRelocMode(const BinaryContext &BC, 75 std::vector<BinaryFunction *> &SortedFunctions, 76 uint64_t DotAddress); 77 uint64_t 78 tentativeLayoutRelocColdPart(const BinaryContext &BC, 79 std::vector<BinaryFunction *> &SortedFunctions, 80 uint64_t DotAddress); 81 void tentativeBBLayout(const BinaryFunction &Func); 82 83 /// Update stubs addresses with their exact address after a round of stub 84 /// insertion and layout estimation is done. 85 void updateStubGroups(); 86 87 /// -- Relaxation/stub insertion methods -- 88 /// Creates a new stub jumping to \p TgtSym and updates bookkeeping about 89 /// this stub using \p AtAddress as its initial location. This location is 90 /// an approximation and will be later resolved to the exact location in 91 /// a next iteration, in updateStubGroups. 92 std::pair<std::unique_ptr<BinaryBasicBlock>, MCSymbol *> 93 createNewStub(BinaryBasicBlock &SourceBB, const MCSymbol *TgtSym, 94 bool TgtIsFunc, uint64_t AtAddress); 95 96 /// Replace the target of call or conditional branch in \p Inst with a 97 /// a stub that in turn will branch to the target (perform stub insertion). 98 /// If a new stub was created, return it. 99 std::unique_ptr<BinaryBasicBlock> 100 replaceTargetWithStub(BinaryBasicBlock &BB, MCInst &Inst, uint64_t DotAddress, 101 uint64_t StubCreationAddress); 102 103 /// Helper used to fetch the closest stub to \p Inst at \p DotAddress that 104 /// is jumping to \p TgtSym. Returns nullptr if the closest stub is out of 105 /// range or if it doesn't exist. The source of truth for stubs will be the 106 /// map \p StubGroups, which can be either local stubs for a particular 107 /// function that is very large and needs to group stubs, or can be global 108 /// stubs if we are sharing stubs across functions. 109 BinaryBasicBlock *lookupStubFromGroup(const StubGroupsTy &StubGroups, 110 const BinaryFunction &Func, 111 const MCInst &Inst, 112 const MCSymbol *TgtSym, 113 uint64_t DotAddress) const; 114 115 /// Lookup closest stub from the global pool, meaning this can return a basic 116 /// block from another function. 117 BinaryBasicBlock *lookupGlobalStub(const BinaryBasicBlock &SourceBB, 118 const MCInst &Inst, const MCSymbol *TgtSym, 119 uint64_t DotAddress) const; 120 121 /// Lookup closest stub local to \p Func. 122 BinaryBasicBlock *lookupLocalStub(const BinaryBasicBlock &SourceBB, 123 const MCInst &Inst, const MCSymbol *TgtSym, 124 uint64_t DotAddress) const; 125 126 /// Helper to identify whether \p Inst is branching to a stub 127 bool usesStub(const BinaryFunction &Func, const MCInst &Inst) const; 128 129 /// True if Inst is a branch that is out of range 130 bool needsStub(const BinaryBasicBlock &BB, const MCInst &Inst, 131 uint64_t DotAddress) const; 132 133 /// Expand the range of the stub in StubBB if necessary 134 bool relaxStub(BinaryBasicBlock &StubBB); 135 136 /// Helper to resolve a symbol address according to our tentative layout 137 uint64_t getSymbolAddress(const BinaryContext &BC, const MCSymbol *Target, 138 const BinaryBasicBlock *TgtBB) const; 139 140 /// Relax function by adding necessary stubs or relaxing existing stubs 141 bool relax(BinaryFunction &BF); 142 143 public: 144 /// BinaryPass public interface 145 LongJmpPass(const cl::opt<bool> & PrintPass)146 explicit LongJmpPass(const cl::opt<bool> &PrintPass) 147 : BinaryFunctionPass(PrintPass) {} 148 getName()149 const char *getName() const override { return "long-jmp"; } 150 151 void runOnFunctions(BinaryContext &BC) override; 152 }; 153 } // namespace bolt 154 } // namespace llvm 155 156 #endif 157