summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocBase.h
Commit message (Collapse)AuthorAgeFilesLines
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* [CodeGen] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-09-131-15/+17
| | | | | | other minor fixes (NFC). llvm-svn: 313194
* Timer: Track name and description.Matthias Braun2016-11-181-0/+1
| | | | | | | | | | | | | The previously used "names" are rather descriptions (they use multiple words and contain spaces), use short programming language identifier like strings for the "names" which should be used when exporting to machine parseable formats. Also removed a unused TimerGroup from Hexxagon. Differential Revision: https://reviews.llvm.org/D25583 llvm-svn: 287369
* Recommit r265547, and r265610,r265639,r265657 on top of it, plusWei Mi2016-04-131-0/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | two fixes with one about error verify-regalloc reported, and another about live range update of phi after rematerialization. r265547: Replace analyzeSiblingValues with new algorithm to fix its compile time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Patches on top of r265547: r265610 "Fix the compare-clang diff error introduced by r265547." r265639 "Fix the sanitizer bootstrap error in r265547." r265657 "InlineSpiller.cpp: Escap \@ in r265547. [-Wdocumentation]" Differential Revision: http://reviews.llvm.org/D15302 Differential Revision: http://reviews.llvm.org/D18934 Differential Revision: http://reviews.llvm.org/D18935 Differential Revision: http://reviews.llvm.org/D18936 llvm-svn: 266162
* Revert r265547 "Recommit r265309 after fixed an invalid memory reference bug ↵Hans Wennborg2016-04-081-10/+0
| | | | | | | | | | | | | happened" It caused PR27275: "ARM: Bad machine code: Using an undefined physical register" Also reverting the following commits that were landed on top: r265610 "Fix the compare-clang diff error introduced by r265547." r265639 "Fix the sanitizer bootstrap error in r265547." r265657 "InlineSpiller.cpp: Escap \@ in r265547. [-Wdocumentation]" llvm-svn: 265790
* Recommit r265309 after fixed an invalid memory reference bug happenedWei Mi2016-04-061-0/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | when DenseMap growed and moved memory. I verified it fixed the bootstrap problem on x86_64-linux-gnu but I cannot verify whether it fixes the bootstrap error on clang-ppc64be-linux. I will watch the build-bot result closely. Replace analyzeSiblingValues with new algorithm to fix its compile time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Differential Revision: http://reviews.llvm.org/D15302 llvm-svn: 265547
* Revert r265309 and r265312 because they caused some errors I need to ↵Wei Mi2016-04-041-10/+0
| | | | | | investigate. llvm-svn: 265317
* Replace analyzeSiblingValues with new algorithm to fix its compileWei Mi2016-04-041-0/+10
| | | | | | | | | | | | | | | | | | | | | | | | | time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Differential Revision: http://reviews.llvm.org/D15302 llvm-svn: 265309
* [RegAllocGreedy] Introduce a late pass to repair broken hints.Quentin Colombet2015-01-081-0/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | A broken hint is a copy where both ends are assigned different colors. When a variable gets evicted in the neighborhood of such copies, it is likely we can reconcile some of them. ** Context ** Copies are inserted during the register allocation via splitting. These split points are required to relax the constraints on the allocation problem. When such a point is inserted, both ends of the copy would not share the same color with respect to the current allocation problem. When variables get evicted, the allocation problem becomes different and some split point may not be required anymore. However, the related variables may already have been colored. This usually shows up in the assembly with pattern like this: def A ... save A to B def A use A restore A from B ... use B Whereas we could simply have done: def B ... def A use A ... use B ** Proposed Solution ** A variable having a broken hint is marked for late recoloring if and only if selecting a register for it evict another variable. Indeed, if no eviction happens this is pointless to look for recoloring opportunities as it means the situation was the same as the initial allocation problem where we had to break the hint. Finally, when everything has been allocated, we look for recoloring opportunities for all the identified candidates. The recoloring is performed very late to rely on accurate copy cost (all involved variables are allocated). The recoloring is simple unlike the last change recoloring. It propagates the color of the broken hint to all its copy-related variables. If the color is available for them, the recoloring uses it, otherwise it gives up on that hint even if a more complex coloring would have worked. The recoloring happens only if it is profitable. The profitability is evaluated using the expected frequency of the copies of the currently recolored variable with a) its current color and b) with the target color. If a) is greater or equal than b), then it is profitable and the recoloring happen. ** Example ** Consider the following example: BB1: a = b = BB2: ... = b = a Let us assume b gets split: BB1: a = b = BB2: c = b ... d = c = d = a Because of how the allocation work, b, c, and d may be assigned different colors. Now, if a gets evicted to make room for c, assuming b and d were assigned to something different than a. We end up with: BB1: a = st a, SpillSlot b = BB2: c = b ... d = c = d e = ld SpillSlot = e This is likely that we can assign the same register for b, c, and d, getting rid of 2 copies. ** Performances ** Both ARM64 and x86_64 show performance improvements of up to 3% for the llvm-testsuite + externals with Os and O3. There are a few regressions too that comes from the (in)accuracy of the block frequency estimate. <rdar://problem/18312047> llvm-svn: 225422
* Canonicalize header guards into a common format.Benjamin Kramer2014-08-131-3/+3
| | | | | | | | | | Add header guards to files that were missing guards. Remove #endif comments as they don't seem common in LLVM (we can easily add them back if we decide they're useful) Changes made by clang-tidy with minor tweaks. llvm-svn: 215558
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-161-1/+2
| | | | | | instead of comparing to nullptr. llvm-svn: 206356
* Replace OwningPtr<T> with std::unique_ptr<T>.Ahmed Charles2014-03-061-1/+0
| | | | | | | | | | This compiles with no changes to clang/lld/lldb with MSVC and includes overloads to various functions which are used by those projects and llvm which have OwningPtr's as parameters. This should allow out of tree projects some time to move. There are also no changes to libs/Target, which should help out of tree targets have time to move, if necessary. llvm-svn: 203083
* [weak vtables] Remove a bunch of weak vtablesJuergen Ributzka2013-11-191-0/+1
| | | | | | | | | | | | This patch removes most of the trivial cases of weak vtables by pinning them to a single object file. The memory leaks in this version have been fixed. Thanks Alexey for pointing them out. Differential Revision: http://llvm-reviews.chandlerc.com/D2068 Reviewed by Andy llvm-svn: 195064
* Revert r194865 and r194874.Alexey Samsonov2013-11-181-1/+0
| | | | | | | | | | | | This change is incorrect. If you delete virtual destructor of both a base class and a subclass, then the following code: Base *foo = new Child(); delete foo; will not cause the destructor for members of Child class. As a result, I observe plently of memory leaks. Notable examples I investigated are: ObjectBuffer and ObjectBufferStream, AttributeImpl and StringSAttributeImpl. llvm-svn: 194997
* [weak vtables] Remove a bunch of weak vtablesJuergen Ributzka2013-11-151-0/+1
| | | | | | | | | | | This patch removes most of the trivial cases of weak vtables by pinning them to a single object file. Differential Revision: http://llvm-reviews.chandlerc.com/D2068 Reviewed by Andy llvm-svn: 194865
* Revert "Give internal classes hidden visibility."Benjamin Kramer2013-09-111-1/+1
| | | | | | | It works with clang, but GCC has different rules so we can't make all of those hidden. This reverts commit r190534. llvm-svn: 190536
* Give internal classes hidden visibility.Benjamin Kramer2013-09-111-1/+1
| | | | | | Worth 100k on a linux/x86_64 Release+Asserts clang. llvm-svn: 190534
* Track new virtual registers by register number.Mark Lacey2013-08-141-1/+1
| | | | | | | | | | Track new virtual registers by register number, rather than by the live interval created for them. This is the first step in separating the creation of new virtual registers and new live intervals. Eventually live intervals will be created and populated on demand after the virtual registers have been created and used in instructions. llvm-svn: 188434
* LiveIntervalUnion is not used in RegAllocBase.Jakob Stoklund Olesen2013-08-141-1/+1
| | | | | | Patch by Matthias Braun! llvm-svn: 188389
* Make constant string pointer into an array to remove a pointer lookup for ↵Craig Topper2013-07-171-1/+1
| | | | | | every access. llvm-svn: 186482
* Sort includes for all of the .h files under the 'lib' tree. These wereChandler Carruth2012-12-041-2/+2
| | | | | | | | | | missed in the first pass because the script didn't yet handle include guards. Note that the script is now able to handle all of these headers without manual edits. =] llvm-svn: 169224
* Make the LiveRegMatrix analysis available to targets.Jakob Stoklund Olesen2012-11-281-1/+1
| | | | | | | | | | | No functional change, just moved header files. Targets can inject custom passes between register allocation and rewriting. This makes it possible to tweak the register allocation before rewriting, using the full global interference checking available from LiveRegMatrix. llvm-svn: 168806
* Remove LiveIntervalUnions from RegAllocBase.Jakob Stoklund Olesen2012-06-201-54/+2
| | | | | | They are living in LiveRegMatrix now. llvm-svn: 158868
* Convert RABasic to using LiveRegMatrix interference checking.Jakob Stoklund Olesen2012-06-201-1/+3
| | | | | | | Stop using the LiveIntervalUnions provided by RegAllocBase, they will be removed soon. llvm-svn: 158866
* Also compute MBB live-in lists in the new rewriter pass.Jakob Stoklund Olesen2012-06-091-3/+0
| | | | | | | | | This deduplicates some code from the optimizing register allocators, and it means that it is now possible to change the register allocators' solutions simply by editing the VirtRegMap between the register allocator pass and the rewriter. llvm-svn: 158249
* Move RegisterClassInfo.h.Andrew Trick2012-06-061-2/+2
| | | | | | Allow targets to access this API. It's required for RegisterPressure. llvm-svn: 158102
* Move LiveUnionArray into LiveIntervalUnion.hJakob Stoklund Olesen2012-06-051-21/+1
| | | | | | It is useful outside RegAllocBase. llvm-svn: 158041
* Make data structures private.Jakob Stoklund Olesen2012-01-111-6/+12
| | | | llvm-svn: 147979
* Sink spillInterferences into RABasic.Jakob Stoklund Olesen2012-01-111-9/+0
| | | | | | This helper method is too simplistic for RAGreedy. llvm-svn: 147976
* Cleanup.Jakob Stoklund Olesen2012-01-111-9/+0
| | | | llvm-svn: 147975
* Switch AllocationOrder to using RegisterClassInfo instead of a BitVectorJakob Stoklund Olesen2011-06-031-0/+2
| | | | | | | | | of reserved registers. Use RegisterClassInfo in RABasic as well. This slightly changes som allocation orders because RegisterClassInfo puts CSR aliases last. llvm-svn: 132581
* Fix PR9883. Make sure all caches are invalidated when a live range is repaired.Jakob Stoklund Olesen2011-05-101-0/+4
| | | | | | | | The previous invalidation missed the alias interference caches. Also add a stats counter for the number of repaired ranges. llvm-svn: 131133
* Tag cached interference with a user-provided tag instead of the virtual ↵Jakob Stoklund Olesen2011-03-161-2/+7
| | | | | | | | | register number. The live range of a virtual register may change which invalidates the cached interference information. llvm-svn: 127772
* Change the RAGreedy register assignment order so large live ranges are ↵Jakob Stoklund Olesen2011-02-221-7/+8
| | | | | | | | | | | | | | allocated first. This is based on the observation that long live ranges are more difficult to allocate, so there is a better chance of solving the puzzle by handling the big pieces first. The allocator will evict and split long alive ranges when they get in the way. RABasic is still using spill weights for its priority queue, so the interface to the queue has been virtualized. llvm-svn: 126259
* Evict a lighter single interference before attempting to split a live range.Jakob Stoklund Olesen2011-02-091-0/+9
| | | | | | | | | | | | | | Registers are not allocated strictly in spill weight order when live range splitting and spilling has created new shorter intervals with higher spill weights. When one of the new heavy intervals conflicts with a single lighter interval, simply evict the old interval instead of trying to split the heavy one. The lighter interval is a better candidate for splitting, it has a smaller use density. llvm-svn: 125151
* Add a missing word to a comment.Cameron Zwarich2010-12-291-1/+1
| | | | llvm-svn: 122625
* Make the -verify-regalloc command line option available to base classes asJakob Stoklund Olesen2010-12-171-0/+4
| | | | | | | | RegAllocBase::VerifyEnabled. Run the machine code verifier in a few interesting places during RegAllocGreedy. llvm-svn: 122107
* Add named timer groups for the different stages of register allocation.Jakob Stoklund Olesen2010-12-111-0/+3
| | | | llvm-svn: 121604
* Move MRI into RegAllocBase. Clean up debug output a bit.Jakob Stoklund Olesen2010-12-101-2/+3
| | | | llvm-svn: 121599
* Added register reassignment prototype to RAGreedy. It's a simpleAndrew Trick2010-12-091-2/+2
| | | | | | | heuristic to reshuffle register assignments when we can't find an available reg. llvm-svn: 121388
* Store (priority,regnum) pairs in the priority queue instead of providing anJakob Stoklund Olesen2010-12-081-11/+6
| | | | | | | | | | | | | | | | | | | | | | | abstract priority queue interface in subclasses that want to override the priority calculations. Subclasses must provide a getPriority() implementation instead. This approach requires less code as long as priorities are expressable as simple floats, and it avoids the dangers of defining potentially expensive priority comparison functions. It also should speed up priority_queue operations since they no longer have to chase pointers when comparing registers. This is not measurable, though. Preferably, we shouldn't use floats to guide code generation. The use of floats here is derived from the use of floats for spill weights. Spill weights have a dynamic range that doesn't lend itself easily to a fixpoint implementation. When someone invents a stable spill weight representation, it can be reused for allocation priorities. llvm-svn: 121294
* Move RABasic::addMBBLiveIns to the base class, it is generally useful.Jakob Stoklund Olesen2010-12-081-0/+3
| | | | | | | Minor optimization to the use of IntervalMap iterators. They are fairly heavyweight, so prefer SI.valid() over SI != end(). llvm-svn: 121217
* Switch LiveIntervalUnion from std::set to IntervalMap.Jakob Stoklund Olesen2010-12-071-3/+6
| | | | | | | This speeds up RegAllocBasic by 20%, not counting releaseMemory which becomes way faster. llvm-svn: 121201
* Coding style. No significant functionality. Abandon linear scan styleAndrew Trick2010-11-301-40/+39
| | | | | | | | in favor of the widespread llvm style. Capitalize variables and add newlines for visual parsing. Rename variables for readability. And other cleanup. llvm-svn: 120490
* Check TRI->getReservedRegs because other allocators do it. Even thoughAndrew Trick2010-11-111-2/+12
| | | | | | | | it makes no sense for allocation_order iterators to visit reserved regs. The inline spiller depends on AliasAnalysis. Manage the Query state to avoid uninitialized or stale results. llvm-svn: 118800
* RABasic is nearly functionally complete. There are a few remainingAndrew Trick2010-11-101-5/+12
| | | | | | | | | benchmarks hitting an assertion. Adds LiveIntervalUnion::collectInterferingVRegs. Fixes "late spilling" by checking for any unspillable live vregs among all physReg aliases. llvm-svn: 118701
* Adds RABasic verification and tracing.Andrew Trick2010-11-091-0/+5
| | | | | | (retry now that the windows build is green) llvm-svn: 118630
* Reverting r118604. Windows build broke.Andrew Trick2010-11-091-5/+0
| | | | llvm-svn: 118613
* Adds RABasic verification and tracing.Andrew Trick2010-11-091-0/+5
| | | | llvm-svn: 118604
* Adds support for spilling previously allocated live intervals toAndrew Trick2010-11-081-3/+13
| | | | | | | | | handle cases in which a register is unavailable for spill code. Adds LiveIntervalUnion::extract. While processing interferences on a live virtual register, reuses the same Query object for each physcial reg. llvm-svn: 118423
OpenPOWER on IntegriCloud