llvm/lib/Transforms/Utils/RelLookupTableConverter.cpp

   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 lookup table has more than one user,
  29   // do not generate a relative lookup table.
  30   // This is to simplify the analysis that needs to be done for this pass.
  31   // TODO: Add support for lookup tables with multiple uses.
  32   // For ex, this can happen when a function that uses a lookup table gets
  33   // inlined into multiple call sites.
  34   if (!GV.hasInitializer() ||
  35       !GV.isConstant() ||
  36       !GV.hasOneUse())
  37     return false;
  38
  39   GetElementPtrInst *GEP =
  40       dyn_cast<GetElementPtrInst>(GV.use_begin()->getUser());
  41   if (!GEP || !GEP->hasOneUse())
  42     return false;
  43
  44   LoadInst *Load = dyn_cast<LoadInst>(GEP->use_begin()->getUser());
  45   if (!Load || !Load->hasOneUse())
  46     return false;
  47
  48   // If the original lookup table does not have local linkage and is
  49   // not dso_local, 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 and
  53   // its elements should have internal linkage and be dso_local, which means
  54   // that they should resolve to symbols within the same linkage unit.
  55   if (!GV.hasLocalLinkage() ||
  56       !GV.isDSOLocal() ||
  57       !GV.isImplicitDSOLocal())
  58     return false;
  59
  60   ConstantArray *Array = dyn_cast<ConstantArray>(GV.getInitializer());
  61   // If values are not pointers, do not generate a relative lookup table.
  62   if (!Array || !Array->getType()->getElementType()->isPointerTy())
  63     return false;
  64
  65   const DataLayout &DL = M.getDataLayout();
  66   for (const Use &Op : Array->operands()) {
  67     Constant *ConstOp = cast<Constant>(&Op);
  68     GlobalValue *GVOp;
  69     APInt Offset;
  70
  71     // If an operand is not a constant offset from a lookup table,
  72     // do not generate a relative lookup table.
  73     if (!IsConstantOffsetFromGlobal(ConstOp, GVOp, Offset, DL))
  74       return false;
  75
  76     // If operand is mutable, do not generate a relative lookup table.
  77     auto *GlovalVarOp = dyn_cast<GlobalVariable>(GVOp);
  78     if (!GlovalVarOp || !GlovalVarOp->isConstant())
  79       return false;
  80
  81     if (!GlovalVarOp->hasLocalLinkage() ||
  82         !GlovalVarOp->isDSOLocal() ||
  83         !GlovalVarOp->isImplicitDSOLocal())
  84       return false;
  85   }
  86
  87   return true;
  88 }
  89
  90 static GlobalVariable *createRelLookupTable(Function &Func,
  91                                             GlobalVariable &LookupTable) {
  92   Module &M = *Func.getParent();
  93   ConstantArray *LookupTableArr =
  94       cast<ConstantArray>(LookupTable.getInitializer());
  95   unsigned NumElts = LookupTableArr->getType()->getNumElements();
  96   ArrayType *IntArrayTy =
  97       ArrayType::get(Type::getInt32Ty(M.getContext()), NumElts);
  98
  99   GlobalVariable *RelLookupTable = new GlobalVariable(
 100     M, IntArrayTy, LookupTable.isConstant(), LookupTable.getLinkage(),
 101     nullptr, "reltable." + Func.getName(), &LookupTable,
 102     LookupTable.getThreadLocalMode(), LookupTable.getAddressSpace(),
 103     LookupTable.isExternallyInitialized());
 104
 105   uint64_t Idx = 0;
 106   SmallVector<Constant *, 64> RelLookupTableContents(NumElts);
 107
 108   for (Use &Operand : LookupTableArr->operands()) {
 109     Constant *Element = cast<Constant>(Operand);
 110     Type *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext());
 111     Constant *Base = llvm::ConstantExpr::getPtrToInt(RelLookupTable, IntPtrTy);
 112     Constant *Target = llvm::ConstantExpr::getPtrToInt(Element, IntPtrTy);
 113     Constant *Sub = llvm::ConstantExpr::getSub(Target, Base);
 114     Constant *RelOffset =
 115         llvm::ConstantExpr::getTrunc(Sub, Type::getInt32Ty(M.getContext()));
 116     RelLookupTableContents[Idx++] = RelOffset;
 117   }
 118
 119   Constant *Initializer =
 120       ConstantArray::get(IntArrayTy, RelLookupTableContents);
 121   RelLookupTable->setInitializer(Initializer);
 122   RelLookupTable->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
 123   RelLookupTable->setAlignment(llvm::Align(4));
 124   return RelLookupTable;
 125 }
 126
 127 static void convertToRelLookupTable(GlobalVariable &LookupTable) {
 128   GetElementPtrInst *GEP =
 129       cast<GetElementPtrInst>(LookupTable.use_begin()->getUser());
 130   LoadInst *Load = cast<LoadInst>(GEP->use_begin()->getUser());
 131
 132   Module &M = *LookupTable.getParent();
 133   BasicBlock *BB = GEP->getParent();
 134   IRBuilder<> Builder(BB);
 135   Function &Func = *BB->getParent();
 136
 137   // Generate an array that consists of relative offsets.
 138   GlobalVariable *RelLookupTable = createRelLookupTable(Func, LookupTable);
 139
 140   // Place new instruction sequence before GEP.
 141   Builder.SetInsertPoint(GEP);
 142   Value *Index = GEP->getOperand(2);
 143   IntegerType *IntTy = cast<IntegerType>(Index->getType());
 144   Value *Offset =
 145       Builder.CreateShl(Index, ConstantInt::get(IntTy, 2), "reltable.shift");
 146
 147   Function *LoadRelIntrinsic = llvm::Intrinsic::getDeclaration(
 148       &M, Intrinsic::load_relative, {Index->getType()});
 149   Value *Base = Builder.CreateBitCast(RelLookupTable, Builder.getInt8PtrTy());
 150
 151   // Create a call to load.relative intrinsic that computes the target address
 152   // by adding base address (lookup table address) and relative offset.
 153   Value *Result = Builder.CreateCall(LoadRelIntrinsic, {Base, Offset},
 154                                      "reltable.intrinsic");
 155
 156   // Create a bitcast instruction if necessary.
 157   if (Load->getType() != Builder.getInt8PtrTy())
 158     Result = Builder.CreateBitCast(Result, Load->getType(), "reltable.bitcast");
 159
 160   // Replace load instruction with the new generated instruction sequence.
 161   Load->replaceAllUsesWith(Result);
 162   // Remove Load and GEP instructions.
 163   Load->eraseFromParent();
 164   GEP->eraseFromParent();
 165 }
 166
 167 // Convert lookup tables to relative lookup tables in the module.
 168 static bool convertToRelativeLookupTables(
 169     Module &M, function_ref<TargetTransformInfo &(Function &)> GetTTI) {
 170   Module::iterator FI = M.begin();
 171   if (FI == M.end())
 172     return false;
 173
 174   // Check if we have a target that supports relative lookup tables.
 175   if (!GetTTI(*FI).shouldBuildRelLookupTables())
 176     return false;
 177
 178   bool Changed = false;
 179
 180   for (auto GVI = M.global_begin(), E = M.global_end(); GVI != E;) {
 181     GlobalVariable &GV = *GVI++;
 182
 183     if (!shouldConvertToRelLookupTable(M, GV))
 184       continue;
 185
 186     convertToRelLookupTable(GV);
 187
 188     // Remove the original lookup table.
 189     GV.eraseFromParent();
 190
 191     Changed = true;
 192   }
 193
 194   return Changed;
 195 }
 196
 197 PreservedAnalyses RelLookupTableConverterPass::run(Module &M,
 198                                                    ModuleAnalysisManager &AM) {
 199   FunctionAnalysisManager &FAM =
 200       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 201
 202   auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
 203     return FAM.getResult<TargetIRAnalysis>(F);
 204   };
 205
 206   if (!convertToRelativeLookupTables(M, GetTTI))
 207     return PreservedAnalyses::all();
 208
 209   PreservedAnalyses PA;
 210   PA.preserveSet<CFGAnalyses>();
 211   return PA;
 212 }