1 //===- RelLookupTableConverterPass - Rel Table Conv -----------------------===// 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 relative lookup table converter that converts 10 // lookup tables to relative lookup tables to make them PIC-friendly. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Transforms/Utils/RelLookupTableConverter.h" 15 #include "llvm/Analysis/ConstantFolding.h" 16 #include "llvm/Analysis/TargetTransformInfo.h" 17 #include "llvm/IR/BasicBlock.h" 18 #include "llvm/IR/IRBuilder.h" 19 #include "llvm/IR/Instructions.h" 20 #include "llvm/IR/Module.h" 21 22 using namespace llvm; 23 24 static bool shouldConvertToRelLookupTable(Module &M, GlobalVariable &GV) { 25 // If lookup table has more than one user, 26 // do not generate a relative lookup table. 27 // This is to simplify the analysis that needs to be done for this pass. 28 // TODO: Add support for lookup tables with multiple uses. 29 // For ex, this can happen when a function that uses a lookup table gets 30 // inlined into multiple call sites. 31 if (!GV.hasInitializer() || 32 !GV.isConstant() || 33 !GV.hasOneUse()) 34 return false; 35 36 GetElementPtrInst *GEP = 37 dyn_cast<GetElementPtrInst>(GV.use_begin()->getUser()); 38 if (!GEP || !GEP->hasOneUse() || 39 GV.getValueType() != GEP->getSourceElementType()) 40 return false; 41 42 LoadInst *Load = dyn_cast<LoadInst>(GEP->use_begin()->getUser()); 43 if (!Load || !Load->hasOneUse() || 44 Load->getType() != GEP->getResultElementType()) 45 return false; 46 47 // If the original lookup table does not have local linkage and is 48 // not dso_local, do not generate a relative lookup table. 49 // This optimization creates a relative lookup table that consists of 50 // offsets between the start of the lookup table and its elements. 51 // To be able to generate these offsets, relative lookup table and 52 // its elements should have internal linkage and be dso_local, which means 53 // that they should resolve to symbols within the same linkage unit. 54 if (!GV.hasLocalLinkage() || 55 !GV.isDSOLocal() || 56 !GV.isImplicitDSOLocal()) 57 return false; 58 59 ConstantArray *Array = dyn_cast<ConstantArray>(GV.getInitializer()); 60 if (!Array) 61 return false; 62 63 // If values are not 64-bit pointers, do not generate a relative lookup table. 64 const DataLayout &DL = M.getDataLayout(); 65 Type *ElemType = Array->getType()->getElementType(); 66 if (!ElemType->isPointerTy() || DL.getPointerTypeSizeInBits(ElemType) != 64) 67 return false; 68 69 SmallVector<GlobalVariable *, 4> GVOps; 70 Triple TT = M.getTargetTriple(); 71 // FIXME: This should be removed in the future. 72 bool ShouldDropUnnamedAddr = 73 // Drop unnamed_addr to avoid matching pattern in 74 // `handleIndirectSymViaGOTPCRel`, which generates GOTPCREL relocations 75 // not supported by the GNU linker and LLD versions below 18 on aarch64. 76 TT.isAArch64() 77 // Apple's ld64 (and ld-prime on Xcode 15.2) miscompile something on 78 // x86_64-apple-darwin. See 79 // https://github.com/rust-lang/rust/issues/140686 and 80 // https://github.com/rust-lang/rust/issues/141306. 81 || (TT.isX86() && TT.isOSDarwin()); 82 83 for (const Use &Op : Array->operands()) { 84 Constant *ConstOp = cast<Constant>(&Op); 85 GlobalValue *GVOp; 86 APInt Offset; 87 88 // If an operand is not a constant offset from a lookup table, 89 // do not generate a relative lookup table. 90 if (!IsConstantOffsetFromGlobal(ConstOp, GVOp, Offset, DL)) 91 return false; 92 93 // If operand is mutable, do not generate a relative lookup table. 94 auto *GlovalVarOp = dyn_cast<GlobalVariable>(GVOp); 95 if (!GlovalVarOp || !GlovalVarOp->isConstant()) 96 return false; 97 98 if (!GlovalVarOp->hasLocalLinkage() || 99 !GlovalVarOp->isDSOLocal() || 100 !GlovalVarOp->isImplicitDSOLocal()) 101 return false; 102 103 if (ShouldDropUnnamedAddr) 104 GVOps.push_back(GlovalVarOp); 105 } 106 107 if (ShouldDropUnnamedAddr) 108 for (auto *GVOp : GVOps) 109 GVOp->setUnnamedAddr(GlobalValue::UnnamedAddr::None); 110 111 return true; 112 } 113 114 static GlobalVariable *createRelLookupTable(Function &Func, 115 GlobalVariable &LookupTable) { 116 Module &M = *Func.getParent(); 117 ConstantArray *LookupTableArr = 118 cast<ConstantArray>(LookupTable.getInitializer()); 119 unsigned NumElts = LookupTableArr->getType()->getNumElements(); 120 ArrayType *IntArrayTy = 121 ArrayType::get(Type::getInt32Ty(M.getContext()), NumElts); 122 123 GlobalVariable *RelLookupTable = new GlobalVariable( 124 M, IntArrayTy, LookupTable.isConstant(), LookupTable.getLinkage(), 125 nullptr, LookupTable.getName() + ".rel", &LookupTable, 126 LookupTable.getThreadLocalMode(), LookupTable.getAddressSpace(), 127 LookupTable.isExternallyInitialized()); 128 129 uint64_t Idx = 0; 130 SmallVector<Constant *, 64> RelLookupTableContents(NumElts); 131 132 for (Use &Operand : LookupTableArr->operands()) { 133 Constant *Element = cast<Constant>(Operand); 134 Type *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext()); 135 Constant *Base = llvm::ConstantExpr::getPtrToInt(RelLookupTable, IntPtrTy); 136 Constant *Target = llvm::ConstantExpr::getPtrToInt(Element, IntPtrTy); 137 Constant *Sub = llvm::ConstantExpr::getSub(Target, Base); 138 Constant *RelOffset = 139 llvm::ConstantExpr::getTrunc(Sub, Type::getInt32Ty(M.getContext())); 140 RelLookupTableContents[Idx++] = RelOffset; 141 } 142 143 Constant *Initializer = 144 ConstantArray::get(IntArrayTy, RelLookupTableContents); 145 RelLookupTable->setInitializer(Initializer); 146 RelLookupTable->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); 147 RelLookupTable->setAlignment(llvm::Align(4)); 148 return RelLookupTable; 149 } 150 151 static void convertToRelLookupTable(GlobalVariable &LookupTable) { 152 GetElementPtrInst *GEP = 153 cast<GetElementPtrInst>(LookupTable.use_begin()->getUser()); 154 LoadInst *Load = cast<LoadInst>(GEP->use_begin()->getUser()); 155 156 Module &M = *LookupTable.getParent(); 157 BasicBlock *BB = GEP->getParent(); 158 IRBuilder<> Builder(BB); 159 Function &Func = *BB->getParent(); 160 161 // Generate an array that consists of relative offsets. 162 GlobalVariable *RelLookupTable = createRelLookupTable(Func, LookupTable); 163 164 // Place new instruction sequence before GEP. 165 Builder.SetInsertPoint(GEP); 166 Value *Index = GEP->getOperand(2); 167 IntegerType *IntTy = cast<IntegerType>(Index->getType()); 168 Value *Offset = 169 Builder.CreateShl(Index, ConstantInt::get(IntTy, 2), "reltable.shift"); 170 171 // Insert the call to load.relative intrinsic before LOAD. 172 // GEP might not be immediately followed by a LOAD, like it can be hoisted 173 // outside the loop or another instruction might be inserted them in between. 174 Builder.SetInsertPoint(Load); 175 Function *LoadRelIntrinsic = llvm::Intrinsic::getOrInsertDeclaration( 176 &M, Intrinsic::load_relative, {Index->getType()}); 177 178 // Create a call to load.relative intrinsic that computes the target address 179 // by adding base address (lookup table address) and relative offset. 180 Value *Result = Builder.CreateCall(LoadRelIntrinsic, {RelLookupTable, Offset}, 181 "reltable.intrinsic"); 182 183 // Replace load instruction with the new generated instruction sequence. 184 Load->replaceAllUsesWith(Result); 185 // Remove Load and GEP instructions. 186 Load->eraseFromParent(); 187 GEP->eraseFromParent(); 188 } 189 190 // Convert lookup tables to relative lookup tables in the module. 191 static bool convertToRelativeLookupTables( 192 Module &M, function_ref<TargetTransformInfo &(Function &)> GetTTI) { 193 for (Function &F : M) { 194 if (F.isDeclaration()) 195 continue; 196 197 // Check if we have a target that supports relative lookup tables. 198 if (!GetTTI(F).shouldBuildRelLookupTables()) 199 return false; 200 201 // We assume that the result is independent of the checked function. 202 break; 203 } 204 205 bool Changed = false; 206 207 for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) { 208 if (!shouldConvertToRelLookupTable(M, GV)) 209 continue; 210 211 convertToRelLookupTable(GV); 212 213 // Remove the original lookup table. 214 GV.eraseFromParent(); 215 216 Changed = true; 217 } 218 219 return Changed; 220 } 221 222 PreservedAnalyses RelLookupTableConverterPass::run(Module &M, 223 ModuleAnalysisManager &AM) { 224 FunctionAnalysisManager &FAM = 225 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 226 227 auto GetTTI = [&](Function &F) -> TargetTransformInfo & { 228 return FAM.getResult<TargetIRAnalysis>(F); 229 }; 230 231 if (!convertToRelativeLookupTables(M, GetTTI)) 232 return PreservedAnalyses::all(); 233 234 PreservedAnalyses PA; 235 PA.preserveSet<CFGAnalyses>(); 236 return PA; 237 } 238