X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPreAllocSplitting.cpp;h=d6e31dae9d13669f555b0806c18b3c320a183cdf;hb=324a24f6aa5d6752c57c39e1e19f00b8c8a4ceec;hp=f08bc20d954c0b52a50660f5fa1bd45aabb5a6d5;hpb=c93023a89e9f3c4937a4b23db13f974afac94e50;p=oota-llvm.git diff --git a/lib/CodeGen/PreAllocSplitting.cpp b/lib/CodeGen/PreAllocSplitting.cpp index f08bc20d954..d6e31dae9d1 100644 --- a/lib/CodeGen/PreAllocSplitting.cpp +++ b/lib/CodeGen/PreAllocSplitting.cpp @@ -15,6 +15,8 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "pre-alloc-split" +#include "VirtRegMap.h" +#include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineDominators.h" @@ -30,6 +32,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,24 +40,30 @@ 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 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; + SlotIndexes *SIs; LiveIntervals *LIs; LiveStacks *LSs; + VirtRegMap *VRM; // Barrier - Current barrier being processed. MachineInstr *Barrier; @@ -63,7 +72,7 @@ namespace { MachineBasicBlock *BarrierMBB; // Barrier - Current barrier index. - unsigned BarrierIdx; + SlotIndex BarrierIdx; // CurrLI - Current live interval being split. LiveInterval *CurrLI; @@ -78,28 +87,34 @@ namespace { DenseMap IntervalSSMap; // Def2SpillMap - A map from a def instruction index to spill index. - DenseMap Def2SpillMap; + DenseMap Def2SpillMap; public: static char ID; - PreAllocSplitting() : MachineFunctionPass(&ID) {} + PreAllocSplitting() : MachineFunctionPass(ID) { + initializePreAllocSplittingPass(*PassRegistry::getPassRegistry()); + } virtual bool runOnMachineFunction(MachineFunction &MF); virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addPreserved(); AU.addRequired(); AU.addPreserved(); AU.addRequired(); AU.addPreserved(); AU.addPreserved(); - if (StrongPHIElim) - AU.addPreservedID(StrongPHIEliminationID); - else - AU.addPreservedID(PHIEliminationID); + AU.addPreserved(); + AU.addPreservedID(StrongPHIEliminationID); + AU.addPreservedID(PHIEliminationID); AU.addRequired(); AU.addRequired(); + AU.addRequired(); AU.addPreserved(); AU.addPreserved(); + AU.addPreserved(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -113,33 +128,28 @@ 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&); MachineBasicBlock::iterator findSpillPoint(MachineBasicBlock*, MachineInstr*, MachineInstr*, - SmallPtrSet&, unsigned&); + SmallPtrSet&); MachineBasicBlock::iterator - findRestorePoint(MachineBasicBlock*, MachineInstr*, unsigned, - SmallPtrSet&, unsigned&); + findRestorePoint(MachineBasicBlock*, MachineInstr*, SlotIndex, + SmallPtrSet&); int CreateSpillStackSlot(unsigned, const TargetRegisterClass *); - bool IsAvailableInStack(MachineBasicBlock*, unsigned, unsigned, unsigned, - unsigned&, int&) const; + bool IsAvailableInStack(MachineBasicBlock*, unsigned, + SlotIndex, SlotIndex, + SlotIndex&, int&) const; - void UpdateSpillSlotInterval(VNInfo*, unsigned, unsigned); + void UpdateSpillSlotInterval(VNInfo*, SlotIndex, SlotIndex); bool SplitRegLiveInterval(LiveInterval*); @@ -151,7 +161,6 @@ namespace { bool Rematerialize(unsigned vreg, VNInfo* ValNo, MachineInstr* DefMI, MachineBasicBlock::iterator RestorePt, - unsigned RestoreIdx, SmallPtrSet& RefsInMBB); MachineInstr* FoldSpill(unsigned vreg, const TargetRegisterClass* RC, MachineInstr* DefMI, @@ -193,27 +202,20 @@ namespace { char PreAllocSplitting::ID = 0; -static RegisterPass -X("pre-alloc-splitting", "Pre-Register Allocation Live Interval Splitting"); - -const PassInfo *const llvm::PreAllocSplittingID = &X; - - -/// findNextEmptySlot - Find a gap after the given machine instruction in the -/// instruction index map. If there isn't one, return end(). -MachineBasicBlock::iterator -PreAllocSplitting::findNextEmptySlot(MachineBasicBlock *MBB, MachineInstr *MI, - unsigned &SpotIndex) { - MachineBasicBlock::iterator MII = MI; - if (++MII != MBB->end()) { - unsigned Index = LIs->findGapBeforeInstr(LIs->getInstructionIndex(MII)); - if (Index) { - SpotIndex = Index; - return MII; - } - } - return MBB->end(); -} +INITIALIZE_PASS_BEGIN(PreAllocSplitting, "pre-alloc-splitting", + "Pre-Register Allocation Live Interval Splitting", + false, false) +INITIALIZE_PASS_DEPENDENCY(SlotIndexes) +INITIALIZE_PASS_DEPENDENCY(LiveIntervals) +INITIALIZE_PASS_DEPENDENCY(LiveStacks) +INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) +INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) +INITIALIZE_PASS_DEPENDENCY(VirtRegMap) +INITIALIZE_PASS_END(PreAllocSplitting, "pre-alloc-splitting", + "Pre-Register Allocation Live Interval Splitting", + false, false) + +char &llvm::PreAllocSplittingID = PreAllocSplitting::ID; /// findSpillPoint - Find a gap as far away from the given MI that's suitable /// for spilling the current live interval. The index must be before any @@ -222,72 +224,38 @@ PreAllocSplitting::findNextEmptySlot(MachineBasicBlock *MBB, MachineInstr *MI, MachineBasicBlock::iterator PreAllocSplitting::findSpillPoint(MachineBasicBlock *MBB, MachineInstr *MI, MachineInstr *DefMI, - SmallPtrSet &RefsInMBB, - unsigned &SpillIndex) { + SmallPtrSet &RefsInMBB) { 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; - - if (MII == EndPt) return Pt; + MachineBasicBlock::iterator MII = MI; + MachineBasicBlock::iterator EndPt = DefMI + ? MachineBasicBlock::iterator(DefMI) : MBB->begin(); - do { - ++MII; - unsigned Index = LIs->getInstructionIndex(MII); - unsigned Gap = LIs->findGapBeforeInstr(Index); - - // We can't insert the spill between the barrier (a call), and its - // corresponding call frame setup/teardown. - if (prior(MII)->getOpcode() == TRI->getCallFrameSetupOpcode()) { - bool reachedBarrier = false; - do { - if (MII == EndPt) { - reachedBarrier = true; - break; - } - ++MII; - } while (MII->getOpcode() != TRI->getCallFrameDestroyOpcode()); - - if (reachedBarrier) break; - } else 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) && + 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 (prior(MII)->getOpcode() == TRI->getCallFrameSetupOpcode()) { + while (MII != EndPt && !RefsInMBB.count(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; - continue; - } if (MII->getOpcode() == TRI->getCallFrameDestroyOpcode()) { - bool reachedBarrier = false; - while (MII->getOpcode() != TRI->getCallFrameSetupOpcode()) { - --MII; - if (MII == EndPt) { - reachedBarrier = true; - break; - } + if (MII == EndPt) { + return Pt; } - - if (reachedBarrier) break; - else continue; - } else if (LIs->hasGapBeforeInstr(Index)) { - Pt = MII; - SpillIndex = LIs->findGapBeforeInstr(Index, true); } - --MII; + continue; + } else { + Pt = MII; } + + if (RefsInMBB.count(MII)) + return Pt; + + + --MII; } return Pt; @@ -299,87 +267,47 @@ PreAllocSplitting::findSpillPoint(MachineBasicBlock *MBB, MachineInstr *MI, /// found. MachineBasicBlock::iterator PreAllocSplitting::findRestorePoint(MachineBasicBlock *MBB, MachineInstr *MI, - unsigned LastIdx, - SmallPtrSet &RefsInMBB, - unsigned &RestoreIndex) { + SlotIndex LastIdx, + SmallPtrSet &RefsInMBB) { // 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; - - if (MII == EndPt) return Pt; - - --MII; - do { - unsigned Index = LIs->getInstructionIndex(MII); - 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->getCallFrameDestroyOpcode()) { - bool reachedBarrier = false; - while (MII->getOpcode() != TRI->getCallFrameSetupOpcode()) { - --MII; - if (MII == EndPt) { - reachedBarrier = true; - break; - } - } - - if (reachedBarrier) break; - else continue; - } else 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->getFirstTerminator()) { - unsigned Index = LIs->getInstructionIndex(MII); - if (Index > LastIdx) - break; - unsigned Gap = LIs->findGapBeforeInstr(Index); + // 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) { + SlotIndex Index = LIs->getInstructionIndex(MII); + if (Index > LastIdx) + break; - // We can't insert a restore between the barrier (a call) and its - // corresponding call frame teardown. - if (MII->getOpcode() == TRI->getCallFrameDestroyOpcode()) { + // 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; - continue; - } else if (prior(MII)->getOpcode() == TRI->getCallFrameSetupOpcode()) { - bool reachedBarrier = false; - do { - if (MII == MBB->getFirstTerminator() || RefsInMBB.count(MII)) { - reachedBarrier = true; - break; - } - - ++MII; - } while (MII->getOpcode() != TRI->getCallFrameDestroyOpcode()); - - if (reachedBarrier) break; - } else if (Gap) { - Pt = MII; - RestoreIndex = Gap; - } - - if (RefsInMBB.count(MII)) - break; - ++MII; + } while (MII->getOpcode() != TRI->getCallFrameDestroyOpcode()); + } else { + Pt = MII; } + + if (RefsInMBB.count(MII)) + return Pt; + + ++MII; } return Pt; @@ -395,16 +323,17 @@ int PreAllocSplitting::CreateSpillStackSlot(unsigned Reg, if (I != IntervalSSMap.end()) { SS = I->second; } else { - SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment()); + SS = MFI->CreateSpillStackObject(RC->getSize(), RC->getAlignment()); IntervalSSMap[Reg] = SS; } // 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(SlotIndex(), 0, + LSs->getVNInfoAllocator()); return SS; } @@ -412,16 +341,18 @@ 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, SlotIndex DefIndex, + SlotIndex RestoreIndex, + SlotIndex &SpillIndex, int& SS) const { if (!DefMBB) return false; - DenseMap::iterator I = IntervalSSMap.find(Reg); + DenseMap::const_iterator I = IntervalSSMap.find(Reg); if (I == IntervalSSMap.end()) return false; - DenseMap::iterator II = Def2SpillMap.find(DefIndex); + DenseMap::const_iterator + II = Def2SpillMap.find(DefIndex); if (II == Def2SpillMap.end()) return false; @@ -441,8 +372,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, SlotIndex SpillIndex, + SlotIndex RestoreIndex) { assert(LIs->getMBBFromIndex(RestoreIndex) == BarrierMBB && "Expect restore in the barrier mbb"); @@ -455,8 +386,8 @@ PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, unsigned SpillIndex, } SmallPtrSet Processed; - unsigned EndIdx = LIs->getMBBEndIdx(MBB); - LiveRange SLR(SpillIndex, EndIdx+1, CurrSValNo); + SlotIndex EndIdx = LIs->getMBBEndIdx(MBB); + LiveRange SLR(SpillIndex, EndIdx, CurrSValNo); CurrSLI->addRange(SLR); Processed.insert(MBB); @@ -475,7 +406,7 @@ PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, unsigned SpillIndex, WorkList.pop_back(); if (Processed.count(MBB)) continue; - unsigned Idx = LIs->getMBBStartIdx(MBB); + SlotIndex Idx = LIs->getMBBStartIdx(MBB); LR = CurrLI->getLiveRangeContaining(Idx); if (LR && LR->valno == ValNo) { EndIdx = LIs->getMBBEndIdx(MBB); @@ -485,7 +416,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, EndIdx.getNextIndex(), CurrSValNo); CurrSLI->addRange(SLR); for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) @@ -548,49 +479,37 @@ PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI, } // 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); + SlotIndex DefIndex = LIs->getInstructionIndex(Walker); + DefIndex = DefIndex.getDefIndex(); + SlotIndex EndIndex = LIs->getMBBEndIdx(MBB); RetVNI = NewVNs[Walker]; - LI->addRange(LiveRange(DefIndex, EndIndex+1, RetVNI)); + LI->addRange(LiveRange(DefIndex, 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 (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()) { + --Walker; 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); } - unsigned UseIndex = LIs->getInstructionIndex(Walker); - UseIndex = LiveIntervals::getUseIndex(UseIndex); - unsigned EndIndex = 0; + if (!found) + return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, + Uses, NewVNs, LiveOut, Phis, + IsTopLevel, IsIntraBlock); + + SlotIndex UseIndex = LIs->getInstructionIndex(Walker); + UseIndex = UseIndex.getUseIndex(); + SlotIndex EndIndex; if (IsIntraBlock) { - EndIndex = LIs->getInstructionIndex(UseI); - EndIndex = LiveIntervals::getUseIndex(EndIndex); + EndIndex = LIs->getInstructionIndex(UseI).getDefIndex(); } else EndIndex = LIs->getMBBEndIdx(MBB); @@ -599,12 +518,9 @@ PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI, RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses, NewVNs, LiveOut, Phis, false, true); - LI->addRange(LiveRange(UseIndex, EndIndex+1, RetVNI)); + LI->addRange(LiveRange(UseIndex, EndIndex, 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); } else if (ContainsDefs && ContainsUses) { SmallPtrSet& BlockDefs = Defs[MBB]; SmallPtrSet& BlockUses = Uses[MBB]; @@ -612,17 +528,11 @@ PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI, // 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()) { + --Walker; if (BlockDefs.count(Walker)) { foundDef = true; break; @@ -630,28 +540,18 @@ PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI, foundUse = true; 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); } - unsigned StartIndex = LIs->getInstructionIndex(Walker); - StartIndex = foundDef ? LiveIntervals::getDefIndex(StartIndex) : - LiveIntervals::getUseIndex(StartIndex); - unsigned EndIndex = 0; + if (!foundDef && !foundUse) + return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, + Uses, NewVNs, LiveOut, Phis, + IsTopLevel, IsIntraBlock); + + SlotIndex StartIndex = LIs->getInstructionIndex(Walker); + StartIndex = foundDef ? StartIndex.getDefIndex() : StartIndex.getUseIndex(); + SlotIndex EndIndex; if (IsIntraBlock) { - EndIndex = LIs->getInstructionIndex(UseI); - EndIndex = LiveIntervals::getUseIndex(EndIndex); + EndIndex = LIs->getInstructionIndex(UseI).getDefIndex(); } else EndIndex = LIs->getMBBEndIdx(MBB); @@ -661,13 +561,7 @@ PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI, RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses, NewVNs, LiveOut, Phis, false, true); - LI->addRange(LiveRange(StartIndex, EndIndex+1, RetVNI)); - - if (foundUse && LI->isKill(RetVNI, StartIndex)) - LI->removeKill(RetVNI, StartIndex); - if (IsIntraBlock) { - LI->addKill(RetVNI, EndIndex); - } + LI->addRange(LiveRange(StartIndex, EndIndex, RetVNI)); } // Memoize results so we don't have to recompute them. @@ -697,9 +591,11 @@ PreAllocSplitting::PerformPHIConstructionFallBack(MachineBasicBlock::iterator Us // 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(~0U, /*FIXME*/ 0, - LIs->getVNInfoAllocator()); + SlotIndex StartIndex = LIs->getMBBStartIdx(MBB); + VNInfo *RetVNI = Phis[MBB] = + LI->getNextValue(SlotIndex(), /*FIXME*/ 0, + LIs->getVNInfoAllocator()); + if (!IsIntraBlock) LiveOut[MBB] = RetVNI; // If there are no uses or defs between our starting point and the @@ -715,7 +611,7 @@ PreAllocSplitting::PerformPHIConstructionFallBack(MachineBasicBlock::iterator Us IncomingVNs[*PI] = Incoming; } - if (MBB->pred_size() == 1 && !RetVNI->hasPHIKill) { + if (MBB->pred_size() == 1 && !RetVNI->hasPHIKill()) { VNInfo* OldVN = RetVNI; VNInfo* NewVN = IncomingVNs.begin()->second; VNInfo* MergedVN = LI->MergeValueNumberInto(OldVN, NewVN); @@ -739,22 +635,16 @@ PreAllocSplitting::PerformPHIConstructionFallBack(MachineBasicBlock::iterator Us // 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); - if (!LiveInterval::isKill(I->second, KillIndex)) - LI->addKill(I->second, KillIndex); + I->second->setHasPHIKill(true); } } - unsigned EndIndex = 0; + SlotIndex EndIndex; if (IsIntraBlock) { - EndIndex = LIs->getInstructionIndex(UseI); - EndIndex = LiveIntervals::getUseIndex(EndIndex); + EndIndex = LIs->getInstructionIndex(UseI).getDefIndex(); } else EndIndex = LIs->getMBBEndIdx(MBB); - LI->addRange(LiveRange(StartIndex, EndIndex+1, RetVNI)); - if (IsIntraBlock) - LI->addKill(RetVNI, EndIndex); + LI->addRange(LiveRange(StartIndex, EndIndex, RetVNI)); // Memoize results so we don't have to recompute them. if (!IsIntraBlock) @@ -770,7 +660,7 @@ PreAllocSplitting::PerformPHIConstructionFallBack(MachineBasicBlock::iterator Us /// ReconstructLiveInterval - Recompute a live interval from scratch. void PreAllocSplitting::ReconstructLiveInterval(LiveInterval* LI) { - BumpPtrAllocator& Alloc = LIs->getVNInfoAllocator(); + VNInfo::Allocator& Alloc = LIs->getVNInfoAllocator(); // Clear the old ranges and valnos; LI->clear(); @@ -788,17 +678,16 @@ 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); + SlotIndex DefIdx = LIs->getInstructionIndex(&*DI); + DefIdx = DefIdx.getDefIndex(); + assert(!DI->isPHI() && "PHI instr in code during pre-alloc splitting."); VNInfo* NewVN = LI->getNextValue(DefIdx, 0, 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; - + if (DI->isCopyLike() && DI->getOperand(0).getReg() == LI->reg) + NewVN->setCopy(&*DI); + NewVNs[&*DI] = NewVN; } @@ -822,14 +711,13 @@ 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); + SlotIndex DefIdx = LIs->getInstructionIndex(&*DI); + DefIdx = DefIdx.getDefIndex(); if (LI->liveAt(DefIdx)) continue; VNInfo* DeadVN = NewVNs[&*DI]; - LI->addRange(LiveRange(DefIdx, DefIdx+1, DeadVN)); - LI->addKill(DeadVN, DefIdx); + LI->addRange(LiveRange(DefIdx, DefIdx.getNextSlot(), DeadVN)); } } @@ -854,22 +742,19 @@ 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(), - KE = OldVN->kills.end(); KI != KE; ++KI) { - MachineInstr* MI = LIs->getInstructionFromIndex(*KI); - unsigned DefIdx = MI->findRegisterDefOperandIdx(CurrLI->reg); - if (DefIdx == ~0U) continue; - if (MI->isRegReDefinedByTwoAddr(DefIdx)) { - VNInfo* NextVN = - CurrLI->findDefinedVNInfo(LiveIntervals::getDefIndex(*KI)); - if (NextVN == OldVN) continue; + for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(CurrLI->reg), + DE = MRI->def_end(); DI != DE; ++DI) { + if (!DI->isRegTiedToUseOperand(DI.getOperandNo())) continue; + SlotIndex DefIdx = LIs->getInstructionIndex(&*DI).getDefIndex(); + VNInfo* NextVN = CurrLI->findDefinedVNInfoForRegInt(DefIdx); + if (std::find(VNsToCopy.begin(), VNsToCopy.end(), NextVN) != + VNsToCopy.end()) Stack.push_back(NextVN); - } } } @@ -884,9 +769,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 @@ -900,10 +783,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); + SlotIndex InstrIdx = LIs->getInstructionIndex(&*I); - if ((MO.isUse() && NewLI.liveAt(LiveIntervals::getUseIndex(InstrIdx))) || - (MO.isDef() && NewLI.liveAt(LiveIntervals::getDefIndex(InstrIdx)))) + if ((MO.isUse() && NewLI.liveAt(InstrIdx.getUseIndex())) || + (MO.isDef() && NewLI.liveAt(InstrIdx.getDefIndex()))) OpsToChange.push_back(std::make_pair(&*I, I.getOperandNo())); } @@ -915,37 +798,37 @@ 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++; + ++NumRenumbers; } -bool PreAllocSplitting::Rematerialize(unsigned vreg, VNInfo* ValNo, +bool PreAllocSplitting::Rematerialize(unsigned VReg, VNInfo* ValNo, MachineInstr* DefMI, MachineBasicBlock::iterator RestorePt, - unsigned RestoreIdx, SmallPtrSet& RefsInMBB) { MachineBasicBlock& MBB = *RestorePt->getParent(); MachineBasicBlock::iterator KillPt = BarrierMBB->end(); - unsigned KillIdx = 0; - if (ValNo->def == ~0U || DefMI->getParent() == BarrierMBB) - KillPt = findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, KillIdx); + if (!DefMI || DefMI->getParent() == BarrierMBB) + KillPt = findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB); else - KillPt = findNextEmptySlot(DefMI->getParent(), DefMI, KillIdx); + KillPt = llvm::next(MachineBasicBlock::iterator(DefMI)); if (KillPt == DefMI->getParent()->end()) return false; - TII->reMaterialize(MBB, RestorePt, vreg, DefMI); - LIs->InsertMachineInstrInMaps(prior(RestorePt), RestoreIdx); + TII->reMaterialize(MBB, RestorePt, VReg, 0, DefMI, *TRI); + SlotIndex RematIdx = LIs->InsertMachineInstrInMaps(prior(RestorePt)); ReconstructLiveInterval(CurrLI); - unsigned RematIdx = LIs->getInstructionIndex(prior(RestorePt)); - RematIdx = LiveIntervals::getDefIndex(RematIdx); - RenumberValno(CurrLI->findDefinedVNInfo(RematIdx)); + RematIdx = RematIdx.getDefIndex(); + RenumberValno(CurrLI->findDefinedVNInfoForRegInt(RematIdx)); ++NumSplits; ++NumRemats; @@ -959,8 +842,6 @@ MachineInstr* PreAllocSplitting::FoldSpill(unsigned vreg, MachineBasicBlock* MBB, int& SS, SmallPtrSet& RefsInMBB) { - MachineBasicBlock::iterator Pt = MBB->begin(); - // Go top down if RefsInMBB is empty. if (RefsInMBB.empty()) return 0; @@ -970,7 +851,7 @@ MachineInstr* PreAllocSplitting::FoldSpill(unsigned vreg, !RefsInMBB.count(FoldPt)) --FoldPt; - int OpIdx = FoldPt->findRegisterDefOperandIdx(vreg, false); + int OpIdx = FoldPt->findRegisterDefOperandIdx(vreg); if (OpIdx == -1) return 0; @@ -984,24 +865,23 @@ MachineInstr* PreAllocSplitting::FoldSpill(unsigned vreg, if (I != IntervalSSMap.end()) { SS = I->second; } else { - SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment()); - + SS = MFI->CreateSpillStackObject(RC->getSize(), RC->getAlignment()); } - MachineInstr* FMI = TII->foldMemoryOperand(*MBB->getParent(), - FoldPt, Ops, SS); + MachineInstr* FMI = TII->foldMemoryOperand(FoldPt, Ops, SS); if (FMI) { LIs->ReplaceMachineInstrInMaps(FoldPt, FMI); - FMI = MBB->insert(MBB->erase(FoldPt), FMI); + FoldPt->eraseFromParent(); ++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(SlotIndex(), 0, + LSs->getVNInfoAllocator()); } return FMI; @@ -1013,15 +893,32 @@ MachineInstr* PreAllocSplitting::FoldRestore(unsigned vreg, 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; - while (FoldPt != MBB->getFirstTerminator() && !RefsInMBB.count(FoldPt)) { - ++FoldPt; + + // 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()) { @@ -1031,8 +928,11 @@ MachineInstr* PreAllocSplitting::FoldRestore(unsigned vreg, ++FoldPt; } - ++FoldPt; - } + if (FoldPt == MBB->getFirstTerminator()) + return 0; + } + + ++FoldPt; } if (FoldPt == MBB->getFirstTerminator()) @@ -1048,13 +948,12 @@ MachineInstr* PreAllocSplitting::FoldRestore(unsigned vreg, if (!TII->canFoldMemoryOperand(FoldPt, Ops)) return 0; - MachineInstr* FMI = TII->foldMemoryOperand(*MBB->getParent(), - FoldPt, Ops, SS); + MachineInstr* FMI = TII->foldMemoryOperand(FoldPt, Ops, SS); if (FMI) { LIs->ReplaceMachineInstrInMaps(FoldPt, FMI); - FMI = MBB->insert(MBB->erase(FoldPt), FMI); - ++NumFolds; + FoldPt->eraseFromParent(); + ++NumRestoreFolds; } return FMI; @@ -1064,25 +963,25 @@ MachineInstr* PreAllocSplitting::FoldRestore(unsigned vreg, /// so it would not cross the barrier that's being processed. Shrink wrap /// (minimize) the live interval to the last uses. bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { + DEBUG(dbgs() << "Pre-alloc splitting " << LI->reg << " for " << *Barrier + << " result: "); + CurrLI = LI; // Find live range where current interval cross the barrier. LiveInterval::iterator LR = - CurrLI->FindLiveRangeContaining(LIs->getUseIndex(BarrierIdx)); + CurrLI->FindLiveRangeContaining(BarrierIdx.getUseIndex()); 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) - ? LIs->getInstructionFromIndex(ValNo->def) : NULL; + MachineInstr *DefMI = LIs->getInstructionFromIndex(ValNo->def); // If this would create a new join point, do not split. - if (DefMI && createsNewJoin(LR, DefMI->getParent(), Barrier->getParent())) + if (DefMI && createsNewJoin(LR, DefMI->getParent(), Barrier->getParent())) { + DEBUG(dbgs() << "FAILED (would create a new join point).\n"); return false; + } // Find all references in the barrier mbb. SmallPtrSet RefsInMBB; @@ -1094,49 +993,56 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { } // Find a point to restore the value after the barrier. - unsigned RestoreIndex = 0; MachineBasicBlock::iterator RestorePt = - findRestorePoint(BarrierMBB, Barrier, LR->end, RefsInMBB, RestoreIndex); - if (RestorePt == BarrierMBB->end()) + findRestorePoint(BarrierMBB, Barrier, LR->end, RefsInMBB); + if (RestorePt == BarrierMBB->end()) { + DEBUG(dbgs() << "FAILED (could not find a suitable restore point).\n"); return false; + } if (DefMI && LIs->isReMaterializable(*LI, ValNo, DefMI)) - if (Rematerialize(LI->reg, ValNo, DefMI, RestorePt, - RestoreIndex, RefsInMBB)) - return true; + if (Rematerialize(LI->reg, ValNo, DefMI, RestorePt, RefsInMBB)) { + DEBUG(dbgs() << "success (remat).\n"); + return true; + } // 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; + SlotIndex 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 (!DefMI) { + // 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); } else { MachineBasicBlock::iterator SpillPt = - findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, SpillIndex); - if (SpillPt == BarrierMBB->begin()) + findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB); + if (SpillPt == BarrierMBB->begin()) { + DEBUG(dbgs() << "FAILED (could not find a suitable spill point).\n"); return false; // No gap to insert spill. + } // Add spill. SS = CreateSpillStackSlot(CurrLI->reg, RC); - TII->storeRegToStackSlot(*BarrierMBB, SpillPt, CurrLI->reg, true, SS, RC); + TII->storeRegToStackSlot(*BarrierMBB, SpillPt, CurrLI->reg, true, SS, RC, + TRI); SpillMI = prior(SpillPt); - LIs->InsertMachineInstrInMaps(SpillMI, SpillIndex); + SpillIndex = LIs->InsertMachineInstrInMaps(SpillMI); } } else if (!IsAvailableInStack(DefMBB, CurrLI->reg, ValNo->def, - RestoreIndex, SpillIndex, SS)) { + LIs->getZeroIndex(), SpillIndex, SS)) { // If it's already split, just restore the value. There is no need to spill // the def again. - if (!DefMI) + if (!DefMI) { + DEBUG(dbgs() << "FAILED (def is dead).\n"); 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. @@ -1144,21 +1050,24 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { if (DefMBB == BarrierMBB) { // Add spill after the def and the last use before the barrier. SpillPt = findSpillPoint(BarrierMBB, Barrier, DefMI, - RefsInMBB, SpillIndex); - if (SpillPt == DefMBB->begin()) + RefsInMBB); + if (SpillPt == DefMBB->begin()) { + DEBUG(dbgs() << "FAILED (could not find a suitable spill point).\n"); return false; // No gap to insert spill. + } } else { - SpillPt = findNextEmptySlot(DefMBB, DefMI, SpillIndex); - if (SpillPt == DefMBB->end()) + SpillPt = llvm::next(MachineBasicBlock::iterator(DefMI)); + if (SpillPt == DefMBB->end()) { + DEBUG(dbgs() << "FAILED (could not find a suitable spill point).\n"); 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, + TRI); SpillMI = prior(SpillPt); - LIs->InsertMachineInstrInMaps(SpillMI, SpillIndex); + SpillIndex = LIs->InsertMachineInstrInMaps(SpillMI); } } @@ -1168,29 +1077,32 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { // Add restore. bool FoldedRestore = false; + SlotIndex RestoreIndex; 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); + TII->loadRegFromStackSlot(*BarrierMBB, RestorePt, CurrLI->reg, SS, RC, TRI); MachineInstr *LoadMI = prior(RestorePt); - LIs->InsertMachineInstrInMaps(LoadMI, RestoreIndex); + RestoreIndex = LIs->InsertMachineInstrInMaps(LoadMI); } // Update spill stack slot live interval. - UpdateSpillSlotInterval(ValNo, LIs->getUseIndex(SpillIndex)+1, - LIs->getDefIndex(RestoreIndex)); + UpdateSpillSlotInterval(ValNo, SpillIndex.getUseIndex().getNextSlot(), + RestoreIndex.getDefIndex()); ReconstructLiveInterval(CurrLI); - + if (!FoldedRestore) { - unsigned RestoreIdx = LIs->getInstructionIndex(prior(RestorePt)); - RestoreIdx = LiveIntervals::getDefIndex(RestoreIdx); - RenumberValno(CurrLI->findDefinedVNInfo(RestoreIdx)); + SlotIndex RestoreIdx = LIs->getInstructionIndex(prior(RestorePt)); + RestoreIdx = RestoreIdx.getDefIndex(); + RenumberValno(CurrLI->findDefinedVNInfoForRegInt(RestoreIdx)); } ++NumSplits; + DEBUG(dbgs() << "success.\n"); return true; } @@ -1208,7 +1120,7 @@ PreAllocSplitting::SplitRegLiveIntervals(const TargetRegisterClass **RCs, // codegen is not modelling. Ignore these barriers for now. if (!TII->isSafeToMoveRegClassDefs(*RC)) continue; - std::vector &VRs = MRI->getRegClassVirtRegs(*RC); + const std::vector &VRs = MRI->getRegClassVirtRegs(*RC); for (unsigned i = 0, e = VRs.size(); i != e; ++i) { unsigned Reg = VRs[i]; if (!LIs->hasInterval(Reg)) @@ -1226,8 +1138,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); @@ -1248,10 +1158,10 @@ unsigned PreAllocSplitting::getNumberOfNonSpills( int StoreFrameIndex; unsigned StoreVReg = TII->isStoreToStackSlot(*UI, StoreFrameIndex); if (StoreVReg != Reg || StoreFrameIndex != FrameIndex) - NonSpills++; + ++NonSpills; int DefIdx = (*UI)->findRegisterDefOperandIdx(Reg); - if (DefIdx != -1 && (*UI)->isRegReDefinedByTwoAddr(DefIdx)) + if (DefIdx != -1 && (*UI)->isRegTiedToUseOperand(DefIdx)) FeedsTwoAddr = true; } @@ -1273,8 +1183,8 @@ bool PreAllocSplitting::removeDeadSpills(SmallPtrSet& split) { // 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); + SlotIndex index = LIs->getInstructionIndex(&*UI); + index = index.getUseIndex(); const LiveRange* LR = (*LI)->getLiveRangeContaining(index); VNUseCount[LR->valno].insert(&*UI); @@ -1292,17 +1202,16 @@ bool PreAllocSplitting::removeDeadSpills(SmallPtrSet& split) { // 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; + if (CurrVN->hasPHIKill()) continue; // We also don't try to handle the results of PHI joins, since there's // no defining instruction to analyze. - unsigned DefIdx = CurrVN->def; - if (DefIdx == ~0U || DefIdx == ~1U) continue; + MachineInstr* DefMI = LIs->getInstructionFromIndex(CurrVN->def); + if (!DefMI || 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(DefIdx); int FrameIndex; if (!TII->isLoadFromStackSlot(DefMI, FrameIndex)) continue; @@ -1312,7 +1221,7 @@ bool PreAllocSplitting::removeDeadSpills(SmallPtrSet& split) { (*LI)->removeValNo(CurrVN); DefMI->eraseFromParent(); VNUseCount.erase(CurrVN); - NumDeadSpills++; + ++NumDeadSpills; changed = true; continue; } @@ -1348,9 +1257,7 @@ bool PreAllocSplitting::removeDeadSpills(SmallPtrSet& split) { Ops.push_back(OpIdx); if (!TII->canFoldMemoryOperand(use, Ops)) continue; - MachineInstr* NewMI = - TII->foldMemoryOperand(*use->getParent()->getParent(), - use, Ops, FrameIndex); + MachineInstr* NewMI = TII->foldMemoryOperand(use, Ops, FrameIndex); if (!NewMI) continue; @@ -1360,10 +1267,9 @@ bool PreAllocSplitting::removeDeadSpills(SmallPtrSet& split) { (*LI)->removeValNo(CurrVN); DefMI->eraseFromParent(); - MachineBasicBlock* MBB = use->getParent(); - NewMI = MBB->insert(MBB->erase(use), NewMI); + use->eraseFromParent(); 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 = @@ -1385,7 +1291,7 @@ bool PreAllocSplitting::removeDeadSpills(SmallPtrSet& split) { if (VI->second.erase(use)) VI->second.insert(NewMI); - NumDeadSpills++; + ++NumDeadSpills; changed = true; continue; } @@ -1397,7 +1303,7 @@ bool PreAllocSplitting::removeDeadSpills(SmallPtrSet& split) { // Otherwise, this is a load-store case, so DCE them. for (SmallPtrSet::iterator UI = VNUseCount[CurrVN].begin(), UE = VNUseCount[CurrVN].end(); - UI != UI; ++UI) { + UI != UE; ++UI) { LIs->RemoveMachineInstrFromMaps(*UI); (*UI)->eraseFromParent(); } @@ -1407,7 +1313,7 @@ bool PreAllocSplitting::removeDeadSpills(SmallPtrSet& split) { LIs->RemoveMachineInstrFromMaps(DefMI); (*LI)->removeValNo(CurrVN); DefMI->eraseFromParent(); - NumDeadSpills++; + ++NumDeadSpills; changed = true; } } @@ -1421,10 +1327,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); + SlotIndex MBBEnd = LIs->getMBBEndIdx(BarrierMBB); if (LR->end < MBBEnd) return false; @@ -1487,8 +1393,10 @@ bool PreAllocSplitting::runOnMachineFunction(MachineFunction &MF) { TII = TM->getInstrInfo(); MFI = MF.getFrameInfo(); MRI = &MF.getRegInfo(); + SIs = &getAnalysis(); LIs = &getAnalysis(); LSs = &getAnalysis(); + VRM = &getAnalysis(); bool MadeChange = false;