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