Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/TailDuplicator.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- TailDuplicator.cpp - Duplicate blocks into predecessors' tails -----===//
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 utility class duplicates basic blocks ending in unconditional branches
10
// into the tails of their predecessors.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/CodeGen/TailDuplicator.h"
15
#include "llvm/ADT/DenseMap.h"
16
#include "llvm/ADT/DenseSet.h"
17
#include "llvm/ADT/STLExtras.h"
18
#include "llvm/ADT/SetVector.h"
19
#include "llvm/ADT/SmallPtrSet.h"
20
#include "llvm/ADT/SmallVector.h"
21
#include "llvm/ADT/Statistic.h"
22
#include "llvm/CodeGen/MachineBasicBlock.h"
23
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
24
#include "llvm/CodeGen/MachineFunction.h"
25
#include "llvm/CodeGen/MachineInstr.h"
26
#include "llvm/CodeGen/MachineInstrBuilder.h"
27
#include "llvm/CodeGen/MachineOperand.h"
28
#include "llvm/CodeGen/MachineRegisterInfo.h"
29
#include "llvm/CodeGen/MachineSSAUpdater.h"
30
#include "llvm/CodeGen/TargetInstrInfo.h"
31
#include "llvm/CodeGen/TargetRegisterInfo.h"
32
#include "llvm/CodeGen/TargetSubtargetInfo.h"
33
#include "llvm/IR/DebugLoc.h"
34
#include "llvm/IR/Function.h"
35
#include "llvm/Support/CommandLine.h"
36
#include "llvm/Support/Debug.h"
37
#include "llvm/Support/ErrorHandling.h"
38
#include "llvm/Support/raw_ostream.h"
39
#include "llvm/Target/TargetMachine.h"
40
#include <algorithm>
41
#include <cassert>
42
#include <iterator>
43
#include <utility>
44
45
using namespace llvm;
46
47
#define DEBUG_TYPE "tailduplication"
48
49
STATISTIC(NumTails, "Number of tails duplicated");
50
STATISTIC(NumTailDups, "Number of tail duplicated blocks");
51
STATISTIC(NumTailDupAdded,
52
          "Number of instructions added due to tail duplication");
53
STATISTIC(NumTailDupRemoved,
54
          "Number of instructions removed due to tail duplication");
55
STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
56
STATISTIC(NumAddedPHIs, "Number of phis added");
57
58
// Heuristic for tail duplication.
59
static cl::opt<unsigned> TailDuplicateSize(
60
    "tail-dup-size",
61
    cl::desc("Maximum instructions to consider tail duplicating"), cl::init(2),
62
    cl::Hidden);
63
64
static cl::opt<unsigned> TailDupIndirectBranchSize(
65
    "tail-dup-indirect-size",
66
    cl::desc("Maximum instructions to consider tail duplicating blocks that "
67
             "end with indirect branches."), cl::init(20),
68
    cl::Hidden);
69
70
static cl::opt<bool>
71
    TailDupVerify("tail-dup-verify",
72
                  cl::desc("Verify sanity of PHI instructions during taildup"),
73
                  cl::init(false), cl::Hidden);
74
75
static cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U),
76
                                      cl::Hidden);
77
78
void TailDuplicator::initMF(MachineFunction &MFin, bool PreRegAlloc,
79
                            const MachineBranchProbabilityInfo *MBPIin,
80
1.12M
                            bool LayoutModeIn, unsigned TailDupSizeIn) {
81
1.12M
  MF = &MFin;
82
1.12M
  TII = MF->getSubtarget().getInstrInfo();
83
1.12M
  TRI = MF->getSubtarget().getRegisterInfo();
84
1.12M
  MRI = &MF->getRegInfo();
85
1.12M
  MMI = &MF->getMMI();
86
1.12M
  MBPI = MBPIin;
87
1.12M
  TailDupSize = TailDupSizeIn;
88
1.12M
89
1.12M
  assert(MBPI != nullptr && "Machine Branch Probability Info required");
90
1.12M
91
1.12M
  LayoutMode = LayoutModeIn;
92
1.12M
  this->PreRegAlloc = PreRegAlloc;
93
1.12M
}
94
95
0
static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) {
96
0
  for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) {
97
0
    MachineBasicBlock *MBB = &*I;
98
0
    SmallSetVector<MachineBasicBlock *, 8> Preds(MBB->pred_begin(),
99
0
                                                 MBB->pred_end());
100
0
    MachineBasicBlock::iterator MI = MBB->begin();
101
0
    while (MI != MBB->end()) {
102
0
      if (!MI->isPHI())
103
0
        break;
104
0
      for (MachineBasicBlock *PredBB : Preds) {
105
0
        bool Found = false;
106
0
        for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
107
0
          MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB();
108
0
          if (PHIBB == PredBB) {
109
0
            Found = true;
110
0
            break;
111
0
          }
112
0
        }
113
0
        if (!Found) {
114
0
          dbgs() << "Malformed PHI in " << printMBBReference(*MBB) << ": "
115
0
                 << *MI;
116
0
          dbgs() << "  missing input from predecessor "
117
0
                 << printMBBReference(*PredBB) << '\n';
118
0
          llvm_unreachable(nullptr);
119
0
        }
120
0
      }
121
0
122
0
      for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
123
0
        MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB();
124
0
        if (CheckExtra && !Preds.count(PHIBB)) {
125
0
          dbgs() << "Warning: malformed PHI in " << printMBBReference(*MBB)
126
0
                 << ": " << *MI;
127
0
          dbgs() << "  extra input from predecessor "
128
0
                 << printMBBReference(*PHIBB) << '\n';
129
0
          llvm_unreachable(nullptr);
130
0
        }
131
0
        if (PHIBB->getNumber() < 0) {
132
0
          dbgs() << "Malformed PHI in " << printMBBReference(*MBB) << ": "
133
0
                 << *MI;
134
0
          dbgs() << "  non-existing " << printMBBReference(*PHIBB) << '\n';
135
0
          llvm_unreachable(nullptr);
136
0
        }
137
0
      }
138
0
      ++MI;
139
0
    }
140
0
  }
141
0
}
142
143
/// Tail duplicate the block and cleanup.
144
/// \p IsSimple - return value of isSimpleBB
145
/// \p MBB - block to be duplicated
146
/// \p ForcedLayoutPred - If non-null, treat this block as the layout
147
///     predecessor, instead of using the ordering in MF
148
/// \p DuplicatedPreds - if non-null, \p DuplicatedPreds will contain a list of
149
///     all Preds that received a copy of \p MBB.
150
/// \p RemovalCallback - if non-null, called just before MBB is deleted.
151
bool TailDuplicator::tailDuplicateAndUpdate(
152
    bool IsSimple, MachineBasicBlock *MBB,
153
    MachineBasicBlock *ForcedLayoutPred,
154
    SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds,
155
989k
    function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
156
989k
  // Save the successors list.
157
989k
  SmallSetVector<MachineBasicBlock *, 8> Succs(MBB->succ_begin(),
158
989k
                                               MBB->succ_end());
159
989k
160
989k
  SmallVector<MachineBasicBlock *, 8> TDBBs;
161
989k
  SmallVector<MachineInstr *, 16> Copies;
162
989k
  if (!tailDuplicate(IsSimple, MBB, ForcedLayoutPred, TDBBs, Copies))
163
841k
    return false;
164
148k
165
148k
  ++NumTails;
166
148k
167
148k
  SmallVector<MachineInstr *, 8> NewPHIs;
168
148k
  MachineSSAUpdater SSAUpdate(*MF, &NewPHIs);
169
148k
170
148k
  // TailBB's immediate successors are now successors of those predecessors
171
148k
  // which duplicated TailBB. Add the predecessors as sources to the PHI
172
148k
  // instructions.
173
148k
  bool isDead = MBB->pred_empty() && 
!MBB->hasAddressTaken()90.2k
;
174
148k
  if (PreRegAlloc)
175
38.7k
    updateSuccessorsPHIs(MBB, isDead, TDBBs, Succs);
176
148k
177
148k
  // If it is dead, remove it.
178
148k
  if (isDead) {
179
90.2k
    NumTailDupRemoved += MBB->size();
180
90.2k
    removeDeadBlock(MBB, RemovalCallback);
181
90.2k
    ++NumDeadBlocks;
182
90.2k
  }
183
148k
184
148k
  // Update SSA form.
185
148k
  if (!SSAUpdateVRs.empty()) {
186
1.49k
    for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; 
++i818
) {
187
818
      unsigned VReg = SSAUpdateVRs[i];
188
818
      SSAUpdate.Initialize(VReg);
189
818
190
818
      // If the original definition is still around, add it as an available
191
818
      // value.
192
818
      MachineInstr *DefMI = MRI->getVRegDef(VReg);
193
818
      MachineBasicBlock *DefBB = nullptr;
194
818
      if (DefMI) {
195
4
        DefBB = DefMI->getParent();
196
4
        SSAUpdate.AddAvailableValue(DefBB, VReg);
197
4
      }
198
818
199
818
      // Add the new vregs as available values.
200
818
      DenseMap<unsigned, AvailableValsTy>::iterator LI =
201
818
          SSAUpdateVals.find(VReg);
202
3.27k
      for (unsigned j = 0, ee = LI->second.size(); j != ee; 
++j2.45k
) {
203
2.45k
        MachineBasicBlock *SrcBB = LI->second[j].first;
204
2.45k
        unsigned SrcReg = LI->second[j].second;
205
2.45k
        SSAUpdate.AddAvailableValue(SrcBB, SrcReg);
206
2.45k
      }
207
818
208
818
      // Rewrite uses that are outside of the original def's block.
209
818
      MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg);
210
954
      while (UI != MRI->use_end()) {
211
136
        MachineOperand &UseMO = *UI;
212
136
        MachineInstr *UseMI = UseMO.getParent();
213
136
        ++UI;
214
136
        if (UseMI->isDebugValue()) {
215
0
          // SSAUpdate can replace the use with an undef. That creates
216
0
          // a debug instruction that is a kill.
217
0
          // FIXME: Should it SSAUpdate job to delete debug instructions
218
0
          // instead of replacing the use with undef?
219
0
          UseMI->eraseFromParent();
220
0
          continue;
221
0
        }
222
136
        if (UseMI->getParent() == DefBB && 
!UseMI->isPHI()0
)
223
0
          continue;
224
136
        SSAUpdate.RewriteUse(UseMO);
225
136
      }
226
818
    }
227
673
228
673
    SSAUpdateVRs.clear();
229
673
    SSAUpdateVals.clear();
230
673
  }
231
148k
232
148k
  // Eliminate some of the copies inserted by tail duplication to maintain
233
148k
  // SSA form.
234
150k
  for (unsigned i = 0, e = Copies.size(); i != e; 
++i2.55k
) {
235
2.55k
    MachineInstr *Copy = Copies[i];
236
2.55k
    if (!Copy->isCopy())
237
0
      continue;
238
2.55k
    unsigned Dst = Copy->getOperand(0).getReg();
239
2.55k
    unsigned Src = Copy->getOperand(1).getReg();
240
2.55k
    if (MRI->hasOneNonDBGUse(Src) &&
241
2.55k
        
MRI->constrainRegClass(Src, MRI->getRegClass(Dst))1.82k
) {
242
1.82k
      // Copy is the only use. Do trivial copy propagation here.
243
1.82k
      MRI->replaceRegWith(Dst, Src);
244
1.82k
      Copy->eraseFromParent();
245
1.82k
    }
246
2.55k
  }
247
148k
248
148k
  if (NewPHIs.size())
249
16
    NumAddedPHIs += NewPHIs.size();
250
148k
251
148k
  if (DuplicatedPreds)
252
93.5k
    *DuplicatedPreds = std::move(TDBBs);
253
148k
254
148k
  return true;
255
148k
}
256
257
/// Look for small blocks that are unconditionally branched to and do not fall
258
/// through. Tail-duplicate their instructions into their predecessors to
259
/// eliminate (dynamic) branches.
260
1.01M
bool TailDuplicator::tailDuplicateBlocks() {
261
1.01M
  bool MadeChange = false;
262
1.01M
263
1.01M
  if (PreRegAlloc && 
TailDupVerify515k
) {
264
0
    LLVM_DEBUG(dbgs() << "\n*** Before tail-duplicating\n");
265
0
    VerifyPHIs(*MF, true);
266
0
  }
267
1.01M
268
6.79M
  for (MachineFunction::iterator I = ++MF->begin(), E = MF->end(); I != E;) {
269
5.77M
    MachineBasicBlock *MBB = &*I++;
270
5.77M
271
5.77M
    if (NumTails == TailDupLimit)
272
0
      break;
273
5.77M
274
5.77M
    bool IsSimple = isSimpleBB(MBB);
275
5.77M
276
5.77M
    if (!shouldTailDuplicate(IsSimple, *MBB))
277
5.47M
      continue;
278
300k
279
300k
    MadeChange |= tailDuplicateAndUpdate(IsSimple, MBB, nullptr);
280
300k
  }
281
1.01M
282
1.01M
  if (PreRegAlloc && 
TailDupVerify515k
)
283
0
    VerifyPHIs(*MF, false);
284
1.01M
285
1.01M
  return MadeChange;
286
1.01M
}
287
288
static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB,
289
3.24k
                         const MachineRegisterInfo *MRI) {
290
3.24k
  for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
291
3.24k
    if (UseMI.isDebugValue())
292
0
      continue;
293
3.24k
    if (UseMI.getParent() != BB)
294
2.45k
      return true;
295
3.24k
  }
296
3.24k
  
return false788
;
297
3.24k
}
298
299
117k
static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) {
300
431k
  for (unsigned i = 1, e = MI->getNumOperands(); i != e; 
i += 2313k
)
301
431k
    if (MI->getOperand(i + 1).getMBB() == SrcBB)
302
117k
      return i;
303
117k
  
return 00
;
304
117k
}
305
306
// Remember which registers are used by phis in this block. This is
307
// used to determine which registers are liveout while modifying the
308
// block (which is why we need to copy the information).
309
static void getRegsUsedByPHIs(const MachineBasicBlock &BB,
310
989k
                              DenseSet<unsigned> *UsedByPhi) {
311
989k
  for (const auto &MI : BB) {
312
987k
    if (!MI.isPHI())
313
986k
      break;
314
3.51k
    
for (unsigned i = 1, e = MI.getNumOperands(); 901
i != e;
i += 22.61k
) {
315
2.61k
      unsigned SrcReg = MI.getOperand(i).getReg();
316
2.61k
      UsedByPhi->insert(SrcReg);
317
2.61k
    }
318
901
  }
319
989k
}
320
321
/// Add a definition and source virtual registers pair for SSA update.
322
void TailDuplicator::addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
323
2.45k
                                       MachineBasicBlock *BB) {
324
2.45k
  DenseMap<unsigned, AvailableValsTy>::iterator LI =
325
2.45k
      SSAUpdateVals.find(OrigReg);
326
2.45k
  if (LI != SSAUpdateVals.end())
327
1.64k
    LI->second.push_back(std::make_pair(BB, NewReg));
328
818
  else {
329
818
    AvailableValsTy Vals;
330
818
    Vals.push_back(std::make_pair(BB, NewReg));
331
818
    SSAUpdateVals.insert(std::make_pair(OrigReg, Vals));
332
818
    SSAUpdateVRs.push_back(OrigReg);
333
818
  }
334
2.45k
}
335
336
/// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the
337
/// source register that's contributed by PredBB and update SSA update map.
338
void TailDuplicator::processPHI(
339
    MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB,
340
    DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
341
    SmallVectorImpl<std::pair<unsigned, RegSubRegPair>> &Copies,
342
2.55k
    const DenseSet<unsigned> &RegsUsedByPhi, bool Remove) {
343
2.55k
  unsigned DefReg = MI->getOperand(0).getReg();
344
2.55k
  unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB);
345
2.55k
  assert(SrcOpIdx && "Unable to find matching PHI source?");
346
2.55k
  unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg();
347
2.55k
  unsigned SrcSubReg = MI->getOperand(SrcOpIdx).getSubReg();
348
2.55k
  const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
349
2.55k
  LocalVRMap.insert(std::make_pair(DefReg, RegSubRegPair(SrcReg, SrcSubReg)));
350
2.55k
351
2.55k
  // Insert a copy from source to the end of the block. The def register is the
352
2.55k
  // available value liveout of the block.
353
2.55k
  unsigned NewDef = MRI->createVirtualRegister(RC);
354
2.55k
  Copies.push_back(std::make_pair(NewDef, RegSubRegPair(SrcReg, SrcSubReg)));
355
2.55k
  if (isDefLiveOut(DefReg, TailBB, MRI) || 
RegsUsedByPhi.count(DefReg)472
)
356
2.08k
    addSSAUpdateEntry(DefReg, NewDef, PredBB);
357
2.55k
358
2.55k
  if (!Remove)
359
4
    return;
360
2.55k
361
2.55k
  // Remove PredBB from the PHI node.
362
2.55k
  MI->RemoveOperand(SrcOpIdx + 1);
363
2.55k
  MI->RemoveOperand(SrcOpIdx);
364
2.55k
  if (MI->getNumOperands() == 1)
365
856
    MI->eraseFromParent();
366
2.55k
}
367
368
/// Duplicate a TailBB instruction to PredBB and update
369
/// the source operands due to earlier PHI translation.
370
void TailDuplicator::duplicateInstruction(
371
    MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB,
372
    DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
373
680k
    const DenseSet<unsigned> &UsedByPhi) {
374
680k
  // Allow duplication of CFI instructions.
375
680k
  if (MI->isCFIInstruction()) {
376
65
    BuildMI(*PredBB, PredBB->end(), PredBB->findDebugLoc(PredBB->begin()),
377
65
      TII->get(TargetOpcode::CFI_INSTRUCTION)).addCFIIndex(
378
65
      MI->getOperand(0).getCFIIndex());
379
65
    return;
380
65
  }
381
680k
  MachineInstr &NewMI = TII->duplicate(*PredBB, PredBB->end(), *MI);
382
680k
  if (PreRegAlloc) {
383
9.93k
    for (unsigned i = 0, e = NewMI.getNumOperands(); i != e; 
++i6.43k
) {
384
6.43k
      MachineOperand &MO = NewMI.getOperand(i);
385
6.43k
      if (!MO.isReg())
386
3.62k
        continue;
387
2.80k
      unsigned Reg = MO.getReg();
388
2.80k
      if (!TargetRegisterInfo::isVirtualRegister(Reg))
389
895
        continue;
390
1.91k
      if (MO.isDef()) {
391
686
        const TargetRegisterClass *RC = MRI->getRegClass(Reg);
392
686
        unsigned NewReg = MRI->createVirtualRegister(RC);
393
686
        MO.setReg(NewReg);
394
686
        LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
395
686
        if (isDefLiveOut(Reg, TailBB, MRI) || 
UsedByPhi.count(Reg)316
)
396
373
          addSSAUpdateEntry(Reg, NewReg, PredBB);
397
1.22k
      } else {
398
1.22k
        auto VI = LocalVRMap.find(Reg);
399
1.22k
        if (VI != LocalVRMap.end()) {
400
815
          // Need to make sure that the register class of the mapped register
401
815
          // will satisfy the constraints of the class of the register being
402
815
          // replaced.
403
815
          auto *OrigRC = MRI->getRegClass(Reg);
404
815
          auto *MappedRC = MRI->getRegClass(VI->second.Reg);
405
815
          const TargetRegisterClass *ConstrRC;
406
815
          if (VI->second.SubReg != 0) {
407
0
            ConstrRC = TRI->getMatchingSuperRegClass(MappedRC, OrigRC,
408
0
                                                     VI->second.SubReg);
409
0
            if (ConstrRC) {
410
0
              // The actual constraining (as in "find appropriate new class")
411
0
              // is done by getMatchingSuperRegClass, so now we only need to
412
0
              // change the class of the mapped register.
413
0
              MRI->setRegClass(VI->second.Reg, ConstrRC);
414
0
            }
415
815
          } else {
416
815
            // For mapped registers that do not have sub-registers, simply
417
815
            // restrict their class to match the original one.
418
815
            ConstrRC = MRI->constrainRegClass(VI->second.Reg, OrigRC);
419
815
          }
420
815
421
815
          if (ConstrRC) {
422
814
            // If the class constraining succeeded, we can simply replace
423
814
            // the old register with the mapped one.
424
814
            MO.setReg(VI->second.Reg);
425
814
            // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a
426
814
            // sub-register, we need to compose the sub-register indices.
427
814
            MO.setSubReg(TRI->composeSubRegIndices(MO.getSubReg(),
428
814
                                                   VI->second.SubReg));
429
814
          } else {
430
1
            // The direct replacement is not possible, due to failing register
431
1
            // class constraints. An explicit COPY is necessary. Create one
432
1
            // that can be reused
433
1
            auto *NewRC = MI->getRegClassConstraint(i, TII, TRI);
434
1
            if (NewRC == nullptr)
435
1
              NewRC = OrigRC;
436
1
            unsigned NewReg = MRI->createVirtualRegister(NewRC);
437
1
            BuildMI(*PredBB, NewMI, NewMI.getDebugLoc(),
438
1
                    TII->get(TargetOpcode::COPY), NewReg)
439
1
                .addReg(VI->second.Reg, 0, VI->second.SubReg);
440
1
            LocalVRMap.erase(VI);
441
1
            LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
442
1
            MO.setReg(NewReg);
443
1
            // The composed VI.Reg:VI.SubReg is replaced with NewReg, which
444
1
            // is equivalent to the whole register Reg. Hence, Reg:subreg
445
1
            // is same as NewReg:subreg, so keep the sub-register index
446
1
            // unchanged.
447
1
          }
448
815
          // Clear any kill flags from this operand.  The new register could
449
815
          // have uses after this one, so kills are not valid here.
450
815
          MO.setIsKill(false);
451
815
        }
452
1.22k
      }
453
1.91k
    }
454
3.50k
  }
455
680k
}
456
457
/// After FromBB is tail duplicated into its predecessor blocks, the successors
458
/// have gained new predecessors. Update the PHI instructions in them
459
/// accordingly.
460
void TailDuplicator::updateSuccessorsPHIs(
461
    MachineBasicBlock *FromBB, bool isDead,
462
    SmallVectorImpl<MachineBasicBlock *> &TDBBs,
463
38.7k
    SmallSetVector<MachineBasicBlock *, 8> &Succs) {
464
39.2k
  for (MachineBasicBlock *SuccBB : Succs) {
465
81.9k
    for (MachineInstr &MI : *SuccBB) {
466
81.9k
      if (!MI.isPHI())
467
38.9k
        break;
468
43.0k
      MachineInstrBuilder MIB(*FromBB->getParent(), MI);
469
43.0k
      unsigned Idx = 0;
470
87.4k
      for (unsigned i = 1, e = MI.getNumOperands(); i != e; 
i += 244.4k
) {
471
87.4k
        MachineOperand &MO = MI.getOperand(i + 1);
472
87.4k
        if (MO.getMBB() == FromBB) {
473
43.0k
          Idx = i;
474
43.0k
          break;
475
43.0k
        }
476
87.4k
      }
477
43.0k
478
43.0k
      assert(Idx != 0);
479
43.0k
      MachineOperand &MO0 = MI.getOperand(Idx);
480
43.0k
      unsigned Reg = MO0.getReg();
481
43.0k
      if (isDead) {
482
42.8k
        // Folded into the previous BB.
483
42.8k
        // There could be duplicate phi source entries. FIXME: Should sdisel
484
42.8k
        // or earlier pass fixed this?
485
72.7k
        for (unsigned i = MI.getNumOperands() - 2; i != Idx; 
i -= 229.9k
) {
486
29.9k
          MachineOperand &MO = MI.getOperand(i + 1);
487
29.9k
          if (MO.getMBB() == FromBB) {
488
0
            MI.RemoveOperand(i + 1);
489
0
            MI.RemoveOperand(i);
490
0
          }
491
29.9k
        }
492
42.8k
      } else
493
173
        Idx = 0;
494
43.0k
495
43.0k
      // If Idx is set, the operands at Idx and Idx+1 must be removed.
496
43.0k
      // We reuse the location to avoid expensive RemoveOperand calls.
497
43.0k
498
43.0k
      DenseMap<unsigned, AvailableValsTy>::iterator LI =
499
43.0k
          SSAUpdateVals.find(Reg);
500
43.0k
      if (LI != SSAUpdateVals.end()) {
501
804
        // This register is defined in the tail block.
502
3.22k
        for (unsigned j = 0, ee = LI->second.size(); j != ee; 
++j2.42k
) {
503
2.42k
          MachineBasicBlock *SrcBB = LI->second[j].first;
504
2.42k
          // If we didn't duplicate a bb into a particular predecessor, we
505
2.42k
          // might still have added an entry to SSAUpdateVals to correcly
506
2.42k
          // recompute SSA. If that case, avoid adding a dummy extra argument
507
2.42k
          // this PHI.
508
2.42k
          if (!SrcBB->isSuccessor(SuccBB))
509
2
            continue;
510
2.42k
511
2.42k
          unsigned SrcReg = LI->second[j].second;
512
2.42k
          if (Idx != 0) {
513
802
            MI.getOperand(Idx).setReg(SrcReg);
514
802
            MI.getOperand(Idx + 1).setMBB(SrcBB);
515
802
            Idx = 0;
516
1.62k
          } else {
517
1.62k
            MIB.addReg(SrcReg).addMBB(SrcBB);
518
1.62k
          }
519
2.42k
        }
520
42.2k
      } else {
521
42.2k
        // Live in tail block, must also be live in predecessors.
522
88.8k
        for (unsigned j = 0, ee = TDBBs.size(); j != ee; 
++j46.6k
) {
523
46.6k
          MachineBasicBlock *SrcBB = TDBBs[j];
524
46.6k
          if (Idx != 0) {
525
42.0k
            MI.getOperand(Idx).setReg(Reg);
526
42.0k
            MI.getOperand(Idx + 1).setMBB(SrcBB);
527
42.0k
            Idx = 0;
528
42.0k
          } else {
529
4.53k
            MIB.addReg(Reg).addMBB(SrcBB);
530
4.53k
          }
531
46.6k
        }
532
42.2k
      }
533
43.0k
      if (Idx != 0) {
534
0
        MI.RemoveOperand(Idx + 1);
535
0
        MI.RemoveOperand(Idx);
536
0
      }
537
43.0k
    }
538
39.2k
  }
539
38.7k
}
540
541
/// Determine if it is profitable to duplicate this block.
542
bool TailDuplicator::shouldTailDuplicate(bool IsSimple,
543
9.11M
                                         MachineBasicBlock &TailBB) {
544
9.11M
  // When doing tail-duplication during layout, the block ordering is in flux,
545
9.11M
  // so canFallThrough returns a result based on incorrect information and
546
9.11M
  // should just be ignored.
547
9.11M
  if (!LayoutMode && 
TailBB.canFallThrough()5.77M
)
548
4.05M
    return false;
549
5.06M
550
5.06M
  // Don't try to tail-duplicate single-block loops.
551
5.06M
  if (TailBB.isSuccessor(&TailBB))
552
264k
    return false;
553
4.79M
554
4.79M
  // Set the limit on the cost to duplicate. When optimizing for size,
555
4.79M
  // duplicate only one, because one branch instruction can be eliminated to
556
4.79M
  // compensate for the duplication.
557
4.79M
  unsigned MaxDuplicateCount;
558
4.79M
  if (TailDupSize == 0 &&
559
4.79M
      
TailDuplicateSize.getNumOccurrences() == 01.64M
&&
560
4.79M
      
MF->getFunction().hasOptSize()1.64M
)
561
9.45k
    MaxDuplicateCount = 1;
562
4.78M
  else if (TailDupSize == 0)
563
1.63M
    MaxDuplicateCount = TailDuplicateSize;
564
3.15M
  else
565
3.15M
    MaxDuplicateCount = TailDupSize;
566
4.79M
567
4.79M
  // If the block to be duplicated ends in an unanalyzable fallthrough, don't
568
4.79M
  // duplicate it.
569
4.79M
  // A similar check is necessary in MachineBlockPlacement to make sure pairs of
570
4.79M
  // blocks with unanalyzable fallthrough get layed out contiguously.
571
4.79M
  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
572
4.79M
  SmallVector<MachineOperand, 4> PredCond;
573
4.79M
  if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond) &&
574
4.79M
      
TailBB.canFallThrough()1.23M
)
575
43
    return false;
576
4.79M
577
4.79M
  // If the target has hardware branch prediction that can handle indirect
578
4.79M
  // branches, duplicating them can often make them predictable when there
579
4.79M
  // are common paths through the code.  The limit needs to be high enough
580
4.79M
  // to allow undoing the effects of tail merging and other optimizations
581
4.79M
  // that rearrange the predecessors of the indirect branch.
582
4.79M
583
4.79M
  bool HasIndirectbr = false;
584
4.79M
  if (!TailBB.empty())
585
4.79M
    HasIndirectbr = TailBB.back().isIndirectBranch();
586
4.79M
587
4.79M
  if (HasIndirectbr && 
PreRegAlloc16.7k
)
588
5.36k
    MaxDuplicateCount = TailDupIndirectBranchSize;
589
4.79M
590
4.79M
  // Check the instructions in the block to determine whether tail-duplication
591
4.79M
  // is invalid or unlikely to be profitable.
592
4.79M
  unsigned InstrCount = 0;
593
15.4M
  for (MachineInstr &MI : TailBB) {
594
15.4M
    // Non-duplicable things shouldn't be tail-duplicated.
595
15.4M
    // CFI instructions are marked as non-duplicable, because Darwin compact
596
15.4M
    // unwind info emission can't handle multiple prologue setups. In case of
597
15.4M
    // DWARF, allow them be duplicated, so that their existence doesn't prevent
598
15.4M
    // tail duplication of some basic blocks, that would be duplicated otherwise.
599
15.4M
    if (MI.isNotDuplicable() &&
600
15.4M
        
(89.4k
TailBB.getParent()->getTarget().getTargetTriple().isOSDarwin()89.4k
||
601
89.4k
        
!MI.isCFIInstruction()6.43k
))
602
83.7k
      return false;
603
15.3M
604
15.3M
    // Convergent instructions can be duplicated only if doing so doesn't add
605
15.3M
    // new control dependencies, which is what we're going to do here.
606
15.3M
    if (MI.isConvergent())
607
607
      return false;
608
15.3M
609
15.3M
    // Do not duplicate 'return' instructions if this is a pre-regalloc run.
610
15.3M
    // A return may expand into a lot more instructions (e.g. reload of callee
611
15.3M
    // saved registers) after PEI.
612
15.3M
    if (PreRegAlloc && 
MI.isReturn()2.41M
)
613
120k
      return false;
614
15.2M
615
15.2M
    // Avoid duplicating calls before register allocation. Calls presents a
616
15.2M
    // barrier to register allocation so duplicating them may end up increasing
617
15.2M
    // spills.
618
15.2M
    if (PreRegAlloc && 
MI.isCall()2.29M
)
619
73.2k
      return false;
620
15.1M
621
15.1M
    if (!MI.isPHI() && 
!MI.isMetaInstruction()14.9M
)
622
14.9M
      InstrCount += 1;
623
15.1M
624
15.1M
    if (InstrCount > MaxDuplicateCount)
625
2.15M
      return false;
626
15.1M
  }
627
4.79M
628
4.79M
  // Check if any of the successors of TailBB has a PHI node in which the
629
4.79M
  // value corresponding to TailBB uses a subregister.
630
4.79M
  // If a phi node uses a register paired with a subregister, the actual
631
4.79M
  // "value type" of the phi may differ from the type of the register without
632
4.79M
  // any subregisters. Due to a bug, tail duplication may add a new operand
633
4.79M
  // without a necessary subregister, producing an invalid code. This is
634
4.79M
  // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll.
635
4.79M
  // Disable tail duplication for this case for now, until the problem is
636
4.79M
  // fixed.
637
4.79M
  
for (auto SB : TailBB.successors())2.36M
{
638
3.95M
    for (auto &I : *SB) {
639
3.95M
      if (!I.isPHI())
640
3.83M
        break;
641
115k
      unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB);
642
115k
      assert(Idx != 0);
643
115k
      MachineOperand &PU = I.getOperand(Idx);
644
115k
      if (PU.getSubReg() != 0)
645
0
        return false;
646
115k
    }
647
3.83M
  }
648
2.36M
649
2.36M
  if (HasIndirectbr && 
PreRegAlloc12.7k
)
650
4.67k
    return true;
651
2.36M
652
2.36M
  if (IsSimple)
653
39.8k
    return true;
654
2.32M
655
2.32M
  if (!PreRegAlloc)
656
2.26M
    return true;
657
57.1k
658
57.1k
  return canCompletelyDuplicateBB(TailBB);
659
57.1k
}
660
661
/// True if this BB has only one unconditional jump.
662
10.8M
bool TailDuplicator::isSimpleBB(MachineBasicBlock *TailBB) {
663
10.8M
  if (TailBB->succ_size() != 1)
664
7.72M
    return false;
665
3.10M
  if (TailBB->pred_empty())
666
2
    return false;
667
3.10M
  MachineBasicBlock::iterator I = TailBB->getFirstNonDebugInstr();
668
3.10M
  if (I == TailBB->end())
669
89.7k
    return true;
670
3.01M
  return I->isUnconditionalBranch();
671
3.01M
}
672
673
static bool bothUsedInPHI(const MachineBasicBlock &A,
674
49.4k
                          const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) {
675
49.4k
  for (MachineBasicBlock *BB : A.successors())
676
104k
    if (SuccsB.count(BB) && 
!BB->empty()1.42k
&&
BB->begin()->isPHI()1.42k
)
677
1.34k
      return true;
678
49.4k
679
49.4k
  
return false48.1k
;
680
49.4k
}
681
682
57.1k
bool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) {
683
68.7k
  for (MachineBasicBlock *PredBB : BB.predecessors()) {
684
68.7k
    if (PredBB->succ_size() > 1)
685
56.0k
      return false;
686
12.7k
687
12.7k
    MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
688
12.7k
    SmallVector<MachineOperand, 4> PredCond;
689
12.7k
    if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
690
21
      return false;
691
12.6k
692
12.6k
    if (!PredCond.empty())
693
1
      return false;
694
12.6k
  }
695
57.1k
  
return true1.06k
;
696
57.1k
}
697
698
bool TailDuplicator::duplicateSimpleBB(
699
    MachineBasicBlock *TailBB, SmallVectorImpl<MachineBasicBlock *> &TDBBs,
700
    const DenseSet<unsigned> &UsedByPhi,
701
39.8k
    SmallVectorImpl<MachineInstr *> &Copies) {
702
39.8k
  SmallPtrSet<MachineBasicBlock *, 8> Succs(TailBB->succ_begin(),
703
39.8k
                                            TailBB->succ_end());
704
39.8k
  SmallVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(),
705
39.8k
                                            TailBB->pred_end());
706
39.8k
  bool Changed = false;
707
49.8k
  for (MachineBasicBlock *PredBB : Preds) {
708
49.8k
    if (PredBB->hasEHPadSuccessor())
709
354
      continue;
710
49.4k
711
49.4k
    if (bothUsedInPHI(*PredBB, Succs))
712
1.34k
      continue;
713
48.1k
714
48.1k
    MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
715
48.1k
    SmallVector<MachineOperand, 4> PredCond;
716
48.1k
    if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
717
421
      continue;
718
47.7k
719
47.7k
    Changed = true;
720
47.7k
    LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
721
47.7k
                      << "From simple Succ: " << *TailBB);
722
47.7k
723
47.7k
    MachineBasicBlock *NewTarget = *TailBB->succ_begin();
724
47.7k
    MachineBasicBlock *NextBB = PredBB->getNextNode();
725
47.7k
726
47.7k
    // Make PredFBB explicit.
727
47.7k
    if (PredCond.empty())
728
9.34k
      PredFBB = PredTBB;
729
47.7k
730
47.7k
    // Make fall through explicit.
731
47.7k
    if (!PredTBB)
732
3.49k
      PredTBB = NextBB;
733
47.7k
    if (!PredFBB)
734
33.5k
      PredFBB = NextBB;
735
47.7k
736
47.7k
    // Redirect
737
47.7k
    if (PredFBB == TailBB)
738
39.8k
      PredFBB = NewTarget;
739
47.7k
    if (PredTBB == TailBB)
740
17.2k
      PredTBB = NewTarget;
741
47.7k
742
47.7k
    // Make the branch unconditional if possible
743
47.7k
    if (PredTBB == PredFBB) {
744
9.39k
      PredCond.clear();
745
9.39k
      PredFBB = nullptr;
746
9.39k
    }
747
47.7k
748
47.7k
    // Avoid adding fall through branches.
749
47.7k
    if (PredFBB == NextBB)
750
5.96k
      PredFBB = nullptr;
751
47.7k
    if (PredTBB == NextBB && 
PredFBB == nullptr54
)
752
16
      PredTBB = nullptr;
753
47.7k
754
47.7k
    auto DL = PredBB->findBranchDebugLoc();
755
47.7k
    TII->removeBranch(*PredBB);
756
47.7k
757
47.7k
    if (!PredBB->isSuccessor(NewTarget))
758
47.6k
      PredBB->replaceSuccessor(TailBB, NewTarget);
759
47
    else {
760
47
      PredBB->removeSuccessor(TailBB, true);
761
47
      assert(PredBB->succ_size() <= 1);
762
47
    }
763
47.7k
764
47.7k
    if (PredTBB)
765
47.6k
      TII->insertBranch(*PredBB, PredTBB, PredFBB, PredCond, DL);
766
47.7k
767
47.7k
    TDBBs.push_back(PredBB);
768
47.7k
  }
769
39.8k
  return Changed;
770
39.8k
}
771
772
bool TailDuplicator::canTailDuplicate(MachineBasicBlock *TailBB,
773
2.05M
                                      MachineBasicBlock *PredBB) {
774
2.05M
  // EH edges are ignored by analyzeBranch.
775
2.05M
  if (PredBB->succ_size() > 1)
776
1.34M
    return false;
777
711k
778
711k
  MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
779
711k
  SmallVector<MachineOperand, 4> PredCond;
780
711k
  if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
781
313
    return false;
782
711k
  if (!PredCond.empty())
783
23
    return false;
784
711k
  return true;
785
711k
}
786
787
/// If it is profitable, duplicate TailBB's contents in each
788
/// of its predecessors.
789
/// \p IsSimple result of isSimpleBB
790
/// \p TailBB   Block to be duplicated.
791
/// \p ForcedLayoutPred  When non-null, use this block as the layout predecessor
792
///                      instead of the previous block in MF's order.
793
/// \p TDBBs             A vector to keep track of all blocks tail-duplicated
794
///                      into.
795
/// \p Copies            A vector of copy instructions inserted. Used later to
796
///                      walk all the inserted copies and remove redundant ones.
797
bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB,
798
                                   MachineBasicBlock *ForcedLayoutPred,
799
                                   SmallVectorImpl<MachineBasicBlock *> &TDBBs,
800
989k
                                   SmallVectorImpl<MachineInstr *> &Copies) {
801
989k
  LLVM_DEBUG(dbgs() << "\n*** Tail-duplicating " << printMBBReference(*TailBB)
802
989k
                    << '\n');
803
989k
804
989k
  DenseSet<unsigned> UsedByPhi;
805
989k
  getRegsUsedByPHIs(*TailBB, &UsedByPhi);
806
989k
807
989k
  if (IsSimple)
808
39.8k
    return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies);
809
949k
810
949k
  // Iterate through all the unique predecessors and tail-duplicate this
811
949k
  // block into them, if possible. Copying the list ahead of time also
812
949k
  // avoids trouble with the predecessor list reallocating.
813
949k
  bool Changed = false;
814
949k
  SmallSetVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(),
815
949k
                                               TailBB->pred_end());
816
1.57M
  for (MachineBasicBlock *PredBB : Preds) {
817
1.57M
    assert(TailBB != PredBB &&
818
1.57M
           "Single-block loop should have been rejected earlier!");
819
1.57M
820
1.57M
    if (!canTailDuplicate(TailBB, PredBB))
821
1.15M
      continue;
822
417k
823
417k
    // Don't duplicate into a fall-through predecessor (at least for now).
824
417k
    bool IsLayoutSuccessor = false;
825
417k
    if (ForcedLayoutPred)
826
337k
      IsLayoutSuccessor = (ForcedLayoutPred == PredBB);
827
79.8k
    else if (PredBB->isLayoutSuccessor(TailBB) && 
PredBB->canFallThrough()31.7k
)
828
31.7k
      IsLayoutSuccessor = true;
829
417k
    if (IsLayoutSuccessor)
830
189k
      continue;
831
227k
832
227k
    LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
833
227k
                      << "From Succ: " << *TailBB);
834
227k
835
227k
    TDBBs.push_back(PredBB);
836
227k
837
227k
    // Remove PredBB's unconditional branch.
838
227k
    TII->removeBranch(*PredBB);
839
227k
840
227k
    // Clone the contents of TailBB into PredBB.
841
227k
    DenseMap<unsigned, RegSubRegPair> LocalVRMap;
842
227k
    SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos;
843
227k
    for (MachineBasicBlock::iterator I = TailBB->begin(), E = TailBB->end();
844
908k
         I != E; /* empty */) {
845
681k
      MachineInstr *MI = &*I;
846
681k
      ++I;
847
681k
      if (MI->isPHI()) {
848
1.78k
        // Replace the uses of the def of the PHI with the register coming
849
1.78k
        // from PredBB.
850
1.78k
        processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true);
851
679k
      } else {
852
679k
        // Replace def of virtual registers with new registers, and update
853
679k
        // uses with PHI source register or the new registers.
854
679k
        duplicateInstruction(MI, TailBB, PredBB, LocalVRMap, UsedByPhi);
855
679k
      }
856
681k
    }
857
227k
    appendCopies(PredBB, CopyInfos, Copies);
858
227k
859
227k
    NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch
860
227k
861
227k
    // Update the CFG.
862
227k
    PredBB->removeSuccessor(PredBB->succ_begin());
863
227k
    assert(PredBB->succ_empty() &&
864
227k
           "TailDuplicate called on block with multiple successors!");
865
227k
    for (MachineBasicBlock *Succ : TailBB->successors())
866
289k
      PredBB->addSuccessor(Succ, MBPI->getEdgeProbability(TailBB, Succ));
867
227k
868
227k
    Changed = true;
869
227k
    ++NumTailDups;
870
227k
  }
871
949k
872
949k
  // If TailBB was duplicated into all its predecessors except for the prior
873
949k
  // block, which falls through unconditionally, move the contents of this
874
949k
  // block into the prior block.
875
949k
  MachineBasicBlock *PrevBB = ForcedLayoutPred;
876
949k
  if (!PrevBB)
877
260k
    PrevBB = &*std::prev(TailBB->getIterator());
878
949k
  MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
879
949k
  SmallVector<MachineOperand, 4> PriorCond;
880
949k
  // This has to check PrevBB->succ_size() because EH edges are ignored by
881
949k
  // analyzeBranch.
882
949k
  if (PrevBB->succ_size() == 1 &&
883
949k
      // Layout preds are not always CFG preds. Check.
884
949k
      
*PrevBB->succ_begin() == TailBB207k
&&
885
949k
      
!TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond)190k
&&
886
949k
      
PriorCond.empty()189k
&&
887
949k
      
(189k
!PriorTBB189k
||
PriorTBB == TailBB32.5k
) &&
888
949k
      
TailBB->pred_size() == 1189k
&&
889
949k
      
!TailBB->hasAddressTaken()52.4k
) {
890
52.4k
    LLVM_DEBUG(dbgs() << "\nMerging into block: " << *PrevBB
891
52.4k
                      << "From MBB: " << *TailBB);
892
52.4k
    // There may be a branch to the layout successor. This is unlikely but it
893
52.4k
    // happens. The correct thing to do is to remove the branch before
894
52.4k
    // duplicating the instructions in all cases.
895
52.4k
    TII->removeBranch(*PrevBB);
896
52.4k
    if (PreRegAlloc) {
897
802
      DenseMap<unsigned, RegSubRegPair> LocalVRMap;
898
802
      SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos;
899
802
      MachineBasicBlock::iterator I = TailBB->begin();
900
802
      // Process PHI instructions first.
901
1.56k
      while (I != TailBB->end() && 
I->isPHI()1.56k
) {
902
767
        // Replace the uses of the def of the PHI with the register coming
903
767
        // from PredBB.
904
767
        MachineInstr *MI = &*I++;
905
767
        processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true);
906
767
      }
907
802
908
802
      // Now copy the non-PHI instructions.
909
2.02k
      while (I != TailBB->end()) {
910
1.22k
        // Replace def of virtual registers with new registers, and update
911
1.22k
        // uses with PHI source register or the new registers.
912
1.22k
        MachineInstr *MI = &*I++;
913
1.22k
        assert(!MI->isBundle() && "Not expecting bundles before regalloc!");
914
1.22k
        duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi);
915
1.22k
        MI->eraseFromParent();
916
1.22k
      }
917
802
      appendCopies(PrevBB, CopyInfos, Copies);
918
51.5k
    } else {
919
51.5k
      TII->removeBranch(*PrevBB);
920
51.5k
      // No PHIs to worry about, just splice the instructions over.
921
51.5k
      PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());
922
51.5k
    }
923
52.4k
    PrevBB->removeSuccessor(PrevBB->succ_begin());
924
52.4k
    assert(PrevBB->succ_empty());
925
52.4k
    PrevBB->transferSuccessors(TailBB);
926
52.4k
    TDBBs.push_back(PrevBB);
927
52.4k
    Changed = true;
928
52.4k
  }
929
949k
930
949k
  // If this is after register allocation, there are no phis to fix.
931
949k
  if (!PreRegAlloc)
932
944k
    return Changed;
933
5.74k
934
5.74k
  // If we made no changes so far, we are safe.
935
5.74k
  if (!Changed)
936
4.85k
    return Changed;
937
890
938
890
  // Handle the nasty case in that we duplicated a block that is part of a loop
939
890
  // into some but not all of its predecessors. For example:
940
890
  //    1 -> 2 <-> 3                 |
941
890
  //          \                      |
942
890
  //           \---> rest            |
943
890
  // if we duplicate 2 into 1 but not into 3, we end up with
944
890
  // 12 -> 3 <-> 2 -> rest           |
945
890
  //   \             /               |
946
890
  //    \----->-----/                |
947
890
  // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced
948
890
  // with a phi in 3 (which now dominates 2).
949
890
  // What we do here is introduce a copy in 3 of the register defined by the
950
890
  // phi, just like when we are duplicating 2 into 3, but we don't copy any
951
890
  // real instructions or remove the 3 -> 2 edge from the phi in 2.
952
2.36k
  
for (MachineBasicBlock *PredBB : Preds)890
{
953
2.36k
    if (is_contained(TDBBs, PredBB))
954
2.35k
      continue;
955
14
956
14
    // EH edges
957
14
    if (PredBB->succ_size() != 1)
958
12
      continue;
959
2
960
2
    DenseMap<unsigned, RegSubRegPair> LocalVRMap;
961
2
    SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos;
962
2
    MachineBasicBlock::iterator I = TailBB->begin();
963
2
    // Process PHI instructions first.
964
6
    while (I != TailBB->end() && I->isPHI()) {
965
4
      // Replace the uses of the def of the PHI with the register coming
966
4
      // from PredBB.
967
4
      MachineInstr *MI = &*I++;
968
4
      processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false);
969
4
    }
970
2
    appendCopies(PredBB, CopyInfos, Copies);
971
2
  }
972
890
973
890
  return Changed;
974
890
}
975
976
/// At the end of the block \p MBB generate COPY instructions between registers
977
/// described by \p CopyInfos. Append resulting instructions to \p Copies.
978
void TailDuplicator::appendCopies(MachineBasicBlock *MBB,
979
      SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos,
980
228k
      SmallVectorImpl<MachineInstr*> &Copies) {
981
228k
  MachineBasicBlock::iterator Loc = MBB->getFirstTerminator();
982
228k
  const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY);
983
228k
  for (auto &CI : CopyInfos) {
984
2.55k
    auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first)
985
2.55k
                .addReg(CI.second.Reg, 0, CI.second.SubReg);
986
2.55k
    Copies.push_back(C);
987
2.55k
  }
988
228k
}
989
990
/// Remove the specified dead machine basic block from the function, updating
991
/// the CFG.
992
void TailDuplicator::removeDeadBlock(
993
    MachineBasicBlock *MBB,
994
90.2k
    function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
995
90.2k
  assert(MBB->pred_empty() && "MBB must be dead!");
996
90.2k
  LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
997
90.2k
998
90.2k
  if (RemovalCallback)
999
40.3k
    (*RemovalCallback)(MBB);
1000
90.2k
1001
90.2k
  // Remove all successors.
1002
128k
  while (!MBB->succ_empty())
1003
37.8k
    MBB->removeSuccessor(MBB->succ_end() - 1);
1004
90.2k
1005
90.2k
  // Remove the block.
1006
90.2k
  MBB->eraseFromParent();
1007
90.2k
}