Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/PrologEpilogInserter.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function ---===//
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 is responsible for finalizing the functions frame layout, saving
10
// callee saved registers, and for emitting prolog & epilog code for the
11
// function.
12
//
13
// This pass must be run after register allocation.  After this pass is
14
// executed, it is illegal to construct MO_FrameIndex operands.
15
//
16
//===----------------------------------------------------------------------===//
17
18
#include "llvm/ADT/ArrayRef.h"
19
#include "llvm/ADT/BitVector.h"
20
#include "llvm/ADT/DepthFirstIterator.h"
21
#include "llvm/ADT/STLExtras.h"
22
#include "llvm/ADT/SetVector.h"
23
#include "llvm/ADT/SmallPtrSet.h"
24
#include "llvm/ADT/SmallSet.h"
25
#include "llvm/ADT/SmallVector.h"
26
#include "llvm/ADT/Statistic.h"
27
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
28
#include "llvm/CodeGen/MachineBasicBlock.h"
29
#include "llvm/CodeGen/MachineDominators.h"
30
#include "llvm/CodeGen/MachineFrameInfo.h"
31
#include "llvm/CodeGen/MachineFunction.h"
32
#include "llvm/CodeGen/MachineFunctionPass.h"
33
#include "llvm/CodeGen/MachineInstr.h"
34
#include "llvm/CodeGen/MachineInstrBuilder.h"
35
#include "llvm/CodeGen/MachineLoopInfo.h"
36
#include "llvm/CodeGen/MachineModuleInfo.h"
37
#include "llvm/CodeGen/MachineOperand.h"
38
#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
39
#include "llvm/CodeGen/MachineRegisterInfo.h"
40
#include "llvm/CodeGen/RegisterScavenging.h"
41
#include "llvm/CodeGen/TargetFrameLowering.h"
42
#include "llvm/CodeGen/TargetInstrInfo.h"
43
#include "llvm/CodeGen/TargetOpcodes.h"
44
#include "llvm/CodeGen/TargetRegisterInfo.h"
45
#include "llvm/CodeGen/TargetSubtargetInfo.h"
46
#include "llvm/CodeGen/WinEHFuncInfo.h"
47
#include "llvm/IR/Attributes.h"
48
#include "llvm/IR/CallingConv.h"
49
#include "llvm/IR/DebugInfoMetadata.h"
50
#include "llvm/IR/DiagnosticInfo.h"
51
#include "llvm/IR/Function.h"
52
#include "llvm/IR/InlineAsm.h"
53
#include "llvm/IR/LLVMContext.h"
54
#include "llvm/MC/MCRegisterInfo.h"
55
#include "llvm/Pass.h"
56
#include "llvm/Support/CodeGen.h"
57
#include "llvm/Support/CommandLine.h"
58
#include "llvm/Support/Debug.h"
59
#include "llvm/Support/ErrorHandling.h"
60
#include "llvm/Support/MathExtras.h"
61
#include "llvm/Support/raw_ostream.h"
62
#include "llvm/Target/TargetMachine.h"
63
#include "llvm/Target/TargetOptions.h"
64
#include <algorithm>
65
#include <cassert>
66
#include <cstdint>
67
#include <functional>
68
#include <limits>
69
#include <utility>
70
#include <vector>
71
72
using namespace llvm;
73
74
961
#define DEBUG_TYPE "prologepilog"
75
76
using MBBVector = SmallVector<MachineBasicBlock *, 4>;
77
78
STATISTIC(NumLeafFuncWithSpills, "Number of leaf functions with CSRs");
79
STATISTIC(NumFuncSeen, "Number of functions seen in PEI");
80
81
82
namespace {
83
84
class PEI : public MachineFunctionPass {
85
public:
86
  static char ID;
87
88
36.1k
  PEI() : MachineFunctionPass(ID) {
89
36.1k
    initializePEIPass(*PassRegistry::getPassRegistry());
90
36.1k
  }
91
92
  void getAnalysisUsage(AnalysisUsage &AU) const override;
93
94
  /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
95
  /// frame indexes with appropriate references.
96
  bool runOnMachineFunction(MachineFunction &MF) override;
97
98
private:
99
  RegScavenger *RS;
100
101
  // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
102
  // stack frame indexes.
103
  unsigned MinCSFrameIndex = std::numeric_limits<unsigned>::max();
104
  unsigned MaxCSFrameIndex = 0;
105
106
  // Save and Restore blocks of the current function. Typically there is a
107
  // single save block, unless Windows EH funclets are involved.
108
  MBBVector SaveBlocks;
109
  MBBVector RestoreBlocks;
110
111
  // Flag to control whether to use the register scavenger to resolve
112
  // frame index materialization registers. Set according to
113
  // TRI->requiresFrameIndexScavenging() for the current function.
114
  bool FrameIndexVirtualScavenging;
115
116
  // Flag to control whether the scavenger should be passed even though
117
  // FrameIndexVirtualScavenging is used.
118
  bool FrameIndexEliminationScavenging;
119
120
  // Emit remarks.
121
  MachineOptimizationRemarkEmitter *ORE = nullptr;
122
123
  void calculateCallFrameInfo(MachineFunction &MF);
124
  void calculateSaveRestoreBlocks(MachineFunction &MF);
125
  void spillCalleeSavedRegs(MachineFunction &MF);
126
127
  void calculateFrameObjectOffsets(MachineFunction &MF);
128
  void replaceFrameIndices(MachineFunction &MF);
129
  void replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF,
130
                           int &SPAdj);
131
  void insertPrologEpilogCode(MachineFunction &MF);
132
};
133
134
} // end anonymous namespace
135
136
char PEI::ID = 0;
137
138
char &llvm::PrologEpilogCodeInserterID = PEI::ID;
139
140
static cl::opt<unsigned>
141
WarnStackSize("warn-stack-size", cl::Hidden, cl::init((unsigned)-1),
142
              cl::desc("Warn for stack size bigger than the given"
143
                       " number"));
144
145
42.3k
INITIALIZE_PASS_BEGIN(PEI, DEBUG_TYPE, "Prologue/Epilogue Insertion", false,
146
42.3k
                      false)
147
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
148
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
149
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
150
42.3k
INITIALIZE_PASS_END(PEI, DEBUG_TYPE,
151
                    "Prologue/Epilogue Insertion & Frame Finalization", false,
152
                    false)
153
154
36.1k
MachineFunctionPass *llvm::createPrologEpilogInserterPass() {
155
36.1k
  return new PEI();
156
36.1k
}
157
158
STATISTIC(NumBytesStackSpace,
159
          "Number of bytes used for stack in all functions");
160
161
35.8k
void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
162
35.8k
  AU.setPreservesCFG();
163
35.8k
  AU.addPreserved<MachineLoopInfo>();
164
35.8k
  AU.addPreserved<MachineDominatorTree>();
165
35.8k
  AU.addRequired<MachineOptimizationRemarkEmitterPass>();
166
35.8k
  MachineFunctionPass::getAnalysisUsage(AU);
167
35.8k
}
168
169
/// StackObjSet - A set of stack object indexes
170
using StackObjSet = SmallSetVector<int, 8>;
171
172
using SavedDbgValuesMap =
173
    SmallDenseMap<MachineBasicBlock *, SmallVector<MachineInstr *, 4>, 4>;
174
175
/// Stash DBG_VALUEs that describe parameters and which are placed at the start
176
/// of the block. Later on, after the prologue code has been emitted, the
177
/// stashed DBG_VALUEs will be reinserted at the start of the block.
178
static void stashEntryDbgValues(MachineBasicBlock &MBB,
179
497k
                                SavedDbgValuesMap &EntryDbgValues) {
180
497k
  SmallVector<const MachineInstr *, 4> FrameIndexValues;
181
497k
182
501k
  for (auto &MI : MBB) {
183
501k
    if (!MI.isDebugInstr())
184
496k
      break;
185
4.44k
    if (!MI.isDebugValue() || 
!MI.getDebugVariable()->isParameter()4.44k
)
186
64
      continue;
187
4.38k
    if (MI.getOperand(0).isFI()) {
188
20
      // We can only emit valid locations for frame indices after the frame
189
20
      // setup, so do not stash away them.
190
20
      FrameIndexValues.push_back(&MI);
191
20
      continue;
192
20
    }
193
4.36k
    const DILocalVariable *Var = MI.getDebugVariable();
194
4.36k
    const DIExpression *Expr = MI.getDebugExpression();
195
4.36k
    auto Overlaps = [Var, Expr](const MachineInstr *DV) {
196
10
      return Var == DV->getDebugVariable() &&
197
10
             
Expr->fragmentsOverlap(DV->getDebugExpression())1
;
198
10
    };
199
4.36k
    // See if the debug value overlaps with any preceding debug value that will
200
4.36k
    // not be stashed. If that is the case, then we can't stash this value, as
201
4.36k
    // we would then reorder the values at reinsertion.
202
4.36k
    if (llvm::none_of(FrameIndexValues, Overlaps))
203
4.36k
      EntryDbgValues[&MBB].push_back(&MI);
204
4.36k
  }
205
497k
206
497k
  // Remove stashed debug values from the block.
207
497k
  if (EntryDbgValues.count(&MBB))
208
170
    for (auto *MI : EntryDbgValues[&MBB])
209
4.36k
      MI->removeFromParent();
210
497k
}
211
212
/// runOnMachineFunction - Insert prolog/epilog code and replace abstract
213
/// frame indexes with appropriate references.
214
497k
bool PEI::runOnMachineFunction(MachineFunction &MF) {
215
497k
  NumFuncSeen++;
216
497k
  const Function &F = MF.getFunction();
217
497k
  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
218
497k
  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
219
497k
220
497k
  RS = TRI->requiresRegisterScavenging(MF) ? 
new RegScavenger()328k
:
nullptr168k
;
221
497k
  FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(MF);
222
497k
  ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
223
497k
224
497k
  // Calculate the MaxCallFrameSize and AdjustsStack variables for the
225
497k
  // function's frame information. Also eliminates call frame pseudo
226
497k
  // instructions.
227
497k
  calculateCallFrameInfo(MF);
228
497k
229
497k
  // Determine placement of CSR spill/restore code and prolog/epilog code:
230
497k
  // place all spills in the entry block, all restores in return blocks.
231
497k
  calculateSaveRestoreBlocks(MF);
232
497k
233
497k
  // Stash away DBG_VALUEs that should not be moved by insertion of prolog code.
234
497k
  SavedDbgValuesMap EntryDbgValues;
235
497k
  for (MachineBasicBlock *SaveBlock : SaveBlocks)
236
497k
    stashEntryDbgValues(*SaveBlock, EntryDbgValues);
237
497k
238
497k
  // Handle CSR spilling and restoring, for targets that need it.
239
497k
  if (MF.getTarget().usesPhysRegsForPEI())
240
492k
    spillCalleeSavedRegs(MF);
241
497k
242
497k
  // Allow the target machine to make final modifications to the function
243
497k
  // before the frame layout is finalized.
244
497k
  TFI->processFunctionBeforeFrameFinalized(MF, RS);
245
497k
246
497k
  // Calculate actual frame offsets for all abstract stack objects...
247
497k
  calculateFrameObjectOffsets(MF);
248
497k
249
497k
  // Add prolog and epilog code to the function.  This function is required
250
497k
  // to align the stack frame as necessary for any stack variables or
251
497k
  // called functions.  Because of this, calculateCalleeSavedRegisters()
252
497k
  // must be called before this function in order to set the AdjustsStack
253
497k
  // and MaxCallFrameSize variables.
254
497k
  if (!F.hasFnAttribute(Attribute::Naked))
255
496k
    insertPrologEpilogCode(MF);
256
497k
257
497k
  // Reinsert stashed debug values at the start of the entry blocks.
258
497k
  for (auto &I : EntryDbgValues)
259
170
    I.first->insert(I.first->begin(), I.second.begin(), I.second.end());
260
497k
261
497k
  // Replace all MO_FrameIndex operands with physical register references
262
497k
  // and actual offsets.
263
497k
  //
264
497k
  replaceFrameIndices(MF);
265
497k
266
497k
  // If register scavenging is needed, as we've enabled doing it as a
267
497k
  // post-pass, scavenge the virtual registers that frame index elimination
268
497k
  // inserted.
269
497k
  if (TRI->requiresRegisterScavenging(MF) && 
FrameIndexVirtualScavenging328k
)
270
327k
    scavengeFrameVirtualRegs(MF, *RS);
271
497k
272
497k
  // Warn on stack size when we exceeds the given limit.
273
497k
  MachineFrameInfo &MFI = MF.getFrameInfo();
274
497k
  uint64_t StackSize = MFI.getStackSize();
275
497k
  if (WarnStackSize.getNumOccurrences() > 0 && 
WarnStackSize < StackSize21.9k
) {
276
20
    DiagnosticInfoStackSize DiagStackSize(F, StackSize);
277
20
    F.getContext().diagnose(DiagStackSize);
278
20
  }
279
497k
  ORE->emit([&]() {
280
961
    return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "StackSize",
281
961
                                             MF.getFunction().getSubprogram(),
282
961
                                             &MF.front())
283
961
           << ore::NV("NumStackBytes", StackSize) << " stack bytes in function";
284
961
  });
285
497k
286
497k
  delete RS;
287
497k
  SaveBlocks.clear();
288
497k
  RestoreBlocks.clear();
289
497k
  MFI.setSavePoint(nullptr);
290
497k
  MFI.setRestorePoint(nullptr);
291
497k
  return true;
292
497k
}
293
294
/// Calculate the MaxCallFrameSize and AdjustsStack
295
/// variables for the function's frame information and eliminate call frame
296
/// pseudo instructions.
297
497k
void PEI::calculateCallFrameInfo(MachineFunction &MF) {
298
497k
  const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
299
497k
  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
300
497k
  MachineFrameInfo &MFI = MF.getFrameInfo();
301
497k
302
497k
  unsigned MaxCallFrameSize = 0;
303
497k
  bool AdjustsStack = MFI.adjustsStack();
304
497k
305
497k
  // Get the function call frame set-up and tear-down instruction opcode
306
497k
  unsigned FrameSetupOpcode = TII.getCallFrameSetupOpcode();
307
497k
  unsigned FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
308
497k
309
497k
  // Early exit for targets which have no call frame setup/destroy pseudo
310
497k
  // instructions.
311
497k
  if (FrameSetupOpcode == ~0u && 
FrameDestroyOpcode == ~0u2.29k
)
312
2.29k
    return;
313
494k
314
494k
  std::vector<MachineBasicBlock::iterator> FrameSDOps;
315
3.33M
  for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E; 
++BB2.83M
)
316
22.6M
    
for (MachineBasicBlock::iterator I = BB->begin(); 2.83M
I != BB->end();
++I19.7M
)
317
19.7M
      if (TII.isFrameInstr(*I)) {
318
2.90M
        unsigned Size = TII.getFrameSize(*I);
319
2.90M
        if (Size > MaxCallFrameSize) 
MaxCallFrameSize = Size28.2k
;
320
2.90M
        AdjustsStack = true;
321
2.90M
        FrameSDOps.push_back(I);
322
16.8M
      } else if (I->isInlineAsm()) {
323
20.4k
        // Some inline asm's need a stack frame, as indicated by operand 1.
324
20.4k
        unsigned ExtraInfo = I->getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
325
20.4k
        if (ExtraInfo & InlineAsm::Extra_IsAlignStack)
326
21
          AdjustsStack = true;
327
20.4k
      }
328
494k
329
494k
  assert(!MFI.isMaxCallFrameSizeComputed() ||
330
494k
         (MFI.getMaxCallFrameSize() == MaxCallFrameSize &&
331
494k
          MFI.adjustsStack() == AdjustsStack));
332
494k
  MFI.setAdjustsStack(AdjustsStack);
333
494k
  MFI.setMaxCallFrameSize(MaxCallFrameSize);
334
494k
335
494k
  for (std::vector<MachineBasicBlock::iterator>::iterator
336
3.39M
         i = FrameSDOps.begin(), e = FrameSDOps.end(); i != e; 
++i2.90M
) {
337
2.90M
    MachineBasicBlock::iterator I = *i;
338
2.90M
339
2.90M
    // If call frames are not being included as part of the stack frame, and
340
2.90M
    // the target doesn't indicate otherwise, remove the call frame pseudos
341
2.90M
    // here. The sub/add sp instruction pairs are still inserted, but we don't
342
2.90M
    // need to track the SP adjustment for frame index elimination.
343
2.90M
    if (TFI->canSimplifyCallFramePseudos(MF))
344
2.89M
      TFI->eliminateCallFramePseudoInstr(MF, *I->getParent(), I);
345
2.90M
  }
346
494k
}
347
348
/// Compute the sets of entry and return blocks for saving and restoring
349
/// callee-saved registers, and placing prolog and epilog code.
350
497k
void PEI::calculateSaveRestoreBlocks(MachineFunction &MF) {
351
497k
  const MachineFrameInfo &MFI = MF.getFrameInfo();
352
497k
353
497k
  // Even when we do not change any CSR, we still want to insert the
354
497k
  // prologue and epilogue of the function.
355
497k
  // So set the save points for those.
356
497k
357
497k
  // Use the points found by shrink-wrapping, if any.
358
497k
  if (MFI.getSavePoint()) {
359
4.60k
    SaveBlocks.push_back(MFI.getSavePoint());
360
4.60k
    assert(MFI.getRestorePoint() && "Both restore and save must be set");
361
4.60k
    MachineBasicBlock *RestoreBlock = MFI.getRestorePoint();
362
4.60k
    // If RestoreBlock does not have any successor and is not a return block
363
4.60k
    // then the end point is unreachable and we do not need to insert any
364
4.60k
    // epilogue.
365
4.60k
    if (!RestoreBlock->succ_empty() || 
RestoreBlock->isReturnBlock()753
)
366
4.40k
      RestoreBlocks.push_back(RestoreBlock);
367
4.60k
    return;
368
4.60k
  }
369
492k
370
492k
  // Save refs to entry and return blocks.
371
492k
  SaveBlocks.push_back(&MF.front());
372
2.82M
  for (MachineBasicBlock &MBB : MF) {
373
2.82M
    if (MBB.isEHFuncletEntry())
374
131
      SaveBlocks.push_back(&MBB);
375
2.82M
    if (MBB.isReturnBlock())
376
606k
      RestoreBlocks.push_back(&MBB);
377
2.82M
  }
378
492k
}
379
380
static void assignCalleeSavedSpillSlots(MachineFunction &F,
381
                                        const BitVector &SavedRegs,
382
                                        unsigned &MinCSFrameIndex,
383
492k
                                        unsigned &MaxCSFrameIndex) {
384
492k
  if (SavedRegs.empty())
385
6
    return;
386
492k
387
492k
  const TargetRegisterInfo *RegInfo = F.getSubtarget().getRegisterInfo();
388
492k
  const MCPhysReg *CSRegs = F.getRegInfo().getCalleeSavedRegs();
389
492k
390
492k
  std::vector<CalleeSavedInfo> CSI;
391
8.60M
  for (unsigned i = 0; CSRegs[i]; 
++i8.11M
) {
392
8.11M
    unsigned Reg = CSRegs[i];
393
8.11M
    if (SavedRegs.test(Reg))
394
1.36M
      CSI.push_back(CalleeSavedInfo(Reg));
395
8.11M
  }
396
492k
397
492k
  const TargetFrameLowering *TFI = F.getSubtarget().getFrameLowering();
398
492k
  MachineFrameInfo &MFI = F.getFrameInfo();
399
492k
  if (!TFI->assignCalleeSavedSpillSlots(F, RegInfo, CSI)) {
400
313k
    // If target doesn't implement this, use generic code.
401
313k
402
313k
    if (CSI.empty())
403
104k
      return; // Early exit if no callee saved registers are modified!
404
208k
405
208k
    unsigned NumFixedSpillSlots;
406
208k
    const TargetFrameLowering::SpillSlot *FixedSpillSlots =
407
208k
        TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
408
208k
409
208k
    // Now that we know which registers need to be saved and restored, allocate
410
208k
    // stack slots for them.
411
1.31M
    for (auto &CS : CSI) {
412
1.31M
      // If the target has spilled this register to another register, we don't
413
1.31M
      // need to allocate a stack slot.
414
1.31M
      if (CS.isSpilledToReg())
415
3
        continue;
416
1.31M
417
1.31M
      unsigned Reg = CS.getReg();
418
1.31M
      const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg);
419
1.31M
420
1.31M
      int FrameIdx;
421
1.31M
      if (RegInfo->hasReservedSpillSlot(F, Reg, FrameIdx)) {
422
99
        CS.setFrameIdx(FrameIdx);
423
99
        continue;
424
99
      }
425
1.31M
426
1.31M
      // Check to see if this physreg must be spilled to a particular stack slot
427
1.31M
      // on this target.
428
1.31M
      const TargetFrameLowering::SpillSlot *FixedSlot = FixedSpillSlots;
429
1.40M
      while (FixedSlot != FixedSpillSlots + NumFixedSpillSlots &&
430
1.40M
             
FixedSlot->Reg != Reg96.9k
)
431
91.7k
        ++FixedSlot;
432
1.31M
433
1.31M
      unsigned Size = RegInfo->getSpillSize(*RC);
434
1.31M
      if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) {
435
1.30M
        // Nope, just spill it anywhere convenient.
436
1.30M
        unsigned Align = RegInfo->getSpillAlignment(*RC);
437
1.30M
        unsigned StackAlign = TFI->getStackAlignment();
438
1.30M
439
1.30M
        // We may not be able to satisfy the desired alignment specification of
440
1.30M
        // the TargetRegisterClass if the stack alignment is smaller. Use the
441
1.30M
        // min.
442
1.30M
        Align = std::min(Align, StackAlign);
443
1.30M
        FrameIdx = MFI.CreateStackObject(Size, Align, true);
444
1.30M
        if ((unsigned)FrameIdx < MinCSFrameIndex) 
MinCSFrameIndex = FrameIdx207k
;
445
1.30M
        if ((unsigned)FrameIdx > MaxCSFrameIndex) 
MaxCSFrameIndex = FrameIdx1.13M
;
446
1.30M
      } else {
447
5.22k
        // Spill it to the stack where we must.
448
5.22k
        FrameIdx = MFI.CreateFixedSpillStackObject(Size, FixedSlot->Offset);
449
5.22k
      }
450
1.31M
451
1.31M
      CS.setFrameIdx(FrameIdx);
452
1.31M
    }
453
208k
  }
454
492k
455
492k
  MFI.setCalleeSavedInfo(CSI);
456
387k
}
457
458
/// Helper function to update the liveness information for the callee-saved
459
/// registers.
460
227k
static void updateLiveness(MachineFunction &MF) {
461
227k
  MachineFrameInfo &MFI = MF.getFrameInfo();
462
227k
  // Visited will contain all the basic blocks that are in the region
463
227k
  // where the callee saved registers are alive:
464
227k
  // - Anything that is not Save or Restore -> LiveThrough.
465
227k
  // - Save -> LiveIn.
466
227k
  // - Restore -> LiveOut.
467
227k
  // The live-out is not attached to the block, so no need to keep
468
227k
  // Restore in this set.
469
227k
  SmallPtrSet<MachineBasicBlock *, 8> Visited;
470
227k
  SmallVector<MachineBasicBlock *, 8> WorkList;
471
227k
  MachineBasicBlock *Entry = &MF.front();
472
227k
  MachineBasicBlock *Save = MFI.getSavePoint();
473
227k
474
227k
  if (!Save)
475
226k
    Save = Entry;
476
227k
477
227k
  if (Entry != Save) {
478
905
    WorkList.push_back(Entry);
479
905
    Visited.insert(Entry);
480
905
  }
481
227k
  Visited.insert(Save);
482
227k
483
227k
  MachineBasicBlock *Restore = MFI.getRestorePoint();
484
227k
  if (Restore)
485
905
    // By construction Restore cannot be visited, otherwise it
486
905
    // means there exists a path to Restore that does not go
487
905
    // through Save.
488
905
    WorkList.push_back(Restore);
489
227k
490
230k
  while (!WorkList.empty()) {
491
3.09k
    const MachineBasicBlock *CurBB = WorkList.pop_back_val();
492
3.09k
    // By construction, the region that is after the save point is
493
3.09k
    // dominated by the Save and post-dominated by the Restore.
494
3.09k
    if (CurBB == Save && 
Save != Restore491
)
495
0
      continue;
496
3.09k
    // Enqueue all the successors not already visited.
497
3.09k
    // Those are by construction either before Save or after Restore.
498
3.09k
    for (MachineBasicBlock *SuccBB : CurBB->successors())
499
2.78k
      if (Visited.insert(SuccBB).second)
500
1.28k
        WorkList.push_back(SuccBB);
501
3.09k
  }
502
227k
503
227k
  const std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
504
227k
505
227k
  MachineRegisterInfo &MRI = MF.getRegInfo();
506
1.59M
  for (unsigned i = 0, e = CSI.size(); i != e; 
++i1.36M
) {
507
1.37M
    for (MachineBasicBlock *MBB : Visited) {
508
1.37M
      MCPhysReg Reg = CSI[i].getReg();
509
1.37M
      // Add the callee-saved register as live-in.
510
1.37M
      // It's killed at the spill.
511
1.37M
      if (!MRI.isReserved(Reg) && 
!MBB->isLiveIn(Reg)1.17M
)
512
8.96k
        MBB->addLiveIn(Reg);
513
1.37M
    }
514
1.36M
    // If callee-saved register is spilled to another register rather than
515
1.36M
    // spilling to stack, the destination register has to be marked as live for
516
1.36M
    // each MBB between the prologue and epilogue so that it is not clobbered
517
1.36M
    // before it is reloaded in the epilogue. The Visited set contains all
518
1.36M
    // blocks outside of the region delimited by prologue/epilogue.
519
1.36M
    if (CSI[i].isSpilledToReg()) {
520
15
      for (MachineBasicBlock &MBB : MF) {
521
15
        if (Visited.count(&MBB))
522
6
          continue;
523
9
        MCPhysReg DstReg = CSI[i].getDstReg();
524
9
        if (!MBB.isLiveIn(DstReg))
525
9
          MBB.addLiveIn(DstReg);
526
9
      }
527
6
    }
528
1.36M
  }
529
227k
530
227k
}
531
532
/// Insert restore code for the callee-saved registers used in the function.
533
static void insertCSRSaves(MachineBasicBlock &SaveBlock,
534
227k
                           ArrayRef<CalleeSavedInfo> CSI) {
535
227k
  MachineFunction &MF = *SaveBlock.getParent();
536
227k
  const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
537
227k
  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
538
227k
  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
539
227k
540
227k
  MachineBasicBlock::iterator I = SaveBlock.begin();
541
227k
  if (!TFI->spillCalleeSavedRegisters(SaveBlock, I, CSI, TRI)) {
542
3.52k
    for (const CalleeSavedInfo &CS : CSI) {
543
3.52k
      // Insert the spill to the stack frame.
544
3.52k
      unsigned Reg = CS.getReg();
545
3.52k
546
3.52k
      if (CS.isSpilledToReg()) {
547
0
        BuildMI(SaveBlock, I, DebugLoc(),
548
0
                TII.get(TargetOpcode::COPY), CS.getDstReg())
549
0
          .addReg(Reg, getKillRegState(true));
550
3.52k
      } else {
551
3.52k
        const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
552
3.52k
        TII.storeRegToStackSlot(SaveBlock, I, Reg, true, CS.getFrameIdx(), RC,
553
3.52k
                                TRI);
554
3.52k
      }
555
3.52k
    }
556
1.42k
  }
557
227k
}
558
559
/// Insert restore code for the callee-saved registers used in the function.
560
static void insertCSRRestores(MachineBasicBlock &RestoreBlock,
561
297k
                              std::vector<CalleeSavedInfo> &CSI) {
562
297k
  MachineFunction &MF = *RestoreBlock.getParent();
563
297k
  const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
564
297k
  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
565
297k
  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
566
297k
567
297k
  // Restore all registers immediately before the return and any
568
297k
  // terminators that precede it.
569
297k
  MachineBasicBlock::iterator I = RestoreBlock.getFirstTerminator();
570
297k
571
297k
  if (!TFI->restoreCalleeSavedRegisters(RestoreBlock, I, CSI, TRI)) {
572
7.33k
    for (const CalleeSavedInfo &CI : reverse(CSI)) {
573
7.33k
      unsigned Reg = CI.getReg();
574
7.33k
      if (CI.isSpilledToReg()) {
575
0
        BuildMI(RestoreBlock, I, DebugLoc(), TII.get(TargetOpcode::COPY), Reg)
576
0
          .addReg(CI.getDstReg(), getKillRegState(true));
577
7.33k
      } else {
578
7.33k
        const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
579
7.33k
        TII.loadRegFromStackSlot(RestoreBlock, I, Reg, CI.getFrameIdx(), RC, TRI);
580
7.33k
        assert(I != RestoreBlock.begin() &&
581
7.33k
               "loadRegFromStackSlot didn't insert any code!");
582
7.33k
        // Insert in reverse order.  loadRegFromStackSlot can insert
583
7.33k
        // multiple instructions.
584
7.33k
      }
585
7.33k
    }
586
3.53k
  }
587
297k
}
588
589
492k
void PEI::spillCalleeSavedRegs(MachineFunction &MF) {
590
492k
  // We can't list this requirement in getRequiredProperties because some
591
492k
  // targets (WebAssembly) use virtual registers past this point, and the pass
592
492k
  // pipeline is set up without giving the passes a chance to look at the
593
492k
  // TargetMachine.
594
492k
  // FIXME: Find a way to express this in getRequiredProperties.
595
492k
  assert(MF.getProperties().hasProperty(
596
492k
      MachineFunctionProperties::Property::NoVRegs));
597
492k
598
492k
  const Function &F = MF.getFunction();
599
492k
  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
600
492k
  MachineFrameInfo &MFI = MF.getFrameInfo();
601
492k
  MinCSFrameIndex = std::numeric_limits<unsigned>::max();
602
492k
  MaxCSFrameIndex = 0;
603
492k
604
492k
  // Determine which of the registers in the callee save list should be saved.
605
492k
  BitVector SavedRegs;
606
492k
  TFI->determineCalleeSaves(MF, SavedRegs, RS);
607
492k
608
492k
  // Assign stack slots for any callee-saved registers that must be spilled.
609
492k
  assignCalleeSavedSpillSlots(MF, SavedRegs, MinCSFrameIndex, MaxCSFrameIndex);
610
492k
611
492k
  // Add the code to save and restore the callee saved registers.
612
492k
  if (!F.hasFnAttribute(Attribute::Naked)) {
613
492k
    MFI.setCalleeSavedInfoValid(true);
614
492k
615
492k
    std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();
616
492k
    if (!CSI.empty()) {
617
227k
      if (!MFI.hasCalls())
618
5.15k
        NumLeafFuncWithSpills++;
619
227k
620
227k
      for (MachineBasicBlock *SaveBlock : SaveBlocks) {
621
227k
        insertCSRSaves(*SaveBlock, CSI);
622
227k
        // Update the live-in information of all the blocks up to the save
623
227k
        // point.
624
227k
        updateLiveness(MF);
625
227k
      }
626
227k
      for (MachineBasicBlock *RestoreBlock : RestoreBlocks)
627
297k
        insertCSRRestores(*RestoreBlock, CSI);
628
227k
    }
629
492k
  }
630
492k
}
631
632
/// AdjustStackOffset - Helper function used to adjust the stack frame offset.
633
static inline void
634
AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx,
635
                  bool StackGrowsDown, int64_t &Offset,
636
197k
                  unsigned &MaxAlign, unsigned Skew) {
637
197k
  // If the stack grows down, add the object size to find the lowest address.
638
197k
  if (StackGrowsDown)
639
193k
    Offset += MFI.getObjectSize(FrameIdx);
640
197k
641
197k
  unsigned Align = MFI.getObjectAlignment(FrameIdx);
642
197k
643
197k
  // If the alignment of this object is greater than that of the stack, then
644
197k
  // increase the stack alignment to match.
645
197k
  MaxAlign = std::max(MaxAlign, Align);
646
197k
647
197k
  // Adjust to alignment boundary.
648
197k
  Offset = alignTo(Offset, Align, Skew);
649
197k
650
197k
  if (StackGrowsDown) {
651
193k
    LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset
652
193k
                      << "]\n");
653
193k
    MFI.setObjectOffset(FrameIdx, -Offset); // Set the computed offset
654
193k
  } else {
655
4.06k
    LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset
656
4.06k
                      << "]\n");
657
4.06k
    MFI.setObjectOffset(FrameIdx, Offset);
658
4.06k
    Offset += MFI.getObjectSize(FrameIdx);
659
4.06k
  }
660
197k
}
661
662
/// Compute which bytes of fixed and callee-save stack area are unused and keep
663
/// track of them in StackBytesFree.
664
static inline void
665
computeFreeStackSlots(MachineFrameInfo &MFI, bool StackGrowsDown,
666
                      unsigned MinCSFrameIndex, unsigned MaxCSFrameIndex,
667
280
                      int64_t FixedCSEnd, BitVector &StackBytesFree) {
668
280
  // Avoid undefined int64_t -> int conversion below in extreme case.
669
280
  if (FixedCSEnd > std::numeric_limits<int>::max())
670
0
    return;
671
280
672
280
  StackBytesFree.resize(FixedCSEnd, true);
673
280
674
280
  SmallVector<int, 16> AllocatedFrameSlots;
675
280
  // Add fixed objects.
676
326
  for (int i = MFI.getObjectIndexBegin(); i != 0; 
++i46
)
677
46
    // StackSlot scavenging is only implemented for the default stack.
678
46
    if (MFI.getStackID(i) == TargetStackID::Default)
679
46
      AllocatedFrameSlots.push_back(i);
680
280
  // Add callee-save objects.
681
978
  for (int i = MinCSFrameIndex; i <= (int)MaxCSFrameIndex; 
++i698
)
682
698
    if (MFI.getStackID(i) == TargetStackID::Default)
683
698
      AllocatedFrameSlots.push_back(i);
684
280
685
744
  for (int i : AllocatedFrameSlots) {
686
744
    // These are converted from int64_t, but they should always fit in int
687
744
    // because of the FixedCSEnd check above.
688
744
    int ObjOffset = MFI.getObjectOffset(i);
689
744
    int ObjSize = MFI.getObjectSize(i);
690
744
    int ObjStart, ObjEnd;
691
744
    if (StackGrowsDown) {
692
744
      // ObjOffset is negative when StackGrowsDown is true.
693
744
      ObjStart = -ObjOffset - ObjSize;
694
744
      ObjEnd = -ObjOffset;
695
744
    } else {
696
0
      ObjStart = ObjOffset;
697
0
      ObjEnd = ObjOffset + ObjSize;
698
0
    }
699
744
    // Ignore fixed holes that are in the previous stack frame.
700
744
    if (ObjEnd > 0)
701
709
      StackBytesFree.reset(ObjStart, ObjEnd);
702
744
  }
703
280
}
704
705
/// Assign frame object to an unused portion of the stack in the fixed stack
706
/// object range.  Return true if the allocation was successful.
707
static inline bool scavengeStackSlot(MachineFrameInfo &MFI, int FrameIdx,
708
                                     bool StackGrowsDown, unsigned MaxAlign,
709
184k
                                     BitVector &StackBytesFree) {
710
184k
  if (MFI.isVariableSizedObjectIndex(FrameIdx))
711
651
    return false;
712
184k
713
184k
  if (StackBytesFree.none()) {
714
183k
    // clear it to speed up later scavengeStackSlot calls to
715
183k
    // StackBytesFree.none()
716
183k
    StackBytesFree.clear();
717
183k
    return false;
718
183k
  }
719
436
720
436
  unsigned ObjAlign = MFI.getObjectAlignment(FrameIdx);
721
436
  if (ObjAlign > MaxAlign)
722
0
    return false;
723
436
724
436
  int64_t ObjSize = MFI.getObjectSize(FrameIdx);
725
436
  int FreeStart;
726
2.82k
  for (FreeStart = StackBytesFree.find_first(); FreeStart != -1;
727
2.52k
       
FreeStart = StackBytesFree.find_next(FreeStart)2.39k
) {
728
2.52k
729
2.52k
    // Check that free space has suitable alignment.
730
2.52k
    unsigned ObjStart = StackGrowsDown ? FreeStart + ObjSize : 
FreeStart0
;
731
2.52k
    if (alignTo(ObjStart, ObjAlign) != ObjStart)
732
2.11k
      continue;
733
412
734
412
    if (FreeStart + ObjSize > StackBytesFree.size())
735
65
      return false;
736
347
737
347
    bool AllBytesFree = true;
738
2.98k
    for (unsigned Byte = 0; Byte < ObjSize; 
++Byte2.64k
)
739
2.91k
      if (!StackBytesFree.test(FreeStart + Byte)) {
740
277
        AllBytesFree = false;
741
277
        break;
742
277
      }
743
347
    if (AllBytesFree)
744
70
      break;
745
347
  }
746
436
747
436
  
if (371
FreeStart == -1371
)
748
301
    return false;
749
70
750
70
  if (StackGrowsDown) {
751
70
    int ObjStart = -(FreeStart + ObjSize);
752
70
    LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP["
753
70
                      << ObjStart << "]\n");
754
70
    MFI.setObjectOffset(FrameIdx, ObjStart);
755
70
  } else {
756
0
    LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP["
757
0
                      << FreeStart << "]\n");
758
0
    MFI.setObjectOffset(FrameIdx, FreeStart);
759
0
  }
760
70
761
70
  StackBytesFree.reset(FreeStart, FreeStart + ObjSize);
762
70
  return true;
763
70
}
764
765
/// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
766
/// those required to be close to the Stack Protector) to stack offsets.
767
static void
768
AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
769
                      SmallSet<int, 16> &ProtectedObjs,
770
                      MachineFrameInfo &MFI, bool StackGrowsDown,
771
7.86k
                      int64_t &Offset, unsigned &MaxAlign, unsigned Skew) {
772
7.86k
773
7.86k
  for (StackObjSet::const_iterator I = UnassignedObjs.begin(),
774
11.1k
        E = UnassignedObjs.end(); I != E; 
++I3.25k
) {
775
3.25k
    int i = *I;
776
3.25k
    AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign, Skew);
777
3.25k
    ProtectedObjs.insert(i);
778
3.25k
  }
779
7.86k
}
780
781
/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
782
/// abstract stack objects.
783
497k
void PEI::calculateFrameObjectOffsets(MachineFunction &MF) {
784
497k
  const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
785
497k
786
497k
  bool StackGrowsDown =
787
497k
    TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
788
497k
789
497k
  // Loop over all of the stack objects, assigning sequential addresses...
790
497k
  MachineFrameInfo &MFI = MF.getFrameInfo();
791
497k
792
497k
  // Start at the beginning of the local area.
793
497k
  // The Offset is the distance from the stack top in the direction
794
497k
  // of stack growth -- so it's always nonnegative.
795
497k
  int LocalAreaOffset = TFI.getOffsetOfLocalArea();
796
497k
  if (StackGrowsDown)
797
469k
    LocalAreaOffset = -LocalAreaOffset;
798
497k
  assert(LocalAreaOffset >= 0
799
497k
         && "Local area offset should be in direction of stack growth");
800
497k
  int64_t Offset = LocalAreaOffset;
801
497k
802
497k
  // Skew to be applied to alignment.
803
497k
  unsigned Skew = TFI.getStackAlignmentSkew(MF);
804
497k
805
#ifdef EXPENSIVE_CHECKS
806
  for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i)
807
    if (!MFI.isDeadObjectIndex(i) &&
808
        MFI.getStackID(i) == TargetStackID::Default)
809
      assert(MFI.getObjectAlignment(i) <= MFI.getMaxAlignment() &&
810
             "MaxAlignment is invalid");
811
#endif
812
813
497k
  // If there are fixed sized objects that are preallocated in the local area,
814
497k
  // non-fixed objects can't be allocated right at the start of local area.
815
497k
  // Adjust 'Offset' to point to the end of last fixed sized preallocated
816
497k
  // object.
817
658k
  for (int i = MFI.getObjectIndexBegin(); i != 0; 
++i161k
) {
818
161k
    if (MFI.getStackID(i) !=
819
161k
        TargetStackID::Default) // Only allocate objects on the default stack.
820
1
      continue;
821
161k
822
161k
    int64_t FixedOff;
823
161k
    if (StackGrowsDown) {
824
160k
      // The maximum distance from the stack pointer is at lower address of
825
160k
      // the object -- which is given by offset. For down growing stack
826
160k
      // the offset is negative, so we negate the offset to get the distance.
827
160k
      FixedOff = -MFI.getObjectOffset(i);
828
160k
    } else {
829
1.03k
      // The maximum distance from the start pointer is at the upper
830
1.03k
      // address of the object.
831
1.03k
      FixedOff = MFI.getObjectOffset(i) + MFI.getObjectSize(i);
832
1.03k
    }
833
161k
    if (FixedOff > Offset) 
Offset = FixedOff31.6k
;
834
161k
  }
835
497k
836
497k
  // First assign frame offsets to stack objects that are used to spill
837
497k
  // callee saved registers.
838
497k
  if (StackGrowsDown) {
839
1.77M
    for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; 
++i1.30M
) {
840
1.30M
      if (MFI.getStackID(i) !=
841
1.30M
          TargetStackID::Default) // Only allocate objects on the default stack.
842
0
        continue;
843
1.30M
844
1.30M
      // If the stack grows down, we need to add the size to find the lowest
845
1.30M
      // address of the object.
846
1.30M
      Offset += MFI.getObjectSize(i);
847
1.30M
848
1.30M
      unsigned Align = MFI.getObjectAlignment(i);
849
1.30M
      // Adjust to alignment boundary
850
1.30M
      Offset = alignTo(Offset, Align, Skew);
851
1.30M
852
1.30M
      LLVM_DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << -Offset << "]\n");
853
1.30M
      MFI.setObjectOffset(i, -Offset);        // Set the computed offset
854
1.30M
    }
855
469k
  } else 
if (27.7k
MaxCSFrameIndex >= MinCSFrameIndex27.7k
) {
856
54
    // Be careful about underflow in comparisons agains MinCSFrameIndex.
857
202
    for (unsigned i = MaxCSFrameIndex; i != MinCSFrameIndex - 1; 
--i148
) {
858
148
      if (MFI.getStackID(i) !=
859
148
          TargetStackID::Default) // Only allocate objects on the default stack.
860
0
        continue;
861
148
862
148
      if (MFI.isDeadObjectIndex(i))
863
0
        continue;
864
148
865
148
      unsigned Align = MFI.getObjectAlignment(i);
866
148
      // Adjust to alignment boundary
867
148
      Offset = alignTo(Offset, Align, Skew);
868
148
869
148
      LLVM_DEBUG(dbgs() << "alloc FI(" << i << ") at SP[" << Offset << "]\n");
870
148
      MFI.setObjectOffset(i, Offset);
871
148
      Offset += MFI.getObjectSize(i);
872
148
    }
873
54
  }
874
497k
875
497k
  // FixedCSEnd is the stack offset to the end of the fixed and callee-save
876
497k
  // stack area.
877
497k
  int64_t FixedCSEnd = Offset;
878
497k
  unsigned MaxAlign = MFI.getMaxAlignment();
879
497k
880
497k
  // Make sure the special register scavenging spill slot is closest to the
881
497k
  // incoming stack pointer if a frame pointer is required and is closer
882
497k
  // to the incoming rather than the final stack pointer.
883
497k
  const TargetRegisterInfo *RegInfo = MF.getSubtarget().getRegisterInfo();
884
497k
  bool EarlyScavengingSlots = (TFI.hasFP(MF) &&
885
497k
                               
TFI.isFPCloseToIncomingSP()221k
&&
886
497k
                               
RegInfo->useFPForScavengingIndex(MF)220k
&&
887
497k
                               
!RegInfo->needsStackRealignment(MF)220k
);
888
497k
  if (RS && 
EarlyScavengingSlots328k
) {
889
196k
    SmallVector<int, 2> SFIs;
890
196k
    RS->getScavengingFrameIndices(SFIs);
891
196k
    for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
892
202k
           IE = SFIs.end(); I != IE; 
++I5.86k
)
893
5.86k
      AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
894
196k
  }
895
497k
896
497k
  // FIXME: Once this is working, then enable flag will change to a target
897
497k
  // check for whether the frame is large enough to want to use virtual
898
497k
  // frame index registers. Functions which don't want/need this optimization
899
497k
  // will continue to use the existing code path.
900
497k
  if (MFI.getUseLocalStackAllocationBlock()) {
901
306
    unsigned Align = MFI.getLocalFrameMaxAlign();
902
306
903
306
    // Adjust to alignment boundary.
904
306
    Offset = alignTo(Offset, Align, Skew);
905
306
906
306
    LLVM_DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n");
907
306
908
306
    // Resolve offsets for objects in the local block.
909
2.83k
    for (unsigned i = 0, e = MFI.getLocalFrameObjectCount(); i != e; 
++i2.52k
) {
910
2.52k
      std::pair<int, int64_t> Entry = MFI.getLocalFrameObjectMap(i);
911
2.52k
      int64_t FIOffset = (StackGrowsDown ? -Offset : 
Offset0
) + Entry.second;
912
2.52k
      LLVM_DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" << FIOffset
913
2.52k
                        << "]\n");
914
2.52k
      MFI.setObjectOffset(Entry.first, FIOffset);
915
2.52k
    }
916
306
    // Allocate the local block
917
306
    Offset += MFI.getLocalFrameSize();
918
306
919
306
    MaxAlign = std::max(Align, MaxAlign);
920
306
  }
921
497k
922
497k
  // Retrieve the Exception Handler registration node.
923
497k
  int EHRegNodeFrameIndex = std::numeric_limits<int>::max();
924
497k
  if (const WinEHFuncInfo *FuncInfo = MF.getWinEHFuncInfo())
925
107
    EHRegNodeFrameIndex = FuncInfo->EHRegNodeFrameIndex;
926
497k
927
497k
  // Make sure that the stack protector comes before the local variables on the
928
497k
  // stack.
929
497k
  SmallSet<int, 16> ProtectedObjs;
930
497k
  if (MFI.hasStackProtectorIndex()) {
931
2.62k
    int StackProtectorFI = MFI.getStackProtectorIndex();
932
2.62k
    StackObjSet LargeArrayObjs;
933
2.62k
    StackObjSet SmallArrayObjs;
934
2.62k
    StackObjSet AddrOfObjs;
935
2.62k
936
2.62k
    // If we need a stack protector, we need to make sure that
937
2.62k
    // LocalStackSlotPass didn't already allocate a slot for it.
938
2.62k
    // If we are told to use the LocalStackAllocationBlock, the stack protector
939
2.62k
    // is expected to be already pre-allocated.
940
2.62k
    if (!MFI.getUseLocalStackAllocationBlock())
941
2.41k
      AdjustStackOffset(MFI, StackProtectorFI, StackGrowsDown, Offset, MaxAlign,
942
2.41k
                        Skew);
943
203
    else if (!MFI.isObjectPreAllocated(MFI.getStackProtectorIndex()))
944
203
      
llvm_unreachable0
(
945
2.62k
          "Stack protector not pre-allocated by LocalStackSlotPass.");
946
2.62k
947
2.62k
    // Assign large stack objects first.
948
47.3k
    
for (unsigned i = 0, e = MFI.getObjectIndexEnd(); 2.62k
i != e;
++i44.7k
) {
949
44.7k
      if (MFI.isObjectPreAllocated(i) && 
MFI.getUseLocalStackAllocationBlock()7.40k
)
950
1.12k
        continue;
951
43.6k
      if (i >= MinCSFrameIndex && 
i <= MaxCSFrameIndex20.1k
)
952
20.1k
        continue;
953
23.4k
      if (RS && 
RS->isScavengingFrameIndex((int)i)21.3k
)
954
830
        continue;
955
22.6k
      if (MFI.isDeadObjectIndex(i))
956
3.58k
        continue;
957
19.0k
      if (StackProtectorFI == (int)i || 
EHRegNodeFrameIndex == (int)i16.6k
)
958
2.41k
        continue;
959
16.6k
      if (MFI.getStackID(i) !=
960
16.6k
          TargetStackID::Default) // Only allocate objects on the default stack.
961
0
        continue;
962
16.6k
963
16.6k
      switch (MFI.getObjectSSPLayout(i)) {
964
16.6k
      case MachineFrameInfo::SSPLK_None:
965
13.3k
        continue;
966
16.6k
      case MachineFrameInfo::SSPLK_SmallArray:
967
97
        SmallArrayObjs.insert(i);
968
97
        continue;
969
16.6k
      case MachineFrameInfo::SSPLK_AddrOf:
970
299
        AddrOfObjs.insert(i);
971
299
        continue;
972
16.6k
      case MachineFrameInfo::SSPLK_LargeArray:
973
2.85k
        LargeArrayObjs.insert(i);
974
2.85k
        continue;
975
0
      }
976
0
      llvm_unreachable("Unexpected SSPLayoutKind.");
977
0
    }
978
2.62k
979
2.62k
    // We expect **all** the protected stack objects to be pre-allocated by
980
2.62k
    // LocalStackSlotPass. If it turns out that PEI still has to allocate some
981
2.62k
    // of them, we may end up messing up the expected order of the objects.
982
2.62k
    if (MFI.getUseLocalStackAllocationBlock() &&
983
2.62k
        
!(203
LargeArrayObjs.empty()203
&&
SmallArrayObjs.empty()203
&&
984
203
          AddrOfObjs.empty()))
985
2.62k
      
llvm_unreachable0
("Found protected stack objects not pre-allocated by "
986
2.62k
                       "LocalStackSlotPass.");
987
2.62k
988
2.62k
    AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
989
2.62k
                          Offset, MaxAlign, Skew);
990
2.62k
    AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
991
2.62k
                          Offset, MaxAlign, Skew);
992
2.62k
    AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
993
2.62k
                          Offset, MaxAlign, Skew);
994
2.62k
  }
995
497k
996
497k
  SmallVector<int, 8> ObjectsToAllocate;
997
497k
998
497k
  // Then prepare to assign frame offsets to stack objects that are not used to
999
497k
  // spill callee saved registers.
1000
2.03M
  for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; 
++i1.54M
) {
1001
1.54M
    if (MFI.isObjectPreAllocated(i) && 
MFI.getUseLocalStackAllocationBlock()60.3k
)
1002
2.52k
      continue;
1003
1.53M
    if (i >= MinCSFrameIndex && 
i <= MaxCSFrameIndex1.30M
)
1004
1.30M
      continue;
1005
233k
    if (RS && 
RS->isScavengingFrameIndex((int)i)177k
)
1006
6.89k
      continue;
1007
227k
    if (MFI.isDeadObjectIndex(i))
1008
36.5k
      continue;
1009
190k
    if (MFI.getStackProtectorIndex() == (int)i || 
EHRegNodeFrameIndex == (int)i188k
)
1010
2.45k
      continue;
1011
188k
    if (ProtectedObjs.count(i))
1012
3.25k
      continue;
1013
184k
    if (MFI.getStackID(i) !=
1014
184k
        TargetStackID::Default) // Only allocate objects on the default stack.
1015
121
      continue;
1016
184k
1017
184k
    // Add the objects that we need to allocate to our working set.
1018
184k
    ObjectsToAllocate.push_back(i);
1019
184k
  }
1020
497k
1021
497k
  // Allocate the EH registration node first if one is present.
1022
497k
  if (EHRegNodeFrameIndex != std::numeric_limits<int>::max())
1023
34
    AdjustStackOffset(MFI, EHRegNodeFrameIndex, StackGrowsDown, Offset,
1024
34
                      MaxAlign, Skew);
1025
497k
1026
497k
  // Give the targets a chance to order the objects the way they like it.
1027
497k
  if (MF.getTarget().getOptLevel() != CodeGenOpt::None &&
1028
497k
      
MF.getTarget().Options.StackSymbolOrdering488k
)
1029
488k
    TFI.orderFrameObjects(MF, ObjectsToAllocate);
1030
497k
1031
497k
  // Keep track of which bytes in the fixed and callee-save range are used so we
1032
497k
  // can use the holes when allocating later stack objects.  Only do this if
1033
497k
  // stack protector isn't being used and the target requests it and we're
1034
497k
  // optimizing.
1035
497k
  BitVector StackBytesFree;
1036
497k
  if (!ObjectsToAllocate.empty() &&
1037
497k
      
MF.getTarget().getOptLevel() != CodeGenOpt::None61.1k
&&
1038
497k
      
MFI.getStackProtectorIndex() < 058.9k
&&
TFI.enableStackSlotScavenging(MF)57.4k
)
1039
280
    computeFreeStackSlots(MFI, StackGrowsDown, MinCSFrameIndex, MaxCSFrameIndex,
1040
280
                          FixedCSEnd, StackBytesFree);
1041
497k
1042
497k
  // Now walk the objects and actually assign base offsets to them.
1043
497k
  for (auto &Object : ObjectsToAllocate)
1044
184k
    if (!scavengeStackSlot(MFI, Object, StackGrowsDown, MaxAlign,
1045
184k
                           StackBytesFree))
1046
184k
      AdjustStackOffset(MFI, Object, StackGrowsDown, Offset, MaxAlign, Skew);
1047
497k
1048
497k
  // Make sure the special register scavenging spill slot is closest to the
1049
497k
  // stack pointer.
1050
497k
  if (RS && 
!EarlyScavengingSlots328k
) {
1051
132k
    SmallVector<int, 2> SFIs;
1052
132k
    RS->getScavengingFrameIndices(SFIs);
1053
132k
    for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
1054
133k
           IE = SFIs.end(); I != IE; 
++I1.04k
)
1055
1.04k
      AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign, Skew);
1056
132k
  }
1057
497k
1058
497k
  if (!TFI.targetHandlesStackFrameRounding()) {
1059
480k
    // If we have reserved argument space for call sites in the function
1060
480k
    // immediately on entry to the current function, count it as part of the
1061
480k
    // overall stack size.
1062
480k
    if (MFI.adjustsStack() && 
TFI.hasReservedCallFrame(MF)229k
)
1063
224k
      Offset += MFI.getMaxCallFrameSize();
1064
480k
1065
480k
    // Round up the size to a multiple of the alignment.  If the function has
1066
480k
    // any calls or alloca's, align to the target's StackAlignment value to
1067
480k
    // ensure that the callee's frame or the alloca data is suitably aligned;
1068
480k
    // otherwise, for leaf functions, align to the TransientStackAlignment
1069
480k
    // value.
1070
480k
    unsigned StackAlign;
1071
480k
    if (MFI.adjustsStack() || 
MFI.hasVarSizedObjects()250k
||
1072
480k
        
(250k
RegInfo->needsStackRealignment(MF)250k
&&
MFI.getObjectIndexEnd() != 01.49k
))
1073
231k
      StackAlign = TFI.getStackAlignment();
1074
248k
    else
1075
248k
      StackAlign = TFI.getTransientStackAlignment();
1076
480k
1077
480k
    // If the frame pointer is eliminated, all frame offsets will be relative to
1078
480k
    // SP not FP. Align to MaxAlign so this works.
1079
480k
    StackAlign = std::max(StackAlign, MaxAlign);
1080
480k
    Offset = alignTo(Offset, StackAlign, Skew);
1081
480k
  }
1082
497k
1083
497k
  // Update frame info to pretend that this is part of the stack...
1084
497k
  int64_t StackSize = Offset - LocalAreaOffset;
1085
497k
  MFI.setStackSize(StackSize);
1086
497k
  NumBytesStackSpace += StackSize;
1087
497k
}
1088
1089
/// insertPrologEpilogCode - Scan the function for modified callee saved
1090
/// registers, insert spill code for these callee saved registers, then add
1091
/// prolog and epilog code to the function.
1092
496k
void PEI::insertPrologEpilogCode(MachineFunction &MF) {
1093
496k
  const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
1094
496k
1095
496k
  // Add prologue to the function...
1096
496k
  for (MachineBasicBlock *SaveBlock : SaveBlocks)
1097
497k
    TFI.emitPrologue(MF, *SaveBlock);
1098
496k
1099
496k
  // Add epilogue to restore the callee-save registers in each exiting block.
1100
496k
  for (MachineBasicBlock *RestoreBlock : RestoreBlocks)
1101
610k
    TFI.emitEpilogue(MF, *RestoreBlock);
1102
496k
1103
496k
  for (MachineBasicBlock *SaveBlock : SaveBlocks)
1104
497k
    TFI.inlineStackProbe(MF, *SaveBlock);
1105
496k
1106
496k
  // Emit additional code that is required to support segmented stacks, if
1107
496k
  // we've been asked for it.  This, when linked with a runtime with support
1108
496k
  // for segmented stacks (libgcc is one), will result in allocating stack
1109
496k
  // space in small chunks instead of one large contiguous block.
1110
496k
  if (MF.shouldSplitStack()) {
1111
264
    for (MachineBasicBlock *SaveBlock : SaveBlocks)
1112
264
      TFI.adjustForSegmentedStacks(MF, *SaveBlock);
1113
264
    // Record that there are split-stack functions, so we will emit a
1114
264
    // special section to tell the linker.
1115
264
    MF.getMMI().setHasSplitStack(true);
1116
264
  } else
1117
496k
    MF.getMMI().setHasNosplitStack(true);
1118
496k
1119
496k
  // Emit additional code that is required to explicitly handle the stack in
1120
496k
  // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The
1121
496k
  // approach is rather similar to that of Segmented Stacks, but it uses a
1122
496k
  // different conditional check and another BIF for allocating more stack
1123
496k
  // space.
1124
496k
  if (MF.getFunction().getCallingConv() == CallingConv::HiPE)
1125
13
    for (MachineBasicBlock *SaveBlock : SaveBlocks)
1126
13
      TFI.adjustForHiPEPrologue(MF, *SaveBlock);
1127
496k
}
1128
1129
/// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
1130
/// register references and actual offsets.
1131
497k
void PEI::replaceFrameIndices(MachineFunction &MF) {
1132
497k
  const auto &ST = MF.getSubtarget();
1133
497k
  const TargetFrameLowering &TFI = *ST.getFrameLowering();
1134
497k
  if (!TFI.needsFrameIndexResolution(MF))
1135
236k
    return;
1136
260k
1137
260k
  const TargetRegisterInfo *TRI = ST.getRegisterInfo();
1138
260k
1139
260k
  // Allow the target to determine this after knowing the frame size.
1140
260k
  FrameIndexEliminationScavenging = (RS && 
!FrameIndexVirtualScavenging214k
) ||
1141
260k
    
TRI->requiresFrameIndexReplacementScavenging(MF)260k
;
1142
260k
1143
260k
  // Store SPAdj at exit of a basic block.
1144
260k
  SmallVector<int, 8> SPState;
1145
260k
  SPState.resize(MF.getNumBlockIDs());
1146
260k
  df_iterator_default_set<MachineBasicBlock*> Reachable;
1147
260k
1148
260k
  // Iterate over the reachable blocks in DFS order.
1149
260k
  for (auto DFI = df_ext_begin(&MF, Reachable), DFE = df_ext_end(&MF, Reachable);
1150
2.71M
       DFI != DFE; 
++DFI2.44M
) {
1151
2.44M
    int SPAdj = 0;
1152
2.44M
    // Check the exit state of the DFS stack predecessor.
1153
2.44M
    if (DFI.getPathLength() >= 2) {
1154
2.18M
      MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
1155
2.18M
      assert(Reachable.count(StackPred) &&
1156
2.18M
             "DFS stack predecessor is already visited.\n");
1157
2.18M
      SPAdj = SPState[StackPred->getNumber()];
1158
2.18M
    }
1159
2.44M
    MachineBasicBlock *BB = *DFI;
1160
2.44M
    replaceFrameIndices(BB, MF, SPAdj);
1161
2.44M
    SPState[BB->getNumber()] = SPAdj;
1162
2.44M
  }
1163
260k
1164
260k
  // Handle the unreachable blocks.
1165
2.44M
  for (auto &BB : MF) {
1166
2.44M
    if (Reachable.count(&BB))
1167
2.44M
      // Already handled in DFS traversal.
1168
2.44M
      continue;
1169
22
    int SPAdj = 0;
1170
22
    replaceFrameIndices(&BB, MF, SPAdj);
1171
22
  }
1172
260k
}
1173
1174
void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF,
1175
2.44M
                              int &SPAdj) {
1176
2.44M
  assert(MF.getSubtarget().getRegisterInfo() &&
1177
2.44M
         "getRegisterInfo() must be implemented!");
1178
2.44M
  const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
1179
2.44M
  const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
1180
2.44M
  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
1181
2.44M
1182
2.44M
  if (RS && 
FrameIndexEliminationScavenging2.14M
)
1183
608
    RS->enterBasicBlock(*BB);
1184
2.44M
1185
2.44M
  bool InsideCallSequence = false;
1186
2.44M
1187
20.8M
  for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
1188
18.4M
    if (TII.isFrameInstr(*I)) {
1189
2.89k
      InsideCallSequence = TII.isFrameSetup(*I);
1190
2.89k
      SPAdj += TII.getSPAdjust(*I);
1191
2.89k
      I = TFI->eliminateCallFramePseudoInstr(MF, *BB, I);
1192
2.89k
      continue;
1193
2.89k
    }
1194
18.4M
1195
18.4M
    MachineInstr &MI = *I;
1196
18.4M
    bool DoIncr = true;
1197
18.4M
    bool DidFinishLoop = true;
1198
78.3M
    for (unsigned i = 0, e = MI.getNumOperands(); i != e; 
++i59.9M
) {
1199
60.8M
      if (!MI.getOperand(i).isFI())
1200
59.9M
        continue;
1201
939k
1202
939k
      // Frame indices in debug values are encoded in a target independent
1203
939k
      // way with simply the frame index and offset rather than any
1204
939k
      // target-specific addressing mode.
1205
939k
      if (MI.isDebugValue()) {
1206
128
        assert(i == 0 && "Frame indices can only appear as the first "
1207
128
                         "operand of a DBG_VALUE machine instruction");
1208
128
        unsigned Reg;
1209
128
        unsigned FrameIdx = MI.getOperand(0).getIndex();
1210
128
        unsigned Size = MF.getFrameInfo().getObjectSize(FrameIdx);
1211
128
1212
128
        int64_t Offset =
1213
128
            TFI->getFrameIndexReference(MF, FrameIdx, Reg);
1214
128
        MI.getOperand(0).ChangeToRegister(Reg, false /*isDef*/);
1215
128
        MI.getOperand(0).setIsDebug();
1216
128
1217
128
        const DIExpression *DIExpr = MI.getDebugExpression();
1218
128
1219
128
        // If we have a direct DBG_VALUE, and its location expression isn't
1220
128
        // currently complex, then adding an offset will morph it into a
1221
128
        // complex location that is interpreted as being a memory address.
1222
128
        // This changes a pointer-valued variable to dereference that pointer,
1223
128
        // which is incorrect. Fix by adding DW_OP_stack_value.
1224
128
        unsigned PrependFlags = DIExpression::ApplyOffset;
1225
128
        if (!MI.isIndirectDebugValue() && 
!DIExpr->isComplex()47
)
1226
21
          PrependFlags |= DIExpression::StackValue;
1227
128
1228
128
        // If we have DBG_VALUE that is indirect and has a Implicit location
1229
128
        // expression need to insert a deref before prepending a Memory
1230
128
        // location expression. Also after doing this we change the DBG_VALUE
1231
128
        // to be direct.
1232
128
        if (MI.isIndirectDebugValue() && 
DIExpr->isImplicit()81
) {
1233
1
          SmallVector<uint64_t, 2> Ops = {dwarf::DW_OP_deref_size, Size};
1234
1
          bool WithStackValue = true;
1235
1
          DIExpr = DIExpression::prependOpcodes(DIExpr, Ops, WithStackValue);
1236
1
          // Make the DBG_VALUE direct.
1237
1
          MI.getOperand(1).ChangeToRegister(0, false);
1238
1
        }
1239
128
        DIExpr = DIExpression::prepend(DIExpr, PrependFlags, Offset);
1240
128
        MI.getOperand(3).setMetadata(DIExpr);
1241
128
        continue;
1242
128
      }
1243
939k
1244
939k
      // TODO: This code should be commoned with the code for
1245
939k
      // PATCHPOINT. There's no good reason for the difference in
1246
939k
      // implementation other than historical accident.  The only
1247
939k
      // remaining difference is the unconditional use of the stack
1248
939k
      // pointer as the base register.
1249
939k
      if (MI.getOpcode() == TargetOpcode::STATEPOINT) {
1250
277
        assert((!MI.isDebugValue() || i == 0) &&
1251
277
               "Frame indicies can only appear as the first operand of a "
1252
277
               "DBG_VALUE machine instruction");
1253
277
        unsigned Reg;
1254
277
        MachineOperand &Offset = MI.getOperand(i + 1);
1255
277
        int refOffset = TFI->getFrameIndexReferencePreferSP(
1256
277
            MF, MI.getOperand(i).getIndex(), Reg, /*IgnoreSPUpdates*/ false);
1257
277
        Offset.setImm(Offset.getImm() + refOffset + SPAdj);
1258
277
        MI.getOperand(i).ChangeToRegister(Reg, false /*isDef*/);
1259
277
        continue;
1260
277
      }
1261
938k
1262
938k
      // Some instructions (e.g. inline asm instructions) can have
1263
938k
      // multiple frame indices and/or cause eliminateFrameIndex
1264
938k
      // to insert more than one instruction. We need the register
1265
938k
      // scavenger to go through all of these instructions so that
1266
938k
      // it can update its register information. We keep the
1267
938k
      // iterator at the point before insertion so that we can
1268
938k
      // revisit them in full.
1269
938k
      bool AtBeginning = (I == BB->begin());
1270
938k
      if (!AtBeginning) 
--I774k
;
1271
938k
1272
938k
      // If this instruction has a FrameIndex operand, we need to
1273
938k
      // use that target machine register info object to eliminate
1274
938k
      // it.
1275
938k
      TRI.eliminateFrameIndex(MI, SPAdj, i,
1276
938k
                              FrameIndexEliminationScavenging ?  
RS2.11k
:
nullptr936k
);
1277
938k
1278
938k
      // Reset the iterator if we were at the beginning of the BB.
1279
938k
      if (AtBeginning) {
1280
163k
        I = BB->begin();
1281
163k
        DoIncr = false;
1282
163k
      }
1283
938k
1284
938k
      DidFinishLoop = false;
1285
938k
      break;
1286
938k
    }
1287
18.4M
1288
18.4M
    // If we are looking at a call sequence, we need to keep track of
1289
18.4M
    // the SP adjustment made by each instruction in the sequence.
1290
18.4M
    // This includes both the frame setup/destroy pseudos (handled above),
1291
18.4M
    // as well as other instructions that have side effects w.r.t the SP.
1292
18.4M
    // Note that this must come after eliminateFrameIndex, because
1293
18.4M
    // if I itself referred to a frame index, we shouldn't count its own
1294
18.4M
    // adjustment.
1295
18.4M
    if (DidFinishLoop && 
InsideCallSequence17.4M
)
1296
10.0k
      SPAdj += TII.getSPAdjust(MI);
1297
18.4M
1298
18.4M
    if (DoIncr && 
I != BB->end()18.2M
)
++I18.2M
;
1299
18.4M
1300
18.4M
    // Update register states.
1301
18.4M
    if (RS && 
FrameIndexEliminationScavenging15.9M
&&
DidFinishLoop20.0k
)
1302
17.9k
      RS->forward(MI);
1303
18.4M
  }
1304
2.44M
}