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