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