X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=8cfc5871dcc68708f0151b3535e1c248b7ea2e30;hb=2d87734a8ffad5933edbbc15a3b643df1e8a767e;hp=946d80de6b4c074d47b11bcaf4d6210fb130f4dc;hpb=e73701df947d23c65e96abc71a3be40ad77058ee;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 946d80de6b4..8cfc5871dcc 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -34,35 +34,25 @@ #include "llvm/ADT/STLExtras.h" #include #include -#include using namespace llvm; -namespace { - RegisterAnalysis X("liveintervals", "Live Interval Analysis"); - - Statistic<> numIntervals - ("liveintervals", "Number of original intervals"); - - Statistic<> numIntervalsAfter - ("liveintervals", "Number of intervals after coalescing"); - - Statistic<> numJoins - ("liveintervals", "Number of interval joins performed"); - - Statistic<> numPeep - ("liveintervals", "Number of identity moves eliminated after coalescing"); +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"); - Statistic<> numFolded - ("liveintervals", "Number of loads/stores folded into instructions"); +namespace { + RegisterPass X("liveintervals", "Live Interval Analysis"); - cl::opt + static cl::opt EnableJoining("join-liveintervals", - cl::desc("Join compatible live intervals"), + cl::desc("Coallesce copies (default=true)"), cl::init(true)); -}; +} -void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const -{ +void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); AU.addPreservedID(PHIEliminationID); AU.addRequiredID(PHIEliminationID); @@ -71,12 +61,21 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const MachineFunctionPass::getAnalysisUsage(AU); } -void LiveIntervals::releaseMemory() -{ +void LiveIntervals::releaseMemory() { mi2iMap_.clear(); i2miMap_.clear(); r2iMap_.clear(); r2rMap_.clear(); + JoinedLIs.clear(); +} + + +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; } @@ -91,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, 0, true); - for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS) - handlePhysicalRegisterDef(Entry, Entry->begin(), - getOrCreateInterval(*AS), 0, 0, true); + i2miMap_.push_back(I); + MIIndex += InstrSlots::NUM; } } @@ -142,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) { @@ -169,20 +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); - // remove index -> MachineInstr and - // MachineInstr -> index mappings - Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii); - if (mi2i != mi2iMap_.end()) { - i2miMap_[mi2i->second/InstrSlots::NUM] = 0; - mi2iMap_.erase(mi2i); + 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 @@ -190,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; @@ -199,6 +180,26 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { } } + 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; + + // 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; + } + } + DEBUG(dump()); return true; } @@ -207,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"; @@ -222,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 @@ -230,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 << '\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); @@ -250,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_) @@ -280,49 +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()); - 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 << '\n'); + DOUT << "\t\t\t\tadded new interval: "; + nI.print(DOUT, mri_); + DOUT << '\n'; } } } @@ -332,19 +394,37 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { return added; } -void LiveIntervals::printRegName(unsigned reg) const -{ +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, +void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, MachineBasicBlock::iterator mi, - LiveInterval& interval) -{ - DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); + unsigned MIIdx, + LiveInterval &interval) { + DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); // Virtual registers may be defined multiple times (due to phi @@ -352,10 +432,25 @@ 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()) { - // Get the Idx of the defining instructions. - unsigned defIndex = getDefIndex(getInstructionIndex(mi)); + // 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; - unsigned ValNum = interval.getNextValue(); + // Get the Idx of the defining instructions. + unsigned defIndex = getDefIndex(MIIdx); + + unsigned ValNum; + 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. @@ -374,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; } } @@ -390,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 @@ -398,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; } } } @@ -413,35 +508,49 @@ 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, - // becuase the 2-addr copy must be in the same MBB as the redef. + // because the 2-addr copy must be in the same MBB as the redef. interval.removeRange(DefIndex, RedefIndex); - LiveRange LR(DefIndex, RedefIndex, interval.getNextValue()); - DEBUG(std::cerr << " replace range with " << LR); + // Two-address vregs should always only be redefined once. This means + // that at this point, there should be exactly one value number in it. + assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); + + // 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)); + + // Value#0 is now defined by the 2-addr instruction. + interval.setValueNumberInfo(0, std::make_pair(~0U, 0U)); + + // 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); // If this redefinition is dead, we need to add a dummy unit live @@ -449,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); + DOUT << " RESULT: "; + interval.print(DOUT, mri_); } else { // Otherwise, this must be because of phi elimination. If this is the @@ -461,47 +571,53 @@ 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 << "\n"); + DOUT << " Removing [" << Start << "," << End << "] from: "; + interval.print(DOUT, mri_); DOUT << "\n"; interval.removeRange(Start, End); - DEBUG(std::cerr << "RESULT: " << interval); + DOUT << " RESULT: "; interval.print(DOUT, mri_); - // Replace the interval with one of a NEW value number. - LiveRange LR(Start, End, interval.getNextValue()); - DEBUG(std::cerr << " replace range with " << LR); + // 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)); + DOUT << " replace range with " << LR; interval.addRange(LR); - DEBUG(std::cerr << "RESULT: " << interval); + 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; + if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) + ValNum = interval.getNextValue(~0U, 0); + else + ValNum = interval.getNextValue(defIndex, SrcReg); + LiveRange LR(defIndex, - getInstructionIndex(&mbb->back()) + InstrSlots::NUM, - interval.getNextValue()); + 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, - LiveInterval& interval, - unsigned SrcReg, unsigned DestReg, - bool isLiveIn) -{ + 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; @@ -509,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; } @@ -520,247 +636,833 @@ 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; } } // 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(isLiveIn && "physreg was not killed in defining block!"); + assert(!SrcReg && "physreg was not killed in defining block!"); end = getDefIndex(start) + 1; // It's dead. exit: assert(start < end && "did not find end of interval?"); - // Finally, if this is defining a new range for the physical register, and if - // that physreg is just a copy from a vreg, and if THAT vreg was a copy from - // the physreg, then the new fragment has the same value as the one copied - // into the vreg. - if (interval.reg == DestReg && !interval.empty() && - MRegisterInfo::isVirtualRegister(SrcReg)) { - - // Get the live interval for the vreg, see if it is defined by a copy. - LiveInterval &SrcInterval = getOrCreateInterval(SrcReg); - - if (SrcInterval.containsOneValue()) { - assert(!SrcInterval.empty() && "Can't contain a value and be empty!"); - - // Get the first index of the first range. Though the interval may have - // multiple liveranges in it, we only check the first. - unsigned StartIdx = SrcInterval.begin()->start; - MachineInstr *SrcDefMI = getInstructionFromIndex(StartIdx); - - // Check to see if the vreg was defined by a copy instruction, and that - // the source was this physreg. - unsigned VRegSrcSrc, VRegSrcDest; - if (tii_->isMoveInstr(*SrcDefMI, VRegSrcSrc, VRegSrcDest) && - SrcReg == VRegSrcDest && VRegSrcSrc == DestReg) { - // Okay, now we know that the vreg was defined by a copy from this - // physreg. Find the value number being copied and use it as the value - // for this range. - const LiveRange *DefRange = interval.getLiveRangeContaining(StartIdx-1); - if (DefRange) { - LiveRange LR(start, end, DefRange->ValId); - interval.addRange(LR); - DEBUG(std::cerr << " +" << LR << '\n'); - return; - } - } - } - } - - - LiveRange LR(start, end, interval.getNextValue()); + 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 = 0, DestReg = 0; - if (!tii_->isMoveInstr(*MI, SrcReg, DestReg)) - SrcReg = DestReg = 0; - - handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg), - SrcReg, DestReg); + unsigned SrcReg, DstReg; + if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) + SrcReg = 0; + handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg); for (const unsigned* AS = mri_->getAliasSet(reg); *AS; ++AS) - handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS), - SrcReg, DestReg); + 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 /// registers. for some ordering of the machine instructions [1,N] a /// live interval is an interval [i, j) where 1 <= i <= j < N for /// which a variable is live -void LiveIntervals::computeIntervals() -{ - 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 - for (const unsigned* id = tid.ImplicitDefs; *id; ++id) - handleRegisterDef(mbb, mi, *id); - - // handle explicit defs - for (int i = mi->getNumOperands() - 1; i >= 0; --i) { - MachineOperand& mop = mi->getOperand(i); +void LiveIntervals::computeIntervals() { + DOUT << "********** COMPUTING LIVE INTERVALS **********\n" + << "********** Function: " + << ((Value*)mf_->getFunction())->getName() << '\n'; + // Track the index of the current machine instr. + unsigned MIIndex = 0; + for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); + MBBI != E; ++MBBI) { + MachineBasicBlock *MBB = MBBI; + 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 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; } } } -/// IntA is defined as a copy from IntB and we know it only has one value -/// number. If all of the places that IntA and IntB overlap are defined by -/// copies from IntA to IntB, we know that these two ranges can really be -/// merged if we adjust the value numbers. If it is safe, adjust the value -/// numbers and return true, allowing coalescing to occur. -bool LiveIntervals:: -AdjustIfAllOverlappingRangesAreCopiesFrom(LiveInterval &IntA, - LiveInterval &IntB, - unsigned CopyIdx) { - std::vector Ranges; - IntA.getOverlapingRanges(IntB, CopyIdx, Ranges); - - assert(!Ranges.empty() && "Why didn't we do a simple join of this?"); - - unsigned IntBRep = rep(IntB.reg); - - // Check to see if all of the overlaps (entries in Ranges) are defined by a - // copy from IntA. If not, exit. - for (unsigned i = 0, e = Ranges.size(); i != e; ++i) { - unsigned Idx = Ranges[i]->start; - MachineInstr *MI = getInstructionFromIndex(Idx); - unsigned SrcReg, DestReg; - if (!tii_->isMoveInstr(*MI, SrcReg, DestReg)) return false; +/// 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 this copy isn't actually defining this range, it must be a live - // range spanning basic blocks or something. - if (rep(DestReg) != rep(IntA.reg)) return false; + // If the value number is not defined by a copy instruction, ignore it. - // Check to see if this is coming from IntB. If not, bail out. - if (rep(SrcReg) != IntBRep) return false; + // 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)) { + for (const unsigned *AS = mri_->getAliasSet(IntB.reg); *AS; ++AS) { + LiveInterval &AliasLI = getInterval(*AS); + AliasLI.addRange(LiveRange(FillerStart, FillerEnd, + AliasLI.getNextValue(~0U, 0))); + } } - // Okay, we can change this one. Get the IntB value number that IntA is - // copied from. - unsigned ActualValNo = IntA.getLiveRangeContaining(CopyIdx-1)->ValId; - - // Change all of the value numbers to the same as what we IntA is copied from. - for (unsigned i = 0, e = Ranges.size(); i != e; ++i) - Ranges[i]->ValId = ActualValNo; + // 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; } -void LiveIntervals::joinIntervalsInMachineBB(MachineBasicBlock *MBB) { - DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); +/// 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 these 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) { + DOUT << getInstructionIndex(CopyMI) << '\t' << *CopyMI; + + // 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. + } + + // If they are both physical registers, we cannot join them. + 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(repSrcReg) && + !allocatableRegs_[repSrcReg]) { + DOUT << "\tSrc reg is unallocatable physreg.\n"; + return true; // Not coallescable. + } + 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(repSrcReg, repDstReg)) { + DOUT << "\tSrc/Dest are different register classes.\n"; + return true; // Not coallescable. + } + + LiveInterval &SrcInt = getInterval(repSrcReg); + LiveInterval &DestInt = getInterval(repDstReg); + assert(SrcInt.reg == repSrcReg && DestInt.reg == repDstReg && + "Register mapping is horribly broken!"); + + 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; + } + } + } + } - for (MachineBasicBlock::iterator mi = MBB->begin(), mie = MBB->end(); - mi != mie; ++mi) { - DEBUG(std::cerr << getInstructionIndex(mi) << '\t' << *mi); + // 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; + } - // we only join virtual registers with allocatable - // physical registers since we do not have liveness information - // on not allocatable physical registers - unsigned SrcReg, DestReg; - if (tii_->isMoveInstr(*mi, SrcReg, DestReg) && - (MRegisterInfo::isVirtualRegister(SrcReg) || allocatableRegs_[SrcReg])&& - (MRegisterInfo::isVirtualRegister(DestReg)||allocatableRegs_[DestReg])){ + // 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; + } - // Get representative registers. - SrcReg = rep(SrcReg); - DestReg = rep(DestReg); + // 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; + } + } - // If they are already joined we continue. - if (SrcReg == DestReg) - continue; +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 (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 they are both physical registers, we cannot join them. - if (MRegisterInfo::isPhysicalRegister(SrcReg) && - MRegisterInfo::isPhysicalRegister(DestReg)) - continue; + 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. + if (AdjustCopiesBackFrom(SrcInt, DestInt, CopyMI)) + return true; - // If they are not of compatible register classes, we cannot join them. - bool Swap = false; - if (!compatibleRegisterClasses(SrcReg, DestReg, Swap)) { - DEBUG(std::cerr << "Register classes aren't compatible!\n"); - continue; - } + // Otherwise, we are unable to join the intervals. + DOUT << "Interference!\n"; + return false; + } + + bool Swapped = repSrcReg == DestInt.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)) { + 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; + } + + 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); + removeInterval(repSrcReg); + r2rMap_[repSrcReg] = repDstReg; + + // Finally, delete the copy instruction. + RemoveMachineInstrFromMaps(CopyMI); + CopyMI->eraseFromParent(); + ++numPeep; + ++numJoins; + return true; +} - LiveInterval &SrcInt = getInterval(SrcReg); - LiveInterval &DestInt = getInterval(DestReg); - assert(SrcInt.reg == SrcReg && DestInt.reg == DestReg && - "Register mapping is horribly broken!"); +/// 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; + } - DEBUG(std::cerr << "\t\tInspecting " << SrcInt << " and " << DestInt - << ": "); + // 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; +} - // If two intervals contain a single value and are joined by a copy, it - // does not matter if the intervals overlap, they can always be joined. - bool Joinable = SrcInt.containsOneValue() && DestInt.containsOneValue(); +static bool InVector(unsigned Val, const SmallVector &V) { + return std::find(V.begin(), V.end(), Val) != V.end(); +} - unsigned MIDefIdx = getDefIndex(getInstructionIndex(mi)); +/// 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; + } + + 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); + } - // If the intervals think that this is joinable, do so now. - if (!Joinable && DestInt.joinable(SrcInt, MIDefIdx)) - Joinable = true; - - // If DestInt is actually a copy from SrcInt (which we know) that is used - // to define another value of SrcInt, we can change the other range of - // SrcInt to be the value of the range that defines DestInt, allowing a - // coalesce. - if (!Joinable && DestInt.containsOneValue() && - AdjustIfAllOverlappingRangesAreCopiesFrom(SrcInt, DestInt, MIDefIdx)) - Joinable = true; + // We know this entire LHS live range is okay, so skip it now. + if (++LHSIt == LHSEnd) break; + 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; + } + } + } - if (!Joinable || overlapsAliases(&SrcInt, &DestInt)) { - DEBUG(std::cerr << "Interference!\n"); + 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 { - DestInt.join(SrcInt, MIDefIdx); - DEBUG(std::cerr << "Joined. Result = " << DestInt << "\n"); + // Merge into the smallest. + LHS.MergeValueNumberInto(EliminatedLHSVals[i], Smallest); + } + } + 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; + + return true; +} - if (!Swap && !MRegisterInfo::isPhysicalRegister(SrcReg)) { - r2iMap_.erase(SrcReg); - r2rMap_[SrcReg] = DestReg; +/// 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; + + // 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); + } else { + RHSValNoInfo = RHS.getValNumInfo(0); + } + } 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; } else { - // Otherwise merge the data structures the other way so we don't lose - // the physreg information. - r2rMap_[DestReg] = SrcReg; - DestInt.reg = SrcReg; - SrcInt.swap(DestInt); - r2iMap_.erase(DestReg); + // Otherwise, use the specified value #. + LHSValNoAssignments[VN] = RHSValID; + if (VN != (unsigned)RHSValID) + ValueNumberInfo[VN].first = ~1U; + else + ValueNumberInfo[VN] = RHSValNoInfo; } - ++numJoins; + } else { + ValueNumberInfo[VN] = LHS.getValNumInfo(VN); + LHSValNoAssignments[VN] = VN; + } + } + + 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); + } + 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; } + + ComputeUltimateVN(VN, ValueNumberInfo, + RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, + RHSValNoAssignments, LHSValNoAssignments, RHS, LHS); } } + + // 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; + } + + 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; + } + + // 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; + } + + if (I->end < J->end) { + ++I; + if (I == IE) break; + } else { + ++J; + if (J == JE) break; + } + } + + // 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; } + namespace { // DepthMBBCompare - Comparison predicate that sort first based on the loop // depth of the basic block (the unsigned), and then on the MBB number. @@ -774,15 +1476,38 @@ namespace { }; } + +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;) { + 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 (!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) - joinIntervalsInMachineBB(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 @@ -797,65 +1522,146 @@ void LiveIntervals::joinIntervals() { // Finally, join intervals in loop nest order. for (unsigned i = 0, e = MBBs.size(); i != e; ++i) - joinIntervalsInMachineBB(MBBs[i].second); + CopyCoallesceInMBB(MBBs[i].second, TryAgainList); + } + + // 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; + } + } } - DEBUG(std::cerr << "*** Register mapping ***\n"); - DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i) - if (r2rMap_[i]) - std::cerr << " reg " << i << " -> reg " << r2rMap_[i] << "\n"); + // 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 same or compatible -/// register classes. The registers may be either phys or virt regs. -bool LiveIntervals::compatibleRegisterClasses(unsigned RegA, unsigned RegB, - bool &Swap) const { +/// 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 { // 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); + return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA); } // Compare against the regclass for the second reg. - const TargetRegisterClass *RegClassA = mf_->getSSARegMap()->getRegClass(RegA); - if (MRegisterInfo::isVirtualRegister(RegB)) { - const TargetRegisterClass *RegClassB=mf_->getSSARegMap()->getRegClass(RegB); - if (RegClassA == RegClassB) - return true; - else { - if (RegClassB->hasSubRegClass(RegClassA)) { - Swap = true; - return true; + const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA); + if (MRegisterInfo::isVirtualRegister(RegB)) + return RegClass != mf_->getSSARegMap()->getRegClass(RegB); + else + 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; } - return RegClassA->hasSubRegClass(RegClassB); } - } else - return RegClassA->contains(RegB); + + e -= InstrSlots::NUM; + } + + return NULL; } -bool LiveIntervals::overlapsAliases(const LiveInterval *LHS, - const LiveInterval *RHS) const { - if (!MRegisterInfo::isPhysicalRegister(LHS->reg)) { - if (!MRegisterInfo::isPhysicalRegister(RHS->reg)) - return false; // vreg-vreg merge has no aliases! - std::swap(LHS, RHS); + +/// 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; +} - assert(MRegisterInfo::isPhysicalRegister(LHS->reg) && - MRegisterInfo::isVirtualRegister(RHS->reg) && - "first interval must describe a physical register"); +/// 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(); + } +} - for (const unsigned *AS = mri_->getAliasSet(LHS->reg); *AS; ++AS) - if (RHS->overlaps(getInterval(*AS))) +/// 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); }