From: Jakob Stoklund Olesen Date: Wed, 6 Apr 2011 03:57:00 +0000 (+0000) Subject: Analyze blocks with uses separately from live-through blocks without uses. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=db529a8a5d071610f3a8b467693bc40b073e68ef Analyze blocks with uses separately from live-through blocks without uses. About 90% of the relevant blocks are live-through without uses, and the only information required about them is their number. This saves memory and enables later optimizations that need to look at only the use-blocks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128985 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp index 45ed70737eb..689e5c90666 100644 --- a/lib/CodeGen/RegAllocGreedy.cpp +++ b/lib/CodeGen/RegAllocGreedy.cpp @@ -414,20 +414,19 @@ unsigned RAGreedy::tryEvict(LiveInterval &VirtReg, /// this split, assuming that all preferences in SplitConstraints are met. float RAGreedy::calcSplitConstraints(unsigned PhysReg) { InterferenceCache::Cursor Intf(IntfCache, PhysReg); + ArrayRef UseBlocks = SA->getUseBlocks(); // Reset interference dependent info. - SplitConstraints.resize(SA->LiveBlocks.size()); + SplitConstraints.resize(UseBlocks.size()); float StaticCost = 0; - for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { - SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; + for (unsigned i = 0; i != UseBlocks.size(); ++i) { + const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; BC.Number = BI.MBB->getNumber(); Intf.moveToBlock(BC.Number); - BC.Entry = (BI.Uses && BI.LiveIn) ? - SpillPlacement::PrefReg : SpillPlacement::DontCare; - BC.Exit = (BI.Uses && BI.LiveOut) ? - SpillPlacement::PrefReg : SpillPlacement::DontCare; + BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; + BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; if (!Intf.hasInterference()) continue; @@ -438,9 +437,7 @@ float RAGreedy::calcSplitConstraints(unsigned PhysReg) { // Interference for the live-in value. if (BI.LiveIn) { if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) - BC.Entry = SpillPlacement::MustSpill, Ins += BI.Uses; - else if (!BI.Uses) - BC.Entry = SpillPlacement::PrefSpill; + BC.Entry = SpillPlacement::MustSpill, ++Ins; else if (Intf.first() < BI.FirstUse) BC.Entry = SpillPlacement::PrefSpill, ++Ins; else if (Intf.first() < (BI.LiveThrough ? BI.LastUse : BI.Kill)) @@ -450,9 +447,7 @@ float RAGreedy::calcSplitConstraints(unsigned PhysReg) { // Interference for the live-out value. if (BI.LiveOut) { if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) - BC.Exit = SpillPlacement::MustSpill, Ins += BI.Uses; - else if (!BI.Uses) - BC.Exit = SpillPlacement::PrefSpill; + BC.Exit = SpillPlacement::MustSpill, ++Ins; else if (Intf.last() > BI.LastUse) BC.Exit = SpillPlacement::PrefSpill, ++Ins; else if (Intf.last() > (BI.LiveThrough ? BI.FirstUse : BI.Def)) @@ -463,6 +458,33 @@ float RAGreedy::calcSplitConstraints(unsigned PhysReg) { if (Ins) StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); } + + // Now handle the live-through blocks without uses. + ArrayRef ThroughBlocks = SA->getThroughBlocks(); + SplitConstraints.resize(UseBlocks.size() + ThroughBlocks.size()); + for (unsigned i = 0; i != ThroughBlocks.size(); ++i) { + SpillPlacement::BlockConstraint BC = SplitConstraints[UseBlocks.size() + i]; + BC.Number = ThroughBlocks[i]; + BC.Entry = SpillPlacement::DontCare; + BC.Exit = SpillPlacement::DontCare; + + Intf.moveToBlock(BC.Number); + if (!Intf.hasInterference()) + continue; + + // Interference for the live-in value. + if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) + BC.Entry = SpillPlacement::MustSpill; + else + BC.Entry = SpillPlacement::PrefSpill; + + // Interference for the live-out value. + if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) + BC.Exit = SpillPlacement::MustSpill; + else + BC.Exit = SpillPlacement::PrefSpill; + } + return StaticCost; } @@ -473,24 +495,31 @@ float RAGreedy::calcSplitConstraints(unsigned PhysReg) { /// float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) { float GlobalCost = 0; - for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { - SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; + ArrayRef UseBlocks = SA->getUseBlocks(); + for (unsigned i = 0; i != UseBlocks.size(); ++i) { + const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; unsigned Ins = 0; - if (!BI.Uses) - Ins += RegIn != RegOut; - else { - if (BI.LiveIn) - Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); - if (BI.LiveOut) - Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); - } + if (BI.LiveIn) + Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); + if (BI.LiveOut) + Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); if (Ins) GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); } + + ArrayRef ThroughBlocks = SA->getThroughBlocks(); + SplitConstraints.resize(UseBlocks.size() + ThroughBlocks.size()); + for (unsigned i = 0; i != ThroughBlocks.size(); ++i) { + unsigned Number = ThroughBlocks[i]; + bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; + bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; + if (RegIn != RegOut) + GlobalCost += SpillPlacer->getBlockFrequency(Number); + } return GlobalCost; } @@ -520,8 +549,9 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, SE->openIntv(); // First add all defs that are live out of a block. - for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { - SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; + ArrayRef UseBlocks = SA->getUseBlocks(); + 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)]; @@ -548,15 +578,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, if (!Intf.hasInterference()) { // Block is interference-free. DEBUG(dbgs() << ", no interference"); - if (!BI.Uses) { - assert(BI.LiveThrough && "No uses, but not live through block?"); - // Block is live-through without interference. - DEBUG(dbgs() << ", no uses" - << (RegIn ? ", live-through.\n" : ", stack in.\n")); - if (!RegIn) - SE->enterIntvAtEnd(*BI.MBB); - continue; - } if (!BI.LiveThrough) { DEBUG(dbgs() << ", not live-through.\n"); SE->useIntv(SE->enterIntvBefore(BI.Def), Stop); @@ -583,15 +604,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, continue; } - - if (!BI.Uses) { - // No uses in block, avoid interference by reloading as late as possible. - DEBUG(dbgs() << ", no uses.\n"); - SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); - assert(SegStart >= Intf.last() && "Couldn't avoid interference"); - 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. @@ -620,8 +632,8 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, } // Now all defs leading to live bundles are handled, do everything else. - for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { - SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; + 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)]; @@ -642,18 +654,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, if (!Intf.hasInterference()) { // Block is interference-free. DEBUG(dbgs() << ", no interference"); - if (!BI.Uses) { - assert(BI.LiveThrough && "No uses, but not live through block?"); - // Block is live-through without interference. - if (RegOut) { - DEBUG(dbgs() << ", no uses, live-through.\n"); - SE->useIntv(Start, Stop); - } else { - DEBUG(dbgs() << ", no uses, stack-out.\n"); - SE->leaveIntvAtTop(*BI.MBB); - } - continue; - } if (!BI.LiveThrough) { DEBUG(dbgs() << ", killed in block.\n"); SE->useIntv(Start, SE->leaveIntvAfter(BI.Kill)); @@ -696,13 +696,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, continue; } - if (!BI.Uses) { - // No uses in block, avoid interference by spilling as soon as possible. - DEBUG(dbgs() << ", no uses.\n"); - SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); - assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); - continue; - } 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. @@ -724,6 +717,28 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); } + // Handle live-through blocks. + ArrayRef ThroughBlocks = SA->getThroughBlocks(); + for (unsigned i = 0; i != ThroughBlocks.size(); ++i) { + unsigned Number = ThroughBlocks[i]; + bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; + bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; + DEBUG(dbgs() << "Live through BB#" << Number << '\n'); + if (RegIn && RegOut) { + Intf.moveToBlock(Number); + if (!Intf.hasInterference()) { + SE->useIntv(Indexes->getMBBStartIdx(Number), + Indexes->getMBBEndIdx(Number)); + continue; + } + } + MachineBasicBlock *MBB = MF->getBlockNumbered(Number); + if (RegIn) + SE->leaveIntvAtTop(*MBB); + if (RegOut) + SE->enterIntvAtEnd(*MBB); + } + SE->closeIntv(); // FIXME: Should we be more aggressive about splitting the stack region into @@ -797,8 +812,8 @@ unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, /// void RAGreedy::calcGapWeights(unsigned PhysReg, SmallVectorImpl &GapWeight) { - assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); - const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); + assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); + const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); const SmallVectorImpl &Uses = SA->UseSlots; const unsigned NumGaps = Uses.size()-1; @@ -889,8 +904,8 @@ unsigned RAGreedy::nextSplitPoint(unsigned i) { /// unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl &NewVRegs) { - assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); - const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); + assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); + const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); // Note that it is possible to have an interval that is live-in or live-out // while only covering a single block - A phi-def can use undef values from diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp index 238b5668ef1..201e9b16cba 100644 --- a/lib/CodeGen/SplitKit.cpp +++ b/lib/CodeGen/SplitKit.cpp @@ -48,7 +48,8 @@ SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, void SplitAnalysis::clear() { UseSlots.clear(); - LiveBlocks.clear(); + UseBlocks.clear(); + ThroughBlocks.clear(); CurLI = 0; } @@ -121,15 +122,17 @@ void SplitAnalysis::analyzeUses() { DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n"); const_cast(LIS) .shrinkToUses(const_cast(CurLI)); - LiveBlocks.clear(); + UseBlocks.clear(); + ThroughBlocks.clear(); bool fixed = calcLiveBlockInfo(); (void)fixed; assert(fixed && "Couldn't fix broken live interval"); } DEBUG(dbgs() << "Analyze counted " - << UseSlots.size() << " instrs, " - << LiveBlocks.size() << " spanned.\n"); + << UseSlots.size() << " instrs in " + << UseBlocks.size() << " blocks, through " + << ThroughBlocks.size() << " blocks.\n"); } /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks @@ -159,8 +162,8 @@ bool SplitAnalysis::calcLiveBlockInfo() { BI.Def = LVI->start; // Find the first and last uses in the block. - BI.Uses = UseI != UseE && *UseI < Stop; - if (BI.Uses) { + bool Uses = UseI != UseE && *UseI < Stop; + if (Uses) { BI.FirstUse = *UseI; assert(BI.FirstUse >= Start); do ++UseI; @@ -188,11 +191,14 @@ bool SplitAnalysis::calcLiveBlockInfo() { // Don't set LiveThrough when the block has a gap. BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut; - LiveBlocks.push_back(BI); + if (Uses) + UseBlocks.push_back(BI); + else + ThroughBlocks.push_back(BI.MBB->getNumber()); // FIXME: This should never happen. The live range stops or starts without a // corresponding use. An earlier pass did something wrong. - if (!BI.LiveThrough && !BI.Uses) + if (!BI.LiveThrough && !Uses) return false; // LVI is now at LVE or LVI->end >= Stop. @@ -907,12 +913,12 @@ void SplitEditor::finish() { /// may be an advantage to split CurLI for the duration of the block. bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { // If CurLI is local to one block, there is no point to splitting it. - if (LiveBlocks.size() <= 1) + if (UseBlocks.size() <= 1) return false; // Add blocks with multiple uses. - for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { - const BlockInfo &BI = LiveBlocks[i]; - if (!BI.Uses || BI.FirstUse == BI.LastUse) + for (unsigned i = 0, e = UseBlocks.size(); i != e; ++i) { + const BlockInfo &BI = UseBlocks[i]; + if (BI.FirstUse == BI.LastUse) continue; Blocks.insert(BI.MBB); } @@ -923,10 +929,10 @@ bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { /// basic block in Blocks. void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); - - for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) { - const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i]; - if (!BI.Uses || !Blocks.count(BI.MBB)) + 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(); diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 793989f7e37..20ac8a1fdc5 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -12,6 +12,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/IndexedMap.h" @@ -69,16 +70,11 @@ public: SlotIndex LastUse; ///< Last instr using current reg. SlotIndex Kill; ///< Interval end point inside block. SlotIndex Def; ///< Interval start point inside block. - bool Uses; ///< Current reg has uses or defs in block. bool LiveThrough; ///< Live in whole block (Templ 5. or 6. above). bool LiveIn; ///< Current reg is live in. bool LiveOut; ///< Current reg is live out. }; - /// Basic blocks where var is live. This array is parallel to - /// SpillConstraints. - SmallVector LiveBlocks; - private: // Current live interval. const LiveInterval *CurLI; @@ -89,6 +85,12 @@ private: /// successor. SmallVector, 8> LastSplitPoint; + /// UseBlocks - Blocks where CurLI has uses. + SmallVector UseBlocks; + + /// ThroughBlocks - Block numbers where CurLI is live through without uses. + SmallVector ThroughBlocks; + SlotIndex computeLastSplitPoint(unsigned Num); // Sumarize statistics by counting instructions using CurLI. @@ -129,6 +131,14 @@ public: /// splitting. bool isOriginalEndpoint(SlotIndex Idx) const; + /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks + /// where CurLI has uses. + ArrayRef getUseBlocks() { return UseBlocks; } + + /// getThroughBlocks - Return an array of block numbers where CurLI is live + /// through without uses. + ArrayRef getThroughBlocks() { return ThroughBlocks; } + typedef SmallPtrSet BlockPtrSet; /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from