Changes in directory llvm/include/llvm/CodeGen:
LiveInterval.h updated: 1.19 -> 1.20 LiveIntervalAnalysis.h updated: 1.53 -> 1.54 --- Log message: Take advantage of the recent improvements to the liveintervals set (tracking instructions which define each value#) to simplify and improve the coallescer. In particular, this patch: 1. Implements iterative coallescing. 2. Reverts an unsafe hack from handlePhysRegDef, superceeding it with a better solution. 3. Implements PR865: http://llvm.org/PR865 , "coallescing" away the second copy in code like: A = B ... B = A This also includes changes to symbolically print registers in intervals when possible. --- Diffs of the changes: (+62 -17) LiveInterval.h | 25 +++++++++++++++++++--- LiveIntervalAnalysis.h | 54 ++++++++++++++++++++++++++++++++++++------------- 2 files changed, 62 insertions(+), 17 deletions(-) Index: llvm/include/llvm/CodeGen/LiveInterval.h diff -u llvm/include/llvm/CodeGen/LiveInterval.h:1.19 llvm/include/llvm/CodeGen/LiveInterval.h:1.20 --- llvm/include/llvm/CodeGen/LiveInterval.h:1.19 Tue Aug 22 13:19:46 2006 +++ llvm/include/llvm/CodeGen/LiveInterval.h Thu Aug 24 17:43:55 2006 @@ -82,7 +82,7 @@ /// 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. + /// which is treated as unknown, or ~1, which is a deleted value number. SmallVector<unsigned, 4> InstDefiningValue; public: @@ -116,10 +116,13 @@ std::swap(weight, other.weight); std::swap(ranges, other.ranges); std::swap(NumValues, other.NumValues); + std::swap(InstDefiningValue, other.InstDefiningValue); } bool containsOneValue() const { return NumValues == 1; } + unsigned getNumValNums() const { return NumValues; } + /// getNextValue - Create a new value number and return it. MIIdx specifies /// the instruction that defines the value number. unsigned getNextValue(unsigned MIIdx) { @@ -138,6 +141,12 @@ void setInstDefiningValNum(unsigned ValNo, unsigned MIIdx) { InstDefiningValue[ValNo] = MIIdx; } + + /// MergeValueNumberInto - This method is called when two value nubmers + /// are found to be equivalent. This eliminates V1, replacing all + /// LiveRanges with the V1 value number with the V2 value number. This can + /// cause merging of V1/V2 values numbers and compaction of the value space. + void MergeValueNumberInto(unsigned V1, unsigned V2); bool empty() const { return ranges.empty(); } @@ -163,9 +172,19 @@ /// getLiveRangeContaining - Return the live range that contains the /// specified index, or null if there is none. - const LiveRange *getLiveRangeContaining(unsigned Idx) const; - + const LiveRange *getLiveRangeContaining(unsigned Idx) const { + const_iterator I = FindLiveRangeContaining(Idx); + return I == end() ? 0 : &*I; + } + /// FindLiveRangeContaining - Return an iterator to the live range that + /// contains the specified index, or end() if there is none. + const_iterator FindLiveRangeContaining(unsigned Idx) const; + + /// FindLiveRangeContaining - Return an iterator to the live range that + /// contains the specified index, or end() if there is none. + iterator FindLiveRangeContaining(unsigned Idx); + /// joinable - Two intervals are joinable if the either don't overlap at all /// or if the destination of the copy is a single assignment value, and it /// only overlaps with one value in the source interval. Index: llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h diff -u llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h:1.53 llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h:1.54 --- llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h:1.53 Fri May 12 01:06:34 2006 +++ llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h Thu Aug 24 17:43:55 2006 @@ -53,8 +53,18 @@ std::vector<bool> allocatableRegs_; public: - struct InstrSlots - { + struct CopyRec { + MachineInstr *MI; + unsigned SrcReg, DstReg; + }; + CopyRec getCopyRec(MachineInstr *MI, unsigned SrcReg, unsigned DstReg) { + CopyRec R; + R.MI = MI; + R.SrcReg = SrcReg; + R.DstReg = DstReg; + return R; + } + struct InstrSlots { enum { LOAD = 0, USE = 1, @@ -133,16 +143,37 @@ virtual void print(std::ostream &O, const Module* = 0) const; private: + /// RemoveMachineInstrFromMaps - This marks the specified machine instr as + /// deleted. + void RemoveMachineInstrFromMaps(MachineInstr *MI) { + // remove index -> MachineInstr and + // MachineInstr -> index mappings + Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI); + if (mi2i != mi2iMap_.end()) { + i2miMap_[mi2i->second/InstrSlots::NUM] = 0; + mi2iMap_.erase(mi2i); + } + } + /// computeIntervals - compute live intervals void computeIntervals(); /// joinIntervals - join compatible live intervals void joinIntervals(); - /// joinIntervalsInMachineBB - Join intervals based on move - /// instructions in the specified basic block. - void joinIntervalsInMachineBB(MachineBasicBlock *MBB); - + /// CopyCoallesceInMBB - Coallsece copies in the specified MBB, putting + /// copies that cannot yet be coallesced into the "TryAgain" list. + void CopyCoallesceInMBB(MachineBasicBlock *MBB, + std::vector<CopyRec> &TryAgain); + + /// 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 JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned DstReg); + /// handleRegisterDef - update intervals for a register def /// (calls handlePhysicalRegisterDef and /// handleVirtualRegisterDef) @@ -157,14 +188,10 @@ LiveInterval& interval); /// handlePhysicalRegisterDef - update intervals for a physical register - /// def. If the defining instruction is a move instruction, SrcReg will be - /// the input register, and DestReg will be the result. Note that Interval - /// may not match DestReg (it might be an alias instead). - /// + /// def. void handlePhysicalRegisterDef(MachineBasicBlock* mbb, MachineBasicBlock::iterator mi, LiveInterval& interval, - unsigned SrcReg, unsigned DestReg, bool isLiveIn = false); /// Return true if the two specified registers belong to different @@ -172,9 +199,8 @@ bool differingRegisterClasses(unsigned RegA, unsigned RegB) const; - bool AdjustIfAllOverlappingRangesAreCopiesFrom(LiveInterval &IntA, - LiveInterval &IntB, - unsigned CopyIdx); + bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, + MachineInstr *CopyMI, unsigned CopyIdx); bool overlapsAliases(const LiveInterval *lhs, const LiveInterval *rhs) const; _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
