Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/MachineBasicBlock.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// Collect the sequence of machine instructions for a basic block.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/CodeGen/MachineBasicBlock.h"
15
#include "llvm/ADT/SmallPtrSet.h"
16
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
17
#include "llvm/CodeGen/LiveVariables.h"
18
#include "llvm/CodeGen/MachineDominators.h"
19
#include "llvm/CodeGen/MachineFunction.h"
20
#include "llvm/CodeGen/MachineInstrBuilder.h"
21
#include "llvm/CodeGen/MachineLoopInfo.h"
22
#include "llvm/CodeGen/MachineRegisterInfo.h"
23
#include "llvm/CodeGen/SlotIndexes.h"
24
#include "llvm/IR/BasicBlock.h"
25
#include "llvm/IR/DataLayout.h"
26
#include "llvm/IR/DebugInfoMetadata.h"
27
#include "llvm/IR/ModuleSlotTracker.h"
28
#include "llvm/MC/MCAsmInfo.h"
29
#include "llvm/MC/MCContext.h"
30
#include "llvm/Support/DataTypes.h"
31
#include "llvm/Support/Debug.h"
32
#include "llvm/Support/raw_ostream.h"
33
#include "llvm/Target/TargetInstrInfo.h"
34
#include "llvm/Target/TargetMachine.h"
35
#include "llvm/Target/TargetRegisterInfo.h"
36
#include "llvm/Target/TargetSubtargetInfo.h"
37
#include <algorithm>
38
using namespace llvm;
39
40
#define DEBUG_TYPE "codegen"
41
42
MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
43
5.99M
    : BB(B), Number(-1), xParent(&MF) {
44
5.99M
  Insts.Parent = this;
45
5.99M
}
46
47
5.99M
MachineBasicBlock::~MachineBasicBlock() {
48
5.99M
}
49
50
/// Return the MCSymbol for this basic block.
51
4.35M
MCSymbol *MachineBasicBlock::getSymbol() const {
52
4.35M
  if (
!CachedMCSymbol4.35M
) {
53
1.81M
    const MachineFunction *MF = getParent();
54
1.81M
    MCContext &Ctx = MF->getContext();
55
1.81M
    auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
56
1.81M
    assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
57
1.81M
    CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
58
1.81M
                                           Twine(MF->getFunctionNumber()) +
59
1.81M
                                           "_" + Twine(getNumber()));
60
1.81M
  }
61
4.35M
62
4.35M
  return CachedMCSymbol;
63
4.35M
}
64
65
66
0
raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) {
67
0
  MBB.print(OS);
68
0
  return OS;
69
0
}
70
71
/// When an MBB is added to an MF, we need to update the parent pointer of the
72
/// MBB, the MBB numbering, and any instructions in the MBB to be on the right
73
/// operand list for registers.
74
///
75
/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
76
/// gets the next available unique MBB number. If it is removed from a
77
/// MachineFunction, it goes back to being #-1.
78
void ilist_callback_traits<MachineBasicBlock>::addNodeToList(
79
5.99M
    MachineBasicBlock *N) {
80
5.99M
  MachineFunction &MF = *N->getParent();
81
5.99M
  N->Number = MF.addToMBBNumbering(N);
82
5.99M
83
5.99M
  // Make sure the instructions have their operands in the reginfo lists.
84
5.99M
  MachineRegisterInfo &RegInfo = MF.getRegInfo();
85
5.99M
  for (MachineBasicBlock::instr_iterator
86
5.99M
         I = N->instr_begin(), E = N->instr_end(); 
I != E5.99M
;
++I91
)
87
91
    I->AddRegOperandsToUseLists(RegInfo);
88
5.99M
}
89
90
void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList(
91
5.99M
    MachineBasicBlock *N) {
92
5.99M
  N->getParent()->removeFromMBBNumbering(N->Number);
93
5.99M
  N->Number = -1;
94
5.99M
}
95
96
/// When we add an instruction to a basic block list, we update its parent
97
/// pointer and add its operands from reg use/def lists if appropriate.
98
91.2M
void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) {
99
91.2M
  assert(!N->getParent() && "machine instruction already in a basic block");
100
91.2M
  N->setParent(Parent);
101
91.2M
102
91.2M
  // Add the instruction's register operands to their corresponding
103
91.2M
  // use/def lists.
104
91.2M
  MachineFunction *MF = Parent->getParent();
105
91.2M
  N->AddRegOperandsToUseLists(MF->getRegInfo());
106
91.2M
}
107
108
/// When we remove an instruction from a basic block list, we update its parent
109
/// pointer and remove its operands from reg use/def lists if appropriate.
110
51.9M
void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) {
111
51.9M
  assert(N->getParent() && "machine instruction not in a basic block");
112
51.9M
113
51.9M
  // Remove from the use/def lists.
114
51.9M
  if (MachineFunction *MF = N->getParent()->getParent())
115
51.9M
    N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
116
51.9M
117
51.9M
  N->setParent(nullptr);
118
51.9M
}
119
120
/// When moving a range of instructions from one MBB list to another, we need to
121
/// update the parent pointers and the use/def lists.
122
void ilist_traits<MachineInstr>::transferNodesFromList(ilist_traits &FromList,
123
                                                       instr_iterator First,
124
3.98M
                                                       instr_iterator Last) {
125
3.98M
  assert(Parent->getParent() == FromList.Parent->getParent() &&
126
3.98M
        "MachineInstr parent mismatch!");
127
3.98M
  assert(this != &FromList && "Called without a real transfer...");
128
3.98M
  assert(Parent != FromList.Parent && "Two lists have the same parent?");
129
3.98M
130
3.98M
  // If splicing between two blocks within the same function, just update the
131
3.98M
  // parent pointers.
132
11.6M
  for (; 
First != Last11.6M
;
++First7.63M
)
133
7.63M
    First->setParent(Parent);
134
3.98M
}
135
136
51.0M
void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) {
137
51.0M
  assert(!MI->getParent() && "MI is still in a block!");
138
51.0M
  Parent->getParent()->DeleteMachineInstr(MI);
139
51.0M
}
140
141
30.2k
MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() {
142
30.2k
  instr_iterator I = instr_begin(), E = instr_end();
143
55.3k
  while (
I != E && 55.3k
I->isPHI()47.1k
)
144
25.0k
    ++I;
145
30.2k
  assert((I == E || !I->isInsideBundle()) &&
146
30.2k
         "First non-phi MI cannot be inside a bundle!");
147
30.2k
  return I;
148
30.2k
}
149
150
MachineBasicBlock::iterator
151
649k
MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) {
152
649k
  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
153
649k
154
649k
  iterator E = end();
155
1.61M
  while (
I != E && 1.61M
(I->isPHI() || 1.59M
I->isPosition()658k
||
156
1.61M
                    TII->isBasicBlockPrologue(*I)))
157
964k
    ++I;
158
649k
  // FIXME: This needs to change if we wish to bundle labels
159
649k
  // inside the bundle.
160
649k
  assert((I == E || !I->isInsideBundle()) &&
161
649k
         "First non-phi / non-label instruction is inside a bundle!");
162
649k
  return I;
163
649k
}
164
165
MachineBasicBlock::iterator
166
122k
MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I) {
167
122k
  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
168
122k
169
122k
  iterator E = end();
170
123k
  while (
I != E && 123k
(I->isPHI() || 120k
I->isPosition()120k
||
I->isDebugValue()119k
||
171
123k
                    TII->isBasicBlockPrologue(*I)))
172
1.06k
    ++I;
173
122k
  // FIXME: This needs to change if we wish to bundle labels / dbg_values
174
122k
  // inside the bundle.
175
122k
  assert((I == E || !I->isInsideBundle()) &&
176
122k
         "First non-phi / non-label / non-debug "
177
122k
         "instruction is inside a bundle!");
178
122k
  return I;
179
122k
}
180
181
38.3M
MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
182
38.3M
  iterator B = begin(), E = end(), I = E;
183
78.2M
  while (
I != B && 78.2M
((--I)->isTerminator() || 75.1M
I->isDebugValue()35.2M
))
184
39.8M
    ; /*noop */
185
73.6M
  while (
I != E && 73.6M
!I->isTerminator()67.2M
)
186
35.2M
    ++I;
187
38.3M
  return I;
188
38.3M
}
189
190
175k
MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() {
191
175k
  instr_iterator B = instr_begin(), E = instr_end(), I = E;
192
499k
  while (
I != B && 499k
((--I)->isTerminator() || 486k
I->isDebugValue()162k
))
193
324k
    ; /*noop */
194
337k
  while (
I != E && 337k
!I->isTerminator()335k
)
195
162k
    ++I;
196
175k
  return I;
197
175k
}
198
199
27.9M
MachineBasicBlock::iterator MachineBasicBlock::getFirstNonDebugInstr() {
200
27.9M
  // Skip over begin-of-block dbg_value instructions.
201
27.9M
  return skipDebugInstructionsForward(begin(), end());
202
27.9M
}
203
204
133M
MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() {
205
133M
  // Skip over end-of-block dbg_value instructions.
206
133M
  instr_iterator B = instr_begin(), I = instr_end();
207
133M
  while (
I != B133M
) {
208
132M
    --I;
209
132M
    // Return instruction that starts a bundle.
210
132M
    if (
I->isDebugValue() || 132M
I->isInsideBundle()132M
)
211
2.18k
      continue;
212
132M
    return I;
213
132M
  }
214
133M
  // The block is all debug values.
215
900k
  return end();
216
133M
}
217
218
10.2M
bool MachineBasicBlock::hasEHPadSuccessor() const {
219
26.1M
  for (const_succ_iterator I = succ_begin(), E = succ_end(); 
I != E26.1M
;
++I15.8M
)
220
15.9M
    
if (15.9M
(*I)->isEHPad()15.9M
)
221
59.6k
      return true;
222
10.2M
  return false;
223
10.2M
}
224
225
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
226
LLVM_DUMP_METHOD void MachineBasicBlock::dump() const {
227
  print(dbgs());
228
}
229
#endif
230
231
541k
bool MachineBasicBlock::isLegalToHoistInto() const {
232
541k
  if (
isReturnBlock() || 541k
hasEHPadSuccessor()541k
)
233
0
    return false;
234
541k
  return true;
235
541k
}
236
237
1.77k
StringRef MachineBasicBlock::getName() const {
238
1.77k
  if (const BasicBlock *LBB = getBasicBlock())
239
1.76k
    return LBB->getName();
240
1.77k
  else
241
3
    return StringRef("", 0);
242
0
}
243
244
/// Return a hopefully unique identifier for this block.
245
0
std::string MachineBasicBlock::getFullName() const {
246
0
  std::string Name;
247
0
  if (getParent())
248
0
    Name = (getParent()->getName() + ":").str();
249
0
  if (getBasicBlock())
250
0
    Name += getBasicBlock()->getName();
251
0
  else
252
0
    Name += ("BB" + Twine(getNumber())).str();
253
0
  return Name;
254
0
}
255
256
void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes)
257
0
    const {
258
0
  const MachineFunction *MF = getParent();
259
0
  if (
!MF0
) {
260
0
    OS << "Can't print out MachineBasicBlock because parent MachineFunction"
261
0
       << " is null\n";
262
0
    return;
263
0
  }
264
0
  const Function *F = MF->getFunction();
265
0
  const Module *M = F ? 
F->getParent()0
:
nullptr0
;
266
0
  ModuleSlotTracker MST(M);
267
0
  print(OS, MST, Indexes);
268
0
}
269
270
void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST,
271
12.2k
                              const SlotIndexes *Indexes) const {
272
12.2k
  const MachineFunction *MF = getParent();
273
12.2k
  if (
!MF12.2k
) {
274
0
    OS << "Can't print out MachineBasicBlock because parent MachineFunction"
275
0
       << " is null\n";
276
0
    return;
277
0
  }
278
12.2k
279
12.2k
  
if (12.2k
Indexes12.2k
)
280
1.14k
    OS << Indexes->getMBBStartIdx(this) << '\t';
281
12.2k
282
12.2k
  OS << "BB#" << getNumber() << ": ";
283
12.2k
284
12.2k
  const char *Comma = "";
285
12.2k
  if (const BasicBlock *
LBB12.2k
= getBasicBlock()) {
286
12.1k
    OS << Comma << "derived from LLVM BB ";
287
12.1k
    LBB->printAsOperand(OS, /*PrintType=*/false, MST);
288
12.1k
    Comma = ", ";
289
12.1k
  }
290
12.2k
  if (
isEHPad()12.2k
)
{ OS << Comma << "EH LANDING PAD"; Comma = ", "; }4
291
12.2k
  if (
hasAddressTaken()12.2k
)
{ OS << Comma << "ADDRESS TAKEN"; Comma = ", "; }2
292
12.2k
  if (Alignment)
293
0
    OS << Comma << "Align " << Alignment << " (" << (1u << Alignment)
294
0
       << " bytes)";
295
12.2k
296
12.2k
  OS << '\n';
297
12.2k
298
12.2k
  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
299
12.2k
  if (
!livein_empty()12.2k
) {
300
5.30k
    if (
Indexes5.30k
)
OS << '\t'272
;
301
5.30k
    OS << "    Live Ins:";
302
7.74k
    for (const auto &LI : LiveIns) {
303
7.74k
      OS << ' ' << PrintReg(LI.PhysReg, TRI);
304
7.74k
      if (!LI.LaneMask.all())
305
0
        OS << ':' << PrintLaneMask(LI.LaneMask);
306
7.74k
    }
307
5.30k
    OS << '\n';
308
5.30k
  }
309
12.2k
  // Print the preds of this block according to the CFG.
310
12.2k
  if (
!pred_empty()12.2k
) {
311
10.7k
    if (
Indexes10.7k
)
OS << '\t'979
;
312
10.7k
    OS << "    Predecessors according to CFG:";
313
27.7k
    for (const_pred_iterator PI = pred_begin(), E = pred_end(); 
PI != E27.7k
;
++PI17.0k
)
314
17.0k
      OS << " BB#" << (*PI)->getNumber();
315
10.7k
    OS << '\n';
316
10.7k
  }
317
12.2k
318
46.1k
  for (auto &I : instrs()) {
319
46.1k
    if (
Indexes46.1k
) {
320
4.36k
      if (Indexes->hasIndex(I))
321
4.36k
        OS << Indexes->getInstructionIndex(I);
322
4.36k
      OS << '\t';
323
4.36k
    }
324
46.1k
    OS << '\t';
325
46.1k
    if (I.isInsideBundle())
326
8
      OS << "  * ";
327
46.1k
    I.print(OS, MST);
328
46.1k
  }
329
12.2k
330
12.2k
  // Print the successors of this block according to the CFG.
331
12.2k
  if (
!succ_empty()12.2k
) {
332
9.44k
    if (
Indexes9.44k
)
OS << '\t'859
;
333
9.44k
    OS << "    Successors according to CFG:";
334
26.4k
    for (const_succ_iterator SI = succ_begin(), E = succ_end(); 
SI != E26.4k
;
++SI17.0k
) {
335
17.0k
      OS << " BB#" << (*SI)->getNumber();
336
17.0k
      if (!Probs.empty())
337
17.0k
        OS << '(' << *getProbabilityIterator(SI) << ')';
338
17.0k
    }
339
9.44k
    OS << '\n';
340
9.44k
  }
341
12.2k
}
342
343
void MachineBasicBlock::printAsOperand(raw_ostream &OS,
344
0
                                       bool /*PrintType*/) const {
345
0
  OS << "BB#" << getNumber();
346
0
}
347
348
7.40k
void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) {
349
7.40k
  LiveInVector::iterator I = find_if(
350
13.4k
      LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
351
7.40k
  if (I == LiveIns.end())
352
0
    return;
353
7.40k
354
7.40k
  I->LaneMask &= ~LaneMask;
355
7.40k
  if (I->LaneMask.none())
356
7.40k
    LiveIns.erase(I);
357
7.40k
}
358
359
MachineBasicBlock::livein_iterator
360
4.64k
MachineBasicBlock::removeLiveIn(MachineBasicBlock::livein_iterator I) {
361
4.64k
  // Get non-const version of iterator.
362
4.64k
  LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
363
4.64k
  return LiveIns.erase(LI);
364
4.64k
}
365
366
3.36M
bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const {
367
3.36M
  livein_iterator I = find_if(
368
12.8M
      LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
369
1.67M
  return I != livein_end() && (I->LaneMask & LaneMask).any();
370
3.36M
}
371
372
4.50M
void MachineBasicBlock::sortUniqueLiveIns() {
373
4.50M
  std::sort(LiveIns.begin(), LiveIns.end(),
374
48.5M
            [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
375
48.5M
              return LI0.PhysReg < LI1.PhysReg;
376
48.5M
            });
377
4.50M
  // Liveins are sorted by physreg now we can merge their lanemasks.
378
4.50M
  LiveInVector::const_iterator I = LiveIns.begin();
379
4.50M
  LiveInVector::const_iterator J;
380
4.50M
  LiveInVector::iterator Out = LiveIns.begin();
381
26.1M
  for (; 
I != LiveIns.end()26.1M
;
++Out, I = J21.6M
) {
382
21.6M
    unsigned PhysReg = I->PhysReg;
383
21.6M
    LaneBitmask LaneMask = I->LaneMask;
384
21.6M
    for (J = std::next(I); 
J != LiveIns.end() && 21.6M
J->PhysReg == PhysReg17.6M
;
++J200
)
385
200
      LaneMask |= J->LaneMask;
386
21.6M
    Out->PhysReg = PhysReg;
387
21.6M
    Out->LaneMask = LaneMask;
388
21.6M
  }
389
4.50M
  LiveIns.erase(Out, LiveIns.end());
390
4.50M
}
391
392
unsigned
393
25.4k
MachineBasicBlock::addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC) {
394
25.4k
  assert(getParent() && "MBB must be inserted in function");
395
25.4k
  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg");
396
25.4k
  assert(RC && "Register class is required");
397
25.4k
  assert((isEHPad() || this == &getParent()->front()) &&
398
25.4k
         "Only the entry block and landing pads can have physreg live ins");
399
25.4k
400
25.4k
  bool LiveIn = isLiveIn(PhysReg);
401
25.4k
  iterator I = SkipPHIsAndLabels(begin()), E = end();
402
25.4k
  MachineRegisterInfo &MRI = getParent()->getRegInfo();
403
25.4k
  const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
404
25.4k
405
25.4k
  // Look for an existing copy.
406
25.4k
  if (LiveIn)
407
0
    
for (;0
I != E && 0
I->isCopy()0
;
++I0
)
408
0
      
if (0
I->getOperand(1).getReg() == PhysReg0
) {
409
0
        unsigned VirtReg = I->getOperand(0).getReg();
410
0
        if (!MRI.constrainRegClass(VirtReg, RC))
411
0
          llvm_unreachable("Incompatible live-in register class.");
412
0
        return VirtReg;
413
0
      }
414
25.4k
415
25.4k
  // No luck, create a virtual register.
416
25.4k
  unsigned VirtReg = MRI.createVirtualRegister(RC);
417
25.4k
  BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
418
25.4k
    .addReg(PhysReg, RegState::Kill);
419
25.4k
  if (!LiveIn)
420
25.4k
    addLiveIn(PhysReg);
421
25.4k
  return VirtReg;
422
25.4k
}
423
424
27.6k
void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
425
27.6k
  getParent()->splice(NewAfter->getIterator(), getIterator());
426
27.6k
}
427
428
439k
void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
429
439k
  getParent()->splice(++NewBefore->getIterator(), getIterator());
430
439k
}
431
432
4.05M
void MachineBasicBlock::updateTerminator() {
433
4.05M
  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
434
4.05M
  // A block with no successors has no concerns with fall-through edges.
435
4.05M
  if (this->succ_empty())
436
26.1k
    return;
437
4.02M
438
4.02M
  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
439
4.02M
  SmallVector<MachineOperand, 4> Cond;
440
4.02M
  DebugLoc DL = findBranchDebugLoc();
441
4.02M
  bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
442
4.02M
  (void) B;
443
4.02M
  assert(!B && "UpdateTerminators requires analyzable predecessors!");
444
4.02M
  if (
Cond.empty()4.02M
) {
445
1.11M
    if (
TBB1.11M
) {
446
292k
      // The block has an unconditional branch. If its successor is now its
447
292k
      // layout successor, delete the branch.
448
292k
      if (isLayoutSuccessor(TBB))
449
93.4k
        TII->removeBranch(*this);
450
1.11M
    } else {
451
822k
      // The block has an unconditional fallthrough. If its successor is not its
452
822k
      // layout successor, insert a branch. First we have to locate the only
453
822k
      // non-landing-pad successor, as that is the fallthrough block.
454
1.66M
      for (succ_iterator SI = succ_begin(), SE = succ_end(); 
SI != SE1.66M
;
++SI845k
) {
455
845k
        if ((*SI)->isEHPad())
456
22.7k
          continue;
457
845k
        assert(!TBB && "Found more than one non-landing-pad successor!");
458
822k
        TBB = *SI;
459
822k
      }
460
822k
461
822k
      // If there is no non-landing-pad successor, the block has no fall-through
462
822k
      // edges to be concerned with.
463
822k
      if (!TBB)
464
0
        return;
465
822k
466
822k
      // Finally update the unconditional successor to be reached via a branch
467
822k
      // if it would not be reached by fallthrough.
468
822k
      
if (822k
!isLayoutSuccessor(TBB)822k
)
469
97.1k
        TII->insertBranch(*this, TBB, nullptr, Cond, DL);
470
822k
    }
471
1.11M
    return;
472
2.91M
  }
473
2.91M
474
2.91M
  
if (2.91M
FBB2.91M
) {
475
589k
    // The block has a non-fallthrough conditional branch. If one of its
476
589k
    // successors is its layout successor, rewrite it to a fallthrough
477
589k
    // conditional branch.
478
589k
    if (
isLayoutSuccessor(TBB)589k
) {
479
380k
      if (TII->reverseBranchCondition(Cond))
480
16
        return;
481
380k
      TII->removeBranch(*this);
482
380k
      TII->insertBranch(*this, FBB, nullptr, Cond, DL);
483
589k
    } else 
if (208k
isLayoutSuccessor(FBB)208k
) {
484
113k
      TII->removeBranch(*this);
485
113k
      TII->insertBranch(*this, TBB, nullptr, Cond, DL);
486
113k
    }
487
589k
    return;
488
2.32M
  }
489
2.32M
490
2.32M
  // Walk through the successors and find the successor which is not a landing
491
2.32M
  // pad and is not the conditional branch destination (in TBB) as the
492
2.32M
  // fallthrough successor.
493
2.32M
  MachineBasicBlock *FallthroughBB = nullptr;
494
6.97M
  for (succ_iterator SI = succ_begin(), SE = succ_end(); 
SI != SE6.97M
;
++SI4.65M
) {
495
4.65M
    if (
(*SI)->isEHPad() || 4.65M
*SI == TBB4.65M
)
496
2.32M
      continue;
497
4.65M
    assert(!FallthroughBB && "Found more than one fallthrough successor.");
498
2.32M
    FallthroughBB = *SI;
499
2.32M
  }
500
2.32M
501
2.32M
  if (
!FallthroughBB2.32M
) {
502
17
    if (
canFallThrough()17
) {
503
16
      // We fallthrough to the same basic block as the conditional jump targets.
504
16
      // Remove the conditional jump, leaving unconditional fallthrough.
505
16
      // FIXME: This does not seem like a reasonable pattern to support, but it
506
16
      // has been seen in the wild coming out of degenerate ARM test cases.
507
16
      TII->removeBranch(*this);
508
16
509
16
      // Finally update the unconditional successor to be reached via a branch if
510
16
      // it would not be reached by fallthrough.
511
16
      if (!isLayoutSuccessor(TBB))
512
0
        TII->insertBranch(*this, TBB, nullptr, Cond, DL);
513
16
      return;
514
16
    }
515
1
516
1
    // We enter here iff exactly one successor is TBB which cannot fallthrough
517
1
    // and the rest successors if any are EHPads.  In this case, we need to
518
1
    // change the conditional branch into unconditional branch.
519
1
    TII->removeBranch(*this);
520
1
    Cond.clear();
521
1
    TII->insertBranch(*this, TBB, nullptr, Cond, DL);
522
1
    return;
523
1
  }
524
2.32M
525
2.32M
  // The block has a fallthrough conditional branch.
526
2.32M
  
if (2.32M
isLayoutSuccessor(TBB)2.32M
) {
527
408k
    if (
TII->reverseBranchCondition(Cond)408k
) {
528
15
      // We can't reverse the condition, add an unconditional branch.
529
15
      Cond.clear();
530
15
      TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
531
15
      return;
532
15
    }
533
408k
    TII->removeBranch(*this);
534
408k
    TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
535
2.32M
  } else 
if (1.91M
!isLayoutSuccessor(FallthroughBB)1.91M
) {
536
191k
    TII->removeBranch(*this);
537
191k
    TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
538
191k
  }
539
4.05M
}
540
541
0
void MachineBasicBlock::validateSuccProbs() const {
542
#ifndef NDEBUG
543
  int64_t Sum = 0;
544
  for (auto Prob : Probs)
545
    Sum += Prob.getNumerator();
546
  // Due to precision issue, we assume that the sum of probabilities is one if
547
  // the difference between the sum of their numerators and the denominator is
548
  // no greater than the number of successors.
549
  assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <=
550
             Probs.size() &&
551
         "The sum of successors's probabilities exceeds one.");
552
#endif // NDEBUG
553
}
554
555
void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
556
8.63M
                                     BranchProbability Prob) {
557
8.63M
  // Probability list is either empty (if successor list isn't empty, this means
558
8.63M
  // disabled optimization) or has the same size as successor list.
559
8.63M
  if (
!(Probs.empty() && 8.63M
!Successors.empty()5.61M
))
560
8.63M
    Probs.push_back(Prob);
561
8.63M
  Successors.push_back(Succ);
562
8.63M
  Succ->addPredecessor(this);
563
8.63M
}
564
565
3.10k
void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
566
3.10k
  // We need to make sure probability list is either empty or has the same size
567
3.10k
  // of successor list. When this function is called, we can safely delete all
568
3.10k
  // probability in the list.
569
3.10k
  Probs.clear();
570
3.10k
  Successors.push_back(Succ);
571
3.10k
  Succ->addPredecessor(this);
572
3.10k
}
573
574
void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
575
540k
                                        bool NormalizeSuccProbs) {
576
540k
  succ_iterator I = find(Successors, Succ);
577
540k
  removeSuccessor(I, NormalizeSuccProbs);
578
540k
}
579
580
MachineBasicBlock::succ_iterator
581
1.56M
MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) {
582
1.56M
  assert(I != Successors.end() && "Not a current successor!");
583
1.56M
584
1.56M
  // If probability list is empty it means we don't use it (disabled
585
1.56M
  // optimization).
586
1.56M
  if (
!Probs.empty()1.56M
) {
587
1.56M
    probability_iterator WI = getProbabilityIterator(I);
588
1.56M
    Probs.erase(WI);
589
1.56M
    if (NormalizeSuccProbs)
590
26.2k
      normalizeSuccProbs();
591
1.56M
  }
592
1.56M
593
1.56M
  (*I)->removePredecessor(this);
594
1.56M
  return Successors.erase(I);
595
1.56M
}
596
597
void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
598
870k
                                         MachineBasicBlock *New) {
599
870k
  if (Old == New)
600
0
    return;
601
870k
602
870k
  succ_iterator E = succ_end();
603
870k
  succ_iterator NewI = E;
604
870k
  succ_iterator OldI = E;
605
2.60M
  for (succ_iterator I = succ_begin(); 
I != E2.60M
;
++I1.73M
) {
606
1.73M
    if (
*I == Old1.73M
) {
607
870k
      OldI = I;
608
870k
      if (NewI != E)
609
743
        break;
610
1.73M
    }
611
1.73M
    
if (1.73M
*I == New1.73M
) {
612
1.78k
      NewI = I;
613
1.78k
      if (OldI != E)
614
1.04k
        break;
615
1.78k
    }
616
1.73M
  }
617
870k
  assert(OldI != E && "Old is not a successor of this block");
618
870k
619
870k
  // If New isn't already a successor, let it take Old's place.
620
870k
  if (
NewI == E870k
) {
621
868k
    Old->removePredecessor(this);
622
868k
    New->addPredecessor(this);
623
868k
    *OldI = New;
624
868k
    return;
625
868k
  }
626
1.78k
627
1.78k
  // New is already a successor.
628
1.78k
  // Update its probability instead of adding a duplicate edge.
629
1.78k
  
if (1.78k
!Probs.empty()1.78k
) {
630
1.78k
    auto ProbIter = getProbabilityIterator(NewI);
631
1.78k
    if (!ProbIter->isUnknown())
632
1.76k
      *ProbIter += *getProbabilityIterator(OldI);
633
1.78k
  }
634
870k
  removeSuccessor(OldI);
635
870k
}
636
637
9.50M
void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
638
9.50M
  Predecessors.push_back(Pred);
639
9.50M
}
640
641
2.42M
void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
642
2.42M
  pred_iterator I = find(Predecessors, Pred);
643
2.42M
  assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
644
2.42M
  Predecessors.erase(I);
645
2.42M
}
646
647
193k
void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {
648
193k
  if (this == FromMBB)
649
0
    return;
650
193k
651
395k
  
while (193k
!FromMBB->succ_empty()395k
) {
652
202k
    MachineBasicBlock *Succ = *FromMBB->succ_begin();
653
202k
654
202k
    // If probability list is empty it means we don't use it (disabled optimization).
655
202k
    if (
!FromMBB->Probs.empty()202k
) {
656
202k
      auto Prob = *FromMBB->Probs.begin();
657
202k
      addSuccessor(Succ, Prob);
658
202k
    } else
659
24
      addSuccessorWithoutProb(Succ);
660
202k
661
202k
    FromMBB->removeSuccessor(Succ);
662
202k
  }
663
193k
}
664
665
void
666
32.8k
MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
667
32.8k
  if (this == FromMBB)
668
0
    return;
669
32.8k
670
63.5k
  
while (32.8k
!FromMBB->succ_empty()63.5k
) {
671
30.7k
    MachineBasicBlock *Succ = *FromMBB->succ_begin();
672
30.7k
    if (
!FromMBB->Probs.empty()30.7k
) {
673
30.7k
      auto Prob = *FromMBB->Probs.begin();
674
30.7k
      addSuccessor(Succ, Prob);
675
30.7k
    } else
676
24
      addSuccessorWithoutProb(Succ);
677
30.7k
    FromMBB->removeSuccessor(Succ);
678
30.7k
679
30.7k
    // Fix up any PHI nodes in the successor.
680
30.7k
    for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(),
681
54.7k
           ME = Succ->instr_end(); 
MI != ME && 54.7k
MI->isPHI()51.4k
;
++MI23.9k
)
682
96.7k
      
for (unsigned i = 2, e = MI->getNumOperands()+1; 23.9k
i != e96.7k
;
i += 272.8k
) {
683
72.8k
        MachineOperand &MO = MI->getOperand(i);
684
72.8k
        if (MO.getMBB() == FromMBB)
685
23.9k
          MO.setMBB(this);
686
23.9k
      }
687
30.7k
  }
688
32.8k
  normalizeSuccProbs();
689
32.8k
}
690
691
710
bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
692
710
  return is_contained(predecessors(), MBB);
693
710
}
694
695
52.6M
bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {
696
52.6M
  return is_contained(successors(), MBB);
697
52.6M
}
698
699
23.2M
bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {
700
23.2M
  MachineFunction::const_iterator I(this);
701
23.2M
  return std::next(I) == MachineFunction::const_iterator(MBB);
702
23.2M
}
703
704
26.9M
MachineBasicBlock *MachineBasicBlock::getFallThrough() {
705
26.9M
  MachineFunction::iterator Fallthrough = getIterator();
706
26.9M
  ++Fallthrough;
707
26.9M
  // If FallthroughBlock is off the end of the function, it can't fall through.
708
26.9M
  if (Fallthrough == getParent()->end())
709
1.93M
    return nullptr;
710
25.0M
711
25.0M
  // If FallthroughBlock isn't a successor, no fallthrough is possible.
712
25.0M
  
if (25.0M
!isSuccessor(&*Fallthrough)25.0M
)
713
6.93M
    return nullptr;
714
18.1M
715
18.1M
  // Analyze the branches, if any, at the end of the block.
716
18.1M
  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
717
18.1M
  SmallVector<MachineOperand, 4> Cond;
718
18.1M
  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
719
18.1M
  if (
TII->analyzeBranch(*this, TBB, FBB, Cond)18.1M
) {
720
106k
    // If we couldn't analyze the branch, examine the last instruction.
721
106k
    // If the block doesn't end in a known control barrier, assume fallthrough
722
106k
    // is possible. The isPredicated check is needed because this code can be
723
106k
    // called during IfConversion, where an instruction which is normally a
724
106k
    // Barrier is predicated and thus no longer an actual control barrier.
725
106k
    return (empty() || 
!back().isBarrier()106k
||
TII->isPredicated(back())102k
)
726
3.51k
               ? &*Fallthrough
727
102k
               : nullptr;
728
106k
  }
729
18.0M
730
18.0M
  // If there is no branch, control always falls through.
731
18.0M
  
if (18.0M
!TBB18.0M
)
return &*Fallthrough4.85M
;
732
13.1M
733
13.1M
  // If there is some explicit branch to the fallthrough block, it can obviously
734
13.1M
  // reach, even though the branch should get folded to fall through implicitly.
735
13.1M
  
if (13.1M
MachineFunction::iterator(TBB) == Fallthrough ||
736
12.9M
      MachineFunction::iterator(FBB) == Fallthrough)
737
2.28M
    return &*Fallthrough;
738
10.8M
739
10.8M
  // If it's an unconditional branch to some block not the fall through, it
740
10.8M
  // doesn't fall through.
741
10.8M
  
if (10.8M
Cond.empty()10.8M
)
return nullptr13.5k
;
742
10.8M
743
10.8M
  // Otherwise, if it is conditional and has no explicit false block, it falls
744
10.8M
  // through.
745
10.8M
  
return (FBB == nullptr) ? 10.8M
&*Fallthrough10.8M
:
nullptr0
;
746
26.9M
}
747
748
26.9M
bool MachineBasicBlock::canFallThrough() {
749
26.9M
  return getFallThrough() != nullptr;
750
26.9M
}
751
752
MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ,
753
470k
                                                        Pass &P) {
754
470k
  if (!canSplitCriticalEdge(Succ))
755
2.63k
    return nullptr;
756
467k
757
467k
  MachineFunction *MF = getParent();
758
467k
  DebugLoc DL;  // FIXME: this is nowhere
759
467k
760
467k
  MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
761
467k
  MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
762
467k
  DEBUG(dbgs() << "Splitting critical edge:"
763
467k
        " BB#" << getNumber()
764
467k
        << " -- BB#" << NMBB->getNumber()
765
467k
        << " -- BB#" << Succ->getNumber() << '\n');
766
467k
767
467k
  LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>();
768
467k
  SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>();
769
467k
  if (LIS)
770
0
    LIS->insertMBBInMaps(NMBB);
771
467k
  else 
if (467k
Indexes467k
)
772
0
    Indexes->insertMBBInMaps(NMBB);
773
467k
774
467k
  // On some targets like Mips, branches may kill virtual registers. Make sure
775
467k
  // that LiveVariables is properly updated after updateTerminator replaces the
776
467k
  // terminators.
777
467k
  LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>();
778
467k
779
467k
  // Collect a list of virtual registers killed by the terminators.
780
467k
  SmallVector<unsigned, 4> KilledRegs;
781
467k
  if (LV)
782
161k
    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
783
472k
         
I != E472k
;
++I311k
) {
784
311k
      MachineInstr *MI = &*I;
785
311k
      for (MachineInstr::mop_iterator OI = MI->operands_begin(),
786
911k
           OE = MI->operands_end(); 
OI != OE911k
;
++OI600k
) {
787
600k
        if (
!OI->isReg() || 600k
OI->getReg() == 0163k
||
788
600k
            
!OI->isUse()161k
||
!OI->isKill()161k
||
OI->isUndef()145k
)
789
455k
          continue;
790
145k
        unsigned Reg = OI->getReg();
791
145k
        if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
792
145k
            
LV->getVarInfo(Reg).removeKill(*MI)26.8k
) {
793
145k
          KilledRegs.push_back(Reg);
794
145k
          DEBUG(dbgs() << "Removing terminator kill: " << *MI);
795
145k
          OI->setIsKill(false);
796
145k
        }
797
600k
      }
798
161k
    }
799
467k
800
467k
  SmallVector<unsigned, 4> UsedRegs;
801
467k
  if (
LIS467k
) {
802
0
    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
803
0
         
I != E0
;
++I0
) {
804
0
      MachineInstr *MI = &*I;
805
0
806
0
      for (MachineInstr::mop_iterator OI = MI->operands_begin(),
807
0
           OE = MI->operands_end(); 
OI != OE0
;
++OI0
) {
808
0
        if (
!OI->isReg() || 0
OI->getReg() == 00
)
809
0
          continue;
810
0
811
0
        unsigned Reg = OI->getReg();
812
0
        if (!is_contained(UsedRegs, Reg))
813
0
          UsedRegs.push_back(Reg);
814
0
      }
815
0
    }
816
0
  }
817
467k
818
467k
  ReplaceUsesOfBlockWith(Succ, NMBB);
819
467k
820
467k
  // If updateTerminator() removes instructions, we need to remove them from
821
467k
  // SlotIndexes.
822
467k
  SmallVector<MachineInstr*, 4> Terminators;
823
467k
  if (
Indexes467k
) {
824
0
    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
825
0
         
I != E0
;
++I0
)
826
0
      Terminators.push_back(&*I);
827
0
  }
828
467k
829
467k
  updateTerminator();
830
467k
831
467k
  if (
Indexes467k
) {
832
0
    SmallVector<MachineInstr*, 4> NewTerminators;
833
0
    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
834
0
         
I != E0
;
++I0
)
835
0
      NewTerminators.push_back(&*I);
836
0
837
0
    for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
838
0
        E = Terminators.end(); 
I != E0
;
++I0
) {
839
0
      if (!is_contained(NewTerminators, *I))
840
0
        Indexes->removeMachineInstrFromMaps(**I);
841
0
    }
842
0
  }
843
467k
844
467k
  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
845
467k
  NMBB->addSuccessor(Succ);
846
467k
  if (
!NMBB->isLayoutSuccessor(Succ)467k
) {
847
428k
    SmallVector<MachineOperand, 4> Cond;
848
428k
    const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
849
428k
    TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
850
428k
851
428k
    if (
Indexes428k
) {
852
0
      for (MachineInstr &MI : NMBB->instrs()) {
853
0
        // Some instructions may have been moved to NMBB by updateTerminator(),
854
0
        // so we first remove any instruction that already has an index.
855
0
        if (Indexes->hasIndex(MI))
856
0
          Indexes->removeMachineInstrFromMaps(MI);
857
0
        Indexes->insertMachineInstrInMaps(MI);
858
0
      }
859
0
    }
860
428k
  }
861
467k
862
467k
  // Fix PHI nodes in Succ so they refer to NMBB instead of this
863
467k
  for (MachineBasicBlock::instr_iterator
864
467k
         i = Succ->instr_begin(),e = Succ->instr_end();
865
1.04M
       
i != e && 1.04M
i->isPHI()1.04M
;
++i575k
)
866
7.01M
    
for (unsigned ni = 1, ne = i->getNumOperands(); 575k
ni != ne7.01M
;
ni += 26.44M
)
867
6.44M
      
if (6.44M
i->getOperand(ni+1).getMBB() == this6.44M
)
868
579k
        i->getOperand(ni+1).setMBB(NMBB);
869
467k
870
467k
  // Inherit live-ins from the successor
871
467k
  for (const auto &LI : Succ->liveins())
872
268
    NMBB->addLiveIn(LI);
873
467k
874
467k
  // Update LiveVariables.
875
467k
  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
876
467k
  if (
LV467k
) {
877
161k
    // Restore kills of virtual registers that were killed by the terminators.
878
306k
    while (
!KilledRegs.empty()306k
) {
879
145k
      unsigned Reg = KilledRegs.pop_back_val();
880
145k
      for (instr_iterator I = instr_end(), E = instr_begin(); 
I != E145k
;) {
881
145k
        if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
882
11
          continue;
883
145k
        
if (145k
TargetRegisterInfo::isVirtualRegister(Reg)145k
)
884
26.8k
          LV->getVarInfo(Reg).Kills.push_back(&*I);
885
145k
        DEBUG(dbgs() << "Restored terminator kill: " << *I);
886
145k
        break;
887
145k
      }
888
145k
    }
889
161k
    // Update relevant live-through information.
890
161k
    LV->addNewBlock(NMBB, this, Succ);
891
161k
  }
892
467k
893
467k
  if (
LIS467k
) {
894
0
    // After splitting the edge and updating SlotIndexes, live intervals may be
895
0
    // in one of two situations, depending on whether this block was the last in
896
0
    // the function. If the original block was the last in the function, all
897
0
    // live intervals will end prior to the beginning of the new split block. If
898
0
    // the original block was not at the end of the function, all live intervals
899
0
    // will extend to the end of the new split block.
900
0
901
0
    bool isLastMBB =
902
0
      std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
903
0
904
0
    SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
905
0
    SlotIndex PrevIndex = StartIndex.getPrevSlot();
906
0
    SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
907
0
908
0
    // Find the registers used from NMBB in PHIs in Succ.
909
0
    SmallSet<unsigned, 8> PHISrcRegs;
910
0
    for (MachineBasicBlock::instr_iterator
911
0
         I = Succ->instr_begin(), E = Succ->instr_end();
912
0
         
I != E && 0
I->isPHI()0
;
++I0
) {
913
0
      for (unsigned ni = 1, ne = I->getNumOperands(); 
ni != ne0
;
ni += 20
) {
914
0
        if (
I->getOperand(ni+1).getMBB() == NMBB0
) {
915
0
          MachineOperand &MO = I->getOperand(ni);
916
0
          unsigned Reg = MO.getReg();
917
0
          PHISrcRegs.insert(Reg);
918
0
          if (MO.isUndef())
919
0
            continue;
920
0
921
0
          LiveInterval &LI = LIS->getInterval(Reg);
922
0
          VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
923
0
          assert(VNI &&
924
0
                 "PHI sources should be live out of their predecessors.");
925
0
          LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
926
0
        }
927
0
      }
928
0
    }
929
0
930
0
    MachineRegisterInfo *MRI = &getParent()->getRegInfo();
931
0
    for (unsigned i = 0, e = MRI->getNumVirtRegs(); 
i != e0
;
++i0
) {
932
0
      unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
933
0
      if (
PHISrcRegs.count(Reg) || 0
!LIS->hasInterval(Reg)0
)
934
0
        continue;
935
0
936
0
      LiveInterval &LI = LIS->getInterval(Reg);
937
0
      if (!LI.liveAt(PrevIndex))
938
0
        continue;
939
0
940
0
      bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
941
0
      if (
isLiveOut && 0
isLastMBB0
) {
942
0
        VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
943
0
        assert(VNI && "LiveInterval should have VNInfo where it is live.");
944
0
        LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
945
0
      } else 
if (0
!isLiveOut && 0
!isLastMBB0
) {
946
0
        LI.removeSegment(StartIndex, EndIndex);
947
0
      }
948
0
    }
949
0
950
0
    // Update all intervals for registers whose uses may have been modified by
951
0
    // updateTerminator().
952
0
    LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
953
0
  }
954
467k
955
467k
  if (MachineDominatorTree *MDT =
956
467k
          P.getAnalysisIfAvailable<MachineDominatorTree>())
957
467k
    MDT->recordSplitCriticalEdge(this, Succ, NMBB);
958
467k
959
467k
  if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>())
960
467k
    
if (MachineLoop *467k
TIL467k
= MLI->getLoopFor(this)) {
961
141k
      // If one or the other blocks were not in a loop, the new block is not
962
141k
      // either, and thus LI doesn't need to be updated.
963
141k
      if (MachineLoop *
DestLoop141k
= MLI->getLoopFor(Succ)) {
964
96.1k
        if (
TIL == DestLoop96.1k
) {
965
84.9k
          // Both in the same loop, the NMBB joins loop.
966
84.9k
          DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
967
96.1k
        } else 
if (11.2k
TIL->contains(DestLoop)11.2k
) {
968
365
          // Edge from an outer loop to an inner loop.  Add to the outer loop.
969
365
          TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
970
11.2k
        } else 
if (10.8k
DestLoop->contains(TIL)10.8k
) {
971
10.7k
          // Edge from an inner loop to an outer loop.  Add to the outer loop.
972
10.7k
          DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
973
10.8k
        } else {
974
70
          // Edge from two loops with no containment relation.  Because these
975
70
          // are natural loops, we know that the destination block must be the
976
70
          // header of its loop (adding a branch into a loop elsewhere would
977
70
          // create an irreducible loop).
978
70
          assert(DestLoop->getHeader() == Succ &&
979
70
                 "Should not create irreducible loops!");
980
70
          if (MachineLoop *P = DestLoop->getParentLoop())
981
32
            P->addBasicBlockToLoop(NMBB, MLI->getBase());
982
11.2k
        }
983
96.1k
      }
984
467k
    }
985
470k
986
470k
  return NMBB;
987
470k
}
988
989
bool MachineBasicBlock::canSplitCriticalEdge(
990
470k
    const MachineBasicBlock *Succ) const {
991
470k
  // Splitting the critical edge to a landing pad block is non-trivial. Don't do
992
470k
  // it in this generic function.
993
470k
  if (Succ->isEHPad())
994
0
    return false;
995
470k
996
470k
  const MachineFunction *MF = getParent();
997
470k
998
470k
  // Performance might be harmed on HW that implements branching using exec mask
999
470k
  // where both sides of the branches are always executed.
1000
470k
  if (MF->getTarget().requiresStructuredCFG())
1001
45
    return false;
1002
470k
1003
470k
  // We may need to update this's terminator, but we can't do that if
1004
470k
  // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
1005
470k
  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1006
470k
  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1007
470k
  SmallVector<MachineOperand, 4> Cond;
1008
470k
  // AnalyzeBanch should modify this, since we did not allow modification.
1009
470k
  if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1010
470k
                         /*AllowModify*/ false))
1011
2.58k
    return false;
1012
467k
1013
467k
  // Avoid bugpoint weirdness: A block may end with a conditional branch but
1014
467k
  // jumps to the same MBB is either case. We have duplicate CFG edges in that
1015
467k
  // case that we can't handle. Since this never happens in properly optimized
1016
467k
  // code, just skip those edges.
1017
467k
  
if (467k
TBB && 467k
TBB == FBB467k
) {
1018
0
    DEBUG(dbgs() << "Won't split critical edge after degenerate BB#"
1019
0
                 << getNumber() << '\n');
1020
0
    return false;
1021
0
  }
1022
467k
  return true;
1023
467k
}
1024
1025
/// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1026
/// neighboring instructions so the bundle won't be broken by removing MI.
1027
3.91M
static void unbundleSingleMI(MachineInstr *MI) {
1028
3.91M
  // Removing the first instruction in a bundle.
1029
3.91M
  if (
MI->isBundledWithSucc() && 3.91M
!MI->isBundledWithPred()1.23k
)
1030
6
    MI->unbundleFromSucc();
1031
3.91M
  // Removing the last instruction in a bundle.
1032
3.91M
  if (
MI->isBundledWithPred() && 3.91M
!MI->isBundledWithSucc()5.03k
)
1033
3.80k
    MI->unbundleFromPred();
1034
3.91M
  // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1035
3.91M
  // are already fine.
1036
3.91M
}
1037
1038
MachineBasicBlock::instr_iterator
1039
3.91M
MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {
1040
3.91M
  unbundleSingleMI(&*I);
1041
3.91M
  return Insts.erase(I);
1042
3.91M
}
1043
1044
7
MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) {
1045
7
  unbundleSingleMI(MI);
1046
7
  MI->clearFlag(MachineInstr::BundledPred);
1047
7
  MI->clearFlag(MachineInstr::BundledSucc);
1048
7
  return Insts.remove(MI);
1049
7
}
1050
1051
MachineBasicBlock::instr_iterator
1052
48.2k
MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) {
1053
48.2k
  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1054
48.2k
         "Cannot insert instruction with bundle flags");
1055
48.2k
  // Set the bundle flags when inserting inside a bundle.
1056
48.2k
  if (
I != instr_end() && 48.2k
I->isBundledWithPred()48.1k
) {
1057
5.03k
    MI->setFlag(MachineInstr::BundledPred);
1058
5.03k
    MI->setFlag(MachineInstr::BundledSucc);
1059
5.03k
  }
1060
48.2k
  return Insts.insert(I, MI);
1061
48.2k
}
1062
1063
/// This method unlinks 'this' from the containing function, and returns it, but
1064
/// does not delete it.
1065
0
MachineBasicBlock *MachineBasicBlock::removeFromParent() {
1066
0
  assert(getParent() && "Not embedded in a function!");
1067
0
  getParent()->remove(this);
1068
0
  return this;
1069
0
}
1070
1071
/// This method unlinks 'this' from the containing function, and deletes it.
1072
168k
void MachineBasicBlock::eraseFromParent() {
1073
168k
  assert(getParent() && "Not embedded in a function!");
1074
168k
  getParent()->erase(this);
1075
168k
}
1076
1077
/// Given a machine basic block that branched to 'Old', change the code and CFG
1078
/// so that it branches to 'New' instead.
1079
void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
1080
832k
                                               MachineBasicBlock *New) {
1081
832k
  assert(Old != New && "Cannot replace self with self!");
1082
832k
1083
832k
  MachineBasicBlock::instr_iterator I = instr_end();
1084
2.35M
  while (
I != instr_begin()2.35M
) {
1085
2.31M
    --I;
1086
2.31M
    if (
!I->isTerminator()2.31M
)
break793k
;
1087
1.51M
1088
1.51M
    // Scan the operands of this machine instruction, replacing any uses of Old
1089
1.51M
    // with New.
1090
4.30M
    
for (unsigned i = 0, e = I->getNumOperands(); 1.51M
i != e4.30M
;
++i2.78M
)
1091
2.78M
      
if (2.78M
I->getOperand(i).isMBB() &&
1092
1.51M
          I->getOperand(i).getMBB() == Old)
1093
775k
        I->getOperand(i).setMBB(New);
1094
2.31M
  }
1095
832k
1096
832k
  // Update the successor information.
1097
832k
  replaceSuccessor(Old, New);
1098
832k
}
1099
1100
/// Various pieces of code can cause excess edges in the CFG to be inserted.  If
1101
/// we have proven that MBB can only branch to DestA and DestB, remove any other
1102
/// MBB successors from the CFG.  DestA and DestB can be null.
1103
///
1104
/// Besides DestA and DestB, retain other edges leading to LandingPads
1105
/// (currently there can be only one; we don't check or require that here).
1106
/// Note it is possible that DestA and/or DestB are LandingPads.
1107
bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA,
1108
                                             MachineBasicBlock *DestB,
1109
26.2M
                                             bool IsCond) {
1110
26.2M
  // The values of DestA and DestB frequently come from a call to the
1111
26.2M
  // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1112
26.2M
  // values from there.
1113
26.2M
  //
1114
26.2M
  // 1. If both DestA and DestB are null, then the block ends with no branches
1115
26.2M
  //    (it falls through to its successor).
1116
26.2M
  // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1117
26.2M
  //    with only an unconditional branch.
1118
26.2M
  // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1119
26.2M
  //    with a conditional branch that falls through to a successor (DestB).
1120
26.2M
  // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1121
26.2M
  //    conditional branch followed by an unconditional branch. DestA is the
1122
26.2M
  //    'true' destination and DestB is the 'false' destination.
1123
26.2M
1124
26.2M
  bool Changed = false;
1125
26.2M
1126
26.2M
  MachineBasicBlock *FallThru = getNextNode();
1127
26.2M
1128
26.2M
  if (
!DestA && 26.2M
!DestB5.91M
) {
1129
5.91M
    // Block falls through to successor.
1130
5.91M
    DestA = FallThru;
1131
5.91M
    DestB = FallThru;
1132
26.2M
  } else 
if (20.3M
DestA && 20.3M
!DestB20.3M
) {
1133
16.7M
    if (IsCond)
1134
16.7M
      // Block ends in conditional jump that falls through to successor.
1135
11.9M
      DestB = FallThru;
1136
20.3M
  } else {
1137
3.61M
    assert(DestA && DestB && IsCond &&
1138
3.61M
           "CFG in a bad state. Cannot correct CFG edges");
1139
3.61M
  }
1140
26.2M
1141
26.2M
  // Remove superfluous edges. I.e., those which aren't destinations of this
1142
26.2M
  // basic block, duplicate edges, or landing pads.
1143
26.2M
  SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs;
1144
26.2M
  MachineBasicBlock::succ_iterator SI = succ_begin();
1145
68.1M
  while (
SI != succ_end()68.1M
) {
1146
41.8M
    const MachineBasicBlock *MBB = *SI;
1147
41.8M
    if (!SeenMBBs.insert(MBB).second ||
1148
41.8M
        
(MBB != DestA && 41.8M
MBB != DestB15.7M
&&
!MBB->isEHPad()192k
)) {
1149
1.33k
      // This is a superfluous edge, remove it.
1150
1.33k
      SI = removeSuccessor(SI);
1151
1.33k
      Changed = true;
1152
41.8M
    } else {
1153
41.8M
      ++SI;
1154
41.8M
    }
1155
41.8M
  }
1156
26.2M
1157
26.2M
  if (Changed)
1158
1.33k
    normalizeSuccProbs();
1159
26.2M
  return Changed;
1160
26.2M
}
1161
1162
/// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1163
/// instructions.  Return UnknownLoc if there is none.
1164
DebugLoc
1165
403k
MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
1166
403k
  // Skip debug declarations, we don't want a DebugLoc from them.
1167
403k
  MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1168
403k
  if (MBBI != instr_end())
1169
403k
    return MBBI->getDebugLoc();
1170
507
  return {};
1171
507
}
1172
1173
/// Find and return the merged DebugLoc of the branch instructions of the block.
1174
/// Return UnknownLoc if there is none.
1175
DebugLoc
1176
16.0M
MachineBasicBlock::findBranchDebugLoc() {
1177
16.0M
  DebugLoc DL;
1178
16.0M
  auto TI = getFirstTerminator();
1179
16.0M
  while (
TI != end() && 16.0M
!TI->isBranch()13.3M
)
1180
146
    ++TI;
1181
16.0M
1182
16.0M
  if (
TI != end()16.0M
) {
1183
13.3M
    DL = TI->getDebugLoc();
1184
15.3M
    for (++TI ; 
TI != end()15.3M
;
++TI2.01M
)
1185
2.01M
      
if (2.01M
TI->isBranch()2.01M
)
1186
2.01M
        DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1187
13.3M
  }
1188
16.0M
  return DL;
1189
16.0M
}
1190
1191
/// Return probability of the edge from this block to MBB.
1192
BranchProbability
1193
35.1M
MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1194
35.1M
  if (Probs.empty())
1195
213
    return BranchProbability(1, succ_size());
1196
35.1M
1197
35.1M
  const auto &Prob = *getProbabilityIterator(Succ);
1198
35.1M
  if (
Prob.isUnknown()35.1M
) {
1199
9.75M
    // For unknown probabilities, collect the sum of all known ones, and evenly
1200
9.75M
    // ditribute the complemental of the sum to each unknown probability.
1201
9.75M
    unsigned KnownProbNum = 0;
1202
9.75M
    auto Sum = BranchProbability::getZero();
1203
11.5M
    for (auto &P : Probs) {
1204
11.5M
      if (
!P.isUnknown()11.5M
) {
1205
11
        Sum += P;
1206
11
        KnownProbNum++;
1207
11
      }
1208
11.5M
    }
1209
9.75M
    return Sum.getCompl() / (Probs.size() - KnownProbNum);
1210
9.75M
  } else
1211
25.3M
    return Prob;
1212
0
}
1213
1214
/// Set successor probability of a given iterator.
1215
void MachineBasicBlock::setSuccProbability(succ_iterator I,
1216
83.3k
                                           BranchProbability Prob) {
1217
83.3k
  assert(!Prob.isUnknown());
1218
83.3k
  if (Probs.empty())
1219
3
    return;
1220
83.3k
  *getProbabilityIterator(I) = Prob;
1221
83.3k
}
1222
1223
/// Return probability iterator corresonding to the I successor iterator
1224
MachineBasicBlock::const_probability_iterator
1225
MachineBasicBlock::getProbabilityIterator(
1226
35.1M
    MachineBasicBlock::const_succ_iterator I) const {
1227
35.1M
  assert(Probs.size() == Successors.size() && "Async probability list!");
1228
35.1M
  const size_t index = std::distance(Successors.begin(), I);
1229
35.1M
  assert(index < Probs.size() && "Not a current successor!");
1230
35.1M
  return Probs.begin() + index;
1231
35.1M
}
1232
1233
/// Return probability iterator corresonding to the I successor iterator.
1234
MachineBasicBlock::probability_iterator
1235
1.64M
MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1236
1.64M
  assert(Probs.size() == Successors.size() && "Async probability list!");
1237
1.64M
  const size_t index = std::distance(Successors.begin(), I);
1238
1.64M
  assert(index < Probs.size() && "Not a current successor!");
1239
1.64M
  return Probs.begin() + index;
1240
1.64M
}
1241
1242
/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1243
/// as of just before "MI".
1244
///
1245
/// Search is localised to a neighborhood of
1246
/// Neighborhood instructions before (searching for defs or kills) and N
1247
/// instructions after (searching just for defs) MI.
1248
MachineBasicBlock::LivenessQueryResult
1249
MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
1250
                                           unsigned Reg, const_iterator Before,
1251
862
                                           unsigned Neighborhood) const {
1252
862
  unsigned N = Neighborhood;
1253
862
1254
862
  // Start by searching backwards from Before, looking for kills, reads or defs.
1255
862
  const_iterator I(Before);
1256
862
  // If this is the first insn in the block, don't search backwards.
1257
862
  if (
I != begin()862
) {
1258
2.61k
    do {
1259
2.61k
      --I;
1260
2.61k
1261
2.61k
      MachineOperandIteratorBase::PhysRegInfo Info =
1262
2.61k
          ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1263
2.61k
1264
2.61k
      // Defs happen after uses so they take precedence if both are present.
1265
2.61k
1266
2.61k
      // Register is dead after a dead def of the full register.
1267
2.61k
      if (Info.DeadDef)
1268
338
        return LQR_Dead;
1269
2.27k
      // Register is (at least partially) live after a def.
1270
2.27k
      
if (2.27k
Info.Defined2.27k
) {
1271
58
        if (!Info.PartialDeadDef)
1272
55
          return LQR_Live;
1273
3
        // As soon as we saw a partial definition (dead or not),
1274
3
        // we cannot tell if the value is partial live without
1275
3
        // tracking the lanemasks. We are not going to do this,
1276
3
        // so fall back on the remaining of the analysis.
1277
3
        break;
1278
3
      }
1279
2.21k
      // Register is dead after a full kill or clobber and no def.
1280
2.21k
      
if (2.21k
Info.Killed || 2.21k
Info.Clobbered2.18k
)
1281
29
        return LQR_Dead;
1282
2.18k
      // Register must be live if we read it.
1283
2.18k
      
if (2.18k
Info.Read2.18k
)
1284
2
        return LQR_Live;
1285
2.18k
    } while (
I != begin() && 2.18k
--N > 01.86k
);
1286
763
  }
1287
862
1288
862
  // Did we get to the start of the block?
1289
438
  
if (438
I == begin()438
) {
1290
418
    // If so, the register's state is definitely defined by the live-in state.
1291
2.68k
    for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
1292
2.26k
         ++RAI)
1293
2.27k
      
if (2.27k
isLiveIn(*RAI)2.27k
)
1294
13
        return LQR_Live;
1295
418
1296
405
    return LQR_Dead;
1297
20
  }
1298
20
1299
20
  N = Neighborhood;
1300
20
1301
20
  // Try searching forwards from Before, looking for reads or defs.
1302
20
  I = const_iterator(Before);
1303
20
  // If this is the last insn in the block, don't search forwards.
1304
20
  if (
I != end()20
) {
1305
82
    for (++I; 
I != end() && 82
N > 081
;
++I, --N62
) {
1306
80
      MachineOperandIteratorBase::PhysRegInfo Info =
1307
80
          ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1308
80
1309
80
      // Register is live when we read it here.
1310
80
      if (Info.Read)
1311
1
        return LQR_Live;
1312
79
      // Register is dead if we can fully overwrite or clobber it here.
1313
79
      
if (79
Info.FullyDefined || 79
Info.Clobbered70
)
1314
17
        return LQR_Dead;
1315
80
    }
1316
20
  }
1317
20
1318
20
  // At this point we have no idea of the liveness of the register.
1319
2
  return LQR_Unknown;
1320
862
}
1321
1322
const uint32_t *
1323
4.27M
MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
1324
4.27M
  // EH funclet entry does not preserve any registers.
1325
4.27M
  return isEHFuncletEntry() ? 
TRI->getNoPreservedMask()114
:
nullptr4.27M
;
1326
4.27M
}
1327
1328
const uint32_t *
1329
4.27M
MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const {
1330
4.27M
  // If we see a return block with successors, this must be a funclet return,
1331
4.27M
  // which does not preserve any registers. If there are no successors, we don't
1332
4.27M
  // care what kind of return it is, putting a mask after it is a no-op.
1333
4.27M
  return isReturnBlock() && 
!succ_empty()824k
?
TRI->getNoPreservedMask()71
:
nullptr4.27M
;
1334
4.27M
}
1335
1336
131k
void MachineBasicBlock::clearLiveIns() {
1337
131k
  LiveIns.clear();
1338
131k
}
1339
1340
33.1M
MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const {
1341
33.1M
  assert(getParent()->getProperties().hasProperty(
1342
33.1M
      MachineFunctionProperties::Property::TracksLiveness) &&
1343
33.1M
      "Liveness information is accurate");
1344
33.1M
  return LiveIns.begin();
1345
33.1M
}