summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocBase.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Finish moving TargetRegisterInfo::isVirtualRegister() and friends to ↵Daniel Sanders2019-08-011-2/+2
| | | | | | llvm::Register as started by r367614. NFC llvm-svn: 367633
* RegAlloc: try to fail more gracefully when out of registersNicolai Haehnle2019-05-151-6/+10
| | | | | | | | | | | | | | | | | | | | | | | Summary: The emitError path allows the program to continue, unlike report_fatal_error. This is friendlier to use cases where LLVM is embedded in a larger program, because the caller may be able to deal with the error somewhat gracefully. Change the number of requested NOP bytes in the AArch64 and PowerPC test cases to avoid triggering an unrelated assertion. The compilation still fails, as verified by the test. Change-Id: Iafb9ca341002a597b82e59ddc7a1f13c78758e3d Reviewers: arsenm, MatzeB Subscribers: qcolombet, nemanjai, wdng, javed.absar, kristof.beyls, kbarton, jsji, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61489 llvm-svn: 360786
* 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
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-6/+6
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* Rename LiveIntervalAnalysis.h to LiveIntervals.hMatthias Braun2017-12-131-1/+1
| | | | | | | | | | Headers/Implementation files should be named after the class they declare/define. Also eliminated an `#include "llvm/CodeGen/LiveIntervalAnalysis.h"` in favor of `class LiveIntarvals;` llvm-svn: 320546
* Mark all library options as hidden.Zachary Turner2017-12-011-2/+2
| | | | | | | | | | | | | | | | | These command line options are not intended for public use, and often don't even make sense in the context of a particular tool anyway. About 90% of them are already hidden, but when people add new options they forget to hide them, so if you were to make a brand new tool today, link against one of LLVM's libraries, and run tool -help you would get a bunch of junk that doesn't make sense for the tool you're writing. This patch hides these options. The real solution is to not have libraries defining command line options, but that's a much larger effort and not something I'm prepared to take on. Differential Revision: https://reviews.llvm.org/D40674 llvm-svn: 319505
* Fix a bunch more layering of CodeGen headers that are in TargetDavid Blaikie2017-11-171-1/+1
| | | | | | | | All these headers already depend on CodeGen headers so moving them into CodeGen fixes the layering (since CodeGen depends on Target, not the other way around). llvm-svn: 318490
* [CodeGen] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-09-131-3/+8
| | | | | | other minor fixes (NFC). llvm-svn: 313194
* RA: Replace asserts related to empty live intervalsMatt Arsenault2017-07-241-3/+5
| | | | | | | | | These don't exactly assert the same thing anymore, and allow empty live intervals with non-empty uses. Removed in r308808 and r308813. llvm-svn: 308906
* RA: Remove assert on empty live intervalsMatt Arsenault2017-07-211-1/+0
| | | | | | | | | This is possible if there is an undef use when splitting the vreg during spilling. Fixes bug 33620. llvm-svn: 308808
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-3/+2
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* Timer: Track name and description.Matthias Braun2016-11-181-2/+4
| | | | | | | | | | | | | 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
* Create subranges for new intervals resulting from live interval splittingKrzysztof Parzyszek2016-08-241-0/+1
| | | | | | | | | | | | | | | | | | | The register allocator can split a live interval of a register into a set of smaller intervals. After the allocation of registers is complete, the rewriter will modify the IR to replace virtual registers with the corres- ponding physical registers. At this stage, if a register corresponding to a subregister of a virtual register is used, the rewriter will check if that subregister is undefined, and if so, it will add the <undef> flag to the machine operand. The function verifying liveness of the subregis- ter would assume that it is undefined, unless any of the subranges of the live interval proves otherwise. The problem is that the live intervals created during splitting do not have any subranges, even if the original parent interval did. This could result in the <undef> flag placed on a register that is actually defined. Differential Revision: http://reviews.llvm.org/D21189 llvm-svn: 279625
* [NFC] Header cleanupMehdi Amini2016-04-181-3/+0
| | | | | | | | | | | | | | Removed some unused headers, replaced some headers with forward class declarations. Found using simple scripts like this one: clear && ack --cpp -l '#include "llvm/ADT/IndexedMap.h"' | xargs grep -L 'IndexedMap[<]' | xargs grep -n --color=auto 'IndexedMap' Patch by Eugene Kosov <claprix@yandex.ru> Differential Revision: http://reviews.llvm.org/D19219 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 266595
* Recommit r265547, and r265610,r265639,r265657 on top of it, plusWei Mi2016-04-131-0/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-9/+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/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-9/+0
| | | | | | investigate. llvm-svn: 265317
* Replace analyzeSiblingValues with new algorithm to fix its compileWei Mi2016-04-041-0/+9
| | | | | | | | | | | | | | | | | | | | | | | | | 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
* Re-sort includes with sort-includes.py and insert raw_ostream.h where it's used.Benjamin Kramer2015-03-231-0/+1
| | | | llvm-svn: 232998
* [RegAllocGreedy] Introduce a late pass to repair broken hints.Quentin Colombet2015-01-081-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Move register class name strings to a single array in MCRegisterInfo to ↵Craig Topper2014-11-171-1/+1
| | | | | | | | reduce static table size and number of relocation entries. Indices into the table are stored in each MCRegisterClass instead of a pointer. A new method, getRegClassName, is added to MCRegisterInfo and TargetRegisterInfo to lookup the string in the table. llvm-svn: 222118
* Remove unnecessary TargetMachine.h includes.Eric Christopher2014-10-141-1/+0
| | | | llvm-svn: 219672
* [Modules] Remove potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | define below all header includes in the lib/CodeGen/... tree. While the current modules implementation doesn't check for this kind of ODR violation yet, it is likely to grow support for it in the future. It also removes one layer of macro pollution across all the included headers. Other sub-trees will follow. llvm-svn: 206837
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-141-1/+1
| | | | | | instead of comparing to nullptr. llvm-svn: 206142
* Phase 1 of refactoring the MachineRegisterInfo iterators to make them suitableOwen Anderson2014-03-131-4/+9
| | | | | | | | | | | | | | | | | | | for use with C++11 range-based for-loops. The gist of phase 1 is to remove the skipInstruction() and skipBundle() methods from these iterators, instead splitting each iterator into a version that walks operands, a version that walks instructions, and a version that walks bundles. This has the result of making some "clever" loops in lib/CodeGen more verbose, but also makes their iterator invalidation characteristics much more obvious to the casual reader. (Making them concise again in the future is a good motivating case for a pre-incrementing range adapter!) Phase 2 of this undertaking with consist of removing the getOperand() method, and changing operator*() of the operand-walker to return a MachineOperand&. At that point, it should be possible to add range views for them that work as one might expect. llvm-svn: 203757
* Fix typoManman Ren2014-02-221-1/+1
| | | | llvm-svn: 201944
* DEBUG shouldEvict decisionsAndrew Trick2013-11-221-2/+2
| | | | llvm-svn: 195490
* [weak vtables] Remove a bunch of weak vtablesJuergen Ributzka2013-11-191-0/+3
| | | | | | | | | | | | 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-3/+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/+3
| | | | | | | | | | | 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
* Print register in LiveInterval::print()Matthias Braun2013-10-101-1/+1
| | | | llvm-svn: 192398
* Emit a better error when running out of registers on inline asm.Benjamin Kramer2013-10-051-3/+2
| | | | | | | | | The most likely case where this error happens is when the user specifies too many register operands. Don't make it look like an internal LLVM bug when we can see that the error is coming from an inline asm instruction. For other instructions we keep the "ran out of registers" error. llvm-svn: 192041
* Track new virtual registers by register number.Mark Lacey2013-08-141-2/+2
| | | | | | | | | | 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
* Make constant string pointer into an array to remove a pointer lookup for ↵Craig Topper2013-07-171-1/+1
| | | | | | every access. llvm-svn: 186482
* Make the LiveRegMatrix analysis available to targets.Jakob Stoklund Olesen2012-11-281-2/+2
| | | | | | | | | | | 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
* Revert r168630, r168631, and r168633 as these are causing nightly test failures.Chad Rosier2012-11-281-0/+1
| | | | llvm-svn: 168751
* Now that the X86 Maximal Stack Alignment Check pass has been removed (i.e.,Chad Rosier2012-11-261-1/+0
| | | | | | | | | r168627), we no longer need to call the freezeReservedRegs() function a second time. Previously, this pass was conservatively adding the FP to the set of reserved registers, requiring the second update to the reserved registers. rdar://12719844 llvm-svn: 168630
* Remove LiveIntervalUnions from RegAllocBase.Jakob Stoklund Olesen2012-06-201-107/+6
| | | | | | They are living in LiveRegMatrix now. llvm-svn: 158868
* Convert RABasic to using LiveRegMatrix interference checking.Jakob Stoklund Olesen2012-06-201-0/+13
| | | | | | | Stop using the LiveIntervalUnions provided by RegAllocBase, they will be removed soon. llvm-svn: 158866
* Avoid iterating with LiveIntervals::iterator.Jakob Stoklund Olesen2012-06-201-19/+25
| | | | | | | | | | That is a DenseMap iterator keyed by pointers, so the iteration order is nondeterministic. I would like to replace the DenseMap with an IndexedMap which doesn't allow iteration. llvm-svn: 158856
* Also compute MBB live-in lists in the new rewriter pass.Jakob Stoklund Olesen2012-06-091-38/+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 LiveUnionArray into LiveIntervalUnion.hJakob Stoklund Olesen2012-06-051-26/+8
| | | | | | It is useful outside RegAllocBase. llvm-svn: 158041
* Don't print register names in LiveIntervalUnion::print().Jakob Stoklund Olesen2012-06-051-1/+1
| | | | | | | | Soon we'll be making LiveIntervalUnions for register units as well. This was the only place using the RepReg member, so just remove it. llvm-svn: 158038
* Simplify LiveInterval::print().Jakob Stoklund Olesen2012-06-051-1/+1
| | | | | | | | | | Don't print out the register number and spill weight, making the TRI argument unnecessary. This allows callers to interpret the reg field. It can currently be a virtual register, a physical register, a spill slot, or a register unit. llvm-svn: 158031
* Switch all register list clients to the new MC*Iterator interface.Jakob Stoklund Olesen2012-06-011-3/+3
| | | | | | | | | | | | | No functional change intended. Sorry for the churn. The iterator classes are supposed to help avoid giant commits like this one in the future. The TableGen-produced register lists are getting quite large, and it may be necessary to change the table representation. This makes it possible to do so without changing all clients (again). llvm-svn: 157854
* Don't look for empty live ranges in the unions.Jakob Stoklund Olesen2012-05-121-1/+4
| | | | | | | | | Empty live ranges represent undef and still get allocated, but they won't appear in LiveIntervalUnions. Patch by Patrik Hägglund! llvm-svn: 156685
* Moved LiveRangeEdit.h so that it can be called from other parts of the ↵Pete Cooper2012-04-021-1/+1
| | | | | | backend, not just libCodeGen llvm-svn: 153906
* Use uint16_t to store register overlaps to reduce static data.Craig Topper2012-03-041-1/+1
| | | | llvm-svn: 152001
* Sink spillInterferences into RABasic.Jakob Stoklund Olesen2012-01-111-54/+0
| | | | | | This helper method is too simplistic for RAGreedy. llvm-svn: 147976
OpenPOWER on IntegriCloud