diff options
| -rw-r--r-- | lib/CodeGen/RegAllocGreedy.cpp | 394 | ||||
| -rw-r--r-- | lib/CodeGen/SplitKit.cpp | 25 | ||||
| -rw-r--r-- | lib/CodeGen/SplitKit.h | 10 |
3 files changed, 138 insertions, 291 deletions
diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp index 912d899534..d0e6a649a0 100644 --- a/lib/CodeGen/RegAllocGreedy.cpp +++ b/lib/CodeGen/RegAllocGreedy.cpp @@ -763,46 +763,32 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, // Create the main cross-block interval. const unsigned MainIntv = SE->openIntv(); - // First handle all the blocks with uses. + // First add all defs that are live out of a block. ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); for (unsigned i = 0; i != UseBlocks.size(); ++i) { const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; - bool RegIn = BI.LiveIn && - LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; - bool RegOut = BI.LiveOut && - LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; + 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. - // - // |---o---o---| Enter and leave on the stack. - // ____-----____ Create local interval for uses. - // - // | o---o---| Defined in block, leave on stack. - // -----____ Create local interval for uses. - // - // |---o---x | Enter on stack, killed in block. - // ____----- Create local interval for uses. - // - if (!RegIn && !RegOut) { + if (!RegIn && !RegOut && BI.FirstUse != BI.LastUse) { DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); - if (!BI.isOneInstr()) { - SE->splitSingleBlock(BI); - SE->selectIntv(MainIntv); - } + SE->splitSingleBlock(BI); + SE->selectIntv(MainIntv); continue; } + // Should the register be live out? + if (!BI.LiveOut || !RegOut) + continue; + SlotIndex Start, Stop; tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); Intf.moveToBlock(BI.MBB->getNumber()); - DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) - << (RegIn ? " => " : " -- ") - << "BB#" << BI.MBB->getNumber() - << (RegOut ? " => " : " -- ") - << " EB#" << Bundles->getBundle(BI.MBB->getNumber(), 1) + DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" + << Bundles->getBundle(BI.MBB->getNumber(), 1) << " [" << Start << ';' << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop - << ") uses [" << BI.FirstUse << ';' << BI.LastUse << ") intf [" << Intf.first() << ';' << Intf.last() << ')'); // The interference interval should either be invalid or overlap MBB. @@ -811,266 +797,150 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, assert((!Intf.hasInterference() || Intf.last() > Start) && "Bad interference"); - // We are now ready to decide where to split in the current block. There - // are many variables guiding the decision: - // - // - RegIn / RegOut: The global splitting algorithm's decisions for our - // ingoing and outgoing bundles. - // - // - BI.BlockIn / BI.BlockOut: Is the live range live-in and/or live-out - // from this block. - // - // - Intf.hasInterference(): Is there interference in this block. - // - // - Intf.first() / Inft.last(): The range of interference. - // - // The live range should be split such that MainIntv is live-in when RegIn - // is set, and live-out when RegOut is set. MainIntv should never overlap - // the interference, and the stack interval should never have more than one - // use per block. - - // No splits can be inserted after LastSplitPoint, overlap instead. - SlotIndex LastSplitPoint = Stop; - if (BI.LiveOut) - LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); - - // At this point, we know that either RegIn or RegOut is set. We dealt with - // the all-stack case above. - - // Blocks without interference are relatively easy. + // Check interference leaving the block. if (!Intf.hasInterference()) { - DEBUG(dbgs() << ", no interference.\n"); - SE->selectIntv(MainIntv); - // The easiest case has MainIntv live through. - // - // |---o---o---| Live-in, live-out. - // ============= Use MainIntv everywhere. - // - SlotIndex From = Start, To = Stop; - - // Block entry. Reload before the first use if MainIntv is not live-in. - // - // |---o-- Enter on stack. - // ____=== Reload before first use. - // - // | o-- Defined in block. - // === Use MainIntv from def. - // - if (!RegIn) - From = SE->enterIntvBefore(BI.FirstUse); - - // Block exit. Handle cases where MainIntv is not live-out. - if (!BI.LiveOut) - // - // --x | Killed in block. - // === Use MainIntv up to kill. - // - To = SE->leaveIntvAfter(BI.LastUse); - else if (!RegOut) { - // - // --o---| Live-out on stack. - // ===____ Use MainIntv up to last use, switch to stack. - // - // -----o| Live-out on stack, last use after last split point. - // ====== Extend MainIntv to last use, overlapping. - // \____ Copy to stack interval before last split point. - // - if (BI.LastUse < LastSplitPoint) - To = SE->leaveIntvAfter(BI.LastUse); - else { - // The last use is after the last split point, it is probably an - // indirect branch. - To = SE->leaveIntvBefore(LastSplitPoint); - // Run a double interval from the split to the last use. This makes - // it possible to spill the complement without affecting the indirect - // branch. - SE->overlapIntv(To, BI.LastUse); - } + // Block is interference-free. + DEBUG(dbgs() << ", no interference"); + if (!BI.LiveThrough) { + DEBUG(dbgs() << ", not live-through.\n"); + SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); + continue; } - - // Paint in MainIntv liveness for this block. - SE->useIntv(From, To); + if (!RegIn) { + // Block is live-through, but entry bundle is on the stack. + // Reload just before the first use. + DEBUG(dbgs() << ", not live-in, enter before first use.\n"); + SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); + continue; + } + DEBUG(dbgs() << ", live-through.\n"); continue; } - // We are now looking at a block with interference, and we know that either - // RegIn or RegOut is set. - assert(Intf.hasInterference() && (RegIn || RegOut) && "Bad invariant"); - - // If the live range is not live through the block, it is possible that the - // interference doesn't even overlap. Deal with those cases first. Since - // no copy instructions are required, we can tolerate interference starting - // or ending at the same instruction that kills or defines our live range. + // Block has interference. + DEBUG(dbgs() << ", interference to " << Intf.last()); - // Live-in, killed before interference. - // - // ~~~ Interference after kill. - // |---o---x | Killed in block. - // ========= Use MainIntv everywhere. - // - if (RegIn && !BI.LiveOut && BI.LastUse <= Intf.first()) { - DEBUG(dbgs() << ", live-in, killed before interference.\n"); - SE->selectIntv(MainIntv); - SlotIndex To = SE->leaveIntvAfter(BI.LastUse); - SE->useIntv(Start, To); + if (!BI.LiveThrough && Intf.last() <= BI.FirstUse) { + // The interference doesn't reach the outgoing segment. + DEBUG(dbgs() << " doesn't affect def from " << BI.FirstUse << '\n'); + SE->useIntv(BI.FirstUse, Stop); continue; } - // Live-out, defined after interference. - // - // ~~~ Interference before def. - // | o---o---| Defined in block. - // ========= Use MainIntv everywhere. - // - if (RegOut && !BI.LiveIn && BI.FirstUse >= Intf.last()) { - DEBUG(dbgs() << ", live-out, defined after interference.\n"); - SE->selectIntv(MainIntv); - SlotIndex From = SE->enterIntvBefore(BI.FirstUse); - SE->useIntv(From, Stop); - continue; + SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); + if (Intf.last().getBoundaryIndex() < BI.LastUse) { + // There are interference-free uses at the end of the block. + // Find the first use that can get the live-out register. + SmallVectorImpl<SlotIndex>::const_iterator UI = + std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), + Intf.last().getBoundaryIndex()); + assert(UI != SA->UseSlots.end() && "Couldn't find last use"); + SlotIndex Use = *UI; + assert(Use <= BI.LastUse && "Couldn't find last use"); + // Only attempt a split befroe the last split point. + if (Use.getBaseIndex() <= LastSplitPoint) { + DEBUG(dbgs() << ", free use at " << Use << ".\n"); + SlotIndex SegStart = SE->enterIntvBefore(Use); + assert(SegStart >= Intf.last() && "Couldn't avoid interference"); + assert(SegStart < LastSplitPoint && "Impossible split point"); + SE->useIntv(SegStart, Stop); + continue; + } } - // The interference is now known to overlap the live range, but it may - // still be easy to avoid if all the interference is on one side of the - // uses, and we enter or leave on the stack. + // Interference is after the last use. + DEBUG(dbgs() << " after last use.\n"); + SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); + assert(SegStart >= Intf.last() && "Couldn't avoid interference"); + } - // Live-out on stack, interference after last use. - // - // ~~~ Interference after last use. - // |---o---o---| Live-out on stack. - // =========____ Leave MainIntv after last use. - // - // ~ Interference after last use. - // |---o---o--o| Live-out on stack, late last use. - // =========____ Copy to stack after LSP, overlap MainIntv. - // - if (!RegOut && Intf.first() > BI.LastUse.getBoundaryIndex()) { - assert(RegIn && "Stack-in, stack-out should already be handled"); - if (BI.LastUse < LastSplitPoint) { - DEBUG(dbgs() << ", live-in, stack-out, interference after last use.\n"); - SE->selectIntv(MainIntv); - SlotIndex To = SE->leaveIntvAfter(BI.LastUse); - assert(To <= Intf.first() && "Expected to avoid interference"); - SE->useIntv(Start, To); - } else { - DEBUG(dbgs() << ", live-in, stack-out, avoid last split point\n"); - SE->selectIntv(MainIntv); - SlotIndex To = SE->leaveIntvBefore(LastSplitPoint); - assert(To <= Intf.first() && "Expected to avoid interference"); - SE->overlapIntv(To, BI.LastUse); - SE->useIntv(Start, To); + // Now all defs leading to live bundles are handled, do everything else. + for (unsigned i = 0; i != UseBlocks.size(); ++i) { + const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; + bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; + bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; + + // Is the register live-in? + if (!BI.LiveIn || !RegIn) + continue; + + // We have an incoming register. Check for interference. + SlotIndex Start, Stop; + tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); + Intf.moveToBlock(BI.MBB->getNumber()); + DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) + << " -> BB#" << BI.MBB->getNumber() << " [" << Start << ';' + << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop + << ')'); + + // Check interference entering the block. + if (!Intf.hasInterference()) { + // Block is interference-free. + DEBUG(dbgs() << ", no interference"); + if (!BI.LiveThrough) { + DEBUG(dbgs() << ", killed in block.\n"); + SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); + continue; } + if (!RegOut) { + SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); + // Block is live-through, but exit bundle is on the stack. + // Spill immediately after the last use. + if (BI.LastUse < LastSplitPoint) { + DEBUG(dbgs() << ", uses, stack-out.\n"); + SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); + continue; + } + // The last use is after the last split point, it is probably an + // indirect jump. + DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point " + << LastSplitPoint << ", stack-out.\n"); + SlotIndex SegEnd = SE->leaveIntvBefore(LastSplitPoint); + SE->useIntv(Start, SegEnd); + // Run a double interval from the split to the last use. + // This makes it possible to spill the complement without affecting the + // indirect branch. + SE->overlapIntv(SegEnd, BI.LastUse); + continue; + } + // Register is live-through. + DEBUG(dbgs() << ", uses, live-through.\n"); + SE->useIntv(Start, Stop); continue; } - // Live-in on stack, interference before first use. - // - // ~~~ Interference before first use. - // |---o---o---| Live-in on stack. - // ____========= Enter MainIntv before first use. - // - if (!RegIn && Intf.last() < BI.FirstUse.getBaseIndex()) { - assert(RegOut && "Stack-in, stack-out should already be handled"); - DEBUG(dbgs() << ", stack-in, interference before first use.\n"); - SE->selectIntv(MainIntv); - SlotIndex From = SE->enterIntvBefore(BI.FirstUse); - assert(From >= Intf.last() && "Expected to avoid interference"); - SE->useIntv(From, Stop); + // Block has interference. + DEBUG(dbgs() << ", interference from " << Intf.first()); + + if (!BI.LiveThrough && Intf.first() >= BI.LastUse) { + // The interference doesn't reach the outgoing segment. + DEBUG(dbgs() << " doesn't affect kill at " << BI.LastUse << '\n'); + SE->useIntv(Start, BI.LastUse); continue; } - // The interference is overlapping somewhere we wanted to use MainIntv. That - // means we need to create a local interval that can be allocated a - // different register. - DEBUG(dbgs() << ", creating local interval.\n"); - unsigned LocalIntv = SE->openIntv(); - - // We may be creating copies directly between MainIntv and LocalIntv, - // bypassing the stack interval. When we do that, we should never use the - // leaveIntv* methods as they define values in the stack interval. By - // starting from the end of the block and working our way backwards, we can - // get by with only enterIntv* methods. - // - // When selecting split points, we generally try to maximize the stack - // interval as long at it contains no uses, maximize the main interval as - // long as it doesn't overlap interference, and minimize the local interval - // that we don't know how to allocate yet. - - // Handle the block exit, set Pos to the first handled slot. - SlotIndex Pos = BI.LastUse; - if (RegOut) { - assert(Intf.last() < LastSplitPoint && "Cannot be live-out in register"); - // Create a snippet of MainIntv that is live-out. - // - // ~~~ Interference overlapping uses. - // --o---| Live-out in MainIntv. - // ----=== Switch from LocalIntv to MainIntv after interference. - // - SE->selectIntv(MainIntv); - Pos = SE->enterIntvAfter(Intf.last()); - assert(Pos >= Intf.last() && "Expected to avoid interference"); - SE->useIntv(Pos, Stop); - SE->selectIntv(LocalIntv); - } else if (BI.LiveOut) { - if (BI.LastUse < LastSplitPoint) { - // Live-out on the stack. - // - // ~~~ Interference overlapping uses. - // --o---| Live-out on stack. - // ---____ Switch from LocalIntv to stack after last use. - // - Pos = SE->leaveIntvAfter(BI.LastUse); - } else { - // Live-out on the stack, last use after last split point. - // - // ~~~ Interference overlapping uses. - // --o--o| Live-out on stack, late use. - // ------ Copy to stack before LSP, overlap LocalIntv. - // \__ - // - Pos = SE->leaveIntvBefore(LastSplitPoint); - // We need to overlap LocalIntv so it can reach LastUse. - SE->overlapIntv(Pos, BI.LastUse); - } + if (Intf.first().getBaseIndex() > BI.FirstUse) { + // There are interference-free uses at the beginning of the block. + // Find the last use that can get the register. + SmallVectorImpl<SlotIndex>::const_iterator UI = + std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), + Intf.first().getBaseIndex()); + assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); + SlotIndex Use = (--UI)->getBoundaryIndex(); + DEBUG(dbgs() << ", free use at " << *UI << ".\n"); + SlotIndex SegEnd = SE->leaveIntvAfter(Use); + assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); + SE->useIntv(Start, SegEnd); + continue; } - // When not live-out, leave Pos at LastUse. We have handled everything from - // Pos to Stop. Find the starting point for LocalIntv. - assert(SE->currentIntv() == LocalIntv && "Expecting local interval"); - - if (RegIn) { - assert(Start < Intf.first() && "Cannot be live-in with interference"); - // Live-in in MainIntv, only use LocalIntv for interference. - // - // ~~~ Interference overlapping uses. - // |---o-- Live-in in MainIntv. - // ====--- Switch to LocalIntv before interference. - // - SlotIndex Switch = SE->enterIntvBefore(Intf.first()); - assert(Switch <= Intf.first() && "Expected to avoid interference"); - SE->useIntv(Switch, Pos); - SE->selectIntv(MainIntv); - SE->useIntv(Start, Switch); - } else { - // Live-in on stack, enter LocalIntv before first use. - // - // ~~~ Interference overlapping uses. - // |---o-- Live-in in MainIntv. - // ____--- Reload to LocalIntv before interference. - // - // Defined in block. - // - // ~~~ Interference overlapping uses. - // | o-- Defined in block. - // --- Begin LocalIntv at first use. - // - SlotIndex Switch = SE->enterIntvBefore(BI.FirstUse); - SE->useIntv(Switch, Pos); - } + // Interference is before the first use. + DEBUG(dbgs() << " before first use.\n"); + SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); + assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); } // Handle live-through blocks. - SE->selectIntv(MainIntv); for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { unsigned Number = Cand.ActiveBlocks[i]; bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp index a0952a0866..55b1114b5b 100644 --- a/lib/CodeGen/SplitKit.cpp +++ b/lib/CodeGen/SplitKit.cpp @@ -636,7 +636,6 @@ unsigned SplitEditor::openIntv() { void SplitEditor::selectIntv(unsigned Idx) { assert(Idx != 0 && "Cannot select the complement interval"); assert(Idx < Edit->size() && "Can only select previously opened interval"); - DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); OpenIdx = Idx; } @@ -657,24 +656,6 @@ SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { return VNI->def; } -SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { - assert(OpenIdx && "openIntv not called before enterIntvAfter"); - DEBUG(dbgs() << " enterIntvAfter " << Idx); - Idx = Idx.getBoundaryIndex(); - VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); - if (!ParentVNI) { - DEBUG(dbgs() << ": not live\n"); - return Idx; - } - DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); - MachineInstr *MI = LIS.getInstructionFromIndex(Idx); - assert(MI && "enterIntvAfter called with invalid index"); - - VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), - llvm::next(MachineBasicBlock::iterator(MI))); - return VNI->def; -} - SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); SlotIndex End = LIS.getMBBEndIdx(&MBB); @@ -1026,6 +1007,12 @@ void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { markComplexMapped(i, ParentVNI); } +#ifndef NDEBUG + // Every new interval must have a def by now, otherwise the split is bogus. + for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) + assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); +#endif + // Transfer the simply mapped values, check if any are skipped. bool Skipped = transferValues(); if (Skipped) diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index a9ccf40be2..7174c0b55f 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -81,12 +81,6 @@ public: bool LiveThrough; ///< Live in whole block (Templ 5. above). bool LiveIn; ///< Current reg is live in. bool LiveOut; ///< Current reg is live out. - - /// isOneInstr - Returns true when this BlockInfo describes a single - /// instruction. - bool isOneInstr() const { - return SlotIndex::isSameInstr(FirstUse, LastUse); - } }; private: @@ -366,10 +360,6 @@ public: /// Return the beginning of the new live range. SlotIndex enterIntvBefore(SlotIndex Idx); - /// enterIntvAfter - Enter the open interval after the instruction at Idx. - /// Return the beginning of the new live range. - SlotIndex enterIntvAfter(SlotIndex Idx); - /// enterIntvAtEnd - Enter the open interval at the end of MBB. /// Use the open interval from he inserted copy to the MBB end. /// Return the beginning of the new live range. |