TailDuplication.cpp revision 1e1098c6f39590e1e74e5cb3c2a1652d8f3cb16a
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"); 3715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 3815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// Heuristic for tail duplication. 3915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonstatic cl::opt<unsigned> 4015acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonTailDuplicateSize("tail-dup-size", 4115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::desc("Maximum instructions to consider tail duplicating"), 4215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::init(2), cl::Hidden); 4315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4475eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<bool> 4575eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupVerify("tail-dup-verify", 4675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::desc("Verify sanity of PHI instructions during taildup"), 4775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::init(false), cl::Hidden); 4875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 4975eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<unsigned> 5075eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 5175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5211572babb12d169965c63c47aab9c9fad354e5dfEvan Chengtypedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 53111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 5415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonnamespace { 552d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson /// TailDuplicatePass - Perform tail duplication. 562d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson class TailDuplicatePass : public MachineFunctionPass { 5779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng bool PreRegAlloc; 5815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson const TargetInstrInfo *TII; 5915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineModuleInfo *MMI; 60111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineRegisterInfo *MRI; 61111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 62111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 63111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SmallVector<unsigned, 16> SSAUpdateVRs; 64111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 65111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 66111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // source virtual registers. 67111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 6815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 6915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson public: 7015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson static char ID; 7179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng explicit TailDuplicatePass(bool PreRA) : 7279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunctionPass(&ID), PreRegAlloc(PreRA) {} 7315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual bool runOnMachineFunction(MachineFunction &MF); 7515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual const char *getPassName() const { return "Tail Duplication"; } 7615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson private: 7811572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 7911572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB); 8079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 8179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 8275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 8375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> &Copies); 8479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void DuplicateInstruction(MachineInstr *MI, 8579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 8679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 8779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 8879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap); 8975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 9075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 9175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> &Succs); 9215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool TailDuplicateBlocks(MachineFunction &MF); 9375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 943466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 953466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> &Copies); 9615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson void RemoveDeadBlock(MachineBasicBlock *MBB); 9715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson }; 9815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 992d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson char TailDuplicatePass::ID = 0; 10015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 10115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 10279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan ChengFunctionPass *llvm::createTailDuplicatePass(bool PreRegAlloc) { 10379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng return new TailDuplicatePass(PreRegAlloc); 10415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 10515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1062d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 10715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII = MF.getTarget().getInstrInfo(); 108111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MRI = &MF.getRegInfo(); 10915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 11015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 11115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 112057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen while (TailDuplicateBlocks(MF)) 113057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen MadeChange = true; 11415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 11515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 11615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 11715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 11875eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 11975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 12075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *MBB = I; 12175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 12275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->pred_end()); 12375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator MI = MBB->begin(); 12475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (MI != MBB->end()) { 125518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!MI->isPHI()) 12675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 12775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 12875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng PE = Preds.end(); PI != PE; ++PI) { 12975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PredBB = *PI; 13075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool Found = false; 13175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 13275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 13375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB == PredBB) { 13475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Found = true; 13575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 13675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 13775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 13875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!Found) { 13900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 14000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " missing input from predecessor BB#" 14175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PredBB->getNumber() << '\n'; 14275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 14375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 14475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 14575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 14675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 14775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 14875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (CheckExtra && !Preds.count(PHIBB)) { 14975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // This is not a hard error. 15000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 15175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << ": " << *MI; 15200dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " extra input from predecessor BB#" 15375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PHIBB->getNumber() << '\n'; 15475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 15575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB->getNumber() < 0) { 15600dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 15700dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 15875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 15975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++MI; 16275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng} 16575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 16615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// TailDuplicateBlocks - Look for small blocks that are unconditionally 16715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// branched to and do not fall through. Tail-duplicate their instructions 16815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// into their predecessors to eliminate (dynamic) branches. 1692d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 17015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 17115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 17275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) { 17300dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 17475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, true); 17575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 17675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 17775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineInstr*, 8> NewPHIs; 17875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 17975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 18015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 18115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *MBB = I++; 18215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 18375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (NumTails == TailDupLimit) 18475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 18575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 18615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Only duplicate blocks that end with unconditional branches. 18715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (MBB->canFallThrough()) 18815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 18915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 19075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Save the successors list. 19175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 19275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->succ_end()); 19375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 19475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> TDBBs; 1953466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> Copies; 1963466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng if (TailDuplicate(MBB, MF, TDBBs, Copies)) { 19775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++NumTails; 19875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 19975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // TailBB's immediate successors are now successors of those predecessors 20075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // which duplicated TailBB. Add the predecessors as sources to the PHI 20175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // instructions. 20275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool isDead = MBB->pred_empty(); 20375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc) 20475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 20575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 20675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // If it is dead, remove it. 20775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 20875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng NumInstrDups -= MBB->size(); 20975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng RemoveDeadBlock(MBB); 21075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++NumDeadBlocks; 21175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 21275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 21375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Update SSA form. 21475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!SSAUpdateVRs.empty()) { 21575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 21675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned VReg = SSAUpdateVRs[i]; 21775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.Initialize(VReg); 21875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 21975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // If the original definition is still around, add it as an available 22075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // value. 22175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineInstr *DefMI = MRI->getVRegDef(VReg); 22275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *DefBB = 0; 22375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (DefMI) { 22475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DefBB = DefMI->getParent(); 22575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.AddAvailableValue(DefBB, VReg); 22675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 22775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 22875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Add the new vregs as available values. 22975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI = 23075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVals.find(VReg); 23175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 23275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 23375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned SrcReg = LI->second[j].second; 23475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 23575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 23675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 23775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Rewrite uses that are outside of the original def's block. 23875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 23975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (UI != MRI->use_end()) { 24075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &UseMO = UI.getOperand(); 24175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineInstr *UseMI = &*UI; 24275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++UI; 24375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (UseMI->getParent() == DefBB) 24475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng continue; 24575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.RewriteUse(UseMO); 24675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 24775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 24815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 24975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVRs.clear(); 25075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVals.clear(); 25175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 25275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 253bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson // Eliminate some of the copies inserted by tail duplication to maintain 2543466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng // SSA form. 2553466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 2563466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng MachineInstr *Copy = Copies[i]; 2573466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng unsigned Src, Dst, SrcSR, DstSR; 2583466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng if (TII->isMoveInstr(*Copy, Src, Dst, SrcSR, DstSR)) { 2593466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); 2603466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng if (++UI == MRI->use_end()) { 2613466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng // Copy is the only use. Do trivial copy propagation here. 2623466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng MRI->replaceRegWith(Dst, Src); 2633466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng Copy->eraseFromParent(); 2643466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2653466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2663466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2673466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng 26875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) 26975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, false); 27015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MadeChange = true; 27115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 27215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 273111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 27415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 27515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 27615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 277111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 278111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng const MachineRegisterInfo *MRI) { 279111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 280111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng UE = MRI->use_end(); UI != UE; ++UI) { 281111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineInstr *UseMI = &*UI; 282111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (UseMI->getParent() != BB) 283111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return true; 284111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 285111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return false; 286111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 287111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 288111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 289111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 290111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (MI->getOperand(i+1).getMBB() == SrcBB) 291111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return i; 292111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return 0; 293111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 294111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 295111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 296111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// SSA update. 29711572babb12d169965c63c47aab9c9fad354e5dfEvan Chengvoid TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 29811572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB) { 29911572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 300111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (LI != SSAUpdateVals.end()) 30111572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng LI->second.push_back(std::make_pair(BB, NewReg)); 302111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng else { 303111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng AvailableValsTy Vals; 30411572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng Vals.push_back(std::make_pair(BB, NewReg)); 305111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 306111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVRs.push_back(OrigReg); 307111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 308111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 309111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 31075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 31175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// Remember the source register that's contributed by PredBB and update SSA 31275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// update map. 31379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::ProcessPHI(MachineInstr *MI, 31479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 31579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 31675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 31775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> &Copies) { 31879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned DefReg = MI->getOperand(0).getReg(); 31979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 32079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(SrcOpIdx && "Unable to find matching PHI source?"); 32179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 32275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 32379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 32475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 32575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Insert a copy from source to the end of the block. The def register is the 32675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // available value liveout of the block. 32775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned NewDef = MRI->createVirtualRegister(RC); 32875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Copies.push_back(std::make_pair(NewDef, SrcReg)); 32979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (isDefLiveOut(DefReg, TailBB, MRI)) 33075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng AddSSAUpdateEntry(DefReg, NewDef, PredBB); 33179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 33279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Remove PredBB from the PHI node. 33379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx+1); 33479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx); 33579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getNumOperands() == 1) 33679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 33779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 33879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 33979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 34079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// the source operands due to earlier PHI translation. 34179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 34279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 34379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 34479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 34579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap) { 34630ac0467ced4627a9b84d8a1d3ca5e8706ddad63Jakob Stoklund Olesen MachineInstr *NewMI = TII->duplicate(MI, MF); 34779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 34879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineOperand &MO = NewMI->getOperand(i); 34979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (!MO.isReg()) 35079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 35179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned Reg = MO.getReg(); 35279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) 35379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 35479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MO.isDef()) { 35579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(Reg); 35679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned NewReg = MRI->createVirtualRegister(RC); 35779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(NewReg); 35879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(Reg, NewReg)); 35979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (isDefLiveOut(Reg, TailBB, MRI)) 36011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng AddSSAUpdateEntry(Reg, NewReg, PredBB); 36179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 36279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 36379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (VI != LocalVRMap.end()) 36479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(VI->second); 36579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 36679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 36779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->insert(PredBB->end(), NewMI); 36879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 36979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 37079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 37179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// blocks, the successors have gained new predecessors. Update the PHI 37279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// instructions in them accordingly. 37375eb53584367098a5625028e22f1ff8e169d0efdEvan Chengvoid 37475eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 37575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 37679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*,8> &Succs) { 37779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 37879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SE = Succs.end(); SI != SE; ++SI) { 37979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *SuccBB = *SI; 38079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 38179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng II != EE; ++II) { 382518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!II->isPHI()) 38379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 38475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Idx = 0; 38579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 38675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 38775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 38875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Idx = i; 38979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 39075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 39175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 39275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 39375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng assert(Idx != 0); 39475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO0 = II->getOperand(Idx); 39575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Reg = MO0.getReg(); 39675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 39775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Folded into the previous BB. 39875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // There could be duplicate phi source entries. FIXME: Should sdisel 39975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // or earlier pass fixed this? 40075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 40175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 40275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 40375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i+1); 40475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i); 40575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 40675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 40709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else 40809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 40909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 41009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // If Idx is set, the operands at Idx and Idx+1 must be removed. 41109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // We reuse the location to avoid expensive RemoveOperand calls. 41209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 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; 41909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 42009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(SrcReg); 42109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 42209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 42309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 42409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 42509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(SrcBB)); 42609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 42779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 42875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } else { 42975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Live in tail block, must also be live in predecessors. 43075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 43175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = TDBBs[j]; 43209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 43309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(Reg); 43409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 43509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 43609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 43709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(Reg, false)); 43809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(SrcBB)); 43909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 44075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 44179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 44209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 44309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx+1); 44409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx); 44509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 44679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 44779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 44879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 44979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 45015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 45115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// of its predecessors. 45275eb53584367098a5625028e22f1ff8e169d0efdEvan Chengbool 45375eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 4543466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 4553466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> &Copies) { 45615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Set the limit on the number of instructions to duplicate, with a default 45715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // of one less than the tail-merge threshold. When optimizing for size, 45815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // duplicate only one, because one branch instruction can be eliminated to 45915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // compensate for the duplication. 46015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson unsigned MaxDuplicateCount; 461cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson if (MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 462cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = 1; 463cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson else 464cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = TailDuplicateSize; 465cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson 466cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson if (PreRegAlloc) { 467cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson // Pre-regalloc tail duplication hurts compile time and doesn't help 468cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson // much except for indirect branches. 469cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson if (TailBB->empty() || !TailBB->back().getDesc().isIndirectBranch()) 470cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson return false; 47115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If the target has hardware branch prediction that can handle indirect 47215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // branches, duplicating them can often make them predictable when there 47315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // are common paths through the code. The limit needs to be high enough 474cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson // to allow undoing the effects of tail merging and other optimizations 475cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson // that rearrange the predecessors of the indirect branch. 47615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MaxDuplicateCount = 20; 477cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson } 47815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 479bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson // Don't try to tail-duplicate single-block loops. 480bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson if (TailBB->isSuccessor(TailBB)) 481bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson return false; 482bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson 48315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Check the instructions in the block to determine whether tail-duplication 48415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // is invalid or unlikely to be profitable. 485f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson unsigned InstrCount = 0; 48615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool HasCall = false; 48715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::iterator I = TailBB->begin(); 488f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson I != TailBB->end(); ++I) { 48915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Non-duplicable things shouldn't be tail-duplicated. 49015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (I->getDesc().isNotDuplicable()) return false; 49179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Do not duplicate 'return' instructions if this is a pre-regalloc run. 49279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // A return may expand into a lot more instructions (e.g. reload of callee 49379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // saved registers) after PEI. 49479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc && I->getDesc().isReturn()) return false; 49515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate more than the threshold. 496f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson if (InstrCount == MaxDuplicateCount) return false; 49715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remember if we saw a call. 49815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (I->getDesc().isCall()) HasCall = true; 499cbe1e31732c5d4fb1277195e76b9b42c115396aaDevang Patel if (!I->isPHI() && !I->isDebugValue()) 500f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson InstrCount += 1; 50115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 50215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Heuristically, don't tail-duplicate calls if it would expand code size, 50315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // as it's less likely to be worth the extra cost. 504f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson if (InstrCount > 1 && HasCall) 50515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return false; 50615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 50700dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 50875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 50915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Iterate through all the unique predecessors and tail-duplicate this 51015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into them, if possible. Copying the list ahead of time also 51115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // avoids trouble with the predecessor list reallocating. 51215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool Changed = false; 51379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 51479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_end()); 51515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 51615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PE = Preds.end(); PI != PE; ++PI) { 51715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredBB = *PI; 51815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 51915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(TailBB != PredBB && 52015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "Single-block loop should have been rejected earlier!"); 52115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->succ_size() > 1) continue; 52215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 52315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredTBB, *PredFBB; 52415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PredCond; 52515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 52615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 52715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PredCond.empty()) 52815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 52915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // EH edges are ignored by AnalyzeBranch. 53015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->succ_size() != 1) 53115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 53215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate into a fall-through predecessor (at least for now). 53315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 53415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 53515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 53600dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 53715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From Succ: " << *TailBB); 53815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 53975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PredBB); 54075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 54115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove PredBB's unconditional branch. 54215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII->RemoveBranch(*PredBB); 543111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 54415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Clone the contents of TailBB into PredBB. 545111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 5463466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 547111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 54879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 54979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I; 55079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng ++I; 551518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isPHI()) { 552111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // Replace the uses of the def of the PHI with the register coming 553111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // from PredBB. 5543466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos); 55579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 55679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 55779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 55879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap); 559111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 56015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 56175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 5623466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 5631e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 5641e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 5651e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first).addReg(CopyInfos[i].second)); 56675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 56715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 56815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 56915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Update the CFG. 57015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PredBB->removeSuccessor(PredBB->succ_begin()); 57115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(PredBB->succ_empty() && 57215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "TailDuplicate called on block with multiple successors!"); 57315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 57479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng E = TailBB->succ_end(); I != E; ++I) 57579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->addSuccessor(*I); 57615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 57715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 57815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson ++NumTailDups; 57915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 58015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 58115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If TailBB was duplicated into all its predecessors except for the prior 58215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block, which falls through unconditionally, move the contents of this 58315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into the prior block. 58479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 58515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 58615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PriorCond; 58715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool PriorUnAnalyzable = 58879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true); 58915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // This has to check PrevBB->succ_size() because EH edges are ignored by 59015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // AnalyzeBranch. 59115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PriorUnAnalyzable && PriorCond.empty() && !PriorTBB && 59279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_size() == 1 && PrevBB->succ_size() == 1 && 59315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !TailBB->hasAddressTaken()) { 59400dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 59515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From MBB: " << *TailBB); 59679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc) { 59779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 5983466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 59979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 60079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Process PHI instructions first. 601518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (I != TailBB->end() && I->isPHI()) { 60279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace the uses of the def of the PHI with the register coming 60379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // from PredBB. 60479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 6053466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos); 60679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getParent()) 60779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 60879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 60979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 61079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Now copy the non-PHI instructions. 61179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 61279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 61379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 61479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 61579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap); 61679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 61779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 61875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 6193466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 6201e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 6211e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 6221e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first) 6231e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen .addReg(CopyInfos[i].second)); 62475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 62579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 62679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // No PHIs to worry about, just splice the instructions over. 62779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 62879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 62979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->removeSuccessor(PrevBB->succ_begin()); 63079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(PrevBB->succ_empty()); 63179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->transferSuccessors(TailBB); 63275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PrevBB); 63315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 63415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 63515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 63615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return Changed; 63715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 63815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 63915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// RemoveDeadBlock - Remove the specified dead machine basic block from the 64015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// function, updating the CFG. 6412d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonvoid TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 64215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(MBB->pred_empty() && "MBB must be dead!"); 64300dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 64415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 64515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove all successors. 64615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson while (!MBB->succ_empty()) 64715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->removeSuccessor(MBB->succ_end()-1); 64815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 64915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove the block. 65015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->eraseFromParent(); 65115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 65215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 653