From 826f0935177b0183383701ae40e3d802a184fbf4 Mon Sep 17 00:00:00 2001 From: Bill Wendling Date: Mon, 26 Jan 2009 21:30:17 +0000 Subject: [PATCH] Also revert r63206 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@63041 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/PreAllocSplitting.cpp | 321 ++++++++++++++++++++++++++++++ 1 file changed, 321 insertions(+) diff --git a/lib/CodeGen/PreAllocSplitting.cpp b/lib/CodeGen/PreAllocSplitting.cpp index 09b39fab1b4..16a9e6d9b04 100644 --- a/lib/CodeGen/PreAllocSplitting.cpp +++ b/lib/CodeGen/PreAllocSplitting.cpp @@ -139,11 +139,26 @@ namespace { void UpdateSpillSlotInterval(VNInfo*, unsigned, unsigned); + VNInfo* UpdateRegisterInterval(VNInfo*, unsigned, unsigned); + + bool ShrinkWrapToLastUse(MachineBasicBlock*, VNInfo*, + SmallVector&, + SmallPtrSet&); + + void ShrinkWrapLiveInterval(VNInfo*, MachineBasicBlock*, MachineBasicBlock*, + MachineBasicBlock*, SmallPtrSet&, + DenseMap >&, + DenseMap >&, + SmallVector&); + bool SplitRegLiveInterval(LiveInterval*); bool SplitRegLiveIntervals(const TargetRegisterClass **, SmallPtrSet&); + void RepairLiveInterval(LiveInterval* CurrLI, VNInfo* ValNo, + MachineInstr* DefMI, unsigned RestoreIdx); + bool createsNewJoin(LiveRange* LR, MachineBasicBlock* DefMBB, MachineBasicBlock* BarrierMBB); bool Rematerialize(unsigned vreg, VNInfo* ValNo, @@ -408,6 +423,176 @@ PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, unsigned SpillIndex, } } +/// UpdateRegisterInterval - Given the specified val# of the current live +/// interval is being split, and the spill and restore indices, update the live +/// interval accordingly. +VNInfo* +PreAllocSplitting::UpdateRegisterInterval(VNInfo *ValNo, unsigned SpillIndex, + unsigned RestoreIndex) { + assert(LIs->getMBBFromIndex(RestoreIndex) == BarrierMBB && + "Expect restore in the barrier mbb"); + + SmallVector, 4> Before; + SmallVector, 4> After; + SmallVector BeforeKills; + SmallVector AfterKills; + SmallPtrSet Processed; + + // First, let's figure out which parts of the live interval is now defined + // by the restore, which are defined by the original definition. + const LiveRange *LR = CurrLI->getLiveRangeContaining(RestoreIndex); + After.push_back(std::make_pair(RestoreIndex, LR->end)); + if (CurrLI->isKill(ValNo, LR->end)) + AfterKills.push_back(LR->end); + + assert(LR->contains(SpillIndex)); + if (SpillIndex > LR->start) { + Before.push_back(std::make_pair(LR->start, SpillIndex)); + BeforeKills.push_back(SpillIndex); + } + Processed.insert(LR); + + // Start from the restore mbb, figure out what part of the live interval + // are defined by the restore. + SmallVector WorkList; + MachineBasicBlock *MBB = BarrierMBB; + for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), + SE = MBB->succ_end(); SI != SE; ++SI) + WorkList.push_back(*SI); + + SmallPtrSet ProcessedBlocks; + ProcessedBlocks.insert(MBB); + + while (!WorkList.empty()) { + MBB = WorkList.back(); + WorkList.pop_back(); + unsigned Idx = LIs->getMBBStartIdx(MBB); + LR = CurrLI->getLiveRangeContaining(Idx); + if (LR && LR->valno == ValNo && !Processed.count(LR)) { + After.push_back(std::make_pair(LR->start, LR->end)); + if (CurrLI->isKill(ValNo, LR->end)) + AfterKills.push_back(LR->end); + Idx = LIs->getMBBEndIdx(MBB); + if (LR->end > Idx) { + // Live range extend beyond at least one mbb. Let's see what other + // mbbs it reaches. + LIs->findReachableMBBs(LR->start, LR->end, WorkList); + } + Processed.insert(LR); + } + + ProcessedBlocks.insert(MBB); + if (LR) + for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), + SE = MBB->succ_end(); SI != SE; ++SI) + if (!ProcessedBlocks.count(*SI)) + WorkList.push_back(*SI); + } + + for (LiveInterval::iterator I = CurrLI->begin(), E = CurrLI->end(); + I != E; ++I) { + LiveRange *LR = I; + if (LR->valno == ValNo && !Processed.count(LR)) { + Before.push_back(std::make_pair(LR->start, LR->end)); + if (CurrLI->isKill(ValNo, LR->end)) + BeforeKills.push_back(LR->end); + } + } + + // Now create new val#s to represent the live ranges defined by the old def + // those defined by the restore. + unsigned AfterDef = ValNo->def; + MachineInstr *AfterCopy = ValNo->copy; + bool HasPHIKill = ValNo->hasPHIKill; + CurrLI->removeValNo(ValNo); + VNInfo *BValNo = (Before.empty()) + ? NULL + : CurrLI->getNextValue(AfterDef, AfterCopy, LIs->getVNInfoAllocator()); + if (BValNo) + CurrLI->addKills(BValNo, BeforeKills); + + VNInfo *AValNo = (After.empty()) + ? NULL + : CurrLI->getNextValue(RestoreIndex, 0, LIs->getVNInfoAllocator()); + if (AValNo) { + AValNo->hasPHIKill = HasPHIKill; + CurrLI->addKills(AValNo, AfterKills); + } + + for (unsigned i = 0, e = Before.size(); i != e; ++i) { + unsigned Start = Before[i].first; + unsigned End = Before[i].second; + CurrLI->addRange(LiveRange(Start, End, BValNo)); + } + for (unsigned i = 0, e = After.size(); i != e; ++i) { + unsigned Start = After[i].first; + unsigned End = After[i].second; + CurrLI->addRange(LiveRange(Start, End, AValNo)); + } + + return AValNo; +} + +/// ShrinkWrapToLastUse - There are uses of the current live interval in the +/// given block, shrink wrap the live interval to the last use (i.e. remove +/// from last use to the end of the mbb). In case mbb is the where the barrier +/// is, remove from the last use to the barrier. +bool +PreAllocSplitting::ShrinkWrapToLastUse(MachineBasicBlock *MBB, VNInfo *ValNo, + SmallVector &Uses, + SmallPtrSet &UseMIs) { + MachineOperand *LastMO = 0; + MachineInstr *LastMI = 0; + if (MBB != BarrierMBB && Uses.size() == 1) { + // Single use, no need to traverse the block. We can't assume this for the + // barrier bb though since the use is probably below the barrier. + LastMO = Uses[0]; + LastMI = LastMO->getParent(); + } else { + MachineBasicBlock::iterator MEE = MBB->begin(); + MachineBasicBlock::iterator MII; + if (MBB == BarrierMBB) + MII = Barrier; + else + MII = MBB->end(); + while (MII != MEE) { + --MII; + MachineInstr *UseMI = &*MII; + if (!UseMIs.count(UseMI)) + continue; + for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = UseMI->getOperand(i); + if (MO.isReg() && MO.getReg() == CurrLI->reg) { + LastMO = &MO; + break; + } + } + LastMI = UseMI; + break; + } + } + + // Cut off live range from last use (or beginning of the mbb if there + // are no uses in it) to the end of the mbb. + unsigned RangeStart, RangeEnd = LIs->getMBBEndIdx(MBB)+1; + if (LastMI) { + RangeStart = LIs->getUseIndex(LIs->getInstructionIndex(LastMI))+1; + assert(!LastMO->isKill() && "Last use already terminates the interval?"); + LastMO->setIsKill(); + } else { + assert(MBB == BarrierMBB); + RangeStart = LIs->getMBBStartIdx(MBB); + } + if (MBB == BarrierMBB) + RangeEnd = LIs->getUseIndex(BarrierIdx)+1; + CurrLI->removeRange(RangeStart, RangeEnd); + if (LastMI) + CurrLI->addKill(ValNo, RangeStart); + + // Return true if the last use becomes a new kill. + return LastMI; +} + /// PerformPHIConstruction - From properly set up use and def lists, use a PHI /// construction algorithm to compute the ranges and valnos for an interval. VNInfo* PreAllocSplitting::PerformPHIConstruction( @@ -705,6 +890,142 @@ void PreAllocSplitting::ReconstructLiveInterval(LiveInterval* LI) { } } +/// ShrinkWrapLiveInterval - Recursively traverse the predecessor +/// chain to find the new 'kills' and shrink wrap the live interval to the +/// new kill indices. +void +PreAllocSplitting::ShrinkWrapLiveInterval(VNInfo *ValNo, MachineBasicBlock *MBB, + MachineBasicBlock *SuccMBB, MachineBasicBlock *DefMBB, + SmallPtrSet &Visited, + DenseMap > &Uses, + DenseMap > &UseMIs, + SmallVector &UseMBBs) { + if (Visited.count(MBB)) + return; + + // If live interval is live in another successor path, then we can't process + // this block. But we may able to do so after all the successors have been + // processed. + if (MBB != BarrierMBB) { + for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), + SE = MBB->succ_end(); SI != SE; ++SI) { + MachineBasicBlock *SMBB = *SI; + if (SMBB == SuccMBB) + continue; + if (CurrLI->liveAt(LIs->getMBBStartIdx(SMBB))) + return; + } + } + + Visited.insert(MBB); + + DenseMap >::iterator + UMII = Uses.find(MBB); + if (UMII != Uses.end()) { + // At least one use in this mbb, lets look for the kill. + DenseMap >::iterator + UMII2 = UseMIs.find(MBB); + if (ShrinkWrapToLastUse(MBB, ValNo, UMII->second, UMII2->second)) + // Found a kill, shrink wrapping of this path ends here. + return; + } else if (MBB == DefMBB) { + // There are no uses after the def. + MachineInstr *DefMI = LIs->getInstructionFromIndex(ValNo->def); + if (UseMBBs.empty()) { + // The only use must be below barrier in the barrier block. It's safe to + // remove the def. + LIs->RemoveMachineInstrFromMaps(DefMI); + DefMI->eraseFromParent(); + CurrLI->removeRange(ValNo->def, LIs->getMBBEndIdx(MBB)+1); + } + } else if (MBB == BarrierMBB) { + // Remove entire live range from start of mbb to barrier. + CurrLI->removeRange(LIs->getMBBStartIdx(MBB), + LIs->getUseIndex(BarrierIdx)+1); + } else { + // Remove entire live range of the mbb out of the live interval. + CurrLI->removeRange(LIs->getMBBStartIdx(MBB), LIs->getMBBEndIdx(MBB)+1); + } + + if (MBB == DefMBB) + // Reached the def mbb, stop traversing this path further. + return; + + // Traverse the pathes up the predecessor chains further. + for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), + PE = MBB->pred_end(); PI != PE; ++PI) { + MachineBasicBlock *Pred = *PI; + if (Pred == MBB) + continue; + if (Pred == DefMBB && ValNo->hasPHIKill) + // Pred is the def bb and the def reaches other val#s, we must + // allow the value to be live out of the bb. + continue; + if (!CurrLI->liveAt(LIs->getMBBEndIdx(Pred)-1)) + return; + ShrinkWrapLiveInterval(ValNo, Pred, MBB, DefMBB, Visited, + Uses, UseMIs, UseMBBs); + } + + return; +} + + +void PreAllocSplitting::RepairLiveInterval(LiveInterval* CurrLI, + VNInfo* ValNo, + MachineInstr* DefMI, + unsigned RestoreIdx) { + // Shrink wrap the live interval by walking up the CFG and find the + // new kills. + // Now let's find all the uses of the val#. + DenseMap > Uses; + DenseMap > UseMIs; + SmallPtrSet Seen; + SmallVector UseMBBs; + for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(CurrLI->reg), + UE = MRI->use_end(); UI != UE; ++UI) { + MachineOperand &UseMO = UI.getOperand(); + MachineInstr *UseMI = UseMO.getParent(); + unsigned UseIdx = LIs->getInstructionIndex(UseMI); + LiveInterval::iterator ULR = CurrLI->FindLiveRangeContaining(UseIdx); + if (ULR->valno != ValNo) + continue; + MachineBasicBlock *UseMBB = UseMI->getParent(); + // Remember which other mbb's use this val#. + if (Seen.insert(UseMBB) && UseMBB != BarrierMBB) + UseMBBs.push_back(UseMBB); + DenseMap >::iterator + UMII = Uses.find(UseMBB); + if (UMII != Uses.end()) { + DenseMap >::iterator + UMII2 = UseMIs.find(UseMBB); + UMII->second.push_back(&UseMO); + UMII2->second.insert(UseMI); + } else { + SmallVector Ops; + Ops.push_back(&UseMO); + Uses.insert(std::make_pair(UseMBB, Ops)); + SmallPtrSet MIs; + MIs.insert(UseMI); + UseMIs.insert(std::make_pair(UseMBB, MIs)); + } + } + + // Walk up the predecessor chains. + SmallPtrSet Visited; + ShrinkWrapLiveInterval(ValNo, BarrierMBB, NULL, DefMI->getParent(), Visited, + Uses, UseMIs, UseMBBs); + + // Remove live range from barrier to the restore. FIXME: Find a better + // point to re-start the live interval. + VNInfo* AfterValNo = UpdateRegisterInterval(ValNo, + LIs->getUseIndex(BarrierIdx)+1, + LIs->getDefIndex(RestoreIdx)); + + // Attempt to renumber the new valno into a new vreg. + RenumberValno(AfterValNo); +} + /// RenumberValno - Split the given valno out into a new vreg, allowing it to /// be allocated to a different register. This function creates a new vreg, /// copies the valno and its live ranges over to the new vreg's interval, -- 2.34.1