TailDuplication.cpp revision 00dec1bbf9ad44af7b5b7ae669cae78b79a09c56
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" 20111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 21111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineSSAUpdater.h" 2215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Target/TargetInstrInfo.h" 2315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/CommandLine.h" 2415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/Debug.h" 2575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng#include "llvm/Support/ErrorHandling.h" 2615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/raw_ostream.h" 2715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/SmallSet.h" 2815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/SetVector.h" 2915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/Statistic.h" 3015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonusing namespace llvm; 3115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 3275eb53584367098a5625028e22f1ff8e169d0efdEvan ChengSTATISTIC(NumTails , "Number of tails duplicated"); 3315acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumTailDups , "Number of tail duplicated blocks"); 3415acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 3515acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 3615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 3715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// Heuristic for tail duplication. 3815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonstatic cl::opt<unsigned> 3915acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonTailDuplicateSize("tail-dup-size", 4015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::desc("Maximum instructions to consider tail duplicating"), 4115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::init(2), cl::Hidden); 4215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4375eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<bool> 4475eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupVerify("tail-dup-verify", 4575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::desc("Verify sanity of PHI instructions during taildup"), 4675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::init(false), cl::Hidden); 4775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 4875eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<unsigned> 4975eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 5075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5111572babb12d169965c63c47aab9c9fad354e5dfEvan Chengtypedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 52111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 5315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonnamespace { 542d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson /// TailDuplicatePass - Perform tail duplication. 552d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson class TailDuplicatePass : public MachineFunctionPass { 5679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng bool PreRegAlloc; 5715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson const TargetInstrInfo *TII; 5815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineModuleInfo *MMI; 59111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineRegisterInfo *MRI; 60111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 61111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 62111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SmallVector<unsigned, 16> SSAUpdateVRs; 63111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 64111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 65111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // source virtual registers. 66111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 6715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 6815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson public: 6915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson static char ID; 7079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng explicit TailDuplicatePass(bool PreRA) : 7179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunctionPass(&ID), PreRegAlloc(PreRA) {} 7215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual bool runOnMachineFunction(MachineFunction &MF); 7415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual const char *getPassName() const { return "Tail Duplication"; } 7515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson private: 7711572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 7811572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB); 7979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 8079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 8175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 8275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> &Copies); 8379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void DuplicateInstruction(MachineInstr *MI, 8479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 8579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 8679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 8779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap); 8875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 8975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 9075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> &Succs); 9115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool TailDuplicateBlocks(MachineFunction &MF); 9275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 933466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 943466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> &Copies); 9515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson void RemoveDeadBlock(MachineBasicBlock *MBB); 9615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson }; 9715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 982d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson char TailDuplicatePass::ID = 0; 9915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 10015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 10179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan ChengFunctionPass *llvm::createTailDuplicatePass(bool PreRegAlloc) { 10279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng return new TailDuplicatePass(PreRegAlloc); 10315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 10415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1052d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 10615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII = MF.getTarget().getInstrInfo(); 107111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MRI = &MF.getRegInfo(); 10815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 10915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 11015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 11115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChangeThisIteration = true; 11215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson while (MadeChangeThisIteration) { 11315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MadeChangeThisIteration = false; 11415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MadeChangeThisIteration |= TailDuplicateBlocks(MF); 11515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MadeChange |= MadeChangeThisIteration; 11615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 11715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 11815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 11915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 12015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 12175eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 12275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 12375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *MBB = I; 12475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 12575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->pred_end()); 12675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator MI = MBB->begin(); 12775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (MI != MBB->end()) { 12875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MI->getOpcode() != TargetInstrInfo::PHI) 12975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 13075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 13175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng PE = Preds.end(); PI != PE; ++PI) { 13275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PredBB = *PI; 13375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool Found = false; 13475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 13575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 13675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB == PredBB) { 13775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Found = true; 13875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 13975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 14075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 14175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!Found) { 14200dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 14300dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " missing input from predecessor BB#" 14475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PredBB->getNumber() << '\n'; 14575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 14675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 14775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 14875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 14975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 15075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 15175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (CheckExtra && !Preds.count(PHIBB)) { 15275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // This is not a hard error. 15300dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 15475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << ": " << *MI; 15500dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " extra input from predecessor BB#" 15675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PHIBB->getNumber() << '\n'; 15775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 15875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB->getNumber() < 0) { 15900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 16000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 16175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 16275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++MI; 16575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng} 16875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 16915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// TailDuplicateBlocks - Look for small blocks that are unconditionally 17015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// branched to and do not fall through. Tail-duplicate their instructions 17115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// into their predecessors to eliminate (dynamic) branches. 1722d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 17315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 17415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 17575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) { 17600dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 17775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, true); 17875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 17975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 18075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineInstr*, 8> NewPHIs; 18175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 18275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 18315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 18415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *MBB = I++; 18515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 18675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (NumTails == TailDupLimit) 18775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 18875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 18915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Only duplicate blocks that end with unconditional branches. 19015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (MBB->canFallThrough()) 19115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 19215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 19375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Save the successors list. 19475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 19575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->succ_end()); 19675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 19775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> TDBBs; 1983466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> Copies; 1993466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng if (TailDuplicate(MBB, MF, TDBBs, Copies)) { 20075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++NumTails; 20175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 20275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // TailBB's immediate successors are now successors of those predecessors 20375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // which duplicated TailBB. Add the predecessors as sources to the PHI 20475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // instructions. 20575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool isDead = MBB->pred_empty(); 20675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc) 20775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 20875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 20975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // If it is dead, remove it. 21075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 21175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng NumInstrDups -= MBB->size(); 21275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng RemoveDeadBlock(MBB); 21375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++NumDeadBlocks; 21475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 21575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 21675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Update SSA form. 21775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!SSAUpdateVRs.empty()) { 21875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 21975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned VReg = SSAUpdateVRs[i]; 22075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.Initialize(VReg); 22175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 22275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // If the original definition is still around, add it as an available 22375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // value. 22475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineInstr *DefMI = MRI->getVRegDef(VReg); 22575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *DefBB = 0; 22675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (DefMI) { 22775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DefBB = DefMI->getParent(); 22875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.AddAvailableValue(DefBB, VReg); 22975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 23075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 23175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Add the new vregs as available values. 23275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI = 23375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVals.find(VReg); 23475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 23575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 23675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned SrcReg = LI->second[j].second; 23775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 23875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 23975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 24075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Rewrite uses that are outside of the original def's block. 24175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 24275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (UI != MRI->use_end()) { 24375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &UseMO = UI.getOperand(); 24475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineInstr *UseMI = &*UI; 24575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++UI; 24675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (UseMI->getParent() == DefBB) 24775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng continue; 24875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.RewriteUse(UseMO); 24975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 25075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 25115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 25275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVRs.clear(); 25375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVals.clear(); 25475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 25575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 2563466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng // Eliminate some of the copies inserted tail duplication to maintain 2573466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng // SSA form. 2583466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 2593466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng MachineInstr *Copy = Copies[i]; 2603466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng unsigned Src, Dst, SrcSR, DstSR; 2613466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng if (TII->isMoveInstr(*Copy, Src, Dst, SrcSR, DstSR)) { 2623466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); 2633466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng if (++UI == MRI->use_end()) { 2643466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng // Copy is the only use. Do trivial copy propagation here. 2653466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng MRI->replaceRegWith(Dst, Src); 2663466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng Copy->eraseFromParent(); 2673466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2683466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2693466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2703466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng 27175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) 27275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, false); 27315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MadeChange = true; 27415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 27515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 276111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 27715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 27815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 27915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 280111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 281111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng const MachineRegisterInfo *MRI) { 282111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 283111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng UE = MRI->use_end(); UI != UE; ++UI) { 284111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineInstr *UseMI = &*UI; 285111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (UseMI->getParent() != BB) 286111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return true; 287111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 288111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return false; 289111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 290111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 291111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 292111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 293111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (MI->getOperand(i+1).getMBB() == SrcBB) 294111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return i; 295111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return 0; 296111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 297111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 298111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 299111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// SSA update. 30011572babb12d169965c63c47aab9c9fad354e5dfEvan Chengvoid TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 30111572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB) { 30211572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 303111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (LI != SSAUpdateVals.end()) 30411572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng LI->second.push_back(std::make_pair(BB, NewReg)); 305111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng else { 306111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng AvailableValsTy Vals; 30711572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng Vals.push_back(std::make_pair(BB, NewReg)); 308111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 309111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVRs.push_back(OrigReg); 310111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 311111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 312111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 31375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 31475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// Remember the source register that's contributed by PredBB and update SSA 31575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// update map. 31679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::ProcessPHI(MachineInstr *MI, 31779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 31879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 31975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 32075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> &Copies) { 32179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned DefReg = MI->getOperand(0).getReg(); 32279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 32379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(SrcOpIdx && "Unable to find matching PHI source?"); 32479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 32575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 32679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 32775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 32875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Insert a copy from source to the end of the block. The def register is the 32975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // available value liveout of the block. 33075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned NewDef = MRI->createVirtualRegister(RC); 33175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Copies.push_back(std::make_pair(NewDef, SrcReg)); 33279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (isDefLiveOut(DefReg, TailBB, MRI)) 33375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng AddSSAUpdateEntry(DefReg, NewDef, PredBB); 33479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 33579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Remove PredBB from the PHI node. 33679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx+1); 33779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx); 33879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getNumOperands() == 1) 33979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 34079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 34179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 34279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 34379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// the source operands due to earlier PHI translation. 34479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 34579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 34679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 34779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 34879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap) { 34979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *NewMI = MF.CloneMachineInstr(MI); 35079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 35179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineOperand &MO = NewMI->getOperand(i); 35279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (!MO.isReg()) 35379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 35479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned Reg = MO.getReg(); 35579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) 35679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 35779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MO.isDef()) { 35879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(Reg); 35979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned NewReg = MRI->createVirtualRegister(RC); 36079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(NewReg); 36179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(Reg, NewReg)); 36279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (isDefLiveOut(Reg, TailBB, MRI)) 36311572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng AddSSAUpdateEntry(Reg, NewReg, PredBB); 36479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 36579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 36679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (VI != LocalVRMap.end()) 36779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(VI->second); 36879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 36979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 37079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->insert(PredBB->end(), NewMI); 37179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 37279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 37379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 37479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// blocks, the successors have gained new predecessors. Update the PHI 37579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// instructions in them accordingly. 37675eb53584367098a5625028e22f1ff8e169d0efdEvan Chengvoid 37775eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 37875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 37979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*,8> &Succs) { 38079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 38179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SE = Succs.end(); SI != SE; ++SI) { 38279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *SuccBB = *SI; 38379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 38479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng II != EE; ++II) { 38579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (II->getOpcode() != TargetInstrInfo::PHI) 38679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 38775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Idx = 0; 38879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 38975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 39075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 39175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Idx = i; 39279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 39375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 39475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 39575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 39675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng assert(Idx != 0); 39775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO0 = II->getOperand(Idx); 39875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Reg = MO0.getReg(); 39975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 40075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Folded into the previous BB. 40175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // There could be duplicate phi source entries. FIXME: Should sdisel 40275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // or earlier pass fixed this? 40375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 40475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 40575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 40675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i+1); 40775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i); 40875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 40975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 41075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(Idx+1); 41175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(Idx); 41275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 41375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 41475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (LI != SSAUpdateVals.end()) { 41575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // This register is defined in the tail block. 41679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 41711572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 41811572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng unsigned SrcReg = LI->second[j].second; 41911572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 42011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng II->addOperand(MachineOperand::CreateMBB(SrcBB)); 42179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 42275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } else { 42375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Live in tail block, must also be live in predecessors. 42475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 42575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = TDBBs[j]; 42675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->addOperand(MachineOperand::CreateReg(Reg, false)); 42775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->addOperand(MachineOperand::CreateMBB(SrcBB)); 42875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 42979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 43079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 43179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 43279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 43379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 43415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 43515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// of its predecessors. 43675eb53584367098a5625028e22f1ff8e169d0efdEvan Chengbool 43775eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 4383466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 4393466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> &Copies) { 44015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't try to tail-duplicate single-block loops. 44115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TailBB->isSuccessor(TailBB)) 44215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return false; 44315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 44415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Set the limit on the number of instructions to duplicate, with a default 44515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // of one less than the tail-merge threshold. When optimizing for size, 44615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // duplicate only one, because one branch instruction can be eliminated to 44715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // compensate for the duplication. 44815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson unsigned MaxDuplicateCount; 4493858225afc2a7f1027dce34dc72de5686b636c2dBob Wilson if (!TailBB->empty() && TailBB->back().getDesc().isIndirectBranch()) 45015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If the target has hardware branch prediction that can handle indirect 45115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // branches, duplicating them can often make them predictable when there 45215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // are common paths through the code. The limit needs to be high enough 45315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // to allow undoing the effects of tail merging. 45415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MaxDuplicateCount = 20; 4553858225afc2a7f1027dce34dc72de5686b636c2dBob Wilson else if (MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 4563858225afc2a7f1027dce34dc72de5686b636c2dBob Wilson MaxDuplicateCount = 1; 45715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson else 45815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MaxDuplicateCount = TailDuplicateSize; 45915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 46015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Check the instructions in the block to determine whether tail-duplication 46115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // is invalid or unlikely to be profitable. 462f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson unsigned InstrCount = 0; 46315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool HasCall = false; 46415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::iterator I = TailBB->begin(); 465f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson I != TailBB->end(); ++I) { 46615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Non-duplicable things shouldn't be tail-duplicated. 46715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (I->getDesc().isNotDuplicable()) return false; 46879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Do not duplicate 'return' instructions if this is a pre-regalloc run. 46979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // A return may expand into a lot more instructions (e.g. reload of callee 47079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // saved registers) after PEI. 47179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc && I->getDesc().isReturn()) return false; 47215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate more than the threshold. 473f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson if (InstrCount == MaxDuplicateCount) return false; 47415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remember if we saw a call. 47515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (I->getDesc().isCall()) HasCall = true; 476f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson if (I->getOpcode() != TargetInstrInfo::PHI) 477f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson InstrCount += 1; 47815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 47915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Heuristically, don't tail-duplicate calls if it would expand code size, 48015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // as it's less likely to be worth the extra cost. 481f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson if (InstrCount > 1 && HasCall) 48215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return false; 48315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 48400dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 48575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 48615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Iterate through all the unique predecessors and tail-duplicate this 48715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into them, if possible. Copying the list ahead of time also 48815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // avoids trouble with the predecessor list reallocating. 48915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool Changed = false; 49079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 49179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_end()); 49215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 49315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PE = Preds.end(); PI != PE; ++PI) { 49415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredBB = *PI; 49515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 49615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(TailBB != PredBB && 49715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "Single-block loop should have been rejected earlier!"); 49815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->succ_size() > 1) continue; 49915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 50015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredTBB, *PredFBB; 50115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PredCond; 50215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 50315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 50415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PredCond.empty()) 50515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 50615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // EH edges are ignored by AnalyzeBranch. 50715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->succ_size() != 1) 50815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 50915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate into a fall-through predecessor (at least for now). 51015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 51115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 51215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 51300dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 51415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From Succ: " << *TailBB); 51515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 51675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PredBB); 51775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 51815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove PredBB's unconditional branch. 51915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII->RemoveBranch(*PredBB); 520111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 52115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Clone the contents of TailBB into PredBB. 522111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 5233466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 524111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 52579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 52679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I; 52779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng ++I; 52879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getOpcode() == TargetInstrInfo::PHI) { 529111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // Replace the uses of the def of the PHI with the register coming 530111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // from PredBB. 5313466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos); 53279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 53379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 53479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 53579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap); 536111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 53715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 53875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 5393466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 5403466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(CopyInfos[i].first); 5413466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng TII->copyRegToReg(*PredBB, Loc, CopyInfos[i].first, 5423466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng CopyInfos[i].second, RC,RC); 5433466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng MachineInstr *CopyMI = prior(Loc); 5443466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng Copies.push_back(CopyMI); 54575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 54615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 54715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 54815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Update the CFG. 54915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PredBB->removeSuccessor(PredBB->succ_begin()); 55015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(PredBB->succ_empty() && 55115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "TailDuplicate called on block with multiple successors!"); 55215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 55379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng E = TailBB->succ_end(); I != E; ++I) 55479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->addSuccessor(*I); 55515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 55615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 55715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson ++NumTailDups; 55815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 55915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 56015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If TailBB was duplicated into all its predecessors except for the prior 56115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block, which falls through unconditionally, move the contents of this 56215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into the prior block. 56379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 56415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 56515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PriorCond; 56615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool PriorUnAnalyzable = 56779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true); 56815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // This has to check PrevBB->succ_size() because EH edges are ignored by 56915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // AnalyzeBranch. 57015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PriorUnAnalyzable && PriorCond.empty() && !PriorTBB && 57179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_size() == 1 && PrevBB->succ_size() == 1 && 57215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !TailBB->hasAddressTaken()) { 57300dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 57415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From MBB: " << *TailBB); 57579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc) { 57679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 5773466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 57879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 57979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Process PHI instructions first. 58079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end() && I->getOpcode() == TargetInstrInfo::PHI) { 58179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace the uses of the def of the PHI with the register coming 58279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // from PredBB. 58379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 5843466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos); 58579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getParent()) 58679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 58779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 58879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 58979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Now copy the non-PHI instructions. 59079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 59179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 59279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 59379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 59479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap); 59579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 59679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 59775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 5983466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 5993466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(CopyInfos[i].first); 6003466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng TII->copyRegToReg(*PrevBB, Loc, CopyInfos[i].first, 6013466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng CopyInfos[i].second, RC, RC); 6023466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng MachineInstr *CopyMI = prior(Loc); 6033466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng Copies.push_back(CopyMI); 60475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 60579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 60679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // No PHIs to worry about, just splice the instructions over. 60779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 60879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 60979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->removeSuccessor(PrevBB->succ_begin()); 61079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(PrevBB->succ_empty()); 61179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->transferSuccessors(TailBB); 61275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PrevBB); 61315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 61415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 61515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 61615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return Changed; 61715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 61815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 61915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// RemoveDeadBlock - Remove the specified dead machine basic block from the 62015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// function, updating the CFG. 6212d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonvoid TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 62215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(MBB->pred_empty() && "MBB must be dead!"); 62300dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 62415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 62515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove all successors. 62615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson while (!MBB->succ_empty()) 62715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->removeSuccessor(MBB->succ_end()-1); 62815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 62915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If there are any labels in the basic block, unregister them from 63015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // MachineModuleInfo. 63115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (MMI && !MBB->empty()) { 63215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 63315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson I != E; ++I) { 63415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (I->isLabel()) 63515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // The label ID # is always operand #0, an immediate. 63615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MMI->InvalidateLabel(I->getOperand(0).getImm()); 63715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 63815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 63915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 64015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove the block. 64115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->eraseFromParent(); 64215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 64315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 644