From f5844a75154e73a2302767eeecf3b3401e157bb3 Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Sun, 10 Feb 2013 23:29:54 +0000 Subject: Fix the unused but nearly correct method SlotIndexes::insertMBBInMaps() and add support for updating SlotIndexes to MachineBasicBlock::SplitCriticalEdge(). This calls renumberIndexes() every time; it should be improved to only renumber locally. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174851 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 7e9fb20ffe..2534a74005 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -662,6 +662,9 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { " BB#" << getNumber() << " -- BB#" << NMBB->getNumber() << " -- BB#" << Succ->getNumber() << '\n'); + SlotIndexes *Indexes = P->getAnalysisIfAvailable(); + 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 @@ -697,6 +700,17 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { if (!NMBB->isLayoutSuccessor(Succ)) { Cond.clear(); MF->getTarget().getInstrInfo()->InsertBranch(*NMBB, Succ, NULL, 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 -- cgit v1.2.3-18-g5258 From cbe3f5e1622b5f809bc04d61da125801e4658a73 Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Mon, 11 Feb 2013 09:24:45 +0000 Subject: Update SlotIndexes after updateTerminator() possibly removes instructions. I am really trying to avoid piping SlotIndexes through to RemoveBranch() and friends. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174869 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 2534a74005..7457cd5201 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -693,8 +693,32 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { } 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)) { -- cgit v1.2.3-18-g5258 From 8597c14e9b32259cc7cfd752d95fd71e7aaba0ec Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Mon, 11 Feb 2013 09:24:47 +0000 Subject: Add support for updating LiveIntervals to MachineBasicBlock::SplitCriticalEdge(). This is currently a bit hairier than it needs to be, since depending on where the split block resides the end ListEntry of the split block may be the end ListEntry of the original block or a new entry. Some changes to the SlotIndexes updating should make it possible to eliminate the two cases here. This also isn't as optimized as it could be. In the future Liveinterval should probably get a flag that indicates whether the LiveInterval is within a single basic block. We could ignore all such intervals when splitting an edge. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174870 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 68 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 68 insertions(+) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 7457cd5201..7351302cc3 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -15,10 +15,12 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallString.h" #include "llvm/Assembly/Writer.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/IR/BasicBlock.h" #include "llvm/IR/DataLayout.h" @@ -769,6 +771,72 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { LV->addNewBlock(NMBB, this, Succ); } + if (LiveIntervals *LIS = P->getAnalysisIfAvailable()) { + // 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 = + llvm::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() || !isLastMBB) + break; + + LiveInterval &LI = LIS->getInterval(Reg); + VNInfo *VNI = LI.getVNInfoAt(PrevIndex); + assert(VNI && "PHI sources should be live out of their predecessors."); + LI.addRange(LiveRange(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 = false; + for (MachineBasicBlock::succ_iterator SI = succ_begin(), + SE = succ_end(); SI != SE; ++SI) { + MachineBasicBlock *SuccMBB = *SI == NMBB ? Succ : *SI; + if (LI.liveAt(LIS->getMBBStartIdx(SuccMBB))) { + isLiveOut = true; + break; + } + } + + if (isLiveOut && isLastMBB) { + VNInfo *VNI = LI.getVNInfoAt(PrevIndex); + assert(VNI && "LiveInterval should have VNInfo where it is live."); + LI.addRange(LiveRange(StartIndex, EndIndex, VNI)); + } else if (!isLiveOut && !isLastMBB) { + LI.removeRange(StartIndex, EndIndex); + } + } + } + if (MachineDominatorTree *MDT = P->getAnalysisIfAvailable()) { // Update dominator information. -- cgit v1.2.3-18-g5258 From dbf10c4349bb746e6120ff1195c1ce7e21bebf93 Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Tue, 12 Feb 2013 03:49:17 +0000 Subject: Fix the updating of LiveIntervals after splitting a critical edge. PHI operand live ranges should always be extended, and the only successor that should be considered for extension of other ranges is the target of the split edge. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174935 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 15 +++------------ 1 file changed, 3 insertions(+), 12 deletions(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 7351302cc3..71d59f0b4b 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -796,8 +796,8 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { MachineOperand &MO = I->getOperand(ni); unsigned Reg = MO.getReg(); PHISrcRegs.insert(Reg); - if (MO.isUndef() || !isLastMBB) - break; + if (MO.isUndef()) + continue; LiveInterval &LI = LIS->getInterval(Reg); VNInfo *VNI = LI.getVNInfoAt(PrevIndex); @@ -817,16 +817,7 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { if (!LI.liveAt(PrevIndex)) continue; - bool isLiveOut = false; - for (MachineBasicBlock::succ_iterator SI = succ_begin(), - SE = succ_end(); SI != SE; ++SI) { - MachineBasicBlock *SuccMBB = *SI == NMBB ? Succ : *SI; - if (LI.liveAt(LIS->getMBBStartIdx(SuccMBB))) { - isLiveOut = true; - break; - } - } - + 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."); -- cgit v1.2.3-18-g5258 From dd58fa4869f9bff909720aaa428487a20fab1391 Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Tue, 12 Feb 2013 03:49:20 +0000 Subject: Add blocks to the LiveIntervalAnalysis RegMaskBlocks array when splitting a critical edge. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174936 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 71d59f0b4b..df1c7c2a66 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -664,8 +664,12 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { " BB#" << getNumber() << " -- BB#" << NMBB->getNumber() << " -- BB#" << Succ->getNumber() << '\n'); + + LiveIntervals *LIS = P->getAnalysisIfAvailable(); SlotIndexes *Indexes = P->getAnalysisIfAvailable(); - if (Indexes) + if (LIS) + LIS->insertMBBInMaps(NMBB); + else if (Indexes) Indexes->insertMBBInMaps(NMBB); // On some targets like Mips, branches may kill virtual registers. Make sure @@ -771,7 +775,7 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { LV->addNewBlock(NMBB, this, Succ); } - if (LiveIntervals *LIS = P->getAnalysisIfAvailable()) { + 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 -- cgit v1.2.3-18-g5258 From f0b2535344e8c9e2912da78010918a44c5a18cab Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Sun, 17 Feb 2013 00:10:44 +0000 Subject: Add support for updating the LiveIntervals of registers used by 'exotic' terminators that actually have register uses when splitting critical edges. This commit also introduces a method repairIntervalsInRange() on LiveIntervals, which allows for repairing LiveIntervals in a small range after an arbitrary target hook modifies, inserts, and removes instructions. It's pretty limited right now, but I hope to extend it to support all of the things that are done by the convertToThreeAddress() target hooks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175382 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index df1c7c2a66..3d754366ee 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -698,6 +698,24 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { } } + 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 @@ -830,6 +848,17 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { LI.removeRange(StartIndex, EndIndex); } } + + // Update all intervals for registers whose uses may have been modified by + // updateTerminator(). + iterator FirstTerminator = getFirstTerminator(); + MachineInstr *FirstTerminatorMI = FirstTerminator; + if (FirstTerminatorMI->isBundled()) + FirstTerminatorMI = getBundleStart(FirstTerminatorMI); + reverse_iterator PreTerminators = + (FirstTerminator == begin()) ? rend() + : reverse_iterator(FirstTerminatorMI); + LIS->repairIntervalsInRange(this, rbegin(), PreTerminators, UsedRegs); } if (MachineDominatorTree *MDT = -- cgit v1.2.3-18-g5258 From 0c222835982bae5e4831e16090f6ce594ef541a6 Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Sun, 17 Feb 2013 01:45:04 +0000 Subject: Fix a conversion from a forward iterator to a reverse iterator in MachineBasicBlock::SplitCriticalEdge. Since this is an iterator rather than an instr_iterator, the isBundled() check only passes if getFirstTerminator() returned end() and the garbage memory happens to lean that way. Multiple successors can be present without any terminator instructions in the case of exception handling with a fallthrough. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175383 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 3d754366ee..f22a70716e 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -852,12 +852,13 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { // Update all intervals for registers whose uses may have been modified by // updateTerminator(). iterator FirstTerminator = getFirstTerminator(); - MachineInstr *FirstTerminatorMI = FirstTerminator; - if (FirstTerminatorMI->isBundled()) - FirstTerminatorMI = getBundleStart(FirstTerminatorMI); - reverse_iterator PreTerminators = - (FirstTerminator == begin()) ? rend() - : reverse_iterator(FirstTerminatorMI); + reverse_iterator PreTerminators; + if (FirstTerminator == begin()) + PreTerminators = rend(); + else if (FirstTerminator == end()) + PreTerminators = rbegin(); + else + PreTerminators = reverse_iterator(FirstTerminator); LIS->repairIntervalsInRange(this, rbegin(), PreTerminators, UsedRegs); } -- cgit v1.2.3-18-g5258 From 680c98f6323dde0eae566710ea49497e16499653 Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Sun, 17 Feb 2013 11:09:00 +0000 Subject: Remove use of reverse iterators in repairIntervalsInRange(). While they were arguably better than forward iterators for this use case, they are confusing and there are some implementation problems with reverse iterators and MI bundles. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175393 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 10 +--------- 1 file changed, 1 insertion(+), 9 deletions(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index f22a70716e..898e165fee 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -851,15 +851,7 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { // Update all intervals for registers whose uses may have been modified by // updateTerminator(). - iterator FirstTerminator = getFirstTerminator(); - reverse_iterator PreTerminators; - if (FirstTerminator == begin()) - PreTerminators = rend(); - else if (FirstTerminator == end()) - PreTerminators = rbegin(); - else - PreTerminators = reverse_iterator(FirstTerminator); - LIS->repairIntervalsInRange(this, rbegin(), PreTerminators, UsedRegs); + LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs); } if (MachineDominatorTree *MDT = -- cgit v1.2.3-18-g5258