X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=83df4d174a4cb0b0b5129fd8fa0dac2c1085a577;hb=3627e34486db088661bc7fb6c0dde6a18a543217;hp=75d5aac404856bb6586437ae557558a283125402;hpb=0cbb1164b3227f25f5e5d3681800a8e50e6b9865;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 75d5aac4048..83df4d174a4 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -19,13 +19,13 @@ #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "VirtRegMap.h" #include "llvm/Value.h" -#include "llvm/Analysis/LoopInfo.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/SSARegMap.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" @@ -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(false), 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,13 +51,13 @@ 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(); AU.addRequired(); + AU.addPreservedID(MachineLoopInfoID); + AU.addPreservedID(MachineDominatorsID); AU.addPreservedID(PHIEliminationID); AU.addRequiredID(PHIEliminationID); AU.addRequiredID(TwoAddressInstructionPassID); @@ -67,6 +65,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { } void LiveIntervals::releaseMemory() { + MBB2IdxMap.clear(); Idx2MBBMap.clear(); mi2iMap_.clear(); i2miMap_.clear(); @@ -77,32 +76,14 @@ 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; - tm_ = &fn.getTarget(); - mri_ = tm_->getRegisterInfo(); - tii_ = tm_->getInstrInfo(); - lv_ = &getAnalysis(); - allocatableRegs_ = mri_->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)); @@ -119,20 +100,127 @@ 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(); DOUT << "********** INTERVALS **********\n"; for (iterator I = begin(), E = end(); I != E; ++I) { - I->second.print(DOUT, mri_); + I->second.print(DOUT, tri_); DOUT << "\n"; } @@ -145,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, mri_); - DOUT << "\n"; + I->second.print(O, tri_); + O << "\n"; } O << "********** MACHINEINSTRS **********\n"; @@ -186,12 +274,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; } } @@ -201,8 +289,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; } @@ -214,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 @@ -222,14 +315,13 @@ 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 || + mi->getOpcode() == TargetInstrInfo::INSERT_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?"); @@ -273,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)+1, // MBB ends at -1. + ValNo); + interval.addRange(LR); + DOUT << " +" << LR; } } @@ -307,12 +396,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. @@ -324,27 +413,26 @@ 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. - if (lv_->RegisterDefIsDead(mi, interval.reg)) + if (mi->registerDefIsDead(interval.reg, tri_)) 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 @@ -360,10 +448,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+1); // odd # means phi node - DOUT << " RESULT: "; interval.print(DOUT, mri_); + VNI->hasPHIKill = true; + 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? :) @@ -371,7 +459,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 @@ -380,19 +468,19 @@ 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 || + mi->getOpcode() == TargetInstrInfo::INSERT_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); interval.addRange(LR); - interval.addKill(ValNo, killIndex+1); // odd # means phi node + interval.addKill(ValNo, killIndex); + ValNo->hasPHIKill = true; DOUT << " +" << LR; } } @@ -404,7 +492,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)); @@ -416,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; @@ -427,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: @@ -445,7 +533,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: @@ -454,7 +542,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); @@ -465,19 +553,21 @@ 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 || + 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 = mri_->getSubRegisters(reg); *AS; ++AS) - // Avoid processing some defs more than once. - if (!MI->findRegisterDefOperand(*AS)) + for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++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); } } @@ -494,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: @@ -552,7 +642,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); @@ -571,6 +661,8 @@ void LiveIntervals::computeIntervals() { MIIndex += InstrSlots::NUM; } + + if (MBB->begin() == miEnd) MIIndex += InstrSlots::NUM; // Empty MBB } } @@ -592,78 +684,215 @@ 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(); + 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; + 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, - const VNInfo *ValNo, MachineInstr *MI) { + const VNInfo *ValNo, MachineInstr *MI, + bool &isLoad) { if (DisableReMat) return false; - if (tii_->isTriviallyReMaterializable(MI)) + isLoad = false; + if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) return true; int FrameIdx = 0; - if (!tii_->isLoadFromStackSlot(MI, FrameIdx) || - !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx)) - return false; + 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); + 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; + } + } + return true; + } - // This is a load from fixed stack slot. It can be rematerialized unless it's - // re-defined by a two-address instruction. + return false; +} + +/// 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) { + isLoad = false; 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)) + // Is the def for the val# rematerializable? + if (DefIdx == ~0u) return false; + MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); + bool DefIsLoad = false; + if (!ReMatDefMI || + !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) + return false; + isLoad |= DefIsLoad; } return true; } +/// 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(); + + 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 true; + if (MO.isDef()) + MRInfo |= (unsigned)VirtRegMap::isMod; + else { + // Filter out two-address use operand(s). + if (!MO.isImplicit() && + TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) { + MRInfo = VirtRegMap::isModRef; + continue; + } + MRInfo |= (unsigned)VirtRegMap::isRef; + } + 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 index, unsigned i, - bool isSS, int slot, unsigned reg) { - MachineInstr *fmi = isSS - ? mri_->foldMemoryOperand(MI, i, slot) - : mri_->foldMemoryOperand(MI, i, DefMI); + 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_) lv_->instructionChanged(MI, fmi); else - LiveVariables::transferKillDeadInfo(MI, fmi, mri_); + fmi->copyKillDeadInfo(MI, tri_); MachineBasicBlock &MBB = *MI->getParent(); - if (isSS) { - if (!mf_->getFrameInfo()->isFixedObjectIndex(slot)) - vrm.virtFolded(reg, MI, i, fmi); - } + if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) + vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); vrm.transferSpillPts(MI, fmi); vrm.transferRestorePts(MI, fmi); + vrm.transferEmergencySpills(MI, fmi); mi2iMap_.erase(MI); - i2miMap_[index/InstrSlots::NUM] = fmi; - mi2iMap_[fmi] = index; + i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; + mi2iMap_[fmi] = InstrIdx; MI = MBB.insert(MBB.erase(MI), fmi); ++numFolds; return true; @@ -671,6 +900,25 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, return false; } +/// canFoldMemoryOperand - Returns true if the specified load / store +/// folding is possible. +bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, + 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; + if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) + return false; + + // It's only legal to remat for a use, not a def. + if (ReMat && (MRInfo & VirtRegMap::isMod)) + return false; + + return tii_->canFoldMemoryOperand(MI, FoldOps); +} + bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { SmallPtrSet MBBs; for (LiveInterval::Ranges::const_iterator @@ -688,21 +936,48 @@ 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); + MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); + if (UseMO) + UseMO->setReg(NewVReg); + } +} + /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions /// for addIntervalsForSpills to rewrite uses / defs for the given live range. -void LiveIntervals:: -rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, - unsigned id, unsigned index, unsigned end, MachineInstr *MI, +bool LiveIntervals:: +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, SSARegMap *RegMap, + VirtRegMap &vrm, const TargetRegisterClass* rc, SmallVector &ReMatIds, - unsigned &NewVReg, bool &HasDef, bool &HasUse, - const LoopInfo *loopInfo, - std::map &NewVRegs, - std::vector &NewLIs) { + const MachineLoopInfo *loopInfo, + unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, + std::map &MBBVRegsMap, + 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) { MachineOperand& mop = MI->getOperand(i); @@ -710,20 +985,20 @@ 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; - unsigned SubIdx = mop.getSubReg(); - bool isSubReg = SubIdx != 0; if (Reg != li.reg) continue; bool TryFold = !DefIsReMat; - bool FoldSS = true; + bool FoldSS = true; // Default behavior unless it's a remat. int FoldSlot = Slot; if (DefIsReMat) { // If this is the rematerializable definition MI itself and // all of its uses are rematerialized, simply delete it. if (MI == ReMatOrigDefMI && CanDelete) { + DOUT << "\t\t\t\tErasing re-materlizable def: "; + DOUT << MI << '\n'; RemoveMachineInstrFromMaps(MI); vrm.RemoveMachineInstrFromMaps(MI); MI->eraseFromParent(); @@ -732,8 +1007,7 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, // If def for this use can't be rematerialized, then try folding. // If def is rematerializable and it's a load, also try folding. - TryFold = !ReMatOrigDefMI || - (ReMatOrigDefMI && (MI == ReMatOrigDefMI || isLoad)); + TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); if (isLoad) { // Try fold loads (from stack slot, constant pool, etc.) into uses. FoldSS = isLoadSS; @@ -741,28 +1015,6 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, } } - // Do not fold load / store here if we are splitting. We'll find an - // optimal point to insert a load / store later. - if (TryFold) - TryFold = !TrySplit && NewVReg == 0; - - // FIXME: fold subreg use - if (!isSubReg && TryFold && - tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, i, FoldSS, FoldSlot, - Reg)) - // Folding the load/store can completely change the instruction in - // unpredictable ways, rescan it from the beginning. - goto RestartInstruction; - - // Create a new virtual register for the spill interval. - bool CreatedNewVReg = false; - if (NewVReg == 0) { - NewVReg = RegMap->createVirtualRegister(rc); - vrm.grow(); - CreatedNewVReg = true; - } - mop.setReg(NewVReg); - // Scan all of the operands of this instruction rewriting operands // to use NewVReg instead of li.reg as appropriate. We do this for // two reasons: @@ -774,30 +1026,82 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, // // Keep track of whether we replace a use and/or def so that we can // create the spill interval with the appropriate range. - + HasUse = mop.isUse(); HasDef = mop.isDef(); + SmallVector Ops; + Ops.push_back(i); for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { - if (!MI->getOperand(j).isRegister()) + const MachineOperand &MOj = MI->getOperand(j); + if (!MOj.isRegister()) continue; - unsigned RegJ = MI->getOperand(j).getReg(); - if (RegJ == 0 || MRegisterInfo::isPhysicalRegister(RegJ)) + unsigned RegJ = MOj.getReg(); + if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) continue; if (RegJ == RegI) { - MI->getOperand(j).setReg(NewVReg); - HasUse |= MI->getOperand(j).isUse(); - HasDef |= MI->getOperand(j).isDef(); + Ops.push_back(j); + HasUse |= MOj.isUse(); + HasDef |= MOj.isDef(); + } + } + + // 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) { + if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, + Ops, FoldSS, FoldSlot, Reg)) { + // Folding the load/store can completely change the instruction in + // unpredictable ways, rescan it from the beginning. + HasUse = false; + HasDef = false; + CanFold = false; + if (isRemoved(MI)) { + SSWeight -= Weight; + break; + } + goto RestartInstruction; + } + } else { + // We'll try to fold it later if it's profitable. + CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); } } + // Create a new virtual register for the spill interval. + bool CreatedNewVReg = false; + if (NewVReg == 0) { + 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) { + MachineOperand &mopj = MI->getOperand(Ops[j]); + mopj.setReg(NewVReg); + if (mopj.isImplicit()) + rewriteImplicitOps(li, MI, NewVReg, vrm); + } + if (CreatedNewVReg) { if (DefIsReMat) { 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 @@ -808,13 +1112,24 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, } else { vrm.assignVirt2StackSlot(NewVReg, Slot); } + } else if (HasUse && HasDef && + vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { + // If this interval hasn't been assigned a stack slot (because earlier + // def is a deleted remat def), do it now. + assert(Slot != VirtRegMap::NO_STACK_SLOT); + vrm.assignVirt2StackSlot(NewVReg, Slot); } + // Re-matting an instruction with virtual register use. Add the + // register as an implicit use on the use MI. + if (DefIsReMat && ImpUse) + MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); + // create a new register interval for this spill / remat. LiveInterval &nI = getOrCreateInterval(NewVReg); if (CreatedNewVReg) { NewLIs.push_back(&nI); - NewVRegs.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); + MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); if (TrySplit) vrm.setIsSplitFromReg(NewVReg, li.reg); } @@ -842,11 +1157,11 @@ 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; } - bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI, MachineBasicBlock *MBB, unsigned Idx) const { @@ -859,135 +1174,292 @@ bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, return false; } +/// RewriteInfo - Keep track of machine instrs that will be rewritten +/// during spilling. +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, LiveInterval::Ranges::const_iterator &I, MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, unsigned Slot, int LdSlot, bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, - VirtRegMap &vrm, SSARegMap *RegMap, + VirtRegMap &vrm, const TargetRegisterClass* rc, SmallVector &ReMatIds, - const LoopInfo *loopInfo, + const MachineLoopInfo *loopInfo, BitVector &SpillMBBs, - std::map > &SpillIdxes, + std::map > &SpillIdxes, BitVector &RestoreMBBs, - std::map > &RestoreIdxes, - std::map &NewVRegs, - std::vector &NewLIs) { + std::map > &RestoreIdxes, + std::map &MBBVRegsMap, + std::vector &NewLIs, float &SSWeight) { + bool AllCanFold = true; unsigned NewVReg = 0; - unsigned index = getBaseIndex(I->start); + unsigned start = getBaseIndex(I->start); unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; - bool TrySplitMI = TrySplit && vrm.getPreSplitReg(li.reg) == 0; - 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 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; + 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; + RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); + } + std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); + + unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; + // 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. + unsigned NumUses = MIHasUse; + while (i != e && RewriteMIs[i].MI == MI) { + assert(RewriteMIs[i].Index == index); + bool isUse = RewriteMIs[i].HasUse; + if (isUse) ++NumUses; + MIHasUse |= isUse; + MIHasDef |= RewriteMIs[i].HasDef; + ++i; + } MachineBasicBlock *MBB = MI->getParent(); - NewVReg = 0; - if (TrySplitMI) { - std::map::const_iterator NVI = - NewVRegs.find(MBB->getNumber()); - if (NVI != NewVRegs.end()) - NewVReg = NVI->second; + + if (ImpUse && MI != ReMatDefMI) { + // Re-matting an instruction with virtual register use. Update the + // register interval's spill weight to HUGE_VALF to prevent it from + // being spilled. + LiveInterval &ImpLi = getInterval(ImpUse); + ImpLi.weight = HUGE_VALF; + } + + unsigned MBBId = MBB->getNumber(); + unsigned ThisVReg = 0; + if (TrySplit) { + std::map::const_iterator NVI = MBBVRegsMap.find(MBBId); + if (NVI != MBBVRegsMap.end()) { + ThisVReg = NVI->second; + // One common case: + // x = use + // ... + // ... + // def = ... + // = use + // It's better to start a new interval to avoid artifically + // extend the new interval. + if (MIHasDef && !MIHasUse) { + MBBVRegsMap.erase(MBB->getNumber()); + ThisVReg = 0; + } + } + } + + bool IsNew = ThisVReg == 0; + if (IsNew) { + // This ends the previous live interval. If all of its def / use + // can be folded, give it a low spill weight. + if (NewVReg && TrySplit && AllCanFold) { + LiveInterval &nI = getOrCreateInterval(NewVReg); + nI.weight /= 10.0F; + } + AllCanFold = true; } - bool IsNew = NewVReg == 0; + NewVReg = ThisVReg; + bool HasDef = false; bool HasUse = false; - rewriteInstructionForSpills(li, TrySplitMI, I->valno->id, index, end, - MI, ReMatOrigDefMI, ReMatDefMI, Slot, LdSlot, - isLoad, isLoadSS, DefIsReMat, CanDelete, vrm, - RegMap, rc, ReMatIds, NewVReg, HasDef, HasUse, - loopInfo, NewVRegs, NewLIs); + 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, SSWeight); if (!HasDef && !HasUse) continue; + AllCanFold &= CanFold; + // Update weight of spill interval. LiveInterval &nI = getOrCreateInterval(NewVReg); - if (!TrySplitMI) { + if (!TrySplit) { // The spill weight is now infinity as it cannot be spilled again. nI.weight = HUGE_VALF; continue; } // Keep track of the last def and first use in each MBB. - unsigned MBBId = MBB->getNumber(); if (HasDef) { if (MI != ReMatOrigDefMI || !CanDelete) { - // If this is a two-address code, then this index probably starts a - // VNInfo so we should examine all the VNInfo's. bool HasKill = false; if (!HasUse) HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); else { - const VNInfo *VNI = NULL; - for (LiveInterval::const_vni_iterator i = li.vni_begin(), - e = li.vni_end(); i != e; ++i) - if ((*i)->def == getDefIndex(index)) { - VNI = *i; - break; - } + // If this is a two-address code, then this index starts a new VNInfo. + const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index)); if (VNI) HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); } + std::map >::iterator SII = + SpillIdxes.find(MBBId); if (!HasKill) { - std::map >::iterator SII = - SpillIdxes.find(MBBId); - if (SII == SpillIdxes.end()) - SpillIdxes[MBBId] = std::make_pair(index, true); - else if ((int)index > SII->second.first) { + if (SII == SpillIdxes.end()) { + std::vector S; + S.push_back(SRInfo(index, NewVReg, true)); + SpillIdxes.insert(std::make_pair(MBBId, S)); + } else if (SII->second.back().vreg != NewVReg) { + SII->second.push_back(SRInfo(index, NewVReg, true)); + } else if ((int)index > SII->second.back().index) { // If there is an earlier def and this is a two-address // instruction, then it's not possible to fold the store (which // would also fold the load). - SpillIdxes[MBBId] = std::make_pair(index, !HasUse); + SRInfo &Info = SII->second.back(); + Info.index = index; + Info.canFold = !HasUse; } SpillMBBs.set(MBBId); - } - } - if (!IsNew) { - // It this interval hasn't been assigned a stack slot - // (because earlier def is remat), do it now. - int SS = vrm.getStackSlot(NewVReg); - if (SS != (int)Slot) { - assert(SS == VirtRegMap::NO_STACK_SLOT); - vrm.assignVirt2StackSlot(NewVReg, Slot); + } else if (SII != SpillIdxes.end() && + SII->second.back().vreg == NewVReg && + (int)index > SII->second.back().index) { + // There is an earlier def that's not killed (must be two-address). + // The spill is no longer needed. + SII->second.pop_back(); + if (SII->second.empty()) { + SpillIdxes.erase(MBBId); + SpillMBBs.reset(MBBId); + } } } } if (HasUse) { - std::map >::iterator SII = + std::map >::iterator SII = SpillIdxes.find(MBBId); - if (SII != SpillIdxes.end() && (int)index > SII->second.first) + 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.second = false; - std::map >::iterator RII = + SII->second.back().canFold = false; + std::map >::iterator RII = RestoreIdxes.find(MBBId); - if (RII != RestoreIdxes.end()) + if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) // If we are splitting live intervals, only fold if it's the first // use and there isn't another use later in the MBB. - RII->second.second = false; + RII->second.back().canFold = false; else if (IsNew) { // Only need a reload if there isn't an earlier def / use. - RestoreIdxes[MBBId] = std::make_pair(index, true); + if (RII == RestoreIdxes.end()) { + std::vector Infos; + Infos.push_back(SRInfo(index, NewVReg, true)); + RestoreIdxes.insert(std::make_pair(MBBId, Infos)); + } else { + RII->second.push_back(SRInfo(index, NewVReg, true)); + } RestoreMBBs.set(MBBId); } } // Update spill weight. - unsigned loopDepth = loopInfo->getLoopDepth(MBB->getBasicBlock()); + unsigned loopDepth = loopInfo->getLoopDepth(MBB); nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); } + + if (NewVReg && TrySplit && AllCanFold) { + // If all of its def / use can be folded, give it a low spill weight. + LiveInterval &nI = getOrCreateInterval(NewVReg); + nI.weight /= 10.0F; + } } +bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, + BitVector &RestoreMBBs, + std::map > &RestoreIdxes) { + if (!RestoreMBBs[Id]) + return false; + std::vector &Restores = RestoreIdxes[Id]; + for (unsigned i = 0, e = Restores.size(); i != e; ++i) + if (Restores[i].index == index && + Restores[i].vreg == vr && + Restores[i].canFold) + return true; + return false; +} + +void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, + BitVector &RestoreMBBs, + std::map > &RestoreIdxes) { + if (!RestoreMBBs[Id]) + return; + std::vector &Restores = RestoreIdxes[Id]; + for (unsigned i = 0, e = Restores.size(); i != e; ++i) + if (Restores[i].index == index && Restores[i].vreg) + 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 LoopInfo *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(); @@ -996,18 +1468,20 @@ 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'; + // 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; + std::map > SpillIdxes; BitVector RestoreMBBs(mf_->getNumBlockIDs()); - std::map > RestoreIdxes; - std::map NewVRegs; + std::map > RestoreIdxes; + std::map MBBVRegsMap; std::vector NewLIs; - SSARegMap *RegMap = mf_->getSSARegMap(); - const TargetRegisterClass* rc = RegMap->getRegClass(li.reg); + const TargetRegisterClass* rc = mri_->getRegClass(li.reg); unsigned NumValNums = li.getNumValNums(); SmallVector ReMatDefs; @@ -1023,6 +1497,16 @@ addIntervalsForSpills(const LiveInterval &li, // it's also guaranteed to be a single val# / range interval. if (vrm.getPreSplitReg(li.reg)) { vrm.setIsSplitFromReg(li.reg, 0); + // Unset the split kill marker on the last use. + unsigned KillIdx = vrm.getKillPoint(li.reg); + if (KillIdx) { + MachineInstr *KillMI = getInstructionFromIndex(KillIdx); + assert(KillMI && "Last use disappeared?"); + int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); + assert(KillOp != -1 && "Last use disappeared?"); + KillMI->getOperand(KillOp).setIsKill(false); + } + vrm.removeKillPoint(li.reg); bool DefIsReMat = vrm.isReMaterialized(li.reg); Slot = vrm.getStackSlot(li.reg); assert(Slot != VirtRegMap::MAX_STACK_SLOT); @@ -1031,7 +1515,7 @@ addIntervalsForSpills(const LiveInterval &li, int LdSlot = 0; bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); bool isLoad = isLoadSS || - (DefIsReMat && (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG)); + (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad())); bool IsFirstRange = true; for (LiveInterval::Ranges::const_iterator I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { @@ -1039,20 +1523,24 @@ addIntervalsForSpills(const LiveInterval &li, // are two-address instructions that re-defined the value. Only the // first def can be rematerialized! if (IsFirstRange) { + // Note ReMatOrigDefMI has already been deleted. rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, - false, vrm, RegMap, rc, ReMatIds, loopInfo, + false, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - NewVRegs, NewLIs); + MBBVRegsMap, NewLIs, SSWeight); } else { rewriteInstructionsForSpills(li, false, I, NULL, 0, Slot, 0, false, false, false, - false, vrm, RegMap, rc, ReMatIds, loopInfo, + false, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - NewVRegs, NewLIs); + MBBVRegsMap, NewLIs, SSWeight); } IsFirstRange = false; } + + SSWeight = 0.0f; // Already accounted for when split. + handleSpilledImpDefs(li, vrm, rc, NewLIs); return NewLIs; } @@ -1072,30 +1560,23 @@ addIntervalsForSpills(const LiveInterval &li, // Is the def for the val# rematerializable? MachineInstr *ReMatDefMI = (DefIdx == ~0u) ? 0 : getInstructionFromIndex(DefIdx); - if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI)) { + bool dummy; + if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, 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. vrm must // delete these! ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone(); - vrm.setVirtIsReMaterialized(li.reg, ReMatDefMI); bool CanDelete = true; - for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { - unsigned KillIdx = VNI->kills[j]; - MachineInstr *KillMI = (KillIdx & 1) - ? NULL : getInstructionFromIndex(KillIdx); - // Kill is a phi node, not all of its uses can be rematerialized. + if (VNI->hasPHIKill) { + // A kill is a phi node, not all of its uses can be rematerialized. // It must not be deleted. - if (!KillMI) { - CanDelete = false; - // Need a stack slot if there is any live range where uses cannot be - // rematerialized. - NeedStackSlot = true; - break; - } + CanDelete = false; + // Need a stack slot if there is any live range where uses cannot be + // rematerialized. + NeedStackSlot = true; } - if (CanDelete) ReMatDelete.set(VN); } else { @@ -1119,127 +1600,280 @@ addIntervalsForSpills(const LiveInterval &li, int LdSlot = 0; bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); bool isLoad = isLoadSS || - (DefIsReMat && (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG)); + (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad()); rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, - CanDelete, vrm, RegMap, rc, ReMatIds, loopInfo, + CanDelete, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - NewVRegs, NewLIs); + MBBVRegsMap, NewLIs, SSWeight); } // Insert spills / restores if we are splitting. - if (TrySplit) { - if (NeedStackSlot) { - int Id = SpillMBBs.find_first(); - while (Id != -1) { - unsigned VReg = NewVRegs[Id]; - int index = SpillIdxes[Id].first; - bool DoFold = SpillIdxes[Id].second; + 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; + unsigned VReg = spills[i].vreg; + LiveInterval &nI = getOrCreateInterval(VReg); bool isReMat = vrm.isReMaterialized(VReg); MachineInstr *MI = getInstructionFromIndex(index); - int OpIdx = -1; - bool FoldedLoad = false; - if (DoFold) { + bool CanFold = false; + bool FoundUse = false; + Ops.clear(); + if (spills[i].canFold) { + CanFold = true; for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { MachineOperand &MO = MI->getOperand(j); if (!MO.isRegister() || MO.getReg() != VReg) continue; - if (MO.isUse()) { - // Can't fold if it's two-address code and the use isn't the - // first and only use. - // If there are more than one uses, a load is still needed. - if (!isReMat && !FoldedLoad && - RestoreMBBs[Id] && RestoreIdxes[Id].first == index && - RestoreIdxes[Id].second) { - FoldedLoad = true; - continue; - } else { - OpIdx = -1; - break; - } + + Ops.push_back(j); + if (MO.isDef()) + continue; + if (isReMat || + (!FoundUse && !alsoFoldARestore(Id, index, VReg, + RestoreMBBs, RestoreIdxes))) { + // MI has two-address uses of the same register. If the use + // isn't the first and only use in the BB, then we can't fold + // it. FIXME: Move this to rewriteInstructionsForSpills. + CanFold = false; + break; } - OpIdx = (int)j; + FoundUse = true; } } // Fold the store into the def if possible. - if (OpIdx == -1) - DoFold = false; - if (DoFold) { - if (tryFoldMemoryOperand(MI, vrm, NULL, index, OpIdx, true, Slot, - VReg)) { - if (FoldedLoad) { - // Folded a two-address instruction, do not issue a load. - RestoreMBBs.reset(Id); - RestoreIdxes.erase(Id); + bool Folded = false; + if (CanFold && !Ops.empty()) { + if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ + Folded = true; + if (FoundUse > 0) { + // Also folded uses, do not issue a load. + eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); + nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); } - } else - DoFold = false; + nI.removeRange(getDefIndex(index), getStoreIndex(index)); + } + } + + // Otherwise tell the spiller to issue a spill. + if (!Folded) { + LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; + bool isKill = LR->end == getStoreIndex(index); + if (!MI->registerDefIsDead(nI.reg)) + // No need to spill a dead def. + vrm.addSpillPoint(VReg, isKill, MI); + if (isKill) + AddedKill.insert(&nI); } - // Else tell the spiller to issue a store for us. - if (!DoFold) - vrm.addSpillPoint(VReg, MI); - Id = SpillMBBs.find_next(Id); + // Update spill slot weight. + if (!isReMat) + SSWeight += getSpillWeight(true, false, loopDepth); } + Id = SpillMBBs.find_next(Id); } + } - int Id = RestoreMBBs.find_first(); - while (Id != -1) { - unsigned VReg = NewVRegs[Id]; - int index = RestoreIdxes[Id].first; - bool DoFold = RestoreIdxes[Id].second; + 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; + if (index == -1) + continue; + unsigned VReg = restores[i].vreg; + LiveInterval &nI = getOrCreateInterval(VReg); + bool isReMat = vrm.isReMaterialized(VReg); MachineInstr *MI = getInstructionFromIndex(index); - int OpIdx = -1; - if (DoFold) { + bool CanFold = false; + Ops.clear(); + if (restores[i].canFold) { + CanFold = true; for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { MachineOperand &MO = MI->getOperand(j); if (!MO.isRegister() || MO.getReg() != VReg) continue; + if (MO.isDef()) { - // Can't fold if it's two-address code. - OpIdx = -1; - break; - } - if (OpIdx != -1) { - // Multiple uses, do not fold! - OpIdx = -1; + // If this restore were to be folded, it would have been folded + // already. + CanFold = false; break; } - OpIdx = (int)j; + Ops.push_back(j); } } // Fold the load into the use if possible. - if (OpIdx == -1) - DoFold = false; - if (DoFold) { - if (vrm.isReMaterialized(VReg)) { + bool Folded = false; + if (CanFold && !Ops.empty()) { + if (!isReMat) + Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); + else { MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); int LdSlot = 0; bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); // If the rematerializable def is a load, also try to fold it. - if (isLoadSS || - (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG)) - DoFold = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, OpIdx, - isLoadSS, LdSlot, VReg); - else - DoFold = false; - } else - DoFold = tryFoldMemoryOperand(MI, vrm, NULL, index, OpIdx, - true, Slot, VReg); + 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 to HUGE_VALF to prevent it from being + // spilled. + LiveInterval &ImpLi = getInterval(ImpUse); + ImpLi.weight = HUGE_VALF; + MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); + } + } } // If folding is not possible / failed, then tell the spiller to issue a // load / rematerialization for us. - if (!DoFold) + if (Folded) + nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); + else vrm.addRestorePoint(VReg, MI); - Id = RestoreMBBs.find_next(Id); + + // Update spill slot weight. + if (!isReMat) + SSWeight += getSpillWeight(false, true, loopDepth); } + Id = RestoreMBBs.find_next(Id); } - // Finalize spill weights. - if (TrySplit) - for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) - NewLIs[i]->weight /= NewLIs[i]->getSize(); + // Finalize intervals: add kills, finalize spill weights, and filter out + // dead intervals. + std::vector RetNewLIs; + for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { + LiveInterval *LI = NewLIs[i]; + if (!LI->empty()) { + LI->weight /= LI->getSize(); + if (!AddedKill.count(LI)) { + LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; + unsigned LastUseIdx = getBaseIndex(LR->end); + MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); + int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); + assert(UseIdx != -1); + if (LastUse->getOperand(UseIdx).isImplicit() || + LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){ + LastUse->getOperand(UseIdx).setIsKill(); + vrm.addKillPoint(LI->reg, LastUseIdx); + } + } + RetNewLIs.push_back(LI); + } + } - return NewLIs; + 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; }