TailDuplication.cpp revision eb25bd2356cca5ef83472b1ae0f764037b82ad82
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" 23eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng#include "llvm/CodeGen/RegisterScavenging.h" 2415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Target/TargetInstrInfo.h" 25eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng#include "llvm/Target/TargetRegisterInfo.h" 2615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/CommandLine.h" 2715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/Debug.h" 2875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng#include "llvm/Support/ErrorHandling.h" 2915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/raw_ostream.h" 30c66d36028b21077aa1715331c22347b47b4da94fJakob Stoklund Olesen#include "llvm/ADT/DenseSet.h" 3115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/SmallSet.h" 3215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/SetVector.h" 3315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/Statistic.h" 3415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonusing namespace llvm; 3515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 3675eb53584367098a5625028e22f1ff8e169d0efdEvan ChengSTATISTIC(NumTails , "Number of tails duplicated"); 3715acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumTailDups , "Number of tail duplicated blocks"); 3815acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 3915acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 400cdca089b289845664d660f0b285499800822919Rafael EspindolaSTATISTIC(NumAddedPHIs , "Number of phis added"); 4115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// Heuristic for tail duplication. 4315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonstatic cl::opt<unsigned> 4415acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonTailDuplicateSize("tail-dup-size", 4515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::desc("Maximum instructions to consider tail duplicating"), 4615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::init(2), cl::Hidden); 4715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4875eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<bool> 4975eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupVerify("tail-dup-verify", 5075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::desc("Verify sanity of PHI instructions during taildup"), 5175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::init(false), cl::Hidden); 5275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5375eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<unsigned> 5475eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 5575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5611572babb12d169965c63c47aab9c9fad354e5dfEvan Chengtypedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 57111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 5815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonnamespace { 592d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson /// TailDuplicatePass - Perform tail duplication. 602d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson class TailDuplicatePass : public MachineFunctionPass { 6115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson const TargetInstrInfo *TII; 62eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng const TargetRegisterInfo *TRI; 6315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineModuleInfo *MMI; 64111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineRegisterInfo *MRI; 65eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng RegScavenger *RS; 66d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick bool PreRegAlloc; 67111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 68111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 69111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SmallVector<unsigned, 16> SSAUpdateVRs; 70111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 71111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 72111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // source virtual registers. 73111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 7415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson public: 7615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson static char ID; 77d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick explicit TailDuplicatePass() : 78d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick MachineFunctionPass(ID), PreRegAlloc(false) {} 7915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 8015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual bool runOnMachineFunction(MachineFunction &MF); 8115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 8215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson private: 8311572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 8411572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB); 8579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 8679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 8775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 880f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 89689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola const DenseSet<unsigned> &UsedByPhi, 90689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola bool Remove); 9179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void DuplicateInstruction(MachineInstr *MI, 9279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 9379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 9479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 950f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 960f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi); 9775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 9875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 9975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> &Succs); 10015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool TailDuplicateBlocks(MachineFunction &MF); 10154c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola bool shouldTailDuplicate(const MachineFunction &MF, 1029dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola bool IsSimple, MachineBasicBlock &TailBB); 103275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola bool isSimpleBB(MachineBasicBlock *TailBB); 10440179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola bool canCompletelyDuplicateBB(MachineBasicBlock &BB); 105d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola bool duplicateSimpleBB(MachineBasicBlock *TailBB, 106275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineBasicBlock*, 8> &TDBBs, 107275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola const DenseSet<unsigned> &RegsUsedByPhi, 108275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineInstr*, 16> &Copies); 1096a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool TailDuplicate(MachineBasicBlock *TailBB, 1106a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 1116a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF, 1123466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 1133466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> &Copies); 1146a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool TailDuplicateAndUpdate(MachineBasicBlock *MBB, 1156a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 1166a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF); 1176a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 11815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson void RemoveDeadBlock(MachineBasicBlock *MBB); 11915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson }; 12015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1212d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson char TailDuplicatePass::ID = 0; 12215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 12315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1241dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::TailDuplicateID = TailDuplicatePass::ID; 1251dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trick 1261dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew TrickINITIALIZE_PASS(TailDuplicatePass, "tailduplication", "Tail Duplication", 1271dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trick false, false) 12815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1292d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 13015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII = MF.getTarget().getInstrInfo(); 131eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng TRI = MF.getTarget().getRegisterInfo(); 132111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MRI = &MF.getRegInfo(); 13315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 134d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick PreRegAlloc = MRI->isSSA(); 135eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng RS = NULL; 136eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (MRI->tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF)) 137eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng RS = new RegScavenger(); 13815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 13915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 140057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen while (TailDuplicateBlocks(MF)) 141057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen MadeChange = true; 14215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 14315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 14415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 14515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 14675eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 14775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 14875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *MBB = I; 14975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 15075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->pred_end()); 15175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator MI = MBB->begin(); 15275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (MI != MBB->end()) { 153518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!MI->isPHI()) 15475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 15575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 15675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng PE = Preds.end(); PI != PE; ++PI) { 15775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PredBB = *PI; 15875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool Found = false; 15975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 16075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 16175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB == PredBB) { 16275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Found = true; 16375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 16475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!Found) { 16700dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 16800dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " missing input from predecessor BB#" 16975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PredBB->getNumber() << '\n'; 17075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 17175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 17275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 17375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 17475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 17575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 17675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (CheckExtra && !Preds.count(PHIBB)) { 17700dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 17875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << ": " << *MI; 17900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " extra input from predecessor BB#" 18075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PHIBB->getNumber() << '\n'; 181d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola llvm_unreachable(0); 18275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB->getNumber() < 0) { 18400dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 18500dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 18675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 18775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++MI; 19075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 19175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 19275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng} 19375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 1946a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola/// TailDuplicateAndUpdate - Tail duplicate the block and cleanup. 1956a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindolabool 1966a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael EspindolaTailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB, 1976a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 1986a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF) { 1996a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Save the successors list. 2006a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 2016a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MBB->succ_end()); 2026a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2036a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineBasicBlock*, 8> TDBBs; 2046a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineInstr*, 16> Copies; 2056a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!TailDuplicate(MBB, IsSimple, MF, TDBBs, Copies)) 2066a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola return false; 2076a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2086a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++NumTails; 2096a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2106a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineInstr*, 8> NewPHIs; 2116a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 2126a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2136a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // TailBB's immediate successors are now successors of those predecessors 2146a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // which duplicated TailBB. Add the predecessors as sources to the PHI 2156a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // instructions. 2166a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); 2176a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (PreRegAlloc) 2186a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 2196a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2206a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // If it is dead, remove it. 2216a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (isDead) { 2226a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola NumInstrDups -= MBB->size(); 2236a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola RemoveDeadBlock(MBB); 2246a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++NumDeadBlocks; 2256a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2266a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2276a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Update SSA form. 2286a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!SSAUpdateVRs.empty()) { 2296a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 2306a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned VReg = SSAUpdateVRs[i]; 2316a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.Initialize(VReg); 2326a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2336a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // If the original definition is still around, add it as an available 2346a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // value. 2356a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineInstr *DefMI = MRI->getVRegDef(VReg); 2366a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineBasicBlock *DefBB = 0; 2376a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (DefMI) { 2386a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola DefBB = DefMI->getParent(); 2396a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.AddAvailableValue(DefBB, VReg); 2406a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2416a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2426a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Add the new vregs as available values. 2436a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola DenseMap<unsigned, AvailableValsTy>::iterator LI = 2446a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVals.find(VReg); 2456a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 2466a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineBasicBlock *SrcBB = LI->second[j].first; 2476a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned SrcReg = LI->second[j].second; 2486a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 2496a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2506a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2516a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Rewrite uses that are outside of the original def's block. 2526a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 2536a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola while (UI != MRI->use_end()) { 2546a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineOperand &UseMO = UI.getOperand(); 2556a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineInstr *UseMI = &*UI; 2566a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++UI; 2576a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (UseMI->isDebugValue()) { 2586a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // SSAUpdate can replace the use with an undef. That creates 2596a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // a debug instruction that is a kill. 2606a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // FIXME: Should it SSAUpdate job to delete debug instructions 2616a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // instead of replacing the use with undef? 2626a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola UseMI->eraseFromParent(); 2636a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2646a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2656a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (UseMI->getParent() == DefBB && !UseMI->isPHI()) 2666a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2676a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.RewriteUse(UseMO); 2686a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2696a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2706a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2716a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVRs.clear(); 2726a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVals.clear(); 2736a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2746a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2756a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Eliminate some of the copies inserted by tail duplication to maintain 2766a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // SSA form. 2776a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 2786a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineInstr *Copy = Copies[i]; 2796a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!Copy->isCopy()) 2806a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2816a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned Dst = Copy->getOperand(0).getReg(); 2826a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned Src = Copy->getOperand(1).getReg(); 2830fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen if (MRI->hasOneNonDBGUse(Src) && 2840fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) { 2856a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Copy is the only use. Do trivial copy propagation here. 2866a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MRI->replaceRegWith(Dst, Src); 2876a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola Copy->eraseFromParent(); 2886a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2896a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2906a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2916a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (NewPHIs.size()) 2926a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola NumAddedPHIs += NewPHIs.size(); 2936a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2946a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola return true; 2956a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola} 2966a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 29715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// TailDuplicateBlocks - Look for small blocks that are unconditionally 29815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// branched to and do not fall through. Tail-duplicate their instructions 29915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// into their predecessors to eliminate (dynamic) branches. 3002d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 30115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 30215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 30375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) { 30400dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 30575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, true); 30675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 30775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 30815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 30915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *MBB = I++; 31015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 31175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (NumTails == TailDupLimit) 31275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 31375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3146a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple = isSimpleBB(MBB); 31575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3166a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!shouldTailDuplicate(MF, IsSimple, *MBB)) 317c0af352038e43bd51ef3ea11e7d43647e4df42bfRafael Espindola continue; 31875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3196a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MadeChange |= TailDuplicateAndUpdate(MBB, IsSimple, MF); 32015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 321c0af352038e43bd51ef3ea11e7d43647e4df42bfRafael Espindola 3226a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (PreRegAlloc && TailDupVerify) 3236a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola VerifyPHIs(MF, false); 324111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 32515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 32615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 32715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 328111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 329111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng const MachineRegisterInfo *MRI) { 330111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 331111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng UE = MRI->use_end(); UI != UE; ++UI) { 332111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineInstr *UseMI = &*UI; 333db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola if (UseMI->isDebugValue()) 334db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola continue; 335111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (UseMI->getParent() != BB) 336111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return true; 337111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 338111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return false; 339111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 340111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 341111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 342111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 343111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (MI->getOperand(i+1).getMBB() == SrcBB) 344111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return i; 345111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return 0; 346111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 347111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 3480f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 3490f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// Remember which registers are used by phis in this block. This is 3500f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// used to determine which registers are liveout while modifying the 3510f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// block (which is why we need to copy the information). 3520f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindolastatic void getRegsUsedByPHIs(const MachineBasicBlock &BB, 35333b465877255cc75241216817247c61374958a36Rafael Espindola DenseSet<unsigned> *UsedByPhi) { 3540f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola for(MachineBasicBlock::const_iterator I = BB.begin(), E = BB.end(); 3550f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola I != E; ++I) { 3560f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const MachineInstr &MI = *I; 3570f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (!MI.isPHI()) 3580f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola break; 3590f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 3600f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola unsigned SrcReg = MI.getOperand(i).getReg(); 3610f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola UsedByPhi->insert(SrcReg); 3620f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3630f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3640f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola} 3650f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 366111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 367111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// SSA update. 36811572babb12d169965c63c47aab9c9fad354e5dfEvan Chengvoid TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 36911572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB) { 37011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 371111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (LI != SSAUpdateVals.end()) 37211572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng LI->second.push_back(std::make_pair(BB, NewReg)); 373111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng else { 374111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng AvailableValsTy Vals; 37511572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng Vals.push_back(std::make_pair(BB, NewReg)); 376111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 377111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVRs.push_back(OrigReg); 378111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 379111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 380111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 38175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 38275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// Remember the source register that's contributed by PredBB and update SSA 38375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// update map. 38479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::ProcessPHI(MachineInstr *MI, 38579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 38679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 38775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 3880f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 38933b465877255cc75241216817247c61374958a36Rafael Espindola const DenseSet<unsigned> &RegsUsedByPhi, 390689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola bool Remove) { 39179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned DefReg = MI->getOperand(0).getReg(); 39279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 39379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(SrcOpIdx && "Unable to find matching PHI source?"); 39479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 39575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 39679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 39775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 39875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Insert a copy from source to the end of the block. The def register is the 39975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // available value liveout of the block. 40075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned NewDef = MRI->createVirtualRegister(RC); 40175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Copies.push_back(std::make_pair(NewDef, SrcReg)); 4020f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) 40375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng AddSSAUpdateEntry(DefReg, NewDef, PredBB); 40479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 405689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Remove) 406689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return; 407689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 40879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Remove PredBB from the PHI node. 40979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx+1); 41079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx); 41179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getNumOperands() == 1) 41279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 41379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 41479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 41579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 41679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// the source operands due to earlier PHI translation. 41779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 41879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 41979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 42079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 4210f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 4220f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi) { 42330ac0467ced4627a9b84d8a1d3ca5e8706ddad63Jakob Stoklund Olesen MachineInstr *NewMI = TII->duplicate(MI, MF); 42479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 42579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineOperand &MO = NewMI->getOperand(i); 42679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (!MO.isReg()) 42779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 42879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned Reg = MO.getReg(); 429c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 43079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 43179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MO.isDef()) { 43279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(Reg); 43379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned NewReg = MRI->createVirtualRegister(RC); 43479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(NewReg); 43579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(Reg, NewReg)); 4360f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) 43711572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng AddSSAUpdateEntry(Reg, NewReg, PredBB); 43879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 43979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 4400fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen if (VI != LocalVRMap.end()) { 44179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(VI->second); 4420fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen MRI->constrainRegClass(VI->second, MRI->getRegClass(Reg)); 4430fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen } 44479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 44579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 446df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng PredBB->insert(PredBB->instr_end(), NewMI); 44779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 44879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 44979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 45079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// blocks, the successors have gained new predecessors. Update the PHI 45179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// instructions in them accordingly. 45275eb53584367098a5625028e22f1ff8e169d0efdEvan Chengvoid 45375eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 45475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 45579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*,8> &Succs) { 45679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 45779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SE = Succs.end(); SI != SE; ++SI) { 45879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *SuccBB = *SI; 45979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 46079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng II != EE; ++II) { 461518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!II->isPHI()) 46279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 46375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Idx = 0; 46479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 46575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 46675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 46775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Idx = i; 46879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 46975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 47075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 47175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 47275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng assert(Idx != 0); 47375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO0 = II->getOperand(Idx); 47475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Reg = MO0.getReg(); 47575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 47675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Folded into the previous BB. 47775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // There could be duplicate phi source entries. FIXME: Should sdisel 47875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // or earlier pass fixed this? 47975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 48075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 48175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 48275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i+1); 48375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i); 48475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 48575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 48609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else 48709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 48809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 48909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // If Idx is set, the operands at Idx and Idx+1 must be removed. 49009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // We reuse the location to avoid expensive RemoveOperand calls. 49109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 49275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 49375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (LI != SSAUpdateVals.end()) { 49475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // This register is defined in the tail block. 49579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 49611572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 497d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // If we didn't duplicate a bb into a particular predecessor, we 498d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // might still have added an entry to SSAUpdateVals to correcly 499d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // recompute SSA. If that case, avoid adding a dummy extra argument 500d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // this PHI. 501d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola if (!SrcBB->isSuccessor(SuccBB)) 502d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola continue; 503d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola 50411572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng unsigned SrcReg = LI->second[j].second; 50509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 50609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(SrcReg); 50709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 50809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 50909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 51009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 51109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(SrcBB)); 51209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 51379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 51475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } else { 51575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Live in tail block, must also be live in predecessors. 51675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 51775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = TDBBs[j]; 51809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 51909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(Reg); 52009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 52109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 52209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 52309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(Reg, false)); 52409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(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 && 5548352062e52eed6e50786fdb89f5e601fdcbe0d90Jakob Stoklund Olesen MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 555cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = 1; 556cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson else 557cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = TailDuplicateSize; 558cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson 559ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // If the target has hardware branch prediction that can handle indirect 560ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // branches, duplicating them can often make them predictable when there 561ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // are common paths through the code. The limit needs to be high enough 562ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // to allow undoing the effects of tail merging and other optimizations 563ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // that rearrange the predecessors of the indirect branch. 564ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 5656a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool HasIndirectbr = false; 5666a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!TailBB.empty()) 5675a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng HasIndirectbr = TailBB.back().isIndirectBranch(); 5686a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 5696a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (HasIndirectbr && PreRegAlloc) 5706a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MaxDuplicateCount = 20; 57115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 57215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Check the instructions in the block to determine whether tail-duplication 57315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // is invalid or unlikely to be profitable. 574f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson unsigned InstrCount = 0; 5757c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng for (MachineBasicBlock::iterator I = TailBB.begin(); I != TailBB.end(); ++I) { 57615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Non-duplicable things shouldn't be tail-duplicated. 5775a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (I->isNotDuplicable()) 578ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 579ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 58079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Do not duplicate 'return' instructions if this is a pre-regalloc run. 58179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // A return may expand into a lot more instructions (e.g. reload of callee 58279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // saved registers) after PEI. 5835a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (PreRegAlloc && I->isReturn()) 584ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 585ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 586ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Avoid duplicating calls before register allocation. Calls presents a 587ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // barrier to register allocation so duplicating them may end up increasing 588ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // spills. 5895a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (PreRegAlloc && I->isCall()) 590ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 591ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 592cbe1e31732c5d4fb1277195e76b9b42c115396aaDevang Patel if (!I->isPHI() && !I->isDebugValue()) 593f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson InstrCount += 1; 594ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 595ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (InstrCount > MaxDuplicateCount) 596ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 59715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 59815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 5996a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (HasIndirectbr && PreRegAlloc) 6009dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return true; 6019dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 6029dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (IsSimple) 603d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return true; 6049dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 6059dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (!PreRegAlloc) 6069dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return true; 6079dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 60840179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola return canCompletelyDuplicateBB(TailBB); 60954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola} 61054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 611275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola/// isSimpleBB - True if this BB has only one unconditional jump. 612275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolabool 613275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolaTailDuplicatePass::isSimpleBB(MachineBasicBlock *TailBB) { 614275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (TailBB->succ_size() != 1) 615275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 6169dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (TailBB->pred_empty()) 6179dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return false; 618d6379a993c7e40521bd5c8c6469e32697b4c41d1Rafael Espindola MachineBasicBlock::iterator I = TailBB->begin(); 619275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock::iterator E = TailBB->end(); 620d6379a993c7e40521bd5c8c6469e32697b4c41d1Rafael Espindola while (I != E && I->isDebugValue()) 621275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola ++I; 622275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (I == E) 623275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 6245a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng return I->isUnconditionalBranch(); 625275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 626275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 627275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolastatic bool 628275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolabothUsedInPHI(const MachineBasicBlock &A, 629275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallPtrSet<MachineBasicBlock*, 8> SuccsB) { 630275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (MachineBasicBlock::const_succ_iterator SI = A.succ_begin(), 631275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SE = A.succ_end(); SI != SE; ++SI) { 632275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *BB = *SI; 633275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI()) 634275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 635275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 636275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 637275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 638275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 639275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 640275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolabool 64140179bf8748b2729d6c733022428dfa1061325c9Rafael EspindolaTailDuplicatePass::canCompletelyDuplicateBB(MachineBasicBlock &BB) { 642275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallPtrSet<MachineBasicBlock*, 8> Succs(BB.succ_begin(), BB.succ_end()); 643275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 644275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (MachineBasicBlock::pred_iterator PI = BB.pred_begin(), 645275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PE = BB.pred_end(); PI != PE; ++PI) { 646275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredBB = *PI; 6479dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 64840179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola if (PredBB->succ_size() > 1) 64940179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola return false; 6509dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 651275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL; 652275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineOperand, 4> PredCond; 653275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 654275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 6559dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 65640179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola if (!PredCond.empty()) 6579dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return false; 658275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 659275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 660275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 661275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 662d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindolabool 663275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolaTailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB, 664275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineBasicBlock*, 8> &TDBBs, 665275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola const DenseSet<unsigned> &UsedByPhi, 666275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineInstr*, 16> &Copies) { 667d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola SmallPtrSet<MachineBasicBlock*, 8> Succs(TailBB->succ_begin(), 668d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola TailBB->succ_end()); 669275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 670275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TailBB->pred_end()); 671d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola bool Changed = false; 672275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 673275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PE = Preds.end(); PI != PE; ++PI) { 674275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredBB = *PI; 675275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 676d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (PredBB->getLandingPadSuccessor()) 677d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 678d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola 679d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (bothUsedInPHI(*PredBB, Succs)) 680d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 681d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola 682275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredTBB = NULL, *PredFBB = NULL; 683275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineOperand, 4> PredCond; 684d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 685d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 686275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 687d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola Changed = true; 688275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 689275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola << "From simple Succ: " << *TailBB); 690275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 691275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *NewTarget = *TailBB->succ_begin(); 692289a27946fc11ae6b5a9aa517639d94efa4d91d9Francois Pichet MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(PredBB)); 693275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 694275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make PredFBB explicit. 695275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredCond.empty()) 696275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = PredTBB; 697275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 698275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make fall through explicit. 699275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (!PredTBB) 700275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredTBB = NextBB; 701275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (!PredFBB) 702275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NextBB; 703275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 704275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Redirect 705275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredFBB == TailBB) 706275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NewTarget; 707275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredTBB == TailBB) 708275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredTBB = NewTarget; 709275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 710275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make the branch unconditional if possible 711689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola if (PredTBB == PredFBB) { 712689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola PredCond.clear(); 713275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NULL; 714689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola } 715275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 716275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Avoid adding fall through branches. 717275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredFBB == NextBB) 718275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NULL; 719275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredTBB == NextBB && PredFBB == NULL) 720275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredTBB = NULL; 721275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 722275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TII->RemoveBranch(*PredBB); 723275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 724275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredTBB) 725275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc()); 726275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 727275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredBB->removeSuccessor(TailBB); 728689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola unsigned NumSuccessors = PredBB->succ_size(); 729689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola assert(NumSuccessors <= 1); 730689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget) 731689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola PredBB->addSuccessor(NewTarget); 732275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 733275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TDBBs.push_back(PredBB); 734275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 735d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return Changed; 736275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 737275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 73854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 73954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// of its predecessors. 74054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindolabool 7416a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael EspindolaTailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, 7426a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 7436a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF, 74454c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola SmallVector<MachineBasicBlock*, 8> &TDBBs, 74554c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola SmallVector<MachineInstr*, 16> &Copies) { 74600dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 74775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 748275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola DenseSet<unsigned> UsedByPhi; 749275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola getRegsUsedByPHIs(*TailBB, &UsedByPhi); 750275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 751d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (IsSimple) 752d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies); 753275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 75415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Iterate through all the unique predecessors and tail-duplicate this 75515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into them, if possible. Copying the list ahead of time also 75615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // avoids trouble with the predecessor list reallocating. 75715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool Changed = false; 75879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 75979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_end()); 76015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 76115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PE = Preds.end(); PI != PE; ++PI) { 76215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredBB = *PI; 76315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 76415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(TailBB != PredBB && 76515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "Single-block loop should have been rejected earlier!"); 7669a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola // EH edges are ignored by AnalyzeBranch. 7679a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola if (PredBB->succ_size() > 1) 7689a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola continue; 76915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 77015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredTBB, *PredFBB; 77115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PredCond; 77215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 77315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 77415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PredCond.empty()) 77515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 77615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate into a fall-through predecessor (at least for now). 77715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 77815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 77915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 78000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 78115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From Succ: " << *TailBB); 78215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 78375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PredBB); 78475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 78515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove PredBB's unconditional branch. 78615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII->RemoveBranch(*PredBB); 787111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 788eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (RS && !TailBB->livein_empty()) { 789eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // Update PredBB livein. 790eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng RS->enterBasicBlock(PredBB); 791eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (!PredBB->empty()) 792eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng RS->forward(prior(PredBB->end())); 793eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng BitVector RegsLiveAtExit(TRI->getNumRegs()); 794eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng RS->getRegsUsed(RegsLiveAtExit, false); 795eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng for (MachineBasicBlock::livein_iterator I = TailBB->livein_begin(), 796eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng E = TailBB->livein_end(); I != E; ++I) { 797eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (!RegsLiveAtExit[*I]) 798eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // If a register is previously livein to the tail but it's not live 799eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // at the end of predecessor BB, then it should be added to its 800eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // livein list. 801eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng PredBB->addLiveIn(*I); 802eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng } 803eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng } 804eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng 80515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Clone the contents of TailBB into PredBB. 806111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 8073466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 808df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng // Use instr_iterator here to properly handle bundles, e.g. 809df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng // ARM Thumb2 IT block. 810df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng MachineBasicBlock::instr_iterator I = TailBB->instr_begin(); 811df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng while (I != TailBB->instr_end()) { 81279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I; 81379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng ++I; 814518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isPHI()) { 815111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // Replace the uses of the def of the PHI with the register coming 816111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // from PredBB. 817689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); 81879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 81979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 82079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 8210f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi); 822111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 82315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 82475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 8253466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 8261e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 8271e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 8281e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first).addReg(CopyInfos[i].second)); 82975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 830ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 831ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Simplify 832ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true); 833ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 83415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 83515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 83615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Update the CFG. 83715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PredBB->removeSuccessor(PredBB->succ_begin()); 83815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(PredBB->succ_empty() && 83915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "TailDuplicate called on block with multiple successors!"); 84015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 84179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng E = TailBB->succ_end(); I != E; ++I) 84279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->addSuccessor(*I); 84315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 84415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 84515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson ++NumTailDups; 84615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 84715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 84815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If TailBB was duplicated into all its predecessors except for the prior 84915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block, which falls through unconditionally, move the contents of this 85015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into the prior block. 85179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 85215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 85315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PriorCond; 85415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // This has to check PrevBB->succ_size() because EH edges are ignored by 85515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // AnalyzeBranch. 856d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick if (PrevBB->succ_size() == 1 && 857a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola !TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true) && 858a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola PriorCond.empty() && !PriorTBB && TailBB->pred_size() == 1 && 85915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !TailBB->hasAddressTaken()) { 86000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 86115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From MBB: " << *TailBB); 86279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc) { 86379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 8643466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 86579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 86679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Process PHI instructions first. 867518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (I != TailBB->end() && I->isPHI()) { 86879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace the uses of the def of the PHI with the register coming 86979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // from PredBB. 87079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 871689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); 87279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getParent()) 87379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 87479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 87579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 87679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Now copy the non-PHI instructions. 87779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 87879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 87979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 88079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 881df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng assert(!MI->isBundle() && "Not expecting bundles before regalloc!"); 8820f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi); 88379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 88479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 88575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 8863466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 8871e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 8881e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 8891e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first) 8901e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen .addReg(CopyInfos[i].second)); 89175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 89279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 89379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // No PHIs to worry about, just splice the instructions over. 89479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 89579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 89679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->removeSuccessor(PrevBB->succ_begin()); 89779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(PrevBB->succ_empty()); 89879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->transferSuccessors(TailBB); 89975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PrevBB); 90015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 90115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 90215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 903689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If this is after register allocation, there are no phis to fix. 904689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!PreRegAlloc) 905689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 906689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 907689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If we made no changes so far, we are safe. 908689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Changed) 909689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 910689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 911689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 912689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Handle the nasty case in that we duplicated a block that is part of a loop 913689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // into some but not all of its predecessors. For example: 9144d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 1 -> 2 <-> 3 | 9154d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ | 9164d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \---> rest | 917689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // if we duplicate 2 into 1 but not into 3, we end up with 9184d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 12 -> 3 <-> 2 -> rest | 9194d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ / | 9204d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \----->-----/ | 921689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced 922689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // with a phi in 3 (which now dominates 2). 923689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // What we do here is introduce a copy in 3 of the register defined by the 924689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // phi, just like when we are duplicating 2 into 3, but we don't copy any 925689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // real instructions or remove the 3 -> 2 edge from the phi in 2. 926689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 927689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola PE = Preds.end(); PI != PE; ++PI) { 928689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock *PredBB = *PI; 929689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (std::find(TDBBs.begin(), TDBBs.end(), PredBB) != TDBBs.end()) 930689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 931689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 932689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // EH edges 933689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (PredBB->succ_size() != 1) 934689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 935689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 936689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola DenseMap<unsigned, unsigned> LocalVRMap; 937689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 938689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator I = TailBB->begin(); 939689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Process PHI instructions first. 940689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola while (I != TailBB->end() && I->isPHI()) { 941689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Replace the uses of the def of the PHI with the register coming 942689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // from PredBB. 943689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineInstr *MI = &*I++; 944689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); 945689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 946689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 947689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 948689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 949689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola TII->get(TargetOpcode::COPY), 950689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola CopyInfos[i].first).addReg(CopyInfos[i].second)); 951689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 952689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 953689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 95415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return Changed; 95515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 95615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 95715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// RemoveDeadBlock - Remove the specified dead machine basic block from the 95815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// function, updating the CFG. 9592d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonvoid TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 96015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(MBB->pred_empty() && "MBB must be dead!"); 96100dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 96215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 96315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove all successors. 96415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson while (!MBB->succ_empty()) 96515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->removeSuccessor(MBB->succ_end()-1); 96615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 96715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove the block. 96815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->eraseFromParent(); 96915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 970