aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegAllocLinearScan.cpp
AgeCommit message (Collapse)Author
2004-09-30Free the VirtRegMap at the end of MachineFunction processing instead of atChris Lattner
the beginning of processing the next one. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16605 91177308-0d34-0410-b5e6-96231b3b80d8
2004-09-03Fixes to make LLVM compile with vc7.1.Alkis Evlogimenos
Patch contributed by Paolo Invernizzi! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16152 91177308-0d34-0410-b5e6-96231b3b80d8
2004-09-02Change the way we choose a free register: instead of picking the firstAlkis Evlogimenos
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
2004-09-02We don't need to sort the added vector as unhandled intervals areAlkis Evlogimenos
stored in a binary heap. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16143 91177308-0d34-0410-b5e6-96231b3b80d8
2004-09-01Changes For Bug 352Reid Spencer
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
2004-09-01Be a bit more efficient when processing the active and inactiveAlkis Evlogimenos
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
2004-08-27Now that LiveIntervals::addIntervalsForSpills is fixed, do not requireAlkis Evlogimenos
LiveVariables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16076 91177308-0d34-0410-b5e6-96231b3b80d8
2004-08-27Back out this change as it broke the build last night. This should beAlkis Evlogimenos
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
2004-08-27The linear scan variants do not require the LiveVariables analysis.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16071 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-25Add some comments to the backtracking code.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15200 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-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-22Some compile time improvements resulting in a 1sec speedup in the 5secAlkis Evlogimenos
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
2004-07-21These files don't need to include <iostream> since they include ↵Brian Gaeke
"Support/Debug.h". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15089 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-19Remove dead code.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15011 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-19Fix assertion to not dereference end!Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14991 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-19Add some asserts that the list of intervals returned by addIntervalsForSpillsChris Lattner
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
2004-07-04Correctly compute the ration of iterations/#intervals.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14626 91177308-0d34-0410-b5e6-96231b3b80d8
2004-07-04Add efficiency statistic.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14590 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-08Add required headerAlkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13417 91177308-0d34-0410-b5e6-96231b3b80d8
2004-05-06numeric_limits::infinity() apparently does not work on all systems. As aChris Lattner
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
2004-03-17Make the set of fixed (preallocated) intervals be a fixed superset ofAlkis Evlogimenos
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
2004-03-01Add a spiller option to llc. A simple spiller will come soon. When we get ↵Alkis Evlogimenos
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
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-27Rename member function to be consistent with the rest.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11898 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-25Remove asssert since it is breaking cases that it shouldn't.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11841 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-25Add an assertionChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11830 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-24Move machine code rewriter and spiller outside the registerAlkis Evlogimenos
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
2004-02-23Remove '4Virt' from member function names as it is obvious.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11781 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-23Refactor VirtRegMap out of RegAllocLinearScan as the first part of bugAlkis Evlogimenos
251 (providing a generic machine code rewriter/spiller). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11780 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-23Add number of spilled registers statistic.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11759 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-23Remove implementation of default constructor as it is useless now.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11755 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-23Improved PhysRegTracker interface. RegAlloc lazily allocates the register ↵Alkis Evlogimenos
tracker using a std::auto_ptr git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11738 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-23Fix comments in PhysRegTracker and rename isPhysRegAvail to isRegAvail to be ↵Alkis Evlogimenos
consistent with the other two git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11723 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-23Pull PhysRegTracker out of RegAllocLinearScan as it can be used by other ↵Alkis Evlogimenos
allocators as well git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11720 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-23Move LiveIntervals.h to lib/CodeGen since it shouldn't be exposed to other ↵Alkis Evlogimenos
parts of the compiler git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11719 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-22Print basic block boundaries in machine instruction debug output.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11704 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-20Fix crash in debug output.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11659 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-20Fix instruction numbering in debug output.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11655 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-19Fix RA::verifyAssignment()Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11629 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-19Rename reloads/spills to loads/stores.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11619 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-18Implement assignment correctness verification.Alkis Evlogimenos
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11609 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-02-14Use std::numeric_limits<float>::infinity() instead ofAlkis Evlogimenos
std::numeric_limits<float>::max() for weighting preallocated intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11427 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-03 00:36:37 +0000