X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=e657c46c721eb69b180a8931b05ebc50714889a8;hb=226dd2ba992b1f00491c10c59ca1889825bf92b6;hp=27e562023831eb23deb961fcac4e06a18b79d13f;hpb=518bb53485df640d7b7e3f6b0544099020c42aa7;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 27e56202383..e657c46c721 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -141,7 +141,7 @@ void LiveIntervals::printInstrs(raw_ostream &OS) const { for (MachineBasicBlock::iterator mii = mbbi->begin(), mie = mbbi->end(); mii != mie; ++mii) { if (mii->isDebugValue()) - OS << SlotIndex::getEmptyKey() << '\t' << *mii; + OS << " \t" << *mii; else OS << getInstructionIndex(mii) << '\t' << *mii; } @@ -218,9 +218,9 @@ bool LiveIntervals::conflictsWithPhysReg(const LiveInterval &li, return false; } -/// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except -/// it can check use as well. -bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, +/// conflictsWithSubPhysRegRef - Similar to conflictsWithPhysRegRef except +/// it checks for sub-register reference and it can check use as well. +bool LiveIntervals::conflictsWithSubPhysRegRef(LiveInterval &li, unsigned Reg, bool CheckUse, SmallPtrSet &JoinedCopies) { for (LiveInterval::Ranges::const_iterator @@ -329,24 +329,43 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, DEBUG(dbgs() << " +" << NewLR); interval.addRange(NewLR); - // Iterate over all of the blocks that the variable is completely - // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the - // live interval. - for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), - E = vi.AliveBlocks.end(); I != E; ++I) { - MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); - LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); - interval.addRange(LR); - DEBUG(dbgs() << " +" << LR); + bool PHIJoin = lv_->isPHIJoin(interval.reg); + + if (PHIJoin) { + // A phi join register is killed at the end of the MBB and revived as a new + // valno in the killing blocks. + assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); + DEBUG(dbgs() << " phi-join"); + ValNo->addKill(indexes_->getTerminatorGap(mbb)); + ValNo->setHasPHIKill(true); + } else { + // Iterate over all of the blocks that the variable is completely + // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the + // live interval. + for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), + E = vi.AliveBlocks.end(); I != E; ++I) { + MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); + LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); + interval.addRange(LR); + DEBUG(dbgs() << " +" << LR); + } } // Finally, this virtual register is live from the start of any killing // block to the 'use' slot of the killing instruction. for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { MachineInstr *Kill = vi.Kills[i]; - SlotIndex killIdx = - getInstructionIndex(Kill).getDefIndex(); - LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo); + SlotIndex Start = getMBBStartIdx(Kill->getParent()); + SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex(); + + // Create interval with one of a NEW value number. Note that this value + // number isn't actually defined by an instruction, weird huh? :) + if (PHIJoin) { + ValNo = interval.getNextValue(SlotIndex(Start, true), 0, false, + VNInfoAllocator); + ValNo->setIsPHIDef(true); + } + LiveRange LR(Start, killIdx, ValNo); interval.addRange(LR); ValNo->addKill(killIdx); DEBUG(dbgs() << " +" << LR); @@ -409,48 +428,11 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, interval.print(dbgs(), tri_); }); } else { - // Otherwise, this must be because of phi elimination. If this is the - // first redefinition of the vreg that we have seen, go back and change - // the live range in the PHI block to be a different value number. - if (interval.containsOneValue()) { - - VNInfo *VNI = interval.getValNumInfo(0); - // Phi elimination may have reused the register for multiple identical - // phi nodes. There will be a kill per phi. Remove the old ranges that - // we now know have an incorrect number. - for (unsigned ki=0, ke=vi.Kills.size(); ki != ke; ++ki) { - MachineInstr *Killer = vi.Kills[ki]; - SlotIndex Start = getMBBStartIdx(Killer->getParent()); - SlotIndex End = getInstructionIndex(Killer).getDefIndex(); - DEBUG({ - dbgs() << "\n\t\trenaming [" << Start << "," << End << "] in: "; - interval.print(dbgs(), tri_); - }); - interval.removeRange(Start, End); - - // Replace the interval with one of a NEW value number. Note that - // this value number isn't actually defined by an instruction, weird - // huh? :) - LiveRange LR(Start, End, - interval.getNextValue(SlotIndex(Start, true), - 0, false, VNInfoAllocator)); - LR.valno->setIsPHIDef(true); - interval.addRange(LR); - LR.valno->addKill(End); - } - - MachineBasicBlock *killMBB = getMBBFromIndex(VNI->def); - VNI->addKill(indexes_->getTerminatorGap(killMBB)); - VNI->setHasPHIKill(true); - DEBUG({ - dbgs() << " RESULT: "; - interval.print(dbgs(), tri_); - }); - } - + assert(lv_->isPHIJoin(interval.reg) && "Multiply defined register"); // In the case of PHI elimination, each variable definition is only // live until the end of the block. We've already taken care of the // rest of the live range. + SlotIndex defIndex = MIIdx.getDefIndex(); if (MO.isEarlyClobber()) defIndex = MIIdx.getUseIndex(); @@ -468,7 +450,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, interval.addRange(LR); ValNo->addKill(indexes_->getTerminatorGap(mbb)); ValNo->setHasPHIKill(true); - DEBUG(dbgs() << " +" << LR); + DEBUG(dbgs() << " phi-join +" << LR); } } @@ -512,6 +494,8 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, baseIndex = baseIndex.getNextIndex(); while (++mi != MBB->end()) { + if (mi->isDebugValue()) + continue; if (getInstructionFromIndex(baseIndex) == 0) baseIndex = indexes_->getNextNonNullIndex(baseIndex); @@ -527,8 +511,8 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, end = baseIndex.getDefIndex(); } else { // Another instruction redefines the register before it is ever read. - // Then the register is essentially dead at the instruction that defines - // it. Hence its interval is: + // Then the register is essentially dead at the instruction that + // defines it. Hence its interval is: // [defSlot(def), defSlot(def)+1) DEBUG(dbgs() << " dead"); end = start.getStoreIndex(); @@ -599,6 +583,16 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, // Look for kills, if it reaches a def before it's killed, then it shouldn't // be considered a livein. MachineBasicBlock::iterator mi = MBB->begin(); + MachineBasicBlock::iterator E = MBB->end(); + // Skip over DBG_VALUE at the start of the MBB. + if (mi != E && mi->isDebugValue()) { + while (++mi != E && mi->isDebugValue()) + ; + if (mi == E) + // MBB is empty except for DBG_VALUE's. + return; + } + SlotIndex baseIndex = MIIdx; SlotIndex start = baseIndex; if (getInstructionFromIndex(baseIndex) == 0) @@ -606,8 +600,8 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, SlotIndex end = baseIndex; bool SeenDefUse = false; - - while (mi != MBB->end()) { + + while (mi != E) { if (mi->killsRegister(interval.reg, tri_)) { DEBUG(dbgs() << " killed"); end = baseIndex.getDefIndex(); @@ -624,10 +618,11 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, break; } - ++mi; - if (mi != MBB->end()) { + while (++mi != E && mi->isDebugValue()) + // Skip over DBG_VALUE. + ; + if (mi != E) baseIndex = indexes_->getNextNonNullIndex(baseIndex); - } } // Live-in register might not be used at all. @@ -824,8 +819,9 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, unsigned ImpUse = getReMatImplicitUse(li, MI); if (ImpUse) { const LiveInterval &ImpLi = getInterval(ImpUse); - for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), - re = mri_->use_end(); ri != re; ++ri) { + for (MachineRegisterInfo::use_nodbg_iterator + ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); + ri != re; ++ri) { MachineInstr *UseMI = &*ri; SlotIndex UseIdx = getInstructionIndex(UseMI); if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) @@ -1056,8 +1052,8 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, // If this is the rematerializable definition MI itself and // all of its uses are rematerialized, simply delete it. if (MI == ReMatOrigDefMI && CanDelete) { - DEBUG(dbgs() << "\t\t\t\tErasing re-materlizable def: " - << MI << '\n'); + DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: " + << *MI << '\n'); RemoveMachineInstrFromMaps(MI); vrm.RemoveMachineInstrFromMaps(MI); MI->eraseFromParent(); @@ -1299,6 +1295,12 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, MachineInstr *MI = &*ri; MachineOperand &O = ri.getOperand(); ++ri; + if (MI->isDebugValue()) { + // Remove debug info for now. + O.setReg(0U); + DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); + continue; + } assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); SlotIndex index = getInstructionIndex(MI); if (index < start || index >= end) @@ -1342,11 +1344,9 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, MachineBasicBlock *MBB = MI->getParent(); if (ImpUse && MI != ReMatDefMI) { - // Re-matting an instruction with virtual register use. Update the - // register interval's spill weight to HUGE_VALF to prevent it from - // being spilled. - LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight = HUGE_VALF; + // Re-matting an instruction with virtual register use. Prevent interval + // from being spilled. + getInterval(ImpUse).markNotSpillable(); } unsigned MBBId = MBB->getNumber(); @@ -1398,7 +1398,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, LiveInterval &nI = getOrCreateInterval(NewVReg); if (!TrySplit) { // The spill weight is now infinity as it cannot be spilled again. - nI.weight = HUGE_VALF; + nI.markNotSpillable(); continue; } @@ -1521,6 +1521,12 @@ LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, MachineOperand &O = ri.getOperand(); MachineInstr *MI = &*ri; ++ri; + if (MI->isDebugValue()) { + // Remove debug info for now. + O.setReg(0U); + DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); + continue; + } if (O.isDef()) { assert(MI->isImplicitDef() && "Register def was not rewritten?"); @@ -1546,6 +1552,28 @@ LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, } } +float +LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { + // Limit the loop depth ridiculousness. + if (loopDepth > 200) + loopDepth = 200; + + // The loop depth is used to roughly estimate the number of times the + // instruction is executed. Something like 10^d is simple, but will quickly + // overflow a float. This expression behaves like 10^d for small d, but is + // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of + // headroom before overflow. + float lc = powf(1 + (100.0f / (loopDepth+10)), (float)loopDepth); + + return (isDef + isUse) * lc; +} + +void +LiveIntervals::normalizeSpillWeights(std::vector &NewLIs) { + for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) + normalizeSpillWeight(*NewLIs[i]); +} + std::vector LiveIntervals:: addIntervalsForSpillsFast(const LiveInterval &li, const MachineLoopInfo *loopInfo, @@ -1554,8 +1582,7 @@ addIntervalsForSpillsFast(const LiveInterval &li, std::vector added; - assert(li.weight != HUGE_VALF && - "attempt to spill already spilled interval!"); + assert(li.isSpillable() && "attempt to spill already spilled interval!"); DEBUG({ dbgs() << "\t\t\t\tadding intervals for spills for interval: "; @@ -1591,10 +1618,7 @@ addIntervalsForSpillsFast(const LiveInterval &li, // create a new register for this spill LiveInterval &nI = getOrCreateInterval(NewVReg); - - // the spill weight is now infinity as it - // cannot be spilled again - nI.weight = HUGE_VALF; + nI.markNotSpillable(); // Rewrite register operands to use the new vreg. for (SmallVectorImpl::iterator I = Indices.begin(), @@ -1648,8 +1672,7 @@ addIntervalsForSpills(const LiveInterval &li, if (EnableFastSpilling) return addIntervalsForSpillsFast(li, loopInfo, vrm); - assert(li.weight != HUGE_VALF && - "attempt to spill already spilled interval!"); + assert(li.isSpillable() && "attempt to spill already spilled interval!"); DEBUG({ dbgs() << "\t\t\t\tadding intervals for spills for interval: "; @@ -1723,6 +1746,7 @@ addIntervalsForSpills(const LiveInterval &li, } handleSpilledImpDefs(li, vrm, rc, NewLIs); + normalizeSpillWeights(NewLIs); return NewLIs; } @@ -1798,6 +1822,7 @@ addIntervalsForSpills(const LiveInterval &li, // Insert spills / restores if we are splitting. if (!TrySplit) { handleSpilledImpDefs(li, vrm, rc, NewLIs); + normalizeSpillWeights(NewLIs); return NewLIs; } @@ -1914,11 +1939,10 @@ addIntervalsForSpills(const LiveInterval &li, unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); if (ImpUse) { // Re-matting an instruction with virtual register use. Add the - // register as an implicit use on the use MI and update the register - // interval's spill weight to HUGE_VALF to prevent it from being - // spilled. + // register as an implicit use on the use MI and mark the register + // interval as unspillable. LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight = HUGE_VALF; + ImpLi.markNotSpillable(); MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); } } @@ -1957,6 +1981,7 @@ addIntervalsForSpills(const LiveInterval &li, } handleSpilledImpDefs(li, vrm, rc, RetNewLIs); + normalizeSpillWeights(RetNewLIs); return RetNewLIs; } @@ -1994,6 +2019,8 @@ unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, E = mri_->reg_end(); I != E; ++I) { MachineOperand &O = I.getOperand(); MachineInstr *MI = O.getParent(); + if (MI->isDebugValue()) + continue; SlotIndex Index = getInstructionIndex(MI); if (pli.liveAt(Index)) ++NumConflicts; @@ -2034,7 +2061,7 @@ bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, E = mri_->reg_end(); I != E; ++I) { MachineOperand &O = I.getOperand(); MachineInstr *MI = O.getParent(); - if (SeenMIs.count(MI)) + if (MI->isDebugValue() || SeenMIs.count(MI)) continue; SeenMIs.insert(MI); SlotIndex Index = getInstructionIndex(MI);