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/DenseSet.h" 29#include "llvm/ADT/SmallSet.h" 30#include "llvm/ADT/SetVector.h" 31#include "llvm/ADT/Statistic.h" 32using namespace llvm; 33 34STATISTIC(NumTails , "Number of tails duplicated"); 35STATISTIC(NumTailDups , "Number of tail duplicated blocks"); 36STATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 37STATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 38STATISTIC(NumAddedPHIs , "Number of phis added"); 39 40// Heuristic for tail duplication. 41static cl::opt<unsigned> 42TailDuplicateSize("tail-dup-size", 43 cl::desc("Maximum instructions to consider tail duplicating"), 44 cl::init(2), cl::Hidden); 45 46static cl::opt<bool> 47TailDupVerify("tail-dup-verify", 48 cl::desc("Verify sanity of PHI instructions during taildup"), 49 cl::init(false), cl::Hidden); 50 51static cl::opt<unsigned> 52TailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 53 54typedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 55 56namespace { 57 /// TailDuplicatePass - Perform tail duplication. 58 class TailDuplicatePass : public MachineFunctionPass { 59 const TargetInstrInfo *TII; 60 MachineModuleInfo *MMI; 61 MachineRegisterInfo *MRI; 62 bool PreRegAlloc; 63 64 // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 65 SmallVector<unsigned, 16> SSAUpdateVRs; 66 67 // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 68 // source virtual registers. 69 DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 70 71 public: 72 static char ID; 73 explicit TailDuplicatePass() : 74 MachineFunctionPass(ID), PreRegAlloc(false) {} 75 76 virtual bool runOnMachineFunction(MachineFunction &MF); 77 78 private: 79 void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 80 MachineBasicBlock *BB); 81 void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 82 MachineBasicBlock *PredBB, 83 DenseMap<unsigned, unsigned> &LocalVRMap, 84 SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 85 const DenseSet<unsigned> &UsedByPhi, 86 bool Remove); 87 void DuplicateInstruction(MachineInstr *MI, 88 MachineBasicBlock *TailBB, 89 MachineBasicBlock *PredBB, 90 MachineFunction &MF, 91 DenseMap<unsigned, unsigned> &LocalVRMap, 92 const DenseSet<unsigned> &UsedByPhi); 93 void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 94 SmallVector<MachineBasicBlock*, 8> &TDBBs, 95 SmallSetVector<MachineBasicBlock*, 8> &Succs); 96 bool TailDuplicateBlocks(MachineFunction &MF); 97 bool shouldTailDuplicate(const MachineFunction &MF, 98 bool IsSimple, MachineBasicBlock &TailBB); 99 bool isSimpleBB(MachineBasicBlock *TailBB); 100 bool canCompletelyDuplicateBB(MachineBasicBlock &BB); 101 bool duplicateSimpleBB(MachineBasicBlock *TailBB, 102 SmallVector<MachineBasicBlock*, 8> &TDBBs, 103 const DenseSet<unsigned> &RegsUsedByPhi, 104 SmallVector<MachineInstr*, 16> &Copies); 105 bool TailDuplicate(MachineBasicBlock *TailBB, 106 bool IsSimple, 107 MachineFunction &MF, 108 SmallVector<MachineBasicBlock*, 8> &TDBBs, 109 SmallVector<MachineInstr*, 16> &Copies); 110 bool TailDuplicateAndUpdate(MachineBasicBlock *MBB, 111 bool IsSimple, 112 MachineFunction &MF); 113 114 void RemoveDeadBlock(MachineBasicBlock *MBB); 115 }; 116 117 char TailDuplicatePass::ID = 0; 118} 119 120char &llvm::TailDuplicateID = TailDuplicatePass::ID; 121 122INITIALIZE_PASS(TailDuplicatePass, "tailduplication", "Tail Duplication", 123 false, false) 124 125bool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 126 TII = MF.getTarget().getInstrInfo(); 127 MRI = &MF.getRegInfo(); 128 MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 129 PreRegAlloc = MRI->isSSA(); 130 131 bool MadeChange = false; 132 while (TailDuplicateBlocks(MF)) 133 MadeChange = true; 134 135 return MadeChange; 136} 137 138static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 139 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 140 MachineBasicBlock *MBB = I; 141 SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 142 MBB->pred_end()); 143 MachineBasicBlock::iterator MI = MBB->begin(); 144 while (MI != MBB->end()) { 145 if (!MI->isPHI()) 146 break; 147 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 148 PE = Preds.end(); PI != PE; ++PI) { 149 MachineBasicBlock *PredBB = *PI; 150 bool Found = false; 151 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 152 MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 153 if (PHIBB == PredBB) { 154 Found = true; 155 break; 156 } 157 } 158 if (!Found) { 159 dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 160 dbgs() << " missing input from predecessor BB#" 161 << PredBB->getNumber() << '\n'; 162 llvm_unreachable(0); 163 } 164 } 165 166 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 167 MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 168 if (CheckExtra && !Preds.count(PHIBB)) { 169 dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 170 << ": " << *MI; 171 dbgs() << " extra input from predecessor BB#" 172 << PHIBB->getNumber() << '\n'; 173 llvm_unreachable(0); 174 } 175 if (PHIBB->getNumber() < 0) { 176 dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 177 dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 178 llvm_unreachable(0); 179 } 180 } 181 ++MI; 182 } 183 } 184} 185 186/// TailDuplicateAndUpdate - Tail duplicate the block and cleanup. 187bool 188TailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB, 189 bool IsSimple, 190 MachineFunction &MF) { 191 // Save the successors list. 192 SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 193 MBB->succ_end()); 194 195 SmallVector<MachineBasicBlock*, 8> TDBBs; 196 SmallVector<MachineInstr*, 16> Copies; 197 if (!TailDuplicate(MBB, IsSimple, MF, TDBBs, Copies)) 198 return false; 199 200 ++NumTails; 201 202 SmallVector<MachineInstr*, 8> NewPHIs; 203 MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 204 205 // TailBB's immediate successors are now successors of those predecessors 206 // which duplicated TailBB. Add the predecessors as sources to the PHI 207 // instructions. 208 bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); 209 if (PreRegAlloc) 210 UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 211 212 // If it is dead, remove it. 213 if (isDead) { 214 NumInstrDups -= MBB->size(); 215 RemoveDeadBlock(MBB); 216 ++NumDeadBlocks; 217 } 218 219 // Update SSA form. 220 if (!SSAUpdateVRs.empty()) { 221 for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 222 unsigned VReg = SSAUpdateVRs[i]; 223 SSAUpdate.Initialize(VReg); 224 225 // If the original definition is still around, add it as an available 226 // value. 227 MachineInstr *DefMI = MRI->getVRegDef(VReg); 228 MachineBasicBlock *DefBB = 0; 229 if (DefMI) { 230 DefBB = DefMI->getParent(); 231 SSAUpdate.AddAvailableValue(DefBB, VReg); 232 } 233 234 // Add the new vregs as available values. 235 DenseMap<unsigned, AvailableValsTy>::iterator LI = 236 SSAUpdateVals.find(VReg); 237 for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 238 MachineBasicBlock *SrcBB = LI->second[j].first; 239 unsigned SrcReg = LI->second[j].second; 240 SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 241 } 242 243 // Rewrite uses that are outside of the original def's block. 244 MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 245 while (UI != MRI->use_end()) { 246 MachineOperand &UseMO = UI.getOperand(); 247 MachineInstr *UseMI = &*UI; 248 ++UI; 249 if (UseMI->isDebugValue()) { 250 // SSAUpdate can replace the use with an undef. That creates 251 // a debug instruction that is a kill. 252 // FIXME: Should it SSAUpdate job to delete debug instructions 253 // instead of replacing the use with undef? 254 UseMI->eraseFromParent(); 255 continue; 256 } 257 if (UseMI->getParent() == DefBB && !UseMI->isPHI()) 258 continue; 259 SSAUpdate.RewriteUse(UseMO); 260 } 261 } 262 263 SSAUpdateVRs.clear(); 264 SSAUpdateVals.clear(); 265 } 266 267 // Eliminate some of the copies inserted by tail duplication to maintain 268 // SSA form. 269 for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 270 MachineInstr *Copy = Copies[i]; 271 if (!Copy->isCopy()) 272 continue; 273 unsigned Dst = Copy->getOperand(0).getReg(); 274 unsigned Src = Copy->getOperand(1).getReg(); 275 MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); 276 if (++UI == MRI->use_end()) { 277 // Copy is the only use. Do trivial copy propagation here. 278 MRI->replaceRegWith(Dst, Src); 279 Copy->eraseFromParent(); 280 } 281 } 282 283 if (NewPHIs.size()) 284 NumAddedPHIs += NewPHIs.size(); 285 286 return true; 287} 288 289/// TailDuplicateBlocks - Look for small blocks that are unconditionally 290/// branched to and do not fall through. Tail-duplicate their instructions 291/// into their predecessors to eliminate (dynamic) branches. 292bool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 293 bool MadeChange = false; 294 295 if (PreRegAlloc && TailDupVerify) { 296 DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 297 VerifyPHIs(MF, true); 298 } 299 300 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 301 MachineBasicBlock *MBB = I++; 302 303 if (NumTails == TailDupLimit) 304 break; 305 306 bool IsSimple = isSimpleBB(MBB); 307 308 if (!shouldTailDuplicate(MF, IsSimple, *MBB)) 309 continue; 310 311 MadeChange |= TailDuplicateAndUpdate(MBB, IsSimple, MF); 312 } 313 314 if (PreRegAlloc && TailDupVerify) 315 VerifyPHIs(MF, false); 316 317 return MadeChange; 318} 319 320static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 321 const MachineRegisterInfo *MRI) { 322 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 323 UE = MRI->use_end(); UI != UE; ++UI) { 324 MachineInstr *UseMI = &*UI; 325 if (UseMI->isDebugValue()) 326 continue; 327 if (UseMI->getParent() != BB) 328 return true; 329 } 330 return false; 331} 332 333static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 334 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 335 if (MI->getOperand(i+1).getMBB() == SrcBB) 336 return i; 337 return 0; 338} 339 340 341// Remember which registers are used by phis in this block. This is 342// used to determine which registers are liveout while modifying the 343// block (which is why we need to copy the information). 344static void getRegsUsedByPHIs(const MachineBasicBlock &BB, 345 DenseSet<unsigned> *UsedByPhi) { 346 for(MachineBasicBlock::const_iterator I = BB.begin(), E = BB.end(); 347 I != E; ++I) { 348 const MachineInstr &MI = *I; 349 if (!MI.isPHI()) 350 break; 351 for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 352 unsigned SrcReg = MI.getOperand(i).getReg(); 353 UsedByPhi->insert(SrcReg); 354 } 355 } 356} 357 358/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 359/// SSA update. 360void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 361 MachineBasicBlock *BB) { 362 DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 363 if (LI != SSAUpdateVals.end()) 364 LI->second.push_back(std::make_pair(BB, NewReg)); 365 else { 366 AvailableValsTy Vals; 367 Vals.push_back(std::make_pair(BB, NewReg)); 368 SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 369 SSAUpdateVRs.push_back(OrigReg); 370 } 371} 372 373/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 374/// Remember the source register that's contributed by PredBB and update SSA 375/// update map. 376void TailDuplicatePass::ProcessPHI(MachineInstr *MI, 377 MachineBasicBlock *TailBB, 378 MachineBasicBlock *PredBB, 379 DenseMap<unsigned, unsigned> &LocalVRMap, 380 SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 381 const DenseSet<unsigned> &RegsUsedByPhi, 382 bool Remove) { 383 unsigned DefReg = MI->getOperand(0).getReg(); 384 unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 385 assert(SrcOpIdx && "Unable to find matching PHI source?"); 386 unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 387 const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 388 LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 389 390 // Insert a copy from source to the end of the block. The def register is the 391 // available value liveout of the block. 392 unsigned NewDef = MRI->createVirtualRegister(RC); 393 Copies.push_back(std::make_pair(NewDef, SrcReg)); 394 if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) 395 AddSSAUpdateEntry(DefReg, NewDef, PredBB); 396 397 if (!Remove) 398 return; 399 400 // Remove PredBB from the PHI node. 401 MI->RemoveOperand(SrcOpIdx+1); 402 MI->RemoveOperand(SrcOpIdx); 403 if (MI->getNumOperands() == 1) 404 MI->eraseFromParent(); 405} 406 407/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 408/// the source operands due to earlier PHI translation. 409void TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 410 MachineBasicBlock *TailBB, 411 MachineBasicBlock *PredBB, 412 MachineFunction &MF, 413 DenseMap<unsigned, unsigned> &LocalVRMap, 414 const DenseSet<unsigned> &UsedByPhi) { 415 MachineInstr *NewMI = TII->duplicate(MI, MF); 416 for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 417 MachineOperand &MO = NewMI->getOperand(i); 418 if (!MO.isReg()) 419 continue; 420 unsigned Reg = MO.getReg(); 421 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 422 continue; 423 if (MO.isDef()) { 424 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 425 unsigned NewReg = MRI->createVirtualRegister(RC); 426 MO.setReg(NewReg); 427 LocalVRMap.insert(std::make_pair(Reg, NewReg)); 428 if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) 429 AddSSAUpdateEntry(Reg, NewReg, PredBB); 430 } else { 431 DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 432 if (VI != LocalVRMap.end()) 433 MO.setReg(VI->second); 434 } 435 } 436 PredBB->insert(PredBB->instr_end(), NewMI); 437} 438 439/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 440/// blocks, the successors have gained new predecessors. Update the PHI 441/// instructions in them accordingly. 442void 443TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 444 SmallVector<MachineBasicBlock*, 8> &TDBBs, 445 SmallSetVector<MachineBasicBlock*,8> &Succs) { 446 for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 447 SE = Succs.end(); SI != SE; ++SI) { 448 MachineBasicBlock *SuccBB = *SI; 449 for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 450 II != EE; ++II) { 451 if (!II->isPHI()) 452 break; 453 unsigned Idx = 0; 454 for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 455 MachineOperand &MO = II->getOperand(i+1); 456 if (MO.getMBB() == FromBB) { 457 Idx = i; 458 break; 459 } 460 } 461 462 assert(Idx != 0); 463 MachineOperand &MO0 = II->getOperand(Idx); 464 unsigned Reg = MO0.getReg(); 465 if (isDead) { 466 // Folded into the previous BB. 467 // There could be duplicate phi source entries. FIXME: Should sdisel 468 // or earlier pass fixed this? 469 for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 470 MachineOperand &MO = II->getOperand(i+1); 471 if (MO.getMBB() == FromBB) { 472 II->RemoveOperand(i+1); 473 II->RemoveOperand(i); 474 } 475 } 476 } else 477 Idx = 0; 478 479 // If Idx is set, the operands at Idx and Idx+1 must be removed. 480 // We reuse the location to avoid expensive RemoveOperand calls. 481 482 DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 483 if (LI != SSAUpdateVals.end()) { 484 // This register is defined in the tail block. 485 for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 486 MachineBasicBlock *SrcBB = LI->second[j].first; 487 // If we didn't duplicate a bb into a particular predecessor, we 488 // might still have added an entry to SSAUpdateVals to correcly 489 // recompute SSA. If that case, avoid adding a dummy extra argument 490 // this PHI. 491 if (!SrcBB->isSuccessor(SuccBB)) 492 continue; 493 494 unsigned SrcReg = LI->second[j].second; 495 if (Idx != 0) { 496 II->getOperand(Idx).setReg(SrcReg); 497 II->getOperand(Idx+1).setMBB(SrcBB); 498 Idx = 0; 499 } else { 500 II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 501 II->addOperand(MachineOperand::CreateMBB(SrcBB)); 502 } 503 } 504 } else { 505 // Live in tail block, must also be live in predecessors. 506 for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 507 MachineBasicBlock *SrcBB = TDBBs[j]; 508 if (Idx != 0) { 509 II->getOperand(Idx).setReg(Reg); 510 II->getOperand(Idx+1).setMBB(SrcBB); 511 Idx = 0; 512 } else { 513 II->addOperand(MachineOperand::CreateReg(Reg, false)); 514 II->addOperand(MachineOperand::CreateMBB(SrcBB)); 515 } 516 } 517 } 518 if (Idx != 0) { 519 II->RemoveOperand(Idx+1); 520 II->RemoveOperand(Idx); 521 } 522 } 523 } 524} 525 526/// shouldTailDuplicate - Determine if it is profitable to duplicate this block. 527bool 528TailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF, 529 bool IsSimple, 530 MachineBasicBlock &TailBB) { 531 // Only duplicate blocks that end with unconditional branches. 532 if (TailBB.canFallThrough()) 533 return false; 534 535 // Don't try to tail-duplicate single-block loops. 536 if (TailBB.isSuccessor(&TailBB)) 537 return false; 538 539 // Set the limit on the cost to duplicate. When optimizing for size, 540 // duplicate only one, because one branch instruction can be eliminated to 541 // compensate for the duplication. 542 unsigned MaxDuplicateCount; 543 if (TailDuplicateSize.getNumOccurrences() == 0 && 544 MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 545 MaxDuplicateCount = 1; 546 else 547 MaxDuplicateCount = TailDuplicateSize; 548 549 // If the target has hardware branch prediction that can handle indirect 550 // branches, duplicating them can often make them predictable when there 551 // are common paths through the code. The limit needs to be high enough 552 // to allow undoing the effects of tail merging and other optimizations 553 // that rearrange the predecessors of the indirect branch. 554 555 bool HasIndirectbr = false; 556 if (!TailBB.empty()) 557 HasIndirectbr = TailBB.back().isIndirectBranch(); 558 559 if (HasIndirectbr && PreRegAlloc) 560 MaxDuplicateCount = 20; 561 562 // Check the instructions in the block to determine whether tail-duplication 563 // is invalid or unlikely to be profitable. 564 unsigned InstrCount = 0; 565 for (MachineBasicBlock::iterator I = TailBB.begin(); I != TailBB.end(); ++I) { 566 // Non-duplicable things shouldn't be tail-duplicated. 567 if (I->isNotDuplicable()) 568 return false; 569 570 // Do not duplicate 'return' instructions if this is a pre-regalloc run. 571 // A return may expand into a lot more instructions (e.g. reload of callee 572 // saved registers) after PEI. 573 if (PreRegAlloc && I->isReturn()) 574 return false; 575 576 // Avoid duplicating calls before register allocation. Calls presents a 577 // barrier to register allocation so duplicating them may end up increasing 578 // spills. 579 if (PreRegAlloc && I->isCall()) 580 return false; 581 582 if (!I->isPHI() && !I->isDebugValue()) 583 InstrCount += 1; 584 585 if (InstrCount > MaxDuplicateCount) 586 return false; 587 } 588 589 if (HasIndirectbr && PreRegAlloc) 590 return true; 591 592 if (IsSimple) 593 return true; 594 595 if (!PreRegAlloc) 596 return true; 597 598 return canCompletelyDuplicateBB(TailBB); 599} 600 601/// isSimpleBB - True if this BB has only one unconditional jump. 602bool 603TailDuplicatePass::isSimpleBB(MachineBasicBlock *TailBB) { 604 if (TailBB->succ_size() != 1) 605 return false; 606 if (TailBB->pred_empty()) 607 return false; 608 MachineBasicBlock::iterator I = TailBB->begin(); 609 MachineBasicBlock::iterator E = TailBB->end(); 610 while (I != E && I->isDebugValue()) 611 ++I; 612 if (I == E) 613 return true; 614 return I->isUnconditionalBranch(); 615} 616 617static bool 618bothUsedInPHI(const MachineBasicBlock &A, 619 SmallPtrSet<MachineBasicBlock*, 8> SuccsB) { 620 for (MachineBasicBlock::const_succ_iterator SI = A.succ_begin(), 621 SE = A.succ_end(); SI != SE; ++SI) { 622 MachineBasicBlock *BB = *SI; 623 if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI()) 624 return true; 625 } 626 627 return false; 628} 629 630bool 631TailDuplicatePass::canCompletelyDuplicateBB(MachineBasicBlock &BB) { 632 SmallPtrSet<MachineBasicBlock*, 8> Succs(BB.succ_begin(), BB.succ_end()); 633 634 for (MachineBasicBlock::pred_iterator PI = BB.pred_begin(), 635 PE = BB.pred_end(); PI != PE; ++PI) { 636 MachineBasicBlock *PredBB = *PI; 637 638 if (PredBB->succ_size() > 1) 639 return false; 640 641 MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL; 642 SmallVector<MachineOperand, 4> PredCond; 643 if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 644 return false; 645 646 if (!PredCond.empty()) 647 return false; 648 } 649 return true; 650} 651 652bool 653TailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB, 654 SmallVector<MachineBasicBlock*, 8> &TDBBs, 655 const DenseSet<unsigned> &UsedByPhi, 656 SmallVector<MachineInstr*, 16> &Copies) { 657 SmallPtrSet<MachineBasicBlock*, 8> Succs(TailBB->succ_begin(), 658 TailBB->succ_end()); 659 SmallVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 660 TailBB->pred_end()); 661 bool Changed = false; 662 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 663 PE = Preds.end(); PI != PE; ++PI) { 664 MachineBasicBlock *PredBB = *PI; 665 666 if (PredBB->getLandingPadSuccessor()) 667 continue; 668 669 if (bothUsedInPHI(*PredBB, Succs)) 670 continue; 671 672 MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL; 673 SmallVector<MachineOperand, 4> PredCond; 674 if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 675 continue; 676 677 Changed = true; 678 DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 679 << "From simple Succ: " << *TailBB); 680 681 MachineBasicBlock *NewTarget = *TailBB->succ_begin(); 682 MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(PredBB)); 683 684 // Make PredFBB explicit. 685 if (PredCond.empty()) 686 PredFBB = PredTBB; 687 688 // Make fall through explicit. 689 if (!PredTBB) 690 PredTBB = NextBB; 691 if (!PredFBB) 692 PredFBB = NextBB; 693 694 // Redirect 695 if (PredFBB == TailBB) 696 PredFBB = NewTarget; 697 if (PredTBB == TailBB) 698 PredTBB = NewTarget; 699 700 // Make the branch unconditional if possible 701 if (PredTBB == PredFBB) { 702 PredCond.clear(); 703 PredFBB = NULL; 704 } 705 706 // Avoid adding fall through branches. 707 if (PredFBB == NextBB) 708 PredFBB = NULL; 709 if (PredTBB == NextBB && PredFBB == NULL) 710 PredTBB = NULL; 711 712 TII->RemoveBranch(*PredBB); 713 714 if (PredTBB) 715 TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc()); 716 717 PredBB->removeSuccessor(TailBB); 718 unsigned NumSuccessors = PredBB->succ_size(); 719 assert(NumSuccessors <= 1); 720 if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget) 721 PredBB->addSuccessor(NewTarget); 722 723 TDBBs.push_back(PredBB); 724 } 725 return Changed; 726} 727 728/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 729/// of its predecessors. 730bool 731TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, 732 bool IsSimple, 733 MachineFunction &MF, 734 SmallVector<MachineBasicBlock*, 8> &TDBBs, 735 SmallVector<MachineInstr*, 16> &Copies) { 736 DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 737 738 DenseSet<unsigned> UsedByPhi; 739 getRegsUsedByPHIs(*TailBB, &UsedByPhi); 740 741 if (IsSimple) 742 return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies); 743 744 // Iterate through all the unique predecessors and tail-duplicate this 745 // block into them, if possible. Copying the list ahead of time also 746 // avoids trouble with the predecessor list reallocating. 747 bool Changed = false; 748 SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 749 TailBB->pred_end()); 750 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 751 PE = Preds.end(); PI != PE; ++PI) { 752 MachineBasicBlock *PredBB = *PI; 753 754 assert(TailBB != PredBB && 755 "Single-block loop should have been rejected earlier!"); 756 // EH edges are ignored by AnalyzeBranch. 757 if (PredBB->succ_size() > 1) 758 continue; 759 760 MachineBasicBlock *PredTBB, *PredFBB; 761 SmallVector<MachineOperand, 4> PredCond; 762 if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 763 continue; 764 if (!PredCond.empty()) 765 continue; 766 // Don't duplicate into a fall-through predecessor (at least for now). 767 if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 768 continue; 769 770 DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 771 << "From Succ: " << *TailBB); 772 773 TDBBs.push_back(PredBB); 774 775 // Remove PredBB's unconditional branch. 776 TII->RemoveBranch(*PredBB); 777 778 // Clone the contents of TailBB into PredBB. 779 DenseMap<unsigned, unsigned> LocalVRMap; 780 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 781 // Use instr_iterator here to properly handle bundles, e.g. 782 // ARM Thumb2 IT block. 783 MachineBasicBlock::instr_iterator I = TailBB->instr_begin(); 784 while (I != TailBB->instr_end()) { 785 MachineInstr *MI = &*I; 786 ++I; 787 if (MI->isPHI()) { 788 // Replace the uses of the def of the PHI with the register coming 789 // from PredBB. 790 ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); 791 } else { 792 // Replace def of virtual registers with new registers, and update 793 // uses with PHI source register or the new registers. 794 DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi); 795 } 796 } 797 MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 798 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 799 Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 800 TII->get(TargetOpcode::COPY), 801 CopyInfos[i].first).addReg(CopyInfos[i].second)); 802 } 803 804 // Simplify 805 TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true); 806 807 NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 808 809 // Update the CFG. 810 PredBB->removeSuccessor(PredBB->succ_begin()); 811 assert(PredBB->succ_empty() && 812 "TailDuplicate called on block with multiple successors!"); 813 for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 814 E = TailBB->succ_end(); I != E; ++I) 815 PredBB->addSuccessor(*I); 816 817 Changed = true; 818 ++NumTailDups; 819 } 820 821 // If TailBB was duplicated into all its predecessors except for the prior 822 // block, which falls through unconditionally, move the contents of this 823 // block into the prior block. 824 MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 825 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 826 SmallVector<MachineOperand, 4> PriorCond; 827 // This has to check PrevBB->succ_size() because EH edges are ignored by 828 // AnalyzeBranch. 829 if (PrevBB->succ_size() == 1 && 830 !TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true) && 831 PriorCond.empty() && !PriorTBB && TailBB->pred_size() == 1 && 832 !TailBB->hasAddressTaken()) { 833 DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 834 << "From MBB: " << *TailBB); 835 if (PreRegAlloc) { 836 DenseMap<unsigned, unsigned> LocalVRMap; 837 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 838 MachineBasicBlock::iterator I = TailBB->begin(); 839 // Process PHI instructions first. 840 while (I != TailBB->end() && I->isPHI()) { 841 // Replace the uses of the def of the PHI with the register coming 842 // from PredBB. 843 MachineInstr *MI = &*I++; 844 ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); 845 if (MI->getParent()) 846 MI->eraseFromParent(); 847 } 848 849 // Now copy the non-PHI instructions. 850 while (I != TailBB->end()) { 851 // Replace def of virtual registers with new registers, and update 852 // uses with PHI source register or the new registers. 853 MachineInstr *MI = &*I++; 854 assert(!MI->isBundle() && "Not expecting bundles before regalloc!"); 855 DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi); 856 MI->eraseFromParent(); 857 } 858 MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 859 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 860 Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 861 TII->get(TargetOpcode::COPY), 862 CopyInfos[i].first) 863 .addReg(CopyInfos[i].second)); 864 } 865 } else { 866 // No PHIs to worry about, just splice the instructions over. 867 PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 868 } 869 PrevBB->removeSuccessor(PrevBB->succ_begin()); 870 assert(PrevBB->succ_empty()); 871 PrevBB->transferSuccessors(TailBB); 872 TDBBs.push_back(PrevBB); 873 Changed = true; 874 } 875 876 // If this is after register allocation, there are no phis to fix. 877 if (!PreRegAlloc) 878 return Changed; 879 880 // If we made no changes so far, we are safe. 881 if (!Changed) 882 return Changed; 883 884 885 // Handle the nasty case in that we duplicated a block that is part of a loop 886 // into some but not all of its predecessors. For example: 887 // 1 -> 2 <-> 3 | 888 // \ | 889 // \---> rest | 890 // if we duplicate 2 into 1 but not into 3, we end up with 891 // 12 -> 3 <-> 2 -> rest | 892 // \ / | 893 // \----->-----/ | 894 // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced 895 // with a phi in 3 (which now dominates 2). 896 // What we do here is introduce a copy in 3 of the register defined by the 897 // phi, just like when we are duplicating 2 into 3, but we don't copy any 898 // real instructions or remove the 3 -> 2 edge from the phi in 2. 899 for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 900 PE = Preds.end(); PI != PE; ++PI) { 901 MachineBasicBlock *PredBB = *PI; 902 if (std::find(TDBBs.begin(), TDBBs.end(), PredBB) != TDBBs.end()) 903 continue; 904 905 // EH edges 906 if (PredBB->succ_size() != 1) 907 continue; 908 909 DenseMap<unsigned, unsigned> LocalVRMap; 910 SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 911 MachineBasicBlock::iterator I = TailBB->begin(); 912 // Process PHI instructions first. 913 while (I != TailBB->end() && I->isPHI()) { 914 // Replace the uses of the def of the PHI with the register coming 915 // from PredBB. 916 MachineInstr *MI = &*I++; 917 ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); 918 } 919 MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 920 for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 921 Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 922 TII->get(TargetOpcode::COPY), 923 CopyInfos[i].first).addReg(CopyInfos[i].second)); 924 } 925 } 926 927 return Changed; 928} 929 930/// RemoveDeadBlock - Remove the specified dead machine basic block from the 931/// function, updating the CFG. 932void TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 933 assert(MBB->pred_empty() && "MBB must be dead!"); 934 DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 935 936 // Remove all successors. 937 while (!MBB->succ_empty()) 938 MBB->removeSuccessor(MBB->succ_end()-1); 939 940 // Remove the block. 941 MBB->eraseFromParent(); 942} 943