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 (!GV.hasInitializer())
29     return false;
30 
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   if (!GV.hasOneUse())
38     return false;
39 
40   GetElementPtrInst *GEP =
41       dyn_cast<GetElementPtrInst>(GV.use_begin()->getUser());
42   if (!GEP || !GEP->hasOneUse())
43     return false;
44 
45   if (!isa<LoadInst>(GEP->use_begin()->getUser()))
46     return false;
47 
48   // If the original lookup table is not dso_local,
49   // 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
53   // and its elements should be dso_local, which means that they should
54   // resolve to symbols within the same linkage unit.
55   if (!GV.isDSOLocal())
56     return false;
57 
58   if (!GV.isImplicitDSOLocal())
59     return false;
60 
61   ConstantArray *Array = dyn_cast<ConstantArray>(GV.getInitializer());
62   // If values are not pointers, do not generate a relative lookup table.
63   if (!Array || !Array->getType()->getElementType()->isPointerTy())
64     return false;
65 
66   const DataLayout &DL = M.getDataLayout();
67   for (const Use &Op : Array->operands()) {
68     Constant *ConstOp = cast<Constant>(&Op);
69     GlobalValue *GVOp;
70     APInt Offset;
71 
72     // If an operand is not a constant offset from a lookup table,
73     // do not generate a relative lookup table.
74     if (!IsConstantOffsetFromGlobal(ConstOp, GVOp, Offset, DL))
75       return false;
76 
77     // If an operand in the lookup table is not dso_local,
78     // do not generate a relative lookup table.
79     if (!GVOp->isDSOLocal())
80       return false;
81 
82     if (!GVOp->isImplicitDSOLocal())
83       return false;
84   }
85 
86   return true;
87 }
88 
89 static GlobalVariable *createRelLookupTable(Function &Func,
90                                             GlobalVariable &LookupTable) {
91   Module &M = *Func.getParent();
92   ConstantArray *LookupTableArr =
93       cast<ConstantArray>(LookupTable.getInitializer());
94   unsigned NumElts = LookupTableArr->getType()->getNumElements();
95   ArrayType *IntArrayTy =
96       ArrayType::get(Type::getInt32Ty(M.getContext()), NumElts);
97 
98   GlobalVariable *RelLookupTable = new GlobalVariable(
99     M, IntArrayTy, LookupTable.isConstant(), LookupTable.getLinkage(),
100     nullptr, "reltable." + Func.getName(), &LookupTable,
101     LookupTable.getThreadLocalMode(), LookupTable.getAddressSpace(),
102     LookupTable.isExternallyInitialized());
103 
104   RelLookupTable->copyAttributesFrom(&LookupTable);
105   RelLookupTable->copyMetadata(&LookupTable, 0);
106 
107   uint64_t Idx = 0;
108   SmallVector<Constant *, 64> RelLookupTableContents(NumElts);
109 
110   for (Use &Operand : LookupTableArr->operands()) {
111     Constant *Element = cast<Constant>(Operand);
112     Type *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext());
113     Constant *Base = llvm::ConstantExpr::getPtrToInt(RelLookupTable, IntPtrTy);
114     Constant *Target = llvm::ConstantExpr::getPtrToInt(Element, IntPtrTy);
115     Constant *Sub = llvm::ConstantExpr::getSub(Target, Base);
116     Constant *RelOffset =
117         llvm::ConstantExpr::getTrunc(Sub, Type::getInt32Ty(M.getContext()));
118     RelLookupTableContents[Idx++] = RelOffset;
119   }
120 
121   Constant *Initializer =
122       ConstantArray::get(IntArrayTy, RelLookupTableContents);
123   RelLookupTable->setInitializer(Initializer);
124   RelLookupTable->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
125   RelLookupTable->setAlignment(llvm::Align(4));
126   return RelLookupTable;
127 }
128 
129 static void convertToRelLookupTable(GlobalVariable &LookupTable) {
130   GetElementPtrInst *GEP =
131       cast<GetElementPtrInst>(LookupTable.use_begin()->getUser());
132   LoadInst *Load = cast<LoadInst>(GEP->use_begin()->getUser());
133 
134   Module &M = *LookupTable.getParent();
135   BasicBlock *BB = GEP->getParent();
136   IRBuilder<> Builder(BB);
137   Function &Func = *BB->getParent();
138 
139   // Generate an array that consists of relative offsets.
140   GlobalVariable *RelLookupTable = createRelLookupTable(Func, LookupTable);
141 
142   // Place new instruction sequence after GEP.
143   Builder.SetInsertPoint(GEP);
144   Value *Index = GEP->getOperand(2);
145   IntegerType *IntTy = cast<IntegerType>(Index->getType());
146   Value *Offset =
147       Builder.CreateShl(Index, ConstantInt::get(IntTy, 2), "reltable.shift");
148 
149   Function *LoadRelIntrinsic = llvm::Intrinsic::getDeclaration(
150       &M, Intrinsic::load_relative, {Index->getType()});
151   Value *Base = Builder.CreateBitCast(RelLookupTable, Builder.getInt8PtrTy());
152 
153   // Create a call to load.relative intrinsic that computes the target address
154   // by adding base address (lookup table address) and relative offset.
155   Value *Result = Builder.CreateCall(LoadRelIntrinsic, {Base, Offset},
156                                      "reltable.intrinsic");
157 
158   // Create a bitcast instruction if necessary.
159   if (Load->getType() != Builder.getInt8PtrTy())
160     Result = Builder.CreateBitCast(Result, Load->getType(), "reltable.bitcast");
161 
162   // Replace load instruction with the new generated instruction sequence.
163   BasicBlock::iterator InsertPoint(Load);
164   ReplaceInstWithValue(Load->getParent()->getInstList(), InsertPoint, Result);
165 
166   // Remove GEP instruction.
167   GEP->eraseFromParent();
168 }
169 
170 // Convert lookup tables to relative lookup tables in the module.
171 static bool convertToRelativeLookupTables(
172     Module &M, function_ref<TargetTransformInfo &(Function &)> GetTTI) {
173   Module::iterator FI = M.begin();
174   if (FI == M.end())
175     return false;
176 
177   // Check if we have a target that supports relative lookup tables.
178   if (!GetTTI(*FI).shouldBuildRelLookupTables())
179     return false;
180 
181   bool Changed = false;
182 
183   for (auto GVI = M.global_begin(), E = M.global_end(); GVI != E;) {
184     GlobalVariable &GlobalVar = *GVI++;
185 
186     if (!shouldConvertToRelLookupTable(M, GlobalVar))
187       continue;
188 
189     convertToRelLookupTable(GlobalVar);
190 
191     // Remove the original lookup table.
192     GlobalVar.eraseFromParent();
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 
216 namespace {
217 
218 /// Pass that converts lookup tables to relative lookup tables.
219 class RelLookupTableConverterLegacyPass : public ModulePass {
220 
221 public:
222   /// Pass identification, replacement for typeid
223   static char ID;
224 
225   /// Specify pass name for debug output
226   StringRef getPassName() const override {
227     return "Relative Lookup Table Converter";
228   }
229 
230   RelLookupTableConverterLegacyPass() : ModulePass(ID) {
231     initializeRelLookupTableConverterLegacyPassPass(
232         *PassRegistry::getPassRegistry());
233   }
234 
235   bool runOnModule(Module &M) override {
236     auto GetTTI = [this](Function &F) -> TargetTransformInfo & {
237       return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
238     };
239     return convertToRelativeLookupTables(M, GetTTI);
240   }
241 
242   void getAnalysisUsage(AnalysisUsage &AU) const override {
243     AU.addRequired<TargetTransformInfoWrapperPass>();
244   }
245 };
246 
247 } // anonymous namespace
248 
249 char RelLookupTableConverterLegacyPass::ID = 0;
250 
251 INITIALIZE_PASS_BEGIN(RelLookupTableConverterLegacyPass,
252                       "rel-lookup-table-converter",
253                       "Convert to relative lookup tables", false, false)
254 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
255 INITIALIZE_PASS_END(RelLookupTableConverterLegacyPass,
256                     "rel-lookup-table-converter",
257                     "Convert to relative lookup tables", false, false)
258 
259 namespace llvm {
260 ModulePass *createRelLookupTableConverterPass() {
261   return new RelLookupTableConverterLegacyPass();
262 }
263 } // end namespace llvm
264