X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPreAllocSplitting.cpp;h=52a403bd363c33f179f8c2393be72bc50b7e2161;hb=7d696d80409aad20bb5da0fc4eccab941dd371d4;hp=f08bc20d954c0b52a50660f5fa1bd45aabb5a6d5;hpb=c93023a89e9f3c4937a4b23db13f974afac94e50;p=oota-llvm.git diff --git a/lib/CodeGen/PreAllocSplitting.cpp b/lib/CodeGen/PreAllocSplitting.cpp index f08bc20d954..52a403bd363 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" @@ -38,10 +40,12 @@ 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"); @@ -55,6 +59,7 @@ namespace { MachineRegisterInfo *MRI; LiveIntervals *LIs; LiveStacks *LSs; + VirtRegMap *VRM; // Barrier - Current barrier being processed. MachineInstr *Barrier; @@ -98,8 +103,10 @@ namespace { AU.addPreservedID(PHIEliminationID); AU.addRequired(); AU.addRequired(); + AU.addRequired(); AU.addPreserved(); AU.addPreserved(); + AU.addPreserved(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -226,68 +233,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; + MachineBasicBlock::iterator MII = MI; + MachineBasicBlock::iterator EndPt = DefMI + ? MachineBasicBlock::iterator(DefMI) : MBB->begin(); - if (MII == EndPt) return Pt; + while (MII != EndPt && !RefsInMBB.count(MII) && + MII->getOpcode() != TRI->getCallFrameSetupOpcode()) + --MII; + if (MII == EndPt || RefsInMBB.count(MII)) return Pt; - 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)) { + unsigned Index = LIs->getInstructionIndex(MII); - 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()) { + // 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 if (LIs->hasGapBeforeInstr(Index)) { + Pt = MII; + SpillIndex = LIs->findGapBeforeInstr(Index, true); } + + if (RefsInMBB.count(MII)) + return Pt; + + + --MII; } return Pt; @@ -305,81 +282,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; - - 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) { + 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->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 if (Gap) { + Pt = MII; + RestoreIndex = Gap; } + + if (RefsInMBB.count(MII)) + return Pt; + + ++MII; } return Pt; @@ -400,11 +340,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; } @@ -604,7 +544,7 @@ PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI, // 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); + LI->addKill(RetVNI, EndIndex, false); } else if (ContainsDefs && ContainsUses) { SmallPtrSet& BlockDefs = Defs[MBB]; SmallPtrSet& BlockUses = Uses[MBB]; @@ -666,7 +606,7 @@ PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI, if (foundUse && LI->isKill(RetVNI, StartIndex)) LI->removeKill(RetVNI, StartIndex); if (IsIntraBlock) { - LI->addKill(RetVNI, EndIndex); + LI->addKill(RetVNI, EndIndex, false); } } @@ -698,8 +638,9 @@ PreAllocSplitting::PerformPHIConstructionFallBack(MachineBasicBlock::iterator Us if (Phis.count(MBB)) return Phis[MBB]; unsigned StartIndex = LIs->getMBBStartIdx(MBB); - VNInfo *RetVNI = Phis[MBB] = LI->getNextValue(~0U, /*FIXME*/ 0, - LIs->getVNInfoAllocator()); + 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 @@ -715,7 +656,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,10 +680,10 @@ 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; + I->second->setHasPHIKill(true); unsigned KillIndex = LIs->getMBBEndIdx(I->first); if (!LiveInterval::isKill(I->second, KillIndex)) - LI->addKill(I->second, KillIndex); + LI->addKill(I->second, KillIndex, false); } } @@ -754,7 +695,7 @@ PreAllocSplitting::PerformPHIConstructionFallBack(MachineBasicBlock::iterator Us EndIndex = LIs->getMBBEndIdx(MBB); LI->addRange(LiveRange(StartIndex, EndIndex+1, RetVNI)); if (IsIntraBlock) - LI->addKill(RetVNI, EndIndex); + LI->addKill(RetVNI, EndIndex, false); // Memoize results so we don't have to recompute them. if (!IsIntraBlock) @@ -791,7 +732,9 @@ void PreAllocSplitting::ReconstructLiveInterval(LiveInterval* LI) { unsigned DefIdx = LIs->getInstructionIndex(&*DI); DefIdx = LiveIntervals::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; @@ -829,7 +772,7 @@ void PreAllocSplitting::ReconstructLiveInterval(LiveInterval* LI) { VNInfo* DeadVN = NewVNs[&*DI]; LI->addRange(LiveRange(DefIdx, DefIdx+1, DeadVN)); - LI->addKill(DeadVN, DefIdx); + LI->addKill(DeadVN, DefIdx, false); } } @@ -854,19 +797,20 @@ 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) { - MachineInstr* MI = LIs->getInstructionFromIndex(*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)); + CurrLI->findDefinedVNInfo(LiveIntervals::getDefIndex(KI->killIdx)); if (NextVN == OldVN) continue; Stack.push_back(NextVN); } @@ -884,9 +828,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 @@ -915,6 +857,9 @@ 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]; @@ -931,7 +876,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); @@ -984,8 +929,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(), @@ -997,11 +941,11 @@ 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; @@ -1013,15 +957,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 +992,11 @@ MachineInstr* PreAllocSplitting::FoldRestore(unsigned vreg, ++FoldPt; } - ++FoldPt; - } + if (FoldPt == MBB->getFirstTerminator()) + return 0; + } + + ++FoldPt; } if (FoldPt == MBB->getFirstTerminator()) @@ -1054,7 +1018,7 @@ MachineInstr* PreAllocSplitting::FoldRestore(unsigned vreg, if (FMI) { LIs->ReplaceMachineInstrInMaps(FoldPt, FMI); FMI = MBB->insert(MBB->erase(FoldPt), FMI); - ++NumFolds; + ++NumRestoreFolds; } return FMI; @@ -1071,13 +1035,12 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { CurrLI->FindLiveRangeContaining(LIs->getUseIndex(BarrierIdx)); VNInfo *ValNo = LR->valno; - if (ValNo->def == ~1U) { + if (ValNo->isUnused()) { // Defined by a dead def? How can this be? - assert(0 && "Val# is defined by a dead def?"); - abort(); + LLVM_UNREACHABLE("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. @@ -1111,8 +1074,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); @@ -1171,6 +1134,7 @@ bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { 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); @@ -1251,7 +1215,7 @@ unsigned PreAllocSplitting::getNumberOfNonSpills( NonSpills++; int DefIdx = (*UI)->findRegisterDefOperandIdx(Reg); - if (DefIdx != -1 && (*UI)->isRegReDefinedByTwoAddr(DefIdx)) + if (DefIdx != -1 && (*UI)->isRegTiedToUseOperand(DefIdx)) FeedsTwoAddr = true; } @@ -1292,17 +1256,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; + 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(DefIdx); + MachineInstr* DefMI = LIs->getInstructionFromIndex(CurrVN->def); int FrameIndex; if (!TII->isLoadFromStackSlot(DefMI, FrameIndex)) continue; @@ -1421,7 +1384,7 @@ 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); @@ -1489,6 +1452,7 @@ bool PreAllocSplitting::runOnMachineFunction(MachineFunction &MF) { MRI = &MF.getRegInfo(); LIs = &getAnalysis(); LSs = &getAnalysis(); + VRM = &getAnalysis(); bool MadeChange = false;