LLVM  15.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 
22 using namespace llvm;
23 
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 
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 values are not pointers, do not generate a relative lookup table.
61  if (!Array || !Array->getType()->getElementType()->isPointerTy())
62  return false;
63 
64  const DataLayout &DL = M.getDataLayout();
65  for (const Use &Op : Array->operands()) {
66  Constant *ConstOp = cast<Constant>(&Op);
67  GlobalValue *GVOp;
68  APInt Offset;
69 
70  // If an operand is not a constant offset from a lookup table,
71  // do not generate a relative lookup table.
72  if (!IsConstantOffsetFromGlobal(ConstOp, GVOp, Offset, DL))
73  return false;
74 
75  // If operand is mutable, do not generate a relative lookup table.
76  auto *GlovalVarOp = dyn_cast<GlobalVariable>(GVOp);
77  if (!GlovalVarOp || !GlovalVarOp->isConstant())
78  return false;
79 
80  if (!GlovalVarOp->hasLocalLinkage() ||
81  !GlovalVarOp->isDSOLocal() ||
82  !GlovalVarOp->isImplicitDSOLocal())
83  return false;
84  }
85 
86  return true;
87 }
88 
90  GlobalVariable &LookupTable) {
91  Module &M = *Func.getParent();
92  ConstantArray *LookupTableArr =
93  cast<ConstantArray>(LookupTable.getInitializer());
94  unsigned NumElts = LookupTableArr->getType()->getNumElements();
95  ArrayType *IntArrayTy =
96  ArrayType::get(Type::getInt32Ty(M.getContext()), NumElts);
97 
98  GlobalVariable *RelLookupTable = new GlobalVariable(
99  M, IntArrayTy, LookupTable.isConstant(), LookupTable.getLinkage(),
100  nullptr, "reltable." + Func.getName(), &LookupTable,
101  LookupTable.getThreadLocalMode(), LookupTable.getAddressSpace(),
102  LookupTable.isExternallyInitialized());
103 
104  uint64_t Idx = 0;
105  SmallVector<Constant *, 64> RelLookupTableContents(NumElts);
106 
107  for (Use &Operand : LookupTableArr->operands()) {
108  Constant *Element = cast<Constant>(Operand);
109  Type *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext());
110  Constant *Base = llvm::ConstantExpr::getPtrToInt(RelLookupTable, IntPtrTy);
111  Constant *Target = llvm::ConstantExpr::getPtrToInt(Element, IntPtrTy);
113  Constant *RelOffset =
114  llvm::ConstantExpr::getTrunc(Sub, Type::getInt32Ty(M.getContext()));
115  RelLookupTableContents[Idx++] = RelOffset;
116  }
117 
118  Constant *Initializer =
119  ConstantArray::get(IntArrayTy, RelLookupTableContents);
120  RelLookupTable->setInitializer(Initializer);
122  RelLookupTable->setAlignment(llvm::Align(4));
123  return RelLookupTable;
124 }
125 
126 static void convertToRelLookupTable(GlobalVariable &LookupTable) {
128  cast<GetElementPtrInst>(LookupTable.use_begin()->getUser());
129  LoadInst *Load = cast<LoadInst>(GEP->use_begin()->getUser());
130 
131  Module &M = *LookupTable.getParent();
132  BasicBlock *BB = GEP->getParent();
134  Function &Func = *BB->getParent();
135 
136  // Generate an array that consists of relative offsets.
137  GlobalVariable *RelLookupTable = createRelLookupTable(Func, LookupTable);
138 
139  // Place new instruction sequence before GEP.
140  Builder.SetInsertPoint(GEP);
141  Value *Index = GEP->getOperand(2);
142  IntegerType *IntTy = cast<IntegerType>(Index->getType());
143  Value *Offset =
144  Builder.CreateShl(Index, ConstantInt::get(IntTy, 2), "reltable.shift");
145 
146  // Insert the call to load.relative intrinsic before LOAD.
147  // GEP might not be immediately followed by a LOAD, like it can be hoisted
148  // outside the loop or another instruction might be inserted them in between.
149  Builder.SetInsertPoint(Load);
150  Function *LoadRelIntrinsic = llvm::Intrinsic::getDeclaration(
151  &M, Intrinsic::load_relative, {Index->getType()});
152  Value *Base = Builder.CreateBitCast(RelLookupTable, Builder.getInt8PtrTy());
153 
154  // Create a call to load.relative intrinsic that computes the target address
155  // by adding base address (lookup table address) and relative offset.
156  Value *Result = Builder.CreateCall(LoadRelIntrinsic, {Base, Offset},
157  "reltable.intrinsic");
158 
159  // Create a bitcast instruction if necessary.
160  if (Load->getType() != Builder.getInt8PtrTy())
161  Result = Builder.CreateBitCast(Result, Load->getType(), "reltable.bitcast");
162 
163  // Replace load instruction with the new generated instruction sequence.
164  Load->replaceAllUsesWith(Result);
165  // Remove Load and GEP instructions.
166  Load->eraseFromParent();
167  GEP->eraseFromParent();
168 }
169 
170 // Convert lookup tables to relative lookup tables in the module.
172  Module &M, function_ref<TargetTransformInfo &(Function &)> GetTTI) {
173  for (Function &F : M) {
174  if (F.isDeclaration())
175  continue;
176 
177  // Check if we have a target that supports relative lookup tables.
178  if (!GetTTI(F).shouldBuildRelLookupTables())
179  return false;
180 
181  // We assume that the result is independent of the checked function.
182  break;
183  }
184 
185  bool Changed = false;
186 
187  for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) {
189  continue;
190 
192 
193  // Remove the original lookup table.
194  GV.eraseFromParent();
195 
196  Changed = true;
197  }
198 
199  return Changed;
200 }
201 
203  ModuleAnalysisManager &AM) {
206 
207  auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
208  return FAM.getResult<TargetIRAnalysis>(F);
209  };
210 
211  if (!convertToRelativeLookupTables(M, GetTTI))
212  return PreservedAnalyses::all();
213 
215  PA.preserveSet<CFGAnalyses>();
216  return PA;
217 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2479
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:202
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:1418
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:780
llvm::GlobalValue::getLinkage
LinkageTypes getLinkage() const
Definition: GlobalValue.h:509
llvm::GlobalValue::isImplicitDSOLocal
bool isImplicitDSOLocal() const
Definition: GlobalValue.h:280
llvm::Function
Definition: Function.h:60
convertToRelativeLookupTables
static bool convertToRelativeLookupTables(Module &M, function_ref< TargetTransformInfo &(Function &)> GetTTI)
Definition: RelLookupTableConverter.cpp:171
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:145
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
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:126
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
llvm::GlobalValue::setUnnamedAddr
void setUnnamedAddr(UnnamedAddr Val)
Definition: GlobalValue.h:217
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:357
ConstantFolding.h
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:239
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:55
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:294
llvm::ConstantExpr::getSub
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2734
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::ArrayType::getNumElements
uint64_t getNumElements() const
Definition: DerivedTypes.h:369
llvm::GlobalValue::getThreadLocalMode
ThreadLocalMode getThreadLocalMode() const
Definition: GlobalValue.h:257
shouldConvertToRelLookupTable
static bool shouldConvertToRelLookupTable(Module &M, GlobalVariable &GV)
Definition: RelLookupTableConverter.cpp:24
llvm::ConstantExpr::getPtrToInt
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2238
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::ConstantArray
ConstantArray - Constant Array Declarations.
Definition: Constants.h:410
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:928
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:429
llvm::ConstantExpr::getTrunc
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2128
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
uint64_t
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:620
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:916
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:618
IRBuilder.h
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition: GlobalValue.h:493
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:638
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:651
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:113
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::ConstantArray::get
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1290
llvm::GlobalValue::getAddressSpace
unsigned getAddressSpace() const
Definition: Globals.cpp:121
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
createRelLookupTable
static GlobalVariable * createRelLookupTable(Function &Func, GlobalVariable &LookupTable)
Definition: RelLookupTableConverter.cpp:89
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:42
llvm::GlobalValue::getValueType
Type * getValueType() const
Definition: GlobalValue.h:278
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:937
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:126
llvm::GlobalValue::isDSOLocal
bool isDSOLocal() const
Definition: GlobalValue.h:287
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:455
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43