TailDuplication.cpp revision 7b79b9862c9e6fc31ec072acb09171fd6ec7b0e0
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/CodeGen/Passes.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseSet.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/OwningPtr.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SetVector.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallSet.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 2215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/CodeGen/MachineFunctionPass.h" 231e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineModuleInfo.h" 25111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 26111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineSSAUpdater.h" 27eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng#include "llvm/CodeGen/RegisterScavenging.h" 28d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Function.h" 2915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/CommandLine.h" 3015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/Debug.h" 3175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng#include "llvm/Support/ErrorHandling.h" 3215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/raw_ostream.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 3515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonusing namespace llvm; 3615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 3775eb53584367098a5625028e22f1ff8e169d0efdEvan ChengSTATISTIC(NumTails , "Number of tails duplicated"); 3815acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumTailDups , "Number of tail duplicated blocks"); 3915acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 4015acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 410cdca089b289845664d660f0b285499800822919Rafael EspindolaSTATISTIC(NumAddedPHIs , "Number of phis added"); 4215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// Heuristic for tail duplication. 4415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonstatic cl::opt<unsigned> 4515acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonTailDuplicateSize("tail-dup-size", 4615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::desc("Maximum instructions to consider tail duplicating"), 4715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::init(2), cl::Hidden); 4815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4975eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<bool> 5075eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupVerify("tail-dup-verify", 5175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::desc("Verify sanity of PHI instructions during taildup"), 5275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::init(false), cl::Hidden); 5375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5475eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<unsigned> 5575eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 5675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5711572babb12d169965c63c47aab9c9fad354e5dfEvan Chengtypedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 58111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 5915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonnamespace { 602d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson /// TailDuplicatePass - Perform tail duplication. 612d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson class TailDuplicatePass : public MachineFunctionPass { 6215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson const TargetInstrInfo *TII; 63eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng const TargetRegisterInfo *TRI; 6415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineModuleInfo *MMI; 65111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineRegisterInfo *MRI; 66d14e4e133f940d0c1f454a40f3bd835a8c7a7886Benjamin Kramer OwningPtr<RegScavenger> RS; 67d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick bool PreRegAlloc; 68111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 69111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 70111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SmallVector<unsigned, 16> SSAUpdateVRs; 71111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 72111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 73111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // source virtual registers. 74111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 7515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson public: 7715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson static char ID; 78d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick explicit TailDuplicatePass() : 79d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick MachineFunctionPass(ID), PreRegAlloc(false) {} 8015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 8115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual bool runOnMachineFunction(MachineFunction &MF); 8215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 8315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson private: 8411572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 8511572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB); 8679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 8779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 8875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 890f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 90689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola const DenseSet<unsigned> &UsedByPhi, 91689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola bool Remove); 9279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void DuplicateInstruction(MachineInstr *MI, 9379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 9479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 9579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 960f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 970f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi); 9875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 9975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 10075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> &Succs); 10115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool TailDuplicateBlocks(MachineFunction &MF); 10254c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola bool shouldTailDuplicate(const MachineFunction &MF, 1039dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola bool IsSimple, MachineBasicBlock &TailBB); 104275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola bool isSimpleBB(MachineBasicBlock *TailBB); 10540179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola bool canCompletelyDuplicateBB(MachineBasicBlock &BB); 106d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola bool duplicateSimpleBB(MachineBasicBlock *TailBB, 107275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineBasicBlock*, 8> &TDBBs, 108275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola const DenseSet<unsigned> &RegsUsedByPhi, 109275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineInstr*, 16> &Copies); 1106a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool TailDuplicate(MachineBasicBlock *TailBB, 1116a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 1126a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF, 1133466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 1143466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> &Copies); 1156a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool TailDuplicateAndUpdate(MachineBasicBlock *MBB, 1166a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 1176a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF); 1186a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 11915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson void RemoveDeadBlock(MachineBasicBlock *MBB); 12015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson }; 12115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1222d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson char TailDuplicatePass::ID = 0; 12315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 12415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1251dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::TailDuplicateID = TailDuplicatePass::ID; 1261dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trick 1271dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew TrickINITIALIZE_PASS(TailDuplicatePass, "tailduplication", "Tail Duplication", 1281dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trick false, false) 12915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1302d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 13115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII = MF.getTarget().getInstrInfo(); 132eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng TRI = MF.getTarget().getRegisterInfo(); 133111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MRI = &MF.getRegInfo(); 13415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 135d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick PreRegAlloc = MRI->isSSA(); 136d14e4e133f940d0c1f454a40f3bd835a8c7a7886Benjamin Kramer RS.reset(); 137eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (MRI->tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF)) 138d14e4e133f940d0c1f454a40f3bd835a8c7a7886Benjamin Kramer RS.reset(new RegScavenger()); 13915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 14015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 141057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen while (TailDuplicateBlocks(MF)) 142057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen MadeChange = true; 14315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 14415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 14515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 14615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 14775eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 14875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 14975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *MBB = I; 15075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 15175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->pred_end()); 15275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator MI = MBB->begin(); 15375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (MI != MBB->end()) { 154518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!MI->isPHI()) 15575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 15675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 15775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng PE = Preds.end(); PI != PE; ++PI) { 15875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PredBB = *PI; 15975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool Found = false; 16075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 16175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 16275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB == PredBB) { 16375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Found = true; 16475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 16575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!Found) { 16800dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 16900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " missing input from predecessor BB#" 17075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PredBB->getNumber() << '\n'; 17175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 17275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 17375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 17475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 17575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 17675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 17775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (CheckExtra && !Preds.count(PHIBB)) { 17800dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 17975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << ": " << *MI; 18000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " extra input from predecessor BB#" 18175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PHIBB->getNumber() << '\n'; 182d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola llvm_unreachable(0); 18375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB->getNumber() < 0) { 18500dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 18600dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 18775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 18875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 19075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++MI; 19175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 19275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 19375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng} 19475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 1956a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola/// TailDuplicateAndUpdate - Tail duplicate the block and cleanup. 1966a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindolabool 1976a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael EspindolaTailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB, 1986a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 1996a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF) { 2006a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Save the successors list. 2016a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 2026a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MBB->succ_end()); 2036a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2046a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineBasicBlock*, 8> TDBBs; 2056a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineInstr*, 16> Copies; 2066a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!TailDuplicate(MBB, IsSimple, MF, TDBBs, Copies)) 2076a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola return false; 2086a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2096a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++NumTails; 2106a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2116a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineInstr*, 8> NewPHIs; 2126a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 2136a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2146a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // TailBB's immediate successors are now successors of those predecessors 2156a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // which duplicated TailBB. Add the predecessors as sources to the PHI 2166a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // instructions. 2176a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); 2186a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (PreRegAlloc) 2196a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 2206a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2216a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // If it is dead, remove it. 2226a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (isDead) { 2236a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola NumInstrDups -= MBB->size(); 2246a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola RemoveDeadBlock(MBB); 2256a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++NumDeadBlocks; 2266a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2276a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2286a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Update SSA form. 2296a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!SSAUpdateVRs.empty()) { 2306a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 2316a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned VReg = SSAUpdateVRs[i]; 2326a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.Initialize(VReg); 2336a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2346a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // If the original definition is still around, add it as an available 2356a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // value. 2366a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineInstr *DefMI = MRI->getVRegDef(VReg); 2376a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineBasicBlock *DefBB = 0; 2386a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (DefMI) { 2396a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola DefBB = DefMI->getParent(); 2406a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.AddAvailableValue(DefBB, VReg); 2416a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2426a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2436a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Add the new vregs as available values. 2446a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola DenseMap<unsigned, AvailableValsTy>::iterator LI = 2456a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVals.find(VReg); 2466a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 2476a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineBasicBlock *SrcBB = LI->second[j].first; 2486a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned SrcReg = LI->second[j].second; 2496a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 2506a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2516a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2526a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Rewrite uses that are outside of the original def's block. 2536a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 2546a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola while (UI != MRI->use_end()) { 2556a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineOperand &UseMO = UI.getOperand(); 2566a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineInstr *UseMI = &*UI; 2576a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++UI; 2586a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (UseMI->isDebugValue()) { 2596a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // SSAUpdate can replace the use with an undef. That creates 2606a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // a debug instruction that is a kill. 2616a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // FIXME: Should it SSAUpdate job to delete debug instructions 2626a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // instead of replacing the use with undef? 2636a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola UseMI->eraseFromParent(); 2646a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2656a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2666a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (UseMI->getParent() == DefBB && !UseMI->isPHI()) 2676a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2686a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.RewriteUse(UseMO); 2696a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2706a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2716a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2726a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVRs.clear(); 2736a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVals.clear(); 2746a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2756a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2766a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Eliminate some of the copies inserted by tail duplication to maintain 2776a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // SSA form. 2786a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 2796a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineInstr *Copy = Copies[i]; 2806a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!Copy->isCopy()) 2816a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2826a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned Dst = Copy->getOperand(0).getReg(); 2836a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned Src = Copy->getOperand(1).getReg(); 2840fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen if (MRI->hasOneNonDBGUse(Src) && 2850fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) { 2866a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Copy is the only use. Do trivial copy propagation here. 2876a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MRI->replaceRegWith(Dst, Src); 2886a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola Copy->eraseFromParent(); 2896a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2906a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2916a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2926a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (NewPHIs.size()) 2936a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola NumAddedPHIs += NewPHIs.size(); 2946a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2956a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola return true; 2966a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola} 2976a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 29815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// TailDuplicateBlocks - Look for small blocks that are unconditionally 29915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// branched to and do not fall through. Tail-duplicate their instructions 30015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// into their predecessors to eliminate (dynamic) branches. 3012d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 30215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 30315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 30475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) { 30500dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 30675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, true); 30775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 30875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 30915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 31015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *MBB = I++; 31115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 31275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (NumTails == TailDupLimit) 31375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 31475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3156a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple = isSimpleBB(MBB); 31675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3176a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!shouldTailDuplicate(MF, IsSimple, *MBB)) 318c0af352038e43bd51ef3ea11e7d43647e4df42bfRafael Espindola continue; 31975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3206a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MadeChange |= TailDuplicateAndUpdate(MBB, IsSimple, MF); 32115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 322c0af352038e43bd51ef3ea11e7d43647e4df42bfRafael Espindola 3236a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (PreRegAlloc && TailDupVerify) 3246a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola VerifyPHIs(MF, false); 325111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 32615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 32715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 32815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 329111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 330111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng const MachineRegisterInfo *MRI) { 331111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 332111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng UE = MRI->use_end(); UI != UE; ++UI) { 333111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineInstr *UseMI = &*UI; 334db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola if (UseMI->isDebugValue()) 335db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola continue; 336111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (UseMI->getParent() != BB) 337111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return true; 338111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 339111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return false; 340111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 341111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 342111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 343111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 344111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (MI->getOperand(i+1).getMBB() == SrcBB) 345111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return i; 346111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return 0; 347111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 348111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 3490f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 3500f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// Remember which registers are used by phis in this block. This is 3510f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// used to determine which registers are liveout while modifying the 3520f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// block (which is why we need to copy the information). 3530f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindolastatic void getRegsUsedByPHIs(const MachineBasicBlock &BB, 35433b465877255cc75241216817247c61374958a36Rafael Espindola DenseSet<unsigned> *UsedByPhi) { 3550f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola for(MachineBasicBlock::const_iterator I = BB.begin(), E = BB.end(); 3560f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola I != E; ++I) { 3570f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const MachineInstr &MI = *I; 3580f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (!MI.isPHI()) 3590f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola break; 3600f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 3610f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola unsigned SrcReg = MI.getOperand(i).getReg(); 3620f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola UsedByPhi->insert(SrcReg); 3630f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3640f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3650f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola} 3660f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 367111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 368111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// SSA update. 36911572babb12d169965c63c47aab9c9fad354e5dfEvan Chengvoid TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 37011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB) { 37111572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 372111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (LI != SSAUpdateVals.end()) 37311572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng LI->second.push_back(std::make_pair(BB, NewReg)); 374111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng else { 375111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng AvailableValsTy Vals; 37611572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng Vals.push_back(std::make_pair(BB, NewReg)); 377111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 378111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVRs.push_back(OrigReg); 379111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 380111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 381111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 38275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 38375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// Remember the source register that's contributed by PredBB and update SSA 38475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// update map. 38579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::ProcessPHI(MachineInstr *MI, 38679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 38779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 38875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 3890f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 39033b465877255cc75241216817247c61374958a36Rafael Espindola const DenseSet<unsigned> &RegsUsedByPhi, 391689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola bool Remove) { 39279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned DefReg = MI->getOperand(0).getReg(); 39379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 39479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(SrcOpIdx && "Unable to find matching PHI source?"); 39579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 39675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 39779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 39875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 39975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Insert a copy from source to the end of the block. The def register is the 40075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // available value liveout of the block. 40175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned NewDef = MRI->createVirtualRegister(RC); 40275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Copies.push_back(std::make_pair(NewDef, SrcReg)); 4030f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) 40475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng AddSSAUpdateEntry(DefReg, NewDef, PredBB); 40579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 406689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Remove) 407689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return; 408689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 40979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Remove PredBB from the PHI node. 41079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx+1); 41179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx); 41279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getNumOperands() == 1) 41379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 41479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 41579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 41679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 41779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// the source operands due to earlier PHI translation. 41879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 41979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 42079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 42179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 4220f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 4230f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi) { 42430ac0467ced4627a9b84d8a1d3ca5e8706ddad63Jakob Stoklund Olesen MachineInstr *NewMI = TII->duplicate(MI, MF); 42579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 42679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineOperand &MO = NewMI->getOperand(i); 42779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (!MO.isReg()) 42879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 42979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned Reg = MO.getReg(); 430c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 43179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 43279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MO.isDef()) { 43379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(Reg); 43479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned NewReg = MRI->createVirtualRegister(RC); 43579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(NewReg); 43679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(Reg, NewReg)); 4370f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) 43811572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng AddSSAUpdateEntry(Reg, NewReg, PredBB); 43979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 44079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 4410fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen if (VI != LocalVRMap.end()) { 44279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(VI->second); 4430fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen MRI->constrainRegClass(VI->second, MRI->getRegClass(Reg)); 4440fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen } 44579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 44679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 447df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng PredBB->insert(PredBB->instr_end(), NewMI); 44879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 44979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 45079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 45179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// blocks, the successors have gained new predecessors. Update the PHI 45279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// instructions in them accordingly. 45375eb53584367098a5625028e22f1ff8e169d0efdEvan Chengvoid 45475eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 45575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 45679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*,8> &Succs) { 45779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 45879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SE = Succs.end(); SI != SE; ++SI) { 45979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *SuccBB = *SI; 46079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 46179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng II != EE; ++II) { 462518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!II->isPHI()) 46379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 4647b79b9862c9e6fc31ec072acb09171fd6ec7b0e0Jakob Stoklund Olesen MachineInstrBuilder MIB(*FromBB->getParent(), II); 46575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Idx = 0; 46679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 46775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 46875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 46975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Idx = i; 47079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 47175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 47275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 47375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 47475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng assert(Idx != 0); 47575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO0 = II->getOperand(Idx); 47675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Reg = MO0.getReg(); 47775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 47875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Folded into the previous BB. 47975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // There could be duplicate phi source entries. FIXME: Should sdisel 48075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // or earlier pass fixed this? 48175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 48275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 48375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 48475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i+1); 48575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i); 48675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 48775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 48809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else 48909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 49009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 49109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // If Idx is set, the operands at Idx and Idx+1 must be removed. 49209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // We reuse the location to avoid expensive RemoveOperand calls. 49309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 49475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 49575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (LI != SSAUpdateVals.end()) { 49675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // This register is defined in the tail block. 49779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 49811572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 499d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // If we didn't duplicate a bb into a particular predecessor, we 500d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // might still have added an entry to SSAUpdateVals to correcly 501d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // recompute SSA. If that case, avoid adding a dummy extra argument 502d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // this PHI. 503d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola if (!SrcBB->isSuccessor(SuccBB)) 504d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola continue; 505d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola 50611572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng unsigned SrcReg = LI->second[j].second; 50709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 50809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(SrcReg); 50909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 51009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 51109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 5127b79b9862c9e6fc31ec072acb09171fd6ec7b0e0Jakob Stoklund Olesen MIB.addReg(SrcReg).addMBB(SrcBB); 51309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 51479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 51575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } else { 51675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Live in tail block, must also be live in predecessors. 51775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 51875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = TDBBs[j]; 51909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 52009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(Reg); 52109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 52209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 52309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 5247b79b9862c9e6fc31ec072acb09171fd6ec7b0e0Jakob Stoklund Olesen MIB.addReg(Reg).addMBB(SrcBB); 52509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 52675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 52779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 52809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 52909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx+1); 53009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx); 53109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 53279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 53379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 53479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 53579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 53654c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// shouldTailDuplicate - Determine if it is profitable to duplicate this block. 53775eb53584367098a5625028e22f1ff8e169d0efdEvan Chengbool 53854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael EspindolaTailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF, 5399dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola bool IsSimple, 54054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola MachineBasicBlock &TailBB) { 54154c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola // Only duplicate blocks that end with unconditional branches. 54254c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola if (TailBB.canFallThrough()) 54354c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola return false; 54454c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 545ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Don't try to tail-duplicate single-block loops. 546ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (TailBB.isSuccessor(&TailBB)) 547ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 548ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 54954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola // Set the limit on the cost to duplicate. When optimizing for size, 55015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // duplicate only one, because one branch instruction can be eliminated to 55115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // compensate for the duplication. 55215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson unsigned MaxDuplicateCount; 5538352062e52eed6e50786fdb89f5e601fdcbe0d90Jakob Stoklund Olesen if (TailDuplicateSize.getNumOccurrences() == 0 && 5546765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling MF.getFunction()->getFnAttributes(). 555034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling hasAttribute(Attribute::OptimizeForSize)) 556cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = 1; 557cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson else 558cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = TailDuplicateSize; 559cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson 560ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // If the target has hardware branch prediction that can handle indirect 561ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // branches, duplicating them can often make them predictable when there 562ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // are common paths through the code. The limit needs to be high enough 563ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // to allow undoing the effects of tail merging and other optimizations 564ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // that rearrange the predecessors of the indirect branch. 565ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 5666a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool HasIndirectbr = false; 5676a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!TailBB.empty()) 5685a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng HasIndirectbr = TailBB.back().isIndirectBranch(); 5696a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 5706a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (HasIndirectbr && PreRegAlloc) 5716a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MaxDuplicateCount = 20; 57215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 57315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Check the instructions in the block to determine whether tail-duplication 57415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // is invalid or unlikely to be profitable. 575f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson unsigned InstrCount = 0; 5767c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng for (MachineBasicBlock::iterator I = TailBB.begin(); I != TailBB.end(); ++I) { 57715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Non-duplicable things shouldn't be tail-duplicated. 5785a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (I->isNotDuplicable()) 579ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 580ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 58179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Do not duplicate 'return' instructions if this is a pre-regalloc run. 58279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // A return may expand into a lot more instructions (e.g. reload of callee 58379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // saved registers) after PEI. 5845a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (PreRegAlloc && I->isReturn()) 585ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 586ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 587ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Avoid duplicating calls before register allocation. Calls presents a 588ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // barrier to register allocation so duplicating them may end up increasing 589ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // spills. 5905a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (PreRegAlloc && I->isCall()) 591ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 592ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 593cbe1e31732c5d4fb1277195e76b9b42c115396aaDevang Patel if (!I->isPHI() && !I->isDebugValue()) 594f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson InstrCount += 1; 595ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 596ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (InstrCount > MaxDuplicateCount) 597ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 59815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 59915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 6006a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (HasIndirectbr && PreRegAlloc) 6019dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return true; 6029dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 6039dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (IsSimple) 604d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return true; 6059dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 6069dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (!PreRegAlloc) 6079dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return true; 6089dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 60940179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola return canCompletelyDuplicateBB(TailBB); 61054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola} 61154c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 612275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola/// isSimpleBB - True if this BB has only one unconditional jump. 613275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolabool 614275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolaTailDuplicatePass::isSimpleBB(MachineBasicBlock *TailBB) { 615275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (TailBB->succ_size() != 1) 616275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 6179dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (TailBB->pred_empty()) 6189dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return false; 619d6379a993c7e40521bd5c8c6469e32697b4c41d1Rafael Espindola MachineBasicBlock::iterator I = TailBB->begin(); 620275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock::iterator E = TailBB->end(); 621d6379a993c7e40521bd5c8c6469e32697b4c41d1Rafael Espindola while (I != E && I->isDebugValue()) 622275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola ++I; 623275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (I == E) 624275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 6255a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng return I->isUnconditionalBranch(); 626275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 627275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 628275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolastatic bool 629275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolabothUsedInPHI(const MachineBasicBlock &A, 630275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallPtrSet<MachineBasicBlock*, 8> SuccsB) { 631275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (MachineBasicBlock::const_succ_iterator SI = A.succ_begin(), 632275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SE = A.succ_end(); SI != SE; ++SI) { 633275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *BB = *SI; 634275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI()) 635275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 636275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 637275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 638275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 639275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 640275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 641275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolabool 64240179bf8748b2729d6c733022428dfa1061325c9Rafael EspindolaTailDuplicatePass::canCompletelyDuplicateBB(MachineBasicBlock &BB) { 643275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallPtrSet<MachineBasicBlock*, 8> Succs(BB.succ_begin(), BB.succ_end()); 644275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 645275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (MachineBasicBlock::pred_iterator PI = BB.pred_begin(), 646275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PE = BB.pred_end(); PI != PE; ++PI) { 647275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredBB = *PI; 6489dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 64940179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola if (PredBB->succ_size() > 1) 65040179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola return false; 6519dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 652275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL; 653275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineOperand, 4> PredCond; 654275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 655275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 6569dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 65740179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola if (!PredCond.empty()) 6589dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return false; 659275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 660275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 661275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 662275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 663d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindolabool 664275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolaTailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB, 665275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineBasicBlock*, 8> &TDBBs, 666275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola const DenseSet<unsigned> &UsedByPhi, 667275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineInstr*, 16> &Copies) { 668d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola SmallPtrSet<MachineBasicBlock*, 8> Succs(TailBB->succ_begin(), 669d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola TailBB->succ_end()); 670275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 671275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TailBB->pred_end()); 672d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola bool Changed = false; 673275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 674275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PE = Preds.end(); PI != PE; ++PI) { 675275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredBB = *PI; 676275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 677d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (PredBB->getLandingPadSuccessor()) 678d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 679d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola 680d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (bothUsedInPHI(*PredBB, Succs)) 681d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 682d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola 683275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL; 684275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineOperand, 4> PredCond; 685d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 686d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 687275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 688d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola Changed = true; 689275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 690275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola << "From simple Succ: " << *TailBB); 691275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 692275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *NewTarget = *TailBB->succ_begin(); 693289a27946fc11ae6b5a9aa517639d94efa4d91d9Francois Pichet MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(PredBB)); 694275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 695275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make PredFBB explicit. 696275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredCond.empty()) 697275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = PredTBB; 698275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 699275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make fall through explicit. 700275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (!PredTBB) 701275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredTBB = NextBB; 702275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (!PredFBB) 703275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NextBB; 704275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 705275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Redirect 706275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredFBB == TailBB) 707275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NewTarget; 708275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredTBB == TailBB) 709275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredTBB = NewTarget; 710275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 711275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make the branch unconditional if possible 712689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola if (PredTBB == PredFBB) { 713689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola PredCond.clear(); 714275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NULL; 715689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola } 716275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 717275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Avoid adding fall through branches. 718275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredFBB == NextBB) 719275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NULL; 720275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredTBB == NextBB && PredFBB == NULL) 721275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredTBB = NULL; 722275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 723275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TII->RemoveBranch(*PredBB); 724275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 725275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredTBB) 726275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc()); 727275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 728275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredBB->removeSuccessor(TailBB); 729689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola unsigned NumSuccessors = PredBB->succ_size(); 730689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola assert(NumSuccessors <= 1); 731689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget) 732689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola PredBB->addSuccessor(NewTarget); 733275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 734275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TDBBs.push_back(PredBB); 735275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 736d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return Changed; 737275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 738275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 73954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 74054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// of its predecessors. 74154c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindolabool 7426a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael EspindolaTailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, 7436a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 7446a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF, 74554c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola SmallVector<MachineBasicBlock*, 8> &TDBBs, 74654c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola SmallVector<MachineInstr*, 16> &Copies) { 74700dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 74875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 749275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola DenseSet<unsigned> UsedByPhi; 750275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola getRegsUsedByPHIs(*TailBB, &UsedByPhi); 751275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 752d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (IsSimple) 753d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies); 754275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 75515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Iterate through all the unique predecessors and tail-duplicate this 75615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into them, if possible. Copying the list ahead of time also 75715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // avoids trouble with the predecessor list reallocating. 75815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool Changed = false; 75979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 76079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_end()); 76115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 76215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PE = Preds.end(); PI != PE; ++PI) { 76315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredBB = *PI; 76415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 76515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(TailBB != PredBB && 76615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "Single-block loop should have been rejected earlier!"); 7679a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola // EH edges are ignored by AnalyzeBranch. 7689a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola if (PredBB->succ_size() > 1) 7699a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola continue; 77015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 77115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredTBB, *PredFBB; 77215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PredCond; 77315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 77415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 77515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PredCond.empty()) 77615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 77715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate into a fall-through predecessor (at least for now). 77815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 77915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 78015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 78100dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 78215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From Succ: " << *TailBB); 78315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 78475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PredBB); 78575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 78615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove PredBB's unconditional branch. 78715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII->RemoveBranch(*PredBB); 788111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 789eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (RS && !TailBB->livein_empty()) { 790eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // Update PredBB livein. 791eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng RS->enterBasicBlock(PredBB); 792eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (!PredBB->empty()) 793eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng RS->forward(prior(PredBB->end())); 794eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng BitVector RegsLiveAtExit(TRI->getNumRegs()); 795eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng RS->getRegsUsed(RegsLiveAtExit, false); 796eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng for (MachineBasicBlock::livein_iterator I = TailBB->livein_begin(), 797eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng E = TailBB->livein_end(); I != E; ++I) { 798eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (!RegsLiveAtExit[*I]) 799eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // If a register is previously livein to the tail but it's not live 800eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // at the end of predecessor BB, then it should be added to its 801eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // livein list. 802eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng PredBB->addLiveIn(*I); 803eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng } 804eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng } 805eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng 80615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Clone the contents of TailBB into PredBB. 807111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 8083466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 809df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng // Use instr_iterator here to properly handle bundles, e.g. 810df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng // ARM Thumb2 IT block. 811df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng MachineBasicBlock::instr_iterator I = TailBB->instr_begin(); 812df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng while (I != TailBB->instr_end()) { 81379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I; 81479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng ++I; 815518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isPHI()) { 816111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // Replace the uses of the def of the PHI with the register coming 817111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // from PredBB. 818689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); 81979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 82079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 82179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 8220f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi); 823111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 82415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 82575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 8263466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 8271e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 8281e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 8291e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first).addReg(CopyInfos[i].second)); 83075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 831ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 832ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Simplify 833ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true); 834ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 83515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 83615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 83715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Update the CFG. 83815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PredBB->removeSuccessor(PredBB->succ_begin()); 83915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(PredBB->succ_empty() && 84015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "TailDuplicate called on block with multiple successors!"); 84115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 84279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng E = TailBB->succ_end(); I != E; ++I) 84379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->addSuccessor(*I); 84415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 84515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 84615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson ++NumTailDups; 84715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 84815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 84915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If TailBB was duplicated into all its predecessors except for the prior 85015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block, which falls through unconditionally, move the contents of this 85115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into the prior block. 85279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 85315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 85415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PriorCond; 85515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // This has to check PrevBB->succ_size() because EH edges are ignored by 85615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // AnalyzeBranch. 857d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick if (PrevBB->succ_size() == 1 && 858a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola !TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true) && 859a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola PriorCond.empty() && !PriorTBB && TailBB->pred_size() == 1 && 86015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !TailBB->hasAddressTaken()) { 86100dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 86215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From MBB: " << *TailBB); 86379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc) { 86479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 8653466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 86679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 86779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Process PHI instructions first. 868518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (I != TailBB->end() && I->isPHI()) { 86979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace the uses of the def of the PHI with the register coming 87079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // from PredBB. 87179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 872689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); 87379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getParent()) 87479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 87579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 87679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 87779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Now copy the non-PHI instructions. 87879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 87979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 88079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 88179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 882df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng assert(!MI->isBundle() && "Not expecting bundles before regalloc!"); 8830f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi); 88479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 88579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 88675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 8873466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 8881e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 8891e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 8901e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first) 8911e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen .addReg(CopyInfos[i].second)); 89275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 89379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 89479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // No PHIs to worry about, just splice the instructions over. 89579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 89679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 89779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->removeSuccessor(PrevBB->succ_begin()); 89879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(PrevBB->succ_empty()); 89979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->transferSuccessors(TailBB); 90075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PrevBB); 90115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 90215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 90315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 904689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If this is after register allocation, there are no phis to fix. 905689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!PreRegAlloc) 906689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 907689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 908689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If we made no changes so far, we are safe. 909689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Changed) 910689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 911689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 912689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 913689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Handle the nasty case in that we duplicated a block that is part of a loop 914689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // into some but not all of its predecessors. For example: 9154d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 1 -> 2 <-> 3 | 9164d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ | 9174d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \---> rest | 918689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // if we duplicate 2 into 1 but not into 3, we end up with 9194d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 12 -> 3 <-> 2 -> rest | 9204d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ / | 9214d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \----->-----/ | 922689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced 923689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // with a phi in 3 (which now dominates 2). 924689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // What we do here is introduce a copy in 3 of the register defined by the 925689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // phi, just like when we are duplicating 2 into 3, but we don't copy any 926689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // real instructions or remove the 3 -> 2 edge from the phi in 2. 927689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 928689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola PE = Preds.end(); PI != PE; ++PI) { 929689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock *PredBB = *PI; 930689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (std::find(TDBBs.begin(), TDBBs.end(), PredBB) != TDBBs.end()) 931689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 932689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 933689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // EH edges 934689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (PredBB->succ_size() != 1) 935689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 936689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 937689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola DenseMap<unsigned, unsigned> LocalVRMap; 938689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 939689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator I = TailBB->begin(); 940689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Process PHI instructions first. 941689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola while (I != TailBB->end() && I->isPHI()) { 942689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Replace the uses of the def of the PHI with the register coming 943689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // from PredBB. 944689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineInstr *MI = &*I++; 945689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); 946689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 947689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 948689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 949689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 950689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola TII->get(TargetOpcode::COPY), 951689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola CopyInfos[i].first).addReg(CopyInfos[i].second)); 952689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 953689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 954689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 95515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return Changed; 95615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 95715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 95815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// RemoveDeadBlock - Remove the specified dead machine basic block from the 95915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// function, updating the CFG. 9602d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonvoid TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 96115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(MBB->pred_empty() && "MBB must be dead!"); 96200dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 96315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 96415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove all successors. 96515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson while (!MBB->succ_empty()) 96615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->removeSuccessor(MBB->succ_end()-1); 96715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 96815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove the block. 96915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->eraseFromParent(); 97015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 971