LLVM 19.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();
137 IRBuilder<> Builder(BB);
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
157 // Create a call to load.relative intrinsic that computes the target address
158 // by adding base address (lookup table address) and relative offset.
159 Value *Result = Builder.CreateCall(LoadRelIntrinsic, {RelLookupTable, Offset},
160 "reltable.intrinsic");
161
162 // Replace load instruction with the new generated instruction sequence.
163 Load->replaceAllUsesWith(Result);
164 // Remove Load and GEP instructions.
165 Load->eraseFromParent();
166 GEP->eraseFromParent();
167}
168
169// Convert lookup tables to relative lookup tables in the module.
172 for (Function &F : M) {
173 if (F.isDeclaration())
174 continue;
175
176 // Check if we have a target that supports relative lookup tables.
177 if (!GetTTI(F).shouldBuildRelLookupTables())
178 return false;
179
180 // We assume that the result is independent of the checked function.
181 break;
182 }
183
184 bool Changed = false;
185
186 for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) {
188 continue;
189
191
192 // Remove the original lookup table.
193 GV.eraseFromParent();
194
195 Changed = true;
196 }
197
198 return Changed;
199}
200
205
206 auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
208 };
209
210 if (!convertToRelativeLookupTables(M, GetTTI))
211 return PreservedAnalyses::all();
212
215 return PA;
216}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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:321
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
uint64_t getNumElements() const
Definition: DerivedTypes.h:383
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
ConstantArray - Constant Array Declarations.
Definition: Constants.h:423
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1291
ArrayType * getType() const
Specialize the getType() method to always return an ArrayType, which reduces the amount of casting ne...
Definition: Constants.h:442
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2542
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2112
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2098
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:973
void setAlignment(Align Align)
Sets the alignment attribute of the GlobalObject.
Definition: Globals.cpp:128
bool isDSOLocal() const
Definition: GlobalValue.h:305
bool isImplicitDSOLocal() const
Definition: GlobalValue.h:298
void setUnnamedAddr(UnnamedAddr Val)
Definition: GlobalValue.h:231
bool hasLocalLinkage() const
Definition: GlobalValue.h:528
Type * getValueType() const
Definition: GlobalValue.h:296
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:466
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...
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1416
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args=std::nullopt, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2402
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2656
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:631
Class to represent integer types.
Definition: DerivedTypes.h:40
An instruction for reading from memory.
Definition: Instructions.h:184
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: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
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:1209
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:1469
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
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:656
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39