TailDuplication.cpp revision 33b465877255cc75241216817247c61374958a36
115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson//===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===// 215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// The LLVM Compiler Infrastructure 415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// This file is distributed under the University of Illinois Open Source 615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// License. See LICENSE.TXT for details. 715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson//===----------------------------------------------------------------------===// 915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 1015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// This pass duplicates basic blocks ending in unconditional branches into 1115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// the tails of their predecessors. 1215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 1315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson//===----------------------------------------------------------------------===// 1415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#define DEBUG_TYPE "tailduplication" 1615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Function.h" 1715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/CodeGen/Passes.h" 1815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/CodeGen/MachineModuleInfo.h" 1915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/CodeGen/MachineFunctionPass.h" 201e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 21111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 22111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineSSAUpdater.h" 2315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Target/TargetInstrInfo.h" 2415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/CommandLine.h" 2515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/Debug.h" 2675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng#include "llvm/Support/ErrorHandling.h" 2715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/raw_ostream.h" 2815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/SmallSet.h" 2915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/SetVector.h" 3015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/Statistic.h" 3115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonusing namespace llvm; 3215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 3375eb53584367098a5625028e22f1ff8e169d0efdEvan ChengSTATISTIC(NumTails , "Number of tails duplicated"); 3415acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumTailDups , "Number of tail duplicated blocks"); 3515acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 3615acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 370cdca089b289845664d660f0b285499800822919Rafael EspindolaSTATISTIC(NumAddedPHIs , "Number of phis added"); 3815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 3915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// Heuristic for tail duplication. 4015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonstatic cl::opt<unsigned> 4115acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonTailDuplicateSize("tail-dup-size", 4215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::desc("Maximum instructions to consider tail duplicating"), 4315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::init(2), cl::Hidden); 4415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4575eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<bool> 4675eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupVerify("tail-dup-verify", 4775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::desc("Verify sanity of PHI instructions during taildup"), 4875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::init(false), cl::Hidden); 4975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5075eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<unsigned> 5175eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 5275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5311572babb12d169965c63c47aab9c9fad354e5dfEvan Chengtypedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 54111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 5515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonnamespace { 562d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson /// TailDuplicatePass - Perform tail duplication. 572d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson class TailDuplicatePass : public MachineFunctionPass { 5879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng bool PreRegAlloc; 5915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson const TargetInstrInfo *TII; 6015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineModuleInfo *MMI; 61111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineRegisterInfo *MRI; 62111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 63111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 64111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SmallVector<unsigned, 16> SSAUpdateVRs; 65111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 66111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 67111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // source virtual registers. 68111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 6915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson public: 7115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson static char ID; 7279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng explicit TailDuplicatePass(bool PreRA) : 7390c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson MachineFunctionPass(ID), PreRegAlloc(PreRA) {} 7415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual bool runOnMachineFunction(MachineFunction &MF); 7615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual const char *getPassName() const { return "Tail Duplication"; } 7715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson private: 7911572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 8011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB); 8179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 8279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 8375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 840f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 85689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola const DenseSet<unsigned> &UsedByPhi, 86689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola bool Remove); 8779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void DuplicateInstruction(MachineInstr *MI, 8879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 8979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 9079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 910f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 920f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi); 9375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 9475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 9575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> &Succs); 9615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool TailDuplicateBlocks(MachineFunction &MF); 9754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola bool shouldTailDuplicate(const MachineFunction &MF, 9854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola MachineBasicBlock &TailBB); 9975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 1003466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 1013466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> &Copies); 10215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson void RemoveDeadBlock(MachineBasicBlock *MBB); 10315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson }; 10415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1052d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson char TailDuplicatePass::ID = 0; 10615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 10715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 10879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan ChengFunctionPass *llvm::createTailDuplicatePass(bool PreRegAlloc) { 10979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng return new TailDuplicatePass(PreRegAlloc); 11015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 11115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1122d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 11315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII = MF.getTarget().getInstrInfo(); 114111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MRI = &MF.getRegInfo(); 11515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 11615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 11715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 118057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen while (TailDuplicateBlocks(MF)) 119057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen MadeChange = true; 12015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 12115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 12215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 12315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 12475eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 12575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 12675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *MBB = I; 12775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 12875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->pred_end()); 12975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator MI = MBB->begin(); 13075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (MI != MBB->end()) { 131518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!MI->isPHI()) 13275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 13375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 13475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng PE = Preds.end(); PI != PE; ++PI) { 13575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PredBB = *PI; 13675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool Found = false; 13775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 13875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 13975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB == PredBB) { 14075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Found = true; 14175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 14275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 14375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 14475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!Found) { 14500dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 14600dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " missing input from predecessor BB#" 14775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PredBB->getNumber() << '\n'; 14875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 14975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 15075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 15175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 15275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 15375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 15475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (CheckExtra && !Preds.count(PHIBB)) { 15500dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 15675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << ": " << *MI; 15700dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " extra input from predecessor BB#" 15875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PHIBB->getNumber() << '\n'; 159d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola llvm_unreachable(0); 16075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB->getNumber() < 0) { 16200dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 16300dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 16475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 16575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++MI; 16875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 17075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng} 17175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 17215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// TailDuplicateBlocks - Look for small blocks that are unconditionally 17315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// branched to and do not fall through. Tail-duplicate their instructions 17415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// into their predecessors to eliminate (dynamic) branches. 1752d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 17615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 17715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 17875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) { 17900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 18075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, true); 18175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 18375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineInstr*, 8> NewPHIs; 18475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 18575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 18615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 18715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *MBB = I++; 18815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 18975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (NumTails == TailDupLimit) 19075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 19175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 19275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Save the successors list. 19375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 19475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->succ_end()); 19575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 19675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> TDBBs; 1973466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> Copies; 1983466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng if (TailDuplicate(MBB, MF, TDBBs, Copies)) { 19975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++NumTails; 20075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 20175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // TailBB's immediate successors are now successors of those predecessors 20275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // which duplicated TailBB. Add the predecessors as sources to the PHI 20375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // instructions. 20475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool isDead = MBB->pred_empty(); 20575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc) 20675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 20775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 20875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // If it is dead, remove it. 20975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 21075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng NumInstrDups -= MBB->size(); 21175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng RemoveDeadBlock(MBB); 21275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++NumDeadBlocks; 21375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 21475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 21575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Update SSA form. 21675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!SSAUpdateVRs.empty()) { 21775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 21875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned VReg = SSAUpdateVRs[i]; 21975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.Initialize(VReg); 22075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 22175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // If the original definition is still around, add it as an available 22275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // value. 22375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineInstr *DefMI = MRI->getVRegDef(VReg); 22475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *DefBB = 0; 22575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (DefMI) { 22675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DefBB = DefMI->getParent(); 22775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.AddAvailableValue(DefBB, VReg); 22875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 22975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 23075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Add the new vregs as available values. 23175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI = 23275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVals.find(VReg); 23375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 23475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 23575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned SrcReg = LI->second[j].second; 23675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 23775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 23875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 23975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Rewrite uses that are outside of the original def's block. 24075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 24175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (UI != MRI->use_end()) { 24275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &UseMO = UI.getOperand(); 24375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineInstr *UseMI = &*UI; 24475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++UI; 245c2e9a50dfb523964bd9d7598ee27b37669f9a5b8Rafael Espindola if (UseMI->getParent() == DefBB && !UseMI->isPHI()) 24675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng continue; 24775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.RewriteUse(UseMO); 24875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 24975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 25015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 25175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVRs.clear(); 25275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVals.clear(); 25375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 25475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 255bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson // Eliminate some of the copies inserted by tail duplication to maintain 2563466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng // SSA form. 2573466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 2583466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng MachineInstr *Copy = Copies[i]; 25904c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (!Copy->isCopy()) 26004c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen continue; 26104c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned Dst = Copy->getOperand(0).getReg(); 26204c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned Src = Copy->getOperand(1).getReg(); 26304c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); 26404c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (++UI == MRI->use_end()) { 26504c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen // Copy is the only use. Do trivial copy propagation here. 26604c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen MRI->replaceRegWith(Dst, Src); 26704c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen Copy->eraseFromParent(); 2683466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2693466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2703466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng 27175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) 27275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, false); 27315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MadeChange = true; 27415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 27515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 276d69f85eb416c08e5f803bffccd974745be3d1b2eRafael Espindola NumAddedPHIs += NewPHIs.size(); 277111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 27815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 27915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 28015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 281111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 282111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng const MachineRegisterInfo *MRI) { 283111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 284111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng UE = MRI->use_end(); UI != UE; ++UI) { 285111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineInstr *UseMI = &*UI; 286111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (UseMI->getParent() != BB) 287111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return true; 288111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 289111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return false; 290111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 291111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 292111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 293111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 294111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (MI->getOperand(i+1).getMBB() == SrcBB) 295111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return i; 296111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return 0; 297111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 298111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 2990f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 3000f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// Remember which registers are used by phis in this block. This is 3010f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// used to determine which registers are liveout while modifying the 3020f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// block (which is why we need to copy the information). 3030f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindolastatic void getRegsUsedByPHIs(const MachineBasicBlock &BB, 30433b465877255cc75241216817247c61374958a36Rafael Espindola DenseSet<unsigned> *UsedByPhi) { 3050f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola for(MachineBasicBlock::const_iterator I = BB.begin(), E = BB.end(); 3060f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola I != E; ++I) { 3070f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const MachineInstr &MI = *I; 3080f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (!MI.isPHI()) 3090f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola break; 3100f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 3110f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola unsigned SrcReg = MI.getOperand(i).getReg(); 3120f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola UsedByPhi->insert(SrcReg); 3130f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3140f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3150f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola} 3160f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 317111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 318111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// SSA update. 31911572babb12d169965c63c47aab9c9fad354e5dfEvan Chengvoid TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 32011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB) { 32111572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 322111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (LI != SSAUpdateVals.end()) 32311572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng LI->second.push_back(std::make_pair(BB, NewReg)); 324111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng else { 325111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng AvailableValsTy Vals; 32611572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng Vals.push_back(std::make_pair(BB, NewReg)); 327111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 328111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVRs.push_back(OrigReg); 329111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 330111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 331111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 33275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 33375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// Remember the source register that's contributed by PredBB and update SSA 33475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// update map. 33579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::ProcessPHI(MachineInstr *MI, 33679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 33779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 33875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 3390f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 34033b465877255cc75241216817247c61374958a36Rafael Espindola const DenseSet<unsigned> &RegsUsedByPhi, 341689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola bool Remove) { 34279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned DefReg = MI->getOperand(0).getReg(); 34379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 34479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(SrcOpIdx && "Unable to find matching PHI source?"); 34579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 34675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 34779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 34875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 34975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Insert a copy from source to the end of the block. The def register is the 35075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // available value liveout of the block. 35175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned NewDef = MRI->createVirtualRegister(RC); 35275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Copies.push_back(std::make_pair(NewDef, SrcReg)); 3530f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) 35475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng AddSSAUpdateEntry(DefReg, NewDef, PredBB); 35579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 356689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Remove) 357689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return; 358689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 35979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Remove PredBB from the PHI node. 36079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx+1); 36179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx); 36279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getNumOperands() == 1) 36379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 36479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 36579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 36679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 36779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// the source operands due to earlier PHI translation. 36879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 36979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 37079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 37179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 3720f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 3730f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi) { 37430ac0467ced4627a9b84d8a1d3ca5e8706ddad63Jakob Stoklund Olesen MachineInstr *NewMI = TII->duplicate(MI, MF); 37579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 37679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineOperand &MO = NewMI->getOperand(i); 37779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (!MO.isReg()) 37879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 37979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned Reg = MO.getReg(); 380c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 38179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 38279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MO.isDef()) { 38379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(Reg); 38479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned NewReg = MRI->createVirtualRegister(RC); 38579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(NewReg); 38679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(Reg, NewReg)); 3870f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) 38811572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng AddSSAUpdateEntry(Reg, NewReg, PredBB); 38979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 39079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 39179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (VI != LocalVRMap.end()) 39279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(VI->second); 39379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 39479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 39579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->insert(PredBB->end(), NewMI); 39679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 39779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 39879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 39979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// blocks, the successors have gained new predecessors. Update the PHI 40079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// instructions in them accordingly. 40175eb53584367098a5625028e22f1ff8e169d0efdEvan Chengvoid 40275eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 40375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 40479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*,8> &Succs) { 40579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 40679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SE = Succs.end(); SI != SE; ++SI) { 40779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *SuccBB = *SI; 40879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 40979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng II != EE; ++II) { 410518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!II->isPHI()) 41179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 41275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Idx = 0; 41379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 41475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 41575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 41675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Idx = i; 41779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 41875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 41975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 42075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 42175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng assert(Idx != 0); 42275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO0 = II->getOperand(Idx); 42375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Reg = MO0.getReg(); 42475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 42575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Folded into the previous BB. 42675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // There could be duplicate phi source entries. FIXME: Should sdisel 42775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // or earlier pass fixed this? 42875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 42975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 43075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 43175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i+1); 43275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i); 43375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 43475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 43509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else 43609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 43709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 43809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // If Idx is set, the operands at Idx and Idx+1 must be removed. 43909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // We reuse the location to avoid expensive RemoveOperand calls. 44009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 44175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 44275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (LI != SSAUpdateVals.end()) { 44375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // This register is defined in the tail block. 44479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 44511572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 446d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // If we didn't duplicate a bb into a particular predecessor, we 447d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // might still have added an entry to SSAUpdateVals to correcly 448d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // recompute SSA. If that case, avoid adding a dummy extra argument 449d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // this PHI. 450d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola if (!SrcBB->isSuccessor(SuccBB)) 451d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola continue; 452d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola 45311572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng unsigned SrcReg = LI->second[j].second; 45409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 45509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(SrcReg); 45609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 45709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 45809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 45909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 46009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(SrcBB)); 46109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 46279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 46375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } else { 46475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Live in tail block, must also be live in predecessors. 46575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 46675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = TDBBs[j]; 46709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 46809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(Reg); 46909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 47009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 47109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 47209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(Reg, false)); 47309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(SrcBB)); 47409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 47575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 47679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 47709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 47809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx+1); 47909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx); 48009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 48179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 48279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 48379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 48479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 48554c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// shouldTailDuplicate - Determine if it is profitable to duplicate this block. 48675eb53584367098a5625028e22f1ff8e169d0efdEvan Chengbool 48754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael EspindolaTailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF, 48854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola MachineBasicBlock &TailBB) { 48954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola // Only duplicate blocks that end with unconditional branches. 49054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola if (TailBB.canFallThrough()) 49154c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola return false; 49254c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 49354c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola // Set the limit on the cost to duplicate. When optimizing for size, 49415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // duplicate only one, because one branch instruction can be eliminated to 49515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // compensate for the duplication. 49615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson unsigned MaxDuplicateCount; 4978352062e52eed6e50786fdb89f5e601fdcbe0d90Jakob Stoklund Olesen if (TailDuplicateSize.getNumOccurrences() == 0 && 4988352062e52eed6e50786fdb89f5e601fdcbe0d90Jakob Stoklund Olesen MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 499cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = 1; 500cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson else 501cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = TailDuplicateSize; 502cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson 503cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson if (PreRegAlloc) { 50454c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola if (TailBB.empty()) 505c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng return false; 50654c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola const TargetInstrDesc &TID = TailBB.back().getDesc(); 507c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // Pre-regalloc tail duplication hurts compile time and doesn't help 50854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola // much except for indirect branches. 50954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola if (!TID.isIndirectBranch()) 510cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson return false; 51115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If the target has hardware branch prediction that can handle indirect 51215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // branches, duplicating them can often make them predictable when there 51315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // are common paths through the code. The limit needs to be high enough 514cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson // to allow undoing the effects of tail merging and other optimizations 515cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson // that rearrange the predecessors of the indirect branch. 51615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MaxDuplicateCount = 20; 517cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson } 51815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 519bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson // Don't try to tail-duplicate single-block loops. 52054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola if (TailBB.isSuccessor(&TailBB)) 521bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson return false; 522bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson 52315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Check the instructions in the block to determine whether tail-duplication 52415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // is invalid or unlikely to be profitable. 525f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson unsigned InstrCount = 0; 52615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool HasCall = false; 52754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola for (MachineBasicBlock::const_iterator I = TailBB.begin(); I != TailBB.end(); 52854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola ++I) { 52915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Non-duplicable things shouldn't be tail-duplicated. 53015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (I->getDesc().isNotDuplicable()) return false; 53179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Do not duplicate 'return' instructions if this is a pre-regalloc run. 53279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // A return may expand into a lot more instructions (e.g. reload of callee 53379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // saved registers) after PEI. 53479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc && I->getDesc().isReturn()) return false; 53515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate more than the threshold. 536f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson if (InstrCount == MaxDuplicateCount) return false; 53715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remember if we saw a call. 53815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (I->getDesc().isCall()) HasCall = true; 539cbe1e31732c5d4fb1277195e76b9b42c115396aaDevang Patel if (!I->isPHI() && !I->isDebugValue()) 540f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson InstrCount += 1; 54115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 542c8b90e22a8f2987126a7e2e841adc8db9776521cEvan Cheng // Don't tail-duplicate calls before register allocation. Calls presents a 543c8b90e22a8f2987126a7e2e841adc8db9776521cEvan Cheng // barrier to register allocation so duplicating them may end up increasing 544c8b90e22a8f2987126a7e2e841adc8db9776521cEvan Cheng // spills. 545c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng if (InstrCount > 1 && (PreRegAlloc && HasCall)) 54615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return false; 54715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 54854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola return true; 54954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola} 55054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 55154c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 55254c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// of its predecessors. 55354c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindolabool 55454c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael EspindolaTailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 55554c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola SmallVector<MachineBasicBlock*, 8> &TDBBs, 55654c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola SmallVector<MachineInstr*, 16> &Copies) { 55754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola if (!shouldTailDuplicate(MF, *TailBB)) 55854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola return false; 55954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 56000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 56175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 56215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Iterate through all the unique predecessors and tail-duplicate this 56315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into them, if possible. Copying the list ahead of time also 56415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // avoids trouble with the predecessor list reallocating. 56515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool Changed = false; 56679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 56779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_end()); 5680f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseSet<unsigned> UsedByPhi; 5690f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola getRegsUsedByPHIs(*TailBB, &UsedByPhi); 57015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 57115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PE = Preds.end(); PI != PE; ++PI) { 57215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredBB = *PI; 57315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 57415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(TailBB != PredBB && 57515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "Single-block loop should have been rejected earlier!"); 5769a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola // EH edges are ignored by AnalyzeBranch. 5779a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola if (PredBB->succ_size() > 1) 5789a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola continue; 57915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 58015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredTBB, *PredFBB; 58115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PredCond; 58215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 58315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 58415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PredCond.empty()) 58515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 58615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate into a fall-through predecessor (at least for now). 58715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 58815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 58915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 59000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 59115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From Succ: " << *TailBB); 59215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 59375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PredBB); 59475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 59515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove PredBB's unconditional branch. 59615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII->RemoveBranch(*PredBB); 597111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 59815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Clone the contents of TailBB into PredBB. 599111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 6003466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 601111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 60279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 60379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I; 60479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng ++I; 605518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isPHI()) { 606111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // Replace the uses of the def of the PHI with the register coming 607111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // from PredBB. 608689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); 60979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 61079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 61179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 6120f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi); 613111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 61415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 61575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 6163466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 6171e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 6181e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 6191e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first).addReg(CopyInfos[i].second)); 62075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 62115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 62215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 62315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Update the CFG. 62415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PredBB->removeSuccessor(PredBB->succ_begin()); 62515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(PredBB->succ_empty() && 62615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "TailDuplicate called on block with multiple successors!"); 62715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 62879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng E = TailBB->succ_end(); I != E; ++I) 62979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->addSuccessor(*I); 63015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 63115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 63215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson ++NumTailDups; 63315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 63415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 63515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If TailBB was duplicated into all its predecessors except for the prior 63615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block, which falls through unconditionally, move the contents of this 63715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into the prior block. 63879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 63915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 64015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PriorCond; 64115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // This has to check PrevBB->succ_size() because EH edges are ignored by 64215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // AnalyzeBranch. 643a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola if (PrevBB->succ_size() == 1 && 644a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola !TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true) && 645a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola PriorCond.empty() && !PriorTBB && TailBB->pred_size() == 1 && 64615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !TailBB->hasAddressTaken()) { 64700dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 64815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From MBB: " << *TailBB); 64979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc) { 65079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 6513466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 65279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 65379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Process PHI instructions first. 654518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (I != TailBB->end() && I->isPHI()) { 65579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace the uses of the def of the PHI with the register coming 65679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // from PredBB. 65779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 658689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); 65979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getParent()) 66079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 66179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 66279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 66379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Now copy the non-PHI instructions. 66479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 66579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 66679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 66779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 6680f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi); 66979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 67079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 67175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 6723466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 6731e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 6741e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 6751e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first) 6761e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen .addReg(CopyInfos[i].second)); 67775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 67879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 67979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // No PHIs to worry about, just splice the instructions over. 68079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 68179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 68279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->removeSuccessor(PrevBB->succ_begin()); 68379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(PrevBB->succ_empty()); 68479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->transferSuccessors(TailBB); 68575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PrevBB); 68615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 68715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 68815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 689689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If this is after register allocation, there are no phis to fix. 690689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!PreRegAlloc) 691689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 692689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 693689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If we made no changes so far, we are safe. 694689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Changed) 695689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 696689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 697689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 698689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Handle the nasty case in that we duplicated a block that is part of a loop 699689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // into some but not all of its predecessors. For example: 7004d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 1 -> 2 <-> 3 | 7014d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ | 7024d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \---> rest | 703689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // if we duplicate 2 into 1 but not into 3, we end up with 7044d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 12 -> 3 <-> 2 -> rest | 7054d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ / | 7064d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \----->-----/ | 707689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced 708689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // with a phi in 3 (which now dominates 2). 709689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // What we do here is introduce a copy in 3 of the register defined by the 710689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // phi, just like when we are duplicating 2 into 3, but we don't copy any 711689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // real instructions or remove the 3 -> 2 edge from the phi in 2. 712689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 713689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola PE = Preds.end(); PI != PE; ++PI) { 714689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock *PredBB = *PI; 715689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (std::find(TDBBs.begin(), TDBBs.end(), PredBB) != TDBBs.end()) 716689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 717689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 718689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // EH edges 719689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (PredBB->succ_size() != 1) 720689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 721689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 722689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola DenseMap<unsigned, unsigned> LocalVRMap; 723689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 724689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator I = TailBB->begin(); 725689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Process PHI instructions first. 726689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola while (I != TailBB->end() && I->isPHI()) { 727689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Replace the uses of the def of the PHI with the register coming 728689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // from PredBB. 729689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineInstr *MI = &*I++; 730689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); 731689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 732689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 733689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 734689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 735689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola TII->get(TargetOpcode::COPY), 736689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola CopyInfos[i].first).addReg(CopyInfos[i].second)); 737689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 738689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 739689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 74015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return Changed; 74115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 74215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 74315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// RemoveDeadBlock - Remove the specified dead machine basic block from the 74415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// function, updating the CFG. 7452d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonvoid TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 74615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(MBB->pred_empty() && "MBB must be dead!"); 74700dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 74815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 74915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove all successors. 75015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson while (!MBB->succ_empty()) 75115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->removeSuccessor(MBB->succ_end()-1); 75215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 75315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove the block. 75415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->eraseFromParent(); 75515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 756