LLVM  14.0.0git
RelLookupTableConverter.cpp
Go to the documentation of this file.
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 
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"
24 
25 using namespace llvm;
26 
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 
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 
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);
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);
123  RelLookupTable->setAlignment(llvm::Align(4));
124  return RelLookupTable;
125 }
126 
127 static void convertToRelLookupTable(GlobalVariable &LookupTable) {
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();
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  // Insert the call to load.relative instrinsic before LOAD.
148  // GEP might not be immediately followed by a LOAD, like it can be hoisted
149  // outside the loop or another instruction might be inserted them in between.
150  Builder.SetInsertPoint(Load);
151  Function *LoadRelIntrinsic = llvm::Intrinsic::getDeclaration(
152  &M, Intrinsic::load_relative, {Index->getType()});
153  Value *Base = Builder.CreateBitCast(RelLookupTable, Builder.getInt8PtrTy());
154 
155  // Create a call to load.relative intrinsic that computes the target address
156  // by adding base address (lookup table address) and relative offset.
157  Value *Result = Builder.CreateCall(LoadRelIntrinsic, {Base, Offset},
158  "reltable.intrinsic");
159 
160  // Create a bitcast instruction if necessary.
161  if (Load->getType() != Builder.getInt8PtrTy())
162  Result = Builder.CreateBitCast(Result, Load->getType(), "reltable.bitcast");
163 
164  // Replace load instruction with the new generated instruction sequence.
165  Load->replaceAllUsesWith(Result);
166  // Remove Load and GEP instructions.
167  Load->eraseFromParent();
168  GEP->eraseFromParent();
169 }
170 
171 // Convert lookup tables to relative lookup tables in the module.
173  Module &M, function_ref<TargetTransformInfo &(Function &)> GetTTI) {
174  Module::iterator FI = M.begin();
175  if (FI == M.end())
176  return false;
177 
178  // Check if we have a target that supports relative lookup tables.
179  if (!GetTTI(*FI).shouldBuildRelLookupTables())
180  return false;
181 
182  bool Changed = false;
183 
184  for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) {
186  continue;
187 
189 
190  // Remove the original lookup table.
191  GV.eraseFromParent();
192 
193  Changed = true;
194  }
195 
196  return Changed;
197 }
198 
200  ModuleAnalysisManager &AM) {
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 
212  PA.preserveSet<CFGAnalyses>();
213  return PA;
214 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2420
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::RelLookupTableConverterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: RelLookupTableConverter.cpp:199
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
llvm::Intrinsic::getDeclaration
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1400
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:783
llvm::Module::iterator
FunctionListType::iterator iterator
The Function iterators.
Definition: Module.h:90
llvm::GlobalValue::getLinkage
LinkageTypes getLinkage() const
Definition: GlobalValue.h:467
llvm::GlobalValue::isImplicitDSOLocal
bool isImplicitDSOLocal() const
Definition: GlobalValue.h:275
llvm::Function
Definition: Function.h:62
Pass.h
convertToRelativeLookupTables
static bool convertToRelativeLookupTables(Module &M, function_ref< TargetTransformInfo &(Function &)> GetTTI)
Definition: RelLookupTableConverter.cpp:172
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:137
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1176
llvm::GlobalVariable::isExternallyInitialized
bool isExternallyInitialized() const
Definition: GlobalVariable.h:155
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::IRBuilder<>
llvm::GlobalVariable
Definition: GlobalVariable.h:39
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
convertToRelLookupTable
static void convertToRelLookupTable(GlobalVariable &LookupTable)
Definition: RelLookupTableConverter.cpp:127
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
llvm::GlobalValue::UnnamedAddr::Global
@ Global
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:80
llvm::GlobalValue::setUnnamedAddr
void setUnnamedAddr(UnnamedAddr Val)
Definition: GlobalValue.h:212
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:357
ConstantFolding.h
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:241
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::GlobalVariable::hasInitializer
bool hasInitializer() const
Definitions have initializers, declarations don't.
Definition: GlobalVariable.h:91
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::IsConstantOffsetFromGlobal
bool IsConstantOffsetFromGlobal(Constant *C, GlobalValue *&GV, APInt &Offset, const DataLayout &DL, DSOLocalEquivalent **DSOEquiv=nullptr)
If this constant is a constant offset from a global, return the global and the constant.
Definition: ConstantFolding.cpp:295
llvm::ConstantExpr::getSub
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2721
llvm::ArrayType::getNumElements
uint64_t getNumElements() const
Definition: DerivedTypes.h:369
llvm::GlobalValue::getThreadLocalMode
ThreadLocalMode getThreadLocalMode() const
Definition: GlobalValue.h:252
shouldConvertToRelLookupTable
static bool shouldConvertToRelLookupTable(Module &M, GlobalVariable &GV)
Definition: RelLookupTableConverter.cpp:27
llvm::ConstantExpr::getPtrToInt
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2225
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::ConstantArray
ConstantArray - Constant Array Declarations.
Definition: Constants.h:409
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:925
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::ConstantArray::getType
ArrayType * getType() const
Specialize the getType() method to always return an ArrayType, which reduces the amount of casting ne...
Definition: Constants.h:428
llvm::ConstantExpr::getTrunc
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2115
BasicBlock.h
llvm::GlobalValue
Definition: GlobalValue.h:44
llvm::GlobalVariable::getInitializer
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
Definition: GlobalVariable.h:135
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
uint64_t
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:578
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:933
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:585
IRBuilder.h
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition: GlobalValue.h:451
llvm::Value::use_begin
use_iterator use_begin()
Definition: Value.h:360
llvm::ArrayType::get
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:640
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:180
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::ConstantArray::get
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1288
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::GlobalValue::getAddressSpace
unsigned getAddressSpace() const
Definition: Globals.cpp:119
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
createRelLookupTable
static GlobalVariable * createRelLookupTable(Function &Func, GlobalVariable &LookupTable)
Definition: RelLookupTableConverter.cpp:90
llvm::GlobalVariable::isConstant
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
Definition: GlobalVariable.h:152
TargetTransformInfo.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:940
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::GlobalObject::setAlignment
void setAlignment(MaybeAlign Align)
Definition: Globals.cpp:124
llvm::GlobalValue::isDSOLocal
bool isDSOLocal() const
Definition: GlobalValue.h:282
BasicBlockUtils.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
RelLookupTableConverter.h
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::GlobalVariable::setInitializer
void setInitializer(Constant *InitVal)
setInitializer - Sets the initializer for this global variable, removing any existing initializer if ...
Definition: Globals.cpp:434
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44