LLVM API Documentation

MachineBasicBlock.cpp

Go to the documentation of this file.
00001 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Collect the sequence of machine instructions for a basic block.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/CodeGen/MachineBasicBlock.h"
00015 #include "llvm/BasicBlock.h"
00016 #include "llvm/CodeGen/MachineFunction.h"
00017 #include "llvm/Target/TargetRegisterInfo.h"
00018 #include "llvm/Target/TargetData.h"
00019 #include "llvm/Target/TargetInstrDesc.h"
00020 #include "llvm/Target/TargetMachine.h"
00021 #include "llvm/Support/LeakDetector.h"
00022 #include "llvm/Support/raw_ostream.h"
00023 #include <algorithm>
00024 using namespace llvm;
00025 
00026 MachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb)
00027   : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false) {
00028   Insts.Parent = this;
00029 }
00030 
00031 MachineBasicBlock::~MachineBasicBlock() {
00032   LeakDetector::removeGarbageObject(this);
00033 }
00034 
00035 std::ostream& llvm::operator<<(std::ostream &OS, const MachineBasicBlock &MBB) {
00036   MBB.print(OS);
00037   return OS;
00038 }
00039 raw_ostream& llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) {
00040   MBB.print(OS);
00041   return OS;
00042 }
00043 
00044 /// addNodeToList (MBB) - When an MBB is added to an MF, we need to update the 
00045 /// parent pointer of the MBB, the MBB numbering, and any instructions in the
00046 /// MBB to be on the right operand list for registers.
00047 ///
00048 /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
00049 /// gets the next available unique MBB number. If it is removed from a
00050 /// MachineFunction, it goes back to being #-1.
00051 void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock* N) {
00052   MachineFunction &MF = *N->getParent();
00053   N->Number = MF.addToMBBNumbering(N);
00054 
00055   // Make sure the instructions have their operands in the reginfo lists.
00056   MachineRegisterInfo &RegInfo = MF.getRegInfo();
00057   for (MachineBasicBlock::iterator I = N->begin(), E = N->end(); I != E; ++I)
00058     I->AddRegOperandsToUseLists(RegInfo);
00059 
00060   LeakDetector::removeGarbageObject(N);
00061 }
00062 
00063 void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock* N) {
00064   N->getParent()->removeFromMBBNumbering(N->Number);
00065   N->Number = -1;
00066   LeakDetector::addGarbageObject(N);
00067 }
00068 
00069 
00070 /// addNodeToList (MI) - When we add an instruction to a basic block
00071 /// list, we update its parent pointer and add its operands from reg use/def
00072 /// lists if appropriate.
00073 void ilist_traits<MachineInstr>::addNodeToList(MachineInstr* N) {
00074   assert(N->getParent() == 0 && "machine instruction already in a basic block");
00075   N->setParent(Parent);
00076   
00077   // Add the instruction's register operands to their corresponding
00078   // use/def lists.
00079   MachineFunction *MF = Parent->getParent();
00080   N->AddRegOperandsToUseLists(MF->getRegInfo());
00081 
00082   LeakDetector::removeGarbageObject(N);
00083 }
00084 
00085 /// removeNodeFromList (MI) - When we remove an instruction from a basic block
00086 /// list, we update its parent pointer and remove its operands from reg use/def
00087 /// lists if appropriate.
00088 void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr* N) {
00089   assert(N->getParent() != 0 && "machine instruction not in a basic block");
00090 
00091   // Remove from the use/def lists.
00092   N->RemoveRegOperandsFromUseLists();
00093   
00094   N->setParent(0);
00095 
00096   LeakDetector::addGarbageObject(N);
00097 }
00098 
00099 /// transferNodesFromList (MI) - When moving a range of instructions from one
00100 /// MBB list to another, we need to update the parent pointers and the use/def
00101 /// lists.
00102 void ilist_traits<MachineInstr>::transferNodesFromList(
00103       ilist_traits<MachineInstr>& fromList,
00104       MachineBasicBlock::iterator first,
00105       MachineBasicBlock::iterator last) {
00106   assert(Parent->getParent() == fromList.Parent->getParent() &&
00107         "MachineInstr parent mismatch!");
00108 
00109   // Splice within the same MBB -> no change.
00110   if (Parent == fromList.Parent) return;
00111 
00112   // If splicing between two blocks within the same function, just update the
00113   // parent pointers.
00114   for (; first != last; ++first)
00115     first->setParent(Parent);
00116 }
00117 
00118 void ilist_traits<MachineInstr>::deleteNode(MachineInstr* MI) {
00119   assert(!MI->getParent() && "MI is still in a block!");
00120   Parent->getParent()->DeleteMachineInstr(MI);
00121 }
00122 
00123 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
00124   iterator I = end();
00125   while (I != begin() && (--I)->getDesc().isTerminator())
00126     ; /*noop */
00127   if (I != end() && !I->getDesc().isTerminator()) ++I;
00128   return I;
00129 }
00130 
00131 /// isOnlyReachableViaFallthough - Return true if this basic block has
00132 /// exactly one predecessor and the control transfer mechanism between
00133 /// the predecessor and this block is a fall-through.
00134 bool MachineBasicBlock::isOnlyReachableByFallthrough() const {
00135   // If this is a landing pad, it isn't a fall through.  If it has no preds,
00136   // then nothing falls through to it.
00137   if (isLandingPad() || pred_empty())
00138     return false;
00139   
00140   // If there isn't exactly one predecessor, it can't be a fall through.
00141   const_pred_iterator PI = pred_begin(), PI2 = PI;
00142   ++PI2;
00143   if (PI2 != pred_end())
00144     return false;
00145   
00146   // The predecessor has to be immediately before this block.
00147   const MachineBasicBlock *Pred = *PI;
00148   
00149   if (!Pred->isLayoutSuccessor(this))
00150     return false;
00151   
00152   // If the block is completely empty, then it definitely does fall through.
00153   if (Pred->empty())
00154     return true;
00155   
00156   // Otherwise, check the last instruction.
00157   const MachineInstr &LastInst = Pred->back();
00158   return !LastInst.getDesc().isBarrier();
00159 }
00160 
00161 void MachineBasicBlock::dump() const {
00162   print(*cerr.stream());
00163 }
00164 
00165 static inline void OutputReg(raw_ostream &os, unsigned RegNo,
00166                              const TargetRegisterInfo *TRI = 0) {
00167   if (!RegNo || TargetRegisterInfo::isPhysicalRegister(RegNo)) {
00168     if (TRI)
00169       os << " %" << TRI->get(RegNo).Name;
00170     else
00171       os << " %mreg(" << RegNo << ")";
00172   } else
00173     os << " %reg" << RegNo;
00174 }
00175 
00176 void MachineBasicBlock::print(std::ostream &OS,
00177                               const PrefixPrinter &prefix) const {
00178   raw_os_ostream RawOS(OS);
00179   print(RawOS, prefix);
00180 }
00181 
00182 void MachineBasicBlock::print(raw_ostream &OS,
00183                               const PrefixPrinter &prefix) const {
00184   const MachineFunction *MF = getParent();
00185   if(!MF) {
00186     OS << "Can't print out MachineBasicBlock because parent MachineFunction"
00187        << " is null\n";
00188     return;
00189   }
00190 
00191   const BasicBlock *LBB = getBasicBlock();
00192   OS << "\n";
00193   if (LBB) OS << LBB->getName() << ": ";
00194   OS << (const void*)this
00195      << ", LLVM BB @" << (const void*) LBB << ", ID#" << getNumber();
00196   if (Alignment) OS << ", Alignment " << Alignment;
00197   if (isLandingPad()) OS << ", EH LANDING PAD";
00198   OS << ":\n";
00199 
00200   const TargetRegisterInfo *TRI = MF->getTarget().getRegisterInfo();  
00201   if (!livein_empty()) {
00202     OS << "Live Ins:";
00203     for (const_livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I)
00204       OutputReg(OS, *I, TRI);
00205     OS << "\n";
00206   }
00207   // Print the preds of this block according to the CFG.
00208   if (!pred_empty()) {
00209     OS << "    Predecessors according to CFG:";
00210     for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI)
00211       OS << " " << *PI << " (#" << (*PI)->getNumber() << ")";
00212     OS << "\n";
00213   }
00214   
00215   for (const_iterator I = begin(); I != end(); ++I) {
00216     prefix(OS, *I) << "\t";
00217     I->print(OS, &getParent()->getTarget());
00218   }
00219 
00220   // Print the successors of this block according to the CFG.
00221   if (!succ_empty()) {
00222     OS << "    Successors according to CFG:";
00223     for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI)
00224       OS << " " << *SI << " (#" << (*SI)->getNumber() << ")";
00225     OS << "\n";
00226   }
00227 }
00228 
00229 void MachineBasicBlock::removeLiveIn(unsigned Reg) {
00230   livein_iterator I = std::find(livein_begin(), livein_end(), Reg);
00231   assert(I != livein_end() && "Not a live in!");
00232   LiveIns.erase(I);
00233 }
00234 
00235 bool MachineBasicBlock::isLiveIn(unsigned Reg) const {
00236   const_livein_iterator I = std::find(livein_begin(), livein_end(), Reg);
00237   return I != livein_end();
00238 }
00239 
00240 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
00241   getParent()->splice(NewAfter, this);
00242 }
00243 
00244 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
00245   MachineFunction::iterator BBI = NewBefore;
00246   getParent()->splice(++BBI, this);
00247 }
00248 
00249 
00250 void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ) {
00251   Successors.push_back(succ);
00252   succ->addPredecessor(this);
00253 }
00254 
00255 void MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) {
00256   succ->removePredecessor(this);
00257   succ_iterator I = std::find(Successors.begin(), Successors.end(), succ);
00258   assert(I != Successors.end() && "Not a current successor!");
00259   Successors.erase(I);
00260 }
00261 
00262 MachineBasicBlock::succ_iterator 
00263 MachineBasicBlock::removeSuccessor(succ_iterator I) {
00264   assert(I != Successors.end() && "Not a current successor!");
00265   (*I)->removePredecessor(this);
00266   return Successors.erase(I);
00267 }
00268 
00269 void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) {
00270   Predecessors.push_back(pred);
00271 }
00272 
00273 void MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) {
00274   std::vector<MachineBasicBlock *>::iterator I =
00275     std::find(Predecessors.begin(), Predecessors.end(), pred);
00276   assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
00277   Predecessors.erase(I);
00278 }
00279 
00280 void MachineBasicBlock::transferSuccessors(MachineBasicBlock *fromMBB)
00281 {
00282   if (this == fromMBB)
00283     return;
00284   
00285   for(MachineBasicBlock::succ_iterator iter = fromMBB->succ_begin(), 
00286       end = fromMBB->succ_end(); iter != end; ++iter) {
00287       addSuccessor(*iter);
00288   }
00289   while(!fromMBB->succ_empty())
00290     fromMBB->removeSuccessor(fromMBB->succ_begin());
00291 }
00292 
00293 bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const {
00294   std::vector<MachineBasicBlock *>::const_iterator I =
00295     std::find(Successors.begin(), Successors.end(), MBB);
00296   return I != Successors.end();
00297 }
00298 
00299 bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const {
00300   MachineFunction::const_iterator I(this);
00301   return next(I) == MachineFunction::const_iterator(MBB);
00302 }
00303 
00304 /// removeFromParent - This method unlinks 'this' from the containing function,
00305 /// and returns it, but does not delete it.
00306 MachineBasicBlock *MachineBasicBlock::removeFromParent() {
00307   assert(getParent() && "Not embedded in a function!");
00308   getParent()->remove(this);
00309   return this;
00310 }
00311 
00312 
00313 /// eraseFromParent - This method unlinks 'this' from the containing function,
00314 /// and deletes it.
00315 void MachineBasicBlock::eraseFromParent() {
00316   assert(getParent() && "Not embedded in a function!");
00317   getParent()->erase(this);
00318 }
00319 
00320 
00321 /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to
00322 /// 'Old', change the code and CFG so that it branches to 'New' instead.
00323 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
00324                                                MachineBasicBlock *New) {
00325   assert(Old != New && "Cannot replace self with self!");
00326 
00327   MachineBasicBlock::iterator I = end();
00328   while (I != begin()) {
00329     --I;
00330     if (!I->getDesc().isTerminator()) break;
00331 
00332     // Scan the operands of this machine instruction, replacing any uses of Old
00333     // with New.
00334     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
00335       if (I->getOperand(i).isMBB() &&
00336           I->getOperand(i).getMBB() == Old)
00337         I->getOperand(i).setMBB(New);
00338   }
00339 
00340   // Update the successor information.
00341   removeSuccessor(Old);
00342   addSuccessor(New);
00343 }
00344 
00345 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the
00346 /// CFG to be inserted.  If we have proven that MBB can only branch to DestA and
00347 /// DestB, remove any other MBB successors from the CFG.  DestA and DestB can
00348 /// be null.
00349 /// Besides DestA and DestB, retain other edges leading to LandingPads
00350 /// (currently there can be only one; we don't check or require that here).
00351 /// Note it is possible that DestA and/or DestB are LandingPads.
00352 bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA,
00353                                              MachineBasicBlock *DestB,
00354                                              bool isCond) {
00355   bool MadeChange = false;
00356   bool AddedFallThrough = false;
00357 
00358   MachineFunction::iterator FallThru = next(MachineFunction::iterator(this));
00359   
00360   // If this block ends with a conditional branch that falls through to its
00361   // successor, set DestB as the successor.
00362   if (isCond) {
00363     if (DestB == 0 && FallThru != getParent()->end()) {
00364       DestB = FallThru;
00365       AddedFallThrough = true;
00366     }
00367   } else {
00368     // If this is an unconditional branch with no explicit dest, it must just be
00369     // a fallthrough into DestB.
00370     if (DestA == 0 && FallThru != getParent()->end()) {
00371       DestA = FallThru;
00372       AddedFallThrough = true;
00373     }
00374   }
00375   
00376   MachineBasicBlock::succ_iterator SI = succ_begin();
00377   MachineBasicBlock *OrigDestA = DestA, *OrigDestB = DestB;
00378   while (SI != succ_end()) {
00379     if (*SI == DestA && DestA == DestB) {
00380       DestA = DestB = 0;
00381       ++SI;
00382     } else if (*SI == DestA) {
00383       DestA = 0;
00384       ++SI;
00385     } else if (*SI == DestB) {
00386       DestB = 0;
00387       ++SI;
00388     } else if ((*SI)->isLandingPad() && 
00389                *SI!=OrigDestA && *SI!=OrigDestB) {
00390       ++SI;
00391     } else {
00392       // Otherwise, this is a superfluous edge, remove it.
00393       SI = removeSuccessor(SI);
00394       MadeChange = true;
00395     }
00396   }
00397   if (!AddedFallThrough) {
00398     assert(DestA == 0 && DestB == 0 &&
00399            "MachineCFG is missing edges!");
00400   } else if (isCond) {
00401     assert(DestA == 0 && "MachineCFG is missing edges!");
00402   }
00403   return MadeChange;
00404 }