X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=196109ba09d4fa66d2c936ec6c933c5087b03533;hb=31ec841be1f51a60f5b655aa2a008eb68e48c07a;hp=35f0723b9fc58b5f820416bd6880b323fdb61e97;hpb=313d4b809326f3e04814f94e5b8ae05649d8e0f6;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 35f0723b9fc..196109ba09d 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -36,16 +36,14 @@ #include using namespace llvm; -namespace { - // Hidden options for help debugging. - cl::opt DisableReMat("disable-rematerialization", - cl::init(false), cl::Hidden); - - cl::opt SplitAtBB("split-intervals-at-bb", - cl::init(true), cl::Hidden); - cl::opt SplitLimit("split-limit", - cl::init(-1), cl::Hidden); -} +// Hidden options for help debugging. +static cl::opt DisableReMat("disable-rematerialization", + cl::init(false), cl::Hidden); + +static cl::opt SplitAtBB("split-intervals-at-bb", + cl::init(true), cl::Hidden); +static cl::opt SplitLimit("split-limit", + cl::init(-1), cl::Hidden); STATISTIC(numIntervals, "Number of original intervals"); STATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); @@ -53,9 +51,7 @@ STATISTIC(numFolds , "Number of loads/stores folded into instructions"); STATISTIC(numSplits , "Number of intervals split"); char LiveIntervals::ID = 0; -namespace { - RegisterPass X("liveintervals", "Live Interval Analysis"); -} +static RegisterPass X("liveintervals", "Live Interval Analysis"); void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved(); @@ -69,6 +65,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { } void LiveIntervals::releaseMemory() { + MBB2IdxMap.clear(); Idx2MBBMap.clear(); mi2iMap_.clear(); i2miMap_.clear(); @@ -79,17 +76,14 @@ void LiveIntervals::releaseMemory() { delete ClonedMIs[i]; } -/// runOnMachineFunction - Register allocate the whole function -/// -bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { - mf_ = &fn; - mri_ = &mf_->getRegInfo(); - tm_ = &fn.getTarget(); - tri_ = tm_->getRegisterInfo(); - tii_ = tm_->getInstrInfo(); - lv_ = &getAnalysis(); - allocatableRegs_ = tri_->getAllocatableSet(fn); - +void LiveIntervals::computeNumbering() { + Index2MiMap OldI2MI = i2miMap_; + + Idx2MBBMap.clear(); + MBB2IdxMap.clear(); + mi2iMap_.clear(); + i2miMap_.clear(); + // Number MachineInstrs and MachineBasicBlocks. // Initialize MBB indexes to a sentinal. MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); @@ -106,13 +100,120 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 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()] = std::make_pair(StartIdx, MIIndex - 1); Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); } 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) { + + // 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 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 (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, + // 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]; + } + } else { + LI->end = i2miMap_.size() * InstrSlots::NUM; + } + + // 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); + + 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 + // 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); + + vni->kills[i] = mi2iMap_[newInstr]; + } + } + } +} +/// runOnMachineFunction - Register allocate the whole function +/// +bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { + mf_ = &fn; + mri_ = &mf_->getRegInfo(); + tm_ = &fn.getTarget(); + tri_ = tm_->getRegisterInfo(); + tii_ = tm_->getInstrInfo(); + lv_ = &getAnalysis(); + allocatableRegs_ = tri_->getAllocatableSet(fn); + + computeNumbering(); computeIntervals(); numIntervals += getNumIntervals(); @@ -132,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"; @@ -201,6 +302,11 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); + if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { + DOUT << "is a implicit_def\n"; + return; + } + // Virtual registers may be defined multiple times (due to phi // elimination and 2-addr elimination). Much of what we do only has to be // done once for the vreg. We use an empty interval to detect the first @@ -212,6 +318,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || + mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || tii_->isMoveInstr(*mi, SrcReg, DstReg)) CopyMI = mi; ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); @@ -258,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), + ValNo); + interval.addRange(LR); + DOUT << " +" << LR; } } @@ -324,7 +428,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // If this redefinition is dead, we need to add a dummy unit live // range covering the def slot. - if (lv_->RegisterDefIsDead(mi, interval.reg)) + if (mi->registerDefIsDead(interval.reg, tri_)) interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); DOUT << " RESULT: "; @@ -367,6 +471,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || + mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || tii_->isMoveInstr(*mi, SrcReg, DstReg)) CopyMI = mi; ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); @@ -399,7 +504,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // If it is not used after definition, it is considered dead at // the instruction defining it. Hence its interval is: // [defSlot(def), defSlot(def)+1) - if (lv_->RegisterDefIsDead(mi, interval.reg)) { + if (mi->registerDefIsDead(interval.reg, tri_)) { DOUT << " dead"; end = getDefIndex(start) + 1; goto exit; @@ -410,11 +515,11 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // [defSlot(def), useSlot(kill)+1) while (++mi != MBB->end()) { baseIndex += InstrSlots::NUM; - if (lv_->KillsRegister(mi, interval.reg)) { + if (mi->killsRegister(interval.reg, tri_)) { DOUT << " killed"; end = getUseIndex(baseIndex) + 1; goto exit; - } else if (lv_->ModifiesRegister(mi, interval.reg)) { + } else if (mi->modifiesRegister(interval.reg, tri_)) { // 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: @@ -454,13 +559,15 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || + MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || tii_->isMoveInstr(*MI, SrcReg, DstReg)) CopyMI = MI; handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI); // Def of a register also defines its sub-registers. for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS) - // Avoid processing some defs more than once. - if (!MI->findRegisterDefOperand(*AS)) + // If MI also modifies the sub-register explicitly, avoid processing it + // more than once. Do not pass in TRI here so it checks for exact match. + if (!MI->modifiesRegister(*AS)) handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); } } @@ -477,11 +584,11 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, unsigned start = baseIndex; unsigned end = start; while (mi != MBB->end()) { - if (lv_->KillsRegister(mi, interval.reg)) { + if (mi->killsRegister(interval.reg, tri_)) { DOUT << " killed"; end = getUseIndex(baseIndex) + 1; goto exit; - } else if (lv_->ModifiesRegister(mi, interval.reg)) { + } else if (mi->modifiesRegister(interval.reg, tri_)) { // 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: @@ -554,6 +661,8 @@ void LiveIntervals::computeIntervals() { MIIndex += InstrSlots::NUM; } + + if (MBB->begin() == miEnd) MIIndex += InstrSlots::NUM; // Empty MBB } } @@ -588,6 +697,8 @@ unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) return VNI->copy->getOperand(1).getReg(); + if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG) + return VNI->copy->getOperand(2).getReg(); unsigned SrcReg, DstReg; if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg)) return SrcReg; @@ -640,10 +751,20 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, return false; isLoad = false; - const TargetInstrDesc &TID = MI->getDesc(); - if (TID.isImplicitDef()) + if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) + return true; + + int FrameIdx = 0; + if (tii_->isLoadFromStackSlot(MI, FrameIdx) && + mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) + // FIXME: Let target specific isReallyTriviallyReMaterializable determines + // this but remember this is not safe to fold into a two-address + // instruction. + // This is a load from fixed stack slot. It can be rematerialized. return true; + if (tii_->isTriviallyReMaterializable(MI)) { + const TargetInstrDesc &TID = MI->getDesc(); isLoad = TID.isSimpleLoad(); unsigned ImpUse = getReMatImplicitUse(li, MI); @@ -655,38 +776,14 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, unsigned UseIdx = getInstructionIndex(UseMI); if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) continue; - if (!canFoldMemoryOperand(UseMI, li.reg) && - !isValNoAvailableAt(ImpLi, MI, UseIdx)) + if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) return false; } } return true; } - int FrameIdx = 0; - if (!tii_->isLoadFromStackSlot(MI, FrameIdx) || - !mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) - return false; - - // This is a load from fixed stack slot. It can be rematerialized unless it's - // re-defined by a two-address instruction. - isLoad = true; - for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); - i != e; ++i) { - const VNInfo *VNI = *i; - if (VNI == ValNo) - continue; - unsigned DefIdx = VNI->def; - if (DefIdx == ~1U) - continue; // Dead val#. - MachineInstr *DefMI = (DefIdx == ~0u) - ? NULL : getInstructionFromIndex(DefIdx); - if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg)) { - isLoad = false; - return false; - } - } - return true; + return false; } /// isReMaterializable - Returns true if every definition of MI of every @@ -712,33 +809,22 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { return true; } -/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from -/// slot / to reg or any rematerialized load into ith operand of specified -/// MI. If it is successul, MI is updated with the newly created MI and -/// returns true. -bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, - VirtRegMap &vrm, MachineInstr *DefMI, - unsigned InstrIdx, - SmallVector &Ops, - bool isSS, int Slot, unsigned Reg) { - unsigned MRInfo = 0; +/// FilterFoldedOps - Filter out two-address use operands. Return +/// true if it finds any issue with the operands that ought to prevent +/// folding. +static bool FilterFoldedOps(MachineInstr *MI, + SmallVector &Ops, + unsigned &MRInfo, + SmallVector &FoldOps) { const TargetInstrDesc &TID = MI->getDesc(); - // If it is an implicit def instruction, just delete it. - if (TID.isImplicitDef()) { - RemoveMachineInstrFromMaps(MI); - vrm.RemoveMachineInstrFromMaps(MI); - MI->eraseFromParent(); - ++numFolds; - return true; - } - SmallVector FoldOps; + MRInfo = 0; for (unsigned i = 0, e = Ops.size(); i != e; ++i) { unsigned OpIdx = Ops[i]; MachineOperand &MO = MI->getOperand(OpIdx); // FIXME: fold subreg use. if (MO.getSubReg()) - return false; + return true; if (MO.isDef()) MRInfo |= (unsigned)VirtRegMap::isMod; else { @@ -752,10 +838,46 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, } FoldOps.push_back(OpIdx); } + return false; +} + + +/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from +/// slot / to reg or any rematerialized load into ith operand of specified +/// MI. If it is successul, MI is updated with the newly created MI and +/// returns true. +bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, + VirtRegMap &vrm, MachineInstr *DefMI, + unsigned InstrIdx, + SmallVector &Ops, + bool isSS, int Slot, unsigned Reg) { + // If it is an implicit def instruction, just delete it. + if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { + RemoveMachineInstrFromMaps(MI); + vrm.RemoveMachineInstrFromMaps(MI); + MI->eraseFromParent(); + ++numFolds; + return true; + } + + // Filter the list of operand indexes that are to be folded. Abort if + // any operand will prevent folding. + unsigned MRInfo = 0; + SmallVector FoldOps; + if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) + return false; + + // The only time it's safe to fold into a two address instruction is when + // it's folding reload and spill from / into a spill stack slot. + if (DefMI && (MRInfo & VirtRegMap::isMod)) + return false; MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); if (fmi) { + // Remember this instruction uses the spill slot. + if (isSS) vrm.addSpillSlotUse(Slot, fmi); + // Attempt to fold the memory reference into the instruction. If // we can do this, we don't need to insert spill code. if (lv_) @@ -767,6 +889,7 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); vrm.transferSpillPts(MI, fmi); vrm.transferRestorePts(MI, fmi); + vrm.transferEmergencySpills(MI, fmi); mi2iMap_.erase(MI); i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; mi2iMap_[fmi] = InstrIdx; @@ -780,33 +903,19 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, /// canFoldMemoryOperand - Returns true if the specified load / store /// folding is possible. bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, - SmallVector &Ops) const { + SmallVector &Ops, + bool ReMat) const { + // Filter the list of operand indexes that are to be folded. Abort if + // any operand will prevent folding. + unsigned MRInfo = 0; SmallVector FoldOps; - for (unsigned i = 0, e = Ops.size(); i != e; ++i) { - unsigned OpIdx = Ops[i]; - // FIXME: fold subreg use. - if (MI->getOperand(OpIdx).getSubReg()) - return false; - FoldOps.push_back(OpIdx); - } + if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) + return false; - return tii_->canFoldMemoryOperand(MI, FoldOps); -} + // It's only legal to remat for a use, not a def. + if (ReMat && (MRInfo & VirtRegMap::isMod)) + return false; -bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, unsigned Reg) const { - SmallVector FoldOps; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& mop = MI->getOperand(i); - if (!mop.isRegister()) - continue; - unsigned UseReg = mop.getReg(); - if (UseReg != Reg) - continue; - // FIXME: fold subreg use. - if (mop.getSubReg()) - return false; - FoldOps.push_back(i); - } return tii_->canFoldMemoryOperand(MI, FoldOps); } @@ -845,9 +954,9 @@ void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, if (!vrm.isReMaterialized(Reg)) continue; MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); - int OpIdx = ReMatMI->findRegisterUseOperandIdx(li.reg); - if (OpIdx != -1) - ReMatMI->getOperand(OpIdx).setReg(NewVReg); + MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); + if (UseMO) + UseMO->setReg(NewVReg); } } @@ -865,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) { @@ -888,15 +999,6 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, if (MI == ReMatOrigDefMI && CanDelete) { DOUT << "\t\t\t\tErasing re-materlizable def: "; DOUT << MI << '\n'; - unsigned ImpUse = getReMatImplicitUse(li, MI); - if (ImpUse) { - // To be deleted MI has a virtual register operand, update the - // spill weight of the register interval. - unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); - LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight -= - getSpillWeight(false, true, loopDepth) / ImpLi.getSize(); - } RemoveMachineInstrFromMaps(MI); vrm.RemoveMachineInstrFromMaps(MI); MI->eraseFromParent(); @@ -943,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) { @@ -954,13 +1063,17 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, HasUse = false; HasDef = false; CanFold = false; + if (isRemoved(MI)) { + SSWeight -= Weight; + break; + } goto RestartInstruction; } } else { - CanFold = canFoldMemoryOperand(MI, Ops); + // 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; @@ -1061,33 +1174,24 @@ 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. -struct RewriteInfo { - unsigned Index; - MachineInstr *MI; - bool HasUse; - bool HasDef; - RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) - : Index(i), MI(mi), HasUse(u), HasDef(d) {} -}; - -struct RewriteInfoCompare { - bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { - return LHS.Index < RHS.Index; - } -}; +namespace { + struct RewriteInfo { + unsigned Index; + MachineInstr *MI; + bool HasUse; + bool HasDef; + RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) + : Index(i), MI(mi), HasUse(u), HasDef(d) {} + }; + + struct RewriteInfoCompare { + bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { + return LHS.Index < RHS.Index; + } + }; +} void LiveIntervals:: rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, @@ -1104,20 +1208,21 @@ 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); unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; // First collect all the def / use in this live range that will be rewritten. - // Make sure they are sorted according instruction index. + // Make sure they are sorted according to instruction index. std::vector RewriteMIs; for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), re = mri_->reg_end(); ri != re; ) { - MachineInstr *MI = &(*ri); + MachineInstr *MI = &*ri; MachineOperand &O = ri.getOperand(); ++ri; + assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); unsigned index = getInstructionIndex(MI); if (index < start || index >= end) continue; @@ -1149,11 +1254,10 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, if (ImpUse && MI != ReMatDefMI) { // Re-matting an instruction with virtual register use. Update the - // register interval's spill weight. - unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); + // register interval's spill weight to HUGE_VALF to prevent it from + // being spilled. LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight += - getSpillWeight(false, true, loopDepth) * NumUses / ImpLi.getSize(); + ImpLi.weight = HUGE_VALF; } unsigned MBBId = MBB->getNumber(); @@ -1192,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; @@ -1217,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)); } @@ -1317,10 +1421,45 @@ void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, Restores[i].index = -1; } +/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being +/// spilled and create empty intervals for their uses. +void +LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, + const TargetRegisterClass* rc, + std::vector &NewLIs) { + for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), + re = mri_->reg_end(); ri != re; ) { + MachineOperand &O = ri.getOperand(); + MachineInstr *MI = &*ri; + ++ri; + if (O.isDef()) { + assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && + "Register def was not rewritten?"); + RemoveMachineInstrFromMaps(MI); + vrm.RemoveMachineInstrFromMaps(MI); + MI->eraseFromParent(); + } else { + // This must be an use of an implicit_def so it's not part of the live + // interval. Create a new empty live interval for it. + // FIXME: Can we simply erase some of the instructions? e.g. Stores? + unsigned NewVReg = mri_->createVirtualRegister(rc); + vrm.grow(); + vrm.setIsImplicitlyDefined(NewVReg); + NewLIs.push_back(&getOrCreateInterval(NewVReg)); + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (MO.isReg() && MO.getReg() == li.reg) + MO.setReg(NewVReg); + } + } + } +} + 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(); @@ -1332,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; @@ -1386,16 +1528,19 @@ 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; } @@ -1460,18 +1605,22 @@ 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. - if (!TrySplit) + if (!TrySplit) { + handleSpilledImpDefs(li, vrm, rc, NewLIs); return NewLIs; + } SmallPtrSet AddedKill; SmallVector Ops; 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; @@ -1518,14 +1667,20 @@ addIntervalsForSpills(const LiveInterval &li, } } - // Else tell the spiller to issue a spill. + // Otherwise tell the spiller to issue a spill. if (!Folded) { LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; bool isKill = LR->end == getStoreIndex(index); - vrm.addSpillPoint(VReg, isKill, MI); + if (!MI->registerDefIsDead(nI.reg)) + // No need to spill a dead def. + vrm.addSpillPoint(VReg, isKill, MI); if (isKill) AddedKill.insert(&nI); } + + // Update spill slot weight. + if (!isReMat) + SSWeight += getSpillWeight(true, false, loopDepth); } Id = SpillMBBs.find_next(Id); } @@ -1533,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; @@ -1540,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(); @@ -1563,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); @@ -1577,12 +1736,10 @@ addIntervalsForSpills(const LiveInterval &li, 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. - unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); + // interval's spill weight to HUGE_VALF to prevent it from being + // spilled. LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight += - getSpillWeight(false, true, loopDepth) / ImpLi.getSize(); - + ImpLi.weight = HUGE_VALF; MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); } } @@ -1593,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); } @@ -1608,7 +1769,7 @@ addIntervalsForSpills(const LiveInterval &li, LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; unsigned LastUseIdx = getBaseIndex(LR->end); MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); - int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg); + int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); assert(UseIdx != -1); if (LastUse->getOperand(UseIdx).isImplicit() || LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){ @@ -1620,5 +1781,99 @@ addIntervalsForSpills(const LiveInterval &li, } } + handleSpilledImpDefs(li, vrm, rc, RetNewLIs); return RetNewLIs; } + +/// hasAllocatableSuperReg - Return true if the specified physical register has +/// any super register that's allocatable. +bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { + for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) + if (allocatableRegs_[*AS] && hasInterval(*AS)) + return true; + return false; +} + +/// getRepresentativeReg - Find the largest super register of the specified +/// physical register. +unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { + // Find the largest super-register that is allocatable. + unsigned BestReg = Reg; + for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { + unsigned SuperReg = *AS; + if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { + BestReg = SuperReg; + break; + } + } + return BestReg; +} + +/// getNumConflictsWithPhysReg - Return the number of uses and defs of the +/// specified interval that conflicts with the specified physical register. +unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, + unsigned PhysReg) const { + unsigned NumConflicts = 0; + const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); + for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), + E = mri_->reg_end(); I != E; ++I) { + MachineOperand &O = I.getOperand(); + MachineInstr *MI = O.getParent(); + unsigned Index = getInstructionIndex(MI); + if (pli.liveAt(Index)) + ++NumConflicts; + } + return NumConflicts; +} + +/// spillPhysRegAroundRegDefsUses - Spill the specified physical register +/// around all defs and uses of the specified interval. +void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, + unsigned PhysReg, VirtRegMap &vrm) { + unsigned SpillReg = getRepresentativeReg(PhysReg); + + for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) + // If there are registers which alias PhysReg, but which are not a + // sub-register of the chosen representative super register. Assert + // since we can't handle it yet. + assert(*AS == SpillReg || !allocatableRegs_[*AS] || + tri_->isSuperRegister(*AS, SpillReg)); + + LiveInterval &pli = getInterval(SpillReg); + SmallPtrSet SeenMIs; + for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), + E = mri_->reg_end(); I != E; ++I) { + MachineOperand &O = I.getOperand(); + MachineInstr *MI = O.getParent(); + if (SeenMIs.count(MI)) + continue; + SeenMIs.insert(MI); + unsigned Index = getInstructionIndex(MI); + if (pli.liveAt(Index)) { + vrm.addEmergencySpill(SpillReg, MI); + pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); + for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { + if (!hasInterval(*AS)) + continue; + LiveInterval &spli = getInterval(*AS); + if (spli.liveAt(Index)) + spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); + } + } + } +} + +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; +}