TailDuplication.cpp revision db3983bd762a53f197f6c8a6de401974f39f4789
115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson//===-- TailDuplication.cpp - Duplicate blocks into predecessors' tails ---===// 215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// The LLVM Compiler Infrastructure 415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// This file is distributed under the University of Illinois Open Source 615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// License. See LICENSE.TXT for details. 715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson//===----------------------------------------------------------------------===// 915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 1015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// This pass duplicates basic blocks ending in unconditional branches into 1115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// the tails of their predecessors. 1215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// 1315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson//===----------------------------------------------------------------------===// 1415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#define DEBUG_TYPE "tailduplication" 1615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Function.h" 1715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/CodeGen/Passes.h" 1815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/CodeGen/MachineModuleInfo.h" 1915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/CodeGen/MachineFunctionPass.h" 201e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBuilder.h" 21111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 22111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng#include "llvm/CodeGen/MachineSSAUpdater.h" 2315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Target/TargetInstrInfo.h" 2415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/CommandLine.h" 2515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/Debug.h" 2675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng#include "llvm/Support/ErrorHandling.h" 2715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/Support/raw_ostream.h" 2815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/SmallSet.h" 2915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/SetVector.h" 3015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson#include "llvm/ADT/Statistic.h" 3115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonusing namespace llvm; 3215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 3375eb53584367098a5625028e22f1ff8e169d0efdEvan ChengSTATISTIC(NumTails , "Number of tails duplicated"); 3415acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumTailDups , "Number of tail duplicated blocks"); 3515acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 3615acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 370cdca089b289845664d660f0b285499800822919Rafael EspindolaSTATISTIC(NumAddedPHIs , "Number of phis added"); 3815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 3915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson// Heuristic for tail duplication. 4015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonstatic cl::opt<unsigned> 4115acadde5f87703da5f36721a19c09a7e3f97f53Bob WilsonTailDuplicateSize("tail-dup-size", 4215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::desc("Maximum instructions to consider tail duplicating"), 4315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson cl::init(2), cl::Hidden); 4415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4575eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<bool> 4675eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupVerify("tail-dup-verify", 4775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::desc("Verify sanity of PHI instructions during taildup"), 4875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng cl::init(false), cl::Hidden); 4975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5075eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic cl::opt<unsigned> 5175eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden); 5275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 5311572babb12d169965c63c47aab9c9fad354e5dfEvan Chengtypedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy; 54111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 5515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonnamespace { 562d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson /// TailDuplicatePass - Perform tail duplication. 572d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson class TailDuplicatePass : public MachineFunctionPass { 5879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng bool PreRegAlloc; 5915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson const TargetInstrInfo *TII; 6015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineModuleInfo *MMI; 61111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineRegisterInfo *MRI; 62111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 63111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVRs - A list of virtual registers for which to update SSA form. 64111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SmallVector<unsigned, 16> SSAUpdateVRs; 65111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 66111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of 67111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // source virtual registers. 68111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, AvailableValsTy> SSAUpdateVals; 6915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson public: 7115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson static char ID; 7279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng explicit TailDuplicatePass(bool PreRA) : 7390c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson MachineFunctionPass(ID), PreRegAlloc(PreRA) {} 7415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual bool runOnMachineFunction(MachineFunction &MF); 7615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson virtual const char *getPassName() const { return "Tail Duplication"; } 7715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 7815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson private: 7911572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 8011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB); 8179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB, 8279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 8375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 840f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 85689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola const DenseSet<unsigned> &UsedByPhi, 86689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola bool Remove); 8779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng void DuplicateInstruction(MachineInstr *MI, 8879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 8979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 9079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 910f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 920f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi); 9375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 9475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 9575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> &Succs); 9615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool TailDuplicateBlocks(MachineFunction &MF); 9754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola bool shouldTailDuplicate(const MachineFunction &MF, 9854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola MachineBasicBlock &TailBB); 9975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 1003466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 1013466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> &Copies); 10215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson void RemoveDeadBlock(MachineBasicBlock *MBB); 10315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson }; 10415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1052d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilson char TailDuplicatePass::ID = 0; 10615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 10715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 10879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan ChengFunctionPass *llvm::createTailDuplicatePass(bool PreRegAlloc) { 10979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng return new TailDuplicatePass(PreRegAlloc); 11015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 11115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 1122d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::runOnMachineFunction(MachineFunction &MF) { 11315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII = MF.getTarget().getInstrInfo(); 114111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MRI = &MF.getRegInfo(); 11515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 11615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 11715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 118057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen while (TailDuplicateBlocks(MF)) 119057d53993c8f5ae3b5d8b5357c8c1ec6cc6d63eeJakob Stoklund Olesen MadeChange = true; 12015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 12115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 12215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 12315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 12475eb53584367098a5625028e22f1ff8e169d0efdEvan Chengstatic void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 12575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 12675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *MBB = I; 12775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(), 12875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->pred_end()); 12975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator MI = MBB->begin(); 13075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (MI != MBB->end()) { 131518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!MI->isPHI()) 13275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 13375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 13475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng PE = Preds.end(); PI != PE; ++PI) { 13575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PredBB = *PI; 13675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool Found = false; 13775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 13875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 13975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB == PredBB) { 14075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Found = true; 14175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 14275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 14375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 14475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!Found) { 14500dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 14600dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " missing input from predecessor BB#" 14775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PredBB->getNumber() << '\n'; 14875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 14975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 15075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 15175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 15275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 15375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB(); 15475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (CheckExtra && !Preds.count(PHIBB)) { 15500dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() 15675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << ": " << *MI; 15700dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " extra input from predecessor BB#" 15875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng << PHIBB->getNumber() << '\n'; 159d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola llvm_unreachable(0); 16075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PHIBB->getNumber() < 0) { 16200dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 16300dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 16475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng llvm_unreachable(0); 16575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++MI; 16875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 16975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 17075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng} 17175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 17215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// TailDuplicateBlocks - Look for small blocks that are unconditionally 17315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// branched to and do not fall through. Tail-duplicate their instructions 17415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// into their predecessors to eliminate (dynamic) branches. 1752d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonbool TailDuplicatePass::TailDuplicateBlocks(MachineFunction &MF) { 17615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool MadeChange = false; 17715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 17875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) { 17900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 18075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, true); 18175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 18275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 18375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineInstr*, 8> NewPHIs; 18475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 18575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 18615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 18715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *MBB = I++; 18815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 18975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (NumTails == TailDupLimit) 19075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng break; 19175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 19275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Save the successors list. 19375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(), 19475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MBB->succ_end()); 19575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 19675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> TDBBs; 1973466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<MachineInstr*, 16> Copies; 1983466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng if (TailDuplicate(MBB, MF, TDBBs, Copies)) { 19975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++NumTails; 20075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 20175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // TailBB's immediate successors are now successors of those predecessors 20275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // which duplicated TailBB. Add the predecessors as sources to the PHI 20375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // instructions. 20475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng bool isDead = MBB->pred_empty(); 20575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc) 20675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 20775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 20875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // If it is dead, remove it. 20975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 21075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng NumInstrDups -= MBB->size(); 21175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng RemoveDeadBlock(MBB); 21275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++NumDeadBlocks; 21375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 21475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 21575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Update SSA form. 21675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (!SSAUpdateVRs.empty()) { 21775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 21875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned VReg = SSAUpdateVRs[i]; 21975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.Initialize(VReg); 22075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 22175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // If the original definition is still around, add it as an available 22275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // value. 22375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineInstr *DefMI = MRI->getVRegDef(VReg); 22475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *DefBB = 0; 22575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (DefMI) { 22675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DefBB = DefMI->getParent(); 22775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.AddAvailableValue(DefBB, VReg); 22875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 22975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 23075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Add the new vregs as available values. 23175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI = 23275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVals.find(VReg); 23375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 23475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 23575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned SrcReg = LI->second[j].second; 23675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 23775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 23875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 23975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Rewrite uses that are outside of the original def's block. 24075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 24175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng while (UI != MRI->use_end()) { 24275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &UseMO = UI.getOperand(); 24375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineInstr *UseMI = &*UI; 24475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng ++UI; 245db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola if (UseMI->isDebugValue()) { 246db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola // SSAUpdate can replace the use with an undef. That creates 247db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola // a debug instruction that is a kill. 248db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola // FIXME: Should it SSAUpdate job to delete debug instructions 249db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola // instead of replacing the use with undef? 250db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola UseMI->eraseFromParent(); 251db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola continue; 252db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola } 253c2e9a50dfb523964bd9d7598ee27b37669f9a5b8Rafael Espindola if (UseMI->getParent() == DefBB && !UseMI->isPHI()) 25475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng continue; 25575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdate.RewriteUse(UseMO); 25675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 25775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 25815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 25975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVRs.clear(); 26075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SSAUpdateVals.clear(); 26175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 26275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 263bfdcf3bd49f50050fe98523f882b2241d2752fb4Bob Wilson // Eliminate some of the copies inserted by tail duplication to maintain 2643466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng // SSA form. 2653466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 2663466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng MachineInstr *Copy = Copies[i]; 26704c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (!Copy->isCopy()) 26804c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen continue; 26904c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned Dst = Copy->getOperand(0).getReg(); 27004c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned Src = Copy->getOperand(1).getReg(); 27104c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src); 27204c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (++UI == MRI->use_end()) { 27304c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen // Copy is the only use. Do trivial copy propagation here. 27404c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen MRI->replaceRegWith(Dst, Src); 27504c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen Copy->eraseFromParent(); 2763466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2773466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng } 2783466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng 27975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (PreRegAlloc && TailDupVerify) 28075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng VerifyPHIs(MF, false); 28115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MadeChange = true; 28215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 28315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 284d69f85eb416c08e5f803bffccd974745be3d1b2eRafael Espindola NumAddedPHIs += NewPHIs.size(); 285111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 28615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return MadeChange; 28715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 28815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 289111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 290111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng const MachineRegisterInfo *MRI) { 291111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 292111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng UE = MRI->use_end(); UI != UE; ++UI) { 293111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineInstr *UseMI = &*UI; 294db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola if (UseMI->isDebugValue()) 295db3983bd762a53f197f6c8a6de401974f39f4789Rafael Espindola continue; 296111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (UseMI->getParent() != BB) 297111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return true; 298111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 299111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return false; 300111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 301111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 302111e7629cc84dad39d6b546871cdec3740b22781Evan Chengstatic unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 303111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 304111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (MI->getOperand(i+1).getMBB() == SrcBB) 305111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return i; 306111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng return 0; 307111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 308111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 3090f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 3100f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// Remember which registers are used by phis in this block. This is 3110f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// used to determine which registers are liveout while modifying the 3120f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola// block (which is why we need to copy the information). 3130f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindolastatic void getRegsUsedByPHIs(const MachineBasicBlock &BB, 31433b465877255cc75241216817247c61374958a36Rafael Espindola DenseSet<unsigned> *UsedByPhi) { 3150f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola for(MachineBasicBlock::const_iterator I = BB.begin(), E = BB.end(); 3160f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola I != E; ++I) { 3170f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const MachineInstr &MI = *I; 3180f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (!MI.isPHI()) 3190f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola break; 3200f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 3210f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola unsigned SrcReg = MI.getOperand(i).getReg(); 3220f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola UsedByPhi->insert(SrcReg); 3230f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3240f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola } 3250f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola} 3260f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola 327111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for 328111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng/// SSA update. 32911572babb12d169965c63c47aab9c9fad354e5dfEvan Chengvoid TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 33011572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *BB) { 33111572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg); 332111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng if (LI != SSAUpdateVals.end()) 33311572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng LI->second.push_back(std::make_pair(BB, NewReg)); 334111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng else { 335111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng AvailableValsTy Vals; 33611572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng Vals.push_back(std::make_pair(BB, NewReg)); 337111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 338111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng SSAUpdateVRs.push_back(OrigReg); 339111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 340111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng} 341111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 34275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB. 34375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// Remember the source register that's contributed by PredBB and update SSA 34475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng/// update map. 34579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::ProcessPHI(MachineInstr *MI, 34679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 34779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 34875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned, unsigned> &LocalVRMap, 3490f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> &Copies, 35033b465877255cc75241216817247c61374958a36Rafael Espindola const DenseSet<unsigned> &RegsUsedByPhi, 351689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola bool Remove) { 35279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned DefReg = MI->getOperand(0).getReg(); 35379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 35479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(SrcOpIdx && "Unable to find matching PHI source?"); 35579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 35675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 35779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(DefReg, SrcReg)); 35875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 35975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Insert a copy from source to the end of the block. The def register is the 36075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // available value liveout of the block. 36175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned NewDef = MRI->createVirtualRegister(RC); 36275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Copies.push_back(std::make_pair(NewDef, SrcReg)); 3630f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) 36475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng AddSSAUpdateEntry(DefReg, NewDef, PredBB); 36579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 366689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Remove) 367689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return; 368689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 36979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Remove PredBB from the PHI node. 37079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx+1); 37179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->RemoveOperand(SrcOpIdx); 37279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getNumOperands() == 1) 37379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 37479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 37579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 37679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update 37779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// the source operands due to earlier PHI translation. 37879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Chengvoid TailDuplicatePass::DuplicateInstruction(MachineInstr *MI, 37979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *TailBB, 38079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PredBB, 38179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineFunction &MF, 3820f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseMap<unsigned, unsigned> &LocalVRMap, 3830f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola const DenseSet<unsigned> &UsedByPhi) { 38430ac0467ced4627a9b84d8a1d3ca5e8706ddad63Jakob Stoklund Olesen MachineInstr *NewMI = TII->duplicate(MI, MF); 38579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 38679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineOperand &MO = NewMI->getOperand(i); 38779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (!MO.isReg()) 38879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 38979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned Reg = MO.getReg(); 390c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 39179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng continue; 39279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MO.isDef()) { 39379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng const TargetRegisterClass *RC = MRI->getRegClass(Reg); 39479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng unsigned NewReg = MRI->createVirtualRegister(RC); 39579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(NewReg); 39679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng LocalVRMap.insert(std::make_pair(Reg, NewReg)); 3970f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) 39811572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng AddSSAUpdateEntry(Reg, NewReg, PredBB); 39979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 40079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg); 40179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (VI != LocalVRMap.end()) 40279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MO.setReg(VI->second); 40379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 40479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 40579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->insert(PredBB->end(), NewMI); 40679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 40779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 40879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor 40979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// blocks, the successors have gained new predecessors. Update the PHI 41079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng/// instructions in them accordingly. 41175eb53584367098a5625028e22f1ff8e169d0efdEvan Chengvoid 41275eb53584367098a5625028e22f1ff8e169d0efdEvan ChengTailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, 41375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng SmallVector<MachineBasicBlock*, 8> &TDBBs, 41479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*,8> &Succs) { 41579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(), 41679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SE = Succs.end(); SI != SE; ++SI) { 41779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *SuccBB = *SI; 41879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 41979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng II != EE; ++II) { 420518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!II->isPHI()) 42179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 42275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Idx = 0; 42379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 42475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 42575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 42675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng Idx = i; 42779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng break; 42875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 42975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 43075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 43175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng assert(Idx != 0); 43275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO0 = II->getOperand(Idx); 43375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng unsigned Reg = MO0.getReg(); 43475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (isDead) { 43575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Folded into the previous BB. 43675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // There could be duplicate phi source entries. FIXME: Should sdisel 43775eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // or earlier pass fixed this? 43875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) { 43975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineOperand &MO = II->getOperand(i+1); 44075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (MO.getMBB() == FromBB) { 44175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i+1); 44275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng II->RemoveOperand(i); 44375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 44475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 44509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else 44609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 44709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 44809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // If Idx is set, the operands at Idx and Idx+1 must be removed. 44909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen // We reuse the location to avoid expensive RemoveOperand calls. 45009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen 45175eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg); 45275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng if (LI != SSAUpdateVals.end()) { 45375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // This register is defined in the tail block. 45479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 45511572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng MachineBasicBlock *SrcBB = LI->second[j].first; 456d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // If we didn't duplicate a bb into a particular predecessor, we 457d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // might still have added an entry to SSAUpdateVals to correcly 458d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // recompute SSA. If that case, avoid adding a dummy extra argument 459d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola // this PHI. 460d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola if (!SrcBB->isSuccessor(SuccBB)) 461d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola continue; 462d3f4eeaec177ed34a54fede9faea4ffa94c4d0afRafael Espindola 46311572babb12d169965c63c47aab9c9fad354e5dfEvan Cheng unsigned SrcReg = LI->second[j].second; 46409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 46509eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(SrcReg); 46609eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 46709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 46809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 46909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(SrcReg, false)); 47009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(SrcBB)); 47109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 47279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 47375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } else { 47475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng // Live in tail block, must also be live in predecessors. 47575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 47675eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock *SrcBB = TDBBs[j]; 47709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 47809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx).setReg(Reg); 47909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->getOperand(Idx+1).setMBB(SrcBB); 48009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen Idx = 0; 48109eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } else { 48209eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateReg(Reg, false)); 48309eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->addOperand(MachineOperand::CreateMBB(SrcBB)); 48409eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 48575eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 48679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 48709eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen if (Idx != 0) { 48809eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx+1); 48909eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen II->RemoveOperand(Idx); 49009eeac9f5f8c21621f82f9b6598eb7e34593357eJakob Stoklund Olesen } 49179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 49279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 49379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng} 49479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 49554c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// shouldTailDuplicate - Determine if it is profitable to duplicate this block. 49675eb53584367098a5625028e22f1ff8e169d0efdEvan Chengbool 49754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael EspindolaTailDuplicatePass::shouldTailDuplicate(const MachineFunction &MF, 49854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola MachineBasicBlock &TailBB) { 49954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola // Only duplicate blocks that end with unconditional branches. 50054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola if (TailBB.canFallThrough()) 50154c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola return false; 50254c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 503ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Don't try to tail-duplicate single-block loops. 504ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (TailBB.isSuccessor(&TailBB)) 505ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 506ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 50754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola // Set the limit on the cost to duplicate. When optimizing for size, 50815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // duplicate only one, because one branch instruction can be eliminated to 50915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // compensate for the duplication. 51015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson unsigned MaxDuplicateCount; 5118352062e52eed6e50786fdb89f5e601fdcbe0d90Jakob Stoklund Olesen if (TailDuplicateSize.getNumOccurrences() == 0 && 5128352062e52eed6e50786fdb89f5e601fdcbe0d90Jakob Stoklund Olesen MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 513cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = 1; 514cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson else 515cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson MaxDuplicateCount = TailDuplicateSize; 516cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson 517ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // If the target has hardware branch prediction that can handle indirect 518ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // branches, duplicating them can often make them predictable when there 519ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // are common paths through the code. The limit needs to be high enough 520ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // to allow undoing the effects of tail merging and other optimizations 521ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // that rearrange the predecessors of the indirect branch. 522ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 523ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (PreRegAlloc && !TailBB.empty()) { 52454c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola const TargetInstrDesc &TID = TailBB.back().getDesc(); 525ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (TID.isIndirectBranch()) 526ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola MaxDuplicateCount = 20; 527cb44b28f4d96c059d30c1a77d3b7e406d362d94eBob Wilson } 52815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 52915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Check the instructions in the block to determine whether tail-duplication 53015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // is invalid or unlikely to be profitable. 531f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson unsigned InstrCount = 0; 53254c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola for (MachineBasicBlock::const_iterator I = TailBB.begin(); I != TailBB.end(); 53354c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola ++I) { 53415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Non-duplicable things shouldn't be tail-duplicated. 535ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (I->getDesc().isNotDuplicable()) 536ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 537ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 53879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Do not duplicate 'return' instructions if this is a pre-regalloc run. 53979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // A return may expand into a lot more instructions (e.g. reload of callee 54079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // saved registers) after PEI. 541ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (PreRegAlloc && I->getDesc().isReturn()) 542ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 543ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 544ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Avoid duplicating calls before register allocation. Calls presents a 545ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // barrier to register allocation so duplicating them may end up increasing 546ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // spills. 547ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (PreRegAlloc && I->getDesc().isCall()) 548ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 549ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 550cbe1e31732c5d4fb1277195e76b9b42c115396aaDevang Patel if (!I->isPHI() && !I->isDebugValue()) 551f1e01dcc94fde6b1e184dc799df7145aed34a18bBob Wilson InstrCount += 1; 552ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 553ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola if (InstrCount > MaxDuplicateCount) 554ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola return false; 55515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 55615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 55754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola return true; 55854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola} 55954c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 56054c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// TailDuplicate - If it is profitable, duplicate TailBB's contents in each 56154c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola/// of its predecessors. 56254c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindolabool 56354c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael EspindolaTailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF, 56454c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola SmallVector<MachineBasicBlock*, 8> &TDBBs, 56554c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola SmallVector<MachineInstr*, 16> &Copies) { 56654c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola if (!shouldTailDuplicate(MF, *TailBB)) 56754c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola return false; 56854c256233f8dcd29406d5fe6f8a5be79a826cef3Rafael Espindola 56900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 57075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 57115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Iterate through all the unique predecessors and tail-duplicate this 57215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into them, if possible. Copying the list ahead of time also 57315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // avoids trouble with the predecessor list reallocating. 57415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool Changed = false; 57579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(), 57679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng TailBB->pred_end()); 5770f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DenseSet<unsigned> UsedByPhi; 5780f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola getRegsUsedByPHIs(*TailBB, &UsedByPhi); 57915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 58015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PE = Preds.end(); PI != PE; ++PI) { 58115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredBB = *PI; 58215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 58315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(TailBB != PredBB && 58415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "Single-block loop should have been rejected earlier!"); 5859a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola // EH edges are ignored by AnalyzeBranch. 5869a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola if (PredBB->succ_size() > 1) 5879a9a3a5c0fff9647a7a6454d974c058a4fb187d7Rafael Espindola continue; 58815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 58915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PredTBB, *PredFBB; 59015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PredCond; 59115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 59215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 59315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!PredCond.empty()) 59415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 59515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Don't duplicate into a fall-through predecessor (at least for now). 59615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 59715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson continue; 59815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 59900dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 60015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From Succ: " << *TailBB); 60115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 60275eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PredBB); 60375eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng 60415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove PredBB's unconditional branch. 60515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson TII->RemoveBranch(*PredBB); 606111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng 60715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Clone the contents of TailBB into PredBB. 608111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 6093466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 610111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 61179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 61279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I; 61379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng ++I; 614518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isPHI()) { 615111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // Replace the uses of the def of the PHI with the register coming 616111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng // from PredBB. 617689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); 61879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 61979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 62079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 6210f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi); 622111e7629cc84dad39d6b546871cdec3740b22781Evan Cheng } 62315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 62475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 6253466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 6261e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 6271e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 6281e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first).addReg(CopyInfos[i].second)); 62975eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 630ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 631ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola // Simplify 632ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true); 633ec324e5ae44025c6bdb930b78198f30f807e355bRafael Espindola 63415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson NumInstrDups += TailBB->size() - 1; // subtract one for removed branch 63515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 63615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Update the CFG. 63715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson PredBB->removeSuccessor(PredBB->succ_begin()); 63815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(PredBB->succ_empty() && 63915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson "TailDuplicate called on block with multiple successors!"); 64015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 64179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng E = TailBB->succ_end(); I != E; ++I) 64279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PredBB->addSuccessor(*I); 64315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 64415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 64515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson ++NumTailDups; 64615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 64715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 64815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If TailBB was duplicated into all its predecessors except for the prior 64915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block, which falls through unconditionally, move the contents of this 65015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // block into the prior block. 65179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB)); 65215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 65315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson SmallVector<MachineOperand, 4> PriorCond; 65415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // This has to check PrevBB->succ_size() because EH edges are ignored by 65515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // AnalyzeBranch. 656a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola if (PrevBB->succ_size() == 1 && 657a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola !TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true) && 658a899b223109ca5dba7b44439e955148a03f23d4cRafael Espindola PriorCond.empty() && !PriorTBB && TailBB->pred_size() == 1 && 65915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson !TailBB->hasAddressTaken()) { 66000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 66115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson << "From MBB: " << *TailBB); 66279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (PreRegAlloc) { 66379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng DenseMap<unsigned, unsigned> LocalVRMap; 6643466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 66579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineBasicBlock::iterator I = TailBB->begin(); 66679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Process PHI instructions first. 667518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (I != TailBB->end() && I->isPHI()) { 66879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace the uses of the def of the PHI with the register coming 66979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // from PredBB. 67079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 671689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); 67279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng if (MI->getParent()) 67379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 67479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 67579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng 67679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Now copy the non-PHI instructions. 67779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng while (I != TailBB->end()) { 67879fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // Replace def of virtual registers with new registers, and update 67979fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // uses with PHI source register or the new registers. 68079fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MachineInstr *MI = &*I++; 6810f28c3f0c30769c1a96e5664eea4acbc48eed6a4Rafael Espindola DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi); 68279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng MI->eraseFromParent(); 68379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 68475eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator(); 6853466f13f38b2f3e652cca82bd5da8527e72e195dEvan Cheng for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 6861e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen Copies.push_back(BuildMI(*PrevBB, Loc, DebugLoc(), 6871e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen TII->get(TargetOpcode::COPY), 6881e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen CopyInfos[i].first) 6891e1098c6f39590e1e74e5cb3c2a1652d8f3cb16aJakob Stoklund Olesen .addReg(CopyInfos[i].second)); 69075eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng } 69179fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } else { 69279fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng // No PHIs to worry about, just splice the instructions over. 69379fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 69479fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng } 69579fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->removeSuccessor(PrevBB->succ_begin()); 69679fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng assert(PrevBB->succ_empty()); 69779fc6f44b64f47b8a7d5e298c9f3c596b89fa88dEvan Cheng PrevBB->transferSuccessors(TailBB); 69875eb53584367098a5625028e22f1ff8e169d0efdEvan Cheng TDBBs.push_back(PrevBB); 69915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson Changed = true; 70015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson } 70115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 702689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If this is after register allocation, there are no phis to fix. 703689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!PreRegAlloc) 704689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 705689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 706689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If we made no changes so far, we are safe. 707689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (!Changed) 708689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola return Changed; 709689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 710689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 711689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Handle the nasty case in that we duplicated a block that is part of a loop 712689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // into some but not all of its predecessors. For example: 7134d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 1 -> 2 <-> 3 | 7144d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ | 7154d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \---> rest | 716689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // if we duplicate 2 into 1 but not into 3, we end up with 7174d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // 12 -> 3 <-> 2 -> rest | 7184d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \ / | 7194d7b4573f97157877f6875b69c9d32b2cb8c5329Rafael Espindola // \----->-----/ | 720689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced 721689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // with a phi in 3 (which now dominates 2). 722689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // What we do here is introduce a copy in 3 of the register defined by the 723689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // phi, just like when we are duplicating 2 into 3, but we don't copy any 724689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // real instructions or remove the 3 -> 2 edge from the phi in 2. 725689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 726689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola PE = Preds.end(); PI != PE; ++PI) { 727689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock *PredBB = *PI; 728689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (std::find(TDBBs.begin(), TDBBs.end(), PredBB) != TDBBs.end()) 729689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 730689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 731689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // EH edges 732689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola if (PredBB->succ_size() != 1) 733689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola continue; 734689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 735689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola DenseMap<unsigned, unsigned> LocalVRMap; 736689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos; 737689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator I = TailBB->begin(); 738689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Process PHI instructions first. 739689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola while (I != TailBB->end() && I->isPHI()) { 740689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // Replace the uses of the def of the PHI with the register coming 741689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola // from PredBB. 742689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineInstr *MI = &*I++; 743689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); 744689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 745689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator(); 746689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) { 747689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola Copies.push_back(BuildMI(*PredBB, Loc, DebugLoc(), 748689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola TII->get(TargetOpcode::COPY), 749689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola CopyInfos[i].first).addReg(CopyInfos[i].second)); 750689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 751689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola } 752689d7d5dffc02993eef367be3380f2b4c49e434fRafael Espindola 75315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return Changed; 75415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 75515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 75615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// RemoveDeadBlock - Remove the specified dead machine basic block from the 75715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson/// function, updating the CFG. 7582d521e51acd5f1a0100cbbe4c611a35c978c2456Bob Wilsonvoid TailDuplicatePass::RemoveDeadBlock(MachineBasicBlock *MBB) { 75915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson assert(MBB->pred_empty() && "MBB must be dead!"); 76000dec1bbf9ad44af7b5b7ae669cae78b79a09c56David Greene DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 76115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 76215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove all successors. 76315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson while (!MBB->succ_empty()) 76415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->removeSuccessor(MBB->succ_end()-1); 76515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 76615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Remove the block. 76715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MBB->eraseFromParent(); 76815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 769