diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2011-07-14 00:31:14 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2011-07-14 00:31:14 +0000 |
commit | 6a9feaac935c9345f825b272cf3225248e282f3f (patch) | |
tree | 3dea0c08b277f98940c0512fa9c95bc77a20f5c3 /lib/CodeGen | |
parent | 7e9450107148895cd882dbaa21f17727b876998a (diff) | |
download | external_llvm-6a9feaac935c9345f825b272cf3225248e282f3f.zip external_llvm-6a9feaac935c9345f825b272cf3225248e282f3f.tar.gz external_llvm-6a9feaac935c9345f825b272cf3225248e282f3f.tar.bz2 |
Count references to interference cache entries.
Each InterferenceCache::Cursor instance references a cache entry. A
non-zero reference count guarantees that the entry won't be reused for a
new register.
This makes it possible to have multiple live cursors examining
interference for different physregs.
The total number of live cursors into a cache must be kept below
InterferenceCache::getMaxCursors().
Code generation should be unaffected by this change, and it doesn't seem
to affect the cache replacement strategy either.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135121 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen')
-rw-r--r-- | lib/CodeGen/InterferenceCache.cpp | 17 | ||||
-rw-r--r-- | lib/CodeGen/InterferenceCache.h | 43 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocGreedy.cpp | 21 |
3 files changed, 70 insertions, 11 deletions
diff --git a/lib/CodeGen/InterferenceCache.cpp b/lib/CodeGen/InterferenceCache.cpp index b1014a9..a09bb39 100644 --- a/lib/CodeGen/InterferenceCache.cpp +++ b/lib/CodeGen/InterferenceCache.cpp @@ -14,6 +14,7 @@ #define DEBUG_TYPE "regalloc" #include "InterferenceCache.h" #include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Support/ErrorHandling.h" using namespace llvm; @@ -40,9 +41,18 @@ InterferenceCache::Entry *InterferenceCache::get(unsigned PhysReg) { E = RoundRobin; if (++RoundRobin == CacheEntries) RoundRobin = 0; - Entries[E].reset(PhysReg, LIUArray, TRI, MF); - PhysRegEntries[PhysReg] = E; - return &Entries[E]; + for (unsigned i = 0; i != CacheEntries; ++i) { + // Skip entries that are in use. + if (Entries[E].hasRefs()) { + if (++E == CacheEntries) + E = 0; + continue; + } + Entries[E].reset(PhysReg, LIUArray, TRI, MF); + PhysRegEntries[PhysReg] = E; + return &Entries[E]; + } + llvm_unreachable("Ran out of interference cache entries."); } /// revalidate - LIU contents have changed, update tags. @@ -59,6 +69,7 @@ void InterferenceCache::Entry::reset(unsigned physReg, LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI, const MachineFunction *MF) { + assert(!hasRefs() && "Cannot reset cache entry with references"); // LIU's changed, invalidate cache. ++Tag; PhysReg = physReg; diff --git a/lib/CodeGen/InterferenceCache.h b/lib/CodeGen/InterferenceCache.h index 6434b3a..2f402e4 100644 --- a/lib/CodeGen/InterferenceCache.h +++ b/lib/CodeGen/InterferenceCache.h @@ -43,6 +43,9 @@ class InterferenceCache { /// change. unsigned Tag; + /// RefCount - The total number of Cursor instances referring to this Entry. + unsigned RefCount; + /// MF - The current function. MachineFunction *MF; @@ -68,9 +71,10 @@ class InterferenceCache { void update(unsigned MBBNum); public: - Entry() : PhysReg(0), Tag(0), Indexes(0) {} + Entry() : PhysReg(0), Tag(0), RefCount(0), Indexes(0) {} void clear(MachineFunction *mf, SlotIndexes *indexes) { + assert(!hasRefs() && "Cannot clear cache entry with references"); PhysReg = 0; MF = mf; Indexes = indexes; @@ -78,6 +82,10 @@ class InterferenceCache { unsigned getPhysReg() const { return PhysReg; } + void addRef(int Delta) { RefCount += Delta; } + + bool hasRefs() const { return RefCount > 0; } + void revalidate(); /// valid - Return true if this is a valid entry for physReg. @@ -122,18 +130,47 @@ public: void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*, const TargetRegisterInfo *); + /// getMaxCursors - Return the maximum number of concurrent cursors that can + /// be supported. + unsigned getMaxCursors() const { return CacheEntries; } + /// Cursor - The primary query interface for the block interference cache. class Cursor { Entry *CacheEntry; BlockInterference *Current; + + void setEntry(Entry *E) { + // Update reference counts. Nothing happens when RefCount reaches 0, so + // we don't have to check for E == CacheEntry etc. + if (CacheEntry) + CacheEntry->addRef(-1); + CacheEntry = E; + if (CacheEntry) + CacheEntry->addRef(+1); + Current = 0; + } + public: /// Cursor - Create a dangling cursor. Cursor() : CacheEntry(0), Current(0) {} + ~Cursor() { setEntry(0); } + + Cursor(const Cursor &O) { + setEntry(O.CacheEntry); + } + + Cursor &operator=(const Cursor &O) { + setEntry(O.CacheEntry); + return *this; + } /// setPhysReg - Point this cursor to PhysReg's interference. void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) { - CacheEntry = Cache.get(PhysReg); - Current = 0; + // Release reference before getting a new one. That guarantees we can + // actually have CacheEntries live cursors. + setEntry(0); + if (PhysReg) + setEntry(Cache.get(PhysReg)); } /// moveTo - Move cursor to basic block MBBNum. diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp index 4728a05..8677a3e 100644 --- a/lib/CodeGen/RegAllocGreedy.cpp +++ b/lib/CodeGen/RegAllocGreedy.cpp @@ -854,11 +854,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, }); InterferenceCache::Cursor &Intf = Cand.Intf; - - // FIXME: We need cache reference counts to guarantee that Intf hasn't been - // clobbered. - Intf.setPhysReg(IntfCache, Cand.PhysReg); - LiveRangeEdit LREdit(VirtReg, NewVRegs, this); SE->reset(LREdit); @@ -1252,6 +1247,22 @@ unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, Order.rewind(); while (unsigned PhysReg = Order.next()) { + // Discard bad candidates before we run out of interference cache cursors. + // This will only affect register classes with a lot of registers (>32). + if (NumCands == IntfCache.getMaxCursors()) { + unsigned WorstCount = ~0u; + unsigned Worst = 0; + for (unsigned i = 0; i != NumCands; ++i) { + if (i == BestCand) + continue; + unsigned Count = GlobalCand[i].LiveBundles.count(); + if (Count < WorstCount) + Worst = i, WorstCount = Count; + } + --NumCands; + GlobalCand[Worst] = GlobalCand[NumCands]; + } + if (GlobalCand.size() <= NumCands) GlobalCand.resize(NumCands+1); GlobalSplitCandidate &Cand = GlobalCand[NumCands]; |