X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPreAllocSplitting.cpp;h=b2a7312fd2a5bf69eb07abc1f5448e13422f49bc;hb=6726b6d75a8b679068a58cb954ba97cf9d1690ba;hp=49cc67ba1f04e4fc19e661c17740e7275222ab10;hpb=d7250517b06250ca942847dfd6e51ede261c24c9;p=oota-llvm.git diff --git a/lib/CodeGen/PreAllocSplitting.cpp b/lib/CodeGen/PreAllocSplitting.cpp index 49cc67ba1f0..b2a7312fd2a 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,22 +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 { + class 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; @@ -61,7 +68,7 @@ namespace { MachineBasicBlock *BarrierMBB; // Barrier - Current barrier index. - unsigned BarrierIdx; + LiveIndex BarrierIdx; // CurrLI - Current live interval being split. LiveInterval *CurrLI; @@ -76,7 +83,7 @@ namespace { DenseMap IntervalSSMap; // Def2SpillMap - A map from a def instruction index to spill index. - DenseMap Def2SpillMap; + DenseMap Def2SpillMap; public: static char ID; @@ -85,6 +92,7 @@ namespace { virtual bool runOnMachineFunction(MachineFunction &MF); virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); AU.addRequired(); AU.addPreserved(); AU.addRequired(); @@ -96,8 +104,10 @@ namespace { AU.addPreservedID(PHIEliminationID); AU.addRequired(); AU.addRequired(); + AU.addRequired(); AU.addPreserved(); AU.addPreserved(); + AU.addPreserved(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -111,33 +121,31 @@ namespace { } /// print - Implement the dump method. - virtual void print(std::ostream &O, const Module* M = 0) const { + virtual void print(raw_ostream &O, const Module* M = 0) const { LIs->print(O, M); } - void print(std::ostream *O, const Module* M = 0) const { - if (O) print(*O, M); - } private: MachineBasicBlock::iterator findNextEmptySlot(MachineBasicBlock*, MachineInstr*, - unsigned&); + LiveIndex&); MachineBasicBlock::iterator findSpillPoint(MachineBasicBlock*, MachineInstr*, MachineInstr*, - SmallPtrSet&, unsigned&); + SmallPtrSet&, LiveIndex&); MachineBasicBlock::iterator - findRestorePoint(MachineBasicBlock*, MachineInstr*, unsigned, - SmallPtrSet&, unsigned&); + findRestorePoint(MachineBasicBlock*, MachineInstr*, LiveIndex, + SmallPtrSet&, LiveIndex&); int CreateSpillStackSlot(unsigned, const TargetRegisterClass *); - bool IsAvailableInStack(MachineBasicBlock*, unsigned, unsigned, unsigned, - unsigned&, int&) const; + bool IsAvailableInStack(MachineBasicBlock*, unsigned, + LiveIndex, LiveIndex, + LiveIndex&, int&) const; - void UpdateSpillSlotInterval(VNInfo*, unsigned, unsigned); + void UpdateSpillSlotInterval(VNInfo*, LiveIndex, LiveIndex); bool SplitRegLiveInterval(LiveInterval*); @@ -149,7 +157,7 @@ namespace { bool Rematerialize(unsigned vreg, VNInfo* ValNo, MachineInstr* DefMI, MachineBasicBlock::iterator RestorePt, - unsigned RestoreIdx, + LiveIndex RestoreIdx, SmallPtrSet& RefsInMBB); MachineInstr* FoldSpill(unsigned vreg, const TargetRegisterClass* RC, MachineInstr* DefMI, @@ -157,21 +165,35 @@ 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 getNumberOfSpills(SmallPtrSet& MIs, - unsigned Reg, int FrameIndex); - VNInfo* PerformPHIConstruction(MachineBasicBlock::iterator use, - MachineBasicBlock* MBB, - LiveInterval* LI, + 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 toplevel, bool intrablock); + bool IsTopLevel, bool IsIntraBlock); }; } // end anonymous namespace @@ -187,11 +209,12 @@ const PassInfo *const llvm::PreAllocSplittingID = &X; /// instruction index map. If there isn't one, return end(). MachineBasicBlock::iterator PreAllocSplitting::findNextEmptySlot(MachineBasicBlock *MBB, MachineInstr *MI, - unsigned &SpotIndex) { + LiveIndex &SpotIndex) { MachineBasicBlock::iterator MII = MI; if (++MII != MBB->end()) { - unsigned Index = LIs->findGapBeforeInstr(LIs->getInstructionIndex(MII)); - if (Index) { + LiveIndex Index = + LIs->findGapBeforeInstr(LIs->getInstructionIndex(MII)); + if (Index != LiveIndex()) { SpotIndex = Index; return MII; } @@ -207,35 +230,41 @@ MachineBasicBlock::iterator PreAllocSplitting::findSpillPoint(MachineBasicBlock *MBB, MachineInstr *MI, MachineInstr *DefMI, SmallPtrSet &RefsInMBB, - unsigned &SpillIndex) { + LiveIndex &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)) { + LiveIndex 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; @@ -247,48 +276,50 @@ PreAllocSplitting::findSpillPoint(MachineBasicBlock *MBB, MachineInstr *MI, /// found. MachineBasicBlock::iterator PreAllocSplitting::findRestorePoint(MachineBasicBlock *MBB, MachineInstr *MI, - unsigned LastIdx, + LiveIndex LastIdx, SmallPtrSet &RefsInMBB, - unsigned &RestoreIndex) { + LiveIndex &RestoreIndex) { // 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) { + LiveIndex Index = LIs->getInstructionIndex(MII); + if (Index > LastIdx) + break; + LiveIndex 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 != LiveIndex()) { + Pt = MII; + RestoreIndex = Gap; } + + if (RefsInMBB.count(MII)) + return Pt; + + ++MII; } return Pt; @@ -309,11 +340,12 @@ 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(LiveIndex(), 0, false, + LSs->getVNInfoAllocator()); return SS; } @@ -321,8 +353,9 @@ int PreAllocSplitting::CreateSpillStackSlot(unsigned Reg, /// slot at the specified index. bool PreAllocSplitting::IsAvailableInStack(MachineBasicBlock *DefMBB, - unsigned Reg, unsigned DefIndex, - unsigned RestoreIndex, unsigned &SpillIndex, + unsigned Reg, LiveIndex DefIndex, + LiveIndex RestoreIndex, + LiveIndex &SpillIndex, int& SS) const { if (!DefMBB) return false; @@ -330,7 +363,8 @@ PreAllocSplitting::IsAvailableInStack(MachineBasicBlock *DefMBB, DenseMap::iterator I = IntervalSSMap.find(Reg); if (I == IntervalSSMap.end()) return false; - DenseMap::iterator II = Def2SpillMap.find(DefIndex); + DenseMap::iterator + II = Def2SpillMap.find(DefIndex); if (II == Def2SpillMap.end()) return false; @@ -350,8 +384,8 @@ PreAllocSplitting::IsAvailableInStack(MachineBasicBlock *DefMBB, /// interval being split, and the spill and restore indicies, update the live /// interval of the spill stack slot. void -PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, unsigned SpillIndex, - unsigned RestoreIndex) { +PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, LiveIndex SpillIndex, + LiveIndex RestoreIndex) { assert(LIs->getMBBFromIndex(RestoreIndex) == BarrierMBB && "Expect restore in the barrier mbb"); @@ -364,8 +398,8 @@ PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, unsigned SpillIndex, } SmallPtrSet Processed; - unsigned EndIdx = LIs->getMBBEndIdx(MBB); - LiveRange SLR(SpillIndex, EndIdx+1, CurrSValNo); + LiveIndex EndIdx = LIs->getMBBEndIdx(MBB); + LiveRange SLR(SpillIndex, LIs->getNextSlot(EndIdx), CurrSValNo); CurrSLI->addRange(SLR); Processed.insert(MBB); @@ -384,7 +418,7 @@ PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, unsigned SpillIndex, WorkList.pop_back(); if (Processed.count(MBB)) continue; - unsigned Idx = LIs->getMBBStartIdx(MBB); + LiveIndex Idx = LIs->getMBBStartIdx(MBB); LR = CurrLI->getLiveRangeContaining(Idx); if (LR && LR->valno == ValNo) { EndIdx = LIs->getMBBEndIdx(MBB); @@ -394,7 +428,7 @@ PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, unsigned SpillIndex, CurrSLI->addRange(SLR); } else if (LR->end > EndIdx) { // Live range extends beyond end of mbb, process successors. - LiveRange SLR(Idx, EndIdx+1, CurrSValNo); + LiveRange SLR(Idx, LIs->getNextIndex(EndIdx), CurrSValNo); CurrSLI->addRange(SLR); for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) @@ -410,94 +444,35 @@ PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, unsigned SpillIndex, /// 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( - MachineBasicBlock::iterator use, - MachineBasicBlock* MBB, - LiveInterval* LI, +VNInfo* +PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI, + MachineBasicBlock* MBB, LiveInterval* LI, SmallPtrSet& Visited, DenseMap >& Defs, DenseMap >& Uses, DenseMap& NewVNs, DenseMap& LiveOut, DenseMap& Phis, - bool toplevel, bool intrablock) { + bool IsTopLevel, bool IsIntraBlock) { // Return memoized result if it's available. - if (toplevel && Visited.count(use) && NewVNs.count(use)) - return NewVNs[use]; - else if (!toplevel && intrablock && NewVNs.count(use)) - return NewVNs[use]; - else if (!intrablock && LiveOut.count(MBB)) + 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]; - typedef DenseMap > RegMap; - // Check if our block contains any uses or defs. bool ContainsDefs = Defs.count(MBB); bool ContainsUses = Uses.count(MBB); - VNInfo* ret = 0; + VNInfo* RetVNI = 0; // Enumerate the cases of use/def contaning blocks. if (!ContainsDefs && !ContainsUses) { - Fallback: - // 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); - - if (MBB->pred_size() == 1) { - Phis[MBB] = ret = PerformPHIConstruction((*MBB->pred_begin())->end(), - *(MBB->pred_begin()), LI, Visited, - Defs, Uses, NewVNs, LiveOut, Phis, - false, false); - unsigned EndIndex = 0; - if (intrablock) { - EndIndex = LIs->getInstructionIndex(use); - EndIndex = LiveIntervals::getUseIndex(EndIndex); - } else - EndIndex = LIs->getMBBEndIdx(MBB); - - LI->addRange(LiveRange(StartIndex, EndIndex+1, ret)); - if (intrablock) - LI->addKill(ret, EndIndex); - } else { - Phis[MBB] = ret = LI->getNextValue(~0U, /*FIXME*/ 0, - LIs->getVNInfoAllocator()); - if (!intrablock) LiveOut[MBB] = ret; - - // 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) { - VNInfo* Incoming = PerformPHIConstruction((*PI)->end(), *PI, LI, - Visited, Defs, Uses, NewVNs, - LiveOut, Phis, false, false); - if (Incoming != 0) - IncomingVNs[*PI] = Incoming; - } - - // 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->hasPHIKill = true; - unsigned KillIndex = LIs->getMBBEndIdx(I->first); - LI->addKill(I->second, KillIndex); - } - - unsigned EndIndex = 0; - if (intrablock) { - EndIndex = LIs->getInstructionIndex(use); - EndIndex = LiveIntervals::getUseIndex(EndIndex); - } else - EndIndex = LIs->getMBBEndIdx(MBB); - LI->addRange(LiveRange(StartIndex, EndIndex+1, ret)); - if (intrablock) - LI->addKill(ret, EndIndex); - } + return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, Uses, + NewVNs, LiveOut, Phis, + IsTopLevel, IsIntraBlock); } else if (ContainsDefs && !ContainsUses) { SmallPtrSet& BlockDefs = Defs[MBB]; @@ -505,71 +480,75 @@ VNInfo* PreAllocSplitting::PerformPHIConstruction( // 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(use == MBB->end() && "No use marked in intrablock"); + assert(UseI == MBB->end() && "No use marked in intrablock"); - MachineBasicBlock::iterator walker = use; - --walker; - while (walker != MBB->begin()) - if (BlockDefs.count(walker)) { + MachineBasicBlock::iterator Walker = UseI; + --Walker; + while (Walker != MBB->begin()) { + if (BlockDefs.count(Walker)) break; - } else - --walker; + --Walker; + } // 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); + LiveIndex DefIndex = LIs->getInstructionIndex(Walker); + DefIndex = LIs->getDefIndex(DefIndex); + LiveIndex EndIndex = LIs->getMBBEndIdx(MBB); - ret = NewVNs[walker]; - LI->addRange(LiveRange(DefIndex, EndIndex+1, ret)); + RetVNI = NewVNs[Walker]; + LI->addRange(LiveRange(DefIndex, LIs->getNextSlot(EndIndex), 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 (use == MBB->begin()) - goto Fallback; + // 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 = use; - --walker; + MachineBasicBlock::iterator Walker = UseI; + --Walker; bool found = false; - while (walker != MBB->begin()) - if (BlockUses.count(walker)) { + while (Walker != MBB->begin()) { + if (BlockUses.count(Walker)) { found = true; break; - } else - --walker; + } + --Walker; + } // Must check begin() too. if (!found) { - if (BlockUses.count(walker)) + if (BlockUses.count(Walker)) found = true; else - goto Fallback; + return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, + Uses, NewVNs, LiveOut, Phis, + IsTopLevel, IsIntraBlock); } - unsigned UseIndex = LIs->getInstructionIndex(walker); - UseIndex = LiveIntervals::getUseIndex(UseIndex); - unsigned EndIndex = 0; - if (intrablock) { - EndIndex = LIs->getInstructionIndex(use); - EndIndex = LiveIntervals::getUseIndex(EndIndex); + LiveIndex UseIndex = LIs->getInstructionIndex(Walker); + UseIndex = LIs->getUseIndex(UseIndex); + LiveIndex EndIndex; + if (IsIntraBlock) { + EndIndex = LIs->getInstructionIndex(UseI); + EndIndex = LIs->getUseIndex(EndIndex); } else EndIndex = LIs->getMBBEndIdx(MBB); // Now, recursively phi construct the VNInfo for the use we found, // and then extend it to include the instruction we care about - ret = PerformPHIConstruction(walker, MBB, LI, Visited, Defs, Uses, - NewVNs, LiveOut, Phis, false, true); + RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses, + NewVNs, LiveOut, Phis, false, true); - LI->addRange(LiveRange(UseIndex, EndIndex+1, ret)); + LI->addRange(LiveRange(UseIndex, LIs->getNextSlot(EndIndex), RetVNI)); // FIXME: Need to set kills properly for inter-block stuff. - if (LI->isKill(ret, UseIndex)) LI->removeKill(ret, UseIndex); - if (intrablock) - LI->addKill(ret, EndIndex); - } else if (ContainsDefs && ContainsUses){ + if (RetVNI->isKill(UseIndex)) RetVNI->removeKill(UseIndex); + if (IsIntraBlock) + RetVNI->addKill(EndIndex); + } else if (ContainsDefs && ContainsUses) { SmallPtrSet& BlockDefs = Defs[MBB]; SmallPtrSet& BlockUses = Uses[MBB]; @@ -577,67 +556,161 @@ VNInfo* PreAllocSplitting::PerformPHIConstruction( // special note that checking for defs must take precedence over checking // for uses, because of two-address instructions. - if (use == MBB->begin()) - goto Fallback; + if (UseI == MBB->begin()) + return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, Uses, + NewVNs, LiveOut, Phis, + IsTopLevel, IsIntraBlock); - MachineBasicBlock::iterator walker = use; - --walker; + MachineBasicBlock::iterator Walker = UseI; + --Walker; bool foundDef = false; bool foundUse = false; - while (walker != MBB->begin()) - if (BlockDefs.count(walker)) { + while (Walker != MBB->begin()) { + if (BlockDefs.count(Walker)) { foundDef = true; break; - } else if (BlockUses.count(walker)) { + } else if (BlockUses.count(Walker)) { foundUse = true; break; - } else - --walker; + } + --Walker; + } // Must check begin() too. if (!foundDef && !foundUse) { - if (BlockDefs.count(walker)) + if (BlockDefs.count(Walker)) foundDef = true; - else if (BlockUses.count(walker)) + else if (BlockUses.count(Walker)) foundUse = true; else - goto Fallback; + return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, + Uses, NewVNs, LiveOut, Phis, + IsTopLevel, IsIntraBlock); } - unsigned StartIndex = LIs->getInstructionIndex(walker); - StartIndex = foundDef ? LiveIntervals::getDefIndex(StartIndex) : - LiveIntervals::getUseIndex(StartIndex); - unsigned EndIndex = 0; - if (intrablock) { - EndIndex = LIs->getInstructionIndex(use); - EndIndex = LiveIntervals::getUseIndex(EndIndex); + LiveIndex StartIndex = LIs->getInstructionIndex(Walker); + StartIndex = foundDef ? LIs->getDefIndex(StartIndex) : + LIs->getUseIndex(StartIndex); + LiveIndex EndIndex; + if (IsIntraBlock) { + EndIndex = LIs->getInstructionIndex(UseI); + EndIndex = LIs->getUseIndex(EndIndex); } else EndIndex = LIs->getMBBEndIdx(MBB); if (foundDef) - ret = NewVNs[walker]; + RetVNI = NewVNs[Walker]; else - ret = PerformPHIConstruction(walker, MBB, LI, Visited, Defs, Uses, - NewVNs, LiveOut, Phis, false, true); + RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses, + NewVNs, LiveOut, Phis, false, true); - LI->addRange(LiveRange(StartIndex, EndIndex+1, ret)); + LI->addRange(LiveRange(StartIndex, LIs->getNextSlot(EndIndex), RetVNI)); - if (foundUse && LI->isKill(ret, StartIndex)) - LI->removeKill(ret, StartIndex); - if (intrablock) { - LI->addKill(ret, EndIndex); + if (foundUse && RetVNI->isKill(StartIndex)) + RetVNI->removeKill(StartIndex); + if (IsIntraBlock) { + RetVNI->addKill(EndIndex); } } // Memoize results so we don't have to recompute them. - if (!intrablock) LiveOut[MBB] = ret; + if (!IsIntraBlock) LiveOut[MBB] = RetVNI; else { - if (!NewVNs.count(use)) - NewVNs[use] = ret; - Visited.insert(use); + if (!NewVNs.count(UseI)) + NewVNs[UseI] = RetVNI; + Visited.insert(UseI); } - return ret; + return RetVNI; +} + +/// 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]; + + LiveIndex StartIndex = LIs->getMBBStartIdx(MBB); + VNInfo *RetVNI = Phis[MBB] = + LI->getNextValue(LiveIndex(), /*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) { + 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); + LiveIndex KillIndex = LIs->getMBBEndIdx(I->first); + if (!I->second->isKill(KillIndex)) + I->second->addKill(KillIndex); + } + } + + LiveIndex EndIndex; + if (IsIntraBlock) { + EndIndex = LIs->getInstructionIndex(UseI); + EndIndex = LIs->getUseIndex(EndIndex); + } else + EndIndex = LIs->getMBBEndIdx(MBB); + LI->addRange(LiveRange(StartIndex, LIs->getNextSlot(EndIndex), RetVNI)); + if (IsIntraBlock) + RetVNI->addKill(EndIndex); + + // 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 RetVNI; } /// ReconstructLiveInterval - Recompute a live interval from scratch. @@ -660,16 +733,18 @@ void PreAllocSplitting::ReconstructLiveInterval(LiveInterval* LI) { DE = MRI->def_end(); DI != DE; ++DI) { Defs[(*DI).getParent()].insert(&*DI); - unsigned DefIdx = LIs->getInstructionIndex(&*DI); - DefIdx = LiveIntervals::getDefIndex(DefIdx); + LiveIndex DefIdx = LIs->getInstructionIndex(&*DI); + DefIdx = LIs->getDefIndex(DefIdx); - VNInfo* NewVN = LI->getNextValue(DefIdx, 0, Alloc); + 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->copy = &*DI; + NewVN->setCopy(&*DI); NewVNs[&*DI] = NewVN; } @@ -694,14 +769,32 @@ void PreAllocSplitting::ReconstructLiveInterval(LiveInterval* LI) { // 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); + LiveIndex DefIdx = LIs->getInstructionIndex(&*DI); + DefIdx = LIs->getDefIndex(DefIdx); if (LI->liveAt(DefIdx)) continue; VNInfo* DeadVN = NewVNs[&*DI]; - LI->addRange(LiveRange(DefIdx, DefIdx+1, DeadVN)); - LI->addKill(DeadVN, DefIdx); + LI->addRange(LiveRange(DefIdx, LIs->getNextSlot(DefIdx), DeadVN)); + DeadVN->addKill(DefIdx); + } + + // Update kill markers. + for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end(); + VI != VE; ++VI) { + VNInfo* VNI = *VI; + for (unsigned i = 0, e = VNI->kills.size(); i != e; ++i) { + LiveIndex KillIdx = VNI->kills[i]; + if (KillIdx.isPHIIndex()) + continue; + MachineInstr *KillMI = LIs->getInstructionFromIndex(KillIdx); + if (KillMI) { + MachineOperand *KillMO = KillMI->findRegisterUseOperand(CurrLI->reg); + if (KillMO) + // It could be a dead def. + KillMO->setIsKill(); + } + } } } @@ -726,20 +819,22 @@ void PreAllocSplitting::RenumberValno(VNInfo* VN) { // Bail out if we ever encounter a valno that has a PHI kill. We can't // renumber these. - if (OldVN->hasPHIKill) return; + if (OldVN->hasPHIKill()) return; VNsToCopy.push_back(OldVN); // Locate two-address redefinitions - for (SmallVector::iterator KI = OldVN->kills.begin(), + for (VNInfo::KillSet::iterator KI = OldVN->kills.begin(), KE = OldVN->kills.end(); KI != KE; ++KI) { + assert(!KI->isPHIIndex() && + "VN previously reported having no PHI kills."); MachineInstr* MI = LIs->getInstructionFromIndex(*KI); - //if (!MI) continue; 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)); + CurrLI->findDefinedVNInfoForRegInt(LIs->getDefIndex(*KI)); + if (NextVN == OldVN) continue; Stack.push_back(NextVN); } } @@ -756,9 +851,7 @@ void PreAllocSplitting::RenumberValno(VNInfo* VN) { VNInfo* OldVN = *OI; // Copy the valno over - VNInfo* NewVN = NewLI.getNextValue(OldVN->def, OldVN->copy, - LIs->getVNInfoAllocator()); - NewLI.copyValNumInfo(NewVN, OldVN); + VNInfo* NewVN = NewLI.createValueCopy(OldVN, LIs->getVNInfoAllocator()); NewLI.MergeValueInAsValue(*CurrLI, OldVN, NewVN); // Remove the valno from the old interval @@ -772,10 +865,10 @@ void PreAllocSplitting::RenumberValno(VNInfo* VN) { for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(CurrLI->reg), E = MRI->reg_end(); I != E; ++I) { MachineOperand& MO = I.getOperand(); - unsigned InstrIdx = LIs->getInstructionIndex(&*I); + LiveIndex InstrIdx = LIs->getInstructionIndex(&*I); - if ((MO.isUse() && NewLI.liveAt(LiveIntervals::getUseIndex(InstrIdx))) || - (MO.isDef() && NewLI.liveAt(LiveIntervals::getDefIndex(InstrIdx)))) + if ((MO.isUse() && NewLI.liveAt(LIs->getUseIndex(InstrIdx))) || + (MO.isDef() && NewLI.liveAt(LIs->getDefIndex(InstrIdx)))) OpsToChange.push_back(std::make_pair(&*I, I.getOperandNo())); } @@ -787,19 +880,26 @@ 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, + LiveIndex RestoreIdx, SmallPtrSet& RefsInMBB) { MachineBasicBlock& MBB = *RestorePt->getParent(); MachineBasicBlock::iterator KillPt = BarrierMBB->end(); - unsigned KillIdx = 0; - if (ValNo->def == ~0U || DefMI->getParent() == BarrierMBB) + LiveIndex KillIdx; + if (!ValNo->isDefAccurate() || DefMI->getParent() == BarrierMBB) KillPt = findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, KillIdx); else KillPt = findNextEmptySlot(DefMI->getParent(), DefMI, KillIdx); @@ -807,13 +907,13 @@ 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); ReconstructLiveInterval(CurrLI); - unsigned RematIdx = LIs->getInstructionIndex(prior(RestorePt)); - RematIdx = LiveIntervals::getDefIndex(RematIdx); - RenumberValno(CurrLI->findDefinedVNInfo(RematIdx)); + LiveIndex RematIdx = LIs->getInstructionIndex(prior(RestorePt)); + RematIdx = LIs->getDefIndex(RematIdx); + RenumberValno(CurrLI->findDefinedVNInfoForRegInt(RematIdx)); ++NumSplits; ++NumRemats; @@ -853,7 +953,6 @@ MachineInstr* PreAllocSplitting::FoldSpill(unsigned vreg, SS = I->second; } else { SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment()); - } MachineInstr* FMI = TII->foldMemoryOperand(*MBB->getParent(), @@ -865,11 +964,85 @@ 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(LiveIndex(), 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; @@ -886,13 +1059,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. @@ -909,7 +1078,7 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { } // Find a point to restore the value after the barrier. - unsigned RestoreIndex = 0; + LiveIndex RestoreIndex; MachineBasicBlock::iterator RestorePt = findRestorePoint(BarrierMBB, Barrier, LR->end, RefsInMBB, RestoreIndex); if (RestorePt == BarrierMBB->end()) @@ -923,11 +1092,11 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { // Add a spill either before the barrier or after the definition. MachineBasicBlock *DefMBB = DefMI ? DefMI->getParent() : NULL; const TargetRegisterClass *RC = MRI->getRegClass(CurrLI->reg); - unsigned SpillIndex = 0; + LiveIndex SpillIndex; 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); @@ -951,7 +1120,7 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { return false; // Def is dead. Do nothing. if ((SpillMI = FoldSpill(LI->reg, RC, DefMI, Barrier, - BarrierMBB, SS, RefsInMBB))) { + BarrierMBB, SS, RefsInMBB))) { SpillIndex = LIs->getInstructionIndex(SpillMI); } else { // Check if it's possible to insert a spill after the def MI. @@ -967,11 +1136,9 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { if (SpillPt == DefMBB->end()) return false; // No gap to insert spill. } - // Add spill. The store instruction kills the register if def is before - // the barrier in the barrier block. + // Add spill. SS = CreateSpillStackSlot(CurrLI->reg, RC); - TII->storeRegToStackSlot(*DefMBB, SpillPt, CurrLI->reg, - DefMBB == BarrierMBB, SS, RC); + TII->storeRegToStackSlot(*DefMBB, SpillPt, CurrLI->reg, false, SS, RC); SpillMI = prior(SpillPt); LIs->InsertMachineInstrInMaps(SpillMI, SpillIndex); } @@ -982,18 +1149,29 @@ 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); + 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, + UpdateSpillSlotInterval(ValNo, LIs->getNextSlot(LIs->getUseIndex(SpillIndex)), LIs->getDefIndex(RestoreIndex)); ReconstructLiveInterval(CurrLI); - unsigned RestoreIdx = LIs->getInstructionIndex(prior(RestorePt)); - RestoreIdx = LiveIntervals::getDefIndex(RestoreIdx); - RenumberValno(CurrLI->findDefinedVNInfo(RestoreIdx)); + + if (!FoldedRestore) { + LiveIndex RestoreIdx = LIs->getInstructionIndex(prior(RestorePt)); + RestoreIdx = LIs->getDefIndex(RestoreIdx); + RenumberValno(CurrLI->findDefinedVNInfoForRegInt(RestoreIdx)); + } ++NumSplits; return true; @@ -1008,7 +1186,10 @@ PreAllocSplitting::SplitRegLiveIntervals(const TargetRegisterClass **RCs, // 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) { @@ -1028,8 +1209,6 @@ 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(); bool result = SplitRegLiveInterval(LI); @@ -1040,19 +1219,24 @@ PreAllocSplitting::SplitRegLiveIntervals(const TargetRegisterClass **RCs, return Change; } -unsigned PreAllocSplitting::getNumberOfSpills( +unsigned PreAllocSplitting::getNumberOfNonSpills( SmallPtrSet& MIs, - unsigned Reg, int FrameIndex) { - unsigned Spills = 0; + unsigned Reg, int FrameIndex, + bool& FeedsTwoAddr) { + unsigned NonSpills = 0; for (SmallPtrSet::iterator UI = MIs.begin(), UE = MIs.end(); - UI != UI; ++UI) { + UI != UE; ++UI) { int StoreFrameIndex; unsigned StoreVReg = TII->isStoreToStackSlot(*UI, StoreFrameIndex); - if (StoreVReg == Reg && StoreFrameIndex == FrameIndex) - Spills++; + if (StoreVReg != Reg || StoreFrameIndex != FrameIndex) + NonSpills++; + + int DefIdx = (*UI)->findRegisterDefOperandIdx(Reg); + if (DefIdx != -1 && (*UI)->isRegTiedToUseOperand(DefIdx)) + FeedsTwoAddr = true; } - return Spills; + return NonSpills; } /// removeDeadSpills - After doing splitting, filter through all intervals we've @@ -1060,44 +1244,137 @@ unsigned PreAllocSplitting::getNumberOfSpills( 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); + LiveIndex index = LIs->getInstructionIndex(&*UI); + index = LIs->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; - if (CurrVN->hasPHIKill) continue; - unsigned DefIdx = CurrVN->def; - if (DefIdx == ~0U || DefIdx == ~1U) continue; + // 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; - MachineInstr* DefMI = LIs->getInstructionFromIndex(DefIdx); + // 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; } - unsigned SpillCount = getNumberOfSpills(VNUseCount[CurrVN], - (*LI)->reg, FrameIndex); - if (SpillCount != VNUseCount[CurrVN].size()) 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) { @@ -1105,6 +1382,8 @@ bool PreAllocSplitting::removeDeadSpills(SmallPtrSet& split) { (*UI)->eraseFromParent(); } + VNUseCount.erase(CurrVN); + LIs->RemoveMachineInstrFromMaps(DefMI); (*LI)->removeValNo(CurrVN); DefMI->eraseFromParent(); @@ -1122,10 +1401,10 @@ bool PreAllocSplitting::createsNewJoin(LiveRange* LR, if (DefMBB == BarrierMBB) return false; - if (LR->valno->hasPHIKill) + if (LR->valno->hasPHIKill()) return false; - unsigned MBBEnd = LIs->getMBBEndIdx(BarrierMBB); + LiveIndex MBBEnd = LIs->getMBBEndIdx(BarrierMBB); if (LR->end < MBBEnd) return false; @@ -1184,11 +1463,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;