X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=d6c8a6561e4f85c680c201bca826a46e817b8fee;hb=f9410141f703f4e8a6aba717617ef958249f6d13;hp=02c1191f8480459db515a28224de617cffef295a;hpb=a0c032f9b2eeae3a436850eaca54de4c6a5f23b6;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 02c1191f848..d6c8a6561e4 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -30,6 +30,7 @@ #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetOptions.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/ADT/Statistic.h" @@ -49,6 +50,9 @@ static cl::opt SplitLimit("split-limit", static cl::opt EnableAggressiveRemat("aggressive-remat", cl::Hidden); +static cl::opt EnableFastSpilling("fast-spill", + cl::init(false), cl::Hidden); + STATISTIC(numIntervals, "Number of original intervals"); STATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); STATISTIC(numFolds , "Number of loads/stores folded into instructions"); @@ -64,13 +68,22 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); AU.addPreservedID(MachineLoopInfoID); AU.addPreservedID(MachineDominatorsID); - AU.addPreservedID(PHIEliminationID); - AU.addRequiredID(PHIEliminationID); + + if (!StrongPHIElim) { + AU.addPreservedID(PHIEliminationID); + AU.addRequiredID(PHIEliminationID); + } + AU.addRequiredID(TwoAddressInstructionPassID); MachineFunctionPass::getAnalysisUsage(AU); } void LiveIntervals::releaseMemory() { + // Free the live intervals themselves. + for (DenseMap::iterator I = r2iMap_.begin(), + E = r2iMap_.end(); I != E; ++I) + delete I->second; + MBB2IdxMap.clear(); Idx2MBBMap.clear(); mi2iMap_.clear(); @@ -117,9 +130,13 @@ void LiveIntervals::computeNumbering() { MIIndex += InstrSlots::NUM; FunctionSize++; - // Insert an empty slot after every instruction. - MIIndex += InstrSlots::NUM; - i2miMap_.push_back(0); + // Insert max(1, numdefs) empty slots after every instruction. + unsigned Slots = I->getDesc().getNumDefs(); + if (Slots == 0) + Slots = 1; + MIIndex += InstrSlots::NUM * Slots; + while (Slots--) + i2miMap_.push_back(0); } // Set the MBB2IdxMap entry for this MBB. @@ -129,9 +146,9 @@ void LiveIntervals::computeNumbering() { std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); if (!OldI2MI.empty()) - for (iterator OI = begin(), OE = end(); OI != OE; ++OI) - for (LiveInterval::iterator LI = OI->second.begin(), - LE = OI->second.end(); LI != LE; ++LI) { + for (iterator OI = begin(), OE = end(); OI != OE; ++OI) { + for (LiveInterval::iterator LI = OI->second->begin(), + LE = OI->second->end(); LI != LE; ++LI) { // Remap the start index of the live range to the corresponding new // number, or our best guess at what it _should_ correspond to if the @@ -156,14 +173,13 @@ void LiveIntervals::computeNumbering() { // following instruction. index = (LI->end - 1) / InstrSlots::NUM; offset = LI->end % InstrSlots::NUM; - if (offset == InstrSlots::USE) { + if (offset == InstrSlots::LOAD) { + // VReg dies at end of block. std::vector::const_iterator I = std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end); - // Take the pair containing the index - std::vector::const_iterator J = - (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; + --I; - LI->end = getMBBEndIdx(J->second) + 1; + LI->end = getMBBEndIdx(I->second) + 1; } else { unsigned idx = index; while (index < OldI2MI.size() && !OldI2MI[index]) ++index; @@ -173,41 +189,47 @@ void LiveIntervals::computeNumbering() { else LI->end = InstrSlots::NUM * i2miMap_.size(); } + } + + for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(), + VNE = OI->second->vni_end(); VNI != VNE; ++VNI) { + VNInfo* vni = *VNI; // Remap the VNInfo def index, which works the same as the - // start indices above. - VNInfo* vni = LI->valno; - index = vni->def / InstrSlots::NUM; - offset = vni->def % InstrSlots::NUM; - if (offset == InstrSlots::LOAD) { - std::vector::const_iterator I = + // start indices above. VN's with special sentinel defs + // don't need to be remapped. + if (vni->def != ~0U && vni->def != ~1U) { + unsigned index = vni->def / InstrSlots::NUM; + unsigned offset = vni->def % InstrSlots::NUM; + if (offset == InstrSlots::LOAD) { + std::vector::const_iterator I = std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def); - // Take the pair containing the index - std::vector::const_iterator J = + // Take the pair containing the index + std::vector::const_iterator J = (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; - vni->def = getMBBStartIdx(J->second); - - } else { - vni->def = mi2iMap_[OldI2MI[index]] + offset; + vni->def = getMBBStartIdx(J->second); + } else { + vni->def = mi2iMap_[OldI2MI[index]] + offset; + } } // Remap the VNInfo kill indices, which works the same as // the end indices above. for (size_t i = 0; i < vni->kills.size(); ++i) { - index = (vni->kills[i]-1) / InstrSlots::NUM; - offset = vni->kills[i] % InstrSlots::NUM; - if (offset == InstrSlots::USE) { + // PHI kills don't need to be remapped. + if (!vni->kills[i]) continue; + + unsigned index = (vni->kills[i]-1) / InstrSlots::NUM; + unsigned offset = vni->kills[i] % InstrSlots::NUM; + if (offset == InstrSlots::LOAD) { std::vector::const_iterator I = std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); - // Take the pair containing the index - std::vector::const_iterator J = - (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; + --I; - vni->kills[i] = getMBBEndIdx(J->second) + 1; + vni->kills[i] = getMBBEndIdx(I->second); } else { unsigned idx = index; - while (!OldI2MI[index]) ++index; while (index < OldI2MI.size() && !OldI2MI[index]) ++index; if (index != OldI2MI.size()) @@ -218,6 +240,7 @@ void LiveIntervals::computeNumbering() { } } } + } } /// runOnMachineFunction - Register allocate the whole function @@ -239,7 +262,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { DOUT << "********** INTERVALS **********\n"; for (iterator I = begin(), E = end(); I != E; ++I) { - I->second.print(DOUT, tri_); + I->second->print(DOUT, tri_); DOUT << "\n"; } @@ -252,7 +275,7 @@ 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(O, tri_); + I->second->print(O, tri_); O << "\n"; } @@ -288,7 +311,7 @@ bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, continue; for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& mop = MI->getOperand(i); - if (!mop.isRegister()) + if (!mop.isReg()) continue; unsigned PhysReg = mop.getReg(); if (PhysReg == 0 || PhysReg == li.reg) @@ -334,6 +357,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, if (interval.empty()) { // Get the Idx of the defining instructions. unsigned defIndex = getDefIndex(MIIdx); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + defIndex = getUseIndex(MIIdx); VNInfo *ValNo; MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; @@ -417,6 +443,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, assert(interval.containsOneValue()); unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); unsigned RedefIndex = getDefIndex(MIIdx); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + RedefIndex = getUseIndex(MIIdx); const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); VNInfo *OldValNo = OldLR->valno; @@ -484,6 +513,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // live until the end of the block. We've already taken care of the // rest of the live range. unsigned defIndex = getDefIndex(MIIdx); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + defIndex = getUseIndex(MIIdx); VNInfo *ValNo; MachineInstr *CopyMI = NULL; @@ -518,6 +550,9 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, unsigned baseIndex = MIIdx; unsigned start = getDefIndex(baseIndex); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + start = getUseIndex(MIIdx); unsigned end = start; // If it is not used after definition, it is considered dead at @@ -525,7 +560,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // [defSlot(def), defSlot(def)+1) if (MO.isDead()) { DOUT << " dead"; - end = getDefIndex(start) + 1; + end = start + 1; goto exit; } @@ -547,7 +582,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // it. Hence its interval is: // [defSlot(def), defSlot(def)+1) DOUT << " dead"; - end = getDefIndex(start) + 1; + end = start + 1; goto exit; } @@ -558,7 +593,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // instruction where we know it's dead is if it is live-in to the function // and never used. assert(!CopyMI && "physreg was not killed in defining block!"); - end = getDefIndex(start) + 1; // It's dead. + end = start + 1; exit: assert(start < end && "did not find end of interval?"); @@ -610,7 +645,11 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, MachineBasicBlock::iterator mi = MBB->begin(); unsigned baseIndex = MIIdx; unsigned start = baseIndex; - unsigned end = start; + while (baseIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(baseIndex) == 0) + baseIndex += InstrSlots::NUM; + unsigned end = baseIndex; + while (mi != MBB->end()) { if (mi->killsRegister(interval.reg, tri_)) { DOUT << " killed"; @@ -645,7 +684,7 @@ exit: } } - LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); + LiveRange LR(start, end, interval.getNextValue(~0U, 0, VNInfoAllocator)); interval.addRange(LR); interval.addKill(LR.valno, end); DOUT << " +" << LR << '\n'; @@ -655,21 +694,17 @@ exit: /// registers. for some ordering of the machine instructions [1,N] a /// live interval is an interval [i, j) where 1 <= i <= j < N for /// which a variable is live -void LiveIntervals::computeIntervals() { +void LiveIntervals::computeIntervals() { + DOUT << "********** COMPUTING LIVE INTERVALS **********\n" << "********** Function: " << ((Value*)mf_->getFunction())->getName() << '\n'; - // Track the index of the current machine instr. - unsigned MIIndex = 0; - - // Skip over empty initial indices. - while (MIIndex / InstrSlots::NUM < i2miMap_.size() && - getInstructionFromIndex(MIIndex) == 0) - MIIndex += InstrSlots::NUM; for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); MBBI != E; ++MBBI) { MachineBasicBlock *MBB = MBBI; + // Track the index of the current machine instr. + unsigned MIIndex = getMBBStartIdx(MBB); DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); @@ -685,6 +720,11 @@ void LiveIntervals::computeIntervals() { true); } + // Skip over empty initial indices. + while (MIIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(MIIndex) == 0) + MIIndex += InstrSlots::NUM; + for (; MI != miEnd; ++MI) { DOUT << MIIndex << "\t" << *MI; @@ -692,11 +732,16 @@ void LiveIntervals::computeIntervals() { for (int i = MI->getNumOperands() - 1; i >= 0; --i) { MachineOperand &MO = MI->getOperand(i); // handle register defs - build intervals - if (MO.isRegister() && MO.getReg() && MO.isDef()) + if (MO.isReg() && MO.getReg() && MO.isDef()) { handleRegisterDef(MBB, MI, MIIndex, MO, i); + } } - - MIIndex += InstrSlots::NUM; + + // Skip over the empty slots after each instruction. + unsigned Slots = MI->getDesc().getNumDefs(); + if (Slots == 0) + Slots = 1; + MIIndex += InstrSlots::NUM * Slots; // Skip over empty indices. while (MIIndex / InstrSlots::NUM < i2miMap_.size() && @@ -722,11 +767,10 @@ bool LiveIntervals::findLiveInMBBs(const LiveRange &LR, return ResVal; } - -LiveInterval LiveIntervals::createInterval(unsigned reg) { +LiveInterval* LiveIntervals::createInterval(unsigned reg) { float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; - return LiveInterval(reg, Weight); + return new LiveInterval(reg, Weight); } /// getVNInfoSourceReg - Helper function that parses the specified VNInfo @@ -758,7 +802,7 @@ unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, unsigned RegOp = 0; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (!MO.isRegister() || !MO.isUse()) + if (!MO.isReg() || !MO.isUse()) continue; unsigned Reg = MO.getReg(); if (Reg == 0 || Reg == li.reg) @@ -788,6 +832,7 @@ bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, /// val# of the specified interval is re-materializable. bool LiveIntervals::isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, MachineInstr *MI, + SmallVectorImpl &SpillIs, bool &isLoad) { if (DisableReMat) return false; @@ -824,8 +869,8 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, // If the instruction accesses memory and the memory could be non-constant, // assume the instruction is not rematerializable. - for (std::list::const_iterator I = MI->memoperands_begin(), - E = MI->memoperands_end(); I != E; ++I) { + for (std::list::const_iterator + I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I){ const MachineMemOperand &MMO = *I; if (MMO.isVolatile() || MMO.isStore()) return false; @@ -893,13 +938,21 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) return false; } + + // If a register operand of the re-materialized instruction is going to + // be spilled next, then it's not legal to re-materialize this instruction. + for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) + if (ImpUse == SpillIs[i]->reg) + return false; } return true; } /// isReMaterializable - Returns true if every definition of MI of every /// val# of the specified interval is re-materializable. -bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { +bool LiveIntervals::isReMaterializable(const LiveInterval &li, + SmallVectorImpl &SpillIs, + bool &isLoad) { isLoad = false; for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); i != e; ++i) { @@ -913,7 +966,7 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); bool DefIsLoad = false; if (!ReMatDefMI || - !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) + !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) return false; isLoad |= DefIsLoad; } @@ -1053,7 +1106,7 @@ void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, // use operand. Make sure we rewrite that as well. for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (!MO.isRegister()) + if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) @@ -1080,7 +1133,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, SmallVector &ReMatIds, const MachineLoopInfo *loopInfo, unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, - std::map &MBBVRegsMap, + DenseMap &MBBVRegsMap, std::vector &NewLIs, float &SSWeight) { MachineBasicBlock *MBB = MI->getParent(); unsigned loopDepth = loopInfo->getLoopDepth(MBB); @@ -1088,7 +1141,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, RestartInstruction: for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& mop = MI->getOperand(i); - if (!mop.isRegister()) + if (!mop.isReg()) continue; unsigned Reg = mop.getReg(); unsigned RegI = Reg; @@ -1140,7 +1193,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, Ops.push_back(i); for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { const MachineOperand &MOj = MI->getOperand(j); - if (!MOj.isRegister()) + if (!MOj.isReg()) continue; unsigned RegJ = MOj.getReg(); if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) @@ -1323,10 +1376,10 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, SmallVector &ReMatIds, const MachineLoopInfo *loopInfo, BitVector &SpillMBBs, - std::map > &SpillIdxes, + DenseMap > &SpillIdxes, BitVector &RestoreMBBs, - std::map > &RestoreIdxes, - std::map &MBBVRegsMap, + DenseMap > &RestoreIdxes, + DenseMap &MBBVRegsMap, std::vector &NewLIs, float &SSWeight) { bool AllCanFold = true; unsigned NewVReg = 0; @@ -1393,7 +1446,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, unsigned MBBId = MBB->getNumber(); unsigned ThisVReg = 0; if (TrySplit) { - std::map::const_iterator NVI = MBBVRegsMap.find(MBBId); + DenseMap::iterator NVI = MBBVRegsMap.find(MBBId); if (NVI != MBBVRegsMap.end()) { ThisVReg = NVI->second; // One common case: @@ -1455,7 +1508,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, if (VNI) HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); } - std::map >::iterator SII = + DenseMap >::iterator SII = SpillIdxes.find(MBBId); if (!HasKill) { if (SII == SpillIdxes.end()) { @@ -1488,14 +1541,14 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, } if (HasUse) { - std::map >::iterator SII = + DenseMap >::iterator SII = SpillIdxes.find(MBBId); if (SII != SpillIdxes.end() && SII->second.back().vreg == NewVReg && (int)index > SII->second.back().index) // Use(s) following the last def, it's not safe to fold the spill. SII->second.back().canFold = false; - std::map >::iterator RII = + DenseMap >::iterator RII = RestoreIdxes.find(MBBId); if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) // If we are splitting live intervals, only fold if it's the first @@ -1528,7 +1581,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, BitVector &RestoreMBBs, - std::map > &RestoreIdxes) { + DenseMap > &RestoreIdxes) { if (!RestoreMBBs[Id]) return false; std::vector &Restores = RestoreIdxes[Id]; @@ -1542,7 +1595,7 @@ bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, BitVector &RestoreMBBs, - std::map > &RestoreIdxes) { + DenseMap > &RestoreIdxes) { if (!RestoreMBBs[Id]) return; std::vector &Restores = RestoreIdxes[Id]; @@ -1585,11 +1638,125 @@ LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, } } +namespace { + struct LISorter { + bool operator()(LiveInterval* A, LiveInterval* B) { + return A->beginNumber() < B->beginNumber(); + } + }; +} + +std::vector LiveIntervals:: +addIntervalsForSpillsFast(const LiveInterval &li, + const MachineLoopInfo *loopInfo, + VirtRegMap &vrm, float& SSWeight) { + unsigned slot = vrm.assignVirt2StackSlot(li.reg); + + std::vector added; + + assert(li.weight != HUGE_VALF && + "attempt to spill already spilled interval!"); + + DOUT << "\t\t\t\tadding intervals for spills for interval: "; + DEBUG(li.dump()); + DOUT << '\n'; + + const TargetRegisterClass* rc = mri_->getRegClass(li.reg); + + SSWeight = 0.0f; + + MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); + while (RI != mri_->reg_end()) { + MachineInstr* MI = &*RI; + + SmallVector Indices; + bool HasUse = false; + bool HasDef = false; + + for (unsigned i = 0; i != MI->getNumOperands(); ++i) { + MachineOperand& mop = MI->getOperand(i); + if (!mop.isReg() || mop.getReg() != li.reg) continue; + + HasUse |= MI->getOperand(i).isUse(); + HasDef |= MI->getOperand(i).isDef(); + + Indices.push_back(i); + } + + if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), + Indices, true, slot, li.reg)) { + unsigned NewVReg = mri_->createVirtualRegister(rc); + vrm.grow(); + vrm.assignVirt2StackSlot(NewVReg, slot); + + // 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; + + // Rewrite register operands to use the new vreg. + for (SmallVectorImpl::iterator I = Indices.begin(), + E = Indices.end(); I != E; ++I) { + MI->getOperand(*I).setReg(NewVReg); + + if (MI->getOperand(*I).isUse()) + MI->getOperand(*I).setIsKill(true); + } + + // Fill in the new live interval. + unsigned index = getInstructionIndex(MI); + if (HasUse) { + LiveRange LR(getLoadIndex(index), getUseIndex(index), + nI.getNextValue(~0U, 0, getVNInfoAllocator())); + DOUT << " +" << LR; + nI.addRange(LR); + vrm.addRestorePoint(NewVReg, MI); + } + if (HasDef) { + LiveRange LR(getDefIndex(index), getStoreIndex(index), + nI.getNextValue(~0U, 0, getVNInfoAllocator())); + DOUT << " +" << LR; + nI.addRange(LR); + vrm.addSpillPoint(NewVReg, true, MI); + } + + added.push_back(&nI); + + DOUT << "\t\t\t\tadded new interval: "; + DEBUG(nI.dump()); + DOUT << '\n'; + + unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); + if (HasUse) { + if (HasDef) + SSWeight += getSpillWeight(true, true, loopDepth); + else + SSWeight += getSpillWeight(false, true, loopDepth); + } else + SSWeight += getSpillWeight(true, false, loopDepth); + } + + + RI = mri_->reg_begin(li.reg); + } + + // Clients expect the new intervals to be returned in sorted order. + std::sort(added.begin(), added.end(), LISorter()); + + return added; +} std::vector LiveIntervals:: addIntervalsForSpills(const LiveInterval &li, + SmallVectorImpl &SpillIs, const MachineLoopInfo *loopInfo, VirtRegMap &vrm, float &SSWeight) { + + if (EnableFastSpilling) + return addIntervalsForSpillsFast(li, loopInfo, vrm, SSWeight); + assert(li.weight != HUGE_VALF && "attempt to spill already spilled interval!"); @@ -1602,10 +1769,10 @@ addIntervalsForSpills(const LiveInterval &li, // Each bit specify whether it a spill is required in the MBB. BitVector SpillMBBs(mf_->getNumBlockIDs()); - std::map > SpillIdxes; + DenseMap > SpillIdxes; BitVector RestoreMBBs(mf_->getNumBlockIDs()); - std::map > RestoreIdxes; - std::map MBBVRegsMap; + DenseMap > RestoreIdxes; + DenseMap MBBVRegsMap; std::vector NewLIs; const TargetRegisterClass* rc = mri_->getRegClass(li.reg); @@ -1687,7 +1854,7 @@ addIntervalsForSpills(const LiveInterval &li, MachineInstr *ReMatDefMI = (DefIdx == ~0u) ? 0 : getInstructionFromIndex(DefIdx); bool dummy; - if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) { + if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { // Remember how to remat the def of this val#. ReMatOrigDefs[VN] = ReMatDefMI; // Original def may be modified so we have to make a copy here. @@ -1762,7 +1929,7 @@ addIntervalsForSpills(const LiveInterval &li, CanFold = true; for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { MachineOperand &MO = MI->getOperand(j); - if (!MO.isRegister() || MO.getReg() != VReg) + if (!MO.isReg() || MO.getReg() != VReg) continue; Ops.push_back(j); @@ -1833,7 +2000,7 @@ addIntervalsForSpills(const LiveInterval &li, CanFold = true; for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { MachineOperand &MO = MI->getOperand(j); - if (!MO.isRegister() || MO.getReg() != VReg) + if (!MO.isReg() || MO.getReg() != VReg) continue; if (MO.isDef()) {