From e25dde550baec1f79caf2fc06edd74e7ae6ffa33 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Thu, 10 Oct 2013 21:28:57 +0000 Subject: [PATCH] Work on LiveRange instead of LiveInterval where possible Also change some pointer arguments to references at some places where 0-pointers are not allowed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192396 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveIntervalAnalysis.h | 10 ++-- lib/CodeGen/LiveIntervalAnalysis.cpp | 14 +++--- lib/CodeGen/LiveRangeCalc.cpp | 56 ++++++++++----------- lib/CodeGen/LiveRangeCalc.h | 32 ++++++------ lib/CodeGen/RegisterCoalescer.cpp | 2 +- lib/CodeGen/SplitKit.cpp | 18 +++---- 6 files changed, 63 insertions(+), 69 deletions(-) diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 216a179d1ea..922c2a09df9 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -127,7 +127,7 @@ namespace llvm { LiveInterval &createAndComputeVirtRegInterval(unsigned Reg) { LiveInterval &LI = createEmptyInterval(Reg); - computeVirtRegInterval(&LI); + computeVirtRegInterval(LI); return LI; } @@ -160,7 +160,7 @@ namespace llvm { /// extended to be live out of the basic block. /// /// See also LiveRangeCalc::extend(). - void extendToIndices(LiveInterval *LI, ArrayRef Indices); + void extendToIndices(LiveRange &LR, ArrayRef Indices); /// pruneValue - If an LI value is live at Kill, prune its live range by /// removing any liveness reachable from Kill. Add live range end points to @@ -369,7 +369,7 @@ namespace llvm { if (!LI) { // Compute missing ranges on demand. RegUnitIntervals[Unit] = LI = new LiveInterval(Unit, HUGE_VALF); - computeRegUnitInterval(LI); + computeRegUnitInterval(*LI); } return *LI; } @@ -397,8 +397,8 @@ namespace llvm { void dumpInstrs() const; void computeLiveInRegUnits(); - void computeRegUnitInterval(LiveInterval*); - void computeVirtRegInterval(LiveInterval*); + void computeRegUnitInterval(LiveInterval&); + void computeVirtRegInterval(LiveInterval&); class HMEditor; }; diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 4c0e058e61e..18abe41174b 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -177,9 +177,9 @@ LiveInterval* LiveIntervals::createInterval(unsigned reg) { /// computeVirtRegInterval - Compute the live interval of a virtual register, /// based on defs and uses. -void LiveIntervals::computeVirtRegInterval(LiveInterval *LI) { +void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { assert(LRCalc && "LRCalc not initialized."); - assert(LI->empty() && "Should only compute empty intervals."); + assert(LI.empty() && "Should only compute empty intervals."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); LRCalc->createDeadDefs(LI); LRCalc->extendToUses(LI); @@ -230,8 +230,8 @@ void LiveIntervals::computeRegMasks() { /// computeRegUnitInterval - Compute the live interval of a register unit, based /// on the uses and defs of aliasing registers. The interval should be empty, /// or contain only dead phi-defs from ABI blocks. -void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) { - unsigned Unit = LI->reg; +void LiveIntervals::computeRegUnitInterval(LiveInterval &LI) { + unsigned Unit = LI.reg; assert(LRCalc && "LRCalc not initialized."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); @@ -305,7 +305,7 @@ void LiveIntervals::computeLiveInRegUnits() { // Compute the 'normal' part of the intervals. for (unsigned i = 0, e = NewIntvs.size(); i != e; ++i) - computeRegUnitInterval(NewIntvs[i]); + computeRegUnitInterval(*NewIntvs[i]); } @@ -440,12 +440,12 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, return CanSeparate; } -void LiveIntervals::extendToIndices(LiveInterval *LI, +void LiveIntervals::extendToIndices(LiveRange &LR, ArrayRef Indices) { assert(LRCalc && "LRCalc not initialized."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); for (unsigned i = 0, e = Indices.size(); i != e; ++i) - LRCalc->extend(LI, Indices[i]); + LRCalc->extend(LR, Indices[i]); } void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill, diff --git a/lib/CodeGen/LiveRangeCalc.cpp b/lib/CodeGen/LiveRangeCalc.cpp index bd9c8d03019..ae086bc0c4c 100644 --- a/lib/CodeGen/LiveRangeCalc.cpp +++ b/lib/CodeGen/LiveRangeCalc.cpp @@ -36,11 +36,11 @@ void LiveRangeCalc::reset(const MachineFunction *mf, } -void LiveRangeCalc::createDeadDefs(LiveInterval *LI, unsigned Reg) { +void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) { assert(MRI && Indexes && "call reset() first"); // Visit all def operands. If the same instruction has multiple defs of Reg, - // LI->createDeadDef() will deduplicate. + // LR.createDeadDef() will deduplicate. for (MachineRegisterInfo::def_iterator I = MRI->def_begin(Reg), E = MRI->def_end(); I != E; ++I) { const MachineInstr *MI = &*I; @@ -54,13 +54,13 @@ void LiveRangeCalc::createDeadDefs(LiveInterval *LI, unsigned Reg) { Idx = Indexes->getInstructionIndex(MI) .getRegSlot(I.getOperand().isEarlyClobber()); - // Create the def in LI. This may find an existing def. - LI->createDeadDef(Idx, *Alloc); + // Create the def in LR. This may find an existing def. + LR.createDeadDef(Idx, *Alloc); } } -void LiveRangeCalc::extendToUses(LiveInterval *LI, unsigned Reg) { +void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg) { assert(MRI && Indexes && "call reset() first"); // Visit all operands that read Reg. This may include partial defs. @@ -99,7 +99,7 @@ void LiveRangeCalc::extendToUses(LiveInterval *LI, unsigned Reg) { Idx = Idx.getRegSlot(true); } } - extend(LI, Idx, Reg); + extend(LR, Idx, Reg); } } @@ -125,17 +125,14 @@ void LiveRangeCalc::updateLiveIns() { assert(Seen.test(MBB->getNumber())); LiveOut[MBB] = LiveOutPair(I->Value, (MachineDomTreeNode *)0); } - Updater.setDest(I->LI); + Updater.setDest(&I->LR); Updater.add(Start, End, I->Value); } LiveIn.clear(); } -void LiveRangeCalc::extend(LiveInterval *LI, - SlotIndex Kill, - unsigned PhysReg) { - assert(LI && "Missing live range"); +void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg) { assert(Kill.isValid() && "Invalid SlotIndex"); assert(Indexes && "Missing SlotIndexes"); assert(DomTree && "Missing dominator tree"); @@ -144,14 +141,14 @@ void LiveRangeCalc::extend(LiveInterval *LI, assert(KillMBB && "No MBB at Kill"); // Is there a def in the same MBB we can extend? - if (LI->extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill)) + if (LR.extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill)) return; // Find the single reaching def, or determine if Kill is jointly dominated by // multiple values, and we may need to create even more phi-defs to preserve // VNInfo SSA form. Perform a search for all predecessor blocks where we // know the dominating VNInfo. - if (findReachingDefs(LI, KillMBB, Kill, PhysReg)) + if (findReachingDefs(LR, *KillMBB, Kill, PhysReg)) return; // When there were multiple different values, we may need new PHIs. @@ -170,13 +167,11 @@ void LiveRangeCalc::calculateValues() { } -bool LiveRangeCalc::findReachingDefs(LiveInterval *LI, - MachineBasicBlock *KillMBB, - SlotIndex Kill, - unsigned PhysReg) { - unsigned KillMBBNum = KillMBB->getNumber(); +bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB, + SlotIndex Kill, unsigned PhysReg) { + unsigned KillMBBNum = KillMBB.getNumber(); - // Block numbers where LI should be live-in. + // Block numbers where LR should be live-in. SmallVector WorkList(1, KillMBBNum); // Remember if we have seen more than one value. @@ -203,7 +198,7 @@ bool LiveRangeCalc::findReachingDefs(LiveInterval *LI, #endif for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), - PE = MBB->pred_end(); PI != PE; ++PI) { + PE = MBB->pred_end(); PI != PE; ++PI) { MachineBasicBlock *Pred = *PI; // Is this a known live-out block? @@ -221,7 +216,7 @@ bool LiveRangeCalc::findReachingDefs(LiveInterval *LI, // First time we see Pred. Try to determine the live-out value, but set // it as null if Pred is live-through with an unknown value. - VNInfo *VNI = LI->extendInBlock(Start, End); + VNInfo *VNI = LR.extendInBlock(Start, End); setLiveOutValue(Pred, VNI); if (VNI) { if (TheVNI && TheVNI != VNI) @@ -231,7 +226,7 @@ bool LiveRangeCalc::findReachingDefs(LiveInterval *LI, } // No, we need a live-in value for Pred as well - if (Pred != KillMBB) + if (Pred != &KillMBB) WorkList.push_back(Pred->getNumber()); else // Loopback to KillMBB, so value is really live through. @@ -248,9 +243,9 @@ bool LiveRangeCalc::findReachingDefs(LiveInterval *LI, // If a unique reaching def was found, blit in the live ranges immediately. if (UniqueVNI) { - LiveRangeUpdater Updater(LI); - for (SmallVectorImpl::const_iterator - I = WorkList.begin(), E = WorkList.end(); I != E; ++I) { + LiveRangeUpdater Updater(&LR); + for (SmallVectorImpl::const_iterator I = WorkList.begin(), + E = WorkList.end(); I != E; ++I) { SlotIndex Start, End; tie(Start, End) = Indexes->getMBBRange(*I); // Trim the live range in KillMBB. @@ -270,8 +265,8 @@ bool LiveRangeCalc::findReachingDefs(LiveInterval *LI, for (SmallVectorImpl::const_iterator I = WorkList.begin(), E = WorkList.end(); I != E; ++I) { MachineBasicBlock *MBB = MF->getBlockNumbered(*I); - addLiveInBlock(LI, DomTree->getNode(MBB)); - if (MBB == KillMBB) + addLiveInBlock(LR, DomTree->getNode(MBB)); + if (MBB == &KillMBB) LiveIn.back().Kill = Kill; } @@ -348,16 +343,17 @@ void LiveRangeCalc::updateSSA() { assert(Alloc && "Need VNInfo allocator to create PHI-defs"); SlotIndex Start, End; tie(Start, End) = Indexes->getMBBRange(MBB); - VNInfo *VNI = I->LI->getNextValue(Start, *Alloc); + LiveRange &LR = I->LR; + VNInfo *VNI = LR.getNextValue(Start, *Alloc); I->Value = VNI; // This block is done, we know the final value. I->DomNode = 0; // Add liveness since updateLiveIns now skips this node. if (I->Kill.isValid()) - I->LI->addSegment(LiveInterval::Segment(Start, I->Kill, VNI)); + LR.addSegment(LiveInterval::Segment(Start, I->Kill, VNI)); else { - I->LI->addSegment(LiveInterval::Segment(Start, End, VNI)); + LR.addSegment(LiveInterval::Segment(Start, End, VNI)); LOP = LiveOutPair(VNI, Node); } } else if (IDomValue.first) { diff --git a/lib/CodeGen/LiveRangeCalc.h b/lib/CodeGen/LiveRangeCalc.h index 69c7f765e6b..36d3a089646 100644 --- a/lib/CodeGen/LiveRangeCalc.h +++ b/lib/CodeGen/LiveRangeCalc.h @@ -75,9 +75,9 @@ class LiveRangeCalc { /// LiveInBlock - Information about a basic block where a live range is known /// to be live-in, but the value has not yet been determined. struct LiveInBlock { - // LI - The live range that is live-in to this block. The algorithms can + // The live range set that is live-in to this block. The algorithms can // handle multiple non-overlapping live ranges simultaneously. - LiveInterval *LI; + LiveRange &LR; // DomNode - Dominator tree node for the block. // Cleared when the final value has been determined and LI has been updated. @@ -91,8 +91,8 @@ class LiveRangeCalc { // Live-in value filled in by updateSSA once it is known. VNInfo *Value; - LiveInBlock(LiveInterval *li, MachineDomTreeNode *node, SlotIndex kill) - : LI(li), DomNode(node), Kill(kill), Value(0) {} + LiveInBlock(LiveRange &LR, MachineDomTreeNode *node, SlotIndex kill) + : LR(LR), DomNode(node), Kill(kill), Value(0) {} }; /// LiveIn - Work list of blocks where the live-in value has yet to be @@ -111,10 +111,8 @@ class LiveRangeCalc { /// are added to the LiveIn array, and the function returns false. /// /// PhysReg, when set, is used to verify live-in lists on basic blocks. - bool findReachingDefs(LiveInterval *LI, - MachineBasicBlock *KillMBB, - SlotIndex Kill, - unsigned PhysReg); + bool findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB, + SlotIndex Kill, unsigned PhysReg); /// updateSSA - Compute the values that will be live in to all requested /// blocks in LiveIn. Create PHI-def values as required to preserve SSA form. @@ -161,27 +159,27 @@ public: /// single existing value, Alloc may be null. /// /// PhysReg, when set, is used to verify live-in lists on basic blocks. - void extend(LiveInterval *LI, SlotIndex Kill, unsigned PhysReg = 0); + void extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg = 0); /// createDeadDefs - Create a dead def in LI for every def operand of Reg. /// Each instruction defining Reg gets a new VNInfo with a corresponding /// minimal live range. - void createDeadDefs(LiveInterval *LI, unsigned Reg); + void createDeadDefs(LiveRange &LR, unsigned Reg); /// createDeadDefs - Create a dead def in LI for every def of LI->reg. - void createDeadDefs(LiveInterval *LI) { - createDeadDefs(LI, LI->reg); + void createDeadDefs(LiveInterval &LI) { + createDeadDefs(LI, LI.reg); } /// extendToUses - Extend the live range of LI to reach all uses of Reg. /// /// All uses must be jointly dominated by existing liveness. PHI-defs are /// inserted as needed to preserve SSA form. - void extendToUses(LiveInterval *LI, unsigned Reg); + void extendToUses(LiveRange &LR, unsigned Reg); /// extendToUses - Extend the live range of LI to reach all uses of LI->reg. - void extendToUses(LiveInterval *LI) { - extendToUses(LI, LI->reg); + void extendToUses(LiveInterval &LI) { + extendToUses(LI, LI.reg); } //===--------------------------------------------------------------------===// @@ -217,10 +215,10 @@ public: /// @param Kill Index in block where LI is killed. If the value is /// live-through, set Kill = SLotIndex() and also call /// setLiveOutValue(MBB, 0). - void addLiveInBlock(LiveInterval *LI, + void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill = SlotIndex()) { - LiveIn.push_back(LiveInBlock(LI, DomNode, Kill)); + LiveIn.push_back(LiveInBlock(LR, DomNode, Kill)); } /// calculateValues - Calculate the value that will be live-in to each block diff --git a/lib/CodeGen/RegisterCoalescer.cpp b/lib/CodeGen/RegisterCoalescer.cpp index 578653d06c4..e36c52fe062 100644 --- a/lib/CodeGen/RegisterCoalescer.cpp +++ b/lib/CodeGen/RegisterCoalescer.cpp @@ -2015,7 +2015,7 @@ bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { // CR_Replace conflicts. DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: " << LHS << '\n'); - LIS->extendToIndices(&LHS, EndPoints); + LIS->extendToIndices(LHS, EndPoints); return true; } diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp index b17b644b708..68a15f7fab3 100644 --- a/lib/CodeGen/SplitKit.cpp +++ b/lib/CodeGen/SplitKit.cpp @@ -862,13 +862,13 @@ bool SplitEditor::transferValues() { // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); - LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); + LiveRange &LR = LIS.getInterval(Edit->get(RegIdx)); // Check for a simply defined value that can be blitted directly. ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id)); if (VNInfo *VNI = VFP.getPointer()) { DEBUG(dbgs() << ':' << VNI->id); - LI->addSegment(LiveInterval::Segment(Start, End, VNI)); + LR.addSegment(LiveInterval::Segment(Start, End, VNI)); Start = End; continue; } @@ -892,7 +892,7 @@ bool SplitEditor::transferValues() { // The first block may be live-in, or it may have its own def. if (Start != BlockStart) { - VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End)); + VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End)); assert(VNI && "Missing def for complex mapped value"); DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); // MBB has its own def. Is it also live-out? @@ -912,7 +912,7 @@ bool SplitEditor::transferValues() { if (BlockStart == ParentVNI->def) { // This block has the def of a parent PHI, so it isn't live-in. assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); - VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End)); + VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End)); assert(VNI && "Missing def for complex mapped parent PHI"); if (End >= BlockEnd) LRC.setLiveOutValue(MBB, VNI); // Live-out as well. @@ -920,10 +920,10 @@ bool SplitEditor::transferValues() { // This block needs a live-in value. The last block covered may not // be live-out. if (End < BlockEnd) - LRC.addLiveInBlock(LI, MDT[MBB], End); + LRC.addLiveInBlock(LR, MDT[MBB], End); else { // Live-through, and we don't know the value. - LRC.addLiveInBlock(LI, MDT[MBB]); + LRC.addLiveInBlock(LR, MDT[MBB]); LRC.setLiveOutValue(MBB, 0); } } @@ -950,7 +950,7 @@ void SplitEditor::extendPHIKillRanges() { if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) continue; unsigned RegIdx = RegAssign.lookup(PHIVNI->def); - LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); + LiveRange &LR = LIS.getInterval(Edit->get(RegIdx)); LiveRangeCalc &LRC = getLRCalc(RegIdx); MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), @@ -962,7 +962,7 @@ void SplitEditor::extendPHIKillRanges() { if (Edit->getParent().liveAt(LastUse)) { assert(RegAssign.lookup(LastUse) == RegIdx && "Different register assignment in phi predecessor"); - LRC.extend(LI, End); + LRC.extend(LR, End); } } } @@ -1012,7 +1012,7 @@ void SplitEditor::rewriteAssigned(bool ExtendRanges) { } else Idx = Idx.getRegSlot(true); - getLRCalc(RegIdx).extend(LI, Idx.getNextSlot()); + getLRCalc(RegIdx).extend(*LI, Idx.getNextSlot()); } } -- 2.34.1