summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SplitKit.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Thinking about it, we don't need MachineDominatorTree after all. The DomValueJakob Stoklund Olesen2010-08-181-15/+25
| | | | | | map discovers the iterated dominance frontier for free. llvm-svn: 111400
* Revert r111394. It was too aggressive.Jakob Stoklund Olesen2010-08-181-3/+3
| | | | | | | | | | We must complete the DFS, otherwise we might miss needed phi-defs, and prematurely color live ranges with a non-dominating value. This is not a big deal since we get to color more of the CFG and the next mapValue call will be faster. llvm-svn: 111397
* Aggressively prune the DFS when inserting phi-defs.Jakob Stoklund Olesen2010-08-181-3/+3
| | | | llvm-svn: 111394
* Add the LiveIntervalMap class. Don't hook it up yet.Jakob Stoklund Olesen2010-08-181-1/+213
| | | | | | | | | | | | | | | | 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. llvm-svn: 111393
* Clean up the Spiller.h interface.Jakob Stoklund Olesen2010-08-131-1/+1
| | | | | | | | | The earliestStart argument is entirely specific to linear scan allocation, and can be easily calculated by RegAllocLinearScan. Replace std::vector with SmallVector. llvm-svn: 111055
* Implement splitting inside a single block.Jakob Stoklund Olesen2010-08-131-0/+75
| | | | | | | | 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. llvm-svn: 111043
* Let LiveInterval::addRange extend existing ranges, it will verify that valueJakob Stoklund Olesen2010-08-131-5/+2
| | | | | | | | | | numbers match. The old check could accidentally leave holes in openli. Also let useIntv add all ranges for the phi-def value inserted by enterIntvAtEnd. This works as long at the value mapping is established in enterIntvAtEnd. llvm-svn: 110995
* Remember to actually update SplitAnalysis statistics now that we have a fancyJakob Stoklund Olesen2010-08-131-0/+1
| | | | | | function to do it. llvm-svn: 110994
* Handle an empty dupli.Jakob Stoklund Olesen2010-08-121-2/+8
| | | | | | | | | | | | | | | | | | | | This can happen if the original interval has been broken into two disconnected parts. Ideally, we should be able to detect when the graph is disconnected and create separate intervals, but that code is not implemented yet. Example: Two basic blocks are both branching to a loop header. Our interval is defined in both basic blocks, and live into the loop along both edges. We decide to split the interval around the loop. The interval is split into an inside part and an outside part. The outside part now has two disconnected segments, one in each basic block. If we later decide to split the outside interval into single blocks, we get one interval per basic block and an empty dupli for the remainder. llvm-svn: 110976
* Update the SplitAnalysis statistics as uses are moved from curli to the newJakob Stoklund Olesen2010-08-121-8/+37
| | | | | | | split intervals. THis means the analysis can be used for multiple splits as long as curli doesn't shrink. llvm-svn: 110975
* Also recompute HasPHIKill flags in LiveInterval::RenumberValues.Jakob Stoklund Olesen2010-08-121-1/+1
| | | | | | | If a phi-def value were removed from the interval, the phi-kill flags are no longer valid. llvm-svn: 110949
* Clean up debug output.Jakob Stoklund Olesen2010-08-121-32/+32
| | | | llvm-svn: 110940
* Implement single block splitting.Jakob Stoklund Olesen2010-08-121-0/+128
| | | | | | | | | | Before spilling a live range, we split it into a separate range for each basic block where it is used. That way we only get one reload per basic block if the new smaller ranges can allocate to a register. This type of splitting is already present in the standard spiller. llvm-svn: 110934
* More debug spewJakob Stoklund Olesen2010-08-101-0/+2
| | | | llvm-svn: 110720
* Implement register class inflation.Jakob Stoklund Olesen2010-08-101-0/+1
| | | | | | | | | When splitting a live range, the new registers have fewer uses and the permissible register class may be less constrained. Recompute the register class constraint from the uses of new registers created for a split. This may let them be allocated from a larger set, possibly avoiding a spill. llvm-svn: 110703
* Recalculate the spill weight and allocation hint for virtual registers createdJakob Stoklund Olesen2010-08-101-2/+7
| | | | | | during live range splitting. llvm-svn: 110686
* Lazily defer duplicating the live interval we are splitting until we know it isJakob Stoklund Olesen2010-08-061-36/+45
| | | | | | | | | | necessary. Sometimes, live range splitting doesn't shrink the current interval, but simply changes some instructions to use a new interval. That makes the original more suitable for spilling. In this case, we don't need to duplicate the original. llvm-svn: 110481
* Add LiveInterval::RenumberValues - Garbage collection for VNInfos.Jakob Stoklund Olesen2010-08-061-1/+3
| | | | | | | After heavy editing of a live interval, it is much easier to simply renumber the live values instead of trying to keep track of the unused ones. llvm-svn: 110463
* Fix swapped COPY operands.Jakob Stoklund Olesen2010-08-061-2/+2
| | | | llvm-svn: 110453
* Checkpoint SplitKit progress.Jakob Stoklund Olesen2010-08-041-55/+172
| | | | | | | We are now at a point where we can split around simple single-entry, single-exit loops, although still with some bugs. llvm-svn: 110257
* Add SplitEditor to SplitKit. This class will be used to edit live intervals andJakob Stoklund Olesen2010-07-261-2/+210
| | | | | | | | rewrite instructions for live range splitting. Still work in progress. llvm-svn: 109469
* Change the createSpiller interface to take a MachineFunctionPass argument.Jakob Stoklund Olesen2010-07-201-7/+7
| | | | | | | | The spillers can pluck the analyses they need from the pass reference. Switch some never-null pointers to references. llvm-svn: 108969
* Implement loop splitting analysis.Jakob Stoklund Olesen2010-07-201-18/+148
| | | | | | | Determine which loop exit blocks need a 'pre-exit' block inserted. Recognize when this would be impossible. llvm-svn: 108941
* Appease the colonials.Jakob Stoklund Olesen2010-07-201-3/+3
| | | | llvm-svn: 108845
* Beginning SplitKit - utility classes for live range splitting.Jakob Stoklund Olesen2010-07-201-0/+148
This is a work in progress. So far we have some basic loop analysis to help determine where it is useful to split a live range around a loop. The actual loop splitting code from Splitter.cpp is also going to move in here. llvm-svn: 108842
OpenPOWER on IntegriCloud