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
22using namespace llvm;
23
24static 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>(Val: GV.use_begin()->getUser());
38 if (!GEP || !GEP->hasOneUse() ||
39 GV.getValueType() != GEP->getSourceElementType())
40 return false;
41
42 LoadInst *Load = dyn_cast<LoadInst>(Val: 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>(Val: 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>(Val: &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(C: ConstOp, GV&: 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>(Val: 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(Elt: GlovalVarOp);
105 }
106
107 if (ShouldDropUnnamedAddr)
108 for (auto *GVOp : GVOps)
109 GVOp->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
110
111 return true;
112}
113
114static GlobalVariable *createRelLookupTable(Function &Func,
115 GlobalVariable &LookupTable) {
116 Module &M = *Func.getParent();
117 ConstantArray *LookupTableArr =
118 cast<ConstantArray>(Val: LookupTable.getInitializer());
119 unsigned NumElts = LookupTableArr->getType()->getNumElements();
120 ArrayType *IntArrayTy =
121 ArrayType::get(ElementType: Type::getInt32Ty(C&: M.getContext()), NumElements: 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>(Val&: Operand);
134 Type *IntPtrTy = M.getDataLayout().getIntPtrType(C&: M.getContext());
135 Constant *Base = llvm::ConstantExpr::getPtrToInt(C: RelLookupTable, Ty: IntPtrTy);
136 Constant *Target = llvm::ConstantExpr::getPtrToInt(C: Element, Ty: IntPtrTy);
137 Constant *Sub = llvm::ConstantExpr::getSub(C1: Target, C2: Base);
138 Constant *RelOffset =
139 llvm::ConstantExpr::getTrunc(C: Sub, Ty: Type::getInt32Ty(C&: M.getContext()));
140 RelLookupTableContents[Idx++] = RelOffset;
141 }
142
143 Constant *Initializer =
144 ConstantArray::get(T: IntArrayTy, V: RelLookupTableContents);
145 RelLookupTable->setInitializer(Initializer);
146 RelLookupTable->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
147 RelLookupTable->setAlignment(llvm::Align(4));
148 return RelLookupTable;
149}
150
151static void convertToRelLookupTable(GlobalVariable &LookupTable) {
152 GetElementPtrInst *GEP =
153 cast<GetElementPtrInst>(Val: LookupTable.use_begin()->getUser());
154 LoadInst *Load = cast<LoadInst>(Val: 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(i_nocapture: 2);
167 IntegerType *IntTy = cast<IntegerType>(Val: Index->getType());
168 Value *Offset =
169 Builder.CreateShl(LHS: Index, RHS: ConstantInt::get(Ty: IntTy, V: 2), Name: "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: &M, id: Intrinsic::load_relative, Tys: {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(Callee: LoadRelIntrinsic, Args: {RelLookupTable, Offset},
181 Name: "reltable.intrinsic");
182
183 // Replace load instruction with the new generated instruction sequence.
184 Load->replaceAllUsesWith(V: 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.
191static 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(Range: M.globals())) {
208 if (!shouldConvertToRelLookupTable(M, GV))
209 continue;
210
211 convertToRelLookupTable(LookupTable&: GV);
212
213 // Remove the original lookup table.
214 GV.eraseFromParent();
215
216 Changed = true;
217 }
218
219 return Changed;
220}
221
222PreservedAnalyses RelLookupTableConverterPass::run(Module &M,
223 ModuleAnalysisManager &AM) {
224 FunctionAnalysisManager &FAM =
225 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
226
227 auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
228 return FAM.getResult<TargetIRAnalysis>(IR&: 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