X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=83df4d174a4cb0b0b5129fd8fa0dac2c1085a577;hb=3627e34486db088661bc7fb6c0dde6a18a543217;hp=f711c0ccaa5c25fcf076991e2b3d455bb8083f45;hpb=7eec0c243320fb2629554681547d7384ea9d0c53;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index f711c0ccaa5..83df4d174a4 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -65,6 +65,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { } void LiveIntervals::releaseMemory() { + MBB2IdxMap.clear(); Idx2MBBMap.clear(); mi2iMap_.clear(); i2miMap_.clear(); @@ -99,11 +100,14 @@ void LiveIntervals::computeNumbering() { i2miMap_.push_back(I); MIIndex += InstrSlots::NUM; } - + + if (StartIdx == MIIndex) { + // Empty MBB + MIIndex += InstrSlots::NUM; + i2miMap_.push_back(0); + } // Set the MBB2IdxMap entry for this MBB. - MBB2IdxMap[MBB->getNumber()] = (StartIdx == MIIndex) - ? std::make_pair(StartIdx, StartIdx) // Empty MBB - : std::make_pair(StartIdx, MIIndex - 1); + MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); } std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); @@ -128,13 +132,11 @@ void LiveIntervals::computeNumbering() { i++; } while (!newInstr); - MachineInstr* preceding = i2miMap_[(mi2iMap_[newInstr] - - InstrSlots::NUM) / InstrSlots::NUM]; - if (preceding->getParent() == newInstr->getParent() && - preceding->modifiesRegister(I->second.reg)) - LI->start = mi2iMap_[newInstr] - InstrSlots::NUM + offset; - else + if (mi2iMap_[newInstr] == + MBB2IdxMap[newInstr->getParent()->getNumber()].first) LI->start = mi2iMap_[newInstr]; + else + LI->start = mi2iMap_[newInstr] - InstrSlots::NUM + offset; } // Remap the ending index in the same way that we remapped the start, @@ -172,13 +174,11 @@ void LiveIntervals::computeNumbering() { i++; } while (!newInstr); - MachineInstr* preceding = i2miMap_[(mi2iMap_[newInstr] - - InstrSlots::NUM) / InstrSlots::NUM]; - if (preceding->getParent() == newInstr->getParent() && - preceding->modifiesRegister(I->second.reg)) - vni->def = mi2iMap_[newInstr] - InstrSlots::NUM + offset; - else + if (mi2iMap_[newInstr] == + MBB2IdxMap[newInstr->getParent()->getNumber()].first) vni->def = mi2iMap_[newInstr]; + else + vni->def = mi2iMap_[newInstr] - InstrSlots::NUM + offset; } // Remap the VNInfo kill indices, which works the same as @@ -233,8 +233,8 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { void LiveIntervals::print(std::ostream &O, const Module* ) const { O << "********** INTERVALS **********\n"; for (const_iterator I = begin(), E = end(); I != E; ++I) { - I->second.print(DOUT, tri_); - DOUT << "\n"; + I->second.print(O, tri_); + O << "\n"; } O << "********** MACHINEINSTRS **********\n"; @@ -365,14 +365,11 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // live interval. for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { if (vi.AliveBlocks[i]) { - MachineBasicBlock *MBB = mf_->getBlockNumbered(i); - if (!MBB->empty()) { - LiveRange LR(getMBBStartIdx(i), - getInstructionIndex(&MBB->back()) + InstrSlots::NUM, - ValNo); - interval.addRange(LR); - DOUT << " +" << LR; - } + LiveRange LR(getMBBStartIdx(i), + getMBBEndIdx(i)+1, // MBB ends at -1. + ValNo); + interval.addRange(LR); + DOUT << " +" << LR; } } @@ -664,6 +661,8 @@ void LiveIntervals::computeIntervals() { MIIndex += InstrSlots::NUM; } + + if (MBB->begin() == miEnd) MIIndex += InstrSlots::NUM; // Empty MBB } } @@ -975,7 +974,9 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, const MachineLoopInfo *loopInfo, unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, std::map &MBBVRegsMap, - std::vector &NewLIs) { + std::vector &NewLIs, float &SSWeight) { + MachineBasicBlock *MBB = MI->getParent(); + unsigned loopDepth = loopInfo->getLoopDepth(MBB); bool CanFold = false; RestartInstruction: for (unsigned i = 0; i != MI->getNumOperands(); ++i) { @@ -1044,7 +1045,14 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, } } - if (TryFold) { + // Update stack slot spill weight if we are splitting. + float Weight = getSpillWeight(HasDef, HasUse, loopDepth); + if (!TrySplit) + SSWeight += Weight; + + if (!TryFold) + CanFold = false; + else { // Do not fold load / store here if we are splitting. We'll find an // optimal point to insert a load / store later. if (!TrySplit) { @@ -1055,15 +1063,17 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, HasUse = false; HasDef = false; CanFold = false; - if (isRemoved(MI)) + if (isRemoved(MI)) { + SSWeight -= Weight; break; + } goto RestartInstruction; } } else { + // We'll try to fold it later if it's profitable. CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); } - } else - CanFold = false; + } // Create a new virtual register for the spill interval. bool CreatedNewVReg = false; @@ -1164,17 +1174,6 @@ bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, return false; } -static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) { - const VNInfo *VNI = NULL; - for (LiveInterval::const_vni_iterator i = li.vni_begin(), - e = li.vni_end(); i != e; ++i) - if ((*i)->def == DefIdx) { - VNI = *i; - break; - } - return VNI; -} - /// RewriteInfo - Keep track of machine instrs that will be rewritten /// during spilling. namespace { @@ -1209,7 +1208,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, BitVector &RestoreMBBs, std::map > &RestoreIdxes, std::map &MBBVRegsMap, - std::vector &NewLIs) { + std::vector &NewLIs, float &SSWeight) { bool AllCanFold = true; unsigned NewVReg = 0; unsigned start = getBaseIndex(I->start); @@ -1297,10 +1296,10 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, bool HasDef = false; bool HasUse = false; bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, - index, end, MI, ReMatOrigDefMI, ReMatDefMI, - Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, - CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, - ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); + index, end, MI, ReMatOrigDefMI, ReMatDefMI, + Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, + CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, + ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs, SSWeight); if (!HasDef && !HasUse) continue; @@ -1322,7 +1321,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); else { // If this is a two-address code, then this index starts a new VNInfo. - const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index)); + const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index)); if (VNI) HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); } @@ -1459,7 +1458,8 @@ LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, std::vector LiveIntervals:: addIntervalsForSpills(const LiveInterval &li, - const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { + const MachineLoopInfo *loopInfo, VirtRegMap &vrm, + float &SSWeight) { // Since this is called after the analysis is done we don't know if // LiveVariables is available lv_ = getAnalysisToUpdate(); @@ -1471,6 +1471,9 @@ addIntervalsForSpills(const LiveInterval &li, li.print(DOUT, tri_); DOUT << '\n'; + // Spill slot weight. + SSWeight = 0.0f; + // Each bit specify whether it a spill is required in the MBB. BitVector SpillMBBs(mf_->getNumBlockIDs()); std::map > SpillIdxes; @@ -1525,17 +1528,18 @@ addIntervalsForSpills(const LiveInterval &li, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, false, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - MBBVRegsMap, NewLIs); + MBBVRegsMap, NewLIs, SSWeight); } else { rewriteInstructionsForSpills(li, false, I, NULL, 0, Slot, 0, false, false, false, false, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - MBBVRegsMap, NewLIs); + MBBVRegsMap, NewLIs, SSWeight); } IsFirstRange = false; } + SSWeight = 0.0f; // Already accounted for when split. handleSpilledImpDefs(li, vrm, rc, NewLIs); return NewLIs; } @@ -1601,7 +1605,7 @@ addIntervalsForSpills(const LiveInterval &li, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, CanDelete, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - MBBVRegsMap, NewLIs); + MBBVRegsMap, NewLIs, SSWeight); } // Insert spills / restores if we are splitting. @@ -1615,6 +1619,8 @@ addIntervalsForSpills(const LiveInterval &li, if (NeedStackSlot) { int Id = SpillMBBs.find_first(); while (Id != -1) { + MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); + unsigned loopDepth = loopInfo->getLoopDepth(MBB); std::vector &spills = SpillIdxes[Id]; for (unsigned i = 0, e = spills.size(); i != e; ++i) { int index = spills[i].index; @@ -1671,6 +1677,10 @@ addIntervalsForSpills(const LiveInterval &li, if (isKill) AddedKill.insert(&nI); } + + // Update spill slot weight. + if (!isReMat) + SSWeight += getSpillWeight(true, false, loopDepth); } Id = SpillMBBs.find_next(Id); } @@ -1678,6 +1688,9 @@ addIntervalsForSpills(const LiveInterval &li, int Id = RestoreMBBs.find_first(); while (Id != -1) { + MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); + unsigned loopDepth = loopInfo->getLoopDepth(MBB); + std::vector &restores = RestoreIdxes[Id]; for (unsigned i = 0, e = restores.size(); i != e; ++i) { int index = restores[i].index; @@ -1685,6 +1698,7 @@ addIntervalsForSpills(const LiveInterval &li, continue; unsigned VReg = restores[i].vreg; LiveInterval &nI = getOrCreateInterval(VReg); + bool isReMat = vrm.isReMaterialized(VReg); MachineInstr *MI = getInstructionFromIndex(index); bool CanFold = false; Ops.clear(); @@ -1708,7 +1722,7 @@ addIntervalsForSpills(const LiveInterval &li, // Fold the load into the use if possible. bool Folded = false; if (CanFold && !Ops.empty()) { - if (!vrm.isReMaterialized(VReg)) + if (!isReMat) Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); else { MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); @@ -1736,6 +1750,10 @@ addIntervalsForSpills(const LiveInterval &li, nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); else vrm.addRestorePoint(VReg, MI); + + // Update spill slot weight. + if (!isReMat) + SSWeight += getSpillWeight(false, true, loopDepth); } Id = RestoreMBBs.find_next(Id); } @@ -1844,3 +1862,18 @@ void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, } } } + +LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, + MachineInstr* startInst) { + LiveInterval& Interval = getOrCreateInterval(reg); + VNInfo* VN = Interval.getNextValue( + getInstructionIndex(startInst) + InstrSlots::DEF, + startInst, getVNInfoAllocator()); + VN->hasPHIKill = true; + VN->kills.push_back(getMBBEndIdx(startInst->getParent())); + LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF, + getMBBEndIdx(startInst->getParent()) + 1, VN); + Interval.addRange(LR); + + return LR; +}