MachineBasicBlock.cpp revision 33cc8d6b55ca5e1275d0984860f5d4f36f84f356
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/TargetInstrInfo.h" 21#include "llvm/Target/TargetMachine.h" 22#include "llvm/Support/Debug.h" 23#include "llvm/Support/LeakDetector.h" 24#include "llvm/Support/raw_ostream.h" 25#include "llvm/Assembly/Writer.h" 26#include <algorithm> 27using namespace llvm; 28 29MachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb) 30 : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false), 31 AddressTaken(false) { 32 Insts.Parent = this; 33} 34 35MachineBasicBlock::~MachineBasicBlock() { 36 LeakDetector::removeGarbageObject(this); 37} 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(dbgs()); 163} 164 165static inline void OutputReg(raw_ostream &os, unsigned RegNo, 166 const TargetRegisterInfo *TRI = 0) { 167 if (RegNo != 0 && TargetRegisterInfo::isPhysicalRegister(RegNo)) { 168 if (TRI) 169 os << " %" << TRI->get(RegNo).Name; 170 else 171 os << " %physreg" << RegNo; 172 } else 173 os << " %reg" << RegNo; 174} 175 176StringRef MachineBasicBlock::getName() const { 177 if (const BasicBlock *LBB = getBasicBlock()) 178 return LBB->getName(); 179 else 180 return "(null)"; 181} 182 183void MachineBasicBlock::print(raw_ostream &OS) 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 if (Alignment) { OS << "Alignment " << Alignment << "\n"; } 192 193 OS << "BB#" << getNumber() << ": "; 194 195 const char *Comma = ""; 196 if (const BasicBlock *LBB = getBasicBlock()) { 197 OS << Comma << "derived from LLVM BB "; 198 WriteAsOperand(OS, LBB, /*PrintType=*/false); 199 Comma = ", "; 200 } 201 if (isLandingPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; } 202 if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; } 203 OS << '\n'; 204 205 const TargetRegisterInfo *TRI = MF->getTarget().getRegisterInfo(); 206 if (!livein_empty()) { 207 OS << " Live Ins:"; 208 for (const_livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I) 209 OutputReg(OS, *I, TRI); 210 OS << '\n'; 211 } 212 // Print the preds of this block according to the CFG. 213 if (!pred_empty()) { 214 OS << " Predecessors according to CFG:"; 215 for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI) 216 OS << " BB#" << (*PI)->getNumber(); 217 OS << '\n'; 218 } 219 220 for (const_iterator I = begin(); I != end(); ++I) { 221 OS << '\t'; 222 I->print(OS, &getParent()->getTarget()); 223 } 224 225 // Print the successors of this block according to the CFG. 226 if (!succ_empty()) { 227 OS << " Successors according to CFG:"; 228 for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) 229 OS << " BB#" << (*SI)->getNumber(); 230 OS << '\n'; 231 } 232} 233 234void MachineBasicBlock::removeLiveIn(unsigned Reg) { 235 livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 236 assert(I != livein_end() && "Not a live in!"); 237 LiveIns.erase(I); 238} 239 240bool MachineBasicBlock::isLiveIn(unsigned Reg) const { 241 const_livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 242 return I != livein_end(); 243} 244 245void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { 246 getParent()->splice(NewAfter, this); 247} 248 249void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { 250 MachineFunction::iterator BBI = NewBefore; 251 getParent()->splice(++BBI, this); 252} 253 254void MachineBasicBlock::updateTerminator() { 255 const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); 256 // A block with no successors has no concerns with fall-through edges. 257 if (this->succ_empty()) return; 258 259 MachineBasicBlock *TBB = 0, *FBB = 0; 260 SmallVector<MachineOperand, 4> Cond; 261 bool B = TII->AnalyzeBranch(*this, TBB, FBB, Cond); 262 (void) B; 263 assert(!B && "UpdateTerminators requires analyzable predecessors!"); 264 if (Cond.empty()) { 265 if (TBB) { 266 // The block has an unconditional branch. If its successor is now 267 // its layout successor, delete the branch. 268 if (isLayoutSuccessor(TBB)) 269 TII->RemoveBranch(*this); 270 } else { 271 // The block has an unconditional fallthrough. If its successor is not 272 // its layout successor, insert a branch. 273 TBB = *succ_begin(); 274 if (!isLayoutSuccessor(TBB)) 275 TII->InsertBranch(*this, TBB, 0, Cond); 276 } 277 } else { 278 if (FBB) { 279 // The block has a non-fallthrough conditional branch. If one of its 280 // successors is its layout successor, rewrite it to a fallthrough 281 // conditional branch. 282 if (isLayoutSuccessor(TBB)) { 283 if (TII->ReverseBranchCondition(Cond)) 284 return; 285 TII->RemoveBranch(*this); 286 TII->InsertBranch(*this, FBB, 0, Cond); 287 } else if (isLayoutSuccessor(FBB)) { 288 TII->RemoveBranch(*this); 289 TII->InsertBranch(*this, TBB, 0, Cond); 290 } 291 } else { 292 // The block has a fallthrough conditional branch. 293 MachineBasicBlock *MBBA = *succ_begin(); 294 MachineBasicBlock *MBBB = *llvm::next(succ_begin()); 295 if (MBBA == TBB) std::swap(MBBB, MBBA); 296 if (isLayoutSuccessor(TBB)) { 297 if (TII->ReverseBranchCondition(Cond)) { 298 // We can't reverse the condition, add an unconditional branch. 299 Cond.clear(); 300 TII->InsertBranch(*this, MBBA, 0, Cond); 301 return; 302 } 303 TII->RemoveBranch(*this); 304 TII->InsertBranch(*this, MBBA, 0, Cond); 305 } else if (!isLayoutSuccessor(MBBA)) { 306 TII->RemoveBranch(*this); 307 TII->InsertBranch(*this, TBB, MBBA, Cond); 308 } 309 } 310 } 311} 312 313void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ) { 314 Successors.push_back(succ); 315 succ->addPredecessor(this); 316} 317 318void MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) { 319 succ->removePredecessor(this); 320 succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); 321 assert(I != Successors.end() && "Not a current successor!"); 322 Successors.erase(I); 323} 324 325MachineBasicBlock::succ_iterator 326MachineBasicBlock::removeSuccessor(succ_iterator I) { 327 assert(I != Successors.end() && "Not a current successor!"); 328 (*I)->removePredecessor(this); 329 return Successors.erase(I); 330} 331 332void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) { 333 Predecessors.push_back(pred); 334} 335 336void MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) { 337 std::vector<MachineBasicBlock *>::iterator I = 338 std::find(Predecessors.begin(), Predecessors.end(), pred); 339 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); 340 Predecessors.erase(I); 341} 342 343void MachineBasicBlock::transferSuccessors(MachineBasicBlock *fromMBB) { 344 if (this == fromMBB) 345 return; 346 347 for (MachineBasicBlock::succ_iterator I = fromMBB->succ_begin(), 348 E = fromMBB->succ_end(); I != E; ++I) 349 addSuccessor(*I); 350 351 while (!fromMBB->succ_empty()) 352 fromMBB->removeSuccessor(fromMBB->succ_begin()); 353} 354 355bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { 356 std::vector<MachineBasicBlock *>::const_iterator I = 357 std::find(Successors.begin(), Successors.end(), MBB); 358 return I != Successors.end(); 359} 360 361bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { 362 MachineFunction::const_iterator I(this); 363 return llvm::next(I) == MachineFunction::const_iterator(MBB); 364} 365 366bool MachineBasicBlock::canFallThrough() { 367 MachineFunction::iterator Fallthrough = this; 368 ++Fallthrough; 369 // If FallthroughBlock is off the end of the function, it can't fall through. 370 if (Fallthrough == getParent()->end()) 371 return false; 372 373 // If FallthroughBlock isn't a successor, no fallthrough is possible. 374 if (!isSuccessor(Fallthrough)) 375 return false; 376 377 // Analyze the branches, if any, at the end of the block. 378 MachineBasicBlock *TBB = 0, *FBB = 0; 379 SmallVector<MachineOperand, 4> Cond; 380 const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); 381 if (TII->AnalyzeBranch(*this, TBB, FBB, Cond)) { 382 // If we couldn't analyze the branch, examine the last instruction. 383 // If the block doesn't end in a known control barrier, assume fallthrough 384 // is possible. The isPredicable check is needed because this code can be 385 // called during IfConversion, where an instruction which is normally a 386 // Barrier is predicated and thus no longer an actual control barrier. This 387 // is over-conservative though, because if an instruction isn't actually 388 // predicated we could still treat it like a barrier. 389 return empty() || !back().getDesc().isBarrier() || 390 back().getDesc().isPredicable(); 391 } 392 393 // If there is no branch, control always falls through. 394 if (TBB == 0) return true; 395 396 // If there is some explicit branch to the fallthrough block, it can obviously 397 // reach, even though the branch should get folded to fall through implicitly. 398 if (MachineFunction::iterator(TBB) == Fallthrough || 399 MachineFunction::iterator(FBB) == Fallthrough) 400 return true; 401 402 // If it's an unconditional branch to some block not the fall through, it 403 // doesn't fall through. 404 if (Cond.empty()) return false; 405 406 // Otherwise, if it is conditional and has no explicit false block, it falls 407 // through. 408 return FBB == 0; 409} 410 411/// removeFromParent - This method unlinks 'this' from the containing function, 412/// and returns it, but does not delete it. 413MachineBasicBlock *MachineBasicBlock::removeFromParent() { 414 assert(getParent() && "Not embedded in a function!"); 415 getParent()->remove(this); 416 return this; 417} 418 419 420/// eraseFromParent - This method unlinks 'this' from the containing function, 421/// and deletes it. 422void MachineBasicBlock::eraseFromParent() { 423 assert(getParent() && "Not embedded in a function!"); 424 getParent()->erase(this); 425} 426 427 428/// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 429/// 'Old', change the code and CFG so that it branches to 'New' instead. 430void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, 431 MachineBasicBlock *New) { 432 assert(Old != New && "Cannot replace self with self!"); 433 434 MachineBasicBlock::iterator I = end(); 435 while (I != begin()) { 436 --I; 437 if (!I->getDesc().isTerminator()) break; 438 439 // Scan the operands of this machine instruction, replacing any uses of Old 440 // with New. 441 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 442 if (I->getOperand(i).isMBB() && 443 I->getOperand(i).getMBB() == Old) 444 I->getOperand(i).setMBB(New); 445 } 446 447 // Update the successor information. 448 removeSuccessor(Old); 449 addSuccessor(New); 450} 451 452/// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the 453/// CFG to be inserted. If we have proven that MBB can only branch to DestA and 454/// DestB, remove any other MBB successors from the CFG. DestA and DestB can be 455/// null. 456/// 457/// Besides DestA and DestB, retain other edges leading to LandingPads 458/// (currently there can be only one; we don't check or require that here). 459/// Note it is possible that DestA and/or DestB are LandingPads. 460bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, 461 MachineBasicBlock *DestB, 462 bool isCond) { 463 // The values of DestA and DestB frequently come from a call to the 464 // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial 465 // values from there. 466 // 467 // 1. If both DestA and DestB are null, then the block ends with no branches 468 // (it falls through to its successor). 469 // 2. If DestA is set, DestB is null, and isCond is false, then the block ends 470 // with only an unconditional branch. 471 // 3. If DestA is set, DestB is null, and isCond is true, then the block ends 472 // with a conditional branch that falls through to a successor (DestB). 473 // 4. If DestA and DestB is set and isCond is true, then the block ends with a 474 // conditional branch followed by an unconditional branch. DestA is the 475 // 'true' destination and DestB is the 'false' destination. 476 477 bool MadeChange = false; 478 bool AddedFallThrough = false; 479 480 MachineFunction::iterator FallThru = 481 llvm::next(MachineFunction::iterator(this)); 482 483 if (isCond) { 484 // If this block ends with a conditional branch that falls through to its 485 // successor, set DestB as the successor. 486 if (DestB == 0 && FallThru != getParent()->end()) { 487 DestB = FallThru; 488 AddedFallThrough = true; 489 } 490 } else { 491 // If this is an unconditional branch with no explicit dest, it must just be 492 // a fallthrough into DestA. 493 if (DestA == 0 && FallThru != getParent()->end()) { 494 DestA = FallThru; 495 AddedFallThrough = true; 496 } 497 } 498 499 MachineBasicBlock::succ_iterator SI = succ_begin(); 500 MachineBasicBlock *OrigDestA = DestA, *OrigDestB = DestB; 501 while (SI != succ_end()) { 502 const MachineBasicBlock *MBB = *SI; 503 if (MBB == DestA) { 504 DestA = 0; 505 ++SI; 506 } else if (MBB == DestB) { 507 DestB = 0; 508 ++SI; 509 } else if (MBB->isLandingPad() && 510 MBB != OrigDestA && MBB != OrigDestB) { 511 ++SI; 512 } else { 513 // Otherwise, this is a superfluous edge, remove it. 514 SI = removeSuccessor(SI); 515 MadeChange = true; 516 } 517 } 518 519 if (!AddedFallThrough) 520 assert(DestA == 0 && DestB == 0 && "MachineCFG is missing edges!"); 521 else if (isCond) 522 assert(DestA == 0 && "MachineCFG is missing edges!"); 523 524 return MadeChange; 525} 526 527void llvm::WriteAsOperand(raw_ostream &OS, const MachineBasicBlock *MBB, 528 bool t) { 529 OS << "BB#" << MBB->getNumber(); 530} 531