LLVM  13.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  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.
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 
184  continue;
185 
187 
188  // Remove the original lookup table.
189  GV.eraseFromParent();
190 
191  Changed = true;
192  }
193 
194  return Changed;
195 }
196 
198  ModuleAnalysisManager &AM) {
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 
210  PA.preserveSet<CFGAnalyses>();
211  return PA;
212 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::GlobalVariable::eraseFromParent
void eraseFromParent()
eraseFromParent - This method unlinks 'this' from the containing module and deletes it.
Definition: Globals.cpp:385
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2320
llvm
Definition: AllocatorList.h:23
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:112
llvm::RelLookupTableConverterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: RelLookupTableConverter.cpp:197
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:435
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:1329
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:769
llvm::Module::iterator
FunctionListType::iterator iterator
The Function iterators.
Definition: Module.h:92
llvm::GlobalValue::getLinkage
LinkageTypes getLinkage() const
Definition: GlobalValue.h:461
llvm::GlobalValue::isImplicitDSOLocal
bool isImplicitDSOLocal() const
Definition: GlobalValue.h:275
llvm::Function
Definition: Function.h:61
Pass.h
convertToRelativeLookupTables
static bool convertToRelativeLookupTables(Module &M, function_ref< TargetTransformInfo &(Function &)> GetTTI)
Definition: RelLookupTableConverter.cpp:168
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:125
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::GlobalVariable::isExternallyInitialized
bool isExternallyInitialized() const
Definition: GlobalVariable.h:156
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
llvm::IRBuilder<>
llvm::GlobalVariable
Definition: GlobalVariable.h:40
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
convertToRelLookupTable
static void convertToRelLookupTable(GlobalVariable &LookupTable)
Definition: RelLookupTableConverter.cpp:127
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
Module.h
llvm::GlobalValue::UnnamedAddr::Global
@ Global
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::GlobalValue::setUnnamedAddr
void setUnnamedAddr(UnnamedAddr Val)
Definition: GlobalValue.h:212
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:359
ConstantFolding.h
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:197
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::GlobalVariable::hasInitializer
bool hasInitializer() const
Definitions have initializers, declarations don't.
Definition: GlobalVariable.h:92
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:303
llvm::ConstantExpr::getSub
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2688
llvm::ArrayType::getNumElements
uint64_t getNumElements() const
Definition: DerivedTypes.h:371
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:2192
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::ConstantArray
ConstantArray - Constant Array Declarations.
Definition: Constants.h:407
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:898
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: STLExtras.h:168
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:426
llvm::ConstantExpr::getTrunc
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2082
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:136
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:931
IRBuilder.h
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition: GlobalValue.h:445
llvm::Value::use_begin
use_iterator use_begin()
Definition: Value.h:361
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:598
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
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:174
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
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:1261
llvm::GlobalValue::getAddressSpace
unsigned getAddressSpace() const
Definition: Globals.cpp:112
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:153
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:926
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:171
llvm::GlobalObject::setAlignment
void setAlignment(MaybeAlign Align)
Definition: Globals.cpp:117
llvm::GlobalValue::isDSOLocal
bool isDSOLocal() const
Definition: GlobalValue.h:282
BasicBlockUtils.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
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:389
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44