summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SplitKit.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Don't crash when a value is defined after the last split point.Jakob Stoklund Olesen2011-04-051-1/+2
| | | | llvm-svn: 128962
* Use std::unique instead of a SmallPtrSet to ensure unique instructions in ↵Jakob Stoklund Olesen2011-04-051-38/+26
| | | | | | | | | | | 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. llvm-svn: 128886
* Stop precomputing last split points, query the SplitAnalysis cache on demand.Jakob Stoklund Olesen2011-04-051-9/+4
| | | | llvm-svn: 128875
* Cache the fairly expensive last split point computation and provide a fastJakob Stoklund Olesen2011-04-051-10/+36
| | | | | | | | | 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. llvm-svn: 128874
* Stop caching basic block index ranges now that SlotIndexes can keep up.Jakob Stoklund Olesen2011-04-041-10/+11
| | | | llvm-svn: 128821
* Recompute register class and hint for registers created during spilling.Jakob Stoklund Olesen2011-03-291-9/+1
| | | | | | The spill weight is not recomputed for an unspillable register - it stays infinite. llvm-svn: 128490
* Handle the special case when all uses follow the last split point.Jakob Stoklund Olesen2011-03-291-1/+2
| | | | llvm-svn: 128450
* Amend debug output.Jakob Stoklund Olesen2011-03-271-2/+3
| | | | llvm-svn: 128398
* Process all dead defs after rematerializing during splitting.Jakob Stoklund Olesen2011-03-201-22/+15
| | | | llvm-svn: 127973
* Be more accurate about the slot index reading a register when dealing with defsJakob Stoklund Olesen2011-03-181-4/+20
| | | | | | | | and early clobbers. Assert when trying to find an undefined value. llvm-svn: 127856
* Dead code elimination may separate the live interval into multiple connected ↵Jakob Stoklund Olesen2011-03-171-4/+4
| | | | | | | | | components. I have convinced myself that it can only happen when a phi value dies. When it happens, allocate new virtual registers for the components. llvm-svn: 127827
* Rewrite instructions as part of ConnectedVNInfoEqClasses::Distribute.Jakob Stoklund Olesen2011-03-171-24/+1
| | | | llvm-svn: 127779
* Preserve both isPHIDef and isDefByCopy bits when copying parent values.Jakob Stoklund Olesen2011-03-151-5/+4
| | | | llvm-svn: 127697
* Delete dead code after rematerializing.Jakob Stoklund Olesen2011-03-081-1/+37
| | | | | | | | 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. llvm-svn: 127287
* Work around a coalescer bug.Jakob Stoklund Olesen2011-03-051-3/+22
| | | | | | | | | | | | 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. llvm-svn: 127096
* Tweak debug output. No functional changes.Jakob Stoklund Olesen2011-03-041-9/+0
| | | | llvm-svn: 127006
* Use an IndexedMap instead of a DenseMap for the live-out cache.Jakob Stoklund Olesen2011-03-041-47/+40
| | | | | | | This speeds up updateSSA() so it only accounts for 5% of the live range splitting time. llvm-svn: 126972
* Cache basic block bounds instead of asking SlotIndexes::getMBBRange all the ↵Jakob Stoklund Olesen2011-03-031-11/+10
| | | | | | | | | time. This speeds up the greedy register allocator by 15%. DenseMap is not as fast as one might hope. llvm-svn: 126921
* Change the SplitEditor interface to a single instance can be shared for ↵Jakob Stoklund Olesen2011-03-031-4/+11
| | | | | | multiple splits. llvm-svn: 126912
* Only run the updateSSA loop when we have actually seen multiple values.Jakob Stoklund Olesen2011-03-031-3/+23
| | | | | | When only a single value has been seen, new PHIDefs are never needed. llvm-svn: 126911
* Turn the Edit member into a pointer so it can change dynamically.Jakob Stoklund Olesen2011-03-021-43/+43
| | | | | | No functional change. llvm-svn: 126898
* Transfer simply defined values directly without recomputing liveness and SSA.Jakob Stoklund Olesen2011-03-021-24/+66
| | | | | | | | 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. llvm-svn: 126894
* Extract a method. No functional change.Jakob Stoklund Olesen2011-03-021-27/+24
| | | | llvm-svn: 126893
* Move extendRange() into SplitEditor and delete the LiveRangeMap class.Jakob Stoklund Olesen2011-03-021-176/+135
| | | | | | | | | 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. llvm-svn: 126818
* Rename mapValue to extendRange because that is its function now.Jakob Stoklund Olesen2011-03-021-20/+9
| | | | | | Simplify the signature - The return value and ParentVNI are no longer needed. llvm-svn: 126809
* Move LiveIntervalMap::extendTo into LiveInterval itself.Jakob Stoklund Olesen2011-03-021-19/+5
| | | | | | | This method could probably be used by LiveIntervalAnalysis::shrinkToUses, and now it can use extendIntervalEndTo() which coalesces ranges. llvm-svn: 126803
* 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
OpenPOWER on IntegriCloud