aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen
diff options
context:
space:
mode:
authorJakob Stoklund Olesen <stoklund@2pi.dk>2012-06-20 22:52:24 +0000
committerJakob Stoklund Olesen <stoklund@2pi.dk>2012-06-20 22:52:24 +0000
commit812cda9a5cc26b1f8dda6f909bf5062c215b65d7 (patch)
tree87bc7026acaa8316786b6a087b6223af4d709ec7 /lib/CodeGen
parent797e9a7737136a5e13d9114fe11543da471f9bdc (diff)
Convert RABasic to using LiveRegMatrix interference checking.
Stop using the LiveIntervalUnions provided by RegAllocBase, they will be removed soon. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158866 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen')
-rw-r--r--lib/CodeGen/RegAllocBase.cpp13
-rw-r--r--lib/CodeGen/RegAllocBase.h4
-rw-r--r--lib/CodeGen/RegAllocBasic.cpp119
3 files changed, 67 insertions, 69 deletions
diff --git a/lib/CodeGen/RegAllocBase.cpp b/lib/CodeGen/RegAllocBase.cpp
index f4774dcab0..1f824a8fdb 100644
--- a/lib/CodeGen/RegAllocBase.cpp
+++ b/lib/CodeGen/RegAllocBase.cpp
@@ -14,6 +14,7 @@
#define DEBUG_TYPE "regalloc"
#include "RegAllocBase.h"
+#include "LiveRegMatrix.h"
#include "Spiller.h"
#include "VirtRegMap.h"
#include "llvm/ADT/Statistic.h"
@@ -134,6 +135,11 @@ void RegAllocBase::seedLiveRegs() {
}
void RegAllocBase::assign(LiveInterval &VirtReg, unsigned PhysReg) {
+ // FIXME: This diversion is temporary.
+ if (Matrix) {
+ Matrix->assign(VirtReg, PhysReg);
+ return;
+ }
DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI)
<< " to " << PrintReg(PhysReg, TRI) << '\n');
assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
@@ -144,6 +150,11 @@ void RegAllocBase::assign(LiveInterval &VirtReg, unsigned PhysReg) {
}
void RegAllocBase::unassign(LiveInterval &VirtReg, unsigned PhysReg) {
+ // FIXME: This diversion is temporary.
+ if (Matrix) {
+ Matrix->unassign(VirtReg);
+ return;
+ }
DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI)
<< " from " << PrintReg(PhysReg, TRI) << '\n');
assert(VRM->getPhys(VirtReg.reg) == PhysReg && "Inconsistent unassign");
@@ -170,6 +181,8 @@ void RegAllocBase::allocatePhysRegs() {
// Invalidate all interference queries, live ranges could have changed.
invalidateVirtRegs();
+ if (Matrix)
+ Matrix->invalidateVirtRegs();
// selectOrSplit requests the allocator to return an available physical
// register if possible and populate a list of new live intervals that
diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h
index cc13e75947..367efa4f6a 100644
--- a/lib/CodeGen/RegAllocBase.h
+++ b/lib/CodeGen/RegAllocBase.h
@@ -47,6 +47,7 @@ template<typename T> class SmallVectorImpl;
class TargetRegisterInfo;
class VirtRegMap;
class LiveIntervals;
+class LiveRegMatrix;
class Spiller;
/// RegAllocBase provides the register allocation driver and interface that can
@@ -73,9 +74,10 @@ protected:
MachineRegisterInfo *MRI;
VirtRegMap *VRM;
LiveIntervals *LIS;
+ LiveRegMatrix *Matrix;
RegisterClassInfo RegClassInfo;
- RegAllocBase(): UserTag(0), TRI(0), MRI(0), VRM(0), LIS(0) {}
+ RegAllocBase(): UserTag(0), TRI(0), MRI(0), VRM(0), LIS(0), Matrix(0) {}
virtual ~RegAllocBase() {}
diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp
index 73059ec0ab..9d1f01abdb 100644
--- a/lib/CodeGen/RegAllocBasic.cpp
+++ b/lib/CodeGen/RegAllocBasic.cpp
@@ -13,11 +13,13 @@
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "regalloc"
+#include "AllocationOrder.h"
#include "RegAllocBase.h"
#include "LiveDebugVariables.h"
#include "RenderMachineFunction.h"
#include "Spiller.h"
#include "VirtRegMap.h"
+#include "LiveRegMatrix.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Function.h"
#include "llvm/PassAnalysisSupport.h"
@@ -119,9 +121,6 @@ public:
bool spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
SmallVectorImpl<LiveInterval*> &SplitVRegs);
- void spillReg(LiveInterval &VirtReg, unsigned PhysReg,
- SmallVectorImpl<LiveInterval*> &SplitVRegs);
-
static char ID;
};
@@ -140,6 +139,7 @@ RABasic::RABasic(): MachineFunctionPass(ID) {
initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
+ initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry());
initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
}
@@ -161,6 +161,8 @@ void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addPreserved<MachineLoopInfo>();
AU.addRequired<VirtRegMap>();
AU.addPreserved<VirtRegMap>();
+ AU.addRequired<LiveRegMatrix>();
+ AU.addPreserved<LiveRegMatrix>();
DEBUG(AU.addRequired<RenderMachineFunction>());
MachineFunctionPass::getAnalysisUsage(AU);
}
@@ -170,32 +172,6 @@ void RABasic::releaseMemory() {
RegAllocBase::releaseMemory();
}
-// Helper for spillInterferences() that spills all interfering vregs currently
-// assigned to this physical register.
-void RABasic::spillReg(LiveInterval& VirtReg, unsigned PhysReg,
- SmallVectorImpl<LiveInterval*> &SplitVRegs) {
- LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg);
- assert(Q.seenAllInterferences() && "need collectInterferences()");
- const SmallVectorImpl<LiveInterval*> &PendingSpills = Q.interferingVRegs();
-
- for (SmallVectorImpl<LiveInterval*>::const_iterator I = PendingSpills.begin(),
- E = PendingSpills.end(); I != E; ++I) {
- LiveInterval &SpilledVReg = **I;
- DEBUG(dbgs() << "extracting from " <<
- TRI->getName(PhysReg) << " " << SpilledVReg << '\n');
-
- // Deallocate the interfering vreg by removing it from the union.
- // A LiveInterval instance may not be in a union during modification!
- unassign(SpilledVReg, PhysReg);
-
- // Spill the extracted interval.
- LiveRangeEdit LRE(&SpilledVReg, SplitVRegs, *MF, *LIS, VRM);
- spiller().spill(LRE);
- }
- // After extracting segments, the query's results are invalid. But keep the
- // contents valid until we're done accessing pendingSpills.
- Q.clear();
-}
// Spill or split all live virtual registers currently unified under PhysReg
// that interfere with VirtReg. The newly spilled or split live intervals are
@@ -204,22 +180,41 @@ bool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
SmallVectorImpl<LiveInterval*> &SplitVRegs) {
// Record each interference and determine if all are spillable before mutating
// either the union or live intervals.
- unsigned NumInterferences = 0;
+ SmallVector<LiveInterval*, 8> Intfs;
+
// Collect interferences assigned to any alias of the physical register.
- for (MCRegAliasIterator AI(PhysReg, TRI, true); AI.isValid(); ++AI) {
- LiveIntervalUnion::Query &QAlias = query(VirtReg, *AI);
- NumInterferences += QAlias.collectInterferingVRegs();
- if (QAlias.seenUnspillableVReg()) {
+ for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
+ LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
+ Q.collectInterferingVRegs();
+ if (Q.seenUnspillableVReg())
return false;
+ for (unsigned i = Q.interferingVRegs().size(); i; --i) {
+ LiveInterval *Intf = Q.interferingVRegs()[i - 1];
+ if (!Intf->isSpillable() || Intf->weight > VirtReg.weight)
+ return false;
+ Intfs.push_back(Intf);
}
}
DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) <<
" interferences with " << VirtReg << "\n");
- assert(NumInterferences > 0 && "expect interference");
+ assert(!Intfs.empty() && "expected interference");
// Spill each interfering vreg allocated to PhysReg or an alias.
- for (MCRegAliasIterator AI(PhysReg, TRI, true); AI.isValid(); ++AI)
- spillReg(VirtReg, *AI, SplitVRegs);
+ for (unsigned i = 0, e = Intfs.size(); i != e; ++i) {
+ LiveInterval &Spill = *Intfs[i];
+
+ // Skip duplicates.
+ if (!VRM->hasPhys(Spill.reg))
+ continue;
+
+ // Deallocate the interfering vreg by removing it from the union.
+ // A LiveInterval instance may not be in a union during modification!
+ Matrix->unassign(Spill);
+
+ // Spill the extracted interval.
+ LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM);
+ spiller().spill(LRE);
+ }
return true;
}
@@ -237,49 +232,36 @@ bool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
// selectOrSplit().
unsigned RABasic::selectOrSplit(LiveInterval &VirtReg,
SmallVectorImpl<LiveInterval*> &SplitVRegs) {
- // Check for register mask interference. When live ranges cross calls, the
- // set of usable registers is reduced to the callee-saved ones.
- bool CrossRegMasks = LIS->checkRegMaskInterference(VirtReg, UsableRegs);
-
// Populate a list of physical register spill candidates.
SmallVector<unsigned, 8> PhysRegSpillCands;
// Check for an available register in this class.
- ArrayRef<unsigned> Order =
- RegClassInfo.getOrder(MRI->getRegClass(VirtReg.reg));
- for (ArrayRef<unsigned>::iterator I = Order.begin(), E = Order.end(); I != E;
- ++I) {
- unsigned PhysReg = *I;
-
- // If PhysReg is clobbered by a register mask, it isn't useful for
- // allocation or spilling.
- if (CrossRegMasks && !UsableRegs.test(PhysReg))
- continue;
-
- // Check interference and as a side effect, intialize queries for this
- // VirtReg and its aliases.
- unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg);
- if (interfReg == 0) {
- // Found an available register.
+ AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo);
+ while (unsigned PhysReg = Order.next()) {
+ // Check for interference in PhysReg
+ switch (Matrix->checkInterference(VirtReg, PhysReg)) {
+ case LiveRegMatrix::IK_Free:
+ // PhysReg is available, allocate it.
return PhysReg;
- }
- LiveIntervalUnion::Query &IntfQ = query(VirtReg, interfReg);
- IntfQ.collectInterferingVRegs(1);
- LiveInterval *interferingVirtReg = IntfQ.interferingVRegs().front();
- // The current VirtReg must either be spillable, or one of its interferences
- // must have less spill weight.
- if (interferingVirtReg->weight < VirtReg.weight ) {
+ case LiveRegMatrix::IK_VirtReg:
+ // Only virtual registers in the way, we may be able to spill them.
PhysRegSpillCands.push_back(PhysReg);
+ continue;
+
+ default:
+ // RegMask or RegUnit interference.
+ continue;
}
}
+
// Try to spill another interfering reg with less spill weight.
for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
- PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
-
- if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue;
+ PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
+ if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs))
+ continue;
- assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 &&
+ assert(!Matrix->checkInterference(VirtReg, *PhysRegI) &&
"Interference after spill.");
// Tell the caller to allocate to this newly freed physical register.
return *PhysRegI;
@@ -306,6 +288,7 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) {
DEBUG(RMF = &getAnalysis<RenderMachineFunction>());
RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
+ Matrix = &getAnalysis<LiveRegMatrix>();
SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
allocatePhysRegs();