From 91725b75852443923b419fd23215194cfc65dd88 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 31 Aug 2006 05:54:43 +0000 Subject: [PATCH] avoid calling the virtual isMoveInstr method endlessly by caching its results. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29994 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveInterval.h | 49 +++++--- include/llvm/CodeGen/LiveIntervalAnalysis.h | 4 +- lib/CodeGen/LiveInterval.cpp | 24 ++-- lib/CodeGen/LiveIntervalAnalysis.cpp | 124 ++++++++++---------- 4 files changed, 107 insertions(+), 94 deletions(-) diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 33b2c75e6a2..95360adf523 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -78,10 +78,12 @@ namespace llvm { float weight; // weight of this interval Ranges ranges; // the ranges in which this register is live private: - /// InstDefiningValue - This tracks the def index of the instruction that - /// defines a particular value number in the interval. This may be ~0, - /// which is treated as unknown, or ~1, which is a deleted value number. - SmallVector InstDefiningValue; + /// ValueNumberInfo - If this value number is not defined by a copy, this + /// holds ~0,x. If the value number is not in use, it contains ~1,x to + /// indicate that the value # is not used. If the val# is defined by a + /// copy, the first entry is the instruction # of the copy, and the second + /// is the register number copied from. + SmallVector, 4> ValueNumberInfo; public: LiveInterval(unsigned Reg, float Weight) @@ -113,31 +115,44 @@ namespace llvm { std::swap(reg, other.reg); std::swap(weight, other.weight); std::swap(ranges, other.ranges); - std::swap(InstDefiningValue, other.InstDefiningValue); + std::swap(ValueNumberInfo, other.ValueNumberInfo); } - bool containsOneValue() const { return InstDefiningValue.size() == 1; } + bool containsOneValue() const { return ValueNumberInfo.size() == 1; } - unsigned getNumValNums() const { return InstDefiningValue.size(); } + unsigned getNumValNums() const { return ValueNumberInfo.size(); } /// getNextValue - Create a new value number and return it. MIIdx specifies /// the instruction that defines the value number. - unsigned getNextValue(unsigned MIIdx) { - InstDefiningValue.push_back(MIIdx); - return InstDefiningValue.size()-1; + unsigned getNextValue(unsigned MIIdx, unsigned SrcReg) { + ValueNumberInfo.push_back(std::make_pair(MIIdx, SrcReg)); + return ValueNumberInfo.size()-1; } /// getInstForValNum - Return the machine instruction index that defines the /// specified value number. unsigned getInstForValNum(unsigned ValNo) const { - assert(ValNo < InstDefiningValue.size()); - return InstDefiningValue[ValNo]; + assert(ValNo < ValueNumberInfo.size()); + return ValueNumberInfo[ValNo].first; } - /// setInstDefiningValNum - Change the instruction defining the specified - /// value number to the specified instruction. - void setInstDefiningValNum(unsigned ValNo, unsigned MIIdx) { - InstDefiningValue[ValNo] = MIIdx; + unsigned getSrcRegForValNum(unsigned ValNo) const { + assert(ValNo < ValueNumberInfo.size()); + if (ValueNumberInfo[ValNo].first < ~2U) + return ValueNumberInfo[ValNo].second; + return 0; + } + + std::pair getValNumInfo(unsigned ValNo) const { + assert(ValNo < ValueNumberInfo.size()); + return ValueNumberInfo[ValNo]; + } + + /// setValueNumberInfo - Change the value number info for the specified + /// value number. + void setValueNumberInfo(unsigned ValNo, + const std::pair &I){ + ValueNumberInfo[ValNo] = I; } /// MergeValueNumberInto - This method is called when two value nubmers @@ -216,7 +231,7 @@ namespace llvm { /// the intervals are not joinable, this aborts. void join(LiveInterval &Other, int *ValNoAssignments, int *RHSValNoAssignments, - SmallVector &NewInstDefiningValue); + SmallVector,16> &NewValueNumberInfo); /// removeRange - Remove the specified range from this interval. Note that diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 845a4b07169..6834fc272af 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -198,8 +198,8 @@ namespace llvm { /// def. void handlePhysicalRegisterDef(MachineBasicBlock* mbb, MachineBasicBlock::iterator mi, - LiveInterval& interval, - bool isLiveIn = false); + LiveInterval &interval, + unsigned SrcReg); /// Return true if the two specified registers belong to different /// register classes. The registers may be either phys or virt regs. diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index 8be96779291..eecb570db53 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -280,7 +280,8 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) { /// the intervals are not joinable, this aborts. void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments, int *RHSValNoAssignments, - SmallVector &NewInstDefiningValue) { + SmallVector, 16> &NewValueNumberInfo) { // Try to do the least amount of work possible. In particular, if there are // more liverange chunks in the other set than there are in the 'this' set, @@ -300,7 +301,7 @@ void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments, // we want to avoid the interval scan if not. bool MustMapCurValNos = false; for (unsigned i = 0, e = getNumValNums(); i != e; ++i) { - if (InstDefiningValue[i] == ~2U) continue; // tombstone value # + if (ValueNumberInfo[i].first == ~2U) continue; // tombstone value # if (i != (unsigned)LHSValNoAssignments[i]) { MustMapCurValNos = true; break; @@ -345,9 +346,8 @@ void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments, InsertPos = addRangeFrom(*I, InsertPos); } - InstDefiningValue.clear(); - InstDefiningValue.append(NewInstDefiningValue.begin(), - NewInstDefiningValue.end()); + ValueNumberInfo.clear(); + ValueNumberInfo.append(NewValueNumberInfo.begin(), NewValueNumberInfo.end()); weight += Other.weight; } @@ -360,7 +360,7 @@ void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers) { // Find a value # to use for the clobber ranges. If there is already a value# // for unknown values, use it. // FIXME: Use a single sentinal number for these! - unsigned ClobberValNo = getNextValue(~0U); + unsigned ClobberValNo = getNextValue(~0U, 0); iterator IP = begin(); for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) { @@ -399,7 +399,7 @@ void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) { // Make sure V2 is smaller than V1. if (V1 < V2) { - setInstDefiningValNum(V1, getInstForValNum(V2)); + setValueNumberInfo(V1, getValNumInfo(V2)); std::swap(V1, V2); } @@ -443,10 +443,10 @@ void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) { // ~1U so it can be nuked later. if (V1 == getNumValNums()-1) { do { - InstDefiningValue.pop_back(); - } while (InstDefiningValue.back() == ~1U); + ValueNumberInfo.pop_back(); + } while (ValueNumberInfo.back().first == ~1U); } else { - InstDefiningValue[V1] = ~1U; + ValueNumberInfo[V1].first = ~1U; } } @@ -482,10 +482,10 @@ void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const { for (unsigned i = 0; i != getNumValNums(); ++i) { if (i) OS << " "; OS << i << "@"; - if (InstDefiningValue[i] == ~0U) { + if (ValueNumberInfo[i].first == ~0U) { OS << "?"; } else { - OS << InstDefiningValue[i]; + OS << ValueNumberInfo[i].first; } } } diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 0e9609cdcc6..82389b20b32 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -138,10 +138,10 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { for (MachineFunction::livein_iterator I = fn.livein_begin(), E = fn.livein_end(); I != E; ++I) { handlePhysicalRegisterDef(Entry, Entry->begin(), - getOrCreateInterval(I->first), true); + getOrCreateInterval(I->first), 0); for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS) handlePhysicalRegisterDef(Entry, Entry->begin(), - getOrCreateInterval(*AS), true); + getOrCreateInterval(*AS), 0); } } @@ -321,7 +321,7 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { // the spill weight is now infinity as it // cannot be spilled again nI.weight = float(HUGE_VAL); - LiveRange LR(start, end, nI.getNextValue(~0U)); + LiveRange LR(start, end, nI.getNextValue(~0U, 0)); DEBUG(std::cerr << " +" << LR); nI.addRange(LR); added.push_back(&nI); @@ -366,7 +366,13 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // Get the Idx of the defining instructions. unsigned defIndex = getDefIndex(getInstructionIndex(mi)); - unsigned ValNum = interval.getNextValue(defIndex); + 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. @@ -455,12 +461,13 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // that at this point, there should be exactly one value number in it. assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); - // The new value number is defined by the instruction we claimed defined - // value #0. - unsigned ValNo = interval.getNextValue(DefIndex); + // 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#1 is now defined by the 2-addr instruction. - interval.setInstDefiningValNum(0, RedefIndex); + // 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); @@ -493,7 +500,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // 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)); + LiveRange LR(Start, End, interval.getNextValue(~0U, 0)); DEBUG(std::cerr << " replace range with " << LR); interval.addRange(LR); DEBUG(std::cerr << "RESULT: "; interval.print(std::cerr, mri_)); @@ -503,9 +510,16 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // 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 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(defIndex)); + getInstructionIndex(&mbb->back()) + InstrSlots::NUM, ValNum); interval.addRange(LR); DEBUG(std::cerr << " +" << LR); } @@ -516,8 +530,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator mi, - LiveInterval& interval, - bool isLiveIn) { + 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)); @@ -551,13 +565,14 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // The only case we should have a dead physreg here without a killing or // instruction where we know it's dead is if it is live-in to the function // and never used. - assert(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?"); - LiveRange LR(start, end, interval.getNextValue(isLiveIn ? ~0U : start)); + LiveRange LR(start, end, interval.getNextValue(SrcReg != 0 ? start : ~0U, + SrcReg)); interval.addRange(LR); DEBUG(std::cerr << " +" << LR << '\n'); } @@ -568,9 +583,12 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, if (MRegisterInfo::isVirtualRegister(reg)) handleVirtualRegisterDef(MBB, MI, getOrCreateInterval(reg)); else if (allocatableRegs_[reg]) { - handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg)); + unsigned SrcReg, DstReg; + if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) + SrcReg = 0; + handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg), SrcReg); for (const unsigned* AS = mri_->getAliasSet(reg); *AS; ++AS) - handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS), true); + handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS), 0); } } @@ -652,24 +670,17 @@ bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, // If AValNo is defined as a copy from IntB, we can potentially process this. // Get the instruction that defines this value number. - unsigned AValNoInstIdx = IntA.getInstForValNum(AValNo); - - // If it's unknown, ignore it. - if (AValNoInstIdx == ~0U || AValNoInstIdx == ~1U) return false; - // Otherwise, get the instruction for it. - MachineInstr *AValNoInstMI = getInstructionFromIndex(AValNoInstIdx); + unsigned SrcReg = IntA.getSrcRegForValNum(AValNo); + if (!SrcReg) return false; // Not defined by a copy. // If the value number is not defined by a copy instruction, ignore it. - unsigned SrcReg, DstReg; - if (!tii_->isMoveInstr(*AValNoInstMI, SrcReg, DstReg)) - return false; // If the source register comes from an interval other than IntB, we can't // handle this. - assert(rep(DstReg) == IntA.reg && "Not defining a reg in IntA?"); 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 @@ -687,7 +698,7 @@ bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, // We are about to delete CopyMI, so need to remove it as the 'instruction // that defines this value #'. - IntB.setInstDefiningValNum(BValNo, ~0U); + 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 @@ -701,7 +712,7 @@ bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, for (const unsigned *AS = mri_->getAliasSet(IntB.reg); *AS; ++AS) { LiveInterval &AliasLI = getInterval(*AS); AliasLI.addRange(LiveRange(FillerStart, FillerEnd, - AliasLI.getNextValue(~0U))); + AliasLI.getNextValue(~0U, 0))); } } @@ -832,7 +843,8 @@ bool LiveIntervals::JoinCopy(MachineInstr *CopyMI, /// contains the value number the copy is from. /// static unsigned ComputeUltimateVN(unsigned VN, - SmallVector &InstDefiningValue, + SmallVector, 16> &ValueNumberInfo, SmallVector &ThisFromOther, SmallVector &OtherFromThis, SmallVector &ThisValNoAssignments, @@ -847,8 +859,8 @@ static unsigned ComputeUltimateVN(unsigned VN, // number in the destination. int OtherValNo = ThisFromOther[VN]; if (OtherValNo == -1) { - InstDefiningValue.push_back(ThisLI.getInstForValNum(VN)); - return ThisValNoAssignments[VN] = InstDefiningValue.size()-1; + ValueNumberInfo.push_back(ThisLI.getValNumInfo(VN)); + return ThisValNoAssignments[VN] = ValueNumberInfo.size()-1; } // Otherwise, this *is* a copy from the RHS. Mark this value number as @@ -856,7 +868,7 @@ static unsigned ComputeUltimateVN(unsigned VN, // value is. ThisValNoAssignments[VN] = -2; unsigned UltimateVN = - ComputeUltimateVN(OtherValNo, InstDefiningValue, + ComputeUltimateVN(OtherValNo, ValueNumberInfo, OtherFromThis, ThisFromOther, OtherValNoAssignments, ThisValNoAssignments, OtherLI, ThisLI); @@ -875,24 +887,17 @@ bool LiveIntervals::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { SmallVector LHSValsDefinedFromRHS; LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), -1); for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { - unsigned ValInst = LHS.getInstForValNum(VN); - if (ValInst == ~0U || ValInst == ~1U) - continue; - - // If the instruction defining the LHS's value is a copy. - MachineInstr *ValInstMI = getInstructionFromIndex(ValInst); - - // If the value number is not defined by a copy instruction, ignore it. - unsigned SrcReg, DstReg; - if (!tii_->isMoveInstr(*ValInstMI, SrcReg, DstReg)) + 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(SrcReg) != RHS.reg) + 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; } @@ -901,24 +906,17 @@ bool LiveIntervals::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { SmallVector RHSValsDefinedFromLHS; RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), -1); for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { - unsigned ValInst = RHS.getInstForValNum(VN); - if (ValInst == ~0U || ValInst == ~1U) - continue; - - // If the instruction defining the RHS's value is a copy. - MachineInstr *ValInstMI = getInstructionFromIndex(ValInst); - - // If the value number is not defined by a copy instruction, ignore it. - unsigned SrcReg, DstReg; - if (!tii_->isMoveInstr(*ValInstMI, SrcReg, DstReg)) + 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(SrcReg) != LHS.reg) + 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; } @@ -926,20 +924,20 @@ bool LiveIntervals::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { // assuming that the live ranges can be coallesced. SmallVector LHSValNoAssignments; SmallVector RHSValNoAssignments; - SmallVector InstDefiningValue; + SmallVector, 16> ValueNumberInfo; LHSValNoAssignments.resize(LHS.getNumValNums(), -1); RHSValNoAssignments.resize(RHS.getNumValNums(), -1); // Compute ultimate value numbers for the LHS and RHS values. for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { if (LHS.getInstForValNum(VN) == ~2U) continue; - ComputeUltimateVN(VN, InstDefiningValue, + ComputeUltimateVN(VN, ValueNumberInfo, LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, LHSValNoAssignments, RHSValNoAssignments, LHS, RHS); } for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { if (RHS.getInstForValNum(VN) == ~2U) continue; - ComputeUltimateVN(VN, InstDefiningValue, + ComputeUltimateVN(VN, ValueNumberInfo, RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, RHSValNoAssignments, LHSValNoAssignments, RHS, LHS); } @@ -989,7 +987,7 @@ bool LiveIntervals::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { // 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], - InstDefiningValue); + ValueNumberInfo); return true; } -- 2.34.1