From b82636bb80702d56b78dca84a3ec9cfe8ac41c3b Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Thu, 18 Dec 2014 19:58:52 +0000 Subject: [PATCH] LiveIntervalAnalysis: Cleanup computeDeadValues - This also fixes a bug introduced in r223880 where values were not correctly marked as Dead anymore. - Cleanup computeDeadValues(): split up SubRange code variant, simplify arguments. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@224538 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveInterval.h | 6 +++ include/llvm/CodeGen/LiveIntervalAnalysis.h | 20 ++++---- lib/CodeGen/LiveIntervalAnalysis.cpp | 57 ++++++++++++--------- 3 files changed, 48 insertions(+), 35 deletions(-) diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 594767a4ea6..3d0e373dada 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -472,6 +472,12 @@ namespace llvm { removeSegment(S.start, S.end, RemoveDeadValNo); } + /// Remove segment pointed to by iterator @p I from this range. This does + /// not remove dead value numbers. + iterator removeSegment(iterator I) { + return segments.erase(I); + } + /// Query Liveness at Idx. /// The sub-instruction slot of Idx doesn't matter, only the instruction /// it refers to is considered. diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 7d79f627501..d8c921fce31 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -158,7 +158,7 @@ namespace llvm { /// shrinkToUses(LiveInterval *li, SmallVectorImpl *dead) /// that works on a subregister live range and only looks at uses matching /// the lane mask of the subregister range. - bool shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg); + void shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg); /// extendToIndices - Extend the live range of LI to reach all points in /// Indices. The points in the Indices array must be jointly dominated by @@ -406,17 +406,15 @@ namespace llvm { /// Compute RegMaskSlots and RegMaskBits. void computeRegMasks(); - /// \brief Walk the values in the @p LR live range and compute which ones - /// are dead in live range @p Segments. Dead values are not deleted, - /// however: + /// Walk the values in @p LI and check for dead values: /// - Dead PHIDef values are marked as unused. - /// - if @p dead != nullptr then dead operands are marked as such and - /// completely dead machine instructions are added to the @p dead vector. - /// - CanSeparate is set to true if the interval may have been separated - /// into multiple connected components. - void computeDeadValues(LiveRange &Segments, LiveRange &LR, - bool *CanSeparate = nullptr, unsigned Reg = 0, - SmallVectorImpl *dead = nullptr); + /// - Dead operands are marked as such. + /// - Completely dead machine instructions are added to the @p dead vector + /// if it is not nullptr. + /// Returns true if any PHI value numbers have been removed which may + /// have separated the interval into multiple connected components. + bool computeDeadValues(LiveInterval &LI, + SmallVectorImpl *dead); static LiveInterval* createInterval(unsigned Reg); diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 088ac4f7d8e..88fd7bf66e9 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -193,7 +193,7 @@ void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { assert(LI.empty() && "Should only compute empty intervals."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); LRCalc->calculate(LI); - computeDeadValues(LI, LI); + computeDeadValues(LI, nullptr); } void LiveIntervals::computeVirtRegs() { @@ -433,49 +433,46 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end())); extendSegmentsToUses(NewLR, *Indexes, WorkList, *li); - // Handle dead values. - bool CanSeparate; - computeDeadValues(NewLR, *li, &CanSeparate, li->reg, dead); - // Move the trimmed segments back. li->segments.swap(NewLR.segments); + + // Handle dead values. + bool CanSeparate = computeDeadValues(*li, dead); DEBUG(dbgs() << "Shrunk: " << *li << '\n'); return CanSeparate; } -void LiveIntervals::computeDeadValues(LiveRange &Segments, LiveRange &LR, - bool *CanSeparateRes, unsigned Reg, +bool LiveIntervals::computeDeadValues(LiveInterval &LI, SmallVectorImpl *dead) { - bool CanSeparate = false; - for (auto VNI : LR.valnos) { + bool PHIRemoved = false; + for (auto VNI : LI.valnos) { if (VNI->isUnused()) continue; - LiveRange::iterator LRI = Segments.FindSegmentContaining(VNI->def); - assert(LRI != Segments.end() && "Missing segment for PHI"); - if (LRI->end != VNI->def.getDeadSlot()) + LiveRange::iterator I = LI.FindSegmentContaining(VNI->def); + assert(I != LI.end() && "Missing segment for VNI"); + if (I->end != VNI->def.getDeadSlot()) continue; if (VNI->isPHIDef()) { // This is a dead PHI. Remove it. VNI->markUnused(); - Segments.removeSegment(LRI->start, LRI->end); + LI.removeSegment(I); DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); - CanSeparate = true; - } else if (dead != nullptr) { + PHIRemoved = true; + } else { // This is a dead def. Make sure the instruction knows. MachineInstr *MI = getInstructionFromIndex(VNI->def); assert(MI && "No instruction defining live value"); - MI->addRegisterDead(Reg, TRI); + MI->addRegisterDead(LI.reg, TRI); if (dead && MI->allDefsAreDead()) { DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); dead->push_back(MI); } } } - if (CanSeparateRes != nullptr) - *CanSeparateRes = CanSeparate; + return PHIRemoved; } -bool LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) +void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) { DEBUG(dbgs() << "Shrink: " << SR << '\n'); assert(TargetRegisterInfo::isVirtualRegister(Reg) @@ -522,14 +519,26 @@ bool LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end())); extendSegmentsToUses(NewLR, *Indexes, WorkList, SR); - // Handle dead values. - bool CanSeparate; - computeDeadValues(NewLR, SR, &CanSeparate); - // Move the trimmed ranges back. SR.segments.swap(NewLR.segments); + + // Remove dead PHI value numbers + for (auto VNI : SR.valnos) { + if (VNI->isUnused()) + continue; + const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def); + assert(Segment != nullptr && "Missing segment for VNI"); + if (Segment->end != VNI->def.getDeadSlot()) + continue; + if (VNI->isPHIDef()) { + // This is a dead PHI. Remove it. + VNI->markUnused(); + SR.removeSegment(*Segment); + DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); + } + } + DEBUG(dbgs() << "Shrunk: " << SR << '\n'); - return CanSeparate; } void LiveIntervals::extendToIndices(LiveRange &LR, -- 2.34.1