diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2011-03-03 03:41:29 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2011-03-03 03:41:29 +0000 |
commit | 36d61863bc83bd2301e0224adc560098b35ec0dc (patch) | |
tree | f263712c35c5e76d30493c5b80e9bfe9175d2099 /lib/CodeGen/RegAllocGreedy.cpp | |
parent | f27a40a9717c019fd07990483fb475b544bc895e (diff) | |
download | external_llvm-36d61863bc83bd2301e0224adc560098b35ec0dc.tar.gz external_llvm-36d61863bc83bd2301e0224adc560098b35ec0dc.tar.bz2 external_llvm-36d61863bc83bd2301e0224adc560098b35ec0dc.zip |
Cache basic block bounds instead of asking SlotIndexes::getMBBRange all the time.
This speeds up the greedy register allocator by 15%.
DenseMap is not as fast as one might hope.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126921 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen/RegAllocGreedy.cpp')
-rw-r--r-- | lib/CodeGen/RegAllocGreedy.cpp | 69 |
1 files changed, 30 insertions, 39 deletions
diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp index ea20ae08ea..cbecc4b2d3 100644 --- a/lib/CodeGen/RegAllocGreedy.cpp +++ b/lib/CodeGen/RegAllocGreedy.cpp @@ -473,19 +473,17 @@ float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) { for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; - SlotIndex Start, Stop; - tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); // Skip interference-free blocks. - if (IntI.start() >= Stop) + if (IntI.start() >= BI.Stop) continue; // Is the interference live-in? if (BI.LiveIn) { - IntI.advanceTo(Start); + IntI.advanceTo(BI.Start); if (!IntI.valid()) break; - if (IntI.start() <= Start) + if (IntI.start() <= BI.Start) BC.Entry = SpillPlacement::MustSpill; } @@ -495,7 +493,7 @@ float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) { IntI.advanceTo(BI.LastSplitPoint.getPrevSlot()); if (!IntI.valid()) break; - if (IntI.start() < Stop) + if (IntI.start() < BI.Stop) BC.Exit = SpillPlacement::MustSpill; } } @@ -505,20 +503,18 @@ float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) { for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; - SlotIndex Start, Stop; - tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); // Skip interference-free blocks. - if (IntI.start() >= Stop) + if (IntI.start() >= BI.Stop) continue; // Handle transparent blocks with interference separately. // Transparent blocks never incur any fixed cost. if (BI.LiveThrough && !BI.Uses) { - IntI.advanceTo(Start); + IntI.advanceTo(BI.Start); if (!IntI.valid()) break; - if (IntI.start() >= Stop) + if (IntI.start() >= BI.Stop) continue; if (BC.Entry != SpillPlacement::MustSpill) @@ -534,7 +530,7 @@ float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) { // Check interference on entry. if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) { - IntI.advanceTo(Start); + IntI.advanceTo(BI.Start); if (!IntI.valid()) break; // Not live in, but before the first use. @@ -575,7 +571,7 @@ float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) { IntI.advanceTo(BI.LastUse); if (!IntI.valid()) break; - if (IntI.start() < Stop) { + if (IntI.start() < BI.Stop) { BC.Exit = SpillPlacement::PrefSpill; // Avoid splitting twice in the same block. if (!BI.LiveThrough && !SA->isOriginalEndpoint(BI.Def)) @@ -668,18 +664,17 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; IndexPair &IP = InterferenceRanges[i]; - SlotIndex Start, Stop; - tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); + // Skip interference-free blocks. - if (IntI.start() >= Stop) + if (IntI.start() >= BI.Stop) continue; // First interference in block. if (BI.LiveIn) { - IntI.advanceTo(Start); + IntI.advanceTo(BI.Start); if (!IntI.valid()) break; - if (IntI.start() >= Stop) + if (IntI.start() >= BI.Stop) continue; if (!IP.first.isValid() || IntI.start() < IP.first) IP.first = IntI.start(); @@ -687,10 +682,10 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, // Last interference in block. if (BI.LiveOut) { - IntI.advanceTo(Stop); - if (!IntI.valid() || IntI.start() >= Stop) + IntI.advanceTo(BI.Stop); + if (!IntI.valid() || IntI.start() >= BI.Stop) --IntI; - if (IntI.stop() <= Start) + if (IntI.stop() <= BI.Start) continue; if (!IP.second.isValid() || IntI.stop() > IP.second) IP.second = IntI.stop(); @@ -716,16 +711,14 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, continue; IndexPair &IP = InterferenceRanges[i]; - SlotIndex Start, Stop; - tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); - DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" << Bundles->getBundle(BI.MBB->getNumber(), 1) << " intf [" << IP.first << ';' << IP.second << ')'); // The interference interval should either be invalid or overlap MBB. - assert((!IP.first.isValid() || IP.first < Stop) && "Bad interference"); - assert((!IP.second.isValid() || IP.second > Start) && "Bad interference"); + assert((!IP.first.isValid() || IP.first < BI.Stop) && "Bad interference"); + assert((!IP.second.isValid() || IP.second > BI.Start) + && "Bad interference"); // Check interference leaving the block. if (!IP.second.isValid()) { @@ -742,14 +735,14 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, } if (!BI.LiveThrough) { DEBUG(dbgs() << ", not live-through.\n"); - SE->useIntv(SE->enterIntvBefore(BI.Def), Stop); + SE->useIntv(SE->enterIntvBefore(BI.Def), BI.Stop); continue; } if (!RegIn) { // Block is live-through, but entry bundle is on the stack. // Reload just before the first use. DEBUG(dbgs() << ", not live-in, enter before first use.\n"); - SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); + SE->useIntv(SE->enterIntvBefore(BI.FirstUse), BI.Stop); continue; } DEBUG(dbgs() << ", live-through.\n"); @@ -762,7 +755,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, if (!BI.LiveThrough && IP.second <= BI.Def) { // The interference doesn't reach the outgoing segment. DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n'); - SE->useIntv(BI.Def, Stop); + SE->useIntv(BI.Def, BI.Stop); continue; } @@ -790,7 +783,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, SlotIndex SegStart = SE->enterIntvBefore(Use); assert(SegStart >= IP.second && "Couldn't avoid interference"); assert(SegStart < BI.LastSplitPoint && "Impossible split point"); - SE->useIntv(SegStart, Stop); + SE->useIntv(SegStart, BI.Stop); continue; } } @@ -813,8 +806,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, // We have an incoming register. Check for interference. IndexPair &IP = InterferenceRanges[i]; - SlotIndex Start, Stop; - tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) << " -> BB#" << BI.MBB->getNumber()); @@ -828,7 +819,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, // Block is live-through without interference. if (RegOut) { DEBUG(dbgs() << ", no uses, live-through.\n"); - SE->useIntv(Start, Stop); + SE->useIntv(BI.Start, BI.Stop); } else { DEBUG(dbgs() << ", no uses, stack-out.\n"); SE->leaveIntvAtTop(*BI.MBB); @@ -837,7 +828,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, } if (!BI.LiveThrough) { DEBUG(dbgs() << ", killed in block.\n"); - SE->useIntv(Start, SE->leaveIntvAfter(BI.Kill)); + SE->useIntv(BI.Start, SE->leaveIntvAfter(BI.Kill)); continue; } if (!RegOut) { @@ -845,7 +836,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, // Spill immediately after the last use. if (BI.LastUse < BI.LastSplitPoint) { DEBUG(dbgs() << ", uses, stack-out.\n"); - SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); + SE->useIntv(BI.Start, SE->leaveIntvAfter(BI.LastUse)); continue; } // The last use is after the last split point, it is probably an @@ -853,7 +844,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point " << BI.LastSplitPoint << ", stack-out.\n"); SlotIndex SegEnd = SE->leaveIntvBefore(BI.LastSplitPoint); - SE->useIntv(Start, SegEnd); + SE->useIntv(BI.Start, SegEnd); // Run a double interval from the split to the last use. // This makes it possible to spill the complement without affecting the // indirect branch. @@ -862,7 +853,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, } // Register is live-through. DEBUG(dbgs() << ", uses, live-through.\n"); - SE->useIntv(Start, Stop); + SE->useIntv(BI.Start, BI.Stop); continue; } @@ -872,7 +863,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, if (!BI.LiveThrough && IP.first >= BI.Kill) { // The interference doesn't reach the outgoing segment. DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n'); - SE->useIntv(Start, BI.Kill); + SE->useIntv(BI.Start, BI.Kill); continue; } @@ -894,7 +885,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, DEBUG(dbgs() << ", free use at " << *UI << ".\n"); SlotIndex SegEnd = SE->leaveIntvAfter(Use); assert(SegEnd <= IP.first && "Couldn't avoid interference"); - SE->useIntv(Start, SegEnd); + SE->useIntv(BI.Start, SegEnd); continue; } |