Index: include/llvm/CodeGen/MachineBasicBlock.h =================================================================== --- include/llvm/CodeGen/MachineBasicBlock.h +++ include/llvm/CodeGen/MachineBasicBlock.h @@ -21,7 +21,6 @@ namespace llvm { -class Pass; class BasicBlock; class MachineFunction; class MCSymbol; @@ -472,14 +471,6 @@ iterator getLastNonDebugInstr(); const_iterator getLastNonDebugInstr() const; - /// SplitCriticalEdge - Split the critical edge from this block to the - /// given successor block, and return the newly created block, or null - /// if splitting is not possible. - /// - /// This function updates LiveVariables, MachineDominatorTree, and - /// MachineLoopInfo, as applicable. - MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P); - void pop_front() { Insts.pop_front(); } void pop_back() { Insts.pop_back(); } void push_back(MachineInstr *MI) { Insts.push_back(MI); } Index: include/llvm/CodeGen/SplitCriticalEdge.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/SplitCriticalEdge.h @@ -0,0 +1,32 @@ +//===-- llvm/CodeGen/SplitCriticalEdge.h ------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares a function that splits a critical edge from a basic block. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_SPLITCRITICALEDGE_H +#define LLVM_CODEGEN_SPLITCRITICALEDGE_H + +namespace llvm { + +class Pass; +class MachineBasicBlock; + +/// Split the critical edge from the block BB to the given successor block, and +/// return the newly created block, or null if splitting is not possible. +/// +/// This function updates LiveVariables, MachineDominatorTree, and +/// MachineLoopInfo, as applicable. +MachineBasicBlock *splitCriticalEdge(MachineBasicBlock *BB, + MachineBasicBlock *Succ, Pass *P); + +} // End namespace llvm + +#endif Index: lib/CodeGen/CMakeLists.txt =================================================================== --- lib/CodeGen/CMakeLists.txt +++ lib/CodeGen/CMakeLists.txt @@ -100,6 +100,7 @@ SjLjEHPrepare.cpp SlotIndexes.cpp SpillPlacement.cpp + SplitCriticalEdge.cpp SplitKit.cpp StackColoring.cpp StackProtector.cpp Index: lib/CodeGen/MachineBasicBlock.cpp =================================================================== --- lib/CodeGen/MachineBasicBlock.cpp +++ lib/CodeGen/MachineBasicBlock.cpp @@ -14,12 +14,8 @@ #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallString.h" -#include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/CodeGen/LiveVariables.h" -#include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstrBuilder.h" -#include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/SlotIndexes.h" #include "llvm/IR/BasicBlock.h" @@ -664,270 +660,6 @@ return FBB == nullptr; } -MachineBasicBlock * -MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { - // Splitting the critical edge to a landing pad block is non-trivial. Don't do - // it in this generic function. - if (Succ->isLandingPad()) - return nullptr; - - MachineFunction *MF = getParent(); - DebugLoc dl; // FIXME: this is nowhere - - // Performance might be harmed on HW that implements branching using exec mask - // where both sides of the branches are always executed. - if (MF->getTarget().requiresStructuredCFG()) - return nullptr; - - // We may need to update this's terminator, but we can't do that if - // AnalyzeBranch fails. If this uses a jump table, we won't touch it. - const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); - MachineBasicBlock *TBB = nullptr, *FBB = nullptr; - SmallVector Cond; - if (TII->AnalyzeBranch(*this, TBB, FBB, Cond)) - return nullptr; - - // Avoid bugpoint weirdness: A block may end with a conditional branch but - // jumps to the same MBB is either case. We have duplicate CFG edges in that - // case that we can't handle. Since this never happens in properly optimized - // code, just skip those edges. - if (TBB && TBB == FBB) { - DEBUG(dbgs() << "Won't split critical edge after degenerate BB#" - << getNumber() << '\n'); - return nullptr; - } - - MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); - MF->insert(std::next(MachineFunction::iterator(this)), NMBB); - DEBUG(dbgs() << "Splitting critical edge:" - " BB#" << getNumber() - << " -- BB#" << NMBB->getNumber() - << " -- BB#" << Succ->getNumber() << '\n'); - - LiveIntervals *LIS = P->getAnalysisIfAvailable(); - SlotIndexes *Indexes = P->getAnalysisIfAvailable(); - if (LIS) - LIS->insertMBBInMaps(NMBB); - else if (Indexes) - Indexes->insertMBBInMaps(NMBB); - - // On some targets like Mips, branches may kill virtual registers. Make sure - // that LiveVariables is properly updated after updateTerminator replaces the - // terminators. - LiveVariables *LV = P->getAnalysisIfAvailable(); - - // Collect a list of virtual registers killed by the terminators. - SmallVector KilledRegs; - if (LV) - for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); - I != E; ++I) { - MachineInstr *MI = I; - for (MachineInstr::mop_iterator OI = MI->operands_begin(), - OE = MI->operands_end(); OI != OE; ++OI) { - if (!OI->isReg() || OI->getReg() == 0 || - !OI->isUse() || !OI->isKill() || OI->isUndef()) - continue; - unsigned Reg = OI->getReg(); - if (TargetRegisterInfo::isPhysicalRegister(Reg) || - LV->getVarInfo(Reg).removeKill(MI)) { - KilledRegs.push_back(Reg); - DEBUG(dbgs() << "Removing terminator kill: " << *MI); - OI->setIsKill(false); - } - } - } - - SmallVector UsedRegs; - if (LIS) { - for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); - I != E; ++I) { - MachineInstr *MI = I; - - for (MachineInstr::mop_iterator OI = MI->operands_begin(), - OE = MI->operands_end(); OI != OE; ++OI) { - if (!OI->isReg() || OI->getReg() == 0) - continue; - - unsigned Reg = OI->getReg(); - if (std::find(UsedRegs.begin(), UsedRegs.end(), Reg) == UsedRegs.end()) - UsedRegs.push_back(Reg); - } - } - } - - ReplaceUsesOfBlockWith(Succ, NMBB); - - // If updateTerminator() removes instructions, we need to remove them from - // SlotIndexes. - SmallVector Terminators; - if (Indexes) { - for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); - I != E; ++I) - Terminators.push_back(I); - } - - updateTerminator(); - - if (Indexes) { - SmallVector NewTerminators; - for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); - I != E; ++I) - NewTerminators.push_back(I); - - for (SmallVectorImpl::iterator I = Terminators.begin(), - E = Terminators.end(); I != E; ++I) { - if (std::find(NewTerminators.begin(), NewTerminators.end(), *I) == - NewTerminators.end()) - Indexes->removeMachineInstrFromMaps(*I); - } - } - - // Insert unconditional "jump Succ" instruction in NMBB if necessary. - NMBB->addSuccessor(Succ); - if (!NMBB->isLayoutSuccessor(Succ)) { - Cond.clear(); - MF->getSubtarget().getInstrInfo()->InsertBranch(*NMBB, Succ, nullptr, Cond, - dl); - - if (Indexes) { - for (instr_iterator I = NMBB->instr_begin(), E = NMBB->instr_end(); - I != E; ++I) { - // Some instructions may have been moved to NMBB by updateTerminator(), - // so we first remove any instruction that already has an index. - if (Indexes->hasIndex(I)) - Indexes->removeMachineInstrFromMaps(I); - Indexes->insertMachineInstrInMaps(I); - } - } - } - - // Fix PHI nodes in Succ so they refer to NMBB instead of this - for (MachineBasicBlock::instr_iterator - i = Succ->instr_begin(),e = Succ->instr_end(); - i != e && i->isPHI(); ++i) - for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2) - if (i->getOperand(ni+1).getMBB() == this) - i->getOperand(ni+1).setMBB(NMBB); - - // Inherit live-ins from the successor - for (MachineBasicBlock::livein_iterator I = Succ->livein_begin(), - E = Succ->livein_end(); I != E; ++I) - NMBB->addLiveIn(*I); - - // Update LiveVariables. - const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); - if (LV) { - // Restore kills of virtual registers that were killed by the terminators. - while (!KilledRegs.empty()) { - unsigned Reg = KilledRegs.pop_back_val(); - for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) { - if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false)) - continue; - if (TargetRegisterInfo::isVirtualRegister(Reg)) - LV->getVarInfo(Reg).Kills.push_back(I); - DEBUG(dbgs() << "Restored terminator kill: " << *I); - break; - } - } - // Update relevant live-through information. - LV->addNewBlock(NMBB, this, Succ); - } - - if (LIS) { - // After splitting the edge and updating SlotIndexes, live intervals may be - // in one of two situations, depending on whether this block was the last in - // the function. If the original block was the last in the function, all live - // intervals will end prior to the beginning of the new split block. If the - // original block was not at the end of the function, all live intervals will - // extend to the end of the new split block. - - bool isLastMBB = - std::next(MachineFunction::iterator(NMBB)) == getParent()->end(); - - SlotIndex StartIndex = Indexes->getMBBEndIdx(this); - SlotIndex PrevIndex = StartIndex.getPrevSlot(); - SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB); - - // Find the registers used from NMBB in PHIs in Succ. - SmallSet PHISrcRegs; - for (MachineBasicBlock::instr_iterator - I = Succ->instr_begin(), E = Succ->instr_end(); - I != E && I->isPHI(); ++I) { - for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) { - if (I->getOperand(ni+1).getMBB() == NMBB) { - MachineOperand &MO = I->getOperand(ni); - unsigned Reg = MO.getReg(); - PHISrcRegs.insert(Reg); - if (MO.isUndef()) - continue; - - LiveInterval &LI = LIS->getInterval(Reg); - VNInfo *VNI = LI.getVNInfoAt(PrevIndex); - assert(VNI && "PHI sources should be live out of their predecessors."); - LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); - } - } - } - - MachineRegisterInfo *MRI = &getParent()->getRegInfo(); - for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { - unsigned Reg = TargetRegisterInfo::index2VirtReg(i); - if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg)) - continue; - - LiveInterval &LI = LIS->getInterval(Reg); - if (!LI.liveAt(PrevIndex)) - continue; - - bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ)); - if (isLiveOut && isLastMBB) { - VNInfo *VNI = LI.getVNInfoAt(PrevIndex); - assert(VNI && "LiveInterval should have VNInfo where it is live."); - LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); - } else if (!isLiveOut && !isLastMBB) { - LI.removeSegment(StartIndex, EndIndex); - } - } - - // Update all intervals for registers whose uses may have been modified by - // updateTerminator(). - LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs); - } - - if (MachineDominatorTree *MDT = - P->getAnalysisIfAvailable()) - MDT->recordSplitCriticalEdge(this, Succ, NMBB); - - if (MachineLoopInfo *MLI = P->getAnalysisIfAvailable()) - if (MachineLoop *TIL = MLI->getLoopFor(this)) { - // If one or the other blocks were not in a loop, the new block is not - // either, and thus LI doesn't need to be updated. - if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) { - if (TIL == DestLoop) { - // Both in the same loop, the NMBB joins loop. - DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); - } else if (TIL->contains(DestLoop)) { - // Edge from an outer loop to an inner loop. Add to the outer loop. - TIL->addBasicBlockToLoop(NMBB, MLI->getBase()); - } else if (DestLoop->contains(TIL)) { - // Edge from an inner loop to an outer loop. Add to the outer loop. - DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); - } else { - // Edge from two loops with no containment relation. Because these - // are natural loops, we know that the destination block must be the - // header of its loop (adding a branch into a loop elsewhere would - // create an irreducible loop). - assert(DestLoop->getHeader() == Succ && - "Should not create irreducible loops!"); - if (MachineLoop *P = DestLoop->getParentLoop()) - P->addBasicBlockToLoop(NMBB, MLI->getBase()); - } - } - } - - return NMBB; -} - /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's /// neighboring instructions so the bundle won't be broken by removing MI. static void unbundleSingleMI(MachineInstr *MI) { Index: lib/CodeGen/MachineLICM.cpp =================================================================== --- lib/CodeGen/MachineLICM.cpp +++ lib/CodeGen/MachineLICM.cpp @@ -27,6 +27,7 @@ #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/PseudoSourceValue.h" +#include "llvm/CodeGen/SplitCriticalEdge.h" #include "llvm/MC/MCInstrItineraries.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" @@ -1459,7 +1460,7 @@ return nullptr; } - CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), this); + CurPreheader = splitCriticalEdge(Pred, CurLoop->getHeader(), this); if (!CurPreheader) { CurPreheader = reinterpret_cast(-1); return nullptr; Index: lib/CodeGen/MachineSink.cpp =================================================================== --- lib/CodeGen/MachineSink.cpp +++ lib/CodeGen/MachineSink.cpp @@ -27,6 +27,7 @@ #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachinePostDominators.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/SplitCriticalEdge.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -275,7 +276,7 @@ // If we have anything we marked as toSplit, split it now. for (auto &Pair : ToSplit) { - auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, this); + auto NewSucc = splitCriticalEdge(Pair.first, Pair.second, this); if (NewSucc != nullptr) { DEBUG(dbgs() << " *** Splitting critical edge:" " BB#" << Pair.first->getNumber() Index: lib/CodeGen/PHIElimination.cpp =================================================================== --- lib/CodeGen/PHIElimination.cpp +++ lib/CodeGen/PHIElimination.cpp @@ -25,6 +25,7 @@ #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/SplitCriticalEdge.h" #include "llvm/IR/Function.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" @@ -612,7 +613,7 @@ } if (!ShouldSplit && !SplitAllCriticalEdges) continue; - if (!PreMBB->SplitCriticalEdge(&MBB, this)) { + if (!splitCriticalEdge(PreMBB, &MBB, this)) { DEBUG(dbgs() << "Failed to split critical edge.\n"); continue; } Index: lib/CodeGen/SplitCriticalEdge.cpp =================================================================== --- /dev/null +++ lib/CodeGen/SplitCriticalEdge.cpp @@ -0,0 +1,308 @@ +//===-- llvm/CodeGen/SplitCriticalEdge.cpp ----------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a function that splits a critical edge from a basic +// block. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/SplitCriticalEdge.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/LiveVariables.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include +using namespace llvm; + +#define DEBUG_TYPE "codegen" + +MachineBasicBlock *llvm::splitCriticalEdge(MachineBasicBlock *BB, + MachineBasicBlock *Succ, Pass *P) { + // Splitting the critical edge to a landing pad block is non-trivial. Don't do + // it in this generic function. + if (Succ->isLandingPad()) + return nullptr; + + MachineFunction *MF = BB->getParent(); + DebugLoc dl; // FIXME: this is nowhere + + // Performance might be harmed on HW that implements branching using exec mask + // where both sides of the branches are always executed. + if (MF->getTarget().requiresStructuredCFG()) + return nullptr; + + // We may need to update this's terminator, but we can't do that if + // AnalyzeBranch fails. If this uses a jump table, we won't touch it. + const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); + MachineBasicBlock *TBB = nullptr, *FBB = nullptr; + SmallVector Cond; + if (TII->AnalyzeBranch(*BB, TBB, FBB, Cond)) + return nullptr; + + // Avoid bugpoint weirdness: A block may end with a conditional branch but + // jumps to the same MBB is either case. We have duplicate CFG edges in that + // case that we can't handle. Since this never happens in properly optimized + // code, just skip those edges. + if (TBB && TBB == FBB) { + DEBUG(dbgs() << "Won't split critical edge after degenerate BB#" + << BB->getNumber() << '\n'); + return nullptr; + } + + MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); + MF->insert(std::next(MachineFunction::iterator(BB)), NMBB); + DEBUG(dbgs() << "Splitting critical edge:" + " BB#" << BB->getNumber() << " -- BB#" << NMBB->getNumber() + << " -- BB#" << Succ->getNumber() << '\n'); + + LiveIntervals *LIS = P->getAnalysisIfAvailable(); + SlotIndexes *Indexes = P->getAnalysisIfAvailable(); + if (LIS) + LIS->insertMBBInMaps(NMBB); + else if (Indexes) + Indexes->insertMBBInMaps(NMBB); + + // On some targets like Mips, branches may kill virtual registers. Make sure + // that LiveVariables is properly updated after updateTerminator replaces the + // terminators. + LiveVariables *LV = P->getAnalysisIfAvailable(); + + // Collect a list of virtual registers killed by the terminators. + SmallVector KilledRegs; + if (LV) + for (MachineBasicBlock::instr_iterator I = BB->getFirstInstrTerminator(), + E = BB->instr_end(); + I != E; ++I) { + MachineInstr *MI = I; + for (MachineInstr::mop_iterator OI = MI->operands_begin(), + OE = MI->operands_end(); + OI != OE; ++OI) { + if (!OI->isReg() || OI->getReg() == 0 || !OI->isUse() || + !OI->isKill() || OI->isUndef()) + continue; + unsigned Reg = OI->getReg(); + if (TargetRegisterInfo::isPhysicalRegister(Reg) || + LV->getVarInfo(Reg).removeKill(MI)) { + KilledRegs.push_back(Reg); + DEBUG(dbgs() << "Removing terminator kill: " << *MI); + OI->setIsKill(false); + } + } + } + + SmallVector UsedRegs; + if (LIS) { + for (MachineBasicBlock::instr_iterator I = BB->getFirstInstrTerminator(), + E = BB->instr_end(); + I != E; ++I) { + MachineInstr *MI = I; + + for (MachineInstr::mop_iterator OI = MI->operands_begin(), + OE = MI->operands_end(); + OI != OE; ++OI) { + if (!OI->isReg() || OI->getReg() == 0) + continue; + + unsigned Reg = OI->getReg(); + if (std::find(UsedRegs.begin(), UsedRegs.end(), Reg) == UsedRegs.end()) + UsedRegs.push_back(Reg); + } + } + } + + BB->ReplaceUsesOfBlockWith(Succ, NMBB); + + // If updateTerminator() removes instructions, we need to remove them from + // SlotIndexes. + SmallVector Terminators; + if (Indexes) { + for (MachineBasicBlock::instr_iterator I = BB->getFirstInstrTerminator(), + E = BB->instr_end(); + I != E; ++I) + Terminators.push_back(I); + } + + BB->updateTerminator(); + + if (Indexes) { + SmallVector NewTerminators; + for (MachineBasicBlock::instr_iterator I = BB->getFirstInstrTerminator(), + E = BB->instr_end(); + I != E; ++I) + NewTerminators.push_back(I); + + for (SmallVectorImpl::iterator I = Terminators.begin(), + E = Terminators.end(); + I != E; ++I) { + if (std::find(NewTerminators.begin(), NewTerminators.end(), *I) == + NewTerminators.end()) + Indexes->removeMachineInstrFromMaps(*I); + } + } + + // Insert unconditional "jump Succ" instruction in NMBB if necessary. + NMBB->addSuccessor(Succ); + if (!NMBB->isLayoutSuccessor(Succ)) { + Cond.clear(); + MF->getSubtarget().getInstrInfo()->InsertBranch(*NMBB, Succ, nullptr, Cond, + dl); + + if (Indexes) { + for (MachineBasicBlock::instr_iterator I = NMBB->instr_begin(), + E = NMBB->instr_end(); + I != E; ++I) { + // Some instructions may have been moved to NMBB by updateTerminator(), + // so we first remove any instruction that already has an index. + if (Indexes->hasIndex(I)) + Indexes->removeMachineInstrFromMaps(I); + Indexes->insertMachineInstrInMaps(I); + } + } + } + + // Fix PHI nodes in Succ so they refer to NMBB instead of this + for (MachineBasicBlock::instr_iterator i = Succ->instr_begin(), + e = Succ->instr_end(); + i != e && i->isPHI(); ++i) + for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2) + if (i->getOperand(ni + 1).getMBB() == BB) + i->getOperand(ni + 1).setMBB(NMBB); + + // Inherit live-ins from the successor + for (MachineBasicBlock::livein_iterator I = Succ->livein_begin(), + E = Succ->livein_end(); + I != E; ++I) + NMBB->addLiveIn(*I); + + // Update LiveVariables. + const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); + if (LV) { + // Restore kills of virtual registers that were killed by the terminators. + while (!KilledRegs.empty()) { + unsigned Reg = KilledRegs.pop_back_val(); + for (MachineBasicBlock::instr_iterator I = BB->instr_end(), + E = BB->instr_begin(); + I != E;) { + if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false)) + continue; + if (TargetRegisterInfo::isVirtualRegister(Reg)) + LV->getVarInfo(Reg).Kills.push_back(I); + DEBUG(dbgs() << "Restored terminator kill: " << *I); + break; + } + } + // Update relevant live-through information. + LV->addNewBlock(NMBB, BB, Succ); + } + + if (LIS) { + // After splitting the edge and updating SlotIndexes, live intervals may be + // in one of two situations, depending on whether this block was the last in + // the function. If the original block was the last in the function, all + // live + // intervals will end prior to the beginning of the new split block. If the + // original block was not at the end of the function, all live intervals + // will + // extend to the end of the new split block. + + bool isLastMBB = std::next(MachineFunction::iterator(NMBB)) == MF->end(); + + SlotIndex StartIndex = Indexes->getMBBEndIdx(BB); + SlotIndex PrevIndex = StartIndex.getPrevSlot(); + SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB); + + // Find the registers used from NMBB in PHIs in Succ. + SmallSet PHISrcRegs; + for (MachineBasicBlock::instr_iterator I = Succ->instr_begin(), + E = Succ->instr_end(); + I != E && I->isPHI(); ++I) { + for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) { + if (I->getOperand(ni + 1).getMBB() == NMBB) { + MachineOperand &MO = I->getOperand(ni); + unsigned Reg = MO.getReg(); + PHISrcRegs.insert(Reg); + if (MO.isUndef()) + continue; + + LiveInterval &LI = LIS->getInterval(Reg); + VNInfo *VNI = LI.getVNInfoAt(PrevIndex); + assert(VNI && + "PHI sources should be live out of their predecessors."); + LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); + } + } + } + + MachineRegisterInfo *MRI = &MF->getRegInfo(); + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg)) + continue; + + LiveInterval &LI = LIS->getInterval(Reg); + if (!LI.liveAt(PrevIndex)) + continue; + + bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ)); + if (isLiveOut && isLastMBB) { + VNInfo *VNI = LI.getVNInfoAt(PrevIndex); + assert(VNI && "LiveInterval should have VNInfo where it is live."); + LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); + } else if (!isLiveOut && !isLastMBB) { + LI.removeSegment(StartIndex, EndIndex); + } + } + + // Update all intervals for registers whose uses may have been modified by + // updateTerminator(). + LIS->repairIntervalsInRange(BB, BB->getFirstTerminator(), BB->end(), + UsedRegs); + } + + if (MachineDominatorTree *MDT = + P->getAnalysisIfAvailable()) + MDT->recordSplitCriticalEdge(BB, Succ, NMBB); + + if (MachineLoopInfo *MLI = P->getAnalysisIfAvailable()) + if (MachineLoop *TIL = MLI->getLoopFor(BB)) { + // If one or the other blocks were not in a loop, the new block is not + // either, and thus LI doesn't need to be updated. + if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) { + if (TIL == DestLoop) { + // Both in the same loop, the NMBB joins loop. + DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); + } else if (TIL->contains(DestLoop)) { + // Edge from an outer loop to an inner loop. Add to the outer loop. + TIL->addBasicBlockToLoop(NMBB, MLI->getBase()); + } else if (DestLoop->contains(TIL)) { + // Edge from an inner loop to an outer loop. Add to the outer loop. + DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); + } else { + // Edge from two loops with no containment relation. Because these + // are natural loops, we know that the destination block must be the + // header of its loop (adding a branch into a loop elsewhere would + // create an irreducible loop). + assert(DestLoop->getHeader() == Succ && + "Should not create irreducible loops!"); + if (MachineLoop *P = DestLoop->getParentLoop()) + P->addBasicBlockToLoop(NMBB, MLI->getBase()); + } + } + } + + return NMBB; +}