LLVM  16.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 (!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 
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);
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);
126  RelLookupTable->setAlignment(llvm::Align(4));
127  return RelLookupTable;
128 }
129 
130 static void convertToRelLookupTable(GlobalVariable &LookupTable) {
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();
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.
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())) {
193  continue;
194 
196 
197  // Remove the original lookup table.
198  GV.eraseFromParent();
199 
200  Changed = true;
201  }
202 
203  return Changed;
204 }
205 
207  ModuleAnalysisManager &AM) {
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 
219  PA.preserveSet<CFGAnalyses>();
220  return PA;
221 }
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:2585
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:206
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:1481
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:237
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:774
llvm::GlobalValue::isImplicitDSOLocal
bool isImplicitDSOLocal() const
Definition: GlobalValue.h:292
llvm::Function
Definition: Function.h:60
convertToRelativeLookupTables
static bool convertToRelativeLookupTables(Module &M, function_ref< TargetTransformInfo &(Function &)> GetTTI)
Definition: RelLookupTableConverter.cpp:175
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:149
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:172
llvm::IRBuilder<>
llvm::GlobalVariable
Definition: GlobalVariable.h:39
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
convertToRelLookupTable
static void convertToRelLookupTable(GlobalVariable &LookupTable)
Definition: RelLookupTableConverter.cpp:130
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:225
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:295
llvm::ConstantExpr::getSub
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2637
llvm::ArrayType::getNumElements
uint64_t getNumElements() const
Definition: DerivedTypes.h:369
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:2174
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:879
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:2064
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::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
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:716
IRBuilder.h
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition: GlobalValue.h:521
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:348
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::ConstantArray::get
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1241
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:93
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:290
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:931
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:299
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:468
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43