blob: 3ebc89158173d0b10d0abf038d5c1e9d6b50ca8a [file] [log] [blame]
//===- RelLookupTableConverterPass - Rel Table Conv -----------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements relative lookup table converter that converts
// lookup tables to relative lookup tables to make them PIC-friendly.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Utils/RelLookupTableConverter.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
using namespace llvm;
static bool shouldConvertToRelLookupTable(Module &M, GlobalVariable &GV) {
// If lookup table has more than one user,
// do not generate a relative lookup table.
// This is to simplify the analysis that needs to be done for this pass.
// TODO: Add support for lookup tables with multiple uses.
// For ex, this can happen when a function that uses a lookup table gets
// inlined into multiple call sites.
if (!GV.hasInitializer() ||
!GV.isConstant() ||
!GV.hasOneUse())
return false;
GetElementPtrInst *GEP =
dyn_cast<GetElementPtrInst>(GV.use_begin()->getUser());
if (!GEP || !GEP->hasOneUse())
return false;
LoadInst *Load = dyn_cast<LoadInst>(GEP->use_begin()->getUser());
if (!Load || !Load->hasOneUse())
return false;
// If the original lookup table does not have local linkage and is
// not dso_local, do not generate a relative lookup table.
// This optimization creates a relative lookup table that consists of
// offsets between the start of the lookup table and its elements.
// To be able to generate these offsets, relative lookup table and
// its elements should have internal linkage and be dso_local, which means
// that they should resolve to symbols within the same linkage unit.
if (!GV.hasLocalLinkage() ||
!GV.isDSOLocal() ||
!GV.isImplicitDSOLocal())
return false;
ConstantArray *Array = dyn_cast<ConstantArray>(GV.getInitializer());
// If values are not pointers, do not generate a relative lookup table.
if (!Array || !Array->getType()->getElementType()->isPointerTy())
return false;
const DataLayout &DL = M.getDataLayout();
for (const Use &Op : Array->operands()) {
Constant *ConstOp = cast<Constant>(&Op);
GlobalValue *GVOp;
APInt Offset;
// If an operand is not a constant offset from a lookup table,
// do not generate a relative lookup table.
if (!IsConstantOffsetFromGlobal(ConstOp, GVOp, Offset, DL))
return false;
// If operand is mutable, do not generate a relative lookup table.
auto *GlovalVarOp = dyn_cast<GlobalVariable>(GVOp);
if (!GlovalVarOp || !GlovalVarOp->isConstant())
return false;
if (!GlovalVarOp->hasLocalLinkage() ||
!GlovalVarOp->isDSOLocal() ||
!GlovalVarOp->isImplicitDSOLocal())
return false;
}
return true;
}
static GlobalVariable *createRelLookupTable(Function &Func,
GlobalVariable &LookupTable) {
Module &M = *Func.getParent();
ConstantArray *LookupTableArr =
cast<ConstantArray>(LookupTable.getInitializer());
unsigned NumElts = LookupTableArr->getType()->getNumElements();
ArrayType *IntArrayTy =
ArrayType::get(Type::getInt32Ty(M.getContext()), NumElts);
GlobalVariable *RelLookupTable = new GlobalVariable(
M, IntArrayTy, LookupTable.isConstant(), LookupTable.getLinkage(),
nullptr, "reltable." + Func.getName(), &LookupTable,
LookupTable.getThreadLocalMode(), LookupTable.getAddressSpace(),
LookupTable.isExternallyInitialized());
uint64_t Idx = 0;
SmallVector<Constant *, 64> RelLookupTableContents(NumElts);
for (Use &Operand : LookupTableArr->operands()) {
Constant *Element = cast<Constant>(Operand);
Type *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext());
Constant *Base = llvm::ConstantExpr::getPtrToInt(RelLookupTable, IntPtrTy);
Constant *Target = llvm::ConstantExpr::getPtrToInt(Element, IntPtrTy);
Constant *Sub = llvm::ConstantExpr::getSub(Target, Base);
Constant *RelOffset =
llvm::ConstantExpr::getTrunc(Sub, Type::getInt32Ty(M.getContext()));
RelLookupTableContents[Idx++] = RelOffset;
}
Constant *Initializer =
ConstantArray::get(IntArrayTy, RelLookupTableContents);
RelLookupTable->setInitializer(Initializer);
RelLookupTable->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
RelLookupTable->setAlignment(llvm::Align(4));
return RelLookupTable;
}
static void convertToRelLookupTable(GlobalVariable &LookupTable) {
GetElementPtrInst *GEP =
cast<GetElementPtrInst>(LookupTable.use_begin()->getUser());
LoadInst *Load = cast<LoadInst>(GEP->use_begin()->getUser());
Module &M = *LookupTable.getParent();
BasicBlock *BB = GEP->getParent();
IRBuilder<> Builder(BB);
Function &Func = *BB->getParent();
// Generate an array that consists of relative offsets.
GlobalVariable *RelLookupTable = createRelLookupTable(Func, LookupTable);
// Place new instruction sequence before GEP.
Builder.SetInsertPoint(GEP);
Value *Index = GEP->getOperand(2);
IntegerType *IntTy = cast<IntegerType>(Index->getType());
Value *Offset =
Builder.CreateShl(Index, ConstantInt::get(IntTy, 2), "reltable.shift");
Function *LoadRelIntrinsic = llvm::Intrinsic::getDeclaration(
&M, Intrinsic::load_relative, {Index->getType()});
Value *Base = Builder.CreateBitCast(RelLookupTable, Builder.getInt8PtrTy());
// Create a call to load.relative intrinsic that computes the target address
// by adding base address (lookup table address) and relative offset.
Value *Result = Builder.CreateCall(LoadRelIntrinsic, {Base, Offset},
"reltable.intrinsic");
// Create a bitcast instruction if necessary.
if (Load->getType() != Builder.getInt8PtrTy())
Result = Builder.CreateBitCast(Result, Load->getType(), "reltable.bitcast");
// Replace load instruction with the new generated instruction sequence.
Load->replaceAllUsesWith(Result);
// Remove Load and GEP instructions.
Load->eraseFromParent();
GEP->eraseFromParent();
}
// Convert lookup tables to relative lookup tables in the module.
static bool convertToRelativeLookupTables(
Module &M, function_ref<TargetTransformInfo &(Function &)> GetTTI) {
Module::iterator FI = M.begin();
if (FI == M.end())
return false;
// Check if we have a target that supports relative lookup tables.
if (!GetTTI(*FI).shouldBuildRelLookupTables())
return false;
bool Changed = false;
for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) {
if (!shouldConvertToRelLookupTable(M, GV))
continue;
convertToRelLookupTable(GV);
// Remove the original lookup table.
GV.eraseFromParent();
Changed = true;
}
return Changed;
}
PreservedAnalyses RelLookupTableConverterPass::run(Module &M,
ModuleAnalysisManager &AM) {
FunctionAnalysisManager &FAM =
AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
return FAM.getResult<TargetIRAnalysis>(F);
};
if (!convertToRelativeLookupTables(M, GetTTI))
return PreservedAnalyses::all();
PreservedAnalyses PA;
PA.preserveSet<CFGAnalyses>();
return PA;
}