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 #include "llvm/InitializePasses.h" 22 #include "llvm/Pass.h" 23 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 24 25 using namespace llvm; 26 27 static bool shouldConvertToRelLookupTable(Module &M, GlobalVariable &GV) { 28 // If lookup table has more than one user, 29 // do not generate a relative lookup table. 30 // This is to simplify the analysis that needs to be done for this pass. 31 // TODO: Add support for lookup tables with multiple uses. 32 // For ex, this can happen when a function that uses a lookup table gets 33 // inlined into multiple call sites. 34 if (!GV.hasInitializer() || 35 !GV.isConstant() || 36 !GV.hasOneUse()) 37 return false; 38 39 GetElementPtrInst *GEP = 40 dyn_cast<GetElementPtrInst>(GV.use_begin()->getUser()); 41 if (!GEP || !GEP->hasOneUse() || 42 GV.getValueType() != GEP->getSourceElementType()) 43 return false; 44 45 LoadInst *Load = dyn_cast<LoadInst>(GEP->use_begin()->getUser()); 46 if (!Load || !Load->hasOneUse() || 47 Load->getType() != GEP->getResultElementType()) 48 return false; 49 50 // If the original lookup table does not have local linkage and is 51 // not dso_local, do not generate a relative lookup table. 52 // This optimization creates a relative lookup table that consists of 53 // offsets between the start of the lookup table and its elements. 54 // To be able to generate these offsets, relative lookup table and 55 // its elements should have internal linkage and be dso_local, which means 56 // that they should resolve to symbols within the same linkage unit. 57 if (!GV.hasLocalLinkage() || 58 !GV.isDSOLocal() || 59 !GV.isImplicitDSOLocal()) 60 return false; 61 62 ConstantArray *Array = dyn_cast<ConstantArray>(GV.getInitializer()); 63 // If values are not pointers, do not generate a relative lookup table. 64 if (!Array || !Array->getType()->getElementType()->isPointerTy()) 65 return false; 66 67 const DataLayout &DL = M.getDataLayout(); 68 for (const Use &Op : Array->operands()) { 69 Constant *ConstOp = cast<Constant>(&Op); 70 GlobalValue *GVOp; 71 APInt Offset; 72 73 // If an operand is not a constant offset from a lookup table, 74 // do not generate a relative lookup table. 75 if (!IsConstantOffsetFromGlobal(ConstOp, GVOp, Offset, DL)) 76 return false; 77 78 // If operand is mutable, do not generate a relative lookup table. 79 auto *GlovalVarOp = dyn_cast<GlobalVariable>(GVOp); 80 if (!GlovalVarOp || !GlovalVarOp->isConstant()) 81 return false; 82 83 if (!GlovalVarOp->hasLocalLinkage() || 84 !GlovalVarOp->isDSOLocal() || 85 !GlovalVarOp->isImplicitDSOLocal()) 86 return false; 87 } 88 89 return true; 90 } 91 92 static GlobalVariable *createRelLookupTable(Function &Func, 93 GlobalVariable &LookupTable) { 94 Module &M = *Func.getParent(); 95 ConstantArray *LookupTableArr = 96 cast<ConstantArray>(LookupTable.getInitializer()); 97 unsigned NumElts = LookupTableArr->getType()->getNumElements(); 98 ArrayType *IntArrayTy = 99 ArrayType::get(Type::getInt32Ty(M.getContext()), NumElts); 100 101 GlobalVariable *RelLookupTable = new GlobalVariable( 102 M, IntArrayTy, LookupTable.isConstant(), LookupTable.getLinkage(), 103 nullptr, "reltable." + Func.getName(), &LookupTable, 104 LookupTable.getThreadLocalMode(), LookupTable.getAddressSpace(), 105 LookupTable.isExternallyInitialized()); 106 107 uint64_t Idx = 0; 108 SmallVector<Constant *, 64> RelLookupTableContents(NumElts); 109 110 for (Use &Operand : LookupTableArr->operands()) { 111 Constant *Element = cast<Constant>(Operand); 112 Type *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext()); 113 Constant *Base = llvm::ConstantExpr::getPtrToInt(RelLookupTable, IntPtrTy); 114 Constant *Target = llvm::ConstantExpr::getPtrToInt(Element, IntPtrTy); 115 Constant *Sub = llvm::ConstantExpr::getSub(Target, Base); 116 Constant *RelOffset = 117 llvm::ConstantExpr::getTrunc(Sub, Type::getInt32Ty(M.getContext())); 118 RelLookupTableContents[Idx++] = RelOffset; 119 } 120 121 Constant *Initializer = 122 ConstantArray::get(IntArrayTy, RelLookupTableContents); 123 RelLookupTable->setInitializer(Initializer); 124 RelLookupTable->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); 125 RelLookupTable->setAlignment(llvm::Align(4)); 126 return RelLookupTable; 127 } 128 129 static void convertToRelLookupTable(GlobalVariable &LookupTable) { 130 GetElementPtrInst *GEP = 131 cast<GetElementPtrInst>(LookupTable.use_begin()->getUser()); 132 LoadInst *Load = cast<LoadInst>(GEP->use_begin()->getUser()); 133 134 Module &M = *LookupTable.getParent(); 135 BasicBlock *BB = GEP->getParent(); 136 IRBuilder<> Builder(BB); 137 Function &Func = *BB->getParent(); 138 139 // Generate an array that consists of relative offsets. 140 GlobalVariable *RelLookupTable = createRelLookupTable(Func, LookupTable); 141 142 // Place new instruction sequence before GEP. 143 Builder.SetInsertPoint(GEP); 144 Value *Index = GEP->getOperand(2); 145 IntegerType *IntTy = cast<IntegerType>(Index->getType()); 146 Value *Offset = 147 Builder.CreateShl(Index, ConstantInt::get(IntTy, 2), "reltable.shift"); 148 149 // Insert the call to load.relative instrinsic before LOAD. 150 // GEP might not be immediately followed by a LOAD, like it can be hoisted 151 // outside the loop or another instruction might be inserted them in between. 152 Builder.SetInsertPoint(Load); 153 Function *LoadRelIntrinsic = llvm::Intrinsic::getDeclaration( 154 &M, Intrinsic::load_relative, {Index->getType()}); 155 Value *Base = Builder.CreateBitCast(RelLookupTable, Builder.getInt8PtrTy()); 156 157 // Create a call to load.relative intrinsic that computes the target address 158 // by adding base address (lookup table address) and relative offset. 159 Value *Result = Builder.CreateCall(LoadRelIntrinsic, {Base, Offset}, 160 "reltable.intrinsic"); 161 162 // Create a bitcast instruction if necessary. 163 if (Load->getType() != Builder.getInt8PtrTy()) 164 Result = Builder.CreateBitCast(Result, Load->getType(), "reltable.bitcast"); 165 166 // Replace load instruction with the new generated instruction sequence. 167 Load->replaceAllUsesWith(Result); 168 // Remove Load and GEP instructions. 169 Load->eraseFromParent(); 170 GEP->eraseFromParent(); 171 } 172 173 // Convert lookup tables to relative lookup tables in the module. 174 static bool convertToRelativeLookupTables( 175 Module &M, function_ref<TargetTransformInfo &(Function &)> GetTTI) { 176 Module::iterator FI = M.begin(); 177 if (FI == M.end()) 178 return false; 179 180 // Check if we have a target that supports relative lookup tables. 181 if (!GetTTI(*FI).shouldBuildRelLookupTables()) 182 return false; 183 184 bool Changed = false; 185 186 for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) { 187 if (!shouldConvertToRelLookupTable(M, GV)) 188 continue; 189 190 convertToRelLookupTable(GV); 191 192 // Remove the original lookup table. 193 GV.eraseFromParent(); 194 195 Changed = true; 196 } 197 198 return Changed; 199 } 200 201 PreservedAnalyses RelLookupTableConverterPass::run(Module &M, 202 ModuleAnalysisManager &AM) { 203 FunctionAnalysisManager &FAM = 204 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 205 206 auto GetTTI = [&](Function &F) -> TargetTransformInfo & { 207 return FAM.getResult<TargetIRAnalysis>(F); 208 }; 209 210 if (!convertToRelativeLookupTables(M, GetTTI)) 211 return PreservedAnalyses::all(); 212 213 PreservedAnalyses PA; 214 PA.preserveSet<CFGAnalyses>(); 215 return PA; 216 } 217