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
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 gets
36 // inlined into multiple call sites.
37 //
38 // If the original lookup table does not have local linkage and is
39 // not dso_local, do not generate a relative lookup table.
40 // This optimization creates a relative lookup table that consists of
41 // offsets between the start of the lookup table and its elements.
42 // To be able to generate these offsets, relative lookup table and
43 // its elements should have internal linkage and be dso_local, which means
44 // 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>(Val: GV.use_begin()->getUser());
50 if (!GEP || !GEP->hasOneUse())
51 return false;
52
53 auto *Load = dyn_cast<LoadInst>(Val: GEP->use_begin()->getUser());
54 if (!Load || Load->isVolatile())
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 = DL.getIndexTypeSizeInBits(Ty: GEP->getType());
65 SmallMapVector<Value *, APInt, 4> VarOffsets;
66 APInt ConstOffset(IndexWidth, 0);
67 if (!GEP->collectOffset(DL, BitWidth: IndexWidth, VariableOffsets&: VarOffsets, ConstantOffset&: ConstOffset) ||
68 !ConstOffset.isZero() || VarOffsets.size() != 1)
69 return false;
70
71 // This can't be a pointer lookup table if the stride is smaller than a
72 // pointer.
73 Info.Index = VarOffsets.front().first;
74 const APInt &Stride = VarOffsets.front().second;
75 if (Stride.ult(RHS: DL.getTypeStoreSize(Ty: ElemType)))
76 return false;
77
78 SmallVector<GlobalVariable *, 4> GVOps;
79 Triple TT = M.getTargetTriple();
80 // FIXME: This should be removed in the future.
81 bool ShouldDropUnnamedAddr =
82 // Drop unnamed_addr to avoid matching pattern in
83 // `handleIndirectSymViaGOTPCRel`, which generates GOTPCREL relocations
84 // not supported by the GNU linker and LLD versions below 18 on aarch64.
85 TT.isAArch64()
86 // Apple's ld64 (and ld-prime on Xcode 15.2) miscompile something on
87 // x86_64-apple-darwin. See
88 // https://github.com/rust-lang/rust/issues/140686 and
89 // https://github.com/rust-lang/rust/issues/141306.
90 || (TT.isX86() && TT.isOSDarwin());
91
92 APInt Offset(IndexWidth, 0);
93 uint64_t GVSize = GV.getGlobalSize(DL);
94 bool HasNonPoison = false;
95 for (; Offset.ult(RHS: GVSize); Offset += Stride) {
96 Constant *C =
97 ConstantFoldLoadFromConst(C: GV.getInitializer(), Ty: ElemType, Offset, DL);
98 if (!C)
99 return false;
100
101 if (isa<PoisonValue>(Val: C)) {
102 Info.Ptrs.push_back(Elt: C);
103 continue;
104 }
105
106 GlobalValue *GVOp;
107 APInt GVOffset;
108
109 // If an operand is not a constant offset from a lookup table,
110 // do not generate a relative lookup table.
111 if (!IsConstantOffsetFromGlobal(C, GV&: GVOp, Offset&: GVOffset, DL))
112 return false;
113
114 // If operand is mutable, do not generate a relative lookup table.
115 auto *GlobalVarOp = dyn_cast<GlobalVariable>(Val: GVOp);
116 if (!GlobalVarOp || !GlobalVarOp->isConstant())
117 return false;
118
119 // FIXME: This excludes declarations because the MachO writer rejects them
120 // on x86. They should be fine on ELF at least.
121 if (!GlobalVarOp->isStrongDefinitionForLinker() ||
122 !GlobalVarOp->isImplicitDSOLocal())
123 return false;
124
125 // On AArch64 small code model, the text-to-data span can be up to 4GB,
126 // which exceeds 32-bit signed relative offsets. Avoid converting if the
127 // target operand requires dynamic relocations (placing it in .data.rel.ro
128 // in the data segment rather than .rodata in the text segment).
129 if (TT.isAArch64() &&
130 (!GlobalVarOp->hasInitializer() ||
131 GlobalVarOp->getInitializer()->needsDynamicRelocation()))
132 return false;
133
134 if (ShouldDropUnnamedAddr)
135 GVOps.push_back(Elt: GlobalVarOp);
136
137 HasNonPoison = true;
138 Info.Ptrs.push_back(Elt: C);
139 }
140
141 if (!HasNonPoison)
142 return false;
143
144 if (ShouldDropUnnamedAddr)
145 for (auto *GVOp : GVOps)
146 GVOp->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
147
148 return true;
149}
150
151static GlobalVariable *createRelLookupTable(LookupTableInfo &Info,
152 GlobalVariable &LookupTable) {
153 Module &M = *LookupTable.getParent();
154 ArrayType *IntArrayTy =
155 ArrayType::get(ElementType: Type::getInt32Ty(C&: M.getContext()), NumElements: Info.Ptrs.size());
156
157 GlobalVariable *RelLookupTable = new GlobalVariable(
158 M, IntArrayTy, LookupTable.isConstant(), LookupTable.getLinkage(),
159 nullptr, LookupTable.getName() + ".rel", &LookupTable,
160 LookupTable.getThreadLocalMode(), LookupTable.getAddressSpace(),
161 LookupTable.isExternallyInitialized());
162
163 Type *IntPtrTy = M.getDataLayout().getIntPtrType(C&: M.getContext());
164 Type *Int32Ty = Type::getInt32Ty(C&: M.getContext());
165 Constant *Base = ConstantExpr::getPtrToInt(C: RelLookupTable, Ty: IntPtrTy);
166
167 uint64_t Idx = 0;
168 SmallVector<Constant *, 64> RelLookupTableContents(Info.Ptrs.size());
169
170 for (Constant *Element : Info.Ptrs) {
171 if (isa<PoisonValue>(Val: Element)) {
172 RelLookupTableContents[Idx++] = PoisonValue::get(T: Int32Ty);
173 continue;
174 }
175
176 Constant *Target = ConstantExpr::getPtrToInt(C: Element, Ty: IntPtrTy);
177 Constant *Sub = ConstantExpr::getSub(C1: Target, C2: Base);
178 Constant *RelOffset = ConstantExpr::getTrunc(C: Sub, Ty: Int32Ty);
179 RelLookupTableContents[Idx++] = RelOffset;
180 }
181
182 Constant *Initializer =
183 ConstantArray::get(T: IntArrayTy, V: RelLookupTableContents);
184 RelLookupTable->setInitializer(Initializer);
185 RelLookupTable->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
186 RelLookupTable->setAlignment(llvm::Align(4));
187 return RelLookupTable;
188}
189
190static void convertToRelLookupTable(LookupTableInfo &Info,
191 GlobalVariable &LookupTable) {
192 GetElementPtrInst *GEP =
193 cast<GetElementPtrInst>(Val: LookupTable.use_begin()->getUser());
194 LoadInst *Load = cast<LoadInst>(Val: GEP->use_begin()->getUser());
195
196 Module &M = *LookupTable.getParent();
197 BasicBlock *BB = GEP->getParent();
198 IRBuilder<> Builder(BB);
199
200 // Generate an array that consists of relative offsets.
201 GlobalVariable *RelLookupTable =
202 createRelLookupTable(Info, LookupTable);
203
204 // Place new instruction sequence before GEP.
205 Builder.SetInsertPoint(GEP);
206 IntegerType *IntTy = cast<IntegerType>(Val: Info.Index->getType());
207 Value *Offset = Builder.CreateShl(LHS: Info.Index, RHS: ConstantInt::get(Ty: IntTy, V: 2),
208 Name: "reltable.shift");
209
210 // Insert the call to load.relative intrinsic before LOAD.
211 // GEP might not be immediately followed by a LOAD, like it can be hoisted
212 // outside the loop or another instruction might be inserted them in between.
213 Builder.SetInsertPoint(Load);
214 Function *LoadRelIntrinsic = llvm::Intrinsic::getOrInsertDeclaration(
215 M: &M, id: Intrinsic::load_relative, OverloadTys: {Info.Index->getType()});
216
217 // Create a call to load.relative intrinsic that computes the target address
218 // by adding base address (lookup table address) and relative offset.
219 Value *Result = Builder.CreateCall(Callee: LoadRelIntrinsic, Args: {RelLookupTable, Offset},
220 Name: "reltable.intrinsic");
221
222 // Replace load instruction with the new generated instruction sequence.
223 Load->replaceAllUsesWith(V: Result);
224 // Remove Load and GEP instructions.
225 Load->eraseFromParent();
226 GEP->eraseFromParent();
227}
228
229// Convert lookup tables to relative lookup tables in the module.
230static bool convertToRelativeLookupTables(
231 Module &M, function_ref<TargetTransformInfo &(Function &)> GetTTI) {
232 for (Function &F : M) {
233 if (F.isDeclaration())
234 continue;
235
236 // Check if we have a target that supports relative lookup tables.
237 if (!GetTTI(F).shouldBuildRelLookupTables())
238 return false;
239
240 // We assume that the result is independent of the checked function.
241 break;
242 }
243
244 bool Changed = false;
245
246 for (GlobalVariable &GV : llvm::make_early_inc_range(Range: M.globals())) {
247 LookupTableInfo Info;
248 if (!shouldConvertToRelLookupTable(Info, M, GV))
249 continue;
250
251 convertToRelLookupTable(Info, LookupTable&: GV);
252
253 // Remove the original lookup table.
254 GV.eraseFromParent();
255
256 Changed = true;
257 }
258
259 return Changed;
260}
261
262PreservedAnalyses RelLookupTableConverterPass::run(Module &M,
263 ModuleAnalysisManager &AM) {
264 FunctionAnalysisManager &FAM =
265 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
266
267 auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
268 return FAM.getResult<TargetIRAnalysis>(IR&: F);
269 };
270
271 if (!convertToRelativeLookupTables(M, GetTTI))
272 return PreservedAnalyses::all();
273
274 PreservedAnalyses PA;
275 PA.preserveSet<CFGAnalyses>();
276 return PA;
277}
278