TailDuplicator.cpp revision 321369
133965Sjdp//===- TailDuplicator.cpp - Duplicate blocks into predecessors' tails -----===// 2218822Sdim// 3218822Sdim// The LLVM Compiler Infrastructure 433965Sjdp// 533965Sjdp// This file is distributed under the University of Illinois Open Source 6104834Sobrien// License. See LICENSE.TXT for details. 733965Sjdp// 8104834Sobrien//===----------------------------------------------------------------------===// 9104834Sobrien// 10104834Sobrien// This utility class duplicates basic blocks ending in unconditional branches 11104834Sobrien// into the tails of their predecessors. 1233965Sjdp// 13104834Sobrien//===----------------------------------------------------------------------===// 14104834Sobrien 15104834Sobrien#include "llvm/ADT/DenseMap.h" 16104834Sobrien#include "llvm/ADT/DenseSet.h" 1733965Sjdp#include "llvm/ADT/SetVector.h" 18104834Sobrien#include "llvm/ADT/SmallPtrSet.h" 19104834Sobrien#include "llvm/ADT/SmallVector.h" 20218822Sdim#include "llvm/ADT/Statistic.h" 2133965Sjdp#include "llvm/ADT/STLExtras.h" 2233965Sjdp#include "llvm/CodeGen/MachineBasicBlock.h" 2333965Sjdp#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 2433965Sjdp#include "llvm/CodeGen/MachineFunction.h" 2533965Sjdp#include "llvm/CodeGen/MachineInstr.h" 2633965Sjdp#include "llvm/CodeGen/MachineInstrBuilder.h" 2733965Sjdp#include "llvm/CodeGen/MachineOperand.h" 2833965Sjdp#include "llvm/CodeGen/MachineRegisterInfo.h" 2933965Sjdp#include "llvm/CodeGen/MachineSSAUpdater.h" 3033965Sjdp#include "llvm/CodeGen/TailDuplicator.h" 3133965Sjdp#include "llvm/IR/DebugLoc.h" 3233965Sjdp#include "llvm/IR/Function.h" 3333965Sjdp#include "llvm/Support/CommandLine.h" 3433965Sjdp#include "llvm/Support/Debug.h" 3533965Sjdp#include "llvm/Support/ErrorHandling.h" 3633965Sjdp#include "llvm/Support/raw_ostream.h" 3733965Sjdp#include "llvm/Target/TargetInstrInfo.h" 3889857Sobrien#include "llvm/Target/TargetRegisterInfo.h" 3989857Sobrien#include "llvm/Target/TargetSubtargetInfo.h" 4033965Sjdp#include <algorithm> 4133965Sjdp#include <cassert> 4233965Sjdp#include <iterator> 4333965Sjdp#include <utility> 4489857Sobrien 4589857Sobrienusing namespace llvm; 4689857Sobrien 4789857Sobrien#define DEBUG_TYPE "tailduplication" 4889857Sobrien 4989857SobrienSTATISTIC(NumTails, "Number of tails duplicated"); 5089857SobrienSTATISTIC(NumTailDups, "Number of tail duplicated blocks"); 5189857SobrienSTATISTIC(NumTailDupAdded, 5289857Sobrien "Number of instructions added due to tail duplication"); 5333965SjdpSTATISTIC(NumTailDupRemoved, 5433965Sjdp "Number of instructions removed due to tail duplication"); 5533965SjdpSTATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 5633965SjdpSTATISTIC(NumAddedPHIs, "Number of phis added"); 5733965Sjdp 5833965Sjdp// Heuristic for tail duplication. 5933965Sjdpstatic cl::opt<unsigned> TailDuplicateSize( 6033965Sjdp "tail-dup-size", 6133965Sjdp cl::desc("Maximum instructions to consider tail duplicating"), cl::init(2), 6233965Sjdp cl::Hidden); 6333965Sjdp 6433965Sjdpstatic cl::opt<unsigned> TailDupIndirectBranchSize( 6533965Sjdp "tail-dup-indirect-size", 6633965Sjdp cl::desc("Maximum instructions to consider tail duplicating blocks that " 6733965Sjdp "end with indirect branches."), cl::init(20), 6833965Sjdp cl::Hidden); 69130561Sobrien 70130561Sobrienstatic cl::opt<bool> 71130561Sobrien TailDupVerify("tail-dup-verify", 72130561Sobrien cl::desc("Verify sanity of PHI instructions during taildup"), 73130561Sobrien cl::init(false), cl::Hidden); 74130561Sobrien 75130561Sobrienstatic cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U), 76130561Sobrien cl::Hidden); 7733965Sjdp 7833965Sjdpvoid TailDuplicator::initMF(MachineFunction &MFin, 7933965Sjdp const MachineBranchProbabilityInfo *MBPIin, 8033965Sjdp bool LayoutModeIn, unsigned TailDupSizeIn) { 8133965Sjdp MF = &MFin; 8233965Sjdp TII = MF->getSubtarget().getInstrInfo(); 8333965Sjdp TRI = MF->getSubtarget().getRegisterInfo(); 84130561Sobrien MRI = &MF->getRegInfo(); 8533965Sjdp MMI = &MF->getMMI(); 8633965Sjdp MBPI = MBPIin; 8733965Sjdp TailDupSize = TailDupSizeIn; 8833965Sjdp 8933965Sjdp assert(MBPI != nullptr && "Machine Branch Probability Info required"); 9033965Sjdp 9133965Sjdp LayoutMode = LayoutModeIn; 9233965Sjdp PreRegAlloc = MRI->isSSA(); 9333965Sjdp} 9433965Sjdp 95218822Sdimstatic void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { 96218822Sdim for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) { 97218822Sdim MachineBasicBlock *MBB = &*I; 98218822Sdim SmallSetVector<MachineBasicBlock *, 8> Preds(MBB->pred_begin(), 99218822Sdim MBB->pred_end()); 100218822Sdim MachineBasicBlock::iterator MI = MBB->begin(); 101218822Sdim while (MI != MBB->end()) { 102218822Sdim if (!MI->isPHI()) 103218822Sdim break; 104218822Sdim for (MachineBasicBlock *PredBB : Preds) { 105218822Sdim bool Found = false; 106218822Sdim for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 107218822Sdim MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB(); 108218822Sdim if (PHIBB == PredBB) { 109218822Sdim Found = true; 110218822Sdim break; 111218822Sdim } 112218822Sdim } 113218822Sdim if (!Found) { 114218822Sdim dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 11533965Sjdp dbgs() << " missing input from predecessor BB#" 116218822Sdim << PredBB->getNumber() << '\n'; 11733965Sjdp llvm_unreachable(nullptr); 11833965Sjdp } 11933965Sjdp } 12033965Sjdp 121218822Sdim for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { 122218822Sdim MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB(); 12333965Sjdp if (CheckExtra && !Preds.count(PHIBB)) { 12433965Sjdp dbgs() << "Warning: malformed PHI in BB#" << MBB->getNumber() << ": " 12533965Sjdp << *MI; 12633965Sjdp dbgs() << " extra input from predecessor BB#" << PHIBB->getNumber() 12733965Sjdp << '\n'; 128218822Sdim llvm_unreachable(nullptr); 12933965Sjdp } 13033965Sjdp if (PHIBB->getNumber() < 0) { 13133965Sjdp dbgs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI; 13233965Sjdp dbgs() << " non-existing BB#" << PHIBB->getNumber() << '\n'; 13333965Sjdp llvm_unreachable(nullptr); 13433965Sjdp } 135218822Sdim } 13633965Sjdp ++MI; 137130561Sobrien } 138130561Sobrien } 139130561Sobrien} 140130561Sobrien 141130561Sobrien/// Tail duplicate the block and cleanup. 142130561Sobrien/// \p IsSimple - return value of isSimpleBB 143130561Sobrien/// \p MBB - block to be duplicated 144130561Sobrien/// \p ForcedLayoutPred - If non-null, treat this block as the layout 14533965Sjdp/// predecessor, instead of using the ordering in MF 14633965Sjdp/// \p DuplicatedPreds - if non-null, \p DuplicatedPreds will contain a list of 14733965Sjdp/// all Preds that received a copy of \p MBB. 14833965Sjdp/// \p RemovalCallback - if non-null, called just before MBB is deleted. 14933965Sjdpbool TailDuplicator::tailDuplicateAndUpdate( 150218822Sdim bool IsSimple, MachineBasicBlock *MBB, 15133965Sjdp MachineBasicBlock *ForcedLayoutPred, 15233965Sjdp SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds, 15333965Sjdp function_ref<void(MachineBasicBlock *)> *RemovalCallback) { 15433965Sjdp // Save the successors list. 15533965Sjdp SmallSetVector<MachineBasicBlock *, 8> Succs(MBB->succ_begin(), 15633965Sjdp MBB->succ_end()); 15733965Sjdp 15833965Sjdp SmallVector<MachineBasicBlock *, 8> TDBBs; 15933965Sjdp SmallVector<MachineInstr *, 16> Copies; 16033965Sjdp if (!tailDuplicate(IsSimple, MBB, ForcedLayoutPred, TDBBs, Copies)) 16133965Sjdp return false; 16233965Sjdp 16333965Sjdp ++NumTails; 16433965Sjdp 16533965Sjdp SmallVector<MachineInstr *, 8> NewPHIs; 16633965Sjdp MachineSSAUpdater SSAUpdate(*MF, &NewPHIs); 16733965Sjdp 16833965Sjdp // TailBB's immediate successors are now successors of those predecessors 16933965Sjdp // which duplicated TailBB. Add the predecessors as sources to the PHI 17033965Sjdp // instructions. 17133965Sjdp bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); 172130561Sobrien if (PreRegAlloc) 17389857Sobrien updateSuccessorsPHIs(MBB, isDead, TDBBs, Succs); 17433965Sjdp 17533965Sjdp // If it is dead, remove it. 176130561Sobrien if (isDead) { 17733965Sjdp NumTailDupRemoved += MBB->size(); 17833965Sjdp removeDeadBlock(MBB, RemovalCallback); 17933965Sjdp ++NumDeadBlocks; 180130561Sobrien } 181130561Sobrien 18233965Sjdp // Update SSA form. 18333965Sjdp if (!SSAUpdateVRs.empty()) { 18433965Sjdp for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { 18533965Sjdp unsigned VReg = SSAUpdateVRs[i]; 18633965Sjdp SSAUpdate.Initialize(VReg); 18733965Sjdp 188130561Sobrien // If the original definition is still around, add it as an available 189130561Sobrien // value. 19033965Sjdp MachineInstr *DefMI = MRI->getVRegDef(VReg); 19133965Sjdp MachineBasicBlock *DefBB = nullptr; 19233965Sjdp if (DefMI) { 193130561Sobrien DefBB = DefMI->getParent(); 194130561Sobrien SSAUpdate.AddAvailableValue(DefBB, VReg); 195130561Sobrien } 19633965Sjdp 19733965Sjdp // Add the new vregs as available values. 19833965Sjdp DenseMap<unsigned, AvailableValsTy>::iterator LI = 199130561Sobrien SSAUpdateVals.find(VReg); 200104834Sobrien for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 201218822Sdim MachineBasicBlock *SrcBB = LI->second[j].first; 202218822Sdim unsigned SrcReg = LI->second[j].second; 203218822Sdim SSAUpdate.AddAvailableValue(SrcBB, SrcReg); 204218822Sdim } 205104834Sobrien 206104834Sobrien // Rewrite uses that are outside of the original def's block. 207104834Sobrien MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg); 208104834Sobrien while (UI != MRI->use_end()) { 209104834Sobrien MachineOperand &UseMO = *UI; 21033965Sjdp MachineInstr *UseMI = UseMO.getParent(); 211130561Sobrien ++UI; 212130561Sobrien if (UseMI->isDebugValue()) { 213130561Sobrien // SSAUpdate can replace the use with an undef. That creates 214130561Sobrien // a debug instruction that is a kill. 215130561Sobrien // FIXME: Should it SSAUpdate job to delete debug instructions 216130561Sobrien // instead of replacing the use with undef? 217130561Sobrien UseMI->eraseFromParent(); 218130561Sobrien continue; 219130561Sobrien } 220130561Sobrien if (UseMI->getParent() == DefBB && !UseMI->isPHI()) 221130561Sobrien continue; 222130561Sobrien SSAUpdate.RewriteUse(UseMO); 223130561Sobrien } 224218822Sdim } 225218822Sdim 22633965Sjdp SSAUpdateVRs.clear(); 22733965Sjdp SSAUpdateVals.clear(); 22833965Sjdp } 22933965Sjdp 23033965Sjdp // Eliminate some of the copies inserted by tail duplication to maintain 231130561Sobrien // SSA form. 232130561Sobrien for (unsigned i = 0, e = Copies.size(); i != e; ++i) { 233104834Sobrien MachineInstr *Copy = Copies[i]; 234130561Sobrien if (!Copy->isCopy()) 235104834Sobrien continue; 236130561Sobrien unsigned Dst = Copy->getOperand(0).getReg(); 237104834Sobrien unsigned Src = Copy->getOperand(1).getReg(); 238130561Sobrien if (MRI->hasOneNonDBGUse(Src) && 239104834Sobrien MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) { 240104834Sobrien // Copy is the only use. Do trivial copy propagation here. 241130561Sobrien MRI->replaceRegWith(Dst, Src); 242104834Sobrien Copy->eraseFromParent(); 243130561Sobrien } 244130561Sobrien } 245104834Sobrien 246130561Sobrien if (NewPHIs.size()) 247130561Sobrien NumAddedPHIs += NewPHIs.size(); 248104834Sobrien 249130561Sobrien if (DuplicatedPreds) 25089857Sobrien *DuplicatedPreds = std::move(TDBBs); 251130561Sobrien 252104834Sobrien return true; 253130561Sobrien} 254130561Sobrien 255104834Sobrien/// Look for small blocks that are unconditionally branched to and do not fall 256130561Sobrien/// through. Tail-duplicate their instructions into their predecessors to 25733965Sjdp/// eliminate (dynamic) branches. 25833965Sjdpbool TailDuplicator::tailDuplicateBlocks() { 25933965Sjdp bool MadeChange = false; 260130561Sobrien 261104834Sobrien if (PreRegAlloc && TailDupVerify) { 262130561Sobrien DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); 26360484Sobrien VerifyPHIs(*MF, true); 264130561Sobrien } 265104834Sobrien 266130561Sobrien for (MachineFunction::iterator I = ++MF->begin(), E = MF->end(); I != E;) { 267130561Sobrien MachineBasicBlock *MBB = &*I++; 268104834Sobrien 269130561Sobrien if (NumTails == TailDupLimit) 270130561Sobrien break; 271104834Sobrien 272218822Sdim bool IsSimple = isSimpleBB(MBB); 273218822Sdim 274218822Sdim if (!shouldTailDuplicate(IsSimple, *MBB)) 275218822Sdim continue; 276218822Sdim 277218822Sdim MadeChange |= tailDuplicateAndUpdate(IsSimple, MBB, nullptr); 278218822Sdim } 279218822Sdim 280130561Sobrien if (PreRegAlloc && TailDupVerify) 281130561Sobrien VerifyPHIs(*MF, false); 282130561Sobrien 283104834Sobrien return MadeChange; 284130561Sobrien} 285130561Sobrien 286130561Sobrienstatic bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB, 287104834Sobrien const MachineRegisterInfo *MRI) { 288130561Sobrien for (MachineInstr &UseMI : MRI->use_instructions(Reg)) { 289130561Sobrien if (UseMI.isDebugValue()) 290130561Sobrien continue; 291130561Sobrien if (UseMI.getParent() != BB) 292130561Sobrien return true; 293130561Sobrien } 294130561Sobrien return false; 295130561Sobrien} 296130561Sobrien 297130561Sobrienstatic unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { 298130561Sobrien for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) 299130561Sobrien if (MI->getOperand(i + 1).getMBB() == SrcBB) 300130561Sobrien return i; 301130561Sobrien return 0; 302130561Sobrien} 303130561Sobrien 304130561Sobrien// Remember which registers are used by phis in this block. This is 305130561Sobrien// used to determine which registers are liveout while modifying the 306130561Sobrien// block (which is why we need to copy the information). 307130561Sobrienstatic void getRegsUsedByPHIs(const MachineBasicBlock &BB, 308130561Sobrien DenseSet<unsigned> *UsedByPhi) { 309130561Sobrien for (const auto &MI : BB) { 310130561Sobrien if (!MI.isPHI()) 311130561Sobrien break; 312130561Sobrien for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 313130561Sobrien unsigned SrcReg = MI.getOperand(i).getReg(); 314130561Sobrien UsedByPhi->insert(SrcReg); 315130561Sobrien } 316130561Sobrien } 317130561Sobrien} 318130561Sobrien 319130561Sobrien/// Add a definition and source virtual registers pair for SSA update. 320218822Sdimvoid TailDuplicator::addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg, 321218822Sdim MachineBasicBlock *BB) { 322218822Sdim DenseMap<unsigned, AvailableValsTy>::iterator LI = 323218822Sdim SSAUpdateVals.find(OrigReg); 324218822Sdim if (LI != SSAUpdateVals.end()) 325218822Sdim LI->second.push_back(std::make_pair(BB, NewReg)); 326218822Sdim else { 327218822Sdim AvailableValsTy Vals; 328218822Sdim Vals.push_back(std::make_pair(BB, NewReg)); 329218822Sdim SSAUpdateVals.insert(std::make_pair(OrigReg, Vals)); 330218822Sdim SSAUpdateVRs.push_back(OrigReg); 331218822Sdim } 332218822Sdim} 333218822Sdim 334218822Sdim/// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the 335218822Sdim/// source register that's contributed by PredBB and update SSA update map. 336218822Sdimvoid TailDuplicator::processPHI( 337218822Sdim MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB, 338218822Sdim DenseMap<unsigned, RegSubRegPair> &LocalVRMap, 339218822Sdim SmallVectorImpl<std::pair<unsigned, RegSubRegPair>> &Copies, 340218822Sdim const DenseSet<unsigned> &RegsUsedByPhi, bool Remove) { 341218822Sdim unsigned DefReg = MI->getOperand(0).getReg(); 342218822Sdim unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB); 343218822Sdim assert(SrcOpIdx && "Unable to find matching PHI source?"); 344218822Sdim unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg(); 345218822Sdim unsigned SrcSubReg = MI->getOperand(SrcOpIdx).getSubReg(); 346218822Sdim const TargetRegisterClass *RC = MRI->getRegClass(DefReg); 347218822Sdim LocalVRMap.insert(std::make_pair(DefReg, RegSubRegPair(SrcReg, SrcSubReg))); 348218822Sdim 349218822Sdim // Insert a copy from source to the end of the block. The def register is the 350130561Sobrien // available value liveout of the block. 351130561Sobrien unsigned NewDef = MRI->createVirtualRegister(RC); 352130561Sobrien Copies.push_back(std::make_pair(NewDef, RegSubRegPair(SrcReg, SrcSubReg))); 353130561Sobrien if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg)) 354130561Sobrien addSSAUpdateEntry(DefReg, NewDef, PredBB); 355130561Sobrien 356130561Sobrien if (!Remove) 357130561Sobrien return; 358130561Sobrien 359130561Sobrien // Remove PredBB from the PHI node. 360130561Sobrien MI->RemoveOperand(SrcOpIdx + 1); 36133965Sjdp MI->RemoveOperand(SrcOpIdx); 36233965Sjdp if (MI->getNumOperands() == 1) 363104834Sobrien MI->eraseFromParent(); 36433965Sjdp} 36533965Sjdp 366104834Sobrien/// Duplicate a TailBB instruction to PredBB and update 367130561Sobrien/// the source operands due to earlier PHI translation. 368130561Sobrienvoid TailDuplicator::duplicateInstruction( 369130561Sobrien MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB, 370104834Sobrien DenseMap<unsigned, RegSubRegPair> &LocalVRMap, 371130561Sobrien const DenseSet<unsigned> &UsedByPhi) { 372130561Sobrien MachineInstr *NewMI = TII->duplicate(*MI, *MF); 373130561Sobrien if (PreRegAlloc) { 374130561Sobrien for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { 375104834Sobrien MachineOperand &MO = NewMI->getOperand(i); 376130561Sobrien if (!MO.isReg()) 377130561Sobrien continue; 378104834Sobrien unsigned Reg = MO.getReg(); 37933965Sjdp if (!TargetRegisterInfo::isVirtualRegister(Reg)) 38033965Sjdp continue; 381104834Sobrien if (MO.isDef()) { 38233965Sjdp const TargetRegisterClass *RC = MRI->getRegClass(Reg); 38333965Sjdp unsigned NewReg = MRI->createVirtualRegister(RC); 38433965Sjdp MO.setReg(NewReg); 385104834Sobrien LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0))); 38633965Sjdp if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg)) 387130561Sobrien addSSAUpdateEntry(Reg, NewReg, PredBB); 38833965Sjdp } else { 38933965Sjdp auto VI = LocalVRMap.find(Reg); 390104834Sobrien if (VI != LocalVRMap.end()) { 39133965Sjdp // Need to make sure that the register class of the mapped register 39233965Sjdp // will satisfy the constraints of the class of the register being 39333965Sjdp // replaced. 394104834Sobrien auto *OrigRC = MRI->getRegClass(Reg); 395130561Sobrien auto *MappedRC = MRI->getRegClass(VI->second.Reg); 396130561Sobrien const TargetRegisterClass *ConstrRC; 397130561Sobrien if (VI->second.SubReg != 0) { 398218822Sdim ConstrRC = TRI->getMatchingSuperRegClass(MappedRC, OrigRC, 399130561Sobrien VI->second.SubReg); 400130561Sobrien if (ConstrRC) { 401130561Sobrien // The actual constraining (as in "find appropriate new class") 402130561Sobrien // is done by getMatchingSuperRegClass, so now we only need to 403130561Sobrien // change the class of the mapped register. 404130561Sobrien MRI->setRegClass(VI->second.Reg, ConstrRC); 405130561Sobrien } 406130561Sobrien } else { 407130561Sobrien // For mapped registers that do not have sub-registers, simply 408130561Sobrien // restrict their class to match the original one. 409130561Sobrien ConstrRC = MRI->constrainRegClass(VI->second.Reg, OrigRC); 410130561Sobrien } 41133965Sjdp 412130561Sobrien if (ConstrRC) { 41360484Sobrien // If the class constraining succeeded, we can simply replace 41460484Sobrien // the old register with the mapped one. 41560484Sobrien MO.setReg(VI->second.Reg); 41660484Sobrien // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a 417104834Sobrien // sub-register, we need to compose the sub-register indices. 41860484Sobrien MO.setSubReg(TRI->composeSubRegIndices(MO.getSubReg(), 41960484Sobrien VI->second.SubReg)); 42060484Sobrien } else { 42177298Sobrien // The direct replacement is not possible, due to failing register 422218822Sdim // class constraints. An explicit COPY is necessary. Create one 423218822Sdim // that can be reused 424218822Sdim auto *NewRC = MI->getRegClassConstraint(i, TII, TRI); 425218822Sdim if (NewRC == nullptr) 426218822Sdim NewRC = OrigRC; 427218822Sdim unsigned NewReg = MRI->createVirtualRegister(NewRC); 428218822Sdim BuildMI(*PredBB, MI, MI->getDebugLoc(), 429218822Sdim TII->get(TargetOpcode::COPY), NewReg) 430218822Sdim .addReg(VI->second.Reg, 0, VI->second.SubReg); 431218822Sdim LocalVRMap.erase(VI); 432218822Sdim LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0))); 433130561Sobrien MO.setReg(NewReg); 434104834Sobrien // The composed VI.Reg:VI.SubReg is replaced with NewReg, which 435104834Sobrien // is equivalent to the whole register Reg. Hence, Reg:subreg 436104834Sobrien // is same as NewReg:subreg, so keep the sub-register index 43789857Sobrien // unchanged. 438130561Sobrien } 439130561Sobrien // Clear any kill flags from this operand. The new register could 440130561Sobrien // have uses after this one, so kills are not valid here. 441130561Sobrien MO.setIsKill(false); 44289857Sobrien } 443130561Sobrien } 444130561Sobrien } 44589857Sobrien } 446130561Sobrien PredBB->insert(PredBB->instr_end(), NewMI); 447130561Sobrien} 44889857Sobrien 449130561Sobrien/// After FromBB is tail duplicated into its predecessor blocks, the successors 450130561Sobrien/// have gained new predecessors. Update the PHI instructions in them 451218822Sdim/// accordingly. 452218822Sdimvoid TailDuplicator::updateSuccessorsPHIs( 453218822Sdim MachineBasicBlock *FromBB, bool isDead, 454218822Sdim SmallVectorImpl<MachineBasicBlock *> &TDBBs, 455218822Sdim SmallSetVector<MachineBasicBlock *, 8> &Succs) { 456218822Sdim for (MachineBasicBlock *SuccBB : Succs) { 45733965Sjdp for (MachineInstr &MI : *SuccBB) { 45833965Sjdp if (!MI.isPHI()) 459218822Sdim break; 460218822Sdim MachineInstrBuilder MIB(*FromBB->getParent(), MI); 461218822Sdim unsigned Idx = 0; 462218822Sdim for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { 463218822Sdim MachineOperand &MO = MI.getOperand(i + 1); 464218822Sdim if (MO.getMBB() == FromBB) { 46533965Sjdp Idx = i; 46633965Sjdp break; 46733965Sjdp } 46833965Sjdp } 46933965Sjdp 47033965Sjdp assert(Idx != 0); 47133965Sjdp MachineOperand &MO0 = MI.getOperand(Idx); 472130561Sobrien unsigned Reg = MO0.getReg(); 473130561Sobrien if (isDead) { 47433965Sjdp // Folded into the previous BB. 47533965Sjdp // There could be duplicate phi source entries. FIXME: Should sdisel 47633965Sjdp // or earlier pass fixed this? 47733965Sjdp for (unsigned i = MI.getNumOperands() - 2; i != Idx; i -= 2) { 47833965Sjdp MachineOperand &MO = MI.getOperand(i + 1); 47933965Sjdp if (MO.getMBB() == FromBB) { 480130561Sobrien MI.RemoveOperand(i + 1); 481130561Sobrien MI.RemoveOperand(i); 482130561Sobrien } 483130561Sobrien } 48433965Sjdp } else 48533965Sjdp Idx = 0; 48633965Sjdp 48733965Sjdp // If Idx is set, the operands at Idx and Idx+1 must be removed. 48833965Sjdp // We reuse the location to avoid expensive RemoveOperand calls. 48933965Sjdp 49033965Sjdp DenseMap<unsigned, AvailableValsTy>::iterator LI = 49133965Sjdp SSAUpdateVals.find(Reg); 49233965Sjdp if (LI != SSAUpdateVals.end()) { 49333965Sjdp // This register is defined in the tail block. 49433965Sjdp for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) { 495130561Sobrien MachineBasicBlock *SrcBB = LI->second[j].first; 496130561Sobrien // If we didn't duplicate a bb into a particular predecessor, we 497130561Sobrien // might still have added an entry to SSAUpdateVals to correcly 498130561Sobrien // recompute SSA. If that case, avoid adding a dummy extra argument 49933965Sjdp // this PHI. 50033965Sjdp if (!SrcBB->isSuccessor(SuccBB)) 50133965Sjdp continue; 502130561Sobrien 50333965Sjdp unsigned SrcReg = LI->second[j].second; 50433965Sjdp if (Idx != 0) { 505130561Sobrien MI.getOperand(Idx).setReg(SrcReg); 506130561Sobrien MI.getOperand(Idx + 1).setMBB(SrcBB); 507130561Sobrien Idx = 0; 50833965Sjdp } else { 50933965Sjdp MIB.addReg(SrcReg).addMBB(SrcBB); 510130561Sobrien } 51133965Sjdp } 512130561Sobrien } else { 51333965Sjdp // Live in tail block, must also be live in predecessors. 514130561Sobrien for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) { 515130561Sobrien MachineBasicBlock *SrcBB = TDBBs[j]; 516130561Sobrien if (Idx != 0) { 51733965Sjdp MI.getOperand(Idx).setReg(Reg); 51833965Sjdp MI.getOperand(Idx + 1).setMBB(SrcBB); 51933965Sjdp Idx = 0; 52033965Sjdp } else { 52133965Sjdp MIB.addReg(Reg).addMBB(SrcBB); 52233965Sjdp } 52333965Sjdp } 524130561Sobrien } 525130561Sobrien if (Idx != 0) { 526130561Sobrien MI.RemoveOperand(Idx + 1); 52733965Sjdp MI.RemoveOperand(Idx); 52833965Sjdp } 52933965Sjdp } 53060484Sobrien } 53160484Sobrien} 532130561Sobrien 533130561Sobrien/// Determine if it is profitable to duplicate this block. 534130561Sobrienbool TailDuplicator::shouldTailDuplicate(bool IsSimple, 535218822Sdim MachineBasicBlock &TailBB) { 536218822Sdim // When doing tail-duplication during layout, the block ordering is in flux, 537218822Sdim // so canFallThrough returns a result based on incorrect information and 538218822Sdim // should just be ignored. 539218822Sdim if (!LayoutMode && TailBB.canFallThrough()) 54033965Sjdp return false; 54133965Sjdp 54233965Sjdp // Don't try to tail-duplicate single-block loops. 543130561Sobrien if (TailBB.isSuccessor(&TailBB)) 544218822Sdim return false; 545218822Sdim 546218822Sdim // Set the limit on the cost to duplicate. When optimizing for size, 54733965Sjdp // duplicate only one, because one branch instruction can be eliminated to 548218822Sdim // compensate for the duplication. 54933965Sjdp unsigned MaxDuplicateCount; 55033965Sjdp if (TailDupSize == 0 && 55133965Sjdp TailDuplicateSize.getNumOccurrences() == 0 && 55233965Sjdp MF->getFunction()->optForSize()) 553130561Sobrien MaxDuplicateCount = 1; 554130561Sobrien else if (TailDupSize == 0) 555130561Sobrien MaxDuplicateCount = TailDuplicateSize; 55633965Sjdp else 55733965Sjdp MaxDuplicateCount = TailDupSize; 55833965Sjdp 55933965Sjdp // If the block to be duplicated ends in an unanalyzable fallthrough, don't 56033965Sjdp // duplicate it. 56133965Sjdp // A similar check is necessary in MachineBlockPlacement to make sure pairs of 562130561Sobrien // blocks with unanalyzable fallthrough get layed out contiguously. 563130561Sobrien MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 564130561Sobrien SmallVector<MachineOperand, 4> PredCond; 56533965Sjdp if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond) && 56633965Sjdp TailBB.canFallThrough()) 56733965Sjdp return false; 56833965Sjdp 569130561Sobrien // If the target has hardware branch prediction that can handle indirect 570130561Sobrien // branches, duplicating them can often make them predictable when there 571130561Sobrien // are common paths through the code. The limit needs to be high enough 572218822Sdim // to allow undoing the effects of tail merging and other optimizations 573218822Sdim // that rearrange the predecessors of the indirect branch. 574218822Sdim 575218822Sdim bool HasIndirectbr = false; 576218822Sdim if (!TailBB.empty()) 577218822Sdim HasIndirectbr = TailBB.back().isIndirectBranch(); 578218822Sdim 579218822Sdim if (HasIndirectbr && PreRegAlloc) 580218822Sdim MaxDuplicateCount = TailDupIndirectBranchSize; 581218822Sdim 582218822Sdim // Check the instructions in the block to determine whether tail-duplication 583218822Sdim // is invalid or unlikely to be profitable. 584218822Sdim unsigned InstrCount = 0; 585218822Sdim for (MachineInstr &MI : TailBB) { 586218822Sdim // Non-duplicable things shouldn't be tail-duplicated. 587218822Sdim if (MI.isNotDuplicable()) 58833965Sjdp return false; 58933965Sjdp 59033965Sjdp // Convergent instructions can be duplicated only if doing so doesn't add 59133965Sjdp // new control dependencies, which is what we're going to do here. 59233965Sjdp if (MI.isConvergent()) 59333965Sjdp return false; 59433965Sjdp 59533965Sjdp // Do not duplicate 'return' instructions if this is a pre-regalloc run. 59633965Sjdp // A return may expand into a lot more instructions (e.g. reload of callee 59733965Sjdp // saved registers) after PEI. 59833965Sjdp if (PreRegAlloc && MI.isReturn()) 59933965Sjdp return false; 60033965Sjdp 60133965Sjdp // Avoid duplicating calls before register allocation. Calls presents a 60233965Sjdp // barrier to register allocation so duplicating them may end up increasing 60333965Sjdp // spills. 60433965Sjdp if (PreRegAlloc && MI.isCall()) 605218822Sdim return false; 60633965Sjdp 607130561Sobrien if (!MI.isPHI() && !MI.isDebugValue()) 60833965Sjdp InstrCount += 1; 60933965Sjdp 61033965Sjdp if (InstrCount > MaxDuplicateCount) 61133965Sjdp return false; 61233965Sjdp } 61333965Sjdp 614130561Sobrien // Check if any of the successors of TailBB has a PHI node in which the 61533965Sjdp // value corresponding to TailBB uses a subregister. 61633965Sjdp // If a phi node uses a register paired with a subregister, the actual 61733965Sjdp // "value type" of the phi may differ from the type of the register without 618130561Sobrien // any subregisters. Due to a bug, tail duplication may add a new operand 61933965Sjdp // without a necessary subregister, producing an invalid code. This is 620130561Sobrien // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll. 62133965Sjdp // Disable tail duplication for this case for now, until the problem is 62233965Sjdp // fixed. 62333965Sjdp for (auto SB : TailBB.successors()) { 62433965Sjdp for (auto &I : *SB) { 625218822Sdim if (!I.isPHI()) 62633965Sjdp break; 62733965Sjdp unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB); 62833965Sjdp assert(Idx != 0); 62933965Sjdp MachineOperand &PU = I.getOperand(Idx); 63033965Sjdp if (PU.getSubReg() != 0) 63133965Sjdp return false; 632104834Sobrien } 633104834Sobrien } 634104834Sobrien 635104834Sobrien if (HasIndirectbr && PreRegAlloc) 636104834Sobrien return true; 637104834Sobrien 63833965Sjdp if (IsSimple) 63933965Sjdp return true; 64033965Sjdp 64133965Sjdp if (!PreRegAlloc) 64233965Sjdp return true; 64333965Sjdp 64433965Sjdp return canCompletelyDuplicateBB(TailBB); 64533965Sjdp} 64633965Sjdp 64733965Sjdp/// True if this BB has only one unconditional jump. 64833965Sjdpbool TailDuplicator::isSimpleBB(MachineBasicBlock *TailBB) { 64933965Sjdp if (TailBB->succ_size() != 1) 65033965Sjdp return false; 65133965Sjdp if (TailBB->pred_empty()) 65233965Sjdp return false; 65333965Sjdp MachineBasicBlock::iterator I = TailBB->getFirstNonDebugInstr(); 65433965Sjdp if (I == TailBB->end()) 65533965Sjdp return true; 65633965Sjdp return I->isUnconditionalBranch(); 65733965Sjdp} 65833965Sjdp 65933965Sjdpstatic bool bothUsedInPHI(const MachineBasicBlock &A, 66033965Sjdp const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) { 66133965Sjdp for (MachineBasicBlock *BB : A.successors()) 66233965Sjdp if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI()) 66333965Sjdp return true; 66433965Sjdp 66533965Sjdp return false; 66633965Sjdp} 66733965Sjdp 66833965Sjdpbool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) { 66933965Sjdp for (MachineBasicBlock *PredBB : BB.predecessors()) { 67033965Sjdp if (PredBB->succ_size() > 1) 67133965Sjdp return false; 67233965Sjdp 67333965Sjdp MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 67433965Sjdp SmallVector<MachineOperand, 4> PredCond; 67533965Sjdp if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond)) 67633965Sjdp return false; 67733965Sjdp 67833965Sjdp if (!PredCond.empty()) 67933965Sjdp return false; 68033965Sjdp } 68133965Sjdp return true; 68233965Sjdp} 68333965Sjdp 68433965Sjdpbool TailDuplicator::duplicateSimpleBB( 68533965Sjdp MachineBasicBlock *TailBB, SmallVectorImpl<MachineBasicBlock *> &TDBBs, 68633965Sjdp const DenseSet<unsigned> &UsedByPhi, 687130561Sobrien SmallVectorImpl<MachineInstr *> &Copies) { 68833965Sjdp SmallPtrSet<MachineBasicBlock *, 8> Succs(TailBB->succ_begin(), 68933965Sjdp TailBB->succ_end()); 69033965Sjdp SmallVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(), 69133965Sjdp TailBB->pred_end()); 69233965Sjdp bool Changed = false; 69333965Sjdp for (MachineBasicBlock *PredBB : Preds) { 694130561Sobrien if (PredBB->hasEHPadSuccessor()) 69533965Sjdp continue; 69633965Sjdp 69733965Sjdp if (bothUsedInPHI(*PredBB, Succs)) 698130561Sobrien continue; 69933965Sjdp 700130561Sobrien MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 70160484Sobrien SmallVector<MachineOperand, 4> PredCond; 702130561Sobrien if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond)) 703130561Sobrien continue; 704104834Sobrien 705130561Sobrien Changed = true; 706104834Sobrien DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 707104834Sobrien << "From simple Succ: " << *TailBB); 708130561Sobrien 709130561Sobrien MachineBasicBlock *NewTarget = *TailBB->succ_begin(); 710130561Sobrien MachineBasicBlock *NextBB = PredBB->getNextNode(); 711130561Sobrien 712130561Sobrien // Make PredFBB explicit. 71333965Sjdp if (PredCond.empty()) 71433965Sjdp PredFBB = PredTBB; 715130561Sobrien 716130561Sobrien // Make fall through explicit. 717130561Sobrien if (!PredTBB) 718130561Sobrien PredTBB = NextBB; 719130561Sobrien if (!PredFBB) 720130561Sobrien PredFBB = NextBB; 721130561Sobrien 722130561Sobrien // Redirect 723130561Sobrien if (PredFBB == TailBB) 724130561Sobrien PredFBB = NewTarget; 725130561Sobrien if (PredTBB == TailBB) 726130561Sobrien PredTBB = NewTarget; 72733965Sjdp 72833965Sjdp // Make the branch unconditional if possible 72933965Sjdp if (PredTBB == PredFBB) { 73033965Sjdp PredCond.clear(); 73133965Sjdp PredFBB = nullptr; 73233965Sjdp } 73333965Sjdp 73433965Sjdp // Avoid adding fall through branches. 73533965Sjdp if (PredFBB == NextBB) 73633965Sjdp PredFBB = nullptr; 73733965Sjdp if (PredTBB == NextBB && PredFBB == nullptr) 73833965Sjdp PredTBB = nullptr; 73933965Sjdp 74033965Sjdp auto DL = PredBB->findBranchDebugLoc(); 74133965Sjdp TII->removeBranch(*PredBB); 74233965Sjdp 74333965Sjdp if (!PredBB->isSuccessor(NewTarget)) 74433965Sjdp PredBB->replaceSuccessor(TailBB, NewTarget); 74533965Sjdp else { 74633965Sjdp PredBB->removeSuccessor(TailBB, true); 74733965Sjdp assert(PredBB->succ_size() <= 1); 748130561Sobrien } 74933965Sjdp 750130561Sobrien if (PredTBB) 75133965Sjdp TII->insertBranch(*PredBB, PredTBB, PredFBB, PredCond, DL); 75233965Sjdp 75333965Sjdp TDBBs.push_back(PredBB); 75433965Sjdp } 75533965Sjdp return Changed; 75633965Sjdp} 757130561Sobrien 758130561Sobrienbool TailDuplicator::canTailDuplicate(MachineBasicBlock *TailBB, 759130561Sobrien MachineBasicBlock *PredBB) { 760130561Sobrien // EH edges are ignored by analyzeBranch. 76133965Sjdp if (PredBB->succ_size() > 1) 76233965Sjdp return false; 763218822Sdim 764218822Sdim MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 765218822Sdim SmallVector<MachineOperand, 4> PredCond; 766218822Sdim if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond)) 767218822Sdim return false; 768218822Sdim if (!PredCond.empty()) 769218822Sdim return false; 770218822Sdim return true; 77133965Sjdp} 772 773/// If it is profitable, duplicate TailBB's contents in each 774/// of its predecessors. 775/// \p IsSimple result of isSimpleBB 776/// \p TailBB Block to be duplicated. 777/// \p ForcedLayoutPred When non-null, use this block as the layout predecessor 778/// instead of the previous block in MF's order. 779/// \p TDBBs A vector to keep track of all blocks tail-duplicated 780/// into. 781/// \p Copies A vector of copy instructions inserted. Used later to 782/// walk all the inserted copies and remove redundant ones. 783bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB, 784 MachineBasicBlock *ForcedLayoutPred, 785 SmallVectorImpl<MachineBasicBlock *> &TDBBs, 786 SmallVectorImpl<MachineInstr *> &Copies) { 787 DEBUG(dbgs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n'); 788 789 DenseSet<unsigned> UsedByPhi; 790 getRegsUsedByPHIs(*TailBB, &UsedByPhi); 791 792 if (IsSimple) 793 return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi, Copies); 794 795 // Iterate through all the unique predecessors and tail-duplicate this 796 // block into them, if possible. Copying the list ahead of time also 797 // avoids trouble with the predecessor list reallocating. 798 bool Changed = false; 799 SmallSetVector<MachineBasicBlock *, 8> Preds(TailBB->pred_begin(), 800 TailBB->pred_end()); 801 for (MachineBasicBlock *PredBB : Preds) { 802 assert(TailBB != PredBB && 803 "Single-block loop should have been rejected earlier!"); 804 805 if (!canTailDuplicate(TailBB, PredBB)) 806 continue; 807 808 // Don't duplicate into a fall-through predecessor (at least for now). 809 bool IsLayoutSuccessor = false; 810 if (ForcedLayoutPred) 811 IsLayoutSuccessor = (ForcedLayoutPred == PredBB); 812 else if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) 813 IsLayoutSuccessor = true; 814 if (IsLayoutSuccessor) 815 continue; 816 817 DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB 818 << "From Succ: " << *TailBB); 819 820 TDBBs.push_back(PredBB); 821 822 // Remove PredBB's unconditional branch. 823 TII->removeBranch(*PredBB); 824 825 // Clone the contents of TailBB into PredBB. 826 DenseMap<unsigned, RegSubRegPair> LocalVRMap; 827 SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos; 828 // Use instr_iterator here to properly handle bundles, e.g. 829 // ARM Thumb2 IT block. 830 MachineBasicBlock::instr_iterator I = TailBB->instr_begin(); 831 while (I != TailBB->instr_end()) { 832 MachineInstr *MI = &*I; 833 ++I; 834 if (MI->isPHI()) { 835 // Replace the uses of the def of the PHI with the register coming 836 // from PredBB. 837 processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true); 838 } else { 839 // Replace def of virtual registers with new registers, and update 840 // uses with PHI source register or the new registers. 841 duplicateInstruction(MI, TailBB, PredBB, LocalVRMap, UsedByPhi); 842 } 843 } 844 appendCopies(PredBB, CopyInfos, Copies); 845 846 // Simplify 847 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; 848 SmallVector<MachineOperand, 4> PredCond; 849 TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond); 850 851 NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch 852 853 // Update the CFG. 854 PredBB->removeSuccessor(PredBB->succ_begin()); 855 assert(PredBB->succ_empty() && 856 "TailDuplicate called on block with multiple successors!"); 857 for (MachineBasicBlock *Succ : TailBB->successors()) 858 PredBB->addSuccessor(Succ, MBPI->getEdgeProbability(TailBB, Succ)); 859 860 Changed = true; 861 ++NumTailDups; 862 } 863 864 // If TailBB was duplicated into all its predecessors except for the prior 865 // block, which falls through unconditionally, move the contents of this 866 // block into the prior block. 867 MachineBasicBlock *PrevBB = ForcedLayoutPred; 868 if (!PrevBB) 869 PrevBB = &*std::prev(TailBB->getIterator()); 870 MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr; 871 SmallVector<MachineOperand, 4> PriorCond; 872 // This has to check PrevBB->succ_size() because EH edges are ignored by 873 // analyzeBranch. 874 if (PrevBB->succ_size() == 1 && 875 // Layout preds are not always CFG preds. Check. 876 *PrevBB->succ_begin() == TailBB && 877 !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond) && 878 PriorCond.empty() && 879 (!PriorTBB || PriorTBB == TailBB) && 880 TailBB->pred_size() == 1 && 881 !TailBB->hasAddressTaken()) { 882 DEBUG(dbgs() << "\nMerging into block: " << *PrevBB 883 << "From MBB: " << *TailBB); 884 // There may be a branch to the layout successor. This is unlikely but it 885 // happens. The correct thing to do is to remove the branch before 886 // duplicating the instructions in all cases. 887 TII->removeBranch(*PrevBB); 888 if (PreRegAlloc) { 889 DenseMap<unsigned, RegSubRegPair> LocalVRMap; 890 SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos; 891 MachineBasicBlock::iterator I = TailBB->begin(); 892 // Process PHI instructions first. 893 while (I != TailBB->end() && I->isPHI()) { 894 // Replace the uses of the def of the PHI with the register coming 895 // from PredBB. 896 MachineInstr *MI = &*I++; 897 processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi, true); 898 } 899 900 // Now copy the non-PHI instructions. 901 while (I != TailBB->end()) { 902 // Replace def of virtual registers with new registers, and update 903 // uses with PHI source register or the new registers. 904 MachineInstr *MI = &*I++; 905 assert(!MI->isBundle() && "Not expecting bundles before regalloc!"); 906 duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi); 907 MI->eraseFromParent(); 908 } 909 appendCopies(PrevBB, CopyInfos, Copies); 910 } else { 911 TII->removeBranch(*PrevBB); 912 // No PHIs to worry about, just splice the instructions over. 913 PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); 914 } 915 PrevBB->removeSuccessor(PrevBB->succ_begin()); 916 assert(PrevBB->succ_empty()); 917 PrevBB->transferSuccessors(TailBB); 918 TDBBs.push_back(PrevBB); 919 Changed = true; 920 } 921 922 // If this is after register allocation, there are no phis to fix. 923 if (!PreRegAlloc) 924 return Changed; 925 926 // If we made no changes so far, we are safe. 927 if (!Changed) 928 return Changed; 929 930 // Handle the nasty case in that we duplicated a block that is part of a loop 931 // into some but not all of its predecessors. For example: 932 // 1 -> 2 <-> 3 | 933 // \ | 934 // \---> rest | 935 // if we duplicate 2 into 1 but not into 3, we end up with 936 // 12 -> 3 <-> 2 -> rest | 937 // \ / | 938 // \----->-----/ | 939 // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced 940 // with a phi in 3 (which now dominates 2). 941 // What we do here is introduce a copy in 3 of the register defined by the 942 // phi, just like when we are duplicating 2 into 3, but we don't copy any 943 // real instructions or remove the 3 -> 2 edge from the phi in 2. 944 for (MachineBasicBlock *PredBB : Preds) { 945 if (is_contained(TDBBs, PredBB)) 946 continue; 947 948 // EH edges 949 if (PredBB->succ_size() != 1) 950 continue; 951 952 DenseMap<unsigned, RegSubRegPair> LocalVRMap; 953 SmallVector<std::pair<unsigned, RegSubRegPair>, 4> CopyInfos; 954 MachineBasicBlock::iterator I = TailBB->begin(); 955 // Process PHI instructions first. 956 while (I != TailBB->end() && I->isPHI()) { 957 // Replace the uses of the def of the PHI with the register coming 958 // from PredBB. 959 MachineInstr *MI = &*I++; 960 processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false); 961 } 962 appendCopies(PredBB, CopyInfos, Copies); 963 } 964 965 return Changed; 966} 967 968/// At the end of the block \p MBB generate COPY instructions between registers 969/// described by \p CopyInfos. Append resulting instructions to \p Copies. 970void TailDuplicator::appendCopies(MachineBasicBlock *MBB, 971 SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos, 972 SmallVectorImpl<MachineInstr*> &Copies) { 973 MachineBasicBlock::iterator Loc = MBB->getFirstTerminator(); 974 const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY); 975 for (auto &CI : CopyInfos) { 976 auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first) 977 .addReg(CI.second.Reg, 0, CI.second.SubReg); 978 Copies.push_back(C); 979 } 980} 981 982/// Remove the specified dead machine basic block from the function, updating 983/// the CFG. 984void TailDuplicator::removeDeadBlock( 985 MachineBasicBlock *MBB, 986 function_ref<void(MachineBasicBlock *)> *RemovalCallback) { 987 assert(MBB->pred_empty() && "MBB must be dead!"); 988 DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); 989 990 if (RemovalCallback) 991 (*RemovalCallback)(MBB); 992 993 // Remove all successors. 994 while (!MBB->succ_empty()) 995 MBB->removeSuccessor(MBB->succ_end() - 1); 996 997 // Remove the block. 998 MBB->eraseFromParent(); 999} 1000