MachineBasicBlock.cpp revision bc18967dc5cbda59461d704cc1543b4fbd57f592
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/LeakDetector.h" 23#include "llvm/Support/raw_ostream.h" 24#include "llvm/Assembly/Writer.h" 25#include <algorithm> 26using namespace llvm; 27 28MachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb) 29 : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false), 30 AddressTaken(false) { 31 Insts.Parent = this; 32} 33 34MachineBasicBlock::~MachineBasicBlock() { 35 LeakDetector::removeGarbageObject(this); 36} 37 38raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) { 39 MBB.print(OS); 40 return OS; 41} 42 43/// addNodeToList (MBB) - When an MBB is added to an MF, we need to update the 44/// parent pointer of the MBB, the MBB numbering, and any instructions in the 45/// MBB to be on the right operand list for registers. 46/// 47/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it 48/// gets the next available unique MBB number. If it is removed from a 49/// MachineFunction, it goes back to being #-1. 50void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock *N) { 51 MachineFunction &MF = *N->getParent(); 52 N->Number = MF.addToMBBNumbering(N); 53 54 // Make sure the instructions have their operands in the reginfo lists. 55 MachineRegisterInfo &RegInfo = MF.getRegInfo(); 56 for (MachineBasicBlock::iterator I = N->begin(), E = N->end(); I != E; ++I) 57 I->AddRegOperandsToUseLists(RegInfo); 58 59 LeakDetector::removeGarbageObject(N); 60} 61 62void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock *N) { 63 N->getParent()->removeFromMBBNumbering(N->Number); 64 N->Number = -1; 65 LeakDetector::addGarbageObject(N); 66} 67 68 69/// addNodeToList (MI) - When we add an instruction to a basic block 70/// list, we update its parent pointer and add its operands from reg use/def 71/// lists if appropriate. 72void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) { 73 assert(N->getParent() == 0 && "machine instruction already in a basic block"); 74 N->setParent(Parent); 75 76 // Add the instruction's register operands to their corresponding 77 // use/def lists. 78 MachineFunction *MF = Parent->getParent(); 79 N->AddRegOperandsToUseLists(MF->getRegInfo()); 80 81 LeakDetector::removeGarbageObject(N); 82} 83 84/// removeNodeFromList (MI) - When we remove an instruction from a basic block 85/// list, we update its parent pointer and remove its operands from reg use/def 86/// lists if appropriate. 87void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) { 88 assert(N->getParent() != 0 && "machine instruction not in a basic block"); 89 90 // Remove from the use/def lists. 91 N->RemoveRegOperandsFromUseLists(); 92 93 N->setParent(0); 94 95 LeakDetector::addGarbageObject(N); 96} 97 98/// transferNodesFromList (MI) - When moving a range of instructions from one 99/// MBB list to another, we need to update the parent pointers and the use/def 100/// lists. 101void ilist_traits<MachineInstr>:: 102transferNodesFromList(ilist_traits<MachineInstr> &fromList, 103 MachineBasicBlock::iterator first, 104 MachineBasicBlock::iterator last) { 105 assert(Parent->getParent() == fromList.Parent->getParent() && 106 "MachineInstr parent mismatch!"); 107 108 // Splice within the same MBB -> no change. 109 if (Parent == fromList.Parent) return; 110 111 // If splicing between two blocks within the same function, just update the 112 // parent pointers. 113 for (; first != last; ++first) 114 first->setParent(Parent); 115} 116 117void ilist_traits<MachineInstr>::deleteNode(MachineInstr* MI) { 118 assert(!MI->getParent() && "MI is still in a block!"); 119 Parent->getParent()->DeleteMachineInstr(MI); 120} 121 122MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { 123 iterator I = end(); 124 while (I != begin() && (--I)->getDesc().isTerminator()) 125 ; /*noop */ 126 if (I != end() && !I->getDesc().isTerminator()) ++I; 127 return I; 128} 129 130/// isOnlyReachableViaFallthough - Return true if this basic block has 131/// exactly one predecessor and the control transfer mechanism between 132/// the predecessor and this block is a fall-through. 133bool MachineBasicBlock::isOnlyReachableByFallthrough() const { 134 // If this is a landing pad, it isn't a fall through. If it has no preds, 135 // then nothing falls through to it. 136 if (isLandingPad() || pred_empty()) 137 return false; 138 139 // If there isn't exactly one predecessor, it can't be a fall through. 140 const_pred_iterator PI = pred_begin(), PI2 = PI; 141 ++PI2; 142 if (PI2 != pred_end()) 143 return false; 144 145 // The predecessor has to be immediately before this block. 146 const MachineBasicBlock *Pred = *PI; 147 148 if (!Pred->isLayoutSuccessor(this)) 149 return false; 150 151 // If the block is completely empty, then it definitely does fall through. 152 if (Pred->empty()) 153 return true; 154 155 // Otherwise, check the last instruction. 156 const MachineInstr &LastInst = Pred->back(); 157 return !LastInst.getDesc().isBarrier(); 158} 159 160void MachineBasicBlock::dump() const { 161 print(errs()); 162} 163 164static inline void OutputReg(raw_ostream &os, unsigned RegNo, 165 const TargetRegisterInfo *TRI = 0) { 166 if (RegNo != 0 && TargetRegisterInfo::isPhysicalRegister(RegNo)) { 167 if (TRI) 168 os << " %" << TRI->get(RegNo).Name; 169 else 170 os << " %physreg" << RegNo; 171 } else 172 os << " %reg" << RegNo; 173} 174 175StringRef MachineBasicBlock::getName() const { 176 if (const BasicBlock *LBB = getBasicBlock()) 177 return LBB->getName(); 178 else 179 return "(null)"; 180} 181 182void MachineBasicBlock::print(raw_ostream &OS) const { 183 const MachineFunction *MF = getParent(); 184 if (!MF) { 185 OS << "Can't print out MachineBasicBlock because parent MachineFunction" 186 << " is null\n"; 187 return; 188 } 189 190 if (Alignment) { OS << "Alignment " << Alignment << "\n"; } 191 192 OS << "BB#" << getNumber() << ": "; 193 194 const char *Comma = ""; 195 if (const BasicBlock *LBB = getBasicBlock()) { 196 OS << Comma << "derived from LLVM BB "; 197 WriteAsOperand(OS, LBB, /*PrintType=*/false); 198 Comma = ", "; 199 } 200 if (isLandingPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; } 201 if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; } 202 OS << '\n'; 203 204 const TargetRegisterInfo *TRI = MF->getTarget().getRegisterInfo(); 205 if (!livein_empty()) { 206 OS << " Live Ins:"; 207 for (const_livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I) 208 OutputReg(OS, *I, TRI); 209 OS << '\n'; 210 } 211 // Print the preds of this block according to the CFG. 212 if (!pred_empty()) { 213 OS << " Predecessors according to CFG:"; 214 for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI) 215 OS << " BB#" << (*PI)->getNumber(); 216 OS << '\n'; 217 } 218 219 for (const_iterator I = begin(); I != end(); ++I) { 220 OS << '\t'; 221 I->print(OS, &getParent()->getTarget()); 222 } 223 224 // Print the successors of this block according to the CFG. 225 if (!succ_empty()) { 226 OS << " Successors according to CFG:"; 227 for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) 228 OS << " BB#" << (*SI)->getNumber(); 229 OS << '\n'; 230 } 231} 232 233void MachineBasicBlock::removeLiveIn(unsigned Reg) { 234 livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 235 assert(I != livein_end() && "Not a live in!"); 236 LiveIns.erase(I); 237} 238 239bool MachineBasicBlock::isLiveIn(unsigned Reg) const { 240 const_livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 241 return I != livein_end(); 242} 243 244void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { 245 getParent()->splice(NewAfter, this); 246} 247 248void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { 249 MachineFunction::iterator BBI = NewBefore; 250 getParent()->splice(++BBI, this); 251} 252 253void MachineBasicBlock::updateTerminator() { 254 const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); 255 // A block with no successors has no concerns with fall-through edges. 256 if (this->succ_empty()) return; 257 258 MachineBasicBlock *TBB = 0, *FBB = 0; 259 SmallVector<MachineOperand, 4> Cond; 260 bool B = TII->AnalyzeBranch(*this, TBB, FBB, Cond); 261 (void) B; 262 assert(!B && "UpdateTerminators requires analyzable predecessors!"); 263 if (Cond.empty()) { 264 if (TBB) { 265 // The block has an unconditional branch. If its successor is now 266 // its layout successor, delete the branch. 267 if (isLayoutSuccessor(TBB)) 268 TII->RemoveBranch(*this); 269 } else { 270 // The block has an unconditional fallthrough. If its successor is not 271 // its layout successor, insert a branch. 272 TBB = *succ_begin(); 273 if (!isLayoutSuccessor(TBB)) 274 TII->InsertBranch(*this, TBB, 0, Cond); 275 } 276 } else { 277 if (FBB) { 278 // The block has a non-fallthrough conditional branch. If one of its 279 // successors is its layout successor, rewrite it to a fallthrough 280 // conditional branch. 281 if (isLayoutSuccessor(TBB)) { 282 if (TII->ReverseBranchCondition(Cond)) 283 return; 284 TII->RemoveBranch(*this); 285 TII->InsertBranch(*this, FBB, 0, Cond); 286 } else if (isLayoutSuccessor(FBB)) { 287 TII->RemoveBranch(*this); 288 TII->InsertBranch(*this, TBB, 0, Cond); 289 } 290 } else { 291 // The block has a fallthrough conditional branch. 292 MachineBasicBlock *MBBA = *succ_begin(); 293 MachineBasicBlock *MBBB = *llvm::next(succ_begin()); 294 if (MBBA == TBB) std::swap(MBBB, MBBA); 295 if (isLayoutSuccessor(TBB)) { 296 if (TII->ReverseBranchCondition(Cond)) { 297 // We can't reverse the condition, add an unconditional branch. 298 Cond.clear(); 299 TII->InsertBranch(*this, MBBA, 0, Cond); 300 return; 301 } 302 TII->RemoveBranch(*this); 303 TII->InsertBranch(*this, MBBA, 0, Cond); 304 } else if (!isLayoutSuccessor(MBBA)) { 305 TII->RemoveBranch(*this); 306 TII->InsertBranch(*this, TBB, MBBA, Cond); 307 } 308 } 309 } 310} 311 312void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ) { 313 Successors.push_back(succ); 314 succ->addPredecessor(this); 315} 316 317void MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) { 318 succ->removePredecessor(this); 319 succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); 320 assert(I != Successors.end() && "Not a current successor!"); 321 Successors.erase(I); 322} 323 324MachineBasicBlock::succ_iterator 325MachineBasicBlock::removeSuccessor(succ_iterator I) { 326 assert(I != Successors.end() && "Not a current successor!"); 327 (*I)->removePredecessor(this); 328 return Successors.erase(I); 329} 330 331void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) { 332 Predecessors.push_back(pred); 333} 334 335void MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) { 336 std::vector<MachineBasicBlock *>::iterator I = 337 std::find(Predecessors.begin(), Predecessors.end(), pred); 338 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); 339 Predecessors.erase(I); 340} 341 342void MachineBasicBlock::transferSuccessors(MachineBasicBlock *fromMBB) { 343 if (this == fromMBB) 344 return; 345 346 for (MachineBasicBlock::succ_iterator I = fromMBB->succ_begin(), 347 E = fromMBB->succ_end(); I != E; ++I) 348 addSuccessor(*I); 349 350 while (!fromMBB->succ_empty()) 351 fromMBB->removeSuccessor(fromMBB->succ_begin()); 352} 353 354bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { 355 std::vector<MachineBasicBlock *>::const_iterator I = 356 std::find(Successors.begin(), Successors.end(), MBB); 357 return I != Successors.end(); 358} 359 360bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { 361 MachineFunction::const_iterator I(this); 362 return llvm::next(I) == MachineFunction::const_iterator(MBB); 363} 364 365bool MachineBasicBlock::canFallThrough() { 366 MachineFunction::iterator Fallthrough = this; 367 ++Fallthrough; 368 // If FallthroughBlock is off the end of the function, it can't fall through. 369 if (Fallthrough == getParent()->end()) 370 return false; 371 372 // If FallthroughBlock isn't a successor, no fallthrough is possible. 373 if (!isSuccessor(Fallthrough)) 374 return false; 375 376 // Analyze the branches, if any, at the end of the block. 377 MachineBasicBlock *TBB = 0, *FBB = 0; 378 SmallVector<MachineOperand, 4> Cond; 379 const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); 380 if (TII->AnalyzeBranch(*this, TBB, FBB, Cond, true)) { 381 // If we couldn't analyze the branch, examine the last instruction. 382 // If the block doesn't end in a known control barrier, assume fallthrough 383 // is possible. The isPredicable check is needed because this code can be 384 // called during IfConversion, where an instruction which is normally a 385 // Barrier is predicated and thus no longer an actual control barrier. This 386 // is over-conservative though, because if an instruction isn't actually 387 // predicated we could still treat it like a barrier. 388 return empty() || !back().getDesc().isBarrier() || 389 back().getDesc().isPredicable(); 390 } 391 392 // If there is no branch, control always falls through. 393 if (TBB == 0) return true; 394 395 // If there is some explicit branch to the fallthrough block, it can obviously 396 // reach, even though the branch should get folded to fall through implicitly. 397 if (MachineFunction::iterator(TBB) == Fallthrough || 398 MachineFunction::iterator(FBB) == Fallthrough) 399 return true; 400 401 // If it's an unconditional branch to some block not the fall through, it 402 // doesn't fall through. 403 if (Cond.empty()) return false; 404 405 // Otherwise, if it is conditional and has no explicit false block, it falls 406 // through. 407 return FBB == 0; 408} 409 410/// removeFromParent - This method unlinks 'this' from the containing function, 411/// and returns it, but does not delete it. 412MachineBasicBlock *MachineBasicBlock::removeFromParent() { 413 assert(getParent() && "Not embedded in a function!"); 414 getParent()->remove(this); 415 return this; 416} 417 418 419/// eraseFromParent - This method unlinks 'this' from the containing function, 420/// and deletes it. 421void MachineBasicBlock::eraseFromParent() { 422 assert(getParent() && "Not embedded in a function!"); 423 getParent()->erase(this); 424} 425 426 427/// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 428/// 'Old', change the code and CFG so that it branches to 'New' instead. 429void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, 430 MachineBasicBlock *New) { 431 assert(Old != New && "Cannot replace self with self!"); 432 433 MachineBasicBlock::iterator I = end(); 434 while (I != begin()) { 435 --I; 436 if (!I->getDesc().isTerminator()) break; 437 438 // Scan the operands of this machine instruction, replacing any uses of Old 439 // with New. 440 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 441 if (I->getOperand(i).isMBB() && 442 I->getOperand(i).getMBB() == Old) 443 I->getOperand(i).setMBB(New); 444 } 445 446 // Update the successor information. 447 removeSuccessor(Old); 448 addSuccessor(New); 449} 450 451/// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the 452/// CFG to be inserted. If we have proven that MBB can only branch to DestA and 453/// DestB, remove any other MBB successors from the CFG. DestA and DestB can 454/// be null. 455/// Besides DestA and DestB, retain other edges leading to LandingPads 456/// (currently there can be only one; we don't check or require that here). 457/// Note it is possible that DestA and/or DestB are LandingPads. 458bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, 459 MachineBasicBlock *DestB, 460 bool isCond) { 461 bool MadeChange = false; 462 bool AddedFallThrough = false; 463 464 MachineFunction::iterator FallThru = 465 llvm::next(MachineFunction::iterator(this)); 466 467 // If this block ends with a conditional branch that falls through to its 468 // successor, set DestB as the successor. 469 if (isCond) { 470 if (DestB == 0 && FallThru != getParent()->end()) { 471 DestB = FallThru; 472 AddedFallThrough = true; 473 } 474 } else { 475 // If this is an unconditional branch with no explicit dest, it must just be 476 // a fallthrough into DestB. 477 if (DestA == 0 && FallThru != getParent()->end()) { 478 DestA = FallThru; 479 AddedFallThrough = true; 480 } 481 } 482 483 MachineBasicBlock::succ_iterator SI = succ_begin(); 484 MachineBasicBlock *OrigDestA = DestA, *OrigDestB = DestB; 485 while (SI != succ_end()) { 486 if (*SI == DestA) { 487 DestA = 0; 488 ++SI; 489 } else if (*SI == DestB) { 490 DestB = 0; 491 ++SI; 492 } else if ((*SI)->isLandingPad() && 493 *SI!=OrigDestA && *SI!=OrigDestB) { 494 ++SI; 495 } else { 496 // Otherwise, this is a superfluous edge, remove it. 497 SI = removeSuccessor(SI); 498 MadeChange = true; 499 } 500 } 501 if (!AddedFallThrough) { 502 assert(DestA == 0 && DestB == 0 && 503 "MachineCFG is missing edges!"); 504 } else if (isCond) { 505 assert(DestA == 0 && "MachineCFG is missing edges!"); 506 } 507 return MadeChange; 508} 509 510void llvm::WriteAsOperand(raw_ostream &OS, const MachineBasicBlock *MBB, 511 bool t) { 512 OS << "BB#" << MBB->getNumber(); 513} 514