X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=49015a81a85a1e8de9dafc0bc7c5bba7562ccd96;hb=d70dbb5d627a0408eccf88033143efa62ee0e6c0;hp=80d3547e4b41798b68e8d3d19bbdad5d7d0a44a0;hpb=749c6f6b5ed301c84aac562e414486549d7b98eb;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 80d3547e4b4..49015a81a85 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -25,7 +25,7 @@ #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" -#include "llvm/Target/MRegisterInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Support/CommandLine.h" @@ -79,31 +79,16 @@ void LiveIntervals::releaseMemory() { delete ClonedMIs[i]; } -namespace llvm { - inline bool operator<(unsigned V, const IdxMBBPair &IM) { - return V < IM.first; - } - - inline bool operator<(const IdxMBBPair &IM, unsigned V) { - return IM.first < V; - } - - struct Idx2MBBCompare { - bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const { - return LHS.first < RHS.first; - } - }; -} - /// runOnMachineFunction - Register allocate the whole function /// bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { mf_ = &fn; + mri_ = &mf_->getRegInfo(); tm_ = &fn.getTarget(); - mri_ = tm_->getRegisterInfo(); + tri_ = tm_->getRegisterInfo(); tii_ = tm_->getInstrInfo(); lv_ = &getAnalysis(); - allocatableRegs_ = mri_->getAllocatableSet(fn); + allocatableRegs_ = tri_->getAllocatableSet(fn); // Number MachineInstrs and MachineBasicBlocks. // Initialize MBB indexes to a sentinal. @@ -134,7 +119,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { DOUT << "********** INTERVALS **********\n"; for (iterator I = begin(), E = end(); I != E; ++I) { - I->second.print(DOUT, mri_); + I->second.print(DOUT, tri_); DOUT << "\n"; } @@ -147,7 +132,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(DOUT, mri_); + I->second.print(DOUT, tri_); DOUT << "\n"; } @@ -188,12 +173,12 @@ bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, unsigned PhysReg = mop.getReg(); if (PhysReg == 0 || PhysReg == li.reg) continue; - if (MRegisterInfo::isVirtualRegister(PhysReg)) { + if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { if (!vrm.hasPhys(PhysReg)) continue; PhysReg = vrm.getPhys(PhysReg); } - if (PhysReg && mri_->regsOverlap(PhysReg, reg)) + if (PhysReg && tri_->regsOverlap(PhysReg, reg)) return true; } } @@ -203,8 +188,8 @@ bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, } void LiveIntervals::printRegName(unsigned reg) const { - if (MRegisterInfo::isPhysicalRegister(reg)) - cerr << mri_->getName(reg); + if (TargetRegisterInfo::isPhysicalRegister(reg)) + cerr << tri_->getName(reg); else cerr << "%reg" << reg; } @@ -224,14 +209,12 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // Get the Idx of the defining instructions. unsigned defIndex = getDefIndex(MIIdx); VNInfo *ValNo; + MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; - if (tii_->isMoveInstr(*mi, SrcReg, DstReg)) - ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator); - else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) - ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(), - VNInfoAllocator); - else - ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator); + if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || + tii_->isMoveInstr(*mi, SrcReg, DstReg)) + CopyMI = mi; + ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); assert(ValNo->id == 0 && "First value in interval is not 0?"); @@ -309,12 +292,12 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // are actually two values in the live interval. Because of this we // need to take the LiveRegion that defines this register and split it // into two values. - unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); + assert(interval.containsOneValue()); + unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); unsigned RedefIndex = getDefIndex(MIIdx); const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); VNInfo *OldValNo = OldLR->valno; - unsigned OldEnd = OldLR->end; // Delete the initial value, which should be short and continuous, // because the 2-addr copy must be in the same MBB as the redef. @@ -326,19 +309,18 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // The new value number (#1) is defined by the instruction we claimed // defined value #0. - VNInfo *ValNo = interval.getNextValue(0, 0, VNInfoAllocator); - interval.copyValNumInfo(ValNo, OldValNo); + VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy, + VNInfoAllocator); // Value#0 is now defined by the 2-addr instruction. - OldValNo->def = RedefIndex; - OldValNo->reg = 0; + OldValNo->def = RedefIndex; + OldValNo->copy = 0; // Add the new live interval which replaces the range for the input copy. LiveRange LR(DefIndex, RedefIndex, ValNo); DOUT << " replace range with " << LR; interval.addRange(LR); interval.addKill(ValNo, RedefIndex); - interval.removeKills(ValNo, RedefIndex, OldEnd); // If this redefinition is dead, we need to add a dummy unit live // range covering the def slot. @@ -346,7 +328,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); DOUT << " RESULT: "; - interval.print(DOUT, mri_); + interval.print(DOUT, tri_); } else { // Otherwise, this must be because of phi elimination. If this is the @@ -362,11 +344,10 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, unsigned Start = getMBBStartIdx(Killer->getParent()); unsigned End = getUseIndex(getInstructionIndex(Killer))+1; DOUT << " Removing [" << Start << "," << End << "] from: "; - interval.print(DOUT, mri_); DOUT << "\n"; + interval.print(DOUT, tri_); DOUT << "\n"; interval.removeRange(Start, End); - interval.addKill(VNI, Start); VNI->hasPHIKill = true; - DOUT << " RESULT: "; interval.print(DOUT, mri_); + DOUT << " RESULT: "; interval.print(DOUT, tri_); // Replace the interval with one of a NEW value number. Note that this // value number isn't actually defined by an instruction, weird huh? :) @@ -374,7 +355,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, DOUT << " replace range with " << LR; interval.addRange(LR); interval.addKill(LR.valno, End); - DOUT << " RESULT: "; interval.print(DOUT, mri_); + DOUT << " RESULT: "; interval.print(DOUT, tri_); } // In the case of PHI elimination, each variable definition is only @@ -383,14 +364,12 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, unsigned defIndex = getDefIndex(MIIdx); VNInfo *ValNo; + MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; - if (tii_->isMoveInstr(*mi, SrcReg, DstReg)) - ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator); - else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) - ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(), - VNInfoAllocator); - else - ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator); + if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || + tii_->isMoveInstr(*mi, SrcReg, DstReg)) + CopyMI = mi; + ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; LiveRange LR(defIndex, killIndex, ValNo); @@ -408,7 +387,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator mi, unsigned MIIdx, LiveInterval &interval, - unsigned SrcReg) { + MachineInstr *CopyMI) { // A physical register cannot be live across basic block, so its // lifetime must end somewhere in its defining basic block. DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); @@ -449,7 +428,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // 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(!SrcReg && "physreg was not killed in defining block!"); + assert(!CopyMI && "physreg was not killed in defining block!"); end = getDefIndex(start) + 1; // It's dead. exit: @@ -458,7 +437,7 @@ exit: // Already exists? Extend old live interval. LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); VNInfo *ValNo = (OldLR != interval.end()) - ? OldLR->valno : interval.getNextValue(start, SrcReg, VNInfoAllocator); + ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator); LiveRange LR(start, end, ValNo); interval.addRange(LR); interval.addKill(LR.valno, end); @@ -469,17 +448,17 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI, unsigned MIIdx, unsigned reg) { - if (MRegisterInfo::isVirtualRegister(reg)) + if (TargetRegisterInfo::isVirtualRegister(reg)) handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); else if (allocatableRegs_[reg]) { + MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; - if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) - SrcReg = MI->getOperand(1).getReg(); - else if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) - SrcReg = 0; - handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg); + if (MI->getOpcode() == TargetInstrInfo::EXTRACT_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 = mri_->getSubRegisters(reg); *AS; ++AS) + for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS) // Avoid processing some defs more than once. if (!MI->findRegisterDefOperand(*AS)) handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); @@ -556,7 +535,7 @@ void LiveIntervals::computeIntervals() { LE = MBB->livein_end(); LI != LE; ++LI) { handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); // Multiple live-ins can alias the same register. - for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS) + for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) if (!hasInterval(*AS)) handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), true); @@ -596,16 +575,62 @@ bool LiveIntervals::findLiveInMBBs(const LiveRange &LR, LiveInterval LiveIntervals::createInterval(unsigned reg) { - float Weight = MRegisterInfo::isPhysicalRegister(reg) ? + float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; return LiveInterval(reg, Weight); } +/// getVNInfoSourceReg - Helper function that parses the specified VNInfo +/// copy field and returns the source register that defines it. +unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { + if (!VNI->copy) + return 0; + + if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) + return VNI->copy->getOperand(1).getReg(); + unsigned SrcReg, DstReg; + if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg)) + return SrcReg; + assert(0 && "Unrecognized copy instruction!"); + return 0; +} //===----------------------------------------------------------------------===// // Register allocator hooks. // +/// getReMatImplicitUse - If the remat definition MI has one (for now, we only +/// allow one) virtual register operand, then its uses are implicitly using +/// the register. Returns the virtual register. +unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, + MachineInstr *MI) const { + unsigned RegOp = 0; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isRegister() || !MO.isUse()) + continue; + unsigned Reg = MO.getReg(); + if (Reg == 0 || Reg == li.reg) + continue; + // FIXME: For now, only remat MI with at most one register operand. + assert(!RegOp && + "Can't rematerialize instruction with multiple register operand!"); + RegOp = MO.getReg(); + break; + } + return RegOp; +} + +/// isValNoAvailableAt - Return true if the val# of the specified interval +/// which reaches the given instruction also reaches the specified use index. +bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, + unsigned UseIdx) const { + unsigned Index = getInstructionIndex(MI); + VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; + LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); + return UI != li.end() && UI->valno == ValNo; +} + /// isReMaterializable - Returns true if the definition MI of the specified /// val# of the specified interval is re-materializable. bool LiveIntervals::isReMaterializable(const LiveInterval &li, @@ -616,14 +641,31 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, isLoad = false; const TargetInstrDesc &TID = MI->getDesc(); - if (TID.isImplicitDef() || tii_->isTriviallyReMaterializable(MI)) { + if (TID.isImplicitDef()) + return true; + if (tii_->isTriviallyReMaterializable(MI)) { 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) + continue; + if (!canFoldMemoryOperand(UseMI, li.reg) && + !isValNoAvailableAt(ImpLi, MI, UseIdx)) + return false; + } + } return true; } int FrameIdx = 0; if (!tii_->isLoadFromStackSlot(MI, FrameIdx) || - !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx)) + !mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) return false; // This is a load from fixed stack slot. It can be rematerialized unless it's @@ -662,7 +704,8 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { return false; MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); bool DefIsLoad = false; - if (!ReMatDefMI || !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) + if (!ReMatDefMI || + !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) return false; isLoad |= DefIsLoad; } @@ -692,14 +735,16 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, SmallVector FoldOps; for (unsigned i = 0, e = Ops.size(); i != e; ++i) { unsigned OpIdx = Ops[i]; + MachineOperand &MO = MI->getOperand(OpIdx); // FIXME: fold subreg use. - if (MI->getOperand(OpIdx).getSubReg()) + if (MO.getSubReg()) return false; - if (MI->getOperand(OpIdx).isDef()) + if (MO.isDef()) MRInfo |= (unsigned)VirtRegMap::isMod; else { // Filter out two-address use operand(s). - if (TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) { + if (!MO.isImplicit() && + TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) { MRInfo = VirtRegMap::isModRef; continue; } @@ -708,17 +753,17 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, FoldOps.push_back(OpIdx); } - MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(MI, FoldOps, Slot) - : tii_->foldMemoryOperand(MI, FoldOps, DefMI); + MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) + : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); if (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_) lv_->instructionChanged(MI, fmi); else - LiveVariables::transferKillDeadInfo(MI, fmi, mri_); + fmi->copyKillDeadInfo(MI, tri_); MachineBasicBlock &MBB = *MI->getParent(); - if (isSS && !mf_->getFrameInfo()->isFixedObjectIndex(Slot)) + if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); vrm.transferSpillPts(MI, fmi); vrm.transferRestorePts(MI, fmi); @@ -748,6 +793,23 @@ bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, return tii_->canFoldMemoryOperand(MI, FoldOps); } +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); +} + bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { SmallPtrSet MBBs; for (LiveInterval::Ranges::const_iterator @@ -765,19 +827,43 @@ bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { return true; } +/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of +/// interval on to-be re-materialized operands of MI) with new register. +void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, + MachineInstr *MI, unsigned NewVReg, + VirtRegMap &vrm) { + // There is an implicit use. That means one of the other operand is + // being remat'ed and the remat'ed instruction has li.reg as an + // 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()) + continue; + unsigned Reg = MO.getReg(); + if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) + continue; + if (!vrm.isReMaterialized(Reg)) + continue; + MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); + int OpIdx = ReMatMI->findRegisterUseOperandIdx(li.reg); + if (OpIdx != -1) + ReMatMI->getOperand(OpIdx).setReg(NewVReg); + } +} + /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions /// for addIntervalsForSpills to rewrite uses / defs for the given live range. bool LiveIntervals:: -rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, - unsigned id, unsigned index, unsigned end, MachineInstr *MI, +rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, + bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, unsigned Slot, int LdSlot, bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, - VirtRegMap &vrm, MachineRegisterInfo &RegInfo, + VirtRegMap &vrm, const TargetRegisterClass* rc, SmallVector &ReMatIds, - unsigned &NewVReg, bool &HasDef, bool &HasUse, const MachineLoopInfo *loopInfo, + unsigned &NewVReg, bool &HasDef, bool &HasUse, std::map &MBBVRegsMap, std::vector &NewLIs) { bool CanFold = false; @@ -788,7 +874,7 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, continue; unsigned Reg = mop.getReg(); unsigned RegI = Reg; - if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg)) + if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; if (Reg != li.reg) continue; @@ -802,6 +888,14 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, 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); + } RemoveMachineInstrFromMaps(MI); vrm.RemoveMachineInstrFromMaps(MI); MI->eraseFromParent(); @@ -839,7 +933,7 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, if (!MOj.isRegister()) continue; unsigned RegJ = MOj.getReg(); - if (RegJ == 0 || MRegisterInfo::isPhysicalRegister(RegJ)) + if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) continue; if (RegJ == RegI) { Ops.push_back(j); @@ -870,24 +964,40 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, // Create a new virtual register for the spill interval. bool CreatedNewVReg = false; if (NewVReg == 0) { - NewVReg = RegInfo.createVirtualRegister(rc); + NewVReg = mri_->createVirtualRegister(rc); vrm.grow(); CreatedNewVReg = true; } mop.setReg(NewVReg); + if (mop.isImplicit()) + rewriteImplicitOps(li, MI, NewVReg, vrm); // Reuse NewVReg for other reads. - for (unsigned j = 0, e = Ops.size(); j != e; ++j) - MI->getOperand(Ops[j]).setReg(NewVReg); + for (unsigned j = 0, e = Ops.size(); j != e; ++j) { + MachineOperand &mopj = MI->getOperand(Ops[j]); + mopj.setReg(NewVReg); + if (mopj.isImplicit()) + rewriteImplicitOps(li, MI, NewVReg, vrm); + } if (CreatedNewVReg) { if (DefIsReMat) { + 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. + unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); + LiveInterval &ImpLi = getInterval(ImpUse); + ImpLi.weight += getSpillWeight(false, true, loopDepth); + MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); + } vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); - if (ReMatIds[id] == VirtRegMap::MAX_STACK_SLOT) { + if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { // Each valnum may have its own remat id. - ReMatIds[id] = vrm.assignVirtReMatId(NewVReg); + ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); } else { - vrm.assignVirtReMatId(NewVReg, ReMatIds[id]); + vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); } if (!CanDelete || (HasUse && HasDef)) { // If this is a two-addr instruction then its use operands are @@ -938,7 +1048,7 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, } DOUT << "\t\t\t\tAdded new interval: "; - nI.print(DOUT, mri_); + nI.print(DOUT, tri_); DOUT << '\n'; } return CanFold; @@ -966,13 +1076,30 @@ static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) 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; + } +}; + void LiveIntervals:: rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, LiveInterval::Ranges::const_iterator &I, MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, unsigned Slot, int LdSlot, bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, - VirtRegMap &vrm, MachineRegisterInfo &RegInfo, + VirtRegMap &vrm, const TargetRegisterClass* rc, SmallVector &ReMatIds, const MachineLoopInfo *loopInfo, @@ -984,20 +1111,45 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, std::vector &NewLIs) { bool AllCanFold = true; unsigned NewVReg = 0; - unsigned index = getBaseIndex(I->start); + unsigned start = getBaseIndex(I->start); unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; - for (; index != end; index += InstrSlots::NUM) { - // skip deleted instructions - while (index != end && !getInstructionFromIndex(index)) - index += InstrSlots::NUM; - if (index == end) break; - MachineInstr *MI = getInstructionFromIndex(index); + // First collect all the def / use in this live range that will be rewritten. + // Make sure they are sorted according instruction index. + std::vector RewriteMIs; + for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), + re = mri_->reg_end(); ri != re; ) { + MachineInstr *MI = &(*ri); + MachineOperand &O = ri.getOperand(); + ++ri; + unsigned index = getInstructionIndex(MI); + if (index < start || index >= end) + continue; + RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); + } + std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); + + // Now rewrite the defs and uses. + for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { + RewriteInfo &rwi = RewriteMIs[i]; + ++i; + unsigned index = rwi.Index; + bool MIHasUse = rwi.HasUse; + bool MIHasDef = rwi.HasDef; + MachineInstr *MI = rwi.MI; + // If MI def and/or use the same register multiple times, then there + // are multiple entries. + while (i != e && RewriteMIs[i].MI == MI) { + assert(RewriteMIs[i].Index == index); + MIHasUse |= RewriteMIs[i].HasUse; + MIHasDef |= RewriteMIs[i].HasDef; + ++i; + } MachineBasicBlock *MBB = MI->getParent(); + unsigned MBBId = MBB->getNumber(); unsigned ThisVReg = 0; if (TrySplit) { - std::map::const_iterator NVI = - MBBVRegsMap.find(MBB->getNumber()); + std::map::const_iterator NVI = MBBVRegsMap.find(MBBId); if (NVI != MBBVRegsMap.end()) { ThisVReg = NVI->second; // One common case: @@ -1008,18 +1160,6 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, // = use // It's better to start a new interval to avoid artifically // extend the new interval. - // FIXME: Too slow? Can we fix it after rewriteInstructionsForSpills? - bool MIHasUse = false; - bool MIHasDef = false; - for (unsigned i = 0; i != MI->getNumOperands(); ++i) { - MachineOperand& mop = MI->getOperand(i); - if (!mop.isRegister() || mop.getReg() != li.reg) - continue; - if (mop.isUse()) - MIHasUse = true; - else - MIHasDef = true; - } if (MIHasDef && !MIHasUse) { MBBVRegsMap.erase(MBB->getNumber()); ThisVReg = 0; @@ -1041,11 +1181,11 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, bool HasDef = false; bool HasUse = false; - bool CanFold = rewriteInstructionForSpills(li, TrySplit, I->valno->id, + bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, index, end, MI, ReMatOrigDefMI, ReMatDefMI, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, - CanDelete, vrm, RegInfo, rc, ReMatIds, NewVReg, - HasDef, HasUse, loopInfo, MBBVRegsMap, NewLIs); + CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, + HasDef, HasUse, MBBVRegsMap, NewLIs); if (!HasDef && !HasUse) continue; @@ -1060,7 +1200,6 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, } // Keep track of the last def and first use in each MBB. - unsigned MBBId = MBB->getNumber(); if (HasDef) { if (MI != ReMatOrigDefMI || !CanDelete) { bool HasKill = false; @@ -1180,7 +1319,7 @@ addIntervalsForSpills(const LiveInterval &li, "attempt to spill already spilled interval!"); DOUT << "\t\t\t\tadding intervals for spills for interval: "; - li.print(DOUT, mri_); + li.print(DOUT, tri_); DOUT << '\n'; // Each bit specify whether it a spill is required in the MBB. @@ -1190,8 +1329,7 @@ addIntervalsForSpills(const LiveInterval &li, std::map > RestoreIdxes; std::map MBBVRegsMap; std::vector NewLIs; - MachineRegisterInfo &RegInfo = mf_->getRegInfo(); - const TargetRegisterClass* rc = RegInfo.getRegClass(li.reg); + const TargetRegisterClass* rc = mri_->getRegClass(li.reg); unsigned NumValNums = li.getNumValNums(); SmallVector ReMatDefs; @@ -1236,13 +1374,13 @@ addIntervalsForSpills(const LiveInterval &li, // Note ReMatOrigDefMI has already been deleted. rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, - false, vrm, RegInfo, rc, ReMatIds, loopInfo, + false, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, MBBVRegsMap, NewLIs); } else { rewriteInstructionsForSpills(li, false, I, NULL, 0, Slot, 0, false, false, false, - false, vrm, RegInfo, rc, ReMatIds, loopInfo, + false, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, MBBVRegsMap, NewLIs); } @@ -1310,7 +1448,7 @@ addIntervalsForSpills(const LiveInterval &li, (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad()); rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, - CanDelete, vrm, RegInfo, rc, ReMatIds, loopInfo, + CanDelete, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, MBBVRegsMap, NewLIs); } @@ -1425,6 +1563,16 @@ addIntervalsForSpills(const LiveInterval &li, if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad()) Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, Ops, isLoadSS, LdSlot, VReg); + 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. + unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); + LiveInterval &ImpLi = getInterval(ImpUse); + ImpLi.weight += getSpillWeight(false, true, loopDepth); + MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); + } } } // If folding is not possible / failed, then tell the spiller to issue a @@ -1450,8 +1598,8 @@ addIntervalsForSpills(const LiveInterval &li, MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg); assert(UseIdx != -1); - if (LastUse->getDesc().getOperandConstraint(UseIdx, TOI::TIED_TO) == - -1) { + if (LastUse->getOperand(UseIdx).isImplicit() || + LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){ LastUse->getOperand(UseIdx).setIsKill(); vrm.addKillPoint(LI->reg, LastUseIdx); }