aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/SplitKit.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Eliminate curli from SplitEditor. Use the LiveRangeEdit reference instead.Jakob Stoklund Olesen2010-10-151-15/+13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116547 91177308-0d34-0410-b5e6-96231b3b80d8
* Move stack slot assignments into LiveRangeEdit.Jakob Stoklund Olesen2010-10-151-6/+0
| | | | | | | | | | All registers created during splitting or spilling are assigned to the same stack slot as the parent register. When splitting or rematting, we may not spill at all. In that case the stack slot is still assigned, but it will be dead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116546 91177308-0d34-0410-b5e6-96231b3b80d8
* Create a new LiveRangeEdit class to keep track of the new registers created whenJakob Stoklund Olesen2010-10-141-32/+21
| | | | | | | | | 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
* Only split around a loop if the live range has uses outside the loop periphery.Jakob Stoklund Olesen2010-10-141-14/+13
| | | | | | | | | | Before we would also split around a loop if any peripheral block had multiple uses. This could cause repeated splitting when splitting a different live range would insert uses into the periphery. Now -spiller=inline passes the nightly test suite again. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116494 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename SplitEditor::rewrite to finish() and break it out into a couple of newJakob Stoklund Olesen2010-10-081-36/+45
| | | | | | | | | 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
* After splitting, the remaining LiveInterval may be fragmented into multipleJakob Stoklund Olesen2010-10-071-11/+24
| | | | | | | | | | | | | connected components. These components should be allocated different virtual registers because there is no reason for them to be allocated together. Add the ConnectedVNInfoEqClasses class to calculate the connected components, and move values to new LiveIntervals. Use it from SplitKit::rewrite by creating new virtual registers for the components. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116006 91177308-0d34-0410-b5e6-96231b3b80d8
* Print more loop info.Jakob Stoklund Olesen2010-10-071-0/+16
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115951 91177308-0d34-0410-b5e6-96231b3b80d8
* Print out MBB number when rewriting.Jakob Stoklund Olesen2010-10-071-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115950 91177308-0d34-0410-b5e6-96231b3b80d8
* Cache interval iterators in SplitEditor::addTruncSimpleRange so we only have toJakob Stoklund Olesen2010-10-071-10/+20
| | | | | | do one find(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115929 91177308-0d34-0410-b5e6-96231b3b80d8
* Clean up debug printing.Jakob Stoklund Olesen2010-10-071-15/+19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115928 91177308-0d34-0410-b5e6-96231b3b80d8
* Count uses in all nested loops, not just the deepest.Jakob Stoklund Olesen2010-10-051-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115710 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove SplitAnalysis::removeUse. It was only used to make SplitAnalysisJakob Stoklund Olesen2010-10-051-29/+0
| | | | | | | 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
* dupli always has an interval now.Jakob Stoklund Olesen2010-10-051-14/+11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115708 91177308-0d34-0410-b5e6-96231b3b80d8
* We can split around loops with multiple exits now.Jakob Stoklund Olesen2010-10-051-6/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115696 91177308-0d34-0410-b5e6-96231b3b80d8
* Update SplitEditor API to reflect the fact that the original live interval isJakob Stoklund Olesen2010-10-051-13/+9
| | | | | | | | | | 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
* Intervals are half-open.Jakob Stoklund Olesen2010-10-051-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115694 91177308-0d34-0410-b5e6-96231b3b80d8
* When we find a reaching definition, make sure it is visited from all paths byJakob Stoklund Olesen2010-10-051-5/+12
| | | | | | erasing it from the visited set. That ensures we create the right phi defs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115666 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't use nextIndex to check for live out of instruction.Jakob Stoklund Olesen2010-10-051-12/+8
| | | | | | | | | | | 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
* Removed VNInfo::isDefAccurate(). Def "accuracy" can be checked by testing ↵Lang Hames2010-09-251-2/+2
| | | | | | whether LiveIntervals::getInstructionFromIndex(def) returns NULL. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114791 91177308-0d34-0410-b5e6-96231b3b80d8
* Build the complement interval dupli after the split intervals instead ofJakob Stoklund Olesen2010-09-211-25/+118
| | | | | | | | | | | | | 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-161-205/+73
| | | | | | | | | | | | | | | | | 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-131-70/+72
| | | | | | 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-131-14/+24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113815 91177308-0d34-0410-b5e6-96231b3b80d8
* Let's just declare that it is impossible to construct a std::pair from a nullJakob Stoklund Olesen2010-09-131-22/+11
| | | | | | pointer and work around that. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113788 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix the msvc 2010 build.Michael J. Spencer2010-08-191-2/+19
| | | | | | | | | | | | | | The Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.30319.01 implements parts of C++0x based on the draft standard. An old version of the draft had a bug that makes std::pair<T1*, T2*>(something, 0) fail to compile. This is because the template<class U, class V> pair(U&& x, V&& y) constructor is selected, even though it later fails to implicitly convert U and V to frist_type and second_type. This has been fixed in n3090, but it seems that Microsoft is not going to update msvc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111535 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111400 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111397 91177308-0d34-0410-b5e6-96231b3b80d8
* Aggressively prune the DFS when inserting phi-defs.Jakob Stoklund Olesen2010-08-181-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111394 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. 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-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. 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-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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111043 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110995 91177308-0d34-0410-b5e6-96231b3b80d8
* Remember to actually update SplitAnalysis statistics now that we have a fancyJakob Stoklund Olesen2010-08-131-0/+1
| | | | | | function to do it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110994 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110976 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110975 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110949 91177308-0d34-0410-b5e6-96231b3b80d8
* Clean up debug output.Jakob Stoklund Olesen2010-08-121-32/+32
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110940 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110934 91177308-0d34-0410-b5e6-96231b3b80d8
* More debug spewJakob Stoklund Olesen2010-08-101-0/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110720 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110703 91177308-0d34-0410-b5e6-96231b3b80d8
* Recalculate the spill weight and allocation hint for virtual registers createdJakob Stoklund Olesen2010-08-101-2/+7
| | | | | | during live range splitting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110686 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110481 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110463 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix swapped COPY operands.Jakob Stoklund Olesen2010-08-061-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110453 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110257 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109469 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108969 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108941 91177308-0d34-0410-b5e6-96231b3b80d8
* Appease the colonials.Jakob Stoklund Olesen2010-07-201-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108845 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108842 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2024-09-19 18:52:53 +0000