LLVM 18.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"
20#include "llvm/IR/Module.h"
21
22using 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() ||
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;
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 =
119 RelLookupTableContents[Idx++] = RelOffset;
120 }
121
122 Constant *Initializer =
123 ConstantArray::get(IntArrayTy, RelLookupTableContents);
124 RelLookupTable->setInitializer(Initializer);
125 RelLookupTable->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
126 RelLookupTable->setAlignment(llvm::Align(4));
127 return RelLookupTable;
128}
129
130static 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.
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
210
211 auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
213 };
214
215 if (!convertToRelativeLookupTables(M, GetTTI))
216 return PreservedAnalyses::all();
217
220 return PA;
221}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
assume Assume Builder
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Hexagon Common GEP
#define F(x, y, z)
Definition: MD5.cpp:55
Module.h This file contains the declarations for the Module class.
FunctionAnalysisManager FAM
static bool shouldConvertToRelLookupTable(Module &M, GlobalVariable &GV)
static void convertToRelLookupTable(GlobalVariable &LookupTable)
static bool convertToRelativeLookupTables(Module &M, function_ref< TargetTransformInfo &(Function &)> GetTTI)
static GlobalVariable * createRelLookupTable(Function &Func, GlobalVariable &LookupTable)
This file implements relative lookup table converter that converts lookup tables to relative lookup t...
This pass exposes codegen information to IR-level passes.
Class for arbitrary precision integers.
Definition: APInt.h:76
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
uint64_t getNumElements() const
Definition: DerivedTypes.h:380
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
ConstantArray - Constant Array Declarations.
Definition: Constants.h:408
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1235
ArrayType * getType() const
Specialize the getType() method to always return an ArrayType, which reduces the amount of casting ne...
Definition: Constants.h:427
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2573
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2185
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2075
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:888
This is an important base class in LLVM.
Definition: Constant.h:41
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:940
void setAlignment(Align Align)
Sets the alignment attribute of the GlobalObject.
Definition: Globals.cpp:128
bool isDSOLocal() const
Definition: GlobalValue.h:301
bool isImplicitDSOLocal() const
Definition: GlobalValue.h:294
void setUnnamedAddr(UnnamedAddr Val)
Definition: GlobalValue.h:227
bool hasLocalLinkage() const
Definition: GlobalValue.h:523
Type * getValueType() const
Definition: GlobalValue.h:292
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
void setInitializer(Constant *InitVal)
setInitializer - Sets the initializer for this global variable, removing any existing initializer if ...
Definition: Globals.cpp:458
bool hasInitializer() const
Definitions have initializers, declarations don't.
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2628
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:933
Class to represent integer types.
Definition: DerivedTypes.h:40
An instruction for reading from memory.
Definition: Instructions.h:177
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Target - Wrapper for Target specific information.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:255
static IntegerType * getInt32Ty(LLVMContext &C)
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
LLVM Value Representation.
Definition: Value.h:74
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
use_iterator use_begin()
Definition: Value.h:360
An efficient, type-erasing, non-owning reference to a callable.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1422
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:440
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.
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:666
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39