LLVM: lib/Transforms/Utils/RelLookupTableConverter.cpp Source File

LLVM 22.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
14#include "llvm/Transforms/Utils/RelLookupTableConverter.h"
15#include "llvm/Analysis/ConstantFolding.h"
16#include "llvm/Analysis/TargetTransformInfo.h"
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
22using namespace llvm;
23
28
30 GlobalVariable &GV) {
31 // If lookup table has more than one user,
32 // do not generate a relative lookup table.
33 // This is to simplify the analysis that needs to be done for this pass.
34 // TODO: Add support for lookup tables with multiple uses.
35 // For ex, this can happen when a function that uses a lookup table gets
36 // inlined into multiple call sites.
37 //
38 // If the original lookup table does not have local linkage and is
39 // not dso_local, do not generate a relative lookup table.
40 // This optimization creates a relative lookup table that consists of
41 // offsets between the start of the lookup table and its elements.
42 // To be able to generate these offsets, relative lookup table and
43 // its elements should have internal linkage and be dso_local, which means
44 // that they should resolve to symbols within the same linkage unit.
45 if (!GV.hasInitializer() || !GV.isConstant() || !GV.hasOneUse() ||
46 !GV.hasLocalLinkage() || !GV.isDSOLocal() || !GV.isImplicitDSOLocal())
47 return false;
48
50 if (!GEP || !GEP->hasOneUse())
51 return false;
52
53 auto *Load = dyn_cast<LoadInst>(GEP->use_begin()->getUser());
54 if (!Load || !Load->hasOneUse())
55 return false;
56
57 // If values are not 64-bit pointers, do not generate a relative lookup table.
58 const DataLayout &DL = M.getDataLayout();
59 Type *ElemType = Load->getType();
60 if (!ElemType->isPointerTy() || DL.getPointerTypeSizeInBits(ElemType) != 64)
61 return false;
62
63 // Make sure this is a gep of the form GV + scale*var.
64 unsigned IndexWidth =
65 DL.getIndexTypeSizeInBits(Load->getPointerOperand()->getType());
67 APInt ConstOffset(IndexWidth, 0);
68 if (!GEP->collectOffset(DL, IndexWidth, VarOffsets, ConstOffset) ||
69 !ConstOffset.isZero() || VarOffsets.size() != 1)
70 return false;
71
72 // This can't be a pointer lookup table if the stride is smaller than a
73 // pointer.
74 Info.Index = VarOffsets.front().first;
75 const APInt &Stride = VarOffsets.front().second;
76 if (Stride.ult(DL.getTypeStoreSize(ElemType)))
77 return false;
78
80 Triple TT = M.getTargetTriple();
81 // FIXME: This should be removed in the future.
82 bool ShouldDropUnnamedAddr =
83 // Drop unnamed_addr to avoid matching pattern in
84 // `handleIndirectSymViaGOTPCRel`, which generates GOTPCREL relocations
85 // not supported by the GNU linker and LLD versions below 18 on aarch64.
86 TT.isAArch64()
87 // Apple's ld64 (and ld-prime on Xcode 15.2) miscompile something on
88 // x86_64-apple-darwin. See
89 // https://github.com/rust-lang/rust/issues/140686 and
90 // https://github.com/rust-lang/rust/issues/141306.
91 || (TT.isX86() && TT.isOSDarwin());
92
93 APInt Offset(IndexWidth, 0);
94 uint64_t GVSize = DL.getTypeAllocSize(GV.getValueType());
95 for (; Offset.ult(GVSize); Offset += Stride) {
96 Constant *C =
98 if (!C)
99 return false;
100
101 GlobalValue *GVOp;
102 APInt GVOffset;
103
104 // If an operand is not a constant offset from a lookup table,
105 // do not generate a relative lookup table.
106 if (!IsConstantOffsetFromGlobal(C, GVOp, GVOffset, DL))
107 return false;
108
109 // If operand is mutable, do not generate a relative lookup table.
110 auto *GlovalVarOp = dyn_cast<GlobalVariable>(GVOp);
111 if (!GlovalVarOp || !GlovalVarOp->isConstant())
112 return false;
113
114 if (!GlovalVarOp->hasLocalLinkage() ||
115 !GlovalVarOp->isDSOLocal() ||
116 !GlovalVarOp->isImplicitDSOLocal())
117 return false;
118
119 if (ShouldDropUnnamedAddr)
120 GVOps.push_back(GlovalVarOp);
121
122 Info.Ptrs.push_back(C);
123 }
124
125 if (ShouldDropUnnamedAddr)
126 for (auto *GVOp : GVOps)
127 GVOp->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
128
129 return true;
130}
131
133 Function &Func,
134 GlobalVariable &LookupTable) {
135 Module &M = *Func.getParent();
136 ArrayType *IntArrayTy =
137 ArrayType::get(Type::getInt32Ty(M.getContext()), Info.Ptrs.size());
138
139 GlobalVariable *RelLookupTable = new GlobalVariable(
140 M, IntArrayTy, LookupTable.isConstant(), LookupTable.getLinkage(),
141 nullptr, LookupTable.getName() + ".rel", &LookupTable,
142 LookupTable.getThreadLocalMode(), LookupTable.getAddressSpace(),
143 LookupTable.isExternallyInitialized());
144
145 uint64_t Idx = 0;
146 SmallVector<Constant *, 64> RelLookupTableContents(Info.Ptrs.size());
147
148 for (Constant *Element : Info.Ptrs) {
149 Type *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext());
150 Constant *Base = llvm::ConstantExpr::getPtrToInt(RelLookupTable, IntPtrTy);
151 Constant *Target = llvm::ConstantExpr::getPtrToInt(Element, IntPtrTy);
153 Constant *RelOffset =
155 RelLookupTableContents[Idx++] = RelOffset;
156 }
157
158 Constant *Initializer =
159 ConstantArray::get(IntArrayTy, RelLookupTableContents);
160 RelLookupTable->setInitializer(Initializer);
162 RelLookupTable->setAlignment(llvm::Align(4));
163 return RelLookupTable;
164}
165
167 GlobalVariable &LookupTable) {
169 cast<GetElementPtrInst>(LookupTable.use_begin()->getUser());
170 LoadInst *Load = cast<LoadInst>(GEP->use_begin()->getUser());
171
172 Module &M = *LookupTable.getParent();
173 BasicBlock *BB = GEP->getParent();
174 IRBuilder<> Builder(BB);
175 Function &Func = *BB->getParent();
176
177 // Generate an array that consists of relative offsets.
178 GlobalVariable *RelLookupTable =
179 createRelLookupTable(Info, Func, LookupTable);
180
181 // Place new instruction sequence before GEP.
182 Builder.SetInsertPoint(GEP);
183 IntegerType *IntTy = cast<IntegerType>(Info.Index->getType());
184 Value *Offset = Builder.CreateShl(Info.Index, ConstantInt::get(IntTy, 2),
185 "reltable.shift");
186
187 // Insert the call to load.relative intrinsic before LOAD.
188 // GEP might not be immediately followed by a LOAD, like it can be hoisted
189 // outside the loop or another instruction might be inserted them in between.
190 Builder.SetInsertPoint(Load);
192 &M, Intrinsic::load_relative, {Info.Index->getType()});
193
194 // Create a call to load.relative intrinsic that computes the target address
195 // by adding base address (lookup table address) and relative offset.
196 Value *Result = Builder.CreateCall(LoadRelIntrinsic, {RelLookupTable, Offset},
197 "reltable.intrinsic");
198
199 // Replace load instruction with the new generated instruction sequence.
200 Load->replaceAllUsesWith(Result);
201 // Remove Load and GEP instructions.
202 Load->eraseFromParent();
203 GEP->eraseFromParent();
204}
205
206// Convert lookup tables to relative lookup tables in the module.
209 for (Function &F : M) {
210 if (F.isDeclaration())
211 continue;
212
213 // Check if we have a target that supports relative lookup tables.
214 if (!GetTTI(F).shouldBuildRelLookupTables())
215 return false;
216
217 // We assume that the result is independent of the checked function.
218 break;
219 }
220
221 bool Changed = false;
222
223 for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) {
226 continue;
227
229
230 // Remove the original lookup table.
231 GV.eraseFromParent();
232
233 Changed = true;
234 }
235
236 return Changed;
237}
238
243
244 auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
245 return FAM.getResult<TargetIRAnalysis>(F);
246 };
247
248 if (!convertToRelativeLookupTables(M, GetTTI))
249 return PreservedAnalyses::all();
250
253 return PA;
254}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Analysis containing CSE Info
Definition CSEInfo.cpp:27
Hexagon Common GEP
Module.h This file contains the declarations for the Module class.
F
#define F(x, y, z)
Definition MD5.cpp:55
FunctionAnalysisManager FAM
static bool convertToRelativeLookupTables(Module &M, function_ref< TargetTransformInfo &(Function &)> GetTTI)
static bool shouldConvertToRelLookupTable(LookupTableInfo &Info, Module &M, GlobalVariable &GV)
static GlobalVariable * createRelLookupTable(LookupTableInfo &Info, Function &Func, GlobalVariable &LookupTable)
static void convertToRelLookupTable(LookupTableInfo &Info, 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:78
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition APInt.h:381
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition APInt.h:1112
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition PassManager.h:412
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
const Function * getParent() const
Return the enclosing method, or null if none.
Definition BasicBlock.h:213
Represents analyses that only rely on functions' control flow.
Definition Analysis.h:73
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition Constants.cpp:1317
static LLVM_ABI Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition Constants.cpp:2657
static LLVM_ABI Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition Constants.cpp:2303
static LLVM_ABI Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition Constants.cpp:2275
This is an important base class in LLVM.
Definition Constant.h:43
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:63
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition Instructions.h:950
bool isDSOLocal() const
Definition GlobalValue.h:307
bool isImplicitDSOLocal() const
Definition GlobalValue.h:300
void setUnnamedAddr(UnnamedAddr Val)
Definition GlobalValue.h:233
bool hasLocalLinkage() const
Definition GlobalValue.h:530
Type * getValueType() const
Definition GlobalValue.h:298
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
LLVM_ABI void setInitializer(Constant *InitVal)
setInitializer - Sets the initializer for this global variable, removing any existing initializer if ...
Definition Globals.cpp:524
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...
void setAlignment(Align Align)
Sets the alignment attribute of the GlobalVariable.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition IRBuilder.h:2788
Class to represent integer types.
Definition DerivedTypes.h:42
An instruction for reading from memory.
Definition Instructions.h:181
size_type size() const
Definition MapVector.h:56
std::pair< KeyT, ValueT > & front()
Definition MapVector.h:79
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:67
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
Definition Analysis.h:151
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
void push_back(const T &Elt)
Definition SmallVector.h:417
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition SmallVector.h:1203
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.
Triple - Helper class for working with autoconf configuration names.
Definition Triple.h:47
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:45
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
Definition Type.cpp:297
bool isPointerTy() const
True if this is an instance of PointerType.
Definition Type.h:267
User * getUser() const
Returns the User that contains this Use.
Definition Use.h:61
LLVM Value Representation.
Definition Value.h:75
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition Value.h:439
use_iterator use_begin()
Definition Value.h:364
An efficient, type-erasing, non-owning reference to a callable.
Changed
@ C
The default llvm calling convention, compatible with C.
Definition CallingConv.h:34
LLVM_ABI Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})
Look up the Function declaration of the intrinsic id in the Module M.
Definition Intrinsics.cpp:723
This is an optimization pass for GlobalISel generic memory operations.
Definition AddressRanges.h:18
@ Offset
Definition DWP.cpp:477
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
LLVM_ABI 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:632
InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy
Provide the FunctionAnalysisManager to Module proxy.
Definition PassManager.h:671
LLVM_ABI Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)
Extract value of C at the given Offset reinterpreted as Ty.
@ Sub
Subtraction of integers.
Definition IVDescriptors.h:38
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
Definition PassManager.h:564
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
Definition MIRParser.h:39
SmallVector< Constant * > Ptrs
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition Alignment.h:39
A MapVector that performs no allocations if smaller than a certain size.
Definition MapVector.h:257
Generated on for LLVM by doxygen 1.14.0

AltStyle によって変換されたページ (->オリジナル) /