summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SplitKit.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Add print methodsJakob Stoklund Olesen2010-10-221-18/+25
| | | | llvm-svn: 117143
* Don't include the destination interval in the union when computingJakob Stoklund Olesen2010-10-211-2/+4
| | | | | | Parent - union(Y, ...). Doh. llvm-svn: 117042
* Eliminate curli from SplitEditor. Use the LiveRangeEdit reference instead.Jakob Stoklund Olesen2010-10-151-15/+13
| | | | llvm-svn: 116547
* Move stack slot assignments into LiveRangeEdit.Jakob Stoklund Olesen2010-10-151-6/+0
| | | | | | | | | | 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. llvm-svn: 116546
* Create a new LiveRangeEdit class to keep track of the new registers created whenJakob Stoklund Olesen2010-10-141-32/+21
| | | | | | | | | 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. llvm-svn: 116543
* Only split around a loop if the live range has uses outside the loop periphery.Jakob Stoklund Olesen2010-10-141-14/+13
| | | | | | | | | | 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. llvm-svn: 116494
* Rename SplitEditor::rewrite to finish() and break it out into a couple of newJakob Stoklund Olesen2010-10-081-36/+45
| | | | | | | | | functions: computeRemainder and rewrite. When the remainder breaks up into multiple components, remember to rewrite those uses as well. llvm-svn: 116121
* After splitting, the remaining LiveInterval may be fragmented into multipleJakob Stoklund Olesen2010-10-071-11/+24
| | | | | | | | | | | | | 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. llvm-svn: 116006
* Print more loop info.Jakob Stoklund Olesen2010-10-071-0/+16
| | | | llvm-svn: 115951
* Print out MBB number when rewriting.Jakob Stoklund Olesen2010-10-071-1/+2
| | | | llvm-svn: 115950
* Cache interval iterators in SplitEditor::addTruncSimpleRange so we only have toJakob Stoklund Olesen2010-10-071-10/+20
| | | | | | do one find(). llvm-svn: 115929
* Clean up debug printing.Jakob Stoklund Olesen2010-10-071-15/+19
| | | | llvm-svn: 115928
* Count uses in all nested loops, not just the deepest.Jakob Stoklund Olesen2010-10-051-1/+2
| | | | llvm-svn: 115710
* Remove SplitAnalysis::removeUse. It was only used to make SplitAnalysisJakob Stoklund Olesen2010-10-051-29/+0
| | | | | | | reusable, but that is no longer relevant since a split will always replace the original. llvm-svn: 115709
* dupli always has an interval now.Jakob Stoklund Olesen2010-10-051-14/+11
| | | | llvm-svn: 115708
* We can split around loops with multiple exits now.Jakob Stoklund Olesen2010-10-051-6/+0
| | | | llvm-svn: 115696
* Update SplitEditor API to reflect the fact that the original live interval isJakob Stoklund Olesen2010-10-051-13/+9
| | | | | | | | | | never kept after splitting. Keeping the original interval made sense when the split region doesn't modify the register, and the original is spilled. We can get the same effect by detecting reloaded values when spilling around copies. llvm-svn: 115695
* Intervals are half-open.Jakob Stoklund Olesen2010-10-051-1/+1
| | | | llvm-svn: 115694
* When we find a reaching definition, make sure it is visited from all paths byJakob Stoklund Olesen2010-10-051-5/+12
| | | | | | erasing it from the visited set. That ensures we create the right phi defs. llvm-svn: 115666
* Don't use nextIndex to check for live out of instruction.Jakob Stoklund Olesen2010-10-051-12/+8
| | | | | | | | | | | Insert copy after defining instruction. Fix LiveIntervalMap::extendTo to properly handle live segments starting before the current basic block. Make sure the open live range is extended to the inserted copy's use slot. llvm-svn: 115665
* Removed VNInfo::isDefAccurate(). Def "accuracy" can be checked by testing ↵Lang Hames2010-09-251-2/+2
| | | | | | whether LiveIntervals::getInstructionFromIndex(def) returns NULL. llvm-svn: 114791
* Build the complement interval dupli after the split intervals instead ofJakob Stoklund Olesen2010-09-211-25/+118
| | | | | | | | | | | | | creating it before and subtracting split ranges. This way, the SSA update code in LiveIntervalMap can properly create and use new phi values in dupli. Now it is possible to create split regions where a value escapes along two different CFG edges, creating phi values outside the split region. This is a work in progress and probably quite broken. llvm-svn: 114492
* Use the value mapping provided by LiveIntervalMap. This simplifies the code aJakob Stoklund Olesen2010-09-161-205/+73
| | | | | | | | | | | | | | | | | great deal because we don't have to worry about maintaining SSA form. Unconditionally copy back to dupli when the register is live out of the split range, even if the live-out value was defined outside the range. Skipping the back-copy only makes sense when the live range is going to spill outside the split range, and we don't know that it will. Besides, this was a hack to avoid SSA update issues. Clear up some confusion about the end point of a half-open LiveRange. Methinks LiveRanges need to be closed so both start and end are included in the range. The low bits of a SlotIndex are symbolic, so a half-open range doesn't really make sense. This would be a pervasive change, though. llvm-svn: 114043
* Mechanically replace LiveInterval* with LiveIntervalMap for intervals beingJakob Stoklund Olesen2010-09-131-70/+72
| | | | | | edited without actually using LiveIntervalMap functionality. llvm-svn: 113816
OpenPOWER on IntegriCloud