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