Coverage Report

Created: 2019-07-24 05:18

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