LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
LocalStackSlotAllocation.cpp
Go to the documentation of this file.
1 //===- LocalStackSlotAllocation.cpp - Pre-allocate locals to stack slots --===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass assigns local frame indices to stack slots relative to one another
11 // and allocates additional base registers to access them when the target
12 // estimates they are likely to be out of range of stack pointer and frame
13 // pointer relative addressing.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #define DEBUG_TYPE "localstackalloc"
18 #include "llvm/CodeGen/Passes.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SmallSet.h"
21 #include "llvm/ADT/Statistic.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/Intrinsics.h"
30 #include "llvm/IR/LLVMContext.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/Pass.h"
33 #include "llvm/Support/Debug.h"
38 
39 using namespace llvm;
40 
41 STATISTIC(NumAllocations, "Number of frame indices allocated into local block");
42 STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated");
43 STATISTIC(NumReplacements, "Number of frame indices references replaced");
44 
45 namespace {
46  class FrameRef {
47  MachineBasicBlock::iterator MI; // Instr referencing the frame
48  int64_t LocalOffset; // Local offset of the frame idx referenced
49  int FrameIdx; // The frame index
50  public:
51  FrameRef(MachineBasicBlock::iterator I, int64_t Offset, int Idx) :
52  MI(I), LocalOffset(Offset), FrameIdx(Idx) {}
53  bool operator<(const FrameRef &RHS) const {
54  return LocalOffset < RHS.LocalOffset;
55  }
56  MachineBasicBlock::iterator getMachineInstr() const { return MI; }
57  int64_t getLocalOffset() const { return LocalOffset; }
58  int getFrameIndex() const { return FrameIdx; }
59  };
60 
61  class LocalStackSlotPass: public MachineFunctionPass {
62  SmallVector<int64_t,16> LocalOffsets;
63 
64  void AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx, int64_t &Offset,
65  bool StackGrowsDown, unsigned &MaxAlign);
66  void calculateFrameObjectOffsets(MachineFunction &Fn);
67  bool insertFrameReferenceRegisters(MachineFunction &Fn);
68  public:
69  static char ID; // Pass identification, replacement for typeid
70  explicit LocalStackSlotPass() : MachineFunctionPass(ID) { }
71  bool runOnMachineFunction(MachineFunction &MF);
72 
73  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
74  AU.setPreservesCFG();
76  }
77 
78  private:
79  };
80 } // end anonymous namespace
81 
82 char LocalStackSlotPass::ID = 0;
84 INITIALIZE_PASS(LocalStackSlotPass, "localstackalloc",
85  "Local Stack Slot Allocation", false, false)
86 
87 bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) {
88  MachineFrameInfo *MFI = MF.getFrameInfo();
89  const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
90  unsigned LocalObjectCount = MFI->getObjectIndexEnd();
91 
92  // If the target doesn't want/need this pass, or if there are no locals
93  // to consider, early exit.
94  if (!TRI->requiresVirtualBaseRegisters(MF) || LocalObjectCount == 0)
95  return true;
96 
97  // Make sure we have enough space to store the local offsets.
98  LocalOffsets.resize(MFI->getObjectIndexEnd());
99 
100  // Lay out the local blob.
101  calculateFrameObjectOffsets(MF);
102 
103  // Insert virtual base registers to resolve frame index references.
104  bool UsedBaseRegs = insertFrameReferenceRegisters(MF);
105 
106  // Tell MFI whether any base registers were allocated. PEI will only
107  // want to use the local block allocations from this pass if there were any.
108  // Otherwise, PEI can do a bit better job of getting the alignment right
109  // without a hole at the start since it knows the alignment of the stack
110  // at the start of local allocation, and this pass doesn't.
111  MFI->setUseLocalStackAllocationBlock(UsedBaseRegs);
112 
113  return true;
114 }
115 
116 /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
118  int FrameIdx, int64_t &Offset,
119  bool StackGrowsDown,
120  unsigned &MaxAlign) {
121  // If the stack grows down, add the object size to find the lowest address.
122  if (StackGrowsDown)
123  Offset += MFI->getObjectSize(FrameIdx);
124 
125  unsigned Align = MFI->getObjectAlignment(FrameIdx);
126 
127  // If the alignment of this object is greater than that of the stack, then
128  // increase the stack alignment to match.
129  MaxAlign = std::max(MaxAlign, Align);
130 
131  // Adjust to alignment boundary.
132  Offset = (Offset + Align - 1) / Align * Align;
133 
134  int64_t LocalOffset = StackGrowsDown ? -Offset : Offset;
135  DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset "
136  << LocalOffset << "\n");
137  // Keep the offset available for base register allocation
138  LocalOffsets[FrameIdx] = LocalOffset;
139  // And tell MFI about it for PEI to use later
140  MFI->mapLocalFrameObject(FrameIdx, LocalOffset);
141 
142  if (!StackGrowsDown)
143  Offset += MFI->getObjectSize(FrameIdx);
144 
145  ++NumAllocations;
146 }
147 
148 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
149 /// abstract stack objects.
150 ///
151 void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) {
152  // Loop over all of the stack objects, assigning sequential addresses...
153  MachineFrameInfo *MFI = Fn.getFrameInfo();
154  const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering();
155  bool StackGrowsDown =
157  int64_t Offset = 0;
158  unsigned MaxAlign = 0;
159 
160  // Make sure that the stack protector comes before the local variables on the
161  // stack.
162  SmallSet<int, 16> LargeStackObjs;
163  if (MFI->getStackProtectorIndex() >= 0) {
164  AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), Offset,
165  StackGrowsDown, MaxAlign);
166 
167  // Assign large stack objects first.
168  for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
169  if (MFI->isDeadObjectIndex(i))
170  continue;
171  if (MFI->getStackProtectorIndex() == (int)i)
172  continue;
173  if (!MFI->MayNeedStackProtector(i))
174  continue;
175 
176  AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
177  LargeStackObjs.insert(i);
178  }
179  }
180 
181  // Then assign frame offsets to stack objects that are not used to spill
182  // callee saved registers.
183  for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
184  if (MFI->isDeadObjectIndex(i))
185  continue;
186  if (MFI->getStackProtectorIndex() == (int)i)
187  continue;
188  if (LargeStackObjs.count(i))
189  continue;
190 
191  AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
192  }
193 
194  // Remember how big this blob of stack space is
195  MFI->setLocalFrameSize(Offset);
196  MFI->setLocalFrameMaxAlign(MaxAlign);
197 }
198 
199 static inline bool
200 lookupCandidateBaseReg(int64_t BaseOffset,
201  int64_t FrameSizeAdjust,
202  int64_t LocalFrameOffset,
203  const MachineInstr *MI,
204  const TargetRegisterInfo *TRI) {
205  // Check if the relative offset from the where the base register references
206  // to the target address is in range for the instruction.
207  int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset;
208  return TRI->isFrameOffsetLegal(MI, Offset);
209 }
210 
211 bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) {
212  // Scan the function's instructions looking for frame index references.
213  // For each, ask the target if it wants a virtual base register for it
214  // based on what we can tell it about where the local will end up in the
215  // stack frame. If it wants one, re-use a suitable one we've previously
216  // allocated, or if there isn't one that fits the bill, allocate a new one
217  // and ask the target to create a defining instruction for it.
218  bool UsedBaseReg = false;
219 
220  MachineFrameInfo *MFI = Fn.getFrameInfo();
221  const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
222  const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering();
223  bool StackGrowsDown =
225 
226  // Collect all of the instructions in the block that reference
227  // a frame index. Also store the frame index referenced to ease later
228  // lookup. (For any insn that has more than one FI reference, we arbitrarily
229  // choose the first one).
230  SmallVector<FrameRef, 64> FrameReferenceInsns;
231 
232  for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
233  for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
234  MachineInstr *MI = I;
235 
236  // Debug value instructions can't be out of range, so they don't need
237  // any updates.
238  if (MI->isDebugValue())
239  continue;
240 
241  // For now, allocate the base register(s) within the basic block
242  // where they're used, and don't try to keep them around outside
243  // of that. It may be beneficial to try sharing them more broadly
244  // than that, but the increased register pressure makes that a
245  // tricky thing to balance. Investigate if re-materializing these
246  // becomes an issue.
247  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
248  // Consider replacing all frame index operands that reference
249  // an object allocated in the local block.
250  if (MI->getOperand(i).isFI()) {
251  // Don't try this with values not in the local block.
252  if (!MFI->isObjectPreAllocated(MI->getOperand(i).getIndex()))
253  break;
254  int Idx = MI->getOperand(i).getIndex();
255  int64_t LocalOffset = LocalOffsets[Idx];
256  if (!TRI->needsFrameBaseReg(MI, LocalOffset))
257  break;
258  FrameReferenceInsns.
259  push_back(FrameRef(MI, LocalOffset, Idx));
260  break;
261  }
262  }
263  }
264  }
265 
266  // Sort the frame references by local offset
267  array_pod_sort(FrameReferenceInsns.begin(), FrameReferenceInsns.end());
268 
269  MachineBasicBlock *Entry = Fn.begin();
270 
271  unsigned BaseReg = 0;
272  int64_t BaseOffset = 0;
273 
274  // Loop through the frame references and allocate for them as necessary.
275  for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) {
276  FrameRef &FR = FrameReferenceInsns[ref];
277  MachineBasicBlock::iterator I = FR.getMachineInstr();
278  MachineInstr *MI = I;
279  int64_t LocalOffset = FR.getLocalOffset();
280  int FrameIdx = FR.getFrameIndex();
281  assert(MFI->isObjectPreAllocated(FrameIdx) &&
282  "Only pre-allocated locals expected!");
283 
284  DEBUG(dbgs() << "Considering: " << *MI);
285 
286  unsigned idx = 0;
287  for (unsigned f = MI->getNumOperands(); idx != f; ++idx) {
288  if (!MI->getOperand(idx).isFI())
289  continue;
290 
291  if (FrameIdx == I->getOperand(idx).getIndex())
292  break;
293  }
294 
295  assert(idx < MI->getNumOperands() && "Cannot find FI operand");
296 
297  int64_t Offset = 0;
298  int64_t FrameSizeAdjust = StackGrowsDown ? MFI->getLocalFrameSize() : 0;
299 
300  DEBUG(dbgs() << " Replacing FI in: " << *MI);
301 
302  // If we have a suitable base register available, use it; otherwise
303  // create a new one. Note that any offset encoded in the
304  // instruction itself will be taken into account by the target,
305  // so we don't have to adjust for it here when reusing a base
306  // register.
307  if (UsedBaseReg && lookupCandidateBaseReg(BaseOffset, FrameSizeAdjust,
308  LocalOffset, MI, TRI)) {
309  DEBUG(dbgs() << " Reusing base register " << BaseReg << "\n");
310  // We found a register to reuse.
311  Offset = FrameSizeAdjust + LocalOffset - BaseOffset;
312  } else {
313  // No previously defined register was in range, so create a // new one.
314 
315  int64_t InstrOffset = TRI->getFrameIndexInstrOffset(MI, idx);
316 
317  int64_t PrevBaseOffset = BaseOffset;
318  BaseOffset = FrameSizeAdjust + LocalOffset + InstrOffset;
319 
320  // We'd like to avoid creating single-use virtual base registers.
321  // Because the FrameRefs are in sorted order, and we've already
322  // processed all FrameRefs before this one, just check whether or not
323  // the next FrameRef will be able to reuse this new register. If not,
324  // then don't bother creating it.
325  bool CanReuse = false;
326  for (int refn = ref + 1; refn < e; ++refn) {
327  FrameRef &FRN = FrameReferenceInsns[refn];
328  MachineBasicBlock::iterator J = FRN.getMachineInstr();
329  MachineInstr *MIN = J;
330 
331  CanReuse = lookupCandidateBaseReg(BaseOffset, FrameSizeAdjust,
332  FRN.getLocalOffset(), MIN, TRI);
333  break;
334  }
335 
336  if (!CanReuse) {
337  BaseOffset = PrevBaseOffset;
338  continue;
339  }
340 
341  const MachineFunction *MF = MI->getParent()->getParent();
342  const TargetRegisterClass *RC = TRI->getPointerRegClass(*MF);
343  BaseReg = Fn.getRegInfo().createVirtualRegister(RC);
344 
345  DEBUG(dbgs() << " Materializing base register " << BaseReg <<
346  " at frame local offset " << LocalOffset + InstrOffset << "\n");
347 
348  // Tell the target to insert the instruction to initialize
349  // the base register.
350  // MachineBasicBlock::iterator InsertionPt = Entry->begin();
351  TRI->materializeFrameBaseRegister(Entry, BaseReg, FrameIdx,
352  InstrOffset);
353 
354  // The base register already includes any offset specified
355  // by the instruction, so account for that so it doesn't get
356  // applied twice.
357  Offset = -InstrOffset;
358 
359  ++NumBaseRegisters;
360  UsedBaseReg = true;
361  }
362  assert(BaseReg != 0 && "Unable to allocate virtual base register!");
363 
364  // Modify the instruction to use the new base register rather
365  // than the frame index operand.
366  TRI->resolveFrameIndex(I, BaseReg, Offset);
367  DEBUG(dbgs() << "Resolved: " << *MI);
368 
369  ++NumReplacements;
370  }
371 
372  return UsedBaseReg;
373 }
const MachineFunction * getParent() const
void mapLocalFrameObject(int ObjectIndex, int64_t Offset)
mapLocalFrameObject - Map a frame index into the local object block
unsigned createVirtualRegister(const TargetRegisterClass *RegClass)
void operator<(const Optional< T > &X, const Optional< U > &Y)
Poison comparison between two Optional objects. Clients needs to explicitly compare the underlying va...
static bool lookupCandidateBaseReg(int64_t BaseOffset, int64_t FrameSizeAdjust, int64_t LocalFrameOffset, const MachineInstr *MI, const TargetRegisterInfo *TRI)
bool isObjectPreAllocated(int ObjectIdx) const
int64_t getLocalFrameSize() const
getLocalFrameSize - Get the size of the local object blob.
virtual int64_t getFrameIndexInstrOffset(const MachineInstr *MI, int Idx) const
void setLocalFrameSize(int64_t sz)
setLocalFrameSize - Set the size of the local object blob.
void setUseLocalStackAllocationBlock(bool v)
Abstract Stack Frame Information.
ID
LLVM Calling Convention Representation.
Definition: CallingConv.h:26
STATISTIC(NumAllocations,"Number of frame indices allocated into local block")
unsigned getNumOperands() const
Definition: MachineInstr.h:265
INITIALIZE_PASS(LocalStackSlotPass,"localstackalloc","Local Stack Slot Allocation", false, false) bool LocalStackSlotPass
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
void setLocalFrameMaxAlign(unsigned Align)
bool insert(const T &V)
Definition: SmallSet.h:59
virtual bool requiresVirtualBaseRegisters(const MachineFunction &MF) const
virtual void materializeFrameBaseRegister(MachineBasicBlock *MBB, unsigned BaseReg, int FrameIdx, int64_t Offset) const
virtual void resolveFrameIndex(MachineBasicBlock::iterator I, unsigned BaseReg, int64_t Offset) const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:119
bool isDebugValue() const
Definition: MachineInstr.h:639
bundle_iterator< MachineInstr, instr_iterator > iterator
void array_pod_sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:289
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:267
virtual const TargetFrameLowering * getFrameLowering() const
bool isDeadObjectIndex(int ObjectIdx) const
unsigned getObjectAlignment(int ObjectIdx) const
getObjectAlignment - Return the alignment of the specified stack object.
MachineFrameInfo * getFrameInfo()
void setPreservesCFG()
Definition: Pass.cpp:249
raw_ostream & dbgs()
dbgs - Return a circular-buffered debug stream.
Definition: Debug.cpp:101
static void AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx, bool StackGrowsDown, int64_t &Offset, unsigned &MaxAlign)
AdjustStackOffset - Helper function used to adjust the stack frame offset.
static cl::opt< AlignMode > Align(cl::desc("Load/store alignment support"), cl::Hidden, cl::init(DefaultAlign), cl::values(clEnumValN(DefaultAlign,"arm-default-align","Generate unaligned accesses only on hardware/OS ""combinations that are known to support them"), clEnumValN(StrictAlign,"arm-strict-align","Disallow all unaligned memory accesses"), clEnumValN(NoStrictAlign,"arm-no-strict-align","Allow unaligned memory accesses"), clEnumValEnd))
int getStackProtectorIndex() const
bool count(const T &V) const
count - Return true if the element is in the set.
Definition: SmallSet.h:48
StackDirection getStackGrowthDirection() const
virtual bool needsFrameBaseReg(MachineInstr *MI, int64_t Offset) const
virtual bool isFrameOffsetLegal(const MachineInstr *MI, int64_t Offset) const
MachineRegisterInfo & getRegInfo()
virtual void getAnalysisUsage(AnalysisUsage &AU) const
#define I(x, y, z)
Definition: MD5.cpp:54
const TargetMachine & getTarget() const
virtual const TargetRegisterInfo * getRegisterInfo() const
BasicBlockListType::iterator iterator
#define DEBUG(X)
Definition: Debug.h:97
int getObjectIndexEnd() const
char & LocalStackSlotAllocationID
virtual const TargetRegisterClass * getPointerRegClass(const MachineFunction &MF, unsigned Kind=0) const
int64_t getObjectSize(int ObjectIdx) const
bool MayNeedStackProtector(int ObjectIdx) const