1 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Collect the sequence of machine instructions for a basic block.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/MachineBasicBlock.h"
15 #include "llvm/BasicBlock.h"
16 #include "llvm/CodeGen/LiveVariables.h"
17 #include "llvm/CodeGen/MachineDominators.h"
18 #include "llvm/CodeGen/MachineFunction.h"
19 #include "llvm/CodeGen/MachineLoopInfo.h"
20 #include "llvm/MC/MCAsmInfo.h"
21 #include "llvm/MC/MCContext.h"
22 #include "llvm/Target/TargetRegisterInfo.h"
23 #include "llvm/Target/TargetData.h"
24 #include "llvm/Target/TargetInstrDesc.h"
25 #include "llvm/Target/TargetInstrInfo.h"
26 #include "llvm/Target/TargetMachine.h"
27 #include "llvm/Assembly/Writer.h"
28 #include "llvm/ADT/SmallString.h"
29 #include "llvm/ADT/SmallPtrSet.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/LeakDetector.h"
32 #include "llvm/Support/raw_ostream.h"
36 MachineBasicBlock::MachineBasicBlock(MachineFunction
&mf
, const BasicBlock
*bb
)
37 : BB(bb
), Number(-1), xParent(&mf
), Alignment(0), IsLandingPad(false),
42 MachineBasicBlock::~MachineBasicBlock() {
43 LeakDetector::removeGarbageObject(this);
46 /// getSymbol - Return the MCSymbol for this basic block.
48 MCSymbol
*MachineBasicBlock::getSymbol() const {
49 const MachineFunction
*MF
= getParent();
50 MCContext
&Ctx
= MF
->getContext();
51 const char *Prefix
= Ctx
.getAsmInfo().getPrivateGlobalPrefix();
52 return Ctx
.GetOrCreateSymbol(Twine(Prefix
) + "BB" +
53 Twine(MF
->getFunctionNumber()) + "_" +
58 raw_ostream
&llvm::operator<<(raw_ostream
&OS
, const MachineBasicBlock
&MBB
) {
63 /// addNodeToList (MBB) - When an MBB is added to an MF, we need to update the
64 /// parent pointer of the MBB, the MBB numbering, and any instructions in the
65 /// MBB to be on the right operand list for registers.
67 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
68 /// gets the next available unique MBB number. If it is removed from a
69 /// MachineFunction, it goes back to being #-1.
70 void ilist_traits
<MachineBasicBlock
>::addNodeToList(MachineBasicBlock
*N
) {
71 MachineFunction
&MF
= *N
->getParent();
72 N
->Number
= MF
.addToMBBNumbering(N
);
74 // Make sure the instructions have their operands in the reginfo lists.
75 MachineRegisterInfo
&RegInfo
= MF
.getRegInfo();
76 for (MachineBasicBlock::iterator I
= N
->begin(), E
= N
->end(); I
!= E
; ++I
)
77 I
->AddRegOperandsToUseLists(RegInfo
);
79 LeakDetector::removeGarbageObject(N
);
82 void ilist_traits
<MachineBasicBlock
>::removeNodeFromList(MachineBasicBlock
*N
) {
83 N
->getParent()->removeFromMBBNumbering(N
->Number
);
85 LeakDetector::addGarbageObject(N
);
89 /// addNodeToList (MI) - When we add an instruction to a basic block
90 /// list, we update its parent pointer and add its operands from reg use/def
91 /// lists if appropriate.
92 void ilist_traits
<MachineInstr
>::addNodeToList(MachineInstr
*N
) {
93 assert(N
->getParent() == 0 && "machine instruction already in a basic block");
96 // Add the instruction's register operands to their corresponding
98 MachineFunction
*MF
= Parent
->getParent();
99 N
->AddRegOperandsToUseLists(MF
->getRegInfo());
101 LeakDetector::removeGarbageObject(N
);
104 /// removeNodeFromList (MI) - When we remove an instruction from a basic block
105 /// list, we update its parent pointer and remove its operands from reg use/def
106 /// lists if appropriate.
107 void ilist_traits
<MachineInstr
>::removeNodeFromList(MachineInstr
*N
) {
108 assert(N
->getParent() != 0 && "machine instruction not in a basic block");
110 // Remove from the use/def lists.
111 N
->RemoveRegOperandsFromUseLists();
115 LeakDetector::addGarbageObject(N
);
118 /// transferNodesFromList (MI) - When moving a range of instructions from one
119 /// MBB list to another, we need to update the parent pointers and the use/def
121 void ilist_traits
<MachineInstr
>::
122 transferNodesFromList(ilist_traits
<MachineInstr
> &fromList
,
123 MachineBasicBlock::iterator first
,
124 MachineBasicBlock::iterator last
) {
125 assert(Parent
->getParent() == fromList
.Parent
->getParent() &&
126 "MachineInstr parent mismatch!");
128 // Splice within the same MBB -> no change.
129 if (Parent
== fromList
.Parent
) return;
131 // If splicing between two blocks within the same function, just update the
133 for (; first
!= last
; ++first
)
134 first
->setParent(Parent
);
137 void ilist_traits
<MachineInstr
>::deleteNode(MachineInstr
* MI
) {
138 assert(!MI
->getParent() && "MI is still in a block!");
139 Parent
->getParent()->DeleteMachineInstr(MI
);
142 MachineBasicBlock::iterator
MachineBasicBlock::getFirstNonPHI() {
143 iterator I
= begin();
144 while (I
!= end() && I
->isPHI())
149 MachineBasicBlock::iterator
MachineBasicBlock::getFirstTerminator() {
151 while (I
!= begin() && (--I
)->getDesc().isTerminator())
153 if (I
!= end() && !I
->getDesc().isTerminator()) ++I
;
157 void MachineBasicBlock::dump() const {
161 static inline void OutputReg(raw_ostream
&os
, unsigned RegNo
,
162 const TargetRegisterInfo
*TRI
= 0) {
163 if (RegNo
!= 0 && TargetRegisterInfo::isPhysicalRegister(RegNo
)) {
165 os
<< " %" << TRI
->get(RegNo
).Name
;
167 os
<< " %physreg" << RegNo
;
169 os
<< " %reg" << RegNo
;
172 StringRef
MachineBasicBlock::getName() const {
173 if (const BasicBlock
*LBB
= getBasicBlock())
174 return LBB
->getName();
179 void MachineBasicBlock::print(raw_ostream
&OS
) const {
180 const MachineFunction
*MF
= getParent();
182 OS
<< "Can't print out MachineBasicBlock because parent MachineFunction"
187 if (Alignment
) { OS
<< "Alignment " << Alignment
<< "\n"; }
189 OS
<< "BB#" << getNumber() << ": ";
191 const char *Comma
= "";
192 if (const BasicBlock
*LBB
= getBasicBlock()) {
193 OS
<< Comma
<< "derived from LLVM BB ";
194 WriteAsOperand(OS
, LBB
, /*PrintType=*/false);
197 if (isLandingPad()) { OS
<< Comma
<< "EH LANDING PAD"; Comma
= ", "; }
198 if (hasAddressTaken()) { OS
<< Comma
<< "ADDRESS TAKEN"; Comma
= ", "; }
201 const TargetRegisterInfo
*TRI
= MF
->getTarget().getRegisterInfo();
202 if (!livein_empty()) {
204 for (livein_iterator I
= livein_begin(),E
= livein_end(); I
!= E
; ++I
)
205 OutputReg(OS
, *I
, TRI
);
208 // Print the preds of this block according to the CFG.
210 OS
<< " Predecessors according to CFG:";
211 for (const_pred_iterator PI
= pred_begin(), E
= pred_end(); PI
!= E
; ++PI
)
212 OS
<< " BB#" << (*PI
)->getNumber();
216 for (const_iterator I
= begin(); I
!= end(); ++I
) {
218 I
->print(OS
, &getParent()->getTarget());
221 // Print the successors of this block according to the CFG.
223 OS
<< " Successors according to CFG:";
224 for (const_succ_iterator SI
= succ_begin(), E
= succ_end(); SI
!= E
; ++SI
)
225 OS
<< " BB#" << (*SI
)->getNumber();
230 void MachineBasicBlock::removeLiveIn(unsigned Reg
) {
231 std::vector
<unsigned>::iterator I
=
232 std::find(LiveIns
.begin(), LiveIns
.end(), Reg
);
233 assert(I
!= LiveIns
.end() && "Not a live in!");
237 bool MachineBasicBlock::isLiveIn(unsigned Reg
) const {
238 livein_iterator I
= std::find(livein_begin(), livein_end(), Reg
);
239 return I
!= livein_end();
242 void MachineBasicBlock::moveBefore(MachineBasicBlock
*NewAfter
) {
243 getParent()->splice(NewAfter
, this);
246 void MachineBasicBlock::moveAfter(MachineBasicBlock
*NewBefore
) {
247 MachineFunction::iterator BBI
= NewBefore
;
248 getParent()->splice(++BBI
, this);
251 void MachineBasicBlock::updateTerminator() {
252 const TargetInstrInfo
*TII
= getParent()->getTarget().getInstrInfo();
253 // A block with no successors has no concerns with fall-through edges.
254 if (this->succ_empty()) return;
256 MachineBasicBlock
*TBB
= 0, *FBB
= 0;
257 SmallVector
<MachineOperand
, 4> Cond
;
258 DebugLoc dl
; // FIXME: this is nowhere
259 bool B
= TII
->AnalyzeBranch(*this, TBB
, FBB
, Cond
);
261 assert(!B
&& "UpdateTerminators requires analyzable predecessors!");
264 // The block has an unconditional branch. If its successor is now
265 // its layout successor, delete the branch.
266 if (isLayoutSuccessor(TBB
))
267 TII
->RemoveBranch(*this);
269 // The block has an unconditional fallthrough. If its successor is not
270 // its layout successor, insert a branch.
272 if (!isLayoutSuccessor(TBB
))
273 TII
->InsertBranch(*this, TBB
, 0, Cond
, dl
);
277 // The block has a non-fallthrough conditional branch. If one of its
278 // successors is its layout successor, rewrite it to a fallthrough
279 // conditional branch.
280 if (isLayoutSuccessor(TBB
)) {
281 if (TII
->ReverseBranchCondition(Cond
))
283 TII
->RemoveBranch(*this);
284 TII
->InsertBranch(*this, FBB
, 0, Cond
, dl
);
285 } else if (isLayoutSuccessor(FBB
)) {
286 TII
->RemoveBranch(*this);
287 TII
->InsertBranch(*this, TBB
, 0, Cond
, dl
);
290 // The block has a fallthrough conditional branch.
291 MachineBasicBlock
*MBBA
= *succ_begin();
292 MachineBasicBlock
*MBBB
= *llvm::next(succ_begin());
293 if (MBBA
== TBB
) std::swap(MBBB
, MBBA
);
294 if (isLayoutSuccessor(TBB
)) {
295 if (TII
->ReverseBranchCondition(Cond
)) {
296 // We can't reverse the condition, add an unconditional branch.
298 TII
->InsertBranch(*this, MBBA
, 0, Cond
, dl
);
301 TII
->RemoveBranch(*this);
302 TII
->InsertBranch(*this, MBBA
, 0, Cond
, dl
);
303 } else if (!isLayoutSuccessor(MBBA
)) {
304 TII
->RemoveBranch(*this);
305 TII
->InsertBranch(*this, TBB
, MBBA
, Cond
, dl
);
311 void MachineBasicBlock::addSuccessor(MachineBasicBlock
*succ
) {
312 Successors
.push_back(succ
);
313 succ
->addPredecessor(this);
316 void MachineBasicBlock::removeSuccessor(MachineBasicBlock
*succ
) {
317 succ
->removePredecessor(this);
318 succ_iterator I
= std::find(Successors
.begin(), Successors
.end(), succ
);
319 assert(I
!= Successors
.end() && "Not a current successor!");
323 MachineBasicBlock::succ_iterator
324 MachineBasicBlock::removeSuccessor(succ_iterator I
) {
325 assert(I
!= Successors
.end() && "Not a current successor!");
326 (*I
)->removePredecessor(this);
327 return Successors
.erase(I
);
330 void MachineBasicBlock::addPredecessor(MachineBasicBlock
*pred
) {
331 Predecessors
.push_back(pred
);
334 void MachineBasicBlock::removePredecessor(MachineBasicBlock
*pred
) {
335 std::vector
<MachineBasicBlock
*>::iterator I
=
336 std::find(Predecessors
.begin(), Predecessors
.end(), pred
);
337 assert(I
!= Predecessors
.end() && "Pred is not a predecessor of this block!");
338 Predecessors
.erase(I
);
341 void MachineBasicBlock::transferSuccessors(MachineBasicBlock
*fromMBB
) {
345 while (!fromMBB
->succ_empty()) {
346 MachineBasicBlock
*Succ
= *fromMBB
->succ_begin();
348 fromMBB
->removeSuccessor(Succ
);
353 MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock
*fromMBB
) {
357 while (!fromMBB
->succ_empty()) {
358 MachineBasicBlock
*Succ
= *fromMBB
->succ_begin();
360 fromMBB
->removeSuccessor(Succ
);
362 // Fix up any PHI nodes in the successor.
363 for (MachineBasicBlock::iterator MI
= Succ
->begin(), ME
= Succ
->end();
364 MI
!= ME
&& MI
->isPHI(); ++MI
)
365 for (unsigned i
= 2, e
= MI
->getNumOperands()+1; i
!= e
; i
+= 2) {
366 MachineOperand
&MO
= MI
->getOperand(i
);
367 if (MO
.getMBB() == fromMBB
)
373 bool MachineBasicBlock::isSuccessor(const MachineBasicBlock
*MBB
) const {
374 std::vector
<MachineBasicBlock
*>::const_iterator I
=
375 std::find(Successors
.begin(), Successors
.end(), MBB
);
376 return I
!= Successors
.end();
379 bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock
*MBB
) const {
380 MachineFunction::const_iterator
I(this);
381 return llvm::next(I
) == MachineFunction::const_iterator(MBB
);
384 bool MachineBasicBlock::canFallThrough() {
385 MachineFunction::iterator Fallthrough
= this;
387 // If FallthroughBlock is off the end of the function, it can't fall through.
388 if (Fallthrough
== getParent()->end())
391 // If FallthroughBlock isn't a successor, no fallthrough is possible.
392 if (!isSuccessor(Fallthrough
))
395 // Analyze the branches, if any, at the end of the block.
396 MachineBasicBlock
*TBB
= 0, *FBB
= 0;
397 SmallVector
<MachineOperand
, 4> Cond
;
398 const TargetInstrInfo
*TII
= getParent()->getTarget().getInstrInfo();
399 if (TII
->AnalyzeBranch(*this, TBB
, FBB
, Cond
)) {
400 // If we couldn't analyze the branch, examine the last instruction.
401 // If the block doesn't end in a known control barrier, assume fallthrough
402 // is possible. The isPredicable check is needed because this code can be
403 // called during IfConversion, where an instruction which is normally a
404 // Barrier is predicated and thus no longer an actual control barrier. This
405 // is over-conservative though, because if an instruction isn't actually
406 // predicated we could still treat it like a barrier.
407 return empty() || !back().getDesc().isBarrier() ||
408 back().getDesc().isPredicable();
411 // If there is no branch, control always falls through.
412 if (TBB
== 0) return true;
414 // If there is some explicit branch to the fallthrough block, it can obviously
415 // reach, even though the branch should get folded to fall through implicitly.
416 if (MachineFunction::iterator(TBB
) == Fallthrough
||
417 MachineFunction::iterator(FBB
) == Fallthrough
)
420 // If it's an unconditional branch to some block not the fall through, it
421 // doesn't fall through.
422 if (Cond
.empty()) return false;
424 // Otherwise, if it is conditional and has no explicit false block, it falls
430 MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock
*Succ
, Pass
*P
) {
431 MachineFunction
*MF
= getParent();
432 DebugLoc dl
; // FIXME: this is nowhere
434 // We may need to update this's terminator, but we can't do that if AnalyzeBranch
435 // fails. If this uses a jump table, we won't touch it.
436 const TargetInstrInfo
*TII
= MF
->getTarget().getInstrInfo();
437 MachineBasicBlock
*TBB
= 0, *FBB
= 0;
438 SmallVector
<MachineOperand
, 4> Cond
;
439 if (TII
->AnalyzeBranch(*this, TBB
, FBB
, Cond
))
442 MachineBasicBlock
*NMBB
= MF
->CreateMachineBasicBlock();
443 MF
->insert(llvm::next(MachineFunction::iterator(this)), NMBB
);
444 DEBUG(dbgs() << "PHIElimination splitting critical edge:"
445 " BB#" << getNumber()
446 << " -- BB#" << NMBB
->getNumber()
447 << " -- BB#" << Succ
->getNumber() << '\n');
449 ReplaceUsesOfBlockWith(Succ
, NMBB
);
452 // Insert unconditional "jump Succ" instruction in NMBB if necessary.
453 NMBB
->addSuccessor(Succ
);
454 if (!NMBB
->isLayoutSuccessor(Succ
)) {
456 MF
->getTarget().getInstrInfo()->InsertBranch(*NMBB
, Succ
, NULL
, Cond
, dl
);
459 // Fix PHI nodes in Succ so they refer to NMBB instead of this
460 for (MachineBasicBlock::iterator i
= Succ
->begin(), e
= Succ
->end();
461 i
!= e
&& i
->isPHI(); ++i
)
462 for (unsigned ni
= 1, ne
= i
->getNumOperands(); ni
!= ne
; ni
+= 2)
463 if (i
->getOperand(ni
+1).getMBB() == this)
464 i
->getOperand(ni
+1).setMBB(NMBB
);
466 if (LiveVariables
*LV
=
467 P
->getAnalysisIfAvailable
<LiveVariables
>())
468 LV
->addNewBlock(NMBB
, this, Succ
);
470 if (MachineDominatorTree
*MDT
=
471 P
->getAnalysisIfAvailable
<MachineDominatorTree
>())
472 MDT
->addNewBlock(NMBB
, this);
474 if (MachineLoopInfo
*MLI
=
475 P
->getAnalysisIfAvailable
<MachineLoopInfo
>())
476 if (MachineLoop
*TIL
= MLI
->getLoopFor(this)) {
477 // If one or the other blocks were not in a loop, the new block is not
478 // either, and thus LI doesn't need to be updated.
479 if (MachineLoop
*DestLoop
= MLI
->getLoopFor(Succ
)) {
480 if (TIL
== DestLoop
) {
481 // Both in the same loop, the NMBB joins loop.
482 DestLoop
->addBasicBlockToLoop(NMBB
, MLI
->getBase());
483 } else if (TIL
->contains(DestLoop
)) {
484 // Edge from an outer loop to an inner loop. Add to the outer loop.
485 TIL
->addBasicBlockToLoop(NMBB
, MLI
->getBase());
486 } else if (DestLoop
->contains(TIL
)) {
487 // Edge from an inner loop to an outer loop. Add to the outer loop.
488 DestLoop
->addBasicBlockToLoop(NMBB
, MLI
->getBase());
490 // Edge from two loops with no containment relation. Because these
491 // are natural loops, we know that the destination block must be the
492 // header of its loop (adding a branch into a loop elsewhere would
493 // create an irreducible loop).
494 assert(DestLoop
->getHeader() == Succ
&&
495 "Should not create irreducible loops!");
496 if (MachineLoop
*P
= DestLoop
->getParentLoop())
497 P
->addBasicBlockToLoop(NMBB
, MLI
->getBase());
505 /// removeFromParent - This method unlinks 'this' from the containing function,
506 /// and returns it, but does not delete it.
507 MachineBasicBlock
*MachineBasicBlock::removeFromParent() {
508 assert(getParent() && "Not embedded in a function!");
509 getParent()->remove(this);
514 /// eraseFromParent - This method unlinks 'this' from the containing function,
516 void MachineBasicBlock::eraseFromParent() {
517 assert(getParent() && "Not embedded in a function!");
518 getParent()->erase(this);
522 /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to
523 /// 'Old', change the code and CFG so that it branches to 'New' instead.
524 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock
*Old
,
525 MachineBasicBlock
*New
) {
526 assert(Old
!= New
&& "Cannot replace self with self!");
528 MachineBasicBlock::iterator I
= end();
529 while (I
!= begin()) {
531 if (!I
->getDesc().isTerminator()) break;
533 // Scan the operands of this machine instruction, replacing any uses of Old
535 for (unsigned i
= 0, e
= I
->getNumOperands(); i
!= e
; ++i
)
536 if (I
->getOperand(i
).isMBB() &&
537 I
->getOperand(i
).getMBB() == Old
)
538 I
->getOperand(i
).setMBB(New
);
541 // Update the successor information.
542 removeSuccessor(Old
);
546 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the
547 /// CFG to be inserted. If we have proven that MBB can only branch to DestA and
548 /// DestB, remove any other MBB successors from the CFG. DestA and DestB can be
551 /// Besides DestA and DestB, retain other edges leading to LandingPads
552 /// (currently there can be only one; we don't check or require that here).
553 /// Note it is possible that DestA and/or DestB are LandingPads.
554 bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock
*DestA
,
555 MachineBasicBlock
*DestB
,
557 // The values of DestA and DestB frequently come from a call to the
558 // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial
559 // values from there.
561 // 1. If both DestA and DestB are null, then the block ends with no branches
562 // (it falls through to its successor).
563 // 2. If DestA is set, DestB is null, and isCond is false, then the block ends
564 // with only an unconditional branch.
565 // 3. If DestA is set, DestB is null, and isCond is true, then the block ends
566 // with a conditional branch that falls through to a successor (DestB).
567 // 4. If DestA and DestB is set and isCond is true, then the block ends with a
568 // conditional branch followed by an unconditional branch. DestA is the
569 // 'true' destination and DestB is the 'false' destination.
571 bool Changed
= false;
573 MachineFunction::iterator FallThru
=
574 llvm::next(MachineFunction::iterator(this));
576 if (DestA
== 0 && DestB
== 0) {
577 // Block falls through to successor.
580 } else if (DestA
!= 0 && DestB
== 0) {
582 // Block ends in conditional jump that falls through to successor.
585 assert(DestA
&& DestB
&& isCond
&&
586 "CFG in a bad state. Cannot correct CFG edges");
589 // Remove superfluous edges. I.e., those which aren't destinations of this
590 // basic block, duplicate edges, or landing pads.
591 SmallPtrSet
<const MachineBasicBlock
*, 8> SeenMBBs
;
592 MachineBasicBlock::succ_iterator SI
= succ_begin();
593 while (SI
!= succ_end()) {
594 const MachineBasicBlock
*MBB
= *SI
;
595 if (!SeenMBBs
.insert(MBB
) ||
596 (MBB
!= DestA
&& MBB
!= DestB
&& !MBB
->isLandingPad())) {
597 // This is a superfluous edge, remove it.
598 SI
= removeSuccessor(SI
);
608 /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping
609 /// any DBG_VALUE instructions. Return UnknownLoc if there is none.
611 MachineBasicBlock::findDebugLoc(MachineBasicBlock::iterator
&MBBI
) {
613 MachineBasicBlock::iterator E
= end();
615 // Skip debug declarations, we don't want a DebugLoc from them.
616 MachineBasicBlock::iterator MBBI2
= MBBI
;
617 while (MBBI2
!= E
&& MBBI2
->isDebugValue())
620 DL
= MBBI2
->getDebugLoc();
625 void llvm::WriteAsOperand(raw_ostream
&OS
, const MachineBasicBlock
*MBB
,
627 OS
<< "BB#" << MBB
->getNumber();