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#include "llvm/CodeGen/Passes.h" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseSet.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SetVector.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallSet.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 2115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/CodeGen/MachineFunctionPass.h" 221e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineModuleInfo.h" 24111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 25111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineSSAUpdater.h" 26eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng#include "llvm/CodeGen/RegisterScavenging.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 2815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/CommandLine.h" 2915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/Debug.h" 3075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng#include "llvm/Support/ErrorHandling.h" 3115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/raw_ostream.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 3415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonusing namespace llvm; 3515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "tailduplication" 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 3875eb53584367098a5625028e22f1ff8e169d0efdEvan ChengSTATISTIC(NumTails , "Number of tails duplicated"); 3915acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumTailDups , "Number of tail duplicated blocks"); 4015acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 4115acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 420cdca089b289845664d660f0b285499800822919Rafael EspindolaSTATISTIC(NumAddedPHIs , "Number of phis added"); 4315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// Heuristic for tail duplication. 4515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonstatic cl::opt<unsigned> 4615acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonTailDuplicateSize("tail-dup-size", 4715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::desc("Maximum instructions to consider tail duplicating"), 4815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::init(2), cl::Hidden); 4915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 5075eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<bool> 5175eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupVerify("tail-dup-verify", 5275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::desc("Verify sanity of PHI instructions during taildup"), 5375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::init(false), cl::Hidden); 5475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5575eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<unsigned> 5675eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 5775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5811572babb12d169965c63c47aab9c9fad354e5dfEvan Chengtypedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 59111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 6015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonnamespace { 612d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson /// TailDuplicatePass - Perform tail duplication. 622d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson class TailDuplicatePass : public MachineFunctionPass { 6315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson const TargetInstrInfo *TII; 64eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng const TargetRegisterInfo *TRI; 6536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const MachineBranchProbabilityInfo *MBPI; 6615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineModuleInfo *MMI; 67111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineRegisterInfo *MRI; 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<RegScavenger> RS; 69d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick bool PreRegAlloc; 70111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 71111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 72111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SmallVector<unsigned, 16> SSAUpdateVRs; 73111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 74111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 75111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // source virtual registers. 76111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 7715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson public: 7915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson static char ID; 80d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick explicit TailDuplicatePass() : 81d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick MachineFunctionPass(ID), PreRegAlloc(false) {} 8215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnMachineFunction(MachineFunction &MF) override; 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 8615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 8715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson private: 8811572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 8911572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB); 9079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 9179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 9275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 93a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<std::pair<unsigned,unsigned> > &Copies, 94689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola const DenseSet<unsigned> &UsedByPhi, 95689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola bool Remove); 9679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void DuplicateInstruction(MachineInstr *MI, 9779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 9879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 9979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 1000f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 1010f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi); 10275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 103a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineBasicBlock *> &TDBBs, 10475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> &Succs); 10515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool TailDuplicateBlocks(MachineFunction &MF); 10654c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola bool shouldTailDuplicate(const MachineFunction &MF, 1079dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola bool IsSimple, MachineBasicBlock &TailBB); 108275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola bool isSimpleBB(MachineBasicBlock *TailBB); 10940179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola bool canCompletelyDuplicateBB(MachineBasicBlock &BB); 110d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola bool duplicateSimpleBB(MachineBasicBlock *TailBB, 111a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineBasicBlock *> &TDBBs, 112275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola const DenseSet<unsigned> &RegsUsedByPhi, 113a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &Copies); 1146a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool TailDuplicate(MachineBasicBlock *TailBB, 1156a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 1166a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF, 117a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineBasicBlock *> &TDBBs, 118a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &Copies); 1196a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool TailDuplicateAndUpdate(MachineBasicBlock *MBB, 1206a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 1216a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF); 1226a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 12315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson void RemoveDeadBlock(MachineBasicBlock *MBB); 12415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson }; 12515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1262d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson char TailDuplicatePass::ID = 0; 12715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 12815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1291dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::TailDuplicateID = TailDuplicatePass::ID; 1301dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trick 1311dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew TrickINITIALIZE_PASS(TailDuplicatePass, "tailduplication", "Tail Duplication", 1321dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trick false, false) 13315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1342d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 13536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (skipOptnoneFunction(*MF.getFunction())) 13636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 13736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 13815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII = MF.getTarget().getInstrInfo(); 139eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng TRI = MF.getTarget().getRegisterInfo(); 140111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MRI = &MF.getRegInfo(); 14115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 14236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 14336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 144d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick PreRegAlloc = MRI->isSSA(); 145d14e4e133f940d0c1f454a40f3bd835a8c7a7886Benjamin Kramer RS.reset(); 146eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (MRI->tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF)) 147d14e4e133f940d0c1f454a40f3bd835a8c7a7886Benjamin Kramer RS.reset(new RegScavenger()); 14815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 14915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 150057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen while (TailDuplicateBlocks(MF)) 151057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen MadeChange = true; 15215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 15315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 15415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 15515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid TailDuplicatePass::getAnalysisUsage(AnalysisUsage &AU) const { 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<MachineBranchProbabilityInfo>(); 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineFunctionPass::getAnalysisUsage(AU); 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16175eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 16275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 16375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *MBB = I; 16475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 16575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->pred_end()); 16675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator MI = MBB->begin(); 16775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (MI != MBB->end()) { 168518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!MI->isPHI()) 16975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 17075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 17175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng PE = Preds.end(); PI != PE; ++PI) { 17275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PredBB = *PI; 17375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool Found = false; 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 (PHIBB == PredBB) { 17775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Found = true; 17875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 17975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!Found) { 18200dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 18300dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " missing input from predecessor BB#" 18475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PredBB->getNumber() << '\n'; 185dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines llvm_unreachable(nullptr); 18675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 18975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 19075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 19175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (CheckExtra && !Preds.count(PHIBB)) { 19200dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 19375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << ": " << *MI; 19400dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " extra input from predecessor BB#" 19575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PHIBB->getNumber() << '\n'; 196dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines llvm_unreachable(nullptr); 19775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 19875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB->getNumber() < 0) { 19900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 20000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 201dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines llvm_unreachable(nullptr); 20275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 20375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 20475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++MI; 20575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 20675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 20775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng} 20875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 2096a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola/// TailDuplicateAndUpdate - Tail duplicate the block and cleanup. 2106a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindolabool 2116a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael EspindolaTailDuplicatePass::TailDuplicateAndUpdate(MachineBasicBlock *MBB, 2126a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 2136a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF) { 2146a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Save the successors list. 2156a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 2166a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MBB->succ_end()); 2176a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2186a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineBasicBlock*, 8> TDBBs; 2196a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineInstr*, 16> Copies; 2206a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!TailDuplicate(MBB, IsSimple, MF, TDBBs, Copies)) 2216a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola return false; 2226a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2236a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++NumTails; 2246a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2256a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SmallVector<MachineInstr*, 8> NewPHIs; 2266a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 2276a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2286a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // TailBB's immediate successors are now successors of those predecessors 2296a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // which duplicated TailBB. Add the predecessors as sources to the PHI 2306a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // instructions. 2316a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); 2326a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (PreRegAlloc) 2336a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 2346a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2356a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // If it is dead, remove it. 2366a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (isDead) { 2376a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola NumInstrDups -= MBB->size(); 2386a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola RemoveDeadBlock(MBB); 2396a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++NumDeadBlocks; 2406a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2416a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2426a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Update SSA form. 2436a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!SSAUpdateVRs.empty()) { 2446a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 2456a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned VReg = SSAUpdateVRs[i]; 2466a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.Initialize(VReg); 2476a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2486a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // If the original definition is still around, add it as an available 2496a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // value. 2506a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineInstr *DefMI = MRI->getVRegDef(VReg); 251dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *DefBB = nullptr; 2526a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (DefMI) { 2536a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola DefBB = DefMI->getParent(); 2546a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.AddAvailableValue(DefBB, VReg); 2556a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2566a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2576a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Add the new vregs as available values. 2586a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola DenseMap<unsigned, AvailableValsTy>::iterator LI = 2596a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVals.find(VReg); 2606a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 2616a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineBasicBlock *SrcBB = LI->second[j].first; 2626a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned SrcReg = LI->second[j].second; 2636a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 2646a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2656a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2666a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Rewrite uses that are outside of the original def's block. 2676a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 2686a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola while (UI != MRI->use_end()) { 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineOperand &UseMO = *UI; 27036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineInstr *UseMI = UseMO.getParent(); 2716a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola ++UI; 2726a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (UseMI->isDebugValue()) { 2736a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // SSAUpdate can replace the use with an undef. That creates 2746a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // a debug instruction that is a kill. 2756a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // FIXME: Should it SSAUpdate job to delete debug instructions 2766a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // instead of replacing the use with undef? 2776a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola UseMI->eraseFromParent(); 2786a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2796a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2806a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (UseMI->getParent() == DefBB && !UseMI->isPHI()) 2816a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2826a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdate.RewriteUse(UseMO); 2836a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2846a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2856a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2866a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVRs.clear(); 2876a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola SSAUpdateVals.clear(); 2886a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 2896a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 2906a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Eliminate some of the copies inserted by tail duplication to maintain 2916a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // SSA form. 2926a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 2936a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineInstr *Copy = Copies[i]; 2946a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!Copy->isCopy()) 2956a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola continue; 2966a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned Dst = Copy->getOperand(0).getReg(); 2976a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola unsigned Src = Copy->getOperand(1).getReg(); 2980fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen if (MRI->hasOneNonDBGUse(Src) && 2990fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) { 3006a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola // Copy is the only use. Do trivial copy propagation here. 3016a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MRI->replaceRegWith(Dst, Src); 3026a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola Copy->eraseFromParent(); 3036a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 3046a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola } 3056a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 3066a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (NewPHIs.size()) 3076a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola NumAddedPHIs += NewPHIs.size(); 3086a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 3096a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola return true; 3106a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola} 3116a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 31215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// TailDuplicateBlocks - Look for small blocks that are unconditionally 31315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// branched to and do not fall through. Tail-duplicate their instructions 31415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// into their predecessors to eliminate (dynamic) branches. 3152d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 31615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 31715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 31875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) { 31900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 32075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, true); 32175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 32275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 32315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 32415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *MBB = I++; 32515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 32675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (NumTails == TailDupLimit) 32775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 32875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3296a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple = isSimpleBB(MBB); 33075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3316a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!shouldTailDuplicate(MF, IsSimple, *MBB)) 332c0af352038e43bd51ef3ea11e7d43647e4df42bfRafael Espindola continue; 33375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 3346a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MadeChange |= TailDuplicateAndUpdate(MBB, IsSimple, MF); 33515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 336c0af352038e43bd51ef3ea11e7d43647e4df42bfRafael Espindola 3376a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (PreRegAlloc && TailDupVerify) 3386a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola VerifyPHIs(MF, false); 339111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 34015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 34115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 34215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 343111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 344111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng const MachineRegisterInfo *MRI) { 34536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineInstr &UseMI : MRI->use_instructions(Reg)) { 34636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (UseMI.isDebugValue()) 347db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola continue; 34836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (UseMI.getParent() != BB) 349111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return true; 350111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 351111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return false; 352111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 353111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 354111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 355111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 356111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (MI->getOperand(i+1).getMBB() == SrcBB) 357111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return i; 358111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return 0; 359111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 360111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 3610f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 3620f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// Remember which registers are used by phis in this block. This is 3630f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// used to determine which registers are liveout while modifying the 3640f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// block (which is why we need to copy the information). 3650f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindolastatic void getRegsUsedByPHIs(const MachineBasicBlock &BB, 36633b465877255cc75241216817247c61374958a36Rafael Espindola DenseSet<unsigned> *UsedByPhi) { 367dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto &MI : BB) { 3680f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (!MI.isPHI()) 3690f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola break; 3700f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 3710f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola unsigned SrcReg = MI.getOperand(i).getReg(); 3720f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola UsedByPhi->insert(SrcReg); 3730f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3740f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3750f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola} 3760f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 377111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 378111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// SSA update. 37911572babb12d169965c63c47aab9c9fad354e5dfEvan Chengvoid TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 38011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB) { 38111572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 382111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (LI != SSAUpdateVals.end()) 38311572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng LI->second.push_back(std::make_pair(BB, NewReg)); 384111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng else { 385111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng AvailableValsTy Vals; 38611572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng Vals.push_back(std::make_pair(BB, NewReg)); 387111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 388111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVRs.push_back(OrigReg); 389111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 390111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 391111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 39275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 39375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// Remember the source register that's contributed by PredBB and update SSA 39475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// update map. 39583d63f8a4dca45d1bba13710c26b4173ace58a65Tobias Grosservoid TailDuplicatePass::ProcessPHI( 39683d63f8a4dca45d1bba13710c26b4173ace58a65Tobias Grosser MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB, 39783d63f8a4dca45d1bba13710c26b4173ace58a65Tobias Grosser DenseMap<unsigned, unsigned> &LocalVRMap, 39883d63f8a4dca45d1bba13710c26b4173ace58a65Tobias Grosser SmallVectorImpl<std::pair<unsigned, unsigned> > &Copies, 39983d63f8a4dca45d1bba13710c26b4173ace58a65Tobias Grosser const DenseSet<unsigned> &RegsUsedByPhi, bool Remove) { 40079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned DefReg = MI->getOperand(0).getReg(); 40179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 40279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(SrcOpIdx && "Unable to find matching PHI source?"); 40379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 40475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 40579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 40675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 40775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Insert a copy from source to the end of the block. The def register is the 40875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // available value liveout of the block. 40975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned NewDef = MRI->createVirtualRegister(RC); 41075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Copies.push_back(std::make_pair(NewDef, SrcReg)); 4110f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) 41275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng AddSSAUpdateEntry(DefReg, NewDef, PredBB); 41379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 414689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Remove) 415689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return; 416689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 41779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Remove PredBB from the PHI node. 41879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx+1); 41979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx); 42079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getNumOperands() == 1) 42179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 42279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 42379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 42479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 42579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// the source operands due to earlier PHI translation. 42679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 42779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 42879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 42979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 4300f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 4310f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi) { 43230ac0467ced4627a9b84d8a1d3ca5e8706ddad63Jakob Stoklund Olesen MachineInstr *NewMI = TII->duplicate(MI, MF); 43379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 43479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineOperand &MO = NewMI->getOperand(i); 43579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (!MO.isReg()) 43679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 43779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned Reg = MO.getReg(); 438c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 43979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 44079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MO.isDef()) { 44179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(Reg); 44279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned NewReg = MRI->createVirtualRegister(RC); 44379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(NewReg); 44479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(Reg, NewReg)); 4450f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) 44611572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng AddSSAUpdateEntry(Reg, NewReg, PredBB); 44779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 44879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 4490fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen if (VI != LocalVRMap.end()) { 45079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(VI->second); 4510fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen MRI->constrainRegClass(VI->second, MRI->getRegClass(Reg)); 4520fda545c2c164dc607f48f4b77f54c35bcafa413Jakob Stoklund Olesen } 45379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 45479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 455df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng PredBB->insert(PredBB->instr_end(), NewMI); 45679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 45779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 45879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 45979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// blocks, the successors have gained new predecessors. Update the PHI 46079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// instructions in them accordingly. 46175eb53584367098a5625028e22f1ff8e169d0efdEvan Chengvoid 46275eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 463a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineBasicBlock *> &TDBBs, 46479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*,8> &Succs) { 46579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 46679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SE = Succs.end(); SI != SE; ++SI) { 46779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *SuccBB = *SI; 46879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 46979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng II != EE; ++II) { 470518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!II->isPHI()) 47179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 4727b79b9862c9e6fc31ec072acb09171fd6ec7b0e0Jakob Stoklund Olesen MachineInstrBuilder MIB(*FromBB->getParent(), II); 47375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Idx = 0; 47479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 47575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 47675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 47775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Idx = i; 47879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 47975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 48075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 48175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 48275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng assert(Idx != 0); 48375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO0 = II->getOperand(Idx); 48475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Reg = MO0.getReg(); 48575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 48675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Folded into the previous BB. 48775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // There could be duplicate phi source entries. FIXME: Should sdisel 48875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // or earlier pass fixed this? 48975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 49075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 49175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 49275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i+1); 49375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i); 49475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 49575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 49609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else 49709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 49809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 49909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // If Idx is set, the operands at Idx and Idx+1 must be removed. 50009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // We reuse the location to avoid expensive RemoveOperand calls. 50109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 50275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 50375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (LI != SSAUpdateVals.end()) { 50475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // This register is defined in the tail block. 50579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 50611572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 507d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // If we didn't duplicate a bb into a particular predecessor, we 508d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // might still have added an entry to SSAUpdateVals to correcly 509d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // recompute SSA. If that case, avoid adding a dummy extra argument 510d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // this PHI. 511d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola if (!SrcBB->isSuccessor(SuccBB)) 512d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola continue; 513d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola 51411572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng unsigned SrcReg = LI->second[j].second; 51509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 51609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(SrcReg); 51709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 51809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 51909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 5207b79b9862c9e6fc31ec072acb09171fd6ec7b0e0Jakob Stoklund Olesen MIB.addReg(SrcReg).addMBB(SrcBB); 52109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 52279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 52375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } else { 52475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Live in tail block, must also be live in predecessors. 52575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 52675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = TDBBs[j]; 52709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 52809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(Reg); 52909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 53009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 53109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 5327b79b9862c9e6fc31ec072acb09171fd6ec7b0e0Jakob Stoklund Olesen MIB.addReg(Reg).addMBB(SrcBB); 53309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 53475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 53579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 53609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 53709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx+1); 53809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx); 53909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 54079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 54179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 54279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 54379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 54454c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// shouldTailDuplicate - Determine if it is profitable to duplicate this block. 54575eb53584367098a5625028e22f1ff8e169d0efdEvan Chengbool 54654c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael EspindolaTailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF, 5479dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola bool IsSimple, 54854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola MachineBasicBlock &TailBB) { 54954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola // Only duplicate blocks that end with unconditional branches. 55054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola if (TailBB.canFallThrough()) 55154c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola return false; 55254c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 553ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Don't try to tail-duplicate single-block loops. 554ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (TailBB.isSuccessor(&TailBB)) 555ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 556ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 55754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola // Set the limit on the cost to duplicate. When optimizing for size, 55815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // duplicate only one, because one branch instruction can be eliminated to 55915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // compensate for the duplication. 56015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson unsigned MaxDuplicateCount; 5618352062e52eed6e50786fdb89f5e601fdcbe0d90Jakob Stoklund Olesen if (TailDuplicateSize.getNumOccurrences() == 0 && 562831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling MF.getFunction()->getAttributes(). 563831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize)) 564cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = 1; 565cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson else 566cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = TailDuplicateSize; 567cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson 568ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // If the target has hardware branch prediction that can handle indirect 569ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // branches, duplicating them can often make them predictable when there 570ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // are common paths through the code. The limit needs to be high enough 571ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // to allow undoing the effects of tail merging and other optimizations 572ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // that rearrange the predecessors of the indirect branch. 573ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 5746a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool HasIndirectbr = false; 5756a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (!TailBB.empty()) 5765a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng HasIndirectbr = TailBB.back().isIndirectBranch(); 5776a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola 5786a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (HasIndirectbr && PreRegAlloc) 5796a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MaxDuplicateCount = 20; 58015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 58115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Check the instructions in the block to determine whether tail-duplication 58215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // is invalid or unlikely to be profitable. 583f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson unsigned InstrCount = 0; 5847c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng for (MachineBasicBlock::iterator I = TailBB.begin(); I != TailBB.end(); ++I) { 58515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Non-duplicable things shouldn't be tail-duplicated. 5865a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (I->isNotDuplicable()) 587ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 588ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 58979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Do not duplicate 'return' instructions if this is a pre-regalloc run. 59079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // A return may expand into a lot more instructions (e.g. reload of callee 59179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // saved registers) after PEI. 5925a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (PreRegAlloc && I->isReturn()) 593ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 594ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 595ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Avoid duplicating calls before register allocation. Calls presents a 596ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // barrier to register allocation so duplicating them may end up increasing 597ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // spills. 5985a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (PreRegAlloc && I->isCall()) 599ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 600ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 601cbe1e31732c5d4fb1277195e76b9b42c115396aaDevang Patel if (!I->isPHI() && !I->isDebugValue()) 602f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson InstrCount += 1; 603ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 604ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (InstrCount > MaxDuplicateCount) 605ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 60615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 60715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 6086a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola if (HasIndirectbr && PreRegAlloc) 6099dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return true; 6109dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 6119dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (IsSimple) 612d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return true; 6139dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 6149dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (!PreRegAlloc) 6159dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return true; 6169dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 61740179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola return canCompletelyDuplicateBB(TailBB); 61854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola} 61954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 620275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola/// isSimpleBB - True if this BB has only one unconditional jump. 621275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolabool 622275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolaTailDuplicatePass::isSimpleBB(MachineBasicBlock *TailBB) { 623275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (TailBB->succ_size() != 1) 624275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 6259dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola if (TailBB->pred_empty()) 6269dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return false; 627d6379a993c7e40521bd5c8c6469e32697b4c41d1Rafael Espindola MachineBasicBlock::iterator I = TailBB->begin(); 628275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock::iterator E = TailBB->end(); 629d6379a993c7e40521bd5c8c6469e32697b4c41d1Rafael Espindola while (I != E && I->isDebugValue()) 630275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola ++I; 631275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (I == E) 632275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 6335a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng return I->isUnconditionalBranch(); 634275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 635275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 636275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolastatic bool 637275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolabothUsedInPHI(const MachineBasicBlock &A, 638275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallPtrSet<MachineBasicBlock*, 8> SuccsB) { 639275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (MachineBasicBlock::const_succ_iterator SI = A.succ_begin(), 640275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SE = A.succ_end(); SI != SE; ++SI) { 641275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *BB = *SI; 642275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI()) 643275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 644275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 645275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 646275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 647275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 648275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 649275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindolabool 65040179bf8748b2729d6c733022428dfa1061325c9Rafael EspindolaTailDuplicatePass::canCompletelyDuplicateBB(MachineBasicBlock &BB) { 651275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (MachineBasicBlock::pred_iterator PI = BB.pred_begin(), 652275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PE = BB.pred_end(); PI != PE; ++PI) { 653275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredBB = *PI; 6549dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 65540179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola if (PredBB->succ_size() > 1) 65640179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola return false; 6579dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 658dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 659275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineOperand, 4> PredCond; 660275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 661275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return false; 6629dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola 66340179bf8748b2729d6c733022428dfa1061325c9Rafael Espindola if (!PredCond.empty()) 6649dbbd87938a0dc2ffe23f4205ec61618e052ca92Rafael Espindola return false; 665275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 666275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola return true; 667275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 668275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 669d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindolabool 670275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael EspindolaTailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB, 671a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineBasicBlock *> &TDBBs, 672a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper const DenseSet<unsigned> &UsedByPhi, 673a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &Copies) { 674d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola SmallPtrSet<MachineBasicBlock*, 8> Succs(TailBB->succ_begin(), 675d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola TailBB->succ_end()); 676275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 677275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TailBB->pred_end()); 678d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola bool Changed = false; 679275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 680275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PE = Preds.end(); PI != PE; ++PI) { 681275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *PredBB = *PI; 682275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 683d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (PredBB->getLandingPadSuccessor()) 684d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 685d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola 686d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (bothUsedInPHI(*PredBB, Succs)) 687d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 688d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola 689dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 690275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola SmallVector<MachineOperand, 4> PredCond; 691d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 692d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola continue; 693275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 694d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola Changed = true; 695275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 696275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola << "From simple Succ: " << *TailBB); 697275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 698275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola MachineBasicBlock *NewTarget = *TailBB->succ_begin(); 69936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineBasicBlock *NextBB = std::next(MachineFunction::iterator(PredBB)); 700275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 701275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make PredFBB explicit. 702275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredCond.empty()) 703275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = PredTBB; 704275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 705275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make fall through explicit. 706275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (!PredTBB) 707275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredTBB = NextBB; 708275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (!PredFBB) 709275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NextBB; 710275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 711275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Redirect 712275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredFBB == TailBB) 713275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredFBB = NewTarget; 714275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredTBB == TailBB) 715275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredTBB = NewTarget; 716275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 717275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Make the branch unconditional if possible 718689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola if (PredTBB == PredFBB) { 719689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola PredCond.clear(); 720dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PredFBB = nullptr; 721689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola } 722275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 723275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola // Avoid adding fall through branches. 724275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredFBB == NextBB) 725dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PredFBB = nullptr; 726dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (PredTBB == NextBB && PredFBB == nullptr) 727dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PredTBB = nullptr; 728275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 729275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TII->RemoveBranch(*PredBB); 730275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 731275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola if (PredTBB) 732275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc()); 733275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 73436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines uint32_t Weight = MBPI->getEdgeWeight(PredBB, TailBB); 735275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola PredBB->removeSuccessor(TailBB); 736689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola unsigned NumSuccessors = PredBB->succ_size(); 737689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola assert(NumSuccessors <= 1); 738689c24768bce1a3bf33b47559e9398525d11142dRafael Espindola if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget) 73936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PredBB->addSuccessor(NewTarget, Weight); 740275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 741275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola TDBBs.push_back(PredBB); 742275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola } 743d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return Changed; 744275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola} 745275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 74654c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 74754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// of its predecessors. 74854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindolabool 7496a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael EspindolaTailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, 7506a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola bool IsSimple, 7516a9d2b13fdc14d19b27776666cf50684bcfddc8dRafael Espindola MachineFunction &MF, 752a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineBasicBlock *> &TDBBs, 753a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &Copies) { 75400dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 75575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 756275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola DenseSet<unsigned> UsedByPhi; 757275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola getRegsUsedByPHIs(*TailBB, &UsedByPhi); 758275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 759d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola if (IsSimple) 760d7f35fa824165eea799a583ff5af678f2d842b87Rafael Espindola return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies); 761275c1f9f93bf71bcf97fe0315bbd9b86dd020177Rafael Espindola 76215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Iterate through all the unique predecessors and tail-duplicate this 76315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into them, if possible. Copying the list ahead of time also 76415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // avoids trouble with the predecessor list reallocating. 76515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool Changed = false; 76679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 76779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_end()); 76815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 76915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PE = Preds.end(); PI != PE; ++PI) { 77015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredBB = *PI; 77115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 77215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(TailBB != PredBB && 77315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "Single-block loop should have been rejected earlier!"); 7749a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola // EH edges are ignored by AnalyzeBranch. 7759a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola if (PredBB->succ_size() > 1) 7769a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola continue; 77715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 77815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredTBB, *PredFBB; 77915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PredCond; 78015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 78115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 78215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PredCond.empty()) 78315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 78415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate into a fall-through predecessor (at least for now). 78515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 78615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 78715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 78800dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 78915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From Succ: " << *TailBB); 79015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 79175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PredBB); 79275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 79315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove PredBB's unconditional branch. 79415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII->RemoveBranch(*PredBB); 795111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 796eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (RS && !TailBB->livein_empty()) { 797eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // Update PredBB livein. 798eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng RS->enterBasicBlock(PredBB); 799eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (!PredBB->empty()) 80036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RS->forward(std::prev(PredBB->end())); 801eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng BitVector RegsLiveAtExit(TRI->getNumRegs()); 802eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng RS->getRegsUsed(RegsLiveAtExit, false); 803eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng for (MachineBasicBlock::livein_iterator I = TailBB->livein_begin(), 804eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng E = TailBB->livein_end(); I != E; ++I) { 805eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng if (!RegsLiveAtExit[*I]) 806eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // If a register is previously livein to the tail but it's not live 807eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // at the end of predecessor BB, then it should be added to its 808eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng // livein list. 809eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng PredBB->addLiveIn(*I); 810eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng } 811eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng } 812eb25bd2356cca5ef83472b1ae0f764037b82ad82Evan Cheng 81315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Clone the contents of TailBB into PredBB. 814111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 8153466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 816df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng // Use instr_iterator here to properly handle bundles, e.g. 817df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng // ARM Thumb2 IT block. 818df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng MachineBasicBlock::instr_iterator I = TailBB->instr_begin(); 819df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng while (I != TailBB->instr_end()) { 82079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I; 82179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng ++I; 822518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isPHI()) { 823111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // Replace the uses of the def of the PHI with the register coming 824111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // from PredBB. 825689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); 82679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 82779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 82879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 8290f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi); 830111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 83115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 83275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 8333466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 8341e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 8351e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 8361e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first).addReg(CopyInfos[i].second)); 83775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 838ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 839ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Simplify 840ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true); 841ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 84215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 84315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 84415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Update the CFG. 84515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PredBB->removeSuccessor(PredBB->succ_begin()); 84615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(PredBB->succ_empty() && 84715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "TailDuplicate called on block with multiple successors!"); 84815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 84979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng E = TailBB->succ_end(); I != E; ++I) 85036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PredBB->addSuccessor(*I, MBPI->getEdgeWeight(TailBB, I)); 85115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 85215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 85315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson ++NumTailDups; 85415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 85515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 85615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If TailBB was duplicated into all its predecessors except for the prior 85715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block, which falls through unconditionally, move the contents of this 85815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into the prior block. 85936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineBasicBlock *PrevBB = std::prev(MachineFunction::iterator(TailBB)); 860dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr; 86115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PriorCond; 86215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // This has to check PrevBB->succ_size() because EH edges are ignored by 86315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // AnalyzeBranch. 864d2a7bedbc9d3db35ff424a6a2d257c72341af224Andrew Trick if (PrevBB->succ_size() == 1 && 865a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola !TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true) && 866a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola PriorCond.empty() && !PriorTBB && TailBB->pred_size() == 1 && 86715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !TailBB->hasAddressTaken()) { 86800dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 86915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From MBB: " << *TailBB); 87079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc) { 87179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 8723466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 87379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 87479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Process PHI instructions first. 875518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (I != TailBB->end() && I->isPHI()) { 87679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace the uses of the def of the PHI with the register coming 87779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // from PredBB. 87879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 879689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); 88079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getParent()) 88179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 88279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 88379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 88479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Now copy the non-PHI instructions. 88579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 88679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 88779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 88879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 889df7e8bd7020c300a3c17f5858d281828a5e0cf87Evan Cheng assert(!MI->isBundle() && "Not expecting bundles before regalloc!"); 8900f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi); 89179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 89279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 89375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 8943466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 8951e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 8961e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 8971e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first) 8981e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen .addReg(CopyInfos[i].second)); 89975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 90079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 90179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // No PHIs to worry about, just splice the instructions over. 90279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 90379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 90479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->removeSuccessor(PrevBB->succ_begin()); 90579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(PrevBB->succ_empty()); 90679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->transferSuccessors(TailBB); 90775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PrevBB); 90815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 90915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 91015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 911689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If this is after register allocation, there are no phis to fix. 912689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!PreRegAlloc) 913689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 914689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 915689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If we made no changes so far, we are safe. 916689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Changed) 917689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 918689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 919689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 920689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Handle the nasty case in that we duplicated a block that is part of a loop 921689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // into some but not all of its predecessors. For example: 9224d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 1 -> 2 <-> 3 | 9234d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ | 9244d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \---> rest | 925689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // if we duplicate 2 into 1 but not into 3, we end up with 9264d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 12 -> 3 <-> 2 -> rest | 9274d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ / | 9284d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \----->-----/ | 929689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced 930689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // with a phi in 3 (which now dominates 2). 931689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // What we do here is introduce a copy in 3 of the register defined by the 932689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // phi, just like when we are duplicating 2 into 3, but we don't copy any 933689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // real instructions or remove the 3 -> 2 edge from the phi in 2. 934689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 935689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola PE = Preds.end(); PI != PE; ++PI) { 936689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock *PredBB = *PI; 937689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (std::find(TDBBs.begin(), TDBBs.end(), PredBB) != TDBBs.end()) 938689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 939689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 940689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // EH edges 941689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (PredBB->succ_size() != 1) 942689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 943689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 944689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola DenseMap<unsigned, unsigned> LocalVRMap; 945689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 946689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator I = TailBB->begin(); 947689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Process PHI instructions first. 948689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola while (I != TailBB->end() && I->isPHI()) { 949689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Replace the uses of the def of the PHI with the register coming 950689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // from PredBB. 951689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineInstr *MI = &*I++; 952689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); 953689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 954689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 955689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 956689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 957689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola TII->get(TargetOpcode::COPY), 958689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola CopyInfos[i].first).addReg(CopyInfos[i].second)); 959689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 960689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 961689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 96215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return Changed; 96315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 96415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 96515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// RemoveDeadBlock - Remove the specified dead machine basic block from the 96615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// function, updating the CFG. 9672d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonvoid TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 96815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(MBB->pred_empty() && "MBB must be dead!"); 96900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 97015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 97115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove all successors. 97215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson while (!MBB->succ_empty()) 97315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->removeSuccessor(MBB->succ_end()-1); 97415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 97515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove the block. 97615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->eraseFromParent(); 97715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 978