Line data Source code
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 : #include "llvm/ADT/SetVector.h"
18 : #include "llvm/ADT/SmallSet.h"
19 : #include "llvm/ADT/SmallVector.h"
20 : #include "llvm/ADT/Statistic.h"
21 : #include "llvm/CodeGen/MachineBasicBlock.h"
22 : #include "llvm/CodeGen/MachineFrameInfo.h"
23 : #include "llvm/CodeGen/MachineFunction.h"
24 : #include "llvm/CodeGen/MachineFunctionPass.h"
25 : #include "llvm/CodeGen/MachineInstr.h"
26 : #include "llvm/CodeGen/MachineOperand.h"
27 : #include "llvm/CodeGen/MachineRegisterInfo.h"
28 : #include "llvm/CodeGen/TargetFrameLowering.h"
29 : #include "llvm/CodeGen/TargetOpcodes.h"
30 : #include "llvm/CodeGen/TargetRegisterInfo.h"
31 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
32 : #include "llvm/Pass.h"
33 : #include "llvm/Support/Debug.h"
34 : #include "llvm/Support/ErrorHandling.h"
35 : #include "llvm/Support/raw_ostream.h"
36 : #include <algorithm>
37 : #include <cassert>
38 : #include <cstdint>
39 : #include <tuple>
40 :
41 : using namespace llvm;
42 :
43 : #define DEBUG_TYPE "localstackalloc"
44 :
45 : STATISTIC(NumAllocations, "Number of frame indices allocated into local block");
46 : STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated");
47 : STATISTIC(NumReplacements, "Number of frame indices references replaced");
48 :
49 : namespace {
50 :
51 : class FrameRef {
52 : MachineBasicBlock::iterator MI; // Instr referencing the frame
53 : int64_t LocalOffset; // Local offset of the frame idx referenced
54 : int FrameIdx; // The frame index
55 :
56 : // Order reference instruction appears in program. Used to ensure
57 : // deterministic order when multiple instructions may reference the same
58 : // location.
59 : unsigned Order;
60 :
61 : public:
62 189 : FrameRef(MachineInstr *I, int64_t Offset, int Idx, unsigned Ord) :
63 189 : MI(I), LocalOffset(Offset), FrameIdx(Idx), Order(Ord) {}
64 :
65 : bool operator<(const FrameRef &RHS) const {
66 0 : return std::tie(LocalOffset, FrameIdx, Order) <
67 0 : std::tie(RHS.LocalOffset, RHS.FrameIdx, RHS.Order);
68 : }
69 :
70 0 : MachineBasicBlock::iterator getMachineInstr() const { return MI; }
71 0 : int64_t getLocalOffset() const { return LocalOffset; }
72 0 : int getFrameIndex() const { return FrameIdx; }
73 : };
74 :
75 : class LocalStackSlotPass: public MachineFunctionPass {
76 : SmallVector<int64_t, 16> LocalOffsets;
77 :
78 : /// StackObjSet - A set of stack object indexes
79 : using StackObjSet = SmallSetVector<int, 8>;
80 :
81 : void AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx, int64_t &Offset,
82 : bool StackGrowsDown, unsigned &MaxAlign);
83 : void AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
84 : SmallSet<int, 16> &ProtectedObjs,
85 : MachineFrameInfo &MFI, bool StackGrowsDown,
86 : int64_t &Offset, unsigned &MaxAlign);
87 : void calculateFrameObjectOffsets(MachineFunction &Fn);
88 : bool insertFrameReferenceRegisters(MachineFunction &Fn);
89 :
90 : public:
91 : static char ID; // Pass identification, replacement for typeid
92 :
93 27453 : explicit LocalStackSlotPass() : MachineFunctionPass(ID) {
94 27453 : initializeLocalStackSlotPassPass(*PassRegistry::getPassRegistry());
95 27453 : }
96 :
97 : bool runOnMachineFunction(MachineFunction &MF) override;
98 :
99 27260 : void getAnalysisUsage(AnalysisUsage &AU) const override {
100 27260 : AU.setPreservesCFG();
101 27260 : MachineFunctionPass::getAnalysisUsage(AU);
102 27260 : }
103 : };
104 :
105 : } // end anonymous namespace
106 :
107 : char LocalStackSlotPass::ID = 0;
108 :
109 : char &llvm::LocalStackSlotAllocationID = LocalStackSlotPass::ID;
110 112600 : INITIALIZE_PASS(LocalStackSlotPass, DEBUG_TYPE,
111 : "Local Stack Slot Allocation", false, false)
112 :
113 405880 : bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) {
114 405880 : MachineFrameInfo &MFI = MF.getFrameInfo();
115 405880 : const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
116 : unsigned LocalObjectCount = MFI.getObjectIndexEnd();
117 :
118 : // If the target doesn't want/need this pass, or if there are no locals
119 : // to consider, early exit.
120 405880 : if (!TRI->requiresVirtualBaseRegisters(MF) || LocalObjectCount == 0)
121 : return true;
122 :
123 : // Make sure we have enough space to store the local offsets.
124 6272 : LocalOffsets.resize(MFI.getObjectIndexEnd());
125 :
126 : // Lay out the local blob.
127 3136 : calculateFrameObjectOffsets(MF);
128 :
129 : // Insert virtual base registers to resolve frame index references.
130 3136 : bool UsedBaseRegs = insertFrameReferenceRegisters(MF);
131 :
132 : // Tell MFI whether any base registers were allocated. PEI will only
133 : // want to use the local block allocations from this pass if there were any.
134 : // Otherwise, PEI can do a bit better job of getting the alignment right
135 : // without a hole at the start since it knows the alignment of the stack
136 : // at the start of local allocation, and this pass doesn't.
137 : MFI.setUseLocalStackAllocationBlock(UsedBaseRegs);
138 :
139 3136 : return true;
140 : }
141 :
142 : /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
143 6074 : void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo &MFI,
144 : int FrameIdx, int64_t &Offset,
145 : bool StackGrowsDown,
146 : unsigned &MaxAlign) {
147 : // If the stack grows down, add the object size to find the lowest address.
148 6074 : if (StackGrowsDown)
149 5402 : Offset += MFI.getObjectSize(FrameIdx);
150 :
151 6074 : unsigned Align = MFI.getObjectAlignment(FrameIdx);
152 :
153 : // If the alignment of this object is greater than that of the stack, then
154 : // increase the stack alignment to match.
155 6074 : MaxAlign = std::max(MaxAlign, Align);
156 :
157 : // Adjust to alignment boundary.
158 6074 : Offset = (Offset + Align - 1) / Align * Align;
159 :
160 6074 : int64_t LocalOffset = StackGrowsDown ? -Offset : Offset;
161 : LLVM_DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset "
162 : << LocalOffset << "\n");
163 : // Keep the offset available for base register allocation
164 12148 : LocalOffsets[FrameIdx] = LocalOffset;
165 : // And tell MFI about it for PEI to use later
166 : MFI.mapLocalFrameObject(FrameIdx, LocalOffset);
167 :
168 6074 : if (!StackGrowsDown)
169 672 : Offset += MFI.getObjectSize(FrameIdx);
170 :
171 : ++NumAllocations;
172 6074 : }
173 :
174 : /// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
175 : /// those required to be close to the Stack Protector) to stack offsets.
176 174 : void LocalStackSlotPass::AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
177 : SmallSet<int, 16> &ProtectedObjs,
178 : MachineFrameInfo &MFI,
179 : bool StackGrowsDown, int64_t &Offset,
180 : unsigned &MaxAlign) {
181 82 : for (StackObjSet::const_iterator I = UnassignedObjs.begin(),
182 256 : E = UnassignedObjs.end(); I != E; ++I) {
183 82 : int i = *I;
184 82 : AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
185 82 : ProtectedObjs.insert(i);
186 : }
187 174 : }
188 :
189 : /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
190 : /// abstract stack objects.
191 3136 : void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) {
192 : // Loop over all of the stack objects, assigning sequential addresses...
193 3136 : MachineFrameInfo &MFI = Fn.getFrameInfo();
194 3136 : const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
195 : bool StackGrowsDown =
196 3136 : TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
197 3136 : int64_t Offset = 0;
198 3136 : unsigned MaxAlign = 0;
199 :
200 : // Make sure that the stack protector comes before the local variables on the
201 : // stack.
202 3136 : SmallSet<int, 16> ProtectedObjs;
203 3136 : if (MFI.getStackProtectorIndex() >= 0) {
204 : StackObjSet LargeArrayObjs;
205 : StackObjSet SmallArrayObjs;
206 : StackObjSet AddrOfObjs;
207 :
208 58 : AdjustStackOffset(MFI, MFI.getStackProtectorIndex(), Offset,
209 : StackGrowsDown, MaxAlign);
210 :
211 : // Assign large stack objects first.
212 219 : for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
213 322 : if (MFI.isDeadObjectIndex(i))
214 : continue;
215 161 : if (MFI.getStackProtectorIndex() == (int)i)
216 : continue;
217 :
218 103 : switch (MFI.getObjectSSPLayout(i)) {
219 : case MachineFrameInfo::SSPLK_None:
220 : continue;
221 10 : case MachineFrameInfo::SSPLK_SmallArray:
222 10 : SmallArrayObjs.insert(i);
223 10 : continue;
224 6 : case MachineFrameInfo::SSPLK_AddrOf:
225 6 : AddrOfObjs.insert(i);
226 6 : continue;
227 66 : case MachineFrameInfo::SSPLK_LargeArray:
228 66 : LargeArrayObjs.insert(i);
229 66 : continue;
230 : }
231 0 : llvm_unreachable("Unexpected SSPLayoutKind.");
232 : }
233 :
234 58 : AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
235 : Offset, MaxAlign);
236 58 : AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
237 : Offset, MaxAlign);
238 58 : AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
239 : Offset, MaxAlign);
240 : }
241 :
242 : // Then assign frame offsets to stack objects that are not used to spill
243 : // callee saved registers.
244 9234 : for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
245 12196 : if (MFI.isDeadObjectIndex(i))
246 : continue;
247 6074 : if (MFI.getStackProtectorIndex() == (int)i)
248 : continue;
249 6016 : if (ProtectedObjs.count(i))
250 : continue;
251 :
252 5934 : AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
253 : }
254 :
255 : // Remember how big this blob of stack space is
256 3136 : MFI.setLocalFrameSize(Offset);
257 3136 : MFI.setLocalFrameMaxAlign(MaxAlign);
258 3136 : }
259 :
260 : static inline bool
261 : lookupCandidateBaseReg(unsigned BaseReg,
262 : int64_t BaseOffset,
263 : int64_t FrameSizeAdjust,
264 : int64_t LocalFrameOffset,
265 : const MachineInstr &MI,
266 : const TargetRegisterInfo *TRI) {
267 : // Check if the relative offset from the where the base register references
268 : // to the target address is in range for the instruction.
269 146 : int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset;
270 131 : return TRI->isFrameOffsetLegal(&MI, BaseReg, Offset);
271 : }
272 :
273 3136 : bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) {
274 : // Scan the function's instructions looking for frame index references.
275 : // For each, ask the target if it wants a virtual base register for it
276 : // based on what we can tell it about where the local will end up in the
277 : // stack frame. If it wants one, re-use a suitable one we've previously
278 : // allocated, or if there isn't one that fits the bill, allocate a new one
279 : // and ask the target to create a defining instruction for it.
280 : bool UsedBaseReg = false;
281 :
282 3136 : MachineFrameInfo &MFI = Fn.getFrameInfo();
283 3136 : const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
284 3136 : const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
285 : bool StackGrowsDown =
286 3136 : TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
287 :
288 : // Collect all of the instructions in the block that reference
289 : // a frame index. Also store the frame index referenced to ease later
290 : // lookup. (For any insn that has more than one FI reference, we arbitrarily
291 : // choose the first one).
292 3136 : SmallVector<FrameRef, 64> FrameReferenceInsns;
293 :
294 : unsigned Order = 0;
295 :
296 8649 : for (MachineBasicBlock &BB : Fn) {
297 110919 : for (MachineInstr &MI : BB) {
298 : // Debug value, stackmap and patchpoint instructions can't be out of
299 : // range, so they don't need any updates.
300 105390 : if (MI.isDebugInstr() || MI.getOpcode() == TargetOpcode::STATEPOINT ||
301 105380 : MI.getOpcode() == TargetOpcode::STACKMAP ||
302 : MI.getOpcode() == TargetOpcode::PATCHPOINT)
303 : continue;
304 :
305 : // For now, allocate the base register(s) within the basic block
306 : // where they're used, and don't try to keep them around outside
307 : // of that. It may be beneficial to try sharing them more broadly
308 : // than that, but the increased register pressure makes that a
309 : // tricky thing to balance. Investigate if re-materializing these
310 : // becomes an issue.
311 468768 : for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
312 : // Consider replacing all frame index operands that reference
313 : // an object allocated in the local block.
314 762374 : if (MI.getOperand(i).isFI()) {
315 : // Don't try this with values not in the local block.
316 35590 : if (!MFI.isObjectPreAllocated(MI.getOperand(i).getIndex()))
317 : break;
318 : int Idx = MI.getOperand(i).getIndex();
319 17339 : int64_t LocalOffset = LocalOffsets[Idx];
320 17339 : if (!TRI->needsFrameBaseReg(&MI, LocalOffset))
321 : break;
322 378 : FrameReferenceInsns.push_back(FrameRef(&MI, LocalOffset, Idx, Order++));
323 189 : break;
324 : }
325 : }
326 : }
327 : }
328 :
329 : // Sort the frame references by local offset.
330 : // Use frame index as a tie-breaker in case MI's have the same offset.
331 3136 : llvm::sort(FrameReferenceInsns);
332 :
333 : MachineBasicBlock *Entry = &Fn.front();
334 :
335 : unsigned BaseReg = 0;
336 : int64_t BaseOffset = 0;
337 :
338 : // Loop through the frame references and allocate for them as necessary.
339 3325 : for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) {
340 189 : FrameRef &FR = FrameReferenceInsns[ref];
341 : MachineInstr &MI = *FR.getMachineInstr();
342 189 : int64_t LocalOffset = FR.getLocalOffset();
343 189 : int FrameIdx = FR.getFrameIndex();
344 : assert(MFI.isObjectPreAllocated(FrameIdx) &&
345 : "Only pre-allocated locals expected!");
346 :
347 : LLVM_DEBUG(dbgs() << "Considering: " << MI);
348 :
349 : unsigned idx = 0;
350 479 : for (unsigned f = MI.getNumOperands(); idx != f; ++idx) {
351 958 : if (!MI.getOperand(idx).isFI())
352 : continue;
353 :
354 189 : if (FrameIdx == MI.getOperand(idx).getIndex())
355 : break;
356 : }
357 :
358 : assert(idx < MI.getNumOperands() && "Cannot find FI operand");
359 :
360 : int64_t Offset = 0;
361 189 : int64_t FrameSizeAdjust = StackGrowsDown ? MFI.getLocalFrameSize() : 0;
362 :
363 : LLVM_DEBUG(dbgs() << " Replacing FI in: " << MI);
364 :
365 : // If we have a suitable base register available, use it; otherwise
366 : // create a new one. Note that any offset encoded in the
367 : // instruction itself will be taken into account by the target,
368 : // so we don't have to adjust for it here when reusing a base
369 : // register.
370 320 : if (UsedBaseReg &&
371 : lookupCandidateBaseReg(BaseReg, BaseOffset, FrameSizeAdjust,
372 : LocalOffset, MI, TRI)) {
373 : LLVM_DEBUG(dbgs() << " Reusing base register " << BaseReg << "\n");
374 : // We found a register to reuse.
375 : Offset = FrameSizeAdjust + LocalOffset - BaseOffset;
376 : } else {
377 : // No previously defined register was in range, so create a new one.
378 58 : int64_t InstrOffset = TRI->getFrameIndexInstrOffset(&MI, idx);
379 :
380 : int64_t PrevBaseOffset = BaseOffset;
381 58 : BaseOffset = FrameSizeAdjust + LocalOffset + InstrOffset;
382 :
383 : // We'd like to avoid creating single-use virtual base registers.
384 : // Because the FrameRefs are in sorted order, and we've already
385 : // processed all FrameRefs before this one, just check whether or not
386 : // the next FrameRef will be able to reuse this new register. If not,
387 : // then don't bother creating it.
388 73 : if (ref + 1 >= e ||
389 15 : !lookupCandidateBaseReg(
390 : BaseReg, BaseOffset, FrameSizeAdjust,
391 : FrameReferenceInsns[ref + 1].getLocalOffset(),
392 15 : *FrameReferenceInsns[ref + 1].getMachineInstr(), TRI)) {
393 : BaseOffset = PrevBaseOffset;
394 48 : continue;
395 : }
396 :
397 : const MachineFunction *MF = MI.getMF();
398 10 : const TargetRegisterClass *RC = TRI->getPointerRegClass(*MF);
399 20 : BaseReg = Fn.getRegInfo().createVirtualRegister(RC);
400 :
401 : LLVM_DEBUG(dbgs() << " Materializing base register " << BaseReg
402 : << " at frame local offset "
403 : << LocalOffset + InstrOffset << "\n");
404 :
405 : // Tell the target to insert the instruction to initialize
406 : // the base register.
407 : // MachineBasicBlock::iterator InsertionPt = Entry->begin();
408 10 : TRI->materializeFrameBaseRegister(Entry, BaseReg, FrameIdx,
409 10 : InstrOffset);
410 :
411 : // The base register already includes any offset specified
412 : // by the instruction, so account for that so it doesn't get
413 : // applied twice.
414 10 : Offset = -InstrOffset;
415 :
416 : ++NumBaseRegisters;
417 : UsedBaseReg = true;
418 : }
419 : assert(BaseReg != 0 && "Unable to allocate virtual base register!");
420 :
421 : // Modify the instruction to use the new base register rather
422 : // than the frame index operand.
423 141 : TRI->resolveFrameIndex(MI, BaseReg, Offset);
424 : LLVM_DEBUG(dbgs() << "Resolved: " << MI);
425 :
426 : ++NumReplacements;
427 : }
428 :
429 3136 : return UsedBaseReg;
430 : }
|
