X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=5ada75ca016c87f91abd241f78f14c0899f02bf3;hb=c3417609ae6e744a29be6962d4fb7811c0102d17;hp=e936158f3e1223262c03370b18329afb01f7b71e;hpb=24a3cc4c83e5edb25fadf7b8979a26b4451795c6;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index e936158f3e1..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,90 +19,79 @@ #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" #include "llvm/Support/Debug.h" -#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" #include #include using namespace llvm; +// 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"); -STATISTIC(numJoins , "Number of interval joins performed"); -STATISTIC(numPeep , "Number of identity moves eliminated after coalescing"); -STATISTIC(numFolded , "Number of loads/stores folded into instructions"); -STATISTIC(numAborts , "Number of times interval joining aborted"); - -namespace { - RegisterPass X("liveintervals", "Live Interval Analysis"); +STATISTIC(numFolds , "Number of loads/stores folded into instructions"); +STATISTIC(numSplits , "Number of intervals split"); - static cl::opt - EnableJoining("join-liveintervals", - cl::desc("Coallesce copies (default=true)"), - cl::init(true)); -} +char LiveIntervals::ID = 0; +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); - AU.addRequired(); MachineFunctionPass::getAnalysisUsage(AU); } void LiveIntervals::releaseMemory() { + MBB2IdxMap.clear(); + Idx2MBBMap.clear(); mi2iMap_.clear(); i2miMap_.clear(); r2iMap_.clear(); - r2rMap_.clear(); - JoinedLIs.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]; } - -static bool isZeroLengthInterval(LiveInterval *li) { - for (LiveInterval::Ranges::const_iterator - i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i) - if (i->end - i->start > LiveIntervals::InstrSlots::NUM) - return false; - return true; -} - - -/// runOnMachineFunction - Register allocate the whole function -/// -bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { - mf_ = &fn; - tm_ = &fn.getTarget(); - mri_ = tm_->getRegisterInfo(); - tii_ = tm_->getInstrInfo(); - lv_ = &getAnalysis(); - r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); - allocatableRegs_ = mri_->getAllocatableSet(fn); - for (MRegisterInfo::regclass_iterator I = mri_->regclass_begin(), - E = mri_->regclass_end(); I != E; ++I) - allocatableRCRegs_.insert(std::make_pair(*I,mri_->getAllocatableSet(fn, *I))); - +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(), ~0U); + MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); unsigned MIIndex = 0; for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); MBB != E; ++MBB) { - // Set the MBB2IdxMap entry for this MBB. - MBB2IdxMap[MBB->getNumber()] = MIIndex; + unsigned StartIdx = MIIndex; for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) { @@ -111,111 +100,131 @@ 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"; } - // Join (coallesce) intervals if requested. - if (EnableJoining) { - joinIntervals(); - DOUT << "********** INTERVALS POST JOINING **********\n"; - for (iterator I = begin(), E = end(); I != E; ++I) { - I->second.print(DOUT, mri_); - DOUT << "\n"; - } - } - numIntervalsAfter += getNumIntervals(); - - // perform a final pass over the instructions and compute spill - // weights, coalesce virtual registers and remove identity moves. - const LoopInfo &loopInfo = getAnalysis(); - - for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); - mbbi != mbbe; ++mbbi) { - MachineBasicBlock* mbb = mbbi; - unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); - - for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); - mii != mie; ) { - // if the move will be an identity move delete it - unsigned srcReg, dstReg, RegRep; - if (tii_->isMoveInstr(*mii, srcReg, dstReg) && - (RegRep = rep(srcReg)) == rep(dstReg)) { - // remove from def list - LiveInterval &RegInt = getOrCreateInterval(RegRep); - MachineOperand *MO = mii->findRegisterDefOperand(dstReg); - // If def of this move instruction is dead, remove its live range from - // the dstination register's live interval. - if (MO->isDead()) { - unsigned MoveIdx = getDefIndex(getInstructionIndex(mii)); - LiveInterval::iterator MLR = RegInt.FindLiveRangeContaining(MoveIdx); - RegInt.removeRange(MLR->start, MoveIdx+1); - if (RegInt.empty()) - removeInterval(RegRep); - } - RemoveMachineInstrFromMaps(mii); - mii = mbbi->erase(mii); - ++numPeep; - } else { - SmallSet UniqueUses; - for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { - const MachineOperand &mop = mii->getOperand(i); - if (mop.isRegister() && mop.getReg() && - MRegisterInfo::isVirtualRegister(mop.getReg())) { - // replace register with representative register - unsigned reg = rep(mop.getReg()); - mii->getOperand(i).setReg(reg); - - // Multiple uses of reg by the same instruction. It should not - // contribute to spill weight again. - if (UniqueUses.count(reg) != 0) - continue; - LiveInterval &RegInt = getInterval(reg); - float w = (mop.isUse()+mop.isDef()) * powf(10.0F, (float)loopDepth); - // If the definition instruction is re-materializable, its spill - // weight is half of what it would have been normally unless it's - // a load from fixed stack slot. - int Dummy; - if (RegInt.remat && !tii_->isLoadFromStackSlot(RegInt.remat, Dummy)) - w /= 2; - RegInt.weight += w; - UniqueUses.insert(reg); - } - } - ++mii; - } - } - } - - for (iterator I = begin(), E = end(); I != E; ++I) { - LiveInterval &LI = I->second; - if (MRegisterInfo::isVirtualRegister(LI.reg)) { - // If the live interval length is essentially zero, i.e. in every live - // range the use follows def immediately, it doesn't make sense to spill - // it and hope it will be easier to allocate for this li. - if (isZeroLengthInterval(&LI)) - LI.weight = HUGE_VALF; - - // Slightly prefer live interval that has been assigned a preferred reg. - if (LI.preference) - LI.weight *= 1.01F; - - // Divide the weight of the interval by its size. This encourages - // spilling of intervals that are large and have few uses, and - // discourages spilling of small intervals with many uses. - LI.weight /= LI.getSize(); - } - } - DEBUG(dump()); return true; } @@ -224,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"; @@ -239,203 +248,53 @@ void LiveIntervals::print(std::ostream &O, const Module* ) const { } } -/// CreateNewLiveInterval - Create a new live interval with the given live -/// ranges. The new live interval will have an infinite spill weight. -LiveInterval& -LiveIntervals::CreateNewLiveInterval(const LiveInterval *LI, - const std::vector &LRs) { - const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(LI->reg); - - // Create a new virtual register for the spill interval. - unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(RC); - - // Replace the old virtual registers in the machine operands with the shiny - // new one. - for (std::vector::const_iterator - I = LRs.begin(), E = LRs.end(); I != E; ++I) { - unsigned Index = getBaseIndex(I->start); - unsigned End = getBaseIndex(I->end - 1) + InstrSlots::NUM; - - for (; Index != End; Index += InstrSlots::NUM) { - // Skip deleted instructions - while (Index != End && !getInstructionFromIndex(Index)) - Index += InstrSlots::NUM; - - if (Index == End) break; - - MachineInstr *MI = getInstructionFromIndex(Index); - - for (unsigned J = 0, e = MI->getNumOperands(); J != e; ++J) { - MachineOperand &MOp = MI->getOperand(J); - if (MOp.isRegister() && rep(MOp.getReg()) == LI->reg) - MOp.setReg(NewVReg); - } - } - } - - LiveInterval &NewLI = getOrCreateInterval(NewVReg); - - // The spill weight is now infinity as it cannot be spilled again - NewLI.weight = float(HUGE_VAL); - - for (std::vector::const_iterator - I = LRs.begin(), E = LRs.end(); I != E; ++I) { - DOUT << " Adding live range " << *I << " to new interval\n"; - NewLI.addRange(*I); - } - - DOUT << "Created new live interval " << NewLI << "\n"; - return NewLI; -} - -std::vector LiveIntervals:: -addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { - // since this is called after the analysis is done we don't know if - // LiveVariables is available - lv_ = getAnalysisToUpdate(); - - std::vector added; - - assert(li.weight != HUGE_VALF && - "attempt to spill already spilled interval!"); - - DOUT << "\t\t\t\tadding intervals for spills for interval: "; - li.print(DOUT, mri_); - DOUT << '\n'; - - const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); - +/// conflictsWithPhysRegDef - Returns true if the specified register +/// is defined during the duration of the specified interval. +bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, + VirtRegMap &vrm, unsigned reg) { for (LiveInterval::Ranges::const_iterator - i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { - unsigned index = getBaseIndex(i->start); - unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM; - for (; index != end; index += InstrSlots::NUM) { + I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { + for (unsigned index = getBaseIndex(I->start), + end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; + index += InstrSlots::NUM) { // skip deleted instructions while (index != end && !getInstructionFromIndex(index)) index += InstrSlots::NUM; if (index == end) break; MachineInstr *MI = getInstructionFromIndex(index); - - RestartInstruction: + unsigned SrcReg, DstReg; + if (tii_->isMoveInstr(*MI, SrcReg, DstReg)) + if (SrcReg == li.reg || DstReg == li.reg) + continue; for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& mop = MI->getOperand(i); - if (mop.isRegister() && mop.getReg() == li.reg) { - MachineInstr *fmi = li.remat ? NULL - : mri_->foldMemoryOperand(MI, i, slot); - if (fmi) { - // Attempt to fold the memory reference into the instruction. If we - // can do this, we don't need to insert spill code. - if (lv_) - lv_->instructionChanged(MI, fmi); - MachineBasicBlock &MBB = *MI->getParent(); - vrm.virtFolded(li.reg, MI, i, fmi); - mi2iMap_.erase(MI); - i2miMap_[index/InstrSlots::NUM] = fmi; - mi2iMap_[fmi] = index; - MI = MBB.insert(MBB.erase(MI), fmi); - ++numFolded; - // Folding the load/store can completely change the instruction in - // unpredictable ways, rescan it from the beginning. - goto RestartInstruction; - } else { - // Create a new virtual register for the spill interval. - unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(rc); - - // 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: - // - // 1. If the instr reads the same spilled vreg multiple times, we - // want to reuse the NewVReg. - // 2. If the instr is a two-addr instruction, we are required to - // keep the src/dst regs pinned. - // - // Keep track of whether we replace a use and/or def so that we can - // create the spill interval with the appropriate range. - mop.setReg(NewVReg); - - bool HasUse = mop.isUse(); - bool HasDef = mop.isDef(); - for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { - if (MI->getOperand(j).isReg() && - MI->getOperand(j).getReg() == li.reg) { - MI->getOperand(j).setReg(NewVReg); - HasUse |= MI->getOperand(j).isUse(); - HasDef |= MI->getOperand(j).isDef(); - } - } - - // create a new register for this spill - vrm.grow(); - if (li.remat) - vrm.setVirtIsReMaterialized(NewVReg, li.remat); - vrm.assignVirt2StackSlot(NewVReg, slot); - LiveInterval &nI = getOrCreateInterval(NewVReg); - nI.remat = li.remat; - assert(nI.empty()); - - // the spill weight is now infinity as it - // cannot be spilled again - nI.weight = HUGE_VALF; - - if (HasUse) { - LiveRange LR(getLoadIndex(index), getUseIndex(index), - nI.getNextValue(~0U, 0)); - DOUT << " +" << LR; - nI.addRange(LR); - } - if (HasDef) { - LiveRange LR(getDefIndex(index), getStoreIndex(index), - nI.getNextValue(~0U, 0)); - DOUT << " +" << LR; - nI.addRange(LR); - } - - added.push_back(&nI); - - // update live variables if it is available - if (lv_) - lv_->addVirtualRegisterKilled(NewVReg, MI); - - DOUT << "\t\t\t\tadded new interval: "; - nI.print(DOUT, mri_); - DOUT << '\n'; - } + if (!mop.isRegister()) + continue; + unsigned PhysReg = mop.getReg(); + if (PhysReg == 0 || PhysReg == li.reg) + continue; + if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { + if (!vrm.hasPhys(PhysReg)) + continue; + PhysReg = vrm.getPhys(PhysReg); } + if (PhysReg && tri_->regsOverlap(PhysReg, reg)) + return true; } } } - return added; + return false; } 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; } -/// isReDefinedByTwoAddr - Returns true if the Reg re-definition is due to -/// two addr elimination. -static bool isReDefinedByTwoAddr(MachineInstr *MI, unsigned Reg, - const TargetInstrInfo *TII) { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO1 = MI->getOperand(i); - if (MO1.isRegister() && MO1.isDef() && MO1.getReg() == Reg) { - for (unsigned j = i+1; j < e; ++j) { - MachineOperand &MO2 = MI->getOperand(j); - if (MO2.isRegister() && MO2.isUse() && MO2.getReg() == Reg && - MI->getInstrDescriptor()-> - getOperandConstraint(j, TOI::TIED_TO) == (int)i) - return true; - } - } - } - return false; -} - void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, MachineBasicBlock::iterator mi, unsigned MIIdx, @@ -443,32 +302,28 @@ 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 // time we see a vreg. if (interval.empty()) { - // Remember if the definition can be rematerialized. All load's from fixed - // stack slots are re-materializable. - int FrameIdx = 0; - if (vi.DefInst && - (tii_->isReMaterializable(vi.DefInst->getOpcode()) || - (tii_->isLoadFromStackSlot(vi.DefInst, FrameIdx) && - mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx)))) - interval.remat = vi.DefInst; - // Get the Idx of the defining instructions. unsigned defIndex = getDefIndex(MIIdx); - - unsigned ValNum; + VNInfo *ValNo; + MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; - if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) - ValNum = interval.getNextValue(~0U, 0); - else - ValNum = interval.getNextValue(defIndex, SrcReg); - - assert(ValNum == 0 && "First value in interval is not 0?"); - ValNum = 0; // Clue in the optimizer. + 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?"); // Loop over all of the blocks that the vreg is defined in. There are // two cases we have to handle here. The most common case is a vreg @@ -487,9 +342,10 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, if (killIdx > defIndex) { assert(vi.AliveBlocks.none() && "Shouldn't be alive across any blocks!"); - LiveRange LR(defIndex, killIdx, ValNum); + LiveRange LR(defIndex, killIdx, ValNo); interval.addRange(LR); DOUT << " +" << LR << "\n"; + interval.addKill(ValNo, killIdx); return; } } @@ -500,7 +356,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // range that goes from this definition to the end of the defining block. LiveRange NewLR(defIndex, getInstructionIndex(&mbb->back()) + InstrSlots::NUM, - ValNum); + ValNo); DOUT << " +" << NewLR; interval.addRange(NewLR); @@ -509,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, - ValNum); - interval.addRange(LR); - DOUT << " +" << LR; - } + LiveRange LR(getMBBStartIdx(i), + getMBBEndIdx(i)+1, // MBB ends at -1. + ValNo); + interval.addRange(LR); + DOUT << " +" << LR; } } @@ -524,30 +377,32 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // block to the 'use' slot of the killing instruction. for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { MachineInstr *Kill = vi.Kills[i]; + unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; LiveRange LR(getMBBStartIdx(Kill->getParent()), - getUseIndex(getInstructionIndex(Kill))+1, - ValNum); + killIdx, ValNo); interval.addRange(LR); + interval.addKill(ValNo, killIdx); DOUT << " +" << LR; } } else { - // Can no longer safely assume definition is rematerializable. - interval.remat = NULL; - // If this is the second time we see a virtual register definition, it // 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 (isReDefinedByTwoAddr(mi, interval.reg, tii_)) { + if (mi->isRegReDefinedByTwoAddr(interval.reg)) { // 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 // 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; + // Delete the initial value, which should be short and continuous, // because the 2-addr copy must be in the same MBB as the redef. interval.removeRange(DefIndex, RedefIndex); @@ -558,24 +413,26 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // The new value number (#1) is defined by the instruction we claimed // defined value #0. - unsigned ValNo = interval.getNextValue(0, 0); - interval.setValueNumberInfo(1, interval.getValNumInfo(0)); + VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy, + VNInfoAllocator); // Value#0 is now defined by the 2-addr instruction. - interval.setValueNumberInfo(0, std::make_pair(~0U, 0U)); + 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); // If this redefinition is dead, we need to add a dummy unit live // range covering the def slot. - if (lv_->RegisterDefIsDead(mi, interval.reg)) - interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); + 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 @@ -586,20 +443,23 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, "PHI elimination vreg should have one kill, the PHI itself!"); // Remove the old range that we now know has an incorrect number. + VNInfo *VNI = interval.getValNumInfo(0); MachineInstr *Killer = vi.Kills[0]; 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); - 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? :) - LiveRange LR(Start, End, interval.getNextValue(~0U, 0)); + LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); DOUT << " replace range with " << LR; interval.addRange(LR); - DOUT << " RESULT: "; interval.print(DOUT, mri_); + interval.addKill(LR.valno, End); + DOUT << " RESULT: "; interval.print(DOUT, tri_); } // In the case of PHI elimination, each variable definition is only @@ -607,16 +467,20 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // rest of the live range. unsigned defIndex = getDefIndex(MIIdx); - unsigned ValNum; + VNInfo *ValNo; + MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; - if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) - ValNum = interval.getNextValue(~0U, 0); - else - ValNum = interval.getNextValue(defIndex, SrcReg); + if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || + mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || + tii_->isMoveInstr(*mi, SrcReg, DstReg)) + CopyMI = mi; + ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); - LiveRange LR(defIndex, - getInstructionIndex(&mbb->back()) + InstrSlots::NUM, ValNum); + unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; + LiveRange LR(defIndex, killIndex, ValNo); interval.addRange(LR); + interval.addKill(ValNo, killIndex); + ValNo->hasPHIKill = true; DOUT << " +" << LR; } } @@ -628,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)); @@ -640,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; @@ -651,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: @@ -669,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: @@ -677,11 +541,11 @@ exit: // Already exists? Extend old live interval. LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); - unsigned Id = (OldLR != interval.end()) - ? OldLR->ValId - : interval.getNextValue(SrcReg != 0 ? start : ~0U, SrcReg); - LiveRange LR(start, end, Id); + VNInfo *ValNo = (OldLR != interval.end()) + ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator); + LiveRange LR(start, end, ValNo); interval.addRange(LR); + interval.addKill(LR.valno, end); DOUT << " +" << LR << '\n'; } @@ -689,17 +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 (!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); } } @@ -716,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: @@ -735,17 +603,21 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, } exit: - // Alias of a live-in register might not be used at all. - if (isAlias && end == 0) { - DOUT << " dead"; - end = getDefIndex(start) + 1; + // Live-in register might not be used at all. + if (end == MIIdx) { + if (isAlias) { + DOUT << " dead"; + end = getDefIndex(MIIdx) + 1; + } else { + DOUT << " live through"; + end = baseIndex; + } } - assert(start < end && "did not find end of interval?"); - - LiveRange LR(start, end, interval.getNextValue(~0U, 0)); - DOUT << " +" << LR << '\n'; + LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); interval.addRange(LR); + interval.addKill(LR.valno, end); + DOUT << " +" << LR << '\n'; } /// computeIntervals - computes the live intervals for virtual @@ -765,16 +637,15 @@ void LiveIntervals::computeIntervals() { MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); - if (MBB->livein_begin() != MBB->livein_end()) { - // Create intervals for live-ins to this BB first. - for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), - 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) - if (!hasInterval(*AS)) - handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), true); - } + // Create intervals for live-ins to this BB first. + for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), + LE = MBB->livein_end(); LI != LE; ++LI) { + handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); + // Multiple live-ins can alias the same register. + for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) + if (!hasInterval(*AS)) + handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), + true); } for (; MI != miEnd; ++MI) { @@ -790,914 +661,1219 @@ void LiveIntervals::computeIntervals() { MIIndex += InstrSlots::NUM; } + + if (MBB->begin() == miEnd) MIIndex += InstrSlots::NUM; // Empty MBB } } -/// AdjustCopiesBackFrom - We found a non-trivially-coallescable copy with IntA -/// being the source and IntB being the dest, thus this defines a value number -/// in IntB. If the source value number (in IntA) is defined by a copy from B, -/// see if we can merge these two pieces of B into a single value number, -/// eliminating a copy. For example: -/// -/// A3 = B0 -/// ... -/// B1 = A3 <- this copy -/// -/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 -/// value number to be replaced with B0 (which simplifies the B liveinterval). -/// -/// This returns true if an interval was modified. -/// -bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, - MachineInstr *CopyMI) { - unsigned CopyIdx = getDefIndex(getInstructionIndex(CopyMI)); - - // BValNo is a value number in B that is defined by a copy from A. 'B3' in - // the example above. - LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); - unsigned BValNo = BLR->ValId; - - // Get the location that B is defined at. Two options: either this value has - // an unknown definition point or it is defined at CopyIdx. If unknown, we - // can't process it. - unsigned BValNoDefIdx = IntB.getInstForValNum(BValNo); - if (BValNoDefIdx == ~0U) return false; - assert(BValNoDefIdx == CopyIdx && - "Copy doesn't define the value?"); - - // AValNo is the value number in A that defines the copy, A0 in the example. - LiveInterval::iterator AValLR = IntA.FindLiveRangeContaining(CopyIdx-1); - unsigned AValNo = AValLR->ValId; - - // If AValNo is defined as a copy from IntB, we can potentially process this. - - // Get the instruction that defines this value number. - unsigned SrcReg = IntA.getSrcRegForValNum(AValNo); - if (!SrcReg) return false; // Not defined by a copy. - - // If the value number is not defined by a copy instruction, ignore it. - - // If the source register comes from an interval other than IntB, we can't - // handle this. - if (rep(SrcReg) != IntB.reg) return false; - - // Get the LiveRange in IntB that this value number starts with. - unsigned AValNoInstIdx = IntA.getInstForValNum(AValNo); - LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNoInstIdx-1); - - // Make sure that the end of the live range is inside the same block as - // CopyMI. - MachineInstr *ValLREndInst = getInstructionFromIndex(ValLR->end-1); - if (!ValLREndInst || - ValLREndInst->getParent() != CopyMI->getParent()) return false; - - // Okay, we now know that ValLR ends in the same block that the CopyMI - // live-range starts. If there are no intervening live ranges between them in - // IntB, we can merge them. - if (ValLR+1 != BLR) return false; - - DOUT << "\nExtending: "; IntB.print(DOUT, mri_); - - // We are about to delete CopyMI, so need to remove it as the 'instruction - // that defines this value #'. - IntB.setValueNumberInfo(BValNo, std::make_pair(~0U, 0)); - - // Okay, we can merge them. We need to insert a new liverange: - // [ValLR.end, BLR.begin) of either value number, then we merge the - // two value numbers. - unsigned FillerStart = ValLR->end, FillerEnd = BLR->start; - IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); - - // If the IntB live range is assigned to a physical register, and if that - // physreg has aliases, - if (MRegisterInfo::isPhysicalRegister(IntB.reg)) { - // Update the liveintervals of sub-registers. - for (const unsigned *AS = mri_->getSubRegisters(IntB.reg); *AS; ++AS) { - LiveInterval &AliasLI = getInterval(*AS); - AliasLI.addRange(LiveRange(FillerStart, FillerEnd, - AliasLI.getNextValue(~0U, 0))); - } +bool LiveIntervals::findLiveInMBBs(const LiveRange &LR, + SmallVectorImpl &MBBs) const { + std::vector::const_iterator I = + std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start); + + bool ResVal = false; + while (I != Idx2MBBMap.end()) { + if (LR.end <= I->first) + break; + MBBs.push_back(I->second); + ResVal = true; + ++I; } + return ResVal; +} - // Okay, merge "B1" into the same value number as "B0". - if (BValNo != ValLR->ValId) - IntB.MergeValueNumberInto(BValNo, ValLR->ValId); - DOUT << " result = "; IntB.print(DOUT, mri_); - DOUT << "\n"; - - // If the source instruction was killing the source register before the - // merge, unset the isKill marker given the live range has been extended. - int UIdx = ValLREndInst->findRegisterUseOperand(IntB.reg, true); - if (UIdx != -1) - ValLREndInst->getOperand(UIdx).unsetIsKill(); - - // Finally, delete the copy instruction. - RemoveMachineInstrFromMaps(CopyMI); - CopyMI->eraseFromParent(); - ++numPeep; - return true; + +LiveInterval LiveIntervals::createInterval(unsigned 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; +} -/// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, -/// which are the src/dst of the copy instruction CopyMI. This returns true -/// if the copy was successfully coallesced away, or if it is never possible -/// to coallesce this copy, due to register constraints. It returns -/// false if it is not currently possible to coallesce this interval, but -/// it may be possible if other things get coallesced. -bool LiveIntervals::JoinCopy(MachineInstr *CopyMI, - unsigned SrcReg, unsigned DstReg, bool PhysOnly) { - DOUT << getInstructionIndex(CopyMI) << '\t' << *CopyMI; +//===----------------------------------------------------------------------===// +// Register allocator hooks. +// - // Get representative registers. - unsigned repSrcReg = rep(SrcReg); - unsigned repDstReg = rep(DstReg); - - // If they are already joined we continue. - if (repSrcReg == repDstReg) { - DOUT << "\tCopy already coallesced.\n"; - return true; // Not coallescable. +/// 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; } - - bool SrcIsPhys = MRegisterInfo::isPhysicalRegister(repSrcReg); - bool DstIsPhys = MRegisterInfo::isPhysicalRegister(repDstReg); - if (PhysOnly && !SrcIsPhys && !DstIsPhys) - // Only joining physical registers with virtual registers in this round. + 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, + bool &isLoad) { + if (DisableReMat) + return false; + + isLoad = false; + if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) return true; - // If they are both physical registers, we cannot join them. - if (SrcIsPhys && DstIsPhys) { - DOUT << "\tCan not coallesce physregs.\n"; - return true; // Not coallescable. - } - - // We only join virtual registers with allocatable physical registers. - if (SrcIsPhys && !allocatableRegs_[repSrcReg]) { - DOUT << "\tSrc reg is unallocatable physreg.\n"; - return true; // Not coallescable. - } - if (DstIsPhys && !allocatableRegs_[repDstReg]) { - DOUT << "\tDst reg is unallocatable physreg.\n"; - return true; // Not coallescable. - } - - // If they are not of the same register class, we cannot join them. - if (differingRegisterClasses(repSrcReg, repDstReg)) { - DOUT << "\tSrc/Dest are different register classes.\n"; - return true; // Not coallescable. - } - - LiveInterval &SrcInt = getInterval(repSrcReg); - LiveInterval &DstInt = getInterval(repDstReg); - assert(SrcInt.reg == repSrcReg && DstInt.reg == repDstReg && - "Register mapping is horribly broken!"); - - DOUT << "\t\tInspecting "; SrcInt.print(DOUT, mri_); - DOUT << " and "; DstInt.print(DOUT, mri_); - DOUT << ": "; - - // Check if it is necessary to propagate "isDead" property before intervals - // are joined. - MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg); - bool isDead = mopd->isDead(); - bool isShorten = false; - unsigned SrcStart = 0, RemoveStart = 0; - unsigned SrcEnd = 0, RemoveEnd = 0; - if (isDead) { - unsigned CopyIdx = getInstructionIndex(CopyMI); - LiveInterval::iterator SrcLR = - SrcInt.FindLiveRangeContaining(getUseIndex(CopyIdx)); - RemoveStart = SrcStart = SrcLR->start; - RemoveEnd = SrcEnd = SrcLR->end; - // The instruction which defines the src is only truly dead if there are - // no intermediate uses and there isn't a use beyond the copy. - // FIXME: find the last use, mark is kill and shorten the live range. - if (SrcEnd > getDefIndex(CopyIdx)) { - isDead = false; - } else { - MachineOperand *MOU; - MachineInstr *LastUse= lastRegisterUse(repSrcReg, SrcStart, CopyIdx, MOU); - if (LastUse) { - // Shorten the liveinterval to the end of last use. - MOU->setIsKill(); - isDead = false; - isShorten = true; - RemoveStart = getDefIndex(getInstructionIndex(LastUse)); - RemoveEnd = SrcEnd; - } else { - MachineInstr *SrcMI = getInstructionFromIndex(SrcStart); - if (SrcMI) { - MachineOperand *mops = findDefOperand(SrcMI, repSrcReg); - if (mops) - // A dead def should have a single cycle interval. - ++RemoveStart; - } + int FrameIdx = 0; + if (tii_->isLoadFromStackSlot(MI, FrameIdx) && + mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) + // FIXME: Let target specific isReallyTriviallyReMaterializable determines + // this but remember this is not safe to fold into a two-address + // instruction. + // This is a load from fixed stack slot. It can be rematerialized. + return true; + + if (tii_->isTriviallyReMaterializable(MI)) { + const TargetInstrDesc &TID = MI->getDesc(); + isLoad = TID.isSimpleLoad(); + + unsigned ImpUse = getReMatImplicitUse(li, MI); + 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; } - // We need to be careful about coalescing a source physical register with a - // virtual register. Once the coalescing is done, it cannot be broken and - // these are not spillable! If the destination interval uses are far away, - // think twice about coalescing them! - if (!mopd->isDead() && (SrcIsPhys || DstIsPhys)) { - LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt; - unsigned JoinVReg = SrcIsPhys ? repDstReg : repSrcReg; - unsigned JoinPReg = SrcIsPhys ? repSrcReg : repDstReg; - const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(JoinVReg); - unsigned Threshold = allocatableRCRegs_[RC].count(); - - // If the virtual register live interval is long has it has low use desity, - // do not join them, instead mark the physical register as its allocation - // preference. - unsigned Length = JoinVInt.getSize() / InstrSlots::NUM; - LiveVariables::VarInfo &vi = lv_->getVarInfo(JoinVReg); - if (Length > Threshold && - (((float)vi.NumUses / Length) < (1.0 / Threshold))) { - JoinVInt.preference = JoinPReg; - ++numAborts; - DOUT << "\tMay tie down a physical register, abort!\n"; + 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; + unsigned DefIdx = VNI->def; + if (DefIdx == ~1U) + continue; // Dead val#. + // 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; +} - // Okay, attempt to join these two intervals. On failure, this returns false. - // Otherwise, if one of the intervals being joined is a physreg, this method - // always canonicalizes DstInt to be it. The output "SrcInt" will not have - // been modified, so we can use this information below to update aliases. - if (JoinIntervals(DstInt, SrcInt)) { - if (isDead) { - // Result of the copy is dead. Propagate this property. - if (SrcStart == 0) { - assert(MRegisterInfo::isPhysicalRegister(repSrcReg) && - "Live-in must be a physical register!"); - // Live-in to the function but dead. Remove it from entry live-in set. - // JoinIntervals may end up swapping the two intervals. - mf_->begin()->removeLiveIn(repSrcReg); - } else { - MachineInstr *SrcMI = getInstructionFromIndex(SrcStart); - if (SrcMI) { - MachineOperand *mops = findDefOperand(SrcMI, repSrcReg); - if (mops) - mops->setIsDead(); - } +/// 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 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; + } - if (isShorten || isDead) { - // Shorten the live interval. - LiveInterval &LiveInInt = (repSrcReg == DstInt.reg) ? DstInt : SrcInt; - LiveInInt.removeRange(RemoveStart, RemoveEnd); - } - } else { - // Coallescing failed. - - // If we can eliminate the copy without merging the live ranges, do so now. - if (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI)) - 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; - // Otherwise, we are unable to join the intervals. - DOUT << "Interference!\n"; + // 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; - } - bool Swapped = repSrcReg == DstInt.reg; - if (Swapped) - std::swap(repSrcReg, repDstReg); - assert(MRegisterInfo::isVirtualRegister(repSrcReg) && - "LiveInterval::join didn't work right!"); - - // If we're about to merge live ranges into a physical register live range, - // we have to update any aliased register's live ranges to indicate that they - // have clobbered values for this range. - if (MRegisterInfo::isPhysicalRegister(repDstReg)) { - // Update the liveintervals of sub-registers. - for (const unsigned *AS = mri_->getSubRegisters(repDstReg); *AS; ++AS) - getInterval(*AS).MergeInClobberRanges(SrcInt); - } else { - // Merge use info if the destination is a virtual register. - LiveVariables::VarInfo& dVI = lv_->getVarInfo(repDstReg); - LiveVariables::VarInfo& sVI = lv_->getVarInfo(repSrcReg); - dVI.NumUses += sVI.NumUses; - } + 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); - DOUT << "\n\t\tJoined. Result = "; DstInt.print(DOUT, mri_); - DOUT << "\n"; - - // Remember these liveintervals have been joined. - JoinedLIs.set(repSrcReg - MRegisterInfo::FirstVirtualRegister); - if (MRegisterInfo::isVirtualRegister(repDstReg)) - JoinedLIs.set(repDstReg - MRegisterInfo::FirstVirtualRegister); - - // If the intervals were swapped by Join, swap them back so that the register - // mapping (in the r2i map) is correct. - if (Swapped) SrcInt.swap(DstInt); - removeInterval(repSrcReg); - r2rMap_[repSrcReg] = repDstReg; - - // Finally, delete the copy instruction. - RemoveMachineInstrFromMaps(CopyMI); - CopyMI->eraseFromParent(); - ++numPeep; - ++numJoins; - return true; + // 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; + MI = MBB.insert(MBB.erase(MI), fmi); + ++numFolds; + return true; + } + return false; } -/// ComputeUltimateVN - Assuming we are going to join two live intervals, -/// compute what the resultant value numbers for each value in the input two -/// ranges will be. This is complicated by copies between the two which can -/// and will commonly cause multiple value numbers to be merged into one. -/// -/// VN is the value number that we're trying to resolve. InstDefiningValue -/// keeps track of the new InstDefiningValue assignment for the result -/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of -/// whether a value in this or other is a copy from the opposite set. -/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have -/// already been assigned. -/// -/// ThisFromOther[x] - If x is defined as a copy from the other interval, this -/// contains the value number the copy is from. -/// -static unsigned ComputeUltimateVN(unsigned VN, - SmallVector, 16> &ValueNumberInfo, - SmallVector &ThisFromOther, - SmallVector &OtherFromThis, - SmallVector &ThisValNoAssignments, - SmallVector &OtherValNoAssignments, - LiveInterval &ThisLI, LiveInterval &OtherLI) { - // If the VN has already been computed, just return it. - if (ThisValNoAssignments[VN] >= 0) - return ThisValNoAssignments[VN]; -// assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?"); - - // If this val is not a copy from the other val, then it must be a new value - // number in the destination. - int OtherValNo = ThisFromOther[VN]; - if (OtherValNo == -1) { - ValueNumberInfo.push_back(ThisLI.getValNumInfo(VN)); - return ThisValNoAssignments[VN] = ValueNumberInfo.size()-1; - } +/// 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; - // Otherwise, this *is* a copy from the RHS. If the other side has already - // been computed, return it. - if (OtherValNoAssignments[OtherValNo] >= 0) - return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo]; - - // Mark this value number as currently being computed, then ask what the - // ultimate value # of the other value is. - ThisValNoAssignments[VN] = -2; - unsigned UltimateVN = - ComputeUltimateVN(OtherValNo, ValueNumberInfo, - OtherFromThis, ThisFromOther, - OtherValNoAssignments, ThisValNoAssignments, - OtherLI, ThisLI); - return ThisValNoAssignments[VN] = UltimateVN; + // It's only legal to remat for a use, not a def. + if (ReMat && (MRInfo & VirtRegMap::isMod)) + return false; + + return tii_->canFoldMemoryOperand(MI, FoldOps); } -static bool InVector(unsigned Val, const SmallVector &V) { - return std::find(V.begin(), V.end(), Val) != V.end(); +bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { + SmallPtrSet MBBs; + for (LiveInterval::Ranges::const_iterator + I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { + std::vector::const_iterator II = + std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); + if (II == Idx2MBBMap.end()) + continue; + if (I->end > II->first) // crossing a MBB. + return false; + MBBs.insert(II->second); + if (MBBs.size() > 1) + return false; + } + return true; } -/// SimpleJoin - Attempt to joint the specified interval into this one. The -/// caller of this method must guarantee that the RHS only contains a single -/// value number and that the RHS is not defined by a copy from this -/// interval. This returns false if the intervals are not joinable, or it -/// joins them and returns true. -bool LiveIntervals::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) { - assert(RHS.containsOneValue()); - - // Some number (potentially more than one) value numbers in the current - // interval may be defined as copies from the RHS. Scan the overlapping - // portions of the LHS and RHS, keeping track of this and looking for - // overlapping live ranges that are NOT defined as copies. If these exist, we - // cannot coallesce. - - LiveInterval::iterator LHSIt = LHS.begin(), LHSEnd = LHS.end(); - LiveInterval::iterator RHSIt = RHS.begin(), RHSEnd = RHS.end(); - - if (LHSIt->start < RHSIt->start) { - LHSIt = std::upper_bound(LHSIt, LHSEnd, RHSIt->start); - if (LHSIt != LHS.begin()) --LHSIt; - } else if (RHSIt->start < LHSIt->start) { - RHSIt = std::upper_bound(RHSIt, RHSEnd, LHSIt->start); - if (RHSIt != RHS.begin()) --RHSIt; +/// 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); } - - SmallVector EliminatedLHSVals; - - while (1) { - // Determine if these live intervals overlap. - bool Overlaps = false; - if (LHSIt->start <= RHSIt->start) - Overlaps = LHSIt->end > RHSIt->start; - else - Overlaps = RHSIt->end > LHSIt->start; - - // If the live intervals overlap, there are two interesting cases: if the - // LHS interval is defined by a copy from the RHS, it's ok and we record - // that the LHS value # is the same as the RHS. If it's not, then we cannot - // coallesce these live ranges and we bail out. - if (Overlaps) { - // If we haven't already recorded that this value # is safe, check it. - if (!InVector(LHSIt->ValId, EliminatedLHSVals)) { - // Copy from the RHS? - unsigned SrcReg = LHS.getSrcRegForValNum(LHSIt->ValId); - if (rep(SrcReg) != RHS.reg) - return false; // Nope, bail out. - - EliminatedLHSVals.push_back(LHSIt->ValId); - } - - // We know this entire LHS live range is okay, so skip it now. - if (++LHSIt == LHSEnd) break; +} + +/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions +/// for addIntervalsForSpills to rewrite uses / defs for the given live range. +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, + const TargetRegisterClass* rc, + SmallVector &ReMatIds, + 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); + if (!mop.isRegister()) + continue; + unsigned Reg = mop.getReg(); + unsigned RegI = Reg; + if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) + continue; + if (Reg != li.reg) continue; - } - - if (LHSIt->end < RHSIt->end) { - if (++LHSIt == LHSEnd) break; - } else { - // One interesting case to check here. It's possible that we have - // something like "X3 = Y" which defines a new value number in the LHS, - // and is the last use of this liverange of the RHS. In this case, we - // want to notice this copy (so that it gets coallesced away) even though - // the live ranges don't actually overlap. - if (LHSIt->start == RHSIt->end) { - if (InVector(LHSIt->ValId, EliminatedLHSVals)) { - // We already know that this value number is going to be merged in - // if coallescing succeeds. Just skip the liverange. - if (++LHSIt == LHSEnd) break; - } else { - // Otherwise, if this is a copy from the RHS, mark it as being merged - // in. - if (rep(LHS.getSrcRegForValNum(LHSIt->ValId)) == RHS.reg) { - EliminatedLHSVals.push_back(LHSIt->ValId); - // We know this entire LHS live range is okay, so skip it now. - if (++LHSIt == LHSEnd) break; - } - } + bool TryFold = !DefIsReMat; + 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(); + break; } - - if (++RHSIt == RHSEnd) break; - } - } - - // If we got here, we know that the coallescing will be successful and that - // the value numbers in EliminatedLHSVals will all be merged together. Since - // the most common case is that EliminatedLHSVals has a single number, we - // optimize for it: if there is more than one value, we merge them all into - // the lowest numbered one, then handle the interval as if we were merging - // with one value number. - unsigned LHSValNo; - if (EliminatedLHSVals.size() > 1) { - // Loop through all the equal value numbers merging them into the smallest - // one. - unsigned Smallest = EliminatedLHSVals[0]; - for (unsigned i = 1, e = EliminatedLHSVals.size(); i != e; ++i) { - if (EliminatedLHSVals[i] < Smallest) { - // Merge the current notion of the smallest into the smaller one. - LHS.MergeValueNumberInto(Smallest, EliminatedLHSVals[i]); - Smallest = EliminatedLHSVals[i]; - } else { - // Merge into the smallest. - LHS.MergeValueNumberInto(EliminatedLHSVals[i], Smallest); + + // 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 = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); + if (isLoad) { + // Try fold loads (from stack slot, constant pool, etc.) into uses. + FoldSS = isLoadSS; + FoldSlot = LdSlot; } } - LHSValNo = Smallest; - } else { - assert(!EliminatedLHSVals.empty() && "No copies from the RHS?"); - LHSValNo = EliminatedLHSVals[0]; - } - - // Okay, now that there is a single LHS value number that we're merging the - // RHS into, update the value number info for the LHS to indicate that the - // value number is defined where the RHS value number was. - LHS.setValueNumberInfo(LHSValNo, RHS.getValNumInfo(0)); - - // Okay, the final step is to loop over the RHS live intervals, adding them to - // the LHS. - LHS.MergeRangesInAsValue(RHS, LHSValNo); - LHS.weight += RHS.weight; - if (RHS.preference && !LHS.preference) - LHS.preference = RHS.preference; - - return true; -} -/// JoinIntervals - Attempt to join these two intervals. On failure, this -/// returns false. Otherwise, if one of the intervals being joined is a -/// physreg, this method always canonicalizes LHS to be it. The output -/// "RHS" will not have been modified, so we can use this information -/// below to update aliases. -bool LiveIntervals::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { - // Compute the final value assignment, assuming that the live ranges can be - // coallesced. - SmallVector LHSValNoAssignments; - SmallVector RHSValNoAssignments; - SmallVector, 16> ValueNumberInfo; - - // If a live interval is a physical register, conservatively check if any - // of its sub-registers is overlapping the live interval of the virtual - // register. If so, do not coalesce. - if (MRegisterInfo::isPhysicalRegister(LHS.reg) && - *mri_->getSubRegisters(LHS.reg)) { - for (const unsigned* SR = mri_->getSubRegisters(LHS.reg); *SR; ++SR) - if (hasInterval(*SR) && RHS.overlaps(getInterval(*SR))) { - DOUT << "Interfere with sub-register "; - DEBUG(getInterval(*SR).print(DOUT, mri_)); - return false; - } - } else if (MRegisterInfo::isPhysicalRegister(RHS.reg) && - *mri_->getSubRegisters(RHS.reg)) { - for (const unsigned* SR = mri_->getSubRegisters(RHS.reg); *SR; ++SR) - if (hasInterval(*SR) && LHS.overlaps(getInterval(*SR))) { - DOUT << "Interfere with sub-register "; - DEBUG(getInterval(*SR).print(DOUT, mri_)); - return false; + // 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: + // + // 1. If the instr reads the same spilled vreg multiple times, we + // want to reuse the NewVReg. + // 2. If the instr is a two-addr instruction, we are required to + // keep the src/dst regs pinned. + // + // 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) { + const MachineOperand &MOj = MI->getOperand(j); + if (!MOj.isRegister()) + continue; + unsigned RegJ = MOj.getReg(); + if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) + continue; + if (RegJ == RegI) { + Ops.push_back(j); + HasUse |= MOj.isUse(); + HasDef |= MOj.isDef(); } - } - - // Compute ultimate value numbers for the LHS and RHS values. - if (RHS.containsOneValue()) { - // Copies from a liveinterval with a single value are simple to handle and - // very common, handle the special case here. This is important, because - // often RHS is small and LHS is large (e.g. a physreg). - - // Find out if the RHS is defined as a copy from some value in the LHS. - int RHSValID = -1; - std::pair RHSValNoInfo; - unsigned RHSSrcReg = RHS.getSrcRegForValNum(0); - if ((RHSSrcReg == 0 || rep(RHSSrcReg) != LHS.reg)) { - // If RHS is not defined as a copy from the LHS, we can use simpler and - // faster checks to see if the live ranges are coallescable. This joiner - // can't swap the LHS/RHS intervals though. - if (!MRegisterInfo::isPhysicalRegister(RHS.reg)) { - return SimpleJoin(LHS, RHS); + } + + // 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 { - RHSValNoInfo = RHS.getValNumInfo(0); + // We'll try to fold it later if it's profitable. + CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); } - } else { - // It was defined as a copy from the LHS, find out what value # it is. - unsigned ValInst = RHS.getInstForValNum(0); - RHSValID = LHS.getLiveRangeContaining(ValInst-1)->ValId; - RHSValNoInfo = LHS.getValNumInfo(RHSValID); } - - LHSValNoAssignments.resize(LHS.getNumValNums(), -1); - RHSValNoAssignments.resize(RHS.getNumValNums(), -1); - ValueNumberInfo.resize(LHS.getNumValNums()); - - // Okay, *all* of the values in LHS that are defined as a copy from RHS - // should now get updated. - for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { - if (unsigned LHSSrcReg = LHS.getSrcRegForValNum(VN)) { - if (rep(LHSSrcReg) != RHS.reg) { - // If this is not a copy from the RHS, its value number will be - // unmodified by the coallescing. - ValueNumberInfo[VN] = LHS.getValNumInfo(VN); - LHSValNoAssignments[VN] = VN; - } else if (RHSValID == -1) { - // Otherwise, it is a copy from the RHS, and we don't already have a - // value# for it. Keep the current value number, but remember it. - LHSValNoAssignments[VN] = RHSValID = VN; - ValueNumberInfo[VN] = RHSValNoInfo; + + // 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[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { + // Each valnum may have its own remat id. + ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); } else { - // Otherwise, use the specified value #. - LHSValNoAssignments[VN] = RHSValID; - if (VN != (unsigned)RHSValID) - ValueNumberInfo[VN].first = ~1U; - else - ValueNumberInfo[VN] = RHSValNoInfo; + vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); + } + if (!CanDelete || (HasUse && HasDef)) { + // If this is a two-addr instruction then its use operands are + // rematerializable but its def is not. It should be assigned a + // stack slot. + vrm.assignVirt2StackSlot(NewVReg, Slot); } } else { - ValueNumberInfo[VN] = LHS.getValNumInfo(VN); - LHSValNoAssignments[VN] = VN; + 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); } - - assert(RHSValID != -1 && "Didn't find value #?"); - RHSValNoAssignments[0] = RHSValID; - - } else { - // Loop over the value numbers of the LHS, seeing if any are defined from - // the RHS. - SmallVector LHSValsDefinedFromRHS; - LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), -1); - for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { - unsigned ValSrcReg = LHS.getSrcRegForValNum(VN); - if (ValSrcReg == 0) // Src not defined by a copy? - continue; - - // DstReg is known to be a register in the LHS interval. If the src is - // from the RHS interval, we can use its value #. - if (rep(ValSrcReg) != RHS.reg) - continue; - - // Figure out the value # from the RHS. - unsigned ValInst = LHS.getInstForValNum(VN); - LHSValsDefinedFromRHS[VN] = RHS.getLiveRangeContaining(ValInst-1)->ValId; - } - - // Loop over the value numbers of the RHS, seeing if any are defined from - // the LHS. - SmallVector RHSValsDefinedFromLHS; - RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), -1); - for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { - unsigned ValSrcReg = RHS.getSrcRegForValNum(VN); - if (ValSrcReg == 0) // Src not defined by a copy? - continue; - - // DstReg is known to be a register in the RHS interval. If the src is - // from the LHS interval, we can use its value #. - if (rep(ValSrcReg) != LHS.reg) - continue; - - // Figure out the value # from the LHS. - unsigned ValInst = RHS.getInstForValNum(VN); - RHSValsDefinedFromLHS[VN] = LHS.getLiveRangeContaining(ValInst-1)->ValId; - } - - LHSValNoAssignments.resize(LHS.getNumValNums(), -1); - RHSValNoAssignments.resize(RHS.getNumValNums(), -1); - ValueNumberInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); - - for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { - if (LHSValNoAssignments[VN] >= 0 || LHS.getInstForValNum(VN) == ~2U) - continue; - ComputeUltimateVN(VN, ValueNumberInfo, - LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, - LHSValNoAssignments, RHSValNoAssignments, LHS, RHS); + + // 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); + MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); + if (TrySplit) + vrm.setIsSplitFromReg(NewVReg, li.reg); } - for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { - if (RHSValNoAssignments[VN] >= 0 || RHS.getInstForValNum(VN) == ~2U) - continue; - // If this value number isn't a copy from the LHS, it's a new number. - if (RHSValsDefinedFromLHS[VN] == -1) { - ValueNumberInfo.push_back(RHS.getValNumInfo(VN)); - RHSValNoAssignments[VN] = ValueNumberInfo.size()-1; - continue; + + if (HasUse) { + if (CreatedNewVReg) { + LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, + nI.getNextValue(~0U, 0, VNInfoAllocator)); + DOUT << " +" << LR; + nI.addRange(LR); + } else { + // Extend the split live interval to this def / use. + unsigned End = getUseIndex(index)+1; + LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, + nI.getValNumInfo(nI.getNumValNums()-1)); + DOUT << " +" << LR; + nI.addRange(LR); } - - ComputeUltimateVN(VN, ValueNumberInfo, - RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, - RHSValNoAssignments, LHSValNoAssignments, RHS, LHS); } + if (HasDef) { + LiveRange LR(getDefIndex(index), getStoreIndex(index), + nI.getNextValue(~0U, 0, VNInfoAllocator)); + DOUT << " +" << LR; + nI.addRange(LR); + } + + DOUT << "\t\t\t\tAdded new interval: "; + nI.print(DOUT, tri_); + DOUT << '\n'; } - - // Armed with the mappings of LHS/RHS values to ultimate values, walk the - // interval lists to see if these intervals are coallescable. - LiveInterval::const_iterator I = LHS.begin(); - LiveInterval::const_iterator IE = LHS.end(); - LiveInterval::const_iterator J = RHS.begin(); - LiveInterval::const_iterator JE = RHS.end(); - - // Skip ahead until the first place of potential sharing. - if (I->start < J->start) { - I = std::upper_bound(I, IE, J->start); - if (I != LHS.begin()) --I; - } else if (J->start < I->start) { - J = std::upper_bound(J, JE, I->start); - if (J != RHS.begin()) --J; + return CanFold; +} +bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, + const VNInfo *VNI, + MachineBasicBlock *MBB, unsigned Idx) const { + unsigned End = getMBBEndIdx(MBB); + for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { + unsigned KillIdx = VNI->kills[j]; + if (KillIdx > Idx && KillIdx < End) + return true; } - - while (1) { - // Determine if these two live ranges overlap. - bool Overlaps; - if (I->start < J->start) { - Overlaps = I->end > J->start; - } else { - Overlaps = J->end > I->start; + 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; } + }; +} - // If so, check value # info to determine if they are really different. - if (Overlaps) { - // If the live range overlap will map to the same value number in the - // result liverange, we can still coallesce them. If not, we can't. - if (LHSValNoAssignments[I->ValId] != RHSValNoAssignments[J->ValId]) - return false; +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, + const TargetRegisterClass* rc, + SmallVector &ReMatIds, + const MachineLoopInfo *loopInfo, + BitVector &SpillMBBs, + std::map > &SpillIdxes, + BitVector &RestoreMBBs, + std::map > &RestoreIdxes, + std::map &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 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; } - - if (I->end < J->end) { - ++I; - if (I == IE) break; - } else { - ++J; - if (J == JE) break; + MachineBasicBlock *MBB = MI->getParent(); + + 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; } - } - // If we get here, we know that we can coallesce the live ranges. Ask the - // intervals to coallesce themselves now. - LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], - ValueNumberInfo); - return true; -} + 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; + } + NewVReg = ThisVReg; + + 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, SSWeight); + if (!HasDef && !HasUse) + continue; -namespace { - // DepthMBBCompare - Comparison predicate that sort first based on the loop - // depth of the basic block (the unsigned), and then on the MBB number. - struct DepthMBBCompare { - typedef std::pair DepthMBBPair; - bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { - if (LHS.first > RHS.first) return true; // Deeper loops first - return LHS.first == RHS.first && - LHS.second->getNumber() < RHS.second->getNumber(); + AllCanFold &= CanFold; + + // Update weight of spill interval. + LiveInterval &nI = getOrCreateInterval(NewVReg); + 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. + if (HasDef) { + if (MI != ReMatOrigDefMI || !CanDelete) { + bool HasKill = false; + if (!HasUse) + 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 = li.findDefinedVNInfo(getDefIndex(index)); + if (VNI) + HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); + } + std::map >::iterator SII = + SpillIdxes.find(MBBId); + if (!HasKill) { + 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). + SRInfo &Info = SII->second.back(); + Info.index = index; + Info.canFold = !HasUse; + } + SpillMBBs.set(MBBId); + } 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 = + 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 = + 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 + // use and there isn't another use later in the MBB. + RII->second.back().canFold = false; + else if (IsNew) { + // Only need a reload if there isn't an earlier def / use. + 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); + 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; +} -void LiveIntervals::CopyCoallesceInMBB(MachineBasicBlock *MBB, - std::vector *TryAgain, bool PhysOnly) { - DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; - - for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); - MII != E;) { - MachineInstr *Inst = MII++; - - // If this isn't a copy, we can't join intervals. - unsigned SrcReg, DstReg; - if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg)) continue; - - if (TryAgain && !JoinCopy(Inst, SrcReg, DstReg, PhysOnly)) - TryAgain->push_back(getCopyRec(Inst, SrcReg, DstReg)); +/// 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); + } + } } } -void LiveIntervals::joinIntervals() { - DOUT << "********** JOINING INTERVALS ***********\n"; +std::vector LiveIntervals:: +addIntervalsForSpills(const LiveInterval &li, + 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(); - JoinedLIs.resize(getNumIntervals()); - JoinedLIs.reset(); + assert(li.weight != HUGE_VALF && + "attempt to spill already spilled interval!"); - std::vector TryAgainList; - const LoopInfo &LI = getAnalysis(); - if (LI.begin() == LI.end()) { - // If there are no loops in the function, join intervals in function order. - for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); - I != E; ++I) - CopyCoallesceInMBB(I, &TryAgainList); - } else { - // Otherwise, join intervals in inner loops before other intervals. - // Unfortunately we can't just iterate over loop hierarchy here because - // there may be more MBB's than BB's. Collect MBB's for sorting. - - // Join intervals in the function prolog first. We want to join physical - // registers with virtual registers before the intervals got too long. - std::vector > MBBs; - for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); I != E;++I) - MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I)); - - // Sort by loop depth. - std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); - - // Finally, join intervals in loop nest order. - for (unsigned i = 0, e = MBBs.size(); i != e; ++i) - CopyCoallesceInMBB(MBBs[i].second, NULL, true); - for (unsigned i = 0, e = MBBs.size(); i != e; ++i) - CopyCoallesceInMBB(MBBs[i].second, &TryAgainList, false); - } - - // Joining intervals can allow other intervals to be joined. Iteratively join - // until we make no progress. - bool ProgressMade = true; - while (ProgressMade) { - ProgressMade = false; - - for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) { - CopyRec &TheCopy = TryAgainList[i]; - if (TheCopy.MI && - JoinCopy(TheCopy.MI, TheCopy.SrcReg, TheCopy.DstReg)) { - TheCopy.MI = 0; // Mark this one as done. - ProgressMade = true; + DOUT << "\t\t\t\tadding intervals for spills for interval: "; + 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; + BitVector RestoreMBBs(mf_->getNumBlockIDs()); + std::map > RestoreIdxes; + std::map MBBVRegsMap; + std::vector NewLIs; + const TargetRegisterClass* rc = mri_->getRegClass(li.reg); + + unsigned NumValNums = li.getNumValNums(); + SmallVector ReMatDefs; + ReMatDefs.resize(NumValNums, NULL); + SmallVector ReMatOrigDefs; + ReMatOrigDefs.resize(NumValNums, NULL); + SmallVector ReMatIds; + ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); + BitVector ReMatDelete(NumValNums); + unsigned Slot = VirtRegMap::MAX_STACK_SLOT; + + // Spilling a split live interval. It cannot be split any further. Also, + // 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); + MachineInstr *ReMatDefMI = DefIsReMat ? + vrm.getReMaterializedMI(li.reg) : NULL; + int LdSlot = 0; + bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); + bool isLoad = isLoadSS || + (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad())); + bool IsFirstRange = true; + for (LiveInterval::Ranges::const_iterator + I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { + // If this is a split live interval with multiple ranges, it means there + // 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, rc, ReMatIds, loopInfo, + SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, + 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, SSWeight); } + IsFirstRange = false; } + + SSWeight = 0.0f; // Already accounted for when split. + handleSpilledImpDefs(li, vrm, rc, NewLIs); + return NewLIs; } - // Some live range has been lengthened due to colaescing, eliminate the - // unnecessary kills. - int RegNum = JoinedLIs.find_first(); - while (RegNum != -1) { - unsigned Reg = RegNum + MRegisterInfo::FirstVirtualRegister; - unsigned repReg = rep(Reg); - LiveInterval &LI = getInterval(repReg); - LiveVariables::VarInfo& svi = lv_->getVarInfo(Reg); - for (unsigned i = 0, e = svi.Kills.size(); i != e; ++i) { - MachineInstr *Kill = svi.Kills[i]; - // Suppose vr1 = op vr2, x - // and vr1 and vr2 are coalesced. vr2 should still be marked kill - // unless it is a two-address operand. - if (isRemoved(Kill) || hasRegisterDef(Kill, repReg)) - continue; - if (LI.liveAt(getInstructionIndex(Kill) + InstrSlots::NUM)) - unsetRegisterKill(Kill, repReg); + bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); + if (SplitLimit != -1 && (int)numSplits >= SplitLimit) + TrySplit = false; + if (TrySplit) + ++numSplits; + bool NeedStackSlot = false; + for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); + i != e; ++i) { + const VNInfo *VNI = *i; + unsigned VN = VNI->id; + unsigned DefIdx = VNI->def; + if (DefIdx == ~1U) + continue; // Dead val#. + // Is the def for the val# rematerializable? + MachineInstr *ReMatDefMI = (DefIdx == ~0u) + ? 0 : getInstructionFromIndex(DefIdx); + 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(); + + bool CanDelete = true; + if (VNI->hasPHIKill) { + // A kill is a phi node, not all of its uses can be rematerialized. + // It must not be deleted. + 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 { + // Need a stack slot if there is any live range where uses cannot be + // rematerialized. + NeedStackSlot = true; } - RegNum = JoinedLIs.find_next(RegNum); } - - DOUT << "*** Register mapping ***\n"; - for (int i = 0, e = r2rMap_.size(); i != e; ++i) - if (r2rMap_[i]) { - DOUT << " reg " << i << " -> "; - DEBUG(printRegName(r2rMap_[i])); - DOUT << "\n"; - } -} -/// Return true if the two specified registers belong to different register -/// classes. The registers may be either phys or virt regs. -bool LiveIntervals::differingRegisterClasses(unsigned RegA, - unsigned RegB) const { + // One stack slot per live interval. + if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) + Slot = vrm.assignVirt2StackSlot(li.reg); - // Get the register classes for the first reg. - if (MRegisterInfo::isPhysicalRegister(RegA)) { - assert(MRegisterInfo::isVirtualRegister(RegB) && - "Shouldn't consider two physregs!"); - return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA); + // Create new intervals and rewrite defs and uses. + for (LiveInterval::Ranges::const_iterator + I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { + MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; + MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; + bool DefIsReMat = ReMatDefMI != NULL; + bool CanDelete = ReMatDelete[I->valno->id]; + int LdSlot = 0; + bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); + bool isLoad = isLoadSS || + (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad()); + rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, + Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, + CanDelete, vrm, rc, ReMatIds, loopInfo, + SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, + MBBVRegsMap, NewLIs, SSWeight); } - // Compare against the regclass for the second reg. - const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA); - if (MRegisterInfo::isVirtualRegister(RegB)) - return RegClass != mf_->getSSARegMap()->getRegClass(RegB); - else - return !RegClass->contains(RegB); -} + // Insert spills / restores if we are splitting. + if (!TrySplit) { + handleSpilledImpDefs(li, vrm, rc, NewLIs); + return NewLIs; + } -/// lastRegisterUse - Returns the last use of the specific register between -/// cycles Start and End. It also returns the use operand by reference. It -/// returns NULL if there are no uses. -MachineInstr * -LiveIntervals::lastRegisterUse(unsigned Reg, unsigned Start, unsigned End, - MachineOperand *&MOU) { - int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM; - int s = Start; - while (e >= s) { - // Skip deleted instructions - MachineInstr *MI = getInstructionFromIndex(e); - while ((e - InstrSlots::NUM) >= s && !MI) { - e -= InstrSlots::NUM; - MI = getInstructionFromIndex(e); + 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); + 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; + + 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; + } + FoundUse = true; + } + } + // Fold the store into the def if possible. + 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); + } + 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); + } + + // Update spill slot weight. + if (!isReMat) + SSWeight += getSpillWeight(true, false, loopDepth); + } + Id = SpillMBBs.find_next(Id); } - if (e < s || MI == NULL) - return NULL; - - for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isReg() && MO.isUse() && MO.getReg() && - mri_->regsOverlap(rep(MO.getReg()), Reg)) { - MOU = &MO; - return MI; + } + + 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); + 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()) { + // If this restore were to be folded, it would have been folded + // already. + CanFold = false; + break; + } + Ops.push_back(j); + } } + + // Fold the load into the use if possible. + 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->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 (Folded) + 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); + } - e -= InstrSlots::NUM; + // 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 NULL; + 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; +} -/// findDefOperand - Returns the MachineOperand that is a def of the specific -/// register. It returns NULL if the def is not found. -MachineOperand *LiveIntervals::findDefOperand(MachineInstr *MI, unsigned Reg) { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isReg() && MO.isDef() && - mri_->regsOverlap(rep(MO.getReg()), Reg)) - return &MO; +/// 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 NULL; + return BestReg; } -/// unsetRegisterKill - Unset IsKill property of all uses of specific register -/// of the specific instruction. -void LiveIntervals::unsetRegisterKill(MachineInstr *MI, unsigned Reg) { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isReg() && MO.isUse() && MO.isKill() && MO.getReg() && - mri_->regsOverlap(rep(MO.getReg()), Reg)) - MO.unsetIsKill(); +/// 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; } -/// hasRegisterDef - True if the instruction defines the specific register. -/// -bool LiveIntervals::hasRegisterDef(MachineInstr *MI, unsigned Reg) { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isReg() && MO.isDef() && - mri_->regsOverlap(rep(MO.getReg()), Reg)) - return true; +/// 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); + } + } } - return false; } -LiveInterval LiveIntervals::createInterval(unsigned reg) { - float Weight = MRegisterInfo::isPhysicalRegister(reg) ? - HUGE_VALF : 0.0F; - return LiveInterval(reg, Weight); +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; }