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