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