TailDuplication.cpp revision c8b90e22a8f2987126a7e2e841adc8db9776521c
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) : 7290c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson 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]; 25704c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (!Copy->isCopy()) 25804c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen continue; 25904c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned Dst = Copy->getOperand(0).getReg(); 26004c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned Src = Copy->getOperand(1).getReg(); 26104c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); 26204c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (++UI == MRI->use_end()) { 26304c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen // Copy is the only use. Do trivial copy propagation here. 26404c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen MRI->replaceRegWith(Dst, Src); 26504c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen Copy->eraseFromParent(); 2663466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2673466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2683466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng 26975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) 27075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, false); 27115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MadeChange = true; 27215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 27315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 274111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 27515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 27615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 27715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 278111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 279111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng const MachineRegisterInfo *MRI) { 280111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 281111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng UE = MRI->use_end(); UI != UE; ++UI) { 282111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineInstr *UseMI = &*UI; 283111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (UseMI->getParent() != BB) 284111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return true; 285111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 286111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return false; 287111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 288111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 289111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 290111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 291111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (MI->getOperand(i+1).getMBB() == SrcBB) 292111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return i; 293111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return 0; 294111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 295111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 296111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 297111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// SSA update. 29811572babb12d169965c63c47aab9c9fad354e5dfEvan Chengvoid TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 29911572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB) { 30011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 301111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (LI != SSAUpdateVals.end()) 30211572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng LI->second.push_back(std::make_pair(BB, NewReg)); 303111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng else { 304111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng AvailableValsTy Vals; 30511572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng Vals.push_back(std::make_pair(BB, NewReg)); 306111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 307111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVRs.push_back(OrigReg); 308111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 309111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 310111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 31175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 31275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// Remember the source register that's contributed by PredBB and update SSA 31375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// update map. 31479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::ProcessPHI(MachineInstr *MI, 31579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 31679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 31775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 31875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> &Copies) { 31979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned DefReg = MI->getOperand(0).getReg(); 32079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 32179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(SrcOpIdx && "Unable to find matching PHI source?"); 32279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 32375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 32479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 32575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 32675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Insert a copy from source to the end of the block. The def register is the 32775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // available value liveout of the block. 32875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned NewDef = MRI->createVirtualRegister(RC); 32975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Copies.push_back(std::make_pair(NewDef, SrcReg)); 33079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (isDefLiveOut(DefReg, TailBB, MRI)) 33175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng AddSSAUpdateEntry(DefReg, NewDef, PredBB); 33279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 33379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Remove PredBB from the PHI node. 33479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx+1); 33579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx); 33679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getNumOperands() == 1) 33779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 33879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 33979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 34079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 34179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// the source operands due to earlier PHI translation. 34279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 34379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 34479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 34579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 34679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap) { 34730ac0467ced4627a9b84d8a1d3ca5e8706ddad63Jakob Stoklund Olesen MachineInstr *NewMI = TII->duplicate(MI, MF); 34879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 34979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineOperand &MO = NewMI->getOperand(i); 35079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (!MO.isReg()) 35179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 35279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned Reg = MO.getReg(); 353c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 35479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 35579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MO.isDef()) { 35679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(Reg); 35779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned NewReg = MRI->createVirtualRegister(RC); 35879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(NewReg); 35979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(Reg, NewReg)); 36079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (isDefLiveOut(Reg, TailBB, MRI)) 36111572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng AddSSAUpdateEntry(Reg, NewReg, PredBB); 36279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 36379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 36479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (VI != LocalVRMap.end()) 36579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(VI->second); 36679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 36779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 36879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->insert(PredBB->end(), NewMI); 36979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 37079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 37179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 37279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// blocks, the successors have gained new predecessors. Update the PHI 37379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// instructions in them accordingly. 37475eb53584367098a5625028e22f1ff8e169d0efdEvan Chengvoid 37575eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 37675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 37779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*,8> &Succs) { 37879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 37979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SE = Succs.end(); SI != SE; ++SI) { 38079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *SuccBB = *SI; 38179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 38279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng II != EE; ++II) { 383518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!II->isPHI()) 38479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 38575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Idx = 0; 38679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 38775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 38875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 38975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Idx = i; 39079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 39175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 39275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 39375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 39475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng assert(Idx != 0); 39575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO0 = II->getOperand(Idx); 39675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Reg = MO0.getReg(); 39775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 39875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Folded into the previous BB. 39975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // There could be duplicate phi source entries. FIXME: Should sdisel 40075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // or earlier pass fixed this? 40175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 40275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 40375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 40475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i+1); 40575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i); 40675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 40775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 40809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else 40909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 41009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 41109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // If Idx is set, the operands at Idx and Idx+1 must be removed. 41209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // We reuse the location to avoid expensive RemoveOperand calls. 41309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 41475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 41575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (LI != SSAUpdateVals.end()) { 41675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // This register is defined in the tail block. 41779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 41811572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 41911572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng unsigned SrcReg = LI->second[j].second; 42009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 42109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(SrcReg); 42209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 42309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 42409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 42509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 42609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(SrcBB)); 42709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 42879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 42975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } else { 43075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Live in tail block, must also be live in predecessors. 43175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 43275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = TDBBs[j]; 43309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 43409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(Reg); 43509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 43609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 43709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 43809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(Reg, false)); 43909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(SrcBB)); 44009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 44175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 44279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 44309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 44409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx+1); 44509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx); 44609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 44779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 44879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 44979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 45079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 45115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 45215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// of its predecessors. 45375eb53584367098a5625028e22f1ff8e169d0efdEvan Chengbool 45475eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 4553466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 4563466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> &Copies) { 45715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Set the limit on the number of instructions to duplicate, with a default 45815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // of one less than the tail-merge threshold. When optimizing for size, 45915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // duplicate only one, because one branch instruction can be eliminated to 46015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // compensate for the duplication. 46115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson unsigned MaxDuplicateCount; 4628352062e52eed6e50786fdb89f5e601fdcbe0d90Jakob Stoklund Olesen if (TailDuplicateSize.getNumOccurrences() == 0 && 4638352062e52eed6e50786fdb89f5e601fdcbe0d90Jakob Stoklund Olesen MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 464cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = 1; 465cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson else 466cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = TailDuplicateSize; 467cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson 468cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson if (PreRegAlloc) { 469c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng if (TailBB->empty()) 470c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng return false; 471c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng const TargetInstrDesc &TID = TailBB->back().getDesc(); 472c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // Pre-regalloc tail duplication hurts compile time and doesn't help 473c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // much except for indirect branches and returns. 474c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng if (!TID.isIndirectBranch() && !TID.isReturn()) 475cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson return false; 47615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If the target has hardware branch prediction that can handle indirect 47715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // branches, duplicating them can often make them predictable when there 47815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // are common paths through the code. The limit needs to be high enough 479cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson // to allow undoing the effects of tail merging and other optimizations 480cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson // that rearrange the predecessors of the indirect branch. 48115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MaxDuplicateCount = 20; 482cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson } 48315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 484bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson // Don't try to tail-duplicate single-block loops. 485bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson if (TailBB->isSuccessor(TailBB)) 486bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson return false; 487bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson 48815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Check the instructions in the block to determine whether tail-duplication 48915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // is invalid or unlikely to be profitable. 490f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson unsigned InstrCount = 0; 49115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool HasCall = false; 49215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::iterator I = TailBB->begin(); 493f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson I != TailBB->end(); ++I) { 49415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Non-duplicable things shouldn't be tail-duplicated. 49515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (I->getDesc().isNotDuplicable()) return false; 49679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Do not duplicate 'return' instructions if this is a pre-regalloc run. 49779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // A return may expand into a lot more instructions (e.g. reload of callee 49879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // saved registers) after PEI. 49979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc && I->getDesc().isReturn()) return false; 50015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate more than the threshold. 501f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson if (InstrCount == MaxDuplicateCount) return false; 50215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remember if we saw a call. 50315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (I->getDesc().isCall()) HasCall = true; 504cbe1e31732c5d4fb1277195e76b9b42c115396aaDevang Patel if (!I->isPHI() && !I->isDebugValue()) 505f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson InstrCount += 1; 50615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 507c8b90e22a8f2987126a7e2e841adc8db9776521cEvan Cheng // Don't tail-duplicate calls before register allocation. Calls presents a 508c8b90e22a8f2987126a7e2e841adc8db9776521cEvan Cheng // barrier to register allocation so duplicating them may end up increasing 509c8b90e22a8f2987126a7e2e841adc8db9776521cEvan Cheng // spills. 510c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng if (InstrCount > 1 && (PreRegAlloc && HasCall)) 51115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return false; 51215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 51300dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 51475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 51515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Iterate through all the unique predecessors and tail-duplicate this 51615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into them, if possible. Copying the list ahead of time also 51715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // avoids trouble with the predecessor list reallocating. 51815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool Changed = false; 51979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 52079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_end()); 52115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 52215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PE = Preds.end(); PI != PE; ++PI) { 52315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredBB = *PI; 52415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 52515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(TailBB != PredBB && 52615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "Single-block loop should have been rejected earlier!"); 52715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->succ_size() > 1) continue; 52815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 52915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredTBB, *PredFBB; 53015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PredCond; 53115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 53215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 53315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PredCond.empty()) 53415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 53515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // EH edges are ignored by AnalyzeBranch. 53615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->succ_size() != 1) 53715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 53815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate into a fall-through predecessor (at least for now). 53915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 54015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 54115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 54200dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 54315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From Succ: " << *TailBB); 54415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 54575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PredBB); 54675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 54715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove PredBB's unconditional branch. 54815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII->RemoveBranch(*PredBB); 549111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 55015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Clone the contents of TailBB into PredBB. 551111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 5523466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 553111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 55479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 55579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I; 55679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng ++I; 557518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isPHI()) { 558111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // Replace the uses of the def of the PHI with the register coming 559111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // from PredBB. 5603466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos); 56179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 56279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 56379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 56479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap); 565111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 56615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 56775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 5683466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 5691e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 5701e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 5711e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first).addReg(CopyInfos[i].second)); 57275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 57315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 57415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 57515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Update the CFG. 57615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PredBB->removeSuccessor(PredBB->succ_begin()); 57715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(PredBB->succ_empty() && 57815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "TailDuplicate called on block with multiple successors!"); 57915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 58079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng E = TailBB->succ_end(); I != E; ++I) 58179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->addSuccessor(*I); 58215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 58315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 58415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson ++NumTailDups; 58515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 58615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 58715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If TailBB was duplicated into all its predecessors except for the prior 58815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block, which falls through unconditionally, move the contents of this 58915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into the prior block. 59079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 59115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 59215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PriorCond; 59315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool PriorUnAnalyzable = 59479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true); 59515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // This has to check PrevBB->succ_size() because EH edges are ignored by 59615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // AnalyzeBranch. 59715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PriorUnAnalyzable && PriorCond.empty() && !PriorTBB && 59879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_size() == 1 && PrevBB->succ_size() == 1 && 59915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !TailBB->hasAddressTaken()) { 60000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 60115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From MBB: " << *TailBB); 60279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc) { 60379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 6043466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 60579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 60679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Process PHI instructions first. 607518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (I != TailBB->end() && I->isPHI()) { 60879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace the uses of the def of the PHI with the register coming 60979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // from PredBB. 61079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 6113466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos); 61279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getParent()) 61379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 61479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 61579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 61679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Now copy the non-PHI instructions. 61779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 61879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 61979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 62079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 62179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap); 62279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 62379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 62475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 6253466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 6261e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 6271e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 6281e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first) 6291e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen .addReg(CopyInfos[i].second)); 63075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 63179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 63279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // No PHIs to worry about, just splice the instructions over. 63379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 63479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 63579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->removeSuccessor(PrevBB->succ_begin()); 63679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(PrevBB->succ_empty()); 63779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->transferSuccessors(TailBB); 63875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PrevBB); 63915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 64015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 64115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 64215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return Changed; 64315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 64415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 64515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// RemoveDeadBlock - Remove the specified dead machine basic block from the 64615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// function, updating the CFG. 6472d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonvoid TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 64815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(MBB->pred_empty() && "MBB must be dead!"); 64900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 65015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 65115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove all successors. 65215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson while (!MBB->succ_empty()) 65315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->removeSuccessor(MBB->succ_end()-1); 65415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 65515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove the block. 65615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->eraseFromParent(); 65715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 65815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 659