Index: include/llvm/CodeGen/LiveInterval.h =================================================================== --- include/llvm/CodeGen/LiveInterval.h +++ include/llvm/CodeGen/LiveInterval.h @@ -225,19 +225,9 @@ /// Constructs a new LiveRange object by copying segments and valnos from /// another LiveRange. - LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator) + LiveRange(const LiveRange &Other, VNInfo::Allocator &Allocator) : segmentSet(nullptr) { - assert(Other.segmentSet == nullptr && - "Copying of LiveRanges with active SegmentSets is not supported"); - - // Duplicate valnos. - for (const VNInfo *VNI : Other.valnos) { - createValueCopy(VNI, Allocator); - } - // Now we can copy segments and remap their valnos. - for (const Segment &S : Other.segments) { - segments.push_back(Segment(S.start, S.end, valnos[S.valno->id])); - } + copyFrom(Other, Allocator); } ~LiveRange() { delete segmentSet; } @@ -319,15 +309,9 @@ /// add liveness for a dead def. VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator); - /// Create a copy of the given value. The new value will be identical except - /// for the Value number. - VNInfo *createValueCopy(const VNInfo *orig, - VNInfo::Allocator &VNInfoAllocator) { - VNInfo *VNI = - new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig); - valnos.push_back(VNI); - return VNI; - } + /// Copy range @p Other into this range. This is done by duplicating the + /// value numbers and recreating all segments with these numbers. + void copyFrom(const LiveRange &Other, VNInfo::Allocator &Allocator); /// RenumberValues - Renumber all values in order of appearance and remove /// unused values. @@ -708,10 +692,6 @@ /// are not considered valid and should only exist temporarily). void removeEmptySubRanges(); - /// Construct main live range by merging the SubRanges of @p LI. - void constructMainRangeFromSubranges(const SlotIndexes &Indexes, - VNInfo::Allocator &VNIAllocator); - /// getSize - Returns the sum of sizes of all the LiveRange's. /// unsigned getSize() const; Index: lib/CodeGen/LiveInterval.cpp =================================================================== --- lib/CodeGen/LiveInterval.cpp +++ lib/CodeGen/LiveInterval.cpp @@ -741,6 +741,19 @@ return V2; } +void LiveRange::copyFrom(const LiveRange &Other, VNInfo::Allocator &Allocator) { + assert(valnos.empty() && segments.empty() && "this range must be empty"); + assert(Other.segmentSet == nullptr && + "Copying of LiveRanges with active SegmentSets is not supported"); + + // Duplicate valnos. + for (const VNInfo *VNI : Other.valnos) + getNextValue(VNI->def, Allocator); + // Now we can copy segments and remap their valnos. + for (const Segment &S : Other.segments) + segments.push_back(Segment(S.start, S.end, valnos[S.valno->id])); +} + void LiveRange::flushSegmentSet() { assert(segmentSet != nullptr && "segment set must have been created"); assert( @@ -784,211 +797,6 @@ SubRanges = nullptr; } -/// Helper function for constructMainRangeFromSubranges(): Search the CFG -/// backwards until we find a place covered by a LiveRange segment that actually -/// has a valno set. -static VNInfo *searchForVNI(const SlotIndexes &Indexes, LiveRange &LR, - const MachineBasicBlock *MBB, - SmallPtrSetImpl &Visited) { - // We start the search at the end of MBB. - SlotIndex EndIdx = Indexes.getMBBEndIdx(MBB); - // In our use case we can't live the area covered by the live segments without - // finding an actual VNI def. - LiveRange::iterator I = LR.find(EndIdx.getPrevSlot()); - assert(I != LR.end()); - LiveRange::Segment &S = *I; - if (S.valno != nullptr) - return S.valno; - - VNInfo *VNI = nullptr; - // Continue at predecessors (we could even go to idom with domtree available). - for (const MachineBasicBlock *Pred : MBB->predecessors()) { - // Avoid going in circles. - if (!Visited.insert(Pred).second) - continue; - - VNI = searchForVNI(Indexes, LR, Pred, Visited); - if (VNI != nullptr) { - S.valno = VNI; - break; - } - } - - return VNI; -} - -static void determineMissingVNIs(const SlotIndexes &Indexes, LiveInterval &LI) { - SmallPtrSet Visited; - for (LiveRange::Segment &S : LI.segments) { - if (S.valno != nullptr) - continue; - // This can only happen at the begin of a basic block. - assert(S.start.isBlock() && "valno should only be missing at block begin"); - - Visited.clear(); - const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(S.start); - for (const MachineBasicBlock *Pred : MBB->predecessors()) { - VNInfo *VNI = searchForVNI(Indexes, LI, Pred, Visited); - if (VNI != nullptr) { - S.valno = VNI; - break; - } - } - assert(S.valno != nullptr && "could not determine valno"); - } -} - -void LiveInterval::constructMainRangeFromSubranges( - const SlotIndexes &Indexes, VNInfo::Allocator &VNIAllocator) { - // The basic observations on which this algorithm is based: - // - Each Def/ValNo in a subrange must have a corresponding def on the main - // range, but not further defs/valnos are necessary. - // - If any of the subranges is live at a point the main liverange has to be - // live too, conversily if no subrange is live the main range mustn't be - // live either. - // We do this by scannig through all the subranges simultaneously creating new - // segments in the main range as segments start/ends come up in the subranges. - assert(hasSubRanges() && "expected subranges to be present"); - assert(segments.empty() && valnos.empty() && "expected empty main range"); - - // Collect subrange, iterator pairs for the walk and determine first and last - // SlotIndex involved. - SmallVector, 4> SRs; - SlotIndex First; - SlotIndex Last; - for (const SubRange &SR : subranges()) { - if (SR.empty()) - continue; - SRs.push_back(std::make_pair(&SR, SR.begin())); - if (!First.isValid() || SR.segments.front().start < First) - First = SR.segments.front().start; - if (!Last.isValid() || SR.segments.back().end > Last) - Last = SR.segments.back().end; - } - - // Walk over all subranges simultaneously. - Segment CurrentSegment; - bool ConstructingSegment = false; - bool NeedVNIFixup = false; - unsigned ActiveMask = 0; - SlotIndex Pos = First; - while (true) { - SlotIndex NextPos = Last; - enum { - NOTHING, - BEGIN_SEGMENT, - END_SEGMENT, - } Event = NOTHING; - // Which subregister lanes are affected by the current event. - unsigned EventMask = 0; - // Whether a BEGIN_SEGMENT is also a valno definition point. - bool IsDef = false; - // Find the next begin or end of a subrange segment. Combine masks if we - // have multiple begins/ends at the same position. Ends take precedence over - // Begins. - for (auto &SRP : SRs) { - const SubRange &SR = *SRP.first; - const_iterator &I = SRP.second; - // Advance iterator of subrange to a segment involving Pos; the earlier - // segments are already merged at this point. - while (I != SR.end() && - (I->end < Pos || - (I->end == Pos && (ActiveMask & SR.LaneMask) == 0))) - ++I; - if (I == SR.end()) - continue; - if ((ActiveMask & SR.LaneMask) == 0 && - Pos <= I->start && I->start <= NextPos) { - // Merge multiple begins at the same position. - if (I->start == NextPos && Event == BEGIN_SEGMENT) { - EventMask |= SR.LaneMask; - IsDef |= I->valno->def == I->start; - } else if (I->start < NextPos || Event != END_SEGMENT) { - Event = BEGIN_SEGMENT; - NextPos = I->start; - EventMask = SR.LaneMask; - IsDef = I->valno->def == I->start; - } - } - if ((ActiveMask & SR.LaneMask) != 0 && - Pos <= I->end && I->end <= NextPos) { - // Merge multiple ends at the same position. - if (I->end == NextPos && Event == END_SEGMENT) - EventMask |= SR.LaneMask; - else { - Event = END_SEGMENT; - NextPos = I->end; - EventMask = SR.LaneMask; - } - } - } - - // Advance scan position. - Pos = NextPos; - if (Event == BEGIN_SEGMENT) { - if (ConstructingSegment && IsDef) { - // Finish previous segment because we have to start a new one. - CurrentSegment.end = Pos; - append(CurrentSegment); - ConstructingSegment = false; - } - - // Start a new segment if necessary. - if (!ConstructingSegment) { - // Determine value number for the segment. - VNInfo *VNI; - if (IsDef) { - VNI = getNextValue(Pos, VNIAllocator); - } else { - // We have to reuse an existing value number, if we are lucky - // then we already passed one of the predecessor blocks and determined - // its value number (with blocks in reverse postorder this would be - // always true but we have no such guarantee). - assert(Pos.isBlock()); - const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Pos); - // See if any of the predecessor blocks has a lower number and a VNI - for (const MachineBasicBlock *Pred : MBB->predecessors()) { - SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred); - VNI = getVNInfoBefore(PredEnd); - if (VNI != nullptr) - break; - } - // Def will come later: We have to do an extra fixup pass. - if (VNI == nullptr) - NeedVNIFixup = true; - } - - CurrentSegment.start = Pos; - CurrentSegment.valno = VNI; - ConstructingSegment = true; - } - ActiveMask |= EventMask; - } else if (Event == END_SEGMENT) { - assert(ConstructingSegment); - // Finish segment if no lane is active anymore. - ActiveMask &= ~EventMask; - if (ActiveMask == 0) { - CurrentSegment.end = Pos; - append(CurrentSegment); - ConstructingSegment = false; - } - } else { - // We reached the end of the last subranges and can stop. - assert(Event == NOTHING); - break; - } - } - - // We might not be able to assign new valnos for all segments if the basic - // block containing the definition comes after a segment using the valno. - // Do a fixup pass for this uncommon case. - if (NeedVNIFixup) - determineMissingVNIs(Indexes, *this); - - assert(ActiveMask == 0 && !ConstructingSegment && "all segments ended"); - verify(); -} - unsigned LiveInterval::getSize() const { unsigned Sum = 0; for (const Segment &S : segments) Index: lib/CodeGen/LiveRangeCalc.h =================================================================== --- lib/CodeGen/LiveRangeCalc.h +++ lib/CodeGen/LiveRangeCalc.h @@ -236,6 +236,9 @@ /// Every predecessor of a live-in block must have been given a value with /// setLiveOutValue, the value may be null for live-trough blocks. void calculateValues(); + + /// Construct main live range by merging the SubRanges of @p LI. + void computeMainRangeFromSubranges(LiveInterval &LI); }; } // end namespace llvm Index: lib/CodeGen/LiveRangeCalc.cpp =================================================================== --- lib/CodeGen/LiveRangeCalc.cpp +++ lib/CodeGen/LiveRangeCalc.cpp @@ -14,6 +14,7 @@ #include "LiveRangeCalc.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Support/Debug.h" using namespace llvm; @@ -120,7 +121,7 @@ extendToUses(S, Reg, S.LaneMask); } LI.clear(); - LI.constructMainRangeFromSubranges(*Indexes, *Alloc); + computeMainRangeFromSubranges(LI); } else { resetLiveOutMap(); extendToUses(LI, Reg, ~0u); @@ -459,3 +460,59 @@ } } while (Changes); } + +void LiveRangeCalc::computeMainRangeFromSubranges(LiveInterval &LI) { + // The basic observations on which this algorithm is based: + // - Each Def/ValNo in a subrange must have a corresponding def on the main + // range. + // - If any of the subranges is live at a point the main liverange has to be + // live too, conversily where no subrange is live the main range mustn't be + // live either. + assert(LI.hasSubRanges() && "expected subranges to be present"); + assert(LI.segments.empty() && LI.valnos.empty() && + "expected empty main range"); + + // Shortcut: If we only have a single subrange, then we can simply copy that + // to the main range and are done. + auto I = LI.subrange_begin(); + ++I; + if (I == LI.subrange_end()) { + LI.copyFrom(*LI.subrange_begin(), *Alloc); + return; + } + + // Recreate all defpoints of the subregister ranges in the main liverange. We + // also search for subregister defs without read-undef that should be regarded + // as uses later. + SmallVector AdditionalUses; + for (const LiveInterval::SubRange &SR : LI.subranges()) { + for (const VNInfo *VNI : SR.valnos) { + // We can ignore PHI defs, they will be recreated during SSA construction. + if (VNI->isPHIDef()) + continue; + LI.createDeadDef(VNI->def, *Alloc); + // If another subregister crosses the def point, then this must be a + // subreg def without a read-undef marker. + for (LiveInterval::SubRange &SR2 : LI.subranges()) { + if (&SR2 == &SR) + continue; + LiveQueryResult LRQ = SR2.Query(VNI->def); + if (LRQ.valueIn() != nullptr && LRQ.valueIn() == LRQ.valueOut()) + AdditionalUses.push_back(VNI->def); + } + } + } + + // Consider all subrange live segment endpoints and the previously collected + // subreg-defs as uses and construct SSA form as necessary. + resetLiveOutMap(); + LiveIn.clear(); + for (const LiveInterval::SubRange &SR : LI.subranges()) { + for (const LiveRange::Segment &S : SR.segments) + extend(LI, S.end, 0); + } + for (const SlotIndex &I : AdditionalUses) + extend(LI, I, 0); + + LI.verify(); +}