X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPreAllocSplitting.cpp;h=fbab7e8be7552f8352709f4add6da9d80587aeb9;hb=c02497f5bae87e71fd5617db5751cb0b3a14bbed;hp=c7491ce2a8943a5d5446ea3951f52eba9f2704ea;hpb=25dffa743b2e2d0ee5fe70254d3a45724580a383;p=oota-llvm.git diff --git a/lib/CodeGen/PreAllocSplitting.cpp b/lib/CodeGen/PreAllocSplitting.cpp index c7491ce2a89..fbab7e8be75 100644 --- a/lib/CodeGen/PreAllocSplitting.cpp +++ b/lib/CodeGen/PreAllocSplitting.cpp @@ -15,6 +15,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "pre-alloc-split" +#include "VirtRegMap.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineDominators.h" @@ -30,6 +31,7 @@ #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallPtrSet.h" @@ -37,21 +39,27 @@ using namespace llvm; static cl::opt PreSplitLimit("pre-split-limit", cl::init(-1), cl::Hidden); +static cl::opt DeadSplitLimit("dead-split-limit", cl::init(-1), cl::Hidden); +static cl::opt RestoreFoldLimit("restore-fold-limit", cl::init(-1), cl::Hidden); STATISTIC(NumSplits, "Number of intervals split"); STATISTIC(NumRemats, "Number of intervals split by rematerialization"); STATISTIC(NumFolds, "Number of intervals split with spill folding"); +STATISTIC(NumRestoreFolds, "Number of intervals split with restore folding"); STATISTIC(NumRenumbers, "Number of intervals renumbered into new registers"); +STATISTIC(NumDeadSpills, "Number of dead spills removed"); namespace { class VISIBILITY_HIDDEN PreAllocSplitting : public MachineFunctionPass { MachineFunction *CurrMF; const TargetMachine *TM; const TargetInstrInfo *TII; + const TargetRegisterInfo* TRI; MachineFrameInfo *MFI; MachineRegisterInfo *MRI; LiveIntervals *LIs; LiveStacks *LSs; + VirtRegMap *VRM; // Barrier - Current barrier being processed. MachineInstr *Barrier; @@ -84,6 +92,7 @@ namespace { virtual bool runOnMachineFunction(MachineFunction &MF); virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); AU.addRequired(); AU.addPreserved(); AU.addRequired(); @@ -95,8 +104,10 @@ namespace { AU.addPreservedID(PHIEliminationID); AU.addRequired(); AU.addRequired(); + AU.addRequired(); AU.addPreserved(); AU.addPreserved(); + AU.addPreserved(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -138,24 +149,10 @@ 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 **); - - void RepairLiveInterval(LiveInterval* CurrLI, VNInfo* ValNo, - MachineInstr* DefMI, unsigned RestoreIdx); + bool SplitRegLiveIntervals(const TargetRegisterClass **, + SmallPtrSet&); bool createsNewJoin(LiveRange* LR, MachineBasicBlock* DefMBB, MachineBasicBlock* BarrierMBB); @@ -170,8 +167,36 @@ namespace { MachineBasicBlock* MBB, int& SS, SmallPtrSet& RefsInMBB); + MachineInstr* FoldRestore(unsigned vreg, + const TargetRegisterClass* RC, + MachineInstr* Barrier, + MachineBasicBlock* MBB, + int SS, + SmallPtrSet& RefsInMBB); void RenumberValno(VNInfo* VN); - }; + void ReconstructLiveInterval(LiveInterval* LI); + bool removeDeadSpills(SmallPtrSet& split); + unsigned getNumberOfNonSpills(SmallPtrSet& MIs, + unsigned Reg, int FrameIndex, bool& TwoAddr); + VNInfo* PerformPHIConstruction(MachineBasicBlock::iterator Use, + MachineBasicBlock* MBB, LiveInterval* LI, + SmallPtrSet& Visited, + DenseMap >& Defs, + DenseMap >& Uses, + DenseMap& NewVNs, + DenseMap& LiveOut, + DenseMap& Phis, + bool IsTopLevel, bool IsIntraBlock); + VNInfo* PerformPHIConstructionFallBack(MachineBasicBlock::iterator Use, + MachineBasicBlock* MBB, LiveInterval* LI, + SmallPtrSet& Visited, + DenseMap >& Defs, + DenseMap >& Uses, + DenseMap& NewVNs, + DenseMap& LiveOut, + DenseMap& Phis, + bool IsTopLevel, bool IsIntraBlock); +}; } // end anonymous namespace char PreAllocSplitting::ID = 0; @@ -209,32 +234,38 @@ PreAllocSplitting::findSpillPoint(MachineBasicBlock *MBB, MachineInstr *MI, unsigned &SpillIndex) { MachineBasicBlock::iterator Pt = MBB->begin(); - // Go top down if RefsInMBB is empty. - if (RefsInMBB.empty() && !DefMI) { - MachineBasicBlock::iterator MII = MBB->begin(); - MachineBasicBlock::iterator EndPt = MI; - do { - ++MII; - unsigned Index = LIs->getInstructionIndex(MII); - unsigned Gap = LIs->findGapBeforeInstr(Index); - if (Gap) { - Pt = MII; - SpillIndex = Gap; - break; - } - } while (MII != EndPt); - } else { - MachineBasicBlock::iterator MII = MI; - MachineBasicBlock::iterator EndPt = DefMI - ? MachineBasicBlock::iterator(DefMI) : MBB->begin(); - while (MII != EndPt && !RefsInMBB.count(MII)) { - unsigned Index = LIs->getInstructionIndex(MII); - if (LIs->hasGapBeforeInstr(Index)) { - Pt = MII; - SpillIndex = LIs->findGapBeforeInstr(Index, true); + MachineBasicBlock::iterator MII = MI; + MachineBasicBlock::iterator EndPt = DefMI + ? MachineBasicBlock::iterator(DefMI) : MBB->begin(); + + while (MII != EndPt && !RefsInMBB.count(MII) && + MII->getOpcode() != TRI->getCallFrameSetupOpcode()) + --MII; + if (MII == EndPt || RefsInMBB.count(MII)) return Pt; + + while (MII != EndPt && !RefsInMBB.count(MII)) { + unsigned Index = LIs->getInstructionIndex(MII); + + // We can't insert the spill between the barrier (a call), and its + // corresponding call frame setup. + if (MII->getOpcode() == TRI->getCallFrameDestroyOpcode()) { + while (MII->getOpcode() != TRI->getCallFrameSetupOpcode()) { + --MII; + if (MII == EndPt) { + return Pt; + } } - --MII; + continue; + } else if (LIs->hasGapBeforeInstr(Index)) { + Pt = MII; + SpillIndex = LIs->findGapBeforeInstr(Index, true); } + + if (RefsInMBB.count(MII)) + return Pt; + + + --MII; } return Pt; @@ -252,42 +283,44 @@ PreAllocSplitting::findRestorePoint(MachineBasicBlock *MBB, MachineInstr *MI, // FIXME: Allow spill to be inserted to the beginning of the mbb. Update mbb // begin index accordingly. MachineBasicBlock::iterator Pt = MBB->end(); - unsigned EndIdx = LIs->getMBBEndIdx(MBB); + MachineBasicBlock::iterator EndPt = MBB->getFirstTerminator(); - // Go bottom up if RefsInMBB is empty and the end of the mbb isn't beyond - // the last index in the live range. - if (RefsInMBB.empty() && LastIdx >= EndIdx) { - MachineBasicBlock::iterator MII = MBB->getFirstTerminator(); - MachineBasicBlock::iterator EndPt = MI; - --MII; - do { - unsigned Index = LIs->getInstructionIndex(MII); - unsigned Gap = LIs->findGapBeforeInstr(Index); - if (Gap) { - Pt = MII; - RestoreIndex = Gap; - break; - } - --MII; - } while (MII != EndPt); - } else { - MachineBasicBlock::iterator MII = MI; - MII = ++MII; - // FIXME: Limit the number of instructions to examine to reduce - // compile time? - while (MII != MBB->end()) { - unsigned Index = LIs->getInstructionIndex(MII); - if (Index > LastIdx) - break; - unsigned Gap = LIs->findGapBeforeInstr(Index); - if (Gap) { - Pt = MII; - RestoreIndex = Gap; - } - if (RefsInMBB.count(MII)) - break; - ++MII; + // We start at the call, so walk forward until we find the call frame teardown + // since we can't insert restores before that. Bail if we encounter a use + // during this time. + MachineBasicBlock::iterator MII = MI; + if (MII == EndPt) return Pt; + + while (MII != EndPt && !RefsInMBB.count(MII) && + MII->getOpcode() != TRI->getCallFrameDestroyOpcode()) + ++MII; + if (MII == EndPt || RefsInMBB.count(MII)) return Pt; + ++MII; + + // FIXME: Limit the number of instructions to examine to reduce + // compile time? + while (MII != EndPt) { + unsigned Index = LIs->getInstructionIndex(MII); + if (Index > LastIdx) + break; + unsigned Gap = LIs->findGapBeforeInstr(Index); + + // We can't insert a restore between the barrier (a call) and its + // corresponding call frame teardown. + if (MII->getOpcode() == TRI->getCallFrameSetupOpcode()) { + do { + if (MII == EndPt || RefsInMBB.count(MII)) return Pt; + ++MII; + } while (MII->getOpcode() != TRI->getCallFrameDestroyOpcode()); + } else if (Gap) { + Pt = MII; + RestoreIndex = Gap; } + + if (RefsInMBB.count(MII)) + return Pt; + + ++MII; } return Pt; @@ -308,11 +341,11 @@ int PreAllocSplitting::CreateSpillStackSlot(unsigned Reg, } // Create live interval for stack slot. - CurrSLI = &LSs->getOrCreateInterval(SS); + CurrSLI = &LSs->getOrCreateInterval(SS, RC); if (CurrSLI->hasAtLeastOneValue()) CurrSValNo = CurrSLI->getValNumInfo(0); else - CurrSValNo = CurrSLI->getNextValue(~0U, 0, LSs->getVNInfoAllocator()); + CurrSValNo = CurrSLI->getNextValue(0, 0, false, LSs->getVNInfoAllocator()); return SS; } @@ -407,310 +440,341 @@ 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. +/// 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::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); +PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI, + MachineBasicBlock* MBB, LiveInterval* LI, + SmallPtrSet& Visited, + DenseMap >& Defs, + DenseMap >& Uses, + DenseMap& NewVNs, + DenseMap& LiveOut, + DenseMap& Phis, + bool IsTopLevel, bool IsIntraBlock) { + // Return memoized result if it's available. + if (IsTopLevel && Visited.count(UseI) && NewVNs.count(UseI)) + return NewVNs[UseI]; + else if (!IsTopLevel && IsIntraBlock && NewVNs.count(UseI)) + return NewVNs[UseI]; + else if (!IsIntraBlock && LiveOut.count(MBB)) + return LiveOut[MBB]; + + // Check if our block contains any uses or defs. + bool ContainsDefs = Defs.count(MBB); + bool ContainsUses = Uses.count(MBB); + + VNInfo* RetVNI = 0; + + // Enumerate the cases of use/def contaning blocks. + if (!ContainsDefs && !ContainsUses) { + return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, Uses, + NewVNs, LiveOut, Phis, + IsTopLevel, IsIntraBlock); + } else if (ContainsDefs && !ContainsUses) { + SmallPtrSet& BlockDefs = Defs[MBB]; + + // Search for the def in this block. If we don't find it before the + // instruction we care about, go to the fallback case. Note that that + // should never happen: this cannot be intrablock, so use should + // always be an end() iterator. + assert(UseI == MBB->end() && "No use marked in intrablock"); + + MachineBasicBlock::iterator Walker = UseI; + --Walker; + while (Walker != MBB->begin()) { + if (BlockDefs.count(Walker)) + break; + --Walker; } - 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); + // Once we've found it, extend its VNInfo to our instruction. + unsigned DefIndex = LIs->getInstructionIndex(Walker); + DefIndex = LiveIntervals::getDefIndex(DefIndex); + unsigned EndIndex = LIs->getMBBEndIdx(MBB); + + RetVNI = NewVNs[Walker]; + LI->addRange(LiveRange(DefIndex, EndIndex+1, RetVNI)); + } else if (!ContainsDefs && ContainsUses) { + SmallPtrSet& BlockUses = Uses[MBB]; + + // Search for the use in this block that precedes the instruction we care + // about, going to the fallback case if we don't find it. + if (UseI == MBB->begin()) + return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, + Uses, NewVNs, LiveOut, Phis, + IsTopLevel, IsIntraBlock); + + MachineBasicBlock::iterator Walker = UseI; + --Walker; + bool found = false; + while (Walker != MBB->begin()) { + if (BlockUses.count(Walker)) { + found = true; + break; + } + --Walker; + } + + // Must check begin() too. + if (!found) { + if (BlockUses.count(Walker)) + found = true; + else + return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, + Uses, NewVNs, LiveOut, Phis, + IsTopLevel, IsIntraBlock); } - } - - // 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; -} + unsigned UseIndex = LIs->getInstructionIndex(Walker); + UseIndex = LiveIntervals::getUseIndex(UseIndex); + unsigned EndIndex = 0; + if (IsIntraBlock) { + EndIndex = LIs->getInstructionIndex(UseI); + EndIndex = LiveIntervals::getUseIndex(EndIndex); + } else + EndIndex = LIs->getMBBEndIdx(MBB); -/// 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; - } + // Now, recursively phi construct the VNInfo for the use we found, + // and then extend it to include the instruction we care about + RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses, + NewVNs, LiveOut, Phis, false, true); + + LI->addRange(LiveRange(UseIndex, EndIndex+1, RetVNI)); + + // FIXME: Need to set kills properly for inter-block stuff. + if (LI->isKill(RetVNI, UseIndex)) LI->removeKill(RetVNI, UseIndex); + if (IsIntraBlock) + LI->addKill(RetVNI, EndIndex, false); + } else if (ContainsDefs && ContainsUses) { + SmallPtrSet& BlockDefs = Defs[MBB]; + SmallPtrSet& BlockUses = Uses[MBB]; + + // This case is basically a merging of the two preceding case, with the + // special note that checking for defs must take precedence over checking + // for uses, because of two-address instructions. + + if (UseI == MBB->begin()) + return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, Uses, + NewVNs, LiveOut, Phis, + IsTopLevel, IsIntraBlock); + + MachineBasicBlock::iterator Walker = UseI; + --Walker; + bool foundDef = false; + bool foundUse = false; + while (Walker != MBB->begin()) { + if (BlockDefs.count(Walker)) { + foundDef = true; + break; + } else if (BlockUses.count(Walker)) { + foundUse = true; + break; } - LastMI = UseMI; - break; + --Walker; + } + + // Must check begin() too. + if (!foundDef && !foundUse) { + if (BlockDefs.count(Walker)) + foundDef = true; + else if (BlockUses.count(Walker)) + foundUse = true; + else + return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, + Uses, NewVNs, LiveOut, Phis, + IsTopLevel, IsIntraBlock); } - } - // 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; -} + unsigned StartIndex = LIs->getInstructionIndex(Walker); + StartIndex = foundDef ? LiveIntervals::getDefIndex(StartIndex) : + LiveIntervals::getUseIndex(StartIndex); + unsigned EndIndex = 0; + if (IsIntraBlock) { + EndIndex = LIs->getInstructionIndex(UseI); + EndIndex = LiveIntervals::getUseIndex(EndIndex); + } else + EndIndex = LIs->getMBBEndIdx(MBB); -/// 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 (foundDef) + RetVNI = NewVNs[Walker]; + else + RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses, + NewVNs, LiveOut, Phis, false, true); - // 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; + LI->addRange(LiveRange(StartIndex, EndIndex+1, RetVNI)); + + if (foundUse && LI->isKill(RetVNI, StartIndex)) + LI->removeKill(RetVNI, StartIndex); + if (IsIntraBlock) { + LI->addKill(RetVNI, EndIndex, false); } } - - 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); + + // Memoize results so we don't have to recompute them. + if (!IsIntraBlock) LiveOut[MBB] = RetVNI; + else { + if (!NewVNs.count(UseI)) + NewVNs[UseI] = RetVNI; + Visited.insert(UseI); } - if (MBB == DefMBB) - // Reached the def mbb, stop traversing this path further. - return; + return RetVNI; +} - // Traverse the pathes up the predecessor chains further. +/// PerformPHIConstructionFallBack - PerformPHIConstruction fall back path. +/// +VNInfo* +PreAllocSplitting::PerformPHIConstructionFallBack(MachineBasicBlock::iterator UseI, + MachineBasicBlock* MBB, LiveInterval* LI, + SmallPtrSet& Visited, + DenseMap >& Defs, + DenseMap >& Uses, + DenseMap& NewVNs, + DenseMap& LiveOut, + DenseMap& Phis, + bool IsTopLevel, bool IsIntraBlock) { + // NOTE: Because this is the fallback case from other cases, we do NOT + // assume that we are not intrablock here. + if (Phis.count(MBB)) return Phis[MBB]; + + unsigned StartIndex = LIs->getMBBStartIdx(MBB); + VNInfo *RetVNI = Phis[MBB] = + LI->getNextValue(0, /*FIXME*/ 0, false, LIs->getVNInfoAllocator()); + + if (!IsIntraBlock) LiveOut[MBB] = RetVNI; + + // If there are no uses or defs between our starting point and the + // beginning of the block, then recursive perform phi construction + // on our predecessors. + DenseMap IncomingVNs; 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); + VNInfo* Incoming = PerformPHIConstruction((*PI)->end(), *PI, LI, + Visited, Defs, Uses, NewVNs, + LiveOut, Phis, false, false); + if (Incoming != 0) + IncomingVNs[*PI] = Incoming; + } + + if (MBB->pred_size() == 1 && !RetVNI->hasPHIKill()) { + VNInfo* OldVN = RetVNI; + VNInfo* NewVN = IncomingVNs.begin()->second; + VNInfo* MergedVN = LI->MergeValueNumberInto(OldVN, NewVN); + if (MergedVN == OldVN) std::swap(OldVN, NewVN); + + for (DenseMap::iterator LOI = LiveOut.begin(), + LOE = LiveOut.end(); LOI != LOE; ++LOI) + if (LOI->second == OldVN) + LOI->second = MergedVN; + for (DenseMap::iterator NVI = NewVNs.begin(), + NVE = NewVNs.end(); NVI != NVE; ++NVI) + if (NVI->second == OldVN) + NVI->second = MergedVN; + for (DenseMap::iterator PI = Phis.begin(), + PE = Phis.end(); PI != PE; ++PI) + if (PI->second == OldVN) + PI->second = MergedVN; + RetVNI = MergedVN; + } else { + // Otherwise, merge the incoming VNInfos with a phi join. Create a new + // VNInfo to represent the joined value. + for (DenseMap::iterator I = + IncomingVNs.begin(), E = IncomingVNs.end(); I != E; ++I) { + I->second->setHasPHIKill(true); + unsigned KillIndex = LIs->getMBBEndIdx(I->first); + if (!LiveInterval::isKill(I->second, KillIndex)) + LI->addKill(I->second, KillIndex, false); + } + } + + unsigned EndIndex = 0; + if (IsIntraBlock) { + EndIndex = LIs->getInstructionIndex(UseI); + EndIndex = LiveIntervals::getUseIndex(EndIndex); + } else + EndIndex = LIs->getMBBEndIdx(MBB); + LI->addRange(LiveRange(StartIndex, EndIndex+1, RetVNI)); + if (IsIntraBlock) + LI->addKill(RetVNI, EndIndex, false); + + // Memoize results so we don't have to recompute them. + if (!IsIntraBlock) + LiveOut[MBB] = RetVNI; + else { + if (!NewVNs.count(UseI)) + NewVNs[UseI] = RetVNI; + Visited.insert(UseI); } - return; + return RetVNI; } - -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)); - } +/// ReconstructLiveInterval - Recompute a live interval from scratch. +void PreAllocSplitting::ReconstructLiveInterval(LiveInterval* LI) { + BumpPtrAllocator& Alloc = LIs->getVNInfoAllocator(); + + // Clear the old ranges and valnos; + LI->clear(); + + // Cache the uses and defs of the register + typedef DenseMap > RegMap; + RegMap Defs, Uses; + + // Keep track of the new VNs we're creating. + DenseMap NewVNs; + SmallPtrSet PhiVNs; + + // Cache defs, and create a new VNInfo for each def. + for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(LI->reg), + DE = MRI->def_end(); DI != DE; ++DI) { + Defs[(*DI).getParent()].insert(&*DI); + + unsigned DefIdx = LIs->getInstructionIndex(&*DI); + DefIdx = LiveIntervals::getDefIndex(DefIdx); + + assert(DI->getOpcode() != TargetInstrInfo::PHI && + "Following NewVN isPHIDef flag incorrect. Fix me!"); + VNInfo* NewVN = LI->getNextValue(DefIdx, 0, true, Alloc); + + // If the def is a move, set the copy field. + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + if (TII->isMoveInstr(*DI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) + if (DstReg == LI->reg) + NewVN->setCopy(&*DI); + + NewVNs[&*DI] = NewVN; + } + + // Cache uses as a separate pass from actually processing them. + for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(LI->reg), + UE = MRI->use_end(); UI != UE; ++UI) + Uses[(*UI).getParent()].insert(&*UI); + + // Now, actually process every use and use a phi construction algorithm + // to walk from it to its reaching definitions, building VNInfos along + // the way. + DenseMap LiveOut; + DenseMap Phis; + SmallPtrSet Visited; + for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(LI->reg), + UE = MRI->use_end(); UI != UE; ++UI) { + PerformPHIConstruction(&*UI, UI->getParent(), LI, Visited, Defs, + Uses, NewVNs, LiveOut, Phis, true, true); + } + + // Add ranges for dead defs + for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(LI->reg), + DE = MRI->def_end(); DI != DE; ++DI) { + unsigned DefIdx = LIs->getInstructionIndex(&*DI); + DefIdx = LiveIntervals::getDefIndex(DefIdx); + + if (LI->liveAt(DefIdx)) continue; + + VNInfo* DeadVN = NewVNs[&*DI]; + LI->addRange(LiveRange(DefIdx, DefIdx+1, DeadVN)); + LI->addKill(DeadVN, DefIdx, false); } - - // 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. - if (!AfterValNo->hasPHIKill) - RenumberValno(AfterValNo); } /// RenumberValno - Split the given valno out into a new vreg, allowing it to @@ -719,45 +783,59 @@ void PreAllocSplitting::RepairLiveInterval(LiveInterval* CurrLI, /// removes them from the old interval, and rewrites all uses and defs of /// the original reg to the new vreg within those ranges. void PreAllocSplitting::RenumberValno(VNInfo* VN) { - // Create the new vreg - unsigned NewVReg = MRI->createVirtualRegister(MRI->getRegClass(CurrLI->reg)); - - // Create the new live interval - LiveInterval& NewLI = LIs->getOrCreateInterval(NewVReg); + SmallVector Stack; SmallVector VNsToCopy; - VNsToCopy.push_back(VN); + Stack.push_back(VN); // Walk through and copy the valno we care about, and any other valnos // that are two-address redefinitions of the one we care about. These - // will need to be rewritten as well. - while (!VNsToCopy.empty()) { - VNInfo* OldVN = VNsToCopy.back(); - VNsToCopy.pop_back(); + // will need to be rewritten as well. We also check for safety of the + // renumbering here, by making sure that none of the valno involved has + // phi kills. + while (!Stack.empty()) { + VNInfo* OldVN = Stack.back(); + Stack.pop_back(); + + // Bail out if we ever encounter a valno that has a PHI kill. We can't + // renumber these. + if (OldVN->hasPHIKill()) return; + + VNsToCopy.push_back(OldVN); - // Copy the valno over - VNInfo* NewVN = NewLI.getNextValue(OldVN->def, OldVN->copy, - LIs->getVNInfoAllocator()); - NewLI.copyValNumInfo(NewVN, OldVN); - NewLI.MergeValueInAsValue(*CurrLI, OldVN, NewVN); - // Locate two-address redefinitions - for (SmallVector::iterator KI = NewVN->kills.begin(), - KE = NewVN->kills.end(); KI != KE; ++KI) { - MachineInstr* MI = LIs->getInstructionFromIndex(*KI); + for (VNInfo::KillSet::iterator KI = OldVN->kills.begin(), + KE = OldVN->kills.end(); KI != KE; ++KI) { + assert(!KI->isPHIKill && "VN previously reported having no PHI kills."); + MachineInstr* MI = LIs->getInstructionFromIndex(KI->killIdx); unsigned DefIdx = MI->findRegisterDefOperandIdx(CurrLI->reg); if (DefIdx == ~0U) continue; - if (MI->isRegReDefinedByTwoAddr(DefIdx)) { + if (MI->isRegTiedToUseOperand(DefIdx)) { VNInfo* NextVN = - CurrLI->findDefinedVNInfo(LiveIntervals::getDefIndex(*KI)); - VNsToCopy.push_back(NextVN); + CurrLI->findDefinedVNInfo(LiveIntervals::getDefIndex(KI->killIdx)); + if (NextVN == OldVN) continue; + Stack.push_back(NextVN); } } + } + + // Create the new vreg + unsigned NewVReg = MRI->createVirtualRegister(MRI->getRegClass(CurrLI->reg)); + + // Create the new live interval + LiveInterval& NewLI = LIs->getOrCreateInterval(NewVReg); + + for (SmallVector::iterator OI = VNsToCopy.begin(), OE = + VNsToCopy.end(); OI != OE; ++OI) { + VNInfo* OldVN = *OI; + + // Copy the valno over + VNInfo* NewVN = NewLI.createValueCopy(OldVN, LIs->getVNInfoAllocator()); + NewLI.MergeValueInAsValue(*CurrLI, OldVN, NewVN); // Remove the valno from the old interval CurrLI->removeValNo(OldVN); } - // Rewrite defs and uses. This is done in two stages to avoid invalidating // the reg_iterator. SmallVector, 8> OpsToChange; @@ -780,10 +858,17 @@ void PreAllocSplitting::RenumberValno(VNInfo* VN) { MO.setReg(NewVReg); } + // Grow the VirtRegMap, since we've created a new vreg. + VRM->grow(); + + // The renumbered vreg shares a stack slot with the old register. + if (IntervalSSMap.count(CurrLI->reg)) + IntervalSSMap[NewVReg] = IntervalSSMap[CurrLI->reg]; + NumRenumbers++; } -bool PreAllocSplitting::Rematerialize(unsigned vreg, VNInfo* ValNo, +bool PreAllocSplitting::Rematerialize(unsigned VReg, VNInfo* ValNo, MachineInstr* DefMI, MachineBasicBlock::iterator RestorePt, unsigned RestoreIdx, @@ -792,7 +877,7 @@ bool PreAllocSplitting::Rematerialize(unsigned vreg, VNInfo* ValNo, MachineBasicBlock::iterator KillPt = BarrierMBB->end(); unsigned KillIdx = 0; - if (ValNo->def == ~0U || DefMI->getParent() == BarrierMBB) + if (!ValNo->isDefAccurate() || DefMI->getParent() == BarrierMBB) KillPt = findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, KillIdx); else KillPt = findNextEmptySlot(DefMI->getParent(), DefMI, KillIdx); @@ -800,20 +885,14 @@ bool PreAllocSplitting::Rematerialize(unsigned vreg, VNInfo* ValNo, if (KillPt == DefMI->getParent()->end()) return false; - TII->reMaterialize(MBB, RestorePt, vreg, DefMI); + TII->reMaterialize(MBB, RestorePt, VReg, 0, DefMI); LIs->InsertMachineInstrInMaps(prior(RestorePt), RestoreIdx); - if (KillPt->getParent() == BarrierMBB) { - UpdateRegisterInterval(ValNo, LIs->getUseIndex(KillIdx)+1, - LIs->getDefIndex(RestoreIdx)); - - ++NumSplits; - ++NumRemats; - return true; - } - - RepairLiveInterval(CurrLI, ValNo, DefMI, RestoreIdx); - + ReconstructLiveInterval(CurrLI); + unsigned RematIdx = LIs->getInstructionIndex(prior(RestorePt)); + RematIdx = LiveIntervals::getDefIndex(RematIdx); + RenumberValno(CurrLI->findDefinedVNInfo(RematIdx)); + ++NumSplits; ++NumRemats; return true; @@ -851,8 +930,7 @@ MachineInstr* PreAllocSplitting::FoldSpill(unsigned vreg, if (I != IntervalSSMap.end()) { SS = I->second; } else { - SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment()); - + SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment()); } MachineInstr* FMI = TII->foldMemoryOperand(*MBB->getParent(), @@ -864,11 +942,84 @@ MachineInstr* PreAllocSplitting::FoldSpill(unsigned vreg, ++NumFolds; IntervalSSMap[vreg] = SS; - CurrSLI = &LSs->getOrCreateInterval(SS); + CurrSLI = &LSs->getOrCreateInterval(SS, RC); if (CurrSLI->hasAtLeastOneValue()) CurrSValNo = CurrSLI->getValNumInfo(0); else - CurrSValNo = CurrSLI->getNextValue(~0U, 0, LSs->getVNInfoAllocator()); + CurrSValNo = CurrSLI->getNextValue(0, 0, false, LSs->getVNInfoAllocator()); + } + + return FMI; +} + +MachineInstr* PreAllocSplitting::FoldRestore(unsigned vreg, + const TargetRegisterClass* RC, + MachineInstr* Barrier, + MachineBasicBlock* MBB, + int SS, + SmallPtrSet& RefsInMBB) { + if ((int)RestoreFoldLimit != -1 && RestoreFoldLimit == (int)NumRestoreFolds) + return 0; + + // Go top down if RefsInMBB is empty. + if (RefsInMBB.empty()) + return 0; + + // Can't fold a restore between a call stack setup and teardown. + MachineBasicBlock::iterator FoldPt = Barrier; + + // Advance from barrier to call frame teardown. + while (FoldPt != MBB->getFirstTerminator() && + FoldPt->getOpcode() != TRI->getCallFrameDestroyOpcode()) { + if (RefsInMBB.count(FoldPt)) + return 0; + + ++FoldPt; + } + + if (FoldPt == MBB->getFirstTerminator()) + return 0; + else + ++FoldPt; + + // Now find the restore point. + while (FoldPt != MBB->getFirstTerminator() && !RefsInMBB.count(FoldPt)) { + if (FoldPt->getOpcode() == TRI->getCallFrameSetupOpcode()) { + while (FoldPt != MBB->getFirstTerminator() && + FoldPt->getOpcode() != TRI->getCallFrameDestroyOpcode()) { + if (RefsInMBB.count(FoldPt)) + return 0; + + ++FoldPt; + } + + if (FoldPt == MBB->getFirstTerminator()) + return 0; + } + + ++FoldPt; + } + + if (FoldPt == MBB->getFirstTerminator()) + return 0; + + int OpIdx = FoldPt->findRegisterUseOperandIdx(vreg, true); + if (OpIdx == -1) + return 0; + + SmallVector Ops; + Ops.push_back(OpIdx); + + if (!TII->canFoldMemoryOperand(FoldPt, Ops)) + return 0; + + MachineInstr* FMI = TII->foldMemoryOperand(*MBB->getParent(), + FoldPt, Ops, SS); + + if (FMI) { + LIs->ReplaceMachineInstrInMaps(FoldPt, FMI); + FMI = MBB->insert(MBB->erase(FoldPt), FMI); + ++NumRestoreFolds; } return FMI; @@ -885,13 +1036,9 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { CurrLI->FindLiveRangeContaining(LIs->getUseIndex(BarrierIdx)); VNInfo *ValNo = LR->valno; - if (ValNo->def == ~1U) { - // Defined by a dead def? How can this be? - assert(0 && "Val# is defined by a dead def?"); - abort(); - } + assert(!ValNo->isUnused() && "Val# is defined by a dead def?"); - MachineInstr *DefMI = (ValNo->def != ~0U) + MachineInstr *DefMI = ValNo->isDefAccurate() ? LIs->getInstructionFromIndex(ValNo->def) : NULL; // If this would create a new join point, do not split. @@ -908,7 +1055,7 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { } // Find a point to restore the value after the barrier. - unsigned RestoreIndex; + unsigned RestoreIndex = 0; MachineBasicBlock::iterator RestorePt = findRestorePoint(BarrierMBB, Barrier, LR->end, RefsInMBB, RestoreIndex); if (RestorePt == BarrierMBB->end()) @@ -925,8 +1072,8 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { unsigned SpillIndex = 0; MachineInstr *SpillMI = NULL; int SS = -1; - if (ValNo->def == ~0U) { - // If it's defined by a phi, we must split just before the barrier. + if (!ValNo->isDefAccurate()) { + // If we don't know where the def is we must split just before the barrier. if ((SpillMI = FoldSpill(LI->reg, RC, 0, Barrier, BarrierMBB, SS, RefsInMBB))) { SpillIndex = LIs->getInstructionIndex(SpillMI); @@ -981,31 +1128,30 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { Def2SpillMap[ValNo->def] = SpillIndex; // Add restore. - TII->loadRegFromStackSlot(*BarrierMBB, RestorePt, CurrLI->reg, SS, RC); - MachineInstr *LoadMI = prior(RestorePt); - LIs->InsertMachineInstrInMaps(LoadMI, RestoreIndex); - - // If live interval is spilled in the same block as the barrier, just - // create a hole in the interval. - if (!DefMBB || - (SpillMI && SpillMI->getParent() == BarrierMBB)) { - // Update spill stack slot live interval. - UpdateSpillSlotInterval(ValNo, LIs->getUseIndex(SpillIndex)+1, - LIs->getDefIndex(RestoreIndex)); - - UpdateRegisterInterval(ValNo, LIs->getUseIndex(SpillIndex)+1, - LIs->getDefIndex(RestoreIndex)); - - ++NumSplits; - return true; + bool FoldedRestore = false; + if (MachineInstr* LMI = FoldRestore(CurrLI->reg, RC, Barrier, + BarrierMBB, SS, RefsInMBB)) { + RestorePt = LMI; + RestoreIndex = LIs->getInstructionIndex(RestorePt); + FoldedRestore = true; + } else { + TII->loadRegFromStackSlot(*BarrierMBB, RestorePt, CurrLI->reg, SS, RC); + MachineInstr *LoadMI = prior(RestorePt); + LIs->InsertMachineInstrInMaps(LoadMI, RestoreIndex); } // Update spill stack slot live interval. UpdateSpillSlotInterval(ValNo, LIs->getUseIndex(SpillIndex)+1, LIs->getDefIndex(RestoreIndex)); - RepairLiveInterval(CurrLI, ValNo, DefMI, RestoreIndex); - + ReconstructLiveInterval(CurrLI); + + if (!FoldedRestore) { + unsigned RestoreIdx = LIs->getInstructionIndex(prior(RestorePt)); + RestoreIdx = LiveIntervals::getDefIndex(RestoreIdx); + RenumberValno(CurrLI->findDefinedVNInfo(RestoreIdx)); + } + ++NumSplits; return true; } @@ -1013,12 +1159,16 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { /// SplitRegLiveIntervals - Split all register live intervals that cross the /// barrier that's being processed. bool -PreAllocSplitting::SplitRegLiveIntervals(const TargetRegisterClass **RCs) { +PreAllocSplitting::SplitRegLiveIntervals(const TargetRegisterClass **RCs, + SmallPtrSet& Split) { // First find all the virtual registers whose live intervals are intercepted // by the current barrier. SmallVector Intervals; for (const TargetRegisterClass **RC = RCs; *RC; ++RC) { - if (TII->IgnoreRegisterClassBarriers(*RC)) + // FIXME: If it's not safe to move any instruction that defines the barrier + // register class, then it means there are some special dependencies which + // codegen is not modelling. Ignore these barriers for now. + if (!TII->isSafeToMoveRegClassDefs(*RC)) continue; std::vector &VRs = MRI->getRegClassVirtRegs(*RC); for (unsigned i = 0, e = VRs.size(); i != e; ++i) { @@ -1038,21 +1188,201 @@ PreAllocSplitting::SplitRegLiveIntervals(const TargetRegisterClass **RCs) { while (!Intervals.empty()) { if (PreSplitLimit != -1 && (int)NumSplits == PreSplitLimit) break; + else if (NumSplits == 4) + Change |= Change; LiveInterval *LI = Intervals.back(); Intervals.pop_back(); - Change |= SplitRegLiveInterval(LI); + bool result = SplitRegLiveInterval(LI); + if (result) Split.insert(LI); + Change |= result; } return Change; } +unsigned PreAllocSplitting::getNumberOfNonSpills( + SmallPtrSet& MIs, + unsigned Reg, int FrameIndex, + bool& FeedsTwoAddr) { + unsigned NonSpills = 0; + for (SmallPtrSet::iterator UI = MIs.begin(), UE = MIs.end(); + UI != UE; ++UI) { + int StoreFrameIndex; + unsigned StoreVReg = TII->isStoreToStackSlot(*UI, StoreFrameIndex); + if (StoreVReg != Reg || StoreFrameIndex != FrameIndex) + NonSpills++; + + int DefIdx = (*UI)->findRegisterDefOperandIdx(Reg); + if (DefIdx != -1 && (*UI)->isRegTiedToUseOperand(DefIdx)) + FeedsTwoAddr = true; + } + + return NonSpills; +} + +/// removeDeadSpills - After doing splitting, filter through all intervals we've +/// split, and see if any of the spills are unnecessary. If so, remove them. +bool PreAllocSplitting::removeDeadSpills(SmallPtrSet& split) { + bool changed = false; + + // Walk over all of the live intervals that were touched by the splitter, + // and see if we can do any DCE and/or folding. + for (SmallPtrSet::iterator LI = split.begin(), + LE = split.end(); LI != LE; ++LI) { + DenseMap > VNUseCount; + + // First, collect all the uses of the vreg, and sort them by their + // reaching definition (VNInfo). + for (MachineRegisterInfo::use_iterator UI = MRI->use_begin((*LI)->reg), + UE = MRI->use_end(); UI != UE; ++UI) { + unsigned index = LIs->getInstructionIndex(&*UI); + index = LiveIntervals::getUseIndex(index); + + const LiveRange* LR = (*LI)->getLiveRangeContaining(index); + VNUseCount[LR->valno].insert(&*UI); + } + + // Now, take the definitions (VNInfo's) one at a time and try to DCE + // and/or fold them away. + for (LiveInterval::vni_iterator VI = (*LI)->vni_begin(), + VE = (*LI)->vni_end(); VI != VE; ++VI) { + + if (DeadSplitLimit != -1 && (int)NumDeadSpills == DeadSplitLimit) + return changed; + + VNInfo* CurrVN = *VI; + + // We don't currently try to handle definitions with PHI kills, because + // it would involve processing more than one VNInfo at once. + if (CurrVN->hasPHIKill()) continue; + + // We also don't try to handle the results of PHI joins, since there's + // no defining instruction to analyze. + if (!CurrVN->isDefAccurate() || CurrVN->isUnused()) continue; + + // We're only interested in eliminating cruft introduced by the splitter, + // is of the form load-use or load-use-store. First, check that the + // definition is a load, and remember what stack slot we loaded it from. + MachineInstr* DefMI = LIs->getInstructionFromIndex(CurrVN->def); + int FrameIndex; + if (!TII->isLoadFromStackSlot(DefMI, FrameIndex)) continue; + + // If the definition has no uses at all, just DCE it. + if (VNUseCount[CurrVN].size() == 0) { + LIs->RemoveMachineInstrFromMaps(DefMI); + (*LI)->removeValNo(CurrVN); + DefMI->eraseFromParent(); + VNUseCount.erase(CurrVN); + NumDeadSpills++; + changed = true; + continue; + } + + // Second, get the number of non-store uses of the definition, as well as + // a flag indicating whether it feeds into a later two-address definition. + bool FeedsTwoAddr = false; + unsigned NonSpillCount = getNumberOfNonSpills(VNUseCount[CurrVN], + (*LI)->reg, FrameIndex, + FeedsTwoAddr); + + // If there's one non-store use and it doesn't feed a two-addr, then + // this is a load-use-store case that we can try to fold. + if (NonSpillCount == 1 && !FeedsTwoAddr) { + // Start by finding the non-store use MachineInstr. + SmallPtrSet::iterator UI = VNUseCount[CurrVN].begin(); + int StoreFrameIndex; + unsigned StoreVReg = TII->isStoreToStackSlot(*UI, StoreFrameIndex); + while (UI != VNUseCount[CurrVN].end() && + (StoreVReg == (*LI)->reg && StoreFrameIndex == FrameIndex)) { + ++UI; + if (UI != VNUseCount[CurrVN].end()) + StoreVReg = TII->isStoreToStackSlot(*UI, StoreFrameIndex); + } + if (UI == VNUseCount[CurrVN].end()) continue; + + MachineInstr* use = *UI; + + // Attempt to fold it away! + int OpIdx = use->findRegisterUseOperandIdx((*LI)->reg, false); + if (OpIdx == -1) continue; + SmallVector Ops; + Ops.push_back(OpIdx); + if (!TII->canFoldMemoryOperand(use, Ops)) continue; + + MachineInstr* NewMI = + TII->foldMemoryOperand(*use->getParent()->getParent(), + use, Ops, FrameIndex); + + if (!NewMI) continue; + + // Update relevant analyses. + LIs->RemoveMachineInstrFromMaps(DefMI); + LIs->ReplaceMachineInstrInMaps(use, NewMI); + (*LI)->removeValNo(CurrVN); + + DefMI->eraseFromParent(); + MachineBasicBlock* MBB = use->getParent(); + NewMI = MBB->insert(MBB->erase(use), NewMI); + VNUseCount[CurrVN].erase(use); + + // Remove deleted instructions. Note that we need to remove them from + // the VNInfo->use map as well, just to be safe. + for (SmallPtrSet::iterator II = + VNUseCount[CurrVN].begin(), IE = VNUseCount[CurrVN].end(); + II != IE; ++II) { + for (DenseMap >::iterator + VNI = VNUseCount.begin(), VNE = VNUseCount.end(); VNI != VNE; + ++VNI) + if (VNI->first != CurrVN) + VNI->second.erase(*II); + LIs->RemoveMachineInstrFromMaps(*II); + (*II)->eraseFromParent(); + } + + VNUseCount.erase(CurrVN); + + for (DenseMap >::iterator + VI = VNUseCount.begin(), VE = VNUseCount.end(); VI != VE; ++VI) + if (VI->second.erase(use)) + VI->second.insert(NewMI); + + NumDeadSpills++; + changed = true; + continue; + } + + // If there's more than one non-store instruction, we can't profitably + // fold it, so bail. + if (NonSpillCount) continue; + + // Otherwise, this is a load-store case, so DCE them. + for (SmallPtrSet::iterator UI = + VNUseCount[CurrVN].begin(), UE = VNUseCount[CurrVN].end(); + UI != UI; ++UI) { + LIs->RemoveMachineInstrFromMaps(*UI); + (*UI)->eraseFromParent(); + } + + VNUseCount.erase(CurrVN); + + LIs->RemoveMachineInstrFromMaps(DefMI); + (*LI)->removeValNo(CurrVN); + DefMI->eraseFromParent(); + NumDeadSpills++; + changed = true; + } + } + + return changed; +} + bool PreAllocSplitting::createsNewJoin(LiveRange* LR, MachineBasicBlock* DefMBB, MachineBasicBlock* BarrierMBB) { if (DefMBB == BarrierMBB) return false; - if (LR->valno->hasPHIKill) + if (LR->valno->hasPHIKill()) return false; unsigned MBBEnd = LIs->getMBBEndIdx(BarrierMBB); @@ -1114,11 +1444,13 @@ bool PreAllocSplitting::createsNewJoin(LiveRange* LR, bool PreAllocSplitting::runOnMachineFunction(MachineFunction &MF) { CurrMF = &MF; TM = &MF.getTarget(); + TRI = TM->getRegisterInfo(); TII = TM->getInstrInfo(); MFI = MF.getFrameInfo(); MRI = &MF.getRegInfo(); LIs = &getAnalysis(); LSs = &getAnalysis(); + VRM = &getAnalysis(); bool MadeChange = false; @@ -1128,6 +1460,8 @@ bool PreAllocSplitting::runOnMachineFunction(MachineFunction &MF) { MachineBasicBlock *Entry = MF.begin(); SmallPtrSet Visited; + SmallPtrSet Split; + for (df_ext_iterator > DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); DFI != E; ++DFI) { @@ -1140,9 +1474,11 @@ bool PreAllocSplitting::runOnMachineFunction(MachineFunction &MF) { if (!BarrierRCs) continue; BarrierIdx = LIs->getInstructionIndex(Barrier); - MadeChange |= SplitRegLiveIntervals(BarrierRCs); + MadeChange |= SplitRegLiveIntervals(BarrierRCs, Split); } } + MadeChange |= removeDeadSpills(Split); + return MadeChange; }