xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/LocalStackSlotAllocation.cpp (revision c364ccf9ce2d1d0fc24247aa771cf52e5dfb532a)
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"
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      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, 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      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,
111                  "Local Stack Slot Allocation", false, false)
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 (!TRI->requiresVirtualBaseRegisters(MF) || LocalObjectCount == 0)
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,
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    if (StackGrowsDown)
149      Offset += MFI.getObjectSize(FrameIdx);
150  
151    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    MaxAlign = std::max(MaxAlign, Align);
156  
157    // Adjust to alignment boundary.
158    Offset = (Offset + Align - 1) / Align * Align;
159  
160    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    LocalOffsets[FrameIdx] = LocalOffset;
165    // And tell MFI about it for PEI to use later
166    MFI.mapLocalFrameObject(FrameIdx, LocalOffset);
167  
168    if (!StackGrowsDown)
169      Offset += MFI.getObjectSize(FrameIdx);
170  
171    ++NumAllocations;
172  }
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  void LocalStackSlotPass::AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
177                                             SmallSet<int, 16> &ProtectedObjs,
178                                             MachineFrameInfo &MFI,
179                                             bool StackGrowsDown, int64_t &Offset,
180                                             unsigned &MaxAlign) {
181    for (StackObjSet::const_iterator I = UnassignedObjs.begin(),
182          E = UnassignedObjs.end(); I != E; ++I) {
183      int i = *I;
184      AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
185      ProtectedObjs.insert(i);
186    }
187  }
188  
189  /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
190  /// abstract stack objects.
191  void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) {
192    // Loop over all of the stack objects, assigning sequential addresses...
193    MachineFrameInfo &MFI = Fn.getFrameInfo();
194    const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
195    bool StackGrowsDown =
196      TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
197    int64_t Offset = 0;
198    unsigned MaxAlign = 0;
199  
200    // Make sure that the stack protector comes before the local variables on the
201    // stack.
202    SmallSet<int, 16> ProtectedObjs;
203    if (MFI.hasStackProtectorIndex()) {
204      int StackProtectorFI = MFI.getStackProtectorIndex();
205  
206      // We need to make sure we didn't pre-allocate the stack protector when
207      // doing this.
208      // If we already have a stack protector, this will re-assign it to a slot
209      // that is **not** covering the protected objects.
210      assert(!MFI.isObjectPreAllocated(StackProtectorFI) &&
211             "Stack protector pre-allocated in LocalStackSlotAllocation");
212  
213      StackObjSet LargeArrayObjs;
214      StackObjSet SmallArrayObjs;
215      StackObjSet AddrOfObjs;
216  
217      AdjustStackOffset(MFI, StackProtectorFI, Offset, StackGrowsDown, MaxAlign);
218  
219      // Assign large stack objects first.
220      for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
221        if (MFI.isDeadObjectIndex(i))
222          continue;
223        if (StackProtectorFI == (int)i)
224          continue;
225  
226        switch (MFI.getObjectSSPLayout(i)) {
227        case MachineFrameInfo::SSPLK_None:
228          continue;
229        case MachineFrameInfo::SSPLK_SmallArray:
230          SmallArrayObjs.insert(i);
231          continue;
232        case MachineFrameInfo::SSPLK_AddrOf:
233          AddrOfObjs.insert(i);
234          continue;
235        case MachineFrameInfo::SSPLK_LargeArray:
236          LargeArrayObjs.insert(i);
237          continue;
238        }
239        llvm_unreachable("Unexpected SSPLayoutKind.");
240      }
241  
242      AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
243                            Offset, MaxAlign);
244      AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
245                            Offset, MaxAlign);
246      AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
247                            Offset, MaxAlign);
248    }
249  
250    // Then assign frame offsets to stack objects that are not used to spill
251    // callee saved registers.
252    for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
253      if (MFI.isDeadObjectIndex(i))
254        continue;
255      if (MFI.getStackProtectorIndex() == (int)i)
256        continue;
257      if (ProtectedObjs.count(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(assumeAligned(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) &&
353             "Only pre-allocated locals expected!");
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);
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");
375  
376      int64_t Offset = 0;
377      int64_t FrameSizeAdjust = StackGrowsDown ? MFI.getLocalFrameSize() : 0;
378  
379      LLVM_DEBUG(dbgs() << "  Replacing FI in: " << MI);
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");
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);
416  
417        LLVM_DEBUG(dbgs() << "  Materializing base register " << BaseReg
418                          << " at frame local offset "
419                          << LocalOffset + InstrOffset << "\n");
420  
421        // Tell the target to insert the instruction to initialize
422        // the base register.
423        //            MachineBasicBlock::iterator InsertionPt = Entry->begin();
424        TRI->materializeFrameBaseRegister(Entry, BaseReg, FrameIdx,
425                                          InstrOffset);
426  
427        // The base register already includes any offset specified
428        // by the instruction, so account for that so it doesn't get
429        // applied twice.
430        Offset = -InstrOffset;
431  
432        ++NumBaseRegisters;
433        UsedBaseReg = true;
434      }
435      assert(BaseReg != 0 && "Unable to allocate virtual base register!");
436  
437      // Modify the instruction to use the new base register rather
438      // than the frame index operand.
439      TRI->resolveFrameIndex(MI, BaseReg, Offset);
440      LLVM_DEBUG(dbgs() << "Resolved: " << MI);
441  
442      ++NumReplacements;
443    }
444  
445    return UsedBaseReg;
446  }
447