X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=8cfc5871dcc68708f0151b3535e1c248b7ea2e30;hb=2d87734a8ffad5933edbbc15a3b643df1e8a767e;hp=eeabbd1c05478e87c028eed69066645aa9219b29;hpb=51cdcd197268a7abf19b2698fc824e0da3d98049;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index eeabbd1c054..8cfc5871dcc 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -36,24 +36,16 @@ #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("Coallesce copies (default=true)"), @@ -74,6 +66,7 @@ void LiveIntervals::releaseMemory() { i2miMap_.clear(); r2iMap_.clear(); r2rMap_.clear(); + JoinedLIs.clear(); } @@ -97,28 +90,6 @@ 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 and MachineBasicBlocks. // Initialize MBB indexes to a sentinal. MBB2IdxMap.resize(mf_->getNumBlockIDs(), ~0U); @@ -128,7 +99,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 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; @@ -138,19 +109,6 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { } } - // 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(), 0, - getOrCreateInterval(I->first), 0); - for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS) - handlePhysicalRegisterDef(Entry, Entry->begin(), 0, - getOrCreateInterval(*AS), 0); - } - } - computeIntervals(); numIntervals += getNumIntervals(); @@ -183,12 +141,21 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { if (tii_->isMoveInstr(*mii, srcReg, dstReg) && (RegRep = rep(srcReg)) == rep(dstReg)) { // remove from def list - 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 { + } else { for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { const MachineOperand &mop = mii->getOperand(i); if (mop.isRegister() && mop.getReg() && @@ -198,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; @@ -207,7 +180,6 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { } } - for (iterator I = begin(), E = end(); I != E; ++I) { LiveInterval &LI = I->second; if (MRegisterInfo::isVirtualRegister(LI.reg)) { @@ -333,7 +305,9 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& mop = MI->getOperand(i); if (mop.isRegister() && mop.getReg() == li.reg) { - 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_) @@ -378,8 +352,11 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { // create a new register for this spill vrm.grow(); + if (li.remat) + vrm.setVirtIsReMaterialized(NewVReg, li.remat); vrm.assignVirt2StackSlot(NewVReg, slot); LiveInterval &nI = getOrCreateInterval(NewVReg); + nI.remat = li.remat; assert(nI.empty()); // the spill weight is now infinity as it @@ -419,9 +396,9 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { void LiveIntervals::printRegName(unsigned reg) const { if (MRegisterInfo::isPhysicalRegister(reg)) - llvm_cerr << mri_->getName(reg); + cerr << mri_->getName(reg); else - llvm_cerr << "%reg" << reg; + cerr << "%reg" << reg; } /// isReDefinedByTwoAddr - Returns true if the Reg re-definition is due to @@ -455,6 +432,15 @@ 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(MIIdx); @@ -483,7 +469,7 @@ 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); @@ -530,6 +516,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, } } else { + // Can no longer safely assume definition is rematerializable. + interval.remat = NULL; + // If this is the second time we see a virtual register definition, it // must be due to phi elimination or two addr elimination. If this is // the result of two address elimination, then the vreg is one of the @@ -569,7 +558,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, if (lv_->RegisterDefIsDead(mi, interval.reg)) interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); - DOUT << "RESULT: "; + DOUT << " RESULT: "; interval.print(DOUT, mri_); } else { @@ -584,17 +573,17 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, MachineInstr *Killer = vi.Kills[0]; unsigned Start = getMBBStartIdx(Killer->getParent()); unsigned End = getUseIndex(getInstructionIndex(Killer))+1; - DOUT << "Removing [" << Start << "," << End << "] from: "; + DOUT << " Removing [" << Start << "," << End << "] from: "; interval.print(DOUT, mri_); DOUT << "\n"; interval.removeRange(Start, End); - DOUT << "RESULT: "; interval.print(DOUT, 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)); DOUT << " replace range with " << LR; interval.addRange(LR); - DOUT << "RESULT: "; interval.print(DOUT, mri_); + DOUT << " RESULT: "; interval.print(DOUT, mri_); } // In the case of PHI elimination, each variable definition is only @@ -692,6 +681,44 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, } } +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 @@ -700,8 +727,6 @@ void LiveIntervals::computeIntervals() { DOUT << "********** COMPUTING LIVE INTERVALS **********\n" << "********** Function: " << ((Value*)mf_->getFunction())->getName() << '\n'; - bool IgnoreFirstInstr = mf_->livein_begin() != mf_->livein_end(); - // Track the index of the current machine instr. unsigned MIIndex = 0; for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); @@ -710,10 +735,15 @@ void LiveIntervals::computeIntervals() { DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); - if (IgnoreFirstInstr) { - ++MI; - IgnoreFirstInstr = false; - MIIndex += InstrSlots::NUM; + + 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) { @@ -822,6 +852,12 @@ bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, 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); @@ -830,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 @@ -840,54 +875,173 @@ bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, bool LiveIntervals::JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned DstReg) { 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) { + 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)) { + 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]){ + if (MRegisterInfo::isPhysicalRegister(repSrcReg) && + !allocatableRegs_[repSrcReg]) { DOUT << "\tSrc reg is unallocatable physreg.\n"; return true; // Not coallescable. } - if (MRegisterInfo::isPhysicalRegister(DstReg) && !allocatableRegs_[DstReg]){ + 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)) { + 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!"); 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. @@ -899,28 +1053,38 @@ bool LiveIntervals::JoinCopy(MachineInstr *CopyMI, 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; } 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); @@ -1334,8 +1498,10 @@ void LiveIntervals::CopyCoallesceInMBB(MachineBasicBlock *MBB, void LiveIntervals::joinIntervals() { 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. @@ -1374,6 +1540,27 @@ void LiveIntervals::joinIntervals() { } } } + + // 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) @@ -1404,6 +1591,75 @@ 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) ? HUGE_VALF : 0.0F;