From 20e1f38a4162248a74f118cac5b979f66f42b6f2 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Wed, 10 Dec 2014 01:12:18 +0000 Subject: [PATCH] LiveIntervalAnalysis: Update SubRanges in shrinkToUses(). llvm-svn: 223880 --- llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h | 19 +- llvm/lib/CodeGen/LiveIntervalAnalysis.cpp | 221 +++++++++++++++-------- 2 files changed, 160 insertions(+), 80 deletions(-) diff --git a/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h b/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h index 7460cf5..ea1b32d 100644 --- a/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -393,14 +393,17 @@ namespace llvm { /// Compute RegMaskSlots and RegMaskBits. void computeRegMasks(); - /// \brief Walk the values in the given interval and compute which ones - /// are dead. Dead values are not deleted, however: + /// \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: /// - Dead PHIDef values are marked as unused. - /// - New dead machine instructions are added to the dead vector. + /// - 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(LiveInterval *li, LiveRange &LR, bool *CanSeparate, - SmallVectorImpl *dead); + void computeDeadValues(LiveRange &Segments, LiveRange &LR, + bool *CanSeparate = nullptr, unsigned Reg = 0, + SmallVectorImpl *dead = nullptr); static LiveInterval* createInterval(unsigned Reg); @@ -411,6 +414,12 @@ namespace llvm { void computeRegUnitRange(LiveRange&, unsigned Unit); void computeVirtRegInterval(LiveInterval&); + /// Specialized version of + /// 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); + class HMEditor; }; } // End llvm namespace diff --git a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp index d07d3cc..a1c7424 100644 --- a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -185,7 +185,7 @@ void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); LRCalc->createDeadDefs(LI); LRCalc->extendToUses(LI); - computeDeadValues(&LI, LI, nullptr, nullptr); + computeDeadValues(LI, LI); } void LiveIntervals::computeVirtRegs() { @@ -312,6 +312,70 @@ void LiveIntervals::computeLiveInRegUnits() { } +static void createSegmentsForValues(LiveRange &LR, + iterator_range VNIs) { + for (auto VNI : VNIs) { + if (VNI->isUnused()) + continue; + SlotIndex Def = VNI->def; + LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI)); + } +} + +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)); + } + 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)); + } + } +} + /// shrinkToUses - After removing some uses of a register, shrink its live /// range to just the remaining uses. This method does not compute reaching /// defs for new uses, and it doesn't remove dead defs. @@ -320,11 +384,15 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, DEBUG(dbgs() << "Shrink: " << *li << '\n'); assert(TargetRegisterInfo::isVirtualRegister(li->reg) && "Can only shrink virtual registers"); - // Find all the values used, including PHI kills. - SmallVector, 16> WorkList; - // Blocks that have already been added to WorkList as live-out. - SmallPtrSet LiveOut; + // Shrink subregister live ranges. + for (LiveInterval::subrange_iterator I = li->subrange_begin(), + E = li->subrange_end(); I != E; ++I) { + shrinkToUses(*I, li->reg); + } + + // Find all the values used, including PHI kills. + ShrinkToUsesWorkList WorkList; // Visit all instructions reading li->reg. for (MachineRegisterInfo::reg_instr_iterator @@ -355,65 +423,12 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, // Create new live ranges with only minimal live segments per def. LiveRange NewLR; - for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); - I != E; ++I) { - VNInfo *VNI = *I; - if (VNI->isUnused()) - continue; - NewLR.addSegment(LiveRange::Segment(VNI->def, VNI->def.getDeadSlot(), VNI)); - } - - // Keep track of the PHIs that are in use. - SmallPtrSet UsedPHIs; - - // 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 = getMBBFromIndex(Idx.getPrevSlot()); - SlotIndex BlockStart = getMBBStartIdx(MBB); - - // Extend the live range for VNI to be live at Idx. - if (VNInfo *ExtVNI = NewLR.extendInBlock(BlockStart, Idx)) { - (void)ExtVNI; - assert(ExtVNI == VNI && "Unexpected existing value number"); - // 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 (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), - PE = MBB->pred_end(); PI != PE; ++PI) { - if (!LiveOut.insert(*PI).second) - continue; - SlotIndex Stop = getMBBEndIdx(*PI); - // A predecessor is not required to have a live-out value for a PHI. - if (VNInfo *PVNI = li->getVNInfoBefore(Stop)) - WorkList.push_back(std::make_pair(Stop, PVNI)); - } - continue; - } - - // VNI is live-in to MBB. - DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); - NewLR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); - - // Make sure VNI is live-out from the predecessors. - for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), - PE = MBB->pred_end(); PI != PE; ++PI) { - if (!LiveOut.insert(*PI).second) - continue; - SlotIndex Stop = getMBBEndIdx(*PI); - assert(li->getVNInfoBefore(Stop) == VNI && - "Wrong value out of predecessor"); - WorkList.push_back(std::make_pair(Stop, VNI)); - } - } + createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end())); + extendSegmentsToUses(NewLR, *Indexes, WorkList, *li); // Handle dead values. - bool CanSeparate = false; - computeDeadValues(li, NewLR, &CanSeparate, dead); + bool CanSeparate; + computeDeadValues(NewLR, *li, &CanSeparate, li->reg, dead); // Move the trimmed segments back. li->segments.swap(NewLR.segments); @@ -421,37 +436,93 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, return CanSeparate; } -void LiveIntervals::computeDeadValues(LiveInterval *li, - LiveRange &LR, - bool *CanSeparate, +void LiveIntervals::computeDeadValues(LiveRange &Segments, LiveRange &LR, + bool *CanSeparateRes, unsigned Reg, SmallVectorImpl *dead) { - for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); - I != E; ++I) { - VNInfo *VNI = *I; + bool CanSeparate = false; + for (auto VNI : make_range(LR.vni_begin(), LR.vni_end())) { if (VNI->isUnused()) continue; - LiveRange::iterator LRI = LR.FindSegmentContaining(VNI->def); - assert(LRI != LR.end() && "Missing segment for PHI"); + LiveRange::iterator LRI = Segments.FindSegmentContaining(VNI->def); + assert(LRI != Segments.end() && "Missing segment for PHI"); if (LRI->end != VNI->def.getDeadSlot()) continue; if (VNI->isPHIDef()) { // This is a dead PHI. Remove it. VNI->markUnused(); - LR.removeSegment(LRI->start, LRI->end); + Segments.removeSegment(LRI->start, LRI->end); DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); - if (CanSeparate) - *CanSeparate = true; - } else { + CanSeparate = true; + } else if (dead != nullptr) { // This is a dead def. Make sure the instruction knows. MachineInstr *MI = getInstructionFromIndex(VNI->def); assert(MI && "No instruction defining live value"); - MI->addRegisterDead(li->reg, TRI); + MI->addRegisterDead(Reg, TRI); if (dead && MI->allDefsAreDead()) { DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); dead->push_back(MI); } } } + if (CanSeparateRes != nullptr) + *CanSeparateRes = CanSeparate; +} + +bool LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) +{ + DEBUG(dbgs() << "Shrink: " << SR << '\n'); + assert(TargetRegisterInfo::isVirtualRegister(Reg) + && "Can only shrink virtual registers"); + // Find all the values used, including PHI kills. + ShrinkToUsesWorkList WorkList; + + // Visit all instructions reading Reg. + SlotIndex LastIdx; + for (MachineOperand &MO : MRI->reg_operands(Reg)) { + MachineInstr *UseMI = MO.getParent(); + if (UseMI->isDebugValue()) + continue; + // Maybe the operand is for a subregister we don't care about. + unsigned SubReg = MO.getSubReg(); + if (SubReg != 0) { + unsigned SubRegMask = TRI->getSubRegIndexLaneMask(SubReg); + if ((SubRegMask & SR.LaneMask) == 0) + continue; + } + // We only need to visit each instruction once. + SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); + if (Idx == LastIdx) + continue; + LastIdx = Idx; + + LiveQueryResult LRQ = SR.Query(Idx); + VNInfo *VNI = LRQ.valueIn(); + // For Subranges it is possible that only undef values are left in that + // part of the subregister, so there is no real liverange at the use + if (!VNI) + continue; + + // Special case: An early-clobber tied operand reads and writes the + // register one slot early. + if (VNInfo *DefVNI = LRQ.valueDefined()) + Idx = DefVNI->def; + + WorkList.push_back(std::make_pair(Idx, VNI)); + } + + // 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); + + // Handle dead values. + bool CanSeparate; + computeDeadValues(NewLR, SR, &CanSeparate); + + // Move the trimmed ranges back. + SR.segments.swap(NewLR.segments); + DEBUG(dbgs() << "Shrunk: " << SR << '\n'); + return CanSeparate; } void LiveIntervals::extendToIndices(LiveRange &LR, -- 2.7.4