TailDuplication.cpp revision 205218
133965Sjdp//===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===// 233965Sjdp// 333965Sjdp// The LLVM Compiler Infrastructure 433965Sjdp// 533965Sjdp// This file is distributed under the University of Illinois Open Source 633965Sjdp// License. See LICENSE.TXT for details. 733965Sjdp// 833965Sjdp//===----------------------------------------------------------------------===// 933965Sjdp// 1033965Sjdp// This pass duplicates basic blocks ending in unconditional branches into 1133965Sjdp// the tails of their predecessors. 1233965Sjdp// 1333965Sjdp//===----------------------------------------------------------------------===// 1433965Sjdp 1533965Sjdp#define DEBUG_TYPE "tailduplication" 1633965Sjdp#include "llvm/Function.h" 1733965Sjdp#include "llvm/CodeGen/Passes.h" 1833965Sjdp#include "llvm/CodeGen/MachineModuleInfo.h" 1933965Sjdp#include "llvm/CodeGen/MachineFunctionPass.h" 2033965Sjdp#include "llvm/CodeGen/MachineRegisterInfo.h" 2133965Sjdp#include "llvm/CodeGen/MachineSSAUpdater.h" 2233965Sjdp#include "llvm/Target/TargetInstrInfo.h" 2333965Sjdp#include "llvm/Support/CommandLine.h" 2433965Sjdp#include "llvm/Support/Debug.h" 2533965Sjdp#include "llvm/Support/ErrorHandling.h" 2633965Sjdp#include "llvm/Support/raw_ostream.h" 2733965Sjdp#include "llvm/ADT/SmallSet.h" 2833965Sjdp#include "llvm/ADT/SetVector.h" 2933965Sjdp#include "llvm/ADT/Statistic.h" 3033965Sjdpusing namespace llvm; 3133965Sjdp 3233965SjdpSTATISTIC(NumTails , "Number of tails duplicated"); 3333965SjdpSTATISTIC(NumTailDups , "Number of tail duplicated blocks"); 3433965SjdpSTATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 3533965SjdpSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 3633965Sjdp 3733965Sjdp// Heuristic for tail duplication. 3833965Sjdpstatic cl::opt<unsigned> 3933965SjdpTailDuplicateSize("tail-dup-size", 4033965Sjdp cl::desc("Maximum instructions to consider tail duplicating"), 4133965Sjdp cl::init(2), cl::Hidden); 4233965Sjdp 4333965Sjdpstatic cl::opt<bool> 4433965SjdpTailDupVerify("tail-dup-verify", 4533965Sjdp cl::desc("Verify sanity of PHI instructions during taildup"), 4633965Sjdp cl::init(false), cl::Hidden); 4733965Sjdp 4833965Sjdpstatic cl::opt<unsigned> 4933965SjdpTailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 5033965Sjdp 5133965Sjdptypedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 5233965Sjdp 5333965Sjdpnamespace { 5433965Sjdp /// TailDuplicatePass - Perform tail duplication. 5533965Sjdp class TailDuplicatePass : public MachineFunctionPass { 5633965Sjdp bool PreRegAlloc; 5733965Sjdp const TargetInstrInfo *TII; 5833965Sjdp MachineModuleInfo *MMI; 5933965Sjdp MachineRegisterInfo *MRI; 6033965Sjdp 6133965Sjdp // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 6233965Sjdp 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 while (TailDuplicateBlocks(MF)) 112 MadeChange = true; 113 114 return MadeChange; 115} 116 117static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 118 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 119 MachineBasicBlock *MBB = I; 120 SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 121 MBB->pred_end()); 122 MachineBasicBlock::iterator MI = MBB->begin(); 123 while (MI != MBB->end()) { 124 if (!MI->isPHI()) 125 break; 126 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 127 PE = Preds.end(); PI != PE; ++PI) { 128 MachineBasicBlock *PredBB = *PI; 129 bool Found = false; 130 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 131 MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 132 if (PHIBB == PredBB) { 133 Found = true; 134 break; 135 } 136 } 137 if (!Found) { 138 dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 139 dbgs() << " missing input from predecessor BB#" 140 << PredBB->getNumber() << '\n'; 141 llvm_unreachable(0); 142 } 143 } 144 145 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 146 MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 147 if (CheckExtra && !Preds.count(PHIBB)) { 148 // This is not a hard error. 149 dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 150 << ": " << *MI; 151 dbgs() << " extra input from predecessor BB#" 152 << PHIBB->getNumber() << '\n'; 153 } 154 if (PHIBB->getNumber() < 0) { 155 dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 156 dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 157 llvm_unreachable(0); 158 } 159 } 160 ++MI; 161 } 162 } 163} 164 165/// TailDuplicateBlocks - Look for small blocks that are unconditionally 166/// branched to and do not fall through. Tail-duplicate their instructions 167/// into their predecessors to eliminate (dynamic) branches. 168bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 169 bool MadeChange = false; 170 171 if (PreRegAlloc && TailDupVerify) { 172 DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 173 VerifyPHIs(MF, true); 174 } 175 176 SmallVector<MachineInstr*, 8> NewPHIs; 177 MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 178 179 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 180 MachineBasicBlock *MBB = I++; 181 182 if (NumTails == TailDupLimit) 183 break; 184 185 // Only duplicate blocks that end with unconditional branches. 186 if (MBB->canFallThrough()) 187 continue; 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) 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 unsigned Src, Dst, SrcSR, DstSR; 257 if (TII->isMoveInstr(*Copy, Src, Dst, SrcSR, DstSR)) { 258 MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); 259 if (++UI == MRI->use_end()) { 260 // Copy is the only use. Do trivial copy propagation here. 261 MRI->replaceRegWith(Dst, Src); 262 Copy->eraseFromParent(); 263 } 264 } 265 } 266 267 if (PreRegAlloc && TailDupVerify) 268 VerifyPHIs(MF, false); 269 MadeChange = true; 270 } 271 } 272 273 return MadeChange; 274} 275 276static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 277 const MachineRegisterInfo *MRI) { 278 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 279 UE = MRI->use_end(); UI != UE; ++UI) { 280 MachineInstr *UseMI = &*UI; 281 if (UseMI->getParent() != BB) 282 return true; 283 } 284 return false; 285} 286 287static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 288 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 289 if (MI->getOperand(i+1).getMBB() == SrcBB) 290 return i; 291 return 0; 292} 293 294/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 295/// SSA update. 296void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 297 MachineBasicBlock *BB) { 298 DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 299 if (LI != SSAUpdateVals.end()) 300 LI->second.push_back(std::make_pair(BB, NewReg)); 301 else { 302 AvailableValsTy Vals; 303 Vals.push_back(std::make_pair(BB, NewReg)); 304 SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 305 SSAUpdateVRs.push_back(OrigReg); 306 } 307} 308 309/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 310/// Remember the source register that's contributed by PredBB and update SSA 311/// update map. 312void TailDuplicatePass::ProcessPHI(MachineInstr *MI, 313 MachineBasicBlock *TailBB, 314 MachineBasicBlock *PredBB, 315 DenseMap<unsigned, unsigned> &LocalVRMap, 316 SmallVector<std::pair<unsigned,unsigned>, 4> &Copies) { 317 unsigned DefReg = MI->getOperand(0).getReg(); 318 unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 319 assert(SrcOpIdx && "Unable to find matching PHI source?"); 320 unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 321 const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 322 LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 323 324 // Insert a copy from source to the end of the block. The def register is the 325 // available value liveout of the block. 326 unsigned NewDef = MRI->createVirtualRegister(RC); 327 Copies.push_back(std::make_pair(NewDef, SrcReg)); 328 if (isDefLiveOut(DefReg, TailBB, MRI)) 329 AddSSAUpdateEntry(DefReg, NewDef, PredBB); 330 331 // Remove PredBB from the PHI node. 332 MI->RemoveOperand(SrcOpIdx+1); 333 MI->RemoveOperand(SrcOpIdx); 334 if (MI->getNumOperands() == 1) 335 MI->eraseFromParent(); 336} 337 338/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 339/// the source operands due to earlier PHI translation. 340void TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 341 MachineBasicBlock *TailBB, 342 MachineBasicBlock *PredBB, 343 MachineFunction &MF, 344 DenseMap<unsigned, unsigned> &LocalVRMap) { 345 MachineInstr *NewMI = TII->duplicate(MI, MF); 346 for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 347 MachineOperand &MO = NewMI->getOperand(i); 348 if (!MO.isReg()) 349 continue; 350 unsigned Reg = MO.getReg(); 351 if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) 352 continue; 353 if (MO.isDef()) { 354 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 355 unsigned NewReg = MRI->createVirtualRegister(RC); 356 MO.setReg(NewReg); 357 LocalVRMap.insert(std::make_pair(Reg, NewReg)); 358 if (isDefLiveOut(Reg, TailBB, MRI)) 359 AddSSAUpdateEntry(Reg, NewReg, PredBB); 360 } else { 361 DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 362 if (VI != LocalVRMap.end()) 363 MO.setReg(VI->second); 364 } 365 } 366 PredBB->insert(PredBB->end(), NewMI); 367} 368 369/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 370/// blocks, the successors have gained new predecessors. Update the PHI 371/// instructions in them accordingly. 372void 373TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 374 SmallVector<MachineBasicBlock*, 8> &TDBBs, 375 SmallSetVector<MachineBasicBlock*,8> &Succs) { 376 for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 377 SE = Succs.end(); SI != SE; ++SI) { 378 MachineBasicBlock *SuccBB = *SI; 379 for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 380 II != EE; ++II) { 381 if (!II->isPHI()) 382 break; 383 unsigned Idx = 0; 384 for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 385 MachineOperand &MO = II->getOperand(i+1); 386 if (MO.getMBB() == FromBB) { 387 Idx = i; 388 break; 389 } 390 } 391 392 assert(Idx != 0); 393 MachineOperand &MO0 = II->getOperand(Idx); 394 unsigned Reg = MO0.getReg(); 395 if (isDead) { 396 // Folded into the previous BB. 397 // There could be duplicate phi source entries. FIXME: Should sdisel 398 // or earlier pass fixed this? 399 for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 400 MachineOperand &MO = II->getOperand(i+1); 401 if (MO.getMBB() == FromBB) { 402 II->RemoveOperand(i+1); 403 II->RemoveOperand(i); 404 } 405 } 406 } else 407 Idx = 0; 408 409 // If Idx is set, the operands at Idx and Idx+1 must be removed. 410 // We reuse the location to avoid expensive RemoveOperand calls. 411 412 DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 413 if (LI != SSAUpdateVals.end()) { 414 // This register is defined in the tail block. 415 for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 416 MachineBasicBlock *SrcBB = LI->second[j].first; 417 unsigned SrcReg = LI->second[j].second; 418 if (Idx != 0) { 419 II->getOperand(Idx).setReg(SrcReg); 420 II->getOperand(Idx+1).setMBB(SrcBB); 421 Idx = 0; 422 } else { 423 II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 424 II->addOperand(MachineOperand::CreateMBB(SrcBB)); 425 } 426 } 427 } else { 428 // Live in tail block, must also be live in predecessors. 429 for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 430 MachineBasicBlock *SrcBB = TDBBs[j]; 431 if (Idx != 0) { 432 II->getOperand(Idx).setReg(Reg); 433 II->getOperand(Idx+1).setMBB(SrcBB); 434 Idx = 0; 435 } else { 436 II->addOperand(MachineOperand::CreateReg(Reg, false)); 437 II->addOperand(MachineOperand::CreateMBB(SrcBB)); 438 } 439 } 440 } 441 if (Idx != 0) { 442 II->RemoveOperand(Idx+1); 443 II->RemoveOperand(Idx); 444 } 445 } 446 } 447} 448 449/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 450/// of its predecessors. 451bool 452TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 453 SmallVector<MachineBasicBlock*, 8> &TDBBs, 454 SmallVector<MachineInstr*, 16> &Copies) { 455 // Set the limit on the number of instructions to duplicate, with a default 456 // of one less than the tail-merge threshold. When optimizing for size, 457 // duplicate only one, because one branch instruction can be eliminated to 458 // compensate for the duplication. 459 unsigned MaxDuplicateCount; 460 if (MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 461 MaxDuplicateCount = 1; 462 else 463 MaxDuplicateCount = TailDuplicateSize; 464 465 if (PreRegAlloc) { 466 // Pre-regalloc tail duplication hurts compile time and doesn't help 467 // much except for indirect branches. 468 if (TailBB->empty() || !TailBB->back().getDesc().isIndirectBranch()) 469 return false; 470 // If the target has hardware branch prediction that can handle indirect 471 // branches, duplicating them can often make them predictable when there 472 // are common paths through the code. The limit needs to be high enough 473 // to allow undoing the effects of tail merging and other optimizations 474 // that rearrange the predecessors of the indirect branch. 475 MaxDuplicateCount = 20; 476 } 477 478 // Don't try to tail-duplicate single-block loops. 479 if (TailBB->isSuccessor(TailBB)) 480 return false; 481 482 // Check the instructions in the block to determine whether tail-duplication 483 // is invalid or unlikely to be profitable. 484 unsigned InstrCount = 0; 485 bool HasCall = false; 486 for (MachineBasicBlock::iterator I = TailBB->begin(); 487 I != TailBB->end(); ++I) { 488 // Non-duplicable things shouldn't be tail-duplicated. 489 if (I->getDesc().isNotDuplicable()) return false; 490 // Do not duplicate 'return' instructions if this is a pre-regalloc run. 491 // A return may expand into a lot more instructions (e.g. reload of callee 492 // saved registers) after PEI. 493 if (PreRegAlloc && I->getDesc().isReturn()) return false; 494 // Don't duplicate more than the threshold. 495 if (InstrCount == MaxDuplicateCount) return false; 496 // Remember if we saw a call. 497 if (I->getDesc().isCall()) HasCall = true; 498 if (!I->isPHI()) 499 InstrCount += 1; 500 } 501 // Heuristically, don't tail-duplicate calls if it would expand code size, 502 // as it's less likely to be worth the extra cost. 503 if (InstrCount > 1 && HasCall) 504 return false; 505 506 DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 507 508 // Iterate through all the unique predecessors and tail-duplicate this 509 // block into them, if possible. Copying the list ahead of time also 510 // avoids trouble with the predecessor list reallocating. 511 bool Changed = false; 512 SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 513 TailBB->pred_end()); 514 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 515 PE = Preds.end(); PI != PE; ++PI) { 516 MachineBasicBlock *PredBB = *PI; 517 518 assert(TailBB != PredBB && 519 "Single-block loop should have been rejected earlier!"); 520 if (PredBB->succ_size() > 1) continue; 521 522 MachineBasicBlock *PredTBB, *PredFBB; 523 SmallVector<MachineOperand, 4> PredCond; 524 if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 525 continue; 526 if (!PredCond.empty()) 527 continue; 528 // EH edges are ignored by AnalyzeBranch. 529 if (PredBB->succ_size() != 1) 530 continue; 531 // Don't duplicate into a fall-through predecessor (at least for now). 532 if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 533 continue; 534 535 DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 536 << "From Succ: " << *TailBB); 537 538 TDBBs.push_back(PredBB); 539 540 // Remove PredBB's unconditional branch. 541 TII->RemoveBranch(*PredBB); 542 543 // Clone the contents of TailBB into PredBB. 544 DenseMap<unsigned, unsigned> LocalVRMap; 545 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 546 MachineBasicBlock::iterator I = TailBB->begin(); 547 while (I != TailBB->end()) { 548 MachineInstr *MI = &*I; 549 ++I; 550 if (MI->isPHI()) { 551 // Replace the uses of the def of the PHI with the register coming 552 // from PredBB. 553 ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos); 554 } else { 555 // Replace def of virtual registers with new registers, and update 556 // uses with PHI source register or the new registers. 557 DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap); 558 } 559 } 560 MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 561 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 562 const TargetRegisterClass *RC = MRI->getRegClass(CopyInfos[i].first); 563 TII->copyRegToReg(*PredBB, Loc, CopyInfos[i].first, 564 CopyInfos[i].second, RC,RC); 565 MachineInstr *CopyMI = prior(Loc); 566 Copies.push_back(CopyMI); 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 const TargetRegisterClass *RC = MRI->getRegClass(CopyInfos[i].first); 622 TII->copyRegToReg(*PrevBB, Loc, CopyInfos[i].first, 623 CopyInfos[i].second, RC, RC); 624 MachineInstr *CopyMI = prior(Loc); 625 Copies.push_back(CopyMI); 626 } 627 } else { 628 // No PHIs to worry about, just splice the instructions over. 629 PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 630 } 631 PrevBB->removeSuccessor(PrevBB->succ_begin()); 632 assert(PrevBB->succ_empty()); 633 PrevBB->transferSuccessors(TailBB); 634 TDBBs.push_back(PrevBB); 635 Changed = true; 636 } 637 638 return Changed; 639} 640 641/// RemoveDeadBlock - Remove the specified dead machine basic block from the 642/// function, updating the CFG. 643void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 644 assert(MBB->pred_empty() && "MBB must be dead!"); 645 DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 646 647 // Remove all successors. 648 while (!MBB->succ_empty()) 649 MBB->removeSuccessor(MBB->succ_end()-1); 650 651 // Remove the block. 652 MBB->eraseFromParent(); 653} 654 655