aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/LiveInterval.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Add a register allocation preference field; add a method to compute size of ↵Evan Cheng2007-04-171-0/+9
| | | | | | a live interval. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36216 91177308-0d34-0410-b5e6-96231b3b80d8
* Added an automatic cast to "std::ostream*" etc. from OStream. We then canBill Wendling2006-12-171-1/+1
| | | | | | | | rework the hacks that had us passing OStream in. We pass in std::ostream* instead, check for null, and then dispatch to the correct print() method. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@32636 91177308-0d34-0410-b5e6-96231b3b80d8
* The best unbreakage yet, addressing Bill's concerns.Jeff Cohen2006-12-161-3/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@32622 91177308-0d34-0410-b5e6-96231b3b80d8
* An even better unbreakage...Jeff Cohen2006-12-151-0/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@32617 91177308-0d34-0410-b5e6-96231b3b80d8
* Changed llvm_ostream et all to OStream. llvm_cerr, llvm_cout, llvm_null, areBill Wendling2006-12-071-4/+3
| | | | | | | now cerr, cout, and NullStream resp. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@32298 91177308-0d34-0410-b5e6-96231b3b80d8
* Converted to using llvm streams instead of <iostream>sBill Wendling2006-11-291-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@31992 91177308-0d34-0410-b5e6-96231b3b80d8
* Put the #include for a module first.Bill Wendling2006-11-281-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@31958 91177308-0d34-0410-b5e6-96231b3b80d8
* Changed to using llvm streams.Bill Wendling2006-11-281-5/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@31954 91177308-0d34-0410-b5e6-96231b3b80d8
* For PR786:Reid Spencer2006-11-021-1/+0
| | | | | | | | | | | Turn on -Wunused and -Wno-unused-parameter. Clean up most of the resulting fall out by removing unused variables. Remaining warnings have to do with unused functions (I didn't want to delete code without review) and unused variables in generated code. Maintainers should clean up the remaining issues when they see them. All changes pass DejaGnu tests and Olden. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@31380 91177308-0d34-0410-b5e6-96231b3b80d8
* When joining two intervals where the RHS is really simple, use a light-weightChris Lattner2006-09-021-0/+17
| | | | | | | method for joining the live ranges instead of the fully-general one. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@30049 91177308-0d34-0410-b5e6-96231b3b80d8
* avoid calling the virtual isMoveInstr method endlessly by caching its results.Chris Lattner2006-08-311-12/+12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29994 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach the coallescer to coallesce live intervals joined by an arbitraryChris Lattner2006-08-291-130/+59
| | | | | | | | | number of copies, potentially defining live ranges that appear to have differing value numbers that become identical when coallsced. Among other things, this fixes CodeGen/X86/shift-coalesce.ll and PR687. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29968 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplifications to liveinterval analysis, no functionality change.Chris Lattner2006-08-261-11/+15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29896 91177308-0d34-0410-b5e6-96231b3b80d8
* Completely change the way that joining with physregs is implemented. ThisChris Lattner2006-08-251-7/+40
| | | | | | | | | paves the way for future changes, increases coallescing opportunities (in theory, not witnessed in practice), and eliminates the really expensive LiveIntervals::overlapsAliases method. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29890 91177308-0d34-0410-b5e6-96231b3b80d8
* When replacing value numbers, make sure to compactify the value # space.Chris Lattner2006-08-241-0/+12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29865 91177308-0d34-0410-b5e6-96231b3b80d8
* Take advantage of the recent improvements to the liveintervals set (trackingChris Lattner2006-08-241-8/+83
| | | | | | | | | | | | | | | | | | | | instructions which define each value#) to simplify and improve the coallescer. In particular, this patch: 1. Implements iterative coallescing. 2. Reverts an unsafe hack from handlePhysRegDef, superceeding it with a better solution. 3. Implements PR865, "coallescing" away the second copy in code like: A = B ... B = A This also includes changes to symbolically print registers in intervals when possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29862 91177308-0d34-0410-b5e6-96231b3b80d8
* Improve the LiveInterval class to keep track of which machine instructionChris Lattner2006-08-221-1/+15
| | | | | | | | defines each value# tracked by the interval. This will be used to improve coallescing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29830 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix LiveInterval::getOverlapingRanges to take things in the right orderChris Lattner2005-10-211-3/+3
| | | | | | | | | | | (an unused method). Fix the merger so that it can merge ranges like this [10:12)[16:40) with [12:38) into [10:40) instead of bogus ranges. This sort of input will be possible for the merger coming shortly git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@23865 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a conditional so we don't access past the end of the range. Thanks toChris Lattner2005-10-201-6/+4
| | | | | | | Andrew for bringing this to my attn. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@23850 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix order of eval problem from when I refactored this into a function.Chris Lattner2005-10-201-3/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@23844 91177308-0d34-0410-b5e6-96231b3b80d8
* add a new method, play around with some code.Chris Lattner2005-10-201-10/+56
| | | | | | | | | Fix a *bug* in the extendIntervalEndTo method. In particular, if adding [2:10) to an interval containing [0:2),[10:30), we produced [0:10),[10,30). Which is not the most smart thing to do. Now produce [0:30). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@23841 91177308-0d34-0410-b5e6-96231b3b80d8
* Refactor some code, pulling it out into a function. No functionality change.Chris Lattner2005-10-201-15/+26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@23839 91177308-0d34-0410-b5e6-96231b3b80d8
* Expose the LiveInterval interfaces as public headers.Chris Lattner2005-09-211-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@23400 91177308-0d34-0410-b5e6-96231b3b80d8
* Print the symbolic register name in a register allocator debug dump.Chris Lattner2005-05-141-11/+17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@22002 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove trailing whitespaceMisha Brukman2005-04-211-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21420 91177308-0d34-0410-b5e6-96231b3b80d8
* Prevent accessing past the end of the intervals vector, this fixesChris Lattner2004-12-041-1/+3
| | | | | | | Prolang-C/bison in the JIT git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@18477 91177308-0d34-0410-b5e6-96231b3b80d8
* There is no need to check to see if j overflowed in this loop as we're onlyChris Lattner2004-11-181-1/+3
| | | | | | | incrementing i. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17944 91177308-0d34-0410-b5e6-96231b3b80d8
* Moderate head scratching reveals that this conditional is not needed. IfChris Lattner2004-11-181-4/+0
| | | | | | | i->start == j->start, then certainly i->end > j->start. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17943 91177308-0d34-0410-b5e6-96231b3b80d8
* Take another .7 seconds off of linear scan time.Chris Lattner2004-11-181-3/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17936 91177308-0d34-0410-b5e6-96231b3b80d8
* Add ability to give hints to the overlaps routines.Chris Lattner2004-11-181-5/+13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17934 91177308-0d34-0410-b5e6-96231b3b80d8
* Give a better message for a common assertion failure.Brian Gaeke2004-11-161-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17887 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix includes. Patch contributed by Paolo Invernizzi!Alkis Evlogimenos2004-09-281-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16533 91177308-0d34-0410-b5e6-96231b3b80d8
* Changes For Bug 352Reid Spencer2004-09-011-1/+1
| | | | | | | | | Move include/Config and include/Support into include/llvm/Config, include/llvm/ADT and include/llvm/Support. From here on out, all LLVM public header files must be under include/llvm/. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16137 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix the sense of joinableChris Lattner2004-07-251-4/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15196 91177308-0d34-0410-b5e6-96231b3b80d8
* This patch makes use of the infrastructure implemented before to safely andChris Lattner2004-07-251-1/+43
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | aggressively coallesce live ranges even if they overlap. Consider this LLVM code for example: int %test(int %X) { %Y = mul int %X, 1 ;; Codegens to Y = X %Z = add int %X, %Y ret int %Z } The mul is just there to get a copy into the code stream. This produces this machine code: (0x869e5a8, LLVM BB @0x869b9a0): %reg1024 = mov <fi#-2>, 1, %NOREG, 0 ;; "X" %reg1025 = mov %reg1024 ;; "Y" (subsumed by X) %reg1026 = add %reg1024, %reg1025 %EAX = mov %reg1026 ret Note that the life times of reg1024 and reg1025 overlap, even though they contain the same value. This results in this machine code: test: mov %EAX, DWORD PTR [%ESP + 4] mov %ECX, %EAX add %EAX, %ECX ret Another, worse case involves loops and PHI nodes. Consider this trivial loop: testcase: int %test2(int %X) { entry: br label %Loop Loop: %Y = phi int [%X, %entry], [%Z, %Loop] %Z = add int %Y, 1 %cond = seteq int %Z, 100 br bool %cond, label %Out, label %Loop Out: ret int %Z } Because of interactions between the PHI elimination pass and the register allocator, this got compiled to this code: test2: mov %ECX, DWORD PTR [%ESP + 4] .LBBtest2_1: *** mov %EAX, %ECX inc %EAX cmp %EAX, 100 *** mov %ECX, %EAX jne .LBBtest2_1 ret Or on powerpc, this code: _test2: mflr r0 stw r0, 8(r1) stwu r1, -60(r1) .LBB_test2_1: addi r2, r3, 1 cmpwi cr0, r2, 100 *** or r3, r2, r2 bne cr0, .LBB_test2_1 *** or r3, r2, r2 lwz r0, 68(r1) mtlr r0 addi r1, r1, 60 blr 0 With this improvement in place, we now generate this code for these two testcases, which is what we want: test: mov %EAX, DWORD PTR [%ESP + 4] add %EAX, %EAX ret test2: mov %EAX, DWORD PTR [%ESP + 4] .LBBtest2_1: inc %EAX cmp %EAX, 100 jne .LBBtest2_1 # Loop ret Or on PPC: _test2: mflr r0 stw r0, 8(r1) stwu r1, -60(r1) .LBB_test2_1: addi r3, r3, 1 cmpwi cr0, r3, 100 bne cr0, .LBB_test2_1 lwz r0, 68(r1) mtlr r0 addi r1, r1, 60 blr 0 Static numbers for spill code loads/stores/reg-reg copies (smaller is better): em3d: before: 47/25/26 after: 44/22/24 164.gzip: before: 433/245/310 after: 403/231/278 175.vpr: before: 3721/2189/1581 after: 4144/2081/1423 176.gcc: before: 26195/8866/9235 after: 25942/8082/8275 186.crafty: before: 4295/2587/3079 after: 4119/2519/2916 252.eon: before: 12754/7585/5803 after: 12508/7425/5643 256.bzip2: before: 463/226/315 after: 482:241/309 Runtime perf number samples on X86: gzip: before: 41.09 after: 39.86 bzip2: runtime: before: 56.71s after: 57.07s gcc: before: 6.16 after: 6.12 eon: before: 2.03s after: 2.00s git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15194 91177308-0d34-0410-b5e6-96231b3b80d8
* Make a method const, no functionality changesChris Lattner2004-07-251-5/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15193 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bug in the range removerChris Lattner2004-07-251-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15188 91177308-0d34-0410-b5e6-96231b3b80d8
* Change std::map<unsigned, LiveInterval*> into a std::map<unsigned,Alkis Evlogimenos2004-07-241-2/+2
| | | | | | | | 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
* In the joiner, merge the small interval into the large interval. This restoresChris Lattner2004-07-241-0/+9
| | | | | | | | | us back to taking about 10.5s on gcc, instead of taking 15.6s! The net result is that my big patches have hand no significant effect on compile time or code quality. heh. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15156 91177308-0d34-0410-b5e6-96231b3b80d8
* Little stuff:Chris Lattner2004-07-241-17/+130
| | | | | | | | | | | | | | | | | | | | * Fix comment typeo * add dump() methods * add a few new methods like getLiveRangeContaining, removeRange & joinable (which is currently the same as overlaps) * Remove the unused operator== Bigger change: * In LiveInterval, instead of using a boolean isDefinedOnce to keep track of if there are > 1 definitions in a particular interval, keep a counter, NumValues to keep track of exactly how many there are. * In LiveRange, add a new ValId element to indicate which of the numbered values each LiveRange belongs to. We now no longer merge LiveRanges if they are of differing value ID's even if they are neighbors. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15152 91177308-0d34-0410-b5e6-96231b3b80d8
* Change addRange and join to be a little bit smarter. In particular, we don'tChris Lattner2004-07-231-33/+76
| | | | | | | | | | | | | | | want to insert a new range into the middle of the vector, then delete ranges one at a time next to the inserted one as they are merged. Instead, if the inserted interval overlaps, just start merging. The only time we insert into the middle of the vector is when we don't overlap at all. Also delete blocks of live ranges if we overlap with many of them. This patch speeds up joining by .7 seconds on a large testcase, but more importantly gets all of the range adding code into addRangeFrom. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15141 91177308-0d34-0410-b5e6-96231b3b80d8
* Search by the start point, not by the whole interval. This saves someChris Lattner2004-07-231-11/+12
| | | | | | | comparisons, reducing linscan by another .1 seconds :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15139 91177308-0d34-0410-b5e6-96231b3b80d8
* Instead of searching for a live interval pair, search for a location. This ↵Chris Lattner2004-07-231-6/+4
| | | | | | | | | gives a very modest speedup of .3 seconds compiling 176.gcc (out of 20s). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15136 91177308-0d34-0410-b5e6-96231b3b80d8
* Pull the LiveRange and LiveInterval classes out of LiveIntervals.h (whichChris Lattner2004-07-231-0/+151
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
generated by cgit v1.1 at 2024-10-30 16:18:43 +0000