aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/SplitKit.cpp
AgeCommit message (Collapse)Author
2011-02-08Add assertion.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125101 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-04Add LiveIntervals::getLastSplitPoint().Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124894 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-04Skip unused values.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124842 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Add debug output and asserts to the phi-connecting code.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124813 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Fix coloring bug when mapping values in the middle of a live-through block.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124812 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Return live range end points from SplitEditor::enter*/leave*.Jakob Stoklund Olesen
These end points come from the inserted copies, and can be passed directly to useIntv. This simplifies the coloring code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124799 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Reapply this.Eric Christopher
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124779 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Temporarily revert 124765 in an attempt to find the cycle breaking bootstrap.Eric Christopher
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124778 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Defer SplitKit value mapping until all defs are available.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124765 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-26Rename member variables to follow the rest of LLVM.Jakob Stoklund Olesen
No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124257 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-20Add LiveIntervalMap::dumpCache() to print out the cache used by the ssa ↵Jakob Stoklund Olesen
update algorithm. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123925 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-19Implement RAGreedy::splitAroundRegion and remove loop splitting.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123853 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-18Add RAGreedy methods for splitting live ranges around regions.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123774 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-04Turn the EdgeBundles class into a stand-alone machine CFG analysis pass.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122832 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-22Include a shadow of the original CFG edges in the edge bundle graph.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122444 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-21Add EdgeBundles to SplitKit.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122301 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-18Check that the register is live-in to the loop header before inserting copies inJakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122123 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-15Fix build.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121872 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-15Detect and enumerate bypass loops.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121871 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-15Separate SplitAnalysis::getSplitLoops().Jakob Stoklund Olesen
This method returns the set of loops with uses that are candidates for splitting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121870 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-10No need to add liveness that's already there.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118742 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-10Basic rematerialization during splitting.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118702 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-03Tag debug output as regallocJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118193 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-01When inserting copies during splitting, always use the parent register as theJakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117980 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-01Update kill flags while rewriting instructions after splitting.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117959 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-30Make sure copies are inserted after any exception handling labels at the top ofJakob Stoklund Olesen
a basic block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117764 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-29Don't transfer unused values to the new intervals formed by splitting.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117673 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-29Silence Release build warnings.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117671 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-29Never propagate the idom value out of a block that defines its own value.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117669 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-28Replace SplitKit SSA update with an iterative algorithm very similar to the oneJakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117599 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-28Make MachineDominators available for SplitEditor. We are going to need it forJakob Stoklund Olesen
proper SSA updating. This doesn't cause MachineDominators to be recomputed since we are already requiring MachineLoopInfo which uses dominators as well. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117598 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-27Handle critical loop predecessors by making both inside and outside registersJakob Stoklund Olesen
live out. This doesn't prevent us from inserting a loop preheader later on, if that is better. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117424 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-27Compute critical loop predecessors in the same way as critical loop exits.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117423 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-26After splitting, compute connected components of all new registers, not just forJakob Stoklund Olesen
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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117408 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-26Call RenumberValues for all new registers created during splitting. This isJakob Stoklund Olesen
necessary to get correct hasPHIKill flags. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117406 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-26Preserve PHIDef bits in cloned values during splitting.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117405 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-22Be more strict about detecting multi-use blocks for isolation.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117169 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-22Be more strict when detecting critical edges before loop splitting.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117144 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-22Add print methodsJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117143 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-21Don't include the destination interval in the union when computingJakob Stoklund Olesen
Parent - union(Y, ...). Doh. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117042 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-15Eliminate curli from SplitEditor. Use the LiveRangeEdit reference instead.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116547 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-15Move stack slot assignments into LiveRangeEdit.Jakob Stoklund Olesen
All registers created during splitting or spilling are assigned to the same stack slot as the parent register. When splitting or rematting, we may not spill at all. In that case the stack slot is still assigned, but it will be dead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116546 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-14Create a new LiveRangeEdit class to keep track of the new registers created whenJakob Stoklund Olesen
splitting or spillling, and to help with rematerialization. Use LiveRangeEdit in InlineSpiller and SplitKit. This will eventually make it possible to share remat code between InlineSpiller and SplitKit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116543 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-14Only split around a loop if the live range has uses outside the loop periphery.Jakob Stoklund Olesen
Before we would also split around a loop if any peripheral block had multiple uses. This could cause repeated splitting when splitting a different live range would insert uses into the periphery. Now -spiller=inline passes the nightly test suite again. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116494 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-08Rename SplitEditor::rewrite to finish() and break it out into a couple of newJakob Stoklund Olesen
functions: computeRemainder and rewrite. When the remainder breaks up into multiple components, remember to rewrite those uses as well. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116121 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-07After splitting, the remaining LiveInterval may be fragmented into multipleJakob Stoklund Olesen
connected components. These components should be allocated different virtual registers because there is no reason for them to be allocated together. Add the ConnectedVNInfoEqClasses class to calculate the connected components, and move values to new LiveIntervals. Use it from SplitKit::rewrite by creating new virtual registers for the components. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116006 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-07Print more loop info.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115951 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-07Print out MBB number when rewriting.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115950 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-07Cache interval iterators in SplitEditor::addTruncSimpleRange so we only have toJakob Stoklund Olesen
do one find(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115929 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-07Clean up debug printing.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115928 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-30 11:12:27 +0000