aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/LiveIntervalAnalysis.h
AgeCommit message (Collapse)Author
2005-09-21Expose the LiveInterval interfaces as public headers.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@23400 91177308-0d34-0410-b5e6-96231b3b80d8
2005-09-02Teach live intervals to not crash on dead livein regsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@23206 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-09Allow the live interval analysis pass to be a bit more aggressive aboutChris Lattner
numbering values in live ranges for physical registers. The alpha backend currently generates code that looks like this: vreg = preg ... preg = vreg use preg ... preg = vreg use preg etc. Because vreg contains the value of preg coming in, each of the copies back into preg contain that initial value as well. In the case of the Alpha, this allows this testcase: void "foo"(int %blah) { store int 5, int *%MyVar store int 12, int* %MyVar2 ret void } to compile to: foo: ldgp $29, 0($27) ldiq $0,5 stl $0,MyVar ldiq $0,12 stl $0,MyVar2 ret $31,($26),1 instead of: foo: ldgp $29, 0($27) bis $29,$29,$0 ldiq $1,5 bis $0,$0,$29 stl $1,MyVar ldiq $1,12 bis $0,$0,$29 stl $1,MyVar2 ret $31,($26),1 This does not seem to have any noticable effect on X86 code. This fixes PR535. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20536 91177308-0d34-0410-b5e6-96231b3b80d8
2004-12-07For PR387:\Reid Spencer
Make only one print method to avoid overloaded virtual warnings when \ compiled with -Woverloaded-virtual git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@18589 91177308-0d34-0410-b5e6-96231b3b80d8
2004-09-30* Wrap some comments to 80 colsChris Lattner
* Add const_iterator stuff * Add a print method, which means that I can now call dump() from the debugger. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16612 91177308-0d34-0410-b5e6-96231b3b80d8
2004-09-08Use a DenseMap for mapping reg->reg. This improves the LiveIntervalAlkis Evlogimenos
analysis running time from 2.7869secs to 2.5226secs on 176.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16244 91177308-0d34-0410-b5e6-96231b3b80d8
2004-08-26Use newly added API in MRegisterInfo.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16060 91177308-0d34-0410-b5e6-96231b3b80d8
2004-08-04Clean up whitespace.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15490 91177308-0d34-0410-b5e6-96231b3b80d8
2004-08-04Convert indentation to 2 spaces.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15489 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-24Change std::map<unsigned, LiveInterval*> into a std::map<unsigned,Alkis Evlogimenos
LiveInterval>. This saves some space and removes the pointer indirection caused by following the pointer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15167 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-24Completely eliminate the intervals_ list. instead, the r2iMap_ maintainsChris Lattner
ownership of the intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15155 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-24Add a new differingRegisterClasses methodChris Lattner
make overlapsAliases take pointers instead of references fix indentation git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15153 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-23More minor changes:Chris Lattner
* Inline some functions * Eliminate some comparisons from the release build This is good for another .3 on gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15144 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-23Speedup debug builds a bitChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15137 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-23Rename LiveIntervals.(cpp|h) -> LiveIntervalAnalysis.(cpp|h)Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15135 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-23Pull the LiveRange and LiveInterval classes out of LiveIntervals.h (whichChris Lattner
will soon be renamed) into their own file. The new file should not emit DEBUG output or have other side effects. The LiveInterval class also now doesn't know whether its working on registers or some other thing. In the future we will want to use the LiveInterval class and friends to do stack packing. In addition to a code simplification, this will allow us to do it more easily. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15134 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-23Improve comments a bitChris Lattner
Use an explicit LiveRange class to represent ranges instead of an std::pair. This is a minor cleanup, but is really intended to make a future patch simpler and less invasive. Alkis, could you please take a look at LiveInterval::liveAt? I suspect that you can add an operator<(unsigned) to LiveRange, allowing us to speed up the upper_bound call by quite a bit (this would also apply to other callers of upper/lower_bound). I would do it myself, but I still don't understand that crazy liveAt function, despite the comment. :) Basically I would like to see this: LiveRange dummy(index, index+1); Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), dummy); Turn into: Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), index); git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15130 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-23Force coallescing of live ranges that have a single definition, even if theyChris Lattner
interfere. Because these intervals have a single definition, and one of them is a copy instruction, they are always safe to merge even if their lifetimes interfere. This slightly reduces the amount of spill code, for example on 252.eon, from: 12837 spiller - Number of loads added 7604 spiller - Number of stores added 5842 spiller - Number of register spills 18155 liveintervals - Number of identity moves eliminated after coalescing to: 12754 spiller - Number of loads added 7585 spiller - Number of stores added 5803 spiller - Number of register spills 18262 liveintervals - Number of identity moves eliminated after coalescing The much much bigger win would be to merge intervals with multiple definitions (aka phi nodes) but this is not that day. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15124 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-19Split joinIntervals into two methodsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15003 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-19fill comment to 80 colsChris Lattner
remove map that is not needed git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14988 91177308-0d34-0410-b5e6-96231b3b80d8
2004-06-21Rename Interval class to LiveInterval to avoid conflicting with the alreadyChris Lattner
existing llvm::Interval class. Patch contributed by Vladimir Prus! http://mail.cs.uiuc.edu/pipermail/llvmbugs/2004-June/000710.html git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14281 91177308-0d34-0410-b5e6-96231b3b80d8
2004-05-30Pull Interval class out of LiveIntervals.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13910 91177308-0d34-0410-b5e6-96231b3b80d8
2004-05-30When spilling an register, introduce a new temporary for each of itsAlkis Evlogimenos
spills. This allows for more flexibility when allocating registers for spill code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13907 91177308-0d34-0410-b5e6-96231b3b80d8
2004-05-29Remove defs vector from live intervals.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13892 91177308-0d34-0410-b5e6-96231b3b80d8
2004-04-09Add definition list to each live interval.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12791 91177308-0d34-0410-b5e6-96231b3b80d8
2004-03-01Add the long awaited memory operand folding support for linear scanAlkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12058 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-22Abstract merging of ranges away from number of slots per instruction.Alkis Evlogimenos
Also make it less aggressive as the current implementation breaks in some cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11696 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-20Too many changes in one commit:Alkis Evlogimenos
1. LiveIntervals now implement a 4 slot per instruction model. Load, Use, Def and a Store slot. This is required in order to correctly represent caller saved register clobbering on function calls, register reuse in the same instruction (def resues last use) and also spill code added later by the allocator. The previous representation (2 slots per instruction) was insufficient and as a result was causing subtle bugs. 2. Fixes in spill code generation. This was the major cause of failures in the test suite. 3. Linear scan now has core support for folding memory operands. This is untested and not enabled (the live interval update function does not attempt to fold loads/stores in instructions). 4. Lots of improvements in the debugging output of both live intervals and linear scan. Give it a try... it is beautiful :-) In summary the above fixes all the issues with the recent reserved register elimination changes and get the allocator very close to the next big step: folding memory operands. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11654 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-18Move unused typedefs in private section. Add method to return intervalAlkis Evlogimenos
given a register. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11608 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-17Add LiveIntervals::Interval::empty() member function.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11520 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-15Eliminate the use of spill (reserved) registers.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11476 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-31Merge safe parts from last night's buggy commit. These do not breakAlkis Evlogimenos
any test cases :-) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11032 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-31Revert last night's changes as they broke some tests. Will remerge parts of ↵Alkis Evlogimenos
the patch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11029 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-31Several performance enhancements and cleanups from Chris.Alkis Evlogimenos
Simplification of LiveIntervals::Interval::overlaps() and addition of examples to overlaps() and liveAt() to make them clearer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11028 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-23Fix failing test cases with joined live intervals. It turns out thatAlkis Evlogimenos
when joining we need to check if we overlap with the second interval or any of its aliases. Also make joining intervals the default. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10973 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-22Add option to join live intervals. Two intervals are joined if thereAlkis Evlogimenos
is a move between two registers, at least one of the registers is virtual and the two live intervals do not overlap. This results in about 40% reduction in intervals, 30% decrease in the register allocators running time and a 20% increase in peephole optimizations (mainly move eliminations). The option can be enabled by passing -join-liveintervals where appropriate. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10965 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-16Fold open interval ends handling intoAlkis Evlogimenos
LiveIntervals::Interval::expiredAt() and simplify regalloc code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10894 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-16Use a list instead of a vector to store intervals. This will be neededAlkis Evlogimenos
when we join intervals and one of the two will need to be removed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10892 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-13Remove allocatable registers vector. It is already provided byAlkis Evlogimenos
LiveVariables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10830 91177308-0d34-0410-b5e6-96231b3b80d8
2003-12-28Add coalescing to register allocator. A hint is added to each intervalAlkis Evlogimenos
which denotes the register we would like to be assigned to (virtual or physical). In register allocation, if this hint exists and we can map it to a physical register (it is either a physical register or it is a virtual register that already got assigned to a physical one) we use that register if it is available instead of a random one in the free pool. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10634 91177308-0d34-0410-b5e6-96231b3b80d8
2003-12-21Change weight into a float so that we can take into account theAlkis Evlogimenos
nesting level when computing it. Right now the allocator uses: w = sum_over_defs_uses( 10 ^ nesting level ); git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10569 91177308-0d34-0410-b5e6-96231b3b80d8
2003-12-21Add support for inactive intervals. This effectively reuses registersAlkis Evlogimenos
for live ranges that fall into assigned registers' holes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10566 91177308-0d34-0410-b5e6-96231b3b80d8
2003-12-18Rename LiveIntervals::expired() to LiveIntervals::expiredAt().Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10511 91177308-0d34-0410-b5e6-96231b3b80d8
2003-12-18Handle multiple virtual register definitions gracefully.Alkis Evlogimenos
Move some of the longer LiveIntervals::Interval method out of the header and add debug information to them. Fix bug and simplify range merging code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10509 91177308-0d34-0410-b5e6-96231b3b80d8
2003-12-05Move operator<<(std::ostream&, const LiveInterval&) out of the header file.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10290 91177308-0d34-0410-b5e6-96231b3b80d8
2003-11-20Merging the linear scan register allocator in trunk. It currently passes ↵Alkis Evlogimenos
most tests under test/Programs/SingleSource/Benchmarks/Shootout so development will continue on trunk. The allocator is not enabled by default. You will need to pass -regallo=linearscan to lli or llc to use it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10103 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-02-26 11:44:33 +0000