X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=d6c8a6561e4f85c680c201bca826a46e817b8fee;hb=f9410141f703f4e8a6aba717617ef958249f6d13;hp=295a1615b69d3c59a1683eba1a71900227ecd4dc;hpb=a1566f2e12ce87a5bca30bc0189a0cdbb40136a4;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 295a1615b69..d6c8a6561e4 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -19,15 +19,18 @@ #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "VirtRegMap.h" #include "llvm/Value.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/PseudoSourceValue.h" #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" @@ -45,6 +48,11 @@ static cl::opt SplitAtBB("split-intervals-at-bb", static cl::opt SplitLimit("split-limit", cl::init(-1), cl::Hidden); +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"); @@ -54,17 +62,28 @@ char LiveIntervals::ID = 0; static RegisterPass X("liveintervals", "Live Interval Analysis"); void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.addPreserved(); AU.addPreserved(); 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(); @@ -81,6 +100,7 @@ void LiveIntervals::releaseMemory() { void LiveIntervals::computeNumbering() { Index2MiMap OldI2MI = i2miMap_; + std::vector OldI2MBB = Idx2MBBMap; Idx2MBBMap.clear(); MBB2IdxMap.clear(); @@ -98,21 +118,27 @@ void LiveIntervals::computeNumbering() { MBB != E; ++MBB) { unsigned StartIdx = MIIndex; + // Insert an empty slot at the beginning of each block. + MIIndex += InstrSlots::NUM; + i2miMap_.push_back(0); + for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) { bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; assert(inserted && "multiple MachineInstr -> index mappings"); i2miMap_.push_back(I); MIIndex += InstrSlots::NUM; - FunctionSize++; + + // 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); } - if (StartIdx == MIIndex) { - // Empty MBB - MIIndex += InstrSlots::NUM; - i2miMap_.push_back(0); - } // Set the MBB2IdxMap entry for this MBB. MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); @@ -120,93 +146,101 @@ void LiveIntervals::computeNumbering() { std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); if (!OldI2MI.empty()) - for (iterator I = begin(), E = end(); I != E; ++I) - for (LiveInterval::iterator LI = I->second.begin(), LE = I->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 // original instruction has been erased. This is either the following // instruction or its predecessor. + unsigned index = LI->start / InstrSlots::NUM; unsigned offset = LI->start % InstrSlots::NUM; - if (OldI2MI[LI->start / InstrSlots::NUM]) - LI->start = mi2iMap_[OldI2MI[LI->start / InstrSlots::NUM]] + offset; - else { - unsigned i = 0; - MachineInstr* newInstr = 0; - do { - newInstr = OldI2MI[LI->start / InstrSlots::NUM + i]; - i++; - } while (!newInstr); + if (offset == InstrSlots::LOAD) { + std::vector::const_iterator I = + std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start); + // Take the pair containing the index + std::vector::const_iterator J = + (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; - if (mi2iMap_[newInstr] == - MBB2IdxMap[newInstr->getParent()->getNumber()].first) - LI->start = mi2iMap_[newInstr]; - else - LI->start = mi2iMap_[newInstr] - InstrSlots::NUM + offset; + LI->start = getMBBStartIdx(J->second); + } else { + LI->start = mi2iMap_[OldI2MI[index]] + offset; } // Remap the ending index in the same way that we remapped the start, // except for the final step where we always map to the immediately // following instruction. - if (LI->end / InstrSlots::NUM < OldI2MI.size()) { - offset = LI->end % InstrSlots::NUM; - if (OldI2MI[LI->end / InstrSlots::NUM]) - LI->end = mi2iMap_[OldI2MI[LI->end / InstrSlots::NUM]] + offset; - else { - unsigned i = 0; - MachineInstr* newInstr = 0; - do { - newInstr = OldI2MI[LI->end / InstrSlots::NUM + i]; - i++; - } while (!newInstr); - - LI->end = mi2iMap_[newInstr]; - } + index = (LI->end - 1) / InstrSlots::NUM; + offset = LI->end % InstrSlots::NUM; + if (offset == InstrSlots::LOAD) { + // VReg dies at end of block. + std::vector::const_iterator I = + std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end); + --I; + + LI->end = getMBBEndIdx(I->second) + 1; } else { - LI->end = i2miMap_.size() * InstrSlots::NUM; + unsigned idx = index; + while (index < OldI2MI.size() && !OldI2MI[index]) ++index; + + if (index != OldI2MI.size()) + LI->end = mi2iMap_[OldI2MI[index]] + (idx == index ? offset : 0); + 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; - offset = vni->def % InstrSlots::NUM; - if (OldI2MI[vni->def / InstrSlots::NUM]) - vni->def = mi2iMap_[OldI2MI[vni->def / InstrSlots::NUM]] + offset; - else { - unsigned i = 0; - MachineInstr* newInstr = 0; - do { - newInstr = OldI2MI[vni->def / InstrSlots::NUM + i]; - i++; - } while (!newInstr); + // 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 = + (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; - if (mi2iMap_[newInstr] == - MBB2IdxMap[newInstr->getParent()->getNumber()].first) - vni->def = mi2iMap_[newInstr]; - else - vni->def = mi2iMap_[newInstr] - InstrSlots::NUM + 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) { - offset = vni->kills[i] % InstrSlots::NUM; - if (OldI2MI[vni->kills[i] / InstrSlots::NUM]) - vni->kills[i] = mi2iMap_[OldI2MI[vni->kills[i] / InstrSlots::NUM]] + - offset; - else { - unsigned e = 0; - MachineInstr* newInstr = 0; - do { - newInstr = OldI2MI[vni->kills[i] / InstrSlots::NUM + e]; - e++; - } while (!newInstr); + // 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]); + --I; + + vni->kills[i] = getMBBEndIdx(I->second); + } else { + unsigned idx = index; + while (index < OldI2MI.size() && !OldI2MI[index]) ++index; - vni->kills[i] = mi2iMap_[newInstr]; + if (index != OldI2MI.size()) + vni->kills[i] = mi2iMap_[OldI2MI[index]] + + (idx == index ? offset : 0); + else + vni->kills[i] = InstrSlots::NUM * i2miMap_.size(); } } } + } } /// runOnMachineFunction - Register allocate the whole function @@ -217,6 +251,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { tm_ = &fn.getTarget(); tri_ = tm_->getRegisterInfo(); tii_ = tm_->getInstrInfo(); + aa_ = &getAnalysis(); lv_ = &getAnalysis(); allocatableRegs_ = tri_->getAllocatableSet(fn); @@ -227,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"; } @@ -240,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"; } @@ -276,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) @@ -322,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; @@ -362,9 +400,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // of the defining block, potentially live across some blocks, then is // live into some number of blocks, but gets killed. Start by adding a // range that goes from this definition to the end of the defining block. - LiveRange NewLR(defIndex, - getInstructionIndex(&mbb->back()) + InstrSlots::NUM, - ValNo); + LiveRange NewLR(defIndex, getMBBEndIdx(mbb)+1, ValNo); DOUT << " +" << NewLR; interval.addRange(NewLR); @@ -407,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; @@ -474,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; @@ -484,7 +526,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, CopyMI = mi; ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); - unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; + unsigned killIndex = getMBBEndIdx(mbb) + 1; LiveRange LR(defIndex, killIndex, ValNo); interval.addRange(LR); interval.addKill(ValNo, killIndex); @@ -508,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 @@ -515,15 +560,18 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // [defSlot(def), defSlot(def)+1) if (MO.isDead()) { DOUT << " dead"; - end = getDefIndex(start) + 1; + end = start + 1; goto exit; } // If it is not dead on definition, it must be killed by a // subsequent instruction. Hence its interval is: // [defSlot(def), useSlot(kill)+1) + baseIndex += InstrSlots::NUM; while (++mi != MBB->end()) { - baseIndex += InstrSlots::NUM; + while (baseIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(baseIndex) == 0) + baseIndex += InstrSlots::NUM; if (mi->killsRegister(interval.reg, tri_)) { DOUT << " killed"; end = getUseIndex(baseIndex) + 1; @@ -534,16 +582,18 @@ 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; } + + baseIndex += InstrSlots::NUM; } // The only case we should have a dead physreg here without a killing or // 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?"); @@ -595,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"; @@ -612,6 +666,9 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, } baseIndex += InstrSlots::NUM; + while (baseIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(baseIndex) == 0) + baseIndex += InstrSlots::NUM; ++mi; } @@ -627,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'; @@ -637,15 +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; + 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(); @@ -661,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; @@ -668,14 +732,22 @@ 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); + } } + + // Skip over the empty slots after each instruction. + unsigned Slots = MI->getDesc().getNumDefs(); + if (Slots == 0) + Slots = 1; + MIIndex += InstrSlots::NUM * Slots; - MIIndex += InstrSlots::NUM; + // Skip over empty indices. + while (MIIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(MIIndex) == 0) + MIIndex += InstrSlots::NUM; } - - if (MBB->begin() == miEnd) MIIndex += InstrSlots::NUM; // Empty MBB } } @@ -695,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 @@ -731,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) @@ -740,7 +811,9 @@ unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, assert(!RegOp && "Can't rematerialize instruction with multiple register operand!"); RegOp = MO.getReg(); +#ifndef NDEBUG break; +#endif } return RegOp; } @@ -759,11 +832,11 @@ 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; - isLoad = false; if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) return true; @@ -776,32 +849,110 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, // This is a load from fixed stack slot. It can be rematerialized. return true; - if (tii_->isTriviallyReMaterializable(MI)) { + // If the target-specific rules don't identify an instruction as + // being trivially rematerializable, use some target-independent + // rules. + if (!MI->getDesc().isRematerializable() || + !tii_->isTriviallyReMaterializable(MI)) { + if (!EnableAggressiveRemat) + return false; + + // If the instruction accesses memory but the memoperands have been lost, + // we can't analyze it. const TargetInstrDesc &TID = MI->getDesc(); - isLoad = TID.isSimpleLoad(); - - 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) { - MachineInstr *UseMI = &*ri; - unsigned UseIdx = getInstructionIndex(UseMI); - if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) + if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty()) + return false; + + // Avoid instructions obviously unsafe for remat. + if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable()) + return false; + + // 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){ + const MachineMemOperand &MMO = *I; + if (MMO.isVolatile() || MMO.isStore()) + return false; + const Value *V = MMO.getValue(); + if (!V) + return false; + if (const PseudoSourceValue *PSV = dyn_cast(V)) { + if (!PSV->isConstant(mf_->getFrameInfo())) + return false; + } else if (!aa_->pointsToConstantMemory(V)) + return false; + } + + // If any of the registers accessed are non-constant, conservatively assume + // the instruction is not rematerializable. + unsigned ImpUse = 0; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (MO.isReg()) { + unsigned Reg = MO.getReg(); + if (Reg == 0) continue; - if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) + if (TargetRegisterInfo::isPhysicalRegister(Reg)) + return false; + + // Only allow one def, and that in the first operand. + if (MO.isDef() != (i == 0)) return false; + + // Only allow constant-valued registers. + bool IsLiveIn = mri_->isLiveIn(Reg); + MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg), + E = mri_->def_end(); + + // For the def, it should be the only def. + if (MO.isDef() && (next(I) != E || IsLiveIn)) + return false; + + if (MO.isUse()) { + // Only allow one use other register use, as that's all the + // remat mechanisms support currently. + if (Reg != li.reg) { + if (ImpUse == 0) + ImpUse = Reg; + else if (Reg != ImpUse) + return false; + } + // For uses, there should be only one associate def. + if (I != E && (next(I) != E || IsLiveIn)) + return false; + } } } - return true; } - return false; + 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) { + MachineInstr *UseMI = &*ri; + unsigned UseIdx = getInstructionIndex(UseMI); + if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) + continue; + 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) { @@ -815,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; } @@ -955,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)) @@ -982,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); @@ -990,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; @@ -1042,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)) @@ -1225,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; @@ -1295,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: @@ -1357,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()) { @@ -1390,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 @@ -1430,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]; @@ -1444,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]; @@ -1487,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!"); @@ -1504,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); @@ -1589,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. @@ -1664,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); @@ -1735,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()) { @@ -1793,7 +2058,7 @@ addIntervalsForSpills(const LiveInterval &li, for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { LiveInterval *LI = NewLIs[i]; if (!LI->empty()) { - LI->weight /= getApproximateInstructionCount(*LI); + LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI); if (!AddedKill.count(LI)) { LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; unsigned LastUseIdx = getBaseIndex(LR->end);