diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2012-06-20 22:52:24 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2012-06-20 22:52:24 +0000 |
commit | 812cda9a5cc26b1f8dda6f909bf5062c215b65d7 (patch) | |
tree | 87bc7026acaa8316786b6a087b6223af4d709ec7 /lib/CodeGen | |
parent | 797e9a7737136a5e13d9114fe11543da471f9bdc (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.cpp | 13 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocBase.h | 4 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocBasic.cpp | 119 |
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(); |