LLVM 19.0.0git
LocalStackSlotAllocation.cpp
Go to the documentation of this file.
1//===- LocalStackSlotAllocation.cpp - Pre-allocate locals to stack slots --===//
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 pass assigns local frame indices to stack slots relative to one another
10// and allocates additional base registers to access them when the target
11// estimates they are likely to be out of range of stack pointer and frame
12// pointer relative addressing.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/ADT/SetVector.h"
17#include "llvm/ADT/SmallSet.h"
19#include "llvm/ADT/Statistic.h"
31#include "llvm/Pass.h"
32#include "llvm/Support/Debug.h"
35#include <algorithm>
36#include <cassert>
37#include <cstdint>
38#include <tuple>
39
40using namespace llvm;
41
42#define DEBUG_TYPE "localstackalloc"
43
44STATISTIC(NumAllocations, "Number of frame indices allocated into local block");
45STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated");
46STATISTIC(NumReplacements, "Number of frame indices references replaced");
47
48namespace {
49
50 class FrameRef {
51 MachineBasicBlock::iterator MI; // Instr referencing the frame
52 int64_t LocalOffset; // Local offset of the frame idx referenced
53 int FrameIdx; // The frame index
54
55 // Order reference instruction appears in program. Used to ensure
56 // deterministic order when multiple instructions may reference the same
57 // location.
58 unsigned Order;
59
60 public:
61 FrameRef(MachineInstr *I, int64_t Offset, int Idx, unsigned Ord) :
62 MI(I), LocalOffset(Offset), FrameIdx(Idx), Order(Ord) {}
63
64 bool operator<(const FrameRef &RHS) const {
65 return std::tie(LocalOffset, FrameIdx, Order) <
66 std::tie(RHS.LocalOffset, RHS.FrameIdx, RHS.Order);
67 }
68
70 int64_t getLocalOffset() const { return LocalOffset; }
71 int getFrameIndex() const { return FrameIdx; }
72 };
73
74 class LocalStackSlotPass: public MachineFunctionPass {
75 SmallVector<int64_t, 16> LocalOffsets;
76
77 /// StackObjSet - A set of stack object indexes
79
80 void AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx, int64_t &Offset,
81 bool StackGrowsDown, Align &MaxAlign);
82 void AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
83 SmallSet<int, 16> &ProtectedObjs,
84 MachineFrameInfo &MFI, bool StackGrowsDown,
85 int64_t &Offset, Align &MaxAlign);
86 void calculateFrameObjectOffsets(MachineFunction &Fn);
87 bool insertFrameReferenceRegisters(MachineFunction &Fn);
88
89 public:
90 static char ID; // Pass identification, replacement for typeid
91
92 explicit LocalStackSlotPass() : MachineFunctionPass(ID) {
94 }
95
96 bool runOnMachineFunction(MachineFunction &MF) override;
97
98 void getAnalysisUsage(AnalysisUsage &AU) const override {
99 AU.setPreservesCFG();
101 }
102 };
103
104} // end anonymous namespace
105
106char LocalStackSlotPass::ID = 0;
107
108char &llvm::LocalStackSlotAllocationID = LocalStackSlotPass::ID;
109INITIALIZE_PASS(LocalStackSlotPass, DEBUG_TYPE,
110 "Local Stack Slot Allocation", false, false)
111
112bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) {
113 MachineFrameInfo &MFI = MF.getFrameInfo();
114 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
115 unsigned LocalObjectCount = MFI.getObjectIndexEnd();
116
117 // If the target doesn't want/need this pass, or if there are no locals
118 // to consider, early exit.
119 if (LocalObjectCount == 0 || !TRI->requiresVirtualBaseRegisters(MF))
120 return false;
121
122 // Make sure we have enough space to store the local offsets.
123 LocalOffsets.resize(MFI.getObjectIndexEnd());
124
125 // Lay out the local blob.
126 calculateFrameObjectOffsets(MF);
127
128 // Insert virtual base registers to resolve frame index references.
129 bool UsedBaseRegs = insertFrameReferenceRegisters(MF);
130
131 // Tell MFI whether any base registers were allocated. PEI will only
132 // want to use the local block allocations from this pass if there were any.
133 // Otherwise, PEI can do a bit better job of getting the alignment right
134 // without a hole at the start since it knows the alignment of the stack
135 // at the start of local allocation, and this pass doesn't.
136 MFI.setUseLocalStackAllocationBlock(UsedBaseRegs);
137
138 return true;
139}
140
141/// AdjustStackOffset - Helper function used to adjust the stack frame offset.
142void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx,
143 int64_t &Offset, bool StackGrowsDown,
144 Align &MaxAlign) {
145 // If the stack grows down, add the object size to find the lowest address.
146 if (StackGrowsDown)
147 Offset += MFI.getObjectSize(FrameIdx);
148
149 Align Alignment = MFI.getObjectAlign(FrameIdx);
150
151 // If the alignment of this object is greater than that of the stack, then
152 // increase the stack alignment to match.
153 MaxAlign = std::max(MaxAlign, Alignment);
154
155 // Adjust to alignment boundary.
156 Offset = alignTo(Offset, Alignment);
157
158 int64_t LocalOffset = StackGrowsDown ? -Offset : Offset;
159 LLVM_DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset "
160 << LocalOffset << "\n");
161 // Keep the offset available for base register allocation
162 LocalOffsets[FrameIdx] = LocalOffset;
163 // And tell MFI about it for PEI to use later
164 MFI.mapLocalFrameObject(FrameIdx, LocalOffset);
165
166 if (!StackGrowsDown)
167 Offset += MFI.getObjectSize(FrameIdx);
168
169 ++NumAllocations;
170}
171
172/// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
173/// those required to be close to the Stack Protector) to stack offsets.
174void LocalStackSlotPass::AssignProtectedObjSet(
175 const StackObjSet &UnassignedObjs, SmallSet<int, 16> &ProtectedObjs,
176 MachineFrameInfo &MFI, bool StackGrowsDown, int64_t &Offset,
177 Align &MaxAlign) {
178 for (int i : UnassignedObjs) {
179 AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
180 ProtectedObjs.insert(i);
181 }
182}
183
184/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
185/// abstract stack objects.
186void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) {
187 // Loop over all of the stack objects, assigning sequential addresses...
188 MachineFrameInfo &MFI = Fn.getFrameInfo();
190 bool StackGrowsDown =
192 int64_t Offset = 0;
193 Align MaxAlign;
194
195 // Make sure that the stack protector comes before the local variables on the
196 // stack.
197 SmallSet<int, 16> ProtectedObjs;
198 if (MFI.hasStackProtectorIndex()) {
199 int StackProtectorFI = MFI.getStackProtectorIndex();
200
201 // We need to make sure we didn't pre-allocate the stack protector when
202 // doing this.
203 // If we already have a stack protector, this will re-assign it to a slot
204 // that is **not** covering the protected objects.
205 assert(!MFI.isObjectPreAllocated(StackProtectorFI) &&
206 "Stack protector pre-allocated in LocalStackSlotAllocation");
207
208 StackObjSet LargeArrayObjs;
209 StackObjSet SmallArrayObjs;
210 StackObjSet AddrOfObjs;
211
212 // Only place the stack protector in the local stack area if the target
213 // allows it.
214 if (TFI.isStackIdSafeForLocalArea(MFI.getStackID(StackProtectorFI)))
215 AdjustStackOffset(MFI, StackProtectorFI, Offset, StackGrowsDown,
216 MaxAlign);
217
218 // Assign large stack objects first.
219 for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
220 if (MFI.isDeadObjectIndex(i))
221 continue;
222 if (StackProtectorFI == (int)i)
223 continue;
224 if (!TFI.isStackIdSafeForLocalArea(MFI.getStackID(i)))
225 continue;
226
227 switch (MFI.getObjectSSPLayout(i)) {
229 continue;
231 SmallArrayObjs.insert(i);
232 continue;
234 AddrOfObjs.insert(i);
235 continue;
237 LargeArrayObjs.insert(i);
238 continue;
239 }
240 llvm_unreachable("Unexpected SSPLayoutKind.");
241 }
242
243 AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
244 Offset, MaxAlign);
245 AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
246 Offset, MaxAlign);
247 AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
248 Offset, MaxAlign);
249 }
250
251 // Then assign frame offsets to stack objects that are not used to spill
252 // callee saved registers.
253 for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
254 if (MFI.isDeadObjectIndex(i))
255 continue;
256 if (MFI.getStackProtectorIndex() == (int)i)
257 continue;
258 if (ProtectedObjs.count(i))
259 continue;
260 if (!TFI.isStackIdSafeForLocalArea(MFI.getStackID(i)))
261 continue;
262
263 AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
264 }
265
266 // Remember how big this blob of stack space is
268 MFI.setLocalFrameMaxAlign(MaxAlign);
269}
270
271static inline bool
272lookupCandidateBaseReg(unsigned BaseReg,
273 int64_t BaseOffset,
274 int64_t FrameSizeAdjust,
275 int64_t LocalFrameOffset,
276 const MachineInstr &MI,
277 const TargetRegisterInfo *TRI) {
278 // Check if the relative offset from the where the base register references
279 // to the target address is in range for the instruction.
280 int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset;
281 return TRI->isFrameOffsetLegal(&MI, BaseReg, Offset);
282}
283
284bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) {
285 // Scan the function's instructions looking for frame index references.
286 // For each, ask the target if it wants a virtual base register for it
287 // based on what we can tell it about where the local will end up in the
288 // stack frame. If it wants one, re-use a suitable one we've previously
289 // allocated, or if there isn't one that fits the bill, allocate a new one
290 // and ask the target to create a defining instruction for it.
291
292 MachineFrameInfo &MFI = Fn.getFrameInfo();
295 bool StackGrowsDown =
297
298 // Collect all of the instructions in the block that reference
299 // a frame index. Also store the frame index referenced to ease later
300 // lookup. (For any insn that has more than one FI reference, we arbitrarily
301 // choose the first one).
302 SmallVector<FrameRef, 64> FrameReferenceInsns;
303
304 unsigned Order = 0;
305
306 for (MachineBasicBlock &BB : Fn) {
307 for (MachineInstr &MI : BB) {
308 // Debug value, stackmap and patchpoint instructions can't be out of
309 // range, so they don't need any updates.
310 if (MI.isDebugInstr() || MI.getOpcode() == TargetOpcode::STATEPOINT ||
311 MI.getOpcode() == TargetOpcode::STACKMAP ||
312 MI.getOpcode() == TargetOpcode::PATCHPOINT)
313 continue;
314
315 // For now, allocate the base register(s) within the basic block
316 // where they're used, and don't try to keep them around outside
317 // of that. It may be beneficial to try sharing them more broadly
318 // than that, but the increased register pressure makes that a
319 // tricky thing to balance. Investigate if re-materializing these
320 // becomes an issue.
321 for (const MachineOperand &MO : MI.operands()) {
322 // Consider replacing all frame index operands that reference
323 // an object allocated in the local block.
324 if (MO.isFI()) {
325 // Don't try this with values not in the local block.
326 if (!MFI.isObjectPreAllocated(MO.getIndex()))
327 break;
328 int Idx = MO.getIndex();
329 int64_t LocalOffset = LocalOffsets[Idx];
330 if (!TRI->needsFrameBaseReg(&MI, LocalOffset))
331 break;
332 FrameReferenceInsns.push_back(FrameRef(&MI, LocalOffset, Idx, Order++));
333 break;
334 }
335 }
336 }
337 }
338
339 // Sort the frame references by local offset.
340 // Use frame index as a tie-breaker in case MI's have the same offset.
341 llvm::sort(FrameReferenceInsns);
342
343 MachineBasicBlock *Entry = &Fn.front();
344
345 Register BaseReg;
346 int64_t BaseOffset = 0;
347
348 // Loop through the frame references and allocate for them as necessary.
349 for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) {
350 FrameRef &FR = FrameReferenceInsns[ref];
351 MachineInstr &MI = *FR.getMachineInstr();
352 int64_t LocalOffset = FR.getLocalOffset();
353 int FrameIdx = FR.getFrameIndex();
354 assert(MFI.isObjectPreAllocated(FrameIdx) &&
355 "Only pre-allocated locals expected!");
356
357 // We need to keep the references to the stack protector slot through frame
358 // index operands so that it gets resolved by PEI rather than this pass.
359 // This avoids accesses to the stack protector though virtual base
360 // registers, and forces PEI to address it using fp/sp/bp.
361 if (MFI.hasStackProtectorIndex() &&
362 FrameIdx == MFI.getStackProtectorIndex())
363 continue;
364
365 LLVM_DEBUG(dbgs() << "Considering: " << MI);
366
367 unsigned idx = 0;
368 for (unsigned f = MI.getNumOperands(); idx != f; ++idx) {
369 if (!MI.getOperand(idx).isFI())
370 continue;
371
372 if (FrameIdx == MI.getOperand(idx).getIndex())
373 break;
374 }
375
376 assert(idx < MI.getNumOperands() && "Cannot find FI operand");
377
378 int64_t Offset = 0;
379 int64_t FrameSizeAdjust = StackGrowsDown ? MFI.getLocalFrameSize() : 0;
380
381 LLVM_DEBUG(dbgs() << " Replacing FI in: " << MI);
382
383 // If we have a suitable base register available, use it; otherwise
384 // create a new one. Note that any offset encoded in the
385 // instruction itself will be taken into account by the target,
386 // so we don't have to adjust for it here when reusing a base
387 // register.
388 if (BaseReg.isValid() &&
389 lookupCandidateBaseReg(BaseReg, BaseOffset, FrameSizeAdjust,
390 LocalOffset, MI, TRI)) {
391 LLVM_DEBUG(dbgs() << " Reusing base register " << BaseReg << "\n");
392 // We found a register to reuse.
393 Offset = FrameSizeAdjust + LocalOffset - BaseOffset;
394 } else {
395 // No previously defined register was in range, so create a new one.
396 int64_t InstrOffset = TRI->getFrameIndexInstrOffset(&MI, idx);
397
398 int64_t CandBaseOffset = FrameSizeAdjust + LocalOffset + InstrOffset;
399
400 // We'd like to avoid creating single-use virtual base registers.
401 // Because the FrameRefs are in sorted order, and we've already
402 // processed all FrameRefs before this one, just check whether or not
403 // the next FrameRef will be able to reuse this new register. If not,
404 // then don't bother creating it.
405 if (ref + 1 >= e ||
407 BaseReg, CandBaseOffset, FrameSizeAdjust,
408 FrameReferenceInsns[ref + 1].getLocalOffset(),
409 *FrameReferenceInsns[ref + 1].getMachineInstr(), TRI))
410 continue;
411
412 // Save the base offset.
413 BaseOffset = CandBaseOffset;
414
415 // Tell the target to insert the instruction to initialize
416 // the base register.
417 // MachineBasicBlock::iterator InsertionPt = Entry->begin();
418 BaseReg = TRI->materializeFrameBaseRegister(Entry, FrameIdx, InstrOffset);
419
420 LLVM_DEBUG(dbgs() << " Materialized base register at frame local offset "
421 << LocalOffset + InstrOffset
422 << " into " << printReg(BaseReg, TRI) << '\n');
423
424 // The base register already includes any offset specified
425 // by the instruction, so account for that so it doesn't get
426 // applied twice.
427 Offset = -InstrOffset;
428
429 ++NumBaseRegisters;
430 }
431 assert(BaseReg && "Unable to allocate virtual base register!");
432
433 // Modify the instruction to use the new base register rather
434 // than the frame index operand.
435 TRI->resolveFrameIndex(MI, BaseReg, Offset);
436 LLVM_DEBUG(dbgs() << "Resolved: " << MI);
437
438 ++NumReplacements;
439 }
440
441 return BaseReg.isValid();
442}
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
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static MachineInstr * getMachineInstr(MachineInstr *MI)
IRTranslator LLVM IR MI
static bool lookupCandidateBaseReg(unsigned BaseReg, int64_t BaseOffset, int64_t FrameSizeAdjust, int64_t LocalFrameOffset, const MachineInstr &MI, const TargetRegisterInfo *TRI)
#define DEBUG_TYPE
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
static void AssignProtectedObjSet(const StackObjSet &UnassignedObjs, SmallSet< int, 16 > &ProtectedObjs, MachineFrameInfo &MFI, bool StackGrowsDown, int64_t &Offset, Align &MaxAlign)
AssignProtectedObjSet - Helper function to assign large stack objects (i.e., those required to be clo...
static void AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx, bool StackGrowsDown, int64_t &Offset, Align &MaxAlign)
AdjustStackOffset - Helper function used to adjust the stack frame offset.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Value * RHS
Represent the analysis usage information of a pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:269
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
SSPLayoutKind getObjectSSPLayout(int ObjectIdx) const
bool isObjectPreAllocated(int ObjectIdx) const
Return true if the object was pre-allocated into the local block.
void setUseLocalStackAllocationBlock(bool v)
setUseLocalStackAllocationBlock - Set whether the local allocation blob should be allocated together ...
void setLocalFrameSize(int64_t sz)
Set the size of the local object blob.
@ SSPLK_SmallArray
Array or nested array < SSP-buffer-size.
@ SSPLK_LargeArray
Array or nested array >= SSP-buffer-size.
@ SSPLK_AddrOf
The address of this allocation is exposed and triggered protection.
@ SSPLK_None
Did not trigger a stack protector.
void setLocalFrameMaxAlign(Align Alignment)
Required alignment of the local object blob, which is the strictest alignment of any object in it.
int getStackProtectorIndex() const
Return the index for the stack protector object.
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
void mapLocalFrameObject(int ObjectIndex, int64_t Offset)
Map a frame index into the local object block.
int64_t getObjectSize(int ObjectIdx) const
Return the size of the specified object.
int64_t getLocalFrameSize() const
Get the size of the local object blob.
int getObjectIndexEnd() const
Return one past the maximum frame object index.
bool hasStackProtectorIndex() const
uint8_t getStackID(int ObjectIdx) const
bool isDeadObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a dead object.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Representation of each machine instruction.
Definition: MachineInstr.h:69
MachineOperand class - Representation of each machine instruction operand.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
constexpr bool isValid() const
Definition: Register.h:116
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
size_t size() const
Definition: SmallVector.h:91
void resize(size_type N)
Definition: SmallVector.h:651
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Information about stack frame layout on the target.
virtual bool isStackIdSafeForLocalArea(unsigned StackId) const
This method returns whether or not it is safe for an object with the given stack id to be bundled int...
StackDirection getStackGrowthDirection() const
getStackGrowthDirection - Return the direction the stack grows
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetFrameLowering * getFrameLowering() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:361
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1656
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:155
char & LocalStackSlotAllocationID
LocalStackSlotAllocation - This pass assigns local frame indices to stack slots relative to one anoth...
void initializeLocalStackSlotPassPass(PassRegistry &)
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39