X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=d6c8a6561e4f85c680c201bca826a46e817b8fee;hb=f9410141f703f4e8a6aba717617ef958249f6d13;hp=d710d48034b6c38f5f2c542a16b34a754c793200;hpb=6130f66eaae89f8878590796977678afa8448926;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index d710d48034b..d6c8a6561e4 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -19,15 +19,18 @@ #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "VirtRegMap.h" #include "llvm/Value.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/PseudoSourceValue.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetOptions.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/ADT/Statistic.h" @@ -36,16 +39,19 @@ #include using namespace llvm; -namespace { - // Hidden options for help debugging. - cl::opt DisableReMat("disable-rematerialization", - cl::init(false), cl::Hidden); - - cl::opt SplitAtBB("split-intervals-at-bb", - cl::init(true), cl::Hidden); - cl::opt SplitLimit("split-limit", - cl::init(-1), cl::Hidden); -} +// Hidden options for help debugging. +static cl::opt DisableReMat("disable-rematerialization", + cl::init(false), cl::Hidden); + +static cl::opt SplitAtBB("split-intervals-at-bb", + cl::init(true), cl::Hidden); +static cl::opt SplitLimit("split-limit", + cl::init(-1), cl::Hidden); + +static cl::opt EnableAggressiveRemat("aggressive-remat", cl::Hidden); + +static cl::opt EnableFastSpilling("fast-spill", + cl::init(false), cl::Hidden); STATISTIC(numIntervals, "Number of original intervals"); STATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); @@ -53,43 +59,56 @@ 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.addRequired(); + AU.addPreserved(); AU.addPreserved(); AU.addRequired(); AU.addPreservedID(MachineLoopInfoID); AU.addPreservedID(MachineDominatorsID); - AU.addPreservedID(PHIEliminationID); - AU.addRequiredID(PHIEliminationID); + + if (!StrongPHIElim) { + AU.addPreservedID(PHIEliminationID); + AU.addRequiredID(PHIEliminationID); + } + AU.addRequiredID(TwoAddressInstructionPassID); MachineFunctionPass::getAnalysisUsage(AU); } void LiveIntervals::releaseMemory() { + // Free the live intervals themselves. + for (DenseMap::iterator I = r2iMap_.begin(), + E = r2iMap_.end(); I != E; ++I) + delete I->second; + + MBB2IdxMap.clear(); Idx2MBBMap.clear(); mi2iMap_.clear(); i2miMap_.clear(); r2iMap_.clear(); // Release VNInfo memroy regions after all VNInfo objects are dtor'd. VNInfoAllocator.Reset(); - for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i) - delete ClonedMIs[i]; + while (!ClonedMIs.empty()) { + MachineInstr *MI = ClonedMIs.back(); + ClonedMIs.pop_back(); + mf_->DeleteMachineInstr(MI); + } } -/// runOnMachineFunction - Register allocate the whole function -/// -bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { - mf_ = &fn; - mri_ = &mf_->getRegInfo(); - tm_ = &fn.getTarget(); - tri_ = tm_->getRegisterInfo(); - tii_ = tm_->getInstrInfo(); - lv_ = &getAnalysis(); - allocatableRegs_ = tri_->getAllocatableSet(fn); - +void LiveIntervals::computeNumbering() { + Index2MiMap OldI2MI = i2miMap_; + std::vector OldI2MBB = Idx2MBBMap; + + Idx2MBBMap.clear(); + MBB2IdxMap.clear(); + mi2iMap_.clear(); + i2miMap_.clear(); + + FunctionSize = 0; + // Number MachineInstrs and MachineBasicBlocks. // Initialize MBB indexes to a sentinal. MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); @@ -99,27 +118,151 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { MBB != E; ++MBB) { unsigned StartIdx = MIIndex; + // Insert an empty slot at the beginning of each block. + MIIndex += InstrSlots::NUM; + i2miMap_.push_back(0); + for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) { bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; assert(inserted && "multiple MachineInstr -> index mappings"); i2miMap_.push_back(I); MIIndex += InstrSlots::NUM; + FunctionSize++; + + // Insert max(1, numdefs) empty slots after every instruction. + unsigned Slots = I->getDesc().getNumDefs(); + if (Slots == 0) + Slots = 1; + MIIndex += InstrSlots::NUM * Slots; + while (Slots--) + i2miMap_.push_back(0); } - + // 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 OI = begin(), OE = end(); OI != OE; ++OI) { + for (LiveInterval::iterator LI = OI->second->begin(), + LE = OI->second->end(); LI != LE; ++LI) { + + // Remap the start index of the live range to the corresponding new + // number, or our best guess at what it _should_ correspond to if the + // original instruction has been erased. This is either the following + // instruction or its predecessor. + unsigned index = LI->start / InstrSlots::NUM; + unsigned offset = LI->start % InstrSlots::NUM; + if (offset == InstrSlots::LOAD) { + std::vector::const_iterator I = + std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start); + // Take the pair containing the index + std::vector::const_iterator J = + (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; + + LI->start = getMBBStartIdx(J->second); + } else { + LI->start = mi2iMap_[OldI2MI[index]] + offset; + } + + // Remap the ending index in the same way that we remapped the start, + // except for the final step where we always map to the immediately + // following instruction. + index = (LI->end - 1) / InstrSlots::NUM; + offset = LI->end % InstrSlots::NUM; + if (offset == InstrSlots::LOAD) { + // VReg dies at end of block. + std::vector::const_iterator I = + std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end); + --I; + + LI->end = getMBBEndIdx(I->second) + 1; + } else { + unsigned idx = index; + while (index < OldI2MI.size() && !OldI2MI[index]) ++index; + + if (index != OldI2MI.size()) + LI->end = mi2iMap_[OldI2MI[index]] + (idx == index ? offset : 0); + else + LI->end = InstrSlots::NUM * i2miMap_.size(); + } + } + + for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(), + VNE = OI->second->vni_end(); VNI != VNE; ++VNI) { + VNInfo* vni = *VNI; + + // Remap the VNInfo def index, which works the same as the + // start indices above. VN's with special sentinel defs + // don't need to be remapped. + if (vni->def != ~0U && vni->def != ~1U) { + unsigned index = vni->def / InstrSlots::NUM; + unsigned offset = vni->def % InstrSlots::NUM; + if (offset == InstrSlots::LOAD) { + std::vector::const_iterator I = + std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def); + // Take the pair containing the index + std::vector::const_iterator J = + (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; + + vni->def = getMBBStartIdx(J->second); + } else { + vni->def = mi2iMap_[OldI2MI[index]] + offset; + } + } + + // Remap the VNInfo kill indices, which works the same as + // the end indices above. + for (size_t i = 0; i < vni->kills.size(); ++i) { + // PHI kills don't need to be remapped. + if (!vni->kills[i]) continue; + + unsigned index = (vni->kills[i]-1) / InstrSlots::NUM; + unsigned offset = vni->kills[i] % InstrSlots::NUM; + if (offset == InstrSlots::LOAD) { + std::vector::const_iterator I = + std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); + --I; + + vni->kills[i] = getMBBEndIdx(I->second); + } else { + unsigned idx = index; + while (index < OldI2MI.size() && !OldI2MI[index]) ++index; + + if (index != OldI2MI.size()) + vni->kills[i] = mi2iMap_[OldI2MI[index]] + + (idx == index ? offset : 0); + else + vni->kills[i] = InstrSlots::NUM * i2miMap_.size(); + } + } + } + } +} +/// runOnMachineFunction - Register allocate the whole function +/// +bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { + mf_ = &fn; + mri_ = &mf_->getRegInfo(); + tm_ = &fn.getTarget(); + tri_ = tm_->getRegisterInfo(); + tii_ = tm_->getInstrInfo(); + aa_ = &getAnalysis(); + 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, tri_); + I->second->print(DOUT, tri_); DOUT << "\n"; } @@ -132,8 +275,8 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { void LiveIntervals::print(std::ostream &O, const Module* ) const { O << "********** INTERVALS **********\n"; for (const_iterator I = begin(), E = end(); I != E; ++I) { - I->second.print(DOUT, tri_); - DOUT << "\n"; + I->second->print(O, tri_); + O << "\n"; } O << "********** MACHINEINSTRS **********\n"; @@ -168,7 +311,7 @@ bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, continue; for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& mop = MI->getOperand(i); - if (!mop.isRegister()) + if (!mop.isReg()) continue; unsigned PhysReg = mop.getReg(); if (PhysReg == 0 || PhysReg == li.reg) @@ -196,11 +339,17 @@ void LiveIntervals::printRegName(unsigned reg) const { void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, MachineBasicBlock::iterator mi, - unsigned MIIdx, + unsigned MIIdx, MachineOperand& MO, + unsigned MOIdx, LiveInterval &interval) { 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 @@ -208,10 +357,14 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, if (interval.empty()) { // Get the Idx of the defining instructions. unsigned defIndex = getDefIndex(MIIdx); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + defIndex = getUseIndex(MIIdx); VNInfo *ValNo; MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || + mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || tii_->isMoveInstr(*mi, SrcReg, DstReg)) CopyMI = mi; ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); @@ -247,9 +400,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // of the defining block, potentially live across some blocks, then is // live into some number of blocks, but gets killed. Start by adding a // range that goes from this definition to the end of the defining block. - LiveRange NewLR(defIndex, - getInstructionIndex(&mbb->back()) + InstrSlots::NUM, - ValNo); + LiveRange NewLR(defIndex, getMBBEndIdx(mbb)+1, ValNo); DOUT << " +" << NewLR; interval.addRange(NewLR); @@ -258,14 +409,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; } } @@ -286,7 +434,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // must be due to phi elimination or two addr elimination. If this is // the result of two address elimination, then the vreg is one of the // def-and-use register operand. - if (mi->isRegReDefinedByTwoAddr(interval.reg)) { + if (mi->isRegReDefinedByTwoAddr(interval.reg, MOIdx)) { // If this is a two-address definition, then we have already processed // the live range. The only problem is that we didn't realize there // are actually two values in the live interval. Because of this we @@ -295,6 +443,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, assert(interval.containsOneValue()); unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); unsigned RedefIndex = getDefIndex(MIIdx); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + RedefIndex = getUseIndex(MIIdx); const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); VNInfo *OldValNo = OldLR->valno; @@ -324,7 +475,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // If this redefinition is dead, we need to add a dummy unit live // range covering the def slot. - if (mi->registerDefIsDead(interval.reg, tri_)) + if (MO.isDead()) interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); DOUT << " RESULT: "; @@ -362,16 +513,20 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // live until the end of the block. We've already taken care of the // rest of the live range. unsigned defIndex = getDefIndex(MIIdx); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + defIndex = getUseIndex(MIIdx); VNInfo *ValNo; MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || + mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || tii_->isMoveInstr(*mi, SrcReg, DstReg)) CopyMI = mi; ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); - unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; + unsigned killIndex = getMBBEndIdx(mbb) + 1; LiveRange LR(defIndex, killIndex, ValNo); interval.addRange(LR); interval.addKill(ValNo, killIndex); @@ -386,6 +541,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator mi, unsigned MIIdx, + MachineOperand& MO, LiveInterval &interval, MachineInstr *CopyMI) { // A physical register cannot be live across basic block, so its @@ -394,22 +550,28 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, unsigned baseIndex = MIIdx; unsigned start = getDefIndex(baseIndex); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + start = getUseIndex(MIIdx); unsigned end = start; // If it is not used after definition, it is considered dead at // the instruction defining it. Hence its interval is: // [defSlot(def), defSlot(def)+1) - if (mi->registerDefIsDead(interval.reg, tri_)) { + if (MO.isDead()) { DOUT << " dead"; - end = getDefIndex(start) + 1; + end = start + 1; goto exit; } // If it is not dead on definition, it must be killed by a // subsequent instruction. Hence its interval is: // [defSlot(def), useSlot(kill)+1) + baseIndex += InstrSlots::NUM; while (++mi != MBB->end()) { - baseIndex += InstrSlots::NUM; + while (baseIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(baseIndex) == 0) + baseIndex += InstrSlots::NUM; if (mi->killsRegister(interval.reg, tri_)) { DOUT << " killed"; end = getUseIndex(baseIndex) + 1; @@ -420,16 +582,18 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // it. Hence its interval is: // [defSlot(def), defSlot(def)+1) DOUT << " dead"; - end = getDefIndex(start) + 1; + end = start + 1; goto exit; } + + baseIndex += InstrSlots::NUM; } // The only case we should have a dead physreg here without a killing or // instruction where we know it's dead is if it is live-in to the function // and never used. assert(!CopyMI && "physreg was not killed in defining block!"); - end = getDefIndex(start) + 1; // It's dead. + end = start + 1; exit: assert(start < end && "did not find end of interval?"); @@ -447,22 +611,27 @@ exit: void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI, unsigned MIIdx, - unsigned reg) { - if (TargetRegisterInfo::isVirtualRegister(reg)) - handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); - else if (allocatableRegs_[reg]) { + MachineOperand& MO, + unsigned MOIdx) { + if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) + handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, + getOrCreateInterval(MO.getReg())); + else if (allocatableRegs_[MO.getReg()]) { MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || + MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || tii_->isMoveInstr(*MI, SrcReg, DstReg)) CopyMI = MI; - handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI); + handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, + getOrCreateInterval(MO.getReg()), CopyMI); // Def of a register also defines its sub-registers. - for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS) + for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *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); + handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, + getOrCreateInterval(*AS), 0); } } @@ -476,7 +645,11 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, MachineBasicBlock::iterator mi = MBB->begin(); unsigned baseIndex = MIIdx; unsigned start = baseIndex; - unsigned end = start; + while (baseIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(baseIndex) == 0) + baseIndex += InstrSlots::NUM; + unsigned end = baseIndex; + while (mi != MBB->end()) { if (mi->killsRegister(interval.reg, tri_)) { DOUT << " killed"; @@ -493,6 +666,9 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, } baseIndex += InstrSlots::NUM; + while (baseIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(baseIndex) == 0) + baseIndex += InstrSlots::NUM; ++mi; } @@ -508,7 +684,7 @@ exit: } } - LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); + LiveRange LR(start, end, interval.getNextValue(~0U, 0, VNInfoAllocator)); interval.addRange(LR); interval.addKill(LR.valno, end); DOUT << " +" << LR << '\n'; @@ -518,15 +694,17 @@ exit: /// registers. for some ordering of the machine instructions [1,N] a /// live interval is an interval [i, j) where 1 <= i <= j < N for /// which a variable is live -void LiveIntervals::computeIntervals() { +void LiveIntervals::computeIntervals() { + DOUT << "********** COMPUTING LIVE INTERVALS **********\n" << "********** Function: " << ((Value*)mf_->getFunction())->getName() << '\n'; - // Track the index of the current machine instr. - unsigned MIIndex = 0; + for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); MBBI != E; ++MBBI) { MachineBasicBlock *MBB = MBBI; + // Track the index of the current machine instr. + unsigned MIIndex = getMBBStartIdx(MBB); DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); @@ -542,6 +720,11 @@ void LiveIntervals::computeIntervals() { true); } + // Skip over empty initial indices. + while (MIIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(MIIndex) == 0) + MIIndex += InstrSlots::NUM; + for (; MI != miEnd; ++MI) { DOUT << MIIndex << "\t" << *MI; @@ -549,11 +732,21 @@ void LiveIntervals::computeIntervals() { for (int i = MI->getNumOperands() - 1; i >= 0; --i) { MachineOperand &MO = MI->getOperand(i); // handle register defs - build intervals - if (MO.isRegister() && MO.getReg() && MO.isDef()) - handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); + if (MO.isReg() && MO.getReg() && MO.isDef()) { + handleRegisterDef(MBB, MI, MIIndex, MO, i); + } } + + // Skip over the empty slots after each instruction. + unsigned Slots = MI->getDesc().getNumDefs(); + if (Slots == 0) + Slots = 1; + MIIndex += InstrSlots::NUM * Slots; - MIIndex += InstrSlots::NUM; + // Skip over empty indices. + while (MIIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(MIIndex) == 0) + MIIndex += InstrSlots::NUM; } } } @@ -574,11 +767,10 @@ bool LiveIntervals::findLiveInMBBs(const LiveRange &LR, return ResVal; } - -LiveInterval LiveIntervals::createInterval(unsigned reg) { +LiveInterval* LiveIntervals::createInterval(unsigned reg) { float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; - return LiveInterval(reg, Weight); + return new LiveInterval(reg, Weight); } /// getVNInfoSourceReg - Helper function that parses the specified VNInfo @@ -589,6 +781,8 @@ unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) return VNI->copy->getOperand(1).getReg(); + if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG) + return VNI->copy->getOperand(2).getReg(); unsigned SrcReg, DstReg; if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg)) return SrcReg; @@ -608,7 +802,7 @@ unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, unsigned RegOp = 0; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (!MO.isRegister() || !MO.isUse()) + if (!MO.isReg() || !MO.isUse()) continue; unsigned Reg = MO.getReg(); if (Reg == 0 || Reg == li.reg) @@ -617,7 +811,9 @@ unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, assert(!RegOp && "Can't rematerialize instruction with multiple register operand!"); RegOp = MO.getReg(); +#ifndef NDEBUG break; +#endif } return RegOp; } @@ -636,13 +832,12 @@ bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, /// val# of the specified interval is re-materializable. bool LiveIntervals::isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, MachineInstr *MI, + SmallVectorImpl &SpillIs, bool &isLoad) { if (DisableReMat) return false; - isLoad = false; - const TargetInstrDesc &TID = MI->getDesc(); - if (TID.isImplicitDef()) + if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) return true; int FrameIdx = 0; @@ -654,31 +849,110 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, // This is a load from fixed stack slot. It can be rematerialized. return true; - if (tii_->isTriviallyReMaterializable(MI)) { - isLoad = TID.isSimpleLoad(); - - unsigned ImpUse = getReMatImplicitUse(li, MI); - if (ImpUse) { - const LiveInterval &ImpLi = getInterval(ImpUse); - for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), - re = mri_->use_end(); ri != re; ++ri) { - MachineInstr *UseMI = &*ri; - unsigned UseIdx = getInstructionIndex(UseMI); - if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) + // If the target-specific rules don't identify an instruction as + // being trivially rematerializable, use some target-independent + // rules. + if (!MI->getDesc().isRematerializable() || + !tii_->isTriviallyReMaterializable(MI)) { + if (!EnableAggressiveRemat) + return false; + + // If the instruction accesses memory but the memoperands have been lost, + // we can't analyze it. + const TargetInstrDesc &TID = MI->getDesc(); + if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty()) + return false; + + // Avoid instructions obviously unsafe for remat. + if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable()) + return false; + + // If the instruction accesses memory and the memory could be non-constant, + // assume the instruction is not rematerializable. + for (std::list::const_iterator + I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I){ + const MachineMemOperand &MMO = *I; + if (MMO.isVolatile() || MMO.isStore()) + return false; + const Value *V = MMO.getValue(); + if (!V) + return false; + if (const PseudoSourceValue *PSV = dyn_cast(V)) { + if (!PSV->isConstant(mf_->getFrameInfo())) + return false; + } else if (!aa_->pointsToConstantMemory(V)) + return false; + } + + // If any of the registers accessed are non-constant, conservatively assume + // the instruction is not rematerializable. + unsigned ImpUse = 0; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (MO.isReg()) { + unsigned Reg = MO.getReg(); + if (Reg == 0) continue; - if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) + if (TargetRegisterInfo::isPhysicalRegister(Reg)) + return false; + + // Only allow one def, and that in the first operand. + if (MO.isDef() != (i == 0)) + return false; + + // Only allow constant-valued registers. + bool IsLiveIn = mri_->isLiveIn(Reg); + MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg), + E = mri_->def_end(); + + // For the def, it should be the only def. + if (MO.isDef() && (next(I) != E || IsLiveIn)) return false; + + if (MO.isUse()) { + // Only allow one use other register use, as that's all the + // remat mechanisms support currently. + if (Reg != li.reg) { + if (ImpUse == 0) + ImpUse = Reg; + else if (Reg != ImpUse) + return false; + } + // For uses, there should be only one associate def. + if (I != E && (next(I) != E || IsLiveIn)) + return false; + } } } - return true; } - return false; + unsigned ImpUse = getReMatImplicitUse(li, MI); + if (ImpUse) { + const LiveInterval &ImpLi = getInterval(ImpUse); + for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), + re = mri_->use_end(); ri != re; ++ri) { + MachineInstr *UseMI = &*ri; + unsigned UseIdx = getInstructionIndex(UseMI); + if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) + continue; + if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) + return false; + } + + // If a register operand of the re-materialized instruction is going to + // be spilled next, then it's not legal to re-materialize this instruction. + for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) + if (ImpUse == SpillIs[i]->reg) + return false; + } + return true; } /// isReMaterializable - Returns true if every definition of MI of every /// val# of the specified interval is re-materializable. -bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { +bool LiveIntervals::isReMaterializable(const LiveInterval &li, + SmallVectorImpl &SpillIs, + bool &isLoad) { isLoad = false; for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); i != e; ++i) { @@ -692,7 +966,7 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); bool DefIsLoad = false; if (!ReMatDefMI || - !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) + !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) return false; isLoad |= DefIsLoad; } @@ -741,9 +1015,8 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, unsigned InstrIdx, SmallVector &Ops, bool isSS, int Slot, unsigned Reg) { - const TargetInstrDesc &TID = MI->getDesc(); // If it is an implicit def instruction, just delete it. - if (TID.isImplicitDef()) { + if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { RemoveMachineInstrFromMaps(MI); vrm.RemoveMachineInstrFromMaps(MI); MI->eraseFromParent(); @@ -758,8 +1031,9 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) return false; - // Can't fold a load from fixed stack slot into a two address instruction. - if (isSS && DefMI && (MRInfo & VirtRegMap::isMod)) + // 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) @@ -770,15 +1044,12 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, // 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 - fmi->copyKillDeadInfo(MI, tri_); MachineBasicBlock &MBB = *MI->getParent(); 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_[InstrIdx /InstrSlots::NUM] = fmi; mi2iMap_[fmi] = InstrIdx; @@ -793,7 +1064,7 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, /// folding is possible. bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, SmallVector &Ops, - bool ReMatLoad) const { + bool ReMat) const { // Filter the list of operand indexes that are to be folded. Abort if // any operand will prevent folding. unsigned MRInfo = 0; @@ -801,8 +1072,8 @@ bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) return false; - // Can't fold a remat'ed load into a two address instruction. - if (ReMatLoad && (MRInfo & VirtRegMap::isMod)) + // It's only legal to remat for a use, not a def. + if (ReMat && (MRInfo & VirtRegMap::isMod)) return false; return tii_->canFoldMemoryOperand(MI, FoldOps); @@ -835,7 +1106,7 @@ void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, // use operand. Make sure we rewrite that as well. for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (!MO.isRegister()) + if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) @@ -862,13 +1133,15 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, SmallVector &ReMatIds, const MachineLoopInfo *loopInfo, unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, - std::map &MBBVRegsMap, - std::vector &NewLIs) { + DenseMap &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); - if (!mop.isRegister()) + if (!mop.isReg()) continue; unsigned Reg = mop.getReg(); unsigned RegI = Reg; @@ -886,15 +1159,6 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, if (MI == ReMatOrigDefMI && CanDelete) { DOUT << "\t\t\t\tErasing re-materlizable def: "; DOUT << MI << '\n'; - unsigned ImpUse = getReMatImplicitUse(li, MI); - if (ImpUse) { - // To be deleted MI has a virtual register operand, update the - // spill weight of the register interval. - unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); - LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight -= - getSpillWeight(false, true, loopDepth) / ImpLi.getSize(); - } RemoveMachineInstrFromMaps(MI); vrm.RemoveMachineInstrFromMaps(MI); MI->eraseFromParent(); @@ -929,7 +1193,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, Ops.push_back(i); for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { const MachineOperand &MOj = MI->getOperand(j); - if (!MOj.isRegister()) + if (!MOj.isReg()) continue; unsigned RegJ = MOj.getReg(); if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) @@ -941,7 +1205,26 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, } } - if (TryFold) { + if (HasUse && !li.liveAt(getUseIndex(index))) + // Must be defined by an implicit def. It should not be spilled. Note, + // this is for correctness reason. e.g. + // 8 %reg1024 = IMPLICIT_DEF + // 12 %reg1024 = INSERT_SUBREG %reg1024, %reg1025, 2 + // The live range [12, 14) are not part of the r1024 live interval since + // it's defined by an implicit def. It will not conflicts with live + // interval of r1025. Now suppose both registers are spilled, you can + // easily see a situation where both registers are reloaded before + // the INSERT_SUBREG and both target registers that would overlap. + HasUse = false; + + // 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) { @@ -952,13 +1235,17 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, HasUse = false; HasDef = false; CanFold = false; + if (isRemoved(MI)) { + SSWeight -= Weight; + break; + } goto RestartInstruction; } } else { - CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat && isLoad); + // We'll try to fold it later if it's profitable. + CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); } - } else - CanFold = false; + } // Create a new virtual register for the spill interval. bool CreatedNewVReg = false; @@ -1059,33 +1346,24 @@ bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, return false; } -static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) { - const VNInfo *VNI = NULL; - for (LiveInterval::const_vni_iterator i = li.vni_begin(), - e = li.vni_end(); i != e; ++i) - if ((*i)->def == DefIdx) { - VNI = *i; - break; - } - return VNI; -} - /// RewriteInfo - Keep track of machine instrs that will be rewritten /// during spilling. -struct RewriteInfo { - unsigned Index; - MachineInstr *MI; - bool HasUse; - bool HasDef; - RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) - : Index(i), MI(mi), HasUse(u), HasDef(d) {} -}; - -struct RewriteInfoCompare { - bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { - return LHS.Index < RHS.Index; - } -}; +namespace { + struct RewriteInfo { + unsigned Index; + MachineInstr *MI; + bool HasUse; + bool HasDef; + RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) + : Index(i), MI(mi), HasUse(u), HasDef(d) {} + }; + + struct RewriteInfoCompare { + bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { + return LHS.Index < RHS.Index; + } + }; +} void LiveIntervals:: rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, @@ -1098,27 +1376,39 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, SmallVector &ReMatIds, const MachineLoopInfo *loopInfo, BitVector &SpillMBBs, - std::map > &SpillIdxes, + DenseMap > &SpillIdxes, BitVector &RestoreMBBs, - std::map > &RestoreIdxes, - std::map &MBBVRegsMap, - std::vector &NewLIs) { + DenseMap > &RestoreIdxes, + DenseMap &MBBVRegsMap, + std::vector &NewLIs, float &SSWeight) { bool AllCanFold = true; unsigned NewVReg = 0; unsigned start = getBaseIndex(I->start); unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; // First collect all the def / use in this live range that will be rewritten. - // Make sure they are sorted according instruction index. + // Make sure they are sorted according to instruction index. std::vector RewriteMIs; for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), re = mri_->reg_end(); ri != re; ) { - MachineInstr *MI = &(*ri); + MachineInstr *MI = &*ri; MachineOperand &O = ri.getOperand(); ++ri; + assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); unsigned index = getInstructionIndex(MI); if (index < start || index >= end) continue; + if (O.isUse() && !li.liveAt(getUseIndex(index))) + // Must be defined by an implicit def. It should not be spilled. Note, + // this is for correctness reason. e.g. + // 8 %reg1024 = IMPLICIT_DEF + // 12 %reg1024 = INSERT_SUBREG %reg1024, %reg1025, 2 + // The live range [12, 14) are not part of the r1024 live interval since + // it's defined by an implicit def. It will not conflicts with live + // interval of r1025. Now suppose both registers are spilled, you can + // easily see a situation where both registers are reloaded before + // the INSERT_SUBREG and both target registers that would overlap. + continue; RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); } std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); @@ -1147,17 +1437,16 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, if (ImpUse && MI != ReMatDefMI) { // Re-matting an instruction with virtual register use. Update the - // register interval's spill weight. - unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); + // register interval's spill weight to HUGE_VALF to prevent it from + // being spilled. LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight += - getSpillWeight(false, true, loopDepth) * NumUses / ImpLi.getSize(); + ImpLi.weight = HUGE_VALF; } unsigned MBBId = MBB->getNumber(); unsigned ThisVReg = 0; if (TrySplit) { - std::map::const_iterator NVI = MBBVRegsMap.find(MBBId); + DenseMap::iterator NVI = MBBVRegsMap.find(MBBId); if (NVI != MBBVRegsMap.end()) { ThisVReg = NVI->second; // One common case: @@ -1190,10 +1479,10 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, bool HasDef = false; bool HasUse = false; bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, - index, end, MI, ReMatOrigDefMI, ReMatDefMI, - Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, - CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, - ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); + index, end, MI, ReMatOrigDefMI, ReMatDefMI, + Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, + CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, + ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs, SSWeight); if (!HasDef && !HasUse) continue; @@ -1215,11 +1504,11 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); else { // If this is a two-address code, then this index starts a new VNInfo. - const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index)); + const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index)); if (VNI) HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); } - std::map >::iterator SII = + DenseMap >::iterator SII = SpillIdxes.find(MBBId); if (!HasKill) { if (SII == SpillIdxes.end()) { @@ -1252,14 +1541,14 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, } if (HasUse) { - std::map >::iterator SII = + DenseMap >::iterator SII = SpillIdxes.find(MBBId); if (SII != SpillIdxes.end() && SII->second.back().vreg == NewVReg && (int)index > SII->second.back().index) // Use(s) following the last def, it's not safe to fold the spill. SII->second.back().canFold = false; - std::map >::iterator RII = + DenseMap >::iterator RII = RestoreIdxes.find(MBBId); if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) // If we are splitting live intervals, only fold if it's the first @@ -1292,7 +1581,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, BitVector &RestoreMBBs, - std::map > &RestoreIdxes) { + DenseMap > &RestoreIdxes) { if (!RestoreMBBs[Id]) return false; std::vector &Restores = RestoreIdxes[Id]; @@ -1306,7 +1595,7 @@ bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, BitVector &RestoreMBBs, - std::map > &RestoreIdxes) { + DenseMap > &RestoreIdxes) { if (!RestoreMBBs[Id]) return; std::vector &Restores = RestoreIdxes[Id]; @@ -1315,14 +1604,159 @@ void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, Restores[i].index = -1; } +/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being +/// spilled and create empty intervals for their uses. +void +LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, + const TargetRegisterClass* rc, + std::vector &NewLIs) { + for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), + re = mri_->reg_end(); ri != re; ) { + MachineOperand &O = ri.getOperand(); + MachineInstr *MI = &*ri; + ++ri; + if (O.isDef()) { + assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && + "Register def was not rewritten?"); + RemoveMachineInstrFromMaps(MI); + vrm.RemoveMachineInstrFromMaps(MI); + MI->eraseFromParent(); + } else { + // This must be an use of an implicit_def so it's not part of the live + // interval. Create a new empty live interval for it. + // FIXME: Can we simply erase some of the instructions? e.g. Stores? + unsigned NewVReg = mri_->createVirtualRegister(rc); + vrm.grow(); + vrm.setIsImplicitlyDefined(NewVReg); + NewLIs.push_back(&getOrCreateInterval(NewVReg)); + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (MO.isReg() && MO.getReg() == li.reg) + MO.setReg(NewVReg); + } + } + } +} + +namespace { + struct LISorter { + bool operator()(LiveInterval* A, LiveInterval* B) { + return A->beginNumber() < B->beginNumber(); + } + }; +} std::vector LiveIntervals:: -addIntervalsForSpills(const LiveInterval &li, - const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { - // Since this is called after the analysis is done we don't know if - // LiveVariables is available - lv_ = getAnalysisToUpdate(); +addIntervalsForSpillsFast(const LiveInterval &li, + const MachineLoopInfo *loopInfo, + VirtRegMap &vrm, float& SSWeight) { + unsigned slot = vrm.assignVirt2StackSlot(li.reg); + + std::vector added; + + assert(li.weight != HUGE_VALF && + "attempt to spill already spilled interval!"); + + DOUT << "\t\t\t\tadding intervals for spills for interval: "; + DEBUG(li.dump()); + DOUT << '\n'; + + const TargetRegisterClass* rc = mri_->getRegClass(li.reg); + + SSWeight = 0.0f; + + MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); + while (RI != mri_->reg_end()) { + MachineInstr* MI = &*RI; + + SmallVector Indices; + bool HasUse = false; + bool HasDef = false; + + for (unsigned i = 0; i != MI->getNumOperands(); ++i) { + MachineOperand& mop = MI->getOperand(i); + if (!mop.isReg() || mop.getReg() != li.reg) continue; + + HasUse |= MI->getOperand(i).isUse(); + HasDef |= MI->getOperand(i).isDef(); + + Indices.push_back(i); + } + + if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), + Indices, true, slot, li.reg)) { + unsigned NewVReg = mri_->createVirtualRegister(rc); + vrm.grow(); + vrm.assignVirt2StackSlot(NewVReg, slot); + + // create a new register for this spill + LiveInterval &nI = getOrCreateInterval(NewVReg); + + // the spill weight is now infinity as it + // cannot be spilled again + nI.weight = HUGE_VALF; + + // Rewrite register operands to use the new vreg. + for (SmallVectorImpl::iterator I = Indices.begin(), + E = Indices.end(); I != E; ++I) { + MI->getOperand(*I).setReg(NewVReg); + + if (MI->getOperand(*I).isUse()) + MI->getOperand(*I).setIsKill(true); + } + + // Fill in the new live interval. + unsigned index = getInstructionIndex(MI); + if (HasUse) { + LiveRange LR(getLoadIndex(index), getUseIndex(index), + nI.getNextValue(~0U, 0, getVNInfoAllocator())); + DOUT << " +" << LR; + nI.addRange(LR); + vrm.addRestorePoint(NewVReg, MI); + } + if (HasDef) { + LiveRange LR(getDefIndex(index), getStoreIndex(index), + nI.getNextValue(~0U, 0, getVNInfoAllocator())); + DOUT << " +" << LR; + nI.addRange(LR); + vrm.addSpillPoint(NewVReg, true, MI); + } + + added.push_back(&nI); + + DOUT << "\t\t\t\tadded new interval: "; + DEBUG(nI.dump()); + DOUT << '\n'; + + unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); + if (HasUse) { + if (HasDef) + SSWeight += getSpillWeight(true, true, loopDepth); + else + SSWeight += getSpillWeight(false, true, loopDepth); + } else + SSWeight += getSpillWeight(true, false, loopDepth); + } + + + RI = mri_->reg_begin(li.reg); + } + + // Clients expect the new intervals to be returned in sorted order. + std::sort(added.begin(), added.end(), LISorter()); + return added; +} + +std::vector LiveIntervals:: +addIntervalsForSpills(const LiveInterval &li, + SmallVectorImpl &SpillIs, + const MachineLoopInfo *loopInfo, VirtRegMap &vrm, + float &SSWeight) { + + if (EnableFastSpilling) + return addIntervalsForSpillsFast(li, loopInfo, vrm, SSWeight); + assert(li.weight != HUGE_VALF && "attempt to spill already spilled interval!"); @@ -1330,12 +1764,15 @@ addIntervalsForSpills(const LiveInterval &li, li.print(DOUT, tri_); DOUT << '\n'; + // Spill slot weight. + SSWeight = 0.0f; + // Each bit specify whether it a spill is required in the MBB. BitVector SpillMBBs(mf_->getNumBlockIDs()); - std::map > SpillIdxes; + DenseMap > SpillIdxes; BitVector RestoreMBBs(mf_->getNumBlockIDs()); - std::map > RestoreIdxes; - std::map MBBVRegsMap; + DenseMap > RestoreIdxes; + DenseMap MBBVRegsMap; std::vector NewLIs; const TargetRegisterClass* rc = mri_->getRegClass(li.reg); @@ -1384,16 +1821,19 @@ addIntervalsForSpills(const LiveInterval &li, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, false, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - MBBVRegsMap, NewLIs); + MBBVRegsMap, NewLIs, SSWeight); } else { rewriteInstructionsForSpills(li, false, I, NULL, 0, Slot, 0, false, false, false, false, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - MBBVRegsMap, NewLIs); + MBBVRegsMap, NewLIs, SSWeight); } IsFirstRange = false; } + + SSWeight = 0.0f; // Already accounted for when split. + handleSpilledImpDefs(li, vrm, rc, NewLIs); return NewLIs; } @@ -1414,12 +1854,13 @@ addIntervalsForSpills(const LiveInterval &li, MachineInstr *ReMatDefMI = (DefIdx == ~0u) ? 0 : getInstructionFromIndex(DefIdx); bool dummy; - if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) { + if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { // Remember how to remat the def of this val#. ReMatOrigDefs[VN] = ReMatDefMI; - // Original def may be modified so we have to make a copy here. vrm must - // delete these! - ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone(); + // Original def may be modified so we have to make a copy here. + MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); + ClonedMIs.push_back(Clone); + ReMatDefs[VN] = Clone; bool CanDelete = true; if (VNI->hasPHIKill) { @@ -1458,18 +1899,22 @@ addIntervalsForSpills(const LiveInterval &li, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, CanDelete, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - MBBVRegsMap, NewLIs); + MBBVRegsMap, NewLIs, SSWeight); } // Insert spills / restores if we are splitting. - if (!TrySplit) + if (!TrySplit) { + handleSpilledImpDefs(li, vrm, rc, NewLIs); return NewLIs; + } SmallPtrSet AddedKill; SmallVector Ops; if (NeedStackSlot) { int Id = SpillMBBs.find_first(); while (Id != -1) { + MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); + unsigned loopDepth = loopInfo->getLoopDepth(MBB); std::vector &spills = SpillIdxes[Id]; for (unsigned i = 0, e = spills.size(); i != e; ++i) { int index = spills[i].index; @@ -1484,7 +1929,7 @@ addIntervalsForSpills(const LiveInterval &li, CanFold = true; for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { MachineOperand &MO = MI->getOperand(j); - if (!MO.isRegister() || MO.getReg() != VReg) + if (!MO.isReg() || MO.getReg() != VReg) continue; Ops.push_back(j); @@ -1516,14 +1961,20 @@ addIntervalsForSpills(const LiveInterval &li, } } - // Else tell the spiller to issue a spill. + // Otherwise tell the spiller to issue a spill. if (!Folded) { LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; bool isKill = LR->end == getStoreIndex(index); - vrm.addSpillPoint(VReg, isKill, MI); + if (!MI->registerDefIsDead(nI.reg)) + // No need to spill a dead def. + vrm.addSpillPoint(VReg, isKill, MI); if (isKill) AddedKill.insert(&nI); } + + // Update spill slot weight. + if (!isReMat) + SSWeight += getSpillWeight(true, false, loopDepth); } Id = SpillMBBs.find_next(Id); } @@ -1531,6 +1982,9 @@ addIntervalsForSpills(const LiveInterval &li, int Id = RestoreMBBs.find_first(); while (Id != -1) { + MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); + unsigned loopDepth = loopInfo->getLoopDepth(MBB); + std::vector &restores = RestoreIdxes[Id]; for (unsigned i = 0, e = restores.size(); i != e; ++i) { int index = restores[i].index; @@ -1538,6 +1992,7 @@ addIntervalsForSpills(const LiveInterval &li, continue; unsigned VReg = restores[i].vreg; LiveInterval &nI = getOrCreateInterval(VReg); + bool isReMat = vrm.isReMaterialized(VReg); MachineInstr *MI = getInstructionFromIndex(index); bool CanFold = false; Ops.clear(); @@ -1545,7 +2000,7 @@ addIntervalsForSpills(const LiveInterval &li, CanFold = true; for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { MachineOperand &MO = MI->getOperand(j); - if (!MO.isRegister() || MO.getReg() != VReg) + if (!MO.isReg() || MO.getReg() != VReg) continue; if (MO.isDef()) { @@ -1561,7 +2016,7 @@ addIntervalsForSpills(const LiveInterval &li, // Fold the load into the use if possible. bool Folded = false; if (CanFold && !Ops.empty()) { - if (!vrm.isReMaterialized(VReg)) + if (!isReMat) Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); else { MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); @@ -1575,12 +2030,10 @@ addIntervalsForSpills(const LiveInterval &li, if (ImpUse) { // Re-matting an instruction with virtual register use. Add the // register as an implicit use on the use MI and update the register - // interval's spill weight. - unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); + // interval's spill weight to HUGE_VALF to prevent it from being + // spilled. LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight += - getSpillWeight(false, true, loopDepth) / ImpLi.getSize(); - + ImpLi.weight = HUGE_VALF; MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); } } @@ -1591,6 +2044,10 @@ addIntervalsForSpills(const LiveInterval &li, nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); else vrm.addRestorePoint(VReg, MI); + + // Update spill slot weight. + if (!isReMat) + SSWeight += getSpillWeight(false, true, loopDepth); } Id = RestoreMBBs.find_next(Id); } @@ -1601,7 +2058,7 @@ addIntervalsForSpills(const LiveInterval &li, for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { LiveInterval *LI = NewLIs[i]; if (!LI->empty()) { - LI->weight /= LI->getSize(); + LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI); if (!AddedKill.count(LI)) { LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; unsigned LastUseIdx = getBaseIndex(LR->end); @@ -1618,5 +2075,99 @@ addIntervalsForSpills(const LiveInterval &li, } } + handleSpilledImpDefs(li, vrm, rc, RetNewLIs); return RetNewLIs; } + +/// hasAllocatableSuperReg - Return true if the specified physical register has +/// any super register that's allocatable. +bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { + for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) + if (allocatableRegs_[*AS] && hasInterval(*AS)) + return true; + return false; +} + +/// getRepresentativeReg - Find the largest super register of the specified +/// physical register. +unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { + // Find the largest super-register that is allocatable. + unsigned BestReg = Reg; + for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { + unsigned SuperReg = *AS; + if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { + BestReg = SuperReg; + break; + } + } + return BestReg; +} + +/// getNumConflictsWithPhysReg - Return the number of uses and defs of the +/// specified interval that conflicts with the specified physical register. +unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, + unsigned PhysReg) const { + unsigned NumConflicts = 0; + const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); + for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), + E = mri_->reg_end(); I != E; ++I) { + MachineOperand &O = I.getOperand(); + MachineInstr *MI = O.getParent(); + unsigned Index = getInstructionIndex(MI); + if (pli.liveAt(Index)) + ++NumConflicts; + } + return NumConflicts; +} + +/// spillPhysRegAroundRegDefsUses - Spill the specified physical register +/// around all defs and uses of the specified interval. +void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, + unsigned PhysReg, VirtRegMap &vrm) { + unsigned SpillReg = getRepresentativeReg(PhysReg); + + for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) + // If there are registers which alias PhysReg, but which are not a + // sub-register of the chosen representative super register. Assert + // since we can't handle it yet. + assert(*AS == SpillReg || !allocatableRegs_[*AS] || + tri_->isSuperRegister(*AS, SpillReg)); + + LiveInterval &pli = getInterval(SpillReg); + SmallPtrSet SeenMIs; + for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), + E = mri_->reg_end(); I != E; ++I) { + MachineOperand &O = I.getOperand(); + MachineInstr *MI = O.getParent(); + if (SeenMIs.count(MI)) + continue; + SeenMIs.insert(MI); + unsigned Index = getInstructionIndex(MI); + if (pli.liveAt(Index)) { + vrm.addEmergencySpill(SpillReg, MI); + pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); + for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { + if (!hasInterval(*AS)) + continue; + LiveInterval &spli = getInterval(*AS); + if (spli.liveAt(Index)) + spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); + } + } + } +} + +LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, + MachineInstr* startInst) { + LiveInterval& Interval = getOrCreateInterval(reg); + VNInfo* VN = Interval.getNextValue( + getInstructionIndex(startInst) + InstrSlots::DEF, + startInst, getVNInfoAllocator()); + VN->hasPHIKill = true; + VN->kills.push_back(getMBBEndIdx(startInst->getParent())); + LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF, + getMBBEndIdx(startInst->getParent()) + 1, VN); + Interval.addRange(LR); + + return LR; +}