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