summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SplitKit.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Delete dead code.Jakob Stoklund Olesen2011-03-011-59/+0
| | | | llvm-svn: 126801
* Move the value map from LiveIntervalMap to SplitEditor.Jakob Stoklund Olesen2011-03-011-58/+61
| | | | | | | | | | | The value map is currently not used, all values are 'complex mapped' and LiveIntervalMap::mapValue is used to dig them out. This is the first step in a series changes leading to the removal of LiveIntervalMap. Its data structures can be shared among all the live intervals created by a split, so it is wasteful to create a copy for each. llvm-svn: 126800
* Delete dead code.Jakob Stoklund Olesen2011-03-011-69/+0
| | | | | | | Local live range splitting is better driven by interference. This code was just guessing. llvm-svn: 126799
* It is safe to ignore LastSplitPoint when the variable is not live out.Jakob Stoklund Olesen2011-02-231-2/+2
| | | | | | No code will be inserted after the split point anyway. llvm-svn: 126319
* Add SplitKit::isOriginalEndpoint and use it to force live range splitting to ↵Jakob Stoklund Olesen2011-02-211-0/+14
| | | | | | | | | | | | | | terminate. An original endpoint is an instruction that killed or defined the original live range before any live ranges were split. When splitting global live ranges, avoid creating local live ranges without any original endpoints. We may still create global live ranges without original endpoints, but such a range won't be split again, and live range splitting still terminates. llvm-svn: 126151
* Give SplitAnalysis a VRM member to access VirtRegMap::getOriginal().Jakob Stoklund Olesen2011-02-191-3/+4
| | | | llvm-svn: 126005
* Missed member rename for naming convention.Jakob Stoklund Olesen2011-02-191-7/+7
| | | | llvm-svn: 126003
* Delete unused code for analyzing and splitting around loops.Jakob Stoklund Olesen2011-02-091-315/+2
| | | | | | | Loop splitting is better handled by the more generic global region splitting based on the edge bundle graph. llvm-svn: 125243
* Use the LiveBLocks array for SplitEditor::splitSingleBlocks() as well.Jakob Stoklund Olesen2011-02-091-44/+43
| | | | | | | This fixes a bug where splitSingleBlocks() could split a live range after a terminator instruction. llvm-svn: 125237
* Move calcLiveBlockInfo() and the BlockInfo struct into SplitAnalysis.Jakob Stoklund Olesen2011-02-091-0/+86
| | | | | | No functional changes intended. llvm-svn: 125231
* Ignore <undef> uses when analyzing and rewriting.Jakob Stoklund Olesen2011-02-091-2/+14
| | | | llvm-svn: 125226
* Add SplitEditor::overlapIntv() to create small ranges where both registers ↵Jakob Stoklund Olesen2011-02-081-0/+16
| | | | | | | | | | | | | | | | | | | | | | are live. If a live range is used by a terminator instruction, and that live range needs to leave the block on the stack or in a different register, it can be necessary to have both sides of the split live at the terminator instruction. Example: %vreg2 = COPY %vreg1 JMP %vreg1 Becomes after spilling %vreg2: SPILL %vreg1 JMP %vreg1 The spill doesn't kill the register as is normally the case. llvm-svn: 125102
* Add assertion.Jakob Stoklund Olesen2011-02-081-3/+4
| | | | llvm-svn: 125101
* Add LiveIntervals::getLastSplitPoint().Jakob Stoklund Olesen2011-02-041-1/+1
| | | | | | | | A live range cannot be split everywhere in a basic block. A split must go before the first terminator, and if the variable is live into a landing pad, the split must happen before the call that can throw. llvm-svn: 124894
* Skip unused values.Jakob Stoklund Olesen2011-02-041-1/+3
| | | | llvm-svn: 124842
* Add debug output and asserts to the phi-connecting code.Jakob Stoklund Olesen2011-02-031-2/+13
| | | | llvm-svn: 124813
* Fix coloring bug when mapping values in the middle of a live-through block.Jakob Stoklund Olesen2011-02-031-7/+7
| | | | | | | | | | If the found value is not live-through the block, we should only add liveness up to the requested slot index. When the value is live-through, the whole block should be colored. Bug found by SSA verification in the machine code verifier. llvm-svn: 124812
* Return live range end points from SplitEditor::enter*/leave*.Jakob Stoklund Olesen2011-02-031-41/+26
| | | | | | | These end points come from the inserted copies, and can be passed directly to useIntv. This simplifies the coloring code. llvm-svn: 124799
* Reapply this.Eric Christopher2011-02-031-185/+141
| | | | llvm-svn: 124779
* Temporarily revert 124765 in an attempt to find the cycle breaking bootstrap.Eric Christopher2011-02-031-141/+185
| | | | llvm-svn: 124778
* Defer SplitKit value mapping until all defs are available.Jakob Stoklund Olesen2011-02-031-185/+141
| | | | | | | | | | | | | | | | | | | The greedy register allocator revealed some problems with the value mapping in SplitKit. We would sometimes start mapping values before all defs were known, and that could change a value from a simple 1-1 mapping to a multi-def mapping that requires ssa update. The new approach collects all defs and register assignments first without filling in any live intervals. Only when finish() is called, do we compute liveness and mapped values. At this time we know with certainty which values map to multiple values in a split range. This also has the advantage that we can compute live ranges based on the remaining uses after rematerializing at split points. The current implementation has many opportunities for compile time optimization. llvm-svn: 124765
* Rename member variables to follow the rest of LLVM.Jakob Stoklund Olesen2011-01-261-219/+219
| | | | | | No functional change. llvm-svn: 124257
* Add LiveIntervalMap::dumpCache() to print out the cache used by the ssa ↵Jakob Stoklund Olesen2011-01-201-0/+21
| | | | | | update algorithm. llvm-svn: 123925
* Implement RAGreedy::splitAroundRegion and remove loop splitting.Jakob Stoklund Olesen2011-01-191-3/+3
| | | | | | | | | | | | | | Region splitting includes loop splitting as a subset, and it is more generic. The splitting heuristics for variables that are live in more than one block are now: 1. Try to create a region that covers multiple basic blocks. 2. Try to create a new live range for each block with multiple uses. 3. Spill. Steps 2 and 3 are similar to what the standard spiller is doing. llvm-svn: 123853
* Add RAGreedy methods for splitting live ranges around regions.Jakob Stoklund Olesen2011-01-181-0/+3
| | | | | | | | | | Analyze the live range's behavior entering and leaving basic blocks. Compute an interference pattern for each allocation candidate, and use SpillPlacement to find an optimal region where that register can be live. This code is still not enabled. llvm-svn: 123774
* Turn the EdgeBundles class into a stand-alone machine CFG analysis pass.Jakob Stoklund Olesen2011-01-041-51/+0
| | | | | | | | | | The analysis will be needed by both the greedy register allocator and the X86FloatingPoint pass. It only needs to be computed once when the CFG doesn't change. This pass is very fast, usually showing up as 0.0% wall time. llvm-svn: 122832
* Include a shadow of the original CFG edges in the edge bundle graph.Jakob Stoklund Olesen2010-12-221-0/+4
| | | | llvm-svn: 122444
* Add EdgeBundles to SplitKit.Jakob Stoklund Olesen2010-12-211-0/+47
| | | | | | | | | Edge bundles is an annotation on the CFG that turns it into a bipartite directed graph where each basic block is connected to an outgoing and an ingoing bundle. These bundles are useful for identifying regions of the CFG for live range splitting. llvm-svn: 122301
* Check that the register is live-in to the loop header before inserting copies inJakob Stoklund Olesen2010-12-181-5/+7
| | | | | | | | | the loop predecessors. The register can be live-out from a predecessor without being live-in to the loop header if there is a critical edge from the predecessor. llvm-svn: 122123
* Fix build.Jakob Stoklund Olesen2010-12-151-1/+1
| | | | llvm-svn: 121872
* Detect and enumerate bypass loops.Jakob Stoklund Olesen2010-12-151-0/+30
| | | | | | | | Bypass loops have the current live range live through, but contain no uses or defs. Splitting around a bypass loop can free registers for other uses inside the loop by spilling the split range. llvm-svn: 121871
* Separate SplitAnalysis::getSplitLoops().Jakob Stoklund Olesen2010-12-151-7/+10
| | | | | | | This method returns the set of loops with uses that are candidates for splitting. llvm-svn: 121870
* No need to add liveness that's already there.Jakob Stoklund Olesen2010-11-101-4/+1
| | | | llvm-svn: 118742
* Basic rematerialization during splitting.Jakob Stoklund Olesen2010-11-101-30/+56
| | | | | | | | | | | Whenever splitting wants to insert a copy, it checks if the value can be rematerialized cheaply instead. Missing features: - Delete instructions when all uses have been rematerialized. - Truncate live ranges to the remaining uses after rematerialization. llvm-svn: 118702
* Tag debug output as regallocJakob Stoklund Olesen2010-11-031-1/+1
| | | | llvm-svn: 118193
* When inserting copies during splitting, always use the parent register as theJakob Stoklund Olesen2010-11-011-13/+10
| | | | | | | | | | | | source, and let rewrite() clean it up. This way, kill flags on the inserted copies are fixed as well during rewrite(). We can't just assume that all the copies we insert are going to be kills since critical edges into loop headers sometimes require both source and dest to be live out of a block. llvm-svn: 117980
* Update kill flags while rewriting instructions after splitting.Jakob Stoklund Olesen2010-11-011-0/+3
| | | | llvm-svn: 117959
* Make sure copies are inserted after any exception handling labels at the top ofJakob Stoklund Olesen2010-10-301-1/+1
| | | | | | a basic block. llvm-svn: 117764
* Don't transfer unused values to the new intervals formed by splitting.Jakob Stoklund Olesen2010-10-291-0/+3
| | | | llvm-svn: 117673
* Silence Release build warnings.Benjamin Kramer2010-10-291-4/+3
| | | | llvm-svn: 117671
* Never propagate the idom value out of a block that defines its own value.Jakob Stoklund Olesen2010-10-291-3/+7
| | | | llvm-svn: 117669
* Replace SplitKit SSA update with an iterative algorithm very similar to the oneJakob Stoklund Olesen2010-10-281-87/+158
| | | | | | | | | | | | | | | | in SSAUpdaterImpl.h Verifying live intervals revealed that the old method was completely wrong, and we need an iterative approach to calculating PHI placemant. Fortunately, we have MachineDominators available, so we don't have to compute that over and over like SSAUpdaterImpl.h must. Live-out values are cached between calls to mapValue() and computed in a greedy way, so most calls will be working with very small block sets. Thanks to Bob for explaining how this should work. llvm-svn: 117599
* Make MachineDominators available for SplitEditor. We are going to need it forJakob Stoklund Olesen2010-10-281-3/+7
| | | | | | | | | proper SSA updating. This doesn't cause MachineDominators to be recomputed since we are already requiring MachineLoopInfo which uses dominators as well. llvm-svn: 117598
* Handle critical loop predecessors by making both inside and outside registersJakob Stoklund Olesen2010-10-271-1/+14
| | | | | | | | | live out. This doesn't prevent us from inserting a loop preheader later on, if that is better. llvm-svn: 117424
* Compute critical loop predecessors in the same way as critical loop exits.Jakob Stoklund Olesen2010-10-271-1/+33
| | | | | | | | Critical edges going into a loop are not as bad as critical exits. We can handle them by splitting the critical edge, or by having both inside and outside registers live out of the predecessor. llvm-svn: 117423
* After splitting, compute connected components of all new registers, not just forJakob Stoklund Olesen2010-10-261-17/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | the remainder register. Example: bb0: x = 1 bb1: use(x) ... x = 2 jump bb1 When x is isolated in bb1, the inner part breaks into two components, x1 and x2: bb0: x0 = 1 bb1: x1 = x0 use(x1) ... x2 = 2 x0 = x2 jump bb1 llvm-svn: 117408
* Call RenumberValues for all new registers created during splitting. This isJakob Stoklund Olesen2010-10-261-1/+2
| | | | | | necessary to get correct hasPHIKill flags. llvm-svn: 117406
* Preserve PHIDef bits in cloned values during splitting.Jakob Stoklund Olesen2010-10-261-0/+4
| | | | llvm-svn: 117405
* Be more strict about detecting multi-use blocks for isolation.Jakob Stoklund Olesen2010-10-221-28/+29
| | | | | | | | | | | When a block has exactly two uses and the register is both live-in and live-out, don't isolate the block. We would be inserting two copies, so we haven't really made any progress. If the live-in and live-out values separate into disconnected components after splitting, we would be making progress. We can't detect that for now. llvm-svn: 117169
* Be more strict when detecting critical edges before loop splitting.Jakob Stoklund Olesen2010-10-221-19/+15
| | | | | | | | An exit block with a critical edge must only have predecessors in the loop, or just before the loop. This guarantees that the inserted copies in the loop predecessors dominate the exit block. llvm-svn: 117144
OpenPOWER on IntegriCloud