Changes in directory llvm/lib/CodeGen:
LiveIntervalAnalysis.cpp updated: 1.208 -> 1.209 LiveVariables.cpp updated: 1.67 -> 1.68 MachineBasicBlock.cpp updated: 1.41 -> 1.42 MachineInstr.cpp updated: 1.143 -> 1.144 RegAllocLinearScan.cpp updated: 1.139 -> 1.140 --- Log message: Re-apply my liveintervalanalysis changes. Now with PR1207: http://llvm.org/PR1207 fixes. --- Diffs of the changes: (+164 -85) LiveIntervalAnalysis.cpp | 189 +++++++++++++++++++++++++++++++++-------------- LiveVariables.cpp | 36 +------- MachineBasicBlock.cpp | 8 + MachineInstr.cpp | 11 ++ RegAllocLinearScan.cpp | 5 - 5 files changed, 164 insertions(+), 85 deletions(-) Index: llvm/lib/CodeGen/LiveIntervalAnalysis.cpp diff -u llvm/lib/CodeGen/LiveIntervalAnalysis.cpp:1.208 llvm/lib/CodeGen/LiveIntervalAnalysis.cpp:1.209 --- llvm/lib/CodeGen/LiveIntervalAnalysis.cpp:1.208 Sun Feb 18 21:20:00 2007 +++ llvm/lib/CodeGen/LiveIntervalAnalysis.cpp Mon Feb 19 15:49:53 2007 @@ -98,28 +98,6 @@ // Set the MBB2IdxMap entry for this MBB. MBB2IdxMap[MBB->getNumber()] = MIIndex; - // If this BB 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 (MBB->livein_begin() != MBB->livein_end()) { - unsigned FirstLiveIn = *MBB->livein_begin(); - - // Find a reg class that contains this live in. - const TargetRegisterClass *RC = 0; - for (MRegisterInfo::regclass_iterator RCI = mri_->regclass_begin(), - RCE = mri_->regclass_end(); RCI != RCE; ++RCI) - if ((*RCI)->contains(FirstLiveIn)) { - RC = *RCI; - break; - } - - MachineInstr *OldFirstMI = MBB->begin(); - mri_->copyRegToReg(*MBB, MBB->begin(), - FirstLiveIn, FirstLiveIn, RC); - assert(OldFirstMI != MBB->begin() && - "copyRetToReg didn't insert anything!"); - } - for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) { bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; @@ -161,7 +139,17 @@ 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; @@ -185,7 +173,6 @@ } } - for (iterator I = begin(), E = end(); I != E; ++I) { LiveInterval &LI = I->second; if (MRegisterInfo::isVirtualRegister(LI.reg)) { @@ -670,6 +657,43 @@ } } +void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, + 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 = 0; + unsigned start = 0; + 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)); + interval.addRange(LR); + DOUT << " +" << LR << '\n'; +} + /// 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 @@ -688,17 +712,13 @@ MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); if (MBB->livein_begin() != MBB->livein_end()) { - // Process live-ins to this BB first. - for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), + // 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) { - handlePhysicalRegisterDef(MBB, MBB->begin(), MIIndex, - getOrCreateInterval(*LI), 0); + handleLiveInRegister(MBB, getOrCreateInterval(*LI)); for (const unsigned* AS = mri_->getAliasSet(*LI); *AS; ++AS) - handlePhysicalRegisterDef(MBB, MBB->begin(), MIIndex, - getOrCreateInterval(*AS), 0); + handleLiveInRegister(MBB, getOrCreateInterval(*AS)); } - ++MI; - MIIndex += InstrSlots::NUM; } for (; MI != miEnd; ++MI) { @@ -815,7 +835,6 @@ 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 @@ -825,54 +844,93 @@ 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. + MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg); + bool isDead = mopd->isDead(); + unsigned SrcStart = 0; + unsigned SrcEnd = 0; + if (isDead) { + unsigned CopyIdx = getDefIndex(getInstructionIndex(CopyMI)); + LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx-1); + SrcStart = SrcLR->start; + SrcEnd = SrcLR->end; + if (hasRegisterUse(repSrcReg, SrcStart, SrcEnd)) + isDead = false; + } + // 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) { + // Live-in to the function but dead. Remove it from MBB live-in set. + // JoinIntervals may end up swapping the two intervals. + LiveInterval &LiveInInt = (repSrcReg == DestInt.reg) ? DestInt:SrcInt; + LiveInInt.removeRange(SrcStart, SrcEnd); + MachineBasicBlock *MBB = CopyMI->getParent(); + MBB->removeLiveIn(SrcReg); + } else { + MachineInstr *SrcMI = getInstructionFromIndex(SrcStart); + if (SrcMI) { + // FIXME: SrcMI == NULL means the register is livein to a non-entry + // MBB. Remove the range from its live interval? + MachineOperand *mops = SrcMI->findRegisterDefOperand(SrcReg); + if (mops) + // FIXME: mops == NULL means SrcMI defines a subregister? + mops->setIsDead(); + } + } + } + } else { // Coallescing failed. // If we can eliminate the copy without merging the live ranges, do so now. @@ -884,17 +942,17 @@ 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); } @@ -904,8 +962,8 @@ // 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); @@ -1389,6 +1447,29 @@ return !RegClass->contains(RegB); } +/// hasRegisterUse - Returns true if there is any use of the specific +/// reg between indexes Start and End. +bool +LiveIntervals::hasRegisterUse(unsigned Reg, unsigned Start, unsigned End) { + for (unsigned Index = Start+InstrSlots::NUM; Index != End; + Index += InstrSlots::NUM) { + // Skip deleted instructions + while (Index != End && !getInstructionFromIndex(Index)) + Index += InstrSlots::NUM; + if (Index >= End) break; + + MachineInstr *MI = getInstructionFromIndex(Index); + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (MO.isReg() && MO.isUse() && MO.getReg() && + mri_->regsOverlap(rep(MO.getReg()), Reg)) + return true; + } + } + + return false; +} + LiveInterval LiveIntervals::createInterval(unsigned reg) { float Weight = MRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; Index: llvm/lib/CodeGen/LiveVariables.cpp diff -u llvm/lib/CodeGen/LiveVariables.cpp:1.67 llvm/lib/CodeGen/LiveVariables.cpp:1.68 --- llvm/lib/CodeGen/LiveVariables.cpp:1.67 Sun Feb 18 21:20:00 2007 +++ llvm/lib/CodeGen/LiveVariables.cpp Mon Feb 19 15:49:53 2007 @@ -71,31 +71,11 @@ return VirtRegInfo[RegIdx]; } -/// registerOverlap - Returns true if register 1 is equal to register 2 -/// or if register 1 is equal to any of alias of register 2. -static bool registerOverlap(unsigned Reg1, unsigned Reg2, - const MRegisterInfo *RegInfo) { - bool isVirt1 = MRegisterInfo::isVirtualRegister(Reg1); - bool isVirt2 = MRegisterInfo::isVirtualRegister(Reg2); - if (isVirt1 != isVirt2) - return false; - if (Reg1 == Reg2) - return true; - else if (isVirt1) - return false; - for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg2); - unsigned Alias = *AliasSet; ++AliasSet) { - if (Reg1 == Alias) - return true; - } - return false; -} - bool LiveVariables::KillsRegister(MachineInstr *MI, unsigned Reg) const { for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); if (MO.isReg() && MO.isKill()) { - if (registerOverlap(Reg, MO.getReg(), RegInfo)) + if (RegInfo->regsOverlap(Reg, MO.getReg())) return true; } } @@ -106,7 +86,7 @@ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); if (MO.isReg() && MO.isDead()) - if (registerOverlap(Reg, MO.getReg(), RegInfo)) + if (RegInfo->regsOverlap(Reg, MO.getReg())) return true; } return false; @@ -116,7 +96,7 @@ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); if (MO.isReg() && MO.isDef()) { - if (registerOverlap(Reg, MO.getReg(), RegInfo)) + if (RegInfo->regsOverlap(Reg, MO.getReg())) return true; } } @@ -240,7 +220,7 @@ RegInfo = MF.getTarget().getRegisterInfo(); assert(RegInfo && "Target doesn't have register information?"); - AllocatablePhysicalRegisters = RegInfo->getAllocatableSet(MF); + ReservedRegisters = RegInfo->getReservedRegs(MF); // PhysRegInfo - Keep track of which instruction was the last use of a // physical register. This is a purely local property, because all physical @@ -267,8 +247,8 @@ E = df_ext_end(Entry, Visited); DFI != E; ++DFI) { MachineBasicBlock *MBB = *DFI; - // Mark live-in registers as live-in. - for (MachineBasicBlock::livein_iterator II = MBB->livein_begin(), + // Mark live-in registers as live-in. + for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(), EE = MBB->livein_end(); II != EE; ++II) { assert(MRegisterInfo::isPhysicalRegister(*II) && "Cannot have a live-in virtual register!"); @@ -295,7 +275,7 @@ if (MRegisterInfo::isVirtualRegister(MO.getReg())){ HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI); } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && - AllocatablePhysicalRegisters[MO.getReg()]) { + !ReservedRegisters[MO.getReg()]) { HandlePhysRegUse(MO.getReg(), MI); } } @@ -313,7 +293,7 @@ // Defaults to dead VRInfo.Kills.push_back(MI); } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && - AllocatablePhysicalRegisters[MO.getReg()]) { + !ReservedRegisters[MO.getReg()]) { HandlePhysRegDef(MO.getReg(), MI); } } Index: llvm/lib/CodeGen/MachineBasicBlock.cpp diff -u llvm/lib/CodeGen/MachineBasicBlock.cpp:1.41 llvm/lib/CodeGen/MachineBasicBlock.cpp:1.42 --- llvm/lib/CodeGen/MachineBasicBlock.cpp:1.41 Sun Feb 18 21:20:00 2007 +++ llvm/lib/CodeGen/MachineBasicBlock.cpp Mon Feb 19 15:49:53 2007 @@ -118,7 +118,7 @@ const MRegisterInfo *MRI = MF->getTarget().getRegisterInfo(); if (livein_begin() != livein_end()) { OS << "Live Ins:"; - for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) + for (const_livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I) OutputReg(OS, *I, MRI); OS << "\n"; } @@ -144,6 +144,12 @@ } } +void MachineBasicBlock::removeLiveIn(unsigned Reg) { + livein_iterator I = std::find(livein_begin(), livein_end(), Reg); + assert(I != livein_end() && "Not a live in!"); + LiveIns.erase(I); +} + void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { MachineFunction::BasicBlockListType &BBList =getParent()->getBasicBlockList(); getParent()->getBasicBlockList().splice(NewAfter, BBList, this); Index: llvm/lib/CodeGen/MachineInstr.cpp diff -u llvm/lib/CodeGen/MachineInstr.cpp:1.143 llvm/lib/CodeGen/MachineInstr.cpp:1.144 --- llvm/lib/CodeGen/MachineInstr.cpp:1.143 Sun Feb 18 21:20:00 2007 +++ llvm/lib/CodeGen/MachineInstr.cpp Mon Feb 19 15:49:53 2007 @@ -180,6 +180,17 @@ return NULL; } +/// findRegisterDefOperand() - Returns the MachineOperand that is a def of +/// the specific register or NULL if it is not found. +MachineOperand *MachineInstr::findRegisterDefOperand(unsigned Reg) { + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { + MachineOperand &MO = getOperand(i); + if (MO.isReg() && MO.isDef() && MO.getReg() == Reg) + return &MO; + } + return NULL; +} + /// copyKillDeadInfo - Copies kill / dead operand properties from MI. /// void MachineInstr::copyKillDeadInfo(const MachineInstr *MI) { Index: llvm/lib/CodeGen/RegAllocLinearScan.cpp diff -u llvm/lib/CodeGen/RegAllocLinearScan.cpp:1.139 llvm/lib/CodeGen/RegAllocLinearScan.cpp:1.140 --- llvm/lib/CodeGen/RegAllocLinearScan.cpp:1.139 Sun Feb 18 21:20:00 2007 +++ llvm/lib/CodeGen/RegAllocLinearScan.cpp Mon Feb 19 15:49:53 2007 @@ -292,8 +292,9 @@ } // A brute force way of adding live-ins to every BB. - for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); - MBB != E; ++MBB) { + MachineFunction::iterator MBB = mf_->begin(); + ++MBB; // Skip entry MBB. + for (MachineFunction::iterator E = mf_->end(); MBB != E; ++MBB) { unsigned StartIdx = li_->getMBBStartIdx(MBB->getNumber()); for (IntervalPtrs::iterator i = fixed_.begin(), e = fixed_.end(); i != e; ++i) _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
