aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/SplitKit.cpp
AgeCommit message (Collapse)Author
2011-06-30Reapply r134047 now that the world is ready for it.Jakob Stoklund Olesen
This patch will sometimes choose live range split points next to interference instead of always splitting next to a register point. That means spill code can now appear almost anywhere, and it was necessary to fix code that didn't expect that. The difficult places were: - Between a CALL returning a value on the x87 stack and the corresponding FpPOP_RETVAL (was FpGET_ST0). Probably also near x87 inline assembly, but that didn't actually show up in testing. - Between a CALL popping arguments off the stack and the corresponding ADJCALLSTACKUP. Both are fixed now. The only place spill code can't appear is after terminators, see SplitAnalysis::getLastSplitPoint. Original commit message: Rewrite RAGreedy::splitAroundRegion, now with cool ASCII art. This function has to deal with a lot of special cases, and the old version got it wrong sometimes. In particular, it would sometimes leave multiple uses in the stack interval in a single block. That causes bad code with multiple reloads in the same basic block. The new version handles block entry and exit in a single pass. It first eliminates all the easy cases, and then goes on to create a local interval for the blocks with difficult interference. Previously, we would only create the local interval for completely isolated blocks. It can happen that the stack interval becomes completely empty because we could allocate a register in all edge bundles, and the new local intervals deal with the interference. The empty stack interval is harmless, but we need to remove a SplitKit assertion that checks for empty intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134125 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-29Revert r134047 while investigating a llvm-gcc-i386-linux-selfhostJakob Stoklund Olesen
miscompile. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134053 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-29Rewrite RAGreedy::splitAroundRegion, now with cool ASCII art.Jakob Stoklund Olesen
This function has to deal with a lot of special cases, and the old version got it wrong sometimes. In particular, it would sometimes leave multiple uses in the stack interval in a single block. That causes bad code with multiple reloads in the same basic block. The new version handles block entry and exit in a single pass. It first eliminates all the easy cases, and then goes on to create a local interval for the blocks with difficult interference. Previously, we would only create the local interval for completely isolated blocks. It can happen that the stack interval becomes completely empty because we could allocate a register in all edge bundles, and the new local intervals deal with the interference. The empty stack interval is harmless, but we need to remove a SplitKit assertion that checks for empty intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134047 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-28Fix a bad iterator dereference that Evan uncovered.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133978 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-26There is only one register coalescer. Merge it into the base class andRafael Espindola
remove the analysis group. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133899 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-30Reapply r132245 with a fix for the bug that broke the darwin9/i386 build.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132309 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-29Revert r132245, "Create two BlockInfo entries when a live range is ↵Jakob Stoklund Olesen
discontinuous through a block." This commit seems to have broken a darwin 9 tester. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132299 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-28Create two BlockInfo entries when a live range is discontinuous through a block.Jakob Stoklund Olesen
Delete the Kill and Def markers in BlockInfo. They are no longer necessary when BlockInfo describes a continuous live range. This only affects the relatively rare kind of basic block where a live range looks like this: |---x o---| Now live range splitting can pretend that it is looking at two blocks: |---x o---| This allows the code to be simplified a bit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132245 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-28Add SplitAnalysis::getNumLiveBlocks().Jakob Stoklund Olesen
It is important that this function returns the same number of live blocks as countLiveBlocks(CurLI) because live range splitting uses the number of live blocks to ensure it is making progress. This is in preparation of supporting duplicate UseBlock entries for basic blocks that have a virtual register live-in and live-out, but not live-though. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132244 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-10Fix PR9883. Make sure all caches are invalidated when a live range is repaired.Jakob Stoklund Olesen
The previous invalidation missed the alias interference caches. Also add a stats counter for the number of repaired ranges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131133 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-05Add some statistics to the splitting and spilling frameworks.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130931 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-03Gracefully handle invalid live ranges. Fix PR9831.Jakob Stoklund Olesen
Register coalescing can sometimes create live ranges that end in the middle of a basic block without any killing instruction. When SplitKit detects this, it will repair the live range by shrinking it to its uses. Live range splitting also needs to know about this. When the range shrinks so much that it becomes allocatable, live range splitting fails because it can't find a good split point. It is paranoid about making progress, so an allocatable range is considered an error. The coalescer should really not be creating these bad live ranges. They appear when coalescing dead copies. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130787 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-02Minimize the slot indexes spanned by register ranges created when splitting.Jakob Stoklund Olesen
When an interfering live range ends at a dead slot index between two instructions, make sure that the inserted copy instruction gets a slot index after the dead ones. This makes it possible to avoid the interference. Ideally, there shouldn't be interference ending at a deleted instruction, but physical register coalescing can sometimes do that to sub-registers. This fixes PR9823. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130687 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-26Add a safe-guard against repeated splitting for some rare cases.Jakob Stoklund Olesen
The number of blocks covered by a live range must be strictly decreasing when splitting, otherwise we can't allow repeated splitting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130249 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-21Don't recycle loop variables.Matt Beaumont-Gay
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129928 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-21Allow allocatable ranges from global live range splitting to be split again.Jakob Stoklund Olesen
These intervals are allocatable immediately after splitting, but they may be evicted because of later splitting. This is rare, but when it happens they should be split again. The remainder intervals that cannot be allocated after splitting still move directly to spilling. SplitEditor::finish can optionally provide a mapping from new live intervals back to the original interval indexes returned by openIntv(). Each original interval index can map to multiple new intervals after connected components have been separated. Dead code elimination may also add existing intervals to the list. The reverse mapping allows the SplitEditor client to treat the new intervals differently depending on the split region they came from. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129925 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-16Unbreak the MSVC 2010 build.Francois Pichet
For further information on this particular issue see: http://connect.microsoft.com/VisualStudio/feedback/details/520043/error-converting-from-null-to-a-pointer-type-in-std-pair git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129642 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-15Teach the SplitKit blitter to handle multiply defined values as well.Jakob Stoklund Olesen
The transferValues() function can now handle both singly and multiply defined values, as long as the resulting live range is known. Only rematerialized values have their live range recomputed by extendRange(). The updateSSA() function can now insert PHI values in bulk across multiple values in multiple target registers in one pass. The list of blocks received from transferValues() is in layout order which seems to work well for the iterative algorithm. Blocks from extendRange() are still in reverse BFS order, but this function is used so rarely now that it doesn't matter. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129580 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-13Stop using dead function.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129442 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-12Create new intervals for isolated blocks during region splitting.Jakob Stoklund Olesen
This merges the behavior of splitSingleBlocks into splitAroundRegion, so the RS_Region and RS_Block register stages can be coalesced. That means the leftover intervals after region splitting go directly to spilling instead of a second pass of per-block splitting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129379 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-12Add SplitKit API to query and select the current interval being worked on.Jakob Stoklund Olesen
This makes it possible to target multiple registers in one pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129374 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-09Build the Hopfield network incrementally when splitting global live ranges.Jakob Stoklund Olesen
It is common for large live ranges to have few basic blocks with register uses and many live-through blocks without any uses. This approach grows the Hopfield network incrementally around the use blocks, completely avoiding checking interference for some through blocks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129188 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-06Analyze blocks with uses separately from live-through blocks without uses.Jakob Stoklund Olesen
About 90% of the relevant blocks are live-through without uses, and the only information required about them is their number. This saves memory and enables later optimizations that need to look at only the use-blocks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128985 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-05Sign errorJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128963 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-05Don't crash when a value is defined after the last split point.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128962 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-05Use std::unique instead of a SmallPtrSet to ensure unique instructions in ↵Jakob Stoklund Olesen
UseSlots. This allows us to always keep the smaller slot for an instruction which is what we want when a register has early clobber defines. Drop the UsingInstrs set and the UsingBlocks map. They are no longer needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128886 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-05Stop precomputing last split points, query the SplitAnalysis cache on demand.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128875 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-05Cache the fairly expensive last split point computation and provide a fastJakob Stoklund Olesen
inlined path for the common case. Most basic blocks don't contain a call that may throw, so the last split point os simply the first terminator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128874 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-04Stop caching basic block index ranges now that SlotIndexes can keep up.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128821 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-29Recompute register class and hint for registers created during spilling.Jakob Stoklund Olesen
The spill weight is not recomputed for an unspillable register - it stays infinite. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128490 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-29Handle the special case when all uses follow the last split point.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128450 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-27Amend debug output.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128398 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-20Process all dead defs after rematerializing during splitting.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127973 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-18Be more accurate about the slot index reading a register when dealing with defsJakob Stoklund Olesen
and early clobbers. Assert when trying to find an undefined value. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127856 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-17Dead code elimination may separate the live interval into multiple connected ↵Jakob Stoklund Olesen
components. I have convinced myself that it can only happen when a phi value dies. When it happens, allocate new virtual registers for the components. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127827 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-17Rewrite instructions as part of ConnectedVNInfoEqClasses::Distribute.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127779 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-15Preserve both isPHIDef and isDefByCopy bits when copying parent values.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127697 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-08Delete dead code after rematerializing.Jakob Stoklund Olesen
LiveRangeEdit::eliminateDeadDefs() will eventually be used by coalescing, splitting, and spilling for dead code elimination. It can delete chains of dead instructions as long as there are no dependency loops. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127287 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-05Work around a coalescer bug.Jakob Stoklund Olesen
The coalescer can in very rare cases leave too large live intervals around after rematerializing cheap-as-a-move instructions. Linear scan doesn't really care, but live range splitting gets very confused when a live range is killed by a ghost instruction. I will fix this properly in the coalescer after 2.9 branches. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127096 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-04Tweak debug output. No functional changes.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127006 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-04Use an IndexedMap instead of a DenseMap for the live-out cache.Jakob Stoklund Olesen
This speeds up updateSSA() so it only accounts for 5% of the live range splitting time. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126972 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-03Cache basic block bounds instead of asking SlotIndexes::getMBBRange all the ↵Jakob Stoklund Olesen
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
2011-03-03Change the SplitEditor interface to a single instance can be shared for ↵Jakob Stoklund Olesen
multiple splits. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126912 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-03Only run the updateSSA loop when we have actually seen multiple values.Jakob Stoklund Olesen
When only a single value has been seen, new PHIDefs are never needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126911 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-02Turn the Edit member into a pointer so it can change dynamically.Jakob Stoklund Olesen
No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126898 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-02Transfer simply defined values directly without recomputing liveness and SSA.Jakob Stoklund Olesen
Values that map to a single new value in a new interval after splitting don't need new PHIDefs, and if the parent value was never rematerialized the live range will be the same. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126894 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-02Extract a method. No functional change.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126893 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-02Move extendRange() into SplitEditor and delete the LiveRangeMap class.Jakob Stoklund Olesen
Extract the updateSSA() method from the too long extendRange(). LiveOutCache can be shared among all the new intervals since there is at most one of the new ranges live out from each basic block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126818 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-02Rename mapValue to extendRange because that is its function now.Jakob Stoklund Olesen
Simplify the signature - The return value and ParentVNI are no longer needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126809 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-02Move LiveIntervalMap::extendTo into LiveInterval itself.Jakob Stoklund Olesen
This method could probably be used by LiveIntervalAnalysis::shrinkToUses, and now it can use extendIntervalEndTo() which coalesces ranges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126803 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-17 18:53:45 +0000