summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SplitKit.h
Commit message (Collapse)AuthorAgeFilesLines
...
* Add EdgeBundles to SplitKit.Jakob Stoklund Olesen2010-12-211-1/+38
| | | | | | | | | 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
* Detect and enumerate bypass loops.Jakob Stoklund Olesen2010-12-151-0/+9
| | | | | | | | 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-0/+4
| | | | | | | This method returns the set of loops with uses that are candidates for splitting. llvm-svn: 121870
* Basic rematerialization during splitting.Jakob Stoklund Olesen2010-11-101-8/+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. llvm-svn: 118702
* When inserting copies during splitting, always use the parent register as theJakob Stoklund Olesen2010-11-011-6/+6
| | | | | | | | | | | | 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
* Replace SplitKit SSA update with an iterative algorithm very similar to the oneJakob Stoklund Olesen2010-10-281-1/+23
| | | | | | | | | | | | | | | | 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-2/+6
| | | | | | | | | 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/+5
| | | | | | | | | 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-0/+5
| | | | | | | | 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
* This is a prototype of an experimental register allocationAndrew Trick2010-10-221-1/+1
| | | | | | | | | | | | | | | | 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. llvm-svn: 117174
* Add print methodsJakob Stoklund Olesen2010-10-221-0/+7
| | | | llvm-svn: 117143
* Remove unused accessor.Jakob Stoklund Olesen2010-10-151-2/+0
| | | | llvm-svn: 116580
* Eliminate curli from SplitEditor. Use the LiveRangeEdit reference instead.Jakob Stoklund Olesen2010-10-151-3/+0
| | | | llvm-svn: 116547
* Create a new LiveRangeEdit class to keep track of the new registers created whenJakob Stoklund Olesen2010-10-141-13/+5
| | | | | | | | | 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
* Rename SplitEditor::rewrite to finish() and break it out into a couple of newJakob Stoklund Olesen2010-10-081-4/+11
| | | | | | | | | functions: computeRemainder and rewrite. When the remainder breaks up into multiple components, remember to rewrite those uses as well. llvm-svn: 116121
* Remove SplitAnalysis::removeUse. It was only used to make SplitAnalysisJakob Stoklund Olesen2010-10-051-3/+0
| | | | | | | reusable, but that is no longer relevant since a split will always replace the original. llvm-svn: 115709
* Update SplitEditor API to reflect the fact that the original live interval isJakob Stoklund Olesen2010-10-051-14/+8
| | | | | | | | | | 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
* Don't use nextIndex to check for live out of instruction.Jakob Stoklund Olesen2010-10-051-5/+5
| | | | | | | | | | | 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
* Build the complement interval dupli after the split intervals instead ofJakob Stoklund Olesen2010-09-211-10/+27
| | | | | | | | | | | | | 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-20/+12
| | | | | | | | | | | | | | | | | 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-3/+5
| | | | | | edited without actually using LiveIntervalMap functionality. llvm-svn: 113816
* Allow LiveIntervalMap to be reused by resetting the current live interval.Jakob Stoklund Olesen2010-09-131-4/+9
| | | | llvm-svn: 113815
* Thinking about it, we don't need MachineDominatorTree after all. The DomValueJakob Stoklund Olesen2010-08-181-4/+1
| | | | | | map discovers the iterated dominance frontier for free. llvm-svn: 111400
* Add the LiveIntervalMap class. Don't hook it up yet.Jakob Stoklund Olesen2010-08-181-0/+66
| | | | | | | | | | | | | | | | 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-2/+2
| | | | | | | | | 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-1/+11
| | | | | | | | 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
* Update the SplitAnalysis statistics as uses are moved from curli to the newJakob Stoklund Olesen2010-08-121-3/+7
| | | | | | | split intervals. THis means the analysis can be used for multiple splits as long as curli doesn't shrink. llvm-svn: 110975
* Implement single block splitting.Jakob Stoklund Olesen2010-08-121-5/+21
| | | | | | | | | | 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
* Recalculate the spill weight and allocation hint for virtual registers createdJakob Stoklund Olesen2010-08-101-0/+2
| | | | | | 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-14/+21
| | | | | | | | | | 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
* Checkpoint SplitKit progress.Jakob Stoklund Olesen2010-08-041-29/+46
| | | | | | | 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-6/+88
| | | | | | | | 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-2/+2
| | | | | | | | 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-1/+35
| | | | | | | 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-1/+1
| | | | llvm-svn: 108845
* Beginning SplitKit - utility classes for live range splitting.Jakob Stoklund Olesen2010-07-201-0/+86
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