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