TailDuplication.cpp revision c66d36028b21077aa1715331c22347b47b4da94f
115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson//===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===// 215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// The LLVM Compiler Infrastructure 415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// This file is distributed under the University of Illinois Open Source 615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// License. See LICENSE.TXT for details. 715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson//===----------------------------------------------------------------------===// 915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 1015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// This pass duplicates basic blocks ending in unconditional branches into 1115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// the tails of their predecessors. 1215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 1315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson//===----------------------------------------------------------------------===// 1415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#define DEBUG_TYPE "tailduplication" 1615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Function.h" 1715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/CodeGen/Passes.h" 1815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/CodeGen/MachineModuleInfo.h" 1915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/CodeGen/MachineFunctionPass.h" 201e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 21111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 22111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineSSAUpdater.h" 2315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Target/TargetInstrInfo.h" 2415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/CommandLine.h" 2515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/Debug.h" 2675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng#include "llvm/Support/ErrorHandling.h" 2715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/raw_ostream.h" 28c66d36028b21077aa1715331c22347b47b4da94fJakob Stoklund Olesen#include "llvm/ADT/DenseSet.h" 2915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/SmallSet.h" 3015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/SetVector.h" 3115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/Statistic.h" 3215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonusing namespace llvm; 3315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 3475eb53584367098a5625028e22f1ff8e169d0efdEvan ChengSTATISTIC(NumTails , "Number of tails duplicated"); 3515acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumTailDups , "Number of tail duplicated blocks"); 3615acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 3715acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 380cdca089b289845664d660f0b285499800822919Rafael EspindolaSTATISTIC(NumAddedPHIs , "Number of phis added"); 3915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// Heuristic for tail duplication. 4115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonstatic cl::opt<unsigned> 4215acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonTailDuplicateSize("tail-dup-size", 4315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::desc("Maximum instructions to consider tail duplicating"), 4415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::init(2), cl::Hidden); 4515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4675eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<bool> 4775eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupVerify("tail-dup-verify", 4875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::desc("Verify sanity of PHI instructions during taildup"), 4975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::init(false), cl::Hidden); 5075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5175eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<unsigned> 5275eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 5375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5411572babb12d169965c63c47aab9c9fad354e5dfEvan Chengtypedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 55111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 5615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonnamespace { 572d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson /// TailDuplicatePass - Perform tail duplication. 582d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson class TailDuplicatePass : public MachineFunctionPass { 5979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng bool PreRegAlloc; 6015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson const TargetInstrInfo *TII; 6115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineModuleInfo *MMI; 62111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineRegisterInfo *MRI; 63111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 64111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 65111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SmallVector<unsigned, 16> SSAUpdateVRs; 66111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 67111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 68111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // source virtual registers. 69111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 7015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson public: 7215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson static char ID; 7379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng explicit TailDuplicatePass(bool PreRA) : 7490c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson MachineFunctionPass(ID), PreRegAlloc(PreRA) {} 7515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual bool runOnMachineFunction(MachineFunction &MF); 7715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual const char *getPassName() const { return "Tail Duplication"; } 7815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson private: 8011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 8111572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB); 8279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 8379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 8475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 850f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 86689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola const DenseSet<unsigned> &UsedByPhi, 87689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola bool Remove); 8879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void DuplicateInstruction(MachineInstr *MI, 8979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 9079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 9179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 920f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 930f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi); 9475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 9575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 9675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> &Succs); 9715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool TailDuplicateBlocks(MachineFunction &MF); 9854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola bool shouldTailDuplicate(const MachineFunction &MF, 999dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola bool IsSimple, MachineBasicBlock &TailBB); 100275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola bool isSimpleBB(MachineBasicBlock *TailBB); 10140179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola bool canCompletelyDuplicateBB(MachineBasicBlock &BB); 102d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola bool duplicateSimpleBB(MachineBasicBlock *TailBB, 103275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineBasicBlock*, 8> &TDBBs, 104275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola const DenseSet<unsigned> &RegsUsedByPhi, 105275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineInstr*, 16> &Copies); 1066a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool TailDuplicate(MachineBasicBlock *TailBB, 1076a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 1086a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF, 1093466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 1103466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> &Copies); 1116a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool TailDuplicateAndUpdate(MachineBasicBlock *MBB, 1126a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 1136a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF); 1146a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 11515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson void RemoveDeadBlock(MachineBasicBlock *MBB); 11615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson }; 11715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1182d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson char TailDuplicatePass::ID = 0; 11915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 12015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 12179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan ChengFunctionPass *llvm::createTailDuplicatePass(bool PreRegAlloc) { 12279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng return new TailDuplicatePass(PreRegAlloc); 12315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 12415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1252d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 12615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII = MF.getTarget().getInstrInfo(); 127111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MRI = &MF.getRegInfo(); 12815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 12915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 13015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 131057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen while (TailDuplicateBlocks(MF)) 132057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen MadeChange = true; 13315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 13415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 13515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 13615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 13775eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 13875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 13975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *MBB = I; 14075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 14175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->pred_end()); 14275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator MI = MBB->begin(); 14375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (MI != MBB->end()) { 144518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!MI->isPHI()) 14575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 14675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 14775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng PE = Preds.end(); PI != PE; ++PI) { 14875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PredBB = *PI; 14975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool Found = false; 15075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 15175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 15275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB == PredBB) { 15375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Found = true; 15475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 15575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 15675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 15775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!Found) { 15800dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 15900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " missing input from predecessor BB#" 16075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PredBB->getNumber() << '\n'; 16175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 16275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 16575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 16675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 16775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (CheckExtra && !Preds.count(PHIBB)) { 16800dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 16975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << ": " << *MI; 17000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " extra input from predecessor BB#" 17175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PHIBB->getNumber() << '\n'; 172d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola llvm_unreachable(0); 17375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 17475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB->getNumber() < 0) { 17500dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 17600dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 17775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 17875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 17975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++MI; 18175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng} 18475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 1856a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola/// TailDuplicateAndUpdate - Tail duplicate the block and cleanup. 1866a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindolabool 1876a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael EspindolaTailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB, 1886a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 1896a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF) { 1906a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Save the successors list. 1916a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 1926a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MBB->succ_end()); 1936a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 1946a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineBasicBlock*, 8> TDBBs; 1956a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineInstr*, 16> Copies; 1966a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!TailDuplicate(MBB, IsSimple, MF, TDBBs, Copies)) 1976a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola return false; 1986a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 1996a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++NumTails; 2006a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2016a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineInstr*, 8> NewPHIs; 2026a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 2036a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2046a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // TailBB's immediate successors are now successors of those predecessors 2056a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // which duplicated TailBB. Add the predecessors as sources to the PHI 2066a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // instructions. 2076a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); 2086a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (PreRegAlloc) 2096a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 2106a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2116a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // If it is dead, remove it. 2126a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (isDead) { 2136a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola NumInstrDups -= MBB->size(); 2146a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola RemoveDeadBlock(MBB); 2156a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++NumDeadBlocks; 2166a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2176a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2186a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Update SSA form. 2196a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!SSAUpdateVRs.empty()) { 2206a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 2216a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned VReg = SSAUpdateVRs[i]; 2226a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.Initialize(VReg); 2236a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2246a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // If the original definition is still around, add it as an available 2256a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // value. 2266a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineInstr *DefMI = MRI->getVRegDef(VReg); 2276a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineBasicBlock *DefBB = 0; 2286a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (DefMI) { 2296a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola DefBB = DefMI->getParent(); 2306a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.AddAvailableValue(DefBB, VReg); 2316a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2326a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2336a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Add the new vregs as available values. 2346a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola DenseMap<unsigned, AvailableValsTy>::iterator LI = 2356a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVals.find(VReg); 2366a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 2376a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineBasicBlock *SrcBB = LI->second[j].first; 2386a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned SrcReg = LI->second[j].second; 2396a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 2406a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2416a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2426a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Rewrite uses that are outside of the original def's block. 2436a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 2446a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola while (UI != MRI->use_end()) { 2456a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineOperand &UseMO = UI.getOperand(); 2466a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineInstr *UseMI = &*UI; 2476a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++UI; 2486a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (UseMI->isDebugValue()) { 2496a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // SSAUpdate can replace the use with an undef. That creates 2506a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // a debug instruction that is a kill. 2516a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // FIXME: Should it SSAUpdate job to delete debug instructions 2526a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // instead of replacing the use with undef? 2536a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola UseMI->eraseFromParent(); 2546a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2556a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2566a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (UseMI->getParent() == DefBB && !UseMI->isPHI()) 2576a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2586a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.RewriteUse(UseMO); 2596a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2606a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2616a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2626a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVRs.clear(); 2636a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVals.clear(); 2646a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2656a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2666a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Eliminate some of the copies inserted by tail duplication to maintain 2676a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // SSA form. 2686a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 2696a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineInstr *Copy = Copies[i]; 2706a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!Copy->isCopy()) 2716a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2726a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned Dst = Copy->getOperand(0).getReg(); 2736a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned Src = Copy->getOperand(1).getReg(); 2746a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); 2756a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (++UI == MRI->use_end()) { 2766a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Copy is the only use. Do trivial copy propagation here. 2776a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MRI->replaceRegWith(Dst, Src); 2786a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola Copy->eraseFromParent(); 2796a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2806a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2816a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2826a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (NewPHIs.size()) 2836a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola NumAddedPHIs += NewPHIs.size(); 2846a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2856a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola return true; 2866a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola} 2876a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 28815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// TailDuplicateBlocks - Look for small blocks that are unconditionally 28915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// branched to and do not fall through. Tail-duplicate their instructions 29015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// into their predecessors to eliminate (dynamic) branches. 2912d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 29215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 29315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 29475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) { 29500dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 29675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, true); 29775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 29875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 29915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 30015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *MBB = I++; 30115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 30275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (NumTails == TailDupLimit) 30375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 30475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3056a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple = isSimpleBB(MBB); 30675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3076a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!shouldTailDuplicate(MF, IsSimple, *MBB)) 308c0af352038e43bd51ef3ea11e7d43647e4df42bfRafael Espindola continue; 30975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3106a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MadeChange |= TailDuplicateAndUpdate(MBB, IsSimple, MF); 31115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 312c0af352038e43bd51ef3ea11e7d43647e4df42bfRafael Espindola 3136a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (PreRegAlloc && TailDupVerify) 3146a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola VerifyPHIs(MF, false); 315111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 31615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 31715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 31815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 319111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 320111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng const MachineRegisterInfo *MRI) { 321111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 322111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng UE = MRI->use_end(); UI != UE; ++UI) { 323111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineInstr *UseMI = &*UI; 324db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola if (UseMI->isDebugValue()) 325db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola continue; 326111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (UseMI->getParent() != BB) 327111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return true; 328111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 329111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return false; 330111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 331111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 332111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 333111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 334111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (MI->getOperand(i+1).getMBB() == SrcBB) 335111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return i; 336111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return 0; 337111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 338111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 3390f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 3400f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// Remember which registers are used by phis in this block. This is 3410f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// used to determine which registers are liveout while modifying the 3420f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// block (which is why we need to copy the information). 3430f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindolastatic void getRegsUsedByPHIs(const MachineBasicBlock &BB, 34433b465877255cc75241216817247c61374958a36Rafael Espindola DenseSet<unsigned> *UsedByPhi) { 3450f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola for(MachineBasicBlock::const_iterator I = BB.begin(), E = BB.end(); 3460f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola I != E; ++I) { 3470f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const MachineInstr &MI = *I; 3480f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (!MI.isPHI()) 3490f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola break; 3500f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 3510f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola unsigned SrcReg = MI.getOperand(i).getReg(); 3520f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola UsedByPhi->insert(SrcReg); 3530f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3540f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3550f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola} 3560f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 357111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 358111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// SSA update. 35911572babb12d169965c63c47aab9c9fad354e5dfEvan Chengvoid TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 36011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB) { 36111572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 362111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (LI != SSAUpdateVals.end()) 36311572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng LI->second.push_back(std::make_pair(BB, NewReg)); 364111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng else { 365111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng AvailableValsTy Vals; 36611572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng Vals.push_back(std::make_pair(BB, NewReg)); 367111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 368111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVRs.push_back(OrigReg); 369111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 370111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 371111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 37275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 37375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// Remember the source register that's contributed by PredBB and update SSA 37475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// update map. 37579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::ProcessPHI(MachineInstr *MI, 37679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 37779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 37875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 3790f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 38033b465877255cc75241216817247c61374958a36Rafael Espindola const DenseSet<unsigned> &RegsUsedByPhi, 381689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola bool Remove) { 38279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned DefReg = MI->getOperand(0).getReg(); 38379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 38479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(SrcOpIdx && "Unable to find matching PHI source?"); 38579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 38675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 38779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 38875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 38975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Insert a copy from source to the end of the block. The def register is the 39075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // available value liveout of the block. 39175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned NewDef = MRI->createVirtualRegister(RC); 39275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Copies.push_back(std::make_pair(NewDef, SrcReg)); 3930f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) 39475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng AddSSAUpdateEntry(DefReg, NewDef, PredBB); 39579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 396689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Remove) 397689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return; 398689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 39979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Remove PredBB from the PHI node. 40079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx+1); 40179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx); 40279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getNumOperands() == 1) 40379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 40479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 40579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 40679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 40779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// the source operands due to earlier PHI translation. 40879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 40979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 41079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 41179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 4120f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 4130f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi) { 41430ac0467ced4627a9b84d8a1d3ca5e8706ddad63Jakob Stoklund Olesen MachineInstr *NewMI = TII->duplicate(MI, MF); 41579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 41679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineOperand &MO = NewMI->getOperand(i); 41779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (!MO.isReg()) 41879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 41979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned Reg = MO.getReg(); 420c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 42179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 42279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MO.isDef()) { 42379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(Reg); 42479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned NewReg = MRI->createVirtualRegister(RC); 42579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(NewReg); 42679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(Reg, NewReg)); 4270f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) 42811572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng AddSSAUpdateEntry(Reg, NewReg, PredBB); 42979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 43079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 43179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (VI != LocalVRMap.end()) 43279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(VI->second); 43379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 43479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 43579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->insert(PredBB->end(), NewMI); 43679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 43779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 43879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 43979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// blocks, the successors have gained new predecessors. Update the PHI 44079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// instructions in them accordingly. 44175eb53584367098a5625028e22f1ff8e169d0efdEvan Chengvoid 44275eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 44375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 44479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*,8> &Succs) { 44579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 44679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SE = Succs.end(); SI != SE; ++SI) { 44779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *SuccBB = *SI; 44879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 44979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng II != EE; ++II) { 450518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!II->isPHI()) 45179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 45275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Idx = 0; 45379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 45475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 45575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 45675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Idx = i; 45779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 45875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 45975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 46075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 46175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng assert(Idx != 0); 46275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO0 = II->getOperand(Idx); 46375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Reg = MO0.getReg(); 46475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 46575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Folded into the previous BB. 46675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // There could be duplicate phi source entries. FIXME: Should sdisel 46775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // or earlier pass fixed this? 46875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 46975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 47075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 47175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i+1); 47275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i); 47375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 47475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 47509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else 47609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 47709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 47809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // If Idx is set, the operands at Idx and Idx+1 must be removed. 47909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // We reuse the location to avoid expensive RemoveOperand calls. 48009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 48175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 48275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (LI != SSAUpdateVals.end()) { 48375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // This register is defined in the tail block. 48479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 48511572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 486d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // If we didn't duplicate a bb into a particular predecessor, we 487d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // might still have added an entry to SSAUpdateVals to correcly 488d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // recompute SSA. If that case, avoid adding a dummy extra argument 489d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // this PHI. 490d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola if (!SrcBB->isSuccessor(SuccBB)) 491d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola continue; 492d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola 49311572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng unsigned SrcReg = LI->second[j].second; 49409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 49509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(SrcReg); 49609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 49709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 49809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 49909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 50009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(SrcBB)); 50109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 50279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 50375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } else { 50475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Live in tail block, must also be live in predecessors. 50575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 50675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = TDBBs[j]; 50709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 50809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(Reg); 50909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 51009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 51109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 51209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(Reg, false)); 51309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(SrcBB)); 51409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 51575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 51679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 51709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 51809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx+1); 51909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx); 52009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 52179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 52279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 52379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 52479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 52554c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// shouldTailDuplicate - Determine if it is profitable to duplicate this block. 52675eb53584367098a5625028e22f1ff8e169d0efdEvan Chengbool 52754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael EspindolaTailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF, 5289dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola bool IsSimple, 52954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola MachineBasicBlock &TailBB) { 53054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola // Only duplicate blocks that end with unconditional branches. 53154c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola if (TailBB.canFallThrough()) 53254c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola return false; 53354c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 534ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Don't try to tail-duplicate single-block loops. 535ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (TailBB.isSuccessor(&TailBB)) 536ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 537ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 53854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola // Set the limit on the cost to duplicate. When optimizing for size, 53915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // duplicate only one, because one branch instruction can be eliminated to 54015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // compensate for the duplication. 54115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson unsigned MaxDuplicateCount; 5428352062e52eed6e50786fdb89f5e601fdcbe0d90Jakob Stoklund Olesen if (TailDuplicateSize.getNumOccurrences() == 0 && 5438352062e52eed6e50786fdb89f5e601fdcbe0d90Jakob Stoklund Olesen MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 544cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = 1; 545cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson else 546cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = TailDuplicateSize; 547cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson 548ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // If the target has hardware branch prediction that can handle indirect 549ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // branches, duplicating them can often make them predictable when there 550ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // are common paths through the code. The limit needs to be high enough 551ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // to allow undoing the effects of tail merging and other optimizations 552ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // that rearrange the predecessors of the indirect branch. 553ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 5546a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool HasIndirectbr = false; 5556a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!TailBB.empty()) 5566a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola HasIndirectbr = TailBB.back().getDesc().isIndirectBranch(); 5576a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 5586a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (HasIndirectbr && PreRegAlloc) 5596a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MaxDuplicateCount = 20; 56015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 56115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Check the instructions in the block to determine whether tail-duplication 56215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // is invalid or unlikely to be profitable. 563f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson unsigned InstrCount = 0; 56454c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola for (MachineBasicBlock::const_iterator I = TailBB.begin(); I != TailBB.end(); 56554c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola ++I) { 56615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Non-duplicable things shouldn't be tail-duplicated. 567ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (I->getDesc().isNotDuplicable()) 568ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 569ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 57079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Do not duplicate 'return' instructions if this is a pre-regalloc run. 57179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // A return may expand into a lot more instructions (e.g. reload of callee 57279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // saved registers) after PEI. 573ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (PreRegAlloc && I->getDesc().isReturn()) 574ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 575ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 576ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Avoid duplicating calls before register allocation. Calls presents a 577ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // barrier to register allocation so duplicating them may end up increasing 578ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // spills. 579ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (PreRegAlloc && I->getDesc().isCall()) 580ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 581ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 582cbe1e31732c5d4fb1277195e76b9b42c115396aaDevang Patel if (!I->isPHI() && !I->isDebugValue()) 583f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson InstrCount += 1; 584ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 585ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (InstrCount > MaxDuplicateCount) 586ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 58715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 58815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 5896a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (HasIndirectbr && PreRegAlloc) 5909dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return true; 5919dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 5929dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (IsSimple) 593d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return true; 5949dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 5959dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (!PreRegAlloc) 5969dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return true; 5979dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 59840179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola return canCompletelyDuplicateBB(TailBB); 59954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola} 60054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 601275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola/// isSimpleBB - True if this BB has only one unconditional jump. 602275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolabool 603275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolaTailDuplicatePass::isSimpleBB(MachineBasicBlock *TailBB) { 604275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (TailBB->succ_size() != 1) 605275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 6069dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (TailBB->pred_empty()) 6079dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return false; 608d6379a993c7e40521bd5c8c6469e32697b4c41d1Rafael Espindola MachineBasicBlock::iterator I = TailBB->begin(); 609275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock::iterator E = TailBB->end(); 610d6379a993c7e40521bd5c8c6469e32697b4c41d1Rafael Espindola while (I != E && I->isDebugValue()) 611275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola ++I; 612275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (I == E) 613275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 614275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return I->getDesc().isUnconditionalBranch(); 615275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 616275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 617275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolastatic bool 618275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolabothUsedInPHI(const MachineBasicBlock &A, 619275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallPtrSet<MachineBasicBlock*, 8> SuccsB) { 620275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (MachineBasicBlock::const_succ_iterator SI = A.succ_begin(), 621275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SE = A.succ_end(); SI != SE; ++SI) { 622275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *BB = *SI; 623275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI()) 624275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 625275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 626275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 627275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 628275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 629275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 630275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolabool 63140179bf8748b2729d6c733022428dfa1061325c9Rafael EspindolaTailDuplicatePass::canCompletelyDuplicateBB(MachineBasicBlock &BB) { 632275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallPtrSet<MachineBasicBlock*, 8> Succs(BB.succ_begin(), BB.succ_end()); 633275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 634275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (MachineBasicBlock::pred_iterator PI = BB.pred_begin(), 635275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PE = BB.pred_end(); PI != PE; ++PI) { 636275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredBB = *PI; 6379dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 63840179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola if (PredBB->succ_size() > 1) 63940179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola return false; 6409dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 641275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL; 642275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineOperand, 4> PredCond; 643275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 644275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 6459dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 64640179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola if (!PredCond.empty()) 6479dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return false; 648275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 649275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 650275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 651275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 652d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindolabool 653275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolaTailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB, 654275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineBasicBlock*, 8> &TDBBs, 655275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola const DenseSet<unsigned> &UsedByPhi, 656275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineInstr*, 16> &Copies) { 657d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola SmallPtrSet<MachineBasicBlock*, 8> Succs(TailBB->succ_begin(), 658d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola TailBB->succ_end()); 659275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 660275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TailBB->pred_end()); 661d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola bool Changed = false; 662275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 663275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PE = Preds.end(); PI != PE; ++PI) { 664275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredBB = *PI; 665275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 666d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (PredBB->getLandingPadSuccessor()) 667d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 668d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola 669d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (bothUsedInPHI(*PredBB, Succs)) 670d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 671d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola 672275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL; 673275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineOperand, 4> PredCond; 674d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 675d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 676275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 677d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola Changed = true; 678275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 679275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola << "From simple Succ: " << *TailBB); 680275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 681275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *NewTarget = *TailBB->succ_begin(); 682289a27946fc11ae6b5a9aa517639d94efa4d91d9Francois Pichet MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(PredBB)); 683275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 684275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make PredFBB explicit. 685275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredCond.empty()) 686275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = PredTBB; 687275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 688275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make fall through explicit. 689275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (!PredTBB) 690275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredTBB = NextBB; 691275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (!PredFBB) 692275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NextBB; 693275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 694275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Redirect 695275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredFBB == TailBB) 696275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NewTarget; 697275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredTBB == TailBB) 698275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredTBB = NewTarget; 699275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 700275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make the branch unconditional if possible 701689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola if (PredTBB == PredFBB) { 702689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola PredCond.clear(); 703275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NULL; 704689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola } 705275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 706275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Avoid adding fall through branches. 707275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredFBB == NextBB) 708275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NULL; 709275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredTBB == NextBB && PredFBB == NULL) 710275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredTBB = NULL; 711275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 712275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TII->RemoveBranch(*PredBB); 713275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 714275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredTBB) 715275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc()); 716275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 717275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredBB->removeSuccessor(TailBB); 718689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola unsigned NumSuccessors = PredBB->succ_size(); 719689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola assert(NumSuccessors <= 1); 720689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget) 721689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola PredBB->addSuccessor(NewTarget); 722275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 723275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TDBBs.push_back(PredBB); 724275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 725d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return Changed; 726275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 727275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 72854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 72954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// of its predecessors. 73054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindolabool 7316a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael EspindolaTailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, 7326a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 7336a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF, 73454c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola SmallVector<MachineBasicBlock*, 8> &TDBBs, 73554c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola SmallVector<MachineInstr*, 16> &Copies) { 73600dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 73775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 738275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola DenseSet<unsigned> UsedByPhi; 739275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola getRegsUsedByPHIs(*TailBB, &UsedByPhi); 740275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 741d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (IsSimple) 742d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies); 743275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 74415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Iterate through all the unique predecessors and tail-duplicate this 74515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into them, if possible. Copying the list ahead of time also 74615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // avoids trouble with the predecessor list reallocating. 74715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool Changed = false; 74879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 74979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_end()); 75015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 75115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PE = Preds.end(); PI != PE; ++PI) { 75215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredBB = *PI; 75315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 75415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(TailBB != PredBB && 75515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "Single-block loop should have been rejected earlier!"); 7569a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola // EH edges are ignored by AnalyzeBranch. 7579a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola if (PredBB->succ_size() > 1) 7589a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola continue; 75915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 76015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredTBB, *PredFBB; 76115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PredCond; 76215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 76315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 76415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PredCond.empty()) 76515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 76615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate into a fall-through predecessor (at least for now). 76715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 76815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 76915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 77000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 77115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From Succ: " << *TailBB); 77215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 77375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PredBB); 77475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 77515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove PredBB's unconditional branch. 77615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII->RemoveBranch(*PredBB); 777111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 77815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Clone the contents of TailBB into PredBB. 779111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 7803466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 781111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 78279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 78379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I; 78479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng ++I; 785518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isPHI()) { 786111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // Replace the uses of the def of the PHI with the register coming 787111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // from PredBB. 788689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); 78979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 79079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 79179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 7920f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi); 793111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 79415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 79575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 7963466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 7971e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 7981e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 7991e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first).addReg(CopyInfos[i].second)); 80075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 801ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 802ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Simplify 803ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true); 804ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 80515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 80615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 80715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Update the CFG. 80815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PredBB->removeSuccessor(PredBB->succ_begin()); 80915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(PredBB->succ_empty() && 81015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "TailDuplicate called on block with multiple successors!"); 81115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 81279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng E = TailBB->succ_end(); I != E; ++I) 81379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->addSuccessor(*I); 81415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 81515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 81615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson ++NumTailDups; 81715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 81815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 81915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If TailBB was duplicated into all its predecessors except for the prior 82015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block, which falls through unconditionally, move the contents of this 82115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into the prior block. 82279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 82315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 82415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PriorCond; 82515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // This has to check PrevBB->succ_size() because EH edges are ignored by 82615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // AnalyzeBranch. 827a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola if (PrevBB->succ_size() == 1 && 828a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola !TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true) && 829a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola PriorCond.empty() && !PriorTBB && TailBB->pred_size() == 1 && 83015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !TailBB->hasAddressTaken()) { 83100dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 83215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From MBB: " << *TailBB); 83379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc) { 83479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 8353466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 83679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 83779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Process PHI instructions first. 838518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (I != TailBB->end() && I->isPHI()) { 83979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace the uses of the def of the PHI with the register coming 84079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // from PredBB. 84179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 842689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); 84379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getParent()) 84479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 84579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 84679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 84779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Now copy the non-PHI instructions. 84879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 84979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 85079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 85179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 8520f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi); 85379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 85479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 85575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 8563466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 8571e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 8581e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 8591e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first) 8601e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen .addReg(CopyInfos[i].second)); 86175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 86279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 86379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // No PHIs to worry about, just splice the instructions over. 86479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 86579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 86679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->removeSuccessor(PrevBB->succ_begin()); 86779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(PrevBB->succ_empty()); 86879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->transferSuccessors(TailBB); 86975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PrevBB); 87015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 87115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 87215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 873689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If this is after register allocation, there are no phis to fix. 874689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!PreRegAlloc) 875689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 876689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 877689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If we made no changes so far, we are safe. 878689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Changed) 879689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 880689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 881689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 882689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Handle the nasty case in that we duplicated a block that is part of a loop 883689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // into some but not all of its predecessors. For example: 8844d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 1 -> 2 <-> 3 | 8854d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ | 8864d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \---> rest | 887689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // if we duplicate 2 into 1 but not into 3, we end up with 8884d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 12 -> 3 <-> 2 -> rest | 8894d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ / | 8904d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \----->-----/ | 891689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced 892689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // with a phi in 3 (which now dominates 2). 893689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // What we do here is introduce a copy in 3 of the register defined by the 894689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // phi, just like when we are duplicating 2 into 3, but we don't copy any 895689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // real instructions or remove the 3 -> 2 edge from the phi in 2. 896689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 897689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola PE = Preds.end(); PI != PE; ++PI) { 898689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock *PredBB = *PI; 899689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (std::find(TDBBs.begin(), TDBBs.end(), PredBB) != TDBBs.end()) 900689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 901689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 902689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // EH edges 903689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (PredBB->succ_size() != 1) 904689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 905689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 906689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola DenseMap<unsigned, unsigned> LocalVRMap; 907689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 908689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator I = TailBB->begin(); 909689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Process PHI instructions first. 910689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola while (I != TailBB->end() && I->isPHI()) { 911689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Replace the uses of the def of the PHI with the register coming 912689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // from PredBB. 913689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineInstr *MI = &*I++; 914689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); 915689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 916689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 917689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 918689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 919689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola TII->get(TargetOpcode::COPY), 920689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola CopyInfos[i].first).addReg(CopyInfos[i].second)); 921689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 922689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 923689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 92415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return Changed; 92515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 92615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 92715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// RemoveDeadBlock - Remove the specified dead machine basic block from the 92815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// function, updating the CFG. 9292d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonvoid TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 93015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(MBB->pred_empty() && "MBB must be dead!"); 93100dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 93215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 93315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove all successors. 93415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson while (!MBB->succ_empty()) 93515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->removeSuccessor(MBB->succ_end()-1); 93615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 93715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove the block. 93815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->eraseFromParent(); 93915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 940