summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen
Commit message (Collapse)AuthorAgeFilesLines
...
* Completely eliminate the intervals_ list. instead, the r2iMap_ maintainsChris Lattner2004-07-244-78/+70
| | | | | | ownership of the intervals. llvm-svn: 15155
* 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. llvm-svn: 15154
* Add a new differingRegisterClasses methodChris Lattner2004-07-241-4/+8
| | | | | | | make overlapsAliases take pointers instead of references fix indentation llvm-svn: 15153
* 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. llvm-svn: 15152
* 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. llvm-svn: 15144
* 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. llvm-svn: 15141
* 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 :) llvm-svn: 15139
* New helper methodChris Lattner2004-07-231-1/+7
| | | | llvm-svn: 15138
* Speedup debug builds a bitChris Lattner2004-07-231-2/+3
| | | | llvm-svn: 15137
* 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). llvm-svn: 15136
* Rename LiveIntervals.(cpp|h) -> LiveIntervalAnalysis.(cpp|h)Chris Lattner2004-07-234-7/+7
| | | | llvm-svn: 15135
* 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. llvm-svn: 15134
* 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); llvm-svn: 15130
* Update live intervals more accurately for PHI elim. This slightly reducesChris Lattner2004-07-231-10/+6
| | | | | | the live intervals for some registers. llvm-svn: 15125
* 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. llvm-svn: 15124
* costmetic changesChris Lattner2004-07-221-14/+14
| | | | llvm-svn: 15118
* Fix broken -debug printingChris Lattner2004-07-221-0/+1
| | | | llvm-svn: 15115
* The default has not been 'simple' for AGES!Chris Lattner2004-07-221-1/+1
| | | | llvm-svn: 15114
* Make linear scan the defaultChris Lattner2004-07-221-1/+1
| | | | llvm-svn: 15111
* Put variable name to a separate line.Alkis Evlogimenos2004-07-221-1/+2
| | | | llvm-svn: 15108
* Fix indentation and wrap code at 80 colsMisha Brukman2004-07-221-110/+100
| | | | llvm-svn: 15107
* 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. llvm-svn: 15106
* Fit to 80 columns.Alkis Evlogimenos2004-07-221-10/+11
| | | | llvm-svn: 15105
* 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) llvm-svn: 15103
* Remove extraneous punctuationChris Lattner2004-07-221-2/+2
| | | | llvm-svn: 15098
* Use reverse iterators when updating the vector, since scanning fromAlkis Evlogimenos2004-07-221-11/+14
| | | | | | the end will reduce erase() runtimes. llvm-svn: 15093
* 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. llvm-svn: 15092
* Minor cleanupsChris Lattner2004-07-211-8/+6
| | | | llvm-svn: 15091
* These files don't need to include <iostream> since they include ↵Brian Gaeke2004-07-2110-10/+0
| | | | | | "Support/Debug.h". llvm-svn: 15089
* Fix analysis name.Alkis Evlogimenos2004-07-211-1/+1
| | | | llvm-svn: 15078
* Clear spilled list at once. Remove unused vector.Alkis Evlogimenos2004-07-211-3/+2
| | | | llvm-svn: 15073
* 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. llvm-svn: 15072
* Improve file comment.Alkis Evlogimenos2004-07-211-1/+7
| | | | llvm-svn: 15069
* Add Iterative scan register allocator.Alkis Evlogimenos2004-07-212-4/+479
| | | | llvm-svn: 15068
* Linearscan is no longer experimental.Alkis Evlogimenos2004-07-211-1/+1
| | | | llvm-svn: 15067
* 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. llvm-svn: 15032
* Remove unneeded functor. LiveInterval has a < operator.Alkis Evlogimenos2004-07-201-11/+1
| | | | llvm-svn: 15031
* Remove dead code.Alkis Evlogimenos2004-07-191-17/+0
| | | | llvm-svn: 15011
* Fix a bug that occurs when the last instruction in a range is deadChris Lattner2004-07-191-3/+6
| | | | llvm-svn: 15005
* When joining intervals, join intervals in deeply nested loops first. ThisChris Lattner2004-07-191-4/+34
| | | | | | | is a simple change, but seems to improve code a little. For example, on 256.bzip2, we went from 75.0s -> 73.33s (2% speedup). llvm-svn: 15004
* Split joinIntervals into two methodsChris Lattner2004-07-192-84/+89
| | | | llvm-svn: 15003
* There is no need to store the MBB along with the MI any more, we can nowChris Lattner2004-07-193-16/+16
| | | | | | ask instructions for their parent. llvm-svn: 14998
* Simplify the interface to LiveVariables::addVirtualRegister(Killed|Dead)Chris Lattner2004-07-194-9/+10
| | | | llvm-svn: 14997
* Remove the DefBlock element of VarInfo. DefBlock is always DefInst->getParent()Chris Lattner2004-07-191-4/+4
| | | | llvm-svn: 14996
* Two changes, both very significant:Chris Lattner2004-07-191-11/+2
| | | | | | | | | | * vreg <-> vreg joining now works, enable it unconditionally when joining is enabled (which is the default). * Fix a serious pessimization of spill code where we were saying that a spilled DEF operand was live into the subsequent instruction. This allows for substantially better code when spilling starts to happen. llvm-svn: 14993
* See comments. The live intervals were not coming out of the spiller in sortedChris Lattner2004-07-191-1/+20
| | | | | | | | | order, causing the inactive list in the linearscan list to get unsorted, which basically fuxored everything up severely. These seems to fix the joiner, so with more testing I will enable it by default. llvm-svn: 14992
* Fix assertion to not dereference end!Chris Lattner2004-07-191-2/+2
| | | | llvm-svn: 14991
* Add some asserts that the list of intervals returned by addIntervalsForSpillsChris Lattner2004-07-191-6/+30
| | | | | | | is sorted. This is not the case currently, which is causing no end of problems. llvm-svn: 14990
* remove the mbbi2mbbMap_, which was just keeping track of mbb order anyway.Chris Lattner2004-07-191-54/+73
| | | | | | | | | | Heavily refactor handleVirtualRegisterDef, adding comments and making it more efficient. It is also much easier to follow and convince ones self that it is correct :) Add -debug output to the joine, showing the result of joining the intervals. llvm-svn: 14989
* fill comment to 80 colsChris Lattner2004-07-191-11/+7
| | | | | | remove map that is not needed llvm-svn: 14988
OpenPOWER on IntegriCloud