Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/ShrinkWrap.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ShrinkWrap.cpp - Compute safe point for prolog/epilog insertion ----===//
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 looks for safe point where the prologue and epilogue can be
10
// inserted.
11
// The safe point for the prologue (resp. epilogue) is called Save
12
// (resp. Restore).
13
// A point is safe for prologue (resp. epilogue) if and only if
14
// it 1) dominates (resp. post-dominates) all the frame related operations and
15
// between 2) two executions of the Save (resp. Restore) point there is an
16
// execution of the Restore (resp. Save) point.
17
//
18
// For instance, the following points are safe:
19
// for (int i = 0; i < 10; ++i) {
20
//   Save
21
//   ...
22
//   Restore
23
// }
24
// Indeed, the execution looks like Save -> Restore -> Save -> Restore ...
25
// And the following points are not:
26
// for (int i = 0; i < 10; ++i) {
27
//   Save
28
//   ...
29
// }
30
// for (int i = 0; i < 10; ++i) {
31
//   ...
32
//   Restore
33
// }
34
// Indeed, the execution looks like Save -> Save -> ... -> Restore -> Restore.
35
//
36
// This pass also ensures that the safe points are 3) cheaper than the regular
37
// entry and exits blocks.
38
//
39
// Property #1 is ensured via the use of MachineDominatorTree and
40
// MachinePostDominatorTree.
41
// Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both
42
// points must be in the same loop.
43
// Property #3 is ensured via the MachineBlockFrequencyInfo.
44
//
45
// If this pass found points matching all these properties, then
46
// MachineFrameInfo is updated with this information.
47
//
48
//===----------------------------------------------------------------------===//
49
50
#include "llvm/ADT/BitVector.h"
51
#include "llvm/ADT/PostOrderIterator.h"
52
#include "llvm/ADT/SetVector.h"
53
#include "llvm/ADT/SmallVector.h"
54
#include "llvm/ADT/Statistic.h"
55
#include "llvm/Analysis/CFG.h"
56
#include "llvm/CodeGen/MachineBasicBlock.h"
57
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
58
#include "llvm/CodeGen/MachineDominators.h"
59
#include "llvm/CodeGen/MachineFrameInfo.h"
60
#include "llvm/CodeGen/MachineFunction.h"
61
#include "llvm/CodeGen/MachineFunctionPass.h"
62
#include "llvm/CodeGen/MachineInstr.h"
63
#include "llvm/CodeGen/MachineLoopInfo.h"
64
#include "llvm/CodeGen/MachineOperand.h"
65
#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
66
#include "llvm/CodeGen/MachinePostDominators.h"
67
#include "llvm/CodeGen/RegisterClassInfo.h"
68
#include "llvm/CodeGen/RegisterScavenging.h"
69
#include "llvm/CodeGen/TargetFrameLowering.h"
70
#include "llvm/CodeGen/TargetInstrInfo.h"
71
#include "llvm/CodeGen/TargetLowering.h"
72
#include "llvm/CodeGen/TargetRegisterInfo.h"
73
#include "llvm/CodeGen/TargetSubtargetInfo.h"
74
#include "llvm/IR/Attributes.h"
75
#include "llvm/IR/Function.h"
76
#include "llvm/MC/MCAsmInfo.h"
77
#include "llvm/Pass.h"
78
#include "llvm/Support/CommandLine.h"
79
#include "llvm/Support/Debug.h"
80
#include "llvm/Support/ErrorHandling.h"
81
#include "llvm/Support/raw_ostream.h"
82
#include "llvm/Target/TargetMachine.h"
83
#include <cassert>
84
#include <cstdint>
85
#include <memory>
86
87
using namespace llvm;
88
89
2
#define DEBUG_TYPE "shrink-wrap"
90
91
STATISTIC(NumFunc, "Number of functions");
92
STATISTIC(NumCandidates, "Number of shrink-wrapping candidates");
93
STATISTIC(NumCandidatesDropped,
94
          "Number of shrink-wrapping candidates dropped because of frequency");
95
96
static cl::opt<cl::boolOrDefault>
97
EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden,
98
                    cl::desc("enable the shrink-wrapping pass"));
99
100
namespace {
101
102
/// Class to determine where the safe point to insert the
103
/// prologue and epilogue are.
104
/// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the
105
/// shrink-wrapping term for prologue/epilogue placement, this pass
106
/// does not rely on expensive data-flow analysis. Instead we use the
107
/// dominance properties and loop information to decide which point
108
/// are safe for such insertion.
109
class ShrinkWrap : public MachineFunctionPass {
110
  /// Hold callee-saved information.
111
  RegisterClassInfo RCI;
112
  MachineDominatorTree *MDT;
113
  MachinePostDominatorTree *MPDT;
114
115
  /// Current safe point found for the prologue.
116
  /// The prologue will be inserted before the first instruction
117
  /// in this basic block.
118
  MachineBasicBlock *Save;
119
120
  /// Current safe point found for the epilogue.
121
  /// The epilogue will be inserted before the first terminator instruction
122
  /// in this basic block.
123
  MachineBasicBlock *Restore;
124
125
  /// Hold the information of the basic block frequency.
126
  /// Use to check the profitability of the new points.
127
  MachineBlockFrequencyInfo *MBFI;
128
129
  /// Hold the loop information. Used to determine if Save and Restore
130
  /// are in the same loop.
131
  MachineLoopInfo *MLI;
132
133
  // Emit remarks.
134
  MachineOptimizationRemarkEmitter *ORE = nullptr;
135
136
  /// Frequency of the Entry block.
137
  uint64_t EntryFreq;
138
139
  /// Current opcode for frame setup.
140
  unsigned FrameSetupOpcode;
141
142
  /// Current opcode for frame destroy.
143
  unsigned FrameDestroyOpcode;
144
145
  /// Stack pointer register, used by llvm.{savestack,restorestack}
146
  unsigned SP;
147
148
  /// Entry block.
149
  const MachineBasicBlock *Entry;
150
151
  using SetOfRegs = SmallSetVector<unsigned, 16>;
152
153
  /// Registers that need to be saved for the current function.
154
  mutable SetOfRegs CurrentCSRs;
155
156
  /// Current MachineFunction.
157
  MachineFunction *MachineFunc;
158
159
  /// Check if \p MI uses or defines a callee-saved register or
160
  /// a frame index. If this is the case, this means \p MI must happen
161
  /// after Save and before Restore.
162
  bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS) const;
163
164
22.1k
  const SetOfRegs &getCurrentCSRs(RegScavenger *RS) const {
165
22.1k
    if (CurrentCSRs.empty()) {
166
19.0k
      BitVector SavedRegs;
167
19.0k
      const TargetFrameLowering *TFI =
168
19.0k
          MachineFunc->getSubtarget().getFrameLowering();
169
19.0k
170
19.0k
      TFI->determineCalleeSaves(*MachineFunc, SavedRegs, RS);
171
19.0k
172
24.2k
      for (int Reg = SavedRegs.find_first(); Reg != -1;
173
19.0k
           
Reg = SavedRegs.find_next(Reg)5.19k
)
174
5.19k
        CurrentCSRs.insert((unsigned)Reg);
175
19.0k
    }
176
22.1k
    return CurrentCSRs;
177
22.1k
  }
178
179
  /// Update the Save and Restore points such that \p MBB is in
180
  /// the region that is dominated by Save and post-dominated by Restore
181
  /// and Save and Restore still match the safe point definition.
182
  /// Such point may not exist and Save and/or Restore may be null after
183
  /// this call.
184
  void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS);
185
186
  /// Initialize the pass for \p MF.
187
362k
  void init(MachineFunction &MF) {
188
362k
    RCI.runOnMachineFunction(MF);
189
362k
    MDT = &getAnalysis<MachineDominatorTree>();
190
362k
    MPDT = &getAnalysis<MachinePostDominatorTree>();
191
362k
    Save = nullptr;
192
362k
    Restore = nullptr;
193
362k
    MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
194
362k
    MLI = &getAnalysis<MachineLoopInfo>();
195
362k
    ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
196
362k
    EntryFreq = MBFI->getEntryFreq();
197
362k
    const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
198
362k
    const TargetInstrInfo &TII = *Subtarget.getInstrInfo();
199
362k
    FrameSetupOpcode = TII.getCallFrameSetupOpcode();
200
362k
    FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
201
362k
    SP = Subtarget.getTargetLowering()->getStackPointerRegisterToSaveRestore();
202
362k
    Entry = &MF.front();
203
362k
    CurrentCSRs.clear();
204
362k
    MachineFunc = &MF;
205
362k
206
362k
    ++NumFunc;
207
362k
  }
208
209
  /// Check whether or not Save and Restore points are still interesting for
210
  /// shrink-wrapping.
211
426k
  bool ArePointsInteresting() const { return Save != Entry && 
Save127k
&&
Restore72.1k
; }
212
213
  /// Check if shrink wrapping is enabled for this target and function.
214
  static bool isShrinkWrapEnabled(const MachineFunction &MF);
215
216
public:
217
  static char ID;
218
219
33.8k
  ShrinkWrap() : MachineFunctionPass(ID) {
220
33.8k
    initializeShrinkWrapPass(*PassRegistry::getPassRegistry());
221
33.8k
  }
222
223
33.6k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
224
33.6k
    AU.setPreservesAll();
225
33.6k
    AU.addRequired<MachineBlockFrequencyInfo>();
226
33.6k
    AU.addRequired<MachineDominatorTree>();
227
33.6k
    AU.addRequired<MachinePostDominatorTree>();
228
33.6k
    AU.addRequired<MachineLoopInfo>();
229
33.6k
    AU.addRequired<MachineOptimizationRemarkEmitterPass>();
230
33.6k
    MachineFunctionPass::getAnalysisUsage(AU);
231
33.6k
  }
232
233
33.6k
  MachineFunctionProperties getRequiredProperties() const override {
234
33.6k
    return MachineFunctionProperties().set(
235
33.6k
      MachineFunctionProperties::Property::NoVRegs);
236
33.6k
  }
237
238
518k
  StringRef getPassName() const override { return "Shrink Wrapping analysis"; }
239
240
  /// Perform the shrink-wrapping analysis and update
241
  /// the MachineFrameInfo attached to \p MF with the results.
242
  bool runOnMachineFunction(MachineFunction &MF) override;
243
};
244
245
} // end anonymous namespace
246
247
char ShrinkWrap::ID = 0;
248
249
char &llvm::ShrinkWrapID = ShrinkWrap::ID;
250
251
42.3k
INITIALIZE_PASS_BEGIN(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false)
252
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
253
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
254
42.3k
INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
255
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
256
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
257
42.3k
INITIALIZE_PASS_END(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false)
258
259
bool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI,
260
1.36M
                                 RegScavenger *RS) const {
261
1.36M
  // This prevents premature stack popping when occurs a indirect stack
262
1.36M
  // access. It is overly aggressive for the moment.
263
1.36M
  // TODO: - Obvious non-stack loads and store, such as global values,
264
1.36M
  //         are known to not access the stack.
265
1.36M
  //       - Further, data dependency and alias analysis can validate
266
1.36M
  //         that load and stores never derive from the stack pointer.
267
1.36M
  if (MI.mayLoadOrStore())
268
143k
    return true;
269
1.21M
270
1.21M
  if (MI.getOpcode() == FrameSetupOpcode ||
271
1.21M
      
MI.getOpcode() == FrameDestroyOpcode1.15M
) {
272
64.4k
    LLVM_DEBUG(dbgs() << "Frame instruction: " << MI << '\n');
273
64.4k
    return true;
274
64.4k
  }
275
2.49M
  
for (const MachineOperand &MO : MI.operands())1.15M
{
276
2.49M
    bool UseOrDefCSR = false;
277
2.49M
    if (MO.isReg()) {
278
1.67M
      // Ignore instructions like DBG_VALUE which don't read/def the register.
279
1.67M
      if (!MO.isDef() && 
!MO.readsReg()988k
)
280
2.28k
        continue;
281
1.66M
      unsigned PhysReg = MO.getReg();
282
1.66M
      if (!PhysReg)
283
58.9k
        continue;
284
1.60M
      assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
285
1.60M
             "Unallocated register?!");
286
1.60M
      // The stack pointer is not normally described as a callee-saved register
287
1.60M
      // in calling convention definitions, so we need to watch for it
288
1.60M
      // separately. An SP mentioned by a call instruction, we can ignore,
289
1.60M
      // though, as it's harmless and we do not want to effectively disable tail
290
1.60M
      // calls by forcing the restore point to post-dominate them.
291
1.60M
      UseOrDefCSR = (!MI.isCall() && 
PhysReg == SP1.53M
) ||
292
1.60M
                    
RCI.getLastCalleeSavedAlias(PhysReg)1.60M
;
293
1.60M
    } else 
if (824k
MO.isRegMask()824k
) {
294
22.1k
      // Check if this regmask clobbers any of the CSRs.
295
23.0k
      for (unsigned Reg : getCurrentCSRs(RS)) {
296
23.0k
        if (MO.clobbersPhysReg(Reg)) {
297
13
          UseOrDefCSR = true;
298
13
          break;
299
13
        }
300
23.0k
      }
301
22.1k
    }
302
2.49M
    // Skip FrameIndex operands in DBG_VALUE instructions.
303
2.49M
    
if (2.43M
UseOrDefCSR2.43M
||
(2.26M
MO.isFI()2.26M
&&
!MI.isDebugValue()2.14k
)) {
304
172k
      LLVM_DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI("
305
172k
                        << MO.isFI() << "): " << MI << '\n');
306
172k
      return true;
307
172k
    }
308
2.43M
  }
309
1.15M
  
return false981k
;
310
1.15M
}
311
312
/// Helper function to find the immediate (post) dominator.
313
template <typename ListOfBBs, typename DominanceAnalysis>
314
static MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs,
315
37.0k
                                   DominanceAnalysis &Dom) {
316
37.0k
  MachineBasicBlock *IDom = &Block;
317
72.4k
  for (MachineBasicBlock *BB : BBs) {
318
72.4k
    IDom = Dom.findNearestCommonDominator(IDom, BB);
319
72.4k
    if (!IDom)
320
1.71k
      break;
321
72.4k
  }
322
37.0k
  if (IDom == &Block)
323
429
    return nullptr;
324
36.6k
  return IDom;
325
36.6k
}
ShrinkWrap.cpp:llvm::MachineBasicBlock* FindIDom<llvm::iterator_range<std::__1::__wrap_iter<llvm::MachineBasicBlock**> >, llvm::MachineDominatorTree>(llvm::MachineBasicBlock&, llvm::iterator_range<std::__1::__wrap_iter<llvm::MachineBasicBlock**> >, llvm::MachineDominatorTree&)
Line
Count
Source
315
2.44k
                                   DominanceAnalysis &Dom) {
316
2.44k
  MachineBasicBlock *IDom = &Block;
317
4.88k
  for (MachineBasicBlock *BB : BBs) {
318
4.88k
    IDom = Dom.findNearestCommonDominator(IDom, BB);
319
4.88k
    if (!IDom)
320
0
      break;
321
4.88k
  }
322
2.44k
  if (IDom == &Block)
323
0
    return nullptr;
324
2.44k
  return IDom;
325
2.44k
}
ShrinkWrap.cpp:llvm::MachineBasicBlock* FindIDom<llvm::iterator_range<std::__1::__wrap_iter<llvm::MachineBasicBlock**> >, llvm::MachinePostDominatorTree>(llvm::MachineBasicBlock&, llvm::iterator_range<std::__1::__wrap_iter<llvm::MachineBasicBlock**> >, llvm::MachinePostDominatorTree&)
Line
Count
Source
315
34.5k
                                   DominanceAnalysis &Dom) {
316
34.5k
  MachineBasicBlock *IDom = &Block;
317
67.5k
  for (MachineBasicBlock *BB : BBs) {
318
67.5k
    IDom = Dom.findNearestCommonDominator(IDom, BB);
319
67.5k
    if (!IDom)
320
1.71k
      break;
321
67.5k
  }
322
34.5k
  if (IDom == &Block)
323
429
    return nullptr;
324
34.1k
  return IDom;
325
34.1k
}
326
327
void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB,
328
362k
                                         RegScavenger *RS) {
329
362k
  // Get rid of the easy cases first.
330
362k
  if (!Save)
331
307k
    Save = &MBB;
332
54.9k
  else
333
54.9k
    Save = MDT->findNearestCommonDominator(Save, &MBB);
334
362k
335
362k
  if (!Save) {
336
0
    LLVM_DEBUG(dbgs() << "Found a block that is not reachable from Entry\n");
337
0
    return;
338
0
  }
339
362k
340
362k
  if (!Restore)
341
307k
    Restore = &MBB;
342
54.9k
  else if (MPDT->getNode(&MBB)) // If the block is not in the post dom tree, it
343
54.9k
                                // means the block never returns. If that's the
344
54.9k
                                // case, we don't want to call
345
54.9k
                                // `findNearestCommonDominator`, which will
346
54.9k
                                // return `Restore`.
347
54.9k
    Restore = MPDT->findNearestCommonDominator(Restore, &MBB);
348
0
  else
349
0
    Restore = nullptr; // Abort, we can't find a restore point in this case.
350
362k
351
362k
  // Make sure we would be able to insert the restore code before the
352
362k
  // terminator.
353
362k
  if (Restore == &MBB) {
354
354k
    for (const MachineInstr &Terminator : MBB.terminators()) {
355
354k
      if (!useOrDefCSROrFI(Terminator, RS))
356
335k
        continue;
357
18.2k
      // One of the terminator needs to happen before the restore point.
358
18.2k
      if (MBB.succ_empty()) {
359
164
        Restore = nullptr; // Abort, we can't find a restore point in this case.
360
164
        break;
361
164
      }
362
18.0k
      // Look for a restore point that post-dominates all the successors.
363
18.0k
      // The immediate post-dominator is what we are looking for.
364
18.0k
      Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
365
18.0k
      break;
366
18.0k
    }
367
334k
  }
368
362k
369
362k
  if (!Restore) {
370
9.04k
    LLVM_DEBUG(
371
9.04k
        dbgs() << "Restore point needs to be spanned on several blocks\n");
372
9.04k
    return;
373
9.04k
  }
374
353k
375
353k
  // Make sure Save and Restore are suitable for shrink-wrapping:
376
353k
  // 1. all path from Save needs to lead to Restore before exiting.
377
353k
  // 2. all path to Restore needs to go through Save from Entry.
378
353k
  // We achieve that by making sure that:
379
353k
  // A. Save dominates Restore.
380
353k
  // B. Restore post-dominates Save.
381
353k
  // C. Save and Restore are in the same loop.
382
353k
  bool SaveDominatesRestore = false;
383
353k
  bool RestorePostDominatesSave = false;
384
378k
  while (Save && Restore &&
385
378k
         
(378k
!(SaveDominatesRestore = MDT->dominates(Save, Restore))378k
||
386
378k
          
!(RestorePostDominatesSave = MPDT->dominates(Restore, Save))371k
||
387
378k
          // Post-dominance is not enough in loops to ensure that all uses/defs
388
378k
          // are after the prologue and before the epilogue at runtime.
389
378k
          // E.g.,
390
378k
          // while(1) {
391
378k
          //  Save
392
378k
          //  Restore
393
378k
          //   if (...)
394
378k
          //     break;
395
378k
          //  use/def CSRs
396
378k
          // }
397
378k
          // All the uses/defs of CSRs are dominated by Save and post-dominated
398
378k
          // by Restore. However, the CSRs uses are still reachable after
399
378k
          // Restore and before Save are executed.
400
378k
          //
401
378k
          // For now, just push the restore/save points outside of loops.
402
378k
          // FIXME: Refine the criteria to still find interesting cases
403
378k
          // for loops.
404
378k
          
MLI->getLoopFor(Save)371k
||
MLI->getLoopFor(Restore)364k
)) {
405
25.5k
    // Fix (A).
406
25.5k
    if (!SaveDominatesRestore) {
407
6.92k
      Save = MDT->findNearestCommonDominator(Save, Restore);
408
6.92k
      continue;
409
6.92k
    }
410
18.5k
    // Fix (B).
411
18.5k
    if (!RestorePostDominatesSave)
412
23
      Restore = MPDT->findNearestCommonDominator(Restore, Save);
413
18.5k
414
18.5k
    // Fix (C).
415
18.5k
    if (Save && Restore &&
416
18.5k
        
(18.5k
MLI->getLoopFor(Save)18.5k
||
MLI->getLoopFor(Restore)11.5k
)) {
417
18.5k
      if (MLI->getLoopDepth(Save) > MLI->getLoopDepth(Restore)) {
418
2.44k
        // Push Save outside of this loop if immediate dominator is different
419
2.44k
        // from save block. If immediate dominator is not different, bail out.
420
2.44k
        Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
421
2.44k
        if (!Save)
422
0
          break;
423
16.1k
      } else {
424
16.1k
        // If the loop does not exit, there is no point in looking
425
16.1k
        // for a post-dominator outside the loop.
426
16.1k
        SmallVector<MachineBasicBlock*, 4> ExitBlocks;
427
16.1k
        MLI->getLoopFor(Restore)->getExitingBlocks(ExitBlocks);
428
16.1k
        // Push Restore outside of this loop.
429
16.1k
        // Look for the immediate post-dominator of the loop exits.
430
16.1k
        MachineBasicBlock *IPdom = Restore;
431
16.5k
        for (MachineBasicBlock *LoopExitBB: ExitBlocks) {
432
16.5k
          IPdom = FindIDom<>(*IPdom, LoopExitBB->successors(), *MPDT);
433
16.5k
          if (!IPdom)
434
462
            break;
435
16.5k
        }
436
16.1k
        // If the immediate post-dominator is not in a less nested loop,
437
16.1k
        // then we are stuck in a program with an infinite loop.
438
16.1k
        // In that case, we will not find a safe point, hence, bail out.
439
16.1k
        if (IPdom && 
MLI->getLoopDepth(IPdom) < MLI->getLoopDepth(Restore)15.6k
)
440
15.6k
          Restore = IPdom;
441
498
        else {
442
498
          Restore = nullptr;
443
498
          break;
444
498
        }
445
16.1k
      }
446
18.5k
    }
447
18.5k
  }
448
353k
}
449
450
static bool giveUpWithRemarks(MachineOptimizationRemarkEmitter *ORE,
451
                              StringRef RemarkName, StringRef RemarkMessage,
452
                              const DiagnosticLocation &Loc,
453
52
                              const MachineBasicBlock *MBB) {
454
52
  ORE->emit([&]() {
455
2
    return MachineOptimizationRemarkMissed(DEBUG_TYPE, RemarkName, Loc, MBB)
456
2
           << RemarkMessage;
457
2
  });
458
52
459
52
  LLVM_DEBUG(dbgs() << RemarkMessage << '\n');
460
52
  return false;
461
52
}
462
463
484k
bool ShrinkWrap::runOnMachineFunction(MachineFunction &MF) {
464
484k
  if (skipFunction(MF.getFunction()) || 
MF.empty()484k
||
!isShrinkWrapEnabled(MF)484k
)
465
121k
    return false;
466
362k
467
362k
  LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
468
362k
469
362k
  init(MF);
470
362k
471
362k
  ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
472
362k
  if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *MLI)) {
473
51
    // If MF is irreducible, a block may be in a loop without
474
51
    // MachineLoopInfo reporting it. I.e., we may use the
475
51
    // post-dominance property in loops, which lead to incorrect
476
51
    // results. Moreover, we may miss that the prologue and
477
51
    // epilogue are not in the same loop, leading to unbalanced
478
51
    // construction/deconstruction of the stack frame.
479
51
    return giveUpWithRemarks(ORE, "UnsupportedIrreducibleCFG",
480
51
                             "Irreducible CFGs are not supported yet.",
481
51
                             MF.getFunction().getSubprogram(), &MF.front());
482
51
  }
483
362k
484
362k
  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
485
362k
  std::unique_ptr<RegScavenger> RS(
486
362k
      TRI->requiresRegisterScavenging(MF) ? 
new RegScavenger()302k
:
nullptr60.4k
);
487
362k
488
529k
  for (MachineBasicBlock &MBB : MF) {
489
529k
    LLVM_DEBUG(dbgs() << "Look into: " << MBB.getNumber() << ' '
490
529k
                      << MBB.getName() << '\n');
491
529k
492
529k
    if (MBB.isEHFuncletEntry())
493
1
      return giveUpWithRemarks(ORE, "UnsupportedEHFunclets",
494
1
                               "EH Funclets are not supported yet.",
495
1
                               MBB.front().getDebugLoc(), &MBB);
496
529k
497
529k
    if (MBB.isEHPad()) {
498
10
      // Push the prologue and epilogue outside of
499
10
      // the region that may throw by making sure
500
10
      // that all the landing pads are at least at the
501
10
      // boundary of the save and restore points.
502
10
      // The problem with exceptions is that the throw
503
10
      // is not properly modeled and in particular, a
504
10
      // basic block can jump out from the middle.
505
10
      updateSaveRestorePoints(MBB, RS.get());
506
10
      if (!ArePointsInteresting()) {
507
7
        LLVM_DEBUG(dbgs() << "EHPad prevents shrink-wrapping\n");
508
7
        return false;
509
7
      }
510
3
      continue;
511
3
    }
512
529k
513
1.00M
    
for (const MachineInstr &MI : MBB)529k
{
514
1.00M
      if (!useOrDefCSROrFI(MI, RS.get()))
515
645k
        continue;
516
362k
      // Save (resp. restore) point must dominate (resp. post dominate)
517
362k
      // MI. Look for the proper basic block for those.
518
362k
      updateSaveRestorePoints(MBB, RS.get());
519
362k
      // If we are at a point where we cannot improve the placement of
520
362k
      // save/restore instructions, just give up.
521
362k
      if (!ArePointsInteresting()) {
522
302k
        LLVM_DEBUG(dbgs() << "No Shrink wrap candidate found\n");
523
302k
        return false;
524
302k
      }
525
59.5k
      // No need to look for other instructions, this basic block
526
59.5k
      // will already be part of the handled region.
527
59.5k
      break;
528
59.5k
    }
529
529k
  }
530
362k
  
if (60.0k
!ArePointsInteresting()60.0k
) {
531
55.4k
    // If the points are not interesting at this point, then they must be null
532
55.4k
    // because it means we did not encounter any frame/CSR related code.
533
55.4k
    // Otherwise, we would have returned from the previous loop.
534
55.4k
    assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!");
535
55.4k
    LLVM_DEBUG(dbgs() << "Nothing to shrink-wrap\n");
536
55.4k
    return false;
537
55.4k
  }
538
4.60k
539
4.60k
  LLVM_DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: " << EntryFreq
540
4.60k
                    << '\n');
541
4.60k
542
4.60k
  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
543
4.60k
  do {
544
4.60k
    LLVM_DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "
545
4.60k
                      << Save->getNumber() << ' ' << Save->getName() << ' '
546
4.60k
                      << MBFI->getBlockFreq(Save).getFrequency()
547
4.60k
                      << "\nRestore: " << Restore->getNumber() << ' '
548
4.60k
                      << Restore->getName() << ' '
549
4.60k
                      << MBFI->getBlockFreq(Restore).getFrequency() << '\n');
550
4.60k
551
4.60k
    bool IsSaveCheap, TargetCanUseSaveAsPrologue = false;
552
4.60k
    if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(Save).getFrequency()) &&
553
4.60k
         
EntryFreq >= MBFI->getBlockFreq(Restore).getFrequency()4.60k
) &&
554
4.60k
        
(4.60k
(TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(*Save))4.60k
&&
555
4.60k
         TFI->canUseAsEpilogue(*Restore)))
556
4.60k
      break;
557
2
    LLVM_DEBUG(
558
2
        dbgs() << "New points are too expensive or invalid for the target\n");
559
2
    MachineBasicBlock *NewBB;
560
2
    if (!IsSaveCheap || 
!TargetCanUseSaveAsPrologue1
) {
561
0
      Save = FindIDom<>(*Save, Save->predecessors(), *MDT);
562
0
      if (!Save)
563
0
        break;
564
0
      NewBB = Save;
565
2
    } else {
566
2
      // Restore is expensive.
567
2
      Restore = FindIDom<>(*Restore, Restore->successors(), *MPDT);
568
2
      if (!Restore)
569
0
        break;
570
2
      NewBB = Restore;
571
2
    }
572
2
    updateSaveRestorePoints(*NewBB, RS.get());
573
2
  } while (Save && 
Restore1
);
574
4.60k
575
4.60k
  if (!ArePointsInteresting()) {
576
1
    ++NumCandidatesDropped;
577
1
    return false;
578
1
  }
579
4.60k
580
4.60k
  LLVM_DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: "
581
4.60k
                    << Save->getNumber() << ' ' << Save->getName()
582
4.60k
                    << "\nRestore: " << Restore->getNumber() << ' '
583
4.60k
                    << Restore->getName() << '\n');
584
4.60k
585
4.60k
  MachineFrameInfo &MFI = MF.getFrameInfo();
586
4.60k
  MFI.setSavePoint(Save);
587
4.60k
  MFI.setRestorePoint(Restore);
588
4.60k
  ++NumCandidates;
589
4.60k
  return false;
590
4.60k
}
591
592
484k
bool ShrinkWrap::isShrinkWrapEnabled(const MachineFunction &MF) {
593
484k
  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
594
484k
595
484k
  switch (EnableShrinkWrapOpt) {
596
484k
  case cl::BOU_UNSET:
597
483k
    return TFI->enableShrinkWrapping(MF) &&
598
483k
           // Windows with CFI has some limitations that make it impossible
599
483k
           // to use shrink-wrapping.
600
483k
           
!MF.getTarget().getMCAsmInfo()->usesWindowsCFI()363k
&&
601
483k
           // Sanitizers look at the value of the stack at the location
602
483k
           // of the crash. Since a crash can happen anywhere, the
603
483k
           // frame must be lowered before anything else happen for the
604
483k
           // sanitizers to be able to get a correct stack frame.
605
483k
           
!(362k
MF.getFunction().hasFnAttribute(Attribute::SanitizeAddress)362k
||
606
362k
             
MF.getFunction().hasFnAttribute(Attribute::SanitizeThread)362k
||
607
362k
             
MF.getFunction().hasFnAttribute(Attribute::SanitizeMemory)362k
||
608
362k
             
MF.getFunction().hasFnAttribute(Attribute::SanitizeHWAddress)362k
);
609
484k
  // If EnableShrinkWrap is set, it takes precedence on whatever the
610
484k
  // target sets. The rational is that we assume we want to test
611
484k
  // something related to shrink-wrapping.
612
484k
  case cl::BOU_TRUE:
613
138
    return true;
614
484k
  case cl::BOU_FALSE:
615
154
    return false;
616
0
  }
617
0
  llvm_unreachable("Invalid shrink-wrapping state");
618
0
}