LLVM  9.0.0svn
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"
18 #include "llvm/ADT/SmallVector.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 
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "localstackalloc"
43 
44 STATISTIC(NumAllocations, "Number of frame indices allocated into local block");
45 STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated");
46 STATISTIC(NumReplacements, "Number of frame indices references replaced");
47 
48 namespace {
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, unsigned &MaxAlign);
82  void AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
83  SmallSet<int, 16> &ProtectedObjs,
84  MachineFrameInfo &MFI, bool StackGrowsDown,
85  int64_t &Offset, unsigned &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 
106 char LocalStackSlotPass::ID = 0;
107 
109 INITIALIZE_PASS(LocalStackSlotPass, DEBUG_TYPE,
110  "Local Stack Slot Allocation", false, false)
111 
112 bool 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 (!TRI->requiresVirtualBaseRegisters(MF) || LocalObjectCount == 0)
120  return true;
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.
143  int FrameIdx, int64_t &Offset,
144  bool StackGrowsDown,
145  unsigned &MaxAlign) {
146  // If the stack grows down, add the object size to find the lowest address.
147  if (StackGrowsDown)
148  Offset += MFI.getObjectSize(FrameIdx);
149 
150  unsigned Align = MFI.getObjectAlignment(FrameIdx);
151 
152  // If the alignment of this object is greater than that of the stack, then
153  // increase the stack alignment to match.
154  MaxAlign = std::max(MaxAlign, Align);
155 
156  // Adjust to alignment boundary.
157  Offset = (Offset + Align - 1) / Align * Align;
158 
159  int64_t LocalOffset = StackGrowsDown ? -Offset : Offset;
160  LLVM_DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset "
161  << LocalOffset << "\n");
162  // Keep the offset available for base register allocation
163  LocalOffsets[FrameIdx] = LocalOffset;
164  // And tell MFI about it for PEI to use later
165  MFI.mapLocalFrameObject(FrameIdx, LocalOffset);
166 
167  if (!StackGrowsDown)
168  Offset += MFI.getObjectSize(FrameIdx);
169 
170  ++NumAllocations;
171 }
172 
173 /// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
174 /// those required to be close to the Stack Protector) to stack offsets.
175 void LocalStackSlotPass::AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
176  SmallSet<int, 16> &ProtectedObjs,
177  MachineFrameInfo &MFI,
178  bool StackGrowsDown, int64_t &Offset,
179  unsigned &MaxAlign) {
180  for (StackObjSet::const_iterator I = UnassignedObjs.begin(),
181  E = UnassignedObjs.end(); I != E; ++I) {
182  int i = *I;
183  AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
184  ProtectedObjs.insert(i);
185  }
186 }
187 
188 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
189 /// abstract stack objects.
190 void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) {
191  // Loop over all of the stack objects, assigning sequential addresses...
192  MachineFrameInfo &MFI = Fn.getFrameInfo();
194  bool StackGrowsDown =
196  int64_t Offset = 0;
197  unsigned MaxAlign = 0;
198 
199  // Make sure that the stack protector comes before the local variables on the
200  // stack.
201  SmallSet<int, 16> ProtectedObjs;
202  if (MFI.getStackProtectorIndex() >= 0) {
203  StackObjSet LargeArrayObjs;
204  StackObjSet SmallArrayObjs;
205  StackObjSet AddrOfObjs;
206 
208  StackGrowsDown, MaxAlign);
209 
210  // Assign large stack objects first.
211  for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
212  if (MFI.isDeadObjectIndex(i))
213  continue;
214  if (MFI.getStackProtectorIndex() == (int)i)
215  continue;
216 
217  switch (MFI.getObjectSSPLayout(i)) {
219  continue;
221  SmallArrayObjs.insert(i);
222  continue;
224  AddrOfObjs.insert(i);
225  continue;
227  LargeArrayObjs.insert(i);
228  continue;
229  }
230  llvm_unreachable("Unexpected SSPLayoutKind.");
231  }
232 
233  AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
234  Offset, MaxAlign);
235  AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
236  Offset, MaxAlign);
237  AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
238  Offset, MaxAlign);
239  }
240 
241  // Then assign frame offsets to stack objects that are not used to spill
242  // callee saved registers.
243  for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
244  if (MFI.isDeadObjectIndex(i))
245  continue;
246  if (MFI.getStackProtectorIndex() == (int)i)
247  continue;
248  if (ProtectedObjs.count(i))
249  continue;
250 
251  AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
252  }
253 
254  // Remember how big this blob of stack space is
255  MFI.setLocalFrameSize(Offset);
256  MFI.setLocalFrameMaxAlign(MaxAlign);
257 }
258 
259 static inline bool
260 lookupCandidateBaseReg(unsigned BaseReg,
261  int64_t BaseOffset,
262  int64_t FrameSizeAdjust,
263  int64_t LocalFrameOffset,
264  const MachineInstr &MI,
265  const TargetRegisterInfo *TRI) {
266  // Check if the relative offset from the where the base register references
267  // to the target address is in range for the instruction.
268  int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset;
269  return TRI->isFrameOffsetLegal(&MI, BaseReg, Offset);
270 }
271 
272 bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) {
273  // Scan the function's instructions looking for frame index references.
274  // For each, ask the target if it wants a virtual base register for it
275  // based on what we can tell it about where the local will end up in the
276  // stack frame. If it wants one, re-use a suitable one we've previously
277  // allocated, or if there isn't one that fits the bill, allocate a new one
278  // and ask the target to create a defining instruction for it.
279  bool UsedBaseReg = false;
280 
281  MachineFrameInfo &MFI = Fn.getFrameInfo();
284  bool StackGrowsDown =
286 
287  // Collect all of the instructions in the block that reference
288  // a frame index. Also store the frame index referenced to ease later
289  // lookup. (For any insn that has more than one FI reference, we arbitrarily
290  // choose the first one).
291  SmallVector<FrameRef, 64> FrameReferenceInsns;
292 
293  unsigned Order = 0;
294 
295  for (MachineBasicBlock &BB : Fn) {
296  for (MachineInstr &MI : BB) {
297  // Debug value, stackmap and patchpoint instructions can't be out of
298  // range, so they don't need any updates.
299  if (MI.isDebugInstr() || MI.getOpcode() == TargetOpcode::STATEPOINT ||
300  MI.getOpcode() == TargetOpcode::STACKMAP ||
301  MI.getOpcode() == TargetOpcode::PATCHPOINT)
302  continue;
303 
304  // For now, allocate the base register(s) within the basic block
305  // where they're used, and don't try to keep them around outside
306  // of that. It may be beneficial to try sharing them more broadly
307  // than that, but the increased register pressure makes that a
308  // tricky thing to balance. Investigate if re-materializing these
309  // becomes an issue.
310  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
311  // Consider replacing all frame index operands that reference
312  // an object allocated in the local block.
313  if (MI.getOperand(i).isFI()) {
314  // Don't try this with values not in the local block.
315  if (!MFI.isObjectPreAllocated(MI.getOperand(i).getIndex()))
316  break;
317  int Idx = MI.getOperand(i).getIndex();
318  int64_t LocalOffset = LocalOffsets[Idx];
319  if (!TRI->needsFrameBaseReg(&MI, LocalOffset))
320  break;
321  FrameReferenceInsns.push_back(FrameRef(&MI, LocalOffset, Idx, Order++));
322  break;
323  }
324  }
325  }
326  }
327 
328  // Sort the frame references by local offset.
329  // Use frame index as a tie-breaker in case MI's have the same offset.
330  llvm::sort(FrameReferenceInsns);
331 
332  MachineBasicBlock *Entry = &Fn.front();
333 
334  unsigned BaseReg = 0;
335  int64_t BaseOffset = 0;
336 
337  // Loop through the frame references and allocate for them as necessary.
338  for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) {
339  FrameRef &FR = FrameReferenceInsns[ref];
340  MachineInstr &MI = *FR.getMachineInstr();
341  int64_t LocalOffset = FR.getLocalOffset();
342  int FrameIdx = FR.getFrameIndex();
343  assert(MFI.isObjectPreAllocated(FrameIdx) &&
344  "Only pre-allocated locals expected!");
345 
346  LLVM_DEBUG(dbgs() << "Considering: " << MI);
347 
348  unsigned idx = 0;
349  for (unsigned f = MI.getNumOperands(); idx != f; ++idx) {
350  if (!MI.getOperand(idx).isFI())
351  continue;
352 
353  if (FrameIdx == MI.getOperand(idx).getIndex())
354  break;
355  }
356 
357  assert(idx < MI.getNumOperands() && "Cannot find FI operand");
358 
359  int64_t Offset = 0;
360  int64_t FrameSizeAdjust = StackGrowsDown ? MFI.getLocalFrameSize() : 0;
361 
362  LLVM_DEBUG(dbgs() << " Replacing FI in: " << MI);
363 
364  // If we have a suitable base register available, use it; otherwise
365  // create a new one. Note that any offset encoded in the
366  // instruction itself will be taken into account by the target,
367  // so we don't have to adjust for it here when reusing a base
368  // register.
369  if (UsedBaseReg &&
370  lookupCandidateBaseReg(BaseReg, BaseOffset, FrameSizeAdjust,
371  LocalOffset, MI, TRI)) {
372  LLVM_DEBUG(dbgs() << " Reusing base register " << BaseReg << "\n");
373  // We found a register to reuse.
374  Offset = FrameSizeAdjust + LocalOffset - BaseOffset;
375  } else {
376  // No previously defined register was in range, so create a new one.
377  int64_t InstrOffset = TRI->getFrameIndexInstrOffset(&MI, idx);
378 
379  int64_t PrevBaseOffset = BaseOffset;
380  BaseOffset = FrameSizeAdjust + LocalOffset + InstrOffset;
381 
382  // We'd like to avoid creating single-use virtual base registers.
383  // Because the FrameRefs are in sorted order, and we've already
384  // processed all FrameRefs before this one, just check whether or not
385  // the next FrameRef will be able to reuse this new register. If not,
386  // then don't bother creating it.
387  if (ref + 1 >= e ||
389  BaseReg, BaseOffset, FrameSizeAdjust,
390  FrameReferenceInsns[ref + 1].getLocalOffset(),
391  *FrameReferenceInsns[ref + 1].getMachineInstr(), TRI)) {
392  BaseOffset = PrevBaseOffset;
393  continue;
394  }
395 
396  const MachineFunction *MF = MI.getMF();
397  const TargetRegisterClass *RC = TRI->getPointerRegClass(*MF);
398  BaseReg = Fn.getRegInfo().createVirtualRegister(RC);
399 
400  LLVM_DEBUG(dbgs() << " Materializing base register " << BaseReg
401  << " at frame local offset "
402  << LocalOffset + InstrOffset << "\n");
403 
404  // Tell the target to insert the instruction to initialize
405  // the base register.
406  // MachineBasicBlock::iterator InsertionPt = Entry->begin();
407  TRI->materializeFrameBaseRegister(Entry, BaseReg, FrameIdx,
408  InstrOffset);
409 
410  // The base register already includes any offset specified
411  // by the instruction, so account for that so it doesn't get
412  // applied twice.
413  Offset = -InstrOffset;
414 
415  ++NumBaseRegisters;
416  UsedBaseReg = true;
417  }
418  assert(BaseReg != 0 && "Unable to allocate virtual base register!");
419 
420  // Modify the instruction to use the new base register rather
421  // than the frame index operand.
422  TRI->resolveFrameIndex(MI, BaseReg, Offset);
423  LLVM_DEBUG(dbgs() << "Resolved: " << MI);
424 
425  ++NumReplacements;
426  }
427 
428  return UsedBaseReg;
429 }
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
static bool lookupCandidateBaseReg(unsigned BaseReg, int64_t BaseOffset, int64_t FrameSizeAdjust, int64_t LocalFrameOffset, const MachineInstr &MI, const TargetRegisterInfo *TRI)
static void AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx, bool StackGrowsDown, int64_t &Offset, unsigned &MaxAlign, unsigned Skew)
AdjustStackOffset - Helper function used to adjust the stack frame offset.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
void mapLocalFrameObject(int ObjectIndex, int64_t Offset)
Map a frame index into the local object block.
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define DEBUG_TYPE
Did not trigger a stack protector.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
bool isDeadObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a dead object.
int64_t getLocalFrameSize() const
Get the size of the local object blob.
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
virtual bool isFrameOffsetLegal(const MachineInstr *MI, unsigned BaseReg, int64_t Offset) const
Determine whether a given base register plus offset immediate is encodable to resolve a frame index...
void setLocalFrameSize(int64_t sz)
Set the size of the local object blob.
void setUseLocalStackAllocationBlock(bool v)
setUseLocalStackAllocationBlock - Set whether the local allocation blob should be allocated together ...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:411
The address of this allocation is exposed and triggered protection.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
bool isObjectPreAllocated(int ObjectIdx) const
Return true if the object was pre-allocated into the local block.
void setLocalFrameMaxAlign(unsigned Align)
Required alignment of the local object blob, which is the strictest alignment of any object in it...
int getObjectIndexEnd() const
Return one past the maximum frame object index.
SSPLayoutKind getObjectSSPLayout(int ObjectIdx) const
static MachineInstr * getMachineInstr(MachineInstr *MI)
int64_t getObjectSize(int ObjectIdx) const
Return the size of the specified object.
Array or nested array >= SSP-buffer-size.
unsigned getObjectAlignment(int ObjectIdx) const
Return the alignment of the specified stack object.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
StackDirection getStackGrowthDirection() const
getStackGrowthDirection - Return the direction the stack grows
int getStackProtectorIndex() const
Return the index for the stack protector object.
Represent the analysis usage information of a pass.
virtual int64_t getFrameIndexInstrOffset(const MachineInstr *MI, int Idx) const
Get the offset from the referenced frame index in the instruction, if there is one.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
size_t size() const
Definition: SmallVector.h:52
typename vector_type::const_iterator const_iterator
Definition: SetVector.h:49
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1115
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:839
Information about stack frame layout on the target.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
virtual bool needsFrameBaseReg(MachineInstr *MI, int64_t Offset) const
Returns true if the instruction&#39;s frame index reference would be better served by a base register oth...
virtual bool requiresVirtualBaseRegisters(const MachineFunction &MF) const
Returns true if the target wants the LocalStackAllocation pass to be run and virtual base registers u...
Representation of each machine instruction.
Definition: MachineInstr.h:63
void initializeLocalStackSlotPassPass(PassRegistry &)
#define I(x, y, z)
Definition: MD5.cpp:58
virtual const TargetFrameLowering * getFrameLowering() const
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
INITIALIZE_PASS(LocalStackSlotPass, DEBUG_TYPE, "Local Stack Slot Allocation", false, false) bool LocalStackSlotPass
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:325
Array or nested array < SSP-buffer-size.
IRTranslator LLVM IR MI
char & LocalStackSlotAllocationID
LocalStackSlotAllocation - This pass assigns local frame indices to stack slots relative to one anoth...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
virtual void materializeFrameBaseRegister(MachineBasicBlock *MBB, unsigned BaseReg, int FrameIdx, int64_t Offset) const
Insert defining instruction(s) for BaseReg to be a pointer to FrameIdx before insertion point I...
static void AssignProtectedObjSet(const StackObjSet &UnassignedObjs, SmallSet< int, 16 > &ProtectedObjs, MachineFrameInfo &MFI, bool StackGrowsDown, int64_t &Offset, unsigned &MaxAlign, unsigned Skew)
AssignProtectedObjSet - Helper function to assign large stack objects (i.e., those required to be clo...
virtual const TargetRegisterClass * getPointerRegClass(const MachineFunction &MF, unsigned Kind=0) const
Returns a TargetRegisterClass used for pointer values.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164
void resize(size_type N)
Definition: SmallVector.h:343
virtual void resolveFrameIndex(MachineInstr &MI, unsigned BaseReg, int64_t Offset) const
Resolve a frame index operand of an instruction to reference the indicated base register plus offset ...