Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/MachineBasicBlock.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
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
// Collect the sequence of machine instructions for a basic block.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/CodeGen/MachineBasicBlock.h"
14
#include "llvm/ADT/SmallPtrSet.h"
15
#include "llvm/CodeGen/LiveIntervals.h"
16
#include "llvm/CodeGen/LiveVariables.h"
17
#include "llvm/CodeGen/MachineDominators.h"
18
#include "llvm/CodeGen/MachineFunction.h"
19
#include "llvm/CodeGen/MachineInstrBuilder.h"
20
#include "llvm/CodeGen/MachineLoopInfo.h"
21
#include "llvm/CodeGen/MachineRegisterInfo.h"
22
#include "llvm/CodeGen/SlotIndexes.h"
23
#include "llvm/CodeGen/TargetInstrInfo.h"
24
#include "llvm/CodeGen/TargetRegisterInfo.h"
25
#include "llvm/CodeGen/TargetSubtargetInfo.h"
26
#include "llvm/Config/llvm-config.h"
27
#include "llvm/IR/BasicBlock.h"
28
#include "llvm/IR/DataLayout.h"
29
#include "llvm/IR/DebugInfoMetadata.h"
30
#include "llvm/IR/ModuleSlotTracker.h"
31
#include "llvm/MC/MCAsmInfo.h"
32
#include "llvm/MC/MCContext.h"
33
#include "llvm/Support/DataTypes.h"
34
#include "llvm/Support/Debug.h"
35
#include "llvm/Support/raw_ostream.h"
36
#include "llvm/Target/TargetMachine.h"
37
#include <algorithm>
38
using namespace llvm;
39
40
#define DEBUG_TYPE "codegen"
41
42
MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
43
3.78M
    : BB(B), Number(-1), xParent(&MF) {
44
3.78M
  Insts.Parent = this;
45
3.78M
  if (B)
46
3.28M
    IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();
47
3.78M
}
48
49
3.78M
MachineBasicBlock::~MachineBasicBlock() {
50
3.78M
}
51
52
/// Return the MCSymbol for this basic block.
53
2.91M
MCSymbol *MachineBasicBlock::getSymbol() const {
54
2.91M
  if (!CachedMCSymbol) {
55
1.19M
    const MachineFunction *MF = getParent();
56
1.19M
    MCContext &Ctx = MF->getContext();
57
1.19M
    auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
58
1.19M
    assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
59
1.19M
    CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
60
1.19M
                                           Twine(MF->getFunctionNumber()) +
61
1.19M
                                           "_" + Twine(getNumber()));
62
1.19M
  }
63
2.91M
64
2.91M
  return CachedMCSymbol;
65
2.91M
}
66
67
68
0
raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) {
69
0
  MBB.print(OS);
70
0
  return OS;
71
0
}
72
73
170k
Printable llvm::printMBBReference(const MachineBasicBlock &MBB) {
74
170k
  return Printable([&MBB](raw_ostream &OS) { return MBB.printAsOperand(OS); });
75
170k
}
76
77
/// When an MBB is added to an MF, we need to update the parent pointer of the
78
/// MBB, the MBB numbering, and any instructions in the MBB to be on the right
79
/// operand list for registers.
80
///
81
/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
82
/// gets the next available unique MBB number. If it is removed from a
83
/// MachineFunction, it goes back to being #-1.
84
void ilist_callback_traits<MachineBasicBlock>::addNodeToList(
85
3.78M
    MachineBasicBlock *N) {
86
3.78M
  MachineFunction &MF = *N->getParent();
87
3.78M
  N->Number = MF.addToMBBNumbering(N);
88
3.78M
89
3.78M
  // Make sure the instructions have their operands in the reginfo lists.
90
3.78M
  MachineRegisterInfo &RegInfo = MF.getRegInfo();
91
3.78M
  for (MachineBasicBlock::instr_iterator
92
3.78M
         I = N->instr_begin(), E = N->instr_end(); I != E; 
++I94
)
93
94
    I->AddRegOperandsToUseLists(RegInfo);
94
3.78M
}
95
96
void ilist_callback_traits<MachineBasicBlock>::removeNodeFromList(
97
3.78M
    MachineBasicBlock *N) {
98
3.78M
  N->getParent()->removeFromMBBNumbering(N->Number);
99
3.78M
  N->Number = -1;
100
3.78M
}
101
102
/// When we add an instruction to a basic block list, we update its parent
103
/// pointer and add its operands from reg use/def lists if appropriate.
104
66.5M
void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) {
105
66.5M
  assert(!N->getParent() && "machine instruction already in a basic block");
106
66.5M
  N->setParent(Parent);
107
66.5M
108
66.5M
  // Add the instruction's register operands to their corresponding
109
66.5M
  // use/def lists.
110
66.5M
  MachineFunction *MF = Parent->getParent();
111
66.5M
  N->AddRegOperandsToUseLists(MF->getRegInfo());
112
66.5M
  MF->handleInsertion(*N);
113
66.5M
}
114
115
/// When we remove an instruction from a basic block list, we update its parent
116
/// pointer and remove its operands from reg use/def lists if appropriate.
117
41.6M
void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) {
118
41.6M
  assert(N->getParent() && "machine instruction not in a basic block");
119
41.6M
120
41.6M
  // Remove from the use/def lists.
121
41.6M
  if (MachineFunction *MF = N->getMF()) {
122
41.6M
    MF->handleRemoval(*N);
123
41.6M
    N->RemoveRegOperandsFromUseLists(MF->getRegInfo());
124
41.6M
  }
125
41.6M
126
41.6M
  N->setParent(nullptr);
127
41.6M
}
128
129
/// When moving a range of instructions from one MBB list to another, we need to
130
/// update the parent pointers and the use/def lists.
131
void ilist_traits<MachineInstr>::transferNodesFromList(ilist_traits &FromList,
132
                                                       instr_iterator First,
133
5.20M
                                                       instr_iterator Last) {
134
5.20M
  assert(Parent->getParent() == FromList.Parent->getParent() &&
135
5.20M
         "cannot transfer MachineInstrs between MachineFunctions");
136
5.20M
137
5.20M
  // If it's within the same BB, there's nothing to do.
138
5.20M
  if (this == &FromList)
139
1.56M
    return;
140
3.63M
141
3.63M
  assert(Parent != FromList.Parent && "Two lists have the same parent?");
142
3.63M
143
3.63M
  // If splicing between two blocks within the same function, just update the
144
3.63M
  // parent pointers.
145
10.3M
  for (; First != Last; 
++First6.72M
)
146
6.72M
    First->setParent(Parent);
147
3.63M
}
148
149
40.9M
void ilist_traits<MachineInstr>::deleteNode(MachineInstr *MI) {
150
40.9M
  assert(!MI->getParent() && "MI is still in a block!");
151
40.9M
  Parent->getParent()->DeleteMachineInstr(MI);
152
40.9M
}
153
154
219k
MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() {
155
219k
  instr_iterator I = instr_begin(), E = instr_end();
156
268k
  while (I != E && 
I->isPHI()249k
)
157
49.5k
    ++I;
158
219k
  assert((I == E || !I->isInsideBundle()) &&
159
219k
         "First non-phi MI cannot be inside a bundle!");
160
219k
  return I;
161
219k
}
162
163
MachineBasicBlock::iterator
164
416k
MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) {
165
416k
  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
166
416k
167
416k
  iterator E = end();
168
1.05M
  while (I != E && 
(1.04M
I->isPHI()1.04M
||
I->isPosition()415k
||
169
1.04M
                    
TII->isBasicBlockPrologue(*I)407k
))
170
642k
    ++I;
171
416k
  // FIXME: This needs to change if we wish to bundle labels
172
416k
  // inside the bundle.
173
416k
  assert((I == E || !I->isInsideBundle()) &&
174
416k
         "First non-phi / non-label instruction is inside a bundle!");
175
416k
  return I;
176
416k
}
177
178
MachineBasicBlock::iterator
179
27.7M
MachineBasicBlock::SkipPHIsLabelsAndDebug(MachineBasicBlock::iterator I) {
180
27.7M
  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
181
27.7M
182
27.7M
  iterator E = end();
183
35.9M
  while (I != E && 
(35.9M
I->isPHI()35.9M
||
I->isPosition()35.9M
||
I->isDebugInstr()35.7M
||
184
35.9M
                    
TII->isBasicBlockPrologue(*I)27.7M
))
185
8.14M
    ++I;
186
27.7M
  // FIXME: This needs to change if we wish to bundle labels / dbg_values
187
27.7M
  // inside the bundle.
188
27.7M
  assert((I == E || !I->isInsideBundle()) &&
189
27.7M
         "First non-phi / non-label / non-debug "
190
27.7M
         "instruction is inside a bundle!");
191
27.7M
  return I;
192
27.7M
}
193
194
27.1M
MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
195
27.1M
  iterator B = begin(), E = end(), I = E;
196
53.0M
  while (I != B && 
(51.3M
(--I)->isTerminator()51.3M
||
I->isDebugInstr()25.4M
))
197
25.8M
    ; /*noop */
198
52.5M
  while (I != E && 
!I->isTerminator()48.3M
)
199
25.4M
    ++I;
200
27.1M
  return I;
201
27.1M
}
202
203
179k
MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() {
204
179k
  instr_iterator B = instr_begin(), E = instr_end(), I = E;
205
412k
  while (I != B && 
(405k
(--I)->isTerminator()405k
||
I->isDebugInstr()172k
))
206
232k
    ; /*noop */
207
352k
  while (I != E && 
!I->isTerminator()348k
)
208
172k
    ++I;
209
179k
  return I;
210
179k
}
211
212
17.5M
MachineBasicBlock::iterator MachineBasicBlock::getFirstNonDebugInstr() {
213
17.5M
  // Skip over begin-of-block dbg_value instructions.
214
17.5M
  return skipDebugInstructionsForward(begin(), end());
215
17.5M
}
216
217
75.5M
MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() {
218
75.5M
  // Skip over end-of-block dbg_value instructions.
219
75.5M
  instr_iterator B = instr_begin(), I = instr_end();
220
75.5M
  while (I != B) {
221
75.0M
    --I;
222
75.0M
    // Return instruction that starts a bundle.
223
75.0M
    if (I->isDebugInstr() || 
I->isInsideBundle()75.0M
)
224
3.50k
      continue;
225
75.0M
    return I;
226
75.0M
  }
227
75.5M
  // The block is all debug values.
228
75.5M
  
return end()531k
;
229
75.5M
}
230
231
6.95M
bool MachineBasicBlock::hasEHPadSuccessor() const {
232
17.8M
  for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; 
++I10.9M
)
233
11.0M
    if ((*I)->isEHPad())
234
96.1k
      return true;
235
6.95M
  
return false6.85M
;
236
6.95M
}
237
238
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
239
LLVM_DUMP_METHOD void MachineBasicBlock::dump() const {
240
  print(dbgs());
241
}
242
#endif
243
244
447k
bool MachineBasicBlock::isLegalToHoistInto() const {
245
447k
  if (isReturnBlock() || 
hasEHPadSuccessor()446k
)
246
1.40k
    return false;
247
445k
  return true;
248
445k
}
249
250
3.93k
StringRef MachineBasicBlock::getName() const {
251
3.93k
  if (const BasicBlock *LBB = getBasicBlock())
252
3.72k
    return LBB->getName();
253
208
  else
254
208
    return StringRef("", 0);
255
3.93k
}
256
257
/// Return a hopefully unique identifier for this block.
258
0
std::string MachineBasicBlock::getFullName() const {
259
0
  std::string Name;
260
0
  if (getParent())
261
0
    Name = (getParent()->getName() + ":").str();
262
0
  if (getBasicBlock())
263
0
    Name += getBasicBlock()->getName();
264
0
  else
265
0
    Name += ("BB" + Twine(getNumber())).str();
266
0
  return Name;
267
0
}
268
269
void MachineBasicBlock::print(raw_ostream &OS, const SlotIndexes *Indexes,
270
0
                              bool IsStandalone) const {
271
0
  const MachineFunction *MF = getParent();
272
0
  if (!MF) {
273
0
    OS << "Can't print out MachineBasicBlock because parent MachineFunction"
274
0
       << " is null\n";
275
0
    return;
276
0
  }
277
0
  const Function &F = MF->getFunction();
278
0
  const Module *M = F.getParent();
279
0
  ModuleSlotTracker MST(M);
280
0
  MST.incorporateFunction(F);
281
0
  print(OS, MST, Indexes, IsStandalone);
282
0
}
283
284
void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST,
285
                              const SlotIndexes *Indexes,
286
31.7k
                              bool IsStandalone) const {
287
31.7k
  const MachineFunction *MF = getParent();
288
31.7k
  if (!MF) {
289
0
    OS << "Can't print out MachineBasicBlock because parent MachineFunction"
290
0
       << " is null\n";
291
0
    return;
292
0
  }
293
31.7k
294
31.7k
  if (Indexes)
295
3.23k
    OS << Indexes->getMBBStartIdx(this) << '\t';
296
31.7k
297
31.7k
  OS << "bb." << getNumber();
298
31.7k
  bool HasAttributes = false;
299
31.7k
  if (const auto *BB = getBasicBlock()) {
300
31.6k
    if (BB->hasName()) {
301
31.0k
      OS << "." << BB->getName();
302
31.0k
    } else {
303
549
      HasAttributes = true;
304
549
      OS << " (";
305
549
      int Slot = MST.getLocalSlot(BB);
306
549
      if (Slot == -1)
307
0
        OS << "<ir-block badref>";
308
549
      else
309
549
        OS << (Twine("%ir-block.") + Twine(Slot)).str();
310
549
    }
311
31.6k
  }
312
31.7k
313
31.7k
  if (hasAddressTaken()) {
314
2
    OS << (HasAttributes ? 
", "0
: " (");
315
2
    OS << "address-taken";
316
2
    HasAttributes = true;
317
2
  }
318
31.7k
  if (isEHPad()) {
319
4
    OS << (HasAttributes ? 
", "0
: " (");
320
4
    OS << "landing-pad";
321
4
    HasAttributes = true;
322
4
  }
323
31.7k
  if (getAlignment()) {
324
0
    OS << (HasAttributes ? ", " : " (");
325
0
    OS << "align " << getAlignment();
326
0
    HasAttributes = true;
327
0
  }
328
31.7k
  if (HasAttributes)
329
555
    OS << ")";
330
31.7k
  OS << ":\n";
331
31.7k
332
31.7k
  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
333
31.7k
  const MachineRegisterInfo &MRI = MF->getRegInfo();
334
31.7k
  const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
335
31.7k
  bool HasLineAttributes = false;
336
31.7k
337
31.7k
  // Print the preds of this block according to the CFG.
338
31.7k
  if (!pred_empty() && 
IsStandalone28.7k
) {
339
28.7k
    if (Indexes) 
OS << '\t'2.90k
;
340
28.7k
    // Don't indent(2), align with previous line attributes.
341
28.7k
    OS << "; predecessors: ";
342
68.8k
    for (auto I = pred_begin(), E = pred_end(); I != E; 
++I40.0k
) {
343
40.0k
      if (I != pred_begin())
344
11.2k
        OS << ", ";
345
40.0k
      OS << printMBBReference(**I);
346
40.0k
    }
347
28.7k
    OS << '\n';
348
28.7k
    HasLineAttributes = true;
349
28.7k
  }
350
31.7k
351
31.7k
  if (!succ_empty()) {
352
18.1k
    if (Indexes) 
OS << '\t'1.82k
;
353
18.1k
    // Print the successors
354
18.1k
    OS.indent(2) << "successors: ";
355
58.2k
    for (auto I = succ_begin(), E = succ_end(); I != E; 
++I40.0k
) {
356
40.0k
      if (I != succ_begin())
357
21.8k
        OS << ", ";
358
40.0k
      OS << printMBBReference(**I);
359
40.0k
      if (!Probs.empty())
360
40.0k
        OS << '('
361
40.0k
           << format("0x%08" PRIx32, getSuccProbability(I).getNumerator())
362
40.0k
           << ')';
363
40.0k
    }
364
18.1k
    if (!Probs.empty() && IsStandalone) {
365
18.1k
      // Print human readable probabilities as comments.
366
18.1k
      OS << "; ";
367
58.2k
      for (auto I = succ_begin(), E = succ_end(); I != E; 
++I40.0k
) {
368
40.0k
        const BranchProbability &BP = getSuccProbability(I);
369
40.0k
        if (I != succ_begin())
370
21.8k
          OS << ", ";
371
40.0k
        OS << printMBBReference(**I) << '('
372
40.0k
           << format("%.2f%%",
373
40.0k
                     rint(((double)BP.getNumerator() / BP.getDenominator()) *
374
40.0k
                          100.0 * 100.0) /
375
40.0k
                         100.0)
376
40.0k
           << ')';
377
40.0k
      }
378
18.1k
    }
379
18.1k
380
18.1k
    OS << '\n';
381
18.1k
    HasLineAttributes = true;
382
18.1k
  }
383
31.7k
384
31.7k
  if (!livein_empty() && 
MRI.tracksLiveness()11.2k
) {
385
11.0k
    if (Indexes) 
OS << '\t'815
;
386
11.0k
    OS.indent(2) << "liveins: ";
387
11.0k
388
11.0k
    bool First = true;
389
15.3k
    for (const auto &LI : liveins()) {
390
15.3k
      if (!First)
391
4.29k
        OS << ", ";
392
15.3k
      First = false;
393
15.3k
      OS << printReg(LI.PhysReg, TRI);
394
15.3k
      if (!LI.LaneMask.all())
395
0
        OS << ":0x" << PrintLaneMask(LI.LaneMask);
396
15.3k
    }
397
11.0k
    HasLineAttributes = true;
398
11.0k
  }
399
31.7k
400
31.7k
  if (HasLineAttributes)
401
31.3k
    OS << '\n';
402
31.7k
403
31.7k
  bool IsInBundle = false;
404
134k
  for (const MachineInstr &MI : instrs()) {
405
134k
    if (Indexes) {
406
12.8k
      if (Indexes->hasIndex(MI))
407
12.6k
        OS << Indexes->getInstructionIndex(MI);
408
12.8k
      OS << '\t';
409
12.8k
    }
410
134k
411
134k
    if (IsInBundle && 
!MI.isInsideBundle()10
) {
412
2
      OS.indent(2) << "}\n";
413
2
      IsInBundle = false;
414
2
    }
415
134k
416
134k
    OS.indent(IsInBundle ? 
48
:
2134k
);
417
134k
    MI.print(OS, MST, IsStandalone, /*SkipOpers=*/false, /*SkipDebugLoc=*/false,
418
134k
             /*AddNewLine=*/false, &TII);
419
134k
420
134k
    if (!IsInBundle && 
MI.getFlag(MachineInstr::BundledSucc)134k
) {
421
2
      OS << " {";
422
2
      IsInBundle = true;
423
2
    }
424
134k
    OS << '\n';
425
134k
  }
426
31.7k
427
31.7k
  if (IsInBundle)
428
0
    OS.indent(2) << "}\n";
429
31.7k
430
31.7k
  if (IrrLoopHeaderWeight && 
IsStandalone0
) {
431
0
    if (Indexes) OS << '\t';
432
0
    OS.indent(2) << "; Irreducible loop header weight: "
433
0
                 << IrrLoopHeaderWeight.getValue() << '\n';
434
0
  }
435
31.7k
}
436
437
void MachineBasicBlock::printAsOperand(raw_ostream &OS,
438
170k
                                       bool /*PrintType*/) const {
439
170k
  OS << "%bb." << getNumber();
440
170k
}
441
442
247k
void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) {
443
247k
  LiveInVector::iterator I = find_if(
444
766k
      LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
445
247k
  if (I == LiveIns.end())
446
140k
    return;
447
106k
448
106k
  I->LaneMask &= ~LaneMask;
449
106k
  if (I->LaneMask.none())
450
106k
    LiveIns.erase(I);
451
106k
}
452
453
MachineBasicBlock::livein_iterator
454
4.88k
MachineBasicBlock::removeLiveIn(MachineBasicBlock::livein_iterator I) {
455
4.88k
  // Get non-const version of iterator.
456
4.88k
  LiveInVector::iterator LI = LiveIns.begin() + (I - LiveIns.begin());
457
4.88k
  return LiveIns.erase(LI);
458
4.88k
}
459
460
2.23M
bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const {
461
2.23M
  livein_iterator I = find_if(
462
9.84M
      LiveIns, [Reg](const RegisterMaskPair &LI) { return LI.PhysReg == Reg; });
463
2.23M
  return I != livein_end() && 
(I->LaneMask & LaneMask).any()1.16M
;
464
2.23M
}
465
466
3.06M
void MachineBasicBlock::sortUniqueLiveIns() {
467
3.06M
  llvm::sort(LiveIns,
468
34.0M
             [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) {
469
34.0M
               return LI0.PhysReg < LI1.PhysReg;
470
34.0M
             });
471
3.06M
  // Liveins are sorted by physreg now we can merge their lanemasks.
472
3.06M
  LiveInVector::const_iterator I = LiveIns.begin();
473
3.06M
  LiveInVector::const_iterator J;
474
3.06M
  LiveInVector::iterator Out = LiveIns.begin();
475
17.6M
  for (; I != LiveIns.end(); 
++Out, I = J14.6M
) {
476
14.6M
    unsigned PhysReg = I->PhysReg;
477
14.6M
    LaneBitmask LaneMask = I->LaneMask;
478
14.6M
    for (J = std::next(I); J != LiveIns.end() && 
J->PhysReg == PhysReg11.8M
;
++J710
)
479
710
      LaneMask |= J->LaneMask;
480
14.6M
    Out->PhysReg = PhysReg;
481
14.6M
    Out->LaneMask = LaneMask;
482
14.6M
  }
483
3.06M
  LiveIns.erase(Out, LiveIns.end());
484
3.06M
}
485
486
unsigned
487
6.86k
MachineBasicBlock::addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC) {
488
6.86k
  assert(getParent() && "MBB must be inserted in function");
489
6.86k
  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg");
490
6.86k
  assert(RC && "Register class is required");
491
6.86k
  assert((isEHPad() || this == &getParent()->front()) &&
492
6.86k
         "Only the entry block and landing pads can have physreg live ins");
493
6.86k
494
6.86k
  bool LiveIn = isLiveIn(PhysReg);
495
6.86k
  iterator I = SkipPHIsAndLabels(begin()), E = end();
496
6.86k
  MachineRegisterInfo &MRI = getParent()->getRegInfo();
497
6.86k
  const TargetInstrInfo &TII = *getParent()->getSubtarget().getInstrInfo();
498
6.86k
499
6.86k
  // Look for an existing copy.
500
6.86k
  if (LiveIn)
501
0
    for (;I != E && I->isCopy(); ++I)
502
0
      if (I->getOperand(1).getReg() == PhysReg) {
503
0
        unsigned VirtReg = I->getOperand(0).getReg();
504
0
        if (!MRI.constrainRegClass(VirtReg, RC))
505
0
          llvm_unreachable("Incompatible live-in register class.");
506
0
        return VirtReg;
507
0
      }
508
6.86k
509
6.86k
  // No luck, create a virtual register.
510
6.86k
  unsigned VirtReg = MRI.createVirtualRegister(RC);
511
6.86k
  BuildMI(*this, I, DebugLoc(), TII.get(TargetOpcode::COPY), VirtReg)
512
6.86k
    .addReg(PhysReg, RegState::Kill);
513
6.86k
  if (!LiveIn)
514
6.86k
    addLiveIn(PhysReg);
515
6.86k
  return VirtReg;
516
6.86k
}
517
518
15.3k
void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
519
15.3k
  getParent()->splice(NewAfter->getIterator(), getIterator());
520
15.3k
}
521
522
280k
void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
523
280k
  getParent()->splice(++NewBefore->getIterator(), getIterator());
524
280k
}
525
526
2.65M
void MachineBasicBlock::updateTerminator() {
527
2.65M
  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
528
2.65M
  // A block with no successors has no concerns with fall-through edges.
529
2.65M
  if (this->succ_empty())
530
39.6k
    return;
531
2.61M
532
2.61M
  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
533
2.61M
  SmallVector<MachineOperand, 4> Cond;
534
2.61M
  DebugLoc DL = findBranchDebugLoc();
535
2.61M
  bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
536
2.61M
  (void) B;
537
2.61M
  assert(!B && "UpdateTerminators requires analyzable predecessors!");
538
2.61M
  if (Cond.empty()) {
539
802k
    if (TBB) {
540
240k
      // The block has an unconditional branch. If its successor is now its
541
240k
      // layout successor, delete the branch.
542
240k
      if (isLayoutSuccessor(TBB))
543
70.8k
        TII->removeBranch(*this);
544
561k
    } else {
545
561k
      // The block has an unconditional fallthrough. If its successor is not its
546
561k
      // layout successor, insert a branch. First we have to locate the only
547
561k
      // non-landing-pad successor, as that is the fallthrough block.
548
1.16M
      for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; 
++SI599k
) {
549
599k
        if ((*SI)->isEHPad())
550
37.7k
          continue;
551
561k
        assert(!TBB && "Found more than one non-landing-pad successor!");
552
561k
        TBB = *SI;
553
561k
      }
554
561k
555
561k
      // If there is no non-landing-pad successor, the block has no fall-through
556
561k
      // edges to be concerned with.
557
561k
      if (!TBB)
558
0
        return;
559
561k
560
561k
      // Finally update the unconditional successor to be reached via a branch
561
561k
      // if it would not be reached by fallthrough.
562
561k
      if (!isLayoutSuccessor(TBB))
563
67.6k
        TII->insertBranch(*this, TBB, nullptr, Cond, DL);
564
561k
    }
565
802k
    return;
566
1.81M
  }
567
1.81M
568
1.81M
  if (FBB) {
569
230k
    // The block has a non-fallthrough conditional branch. If one of its
570
230k
    // successors is its layout successor, rewrite it to a fallthrough
571
230k
    // conditional branch.
572
230k
    if (isLayoutSuccessor(TBB)) {
573
128k
      if (TII->reverseBranchCondition(Cond))
574
4
        return;
575
128k
      TII->removeBranch(*this);
576
128k
      TII->insertBranch(*this, FBB, nullptr, Cond, DL);
577
128k
    } else 
if (101k
isLayoutSuccessor(FBB)101k
) {
578
52.4k
      TII->removeBranch(*this);
579
52.4k
      TII->insertBranch(*this, TBB, nullptr, Cond, DL);
580
52.4k
    }
581
230k
    
return230k
;
582
1.58M
  }
583
1.58M
584
1.58M
  // Walk through the successors and find the successor which is not a landing
585
1.58M
  // pad and is not the conditional branch destination (in TBB) as the
586
1.58M
  // fallthrough successor.
587
1.58M
  MachineBasicBlock *FallthroughBB = nullptr;
588
4.75M
  for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; 
++SI3.16M
) {
589
3.16M
    if ((*SI)->isEHPad() || *SI == TBB)
590
1.58M
      continue;
591
1.58M
    assert(!FallthroughBB && "Found more than one fallthrough successor.");
592
1.58M
    FallthroughBB = *SI;
593
1.58M
  }
594
1.58M
595
1.58M
  if (!FallthroughBB) {
596
10
    if (canFallThrough()) {
597
9
      // We fallthrough to the same basic block as the conditional jump targets.
598
9
      // Remove the conditional jump, leaving unconditional fallthrough.
599
9
      // FIXME: This does not seem like a reasonable pattern to support, but it
600
9
      // has been seen in the wild coming out of degenerate ARM test cases.
601
9
      TII->removeBranch(*this);
602
9
603
9
      // Finally update the unconditional successor to be reached via a branch if
604
9
      // it would not be reached by fallthrough.
605
9
      if (!isLayoutSuccessor(TBB))
606
0
        TII->insertBranch(*this, TBB, nullptr, Cond, DL);
607
9
      return;
608
9
    }
609
1
610
1
    // We enter here iff exactly one successor is TBB which cannot fallthrough
611
1
    // and the rest successors if any are EHPads.  In this case, we need to
612
1
    // change the conditional branch into unconditional branch.
613
1
    TII->removeBranch(*this);
614
1
    Cond.clear();
615
1
    TII->insertBranch(*this, TBB, nullptr, Cond, DL);
616
1
    return;
617
1
  }
618
1.58M
619
1.58M
  // The block has a fallthrough conditional branch.
620
1.58M
  if (isLayoutSuccessor(TBB)) {
621
344k
    if (TII->reverseBranchCondition(Cond)) {
622
22
      // We can't reverse the condition, add an unconditional branch.
623
22
      Cond.clear();
624
22
      TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
625
22
      return;
626
22
    }
627
344k
    TII->removeBranch(*this);
628
344k
    TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL);
629
1.23M
  } else if (!isLayoutSuccessor(FallthroughBB)) {
630
128k
    TII->removeBranch(*this);
631
128k
    TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL);
632
128k
  }
633
1.58M
}
634
635
0
void MachineBasicBlock::validateSuccProbs() const {
636
#ifndef NDEBUG
637
  int64_t Sum = 0;
638
  for (auto Prob : Probs)
639
    Sum += Prob.getNumerator();
640
  // Due to precision issue, we assume that the sum of probabilities is one if
641
  // the difference between the sum of their numerators and the denominator is
642
  // no greater than the number of successors.
643
  assert((uint64_t)std::abs(Sum - BranchProbability::getDenominator()) <=
644
             Probs.size() &&
645
         "The sum of successors's probabilities exceeds one.");
646
#endif // NDEBUG
647
}
648
649
void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
650
5.17M
                                     BranchProbability Prob) {
651
5.17M
  // Probability list is either empty (if successor list isn't empty, this means
652
5.17M
  // disabled optimization) or has the same size as successor list.
653
5.17M
  if (!(Probs.empty() && 
!Successors.empty()3.44M
))
654
5.17M
    Probs.push_back(Prob);
655
5.17M
  Successors.push_back(Succ);
656
5.17M
  Succ->addPredecessor(this);
657
5.17M
}
658
659
82.2k
void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
660
82.2k
  // We need to make sure probability list is either empty or has the same size
661
82.2k
  // of successor list. When this function is called, we can safely delete all
662
82.2k
  // probability in the list.
663
82.2k
  Probs.clear();
664
82.2k
  Successors.push_back(Succ);
665
82.2k
  Succ->addPredecessor(this);
666
82.2k
}
667
668
void MachineBasicBlock::splitSuccessor(MachineBasicBlock *Old,
669
                                       MachineBasicBlock *New,
670
0
                                       bool NormalizeSuccProbs) {
671
0
  succ_iterator OldI = llvm::find(successors(), Old);
672
0
  assert(OldI != succ_end() && "Old is not a successor of this block!");
673
0
  assert(llvm::find(successors(), New) == succ_end() &&
674
0
         "New is already a successor of this block!");
675
0
676
0
  // Add a new successor with equal probability as the original one. Note
677
0
  // that we directly copy the probability using the iterator rather than
678
0
  // getting a potentially synthetic probability computed when unknown. This
679
0
  // preserves the probabilities as-is and then we can renormalize them and
680
0
  // query them effectively afterward.
681
0
  addSuccessor(New, Probs.empty() ? BranchProbability::getUnknown()
682
0
                                  : *getProbabilityIterator(OldI));
683
0
  if (NormalizeSuccProbs)
684
0
    normalizeSuccProbs();
685
0
}
686
687
void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
688
407k
                                        bool NormalizeSuccProbs) {
689
407k
  succ_iterator I = find(Successors, Succ);
690
407k
  removeSuccessor(I, NormalizeSuccProbs);
691
407k
}
692
693
MachineBasicBlock::succ_iterator
694
1.04M
MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) {
695
1.04M
  assert(I != Successors.end() && "Not a current successor!");
696
1.04M
697
1.04M
  // If probability list is empty it means we don't use it (disabled
698
1.04M
  // optimization).
699
1.04M
  if (!Probs.empty()) {
700
1.04M
    probability_iterator WI = getProbabilityIterator(I);
701
1.04M
    Probs.erase(WI);
702
1.04M
    if (NormalizeSuccProbs)
703
17.5k
      normalizeSuccProbs();
704
1.04M
  }
705
1.04M
706
1.04M
  (*I)->removePredecessor(this);
707
1.04M
  return Successors.erase(I);
708
1.04M
}
709
710
void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
711
505k
                                         MachineBasicBlock *New) {
712
505k
  if (Old == New)
713
0
    return;
714
505k
715
505k
  succ_iterator E = succ_end();
716
505k
  succ_iterator NewI = E;
717
505k
  succ_iterator OldI = E;
718
1.52M
  for (succ_iterator I = succ_begin(); I != E; 
++I1.02M
) {
719
1.02M
    if (*I == Old) {
720
505k
      OldI = I;
721
505k
      if (NewI != E)
722
617
        break;
723
1.02M
    }
724
1.02M
    if (*I == New) {
725
1.25k
      NewI = I;
726
1.25k
      if (OldI != E)
727
636
        break;
728
1.25k
    }
729
1.02M
  }
730
505k
  assert(OldI != E && "Old is not a successor of this block");
731
505k
732
505k
  // If New isn't already a successor, let it take Old's place.
733
505k
  if (NewI == E) {
734
504k
    Old->removePredecessor(this);
735
504k
    New->addPredecessor(this);
736
504k
    *OldI = New;
737
504k
    return;
738
504k
  }
739
1.25k
740
1.25k
  // New is already a successor.
741
1.25k
  // Update its probability instead of adding a duplicate edge.
742
1.25k
  if (!Probs.empty()) {
743
905
    auto ProbIter = getProbabilityIterator(NewI);
744
905
    if (!ProbIter->isUnknown())
745
888
      *ProbIter += *getProbabilityIterator(OldI);
746
905
  }
747
1.25k
  removeSuccessor(OldI);
748
1.25k
}
749
750
void MachineBasicBlock::copySuccessor(MachineBasicBlock *Orig,
751
10
                                      succ_iterator I) {
752
10
  if (Orig->Probs.empty())
753
0
    addSuccessor(*I, Orig->getSuccProbability(I));
754
10
  else
755
10
    addSuccessorWithoutProb(*I);
756
10
}
757
758
5.76M
void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
759
5.76M
  Predecessors.push_back(Pred);
760
5.76M
}
761
762
1.54M
void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) {
763
1.54M
  pred_iterator I = find(Predecessors, Pred);
764
1.54M
  assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
765
1.54M
  Predecessors.erase(I);
766
1.54M
}
767
768
133k
void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {
769
133k
  if (this == FromMBB)
770
0
    return;
771
133k
772
260k
  
while (133k
!FromMBB->succ_empty()) {
773
127k
    MachineBasicBlock *Succ = *FromMBB->succ_begin();
774
127k
775
127k
    // If probability list is empty it means we don't use it (disabled optimization).
776
127k
    if (!FromMBB->Probs.empty()) {
777
126k
      auto Prob = *FromMBB->Probs.begin();
778
126k
      addSuccessor(Succ, Prob);
779
126k
    } else
780
1.22k
      addSuccessorWithoutProb(Succ);
781
127k
782
127k
    FromMBB->removeSuccessor(Succ);
783
127k
  }
784
133k
}
785
786
void
787
13.1k
MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
788
13.1k
  if (this == FromMBB)
789
0
    return;
790
13.1k
791
23.4k
  
while (13.1k
!FromMBB->succ_empty()) {
792
10.2k
    MachineBasicBlock *Succ = *FromMBB->succ_begin();
793
10.2k
    if (!FromMBB->Probs.empty()) {
794
10.0k
      auto Prob = *FromMBB->Probs.begin();
795
10.0k
      addSuccessor(Succ, Prob);
796
10.0k
    } else
797
226
      addSuccessorWithoutProb(Succ);
798
10.2k
    FromMBB->removeSuccessor(Succ);
799
10.2k
800
10.2k
    // Fix up any PHI nodes in the successor.
801
10.2k
    for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(),
802
20.6k
           ME = Succ->instr_end(); MI != ME && 
MI->isPHI()20.4k
;
++MI10.4k
)
803
40.6k
      
for (unsigned i = 2, e = MI->getNumOperands()+1; 10.4k
i != e;
i += 230.1k
) {
804
30.1k
        MachineOperand &MO = MI->getOperand(i);
805
30.1k
        if (MO.getMBB() == FromMBB)
806
10.4k
          MO.setMBB(this);
807
30.1k
      }
808
10.2k
  }
809
13.1k
  normalizeSuccProbs();
810
13.1k
}
811
812
1.28M
bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
813
1.28M
  return is_contained(predecessors(), MBB);
814
1.28M
}
815
816
31.5M
bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {
817
31.5M
  return is_contained(successors(), MBB);
818
31.5M
}
819
820
21.2M
bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {
821
21.2M
  MachineFunction::const_iterator I(this);
822
21.2M
  return std::next(I) == MachineFunction::const_iterator(MBB);
823
21.2M
}
824
825
16.9M
MachineBasicBlock *MachineBasicBlock::getFallThrough() {
826
16.9M
  MachineFunction::iterator Fallthrough = getIterator();
827
16.9M
  ++Fallthrough;
828
16.9M
  // If FallthroughBlock is off the end of the function, it can't fall through.
829
16.9M
  if (Fallthrough == getParent()->end())
830
1.30M
    return nullptr;
831
15.6M
832
15.6M
  // If FallthroughBlock isn't a successor, no fallthrough is possible.
833
15.6M
  if (!isSuccessor(&*Fallthrough))
834
4.20M
    return nullptr;
835
11.4M
836
11.4M
  // Analyze the branches, if any, at the end of the block.
837
11.4M
  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
838
11.4M
  SmallVector<MachineOperand, 4> Cond;
839
11.4M
  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
840
11.4M
  if (TII->analyzeBranch(*this, TBB, FBB, Cond)) {
841
83.9k
    // If we couldn't analyze the branch, examine the last instruction.
842
83.9k
    // If the block doesn't end in a known control barrier, assume fallthrough
843
83.9k
    // is possible. The isPredicated check is needed because this code can be
844
83.9k
    // called during IfConversion, where an instruction which is normally a
845
83.9k
    // Barrier is predicated and thus no longer an actual control barrier.
846
83.9k
    return (empty() || !back().isBarrier() || 
TII->isPredicated(back())79.3k
)
847
83.9k
               ? 
&*Fallthrough4.98k
848
83.9k
               : 
nullptr78.9k
;
849
83.9k
  }
850
11.3M
851
11.3M
  // If there is no branch, control always falls through.
852
11.3M
  if (!TBB) 
return &*Fallthrough3.24M
;
853
8.09M
854
8.09M
  // If there is some explicit branch to the fallthrough block, it can obviously
855
8.09M
  // reach, even though the branch should get folded to fall through implicitly.
856
8.09M
  if (MachineFunction::iterator(TBB) == Fallthrough ||
857
8.09M
      
MachineFunction::iterator(FBB) == Fallthrough7.95M
)
858
798k
    return &*Fallthrough;
859
7.29M
860
7.29M
  // If it's an unconditional branch to some block not the fall through, it
861
7.29M
  // doesn't fall through.
862
7.29M
  if (Cond.empty()) 
return nullptr13.5k
;
863
7.28M
864
7.28M
  // Otherwise, if it is conditional and has no explicit false block, it falls
865
7.28M
  // through.
866
7.28M
  return (FBB == nullptr) ? &*Fallthrough : 
nullptr0
;
867
7.28M
}
868
869
16.9M
bool MachineBasicBlock::canFallThrough() {
870
16.9M
  return getFallThrough() != nullptr;
871
16.9M
}
872
873
MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ,
874
254k
                                                        Pass &P) {
875
254k
  if (!canSplitCriticalEdge(Succ))
876
2.21k
    return nullptr;
877
252k
878
252k
  MachineFunction *MF = getParent();
879
252k
  DebugLoc DL;  // FIXME: this is nowhere
880
252k
881
252k
  MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
882
252k
  MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
883
252k
  LLVM_DEBUG(dbgs() << "Splitting critical edge: " << printMBBReference(*this)
884
252k
                    << " -- " << printMBBReference(*NMBB) << " -- "
885
252k
                    << printMBBReference(*Succ) << '\n');
886
252k
887
252k
  LiveIntervals *LIS = P.getAnalysisIfAvailable<LiveIntervals>();
888
252k
  SlotIndexes *Indexes = P.getAnalysisIfAvailable<SlotIndexes>();
889
252k
  if (LIS)
890
0
    LIS->insertMBBInMaps(NMBB);
891
252k
  else if (Indexes)
892
0
    Indexes->insertMBBInMaps(NMBB);
893
252k
894
252k
  // On some targets like Mips, branches may kill virtual registers. Make sure
895
252k
  // that LiveVariables is properly updated after updateTerminator replaces the
896
252k
  // terminators.
897
252k
  LiveVariables *LV = P.getAnalysisIfAvailable<LiveVariables>();
898
252k
899
252k
  // Collect a list of virtual registers killed by the terminators.
900
252k
  SmallVector<unsigned, 4> KilledRegs;
901
252k
  if (LV)
902
142k
    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
903
338k
         I != E; 
++I196k
) {
904
196k
      MachineInstr *MI = &*I;
905
196k
      for (MachineInstr::mop_iterator OI = MI->operands_begin(),
906
642k
           OE = MI->operands_end(); OI != OE; 
++OI446k
) {
907
446k
        if (!OI->isReg() || 
OI->getReg() == 0145k
||
908
446k
            
!OI->isUse()142k
||
!OI->isKill()142k
||
OI->isUndef()120k
)
909
326k
          continue;
910
120k
        unsigned Reg = OI->getReg();
911
120k
        if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
912
120k
            
LV->getVarInfo(Reg).removeKill(*MI)31.8k
) {
913
120k
          KilledRegs.push_back(Reg);
914
120k
          LLVM_DEBUG(dbgs() << "Removing terminator kill: " << *MI);
915
120k
          OI->setIsKill(false);
916
120k
        }
917
120k
      }
918
196k
    }
919
252k
920
252k
  SmallVector<unsigned, 4> UsedRegs;
921
252k
  if (LIS) {
922
0
    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
923
0
         I != E; ++I) {
924
0
      MachineInstr *MI = &*I;
925
0
926
0
      for (MachineInstr::mop_iterator OI = MI->operands_begin(),
927
0
           OE = MI->operands_end(); OI != OE; ++OI) {
928
0
        if (!OI->isReg() || OI->getReg() == 0)
929
0
          continue;
930
0
931
0
        unsigned Reg = OI->getReg();
932
0
        if (!is_contained(UsedRegs, Reg))
933
0
          UsedRegs.push_back(Reg);
934
0
      }
935
0
    }
936
0
  }
937
252k
938
252k
  ReplaceUsesOfBlockWith(Succ, NMBB);
939
252k
940
252k
  // If updateTerminator() removes instructions, we need to remove them from
941
252k
  // SlotIndexes.
942
252k
  SmallVector<MachineInstr*, 4> Terminators;
943
252k
  if (Indexes) {
944
0
    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
945
0
         I != E; ++I)
946
0
      Terminators.push_back(&*I);
947
0
  }
948
252k
949
252k
  updateTerminator();
950
252k
951
252k
  if (Indexes) {
952
0
    SmallVector<MachineInstr*, 4> NewTerminators;
953
0
    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
954
0
         I != E; ++I)
955
0
      NewTerminators.push_back(&*I);
956
0
957
0
    for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
958
0
        E = Terminators.end(); I != E; ++I) {
959
0
      if (!is_contained(NewTerminators, *I))
960
0
        Indexes->removeMachineInstrFromMaps(**I);
961
0
    }
962
0
  }
963
252k
964
252k
  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
965
252k
  NMBB->addSuccessor(Succ);
966
252k
  if (!NMBB->isLayoutSuccessor(Succ)) {
967
238k
    SmallVector<MachineOperand, 4> Cond;
968
238k
    const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
969
238k
    TII->insertBranch(*NMBB, Succ, nullptr, Cond, DL);
970
238k
971
238k
    if (Indexes) {
972
0
      for (MachineInstr &MI : NMBB->instrs()) {
973
0
        // Some instructions may have been moved to NMBB by updateTerminator(),
974
0
        // so we first remove any instruction that already has an index.
975
0
        if (Indexes->hasIndex(MI))
976
0
          Indexes->removeMachineInstrFromMaps(MI);
977
0
        Indexes->insertMachineInstrInMaps(MI);
978
0
      }
979
0
    }
980
238k
  }
981
252k
982
252k
  // Fix PHI nodes in Succ so they refer to NMBB instead of this
983
252k
  for (MachineBasicBlock::instr_iterator
984
252k
         i = Succ->instr_begin(),e = Succ->instr_end();
985
577k
       i != e && 
i->isPHI()574k
;
++i325k
)
986
3.48M
    
for (unsigned ni = 1, ne = i->getNumOperands(); 325k
ni != ne;
ni += 23.16M
)
987
3.16M
      if (i->getOperand(ni+1).getMBB() == this)
988
327k
        i->getOperand(ni+1).setMBB(NMBB);
989
252k
990
252k
  // Inherit live-ins from the successor
991
252k
  for (const auto &LI : Succ->liveins())
992
495
    NMBB->addLiveIn(LI);
993
252k
994
252k
  // Update LiveVariables.
995
252k
  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
996
252k
  if (LV) {
997
142k
    // Restore kills of virtual registers that were killed by the terminators.
998
262k
    while (!KilledRegs.empty()) {
999
120k
      unsigned Reg = KilledRegs.pop_back_val();
1000
120k
      for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
1001
120k
        if (!(--I)->addRegisterKilled(Reg, TRI, /* AddIfNotFound= */ false))
1002
10
          continue;
1003
120k
        if (TargetRegisterInfo::isVirtualRegister(Reg))
1004
31.8k
          LV->getVarInfo(Reg).Kills.push_back(&*I);
1005
120k
        LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
1006
120k
        break;
1007
120k
      }
1008
120k
    }
1009
142k
    // Update relevant live-through information.
1010
142k
    LV->addNewBlock(NMBB, this, Succ);
1011
142k
  }
1012
252k
1013
252k
  if (LIS) {
1014
0
    // After splitting the edge and updating SlotIndexes, live intervals may be
1015
0
    // in one of two situations, depending on whether this block was the last in
1016
0
    // the function. If the original block was the last in the function, all
1017
0
    // live intervals will end prior to the beginning of the new split block. If
1018
0
    // the original block was not at the end of the function, all live intervals
1019
0
    // will extend to the end of the new split block.
1020
0
1021
0
    bool isLastMBB =
1022
0
      std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
1023
0
1024
0
    SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
1025
0
    SlotIndex PrevIndex = StartIndex.getPrevSlot();
1026
0
    SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
1027
0
1028
0
    // Find the registers used from NMBB in PHIs in Succ.
1029
0
    SmallSet<unsigned, 8> PHISrcRegs;
1030
0
    for (MachineBasicBlock::instr_iterator
1031
0
         I = Succ->instr_begin(), E = Succ->instr_end();
1032
0
         I != E && I->isPHI(); ++I) {
1033
0
      for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
1034
0
        if (I->getOperand(ni+1).getMBB() == NMBB) {
1035
0
          MachineOperand &MO = I->getOperand(ni);
1036
0
          unsigned Reg = MO.getReg();
1037
0
          PHISrcRegs.insert(Reg);
1038
0
          if (MO.isUndef())
1039
0
            continue;
1040
0
1041
0
          LiveInterval &LI = LIS->getInterval(Reg);
1042
0
          VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1043
0
          assert(VNI &&
1044
0
                 "PHI sources should be live out of their predecessors.");
1045
0
          LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1046
0
        }
1047
0
      }
1048
0
    }
1049
0
1050
0
    MachineRegisterInfo *MRI = &getParent()->getRegInfo();
1051
0
    for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1052
0
      unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1053
0
      if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
1054
0
        continue;
1055
0
1056
0
      LiveInterval &LI = LIS->getInterval(Reg);
1057
0
      if (!LI.liveAt(PrevIndex))
1058
0
        continue;
1059
0
1060
0
      bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
1061
0
      if (isLiveOut && isLastMBB) {
1062
0
        VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
1063
0
        assert(VNI && "LiveInterval should have VNInfo where it is live.");
1064
0
        LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
1065
0
      } else if (!isLiveOut && !isLastMBB) {
1066
0
        LI.removeSegment(StartIndex, EndIndex);
1067
0
      }
1068
0
    }
1069
0
1070
0
    // Update all intervals for registers whose uses may have been modified by
1071
0
    // updateTerminator().
1072
0
    LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
1073
0
  }
1074
252k
1075
252k
  if (MachineDominatorTree *MDT =
1076
252k
          P.getAnalysisIfAvailable<MachineDominatorTree>())
1077
252k
    MDT->recordSplitCriticalEdge(this, Succ, NMBB);
1078
252k
1079
252k
  if (MachineLoopInfo *MLI = P.getAnalysisIfAvailable<MachineLoopInfo>())
1080
252k
    if (MachineLoop *TIL = MLI->getLoopFor(this)) {
1081
70.3k
      // If one or the other blocks were not in a loop, the new block is not
1082
70.3k
      // either, and thus LI doesn't need to be updated.
1083
70.3k
      if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
1084
44.9k
        if (TIL == DestLoop) {
1085
41.0k
          // Both in the same loop, the NMBB joins loop.
1086
41.0k
          DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1087
41.0k
        } else 
if (3.94k
TIL->contains(DestLoop)3.94k
) {
1088
413
          // Edge from an outer loop to an inner loop.  Add to the outer loop.
1089
413
          TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
1090
3.52k
        } else if (DestLoop->contains(TIL)) {
1091
3.37k
          // Edge from an inner loop to an outer loop.  Add to the outer loop.
1092
3.37k
          DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
1093
3.37k
        } else {
1094
157
          // Edge from two loops with no containment relation.  Because these
1095
157
          // are natural loops, we know that the destination block must be the
1096
157
          // header of its loop (adding a branch into a loop elsewhere would
1097
157
          // create an irreducible loop).
1098
157
          assert(DestLoop->getHeader() == Succ &&
1099
157
                 "Should not create irreducible loops!");
1100
157
          if (MachineLoop *P = DestLoop->getParentLoop())
1101
35
            P->addBasicBlockToLoop(NMBB, MLI->getBase());
1102
157
        }
1103
44.9k
      }
1104
70.3k
    }
1105
252k
1106
252k
  return NMBB;
1107
252k
}
1108
1109
bool MachineBasicBlock::canSplitCriticalEdge(
1110
254k
    const MachineBasicBlock *Succ) const {
1111
254k
  // Splitting the critical edge to a landing pad block is non-trivial. Don't do
1112
254k
  // it in this generic function.
1113
254k
  if (Succ->isEHPad())
1114
0
    return false;
1115
254k
1116
254k
  const MachineFunction *MF = getParent();
1117
254k
1118
254k
  // Performance might be harmed on HW that implements branching using exec mask
1119
254k
  // where both sides of the branches are always executed.
1120
254k
  if (MF->getTarget().requiresStructuredCFG())
1121
87
    return false;
1122
254k
1123
254k
  // We may need to update this's terminator, but we can't do that if
1124
254k
  // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
1125
254k
  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1126
254k
  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1127
254k
  SmallVector<MachineOperand, 4> Cond;
1128
254k
  // AnalyzeBanch should modify this, since we did not allow modification.
1129
254k
  if (TII->analyzeBranch(*const_cast<MachineBasicBlock *>(this), TBB, FBB, Cond,
1130
254k
                         /*AllowModify*/ false))
1131
2.13k
    return false;
1132
252k
1133
252k
  // Avoid bugpoint weirdness: A block may end with a conditional branch but
1134
252k
  // jumps to the same MBB is either case. We have duplicate CFG edges in that
1135
252k
  // case that we can't handle. Since this never happens in properly optimized
1136
252k
  // code, just skip those edges.
1137
252k
  if (TBB && TBB == FBB) {
1138
0
    LLVM_DEBUG(dbgs() << "Won't split critical edge after degenerate "
1139
0
                      << printMBBReference(*this) << '\n');
1140
0
    return false;
1141
0
  }
1142
252k
  return true;
1143
252k
}
1144
1145
/// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
1146
/// neighboring instructions so the bundle won't be broken by removing MI.
1147
2.85M
static void unbundleSingleMI(MachineInstr *MI) {
1148
2.85M
  // Removing the first instruction in a bundle.
1149
2.85M
  if (MI->isBundledWithSucc() && 
!MI->isBundledWithPred()2.19k
)
1150
6
    MI->unbundleFromSucc();
1151
2.85M
  // Removing the last instruction in a bundle.
1152
2.85M
  if (MI->isBundledWithPred() && 
!MI->isBundledWithSucc()8.86k
)
1153
6.67k
    MI->unbundleFromPred();
1154
2.85M
  // If MI is not bundled, or if it is internal to a bundle, the neighbor flags
1155
2.85M
  // are already fine.
1156
2.85M
}
1157
1158
MachineBasicBlock::instr_iterator
1159
2.85M
MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {
1160
2.85M
  unbundleSingleMI(&*I);
1161
2.85M
  return Insts.erase(I);
1162
2.85M
}
1163
1164
98
MachineInstr *MachineBasicBlock::remove_instr(MachineInstr *MI) {
1165
98
  unbundleSingleMI(MI);
1166
98
  MI->clearFlag(MachineInstr::BundledPred);
1167
98
  MI->clearFlag(MachineInstr::BundledSucc);
1168
98
  return Insts.remove(MI);
1169
98
}
1170
1171
MachineBasicBlock::instr_iterator
1172
122k
MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) {
1173
122k
  assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
1174
122k
         "Cannot insert instruction with bundle flags");
1175
122k
  // Set the bundle flags when inserting inside a bundle.
1176
122k
  if (I != instr_end() && 
I->isBundledWithPred()122k
) {
1177
8.79k
    MI->setFlag(MachineInstr::BundledPred);
1178
8.79k
    MI->setFlag(MachineInstr::BundledSucc);
1179
8.79k
  }
1180
122k
  return Insts.insert(I, MI);
1181
122k
}
1182
1183
/// This method unlinks 'this' from the containing function, and returns it, but
1184
/// does not delete it.
1185
0
MachineBasicBlock *MachineBasicBlock::removeFromParent() {
1186
0
  assert(getParent() && "Not embedded in a function!");
1187
0
  getParent()->remove(this);
1188
0
  return this;
1189
0
}
1190
1191
/// This method unlinks 'this' from the containing function, and deletes it.
1192
102k
void MachineBasicBlock::eraseFromParent() {
1193
102k
  assert(getParent() && "Not embedded in a function!");
1194
102k
  getParent()->erase(this);
1195
102k
}
1196
1197
/// Given a machine basic block that branched to 'Old', change the code and CFG
1198
/// so that it branches to 'New' instead.
1199
void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
1200
457k
                                               MachineBasicBlock *New) {
1201
457k
  assert(Old != New && "Cannot replace self with self!");
1202
457k
1203
457k
  MachineBasicBlock::instr_iterator I = instr_end();
1204
1.22M
  while (I != instr_begin()) {
1205
1.20M
    --I;
1206
1.20M
    if (!I->isTerminator()) 
break441k
;
1207
765k
1208
765k
    // Scan the operands of this machine instruction, replacing any uses of Old
1209
765k
    // with New.
1210
2.28M
    
for (unsigned i = 0, e = I->getNumOperands(); 765k
i != e;
++i1.52M
)
1211
1.52M
      if (I->getOperand(i).isMBB() &&
1212
1.52M
          
I->getOperand(i).getMBB() == Old764k
)
1213
425k
        I->getOperand(i).setMBB(New);
1214
765k
  }
1215
457k
1216
457k
  // Update the successor information.
1217
457k
  replaceSuccessor(Old, New);
1218
457k
}
1219
1220
/// Various pieces of code can cause excess edges in the CFG to be inserted.  If
1221
/// we have proven that MBB can only branch to DestA and DestB, remove any other
1222
/// MBB successors from the CFG.  DestA and DestB can be null.
1223
///
1224
/// Besides DestA and DestB, retain other edges leading to LandingPads
1225
/// (currently there can be only one; we don't check or require that here).
1226
/// Note it is possible that DestA and/or DestB are LandingPads.
1227
bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA,
1228
                                             MachineBasicBlock *DestB,
1229
16.7M
                                             bool IsCond) {
1230
16.7M
  // The values of DestA and DestB frequently come from a call to the
1231
16.7M
  // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
1232
16.7M
  // values from there.
1233
16.7M
  //
1234
16.7M
  // 1. If both DestA and DestB are null, then the block ends with no branches
1235
16.7M
  //    (it falls through to its successor).
1236
16.7M
  // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
1237
16.7M
  //    with only an unconditional branch.
1238
16.7M
  // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
1239
16.7M
  //    with a conditional branch that falls through to a successor (DestB).
1240
16.7M
  // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
1241
16.7M
  //    conditional branch followed by an unconditional branch. DestA is the
1242
16.7M
  //    'true' destination and DestB is the 'false' destination.
1243
16.7M
1244
16.7M
  bool Changed = false;
1245
16.7M
1246
16.7M
  MachineBasicBlock *FallThru = getNextNode();
1247
16.7M
1248
16.7M
  if (!DestA && 
!DestB4.11M
) {
1249
4.11M
    // Block falls through to successor.
1250
4.11M
    DestA = FallThru;
1251
4.11M
    DestB = FallThru;
1252
12.5M
  } else if (DestA && !DestB) {
1253
10.9M
    if (IsCond)
1254
7.96M
      // Block ends in conditional jump that falls through to successor.
1255
7.96M
      DestB = FallThru;
1256
10.9M
  } else {
1257
1.61M
    assert(DestA && DestB && IsCond &&
1258
1.61M
           "CFG in a bad state. Cannot correct CFG edges");
1259
1.61M
  }
1260
16.7M
1261
16.7M
  // Remove superfluous edges. I.e., those which aren't destinations of this
1262
16.7M
  // basic block, duplicate edges, or landing pads.
1263
16.7M
  SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs;
1264
16.7M
  MachineBasicBlock::succ_iterator SI = succ_begin();
1265
43.0M
  while (SI != succ_end()) {
1266
26.3M
    const MachineBasicBlock *MBB = *SI;
1267
26.3M
    if (!SeenMBBs.insert(MBB).second ||
1268
26.3M
        (MBB != DestA && 
MBB != DestB9.88M
&&
!MBB->isEHPad()299k
)) {
1269
2.92k
      // This is a superfluous edge, remove it.
1270
2.92k
      SI = removeSuccessor(SI);
1271
2.92k
      Changed = true;
1272
26.3M
    } else {
1273
26.3M
      ++SI;
1274
26.3M
    }
1275
26.3M
  }
1276
16.7M
1277
16.7M
  if (Changed)
1278
2.92k
    normalizeSuccProbs();
1279
16.7M
  return Changed;
1280
16.7M
}
1281
1282
/// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
1283
/// instructions.  Return UnknownLoc if there is none.
1284
DebugLoc
1285
528k
MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
1286
528k
  // Skip debug declarations, we don't want a DebugLoc from them.
1287
528k
  MBBI = skipDebugInstructionsForward(MBBI, instr_end());
1288
528k
  if (MBBI != instr_end())
1289
528k
    return MBBI->getDebugLoc();
1290
250
  return {};
1291
250
}
1292
1293
/// Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE
1294
/// instructions.  Return UnknownLoc if there is none.
1295
4.82k
DebugLoc MachineBasicBlock::findPrevDebugLoc(instr_iterator MBBI) {
1296
4.82k
  if (MBBI == instr_begin()) 
return {}286
;
1297
4.53k
  // Skip debug declarations, we don't want a DebugLoc from them.
1298
4.53k
  MBBI = skipDebugInstructionsBackward(std::prev(MBBI), instr_begin());
1299
4.53k
  if (!MBBI->isDebugInstr()) return MBBI->getDebugLoc();
1300
0
  return {};
1301
0
}
1302
1303
/// Find and return the merged DebugLoc of the branch instructions of the block.
1304
/// Return UnknownLoc if there is none.
1305
DebugLoc
1306
10.3M
MachineBasicBlock::findBranchDebugLoc() {
1307
10.3M
  DebugLoc DL;
1308
10.3M
  auto TI = getFirstTerminator();
1309
10.3M
  while (TI != end() && 
!TI->isBranch()8.66M
)
1310
171
    ++TI;
1311
10.3M
1312
10.3M
  if (TI != end()) {
1313
8.66M
    DL = TI->getDebugLoc();
1314
9.54M
    for (++TI ; TI != end() ; 
++TI871k
)
1315
871k
      if (TI->isBranch())
1316
871k
        DL = DILocation::getMergedLocation(DL, TI->getDebugLoc());
1317
8.66M
  }
1318
10.3M
  return DL;
1319
10.3M
}
1320
1321
/// Return probability of the edge from this block to MBB.
1322
BranchProbability
1323
23.7M
MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
1324
23.7M
  if (Probs.empty())
1325
349k
    return BranchProbability(1, succ_size());
1326
23.4M
1327
23.4M
  const auto &Prob = *getProbabilityIterator(Succ);
1328
23.4M
  if (Prob.isUnknown()) {
1329
14.7M
    // For unknown probabilities, collect the sum of all known ones, and evenly
1330
14.7M
    // ditribute the complemental of the sum to each unknown probability.
1331
14.7M
    unsigned KnownProbNum = 0;
1332
14.7M
    auto Sum = BranchProbability::getZero();
1333
23.7M
    for (auto &P : Probs) {
1334
23.7M
      if (!P.isUnknown()) {
1335
21
        Sum += P;
1336
21
        KnownProbNum++;
1337
21
      }
1338
23.7M
    }
1339
14.7M
    return Sum.getCompl() / (Probs.size() - KnownProbNum);
1340
14.7M
  } else
1341
8.70M
    return Prob;
1342
23.4M
}
1343
1344
/// Set successor probability of a given iterator.
1345
void MachineBasicBlock::setSuccProbability(succ_iterator I,
1346
29.7k
                                           BranchProbability Prob) {
1347
29.7k
  assert(!Prob.isUnknown());
1348
29.7k
  if (Probs.empty())
1349
578
    return;
1350
29.1k
  *getProbabilityIterator(I) = Prob;
1351
29.1k
}
1352
1353
/// Return probability iterator corresonding to the I successor iterator
1354
MachineBasicBlock::const_probability_iterator
1355
MachineBasicBlock::getProbabilityIterator(
1356
23.4M
    MachineBasicBlock::const_succ_iterator I) const {
1357
23.4M
  assert(Probs.size() == Successors.size() && "Async probability list!");
1358
23.4M
  const size_t index = std::distance(Successors.begin(), I);
1359
23.4M
  assert(index < Probs.size() && "Not a current successor!");
1360
23.4M
  return Probs.begin() + index;
1361
23.4M
}
1362
1363
/// Return probability iterator corresonding to the I successor iterator.
1364
MachineBasicBlock::probability_iterator
1365
1.07M
MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
1366
1.07M
  assert(Probs.size() == Successors.size() && "Async probability list!");
1367
1.07M
  const size_t index = std::distance(Successors.begin(), I);
1368
1.07M
  assert(index < Probs.size() && "Not a current successor!");
1369
1.07M
  return Probs.begin() + index;
1370
1.07M
}
1371
1372
/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
1373
/// as of just before "MI".
1374
///
1375
/// Search is localised to a neighborhood of
1376
/// Neighborhood instructions before (searching for defs or kills) and N
1377
/// instructions after (searching just for defs) MI.
1378
MachineBasicBlock::LivenessQueryResult
1379
MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
1380
                                           unsigned Reg, const_iterator Before,
1381
95.6k
                                           unsigned Neighborhood) const {
1382
95.6k
  unsigned N = Neighborhood;
1383
95.6k
1384
95.6k
  // Try searching forwards from Before, looking for reads or defs.
1385
95.6k
  const_iterator I(Before);
1386
261k
  for (; I != end() && 
N > 0251k
;
++I166k
) {
1387
235k
    if (I->isDebugInstr())
1388
37
      continue;
1389
235k
1390
235k
    --N;
1391
235k
1392
235k
    MachineOperandIteratorBase::PhysRegInfo Info =
1393
235k
        ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1394
235k
1395
235k
    // Register is live when we read it here.
1396
235k
    if (Info.Read)
1397
2.05k
      return LQR_Live;
1398
233k
    // Register is dead if we can fully overwrite or clobber it here.
1399
233k
    if (Info.FullyDefined || 
Info.Clobbered209k
)
1400
67.3k
      return LQR_Dead;
1401
233k
  }
1402
95.6k
1403
95.6k
  // If we reached the end, it is safe to clobber Reg at the end of a block of
1404
95.6k
  // no successor has it live in.
1405
95.6k
  
if (26.1k
I == end()26.1k
) {
1406
10.4k
    for (MachineBasicBlock *S : successors()) {
1407
10.5k
      for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) {
1408
10.5k
        if (TRI->regsOverlap(LI.PhysReg, Reg))
1409
28
          return LQR_Live;
1410
10.5k
      }
1411
7.31k
    }
1412
10.4k
1413
10.4k
    
return LQR_Dead10.4k
;
1414
15.7k
  }
1415
15.7k
1416
15.7k
1417
15.7k
  N = Neighborhood;
1418
15.7k
1419
15.7k
  // Start by searching backwards from Before, looking for kills, reads or defs.
1420
15.7k
  I = const_iterator(Before);
1421
15.7k
  // If this is the first insn in the block, don't search backwards.
1422
15.7k
  if (I != begin()) {
1423
30.1k
    do {
1424
30.1k
      --I;
1425
30.1k
1426
30.1k
      if (I->isDebugInstr())
1427
8
        continue;
1428
30.1k
1429
30.1k
      --N;
1430
30.1k
1431
30.1k
      MachineOperandIteratorBase::PhysRegInfo Info =
1432
30.1k
          ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
1433
30.1k
1434
30.1k
      // Defs happen after uses so they take precedence if both are present.
1435
30.1k
1436
30.1k
      // Register is dead after a dead def of the full register.
1437
30.1k
      if (Info.DeadDef)
1438
7.16k
        return LQR_Dead;
1439
22.9k
      // Register is (at least partially) live after a def.
1440
22.9k
      if (Info.Defined) {
1441
63
        if (!Info.PartialDeadDef)
1442
63
          return LQR_Live;
1443
0
        // As soon as we saw a partial definition (dead or not),
1444
0
        // we cannot tell if the value is partial live without
1445
0
        // tracking the lanemasks. We are not going to do this,
1446
0
        // so fall back on the remaining of the analysis.
1447
0
        break;
1448
0
      }
1449
22.8k
      // Register is dead after a full kill or clobber and no def.
1450
22.8k
      if (Info.Killed || 
Info.Clobbered22.8k
)
1451
80
        return LQR_Dead;
1452
22.8k
      // Register must be live if we read it.
1453
22.8k
      if (Info.Read)
1454
54
        return LQR_Live;
1455
22.7k
1456
22.7k
    } while (I != begin() && 
N > 021.4k
);
1457
11.2k
  }
1458
15.7k
1459
15.7k
  // Did we get to the start of the block?
1460
15.7k
  
if (8.34k
I == begin()8.34k
) {
1461
5.73k
    // If so, the register's state is definitely defined by the live-in state.
1462
5.73k
    for (const MachineBasicBlock::RegisterMaskPair &LI : liveins())
1463
18.5k
      if (TRI->regsOverlap(LI.PhysReg, Reg))
1464
0
        return LQR_Live;
1465
5.73k
1466
5.73k
    return LQR_Dead;
1467
2.60k
  }
1468
2.60k
1469
2.60k
  // At this point we have no idea of the liveness of the register.
1470
2.60k
  return LQR_Unknown;
1471
2.60k
}
1472
1473
const uint32_t *
1474
2.92M
MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
1475
2.92M
  // EH funclet entry does not preserve any registers.
1476
2.92M
  return isEHFuncletEntry() ? 
TRI->getNoPreservedMask()131
:
nullptr2.92M
;
1477
2.92M
}
1478
1479
const uint32_t *
1480
2.92M
MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const {
1481
2.92M
  // If we see a return block with successors, this must be a funclet return,
1482
2.92M
  // which does not preserve any registers. If there are no successors, we don't
1483
2.92M
  // care what kind of return it is, putting a mask after it is a no-op.
1484
2.92M
  return isReturnBlock() && 
!succ_empty()678k
?
TRI->getNoPreservedMask()82
:
nullptr2.92M
;
1485
2.92M
}
1486
1487
112k
void MachineBasicBlock::clearLiveIns() {
1488
112k
  LiveIns.clear();
1489
112k
}
1490
1491
25.1M
MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const {
1492
25.1M
  assert(getParent()->getProperties().hasProperty(
1493
25.1M
      MachineFunctionProperties::Property::TracksLiveness) &&
1494
25.1M
      "Liveness information is accurate");
1495
25.1M
  return LiveIns.begin();
1496
25.1M
}