TailDuplication.cpp revision 210299
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 unsigned Src, Dst, SrcSR, DstSR; 258 if (TII->isMoveInstr(*Copy, Src, Dst, SrcSR, DstSR)) { 259 MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); 260 if (++UI == MRI->use_end()) { 261 // Copy is the only use. Do trivial copy propagation here. 262 MRI->replaceRegWith(Dst, Src); 263 Copy->eraseFromParent(); 264 } 265 } 266 } 267 268 if (PreRegAlloc && TailDupVerify) 269 VerifyPHIs(MF, false); 270 MadeChange = true; 271 } 272 } 273 274 return MadeChange; 275} 276 277static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 278 const MachineRegisterInfo *MRI) { 279 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 280 UE = MRI->use_end(); UI != UE; ++UI) { 281 MachineInstr *UseMI = &*UI; 282 if (UseMI->getParent() != BB) 283 return true; 284 } 285 return false; 286} 287 288static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 289 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 290 if (MI->getOperand(i+1).getMBB() == SrcBB) 291 return i; 292 return 0; 293} 294 295/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 296/// SSA update. 297void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 298 MachineBasicBlock *BB) { 299 DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 300 if (LI != SSAUpdateVals.end()) 301 LI->second.push_back(std::make_pair(BB, NewReg)); 302 else { 303 AvailableValsTy Vals; 304 Vals.push_back(std::make_pair(BB, NewReg)); 305 SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 306 SSAUpdateVRs.push_back(OrigReg); 307 } 308} 309 310/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 311/// Remember the source register that's contributed by PredBB and update SSA 312/// update map. 313void TailDuplicatePass::ProcessPHI(MachineInstr *MI, 314 MachineBasicBlock *TailBB, 315 MachineBasicBlock *PredBB, 316 DenseMap<unsigned, unsigned> &LocalVRMap, 317 SmallVector<std::pair<unsigned,unsigned>, 4> &Copies) { 318 unsigned DefReg = MI->getOperand(0).getReg(); 319 unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 320 assert(SrcOpIdx && "Unable to find matching PHI source?"); 321 unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 322 const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 323 LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 324 325 // Insert a copy from source to the end of the block. The def register is the 326 // available value liveout of the block. 327 unsigned NewDef = MRI->createVirtualRegister(RC); 328 Copies.push_back(std::make_pair(NewDef, SrcReg)); 329 if (isDefLiveOut(DefReg, TailBB, MRI)) 330 AddSSAUpdateEntry(DefReg, NewDef, PredBB); 331 332 // Remove PredBB from the PHI node. 333 MI->RemoveOperand(SrcOpIdx+1); 334 MI->RemoveOperand(SrcOpIdx); 335 if (MI->getNumOperands() == 1) 336 MI->eraseFromParent(); 337} 338 339/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 340/// the source operands due to earlier PHI translation. 341void TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 342 MachineBasicBlock *TailBB, 343 MachineBasicBlock *PredBB, 344 MachineFunction &MF, 345 DenseMap<unsigned, unsigned> &LocalVRMap) { 346 MachineInstr *NewMI = TII->duplicate(MI, MF); 347 for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 348 MachineOperand &MO = NewMI->getOperand(i); 349 if (!MO.isReg()) 350 continue; 351 unsigned Reg = MO.getReg(); 352 if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) 353 continue; 354 if (MO.isDef()) { 355 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 356 unsigned NewReg = MRI->createVirtualRegister(RC); 357 MO.setReg(NewReg); 358 LocalVRMap.insert(std::make_pair(Reg, NewReg)); 359 if (isDefLiveOut(Reg, TailBB, MRI)) 360 AddSSAUpdateEntry(Reg, NewReg, PredBB); 361 } else { 362 DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 363 if (VI != LocalVRMap.end()) 364 MO.setReg(VI->second); 365 } 366 } 367 PredBB->insert(PredBB->end(), NewMI); 368} 369 370/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 371/// blocks, the successors have gained new predecessors. Update the PHI 372/// instructions in them accordingly. 373void 374TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 375 SmallVector<MachineBasicBlock*, 8> &TDBBs, 376 SmallSetVector<MachineBasicBlock*,8> &Succs) { 377 for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 378 SE = Succs.end(); SI != SE; ++SI) { 379 MachineBasicBlock *SuccBB = *SI; 380 for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 381 II != EE; ++II) { 382 if (!II->isPHI()) 383 break; 384 unsigned Idx = 0; 385 for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 386 MachineOperand &MO = II->getOperand(i+1); 387 if (MO.getMBB() == FromBB) { 388 Idx = i; 389 break; 390 } 391 } 392 393 assert(Idx != 0); 394 MachineOperand &MO0 = II->getOperand(Idx); 395 unsigned Reg = MO0.getReg(); 396 if (isDead) { 397 // Folded into the previous BB. 398 // There could be duplicate phi source entries. FIXME: Should sdisel 399 // or earlier pass fixed this? 400 for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 401 MachineOperand &MO = II->getOperand(i+1); 402 if (MO.getMBB() == FromBB) { 403 II->RemoveOperand(i+1); 404 II->RemoveOperand(i); 405 } 406 } 407 } else 408 Idx = 0; 409 410 // If Idx is set, the operands at Idx and Idx+1 must be removed. 411 // We reuse the location to avoid expensive RemoveOperand calls. 412 413 DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 414 if (LI != SSAUpdateVals.end()) { 415 // This register is defined in the tail block. 416 for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 417 MachineBasicBlock *SrcBB = LI->second[j].first; 418 unsigned SrcReg = LI->second[j].second; 419 if (Idx != 0) { 420 II->getOperand(Idx).setReg(SrcReg); 421 II->getOperand(Idx+1).setMBB(SrcBB); 422 Idx = 0; 423 } else { 424 II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 425 II->addOperand(MachineOperand::CreateMBB(SrcBB)); 426 } 427 } 428 } else { 429 // Live in tail block, must also be live in predecessors. 430 for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 431 MachineBasicBlock *SrcBB = TDBBs[j]; 432 if (Idx != 0) { 433 II->getOperand(Idx).setReg(Reg); 434 II->getOperand(Idx+1).setMBB(SrcBB); 435 Idx = 0; 436 } else { 437 II->addOperand(MachineOperand::CreateReg(Reg, false)); 438 II->addOperand(MachineOperand::CreateMBB(SrcBB)); 439 } 440 } 441 } 442 if (Idx != 0) { 443 II->RemoveOperand(Idx+1); 444 II->RemoveOperand(Idx); 445 } 446 } 447 } 448} 449 450/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 451/// of its predecessors. 452bool 453TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 454 SmallVector<MachineBasicBlock*, 8> &TDBBs, 455 SmallVector<MachineInstr*, 16> &Copies) { 456 // Set the limit on the number of instructions to duplicate, with a default 457 // of one less than the tail-merge threshold. When optimizing for size, 458 // duplicate only one, because one branch instruction can be eliminated to 459 // compensate for the duplication. 460 unsigned MaxDuplicateCount; 461 if (MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 462 MaxDuplicateCount = 1; 463 else 464 MaxDuplicateCount = TailDuplicateSize; 465 466 if (PreRegAlloc) { 467 // Pre-regalloc tail duplication hurts compile time and doesn't help 468 // much except for indirect branches. 469 if (TailBB->empty() || !TailBB->back().getDesc().isIndirectBranch()) 470 return false; 471 // If the target has hardware branch prediction that can handle indirect 472 // branches, duplicating them can often make them predictable when there 473 // are common paths through the code. The limit needs to be high enough 474 // to allow undoing the effects of tail merging and other optimizations 475 // that rearrange the predecessors of the indirect branch. 476 MaxDuplicateCount = 20; 477 } 478 479 // Don't try to tail-duplicate single-block loops. 480 if (TailBB->isSuccessor(TailBB)) 481 return false; 482 483 // Check the instructions in the block to determine whether tail-duplication 484 // is invalid or unlikely to be profitable. 485 unsigned InstrCount = 0; 486 bool HasCall = false; 487 for (MachineBasicBlock::iterator I = TailBB->begin(); 488 I != TailBB->end(); ++I) { 489 // Non-duplicable things shouldn't be tail-duplicated. 490 if (I->getDesc().isNotDuplicable()) return false; 491 // Do not duplicate 'return' instructions if this is a pre-regalloc run. 492 // A return may expand into a lot more instructions (e.g. reload of callee 493 // saved registers) after PEI. 494 if (PreRegAlloc && I->getDesc().isReturn()) return false; 495 // Don't duplicate more than the threshold. 496 if (InstrCount == MaxDuplicateCount) return false; 497 // Remember if we saw a call. 498 if (I->getDesc().isCall()) HasCall = true; 499 if (!I->isPHI() && !I->isDebugValue()) 500 InstrCount += 1; 501 } 502 // Heuristically, don't tail-duplicate calls if it would expand code size, 503 // as it's less likely to be worth the extra cost. 504 if (InstrCount > 1 && HasCall) 505 return false; 506 507 DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 508 509 // Iterate through all the unique predecessors and tail-duplicate this 510 // block into them, if possible. Copying the list ahead of time also 511 // avoids trouble with the predecessor list reallocating. 512 bool Changed = false; 513 SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 514 TailBB->pred_end()); 515 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 516 PE = Preds.end(); PI != PE; ++PI) { 517 MachineBasicBlock *PredBB = *PI; 518 519 assert(TailBB != PredBB && 520 "Single-block loop should have been rejected earlier!"); 521 if (PredBB->succ_size() > 1) continue; 522 523 MachineBasicBlock *PredTBB, *PredFBB; 524 SmallVector<MachineOperand, 4> PredCond; 525 if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 526 continue; 527 if (!PredCond.empty()) 528 continue; 529 // EH edges are ignored by AnalyzeBranch. 530 if (PredBB->succ_size() != 1) 531 continue; 532 // Don't duplicate into a fall-through predecessor (at least for now). 533 if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 534 continue; 535 536 DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 537 << "From Succ: " << *TailBB); 538 539 TDBBs.push_back(PredBB); 540 541 // Remove PredBB's unconditional branch. 542 TII->RemoveBranch(*PredBB); 543 544 // Clone the contents of TailBB into PredBB. 545 DenseMap<unsigned, unsigned> LocalVRMap; 546 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 547 MachineBasicBlock::iterator I = TailBB->begin(); 548 while (I != TailBB->end()) { 549 MachineInstr *MI = &*I; 550 ++I; 551 if (MI->isPHI()) { 552 // Replace the uses of the def of the PHI with the register coming 553 // from PredBB. 554 ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos); 555 } else { 556 // Replace def of virtual registers with new registers, and update 557 // uses with PHI source register or the new registers. 558 DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap); 559 } 560 } 561 MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 562 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 563 Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 564 TII->get(TargetOpcode::COPY), 565 CopyInfos[i].first).addReg(CopyInfos[i].second)); 566 } 567 NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 568 569 // Update the CFG. 570 PredBB->removeSuccessor(PredBB->succ_begin()); 571 assert(PredBB->succ_empty() && 572 "TailDuplicate called on block with multiple successors!"); 573 for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 574 E = TailBB->succ_end(); I != E; ++I) 575 PredBB->addSuccessor(*I); 576 577 Changed = true; 578 ++NumTailDups; 579 } 580 581 // If TailBB was duplicated into all its predecessors except for the prior 582 // block, which falls through unconditionally, move the contents of this 583 // block into the prior block. 584 MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 585 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 586 SmallVector<MachineOperand, 4> PriorCond; 587 bool PriorUnAnalyzable = 588 TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true); 589 // This has to check PrevBB->succ_size() because EH edges are ignored by 590 // AnalyzeBranch. 591 if (!PriorUnAnalyzable && PriorCond.empty() && !PriorTBB && 592 TailBB->pred_size() == 1 && PrevBB->succ_size() == 1 && 593 !TailBB->hasAddressTaken()) { 594 DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 595 << "From MBB: " << *TailBB); 596 if (PreRegAlloc) { 597 DenseMap<unsigned, unsigned> LocalVRMap; 598 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 599 MachineBasicBlock::iterator I = TailBB->begin(); 600 // Process PHI instructions first. 601 while (I != TailBB->end() && I->isPHI()) { 602 // Replace the uses of the def of the PHI with the register coming 603 // from PredBB. 604 MachineInstr *MI = &*I++; 605 ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos); 606 if (MI->getParent()) 607 MI->eraseFromParent(); 608 } 609 610 // Now copy the non-PHI instructions. 611 while (I != TailBB->end()) { 612 // Replace def of virtual registers with new registers, and update 613 // uses with PHI source register or the new registers. 614 MachineInstr *MI = &*I++; 615 DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap); 616 MI->eraseFromParent(); 617 } 618 MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 619 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 620 Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 621 TII->get(TargetOpcode::COPY), 622 CopyInfos[i].first) 623 .addReg(CopyInfos[i].second)); 624 } 625 } else { 626 // No PHIs to worry about, just splice the instructions over. 627 PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 628 } 629 PrevBB->removeSuccessor(PrevBB->succ_begin()); 630 assert(PrevBB->succ_empty()); 631 PrevBB->transferSuccessors(TailBB); 632 TDBBs.push_back(PrevBB); 633 Changed = true; 634 } 635 636 return Changed; 637} 638 639/// RemoveDeadBlock - Remove the specified dead machine basic block from the 640/// function, updating the CFG. 641void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 642 assert(MBB->pred_empty() && "MBB must be dead!"); 643 DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 644 645 // Remove all successors. 646 while (!MBB->succ_empty()) 647 MBB->removeSuccessor(MBB->succ_end()-1); 648 649 // Remove the block. 650 MBB->eraseFromParent(); 651} 652 653