MachineBasicBlock.cpp revision 990ca5517fd6666d4049b6b8281d9df99da11637
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/LiveVariables.h" 17#include "llvm/CodeGen/MachineDominators.h" 18#include "llvm/CodeGen/MachineFunction.h" 19#include "llvm/CodeGen/MachineLoopInfo.h" 20#include "llvm/CodeGen/SlotIndexes.h" 21#include "llvm/MC/MCAsmInfo.h" 22#include "llvm/MC/MCContext.h" 23#include "llvm/Target/TargetRegisterInfo.h" 24#include "llvm/Target/TargetData.h" 25#include "llvm/Target/TargetInstrInfo.h" 26#include "llvm/Target/TargetMachine.h" 27#include "llvm/Assembly/Writer.h" 28#include "llvm/ADT/SmallString.h" 29#include "llvm/ADT/SmallPtrSet.h" 30#include "llvm/Support/Debug.h" 31#include "llvm/Support/LeakDetector.h" 32#include "llvm/Support/raw_ostream.h" 33#include <algorithm> 34using namespace llvm; 35 36MachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb) 37 : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false), 38 AddressTaken(false) { 39 Insts.Parent = this; 40} 41 42MachineBasicBlock::~MachineBasicBlock() { 43 LeakDetector::removeGarbageObject(this); 44} 45 46/// getSymbol - Return the MCSymbol for this basic block. 47/// 48MCSymbol *MachineBasicBlock::getSymbol() const { 49 const MachineFunction *MF = getParent(); 50 MCContext &Ctx = MF->getContext(); 51 const char *Prefix = Ctx.getAsmInfo().getPrivateGlobalPrefix(); 52 return Ctx.GetOrCreateSymbol(Twine(Prefix) + "BB" + 53 Twine(MF->getFunctionNumber()) + "_" + 54 Twine(getNumber())); 55} 56 57 58raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) { 59 MBB.print(OS); 60 return OS; 61} 62 63/// addNodeToList (MBB) - When an MBB is added to an MF, we need to update the 64/// parent pointer of the MBB, the MBB numbering, and any instructions in the 65/// MBB to be on the right operand list for registers. 66/// 67/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it 68/// gets the next available unique MBB number. If it is removed from a 69/// MachineFunction, it goes back to being #-1. 70void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock *N) { 71 MachineFunction &MF = *N->getParent(); 72 N->Number = MF.addToMBBNumbering(N); 73 74 // Make sure the instructions have their operands in the reginfo lists. 75 MachineRegisterInfo &RegInfo = MF.getRegInfo(); 76 for (MachineBasicBlock::instr_iterator 77 I = N->instr_begin(), E = N->instr_end(); I != E; ++I) 78 I->AddRegOperandsToUseLists(RegInfo); 79 80 LeakDetector::removeGarbageObject(N); 81} 82 83void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock *N) { 84 N->getParent()->removeFromMBBNumbering(N->Number); 85 N->Number = -1; 86 LeakDetector::addGarbageObject(N); 87} 88 89 90/// addNodeToList (MI) - When we add an instruction to a basic block 91/// list, we update its parent pointer and add its operands from reg use/def 92/// lists if appropriate. 93void ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) { 94 assert(N->getParent() == 0 && "machine instruction already in a basic block"); 95 N->setParent(Parent); 96 97 // Add the instruction's register operands to their corresponding 98 // use/def lists. 99 MachineFunction *MF = Parent->getParent(); 100 N->AddRegOperandsToUseLists(MF->getRegInfo()); 101 102 LeakDetector::removeGarbageObject(N); 103} 104 105/// removeNodeFromList (MI) - When we remove an instruction from a basic block 106/// list, we update its parent pointer and remove its operands from reg use/def 107/// lists if appropriate. 108void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) { 109 assert(N->getParent() != 0 && "machine instruction not in a basic block"); 110 111 // Remove from the use/def lists. 112 if (MachineFunction *MF = N->getParent()->getParent()) 113 N->RemoveRegOperandsFromUseLists(MF->getRegInfo()); 114 115 N->setParent(0); 116 117 LeakDetector::addGarbageObject(N); 118} 119 120/// transferNodesFromList (MI) - When moving a range of instructions from one 121/// MBB list to another, we need to update the parent pointers and the use/def 122/// lists. 123void ilist_traits<MachineInstr>:: 124transferNodesFromList(ilist_traits<MachineInstr> &fromList, 125 ilist_iterator<MachineInstr> first, 126 ilist_iterator<MachineInstr> last) { 127 assert(Parent->getParent() == fromList.Parent->getParent() && 128 "MachineInstr parent mismatch!"); 129 130 // Splice within the same MBB -> no change. 131 if (Parent == fromList.Parent) return; 132 133 // If splicing between two blocks within the same function, just update the 134 // parent pointers. 135 for (; first != last; ++first) 136 first->setParent(Parent); 137} 138 139void ilist_traits<MachineInstr>::deleteNode(MachineInstr* MI) { 140 assert(!MI->getParent() && "MI is still in a block!"); 141 Parent->getParent()->DeleteMachineInstr(MI); 142} 143 144MachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() { 145 instr_iterator I = instr_begin(), E = instr_end(); 146 while (I != E && I->isPHI()) 147 ++I; 148 assert(!I->isInsideBundle() && "First non-phi MI cannot be inside a bundle!"); 149 return I; 150} 151 152MachineBasicBlock::iterator 153MachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) { 154 iterator E = end(); 155 while (I != E && (I->isPHI() || I->isLabel() || I->isDebugValue())) 156 ++I; 157 // FIXME: This needs to change if we wish to bundle labels / dbg_values 158 // inside the bundle. 159 assert(!I->isInsideBundle() && 160 "First non-phi / non-label instruction is inside a bundle!"); 161 return I; 162} 163 164MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { 165 iterator B = begin(), E = end(), I = E; 166 while (I != B && ((--I)->isTerminator() || I->isDebugValue())) 167 ; /*noop */ 168 while (I != E && !I->isTerminator()) 169 ++I; 170 return I; 171} 172 173MachineBasicBlock::const_iterator 174MachineBasicBlock::getFirstTerminator() const { 175 const_iterator B = begin(), E = end(), I = E; 176 while (I != B && ((--I)->isTerminator() || I->isDebugValue())) 177 ; /*noop */ 178 while (I != E && !I->isTerminator()) 179 ++I; 180 return I; 181} 182 183MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() { 184 instr_iterator B = instr_begin(), E = instr_end(), I = E; 185 while (I != B && ((--I)->isTerminator() || I->isDebugValue())) 186 ; /*noop */ 187 while (I != E && !I->isTerminator()) 188 ++I; 189 return I; 190} 191 192MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() { 193 // Skip over end-of-block dbg_value instructions. 194 instr_iterator B = instr_begin(), I = instr_end(); 195 while (I != B) { 196 --I; 197 // Return instruction that starts a bundle. 198 if (I->isDebugValue() || I->isInsideBundle()) 199 continue; 200 return I; 201 } 202 // The block is all debug values. 203 return end(); 204} 205 206MachineBasicBlock::const_iterator 207MachineBasicBlock::getLastNonDebugInstr() const { 208 // Skip over end-of-block dbg_value instructions. 209 const_instr_iterator B = instr_begin(), I = instr_end(); 210 while (I != B) { 211 --I; 212 // Return instruction that starts a bundle. 213 if (I->isDebugValue() || I->isInsideBundle()) 214 continue; 215 return I; 216 } 217 // The block is all debug values. 218 return end(); 219} 220 221const MachineBasicBlock *MachineBasicBlock::getLandingPadSuccessor() const { 222 // A block with a landing pad successor only has one other successor. 223 if (succ_size() > 2) 224 return 0; 225 for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I) 226 if ((*I)->isLandingPad()) 227 return *I; 228 return 0; 229} 230 231void MachineBasicBlock::dump() const { 232 print(dbgs()); 233} 234 235StringRef MachineBasicBlock::getName() const { 236 if (const BasicBlock *LBB = getBasicBlock()) 237 return LBB->getName(); 238 else 239 return "(null)"; 240} 241 242/// Return a hopefully unique identifier for this block. 243std::string MachineBasicBlock::getFullName() const { 244 std::string Name; 245 if (getParent()) 246 Name = (getParent()->getFunction()->getName() + ":").str(); 247 if (getBasicBlock()) 248 Name += getBasicBlock()->getName(); 249 else 250 Name += (Twine("BB") + Twine(getNumber())).str(); 251 return Name; 252} 253 254void MachineBasicBlock::print(raw_ostream &OS, SlotIndexes *Indexes) const { 255 const MachineFunction *MF = getParent(); 256 if (!MF) { 257 OS << "Can't print out MachineBasicBlock because parent MachineFunction" 258 << " is null\n"; 259 return; 260 } 261 262 if (Indexes) 263 OS << Indexes->getMBBStartIdx(this) << '\t'; 264 265 OS << "BB#" << getNumber() << ": "; 266 267 const char *Comma = ""; 268 if (const BasicBlock *LBB = getBasicBlock()) { 269 OS << Comma << "derived from LLVM BB "; 270 WriteAsOperand(OS, LBB, /*PrintType=*/false); 271 Comma = ", "; 272 } 273 if (isLandingPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; } 274 if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; } 275 if (Alignment) 276 OS << Comma << "Align " << Alignment << " (" << (1u << Alignment) 277 << " bytes)"; 278 279 OS << '\n'; 280 281 const TargetRegisterInfo *TRI = MF->getTarget().getRegisterInfo(); 282 if (!livein_empty()) { 283 if (Indexes) OS << '\t'; 284 OS << " Live Ins:"; 285 for (livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I) 286 OS << ' ' << PrintReg(*I, TRI); 287 OS << '\n'; 288 } 289 // Print the preds of this block according to the CFG. 290 if (!pred_empty()) { 291 if (Indexes) OS << '\t'; 292 OS << " Predecessors according to CFG:"; 293 for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI) 294 OS << " BB#" << (*PI)->getNumber(); 295 OS << '\n'; 296 } 297 298 for (const_instr_iterator I = instr_begin(); I != instr_end(); ++I) { 299 if (Indexes) { 300 if (Indexes->hasIndex(I)) 301 OS << Indexes->getInstructionIndex(I); 302 OS << '\t'; 303 } 304 OS << '\t'; 305 if (I->isInsideBundle()) 306 OS << " * "; 307 I->print(OS, &getParent()->getTarget()); 308 } 309 310 // Print the successors of this block according to the CFG. 311 if (!succ_empty()) { 312 if (Indexes) OS << '\t'; 313 OS << " Successors according to CFG:"; 314 for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) { 315 OS << " BB#" << (*SI)->getNumber(); 316 if (!Weights.empty()) 317 OS << '(' << *getWeightIterator(SI) << ')'; 318 } 319 OS << '\n'; 320 } 321} 322 323void MachineBasicBlock::removeLiveIn(unsigned Reg) { 324 std::vector<unsigned>::iterator I = 325 std::find(LiveIns.begin(), LiveIns.end(), Reg); 326 if (I != LiveIns.end()) 327 LiveIns.erase(I); 328} 329 330bool MachineBasicBlock::isLiveIn(unsigned Reg) const { 331 livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 332 return I != livein_end(); 333} 334 335void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { 336 getParent()->splice(NewAfter, this); 337} 338 339void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { 340 MachineFunction::iterator BBI = NewBefore; 341 getParent()->splice(++BBI, this); 342} 343 344void MachineBasicBlock::updateTerminator() { 345 const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); 346 // A block with no successors has no concerns with fall-through edges. 347 if (this->succ_empty()) return; 348 349 MachineBasicBlock *TBB = 0, *FBB = 0; 350 SmallVector<MachineOperand, 4> Cond; 351 DebugLoc dl; // FIXME: this is nowhere 352 bool B = TII->AnalyzeBranch(*this, TBB, FBB, Cond); 353 (void) B; 354 assert(!B && "UpdateTerminators requires analyzable predecessors!"); 355 if (Cond.empty()) { 356 if (TBB) { 357 // The block has an unconditional branch. If its successor is now 358 // its layout successor, delete the branch. 359 if (isLayoutSuccessor(TBB)) 360 TII->RemoveBranch(*this); 361 } else { 362 // The block has an unconditional fallthrough. If its successor is not 363 // its layout successor, insert a branch. First we have to locate the 364 // only non-landing-pad successor, as that is the fallthrough block. 365 for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) { 366 if ((*SI)->isLandingPad()) 367 continue; 368 assert(!TBB && "Found more than one non-landing-pad successor!"); 369 TBB = *SI; 370 } 371 372 // If there is no non-landing-pad successor, the block has no 373 // fall-through edges to be concerned with. 374 if (!TBB) 375 return; 376 377 // Finally update the unconditional successor to be reached via a branch 378 // if it would not be reached by fallthrough. 379 if (!isLayoutSuccessor(TBB)) 380 TII->InsertBranch(*this, TBB, 0, Cond, dl); 381 } 382 } else { 383 if (FBB) { 384 // The block has a non-fallthrough conditional branch. If one of its 385 // successors is its layout successor, rewrite it to a fallthrough 386 // conditional branch. 387 if (isLayoutSuccessor(TBB)) { 388 if (TII->ReverseBranchCondition(Cond)) 389 return; 390 TII->RemoveBranch(*this); 391 TII->InsertBranch(*this, FBB, 0, Cond, dl); 392 } else if (isLayoutSuccessor(FBB)) { 393 TII->RemoveBranch(*this); 394 TII->InsertBranch(*this, TBB, 0, Cond, dl); 395 } 396 } else { 397 // Walk through the successors and find the successor which is not 398 // a landing pad and is not the conditional branch destination (in TBB) 399 // as the fallthrough successor. 400 MachineBasicBlock *FallthroughBB = 0; 401 for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) { 402 if ((*SI)->isLandingPad() || *SI == TBB) 403 continue; 404 assert(!FallthroughBB && "Found more than one fallthrough successor."); 405 FallthroughBB = *SI; 406 } 407 if (!FallthroughBB && canFallThrough()) { 408 // We fallthrough to the same basic block as the conditional jump 409 // targets. Remove the conditional jump, leaving unconditional 410 // fallthrough. 411 // FIXME: This does not seem like a reasonable pattern to support, but it 412 // has been seen in the wild coming out of degenerate ARM test cases. 413 TII->RemoveBranch(*this); 414 415 // Finally update the unconditional successor to be reached via a branch 416 // if it would not be reached by fallthrough. 417 if (!isLayoutSuccessor(TBB)) 418 TII->InsertBranch(*this, TBB, 0, Cond, dl); 419 return; 420 } 421 422 // The block has a fallthrough conditional branch. 423 if (isLayoutSuccessor(TBB)) { 424 if (TII->ReverseBranchCondition(Cond)) { 425 // We can't reverse the condition, add an unconditional branch. 426 Cond.clear(); 427 TII->InsertBranch(*this, FallthroughBB, 0, Cond, dl); 428 return; 429 } 430 TII->RemoveBranch(*this); 431 TII->InsertBranch(*this, FallthroughBB, 0, Cond, dl); 432 } else if (!isLayoutSuccessor(FallthroughBB)) { 433 TII->RemoveBranch(*this); 434 TII->InsertBranch(*this, TBB, FallthroughBB, Cond, dl); 435 } 436 } 437 } 438} 439 440void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ, uint32_t weight) { 441 442 // If we see non-zero value for the first time it means we actually use Weight 443 // list, so we fill all Weights with 0's. 444 if (weight != 0 && Weights.empty()) 445 Weights.resize(Successors.size()); 446 447 if (weight != 0 || !Weights.empty()) 448 Weights.push_back(weight); 449 450 Successors.push_back(succ); 451 succ->addPredecessor(this); 452 } 453 454void MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) { 455 succ->removePredecessor(this); 456 succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); 457 assert(I != Successors.end() && "Not a current successor!"); 458 459 // If Weight list is empty it means we don't use it (disabled optimization). 460 if (!Weights.empty()) { 461 weight_iterator WI = getWeightIterator(I); 462 Weights.erase(WI); 463 } 464 465 Successors.erase(I); 466} 467 468MachineBasicBlock::succ_iterator 469MachineBasicBlock::removeSuccessor(succ_iterator I) { 470 assert(I != Successors.end() && "Not a current successor!"); 471 472 // If Weight list is empty it means we don't use it (disabled optimization). 473 if (!Weights.empty()) { 474 weight_iterator WI = getWeightIterator(I); 475 Weights.erase(WI); 476 } 477 478 (*I)->removePredecessor(this); 479 return Successors.erase(I); 480} 481 482void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, 483 MachineBasicBlock *New) { 484 if (Old == New) 485 return; 486 487 succ_iterator E = succ_end(); 488 succ_iterator NewI = E; 489 succ_iterator OldI = E; 490 for (succ_iterator I = succ_begin(); I != E; ++I) { 491 if (*I == Old) { 492 OldI = I; 493 if (NewI != E) 494 break; 495 } 496 if (*I == New) { 497 NewI = I; 498 if (OldI != E) 499 break; 500 } 501 } 502 assert(OldI != E && "Old is not a successor of this block"); 503 Old->removePredecessor(this); 504 505 // If New isn't already a successor, let it take Old's place. 506 if (NewI == E) { 507 New->addPredecessor(this); 508 *OldI = New; 509 return; 510 } 511 512 // New is already a successor. 513 // Update its weight instead of adding a duplicate edge. 514 if (!Weights.empty()) { 515 weight_iterator OldWI = getWeightIterator(OldI); 516 *getWeightIterator(NewI) += *OldWI; 517 Weights.erase(OldWI); 518 } 519 Successors.erase(OldI); 520} 521 522void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) { 523 Predecessors.push_back(pred); 524} 525 526void MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) { 527 pred_iterator I = std::find(Predecessors.begin(), Predecessors.end(), pred); 528 assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); 529 Predecessors.erase(I); 530} 531 532void MachineBasicBlock::transferSuccessors(MachineBasicBlock *fromMBB) { 533 if (this == fromMBB) 534 return; 535 536 while (!fromMBB->succ_empty()) { 537 MachineBasicBlock *Succ = *fromMBB->succ_begin(); 538 uint32_t Weight = 0; 539 540 // If Weight list is empty it means we don't use it (disabled optimization). 541 if (!fromMBB->Weights.empty()) 542 Weight = *fromMBB->Weights.begin(); 543 544 addSuccessor(Succ, Weight); 545 fromMBB->removeSuccessor(Succ); 546 } 547} 548 549void 550MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB) { 551 if (this == fromMBB) 552 return; 553 554 while (!fromMBB->succ_empty()) { 555 MachineBasicBlock *Succ = *fromMBB->succ_begin(); 556 uint32_t Weight = 0; 557 if (!fromMBB->Weights.empty()) 558 Weight = *fromMBB->Weights.begin(); 559 addSuccessor(Succ, Weight); 560 fromMBB->removeSuccessor(Succ); 561 562 // Fix up any PHI nodes in the successor. 563 for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(), 564 ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI) 565 for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) { 566 MachineOperand &MO = MI->getOperand(i); 567 if (MO.getMBB() == fromMBB) 568 MO.setMBB(this); 569 } 570 } 571} 572 573bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const { 574 return std::find(pred_begin(), pred_end(), MBB) != pred_end(); 575} 576 577bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { 578 return std::find(succ_begin(), succ_end(), MBB) != succ_end(); 579} 580 581bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { 582 MachineFunction::const_iterator I(this); 583 return llvm::next(I) == MachineFunction::const_iterator(MBB); 584} 585 586bool MachineBasicBlock::canFallThrough() { 587 MachineFunction::iterator Fallthrough = this; 588 ++Fallthrough; 589 // If FallthroughBlock is off the end of the function, it can't fall through. 590 if (Fallthrough == getParent()->end()) 591 return false; 592 593 // If FallthroughBlock isn't a successor, no fallthrough is possible. 594 if (!isSuccessor(Fallthrough)) 595 return false; 596 597 // Analyze the branches, if any, at the end of the block. 598 MachineBasicBlock *TBB = 0, *FBB = 0; 599 SmallVector<MachineOperand, 4> Cond; 600 const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); 601 if (TII->AnalyzeBranch(*this, TBB, FBB, Cond)) { 602 // If we couldn't analyze the branch, examine the last instruction. 603 // If the block doesn't end in a known control barrier, assume fallthrough 604 // is possible. The isPredicated check is needed because this code can be 605 // called during IfConversion, where an instruction which is normally a 606 // Barrier is predicated and thus no longer an actual control barrier. 607 return empty() || !back().isBarrier() || TII->isPredicated(&back()); 608 } 609 610 // If there is no branch, control always falls through. 611 if (TBB == 0) return true; 612 613 // If there is some explicit branch to the fallthrough block, it can obviously 614 // reach, even though the branch should get folded to fall through implicitly. 615 if (MachineFunction::iterator(TBB) == Fallthrough || 616 MachineFunction::iterator(FBB) == Fallthrough) 617 return true; 618 619 // If it's an unconditional branch to some block not the fall through, it 620 // doesn't fall through. 621 if (Cond.empty()) return false; 622 623 // Otherwise, if it is conditional and has no explicit false block, it falls 624 // through. 625 return FBB == 0; 626} 627 628MachineBasicBlock * 629MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { 630 // Splitting the critical edge to a landing pad block is non-trivial. Don't do 631 // it in this generic function. 632 if (Succ->isLandingPad()) 633 return NULL; 634 635 MachineFunction *MF = getParent(); 636 DebugLoc dl; // FIXME: this is nowhere 637 638 // We may need to update this's terminator, but we can't do that if 639 // AnalyzeBranch fails. If this uses a jump table, we won't touch it. 640 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 641 MachineBasicBlock *TBB = 0, *FBB = 0; 642 SmallVector<MachineOperand, 4> Cond; 643 if (TII->AnalyzeBranch(*this, TBB, FBB, Cond)) 644 return NULL; 645 646 // Avoid bugpoint weirdness: A block may end with a conditional branch but 647 // jumps to the same MBB is either case. We have duplicate CFG edges in that 648 // case that we can't handle. Since this never happens in properly optimized 649 // code, just skip those edges. 650 if (TBB && TBB == FBB) { 651 DEBUG(dbgs() << "Won't split critical edge after degenerate BB#" 652 << getNumber() << '\n'); 653 return NULL; 654 } 655 656 MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); 657 MF->insert(llvm::next(MachineFunction::iterator(this)), NMBB); 658 DEBUG(dbgs() << "Splitting critical edge:" 659 " BB#" << getNumber() 660 << " -- BB#" << NMBB->getNumber() 661 << " -- BB#" << Succ->getNumber() << '\n'); 662 663 // On some targets like Mips, branches may kill virtual registers. Make sure 664 // that LiveVariables is properly updated after updateTerminator replaces the 665 // terminators. 666 LiveVariables *LV = P->getAnalysisIfAvailable<LiveVariables>(); 667 668 // Collect a list of virtual registers killed by the terminators. 669 SmallVector<unsigned, 4> KilledRegs; 670 if (LV) 671 for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); 672 I != E; ++I) { 673 MachineInstr *MI = I; 674 for (MachineInstr::mop_iterator OI = MI->operands_begin(), 675 OE = MI->operands_end(); OI != OE; ++OI) { 676 if (!OI->isReg() || OI->getReg() == 0 || 677 !OI->isUse() || !OI->isKill() || OI->isUndef()) 678 continue; 679 unsigned Reg = OI->getReg(); 680 if (TargetRegisterInfo::isPhysicalRegister(Reg) || 681 LV->getVarInfo(Reg).removeKill(MI)) { 682 KilledRegs.push_back(Reg); 683 DEBUG(dbgs() << "Removing terminator kill: " << *MI); 684 OI->setIsKill(false); 685 } 686 } 687 } 688 689 ReplaceUsesOfBlockWith(Succ, NMBB); 690 updateTerminator(); 691 692 // Insert unconditional "jump Succ" instruction in NMBB if necessary. 693 NMBB->addSuccessor(Succ); 694 if (!NMBB->isLayoutSuccessor(Succ)) { 695 Cond.clear(); 696 MF->getTarget().getInstrInfo()->InsertBranch(*NMBB, Succ, NULL, Cond, dl); 697 } 698 699 // Fix PHI nodes in Succ so they refer to NMBB instead of this 700 for (MachineBasicBlock::instr_iterator 701 i = Succ->instr_begin(),e = Succ->instr_end(); 702 i != e && i->isPHI(); ++i) 703 for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2) 704 if (i->getOperand(ni+1).getMBB() == this) 705 i->getOperand(ni+1).setMBB(NMBB); 706 707 // Inherit live-ins from the successor 708 for (MachineBasicBlock::livein_iterator I = Succ->livein_begin(), 709 E = Succ->livein_end(); I != E; ++I) 710 NMBB->addLiveIn(*I); 711 712 // Update LiveVariables. 713 const TargetRegisterInfo *TRI = MF->getTarget().getRegisterInfo(); 714 if (LV) { 715 // Restore kills of virtual registers that were killed by the terminators. 716 while (!KilledRegs.empty()) { 717 unsigned Reg = KilledRegs.pop_back_val(); 718 for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) { 719 if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false)) 720 continue; 721 if (TargetRegisterInfo::isVirtualRegister(Reg)) 722 LV->getVarInfo(Reg).Kills.push_back(I); 723 DEBUG(dbgs() << "Restored terminator kill: " << *I); 724 break; 725 } 726 } 727 // Update relevant live-through information. 728 LV->addNewBlock(NMBB, this, Succ); 729 } 730 731 if (MachineDominatorTree *MDT = 732 P->getAnalysisIfAvailable<MachineDominatorTree>()) { 733 // Update dominator information. 734 MachineDomTreeNode *SucccDTNode = MDT->getNode(Succ); 735 736 bool IsNewIDom = true; 737 for (const_pred_iterator PI = Succ->pred_begin(), E = Succ->pred_end(); 738 PI != E; ++PI) { 739 MachineBasicBlock *PredBB = *PI; 740 if (PredBB == NMBB) 741 continue; 742 if (!MDT->dominates(SucccDTNode, MDT->getNode(PredBB))) { 743 IsNewIDom = false; 744 break; 745 } 746 } 747 748 // We know "this" dominates the newly created basic block. 749 MachineDomTreeNode *NewDTNode = MDT->addNewBlock(NMBB, this); 750 751 // If all the other predecessors of "Succ" are dominated by "Succ" itself 752 // then the new block is the new immediate dominator of "Succ". Otherwise, 753 // the new block doesn't dominate anything. 754 if (IsNewIDom) 755 MDT->changeImmediateDominator(SucccDTNode, NewDTNode); 756 } 757 758 if (MachineLoopInfo *MLI = P->getAnalysisIfAvailable<MachineLoopInfo>()) 759 if (MachineLoop *TIL = MLI->getLoopFor(this)) { 760 // If one or the other blocks were not in a loop, the new block is not 761 // either, and thus LI doesn't need to be updated. 762 if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) { 763 if (TIL == DestLoop) { 764 // Both in the same loop, the NMBB joins loop. 765 DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); 766 } else if (TIL->contains(DestLoop)) { 767 // Edge from an outer loop to an inner loop. Add to the outer loop. 768 TIL->addBasicBlockToLoop(NMBB, MLI->getBase()); 769 } else if (DestLoop->contains(TIL)) { 770 // Edge from an inner loop to an outer loop. Add to the outer loop. 771 DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); 772 } else { 773 // Edge from two loops with no containment relation. Because these 774 // are natural loops, we know that the destination block must be the 775 // header of its loop (adding a branch into a loop elsewhere would 776 // create an irreducible loop). 777 assert(DestLoop->getHeader() == Succ && 778 "Should not create irreducible loops!"); 779 if (MachineLoop *P = DestLoop->getParentLoop()) 780 P->addBasicBlockToLoop(NMBB, MLI->getBase()); 781 } 782 } 783 } 784 785 return NMBB; 786} 787 788MachineBasicBlock::iterator 789MachineBasicBlock::erase(MachineBasicBlock::iterator I) { 790 if (I->isBundle()) { 791 MachineBasicBlock::iterator E = llvm::next(I); 792 return Insts.erase(I.getInstrIterator(), E.getInstrIterator()); 793 } 794 795 return Insts.erase(I.getInstrIterator()); 796} 797 798MachineInstr *MachineBasicBlock::remove(MachineInstr *I) { 799 if (I->isBundle()) { 800 instr_iterator MII = llvm::next(I); 801 iterator E = end(); 802 while (MII != E && MII->isInsideBundle()) { 803 MachineInstr *MI = &*MII++; 804 Insts.remove(MI); 805 } 806 } 807 808 return Insts.remove(I); 809} 810 811void MachineBasicBlock::splice(MachineBasicBlock::iterator where, 812 MachineBasicBlock *Other, 813 MachineBasicBlock::iterator From) { 814 if (From->isBundle()) { 815 MachineBasicBlock::iterator To = llvm::next(From); 816 Insts.splice(where.getInstrIterator(), Other->Insts, 817 From.getInstrIterator(), To.getInstrIterator()); 818 return; 819 } 820 821 Insts.splice(where.getInstrIterator(), Other->Insts, From.getInstrIterator()); 822} 823 824/// removeFromParent - This method unlinks 'this' from the containing function, 825/// and returns it, but does not delete it. 826MachineBasicBlock *MachineBasicBlock::removeFromParent() { 827 assert(getParent() && "Not embedded in a function!"); 828 getParent()->remove(this); 829 return this; 830} 831 832 833/// eraseFromParent - This method unlinks 'this' from the containing function, 834/// and deletes it. 835void MachineBasicBlock::eraseFromParent() { 836 assert(getParent() && "Not embedded in a function!"); 837 getParent()->erase(this); 838} 839 840 841/// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 842/// 'Old', change the code and CFG so that it branches to 'New' instead. 843void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, 844 MachineBasicBlock *New) { 845 assert(Old != New && "Cannot replace self with self!"); 846 847 MachineBasicBlock::instr_iterator I = instr_end(); 848 while (I != instr_begin()) { 849 --I; 850 if (!I->isTerminator()) break; 851 852 // Scan the operands of this machine instruction, replacing any uses of Old 853 // with New. 854 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 855 if (I->getOperand(i).isMBB() && 856 I->getOperand(i).getMBB() == Old) 857 I->getOperand(i).setMBB(New); 858 } 859 860 // Update the successor information. 861 replaceSuccessor(Old, New); 862} 863 864/// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the 865/// CFG to be inserted. If we have proven that MBB can only branch to DestA and 866/// DestB, remove any other MBB successors from the CFG. DestA and DestB can be 867/// null. 868/// 869/// Besides DestA and DestB, retain other edges leading to LandingPads 870/// (currently there can be only one; we don't check or require that here). 871/// Note it is possible that DestA and/or DestB are LandingPads. 872bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, 873 MachineBasicBlock *DestB, 874 bool isCond) { 875 // The values of DestA and DestB frequently come from a call to the 876 // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial 877 // values from there. 878 // 879 // 1. If both DestA and DestB are null, then the block ends with no branches 880 // (it falls through to its successor). 881 // 2. If DestA is set, DestB is null, and isCond is false, then the block ends 882 // with only an unconditional branch. 883 // 3. If DestA is set, DestB is null, and isCond is true, then the block ends 884 // with a conditional branch that falls through to a successor (DestB). 885 // 4. If DestA and DestB is set and isCond is true, then the block ends with a 886 // conditional branch followed by an unconditional branch. DestA is the 887 // 'true' destination and DestB is the 'false' destination. 888 889 bool Changed = false; 890 891 MachineFunction::iterator FallThru = 892 llvm::next(MachineFunction::iterator(this)); 893 894 if (DestA == 0 && DestB == 0) { 895 // Block falls through to successor. 896 DestA = FallThru; 897 DestB = FallThru; 898 } else if (DestA != 0 && DestB == 0) { 899 if (isCond) 900 // Block ends in conditional jump that falls through to successor. 901 DestB = FallThru; 902 } else { 903 assert(DestA && DestB && isCond && 904 "CFG in a bad state. Cannot correct CFG edges"); 905 } 906 907 // Remove superfluous edges. I.e., those which aren't destinations of this 908 // basic block, duplicate edges, or landing pads. 909 SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs; 910 MachineBasicBlock::succ_iterator SI = succ_begin(); 911 while (SI != succ_end()) { 912 const MachineBasicBlock *MBB = *SI; 913 if (!SeenMBBs.insert(MBB) || 914 (MBB != DestA && MBB != DestB && !MBB->isLandingPad())) { 915 // This is a superfluous edge, remove it. 916 SI = removeSuccessor(SI); 917 Changed = true; 918 } else { 919 ++SI; 920 } 921 } 922 923 return Changed; 924} 925 926/// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 927/// any DBG_VALUE instructions. Return UnknownLoc if there is none. 928DebugLoc 929MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { 930 DebugLoc DL; 931 instr_iterator E = instr_end(); 932 if (MBBI == E) 933 return DL; 934 935 // Skip debug declarations, we don't want a DebugLoc from them. 936 while (MBBI != E && MBBI->isDebugValue()) 937 MBBI++; 938 if (MBBI != E) 939 DL = MBBI->getDebugLoc(); 940 return DL; 941} 942 943/// getSuccWeight - Return weight of the edge from this block to MBB. 944/// 945uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const { 946 if (Weights.empty()) 947 return 0; 948 949 return *getWeightIterator(Succ); 950} 951 952/// getWeightIterator - Return wight iterator corresonding to the I successor 953/// iterator 954MachineBasicBlock::weight_iterator MachineBasicBlock:: 955getWeightIterator(MachineBasicBlock::succ_iterator I) { 956 assert(Weights.size() == Successors.size() && "Async weight list!"); 957 size_t index = std::distance(Successors.begin(), I); 958 assert(index < Weights.size() && "Not a current successor!"); 959 return Weights.begin() + index; 960} 961 962/// getWeightIterator - Return wight iterator corresonding to the I successor 963/// iterator 964MachineBasicBlock::const_weight_iterator MachineBasicBlock:: 965getWeightIterator(MachineBasicBlock::const_succ_iterator I) const { 966 assert(Weights.size() == Successors.size() && "Async weight list!"); 967 const size_t index = std::distance(Successors.begin(), I); 968 assert(index < Weights.size() && "Not a current successor!"); 969 return Weights.begin() + index; 970} 971 972void llvm::WriteAsOperand(raw_ostream &OS, const MachineBasicBlock *MBB, 973 bool t) { 974 OS << "BB#" << MBB->getNumber(); 975} 976 977