File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/LocalStackSlotAllocation.cpp |
Warning: | line 415, column 7 Value stored to 'BaseReg' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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" |
20 | #include "llvm/CodeGen/MachineBasicBlock.h" |
21 | #include "llvm/CodeGen/MachineFrameInfo.h" |
22 | #include "llvm/CodeGen/MachineFunction.h" |
23 | #include "llvm/CodeGen/MachineFunctionPass.h" |
24 | #include "llvm/CodeGen/MachineInstr.h" |
25 | #include "llvm/CodeGen/MachineOperand.h" |
26 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
27 | #include "llvm/CodeGen/TargetFrameLowering.h" |
28 | #include "llvm/CodeGen/TargetOpcodes.h" |
29 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
30 | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
31 | #include "llvm/InitializePasses.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" "localstackalloc" |
44 | |
45 | STATISTIC(NumAllocations, "Number of frame indices allocated into local block")static llvm::Statistic NumAllocations = {"localstackalloc", "NumAllocations" , "Number of frame indices allocated into local block"}; |
46 | STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated")static llvm::Statistic NumBaseRegisters = {"localstackalloc", "NumBaseRegisters", "Number of virtual frame base registers allocated" }; |
47 | STATISTIC(NumReplacements, "Number of frame indices references replaced")static llvm::Statistic NumReplacements = {"localstackalloc", "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 | FrameRef(MachineInstr *I, int64_t Offset, int Idx, unsigned Ord) : |
63 | MI(I), LocalOffset(Offset), FrameIdx(Idx), Order(Ord) {} |
64 | |
65 | bool operator<(const FrameRef &RHS) const { |
66 | return std::tie(LocalOffset, FrameIdx, Order) < |
67 | std::tie(RHS.LocalOffset, RHS.FrameIdx, RHS.Order); |
68 | } |
69 | |
70 | MachineBasicBlock::iterator getMachineInstr() const { return MI; } |
71 | int64_t getLocalOffset() const { return LocalOffset; } |
72 | 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, Align &MaxAlign); |
83 | void AssignProtectedObjSet(const StackObjSet &UnassignedObjs, |
84 | SmallSet<int, 16> &ProtectedObjs, |
85 | MachineFrameInfo &MFI, bool StackGrowsDown, |
86 | int64_t &Offset, Align &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 | explicit LocalStackSlotPass() : MachineFunctionPass(ID) { |
94 | initializeLocalStackSlotPassPass(*PassRegistry::getPassRegistry()); |
95 | } |
96 | |
97 | bool runOnMachineFunction(MachineFunction &MF) override; |
98 | |
99 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
100 | AU.setPreservesCFG(); |
101 | MachineFunctionPass::getAnalysisUsage(AU); |
102 | } |
103 | }; |
104 | |
105 | } // end anonymous namespace |
106 | |
107 | char LocalStackSlotPass::ID = 0; |
108 | |
109 | char &llvm::LocalStackSlotAllocationID = LocalStackSlotPass::ID; |
110 | INITIALIZE_PASS(LocalStackSlotPass, DEBUG_TYPE,static void *initializeLocalStackSlotPassPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "Local Stack Slot Allocation" , "localstackalloc", &LocalStackSlotPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<LocalStackSlotPass>), false, false); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeLocalStackSlotPassPassFlag; void llvm::initializeLocalStackSlotPassPass (PassRegistry &Registry) { llvm::call_once(InitializeLocalStackSlotPassPassFlag , initializeLocalStackSlotPassPassOnce, std::ref(Registry)); } |
111 | "Local Stack Slot Allocation", false, false)static void *initializeLocalStackSlotPassPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "Local Stack Slot Allocation" , "localstackalloc", &LocalStackSlotPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<LocalStackSlotPass>), false, false); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeLocalStackSlotPassPassFlag; void llvm::initializeLocalStackSlotPassPass (PassRegistry &Registry) { llvm::call_once(InitializeLocalStackSlotPassPassFlag , initializeLocalStackSlotPassPassOnce, std::ref(Registry)); } |
112 | |
113 | bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) { |
114 | MachineFrameInfo &MFI = MF.getFrameInfo(); |
115 | 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 | if (LocalObjectCount == 0 || !TRI->requiresVirtualBaseRegisters(MF)) |
121 | return true; |
122 | |
123 | // Make sure we have enough space to store the local offsets. |
124 | LocalOffsets.resize(MFI.getObjectIndexEnd()); |
125 | |
126 | // Lay out the local blob. |
127 | calculateFrameObjectOffsets(MF); |
128 | |
129 | // Insert virtual base registers to resolve frame index references. |
130 | 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 | return true; |
140 | } |
141 | |
142 | /// AdjustStackOffset - Helper function used to adjust the stack frame offset. |
143 | void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx, |
144 | int64_t &Offset, bool StackGrowsDown, |
145 | Align &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 | Align Alignment = MFI.getObjectAlign(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, Alignment); |
155 | |
156 | // Adjust to alignment boundary. |
157 | Offset = alignTo(Offset, Alignment); |
158 | |
159 | int64_t LocalOffset = StackGrowsDown ? -Offset : Offset; |
160 | LLVM_DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset "do { } while (false) |
161 | << LocalOffset << "\n")do { } while (false); |
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( |
176 | const StackObjSet &UnassignedObjs, SmallSet<int, 16> &ProtectedObjs, |
177 | MachineFrameInfo &MFI, bool StackGrowsDown, int64_t &Offset, |
178 | Align &MaxAlign) { |
179 | for (int i : UnassignedObjs) { |
180 | AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign); |
181 | ProtectedObjs.insert(i); |
182 | } |
183 | } |
184 | |
185 | /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the |
186 | /// abstract stack objects. |
187 | void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { |
188 | // Loop over all of the stack objects, assigning sequential addresses... |
189 | MachineFrameInfo &MFI = Fn.getFrameInfo(); |
190 | const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering(); |
191 | bool StackGrowsDown = |
192 | TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; |
193 | int64_t Offset = 0; |
194 | Align MaxAlign; |
195 | |
196 | // Make sure that the stack protector comes before the local variables on the |
197 | // stack. |
198 | SmallSet<int, 16> ProtectedObjs; |
199 | if (MFI.hasStackProtectorIndex()) { |
200 | int StackProtectorFI = MFI.getStackProtectorIndex(); |
201 | |
202 | // We need to make sure we didn't pre-allocate the stack protector when |
203 | // doing this. |
204 | // If we already have a stack protector, this will re-assign it to a slot |
205 | // that is **not** covering the protected objects. |
206 | assert(!MFI.isObjectPreAllocated(StackProtectorFI) &&((void)0) |
207 | "Stack protector pre-allocated in LocalStackSlotAllocation")((void)0); |
208 | |
209 | StackObjSet LargeArrayObjs; |
210 | StackObjSet SmallArrayObjs; |
211 | StackObjSet AddrOfObjs; |
212 | |
213 | AdjustStackOffset(MFI, StackProtectorFI, Offset, StackGrowsDown, MaxAlign); |
214 | |
215 | // Assign large stack objects first. |
216 | for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) { |
217 | if (MFI.isDeadObjectIndex(i)) |
218 | continue; |
219 | if (StackProtectorFI == (int)i) |
220 | continue; |
221 | if (!TFI.isStackIdSafeForLocalArea(MFI.getStackID(i))) |
222 | continue; |
223 | |
224 | switch (MFI.getObjectSSPLayout(i)) { |
225 | case MachineFrameInfo::SSPLK_None: |
226 | continue; |
227 | case MachineFrameInfo::SSPLK_SmallArray: |
228 | SmallArrayObjs.insert(i); |
229 | continue; |
230 | case MachineFrameInfo::SSPLK_AddrOf: |
231 | AddrOfObjs.insert(i); |
232 | continue; |
233 | case MachineFrameInfo::SSPLK_LargeArray: |
234 | LargeArrayObjs.insert(i); |
235 | continue; |
236 | } |
237 | llvm_unreachable("Unexpected SSPLayoutKind.")__builtin_unreachable(); |
238 | } |
239 | |
240 | AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown, |
241 | Offset, MaxAlign); |
242 | AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown, |
243 | Offset, MaxAlign); |
244 | AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown, |
245 | Offset, MaxAlign); |
246 | } |
247 | |
248 | // Then assign frame offsets to stack objects that are not used to spill |
249 | // callee saved registers. |
250 | for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) { |
251 | if (MFI.isDeadObjectIndex(i)) |
252 | continue; |
253 | if (MFI.getStackProtectorIndex() == (int)i) |
254 | continue; |
255 | if (ProtectedObjs.count(i)) |
256 | continue; |
257 | if (!TFI.isStackIdSafeForLocalArea(MFI.getStackID(i))) |
258 | continue; |
259 | |
260 | AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign); |
261 | } |
262 | |
263 | // Remember how big this blob of stack space is |
264 | MFI.setLocalFrameSize(Offset); |
265 | MFI.setLocalFrameMaxAlign(MaxAlign); |
266 | } |
267 | |
268 | static inline bool |
269 | lookupCandidateBaseReg(unsigned BaseReg, |
270 | int64_t BaseOffset, |
271 | int64_t FrameSizeAdjust, |
272 | int64_t LocalFrameOffset, |
273 | const MachineInstr &MI, |
274 | const TargetRegisterInfo *TRI) { |
275 | // Check if the relative offset from the where the base register references |
276 | // to the target address is in range for the instruction. |
277 | int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset; |
278 | return TRI->isFrameOffsetLegal(&MI, BaseReg, Offset); |
279 | } |
280 | |
281 | bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { |
282 | // Scan the function's instructions looking for frame index references. |
283 | // For each, ask the target if it wants a virtual base register for it |
284 | // based on what we can tell it about where the local will end up in the |
285 | // stack frame. If it wants one, re-use a suitable one we've previously |
286 | // allocated, or if there isn't one that fits the bill, allocate a new one |
287 | // and ask the target to create a defining instruction for it. |
288 | bool UsedBaseReg = false; |
289 | |
290 | MachineFrameInfo &MFI = Fn.getFrameInfo(); |
291 | const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo(); |
292 | const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering(); |
293 | bool StackGrowsDown = |
294 | TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; |
295 | |
296 | // Collect all of the instructions in the block that reference |
297 | // a frame index. Also store the frame index referenced to ease later |
298 | // lookup. (For any insn that has more than one FI reference, we arbitrarily |
299 | // choose the first one). |
300 | SmallVector<FrameRef, 64> FrameReferenceInsns; |
301 | |
302 | unsigned Order = 0; |
303 | |
304 | for (MachineBasicBlock &BB : Fn) { |
305 | for (MachineInstr &MI : BB) { |
306 | // Debug value, stackmap and patchpoint instructions can't be out of |
307 | // range, so they don't need any updates. |
308 | if (MI.isDebugInstr() || MI.getOpcode() == TargetOpcode::STATEPOINT || |
309 | MI.getOpcode() == TargetOpcode::STACKMAP || |
310 | MI.getOpcode() == TargetOpcode::PATCHPOINT) |
311 | continue; |
312 | |
313 | // For now, allocate the base register(s) within the basic block |
314 | // where they're used, and don't try to keep them around outside |
315 | // of that. It may be beneficial to try sharing them more broadly |
316 | // than that, but the increased register pressure makes that a |
317 | // tricky thing to balance. Investigate if re-materializing these |
318 | // becomes an issue. |
319 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
320 | // Consider replacing all frame index operands that reference |
321 | // an object allocated in the local block. |
322 | if (MI.getOperand(i).isFI()) { |
323 | // Don't try this with values not in the local block. |
324 | if (!MFI.isObjectPreAllocated(MI.getOperand(i).getIndex())) |
325 | break; |
326 | int Idx = MI.getOperand(i).getIndex(); |
327 | int64_t LocalOffset = LocalOffsets[Idx]; |
328 | if (!TRI->needsFrameBaseReg(&MI, LocalOffset)) |
329 | break; |
330 | FrameReferenceInsns.push_back(FrameRef(&MI, LocalOffset, Idx, Order++)); |
331 | break; |
332 | } |
333 | } |
334 | } |
335 | } |
336 | |
337 | // Sort the frame references by local offset. |
338 | // Use frame index as a tie-breaker in case MI's have the same offset. |
339 | llvm::sort(FrameReferenceInsns); |
340 | |
341 | MachineBasicBlock *Entry = &Fn.front(); |
342 | |
343 | unsigned BaseReg = 0; |
344 | int64_t BaseOffset = 0; |
345 | |
346 | // Loop through the frame references and allocate for them as necessary. |
347 | for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) { |
348 | FrameRef &FR = FrameReferenceInsns[ref]; |
349 | MachineInstr &MI = *FR.getMachineInstr(); |
350 | int64_t LocalOffset = FR.getLocalOffset(); |
351 | int FrameIdx = FR.getFrameIndex(); |
352 | assert(MFI.isObjectPreAllocated(FrameIdx) &&((void)0) |
353 | "Only pre-allocated locals expected!")((void)0); |
354 | |
355 | // We need to keep the references to the stack protector slot through frame |
356 | // index operands so that it gets resolved by PEI rather than this pass. |
357 | // This avoids accesses to the stack protector though virtual base |
358 | // registers, and forces PEI to address it using fp/sp/bp. |
359 | if (MFI.hasStackProtectorIndex() && |
360 | FrameIdx == MFI.getStackProtectorIndex()) |
361 | continue; |
362 | |
363 | LLVM_DEBUG(dbgs() << "Considering: " << MI)do { } while (false); |
364 | |
365 | unsigned idx = 0; |
366 | for (unsigned f = MI.getNumOperands(); idx != f; ++idx) { |
367 | if (!MI.getOperand(idx).isFI()) |
368 | continue; |
369 | |
370 | if (FrameIdx == MI.getOperand(idx).getIndex()) |
371 | break; |
372 | } |
373 | |
374 | assert(idx < MI.getNumOperands() && "Cannot find FI operand")((void)0); |
375 | |
376 | int64_t Offset = 0; |
377 | int64_t FrameSizeAdjust = StackGrowsDown ? MFI.getLocalFrameSize() : 0; |
378 | |
379 | LLVM_DEBUG(dbgs() << " Replacing FI in: " << MI)do { } while (false); |
380 | |
381 | // If we have a suitable base register available, use it; otherwise |
382 | // create a new one. Note that any offset encoded in the |
383 | // instruction itself will be taken into account by the target, |
384 | // so we don't have to adjust for it here when reusing a base |
385 | // register. |
386 | if (UsedBaseReg && |
387 | lookupCandidateBaseReg(BaseReg, BaseOffset, FrameSizeAdjust, |
388 | LocalOffset, MI, TRI)) { |
389 | LLVM_DEBUG(dbgs() << " Reusing base register " << BaseReg << "\n")do { } while (false); |
390 | // We found a register to reuse. |
391 | Offset = FrameSizeAdjust + LocalOffset - BaseOffset; |
392 | } else { |
393 | // No previously defined register was in range, so create a new one. |
394 | int64_t InstrOffset = TRI->getFrameIndexInstrOffset(&MI, idx); |
395 | |
396 | int64_t PrevBaseOffset = BaseOffset; |
397 | BaseOffset = FrameSizeAdjust + LocalOffset + InstrOffset; |
398 | |
399 | // We'd like to avoid creating single-use virtual base registers. |
400 | // Because the FrameRefs are in sorted order, and we've already |
401 | // processed all FrameRefs before this one, just check whether or not |
402 | // the next FrameRef will be able to reuse this new register. If not, |
403 | // then don't bother creating it. |
404 | if (ref + 1 >= e || |
405 | !lookupCandidateBaseReg( |
406 | BaseReg, BaseOffset, FrameSizeAdjust, |
407 | FrameReferenceInsns[ref + 1].getLocalOffset(), |
408 | *FrameReferenceInsns[ref + 1].getMachineInstr(), TRI)) { |
409 | BaseOffset = PrevBaseOffset; |
410 | continue; |
411 | } |
412 | |
413 | const MachineFunction *MF = MI.getMF(); |
414 | const TargetRegisterClass *RC = TRI->getPointerRegClass(*MF); |
415 | BaseReg = Fn.getRegInfo().createVirtualRegister(RC); |
Value stored to 'BaseReg' is never read | |
416 | |
417 | LLVM_DEBUG(dbgs() << " Materializing base register"do { } while (false) |
418 | << " at frame local offset "do { } while (false) |
419 | << LocalOffset + InstrOffset)do { } while (false); |
420 | |
421 | // Tell the target to insert the instruction to initialize |
422 | // the base register. |
423 | // MachineBasicBlock::iterator InsertionPt = Entry->begin(); |
424 | BaseReg = TRI->materializeFrameBaseRegister(Entry, FrameIdx, InstrOffset); |
425 | |
426 | LLVM_DEBUG(dbgs() << " into " << printReg(BaseReg, TRI) << '\n')do { } while (false); |
427 | |
428 | // The base register already includes any offset specified |
429 | // by the instruction, so account for that so it doesn't get |
430 | // applied twice. |
431 | Offset = -InstrOffset; |
432 | |
433 | ++NumBaseRegisters; |
434 | UsedBaseReg = true; |
435 | } |
436 | assert(BaseReg != 0 && "Unable to allocate virtual base register!")((void)0); |
437 | |
438 | // Modify the instruction to use the new base register rather |
439 | // than the frame index operand. |
440 | TRI->resolveFrameIndex(MI, BaseReg, Offset); |
441 | LLVM_DEBUG(dbgs() << "Resolved: " << MI)do { } while (false); |
442 | |
443 | ++NumReplacements; |
444 | } |
445 | |
446 | return UsedBaseReg; |
447 | } |