lib/CodeGen/MachineBasicBlock.cpp

   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/BasicBlock.h"
  16 #include "llvm/CodeGen/MachineFunction.h"
  17 #include "llvm/Target/MRegisterInfo.h"
  18 #include "llvm/Target/TargetData.h"
  19 #include "llvm/Target/TargetInstrInfo.h"
  20 #include "llvm/Target/TargetMachine.h"
  21 #include "llvm/Support/LeakDetector.h"
  22 #include <algorithm>
  23 using namespace llvm;
  24
  25 MachineBasicBlock::~MachineBasicBlock() {
  26   LeakDetector::removeGarbageObject(this);
  27 }
  28
  29 std::ostream& llvm::operator<<(std::ostream &OS, const MachineBasicBlock &MBB) {
  30   MBB.print(OS);
  31   return OS;
  32 }
  33
  34 // MBBs start out as #-1. When a MBB is added to a MachineFunction, it
  35 // gets the next available unique MBB number. If it is removed from a
  36 // MachineFunction, it goes back to being #-1.
  37 void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock* N) {
  38   assert(N->getParent() == 0 && "machine instruction already in a basic block");
  39   N->setParent(Parent);
  40   N->Number = Parent->addToMBBNumbering(N);
  41   LeakDetector::removeGarbageObject(N);
  42 }
  43
  44 void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock* N) {
  45   assert(N->getParent() != 0 && "machine instruction not in a basic block");
  46   N->getParent()->removeFromMBBNumbering(N->Number);
  47   N->Number = -1;
  48   N->setParent(0);
  49   LeakDetector::addGarbageObject(N);
  50 }
  51
  52
  53 MachineInstr* ilist_traits<MachineInstr>::createSentinel() {
  54   MachineInstr* dummy = new MachineInstr();
  55   LeakDetector::removeGarbageObject(dummy);
  56   return dummy;
  57 }
  58
  59 void ilist_traits<MachineInstr>::addNodeToList(MachineInstr* N) {
  60   assert(N->getParent() == 0 && "machine instruction already in a basic block");
  61   N->setParent(parent);
  62   LeakDetector::removeGarbageObject(N);
  63 }
  64
  65 void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr* N) {
  66   assert(N->getParent() != 0 && "machine instruction not in a basic block");
  67   N->setParent(0);
  68   LeakDetector::addGarbageObject(N);
  69 }
  70
  71 void ilist_traits<MachineInstr>::transferNodesFromList(
  72       iplist<MachineInstr, ilist_traits<MachineInstr> >& fromList,
  73       ilist_iterator<MachineInstr> first,
  74       ilist_iterator<MachineInstr> last) {
  75   // Splice within the same MBB -> no change.
  76   if (parent == fromList.parent) return;
  77
  78   for (; first != last; ++first)
  79     first->setParent(parent);
  80 }
  81
  82 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
  83   const TargetInstrInfo& TII = *getParent()->getTarget().getInstrInfo();
  84   iterator I = end();
  85   while (I != begin() && TII.isTerminatorInstr((--I)->getOpcode()))
  86     ; /*noop */
  87   if (I != end() && !TII.isTerminatorInstr(I->getOpcode())) ++I;
  88   return I;
  89 }
  90
  91 void MachineBasicBlock::dump() const {
  92   print(*cerr.stream());
  93 }
  94
  95 static inline void OutputReg(std::ostream &os, unsigned RegNo,
  96                              const MRegisterInfo *MRI = 0) {
  97   if (!RegNo || MRegisterInfo::isPhysicalRegister(RegNo)) {
  98     if (MRI)
  99       os << " %" << MRI->get(RegNo).Name;
 100     else
 101       os << " %mreg(" << RegNo << ")";
 102   } else
 103     os << " %reg" << RegNo;
 104 }
 105
 106 void MachineBasicBlock::print(std::ostream &OS) const {
 107   const MachineFunction *MF = getParent();
 108   if(!MF) {
 109     OS << "Can't print out MachineBasicBlock because parent MachineFunction"
 110        << " is null\n";
 111     return;
 112   }
 113
 114   const BasicBlock *LBB = getBasicBlock();
 115   OS << "\n";
 116   if (LBB) OS << LBB->getName() << ": ";
 117   OS << (const void*)this
 118      << ", LLVM BB @" << (const void*) LBB << ", ID#" << getNumber();
 119   if (isLandingPad()) OS << ", EH LANDING PAD";
 120   OS << ":\n";
 121
 122   const MRegisterInfo *MRI = MF->getTarget().getRegisterInfo();
 123   if (!livein_empty()) {
 124     OS << "Live Ins:";
 125     for (const_livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I)
 126       OutputReg(OS, *I, MRI);
 127     OS << "\n";
 128   }
 129   // Print the preds of this block according to the CFG.
 130   if (!pred_empty()) {
 131     OS << "    Predecessors according to CFG:";
 132     for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI)
 133       OS << " " << *PI << " (#" << (*PI)->getNumber() << ")";
 134     OS << "\n";
 135   }
 136
 137   for (const_iterator I = begin(); I != end(); ++I) {
 138     OS << "\t";
 139     I->print(OS, &getParent()->getTarget());
 140   }
 141
 142   // Print the successors of this block according to the CFG.
 143   if (!succ_empty()) {
 144     OS << "    Successors according to CFG:";
 145     for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI)
 146       OS << " " << *SI << " (#" << (*SI)->getNumber() << ")";
 147     OS << "\n";
 148   }
 149 }
 150
 151 void MachineBasicBlock::removeLiveIn(unsigned Reg) {
 152   livein_iterator I = std::find(livein_begin(), livein_end(), Reg);
 153   assert(I != livein_end() && "Not a live in!");
 154   LiveIns.erase(I);
 155 }
 156
 157 void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
 158   MachineFunction::BasicBlockListType &BBList =getParent()->getBasicBlockList();
 159   getParent()->getBasicBlockList().splice(NewAfter, BBList, this);
 160 }
 161
 162 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
 163   MachineFunction::BasicBlockListType &BBList =getParent()->getBasicBlockList();
 164   MachineFunction::iterator BBI = NewBefore;
 165   getParent()->getBasicBlockList().splice(++BBI, BBList, this);
 166 }
 167
 168
 169 void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ) {
 170   Successors.push_back(succ);
 171   succ->addPredecessor(this);
 172 }
 173
 174 void MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) {
 175   succ->removePredecessor(this);
 176   succ_iterator I = std::find(Successors.begin(), Successors.end(), succ);
 177   assert(I != Successors.end() && "Not a current successor!");
 178   Successors.erase(I);
 179 }
 180
 181 MachineBasicBlock::succ_iterator
 182 MachineBasicBlock::removeSuccessor(succ_iterator I) {
 183   assert(I != Successors.end() && "Not a current successor!");
 184   (*I)->removePredecessor(this);
 185   return(Successors.erase(I));
 186 }
 187
 188 void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) {
 189   Predecessors.push_back(pred);
 190 }
 191
 192 void MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) {
 193   std::vector<MachineBasicBlock *>::iterator I =
 194     std::find(Predecessors.begin(), Predecessors.end(), pred);
 195   assert(I != Predecessors.end() && "Pred is not a predecessor of this block!");
 196   Predecessors.erase(I);
 197 }
 198
 199 bool MachineBasicBlock::isSuccessor(MachineBasicBlock *MBB) const {
 200   std::vector<MachineBasicBlock *>::const_iterator I =
 201     std::find(Successors.begin(), Successors.end(), MBB);
 202   return I != Successors.end();
 203 }
 204
 205 /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to
 206 /// 'Old', change the code and CFG so that it branches to 'New' instead.
 207 void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old,
 208                                                MachineBasicBlock *New) {
 209   assert(Old != New && "Cannot replace self with self!");
 210
 211   MachineBasicBlock::iterator I = end();
 212   while (I != begin()) {
 213     --I;
 214     if (!(I->getInstrDescriptor()->Flags & M_TERMINATOR_FLAG)) break;
 215
 216     // Scan the operands of this machine instruction, replacing any uses of Old
 217     // with New.
 218     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 219       if (I->getOperand(i).isMBB() && I->getOperand(i).getMBB() == Old)
 220         I->getOperand(i).setMBB(New);
 221   }
 222
 223   // Update the successor information.  If New was already a successor, just
 224   // remove the link to Old instead of creating another one.  PR 1444.
 225   removeSuccessor(Old);
 226   if (!isSuccessor(New))
 227     addSuccessor(New);
 228 }
 229
 230 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the
 231 /// CFG to be inserted.  If we have proven that MBB can only branch to DestA and
 232 /// DestB, remove any other MBB successors from the CFG.  DestA and DestB can
 233 /// be null.
 234 /// Besides DestA and DestB, retain other edges leading to LandingPads
 235 /// (currently there can be only one; we don't check or require that here).
 236 /// Note it is possible that DestA and/or DestB are LandingPads.
 237 bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA,
 238                                              MachineBasicBlock *DestB,
 239                                              bool isCond) {
 240   bool MadeChange = false;
 241   bool AddedFallThrough = false;
 242
 243   MachineBasicBlock *FallThru = getNext();
 244
 245   // If this block ends with a conditional branch that falls through to its
 246   // successor, set DestB as the successor.
 247   if (isCond) {
 248     if (DestB == 0 && FallThru != getParent()->end()) {
 249       DestB = FallThru;
 250       AddedFallThrough = true;
 251     }
 252   } else {
 253     // If this is an unconditional branch with no explicit dest, it must just be
 254     // a fallthrough into DestB.
 255     if (DestA == 0 && FallThru != getParent()->end()) {
 256       DestA = FallThru;
 257       AddedFallThrough = true;
 258     }
 259   }
 260
 261   MachineBasicBlock::succ_iterator SI = succ_begin();
 262   MachineBasicBlock *OrigDestA = DestA, *OrigDestB = DestB;
 263   while (SI != succ_end()) {
 264     if (*SI == DestA && DestA == DestB) {
 265       DestA = DestB = 0;
 266       ++SI;
 267     } else if (*SI == DestA) {
 268       DestA = 0;
 269       ++SI;
 270     } else if (*SI == DestB) {
 271       DestB = 0;
 272       ++SI;
 273     } else if ((*SI)->isLandingPad() &&
 274                *SI!=OrigDestA && *SI!=OrigDestB) {
 275       ++SI;
 276     } else {
 277       // Otherwise, this is a superfluous edge, remove it.
 278       SI = removeSuccessor(SI);
 279       MadeChange = true;
 280     }
 281   }
 282   if (!AddedFallThrough) {
 283     assert(DestA == 0 && DestB == 0 &&
 284            "MachineCFG is missing edges!");
 285   } else if (isCond) {
 286     assert(DestA == 0 && "MachineCFG is missing edges!");
 287   }
 288   return MadeChange;
 289 }