Coverage Report

Created: 2017-10-03 07:32

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