Index: lib/CodeGen/LiveIntervalAnalysis.cpp =================================================================== --- lib/CodeGen/LiveIntervalAnalysis.cpp +++ lib/CodeGen/LiveIntervalAnalysis.cpp @@ -332,69 +332,66 @@ static void createSegmentsForValues(LiveRange &LR, - iterator_range VNIs) { + iterator_range VNIs, + VNInfo::Allocator &VNA) { for (auto VNI : VNIs) { - if (VNI->isUnused()) - continue; - SlotIndex Def = VNI->def; - LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI)); + if (!VNI->isUnused() && !VNI->isPHIDef()) + LR.createDeadDef(VNI->def, VNA); } } -typedef SmallVector, 16> ShrinkToUsesWorkList; - -static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes, - ShrinkToUsesWorkList &WorkList, - const LiveRange &OldRange) { - // Keep track of the PHIs that are in use. - SmallPtrSet UsedPHIs; - // Blocks that have already been added to WorkList as live-out. - SmallPtrSet LiveOut; - - // Extend intervals to reach all uses in WorkList. - while (!WorkList.empty()) { - SlotIndex Idx = WorkList.back().first; - VNInfo *VNI = WorkList.back().second; - WorkList.pop_back(); - const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot()); - SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB); - - // Extend the live range for VNI to be live at Idx. - if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) { - assert(ExtVNI == VNI && "Unexpected existing value number"); - (void)ExtVNI; - // Is this a PHIDef we haven't seen before? - if (!VNI->isPHIDef() || VNI->def != BlockStart || - !UsedPHIs.insert(VNI).second) - continue; - // The PHI is live, make sure the predecessors are live-out. - for (auto &Pred : MBB->predecessors()) { - if (!LiveOut.insert(Pred).second) - continue; - SlotIndex Stop = Indexes.getMBBEndIdx(Pred); - // A predecessor is not required to have a live-out value for a PHI. - if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop)) - WorkList.push_back(std::make_pair(Stop, PVNI)); - } + +/// Update segments in DstLR to match segments from SrcLR while preserving +/// value numbers in DstLR. +/// Return true if any PHI-defined value has become unused. +static bool transferSegments(LiveRange &DstLR, LiveRange &SrcLR) { + BitVector UsedVNs(DstLR.valnos.size()); + std::map VMap; + for (VNInfo *V : make_range(DstLR.vni_begin(), DstLR.vni_end())) + if (!V->isUnused()) + VMap.insert(std::make_pair(V->def, V)); + + // Iterate over all segments in DstLR. If the corresponding segment exists + // in SrcLR, copy over the end-point, otherwise mark the segment as dead. + LiveRange::iterator SI = SrcLR.begin(), SE = SrcLR.end(); + for (auto DI = DstLR.begin(), DE = DstLR.end(); DI != DE || SI != SE; ) { + if (SI == SE || (DI != DE && DI->start < SI->start)) { + // If we reached the end of SrcLR, or if DI points to a segment that + // is missing in SrcLR, remove it from DstLR. + assert(DI->start.isBlock()); + DI = DstLR.removeSegment(DI); + DE = DstLR.end(); continue; } - - // VNI is live-in to MBB. - DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); - LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); - - // Make sure VNI is live-out from the predecessors. - for (auto &Pred : MBB->predecessors()) { - if (!LiveOut.insert(Pred).second) - continue; - SlotIndex Stop = Indexes.getMBBEndIdx(Pred); - assert(OldRange.getVNInfoBefore(Stop) == VNI && - "Wrong value out of predecessor"); - WorkList.push_back(std::make_pair(Stop, VNI)); + if (DI == DE || DI->start > SI->start) { + // If we reached the end of DstLR, or SI points to a segment that is + // missing in DstLR, insert it into DstLR. + SlotIndex SD = SI->valno->def; + DI = DstLR.addSegment(LiveRange::Segment(SI->start, SI->end, VMap[SD])); + DE = DstLR.end(); + } else { + // Found a matching segment in both ranges, update DstLR. + assert(DI != DE && DI->start == SI->start); + DI->end = SI->end; } + UsedVNs.set(DI->valno->id); + ++SI; + ++DI; + } + + bool Removed = false; + for (VNInfo *V : make_range(DstLR.vni_begin(), DstLR.vni_end())) { + if (V->isUnused() || UsedVNs.test(V->id)) + continue; + if (V->isPHIDef()) + Removed = true; + V->markUnused(); } + + return Removed; } + bool LiveIntervals::shrinkToUses(LiveInterval *li, SmallVectorImpl *dead) { DEBUG(dbgs() << "Shrink: " << *li << '\n'); @@ -411,8 +408,27 @@ if (NeedsCleanup) li->removeEmptySubRanges(); - // Find all the values used, including PHI kills. - ShrinkToUsesWorkList WorkList; + // Create new live ranges with only minimal live segments per def. + // + // Use LiveRangeCalc to extend the live range NewLR to all uses. + // This requires that NewLR does not have any non-register defs. + // In particular, NewLR should not have any PHI defs. The reason is + // that such defs would prevent the originating register defs from + // being extended, since they may only reach the PHI defs. + // LiveRangeCalc assumes that it is the only creator of PHI defs in + // the given range. + // The catch is, however, that any value number added by LRC may + // no longer match its counterpart from li. To make sure that the + // value numbers in li remain unchanged, the segments from NewLR + // will be copied back into li, while preserving the value number + // information. + LiveRange NewLR; + createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end()), + getVNInfoAllocator()); + LiveRangeCalc LRC; + LRC.reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); + // Main range does not need undefs. + const SmallVector NoUndefs; // Visit all instructions reading li->reg. for (MachineRegisterInfo::reg_instr_iterator @@ -438,19 +454,14 @@ if (VNInfo *DefVNI = LRQ.valueDefined()) Idx = DefVNI->def; - WorkList.push_back(std::make_pair(Idx, VNI)); + LRC.extend(NewLR, Idx, 0, NoUndefs); } - // Create new live ranges with only minimal live segments per def. - LiveRange NewLR; - createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end())); - extendSegmentsToUses(NewLR, *Indexes, WorkList, *li); - - // Move the trimmed segments back. - li->segments.swap(NewLR.segments); + // Move the trimmed segments back, preserving the value numbers. + bool CanSeparate = transferSegments(*li, NewLR); // Handle dead values. - bool CanSeparate = computeDeadValues(*li, dead); + CanSeparate |= computeDeadValues(*li, dead); DEBUG(dbgs() << "Shrunk: " << *li << '\n'); return CanSeparate; } @@ -501,8 +512,17 @@ DEBUG(dbgs() << "Shrink: " << SR << '\n'); assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Can only shrink virtual registers"); + + LiveInterval &LI = getInterval(Reg); + SmallVector Undefs; + LI.computeSubRangeUndefs(Undefs, SR.LaneMask, *MRI, *getSlotIndexes()); + // Find all the values used, including PHI kills. - ShrinkToUsesWorkList WorkList; + LiveRange NewLR; + createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end()), + getVNInfoAllocator()); + LiveRangeCalc LRC; + LRC.reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); // Visit all instructions reading Reg. SlotIndex LastIdx; @@ -536,16 +556,11 @@ if (VNInfo *DefVNI = LRQ.valueDefined()) Idx = DefVNI->def; - WorkList.push_back(std::make_pair(Idx, VNI)); + LRC.extend(NewLR, Idx, 0, Undefs); } - // Create a new live ranges with only minimal live segments per def. - LiveRange NewLR; - createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end())); - extendSegmentsToUses(NewLR, *Indexes, WorkList, SR); - - // Move the trimmed ranges back. - SR.segments.swap(NewLR.segments); + // Move the trimmed ranges back, preserving the value numbers. + transferSegments(SR, NewLR); // Remove dead PHI value numbers for (auto VNI : SR.valnos) {