MachineBasicBlock.cpp revision b528d7627c5aa90478e8ae756fabc1d2a61f79d9
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/TargetRegisterInfo.h" 18#include "llvm/Target/TargetData.h" 19#include "llvm/Target/TargetInstrDesc.h" 20#include "llvm/Target/TargetMachine.h" 21#include "llvm/Support/LeakDetector.h" 22#include <algorithm> 23using namespace llvm; 24 25MachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb) 26 : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false) { 27 Insts.Parent = this; 28} 29 30MachineBasicBlock::~MachineBasicBlock() { 31 LeakDetector::removeGarbageObject(this); 32} 33 34std::ostream& llvm::operator<<(std::ostream &OS, const MachineBasicBlock &MBB) { 35 MBB.print(OS); 36 return OS; 37} 38 39/// addNodeToList (MBB) - When an MBB is added to an MF, we need to update the 40/// parent pointer of the MBB, the MBB numbering, and any instructions in the 41/// MBB to be on the right operand list for registers. 42/// 43/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it 44/// gets the next available unique MBB number. If it is removed from a 45/// MachineFunction, it goes back to being #-1. 46void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock* N) { 47 MachineFunction &MF = *N->getParent(); 48 N->Number = MF.addToMBBNumbering(N); 49 50 // Make sure the instructions have their operands in the reginfo lists. 51 MachineRegisterInfo &RegInfo = MF.getRegInfo(); 52 for (MachineBasicBlock::iterator I = N->begin(), E = N->end(); I != E; ++I) 53 I->AddRegOperandsToUseLists(RegInfo); 54 55 LeakDetector::removeGarbageObject(N); 56} 57 58void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock* N) { 59 N->getParent()->removeFromMBBNumbering(N->Number); 60 N->Number = -1; 61 LeakDetector::addGarbageObject(N); 62} 63 64 65/// addNodeToList (MI) - When we add an instruction to a basic block 66/// list, we update its parent pointer and add its operands from reg use/def 67/// lists if appropriate. 68void ilist_traits<MachineInstr>::addNodeToList(MachineInstr* N) { 69 assert(N->getParent() == 0 && "machine instruction already in a basic block"); 70 N->setParent(Parent); 71 72 // Add the instruction's register operands to their corresponding 73 // use/def lists. 74 MachineFunction *MF = Parent->getParent(); 75 N->AddRegOperandsToUseLists(MF->getRegInfo()); 76 77 LeakDetector::removeGarbageObject(N); 78} 79 80/// removeNodeFromList (MI) - When we remove an instruction from a basic block 81/// list, we update its parent pointer and remove its operands from reg use/def 82/// lists if appropriate. 83void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr* N) { 84 assert(N->getParent() != 0 && "machine instruction not in a basic block"); 85 86 // Remove from the use/def lists. 87 N->RemoveRegOperandsFromUseLists(); 88 89 N->setParent(0); 90 91 LeakDetector::addGarbageObject(N); 92} 93 94/// transferNodesFromList (MI) - When moving a range of instructions from one 95/// MBB list to another, we need to update the parent pointers and the use/def 96/// lists. 97void ilist_traits<MachineInstr>::transferNodesFromList( 98 ilist_traits<MachineInstr>& fromList, 99 MachineBasicBlock::iterator first, 100 MachineBasicBlock::iterator last) { 101 assert(Parent->getParent() == fromList.Parent->getParent() && 102 "MachineInstr parent mismatch!"); 103 104 // Splice within the same MBB -> no change. 105 if (Parent == fromList.Parent) return; 106 107 // If splicing between two blocks within the same function, just update the 108 // parent pointers. 109 for (; first != last; ++first) 110 first->setParent(Parent); 111} 112 113void ilist_traits<MachineInstr>::deleteNode(MachineInstr* MI) { 114 assert(!MI->getParent() && "MI is still in a block!"); 115 Parent->getParent()->DeleteMachineInstr(MI); 116} 117 118MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { 119 iterator I = end(); 120 while (I != begin() && (--I)->getDesc().isTerminator()) 121 ; /*noop */ 122 if (I != end() && !I->getDesc().isTerminator()) ++I; 123 return I; 124} 125 126bool 127MachineBasicBlock::isOnlyReachableByFallthrough() const { 128 return !isLandingPad() && 129 !pred_empty() && 130 next(pred_begin()) == pred_end() && 131 (*pred_begin())->isLayoutSuccessor(this) && 132 ((*pred_begin())->empty() || 133 !(*pred_begin())->back().getDesc().isBarrier()); 134} 135 136void MachineBasicBlock::dump() const { 137 print(*cerr.stream()); 138} 139 140static inline void OutputReg(std::ostream &os, unsigned RegNo, 141 const TargetRegisterInfo *TRI = 0) { 142 if (!RegNo || TargetRegisterInfo::isPhysicalRegister(RegNo)) { 143 if (TRI) 144 os << " %" << TRI->get(RegNo).Name; 145 else 146 os << " %mreg(" << RegNo << ")"; 147 } else 148 os << " %reg" << RegNo; 149} 150 151void MachineBasicBlock::print(std::ostream &OS, 152 const PrefixPrinter &prefix) const { 153 const MachineFunction *MF = getParent(); 154 if(!MF) { 155 OS << "Can't print out MachineBasicBlock because parent MachineFunction" 156 << " is null\n"; 157 return; 158 } 159 160 const BasicBlock *LBB = getBasicBlock(); 161 OS << "\n"; 162 if (LBB) OS << LBB->getName() << ": "; 163 OS << (const void*)this 164 << ", LLVM BB @" << (const void*) LBB << ", ID#" << getNumber(); 165 if (Alignment) OS << ", Alignment " << Alignment; 166 if (isLandingPad()) OS << ", EH LANDING PAD"; 167 OS << ":\n"; 168 169 const TargetRegisterInfo *TRI = MF->getTarget().getRegisterInfo(); 170 if (!livein_empty()) { 171 OS << "Live Ins:"; 172 for (const_livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I) 173 OutputReg(OS, *I, TRI); 174 OS << "\n"; 175 } 176 // Print the preds of this block according to the CFG. 177 if (!pred_empty()) { 178 OS << " Predecessors according to CFG:"; 179 for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI) 180 OS << " " << *PI << " (#" << (*PI)->getNumber() << ")"; 181 OS << "\n"; 182 } 183 184 for (const_iterator I = begin(); I != end(); ++I) { 185 OS << prefix(*I); 186 OS << "\t"; 187 I->print(OS, &getParent()->getTarget()); 188 } 189 190 // Print the successors of this block according to the CFG. 191 if (!succ_empty()) { 192 OS << " Successors according to CFG:"; 193 for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) 194 OS << " " << *SI << " (#" << (*SI)->getNumber() << ")"; 195 OS << "\n"; 196 } 197} 198 199void MachineBasicBlock::removeLiveIn(unsigned Reg) { 200 livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 201 assert(I != livein_end() && "Not a live in!"); 202 LiveIns.erase(I); 203} 204 205bool MachineBasicBlock::isLiveIn(unsigned Reg) const { 206 const_livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 207 return I != livein_end(); 208} 209 210void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { 211 getParent()->splice(NewAfter, this); 212} 213 214void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { 215 MachineFunction::iterator BBI = NewBefore; 216 getParent()->splice(++BBI, this); 217} 218 219 220void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ) { 221 Successors.push_back(succ); 222 succ->addPredecessor(this); 223} 224 225void MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) { 226 succ->removePredecessor(this); 227 succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); 228 assert(I != Successors.end() && "Not a current successor!"); 229 Successors.erase(I); 230} 231 232MachineBasicBlock::succ_iterator 233MachineBasicBlock::removeSuccessor(succ_iterator I) { 234 assert(I != Successors.end() && "Not a current successor!"); 235 (*I)->removePredecessor(this); 236 return Successors.erase(I); 237} 238 239void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) { 240 Predecessors.push_back(pred); 241} 242 243void MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) { 244 std::vector<MachineBasicBlock *>::iterator I = 245 std::find(Predecessors.begin(), Predecessors.end(), pred); 246 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); 247 Predecessors.erase(I); 248} 249 250void MachineBasicBlock::transferSuccessors(MachineBasicBlock *fromMBB) 251{ 252 if (this == fromMBB) 253 return; 254 255 for(MachineBasicBlock::succ_iterator iter = fromMBB->succ_begin(), 256 end = fromMBB->succ_end(); iter != end; ++iter) { 257 addSuccessor(*iter); 258 } 259 while(!fromMBB->succ_empty()) 260 fromMBB->removeSuccessor(fromMBB->succ_begin()); 261} 262 263bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { 264 std::vector<MachineBasicBlock *>::const_iterator I = 265 std::find(Successors.begin(), Successors.end(), MBB); 266 return I != Successors.end(); 267} 268 269bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { 270 MachineFunction::const_iterator I(this); 271 return next(I) == MachineFunction::const_iterator(MBB); 272} 273 274/// removeFromParent - This method unlinks 'this' from the containing function, 275/// and returns it, but does not delete it. 276MachineBasicBlock *MachineBasicBlock::removeFromParent() { 277 assert(getParent() && "Not embedded in a function!"); 278 getParent()->remove(this); 279 return this; 280} 281 282 283/// eraseFromParent - This method unlinks 'this' from the containing function, 284/// and deletes it. 285void MachineBasicBlock::eraseFromParent() { 286 assert(getParent() && "Not embedded in a function!"); 287 getParent()->erase(this); 288} 289 290 291/// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 292/// 'Old', change the code and CFG so that it branches to 'New' instead. 293void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, 294 MachineBasicBlock *New) { 295 assert(Old != New && "Cannot replace self with self!"); 296 297 MachineBasicBlock::iterator I = end(); 298 while (I != begin()) { 299 --I; 300 if (!I->getDesc().isTerminator()) break; 301 302 // Scan the operands of this machine instruction, replacing any uses of Old 303 // with New. 304 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 305 if (I->getOperand(i).isMBB() && 306 I->getOperand(i).getMBB() == Old) 307 I->getOperand(i).setMBB(New); 308 } 309 310 // Update the successor information. 311 removeSuccessor(Old); 312 addSuccessor(New); 313} 314 315/// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the 316/// CFG to be inserted. If we have proven that MBB can only branch to DestA and 317/// DestB, remove any other MBB successors from the CFG. DestA and DestB can 318/// be null. 319/// Besides DestA and DestB, retain other edges leading to LandingPads 320/// (currently there can be only one; we don't check or require that here). 321/// Note it is possible that DestA and/or DestB are LandingPads. 322bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, 323 MachineBasicBlock *DestB, 324 bool isCond) { 325 bool MadeChange = false; 326 bool AddedFallThrough = false; 327 328 MachineFunction::iterator FallThru = next(MachineFunction::iterator(this)); 329 330 // If this block ends with a conditional branch that falls through to its 331 // successor, set DestB as the successor. 332 if (isCond) { 333 if (DestB == 0 && FallThru != getParent()->end()) { 334 DestB = FallThru; 335 AddedFallThrough = true; 336 } 337 } else { 338 // If this is an unconditional branch with no explicit dest, it must just be 339 // a fallthrough into DestB. 340 if (DestA == 0 && FallThru != getParent()->end()) { 341 DestA = FallThru; 342 AddedFallThrough = true; 343 } 344 } 345 346 MachineBasicBlock::succ_iterator SI = succ_begin(); 347 MachineBasicBlock *OrigDestA = DestA, *OrigDestB = DestB; 348 while (SI != succ_end()) { 349 if (*SI == DestA && DestA == DestB) { 350 DestA = DestB = 0; 351 ++SI; 352 } else if (*SI == DestA) { 353 DestA = 0; 354 ++SI; 355 } else if (*SI == DestB) { 356 DestB = 0; 357 ++SI; 358 } else if ((*SI)->isLandingPad() && 359 *SI!=OrigDestA && *SI!=OrigDestB) { 360 ++SI; 361 } else { 362 // Otherwise, this is a superfluous edge, remove it. 363 SI = removeSuccessor(SI); 364 MadeChange = true; 365 } 366 } 367 if (!AddedFallThrough) { 368 assert(DestA == 0 && DestB == 0 && 369 "MachineCFG is missing edges!"); 370 } else if (isCond) { 371 assert(DestA == 0 && "MachineCFG is missing edges!"); 372 } 373 return MadeChange; 374} 375