aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen
Commit message (Collapse)AuthorAgeFilesLines
* Add some comments to the backtracking code.Alkis Evlogimenos2004-07-251-2/+17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15200 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix the sense of joinableChris Lattner2004-07-252-5/+5
| | | | 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-252-6/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15193 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bug where we incorrectly value numbered the first PHI definition theChris Lattner2004-07-251-3/+26
| | | | | | | | | same as the PHI use. This is not correct as the PHI use value is different depending on which branch is taken. This fixes espresso with aggressive coallescing, and perhaps others. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15189 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
* Add debugging output for joining assignmentsChris Lattner2004-07-251-0/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15187 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove implementation of operator= and make it private so that it isAlkis Evlogimenos2004-07-241-8/+1
| | | | | | | not used accidentally. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15172 91177308-0d34-0410-b5e6-96231b3b80d8
* Change std::map<unsigned, LiveInterval*> into a std::map<unsigned,Alkis Evlogimenos2004-07-246-35/+49
| | | | | | | | 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
* whoops, didn't mean to remove thisChris Lattner2004-07-241-1/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15157 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
* Completely eliminate the intervals_ list. instead, the r2iMap_ maintainsChris Lattner2004-07-244-78/+70
| | | | | | | ownership of the intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15155 91177308-0d34-0410-b5e6-96231b3b80d8
* Big change to compute logical value numbers for each LiveRange added to anChris Lattner2004-07-241-125/+151
| | | | | | | | | | | | | | | | | | | | | | | | | | Interval. This generalizes the isDefinedOnce mechanism that we used before to help us coallesce ranges that overlap. As part of this, every logical range with a different value is assigned a different number in the interval. For example, for code that looks like this: 0 X = ... 4 X += ... ... N = X We now generate a live interval that contains two ranges: [2,6:0),[6,?:1) reflecting the fact that there are two different values in the range at different positions in the code. Currently we are not using this information at all, so this just slows down liveintervals. In the future, this will change. Note that this change also substantially refactors the joinIntervalsInMachineBB method to merge the cases for virt-virt and phys-virt joining into a single case, adds comments, and makes the code a bit easier to follow. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15154 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a new differingRegisterClasses methodChris Lattner2004-07-241-4/+8
| | | | | | | | 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
* Little stuff:Chris Lattner2004-07-242-27/+167
| | | | | | | | | | | | | | | | | | | | * 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
* More minor changes:Chris Lattner2004-07-232-44/+31
| | | | | | | | | | * 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
* Change addRange and join to be a little bit smarter. In particular, we don'tChris Lattner2004-07-232-36/+85
| | | | | | | | | | | | | | | 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
* New helper methodChris Lattner2004-07-231-1/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15138 91177308-0d34-0410-b5e6-96231b3b80d8
* Speedup debug builds a bitChris Lattner2004-07-231-2/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15137 91177308-0d34-0410-b5e6-96231b3b80d8
* Instead of searching for a live interval pair, search for a location. This ↵Chris Lattner2004-07-232-6/+9
| | | | | | | | | 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
* Rename LiveIntervals.(cpp|h) -> LiveIntervalAnalysis.(cpp|h)Chris Lattner2004-07-234-7/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15135 91177308-0d34-0410-b5e6-96231b3b80d8
* Pull the LiveRange and LiveInterval classes out of LiveIntervals.h (whichChris Lattner2004-07-234-239/+286
| | | | | | | | | | | | | 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
* Improve comments a bitChris Lattner2004-07-232-55/+73
| | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Update live intervals more accurately for PHI elim. This slightly reducesChris Lattner2004-07-231-10/+6
| | | | | | | the live intervals for some registers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15125 91177308-0d34-0410-b5e6-96231b3b80d8
* Force coallescing of live ranges that have a single definition, even if theyChris Lattner2004-07-232-9/+30
| | | | | | | | | | | | | | | | | | | | | | | | | 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
* costmetic changesChris Lattner2004-07-221-14/+14
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15118 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix broken -debug printingChris Lattner2004-07-221-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15115 91177308-0d34-0410-b5e6-96231b3b80d8
* The default has not been 'simple' for AGES!Chris Lattner2004-07-221-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15114 91177308-0d34-0410-b5e6-96231b3b80d8
* Make linear scan the defaultChris Lattner2004-07-221-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15111 91177308-0d34-0410-b5e6-96231b3b80d8
* Put variable name to a separate line.Alkis Evlogimenos2004-07-221-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15108 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix indentation and wrap code at 80 colsMisha Brukman2004-07-221-110/+100
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15107 91177308-0d34-0410-b5e6-96231b3b80d8
* Sorting is now handled by both linearscan and iterative scan so liveAlkis Evlogimenos2004-07-221-10/+0
| | | | | | | | intervals need not be sorted anymore. Removing this redundant step improves LiveIntervals running time by 5% on 176.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15106 91177308-0d34-0410-b5e6-96231b3b80d8
* Fit to 80 columns.Alkis Evlogimenos2004-07-221-10/+11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15105 91177308-0d34-0410-b5e6-96231b3b80d8
* Some compile time improvements resulting in a 1sec speedup in the 5secAlkis Evlogimenos2004-07-221-75/+53
| | | | | | | | | | | | compilation of gcc: * Use vectors instead of lists for the intervals sets * Use a heap for the unhandled set to keep intervals always sorted and makes insertions back to the heap very fast (compared to scanning a list) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15103 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove extraneous punctuationChris Lattner2004-07-221-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15098 91177308-0d34-0410-b5e6-96231b3b80d8
* Use reverse iterators when updating the vector, since scanning fromAlkis Evlogimenos2004-07-221-11/+14
| | | | | | | the end will reduce erase() runtimes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15093 91177308-0d34-0410-b5e6-96231b3b80d8
* That funny 2-address lowering pass can also cause multiple definitions,Chris Lattner2004-07-221-8/+18
| | | | | | | | fortunately, they are easy to handle if we know about them. This patch fixes some serious pessimization of code produced by the linscan register allocator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15092 91177308-0d34-0410-b5e6-96231b3b80d8
* Minor cleanupsChris Lattner2004-07-211-8/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15091 91177308-0d34-0410-b5e6-96231b3b80d8
* These files don't need to include <iostream> since they include ↵Brian Gaeke2004-07-2110-10/+0
| | | | | | "Support/Debug.h". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15089 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix analysis name.Alkis Evlogimenos2004-07-211-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15078 91177308-0d34-0410-b5e6-96231b3b80d8
* Clear spilled list at once. Remove unused vector.Alkis Evlogimenos2004-07-211-3/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15073 91177308-0d34-0410-b5e6-96231b3b80d8
* Change std::list into a std::vector for IntervalSets. This reducesAlkis Evlogimenos2004-07-211-4/+5
| | | | | | | compile time for 176.gcc from 5.6 secs to 4.7 secs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15072 91177308-0d34-0410-b5e6-96231b3b80d8
* Improve file comment.Alkis Evlogimenos2004-07-211-1/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15069 91177308-0d34-0410-b5e6-96231b3b80d8
* Add Iterative scan register allocator.Alkis Evlogimenos2004-07-212-4/+479
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15068 91177308-0d34-0410-b5e6-96231b3b80d8
* Linearscan is no longer experimental.Alkis Evlogimenos2004-07-211-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15067 91177308-0d34-0410-b5e6-96231b3b80d8
* Add function to clear all virtual->physical mappings but not assignedAlkis Evlogimenos2004-07-201-0/+5
| | | | | | | stack slots. This is in preparation for the iterative linear scan. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15032 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unneeded functor. LiveInterval has a < operator.Alkis Evlogimenos2004-07-201-11/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15031 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove dead code.Alkis Evlogimenos2004-07-191-17/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15011 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bug that occurs when the last instruction in a range is deadChris Lattner2004-07-191-3/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15005 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-17 20:44:10 +0000