TailDuplicator.cpp revision 303231
184865Sobrien//===-- TailDuplicator.cpp - Duplicate blocks into predecessors' tails ---===// 2218822Sdim// 384865Sobrien// The LLVM Compiler Infrastructure 4218822Sdim// 584865Sobrien// This file is distributed under the University of Illinois Open Source 684865Sobrien// License. See LICENSE.TXT for details. 784865Sobrien// 884865Sobrien//===----------------------------------------------------------------------===// 984865Sobrien// 1084865Sobrien// This utility class duplicates basic blocks ending in unconditional branches 1184865Sobrien// into the tails of their predecessors. 1284865Sobrien// 1384865Sobrien//===----------------------------------------------------------------------===// 1484865Sobrien 1584865Sobrien#include "llvm/CodeGen/TailDuplicator.h" 1684865Sobrien#include "llvm/ADT/DenseSet.h" 1784865Sobrien#include "llvm/ADT/SetVector.h" 1884865Sobrien#include "llvm/ADT/SmallSet.h" 1984865Sobrien#include "llvm/ADT/Statistic.h" 2084865Sobrien#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 2184865Sobrien#include "llvm/CodeGen/MachineFunctionPass.h" 22218822Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 2384865Sobrien#include "llvm/CodeGen/MachineModuleInfo.h" 24218822Sdim#include "llvm/CodeGen/Passes.h" 2584865Sobrien#include "llvm/IR/Function.h" 2689857Sobrien#include "llvm/Support/CommandLine.h" 2784865Sobrien#include "llvm/Support/Debug.h" 2884865Sobrien#include "llvm/Support/ErrorHandling.h" 2989857Sobrien#include "llvm/Support/raw_ostream.h" 3084865Sobrienusing namespace llvm; 3184865Sobrien 3289857Sobrien#define DEBUG_TYPE "tailduplication" 3384865Sobrien 34130561SobrienSTATISTIC(NumTails, "Number of tails duplicated"); 35130561SobrienSTATISTIC(NumTailDups, "Number of tail duplicated blocks"); 36130561SobrienSTATISTIC(NumTailDupAdded, 37130561Sobrien "Number of instructions added due to tail duplication"); 38130561SobrienSTATISTIC(NumTailDupRemoved, 39130561Sobrien "Number of instructions removed due to tail duplication"); 4089857SobrienSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 4189857SobrienSTATISTIC(NumAddedPHIs, "Number of phis added"); 42130561Sobrien 43130561Sobrien// Heuristic for tail duplication. 44130561Sobrienstatic cl::opt<unsigned> TailDuplicateSize( 45130561Sobrien "tail-dup-size", 46130561Sobrien cl::desc("Maximum instructions to consider tail duplicating"), cl::init(2), 47130561Sobrien cl::Hidden); 48130561Sobrien 49130561Sobrienstatic cl::opt<bool> 50130561Sobrien TailDupVerify("tail-dup-verify", 51130561Sobrien cl::desc("Verify sanity of PHI instructions during taildup"), 52130561Sobrien cl::init(false), cl::Hidden); 5389857Sobrien 54130561Sobrienstatic cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U), 55130561Sobrien cl::Hidden); 56130561Sobrien 57218822Sdimnamespace llvm { 58130561Sobrien 59130561Sobrienvoid TailDuplicator::initMF(MachineFunction &MF, const MachineModuleInfo *MMIin, 60130561Sobrien const MachineBranchProbabilityInfo *MBPIin) { 61130561Sobrien TII = MF.getSubtarget().getInstrInfo(); 62130561Sobrien TRI = MF.getSubtarget().getRegisterInfo(); 63130561Sobrien MRI = &MF.getRegInfo(); 64130561Sobrien MMI = MMIin; 65130561Sobrien MBPI = MBPIin; 66130561Sobrien 67130561Sobrien assert(MBPI != nullptr && "Machine Branch Probability Info required"); 68130561Sobrien 69130561Sobrien PreRegAlloc = MRI->isSSA(); 7089857Sobrien} 71104834Sobrien 72130561Sobrienstatic void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 73130561Sobrien for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 7489857Sobrien MachineBasicBlock *MBB = &*I; 7589857Sobrien SmallSetVector<MachineBasicBlock *, 8> Preds(MBB->pred_begin(), 7689857Sobrien MBB->pred_end()); 7789857Sobrien MachineBasicBlock::iterator MI = MBB->begin(); 7889857Sobrien while (MI != MBB->end()) { 7989857Sobrien if (!MI->isPHI()) 8089857Sobrien break; 8189857Sobrien for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 8289857Sobrien PE = Preds.end(); 8389857Sobrien PI != PE; ++PI) { 8489857Sobrien MachineBasicBlock *PredBB = *PI; 8589857Sobrien bool Found = false; 8689857Sobrien for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 8789857Sobrien MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB(); 8889857Sobrien if (PHIBB == PredBB) { 8989857Sobrien Found = true; 9089857Sobrien break; 91104834Sobrien } 9289857Sobrien } 9389857Sobrien if (!Found) { 9489857Sobrien dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 9589857Sobrien dbgs() << " missing input from predecessor BB#" 96218822Sdim << PredBB->getNumber() << '\n'; 9789857Sobrien llvm_unreachable(nullptr); 98130561Sobrien } 99130561Sobrien } 100130561Sobrien 101104834Sobrien for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 102130561Sobrien MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB(); 103130561Sobrien if (CheckExtra && !Preds.count(PHIBB)) { 104130561Sobrien dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() << ": " 105130561Sobrien << *MI; 10689857Sobrien dbgs() << " extra input from predecessor BB#" << PHIBB->getNumber() 10789857Sobrien << '\n'; 10889857Sobrien llvm_unreachable(nullptr); 10989857Sobrien } 11089857Sobrien if (PHIBB->getNumber() < 0) { 11189857Sobrien dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 11289857Sobrien dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 11389857Sobrien llvm_unreachable(nullptr); 11489857Sobrien } 11589857Sobrien } 11689857Sobrien ++MI; 11789857Sobrien } 11889857Sobrien } 11989857Sobrien} 12089857Sobrien 12189857Sobrien/// Tail duplicate the block and cleanup. 12289857Sobrienbool TailDuplicator::tailDuplicateAndUpdate(MachineFunction &MF, bool IsSimple, 12389857Sobrien MachineBasicBlock *MBB) { 12489857Sobrien // Save the successors list. 12589857Sobrien SmallSetVector<MachineBasicBlock *, 8> Succs(MBB->succ_begin(), 126104834Sobrien MBB->succ_end()); 127104834Sobrien 128104834Sobrien SmallVector<MachineBasicBlock *, 8> TDBBs; 12989857Sobrien SmallVector<MachineInstr *, 16> Copies; 13089857Sobrien if (!tailDuplicate(MF, IsSimple, MBB, TDBBs, Copies)) 13189857Sobrien return false; 13284865Sobrien 13384865Sobrien ++NumTails; 134130561Sobrien 135130561Sobrien SmallVector<MachineInstr *, 8> NewPHIs; 136130561Sobrien MachineSSAUpdater SSAUpdate(MF, &NewPHIs); 13789857Sobrien 138130561Sobrien // TailBB's immediate successors are now successors of those predecessors 13989857Sobrien // which duplicated TailBB. Add the predecessors as sources to the PHI 140130561Sobrien // instructions. 141130561Sobrien bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); 142130561Sobrien if (PreRegAlloc) 143130561Sobrien updateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 14489857Sobrien 14589857Sobrien // If it is dead, remove it. 14689857Sobrien if (isDead) { 14789857Sobrien NumTailDupRemoved += MBB->size(); 14889857Sobrien removeDeadBlock(MBB); 14989857Sobrien ++NumDeadBlocks; 15089857Sobrien } 15189857Sobrien 15289857Sobrien // Update SSA form. 15389857Sobrien if (!SSAUpdateVRs.empty()) { 15489857Sobrien for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 15589857Sobrien unsigned VReg = SSAUpdateVRs[i]; 156130561Sobrien SSAUpdate.Initialize(VReg); 15789857Sobrien 15889857Sobrien // If the original definition is still around, add it as an available 159130561Sobrien // value. 16089857Sobrien MachineInstr *DefMI = MRI->getVRegDef(VReg); 16189857Sobrien MachineBasicBlock *DefBB = nullptr; 16289857Sobrien if (DefMI) { 16389857Sobrien DefBB = DefMI->getParent(); 164130561Sobrien SSAUpdate.AddAvailableValue(DefBB, VReg); 165130561Sobrien } 166130561Sobrien 167130561Sobrien // Add the new vregs as available values. 16889857Sobrien DenseMap<unsigned, AvailableValsTy>::iterator LI = 16989857Sobrien SSAUpdateVals.find(VReg); 17089857Sobrien for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 17189857Sobrien MachineBasicBlock *SrcBB = LI->second[j].first; 172130561Sobrien unsigned SrcReg = LI->second[j].second; 173130561Sobrien SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 174130561Sobrien } 175130561Sobrien 176130561Sobrien // Rewrite uses that are outside of the original def's block. 177130561Sobrien MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 178130561Sobrien while (UI != MRI->use_end()) { 179218822Sdim MachineOperand &UseMO = *UI; 18084865Sobrien MachineInstr *UseMI = UseMO.getParent(); 181104834Sobrien ++UI; 182130561Sobrien if (UseMI->isDebugValue()) { 183130561Sobrien // SSAUpdate can replace the use with an undef. That creates 18489857Sobrien // a debug instruction that is a kill. 185130561Sobrien // FIXME: Should it SSAUpdate job to delete debug instructions 186104834Sobrien // instead of replacing the use with undef? 187130561Sobrien UseMI->eraseFromParent(); 188104834Sobrien continue; 189130561Sobrien } 190104834Sobrien if (UseMI->getParent() == DefBB && !UseMI->isPHI()) 191130561Sobrien continue; 192104834Sobrien SSAUpdate.RewriteUse(UseMO); 193104834Sobrien } 194130561Sobrien } 195104834Sobrien 196104834Sobrien SSAUpdateVRs.clear(); 197130561Sobrien SSAUpdateVals.clear(); 198130561Sobrien } 199130561Sobrien 200130561Sobrien // Eliminate some of the copies inserted by tail duplication to maintain 201104834Sobrien // SSA form. 202130561Sobrien for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 203130561Sobrien MachineInstr *Copy = Copies[i]; 204130561Sobrien if (!Copy->isCopy()) 205130561Sobrien continue; 206130561Sobrien unsigned Dst = Copy->getOperand(0).getReg(); 207130561Sobrien unsigned Src = Copy->getOperand(1).getReg(); 208130561Sobrien if (MRI->hasOneNonDBGUse(Src) && 209130561Sobrien MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) { 210130561Sobrien // Copy is the only use. Do trivial copy propagation here. 211130561Sobrien MRI->replaceRegWith(Dst, Src); 212104834Sobrien Copy->eraseFromParent(); 213130561Sobrien } 214130561Sobrien } 215130561Sobrien 216130561Sobrien if (NewPHIs.size()) 217104834Sobrien NumAddedPHIs += NewPHIs.size(); 218104834Sobrien 219130561Sobrien return true; 220104834Sobrien} 221130561Sobrien 222130561Sobrien/// Look for small blocks that are unconditionally branched to and do not fall 223130561Sobrien/// through. Tail-duplicate their instructions into their predecessors to 224130561Sobrien/// eliminate (dynamic) branches. 225104834Sobrienbool TailDuplicator::tailDuplicateBlocks(MachineFunction &MF) { 226104834Sobrien bool MadeChange = false; 227130561Sobrien 228104834Sobrien if (PreRegAlloc && TailDupVerify) { 229104834Sobrien DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 230104834Sobrien VerifyPHIs(MF, true); 231104834Sobrien } 232104834Sobrien 233104834Sobrien for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E;) { 234104834Sobrien MachineBasicBlock *MBB = &*I++; 235104834Sobrien 23684865Sobrien if (NumTails == TailDupLimit) 23784865Sobrien break; 23884865Sobrien 239130561Sobrien bool IsSimple = isSimpleBB(MBB); 24084865Sobrien 24184865Sobrien if (!shouldTailDuplicate(MF, IsSimple, *MBB)) 24284865Sobrien continue; 24384865Sobrien 24489857Sobrien MadeChange |= tailDuplicateAndUpdate(MF, IsSimple, MBB); 24584865Sobrien } 24689857Sobrien 24784865Sobrien if (PreRegAlloc && TailDupVerify) 248130561Sobrien VerifyPHIs(MF, false); 24984865Sobrien 25084865Sobrien return MadeChange; 25184865Sobrien} 25284865Sobrien 25384865Sobrienstatic bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 25484865Sobrien const MachineRegisterInfo *MRI) { 25584865Sobrien for (MachineInstr &UseMI : MRI->use_instructions(Reg)) { 25684865Sobrien if (UseMI.isDebugValue()) 25784865Sobrien continue; 25884865Sobrien if (UseMI.getParent() != BB) 25984865Sobrien return true; 26084865Sobrien } 26184865Sobrien return false; 26284865Sobrien} 26384865Sobrien 26489857Sobrienstatic unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 265104834Sobrien for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 26689857Sobrien if (MI->getOperand(i + 1).getMBB() == SrcBB) 267130561Sobrien return i; 26884865Sobrien return 0; 26984865Sobrien} 27084865Sobrien 27184865Sobrien// Remember which registers are used by phis in this block. This is 272130561Sobrien// used to determine which registers are liveout while modifying the 27384865Sobrien// block (which is why we need to copy the information). 27484865Sobrienstatic void getRegsUsedByPHIs(const MachineBasicBlock &BB, 27584865Sobrien DenseSet<unsigned> *UsedByPhi) { 27684865Sobrien for (const auto &MI : BB) { 27784865Sobrien if (!MI.isPHI()) 27884865Sobrien break; 27984865Sobrien for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 28084865Sobrien unsigned SrcReg = MI.getOperand(i).getReg(); 281130561Sobrien UsedByPhi->insert(SrcReg); 28284865Sobrien } 28384865Sobrien } 28484865Sobrien} 28584865Sobrien 28684865Sobrien/// Add a definition and source virtual registers pair for SSA update. 28784865Sobrienvoid TailDuplicator::addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 28884865Sobrien MachineBasicBlock *BB) { 28984865Sobrien DenseMap<unsigned, AvailableValsTy>::iterator LI = 29084865Sobrien SSAUpdateVals.find(OrigReg); 29184865Sobrien if (LI != SSAUpdateVals.end()) 29284865Sobrien LI->second.push_back(std::make_pair(BB, NewReg)); 29384865Sobrien else { 29484865Sobrien AvailableValsTy Vals; 29584865Sobrien Vals.push_back(std::make_pair(BB, NewReg)); 29684865Sobrien SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 29784865Sobrien SSAUpdateVRs.push_back(OrigReg); 29884865Sobrien } 29984865Sobrien} 30084865Sobrien 30184865Sobrien/// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the 30284865Sobrien/// source register that's contributed by PredBB and update SSA update map. 30384865Sobrienvoid TailDuplicator::processPHI( 30484865Sobrien MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB, 30584865Sobrien DenseMap<unsigned, RegSubRegPair> &LocalVRMap, 306104834Sobrien SmallVectorImpl<std::pair<unsigned, RegSubRegPair>> &Copies, 307104834Sobrien const DenseSet<unsigned> &RegsUsedByPhi, bool Remove) { 30884865Sobrien unsigned DefReg = MI->getOperand(0).getReg(); 30984865Sobrien unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 31084865Sobrien assert(SrcOpIdx && "Unable to find matching PHI source?"); 31184865Sobrien unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 312130561Sobrien unsigned SrcSubReg = MI->getOperand(SrcOpIdx).getSubReg(); 31384865Sobrien const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 31484865Sobrien LocalVRMap.insert(std::make_pair(DefReg, RegSubRegPair(SrcReg, SrcSubReg))); 31584865Sobrien 31684865Sobrien // Insert a copy from source to the end of the block. The def register is the 31784865Sobrien // available value liveout of the block. 31884865Sobrien unsigned NewDef = MRI->createVirtualRegister(RC); 31984865Sobrien Copies.push_back(std::make_pair(NewDef, RegSubRegPair(SrcReg, SrcSubReg))); 320130561Sobrien if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) 32184865Sobrien addSSAUpdateEntry(DefReg, NewDef, PredBB); 32284865Sobrien 32384865Sobrien if (!Remove) 32484865Sobrien return; 325130561Sobrien 32684865Sobrien // Remove PredBB from the PHI node. 32784865Sobrien MI->RemoveOperand(SrcOpIdx + 1); 32884865Sobrien MI->RemoveOperand(SrcOpIdx); 32984865Sobrien if (MI->getNumOperands() == 1) 330130561Sobrien MI->eraseFromParent(); 33184865Sobrien} 33284865Sobrien 33384865Sobrien/// Duplicate a TailBB instruction to PredBB and update 33484865Sobrien/// the source operands due to earlier PHI translation. 33589857Sobrienvoid TailDuplicator::duplicateInstruction( 33684865Sobrien MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB, 33784865Sobrien MachineFunction &MF, 33884865Sobrien DenseMap<unsigned, RegSubRegPair> &LocalVRMap, 339130561Sobrien const DenseSet<unsigned> &UsedByPhi) { 34084865Sobrien MachineInstr *NewMI = TII->duplicate(*MI, MF); 34184865Sobrien if (PreRegAlloc) { 34284865Sobrien for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 34384865Sobrien MachineOperand &MO = NewMI->getOperand(i); 34489857Sobrien if (!MO.isReg()) 34584865Sobrien continue; 34684865Sobrien unsigned Reg = MO.getReg(); 34789857Sobrien if (!TargetRegisterInfo::isVirtualRegister(Reg)) 34889857Sobrien continue; 34989857Sobrien if (MO.isDef()) { 35089857Sobrien const TargetRegisterClass *RC = MRI->getRegClass(Reg); 35189857Sobrien unsigned NewReg = MRI->createVirtualRegister(RC); 35284865Sobrien MO.setReg(NewReg); 35384865Sobrien LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0))); 35484865Sobrien if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) 35584865Sobrien addSSAUpdateEntry(Reg, NewReg, PredBB); 356130561Sobrien } else { 357130561Sobrien auto VI = LocalVRMap.find(Reg); 358130561Sobrien if (VI != LocalVRMap.end()) { 35984865Sobrien // Need to make sure that the register class of the mapped register 36084865Sobrien // will satisfy the constraints of the class of the register being 36184865Sobrien // replaced. 36284865Sobrien auto *OrigRC = MRI->getRegClass(Reg); 36384865Sobrien auto *MappedRC = MRI->getRegClass(VI->second.Reg); 36484865Sobrien const TargetRegisterClass *ConstrRC; 365130561Sobrien if (VI->second.SubReg != 0) { 36684865Sobrien ConstrRC = TRI->getMatchingSuperRegClass(MappedRC, OrigRC, 36784865Sobrien VI->second.SubReg); 36884865Sobrien if (ConstrRC) { 36989857Sobrien // The actual constraining (as in "find appropriate new class") 37089857Sobrien // is done by getMatchingSuperRegClass, so now we only need to 37184865Sobrien // change the class of the mapped register. 37284865Sobrien MRI->setRegClass(VI->second.Reg, ConstrRC); 37389857Sobrien } 37489857Sobrien } else { 37589857Sobrien // For mapped registers that do not have sub-registers, simply 37689857Sobrien // restrict their class to match the original one. 37789857Sobrien ConstrRC = MRI->constrainRegClass(VI->second.Reg, OrigRC); 37884865Sobrien } 37984865Sobrien 38084865Sobrien if (ConstrRC) { 38184865Sobrien // If the class constraining succeeded, we can simply replace 38284865Sobrien // the old register with the mapped one. 383130561Sobrien MO.setReg(VI->second.Reg); 384130561Sobrien // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a 385130561Sobrien // sub-register, we need to compose the sub-register indices. 386130561Sobrien MO.setSubReg(TRI->composeSubRegIndices(MO.getSubReg(), 387130561Sobrien VI->second.SubReg)); 388130561Sobrien } else { 389130561Sobrien // The direct replacement is not possible, due to failing register 39084865Sobrien // class constraints. An explicit COPY is necessary. Create one 39189857Sobrien // that can be reused 39284865Sobrien auto *NewRC = MI->getRegClassConstraint(i, TII, TRI); 39384865Sobrien if (NewRC == nullptr) 39489857Sobrien NewRC = OrigRC; 39589857Sobrien unsigned NewReg = MRI->createVirtualRegister(NewRC); 39684865Sobrien BuildMI(*PredBB, MI, MI->getDebugLoc(), 39789857Sobrien TII->get(TargetOpcode::COPY), NewReg) 39889857Sobrien .addReg(VI->second.Reg, 0, VI->second.SubReg); 39984865Sobrien LocalVRMap.erase(VI); 40084865Sobrien LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0))); 40189857Sobrien MO.setReg(NewReg); 40289857Sobrien // The composed VI.Reg:VI.SubReg is replaced with NewReg, which 40389857Sobrien // is equivalent to the whole register Reg. Hence, Reg:subreg 40489857Sobrien // is same as NewReg:subreg, so keep the sub-register index 40589857Sobrien // unchanged. 40689857Sobrien } 40789857Sobrien // Clear any kill flags from this operand. The new register could 40889857Sobrien // have uses after this one, so kills are not valid here. 40989857Sobrien MO.setIsKill(false); 41089857Sobrien } 41189857Sobrien } 41289857Sobrien } 41389857Sobrien } 41489857Sobrien PredBB->insert(PredBB->instr_end(), NewMI); 41589857Sobrien} 41684865Sobrien 41784865Sobrien/// After FromBB is tail duplicated into its predecessor blocks, the successors 41884865Sobrien/// have gained new predecessors. Update the PHI instructions in them 41984865Sobrien/// accordingly. 42084865Sobrienvoid TailDuplicator::updateSuccessorsPHIs( 42184865Sobrien MachineBasicBlock *FromBB, bool isDead, 42284865Sobrien SmallVectorImpl<MachineBasicBlock *> &TDBBs, 42389857Sobrien SmallSetVector<MachineBasicBlock *, 8> &Succs) { 42489857Sobrien for (SmallSetVector<MachineBasicBlock *, 8>::iterator SI = Succs.begin(), 42589857Sobrien SE = Succs.end(); 42684865Sobrien SI != SE; ++SI) { 42784865Sobrien MachineBasicBlock *SuccBB = *SI; 42884865Sobrien for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end(); 42989857Sobrien II != EE; ++II) { 43089857Sobrien if (!II->isPHI()) 43189857Sobrien break; 43289857Sobrien MachineInstrBuilder MIB(*FromBB->getParent(), II); 43384865Sobrien unsigned Idx = 0; 43484865Sobrien for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) { 43584865Sobrien MachineOperand &MO = II->getOperand(i + 1); 43684865Sobrien if (MO.getMBB() == FromBB) { 43784865Sobrien Idx = i; 43884865Sobrien break; 43984865Sobrien } 44089857Sobrien } 44189857Sobrien 44289857Sobrien assert(Idx != 0); 44389857Sobrien MachineOperand &MO0 = II->getOperand(Idx); 44489857Sobrien unsigned Reg = MO0.getReg(); 44584865Sobrien if (isDead) { 446130561Sobrien // Folded into the previous BB. 44784865Sobrien // There could be duplicate phi source entries. FIXME: Should sdisel 44884865Sobrien // or earlier pass fixed this? 44984865Sobrien for (unsigned i = II->getNumOperands() - 2; i != Idx; i -= 2) { 45084865Sobrien MachineOperand &MO = II->getOperand(i + 1); 45184865Sobrien if (MO.getMBB() == FromBB) { 45284865Sobrien II->RemoveOperand(i + 1); 45384865Sobrien II->RemoveOperand(i); 45484865Sobrien } 45584865Sobrien } 45689857Sobrien } else 45789857Sobrien Idx = 0; 45884865Sobrien 45984865Sobrien // If Idx is set, the operands at Idx and Idx+1 must be removed. 46084865Sobrien // We reuse the location to avoid expensive RemoveOperand calls. 46189857Sobrien 46289857Sobrien DenseMap<unsigned, AvailableValsTy>::iterator LI = 46389857Sobrien SSAUpdateVals.find(Reg); 46489857Sobrien if (LI != SSAUpdateVals.end()) { 46584865Sobrien // This register is defined in the tail block. 46684865Sobrien for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 46784865Sobrien MachineBasicBlock *SrcBB = LI->second[j].first; 46884865Sobrien // If we didn't duplicate a bb into a particular predecessor, we 46989857Sobrien // might still have added an entry to SSAUpdateVals to correcly 47084865Sobrien // recompute SSA. If that case, avoid adding a dummy extra argument 47189857Sobrien // this PHI. 47284865Sobrien if (!SrcBB->isSuccessor(SuccBB)) 47389857Sobrien continue; 47484865Sobrien 47589857Sobrien unsigned SrcReg = LI->second[j].second; 47684865Sobrien if (Idx != 0) { 47784865Sobrien II->getOperand(Idx).setReg(SrcReg); 47889857Sobrien II->getOperand(Idx + 1).setMBB(SrcBB); 47989857Sobrien Idx = 0; 48089857Sobrien } else { 48189857Sobrien MIB.addReg(SrcReg).addMBB(SrcBB); 48289857Sobrien } 48389857Sobrien } 48489857Sobrien } else { 48589857Sobrien // Live in tail block, must also be live in predecessors. 48689857Sobrien for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 48789857Sobrien MachineBasicBlock *SrcBB = TDBBs[j]; 48889857Sobrien if (Idx != 0) { 48989857Sobrien II->getOperand(Idx).setReg(Reg); 49089857Sobrien II->getOperand(Idx + 1).setMBB(SrcBB); 49189857Sobrien Idx = 0; 49284865Sobrien } else { 49384865Sobrien MIB.addReg(Reg).addMBB(SrcBB); 49484865Sobrien } 49589857Sobrien } 496130561Sobrien } 497130561Sobrien if (Idx != 0) { 49889857Sobrien II->RemoveOperand(Idx + 1); 49984865Sobrien II->RemoveOperand(Idx); 50084865Sobrien } 50189857Sobrien } 50289857Sobrien } 50384865Sobrien} 50484865Sobrien 50584865Sobrien/// Determine if it is profitable to duplicate this block. 50684865Sobrienbool TailDuplicator::shouldTailDuplicate(const MachineFunction &MF, 50789857Sobrien bool IsSimple, 50884865Sobrien MachineBasicBlock &TailBB) { 50984865Sobrien // Only duplicate blocks that end with unconditional branches. 51084865Sobrien if (TailBB.canFallThrough()) 51184865Sobrien return false; 512130561Sobrien 51384865Sobrien // Don't try to tail-duplicate single-block loops. 51484865Sobrien if (TailBB.isSuccessor(&TailBB)) 51589857Sobrien return false; 51689857Sobrien 51789857Sobrien // Set the limit on the cost to duplicate. When optimizing for size, 51889857Sobrien // duplicate only one, because one branch instruction can be eliminated to 51989857Sobrien // compensate for the duplication. 52089857Sobrien unsigned MaxDuplicateCount; 52189857Sobrien if (TailDuplicateSize.getNumOccurrences() == 0 && 52289857Sobrien // FIXME: Use Function::optForSize(). 52389857Sobrien MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize)) 52489857Sobrien MaxDuplicateCount = 1; 52589857Sobrien else 52684865Sobrien MaxDuplicateCount = TailDuplicateSize; 52789857Sobrien 52889857Sobrien // If the target has hardware branch prediction that can handle indirect 52989857Sobrien // branches, duplicating them can often make them predictable when there 53089857Sobrien // are common paths through the code. The limit needs to be high enough 53189857Sobrien // to allow undoing the effects of tail merging and other optimizations 53289857Sobrien // that rearrange the predecessors of the indirect branch. 53389857Sobrien 53489857Sobrien bool HasIndirectbr = false; 53589857Sobrien if (!TailBB.empty()) 53689857Sobrien HasIndirectbr = TailBB.back().isIndirectBranch(); 53789857Sobrien 53889857Sobrien if (HasIndirectbr && PreRegAlloc) 53989857Sobrien MaxDuplicateCount = 20; 54089857Sobrien 54189857Sobrien // Check the instructions in the block to determine whether tail-duplication 54289857Sobrien // is invalid or unlikely to be profitable. 54389857Sobrien unsigned InstrCount = 0; 54489857Sobrien for (MachineInstr &MI : TailBB) { 54584865Sobrien // Non-duplicable things shouldn't be tail-duplicated. 54689857Sobrien if (MI.isNotDuplicable()) 54789857Sobrien return false; 54889857Sobrien 54989857Sobrien // Convergent instructions can be duplicated only if doing so doesn't add 55089857Sobrien // new control dependencies, which is what we're going to do here. 55189857Sobrien if (MI.isConvergent()) 55289857Sobrien return false; 55389857Sobrien 55489857Sobrien // Do not duplicate 'return' instructions if this is a pre-regalloc run. 55589857Sobrien // A return may expand into a lot more instructions (e.g. reload of callee 55689857Sobrien // saved registers) after PEI. 55784865Sobrien if (PreRegAlloc && MI.isReturn()) 55884865Sobrien return false; 55989857Sobrien 56089857Sobrien // Avoid duplicating calls before register allocation. Calls presents a 56184865Sobrien // barrier to register allocation so duplicating them may end up increasing 56284865Sobrien // spills. 56384865Sobrien if (PreRegAlloc && MI.isCall()) 56489857Sobrien return false; 56589857Sobrien 56689857Sobrien if (!MI.isPHI() && !MI.isDebugValue()) 56789857Sobrien InstrCount += 1; 56884865Sobrien 56984865Sobrien if (InstrCount > MaxDuplicateCount) 57084865Sobrien return false; 57189857Sobrien } 57289857Sobrien 57389857Sobrien // Check if any of the successors of TailBB has a PHI node in which the 57489857Sobrien // value corresponding to TailBB uses a subregister. 57589857Sobrien // If a phi node uses a register paired with a subregister, the actual 57689857Sobrien // "value type" of the phi may differ from the type of the register without 57789857Sobrien // any subregisters. Due to a bug, tail duplication may add a new operand 57889857Sobrien // without a necessary subregister, producing an invalid code. This is 57984865Sobrien // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll. 58084865Sobrien // Disable tail duplication for this case for now, until the problem is 58184865Sobrien // fixed. 58289857Sobrien for (auto SB : TailBB.successors()) { 58384865Sobrien for (auto &I : *SB) { 58484865Sobrien if (!I.isPHI()) 58589857Sobrien break; 58689857Sobrien unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB); 58789857Sobrien assert(Idx != 0); 58889857Sobrien MachineOperand &PU = I.getOperand(Idx); 58984865Sobrien if (PU.getSubReg() != 0) 59084865Sobrien return false; 59184865Sobrien } 59284865Sobrien } 59384865Sobrien 59489857Sobrien if (HasIndirectbr && PreRegAlloc) 59589857Sobrien return true; 59684865Sobrien 59784865Sobrien if (IsSimple) 59884865Sobrien return true; 59984865Sobrien 60084865Sobrien if (!PreRegAlloc) 60184865Sobrien return true; 60284865Sobrien 60384865Sobrien return canCompletelyDuplicateBB(TailBB); 60484865Sobrien} 60584865Sobrien 60684865Sobrien/// True if this BB has only one unconditional jump. 607130561Sobrienbool TailDuplicator::isSimpleBB(MachineBasicBlock *TailBB) { 608130561Sobrien if (TailBB->succ_size() != 1) 609130561Sobrien return false; 610130561Sobrien if (TailBB->pred_empty()) 611130561Sobrien return false; 612130561Sobrien MachineBasicBlock::iterator I = TailBB->getFirstNonDebugInstr(); 61384865Sobrien if (I == TailBB->end()) 614130561Sobrien return true; 615130561Sobrien return I->isUnconditionalBranch(); 616130561Sobrien} 617130561Sobrien 618130561Sobrienstatic bool bothUsedInPHI(const MachineBasicBlock &A, 619130561Sobrien const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) { 62084865Sobrien for (MachineBasicBlock *BB : A.successors()) 62184865Sobrien if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI()) 622130561Sobrien return true; 623130561Sobrien 624130561Sobrien return false; 625130561Sobrien} 626130561Sobrien 627130561Sobrienbool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) { 62884865Sobrien for (MachineBasicBlock *PredBB : BB.predecessors()) { 629130561Sobrien if (PredBB->succ_size() > 1) 630130561Sobrien return false; 631130561Sobrien 632130561Sobrien MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 633130561Sobrien SmallVector<MachineOperand, 4> PredCond; 634130561Sobrien if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 63584865Sobrien return false; 63684865Sobrien 637130561Sobrien if (!PredCond.empty()) 638130561Sobrien return false; 639130561Sobrien } 640130561Sobrien return true; 641130561Sobrien} 642130561Sobrien 64384865Sobrienbool TailDuplicator::duplicateSimpleBB( 644130561Sobrien MachineBasicBlock *TailBB, SmallVectorImpl<MachineBasicBlock *> &TDBBs, 645130561Sobrien const DenseSet<unsigned> &UsedByPhi, 646130561Sobrien SmallVectorImpl<MachineInstr *> &Copies) { 647130561Sobrien SmallPtrSet<MachineBasicBlock *, 8> Succs(TailBB->succ_begin(), 648130561Sobrien TailBB->succ_end()); 649130561Sobrien SmallVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(), 65084865Sobrien TailBB->pred_end()); 65184865Sobrien bool Changed = false; 652130561Sobrien for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 653130561Sobrien PE = Preds.end(); 654130561Sobrien PI != PE; ++PI) { 655130561Sobrien MachineBasicBlock *PredBB = *PI; 656130561Sobrien 657130561Sobrien if (PredBB->hasEHPadSuccessor()) 65884865Sobrien continue; 659130561Sobrien 660130561Sobrien if (bothUsedInPHI(*PredBB, Succs)) 661130561Sobrien continue; 662130561Sobrien 663130561Sobrien MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 664130561Sobrien SmallVector<MachineOperand, 4> PredCond; 66584865Sobrien if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 66684865Sobrien continue; 667130561Sobrien 668130561Sobrien Changed = true; 669130561Sobrien DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 670130561Sobrien << "From simple Succ: " << *TailBB); 671130561Sobrien 672130561Sobrien MachineBasicBlock *NewTarget = *TailBB->succ_begin(); 67384865Sobrien MachineBasicBlock *NextBB = &*std::next(PredBB->getIterator()); 674130561Sobrien 675130561Sobrien // Make PredFBB explicit. 676130561Sobrien if (PredCond.empty()) 677130561Sobrien PredFBB = PredTBB; 678130561Sobrien 679130561Sobrien // Make fall through explicit. 68084865Sobrien if (!PredTBB) 68184865Sobrien PredTBB = NextBB; 682130561Sobrien if (!PredFBB) 683130561Sobrien PredFBB = NextBB; 684104834Sobrien 685130561Sobrien // Redirect 686130561Sobrien if (PredFBB == TailBB) 687130561Sobrien PredFBB = NewTarget; 68884865Sobrien if (PredTBB == TailBB) 689130561Sobrien PredTBB = NewTarget; 690130561Sobrien 691130561Sobrien // Make the branch unconditional if possible 692130561Sobrien if (PredTBB == PredFBB) { 693130561Sobrien PredCond.clear(); 694130561Sobrien PredFBB = nullptr; 69584865Sobrien } 696130561Sobrien 697130561Sobrien // Avoid adding fall through branches. 698130561Sobrien if (PredFBB == NextBB) 699104834Sobrien PredFBB = nullptr; 700130561Sobrien if (PredTBB == NextBB && PredFBB == nullptr) 701130561Sobrien PredTBB = nullptr; 702130561Sobrien 70384865Sobrien TII->RemoveBranch(*PredBB); 704130561Sobrien 705130561Sobrien if (!PredBB->isSuccessor(NewTarget)) 706130561Sobrien PredBB->replaceSuccessor(TailBB, NewTarget); 707130561Sobrien else { 708130561Sobrien PredBB->removeSuccessor(TailBB, true); 709130561Sobrien assert(PredBB->succ_size() <= 1); 71084865Sobrien } 71184865Sobrien 71284865Sobrien if (PredTBB) 71384865Sobrien TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc()); 714130561Sobrien 715130561Sobrien TDBBs.push_back(PredBB); 716130561Sobrien } 717130561Sobrien return Changed; 718130561Sobrien} 719130561Sobrien 72084865Sobrien/// If it is profitable, duplicate TailBB's contents in each 721130561Sobrien/// of its predecessors. 722130561Sobrienbool TailDuplicator::tailDuplicate(MachineFunction &MF, bool IsSimple, 723130561Sobrien MachineBasicBlock *TailBB, 724104834Sobrien SmallVectorImpl<MachineBasicBlock *> &TDBBs, 725104834Sobrien SmallVectorImpl<MachineInstr *> &Copies) { 726130561Sobrien DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 72784865Sobrien 72884865Sobrien DenseSet<unsigned> UsedByPhi; 72984865Sobrien getRegsUsedByPHIs(*TailBB, &UsedByPhi); 73084865Sobrien 731130561Sobrien if (IsSimple) 732130561Sobrien return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies); 733130561Sobrien 734130561Sobrien // Iterate through all the unique predecessors and tail-duplicate this 735130561Sobrien // block into them, if possible. Copying the list ahead of time also 736130561Sobrien // avoids trouble with the predecessor list reallocating. 73784865Sobrien bool Changed = false; 738130561Sobrien SmallSetVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(), 739130561Sobrien TailBB->pred_end()); 740130561Sobrien for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 741130561Sobrien PE = Preds.end(); 742130561Sobrien PI != PE; ++PI) { 743130561Sobrien MachineBasicBlock *PredBB = *PI; 74484865Sobrien 74584865Sobrien assert(TailBB != PredBB && 74684865Sobrien "Single-block loop should have been rejected earlier!"); 74784865Sobrien // EH edges are ignored by AnalyzeBranch. 748130561Sobrien if (PredBB->succ_size() > 1) 749130561Sobrien continue; 750104834Sobrien 751130561Sobrien MachineBasicBlock *PredTBB, *PredFBB; 752130561Sobrien SmallVector<MachineOperand, 4> PredCond; 753130561Sobrien if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)) 75484865Sobrien continue; 755130561Sobrien if (!PredCond.empty()) 756130561Sobrien continue; 757130561Sobrien // Don't duplicate into a fall-through predecessor (at least for now). 758130561Sobrien if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 759130561Sobrien continue; 760130561Sobrien 76184865Sobrien DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 76284865Sobrien << "From Succ: " << *TailBB); 763130561Sobrien 764130561Sobrien TDBBs.push_back(PredBB); 765104834Sobrien 766130561Sobrien // Remove PredBB's unconditional branch. 767130561Sobrien TII->RemoveBranch(*PredBB); 768130561Sobrien 76984865Sobrien // Clone the contents of TailBB into PredBB. 770130561Sobrien DenseMap<unsigned, RegSubRegPair> LocalVRMap; 771130561Sobrien SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos; 772130561Sobrien // Use instr_iterator here to properly handle bundles, e.g. 773130561Sobrien // ARM Thumb2 IT block. 774130561Sobrien MachineBasicBlock::instr_iterator I = TailBB->instr_begin(); 775130561Sobrien while (I != TailBB->instr_end()) { 77684865Sobrien MachineInstr *MI = &*I; 77784865Sobrien ++I; 77884865Sobrien if (MI->isPHI()) { 77984865Sobrien // Replace the uses of the def of the PHI with the register coming 780130561Sobrien // from PredBB. 781130561Sobrien processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); 782130561Sobrien } else { 783130561Sobrien // Replace def of virtual registers with new registers, and update 784130561Sobrien // uses with PHI source register or the new registers. 785130561Sobrien duplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap, UsedByPhi); 786104834Sobrien } 787130561Sobrien } 788130561Sobrien appendCopies(PredBB, CopyInfos, Copies); 789130561Sobrien 790130561Sobrien // Simplify 791130561Sobrien TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true); 792130561Sobrien 79384865Sobrien NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch 79484865Sobrien 79584865Sobrien // Update the CFG. 79684865Sobrien PredBB->removeSuccessor(PredBB->succ_begin()); 79784865Sobrien assert(PredBB->succ_empty() && 798130561Sobrien "TailDuplicate called on block with multiple successors!"); 799130561Sobrien for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 800104834Sobrien E = TailBB->succ_end(); 801130561Sobrien I != E; ++I) 802130561Sobrien PredBB->addSuccessor(*I, MBPI->getEdgeProbability(TailBB, I)); 803130561Sobrien 80484865Sobrien Changed = true; 805130561Sobrien ++NumTailDups; 806130561Sobrien } 807130561Sobrien 808130561Sobrien // If TailBB was duplicated into all its predecessors except for the prior 809130561Sobrien // block, which falls through unconditionally, move the contents of this 810130561Sobrien // block into the prior block. 81184865Sobrien MachineBasicBlock *PrevBB = &*std::prev(TailBB->getIterator()); 81284865Sobrien MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr; 813130561Sobrien SmallVector<MachineOperand, 4> PriorCond; 814130561Sobrien // This has to check PrevBB->succ_size() because EH edges are ignored by 815104834Sobrien // AnalyzeBranch. 816130561Sobrien if (PrevBB->succ_size() == 1 && 817130561Sobrien !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true) && 818130561Sobrien PriorCond.empty() && !PriorTBB && TailBB->pred_size() == 1 && 81984865Sobrien !TailBB->hasAddressTaken()) { 820130561Sobrien DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 821130561Sobrien << "From MBB: " << *TailBB); 822130561Sobrien if (PreRegAlloc) { 823130561Sobrien DenseMap<unsigned, RegSubRegPair> LocalVRMap; 824130561Sobrien SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos; 825130561Sobrien MachineBasicBlock::iterator I = TailBB->begin(); 82684865Sobrien // Process PHI instructions first. 82784865Sobrien while (I != TailBB->end() && I->isPHI()) { 828130561Sobrien // Replace the uses of the def of the PHI with the register coming 829130561Sobrien // from PredBB. 830130561Sobrien MachineInstr *MI = &*I++; 831130561Sobrien processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); 832130561Sobrien } 833130561Sobrien 83484865Sobrien // Now copy the non-PHI instructions. 835130561Sobrien while (I != TailBB->end()) { 836130561Sobrien // Replace def of virtual registers with new registers, and update 837130561Sobrien // uses with PHI source register or the new registers. 838130561Sobrien MachineInstr *MI = &*I++; 839130561Sobrien assert(!MI->isBundle() && "Not expecting bundles before regalloc!"); 840130561Sobrien duplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap, UsedByPhi); 84184865Sobrien MI->eraseFromParent(); 84284865Sobrien } 843130561Sobrien appendCopies(PrevBB, CopyInfos, Copies); 844130561Sobrien } else { 845130561Sobrien // No PHIs to worry about, just splice the instructions over. 846130561Sobrien PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 847130561Sobrien } 848130561Sobrien PrevBB->removeSuccessor(PrevBB->succ_begin()); 84984865Sobrien assert(PrevBB->succ_empty()); 850130561Sobrien PrevBB->transferSuccessors(TailBB); 851130561Sobrien TDBBs.push_back(PrevBB); 852130561Sobrien Changed = true; 853130561Sobrien } 854130561Sobrien 855130561Sobrien // If this is after register allocation, there are no phis to fix. 85684865Sobrien if (!PreRegAlloc) 85784865Sobrien return Changed; 858130561Sobrien 859130561Sobrien // If we made no changes so far, we are safe. 860104834Sobrien if (!Changed) 861130561Sobrien return Changed; 862130561Sobrien 863130561Sobrien // Handle the nasty case in that we duplicated a block that is part of a loop 86484865Sobrien // into some but not all of its predecessors. For example: 865130561Sobrien // 1 -> 2 <-> 3 | 866130561Sobrien // \ | 867130561Sobrien // \---> rest | 868130561Sobrien // if we duplicate 2 into 1 but not into 3, we end up with 869130561Sobrien // 12 -> 3 <-> 2 -> rest | 870130561Sobrien // \ / | 87184865Sobrien // \----->-----/ | 87284865Sobrien // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced 873130561Sobrien // with a phi in 3 (which now dominates 2). 874130561Sobrien // What we do here is introduce a copy in 3 of the register defined by the 875104834Sobrien // phi, just like when we are duplicating 2 into 3, but we don't copy any 876130561Sobrien // real instructions or remove the 3 -> 2 edge from the phi in 2. 877130561Sobrien for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(), 878130561Sobrien PE = Preds.end(); 87984865Sobrien PI != PE; ++PI) { 880130561Sobrien MachineBasicBlock *PredBB = *PI; 881130561Sobrien if (std::find(TDBBs.begin(), TDBBs.end(), PredBB) != TDBBs.end()) 882130561Sobrien continue; 883130561Sobrien 884130561Sobrien // EH edges 885130561Sobrien if (PredBB->succ_size() != 1) 88684865Sobrien continue; 88784865Sobrien 888130561Sobrien DenseMap<unsigned, RegSubRegPair> LocalVRMap; 889130561Sobrien SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos; 890130561Sobrien MachineBasicBlock::iterator I = TailBB->begin(); 891130561Sobrien // Process PHI instructions first. 892130561Sobrien while (I != TailBB->end() && I->isPHI()) { 893130561Sobrien // Replace the uses of the def of the PHI with the register coming 89484865Sobrien // from PredBB. 895130561Sobrien MachineInstr *MI = &*I++; 896130561Sobrien processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); 897130561Sobrien } 898104834Sobrien appendCopies(PredBB, CopyInfos, Copies); 899104834Sobrien } 900130561Sobrien 90184865Sobrien return Changed; 90284865Sobrien} 903130561Sobrien 904130561Sobrien/// At the end of the block \p MBB generate COPY instructions between registers 905130561Sobrien/// described by \p CopyInfos. Append resulting instructions to \p Copies. 906130561Sobrienvoid TailDuplicator::appendCopies(MachineBasicBlock *MBB, 907130561Sobrien SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos, 908130561Sobrien SmallVectorImpl<MachineInstr*> &Copies) { 90984865Sobrien MachineBasicBlock::iterator Loc = MBB->getFirstTerminator(); 910130561Sobrien const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY); 911130561Sobrien for (auto &CI : CopyInfos) { 912130561Sobrien auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first) 913104834Sobrien .addReg(CI.second.Reg, 0, CI.second.SubReg); 914104834Sobrien Copies.push_back(C); 915130561Sobrien } 91684865Sobrien} 91784865Sobrien 918130561Sobrien/// Remove the specified dead machine basic block from the function, updating 919130561Sobrien/// the CFG. 920130561Sobrienvoid TailDuplicator::removeDeadBlock(MachineBasicBlock *MBB) { 921130561Sobrien assert(MBB->pred_empty() && "MBB must be dead!"); 922130561Sobrien DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 923130561Sobrien 92484865Sobrien // Remove all successors. 925130561Sobrien while (!MBB->succ_empty()) 926130561Sobrien MBB->removeSuccessor(MBB->succ_end() - 1); 927130561Sobrien 928104834Sobrien // Remove the block. 929104834Sobrien MBB->eraseFromParent(); 930130561Sobrien} 93184865Sobrien 93284865Sobrien} // End llvm namespace 933130561Sobrien