summaryrefslogtreecommitdiff
path: root/lib/CodeGen/SplitKit.h
Commit message (Collapse)AuthorAge
...
* Transfer simply defined values directly without recomputing liveness and SSA.Jakob Stoklund Olesen2011-03-02
| | | | | | | | 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
* Extract a method. No functional change.Jakob Stoklund Olesen2011-03-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126893 91177308-0d34-0410-b5e6-96231b3b80d8
* Move extendRange() into SplitEditor and delete the LiveRangeMap class.Jakob Stoklund Olesen2011-03-02
| | | | | | | | | 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
* Rename mapValue to extendRange because that is its function now.Jakob Stoklund Olesen2011-03-02
| | | | | | 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
* Move LiveIntervalMap::extendTo into LiveInterval itself.Jakob Stoklund Olesen2011-03-02
| | | | | | | 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
* Delete dead code.Jakob Stoklund Olesen2011-03-01
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126801 91177308-0d34-0410-b5e6-96231b3b80d8
* Move the value map from LiveIntervalMap to SplitEditor.Jakob Stoklund Olesen2011-03-01
| | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126800 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete dead code.Jakob Stoklund Olesen2011-03-01
| | | | | | | Local live range splitting is better driven by interference. This code was just guessing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126799 91177308-0d34-0410-b5e6-96231b3b80d8
* Add SplitKit::isOriginalEndpoint and use it to force live range splitting to ↵Jakob Stoklund Olesen2011-02-21
| | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126151 91177308-0d34-0410-b5e6-96231b3b80d8
* Give SplitAnalysis a VRM member to access VirtRegMap::getOriginal().Jakob Stoklund Olesen2011-02-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126005 91177308-0d34-0410-b5e6-96231b3b80d8
* Missed member rename for naming convention.Jakob Stoklund Olesen2011-02-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126003 91177308-0d34-0410-b5e6-96231b3b80d8
* Split local live ranges.Jakob Stoklund Olesen2011-02-17
| | | | | | | | A local live range is live in a single basic block. If such a range fails to allocate, try to find a sub-range that would get a larger spill weight than its interference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125764 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete unused code for analyzing and splitting around loops.Jakob Stoklund Olesen2011-02-09
| | | | | | | Loop splitting is better handled by the more generic global region splitting based on the edge bundle graph. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125243 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the LiveBLocks array for SplitEditor::splitSingleBlocks() as well.Jakob Stoklund Olesen2011-02-09
| | | | | | | This fixes a bug where splitSingleBlocks() could split a live range after a terminator instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125237 91177308-0d34-0410-b5e6-96231b3b80d8
* Move calcLiveBlockInfo() and the BlockInfo struct into SplitAnalysis.Jakob Stoklund Olesen2011-02-09
| | | | | | No functional changes intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125231 91177308-0d34-0410-b5e6-96231b3b80d8
* Add SplitEditor::overlapIntv() to create small ranges where both registers ↵Jakob Stoklund Olesen2011-02-08
| | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125102 91177308-0d34-0410-b5e6-96231b3b80d8
* Return live range end points from SplitEditor::enter*/leave*.Jakob Stoklund Olesen2011-02-03
| | | | | | | 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
* Reapply this.Eric Christopher2011-02-03
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124779 91177308-0d34-0410-b5e6-96231b3b80d8
* Temporarily revert 124765 in an attempt to find the cycle breaking bootstrap.Eric Christopher2011-02-03
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124778 91177308-0d34-0410-b5e6-96231b3b80d8
* Defer SplitKit value mapping until all defs are available.Jakob Stoklund Olesen2011-02-03
| | | | | | | | | | | | | | | | | | | 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
* Rename member variables to follow the rest of LLVM.Jakob Stoklund Olesen2011-01-26
| | | | | | No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124257 91177308-0d34-0410-b5e6-96231b3b80d8
* Add LiveIntervalMap::dumpCache() to print out the cache used by the ssa ↵Jakob Stoklund Olesen2011-01-20
| | | | | | update algorithm. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123925 91177308-0d34-0410-b5e6-96231b3b80d8
* Add RAGreedy methods for splitting live ranges around regions.Jakob Stoklund Olesen2011-01-18
| | | | | | | | | | 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
* Turn the EdgeBundles class into a stand-alone machine CFG analysis pass.Jakob Stoklund Olesen2011-01-04
| | | | | | | | | | 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
* Add EdgeBundles to SplitKit.Jakob Stoklund Olesen2010-12-21
| | | | | | | | | 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
* Detect and enumerate bypass loops.Jakob Stoklund Olesen2010-12-15
| | | | | | | | 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
* Separate SplitAnalysis::getSplitLoops().Jakob Stoklund Olesen2010-12-15
| | | | | | | 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
* Basic rematerialization during splitting.Jakob Stoklund Olesen2010-11-10
| | | | | | | | | | | 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
* When inserting copies during splitting, always use the parent register as theJakob Stoklund Olesen2010-11-01
| | | | | | | | | | | | 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
* Replace SplitKit SSA update with an iterative algorithm very similar to the oneJakob Stoklund Olesen2010-10-28
| | | | | | | | | | | | | | | | 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
* Make MachineDominators available for SplitEditor. We are going to need it forJakob Stoklund Olesen2010-10-28
| | | | | | | | | 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
* Handle critical loop predecessors by making both inside and outside registersJakob Stoklund Olesen2010-10-27
| | | | | | | | | 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
* Compute critical loop predecessors in the same way as critical loop exits.Jakob Stoklund Olesen2010-10-27
| | | | | | | | 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
* This is a prototype of an experimental register allocationAndrew Trick2010-10-22
| | | | | | | | | | | | | | | | | framework. It's purpose is not to improve register allocation per se, but to make it easier to develop powerful live range splitting. I call it the basic allocator because it is as simple as a global allocator can be but provides the building blocks for sophisticated register allocation with live range splitting. A minimal implementation is provided that trivially spills whenever it runs out of registers. I'm checking in now to get high-level design and style feedback. I've only done minimal testing. The next step is implementing a "greedy" allocation algorithm that does some register reassignment and makes better splitting decisions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117174 91177308-0d34-0410-b5e6-96231b3b80d8
* Add print methodsJakob Stoklund Olesen2010-10-22
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117143 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unused accessor.Jakob Stoklund Olesen2010-10-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116580 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate curli from SplitEditor. Use the LiveRangeEdit reference instead.Jakob Stoklund Olesen2010-10-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116547 91177308-0d34-0410-b5e6-96231b3b80d8
* Create a new LiveRangeEdit class to keep track of the new registers created whenJakob Stoklund Olesen2010-10-14
| | | | | | | | | 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
* Rename SplitEditor::rewrite to finish() and break it out into a couple of newJakob Stoklund Olesen2010-10-08
| | | | | | | | | 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
* Remove SplitAnalysis::removeUse. It was only used to make SplitAnalysisJakob Stoklund Olesen2010-10-05
| | | | | | | reusable, but that is no longer relevant since a split will always replace the original. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115709 91177308-0d34-0410-b5e6-96231b3b80d8
* Update SplitEditor API to reflect the fact that the original live interval isJakob Stoklund Olesen2010-10-05
| | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115695 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't use nextIndex to check for live out of instruction.Jakob Stoklund Olesen2010-10-05
| | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115665 91177308-0d34-0410-b5e6-96231b3b80d8
* Build the complement interval dupli after the split intervals instead ofJakob Stoklund Olesen2010-09-21
| | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114492 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the value mapping provided by LiveIntervalMap. This simplifies the code aJakob Stoklund Olesen2010-09-16
| | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114043 91177308-0d34-0410-b5e6-96231b3b80d8
* Mechanically replace LiveInterval* with LiveIntervalMap for intervals beingJakob Stoklund Olesen2010-09-13
| | | | | | edited without actually using LiveIntervalMap functionality. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113816 91177308-0d34-0410-b5e6-96231b3b80d8
* Allow LiveIntervalMap to be reused by resetting the current live interval.Jakob Stoklund Olesen2010-09-13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113815 91177308-0d34-0410-b5e6-96231b3b80d8
* Thinking about it, we don't need MachineDominatorTree after all. The DomValueJakob Stoklund Olesen2010-08-18
| | | | | | map discovers the iterated dominance frontier for free. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111400 91177308-0d34-0410-b5e6-96231b3b80d8
* Add the LiveIntervalMap class. Don't hook it up yet.Jakob Stoklund Olesen2010-08-18
| | | | | | | | | | | | | | | | LiveIntervalMap maps values from a parent LiveInterval to a child interval that is a strict subset. It will create phi-def values as needed to preserve the VNInfo SSA form in the child interval. This leads to an algorithm very similar to the one in SSAUpdaterImpl.h, but with enough differences that the code can't be reused: - We don't need to manipulate PHI instructions. - LiveIntervals have kills. - We have MachineDominatorTree. - We can use df_iterator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111393 91177308-0d34-0410-b5e6-96231b3b80d8
* Clean up the Spiller.h interface.Jakob Stoklund Olesen2010-08-13
| | | | | | | | | The earliestStart argument is entirely specific to linear scan allocation, and can be easily calculated by RegAllocLinearScan. Replace std::vector with SmallVector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111055 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement splitting inside a single block.Jakob Stoklund Olesen2010-08-13
| | | | | | | | When a live range is contained a single block, we can split it around instruction clusters. The current approach is very primitive, splitting before and after the largest gap between uses. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111043 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-09 13:56:08 +0000