1 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source 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/MachineFunction.h"
17 #include "llvm/CodeGen/MachineInstr.h"
18 #include "llvm/Target/MRegisterInfo.h"
19 #include "llvm/Target/TargetData.h"
20 #include "llvm/Target/TargetInstrInfo.h"
21 #include "llvm/Target/TargetMachine.h"
22 #include "llvm/Support/LeakDetector.h"
26 MachineBasicBlock::~MachineBasicBlock() {
27 LeakDetector::removeGarbageObject(this);
30 std::ostream& llvm::operator<<(std::ostream &OS, const MachineBasicBlock &MBB) {
35 // MBBs start out as #-1. When a MBB is added to a MachineFunction, it
36 // gets the next available unique MBB number. If it is removed from a
37 // MachineFunction, it goes back to being #-1.
38 void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock* N) {
39 assert(N->Parent == 0 && "machine instruction already in a basic block");
41 N->Number = Parent->addToMBBNumbering(N);
42 LeakDetector::removeGarbageObject(N);
45 void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock* N) {
46 assert(N->Parent != 0 && "machine instruction not in a basic block");
47 N->Parent->removeFromMBBNumbering(N->Number);
50 LeakDetector::addGarbageObject(N);
54 MachineInstr* ilist_traits<MachineInstr>::createSentinel() {
55 MachineInstr* dummy = new MachineInstr();
56 LeakDetector::removeGarbageObject(dummy);
60 void ilist_traits<MachineInstr>::addNodeToList(MachineInstr* N) {
61 assert(N->parent == 0 && "machine instruction already in a basic block");
63 LeakDetector::removeGarbageObject(N);
66 void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr* N) {
67 assert(N->parent != 0 && "machine instruction not in a basic block");
69 LeakDetector::addGarbageObject(N);
72 void ilist_traits<MachineInstr>::transferNodesFromList(
73 iplist<MachineInstr, ilist_traits<MachineInstr> >& fromList,
74 ilist_iterator<MachineInstr> first,
75 ilist_iterator<MachineInstr> last) {
76 if (parent != fromList.parent)
77 for (; first != last; ++first)
78 first->parent = parent;
81 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
82 const TargetInstrInfo& TII = *getParent()->getTarget().getInstrInfo();
84 while (I != begin() && TII.isTerminatorInstr((--I)->getOpcode()))
86 if (I != end() && !TII.isTerminatorInstr(I->getOpcode())) ++I;
90 void MachineBasicBlock::dump() const {
91 print(*cerr.stream());
94 static inline void OutputReg(std::ostream &os, unsigned RegNo,
95 const MRegisterInfo *MRI = 0) {
96 if (!RegNo || MRegisterInfo::isPhysicalRegister(RegNo)) {
98 os << " %" << MRI->get(RegNo).Name;
100 os << " %mreg(" << RegNo << ")";
102 os << " %reg" << RegNo;
105 void MachineBasicBlock::print(std::ostream &OS) const {
106 const MachineFunction *MF = getParent();
108 OS << "Can't print out MachineBasicBlock because parent MachineFunction"
113 const BasicBlock *LBB = getBasicBlock();
115 if (LBB) OS << LBB->getName() << ": ";
116 OS << (const void*)this
117 << ", LLVM BB @" << (const void*) LBB << ", ID#" << getNumber();
118 if (isLandingPad()) OS << ", EH LANDING PAD";
121 const MRegisterInfo *MRI = MF->getTarget().getRegisterInfo();
122 if (livein_begin() != livein_end()) {
124 for (const_livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I)
125 OutputReg(OS, *I, MRI);
128 // Print the preds of this block according to the CFG.
130 OS << " Predecessors according to CFG:";
131 for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI)
132 OS << " " << *PI << " (#" << (*PI)->getNumber() << ")";
136 for (const_iterator I = begin(); I != end(); ++I) {
138 I->print(OS, &getParent()->getTarget());
141 // Print the successors of this block according to the CFG.
143 OS << " Successors according to CFG:";
144 for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI)
145 OS << " " << *SI << " (#" << (*SI)->getNumber() << ")";
150 void MachineBasicBlock::removeLiveIn(unsigned Reg) {
151 livein_iterator I = std::find(livein_begin(), livein_end(), Reg);
152 assert(I != livein_end() && "Not a live in!");
156 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
157 MachineFunction::BasicBlockListType &BBList =getParent()->getBasicBlockList();
158 getParent()->getBasicBlockList().splice(NewAfter, BBList, this);
161 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
162 MachineFunction::BasicBlockListType &BBList =getParent()->getBasicBlockList();
163 MachineFunction::iterator BBI = NewBefore;
164 getParent()->getBasicBlockList().splice(++BBI, BBList, this);
168 void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ) {
169 Successors.push_back(succ);
170 succ->addPredecessor(this);
173 void MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) {
174 succ->removePredecessor(this);
175 succ_iterator I = std::find(Successors.begin(), Successors.end(), succ);
176 assert(I != Successors.end() && "Not a current successor!");
180 MachineBasicBlock::succ_iterator MachineBasicBlock::removeSuccessor(succ_iterator I) {
181 assert(I != Successors.end() && "Not a current successor!");
182 (*I)->removePredecessor(this);
183 return(Successors.erase(I));
186 void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) {
187 Predecessors.push_back(pred);
190 void MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) {
191 std::vector<MachineBasicBlock *>::iterator I =
192 std::find(Predecessors.begin(), Predecessors.end(), pred);
193 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
194 Predecessors.erase(I);
197 bool MachineBasicBlock::isSuccessor(MachineBasicBlock *MBB) const {
198 std::vector<MachineBasicBlock *>::const_iterator I =
199 std::find(Successors.begin(), Successors.end(), MBB);
200 return I != Successors.end();
203 /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to
204 /// 'Old', change the code and CFG so that it branches to 'New' instead.
205 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
206 MachineBasicBlock *New) {
207 assert(Old != New && "Cannot replace self with self!");
209 MachineBasicBlock::iterator I = end();
210 while (I != begin()) {
212 if (!(I->getInstrDescriptor()->Flags & M_TERMINATOR_FLAG)) break;
214 // Scan the operands of this machine instruction, replacing any uses of Old
216 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
217 if (I->getOperand(i).isMachineBasicBlock() &&
218 I->getOperand(i).getMachineBasicBlock() == Old)
219 I->getOperand(i).setMachineBasicBlock(New);
222 // Update the successor information. If New was already a successor, just
223 // remove the link to Old instead of creating another one. PR 1444.
224 removeSuccessor(Old);
225 if (!isSuccessor(New))
229 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the
230 /// CFG to be inserted. If we have proven that MBB can only branch to DestA and
231 /// DestB, remove any other MBB successors from the CFG. DestA and DestB can
233 /// Besides DestA and DestB, retain other edges leading to LandingPads (currently
234 /// there can be only one; we don't check or require that here).
235 /// Note it is possible that DestA and/or DestB are LandingPads.
236 bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA,
237 MachineBasicBlock *DestB,
239 bool MadeChange = false;
240 bool AddedFallThrough = false;
242 MachineBasicBlock *FallThru = getNext();
244 // If this block ends with a conditional branch that falls through to its
245 // successor, set DestB as the successor.
247 if (DestB == 0 && FallThru != getParent()->end()) {
249 AddedFallThrough = true;
252 // If this is an unconditional branch with no explicit dest, it must just be
253 // a fallthrough into DestB.
254 if (DestA == 0 && FallThru != getParent()->end()) {
256 AddedFallThrough = true;
260 MachineBasicBlock::succ_iterator SI = succ_begin();
261 MachineBasicBlock *OrigDestA = DestA, *OrigDestB = DestB;
262 while (SI != succ_end()) {
263 if (*SI == DestA && DestA == DestB) {
266 } else if (*SI == DestA) {
269 } else if (*SI == DestB) {
272 } else if ((*SI)->isLandingPad() &&
273 *SI!=OrigDestA && *SI!=OrigDestB) {
276 // Otherwise, this is a superfluous edge, remove it.
277 SI = removeSuccessor(SI);
281 if (!AddedFallThrough) {
282 assert(DestA == 0 && DestB == 0 &&
283 "MachineCFG is missing edges!");
285 assert(DestA == 0 && "MachineCFG is missing edges!");