summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Add an InterferenceCache class for caching per-block interference ranges.Jakob Stoklund Olesen2011-04-021-1/+1
| | | | | | | | When the greedy register allocator is splitting multiple global live ranges, it tends to look at the same interference data many times. The InterferenceCache class caches queries for unaltered LiveIntervalUnions. llvm-svn: 128764
* Treat clones the same as their origin.Jakob Stoklund Olesen2011-03-301-5/+21
| | | | | | | | | | | | When DCE clones a live range because it separates into connected components, make sure that the clones enter the same register allocator stage as the register they were cloned from. For instance, clones may be split even when they where created during spilling. Other registers created during spilling are not candidates for splitting or even (re-)spilling. llvm-svn: 128524
* Recompute register class and hint for registers created during spilling.Jakob Stoklund Olesen2011-03-291-0/+1
| | | | | | The spill weight is not recomputed for an unspillable register - it stays infinite. llvm-svn: 128490
* Drop interference reassignment in favor of eviction.Jakob Stoklund Olesen2011-03-271-132/+15
| | | | | | | | | The reassignment phase was able to move interference with a higher spill weight, but it didn't happen very often and it was fairly expensive. The existing interference eviction picks up the slack. llvm-svn: 128397
* Add debug output.Jakob Stoklund Olesen2011-03-191-0/+1
| | | | llvm-svn: 127959
* Add a LiveRangeEdit delegate callback before shrinking a live range.Jakob Stoklund Olesen2011-03-161-0/+12
| | | | | | The register allocator needs to adjust its live interval unions when that happens. llvm-svn: 127774
* Clarify debugging output.Jakob Stoklund Olesen2011-03-161-2/+8
| | | | llvm-svn: 127771
* Tell the register allocator about new unused virtual registers.Jakob Stoklund Olesen2011-03-131-0/+10
| | | | | | | This allows the allocator to free any resources used by the virtual register, including physical register assignments. llvm-svn: 127560
* Change the Spiller interface to take a LiveRangeEdit reference.Jakob Stoklund Olesen2011-03-101-1/+2
| | | | | | | This makes it possible to register delegates and get callbacks when the spiller edits live ranges. llvm-svn: 127389
* Make SpillIs an optional pointer. Avoid creating a bunch of temporary ↵Jakob Stoklund Olesen2011-03-101-2/+1
| | | | | | SmallVectors. llvm-svn: 127388
* Add a LiveRangeEdit::Delegate protocol.Jakob Stoklund Olesen2011-03-091-4/+20
| | | | | | | This will we used for keeping register allocator data structures up to date while LiveRangeEdit is trimming live intervals. llvm-svn: 127300
* Make the UselessRegs argument optional in the LiveRangeEdit constructor.Jakob Stoklund Olesen2011-03-071-6/+3
| | | | llvm-svn: 127181
* Rework the global split cost calculation.Jakob Stoklund Olesen2011-03-051-21/+30
| | | | | | | The global cost is the sum of block frequencies for spill code that must be inserted because preferences weren't met. llvm-svn: 127062
* Compute the constraints for global live range splitting from an interference ↵Jakob Stoklund Olesen2011-03-051-163/+67
| | | | | | | | | | | pattern. This simplifies the code and makes it faster too. The interference patterns are saved for each candidate register. It will be reused for actually executing the split. Work in progress. llvm-svn: 127054
* Extract a method. No functional change.Jakob Stoklund Olesen2011-03-041-40/+52
| | | | llvm-svn: 127040
* Go back to comparing spill weights when deciding if interference can be evicted.Jakob Stoklund Olesen2011-03-041-9/+5
| | | | | | | It gives better results. Sometimes, a live range can be large and still have high spill weight. Such a range should not be spilled. llvm-svn: 127036
* Tweak debug output. No functional changes.Jakob Stoklund Olesen2011-03-041-1/+6
| | | | llvm-svn: 127006
* Precompute block frequencies, pow() isn't free.Jakob Stoklund Olesen2011-03-041-4/+3
| | | | llvm-svn: 126975
* Cache basic block bounds instead of asking SlotIndexes::getMBBRange all the ↵Jakob Stoklund Olesen2011-03-031-39/+30
| | | | | | | | | 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-34/+37
| | | | | | multiple splits. llvm-svn: 126912
* Drop RAGreedy::trySpillInterferences().Jakob Stoklund Olesen2011-03-011-70/+0
| | | | | | | This is a waste of time since we already know how to evict all interferences which is a better approach anyway. llvm-svn: 126798
* Keep track of which stage produced a live range, and bypass earlier stages ↵Jakob Stoklund Olesen2011-03-011-20/+76
| | | | | | | | | | | | | | | | | | | | | | when revisiting. This effectively disables the 'turbo' functionality of the greedy register allocator where all new live ranges created by splitting would be reconsidered as if they were originals. There are two reasons for doing this, 1. It guarantees that the algorithm terminates. Early versions were prone to infinite looping in certain corner cases. 2. It is a 2x speedup. We can skip a lot of unnecessary interference checks that won't lead to good splitting anyway. The problem is that region splitting only gets one shot, so it should probably be changed to target multiple physical registers at once. Local live range splitting is still 'turbo' enabled. It only accounts for a small fraction of compile time, so it is probably not necessary to do anything about that. llvm-svn: 126781
* Try harder to get the hint by preferring to evict hint interference.Jakob Stoklund Olesen2011-02-251-0/+3
| | | | llvm-svn: 126463
* Tweak the register allocator priority queue some more.Jakob Stoklund Olesen2011-02-241-10/+22
| | | | | | | | | | | | New live ranges are assigned in long -> short order, but live ranges that have been evicted at least once are deferred and assigned in short -> long order. Also disable splitting and spilling for live ranges seen for the first time. The intention is to create a realistic interference pattern from the heavy live ranges before starting splitting and spilling around it. llvm-svn: 126451
* Keep track of how many times a live range has been dequeued, and prioritize ↵Jakob Stoklund Olesen2011-02-231-0/+7
| | | | | | | | | | | new ranges. When a large live range is evicted, it will usually be split when it comes around again. By deferring evicted live ranges, the splitting happens at a time when the interference pattern is more realistic. This prevents repeated splitting and evictions. llvm-svn: 126282
* Fix a bug in determining if there is only a single interfering register.Jakob Stoklund Olesen2011-02-231-2/+1
| | | | llvm-svn: 126277
* Be more aggressive about evicting interference.Jakob Stoklund Olesen2011-02-231-26/+88
| | | | | | | | | | | | | Use interval sizes instead of spill weights to determine if it is legal to evict interference. A smaller interval can evict interference if all interfering live ranges are larger. Allow multiple interferences to be evicted as along as they are all larger than the live range being allocated. Spill weights are still used to select the preferred eviction candidate. llvm-svn: 126276
* Change the RAGreedy register assignment order so large live ranges are ↵Jakob Stoklund Olesen2011-02-221-17/+24
| | | | | | | | | | | | | | allocated first. This is based on the observation that long live ranges are more difficult to allocate, so there is a better chance of solving the puzzle by handling the big pieces first. The allocator will evict and split long alive ranges when they get in the way. RABasic is still using spill weights for its priority queue, so the interface to the queue has been virtualized. llvm-svn: 126259
* Add SplitKit::isOriginalEndpoint and use it to force live range splitting to ↵Jakob Stoklund Olesen2011-02-211-2/+11
| | | | | | | | | | | | | | 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-1/+1
| | | | llvm-svn: 126005
* Separate timers for local and global splitting.Jakob Stoklund Olesen2011-02-191-2/+5
| | | | llvm-svn: 126001
* Add VirtRegMap::rewrite() and use it in the new register allocators.Jakob Stoklund Olesen2011-02-181-3/+1
| | | | | | | | | | The rewriter works almost identically to -rewriter=trivial, except it also eliminates any identity copies. This makes the new register allocators independent of VirtRegRewriter.cpp which will be going away at the same time as RegAllocLinearScan. llvm-svn: 125967
* Add basic register allocator statistics.Jakob Stoklund Olesen2011-02-171-0/+10
| | | | llvm-svn: 125789
* Split local live ranges.Jakob Stoklund Olesen2011-02-171-2/+277
| | | | | | | | 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. llvm-svn: 125764
* Simplify using the new leaveIntvBefore()Jakob Stoklund Olesen2011-02-091-13/+2
| | | | llvm-svn: 125238
* Move calcLiveBlockInfo() and the BlockInfo struct into SplitAnalysis.Jakob Stoklund Olesen2011-02-091-143/+20
| | | | | | No functional changes intended. llvm-svn: 125231
* Evict a lighter single interference before attempting to split a live range.Jakob Stoklund Olesen2011-02-091-29/+41
| | | | | | | | | | | | | | Registers are not allocated strictly in spill weight order when live range splitting and spilling has created new shorter intervals with higher spill weights. When one of the new heavy intervals conflicts with a single lighter interval, simply evict the old interval instead of trying to split the heavy one. The lighter interval is a better candidate for splitting, it has a smaller use density. llvm-svn: 125151
* Fix one more case of splitting after the last split point.Jakob Stoklund Olesen2011-02-081-8/+10
| | | | llvm-svn: 125137
* Reorganize interference code to check LastSplitPoint first.Jakob Stoklund Olesen2011-02-081-29/+43
| | | | | | | The last split point can be anywhere in the block, so it interferes with the strictly monotonic requirements of advanceTo(). llvm-svn: 125132
* Also handle the situation where an indirect branch is the first (and last)Jakob Stoklund Olesen2011-02-081-6/+8
| | | | | | instruction in a basic block. llvm-svn: 125116
* Add LiveIntervals::addKillFlags() to recompute kill flags after register ↵Jakob Stoklund Olesen2011-02-081-0/+1
| | | | | | | | | allocation. This is a lot easier than trying to get kill flags right during live range splitting and rematerialization. llvm-svn: 125113
* Trim debug spewJakob Stoklund Olesen2011-02-081-1/+0
| | | | llvm-svn: 125109
* Add SplitEditor::overlapIntv() to create small ranges where both registers ↵Jakob Stoklund Olesen2011-02-081-2/+25
| | | | | | | | | | | | | | | | | | | | | | 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
* Be more strict about the first/last interference-free use.Jakob Stoklund Olesen2011-02-051-4/+25
| | | | | | If the interference overlaps the instruction, we cannot separate it. llvm-svn: 124918
* Add assertions to verify that the new interval is clear of the interference.Jakob Stoklund Olesen2011-02-051-7/+14
| | | | | | | If these inequalities don't hold, we are creating a live range split that won't allocate. llvm-svn: 124917
* Be more accurate about live range splitting at the end of blocks.Jakob Stoklund Olesen2011-02-041-4/+17
| | | | | | | | | | | If interference reaches the last split point, it is effectively live out and should be marked as 'MustSpill'. This can make a difference when the terminator uses a register. There is no way that register can be reused in the outgoing CFG bundle, even if it isn't live out. llvm-svn: 124900
* Verify that one of the ranges produced by region splitting is allocatable.Jakob Stoklund Olesen2011-02-041-1/+15
| | | | | | | We should not be attempting a region split if it won't lead to at least one directly allocatable interval. That could cause infinite splitting loops. llvm-svn: 124893
* Also compute interference intervals for blocks with no uses.Jakob Stoklund Olesen2011-02-041-3/+1
| | | | | | | | When the live range is live through a block that doesn't use the register, but that has interference, region splitting wants to split at the top and bottom of the basic block. llvm-svn: 124839
* Ensure that the computed interference intervals actually overlap their basic ↵Jakob Stoklund Olesen2011-02-031-3/+12
| | | | | | blocks. llvm-svn: 124815
* Return live range end points from SplitEditor::enter*/leave*.Jakob Stoklund Olesen2011-02-031-12/+8
| | | | | | | These end points come from the inserted copies, and can be passed directly to useIntv. This simplifies the coloring code. llvm-svn: 124799
OpenPOWER on IntegriCloud