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