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