summaryrefslogtreecommitdiff
path: root/lib/CodeGen/SplitKit.h
Commit message (Collapse)AuthorAge
* Clean up language and grammar.Eric Christopher2014-05-20
| | | | | | | Based on a patch by jfcaron3@gmail.com! PR19806 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@209216 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-16
| | | | | | instead of comparing to nullptr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206356 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "Give internal classes hidden visibility."Benjamin Kramer2013-09-11
| | | | | | | It works with clang, but GCC has different rules so we can't make all of those hidden. This reverts commit r190534. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190536 91177308-0d34-0410-b5e6-96231b3b80d8
* Give internal classes hidden visibility.Benjamin Kramer2013-09-11
| | | | | | Worth 100k on a linux/x86_64 Release+Asserts clang. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190534 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.Benjamin Kramer2013-06-17
| | | | | | | | | | | | | | | | | | The main advantages here are way better heuristics, taking into account not just loop depth but also __builtin_expect and other static heuristics and will eventually learn how to use profile info. Most of the work in this patch is pushing the MachineBlockFrequencyInfo analysis into the right places. This is good for a 5% speedup on zlib's deflate (x86_64), there were some very unfortunate spilling decisions in its hottest loop in longest_match(). Other benchmarks I tried were mostly neutral. This changes register allocation in subtle ways, update the tests for it. 2012-02-20-MachineCPBug.ll was deleted as it's very fragile and the instruction it looked for was gone already (but the FileCheck pattern picked up unrelated stuff). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@184105 91177308-0d34-0410-b5e6-96231b3b80d8
* Make SplitAnalysis::UseSlots private.Jakob Stoklund Olesen2012-01-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148031 91177308-0d34-0410-b5e6-96231b3b80d8
* Exclusively use SplitAnalysis::getLastSplitPoint().Jakob Stoklund Olesen2012-01-11
| | | | | | | | | Delete the alternative implementation in LiveIntervalAnalysis. These functions computed the same thing, but SplitAnalysis caches the result. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147911 91177308-0d34-0410-b5e6-96231b3b80d8
* Hoist back-copies to the least busy dominator.Jakob Stoklund Olesen2011-09-14
| | | | | | | | | | | | | | | | When a back-copy is hoisted to the nearest common dominator, keep looking up the dominator tree for a less loopy dominator, and place the back-copy there instead. Don't do this when a single existing back-copy dominates all the others. Assume the client knows what he is doing, and keep the dominating back-copy. This prevents us from hoisting back-copies into loops in most cases. If a value is defined in a loop with multiple exits, we may still hoist back-copies into that loop. That is the speed/size tradeoff. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139698 91177308-0d34-0410-b5e6-96231b3b80d8
* Distinguish complex mapped values from forced recomputation.Jakob Stoklund Olesen2011-09-13
| | | | | | | | | | | | | | | | | | When a ParentVNI maps to multiple defs in a new interval, its live range may still be derived directly from RegAssign by transferValues(). On the other hand, when instructions have been rematerialized or hoisted, it may be necessary to completely recompute live ranges using LiveRangeCalc::extend() to all uses. Use a bit in the value map to indicate that a live range must be recomputed. Rename markComplexMapped() to forceRecompute(). This fixes some live range verification errors when -split-spill-mode=size hoists back-copies by recomputing source ranges when RegAssign kills can't be moved. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139660 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement -split-spill-mode=size.Jakob Stoklund Olesen2011-09-13
| | | | | | | | | | Whenever the complement interval is defined by multiple copies of the same value, hoist those back-copies to the nearest common dominator. This ensures that at most one copy is inserted per value in the complement inteval, and no phi-defs are needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139651 91177308-0d34-0410-b5e6-96231b3b80d8
* Add SplitEditor::markOverlappedComplement().Jakob Stoklund Olesen2011-09-13
| | | | | | | | This function is used to flag values where the complement interval may overlap other intervals. Call it from overlapIntv, and use the flag to fully recompute those live ranges in transferValues(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139612 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate the extendRange() wrapper.Jakob Stoklund Olesen2011-09-13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139608 91177308-0d34-0410-b5e6-96231b3b80d8
* Use a separate LiveRangeCalc for the complement in spill modes.Jakob Stoklund Olesen2011-09-13
| | | | | | | | | | The complement interval may overlap the other intervals created, so use a separate LiveRangeCalc instance to compute its live range. A LiveRangeCalc instance can only be shared among non-overlapping intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139603 91177308-0d34-0410-b5e6-96231b3b80d8
* Extract live range calculations from SplitKit.Jakob Stoklund Olesen2011-09-13
| | | | | | | | SplitKit will soon need two copies of these data structures, and the algorithms will also be useful when LiveIntervalAnalysis becomes independent of LiveVariables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139572 91177308-0d34-0410-b5e6-96231b3b80d8
* Add an interface for SplitKit complement spill modes.Jakob Stoklund Olesen2011-09-12
| | | | | | | | | | | | | | | | | | | | | | | | | SplitKit always computes a complement live range to cover the places where the original live range was live, but no explicit region has been allocated. Currently, the complement live range is created to be as small as possible - it never overlaps any of the regions. This minimizes register pressure, but if the complement is going to be spilled anyway, that is not very important. The spiller will eliminate redundant spills, and hoist others by making the spill slot live range overlap some of the regions created by splitting. Stack slots are cheap. This patch adds the interface to enable spill modes in SplitKit. In spill mode, SplitKit will assume that the complement is going to spill, so it will allow it to overlap regions in order to avoid back-copies. By doing some of the spiller's work early, the complement live range becomes simpler. In some cases, it can become much simpler because no extra PHI-defs are required. This will speed up both splitting and spilling. This is only the interface to enable spill modes, no implementation yet. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139500 91177308-0d34-0410-b5e6-96231b3b80d8
* Update comments to reflect some (not so) recent changes.Jakob Stoklund Olesen2011-09-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139498 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete getMultiUseBlocks and splitSingleBlocks.Jakob Stoklund Olesen2011-08-05
| | | | | | | These functions are no longer used, and they are easily replaced with a loop calling shouldSplitSingleBlock and splitSingleBlock. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136993 91177308-0d34-0410-b5e6-96231b3b80d8
* Split around single instructions to enable register class inflation.Jakob Stoklund Olesen2011-08-05
| | | | | | | | | | | | | Normally, we don't create a live range for a single instruction in a basic block, the spiller does that anyway. However, when splitting a live range that belongs to a proper register sub-class, inserting these extra COPY instructions completely remove the constraints from the remainder interval, and it may be allocated from the larger super-class. The spiller will mop up these small live ranges if we end up spilling anyway. It calls them snippets. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136989 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename {First,Last}Use to {First,Last}Instr.Jakob Stoklund Olesen2011-08-02
| | | | | | | With a 'FirstDef' field right there, it is very confusing that FirstUse refers to an instruction that may be a def. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136739 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a BlockInfo::FirstDef field.Jakob Stoklund Olesen2011-08-02
| | | | | | | | | | | This is either an invalid SlotIndex, or valno->def for the first value defined inside the block. PHI values are not counted as defined inside the block. The FirstDef field will be used when estimating the cost of spilling around a block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136736 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete BlockInfo::LiveThrough. It wasn't used any more.Jakob Stoklund Olesen2011-08-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136735 91177308-0d34-0410-b5e6-96231b3b80d8
* Extract parts of RAGreedy::splitAroundRegion as SplitKit methods.Jakob Stoklund Olesen2011-07-15
| | | | | | | | | | | This gets rid of some of the gory splitting details in RAGreedy and makes them available to future SplitKit clients. Slightly generalize the functionality to support multi-way splitting. Specifically, SplitEditor::splitLiveThroughBlock() supports switching between different register intervals in a block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135307 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply r134047 now that the world is ready for it.Jakob Stoklund Olesen2011-06-30
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Revert r134047 while investigating a llvm-gcc-i386-linux-selfhostJakob Stoklund Olesen2011-06-29
| | | | | | miscompile. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134053 91177308-0d34-0410-b5e6-96231b3b80d8
* Rewrite RAGreedy::splitAroundRegion, now with cool ASCII art.Jakob Stoklund Olesen2011-06-29
| | | | | | | | | | | | | | | | | | | | 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
* Reapply r132245 with a fix for the bug that broke the darwin9/i386 build.Jakob Stoklund Olesen2011-05-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132309 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert r132245, "Create two BlockInfo entries when a live range is ↵Jakob Stoklund Olesen2011-05-29
| | | | | | | | 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
* Create two BlockInfo entries when a live range is discontinuous through a block.Jakob Stoklund Olesen2011-05-28
| | | | | | | | | | | | | | | | | | | 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
* Add SplitAnalysis::getNumLiveBlocks().Jakob Stoklund Olesen2011-05-28
| | | | | | | | | | | 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
* Gracefully handle invalid live ranges. Fix PR9831.Jakob Stoklund Olesen2011-05-03
| | | | | | | | | | | | | | | | 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
* Add a safe-guard against repeated splitting for some rare cases.Jakob Stoklund Olesen2011-04-26
| | | | | | | 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
* Give SplitKit.h a header guard.Sebastian Redl2011-04-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130095 91177308-0d34-0410-b5e6-96231b3b80d8
* Allow allocatable ranges from global live range splitting to be split again.Jakob Stoklund Olesen2011-04-21
| | | | | | | | | | | | | | | | | | | | | 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
* Teach the SplitKit blitter to handle multiply defined values as well.Jakob Stoklund Olesen2011-04-15
| | | | | | | | | | | | | | 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
* Stop using dead function.Jakob Stoklund Olesen2011-04-13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129442 91177308-0d34-0410-b5e6-96231b3b80d8
* SparseBitVector is SLOW.Jakob Stoklund Olesen2011-04-12
| | | | | | | Use a Bitvector instead, we didn't need the smaller memory footprint anyway. This makes the greedy register allocator 10% faster. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129390 91177308-0d34-0410-b5e6-96231b3b80d8
* Create new intervals for isolated blocks during region splitting.Jakob Stoklund Olesen2011-04-12
| | | | | | | | | 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
* Add SplitKit API to query and select the current interval being worked on.Jakob Stoklund Olesen2011-04-12
| | | | | | 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
* Build the Hopfield network incrementally when splitting global live ranges.Jakob Stoklund Olesen2011-04-09
| | | | | | | | | 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
* Analyze blocks with uses separately from live-through blocks without uses.Jakob Stoklund Olesen2011-04-06
| | | | | | | | 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
* Use std::unique instead of a SmallPtrSet to ensure unique instructions in ↵Jakob Stoklund Olesen2011-04-05
| | | | | | | | | | | 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
* Stop precomputing last split points, query the SplitAnalysis cache on demand.Jakob Stoklund Olesen2011-04-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128875 91177308-0d34-0410-b5e6-96231b3b80d8
* Cache the fairly expensive last split point computation and provide a fastJakob Stoklund Olesen2011-04-05
| | | | | | | | | 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
* Stop caching basic block index ranges now that SlotIndexes can keep up.Jakob Stoklund Olesen2011-04-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128821 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete leftover data members.Jakob Stoklund Olesen2011-04-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128820 91177308-0d34-0410-b5e6-96231b3b80d8
* Rewrite instructions as part of ConnectedVNInfoEqClasses::Distribute.Jakob Stoklund Olesen2011-03-17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127779 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete dead code after rematerializing.Jakob Stoklund Olesen2011-03-08
| | | | | | | | 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
* Work around a coalescer bug.Jakob Stoklund Olesen2011-03-05
| | | | | | | | | | | | 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
* Use an IndexedMap instead of a DenseMap for the live-out cache.Jakob Stoklund Olesen2011-03-04
| | | | | | | 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
* Cache basic block bounds instead of asking SlotIndexes::getMBBRange all the ↵Jakob Stoklund Olesen2011-03-03
| | | | | | | | | 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
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-29 23:25:56 +0000