summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/CodeGen/EdgeBundles.h7
-rw-r--r--lib/CodeGen/EdgeBundles.cpp15
-rw-r--r--lib/CodeGen/RegAllocGreedy.cpp124
-rw-r--r--lib/CodeGen/SpillPlacement.cpp71
-rw-r--r--lib/CodeGen/SpillPlacement.h26
-rw-r--r--lib/CodeGen/SplitKit.cpp11
-rw-r--r--lib/CodeGen/SplitKit.h13
7 files changed, 183 insertions, 84 deletions
diff --git a/include/llvm/CodeGen/EdgeBundles.h b/include/llvm/CodeGen/EdgeBundles.h
index 2c5215a792..8aab3c64f1 100644
--- a/include/llvm/CodeGen/EdgeBundles.h
+++ b/include/llvm/CodeGen/EdgeBundles.h
@@ -16,6 +16,7 @@
#ifndef LLVM_CODEGEN_EDGEBUNDLES_H
#define LLVM_CODEGEN_EDGEBUNDLES_H
+#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/IntEqClasses.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
@@ -29,6 +30,9 @@ class EdgeBundles : public MachineFunctionPass {
/// 2*BB->getNumber()+1 -> Outgoing bundle.
IntEqClasses EC;
+ /// Blocks - Map each bundle to a list of basic block numbers.
+ SmallVector<SmallVector<unsigned, 8>, 4> Blocks;
+
public:
static char ID;
EdgeBundles() : MachineFunctionPass(ID) {}
@@ -40,6 +44,9 @@ public:
/// getNumBundles - Return the total number of bundles in the CFG.
unsigned getNumBundles() const { return EC.getNumClasses(); }
+ /// getBlocks - Return an array of blocks that are connected to Bundle.
+ ArrayRef<unsigned> getBlocks(unsigned Bundle) { return Blocks[Bundle]; }
+
/// getMachineFunction - Return the last machine function computed.
const MachineFunction *getMachineFunction() const { return MF; }
diff --git a/lib/CodeGen/EdgeBundles.cpp b/lib/CodeGen/EdgeBundles.cpp
index aed8bc9479..646e01407a 100644
--- a/lib/CodeGen/EdgeBundles.cpp
+++ b/lib/CodeGen/EdgeBundles.cpp
@@ -53,6 +53,19 @@ bool EdgeBundles::runOnMachineFunction(MachineFunction &mf) {
EC.compress();
if (ViewEdgeBundles)
view();
+
+ // Compute the reverse mapping.
+ Blocks.clear();
+ Blocks.resize(getNumBundles());
+
+ for (unsigned i = 0, e = MF->getNumBlockIDs(); i != e; ++i) {
+ unsigned b0 = getBundle(i, 0);
+ unsigned b1 = getBundle(i, 1);
+ Blocks[b0].push_back(i);
+ if (b1 != b0)
+ Blocks[b1].push_back(i);
+ }
+
return false;
}
@@ -82,5 +95,3 @@ raw_ostream &llvm::WriteGraph(raw_ostream &O, const EdgeBundles &G,
O << "}\n";
return O;
}
-
-
diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 889bca3011..7c2ed3fc4e 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -22,6 +22,7 @@
#include "SpillPlacement.h"
#include "SplitKit.h"
#include "VirtRegMap.h"
+#include "llvm/ADT/SparseBitVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Function.h"
@@ -126,9 +127,8 @@ class RAGreedy : public MachineFunctionPass,
/// All basic blocks where the current register has uses.
SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
- /// All basic blocks where the current register is live-through and
- /// interference free.
- SmallVector<unsigned, 8> TransparentBlocks;
+ /// Live-through blocks that have already been added to SpillPlacer.
+ SparseBitVector<> ActiveThroughBlocks;
/// Global live range splitting candidate info.
struct GlobalSplitCandidate {
@@ -173,7 +173,9 @@ private:
void LRE_WillShrinkVirtReg(unsigned);
void LRE_DidCloneVirtReg(unsigned, unsigned);
- bool addSplitConstraints(unsigned, float&);
+ bool addSplitConstraints(InterferenceCache::Cursor, float&);
+ void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
+ void growRegion(InterferenceCache::Cursor);
float calcGlobalSplitCost(unsigned, const BitVector&);
void splitAroundRegion(LiveInterval&, unsigned, const BitVector&,
SmallVectorImpl<LiveInterval*>&);
@@ -417,9 +419,9 @@ unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
/// interference pattern in Physreg and its aliases. Add the constraints to
/// SpillPlacement and return the static cost of this split in Cost, assuming
/// that all preferences in SplitConstraints are met.
-/// If it is evident that no bundles will be live, abort early and return false.
-bool RAGreedy::addSplitConstraints(unsigned PhysReg, float &Cost) {
- InterferenceCache::Cursor Intf(IntfCache, PhysReg);
+/// Return false if there are no bundles with positive bias.
+bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
+ float &Cost) {
ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
// Reset interference dependent info.
@@ -464,35 +466,41 @@ bool RAGreedy::addSplitConstraints(unsigned PhysReg, float &Cost) {
if (Ins)
StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
}
+ Cost = StaticCost;
// Add constraints for use-blocks. Note that these are the only constraints
// that may add a positive bias, it is downhill from here.
SpillPlacer->addConstraints(SplitConstraints);
- if (SpillPlacer->getPositiveNodes() == 0)
- return false;
+ return SpillPlacer->scanActiveBundles();
+}
- Cost = StaticCost;
- // Now handle the live-through blocks without uses. These can only add
- // negative bias, so we can abort whenever there are no more positive nodes.
- // Compute constraints for a group of 8 blocks at a time.
+/// addThroughConstraints - Add constraints and links to SpillPlacer from the
+/// live-through blocks in Blocks.
+void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
+ ArrayRef<unsigned> Blocks) {
const unsigned GroupSize = 8;
SpillPlacement::BlockConstraint BCS[GroupSize];
- unsigned B = 0;
- TransparentBlocks.clear();
+ unsigned TBS[GroupSize];
+ unsigned B = 0, T = 0;
- ArrayRef<unsigned> ThroughBlocks = SA->getThroughBlocks();
- for (unsigned i = 0; i != ThroughBlocks.size(); ++i) {
- unsigned Number = ThroughBlocks[i];
- assert(B < GroupSize && "Array overflow");
- BCS[B].Number = Number;
+ for (unsigned i = 0; i != Blocks.size(); ++i) {
+ unsigned Number = Blocks[i];
Intf.moveToBlock(Number);
if (!Intf.hasInterference()) {
- TransparentBlocks.push_back(Number);
+ assert(T < GroupSize && "Array overflow");
+ TBS[T] = Number;
+ if (++T == GroupSize) {
+ SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T));
+ T = 0;
+ }
continue;
}
+ assert(B < GroupSize && "Array overflow");
+ BCS[B].Number = Number;
+
// Interference for the live-in value.
if (Intf.first() <= Indexes->getMBBStartIdx(Number))
BCS[B].Entry = SpillPlacement::MustSpill;
@@ -509,22 +517,55 @@ bool RAGreedy::addSplitConstraints(unsigned PhysReg, float &Cost) {
ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
SpillPlacer->addConstraints(Array);
B = 0;
- // Abort early when all hope is lost.
- if (SpillPlacer->getPositiveNodes() == 0)
- return false;
}
}
ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
SpillPlacer->addConstraints(Array);
- if (SpillPlacer->getPositiveNodes() == 0)
- return false;
-
- // There is still some positive bias. Add all the links.
- SpillPlacer->addLinks(TransparentBlocks);
- return true;
+ SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T));
}
+void RAGreedy::growRegion(InterferenceCache::Cursor Intf) {
+ // Keep track of through blocks that have already been added to SpillPlacer.
+ SparseBitVector<> Added;
+ SmallVector<unsigned, 16> ThroughBlocks;
+#ifndef NDEBUG
+ unsigned Visited = 0;
+#endif
+ for (;;) {
+ ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
+ if (NewBundles.empty())
+ break;
+ // Find new through blocks in the periphery of PrefRegBundles.
+ for (int i = 0, e = NewBundles.size(); i != e; ++i) {
+ unsigned Bundle = NewBundles[i];
+ // Look at all blocks connected to Bundle in the full graph.
+ ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
+ for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
+ I != E; ++I) {
+ unsigned Block = *I;
+ if (!SA->isThroughBlock(Block) || !Added.test_and_set(Block))
+ continue;
+ // This is a new through block. Add it to SpillPlacer later.
+ ThroughBlocks.push_back(Block);
+#ifndef NDEBUG
+ ++Visited;
+#endif
+ }
+ }
+ // Any new blocks to add?
+ if (!ThroughBlocks.empty()) {
+ addThroughConstraints(Intf, ThroughBlocks);
+ ThroughBlocks.clear();
+ }
+ // Perhaps iterating can enable more bundles?
+ SpillPlacer->iterate();
+ }
+
+ // Rememeber the relevant set of through blocks for splitAroundRegion().
+ ActiveThroughBlocks |= Added;
+ DEBUG(dbgs() << ", v=" << Visited);
+}
/// calcGlobalSplitCost - Return the global split cost of following the split
/// pattern in LiveBundles. This cost should be added to the local cost of the
@@ -550,10 +591,9 @@ float RAGreedy::calcGlobalSplitCost(unsigned PhysReg,
}
InterferenceCache::Cursor Intf(IntfCache, PhysReg);
- ArrayRef<unsigned> ThroughBlocks = SA->getThroughBlocks();
- SplitConstraints.resize(UseBlocks.size() + ThroughBlocks.size());
- for (unsigned i = 0; i != ThroughBlocks.size(); ++i) {
- unsigned Number = ThroughBlocks[i];
+ for (SparseBitVector<>::iterator I = ActiveThroughBlocks.begin(),
+ E = ActiveThroughBlocks.end(); I != E; ++I) {
+ unsigned Number = *I;
bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)];
bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
if (!RegIn && !RegOut)
@@ -766,9 +806,9 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
}
// Handle live-through blocks.
- ArrayRef<unsigned> ThroughBlocks = SA->getThroughBlocks();
- for (unsigned i = 0; i != ThroughBlocks.size(); ++i) {
- unsigned Number = ThroughBlocks[i];
+ for (SparseBitVector<>::iterator I = ActiveThroughBlocks.begin(),
+ E = ActiveThroughBlocks.end(); I != E; ++I) {
+ unsigned Number = *I;
bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)];
bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
DEBUG(dbgs() << "Live through BB#" << Number << '\n');
@@ -804,6 +844,7 @@ unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
BitVector LiveBundles, BestBundles;
float BestCost = 0;
unsigned BestReg = 0;
+ ActiveThroughBlocks.clear();
Order.rewind();
for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) {
@@ -813,16 +854,17 @@ unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
SpillPlacer->prepare(LiveBundles);
float Cost;
- if (!addSplitConstraints(PhysReg, Cost)) {
- DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bias\n");
+ InterferenceCache::Cursor Intf(IntfCache, PhysReg);
+ if (!addSplitConstraints(Intf, Cost)) {
+ DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n");
continue;
}
- DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tbiased = "
- << SpillPlacer->getPositiveNodes() << ", static = " << Cost);
+ DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost);
if (BestReg && Cost >= BestCost) {
DEBUG(dbgs() << " worse than " << PrintReg(BestReg, TRI) << '\n');
continue;
}
+ growRegion(Intf);
SpillPlacer->finish();
diff --git a/lib/CodeGen/SpillPlacement.cpp b/lib/CodeGen/SpillPlacement.cpp
index cab18a1240..6949618632 100644
--- a/lib/CodeGen/SpillPlacement.cpp
+++ b/lib/CodeGen/SpillPlacement.cpp
@@ -135,13 +135,10 @@ struct SpillPlacement::Node {
/// addBias - Bias this node from an ingoing[0] or outgoing[1] link.
/// Return the change to the total number of positive biases.
- int addBias(float w, bool out) {
+ void addBias(float w, bool out) {
// Normalize w relative to all connected blocks from that direction.
w *= Scale[out];
- int Before = Bias > 0;
Bias += w;
- int After = Bias > 0;
- return After - Before;
}
/// update - Recompute Value from Bias and Links. Return true when node
@@ -230,14 +227,14 @@ void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
if (I->Entry != DontCare) {
unsigned ib = bundles->getBundle(I->Number, 0);
activate(ib);
- PositiveNodes += nodes[ib].addBias(Freq * Bias[I->Entry], 1);
+ nodes[ib].addBias(Freq * Bias[I->Entry], 1);
}
// Live-out from block?
if (I->Exit != DontCare) {
unsigned ob = bundles->getBundle(I->Number, 1);
activate(ob);
- PositiveNodes += nodes[ob].addBias(Freq * Bias[I->Exit], 0);
+ nodes[ob].addBias(Freq * Bias[I->Exit], 0);
}
}
}
@@ -254,16 +251,42 @@ void SpillPlacement::addLinks(ArrayRef<unsigned> Links) {
continue;
activate(ib);
activate(ob);
+ if (nodes[ib].Links.empty() && !nodes[ib].mustSpill())
+ Linked.push_back(ib);
+ if (nodes[ob].Links.empty() && !nodes[ob].mustSpill())
+ Linked.push_back(ob);
float Freq = getBlockFrequency(Number);
nodes[ib].addLink(ob, Freq, 1);
nodes[ob].addLink(ib, Freq, 0);
}
}
+bool SpillPlacement::scanActiveBundles() {
+ Linked.clear();
+ RecentPositive.clear();
+ for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) {
+ nodes[n].update(nodes);
+ // A node that must spill, or a node without any links is not going to
+ // change its value ever again, so exclude it from iterations.
+ if (nodes[n].mustSpill())
+ continue;
+ if (!nodes[n].Links.empty())
+ Linked.push_back(n);
+ if (nodes[n].preferReg())
+ RecentPositive.push_back(n);
+ }
+ return !RecentPositive.empty();
+}
+
/// iterate - Repeatedly update the Hopfield nodes until stability or the
/// maximum number of iterations is reached.
/// @param Linked - Numbers of linked nodes that need updating.
-void SpillPlacement::iterate(const SmallVectorImpl<unsigned> &Linked) {
+void SpillPlacement::iterate() {
+ // First update the recently positive nodes. They have likely received new
+ // negative bias that will turn them off.
+ while (!RecentPositive.empty())
+ nodes[RecentPositive.pop_back_val()].update(nodes);
+
if (Linked.empty())
return;
@@ -279,10 +302,13 @@ void SpillPlacement::iterate(const SmallVectorImpl<unsigned> &Linked) {
for (SmallVectorImpl<unsigned>::const_reverse_iterator I =
llvm::next(Linked.rbegin()), E = Linked.rend(); I != E; ++I) {
unsigned n = *I;
- bool C = nodes[n].update(nodes);
- Changed |= C;
+ if (nodes[n].update(nodes)) {
+ Changed = true;
+ if (nodes[n].preferReg())
+ RecentPositive.push_back(n);
+ }
}
- if (!Changed)
+ if (!Changed || !RecentPositive.empty())
return;
// Scan forwards, skipping the first node which was just updated.
@@ -290,38 +316,29 @@ void SpillPlacement::iterate(const SmallVectorImpl<unsigned> &Linked) {
for (SmallVectorImpl<unsigned>::const_iterator I =
llvm::next(Linked.begin()), E = Linked.end(); I != E; ++I) {
unsigned n = *I;
- bool C = nodes[n].update(nodes);
- Changed |= C;
+ if (nodes[n].update(nodes)) {
+ Changed = true;
+ if (nodes[n].preferReg())
+ RecentPositive.push_back(n);
+ }
}
- if (!Changed)
+ if (!Changed || !RecentPositive.empty())
return;
}
}
void SpillPlacement::prepare(BitVector &RegBundles) {
+ Linked.clear();
+ RecentPositive.clear();
// Reuse RegBundles as our ActiveNodes vector.
ActiveNodes = &RegBundles;
ActiveNodes->clear();
ActiveNodes->resize(bundles->getNumBundles());
- PositiveNodes = 0;
}
bool
SpillPlacement::finish() {
assert(ActiveNodes && "Call prepare() first");
- // Update all active nodes, and find the ones that are actually linked to
- // something so their value may change when iterating.
- SmallVector<unsigned, 8> Linked;
- for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) {
- nodes[n].update(nodes);
- // A node that must spill, or a node without any links is not going to
- // change its value ever again, so exclude it from iterations.
- if (!nodes[n].Links.empty() && !nodes[n].mustSpill())
- Linked.push_back(n);
- }
-
- // Iterate the network to convergence.
- iterate(Linked);
// Write preferences back to ActiveNodes.
bool Perfect = true;
diff --git a/lib/CodeGen/SpillPlacement.h b/lib/CodeGen/SpillPlacement.h
index 46e64e6fcb..6952ad8009 100644
--- a/lib/CodeGen/SpillPlacement.h
+++ b/lib/CodeGen/SpillPlacement.h
@@ -49,8 +49,12 @@ class SpillPlacement : public MachineFunctionPass {
// caller.
BitVector *ActiveNodes;
- // The number of active nodes with a positive bias.
- unsigned PositiveNodes;
+ // Nodes with active links. Populated by scanActiveBundles.
+ SmallVector<unsigned, 8> Linked;
+
+ // Nodes that went positive during the last call to scanActiveBundles or
+ // iterate.
+ SmallVector<unsigned, 8> RecentPositive;
// Block frequencies are computed once. Indexed by block number.
SmallVector<float, 4> BlockFrequency;
@@ -95,9 +99,20 @@ public:
/// addLinks - Add transparent blocks with the given numbers.
void addLinks(ArrayRef<unsigned> Links);
- /// getPositiveNodes - Return the total number of graph nodes with a positive
- /// bias after adding constraints.
- unsigned getPositiveNodes() const { return PositiveNodes; }
+ /// scanActiveBundles - Perform an initial scan of all bundles activated by
+ /// addConstraints and addLinks, updating their state. Add all the bundles
+ /// that now prefer a register to RecentPositive.
+ /// Prepare internal data structures for iterate.
+ /// Return true is there are any positive nodes.
+ bool scanActiveBundles();
+
+ /// iterate - Update the network iteratively until convergence, or new bundles
+ /// are found.
+ void iterate();
+
+ /// getRecentPositive - Return an array of bundles that became positive during
+ /// the previous call to scanActiveBundles or iterate.
+ ArrayRef<unsigned> getRecentPositive() { return RecentPositive; }
/// finish - Compute the optimal spill code placement given the
/// constraints. No MustSpill constraints will be violated, and the smallest
@@ -120,7 +135,6 @@ private:
virtual void releaseMemory();
void activate(unsigned);
- void iterate(const SmallVectorImpl<unsigned>&);
};
} // end namespace llvm
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index 201e9b16cb..6195ab0f20 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -132,12 +132,14 @@ void SplitAnalysis::analyzeUses() {
DEBUG(dbgs() << "Analyze counted "
<< UseSlots.size() << " instrs in "
<< UseBlocks.size() << " blocks, through "
- << ThroughBlocks.size() << " blocks.\n");
+ << NumThroughBlocks << " blocks.\n");
}
/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
/// where CurLI is live.
bool SplitAnalysis::calcLiveBlockInfo() {
+ ThroughBlocks.resize(MF.getNumBlockIDs());
+ NumThroughBlocks = 0;
if (CurLI->empty())
return true;
@@ -193,9 +195,10 @@ bool SplitAnalysis::calcLiveBlockInfo() {
BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
if (Uses)
UseBlocks.push_back(BI);
- else
- ThroughBlocks.push_back(BI.MBB->getNumber());
-
+ else {
+ ++NumThroughBlocks;
+ ThroughBlocks.set(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 && !Uses)
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index 20ac8a1fdc..f1ff501fbd 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -89,7 +89,10 @@ private:
SmallVector<BlockInfo, 8> UseBlocks;
/// ThroughBlocks - Block numbers where CurLI is live through without uses.
- SmallVector<unsigned, 8> ThroughBlocks;
+ BitVector ThroughBlocks;
+
+ /// NumThroughBlocks - Number of live-through blocks.
+ unsigned NumThroughBlocks;
SlotIndex computeLastSplitPoint(unsigned Num);
@@ -135,9 +138,11 @@ public:
/// where CurLI has uses.
ArrayRef<BlockInfo> getUseBlocks() { return UseBlocks; }
- /// getThroughBlocks - Return an array of block numbers where CurLI is live
- /// through without uses.
- ArrayRef<unsigned> getThroughBlocks() { return ThroughBlocks; }
+ /// getNumThroughBlocks - Return the number of through blocks.
+ unsigned getNumThroughBlocks() const { return NumThroughBlocks; }
+
+ /// isThroughBlock - Return true if CurLI is live through MBB without uses.
+ bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); }
typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-29 21:54:07 +0000