TailDuplication.cpp revision d69f85eb416c08e5f803bffccd974745be3d1b2e
1//===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===// 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// This pass duplicates basic blocks ending in unconditional branches into 11// the tails of their predecessors. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "tailduplication" 16#include "llvm/Function.h" 17#include "llvm/CodeGen/Passes.h" 18#include "llvm/CodeGen/MachineModuleInfo.h" 19#include "llvm/CodeGen/MachineFunctionPass.h" 20#include "llvm/CodeGen/MachineInstrBuilder.h" 21#include "llvm/CodeGen/MachineRegisterInfo.h" 22#include "llvm/CodeGen/MachineSSAUpdater.h" 23#include "llvm/Target/TargetInstrInfo.h" 24#include "llvm/Support/CommandLine.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/ErrorHandling.h" 27#include "llvm/Support/raw_ostream.h" 28#include "llvm/ADT/SmallSet.h" 29#include "llvm/ADT/SetVector.h" 30#include "llvm/ADT/Statistic.h" 31using namespace llvm; 32 33STATISTIC(NumTails , "Number of tails duplicated"); 34STATISTIC(NumTailDups , "Number of tail duplicated blocks"); 35STATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 36STATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 37STATISTIC(NumAddedPHIs , "Number of phis added"); 38 39// Heuristic for tail duplication. 40static cl::opt<unsigned> 41TailDuplicateSize("tail-dup-size", 42 cl::desc("Maximum instructions to consider tail duplicating"), 43 cl::init(2), cl::Hidden); 44 45static cl::opt<bool> 46TailDupVerify("tail-dup-verify", 47 cl::desc("Verify sanity of PHI instructions during taildup"), 48 cl::init(false), cl::Hidden); 49 50static cl::opt<unsigned> 51TailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 52 53typedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 54 55namespace { 56 /// TailDuplicatePass - Perform tail duplication. 57 class TailDuplicatePass : public MachineFunctionPass { 58 bool PreRegAlloc; 59 const TargetInstrInfo *TII; 60 MachineModuleInfo *MMI; 61 MachineRegisterInfo *MRI; 62 63 // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 64 SmallVector<unsigned, 16> SSAUpdateVRs; 65 66 // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 67 // source virtual registers. 68 DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 69 70 public: 71 static char ID; 72 explicit TailDuplicatePass(bool PreRA) : 73 MachineFunctionPass(ID), PreRegAlloc(PreRA) {} 74 75 virtual bool runOnMachineFunction(MachineFunction &MF); 76 virtual const char *getPassName() const { return "Tail Duplication"; } 77 78 private: 79 void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 80 MachineBasicBlock *BB); 81 void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 82 MachineBasicBlock *PredBB, 83 DenseMap<unsigned, unsigned> &LocalVRMap, 84 SmallVector<std::pair<unsigned,unsigned>, 4> &Copies); 85 void DuplicateInstruction(MachineInstr *MI, 86 MachineBasicBlock *TailBB, 87 MachineBasicBlock *PredBB, 88 MachineFunction &MF, 89 DenseMap<unsigned, unsigned> &LocalVRMap); 90 void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 91 SmallVector<MachineBasicBlock*, 8> &TDBBs, 92 SmallSetVector<MachineBasicBlock*, 8> &Succs); 93 bool TailDuplicateBlocks(MachineFunction &MF); 94 bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 95 SmallVector<MachineBasicBlock*, 8> &TDBBs, 96 SmallVector<MachineInstr*, 16> &Copies); 97 void RemoveDeadBlock(MachineBasicBlock *MBB); 98 }; 99 100 char TailDuplicatePass::ID = 0; 101} 102 103FunctionPass *llvm::createTailDuplicatePass(bool PreRegAlloc) { 104 return new TailDuplicatePass(PreRegAlloc); 105} 106 107bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 108 TII = MF.getTarget().getInstrInfo(); 109 MRI = &MF.getRegInfo(); 110 MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 111 112 bool MadeChange = false; 113 while (TailDuplicateBlocks(MF)) 114 MadeChange = true; 115 116 return MadeChange; 117} 118 119static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 120 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 121 MachineBasicBlock *MBB = I; 122 SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 123 MBB->pred_end()); 124 MachineBasicBlock::iterator MI = MBB->begin(); 125 while (MI != MBB->end()) { 126 if (!MI->isPHI()) 127 break; 128 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 129 PE = Preds.end(); PI != PE; ++PI) { 130 MachineBasicBlock *PredBB = *PI; 131 bool Found = false; 132 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 133 MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 134 if (PHIBB == PredBB) { 135 Found = true; 136 break; 137 } 138 } 139 if (!Found) { 140 dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 141 dbgs() << " missing input from predecessor BB#" 142 << PredBB->getNumber() << '\n'; 143 llvm_unreachable(0); 144 } 145 } 146 147 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 148 MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 149 if (CheckExtra && !Preds.count(PHIBB)) { 150 // This is not a hard error. 151 dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 152 << ": " << *MI; 153 dbgs() << " extra input from predecessor BB#" 154 << PHIBB->getNumber() << '\n'; 155 } 156 if (PHIBB->getNumber() < 0) { 157 dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 158 dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 159 llvm_unreachable(0); 160 } 161 } 162 ++MI; 163 } 164 } 165} 166 167/// TailDuplicateBlocks - Look for small blocks that are unconditionally 168/// branched to and do not fall through. Tail-duplicate their instructions 169/// into their predecessors to eliminate (dynamic) branches. 170bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 171 bool MadeChange = false; 172 173 if (PreRegAlloc && TailDupVerify) { 174 DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 175 VerifyPHIs(MF, true); 176 } 177 178 SmallVector<MachineInstr*, 8> NewPHIs; 179 MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 180 181 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 182 MachineBasicBlock *MBB = I++; 183 184 if (NumTails == TailDupLimit) 185 break; 186 187 // Only duplicate blocks that end with unconditional branches. 188 if (MBB->canFallThrough()) 189 continue; 190 191 // Save the successors list. 192 SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 193 MBB->succ_end()); 194 195 SmallVector<MachineBasicBlock*, 8> TDBBs; 196 SmallVector<MachineInstr*, 16> Copies; 197 if (TailDuplicate(MBB, MF, TDBBs, Copies)) { 198 ++NumTails; 199 200 // TailBB's immediate successors are now successors of those predecessors 201 // which duplicated TailBB. Add the predecessors as sources to the PHI 202 // instructions. 203 bool isDead = MBB->pred_empty(); 204 if (PreRegAlloc) 205 UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 206 207 // If it is dead, remove it. 208 if (isDead) { 209 NumInstrDups -= MBB->size(); 210 RemoveDeadBlock(MBB); 211 ++NumDeadBlocks; 212 } 213 214 // Update SSA form. 215 if (!SSAUpdateVRs.empty()) { 216 for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 217 unsigned VReg = SSAUpdateVRs[i]; 218 SSAUpdate.Initialize(VReg); 219 220 // If the original definition is still around, add it as an available 221 // value. 222 MachineInstr *DefMI = MRI->getVRegDef(VReg); 223 MachineBasicBlock *DefBB = 0; 224 if (DefMI) { 225 DefBB = DefMI->getParent(); 226 SSAUpdate.AddAvailableValue(DefBB, VReg); 227 } 228 229 // Add the new vregs as available values. 230 DenseMap<unsigned, AvailableValsTy>::iterator LI = 231 SSAUpdateVals.find(VReg); 232 for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 233 MachineBasicBlock *SrcBB = LI->second[j].first; 234 unsigned SrcReg = LI->second[j].second; 235 SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 236 } 237 238 // Rewrite uses that are outside of the original def's block. 239 MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 240 while (UI != MRI->use_end()) { 241 MachineOperand &UseMO = UI.getOperand(); 242 MachineInstr *UseMI = &*UI; 243 ++UI; 244 if (UseMI->getParent() == DefBB) 245 continue; 246 SSAUpdate.RewriteUse(UseMO); 247 } 248 } 249 250 SSAUpdateVRs.clear(); 251 SSAUpdateVals.clear(); 252 } 253 254 // Eliminate some of the copies inserted by tail duplication to maintain 255 // SSA form. 256 for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 257 MachineInstr *Copy = Copies[i]; 258 if (!Copy->isCopy()) 259 continue; 260 unsigned Dst = Copy->getOperand(0).getReg(); 261 unsigned Src = Copy->getOperand(1).getReg(); 262 MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); 263 if (++UI == MRI->use_end()) { 264 // Copy is the only use. Do trivial copy propagation here. 265 MRI->replaceRegWith(Dst, Src); 266 Copy->eraseFromParent(); 267 } 268 } 269 270 if (PreRegAlloc && TailDupVerify) 271 VerifyPHIs(MF, false); 272 MadeChange = true; 273 } 274 } 275 NumAddedPHIs += NewPHIs.size(); 276 277 return MadeChange; 278} 279 280static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 281 const MachineRegisterInfo *MRI) { 282 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 283 UE = MRI->use_end(); UI != UE; ++UI) { 284 MachineInstr *UseMI = &*UI; 285 if (UseMI->getParent() != BB) 286 return true; 287 } 288 return false; 289} 290 291static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 292 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 293 if (MI->getOperand(i+1).getMBB() == SrcBB) 294 return i; 295 return 0; 296} 297 298/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 299/// SSA update. 300void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 301 MachineBasicBlock *BB) { 302 DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 303 if (LI != SSAUpdateVals.end()) 304 LI->second.push_back(std::make_pair(BB, NewReg)); 305 else { 306 AvailableValsTy Vals; 307 Vals.push_back(std::make_pair(BB, NewReg)); 308 SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 309 SSAUpdateVRs.push_back(OrigReg); 310 } 311} 312 313/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 314/// Remember the source register that's contributed by PredBB and update SSA 315/// update map. 316void TailDuplicatePass::ProcessPHI(MachineInstr *MI, 317 MachineBasicBlock *TailBB, 318 MachineBasicBlock *PredBB, 319 DenseMap<unsigned, unsigned> &LocalVRMap, 320 SmallVector<std::pair<unsigned,unsigned>, 4> &Copies) { 321 unsigned DefReg = MI->getOperand(0).getReg(); 322 unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 323 assert(SrcOpIdx && "Unable to find matching PHI source?"); 324 unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 325 const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 326 LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 327 328 // Insert a copy from source to the end of the block. The def register is the 329 // available value liveout of the block. 330 unsigned NewDef = MRI->createVirtualRegister(RC); 331 Copies.push_back(std::make_pair(NewDef, SrcReg)); 332 if (isDefLiveOut(DefReg, TailBB, MRI)) 333 AddSSAUpdateEntry(DefReg, NewDef, PredBB); 334 335 // Remove PredBB from the PHI node. 336 MI->RemoveOperand(SrcOpIdx+1); 337 MI->RemoveOperand(SrcOpIdx); 338 if (MI->getNumOperands() == 1) 339 MI->eraseFromParent(); 340} 341 342/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 343/// the source operands due to earlier PHI translation. 344void TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 345 MachineBasicBlock *TailBB, 346 MachineBasicBlock *PredBB, 347 MachineFunction &MF, 348 DenseMap<unsigned, unsigned> &LocalVRMap) { 349 MachineInstr *NewMI = TII->duplicate(MI, MF); 350 for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 351 MachineOperand &MO = NewMI->getOperand(i); 352 if (!MO.isReg()) 353 continue; 354 unsigned Reg = MO.getReg(); 355 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 356 continue; 357 if (MO.isDef()) { 358 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 359 unsigned NewReg = MRI->createVirtualRegister(RC); 360 MO.setReg(NewReg); 361 LocalVRMap.insert(std::make_pair(Reg, NewReg)); 362 if (isDefLiveOut(Reg, TailBB, MRI)) 363 AddSSAUpdateEntry(Reg, NewReg, PredBB); 364 } else { 365 DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 366 if (VI != LocalVRMap.end()) 367 MO.setReg(VI->second); 368 } 369 } 370 PredBB->insert(PredBB->end(), NewMI); 371} 372 373/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 374/// blocks, the successors have gained new predecessors. Update the PHI 375/// instructions in them accordingly. 376void 377TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 378 SmallVector<MachineBasicBlock*, 8> &TDBBs, 379 SmallSetVector<MachineBasicBlock*,8> &Succs) { 380 for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 381 SE = Succs.end(); SI != SE; ++SI) { 382 MachineBasicBlock *SuccBB = *SI; 383 for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 384 II != EE; ++II) { 385 if (!II->isPHI()) 386 break; 387 unsigned Idx = 0; 388 for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 389 MachineOperand &MO = II->getOperand(i+1); 390 if (MO.getMBB() == FromBB) { 391 Idx = i; 392 break; 393 } 394 } 395 396 assert(Idx != 0); 397 MachineOperand &MO0 = II->getOperand(Idx); 398 unsigned Reg = MO0.getReg(); 399 if (isDead) { 400 // Folded into the previous BB. 401 // There could be duplicate phi source entries. FIXME: Should sdisel 402 // or earlier pass fixed this? 403 for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 404 MachineOperand &MO = II->getOperand(i+1); 405 if (MO.getMBB() == FromBB) { 406 II->RemoveOperand(i+1); 407 II->RemoveOperand(i); 408 } 409 } 410 } else 411 Idx = 0; 412 413 // If Idx is set, the operands at Idx and Idx+1 must be removed. 414 // We reuse the location to avoid expensive RemoveOperand calls. 415 416 DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 417 if (LI != SSAUpdateVals.end()) { 418 // This register is defined in the tail block. 419 for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 420 MachineBasicBlock *SrcBB = LI->second[j].first; 421 unsigned SrcReg = LI->second[j].second; 422 if (Idx != 0) { 423 II->getOperand(Idx).setReg(SrcReg); 424 II->getOperand(Idx+1).setMBB(SrcBB); 425 Idx = 0; 426 } else { 427 II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 428 II->addOperand(MachineOperand::CreateMBB(SrcBB)); 429 } 430 } 431 } else { 432 // Live in tail block, must also be live in predecessors. 433 for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 434 MachineBasicBlock *SrcBB = TDBBs[j]; 435 if (Idx != 0) { 436 II->getOperand(Idx).setReg(Reg); 437 II->getOperand(Idx+1).setMBB(SrcBB); 438 Idx = 0; 439 } else { 440 II->addOperand(MachineOperand::CreateReg(Reg, false)); 441 II->addOperand(MachineOperand::CreateMBB(SrcBB)); 442 } 443 } 444 } 445 if (Idx != 0) { 446 II->RemoveOperand(Idx+1); 447 II->RemoveOperand(Idx); 448 } 449 } 450 } 451} 452 453/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 454/// of its predecessors. 455bool 456TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 457 SmallVector<MachineBasicBlock*, 8> &TDBBs, 458 SmallVector<MachineInstr*, 16> &Copies) { 459 // Set the limit on the number of instructions to duplicate, with a default 460 // of one less than the tail-merge threshold. When optimizing for size, 461 // duplicate only one, because one branch instruction can be eliminated to 462 // compensate for the duplication. 463 unsigned MaxDuplicateCount; 464 if (TailDuplicateSize.getNumOccurrences() == 0 && 465 MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 466 MaxDuplicateCount = 1; 467 else 468 MaxDuplicateCount = TailDuplicateSize; 469 470 if (PreRegAlloc) { 471 if (TailBB->empty()) 472 return false; 473 const TargetInstrDesc &TID = TailBB->back().getDesc(); 474 // Pre-regalloc tail duplication hurts compile time and doesn't help 475 // much except for indirect branches and returns. 476 if (!TID.isIndirectBranch() && !TID.isReturn()) 477 return false; 478 // If the target has hardware branch prediction that can handle indirect 479 // branches, duplicating them can often make them predictable when there 480 // are common paths through the code. The limit needs to be high enough 481 // to allow undoing the effects of tail merging and other optimizations 482 // that rearrange the predecessors of the indirect branch. 483 MaxDuplicateCount = 20; 484 } 485 486 // Don't try to tail-duplicate single-block loops. 487 if (TailBB->isSuccessor(TailBB)) 488 return false; 489 490 // Check the instructions in the block to determine whether tail-duplication 491 // is invalid or unlikely to be profitable. 492 unsigned InstrCount = 0; 493 bool HasCall = false; 494 for (MachineBasicBlock::iterator I = TailBB->begin(); 495 I != TailBB->end(); ++I) { 496 // Non-duplicable things shouldn't be tail-duplicated. 497 if (I->getDesc().isNotDuplicable()) return false; 498 // Do not duplicate 'return' instructions if this is a pre-regalloc run. 499 // A return may expand into a lot more instructions (e.g. reload of callee 500 // saved registers) after PEI. 501 if (PreRegAlloc && I->getDesc().isReturn()) return false; 502 // Don't duplicate more than the threshold. 503 if (InstrCount == MaxDuplicateCount) return false; 504 // Remember if we saw a call. 505 if (I->getDesc().isCall()) HasCall = true; 506 if (!I->isPHI() && !I->isDebugValue()) 507 InstrCount += 1; 508 } 509 // Don't tail-duplicate calls before register allocation. Calls presents a 510 // barrier to register allocation so duplicating them may end up increasing 511 // spills. 512 if (InstrCount > 1 && (PreRegAlloc && HasCall)) 513 return false; 514 515 DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 516 517 // Iterate through all the unique predecessors and tail-duplicate this 518 // block into them, if possible. Copying the list ahead of time also 519 // avoids trouble with the predecessor list reallocating. 520 bool Changed = false; 521 SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 522 TailBB->pred_end()); 523 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 524 PE = Preds.end(); PI != PE; ++PI) { 525 MachineBasicBlock *PredBB = *PI; 526 527 assert(TailBB != PredBB && 528 "Single-block loop should have been rejected earlier!"); 529 if (PredBB->succ_size() > 1) continue; 530 531 MachineBasicBlock *PredTBB, *PredFBB; 532 SmallVector<MachineOperand, 4> PredCond; 533 if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 534 continue; 535 if (!PredCond.empty()) 536 continue; 537 // EH edges are ignored by AnalyzeBranch. 538 if (PredBB->succ_size() != 1) 539 continue; 540 // Don't duplicate into a fall-through predecessor (at least for now). 541 if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 542 continue; 543 544 DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 545 << "From Succ: " << *TailBB); 546 547 TDBBs.push_back(PredBB); 548 549 // Remove PredBB's unconditional branch. 550 TII->RemoveBranch(*PredBB); 551 552 // Clone the contents of TailBB into PredBB. 553 DenseMap<unsigned, unsigned> LocalVRMap; 554 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 555 MachineBasicBlock::iterator I = TailBB->begin(); 556 while (I != TailBB->end()) { 557 MachineInstr *MI = &*I; 558 ++I; 559 if (MI->isPHI()) { 560 // Replace the uses of the def of the PHI with the register coming 561 // from PredBB. 562 ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos); 563 } else { 564 // Replace def of virtual registers with new registers, and update 565 // uses with PHI source register or the new registers. 566 DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap); 567 } 568 } 569 MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 570 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 571 Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 572 TII->get(TargetOpcode::COPY), 573 CopyInfos[i].first).addReg(CopyInfos[i].second)); 574 } 575 NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 576 577 // Update the CFG. 578 PredBB->removeSuccessor(PredBB->succ_begin()); 579 assert(PredBB->succ_empty() && 580 "TailDuplicate called on block with multiple successors!"); 581 for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 582 E = TailBB->succ_end(); I != E; ++I) 583 PredBB->addSuccessor(*I); 584 585 Changed = true; 586 ++NumTailDups; 587 } 588 589 // If TailBB was duplicated into all its predecessors except for the prior 590 // block, which falls through unconditionally, move the contents of this 591 // block into the prior block. 592 MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 593 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 594 SmallVector<MachineOperand, 4> PriorCond; 595 bool PriorUnAnalyzable = 596 TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true); 597 // This has to check PrevBB->succ_size() because EH edges are ignored by 598 // AnalyzeBranch. 599 if (!PriorUnAnalyzable && PriorCond.empty() && !PriorTBB && 600 TailBB->pred_size() == 1 && PrevBB->succ_size() == 1 && 601 !TailBB->hasAddressTaken()) { 602 DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 603 << "From MBB: " << *TailBB); 604 if (PreRegAlloc) { 605 DenseMap<unsigned, unsigned> LocalVRMap; 606 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 607 MachineBasicBlock::iterator I = TailBB->begin(); 608 // Process PHI instructions first. 609 while (I != TailBB->end() && I->isPHI()) { 610 // Replace the uses of the def of the PHI with the register coming 611 // from PredBB. 612 MachineInstr *MI = &*I++; 613 ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos); 614 if (MI->getParent()) 615 MI->eraseFromParent(); 616 } 617 618 // Now copy the non-PHI instructions. 619 while (I != TailBB->end()) { 620 // Replace def of virtual registers with new registers, and update 621 // uses with PHI source register or the new registers. 622 MachineInstr *MI = &*I++; 623 DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap); 624 MI->eraseFromParent(); 625 } 626 MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 627 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 628 Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 629 TII->get(TargetOpcode::COPY), 630 CopyInfos[i].first) 631 .addReg(CopyInfos[i].second)); 632 } 633 } else { 634 // No PHIs to worry about, just splice the instructions over. 635 PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 636 } 637 PrevBB->removeSuccessor(PrevBB->succ_begin()); 638 assert(PrevBB->succ_empty()); 639 PrevBB->transferSuccessors(TailBB); 640 TDBBs.push_back(PrevBB); 641 Changed = true; 642 } 643 644 return Changed; 645} 646 647/// RemoveDeadBlock - Remove the specified dead machine basic block from the 648/// function, updating the CFG. 649void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 650 assert(MBB->pred_empty() && "MBB must be dead!"); 651 DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 652 653 // Remove all successors. 654 while (!MBB->succ_empty()) 655 MBB->removeSuccessor(MBB->succ_end()-1); 656 657 // Remove the block. 658 MBB->eraseFromParent(); 659} 660 661