TailDuplication.cpp revision 202375
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/MachineRegisterInfo.h" 21#include "llvm/CodeGen/MachineSSAUpdater.h" 22#include "llvm/Target/TargetInstrInfo.h" 23#include "llvm/Support/CommandLine.h" 24#include "llvm/Support/Debug.h" 25#include "llvm/Support/ErrorHandling.h" 26#include "llvm/Support/raw_ostream.h" 27#include "llvm/ADT/SmallSet.h" 28#include "llvm/ADT/SetVector.h" 29#include "llvm/ADT/Statistic.h" 30using namespace llvm; 31 32STATISTIC(NumTails , "Number of tails duplicated"); 33STATISTIC(NumTailDups , "Number of tail duplicated blocks"); 34STATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 35STATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 36 37// Heuristic for tail duplication. 38static cl::opt<unsigned> 39TailDuplicateSize("tail-dup-size", 40 cl::desc("Maximum instructions to consider tail duplicating"), 41 cl::init(2), cl::Hidden); 42 43static cl::opt<bool> 44TailDupVerify("tail-dup-verify", 45 cl::desc("Verify sanity of PHI instructions during taildup"), 46 cl::init(false), cl::Hidden); 47 48static cl::opt<unsigned> 49TailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 50 51typedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 52 53namespace { 54 /// TailDuplicatePass - Perform tail duplication. 55 class TailDuplicatePass : public MachineFunctionPass { 56 bool PreRegAlloc; 57 const TargetInstrInfo *TII; 58 MachineModuleInfo *MMI; 59 MachineRegisterInfo *MRI; 60 61 // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 62 SmallVector<unsigned, 16> SSAUpdateVRs; 63 64 // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 65 // source virtual registers. 66 DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 67 68 public: 69 static char ID; 70 explicit TailDuplicatePass(bool PreRA) : 71 MachineFunctionPass(&ID), PreRegAlloc(PreRA) {} 72 73 virtual bool runOnMachineFunction(MachineFunction &MF); 74 virtual const char *getPassName() const { return "Tail Duplication"; } 75 76 private: 77 void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 78 MachineBasicBlock *BB); 79 void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 80 MachineBasicBlock *PredBB, 81 DenseMap<unsigned, unsigned> &LocalVRMap, 82 SmallVector<std::pair<unsigned,unsigned>, 4> &Copies); 83 void DuplicateInstruction(MachineInstr *MI, 84 MachineBasicBlock *TailBB, 85 MachineBasicBlock *PredBB, 86 MachineFunction &MF, 87 DenseMap<unsigned, unsigned> &LocalVRMap); 88 void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 89 SmallVector<MachineBasicBlock*, 8> &TDBBs, 90 SmallSetVector<MachineBasicBlock*, 8> &Succs); 91 bool TailDuplicateBlocks(MachineFunction &MF); 92 bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 93 SmallVector<MachineBasicBlock*, 8> &TDBBs, 94 SmallVector<MachineInstr*, 16> &Copies); 95 void RemoveDeadBlock(MachineBasicBlock *MBB); 96 }; 97 98 char TailDuplicatePass::ID = 0; 99} 100 101FunctionPass *llvm::createTailDuplicatePass(bool PreRegAlloc) { 102 return new TailDuplicatePass(PreRegAlloc); 103} 104 105bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 106 TII = MF.getTarget().getInstrInfo(); 107 MRI = &MF.getRegInfo(); 108 MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 109 110 bool MadeChange = false; 111 bool MadeChangeThisIteration = true; 112 while (MadeChangeThisIteration) { 113 MadeChangeThisIteration = false; 114 MadeChangeThisIteration |= TailDuplicateBlocks(MF); 115 MadeChange |= MadeChangeThisIteration; 116 } 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->getOpcode() != TargetInstrInfo::PHI) 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 // Only duplicate blocks that end with unconditional branches. 190 if (MBB->canFallThrough()) 191 continue; 192 193 // Save the successors list. 194 SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 195 MBB->succ_end()); 196 197 SmallVector<MachineBasicBlock*, 8> TDBBs; 198 SmallVector<MachineInstr*, 16> Copies; 199 if (TailDuplicate(MBB, MF, TDBBs, Copies)) { 200 ++NumTails; 201 202 // TailBB's immediate successors are now successors of those predecessors 203 // which duplicated TailBB. Add the predecessors as sources to the PHI 204 // instructions. 205 bool isDead = MBB->pred_empty(); 206 if (PreRegAlloc) 207 UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 208 209 // If it is dead, remove it. 210 if (isDead) { 211 NumInstrDups -= MBB->size(); 212 RemoveDeadBlock(MBB); 213 ++NumDeadBlocks; 214 } 215 216 // Update SSA form. 217 if (!SSAUpdateVRs.empty()) { 218 for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 219 unsigned VReg = SSAUpdateVRs[i]; 220 SSAUpdate.Initialize(VReg); 221 222 // If the original definition is still around, add it as an available 223 // value. 224 MachineInstr *DefMI = MRI->getVRegDef(VReg); 225 MachineBasicBlock *DefBB = 0; 226 if (DefMI) { 227 DefBB = DefMI->getParent(); 228 SSAUpdate.AddAvailableValue(DefBB, VReg); 229 } 230 231 // Add the new vregs as available values. 232 DenseMap<unsigned, AvailableValsTy>::iterator LI = 233 SSAUpdateVals.find(VReg); 234 for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 235 MachineBasicBlock *SrcBB = LI->second[j].first; 236 unsigned SrcReg = LI->second[j].second; 237 SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 238 } 239 240 // Rewrite uses that are outside of the original def's block. 241 MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 242 while (UI != MRI->use_end()) { 243 MachineOperand &UseMO = UI.getOperand(); 244 MachineInstr *UseMI = &*UI; 245 ++UI; 246 if (UseMI->getParent() == DefBB) 247 continue; 248 SSAUpdate.RewriteUse(UseMO); 249 } 250 } 251 252 SSAUpdateVRs.clear(); 253 SSAUpdateVals.clear(); 254 } 255 256 // Eliminate some of the copies inserted by tail duplication to maintain 257 // SSA form. 258 for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 259 MachineInstr *Copy = Copies[i]; 260 unsigned Src, Dst, SrcSR, DstSR; 261 if (TII->isMoveInstr(*Copy, Src, Dst, SrcSR, DstSR)) { 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 271 if (PreRegAlloc && TailDupVerify) 272 VerifyPHIs(MF, false); 273 MadeChange = true; 274 } 275 } 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 (!Reg || TargetRegisterInfo::isPhysicalRegister(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->getOpcode() != TargetInstrInfo::PHI) 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 II->RemoveOperand(Idx+1); 411 II->RemoveOperand(Idx); 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 II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 420 II->addOperand(MachineOperand::CreateMBB(SrcBB)); 421 } 422 } else { 423 // Live in tail block, must also be live in predecessors. 424 for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 425 MachineBasicBlock *SrcBB = TDBBs[j]; 426 II->addOperand(MachineOperand::CreateReg(Reg, false)); 427 II->addOperand(MachineOperand::CreateMBB(SrcBB)); 428 } 429 } 430 } 431 } 432} 433 434/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 435/// of its predecessors. 436bool 437TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 438 SmallVector<MachineBasicBlock*, 8> &TDBBs, 439 SmallVector<MachineInstr*, 16> &Copies) { 440 // Pre-regalloc tail duplication hurts compile time and doesn't help 441 // much except for indirect branches. 442 bool hasIndirectBranch = (!TailBB->empty() && 443 TailBB->back().getDesc().isIndirectBranch()); 444 if (PreRegAlloc && !hasIndirectBranch) 445 return false; 446 447 // Set the limit on the number of instructions to duplicate, with a default 448 // of one less than the tail-merge threshold. When optimizing for size, 449 // duplicate only one, because one branch instruction can be eliminated to 450 // compensate for the duplication. 451 unsigned MaxDuplicateCount; 452 if (hasIndirectBranch) 453 // If the target has hardware branch prediction that can handle indirect 454 // branches, duplicating them can often make them predictable when there 455 // are common paths through the code. The limit needs to be high enough 456 // to allow undoing the effects of tail merging. 457 MaxDuplicateCount = 20; 458 else if (MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 459 MaxDuplicateCount = 1; 460 else 461 MaxDuplicateCount = TailDuplicateSize; 462 463 // Don't try to tail-duplicate single-block loops. 464 if (TailBB->isSuccessor(TailBB)) 465 return false; 466 467 // Check the instructions in the block to determine whether tail-duplication 468 // is invalid or unlikely to be profitable. 469 unsigned InstrCount = 0; 470 bool HasCall = false; 471 for (MachineBasicBlock::iterator I = TailBB->begin(); 472 I != TailBB->end(); ++I) { 473 // Non-duplicable things shouldn't be tail-duplicated. 474 if (I->getDesc().isNotDuplicable()) return false; 475 // Do not duplicate 'return' instructions if this is a pre-regalloc run. 476 // A return may expand into a lot more instructions (e.g. reload of callee 477 // saved registers) after PEI. 478 if (PreRegAlloc && I->getDesc().isReturn()) return false; 479 // Don't duplicate more than the threshold. 480 if (InstrCount == MaxDuplicateCount) return false; 481 // Remember if we saw a call. 482 if (I->getDesc().isCall()) HasCall = true; 483 if (I->getOpcode() != TargetInstrInfo::PHI) 484 InstrCount += 1; 485 } 486 // Heuristically, don't tail-duplicate calls if it would expand code size, 487 // as it's less likely to be worth the extra cost. 488 if (InstrCount > 1 && HasCall) 489 return false; 490 491 DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 492 493 // Iterate through all the unique predecessors and tail-duplicate this 494 // block into them, if possible. Copying the list ahead of time also 495 // avoids trouble with the predecessor list reallocating. 496 bool Changed = false; 497 SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 498 TailBB->pred_end()); 499 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 500 PE = Preds.end(); PI != PE; ++PI) { 501 MachineBasicBlock *PredBB = *PI; 502 503 assert(TailBB != PredBB && 504 "Single-block loop should have been rejected earlier!"); 505 if (PredBB->succ_size() > 1) continue; 506 507 MachineBasicBlock *PredTBB, *PredFBB; 508 SmallVector<MachineOperand, 4> PredCond; 509 if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 510 continue; 511 if (!PredCond.empty()) 512 continue; 513 // EH edges are ignored by AnalyzeBranch. 514 if (PredBB->succ_size() != 1) 515 continue; 516 // Don't duplicate into a fall-through predecessor (at least for now). 517 if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 518 continue; 519 520 DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 521 << "From Succ: " << *TailBB); 522 523 TDBBs.push_back(PredBB); 524 525 // Remove PredBB's unconditional branch. 526 TII->RemoveBranch(*PredBB); 527 528 // Clone the contents of TailBB into PredBB. 529 DenseMap<unsigned, unsigned> LocalVRMap; 530 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 531 MachineBasicBlock::iterator I = TailBB->begin(); 532 while (I != TailBB->end()) { 533 MachineInstr *MI = &*I; 534 ++I; 535 if (MI->getOpcode() == TargetInstrInfo::PHI) { 536 // Replace the uses of the def of the PHI with the register coming 537 // from PredBB. 538 ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos); 539 } else { 540 // Replace def of virtual registers with new registers, and update 541 // uses with PHI source register or the new registers. 542 DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap); 543 } 544 } 545 MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 546 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 547 const TargetRegisterClass *RC = MRI->getRegClass(CopyInfos[i].first); 548 TII->copyRegToReg(*PredBB, Loc, CopyInfos[i].first, 549 CopyInfos[i].second, RC,RC); 550 MachineInstr *CopyMI = prior(Loc); 551 Copies.push_back(CopyMI); 552 } 553 NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 554 555 // Update the CFG. 556 PredBB->removeSuccessor(PredBB->succ_begin()); 557 assert(PredBB->succ_empty() && 558 "TailDuplicate called on block with multiple successors!"); 559 for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 560 E = TailBB->succ_end(); I != E; ++I) 561 PredBB->addSuccessor(*I); 562 563 Changed = true; 564 ++NumTailDups; 565 } 566 567 // If TailBB was duplicated into all its predecessors except for the prior 568 // block, which falls through unconditionally, move the contents of this 569 // block into the prior block. 570 MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 571 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 572 SmallVector<MachineOperand, 4> PriorCond; 573 bool PriorUnAnalyzable = 574 TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true); 575 // This has to check PrevBB->succ_size() because EH edges are ignored by 576 // AnalyzeBranch. 577 if (!PriorUnAnalyzable && PriorCond.empty() && !PriorTBB && 578 TailBB->pred_size() == 1 && PrevBB->succ_size() == 1 && 579 !TailBB->hasAddressTaken()) { 580 DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 581 << "From MBB: " << *TailBB); 582 if (PreRegAlloc) { 583 DenseMap<unsigned, unsigned> LocalVRMap; 584 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 585 MachineBasicBlock::iterator I = TailBB->begin(); 586 // Process PHI instructions first. 587 while (I != TailBB->end() && I->getOpcode() == TargetInstrInfo::PHI) { 588 // Replace the uses of the def of the PHI with the register coming 589 // from PredBB. 590 MachineInstr *MI = &*I++; 591 ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos); 592 if (MI->getParent()) 593 MI->eraseFromParent(); 594 } 595 596 // Now copy the non-PHI instructions. 597 while (I != TailBB->end()) { 598 // Replace def of virtual registers with new registers, and update 599 // uses with PHI source register or the new registers. 600 MachineInstr *MI = &*I++; 601 DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap); 602 MI->eraseFromParent(); 603 } 604 MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 605 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 606 const TargetRegisterClass *RC = MRI->getRegClass(CopyInfos[i].first); 607 TII->copyRegToReg(*PrevBB, Loc, CopyInfos[i].first, 608 CopyInfos[i].second, RC, RC); 609 MachineInstr *CopyMI = prior(Loc); 610 Copies.push_back(CopyMI); 611 } 612 } else { 613 // No PHIs to worry about, just splice the instructions over. 614 PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 615 } 616 PrevBB->removeSuccessor(PrevBB->succ_begin()); 617 assert(PrevBB->succ_empty()); 618 PrevBB->transferSuccessors(TailBB); 619 TDBBs.push_back(PrevBB); 620 Changed = true; 621 } 622 623 return Changed; 624} 625 626/// RemoveDeadBlock - Remove the specified dead machine basic block from the 627/// function, updating the CFG. 628void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 629 assert(MBB->pred_empty() && "MBB must be dead!"); 630 DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 631 632 // Remove all successors. 633 while (!MBB->succ_empty()) 634 MBB->removeSuccessor(MBB->succ_end()-1); 635 636 // If there are any labels in the basic block, unregister them from 637 // MachineModuleInfo. 638 if (MMI && !MBB->empty()) { 639 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 640 I != E; ++I) { 641 if (I->isLabel()) 642 // The label ID # is always operand #0, an immediate. 643 MMI->InvalidateLabel(I->getOperand(0).getImm()); 644 } 645 } 646 647 // Remove the block. 648 MBB->eraseFromParent(); 649} 650 651