aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm16/lib/CodeGen/LocalStackSlotAllocation.cpp
blob: e491ed12034d7d7818d7db9ab7f33d3de72499c1 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
//===- LocalStackSlotAllocation.cpp - Pre-allocate locals to stack slots --===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This pass assigns local frame indices to stack slots relative to one another
// and allocates additional base registers to access them when the target
// estimates they are likely to be out of range of stack pointer and frame
// pointer relative addressing.
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/TargetFrameLowering.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <tuple>

using namespace llvm;

#define DEBUG_TYPE "localstackalloc"

STATISTIC(NumAllocations, "Number of frame indices allocated into local block");
STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated");
STATISTIC(NumReplacements, "Number of frame indices references replaced");

namespace {

  class FrameRef {
    MachineBasicBlock::iterator MI; // Instr referencing the frame
    int64_t LocalOffset;            // Local offset of the frame idx referenced
    int FrameIdx;                   // The frame index

    // Order reference instruction appears in program. Used to ensure
    // deterministic order when multiple instructions may reference the same
    // location.
    unsigned Order;

  public:
    FrameRef(MachineInstr *I, int64_t Offset, int Idx, unsigned Ord) :
      MI(I), LocalOffset(Offset), FrameIdx(Idx), Order(Ord) {}

    bool operator<(const FrameRef &RHS) const {
      return std::tie(LocalOffset, FrameIdx, Order) <
             std::tie(RHS.LocalOffset, RHS.FrameIdx, RHS.Order);
    }

    MachineBasicBlock::iterator getMachineInstr() const { return MI; }
    int64_t getLocalOffset() const { return LocalOffset; }
    int getFrameIndex() const { return FrameIdx; }
  };

  class LocalStackSlotPass: public MachineFunctionPass {
    SmallVector<int64_t, 16> LocalOffsets;

    /// StackObjSet - A set of stack object indexes
    using StackObjSet = SmallSetVector<int, 8>;

    void AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx, int64_t &Offset,
                           bool StackGrowsDown, Align &MaxAlign);
    void AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
                               SmallSet<int, 16> &ProtectedObjs,
                               MachineFrameInfo &MFI, bool StackGrowsDown,
                               int64_t &Offset, Align &MaxAlign);
    void calculateFrameObjectOffsets(MachineFunction &Fn);
    bool insertFrameReferenceRegisters(MachineFunction &Fn);

  public:
    static char ID; // Pass identification, replacement for typeid

    explicit LocalStackSlotPass() : MachineFunctionPass(ID) {
      initializeLocalStackSlotPassPass(*PassRegistry::getPassRegistry());
    }

    bool runOnMachineFunction(MachineFunction &MF) override;

    void getAnalysisUsage(AnalysisUsage &AU) const override {
      AU.setPreservesCFG();
      MachineFunctionPass::getAnalysisUsage(AU);
    }
  };

} // end anonymous namespace

char LocalStackSlotPass::ID = 0;

char &llvm::LocalStackSlotAllocationID = LocalStackSlotPass::ID;
INITIALIZE_PASS(LocalStackSlotPass, DEBUG_TYPE,
                "Local Stack Slot Allocation", false, false)

bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) {
  MachineFrameInfo &MFI = MF.getFrameInfo();
  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
  unsigned LocalObjectCount = MFI.getObjectIndexEnd();

  // If the target doesn't want/need this pass, or if there are no locals
  // to consider, early exit.
  if (LocalObjectCount == 0 || !TRI->requiresVirtualBaseRegisters(MF))
    return false;

  // Make sure we have enough space to store the local offsets.
  LocalOffsets.resize(MFI.getObjectIndexEnd());

  // Lay out the local blob.
  calculateFrameObjectOffsets(MF);

  // Insert virtual base registers to resolve frame index references.
  bool UsedBaseRegs = insertFrameReferenceRegisters(MF);

  // Tell MFI whether any base registers were allocated. PEI will only
  // want to use the local block allocations from this pass if there were any.
  // Otherwise, PEI can do a bit better job of getting the alignment right
  // without a hole at the start since it knows the alignment of the stack
  // at the start of local allocation, and this pass doesn't.
  MFI.setUseLocalStackAllocationBlock(UsedBaseRegs);

  return true;
}

/// AdjustStackOffset - Helper function used to adjust the stack frame offset.
void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx,
                                           int64_t &Offset, bool StackGrowsDown,
                                           Align &MaxAlign) {
  // If the stack grows down, add the object size to find the lowest address.
  if (StackGrowsDown)
    Offset += MFI.getObjectSize(FrameIdx);

  Align Alignment = MFI.getObjectAlign(FrameIdx);

  // If the alignment of this object is greater than that of the stack, then
  // increase the stack alignment to match.
  MaxAlign = std::max(MaxAlign, Alignment);

  // Adjust to alignment boundary.
  Offset = alignTo(Offset, Alignment);

  int64_t LocalOffset = StackGrowsDown ? -Offset : Offset;
  LLVM_DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset "
                    << LocalOffset << "\n");
  // Keep the offset available for base register allocation
  LocalOffsets[FrameIdx] = LocalOffset;
  // And tell MFI about it for PEI to use later
  MFI.mapLocalFrameObject(FrameIdx, LocalOffset);

  if (!StackGrowsDown)
    Offset += MFI.getObjectSize(FrameIdx);

  ++NumAllocations;
}

/// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
/// those required to be close to the Stack Protector) to stack offsets.
void LocalStackSlotPass::AssignProtectedObjSet(
    const StackObjSet &UnassignedObjs, SmallSet<int, 16> &ProtectedObjs,
    MachineFrameInfo &MFI, bool StackGrowsDown, int64_t &Offset,
    Align &MaxAlign) {
  for (int i : UnassignedObjs) {
    AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
    ProtectedObjs.insert(i);
  }
}

/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
/// abstract stack objects.
void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) {
  // Loop over all of the stack objects, assigning sequential addresses...
  MachineFrameInfo &MFI = Fn.getFrameInfo();
  const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
  bool StackGrowsDown =
    TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
  int64_t Offset = 0;
  Align MaxAlign;

  // Make sure that the stack protector comes before the local variables on the
  // stack.
  SmallSet<int, 16> ProtectedObjs;
  if (MFI.hasStackProtectorIndex()) {
    int StackProtectorFI = MFI.getStackProtectorIndex();

    // We need to make sure we didn't pre-allocate the stack protector when
    // doing this.
    // If we already have a stack protector, this will re-assign it to a slot
    // that is **not** covering the protected objects.
    assert(!MFI.isObjectPreAllocated(StackProtectorFI) &&
           "Stack protector pre-allocated in LocalStackSlotAllocation");

    StackObjSet LargeArrayObjs;
    StackObjSet SmallArrayObjs;
    StackObjSet AddrOfObjs;

    // Only place the stack protector in the local stack area if the target
    // allows it.
    if (TFI.isStackIdSafeForLocalArea(MFI.getStackID(StackProtectorFI)))
      AdjustStackOffset(MFI, StackProtectorFI, Offset, StackGrowsDown,
                        MaxAlign);

    // Assign large stack objects first.
    for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
      if (MFI.isDeadObjectIndex(i))
        continue;
      if (StackProtectorFI == (int)i)
        continue;
      if (!TFI.isStackIdSafeForLocalArea(MFI.getStackID(i)))
        continue;

      switch (MFI.getObjectSSPLayout(i)) {
      case MachineFrameInfo::SSPLK_None:
        continue;
      case MachineFrameInfo::SSPLK_SmallArray:
        SmallArrayObjs.insert(i);
        continue;
      case MachineFrameInfo::SSPLK_AddrOf:
        AddrOfObjs.insert(i);
        continue;
      case MachineFrameInfo::SSPLK_LargeArray:
        LargeArrayObjs.insert(i);
        continue;
      }
      llvm_unreachable("Unexpected SSPLayoutKind.");
    }

    AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
                          Offset, MaxAlign);
    AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
                          Offset, MaxAlign);
    AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
                          Offset, MaxAlign);
  }

  // Then assign frame offsets to stack objects that are not used to spill
  // callee saved registers.
  for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
    if (MFI.isDeadObjectIndex(i))
      continue;
    if (MFI.getStackProtectorIndex() == (int)i)
      continue;
    if (ProtectedObjs.count(i))
      continue;
    if (!TFI.isStackIdSafeForLocalArea(MFI.getStackID(i)))
      continue;

    AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
  }

  // Remember how big this blob of stack space is
  MFI.setLocalFrameSize(Offset);
  MFI.setLocalFrameMaxAlign(MaxAlign);
}

static inline bool
lookupCandidateBaseReg(unsigned BaseReg,
                       int64_t BaseOffset,
                       int64_t FrameSizeAdjust,
                       int64_t LocalFrameOffset,
                       const MachineInstr &MI,
                       const TargetRegisterInfo *TRI) {
  // Check if the relative offset from the where the base register references
  // to the target address is in range for the instruction.
  int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset;
  return TRI->isFrameOffsetLegal(&MI, BaseReg, Offset);
}

bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) {
  // Scan the function's instructions looking for frame index references.
  // For each, ask the target if it wants a virtual base register for it
  // based on what we can tell it about where the local will end up in the
  // stack frame. If it wants one, re-use a suitable one we've previously
  // allocated, or if there isn't one that fits the bill, allocate a new one
  // and ask the target to create a defining instruction for it.

  MachineFrameInfo &MFI = Fn.getFrameInfo();
  const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
  const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
  bool StackGrowsDown =
    TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;

  // Collect all of the instructions in the block that reference
  // a frame index. Also store the frame index referenced to ease later
  // lookup. (For any insn that has more than one FI reference, we arbitrarily
  // choose the first one).
  SmallVector<FrameRef, 64> FrameReferenceInsns;

  unsigned Order = 0;

  for (MachineBasicBlock &BB : Fn) {
    for (MachineInstr &MI : BB) {
      // Debug value, stackmap and patchpoint instructions can't be out of
      // range, so they don't need any updates.
      if (MI.isDebugInstr() || MI.getOpcode() == TargetOpcode::STATEPOINT ||
          MI.getOpcode() == TargetOpcode::STACKMAP ||
          MI.getOpcode() == TargetOpcode::PATCHPOINT)
        continue;

      // For now, allocate the base register(s) within the basic block
      // where they're used, and don't try to keep them around outside
      // of that. It may be beneficial to try sharing them more broadly
      // than that, but the increased register pressure makes that a
      // tricky thing to balance. Investigate if re-materializing these
      // becomes an issue.
      for (const MachineOperand &MO : MI.operands()) {
        // Consider replacing all frame index operands that reference
        // an object allocated in the local block.
        if (MO.isFI()) {
          // Don't try this with values not in the local block.
          if (!MFI.isObjectPreAllocated(MO.getIndex()))
            break;
          int Idx = MO.getIndex();
          int64_t LocalOffset = LocalOffsets[Idx];
          if (!TRI->needsFrameBaseReg(&MI, LocalOffset))
            break;
          FrameReferenceInsns.push_back(FrameRef(&MI, LocalOffset, Idx, Order++));
          break;
        }
      }
    }
  }

  // Sort the frame references by local offset.
  // Use frame index as a tie-breaker in case MI's have the same offset.
  llvm::sort(FrameReferenceInsns);

  MachineBasicBlock *Entry = &Fn.front();

  Register BaseReg;
  int64_t BaseOffset = 0;

  // Loop through the frame references and allocate for them as necessary.
  for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) {
    FrameRef &FR = FrameReferenceInsns[ref];
    MachineInstr &MI = *FR.getMachineInstr();
    int64_t LocalOffset = FR.getLocalOffset();
    int FrameIdx = FR.getFrameIndex();
    assert(MFI.isObjectPreAllocated(FrameIdx) &&
           "Only pre-allocated locals expected!");

    // We need to keep the references to the stack protector slot through frame
    // index operands so that it gets resolved by PEI rather than this pass.
    // This avoids accesses to the stack protector though virtual base
    // registers, and forces PEI to address it using fp/sp/bp.
    if (MFI.hasStackProtectorIndex() &&
        FrameIdx == MFI.getStackProtectorIndex())
      continue;

    LLVM_DEBUG(dbgs() << "Considering: " << MI);

    unsigned idx = 0;
    for (unsigned f = MI.getNumOperands(); idx != f; ++idx) {
      if (!MI.getOperand(idx).isFI())
        continue;

      if (FrameIdx == MI.getOperand(idx).getIndex())
        break;
    }

    assert(idx < MI.getNumOperands() && "Cannot find FI operand");

    int64_t Offset = 0;
    int64_t FrameSizeAdjust = StackGrowsDown ? MFI.getLocalFrameSize() : 0;

    LLVM_DEBUG(dbgs() << "  Replacing FI in: " << MI);

    // If we have a suitable base register available, use it; otherwise
    // create a new one. Note that any offset encoded in the
    // instruction itself will be taken into account by the target,
    // so we don't have to adjust for it here when reusing a base
    // register.
    if (BaseReg.isValid() &&
        lookupCandidateBaseReg(BaseReg, BaseOffset, FrameSizeAdjust,
                               LocalOffset, MI, TRI)) {
      LLVM_DEBUG(dbgs() << "  Reusing base register " << BaseReg << "\n");
      // We found a register to reuse.
      Offset = FrameSizeAdjust + LocalOffset - BaseOffset;
    } else {
      // No previously defined register was in range, so create a new one.
      int64_t InstrOffset = TRI->getFrameIndexInstrOffset(&MI, idx);

      int64_t CandBaseOffset = FrameSizeAdjust + LocalOffset + InstrOffset;

      // We'd like to avoid creating single-use virtual base registers.
      // Because the FrameRefs are in sorted order, and we've already
      // processed all FrameRefs before this one, just check whether or not
      // the next FrameRef will be able to reuse this new register. If not,
      // then don't bother creating it.
      if (ref + 1 >= e ||
          !lookupCandidateBaseReg(
              BaseReg, CandBaseOffset, FrameSizeAdjust,
              FrameReferenceInsns[ref + 1].getLocalOffset(),
              *FrameReferenceInsns[ref + 1].getMachineInstr(), TRI))
        continue;

      // Save the base offset.
      BaseOffset = CandBaseOffset;

      // Tell the target to insert the instruction to initialize
      // the base register.
      //            MachineBasicBlock::iterator InsertionPt = Entry->begin();
      BaseReg = TRI->materializeFrameBaseRegister(Entry, FrameIdx, InstrOffset);

      LLVM_DEBUG(dbgs() << "  Materialized base register at frame local offset "
                        << LocalOffset + InstrOffset
                        << " into " << printReg(BaseReg, TRI) << '\n');

      // The base register already includes any offset specified
      // by the instruction, so account for that so it doesn't get
      // applied twice.
      Offset = -InstrOffset;

      ++NumBaseRegisters;
    }
    assert(BaseReg && "Unable to allocate virtual base register!");

    // Modify the instruction to use the new base register rather
    // than the frame index operand.
    TRI->resolveFrameIndex(MI, BaseReg, Offset);
    LLVM_DEBUG(dbgs() << "Resolved: " << MI);

    ++NumReplacements;
  }

  return BaseReg.isValid();
}