From fd5c51342a429ecab86a645282d0b36b216c0256 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 12 Apr 2011 19:32:53 +0000 Subject: Create new intervals for isolated blocks during region splitting. This merges the behavior of splitSingleBlocks into splitAroundRegion, so the RS_Region and RS_Block register stages can be coalesced. That means the leftover intervals after region splitting go directly to spilling instead of a second pass of per-block splitting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129379 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/RegAllocGreedy.cpp | 44 ++++++++++++++++++++++-------------------- lib/CodeGen/SplitKit.cpp | 34 +++++++++++++++++--------------- lib/CodeGen/SplitKit.h | 5 +++++ 3 files changed, 46 insertions(+), 37 deletions(-) diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp index f9e494f608..8b5c1b0aa8 100644 --- a/lib/CodeGen/RegAllocGreedy.cpp +++ b/lib/CodeGen/RegAllocGreedy.cpp @@ -95,8 +95,7 @@ class RAGreedy : public MachineFunctionPass, RS_New, ///< Never seen before. RS_First, ///< First time in the queue. RS_Second, ///< Second time in the queue. - RS_Region, ///< Produced by region splitting. - RS_Block, ///< Produced by per-block splitting. + RS_Global, ///< Produced by global splitting. RS_Local, ///< Produced by local splitting. RS_Spill ///< Produced by spilling. }; @@ -636,7 +635,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, SE->reset(LREdit); // Create the main cross-block interval. - SE->openIntv(); + const unsigned MainIntv = SE->openIntv(); // First add all defs that are live out of a block. ArrayRef UseBlocks = SA->getUseBlocks(); @@ -645,6 +644,14 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; + // Create separate intervals for isolated blocks with multiple uses. + if (!RegIn && !RegOut && BI.FirstUse != BI.LastUse) { + DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); + SE->splitSingleBlock(BI); + SE->selectIntv(MainIntv); + continue; + } + // Should the register be live out? if (!BI.LiveOut || !RegOut) continue; @@ -894,7 +901,7 @@ unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, return 0; splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs); - setStage(NewVRegs.begin(), NewVRegs.end(), RS_Region); + setStage(NewVRegs.begin(), NewVRegs.end(), RS_Global); return 0; } @@ -1185,30 +1192,25 @@ unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, // Don't iterate global splitting. // Move straight to spilling if this range was produced by a global split. - LiveRangeStage Stage = getStage(VirtReg); - if (Stage >= RS_Block) + if (getStage(VirtReg) >= RS_Global) return 0; SA->analyze(&VirtReg); // First try to split around a region spanning multiple blocks. - if (Stage < RS_Region) { - unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); - if (PhysReg || !NewVRegs.empty()) - return PhysReg; - } + unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); + if (PhysReg || !NewVRegs.empty()) + return PhysReg; // Then isolate blocks with multiple uses. - if (Stage < RS_Block) { - SplitAnalysis::BlockPtrSet Blocks; - if (SA->getMultiUseBlocks(Blocks)) { - LiveRangeEdit LREdit(VirtReg, NewVRegs, this); - SE->reset(LREdit); - SE->splitSingleBlocks(Blocks); - setStage(NewVRegs.begin(), NewVRegs.end(), RS_Block); - if (VerifyEnabled) - MF->verify(this, "After splitting live range around basic blocks"); - } + SplitAnalysis::BlockPtrSet Blocks; + if (SA->getMultiUseBlocks(Blocks)) { + LiveRangeEdit LREdit(VirtReg, NewVRegs, this); + SE->reset(LREdit); + SE->splitSingleBlocks(Blocks); + setStage(NewVRegs.begin(), NewVRegs.end(), RS_Global); + if (VerifyEnabled) + MF->verify(this, "After splitting live range around basic blocks"); } // Don't assign any physregs. diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp index f85d5d358a..73788f6ba0 100644 --- a/lib/CodeGen/SplitKit.cpp +++ b/lib/CodeGen/SplitKit.cpp @@ -935,6 +935,22 @@ bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { return !Blocks.empty(); } +void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { + openIntv(); + SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); + SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstUse, + LastSplitPoint)); + if (!BI.LiveOut || BI.LastUse < LastSplitPoint) { + useIntv(SegStart, leaveIntvAfter(BI.LastUse)); + } else { + // The last use is after the last valid split point. + SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); + useIntv(SegStart, SegStop); + overlapIntv(SegStop, BI.LastUse); + } + closeIntv(); +} + /// splitSingleBlocks - Split CurLI into a separate live interval inside each /// basic block in Blocks. void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { @@ -942,22 +958,8 @@ void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { ArrayRef UseBlocks = SA.getUseBlocks(); for (unsigned i = 0; i != UseBlocks.size(); ++i) { const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; - if (!Blocks.count(BI.MBB)) - continue; - - openIntv(); - SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); - SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstUse, - LastSplitPoint)); - if (!BI.LiveOut || BI.LastUse < LastSplitPoint) { - useIntv(SegStart, leaveIntvAfter(BI.LastUse)); - } else { - // The last use is after the last valid split point. - SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); - useIntv(SegStart, SegStop); - overlapIntv(SegStop, BI.LastUse); - } - closeIntv(); + if (Blocks.count(BI.MBB)) + splitSingleBlock(BI); } finish(); } diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index fab56f70d9..a387896a5d 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -347,6 +347,11 @@ public: // ===--- High level methods ---=== + /// splitSingleBlock - Split CurLI into a separate live interval around the + /// uses in a single block. This is intended to be used as part of a larger + /// split, and doesn't call finish(). + void splitSingleBlock(const SplitAnalysis::BlockInfo &BI); + /// splitSingleBlocks - Split CurLI into a separate live interval inside each /// basic block in Blocks. void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); -- cgit v1.2.3