X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=8cfc5871dcc68708f0151b3535e1c248b7ea2e30;hb=2d87734a8ffad5933edbbc15a3b643df1e8a767e;hp=5f010a6070a48e401af3371b31a29a7cd1d28bd7;hpb=f21f0205b5dec61f165518887f54e01ab5aab13c;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 5f010a6070a..8cfc5871dcc 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -34,30 +34,21 @@ #include "llvm/ADT/STLExtras.h" #include #include -#include using namespace llvm; +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"); - static Statistic<> numIntervals - ("liveintervals", "Number of original intervals"); - - static Statistic<> numIntervalsAfter - ("liveintervals", "Number of intervals after coalescing"); - - static Statistic<> numJoins - ("liveintervals", "Number of interval joins performed"); - - static Statistic<> numPeep - ("liveintervals", "Number of identity moves eliminated after coalescing"); - - static Statistic<> numFolded - ("liveintervals", "Number of loads/stores folded into instructions"); - static cl::opt EnableJoining("join-liveintervals", - cl::desc("Join compatible live intervals"), + cl::desc("Coallesce copies (default=true)"), cl::init(true)); } @@ -75,6 +66,7 @@ void LiveIntervals::releaseMemory() { i2miMap_.clear(); r2iMap_.clear(); r2rMap_.clear(); + JoinedLIs.clear(); } @@ -98,50 +90,22 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { allocatableRegs_ = mri_->getAllocatableSet(fn); r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); - // If this function has any live ins, insert a dummy instruction at the - // beginning of the function that we will pretend "defines" the values. This - // is to make the interval analysis simpler by providing a number. - if (fn.livein_begin() != fn.livein_end()) { - unsigned FirstLiveIn = fn.livein_begin()->first; - - // Find a reg class that contains this live in. - const TargetRegisterClass *RC = 0; - for (MRegisterInfo::regclass_iterator RCI = mri_->regclass_begin(), - E = mri_->regclass_end(); RCI != E; ++RCI) - if ((*RCI)->contains(FirstLiveIn)) { - RC = *RCI; - break; - } - - MachineInstr *OldFirstMI = fn.begin()->begin(); - mri_->copyRegToReg(*fn.begin(), fn.begin()->begin(), - FirstLiveIn, FirstLiveIn, RC); - assert(OldFirstMI != fn.begin()->begin() && - "copyRetToReg didn't insert anything!"); - } - - // number MachineInstrs - unsigned miIndex = 0; - for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); - mbb != mbbEnd; ++mbb) - for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); - mi != miEnd; ++mi) { - bool inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; + // Number MachineInstrs and MachineBasicBlocks. + // Initialize MBB indexes to a sentinal. + MBB2IdxMap.resize(mf_->getNumBlockIDs(), ~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; + + for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); + I != E; ++I) { + bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; assert(inserted && "multiple MachineInstr -> index mappings"); - i2miMap_.push_back(mi); - miIndex += InstrSlots::NUM; - } - - // Note intervals due to live-in values. - if (fn.livein_begin() != fn.livein_end()) { - MachineBasicBlock *Entry = fn.begin(); - for (MachineFunction::livein_iterator I = fn.livein_begin(), - E = fn.livein_end(); I != E; ++I) { - handlePhysicalRegisterDef(Entry, Entry->begin(), - getOrCreateInterval(I->first), 0); - for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS) - handlePhysicalRegisterDef(Entry, Entry->begin(), - getOrCreateInterval(*AS), 0); + i2miMap_.push_back(I); + MIIndex += InstrSlots::NUM; } } @@ -149,20 +113,21 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { numIntervals += getNumIntervals(); - DEBUG(std::cerr << "********** INTERVALS **********\n"; - for (iterator I = begin(), E = end(); I != E; ++I) { - I->second.print(std::cerr, mri_); - std::cerr << "\n"; - }); + DOUT << "********** INTERVALS **********\n"; + for (iterator I = begin(), E = end(); I != E; ++I) { + I->second.print(DOUT, mri_); + DOUT << "\n"; + } - // join intervals if requested + // Join (coallesce) intervals if requested. if (EnableJoining) joinIntervals(); numIntervalsAfter += getNumIntervals(); + // perform a final pass over the instructions and compute spill - // weights, coalesce virtual registers and remove identity moves - const LoopInfo& loopInfo = getAnalysis(); + // weights, coalesce virtual registers and remove identity moves. + const LoopInfo &loopInfo = getAnalysis(); for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); mbbi != mbbe; ++mbbi) { @@ -176,14 +141,23 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { if (tii_->isMoveInstr(*mii, srcReg, dstReg) && (RegRep = rep(srcReg)) == rep(dstReg)) { // remove from def list - LiveInterval &interval = getOrCreateInterval(RegRep); + 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 { - for (unsigned i = 0; i < mii->getNumOperands(); ++i) { - const MachineOperand& mop = mii->getOperand(i); + } else { + 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 @@ -191,8 +165,14 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { mii->getOperand(i).setReg(reg); LiveInterval &RegInt = getInterval(reg); - RegInt.weight += - (mop.isUse() + mop.isDef()) * pow(10.0F, (int)loopDepth); + 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; } } ++mii; @@ -201,13 +181,22 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { } for (iterator I = begin(), E = end(); I != E; ++I) { - LiveInterval &li = I->second; - if (MRegisterInfo::isVirtualRegister(li.reg)) { + 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 = float(HUGE_VAL); + if (isZeroLengthInterval(&LI)) + LI.weight = HUGE_VALF; + + // 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. + unsigned Size = 0; + for (LiveInterval::iterator II = LI.begin(), E = LI.end(); II != E;++II) + Size += II->end - II->start; + + LI.weight /= Size; } } @@ -219,8 +208,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(std::cerr, mri_); - std::cerr << "\n"; + I->second.print(DOUT, mri_); + DOUT << "\n"; } O << "********** MACHINEINSTRS **********\n"; @@ -234,6 +223,55 @@ 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 @@ -242,11 +280,12 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { std::vector added; - assert(li.weight != HUGE_VAL && + assert(li.weight != HUGE_VALF && "attempt to spill already spilled interval!"); - DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: "; - li.print(std::cerr, mri_); std::cerr << '\n'); + DOUT << "\t\t\t\tadding intervals for spills for interval: "; + li.print(DOUT, mri_); + DOUT << '\n'; const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); @@ -262,23 +301,13 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { MachineInstr *MI = getInstructionFromIndex(index); - // NewRegLiveIn - This instruction might have multiple uses of the spilled - // register. In this case, for the first use, keep track of the new vreg - // that we reload it into. If we see a second use, reuse this vreg - // instead of creating live ranges for two reloads. - unsigned NewRegLiveIn = 0; - - for_operand: + RestartInstruction: for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& mop = MI->getOperand(i); if (mop.isRegister() && mop.getReg() == li.reg) { - if (NewRegLiveIn && mop.isUse()) { - // We already emitted a reload of this value, reuse it for - // subsequent operands. - MI->getOperand(i).setReg(NewRegLiveIn); - DEBUG(std::cerr << "\t\t\t\treused reload into reg" << NewRegLiveIn - << " for operand #" << i << '\n'); - } else if (MachineInstr* fmi = mri_->foldMemoryOperand(MI, i, slot)) { + 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_) @@ -292,50 +321,70 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { ++numFolded; // Folding the load/store can completely change the instruction in // unpredictable ways, rescan it from the beginning. - goto for_operand; + goto RestartInstruction; } else { - // This is tricky. We need to add information in the interval about - // the spill code so we have to use our extra load/store slots. + // 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. // - // If we have a use we are going to have a load so we start the - // interval from the load slot onwards. Otherwise we start from the - // def slot. - unsigned start = (mop.isUse() ? - getLoadIndex(index) : - getDefIndex(index)); - // If we have a def we are going to have a store right after it so - // we end the interval after the use of the next - // instruction. Otherwise we end after the use of this instruction. - unsigned end = 1 + (mop.isDef() ? - getStoreIndex(index) : - getUseIndex(index)); + // 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 - NewRegLiveIn = mf_->getSSARegMap()->createVirtualRegister(rc); - MI->getOperand(i).setReg(NewRegLiveIn); vrm.grow(); - vrm.assignVirt2StackSlot(NewRegLiveIn, slot); - LiveInterval& nI = getOrCreateInterval(NewRegLiveIn); + 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 = float(HUGE_VAL); - LiveRange LR(start, end, nI.getNextValue(~0U, 0)); - DEBUG(std::cerr << " +" << LR); - nI.addRange(LR); + 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(NewRegLiveIn, MI); + lv_->addVirtualRegisterKilled(NewVReg, MI); - // If this is a live in, reuse it for subsequent live-ins. If it's - // a def, we can't do this. - if (!mop.isUse()) NewRegLiveIn = 0; - - DEBUG(std::cerr << "\t\t\t\tadded new interval: "; - nI.print(std::cerr, mri_); std::cerr << '\n'); + DOUT << "\t\t\t\tadded new interval: "; + nI.print(DOUT, mri_); + DOUT << '\n'; } } } @@ -347,15 +396,35 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { void LiveIntervals::printRegName(unsigned reg) const { if (MRegisterInfo::isPhysicalRegister(reg)) - std::cerr << mri_->getName(reg); + cerr << mri_->getName(reg); else - std::cerr << "%reg" << reg; + 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, LiveInterval &interval) { - DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); + DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); // Virtual registers may be defined multiple times (due to phi @@ -363,8 +432,17 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // 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(getInstructionIndex(mi)); + unsigned defIndex = getDefIndex(MIIdx); unsigned ValNum; unsigned SrcReg, DstReg; @@ -391,11 +469,11 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // If the kill happens after the definition, we have an intra-block // live range. if (killIdx > defIndex) { - assert(vi.AliveBlocks.empty() && + assert(vi.AliveBlocks.none() && "Shouldn't be alive across any blocks!"); LiveRange LR(defIndex, killIdx, ValNum); interval.addRange(LR); - DEBUG(std::cerr << " +" << LR << "\n"); + DOUT << " +" << LR << "\n"; return; } } @@ -407,7 +485,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, LiveRange NewLR(defIndex, getInstructionIndex(&mbb->back()) + InstrSlots::NUM, ValNum); - DEBUG(std::cerr << " +" << NewLR); + DOUT << " +" << NewLR; interval.addRange(NewLR); // Iterate over all of the blocks that the variable is completely @@ -415,13 +493,13 @@ 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(getInstructionIndex(&mbb->front()), - getInstructionIndex(&mbb->back()) + InstrSlots::NUM, + MachineBasicBlock *MBB = mf_->getBlockNumbered(i); + if (!MBB->empty()) { + LiveRange LR(getMBBStartIdx(i), + getInstructionIndex(&MBB->back()) + InstrSlots::NUM, ValNum); interval.addRange(LR); - DEBUG(std::cerr << " +" << LR); + DOUT << " +" << LR; } } } @@ -430,28 +508,29 @@ 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]; - LiveRange LR(getInstructionIndex(Kill->getParent()->begin()), + LiveRange LR(getMBBStartIdx(Kill->getParent()), getUseIndex(getInstructionIndex(Kill))+1, ValNum); interval.addRange(LR); - DEBUG(std::cerr << " +" << LR); + 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 the first - // operand, and is a def-and-use. - if (mi->getOperand(0).isRegister() && - mi->getOperand(0).getReg() == interval.reg && - mi->getOperand(0).isDef() && mi->getOperand(0).isUse()) { + // 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 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)); - unsigned RedefIndex = getDefIndex(getInstructionIndex(mi)); + unsigned RedefIndex = getDefIndex(MIIdx); // Delete the initial value, which should be short and continuous, // because the 2-addr copy must be in the same MBB as the redef. @@ -471,7 +550,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // Add the new live interval which replaces the range for the input copy. LiveRange LR(DefIndex, RedefIndex, ValNo); - DEBUG(std::cerr << " replace range with " << LR); + DOUT << " replace range with " << LR; interval.addRange(LR); // If this redefinition is dead, we need to add a dummy unit live @@ -479,7 +558,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, if (lv_->RegisterDefIsDead(mi, interval.reg)) interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); - DEBUG(std::cerr << "RESULT: "; interval.print(std::cerr, mri_)); + DOUT << " RESULT: "; + interval.print(DOUT, mri_); } else { // Otherwise, this must be because of phi elimination. If this is the @@ -491,25 +571,25 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // Remove the old range that we now know has an incorrect number. MachineInstr *Killer = vi.Kills[0]; - unsigned Start = getInstructionIndex(Killer->getParent()->begin()); + unsigned Start = getMBBStartIdx(Killer->getParent()); unsigned End = getUseIndex(getInstructionIndex(Killer))+1; - DEBUG(std::cerr << "Removing [" << Start << "," << End << "] from: "; - interval.print(std::cerr, mri_); std::cerr << "\n"); + DOUT << " Removing [" << Start << "," << End << "] from: "; + interval.print(DOUT, mri_); DOUT << "\n"; interval.removeRange(Start, End); - DEBUG(std::cerr << "RESULT: "; interval.print(std::cerr, mri_)); + DOUT << " RESULT: "; interval.print(DOUT, mri_); // 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)); - DEBUG(std::cerr << " replace range with " << LR); + DOUT << " replace range with " << LR; interval.addRange(LR); - DEBUG(std::cerr << "RESULT: "; interval.print(std::cerr, mri_)); + DOUT << " RESULT: "; interval.print(DOUT, mri_); } // In the case of PHI elimination, each variable definition is only // live until the end of the block. We've already taken care of the // rest of the live range. - unsigned defIndex = getDefIndex(getInstructionIndex(mi)); + unsigned defIndex = getDefIndex(MIIdx); unsigned ValNum; unsigned SrcReg, DstReg; @@ -521,23 +601,23 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, LiveRange LR(defIndex, getInstructionIndex(&mbb->back()) + InstrSlots::NUM, ValNum); interval.addRange(LR); - DEBUG(std::cerr << " +" << LR); + DOUT << " +" << LR; } } - DEBUG(std::cerr << '\n'); + DOUT << '\n'; } void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator mi, + unsigned MIIdx, LiveInterval &interval, unsigned SrcReg) { // A physical register cannot be live across basic block, so its // lifetime must end somewhere in its defining basic block. - DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); - typedef LiveVariables::killed_iterator KillIter; + DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); - unsigned baseIndex = getInstructionIndex(mi); + unsigned baseIndex = MIIdx; unsigned start = getDefIndex(baseIndex); unsigned end = start; @@ -545,7 +625,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // the instruction defining it. Hence its interval is: // [defSlot(def), defSlot(def)+1) if (lv_->RegisterDefIsDead(mi, interval.reg)) { - DEBUG(std::cerr << " dead"); + DOUT << " dead"; end = getDefIndex(start) + 1; goto exit; } @@ -556,9 +636,17 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, while (++mi != MBB->end()) { baseIndex += InstrSlots::NUM; if (lv_->KillsRegister(mi, interval.reg)) { - DEBUG(std::cerr << " killed"); + DOUT << " killed"; end = getUseIndex(baseIndex) + 1; goto exit; + } else if (lv_->ModifiesRegister(mi, interval.reg)) { + // 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: + // [defSlot(def), defSlot(def)+1) + DOUT << " dead"; + end = getDefIndex(start) + 1; + goto exit; } } @@ -574,22 +662,61 @@ exit: LiveRange LR(start, end, interval.getNextValue(SrcReg != 0 ? start : ~0U, SrcReg)); interval.addRange(LR); - DEBUG(std::cerr << " +" << LR << '\n'); + DOUT << " +" << LR << '\n'; } void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI, + unsigned MIIdx, unsigned reg) { if (MRegisterInfo::isVirtualRegister(reg)) - handleVirtualRegisterDef(MBB, MI, getOrCreateInterval(reg)); + handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); else if (allocatableRegs_[reg]) { unsigned SrcReg, DstReg; if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) SrcReg = 0; - handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg), SrcReg); + handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg); for (const unsigned* AS = mri_->getAliasSet(reg); *AS; ++AS) - handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS), 0); + handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); + } +} + +void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, + unsigned MIIdx, + LiveInterval &interval) { + DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); + + // Look for kills, if it reaches a def before it's killed, then it shouldn't + // be considered a livein. + MachineBasicBlock::iterator mi = MBB->begin(); + unsigned baseIndex = MIIdx; + unsigned start = baseIndex; + unsigned end = start; + while (mi != MBB->end()) { + if (lv_->KillsRegister(mi, interval.reg)) { + DOUT << " killed"; + end = getUseIndex(baseIndex) + 1; + goto exit; + } else if (lv_->ModifiesRegister(mi, interval.reg)) { + // 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: + // [defSlot(def), defSlot(def)+1) + DOUT << " dead"; + end = getDefIndex(start) + 1; + goto exit; + } + + baseIndex += InstrSlots::NUM; + ++mi; } + +exit: + assert(start < end && "did not find end of interval?"); + + LiveRange LR(start, end, interval.getNextValue(~0U, 0)); + DOUT << " +" << LR << '\n'; + interval.addRange(LR); } /// computeIntervals - computes the live intervals for virtual @@ -597,36 +724,40 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, /// live interval is an interval [i, j) where 1 <= i <= j < N for /// which a variable is live void LiveIntervals::computeIntervals() { - DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n"); - DEBUG(std::cerr << "********** Function: " - << ((Value*)mf_->getFunction())->getName() << '\n'); - bool IgnoreFirstInstr = mf_->livein_begin() != mf_->livein_end(); - - for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); - I != E; ++I) { - MachineBasicBlock* mbb = I; - DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n"); - - MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); - if (IgnoreFirstInstr) { ++mi; IgnoreFirstInstr = false; } - for (; mi != miEnd; ++mi) { - const TargetInstrDescriptor& tid = - tm_->getInstrInfo()->get(mi->getOpcode()); - DEBUG(std::cerr << getInstructionIndex(mi) << "\t" << *mi); - - // handle implicit defs - if (tid.ImplicitDefs) { - for (const unsigned* id = tid.ImplicitDefs; *id; ++id) - handleRegisterDef(mbb, mi, *id); + DOUT << "********** COMPUTING LIVE INTERVALS **********\n" + << "********** Function: " + << ((Value*)mf_->getFunction())->getName() << '\n'; + // Track the index of the current machine instr. + unsigned MIIndex = 0; + for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); + MBBI != E; ++MBBI) { + MachineBasicBlock *MBB = MBBI; + DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; + + 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)); + for (const unsigned* AS = mri_->getAliasSet(*LI); *AS; ++AS) + handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS)); } + } + + for (; MI != miEnd; ++MI) { + DOUT << MIIndex << "\t" << *MI; - // handle explicit defs - for (int i = mi->getNumOperands() - 1; i >= 0; --i) { - MachineOperand& mop = mi->getOperand(i); + // Handle defs. + for (int i = MI->getNumOperands() - 1; i >= 0; --i) { + MachineOperand &MO = MI->getOperand(i); // handle register defs - build intervals - if (mop.isRegister() && mop.getReg() && mop.isDef()) - handleRegisterDef(mbb, mi, mop.getReg()); + if (MO.isRegister() && MO.getReg() && MO.isDef()) + handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); } + + MIIndex += InstrSlots::NUM; } } } @@ -694,7 +825,7 @@ bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, // IntB, we can merge them. if (ValLR+1 != BLR) return false; - DEBUG(std::cerr << "\nExtending: "; IntB.print(std::cerr, mri_)); + DOUT << "\nExtending: "; IntB.print(DOUT, mri_); // We are about to delete CopyMI, so need to remove it as the 'instruction // that defines this value #'. @@ -719,8 +850,14 @@ bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, // Okay, merge "B1" into the same value number as "B0". if (BValNo != ValLR->ValId) IntB.MergeValueNumberInto(BValNo, ValLR->ValId); - DEBUG(std::cerr << " result = "; IntB.print(std::cerr, mri_); - std::cerr << "\n"); + 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); @@ -729,7 +866,6 @@ bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, return true; } - /// 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 @@ -738,57 +874,174 @@ bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, /// it may be possible if other things get coallesced. bool LiveIntervals::JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned DstReg) { - - - DEBUG(std::cerr << getInstructionIndex(CopyMI) << '\t' << *CopyMI); - + DOUT << getInstructionIndex(CopyMI) << '\t' << *CopyMI; + // Get representative registers. - SrcReg = rep(SrcReg); - DstReg = rep(DstReg); + unsigned repSrcReg = rep(SrcReg); + unsigned repDstReg = rep(DstReg); // If they are already joined we continue. - if (SrcReg == DstReg) { - DEBUG(std::cerr << "\tCopy already coallesced.\n"); + if (repSrcReg == repDstReg) { + DOUT << "\tCopy already coallesced.\n"; return true; // Not coallescable. } // If they are both physical registers, we cannot join them. - if (MRegisterInfo::isPhysicalRegister(SrcReg) && - MRegisterInfo::isPhysicalRegister(DstReg)) { - DEBUG(std::cerr << "\tCan not coallesce physregs.\n"); + if (MRegisterInfo::isPhysicalRegister(repSrcReg) && + MRegisterInfo::isPhysicalRegister(repDstReg)) { + DOUT << "\tCan not coallesce physregs.\n"; return true; // Not coallescable. } // We only join virtual registers with allocatable physical registers. - if (MRegisterInfo::isPhysicalRegister(SrcReg) && !allocatableRegs_[SrcReg]){ - DEBUG(std::cerr << "\tSrc reg is unallocatable physreg.\n"); + if (MRegisterInfo::isPhysicalRegister(repSrcReg) && + !allocatableRegs_[repSrcReg]) { + DOUT << "\tSrc reg is unallocatable physreg.\n"; return true; // Not coallescable. } - if (MRegisterInfo::isPhysicalRegister(DstReg) && !allocatableRegs_[DstReg]){ - DEBUG(std::cerr << "\tDst reg is unallocatable physreg.\n"); + if (MRegisterInfo::isPhysicalRegister(repDstReg) && + !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(SrcReg, DstReg)) { - DEBUG(std::cerr << "\tSrc/Dest are different register classes.\n"); + if (differingRegisterClasses(repSrcReg, repDstReg)) { + DOUT << "\tSrc/Dest are different register classes.\n"; return true; // Not coallescable. } - LiveInterval &SrcInt = getInterval(SrcReg); - LiveInterval &DestInt = getInterval(DstReg); - assert(SrcInt.reg == SrcReg && DestInt.reg == DstReg && + LiveInterval &SrcInt = getInterval(repSrcReg); + LiveInterval &DestInt = getInterval(repDstReg); + assert(SrcInt.reg == repSrcReg && DestInt.reg == repDstReg && "Register mapping is horribly broken!"); - DEBUG(std::cerr << "\t\tInspecting "; SrcInt.print(std::cerr, mri_); - std::cerr << " and "; DestInt.print(std::cerr, mri_); - std::cerr << ": "); - + DOUT << "\t\tInspecting "; SrcInt.print(DOUT, mri_); + DOUT << " and "; DestInt.print(DOUT, mri_); + DOUT << ": "; + + // Check if it is necessary to propagate "isDead" property before intervals + // are joined. + MachineBasicBlock *CopyBB = CopyMI->getParent(); + 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; + } + } + } + } + + // 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() && MRegisterInfo::isPhysicalRegister(repSrcReg)) { + // Small function. No need to worry! + unsigned Threshold = allocatableRegs_.count() * 2; + if (r2iMap_.size() <= Threshold) + goto TryJoin; + + LiveVariables::VarInfo& dvi = lv_->getVarInfo(repDstReg); + // Is the value used in the current BB or any immediate successroe BB? + if (dvi.UsedBlocks[CopyBB->getNumber()]) + goto TryJoin; + for (MachineBasicBlock::succ_iterator SI = CopyBB->succ_begin(), + SE = CopyBB->succ_end(); SI != SE; ++SI) { + MachineBasicBlock *SuccMBB = *SI; + if (dvi.UsedBlocks[SuccMBB->getNumber()]) + goto TryJoin; + } + + // Ok, no use in this BB and no use in immediate successor BB's. Be really + // careful now! + // It's only used in one BB, forget about it! + if (dvi.UsedBlocks.count() < 2) { + ++numAborts; + return false; + } + + // Determine whether to allow coalescing based on how far the closest + // use is. + unsigned CopyIdx = getInstructionIndex(CopyMI); + unsigned MinDist = i2miMap_.size() * InstrSlots::NUM; + int UseBBNum = dvi.UsedBlocks.find_first(); + while (UseBBNum != -1) { + MachineBasicBlock *UseBB = mf_->getBlockNumbered(UseBBNum); + unsigned UseIdx = getMBBStartIdx(UseBB); + if (UseIdx > CopyIdx) { + MinDist = std::min(MinDist, UseIdx - CopyIdx); + if (MinDist <= Threshold) + break; + } + UseBBNum = dvi.UsedBlocks.find_next(UseBBNum); + } + if (MinDist > Threshold) { + // Don't do it! + ++numAborts; + return false; + } + } + +TryJoin: // 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 DestInt to be it. The output "SrcInt" will not have // been modified, so we can use this information below to update aliases. - if (!JoinIntervals(DestInt, SrcInt)) { + if (JoinIntervals(DestInt, 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(); + } + } + } + + if (isShorten || isDead) { + // Shorten the live interval. + LiveInterval &LiveInInt = (repSrcReg == DestInt.reg) ? DestInt : SrcInt; + LiveInInt.removeRange(RemoveStart, RemoveEnd); + } + } else { // Coallescing failed. // If we can eliminate the copy without merging the live ranges, do so now. @@ -796,32 +1049,42 @@ bool LiveIntervals::JoinCopy(MachineInstr *CopyMI, return true; // Otherwise, we are unable to join the intervals. - DEBUG(std::cerr << "Interference!\n"); + DOUT << "Interference!\n"; return false; } - bool Swapped = SrcReg == DestInt.reg; + bool Swapped = repSrcReg == DestInt.reg; if (Swapped) - std::swap(SrcReg, DstReg); - assert(MRegisterInfo::isVirtualRegister(SrcReg) && + 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(DstReg)) { - for (const unsigned *AS = mri_->getAliasSet(DstReg); *AS; ++AS) + if (MRegisterInfo::isPhysicalRegister(repDstReg)) { + for (const unsigned *AS = mri_->getAliasSet(repDstReg); *AS; ++AS) getInterval(*AS).MergeInClobberRanges(SrcInt); + } else { + // Merge UsedBlocks info if the destination is a virtual register. + LiveVariables::VarInfo& dVI = lv_->getVarInfo(repDstReg); + LiveVariables::VarInfo& sVI = lv_->getVarInfo(repSrcReg); + dVI.UsedBlocks |= sVI.UsedBlocks; } - DEBUG(std::cerr << "\n\t\tJoined. Result = "; DestInt.print(std::cerr, mri_); - std::cerr << "\n"); - + DOUT << "\n\t\tJoined. Result = "; DestInt.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(DestInt); - r2iMap_.erase(SrcReg); - r2rMap_[SrcReg] = DstReg; + removeInterval(repSrcReg); + r2rMap_[repSrcReg] = repDstReg; // Finally, delete the copy instruction. RemoveMachineInstrFromMaps(CopyMI); @@ -883,12 +1146,6 @@ static unsigned ComputeUltimateVN(unsigned VN, return ThisValNoAssignments[VN] = UltimateVN; } -Statistic<> A("x", "a"); -Statistic<> B("x", "b"); -Statistic<> C("x", "c"); -Statistic<> D("x", "d"); - - static bool InVector(unsigned Val, const SmallVector &V) { return std::find(V.begin(), V.end(), Val) != V.end(); } @@ -1048,13 +1305,11 @@ bool LiveIntervals::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { } else { RHSValNoInfo = RHS.getValNumInfo(0); } - ++A; } 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); - ++B; } LHSValNoAssignments.resize(LHS.getNumValNums(), -1); @@ -1093,7 +1348,6 @@ bool LiveIntervals::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { RHSValNoAssignments[0] = RHSValID; } else { - ++D; // Loop over the value numbers of the LHS, seeing if any are defined from // the RHS. SmallVector LHSValsDefinedFromRHS; @@ -1223,8 +1477,9 @@ namespace { } -void LiveIntervals::CopyCoallesceInMBB(MachineBasicBlock *MBB) { - DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); +void LiveIntervals::CopyCoallesceInMBB(MachineBasicBlock *MBB, + std::vector &TryAgain) { + DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); MII != E;) { @@ -1234,20 +1489,25 @@ void LiveIntervals::CopyCoallesceInMBB(MachineBasicBlock *MBB) { unsigned SrcReg, DstReg; if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg)) continue; - JoinCopy(Inst, SrcReg, DstReg); + if (!JoinCopy(Inst, SrcReg, DstReg)) + TryAgain.push_back(getCopyRec(Inst, SrcReg, DstReg)); } } void LiveIntervals::joinIntervals() { - DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n"); + DOUT << "********** JOINING INTERVALS ***********\n"; + + JoinedLIs.resize(getNumIntervals()); + JoinedLIs.reset(); + 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); + CopyCoallesceInMBB(I, TryAgainList); } else { // Otherwise, join intervals in inner loops before other intervals. // Unfortunately we can't just iterate over loop hierarchy here because @@ -1262,16 +1522,53 @@ void LiveIntervals::joinIntervals() { // Finally, join intervals in loop nest order. for (unsigned i = 0, e = MBBs.size(); i != e; ++i) - CopyCoallesceInMBB(MBBs[i].second); + CopyCoallesceInMBB(MBBs[i].second, TryAgainList); } - DEBUG(std::cerr << "*** Register mapping ***\n"); - DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i) - if (r2rMap_[i]) { - std::cerr << " reg " << i << " -> "; - printRegName(r2rMap_[i]); - std::cerr << "\n"; - }); + // 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; + } + } + } + + // 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); + } + 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 @@ -1294,8 +1591,77 @@ bool LiveIntervals::differingRegisterClasses(unsigned RegA, return !RegClass->contains(RegB); } +/// 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); + } + 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; + } + } + + e -= InstrSlots::NUM; + } + + return NULL; +} + + +/// 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; + } + return NULL; +} + +/// 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(); + } +} + +/// 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; + } + return false; +} + LiveInterval LiveIntervals::createInterval(unsigned reg) { float Weight = MRegisterInfo::isPhysicalRegister(reg) ? - (float)HUGE_VAL : 0.0F; + HUGE_VALF : 0.0F; return LiveInterval(reg, Weight); }