aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/RegAllocLinearScan.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Keep track of which registers are related to which other registers.Chris Lattner2005-08-231-21/+86
| | | | | | | | | | | | | | Use this information to avoid doing expensive interval intersections for registers that could not possible be interesting. This speeds up linscan on ia64 compiling kc++ in release mode from taking 7.82s to 4.8s(!), total itanium llc time on this program is 27.3s now. This marginally speeds up PPC and X86, but they appear to be limited by other parts of linscan, not this code. On this program, on itanium, live intervals now takes 41% of llc time. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@22986 91177308-0d34-0410-b5e6-96231b3b80d8
* Try to avoid scanning the fixed list. On architectures with a non-stupidChris Lattner2005-08-221-20/+55
| | | | | | | | | | | | | | number of regs (e.g. most riscs), many functions won't need to use callee clobbered registers. Do a speculative check to see if we can get a free register without processing the fixed list (which has all of these). This saves a lot of time on machines with lots of callee clobbered regs (e.g. ppc and itanium, also x86). This reduces ppc llc compile time from 184s -> 172s on kc++. This is probably worth FAR FAR more on itanium though. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@22972 91177308-0d34-0410-b5e6-96231b3b80d8
* Move some code in the register assignment case that only needs to happen ifChris Lattner2005-08-221-17/+26
| | | | | | | | | we spill out of the fast path. The scan of active_ and the calls to updateSpillWeights don't need to happen unless a spill occurs. This reduces debug llc time of kc++ with ppc from 187.3s to 183.2s. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@22971 91177308-0d34-0410-b5e6-96231b3b80d8
* Speed up this loop a bit, based on some observations that Nate made, andChris Lattner2005-08-221-8/+34
| | | | | | | add some comments. This loop really needs to be reevaluated! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@22966 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove trailing whitespaceMisha Brukman2005-04-211-4/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21420 91177308-0d34-0410-b5e6-96231b3b80d8
* Update these register allocators to set the PhysRegUsed info in MachineFunction.Chris Lattner2005-01-231-2/+9
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@19791 91177308-0d34-0410-b5e6-96231b3b80d8
* Silence VS warningsChris Lattner2005-01-081-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@19385 91177308-0d34-0410-b5e6-96231b3b80d8
* Move virtual method call out of loopChris Lattner2004-12-151-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@18955 91177308-0d34-0410-b5e6-96231b3b80d8
* Move virtual function call out of loop to speed up getFreePhysReg by aboutNate Begeman2004-12-071-2/+2
| | | | | | | 20%, shaving 0.1s off hbd compile time on my g5. Yay. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@18592 91177308-0d34-0410-b5e6-96231b3b80d8
* * There is no reason for SpillWeights to be an instance varChris Lattner2004-11-181-69/+71
| | | | | | | | | * Do not put fixed registers into the unhandled set. This means they will never find their way into the inactive, active, or handled sets, so we can simplify a bunch of code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17945 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a couple of bugs where we considered physregs past their range as possiblyChris Lattner2004-11-181-6/+11
| | | | | | | intersecting an interval. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17939 91177308-0d34-0410-b5e6-96231b3b80d8
* Start using the iterators in the fixed_ intervals to avoid having to binaryChris Lattner2004-11-181-5/+12
| | | | | | | | search physreg intervals every time we access it. This takes another half second off of linscan. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17937 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a counter for the number of times linscan has to backtrack. Start usingChris Lattner2004-11-181-22/+36
| | | | | | | | the iterator hints we have to speed up overlaps(). This speeds linscan up by about .2s (out of 8.7) on 175.vpr for PPC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17935 91177308-0d34-0410-b5e6-96231b3b80d8
* * Improve comments/documentation substantiallyChris Lattner2004-11-181-128/+172
| | | | | | | | | | | | | | | | | | | * Eliminate the releaseMemory method, this is not an analysis * Change the fixed, active, and inactive lists of intervals to maintain an iterator for the current position in the interval. This allows us to do constant time increments of the iterator instead of having to do a binary search to find our liverange in our liveinterval all of the time, which substantially speeds up cases where LiveIntervals have many LiveRanges - which is very common for physical registers. On targets with many physregs, this can make a noticable difference. With a release build of LLC for PPC, this halves the time in processInactiveIntervals and processActiveIntervals, from 1.5s to .75s. This also lays the ground for more to come. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17933 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename some methods, use 'begin' instead of 'start', add new LiveIntervalChris Lattner2004-11-181-11/+13
| | | | | | | iterator/begin/end members. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17930 91177308-0d34-0410-b5e6-96231b3b80d8
* Do not make i have bigger scope that we needChris Lattner2004-11-051-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17483 91177308-0d34-0410-b5e6-96231b3b80d8
* Free the VirtRegMap at the end of MachineFunction processing instead of atChris Lattner2004-09-301-1/+1
| | | | | | | the beginning of processing the next one. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16605 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixes to make LLVM compile with vc7.1.Alkis Evlogimenos2004-09-031-2/+2
| | | | | | | Patch contributed by Paolo Invernizzi! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16152 91177308-0d34-0410-b5e6-96231b3b80d8
* Change the way we choose a free register: instead of picking the firstAlkis Evlogimenos2004-09-021-3/+14
| | | | | | | | | | | | | | | | | | | | | | | free allocatable register, we prefer the a free one with the most uses of inactive intervals. This causes less spills and performes a bit better compared to gcc: Program | GCC/LLC (Before)| GCC/LLC (After) 164.gzip/164.gzip | 0.59 | 0.60 175.vpr/175.vpr | 0.57 | 0.58 176.gcc/176.gcc | 0.59 | 0.61 181.mcf/181.mcf | 0.94 | 0.95 186.crafty/186.crafty | 0.62 | 0.62 197.parser/197.parser | 0.89 | 0.88 252.eon/252.eon | 0.61 | 0.66 253.perlbmk/253.perlbmk | 0.79 | 0.84 254.gap/254.gap | 0.81 | 0.81 255.vortex/255.vortex | 0.92 | 0.93 256.bzip2/256.bzip2 | 0.69 | 0.69 300.twolf/300.twolf | 0.91 | 0.90 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16147 91177308-0d34-0410-b5e6-96231b3b80d8
* We don't need to sort the added vector as unhandled intervals areAlkis Evlogimenos2004-09-021-1/+0
| | | | | | | stored in a binary heap. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16143 91177308-0d34-0410-b5e6-96231b3b80d8
* Changes For Bug 352Reid Spencer2004-09-011-3/+3
| | | | | | | | | 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
* Be a bit more efficient when processing the active and inactiveAlkis Evlogimenos2004-09-011-26/+31
| | | | | | | | | | lists. Instead of scanning the vector backwards, scan it forward and swap each element we want to erase. Then at the end erase all removed intervals at once. This doesn't save much: 0.08s out of 4s when compiling 176.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16136 91177308-0d34-0410-b5e6-96231b3b80d8
* Now that LiveIntervals::addIntervalsForSpills is fixed, do not requireAlkis Evlogimenos2004-08-271-2/+0
| | | | | | | LiveVariables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16076 91177308-0d34-0410-b5e6-96231b3b80d8
* Back out this change as it broke the build last night. This should beAlkis Evlogimenos2004-08-271-0/+2
| | | | | | | | investicated further as the linearscan variants don't really need LiveVariables... git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16074 91177308-0d34-0410-b5e6-96231b3b80d8
* The linear scan variants do not require the LiveVariables analysis.Alkis Evlogimenos2004-08-271-2/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16071 91177308-0d34-0410-b5e6-96231b3b80d8
* Convert indentation to 2 spaces.Alkis Evlogimenos2004-08-041-438/+438
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15489 91177308-0d34-0410-b5e6-96231b3b80d8
* 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
* Change std::map<unsigned, LiveInterval*> into a std::map<unsigned,Alkis Evlogimenos2004-07-241-3/+3
| | | | | | | | 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
* Completely eliminate the intervals_ list. instead, the r2iMap_ maintainsChris Lattner2004-07-241-9/+8
| | | | | | | ownership of the intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15155 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename LiveIntervals.(cpp|h) -> LiveIntervalAnalysis.(cpp|h)Chris Lattner2004-07-231-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15135 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
* These files don't need to include <iostream> since they include ↵Brian Gaeke2004-07-211-1/+0
| | | | | | "Support/Debug.h". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15089 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 assertion to not dereference end!Chris Lattner2004-07-191-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14991 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14990 91177308-0d34-0410-b5e6-96231b3b80d8
* Correctly compute the ration of iterations/#intervals.Alkis Evlogimenos2004-07-041-2/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14626 91177308-0d34-0410-b5e6-96231b3b80d8
* Add efficiency statistic.Alkis Evlogimenos2004-07-041-1/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14590 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename Interval class to LiveInterval to avoid conflicting with the alreadyChris Lattner2004-06-211-10/+10
| | | | | | | | | | 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
* Pull Interval class out of LiveIntervals.Alkis Evlogimenos2004-05-301-11/+12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13910 91177308-0d34-0410-b5e6-96231b3b80d8
* When spilling an register, introduce a new temporary for each of itsAlkis Evlogimenos2004-05-301-40/+46
| | | | | | | | 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
* Add required headerAlkis Evlogimenos2004-05-081-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13417 91177308-0d34-0410-b5e6-96231b3b80d8
* numeric_limits::infinity() apparently does not work on all systems. As aChris Lattner2004-05-061-1/+1
| | | | | | | workaround, use the C HUGE_VAL macro instead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13377 91177308-0d34-0410-b5e6-96231b3b80d8
* Make the set of fixed (preallocated) intervals be a fixed superset ofAlkis Evlogimenos2004-03-171-29/+10
| | | | | | | | unhandled + handled. So unhandled is now including all fixed intervals and fixed intervals never changes when processing a function. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12462 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a spiller option to llc. A simple spiller will come soon. When we get ↵Alkis Evlogimenos2004-03-011-1/+3
| | | | | | CFG in the machine code represenation a global spiller will also be possible. Also document the linear scan register allocator but mark it as experimental for now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12062 91177308-0d34-0410-b5e6-96231b3b80d8
* Add the long awaited memory operand folding support for linear scanAlkis Evlogimenos2004-03-011-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12058 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename member function to be consistent with the rest.Alkis Evlogimenos2004-02-271-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11898 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove asssert since it is breaking cases that it shouldn't.Alkis Evlogimenos2004-02-251-1/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11841 91177308-0d34-0410-b5e6-96231b3b80d8
* Add an assertionChris Lattner2004-02-251-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11830 91177308-0d34-0410-b5e6-96231b3b80d8
* Move machine code rewriter and spiller outside the registerAlkis Evlogimenos2004-02-241-141/+15
| | | | | | | | | | | | allocator. The implementation is completely rewritten and now employs several optimizations not exercised before. For example for 164.gzip we have 997 loads and 699 stores vs the 1221 loads and 880 stores we have before. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11798 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove '4Virt' from member function names as it is obvious.Alkis Evlogimenos2004-02-231-12/+12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11781 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-18 09:37:12 +0000