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 /// The shortest distance for any branch instruction on AArch64. 67 static constexpr size_t ShortestJumpBits = 16; 68 static constexpr size_t ShortestJumpSpan = 1ULL << (ShortestJumpBits - 1); 69 70 /// The longest single-instruction branch. 71 static constexpr size_t LongestJumpBits = 28; 72 static constexpr size_t LongestJumpSpan = 1ULL << (LongestJumpBits - 1); 73 74 /// Relax all internal function branches including those between fragments. 75 /// Assume that fragments are placed in different sections but are within 76 /// 128MB of each other. 77 void relaxLocalBranches(BinaryFunction &BF); 78 79 /// -- Layout estimation methods -- 80 /// Try to do layout before running the emitter, by looking at BinaryFunctions 81 /// and MCInsts -- this is an estimation. To be correct for longjmp inserter 82 /// purposes, we need to do a size worst-case estimation. Real layout is done 83 /// by RewriteInstance::mapFileSections() 84 void tentativeLayout(const BinaryContext &BC, 85 std::vector<BinaryFunction *> &SortedFunctions); 86 uint64_t 87 tentativeLayoutRelocMode(const BinaryContext &BC, 88 std::vector<BinaryFunction *> &SortedFunctions, 89 uint64_t DotAddress); 90 uint64_t 91 tentativeLayoutRelocColdPart(const BinaryContext &BC, 92 std::vector<BinaryFunction *> &SortedFunctions, 93 uint64_t DotAddress); 94 void tentativeBBLayout(const BinaryFunction &Func); 95 96 /// Update stubs addresses with their exact address after a round of stub 97 /// insertion and layout estimation is done. 98 void updateStubGroups(); 99 100 /// -- Relaxation/stub insertion methods -- 101 /// Creates a new stub jumping to \p TgtSym and updates bookkeeping about 102 /// this stub using \p AtAddress as its initial location. This location is 103 /// an approximation and will be later resolved to the exact location in 104 /// a next iteration, in updateStubGroups. 105 std::pair<std::unique_ptr<BinaryBasicBlock>, MCSymbol *> 106 createNewStub(BinaryBasicBlock &SourceBB, const MCSymbol *TgtSym, 107 bool TgtIsFunc, uint64_t AtAddress); 108 109 /// Replace the target of call or conditional branch in \p Inst with a 110 /// a stub that in turn will branch to the target (perform stub insertion). 111 /// If a new stub was created, return it. 112 std::unique_ptr<BinaryBasicBlock> 113 replaceTargetWithStub(BinaryBasicBlock &BB, MCInst &Inst, uint64_t DotAddress, 114 uint64_t StubCreationAddress); 115 116 /// Helper used to fetch the closest stub to \p Inst at \p DotAddress that 117 /// is jumping to \p TgtSym. Returns nullptr if the closest stub is out of 118 /// range or if it doesn't exist. The source of truth for stubs will be the 119 /// map \p StubGroups, which can be either local stubs for a particular 120 /// function that is very large and needs to group stubs, or can be global 121 /// stubs if we are sharing stubs across functions. 122 BinaryBasicBlock *lookupStubFromGroup(const StubGroupsTy &StubGroups, 123 const BinaryFunction &Func, 124 const MCInst &Inst, 125 const MCSymbol *TgtSym, 126 uint64_t DotAddress) const; 127 128 /// Lookup closest stub from the global pool, meaning this can return a basic 129 /// block from another function. 130 BinaryBasicBlock *lookupGlobalStub(const BinaryBasicBlock &SourceBB, 131 const MCInst &Inst, const MCSymbol *TgtSym, 132 uint64_t DotAddress) const; 133 134 /// Lookup closest stub local to \p Func. 135 BinaryBasicBlock *lookupLocalStub(const BinaryBasicBlock &SourceBB, 136 const MCInst &Inst, const MCSymbol *TgtSym, 137 uint64_t DotAddress) const; 138 139 /// Helper to identify whether \p Inst is branching to a stub 140 bool usesStub(const BinaryFunction &Func, const MCInst &Inst) const; 141 142 /// True if Inst is a branch that is out of range 143 bool needsStub(const BinaryBasicBlock &BB, const MCInst &Inst, 144 uint64_t DotAddress) const; 145 146 /// Expand the range of the stub in StubBB if necessary 147 Error relaxStub(BinaryBasicBlock &StubBB, bool &Modified); 148 149 /// Helper to resolve a symbol address according to our tentative layout 150 uint64_t getSymbolAddress(const BinaryContext &BC, const MCSymbol *Target, 151 const BinaryBasicBlock *TgtBB) const; 152 153 /// Relax function by adding necessary stubs or relaxing existing stubs 154 Error relax(BinaryFunction &BF, bool &Modified); 155 156 public: 157 /// BinaryPass public interface 158 159 explicit LongJmpPass(const cl::opt<bool> &PrintPass) 160 : BinaryFunctionPass(PrintPass) {} 161 162 const char *getName() const override { return "long-jmp"; } 163 164 Error runOnFunctions(BinaryContext &BC) override; 165 }; 166 } // namespace bolt 167 } // namespace llvm 168 169 #endif 170