TailDuplication.cpp revision 234353
191094Sdes//===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===// 292289Sdes// 391094Sdes// The LLVM Compiler Infrastructure 491094Sdes// 591094Sdes// This file is distributed under the University of Illinois Open Source 691094Sdes// License. See LICENSE.TXT for details. 791094Sdes// 891094Sdes//===----------------------------------------------------------------------===// 991094Sdes// 1091094Sdes// This pass duplicates basic blocks ending in unconditional branches into 1191094Sdes// the tails of their predecessors. 1291094Sdes// 1391094Sdes//===----------------------------------------------------------------------===// 1491094Sdes 1591094Sdes#define DEBUG_TYPE "tailduplication" 1691094Sdes#include "llvm/Function.h" 1791094Sdes#include "llvm/CodeGen/Passes.h" 1891094Sdes#include "llvm/CodeGen/MachineModuleInfo.h" 1991094Sdes#include "llvm/CodeGen/MachineFunctionPass.h" 2091094Sdes#include "llvm/CodeGen/MachineInstrBuilder.h" 2191094Sdes#include "llvm/CodeGen/MachineRegisterInfo.h" 2291094Sdes#include "llvm/CodeGen/MachineSSAUpdater.h" 2391094Sdes#include "llvm/Target/TargetInstrInfo.h" 2491094Sdes#include "llvm/Support/CommandLine.h" 2591094Sdes#include "llvm/Support/Debug.h" 2691094Sdes#include "llvm/Support/ErrorHandling.h" 2791094Sdes#include "llvm/Support/raw_ostream.h" 2891094Sdes#include "llvm/ADT/DenseSet.h" 2991094Sdes#include "llvm/ADT/SmallSet.h" 3091094Sdes#include "llvm/ADT/SetVector.h" 3191094Sdes#include "llvm/ADT/Statistic.h" 3291094Sdesusing namespace llvm; 3391094Sdes 3493982SdesSTATISTIC(NumTails , "Number of tails duplicated"); 3591094SdesSTATISTIC(NumTailDups , "Number of tail duplicated blocks"); 3691094SdesSTATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 3791094SdesSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 3891094SdesSTATISTIC(NumAddedPHIs , "Number of phis added"); 3991094Sdes 4091094Sdes// Heuristic for tail duplication. 4191094Sdesstatic cl::opt<unsigned> 4291094SdesTailDuplicateSize("tail-dup-size", 4391094Sdes cl::desc("Maximum instructions to consider tail duplicating"), 4491094Sdes cl::init(2), cl::Hidden); 4591094Sdes 4691094Sdesstatic cl::opt<bool> 4791094SdesTailDupVerify("tail-dup-verify", 4891094Sdes cl::desc("Verify sanity of PHI instructions during taildup"), 4991094Sdes cl::init(false), cl::Hidden); 5091094Sdes 5191094Sdesstatic cl::opt<unsigned> 5291100SdesTailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 5391100Sdes 5491100Sdestypedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 5591100Sdes 5691094Sdesnamespace { 5791100Sdes /// TailDuplicatePass - Perform tail duplication. 5891100Sdes class TailDuplicatePass : public MachineFunctionPass { 5991100Sdes const TargetInstrInfo *TII; 6091100Sdes MachineModuleInfo *MMI; 6191100Sdes MachineRegisterInfo *MRI; 6291094Sdes bool PreRegAlloc; 6391094Sdes 6491094Sdes // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 6591094Sdes SmallVector<unsigned, 16> SSAUpdateVRs; 6691094Sdes 6791094Sdes // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 6893982Sdes // source virtual registers. 6991094Sdes DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 7091094Sdes 7191094Sdes public: 7291094Sdes static char ID; 7391094Sdes explicit TailDuplicatePass() : 7491094Sdes MachineFunctionPass(ID), PreRegAlloc(false) {} 7591094Sdes 7691094Sdes virtual bool runOnMachineFunction(MachineFunction &MF); 7791094Sdes 7891094Sdes private: 7991094Sdes void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 8091094Sdes MachineBasicBlock *BB); 8191094Sdes void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 8291094Sdes MachineBasicBlock *PredBB, 8391094Sdes DenseMap<unsigned, unsigned> &LocalVRMap, 8491094Sdes SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 8591094Sdes const DenseSet<unsigned> &UsedByPhi, 8691094Sdes bool Remove); 8791094Sdes void DuplicateInstruction(MachineInstr *MI, 8891094Sdes MachineBasicBlock *TailBB, 8991094Sdes MachineBasicBlock *PredBB, 9091094Sdes MachineFunction &MF, 9191094Sdes DenseMap<unsigned, unsigned> &LocalVRMap, 9291094Sdes const DenseSet<unsigned> &UsedByPhi); 9391094Sdes void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 9491094Sdes SmallVector<MachineBasicBlock*, 8> &TDBBs, 9591094Sdes SmallSetVector<MachineBasicBlock*, 8> &Succs); 9691094Sdes bool TailDuplicateBlocks(MachineFunction &MF); 9791094Sdes bool shouldTailDuplicate(const MachineFunction &MF, 9891094Sdes bool IsSimple, MachineBasicBlock &TailBB); 9991094Sdes bool isSimpleBB(MachineBasicBlock *TailBB); 10091094Sdes bool canCompletelyDuplicateBB(MachineBasicBlock &BB); 10191094Sdes bool duplicateSimpleBB(MachineBasicBlock *TailBB, 10291094Sdes SmallVector<MachineBasicBlock*, 8> &TDBBs, 10391094Sdes const DenseSet<unsigned> &RegsUsedByPhi, 10491094Sdes SmallVector<MachineInstr*, 16> &Copies); 10591094Sdes bool TailDuplicate(MachineBasicBlock *TailBB, 10691094Sdes bool IsSimple, 10791094Sdes MachineFunction &MF, 10891094Sdes SmallVector<MachineBasicBlock*, 8> &TDBBs, 10991094Sdes SmallVector<MachineInstr*, 16> &Copies); 11091094Sdes bool TailDuplicateAndUpdate(MachineBasicBlock *MBB, 11191094Sdes bool IsSimple, 11291094Sdes MachineFunction &MF); 11391094Sdes 11491094Sdes void RemoveDeadBlock(MachineBasicBlock *MBB); 11591094Sdes }; 11691094Sdes 11791094Sdes char TailDuplicatePass::ID = 0; 11891094Sdes} 11991094Sdes 12093982Sdeschar &llvm::TailDuplicateID = TailDuplicatePass::ID; 12193982Sdes 12291094SdesINITIALIZE_PASS(TailDuplicatePass, "tailduplication", "Tail Duplication", 12391094Sdes false, false) 12491094Sdes 12591094Sdesbool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 12693982Sdes TII = MF.getTarget().getInstrInfo(); 12791094Sdes MRI = &MF.getRegInfo(); 12891094Sdes MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 12993982Sdes PreRegAlloc = MRI->isSSA(); 13093982Sdes 13193982Sdes bool MadeChange = false; 13293982Sdes while (TailDuplicateBlocks(MF)) 13391094Sdes MadeChange = true; 13493982Sdes 13591094Sdes return MadeChange; 13693982Sdes} 13793982Sdes 13893982Sdesstatic void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 13993982Sdes for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 14091094Sdes MachineBasicBlock *MBB = I; 14191094Sdes SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 14291094Sdes MBB->pred_end()); 14391094Sdes MachineBasicBlock::iterator MI = MBB->begin(); 14491094Sdes while (MI != MBB->end()) { 14591094Sdes if (!MI->isPHI()) 14691094Sdes break; 14791094Sdes for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 14891094Sdes PE = Preds.end(); PI != PE; ++PI) { 14991094Sdes MachineBasicBlock *PredBB = *PI; 15091094Sdes bool Found = false; 15191094Sdes for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 15291094Sdes MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 15391094Sdes if (PHIBB == PredBB) { 15491094Sdes Found = true; 15591094Sdes break; 15691094Sdes } 15791094Sdes } 15891094Sdes if (!Found) { 15991094Sdes dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 16091094Sdes dbgs() << " missing input from predecessor BB#" 16191094Sdes << PredBB->getNumber() << '\n'; 16291094Sdes llvm_unreachable(0); 16391094Sdes } 16491094Sdes } 16591094Sdes 16691094Sdes for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 16791094Sdes MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 16891094Sdes if (CheckExtra && !Preds.count(PHIBB)) { 16991094Sdes dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 17091094Sdes << ": " << *MI; 17191094Sdes dbgs() << " extra input from predecessor BB#" 17291094Sdes << PHIBB->getNumber() << '\n'; 17391094Sdes llvm_unreachable(0); 17491094Sdes } 17591094Sdes if (PHIBB->getNumber() < 0) { 17691094Sdes dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 17791094Sdes dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 17891094Sdes llvm_unreachable(0); 17991094Sdes } 18091094Sdes } 18191094Sdes ++MI; 18291094Sdes } 18391094Sdes } 18491094Sdes} 18591094Sdes 18691094Sdes/// TailDuplicateAndUpdate - Tail duplicate the block and cleanup. 18791094Sdesbool 18891684SdesTailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB, 18991094Sdes bool IsSimple, 19091094Sdes MachineFunction &MF) { 19191094Sdes // Save the successors list. 19291094Sdes SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 19391094Sdes MBB->succ_end()); 19491094Sdes 19591094Sdes SmallVector<MachineBasicBlock*, 8> TDBBs; 19691094Sdes SmallVector<MachineInstr*, 16> Copies; 19791094Sdes if (!TailDuplicate(MBB, IsSimple, MF, TDBBs, Copies)) 19891094Sdes return false; 19991094Sdes 20091094Sdes ++NumTails; 20191094Sdes 20291094Sdes SmallVector<MachineInstr*, 8> NewPHIs; 20393982Sdes MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 20493982Sdes 20591094Sdes // TailBB's immediate successors are now successors of those predecessors 20693982Sdes // which duplicated TailBB. Add the predecessors as sources to the PHI 20793982Sdes // instructions. 20891094Sdes bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); 20991094Sdes if (PreRegAlloc) 21091094Sdes UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 21191094Sdes 21291094Sdes // If it is dead, remove it. 21391094Sdes if (isDead) { 21491684Sdes NumInstrDups -= MBB->size(); 21591684Sdes RemoveDeadBlock(MBB); 21691094Sdes ++NumDeadBlocks; 21791094Sdes } 21891094Sdes 21991100Sdes // Update SSA form. 22091094Sdes if (!SSAUpdateVRs.empty()) { 22191094Sdes for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 22291094Sdes unsigned VReg = SSAUpdateVRs[i]; 22391094Sdes SSAUpdate.Initialize(VReg); 22491094Sdes 22591094Sdes // If the original definition is still around, add it as an available 22691094Sdes // value. 22791094Sdes MachineInstr *DefMI = MRI->getVRegDef(VReg); 22891094Sdes MachineBasicBlock *DefBB = 0; 22991094Sdes if (DefMI) { 23091094Sdes 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