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
  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 }