TailDuplication.cpp revision 212904
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"); 37 38// Heuristic for tail duplication. 39static cl::opt<unsigned> 40TailDuplicateSize("tail-dup-size", 41 cl::desc("Maximum instructions to consider tail duplicating"), 42 cl::init(2), cl::Hidden); 43 44static cl::opt<bool> 45TailDupVerify("tail-dup-verify", 46 cl::desc("Verify sanity of PHI instructions during taildup"), 47 cl::init(false), cl::Hidden); 48 49static cl::opt<unsigned> 50TailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 51 52typedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 53 54namespace { 55 /// TailDuplicatePass - Perform tail duplication. 56 class TailDuplicatePass : public MachineFunctionPass { 57 bool PreRegAlloc; 58 const TargetInstrInfo *TII; 59 MachineModuleInfo *MMI; 60 MachineRegisterInfo *MRI; 61 62 // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 63 SmallVector<unsigned, 16> SSAUpdateVRs; 64 65 // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 66 // source virtual registers. 67 DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 68 69 public: 70 static char ID; 71 explicit TailDuplicatePass(bool PreRA) : 72 MachineFunctionPass(ID), PreRegAlloc(PreRA) {} 73 74 virtual bool runOnMachineFunction(MachineFunction &MF); 75 virtual const char *getPassName() const { return "Tail Duplication"; } 76 77 private: 78 void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 79 MachineBasicBlock *BB); 80 void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 81 MachineBasicBlock *PredBB, 82 DenseMap<unsigned, unsigned> &LocalVRMap, 83 SmallVector<std::pair<unsigned,unsigned>, 4> &Copies); 84 void DuplicateInstruction(MachineInstr *MI, 85 MachineBasicBlock *TailBB, 86 MachineBasicBlock *PredBB, 87 MachineFunction &MF, 88 DenseMap<unsigned, unsigned> &LocalVRMap); 89 void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 90 SmallVector<MachineBasicBlock*, 8> &TDBBs, 91 SmallSetVector<MachineBasicBlock*, 8> &Succs); 92 bool TailDuplicateBlocks(MachineFunction &MF); 93 bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 94 SmallVector<MachineBasicBlock*, 8> &TDBBs, 95 SmallVector<MachineInstr*, 16> &Copies); 96 void RemoveDeadBlock(MachineBasicBlock *MBB); 97 }; 98 99 char TailDuplicatePass::ID = 0; 100} 101 102FunctionPass *llvm::createTailDuplicatePass(bool PreRegAlloc) { 103 return new TailDuplicatePass(PreRegAlloc); 104} 105 106bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 107 TII = MF.getTarget().getInstrInfo(); 108 MRI = &MF.getRegInfo(); 109 MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 110 111 bool MadeChange = false; 112 while (TailDuplicateBlocks(MF)) 113 MadeChange = true; 114 115 return MadeChange; 116} 117 118static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 119 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 120 MachineBasicBlock *MBB = I; 121 SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 122 MBB->pred_end()); 123 MachineBasicBlock::iterator MI = MBB->begin(); 124 while (MI != MBB->end()) { 125 if (!MI->isPHI()) 126 break; 127 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 128 PE = Preds.end(); PI != PE; ++PI) { 129 MachineBasicBlock *PredBB = *PI; 130 bool Found = false; 131 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 132 MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 133 if (PHIBB == PredBB) { 134 Found = true; 135 break; 136 } 137 } 138 if (!Found) { 139 dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 140 dbgs() << " missing input from predecessor BB#" 141 << PredBB->getNumber() << '\n'; 142 llvm_unreachable(0); 143 } 144 } 145 146 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 147 MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 148 if (CheckExtra && !Preds.count(PHIBB)) { 149 // This is not a hard error. 150 dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 151 << ": " << *MI; 152 dbgs() << " extra input from predecessor BB#" 153 << PHIBB->getNumber() << '\n'; 154 } 155 if (PHIBB->getNumber() < 0) { 156 dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 157 dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 158 llvm_unreachable(0); 159 } 160 } 161 ++MI; 162 } 163 } 164} 165 166/// TailDuplicateBlocks - Look for small blocks that are unconditionally 167/// branched to and do not fall through. Tail-duplicate their instructions 168/// into their predecessors to eliminate (dynamic) branches. 169bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 170 bool MadeChange = false; 171 172 if (PreRegAlloc && TailDupVerify) { 173 DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 174 VerifyPHIs(MF, true); 175 } 176 177 SmallVector<MachineInstr*, 8> NewPHIs; 178 MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 179 180 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 181 MachineBasicBlock *MBB = I++; 182 183 if (NumTails == TailDupLimit) 184 break; 185 186 // Only duplicate blocks that end with unconditional branches. 187 if (MBB->canFallThrough()) 188 continue; 189 190 // Save the successors list. 191 SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 192 MBB->succ_end()); 193 194 SmallVector<MachineBasicBlock*, 8> TDBBs; 195 SmallVector<MachineInstr*, 16> Copies; 196 if (TailDuplicate(MBB, MF, TDBBs, Copies)) { 197 ++NumTails; 198 199 // TailBB's immediate successors are now successors of those predecessors 200 // which duplicated TailBB. Add the predecessors as sources to the PHI 201 // instructions. 202 bool isDead = MBB->pred_empty(); 203 if (PreRegAlloc) 204 UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 205 206 // If it is dead, remove it. 207 if (isDead) { 208 NumInstrDups -= MBB->size(); 209 RemoveDeadBlock(MBB); 210 ++NumDeadBlocks; 211 } 212 213 // Update SSA form. 214 if (!SSAUpdateVRs.empty()) { 215 for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 216 unsigned VReg = SSAUpdateVRs[i]; 217 SSAUpdate.Initialize(VReg); 218 219 // If the original definition is still around, add it as an available 220 // value. 221 MachineInstr *DefMI = MRI->getVRegDef(VReg); 222 MachineBasicBlock *DefBB = 0; 223 if (DefMI) { 224 DefBB = DefMI->getParent(); 225 SSAUpdate.AddAvailableValue(DefBB, VReg); 226 } 227 228 // Add the new vregs as available values. 229 DenseMap<unsigned, AvailableValsTy>::iterator LI = 230 SSAUpdateVals.find(VReg); 231 for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 232 MachineBasicBlock *SrcBB = LI->second[j].first; 233 unsigned SrcReg = LI->second[j].second; 234 SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 235 } 236 237 // Rewrite uses that are outside of the original def's block. 238 MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 239 while (UI != MRI->use_end()) { 240 MachineOperand &UseMO = UI.getOperand(); 241 MachineInstr *UseMI = &*UI; 242 ++UI; 243 if (UseMI->getParent() == DefBB) 244 continue; 245 SSAUpdate.RewriteUse(UseMO); 246 } 247 } 248 249 SSAUpdateVRs.clear(); 250 SSAUpdateVals.clear(); 251 } 252 253 // Eliminate some of the copies inserted by tail duplication to maintain 254 // SSA form. 255 for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 256 MachineInstr *Copy = Copies[i]; 257 if (!Copy->isCopy()) 258 continue; 259 unsigned Dst = Copy->getOperand(0).getReg(); 260 unsigned Src = Copy->getOperand(1).getReg(); 261 MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); 262 if (++UI == MRI->use_end()) { 263 // Copy is the only use. Do trivial copy propagation here. 264 MRI->replaceRegWith(Dst, Src); 265 Copy->eraseFromParent(); 266 } 267 } 268 269 if (PreRegAlloc && TailDupVerify) 270 VerifyPHIs(MF, false); 271 MadeChange = true; 272 } 273 } 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 (!Reg || TargetRegisterInfo::isPhysicalRegister(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/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 452/// of its predecessors. 453bool 454TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 455 SmallVector<MachineBasicBlock*, 8> &TDBBs, 456 SmallVector<MachineInstr*, 16> &Copies) { 457 // Set the limit on the number of instructions to duplicate, with a default 458 // of one less than the tail-merge threshold. When optimizing for size, 459 // duplicate only one, because one branch instruction can be eliminated to 460 // compensate for the duplication. 461 unsigned MaxDuplicateCount; 462 if (MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 463 MaxDuplicateCount = 1; 464 else 465 MaxDuplicateCount = TailDuplicateSize; 466 467 if (PreRegAlloc) { 468 // Pre-regalloc tail duplication hurts compile time and doesn't help 469 // much except for indirect branches. 470 if (TailBB->empty() || !TailBB->back().getDesc().isIndirectBranch()) 471 return false; 472 // If the target has hardware branch prediction that can handle indirect 473 // branches, duplicating them can often make them predictable when there 474 // are common paths through the code. The limit needs to be high enough 475 // to allow undoing the effects of tail merging and other optimizations 476 // that rearrange the predecessors of the indirect branch. 477 MaxDuplicateCount = 20; 478 } 479 480 // Don't try to tail-duplicate single-block loops. 481 if (TailBB->isSuccessor(TailBB)) 482 return false; 483 484 // Check the instructions in the block to determine whether tail-duplication 485 // is invalid or unlikely to be profitable. 486 unsigned InstrCount = 0; 487 bool HasCall = false; 488 for (MachineBasicBlock::iterator I = TailBB->begin(); 489 I != TailBB->end(); ++I) { 490 // Non-duplicable things shouldn't be tail-duplicated. 491 if (I->getDesc().isNotDuplicable()) return false; 492 // Do not duplicate 'return' instructions if this is a pre-regalloc run. 493 // A return may expand into a lot more instructions (e.g. reload of callee 494 // saved registers) after PEI. 495 if (PreRegAlloc && I->getDesc().isReturn()) return false; 496 // Don't duplicate more than the threshold. 497 if (InstrCount == MaxDuplicateCount) return false; 498 // Remember if we saw a call. 499 if (I->getDesc().isCall()) HasCall = true; 500 if (!I->isPHI() && !I->isDebugValue()) 501 InstrCount += 1; 502 } 503 // Heuristically, don't tail-duplicate calls if it would expand code size, 504 // as it's less likely to be worth the extra cost. 505 if (InstrCount > 1 && HasCall) 506 return false; 507 508 DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 509 510 // Iterate through all the unique predecessors and tail-duplicate this 511 // block into them, if possible. Copying the list ahead of time also 512 // avoids trouble with the predecessor list reallocating. 513 bool Changed = false; 514 SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 515 TailBB->pred_end()); 516 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 517 PE = Preds.end(); PI != PE; ++PI) { 518 MachineBasicBlock *PredBB = *PI; 519 520 assert(TailBB != PredBB && 521 "Single-block loop should have been rejected earlier!"); 522 if (PredBB->succ_size() > 1) continue; 523 524 MachineBasicBlock *PredTBB, *PredFBB; 525 SmallVector<MachineOperand, 4> PredCond; 526 if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 527 continue; 528 if (!PredCond.empty()) 529 continue; 530 // EH edges are ignored by AnalyzeBranch. 531 if (PredBB->succ_size() != 1) 532 continue; 533 // Don't duplicate into a fall-through predecessor (at least for now). 534 if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 535 continue; 536 537 DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 538 << "From Succ: " << *TailBB); 539 540 TDBBs.push_back(PredBB); 541 542 // Remove PredBB's unconditional branch. 543 TII->RemoveBranch(*PredBB); 544 545 // Clone the contents of TailBB into PredBB. 546 DenseMap<unsigned, unsigned> LocalVRMap; 547 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 548 MachineBasicBlock::iterator I = TailBB->begin(); 549 while (I != TailBB->end()) { 550 MachineInstr *MI = &*I; 551 ++I; 552 if (MI->isPHI()) { 553 // Replace the uses of the def of the PHI with the register coming 554 // from PredBB. 555 ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos); 556 } else { 557 // Replace def of virtual registers with new registers, and update 558 // uses with PHI source register or the new registers. 559 DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap); 560 } 561 } 562 MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 563 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 564 Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 565 TII->get(TargetOpcode::COPY), 566 CopyInfos[i].first).addReg(CopyInfos[i].second)); 567 } 568 NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 569 570 // Update the CFG. 571 PredBB->removeSuccessor(PredBB->succ_begin()); 572 assert(PredBB->succ_empty() && 573 "TailDuplicate called on block with multiple successors!"); 574 for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 575 E = TailBB->succ_end(); I != E; ++I) 576 PredBB->addSuccessor(*I); 577 578 Changed = true; 579 ++NumTailDups; 580 } 581 582 // If TailBB was duplicated into all its predecessors except for the prior 583 // block, which falls through unconditionally, move the contents of this 584 // block into the prior block. 585 MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 586 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 587 SmallVector<MachineOperand, 4> PriorCond; 588 bool PriorUnAnalyzable = 589 TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true); 590 // This has to check PrevBB->succ_size() because EH edges are ignored by 591 // AnalyzeBranch. 592 if (!PriorUnAnalyzable && PriorCond.empty() && !PriorTBB && 593 TailBB->pred_size() == 1 && PrevBB->succ_size() == 1 && 594 !TailBB->hasAddressTaken()) { 595 DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 596 << "From MBB: " << *TailBB); 597 if (PreRegAlloc) { 598 DenseMap<unsigned, unsigned> LocalVRMap; 599 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 600 MachineBasicBlock::iterator I = TailBB->begin(); 601 // Process PHI instructions first. 602 while (I != TailBB->end() && I->isPHI()) { 603 // Replace the uses of the def of the PHI with the register coming 604 // from PredBB. 605 MachineInstr *MI = &*I++; 606 ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos); 607 if (MI->getParent()) 608 MI->eraseFromParent(); 609 } 610 611 // Now copy the non-PHI instructions. 612 while (I != TailBB->end()) { 613 // Replace def of virtual registers with new registers, and update 614 // uses with PHI source register or the new registers. 615 MachineInstr *MI = &*I++; 616 DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap); 617 MI->eraseFromParent(); 618 } 619 MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 620 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 621 Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 622 TII->get(TargetOpcode::COPY), 623 CopyInfos[i].first) 624 .addReg(CopyInfos[i].second)); 625 } 626 } else { 627 // No PHIs to worry about, just splice the instructions over. 628 PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 629 } 630 PrevBB->removeSuccessor(PrevBB->succ_begin()); 631 assert(PrevBB->succ_empty()); 632 PrevBB->transferSuccessors(TailBB); 633 TDBBs.push_back(PrevBB); 634 Changed = true; 635 } 636 637 return Changed; 638} 639 640/// RemoveDeadBlock - Remove the specified dead machine basic block from the 641/// function, updating the CFG. 642void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 643 assert(MBB->pred_empty() && "MBB must be dead!"); 644 DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 645 646 // Remove all successors. 647 while (!MBB->succ_empty()) 648 MBB->removeSuccessor(MBB->succ_end()-1); 649 650 // Remove the block. 651 MBB->eraseFromParent(); 652} 653 654