summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveIntervalUnion.cpp
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
* Report fatal error in the case of out of memorySerge Pavlov2018-02-201-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is the second part of recommit of r325224. The previous part was committed in r325426, which deals with C++ memory allocation. Solution for C memory allocation involved functions `llvm::malloc` and similar. This was a fragile solution because it caused ambiguity errors in some cases. In this commit the new functions have names like `llvm::safe_malloc`. The relevant part of original comment is below, updated for new function names. Analysis of fails in the case of out of memory errors can be tricky on Windows. Such error emerges at the point where memory allocation function fails, but manifests itself when null pointer is used. These two points may be distant from each other. Besides, next runs may not exhibit allocation error. In some cases memory is allocated by a call to some of C allocation functions, malloc, calloc and realloc. They are used for interoperability with C code, when allocated object has variable size and when it is necessary to avoid call of constructors. In many calls the result is not checked for null pointer. To simplify checks, new functions are defined in the namespace 'llvm': `safe_malloc`, `safe_calloc` and `safe_realloc`. They behave as corresponding standard functions but produce fatal error if allocation fails. This change replaces the standard functions like 'malloc' in the cases when the result of the allocation function is not checked for null pointer. Finally, there are plain C code, that uses malloc and similar functions. If the result is not checked, assert statement is added. Differential Revision: https://reviews.llvm.org/D43010 llvm-svn: 325551
* Revert r325224 "Report fatal error in the case of out of memory"Serge Pavlov2018-02-151-1/+1
| | | | | | It caused fails on some buildbots. llvm-svn: 325227
* Report fatal error in the case of out of memorySerge Pavlov2018-02-151-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Analysis of fails in the case of out of memory errors can be tricky on Windows. Such error emerges at the point where memory allocation function fails, but manifests itself when null pointer is used. These two points may be distant from each other. Besides, next runs may not exhibit allocation error. Usual programming practice does not require checking result of 'operator new' because it throws 'std::bad_alloc' in the case of allocation error. However, LLVM is usually built with exceptions turned off, so 'new' can return null pointer. This change installs custom new handler, which causes fatal error in the case of out of memory. The handler is installed automatically prior to call to 'main' during construction of a static object defined in 'lib/Support/ErrorHandling.cpp'. If the application does not use this file, the handler may be installed manually by a call to 'llvm::install_out_of_memory_new_handler', declared in 'include/llvm/Support/ErrorHandling.h". There are calls to C allocation functions, malloc, calloc and realloc. They are used for interoperability with C code, when allocated object has variable size and when it is necessary to avoid call of constructors. In many calls the result is not checked against null pointer. To simplify checks, new functions are defined in the namespace 'llvm' with the same names as these C function. These functions produce fatal error if allocation fails. User should use 'llvm::malloc' instead of 'std::malloc' in order to use the safe variant. This change replaces 'std::malloc' in the cases when the result of allocation function is not checked against null pointer. Finally, there are plain C code, that uses malloc and similar functions. If the result is not checked, assert statements are added. Differential Revision: https://reviews.llvm.org/D43010 llvm-svn: 325224
* [CodeGen] Rename functions PrintReg* to printReg*Francis Visoiu Mistrih2017-11-281-1/+1
| | | | | | | | | | | LLVM Coding Standards: Function names should be verb phrases (as they represent actions), and command-like function should be imperative. The name should be camel case, and start with a lower case letter (e.g. openFile() or isFoo()). Differential Revision: https://reviews.llvm.org/D40416 llvm-svn: 319168
* 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
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-2/+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
* LIU:::Query: Query LiveRange instead of LiveInterval; NFCMatthias Braun2017-03-011-14/+13
| | | | | | | | | - We only need the information from the base class, not the additional details in the LiveInterval class. - Spread more `const` - Some code cleanup llvm-svn: 296684
* [CodeGen] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-02-171-7/+7
| | | | | | other minor fixes (NFC). llvm-svn: 295499
* Use the range variant of find instead of unpacking begin/endDavid Majnemer2016-08-111-3/+2
| | | | | | | | | If the result of the find is only used to compare against end(), just use is_contained instead. No functionality change is intended. llvm-svn: 278433
* LiveIntervalUnion: Allow specification of liverange when unifying/extracting.Matthias Braun2014-12-101-9/+9
| | | | | | This allows it to add subregister ranges into the union. llvm-svn: 223890
* [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-2/+2
| | | | | | instead of comparing to nullptr. llvm-svn: 206142
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-1/+0
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* 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 unused MachineLoopRanges analysis.Jakub Staszak2012-11-271-28/+0
| | | | llvm-svn: 168659
* Move LiveUnionArray into LiveIntervalUnion.hJakob Stoklund Olesen2012-06-051-0/+23
| | | | | | It is useful outside RegAllocBase. llvm-svn: 158041
* Don't print register names in LiveIntervalUnion::print().Jakob Stoklund Olesen2012-06-051-1/+0
| | | | | | | | 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
* Oops - LiveIntervalUnion.cpp file does use std::find. Moving STL header ↵Lang Hames2011-12-211-0/+2
| | | | | | include to LiveIntervalUnion.cpp file. llvm-svn: 147089
* Simplify the interference checking code a bit.Jakob Stoklund Olesen2011-08-121-109/+42
| | | | | | | This is possible now that we now longer provide an interface to iterate the interference overlaps. llvm-svn: 137397
* Eliminate the last use of InterferenceResult.Jakob Stoklund Olesen2011-08-111-60/+54
| | | | | | | | The Query class now holds two iterators instead of an InterferenceResult instance. The iterators are used as bookmarks for repeated collectInterferingVRegs calls. llvm-svn: 137380
* Remove more dead code.Jakob Stoklund Olesen2011-08-111-26/+2
| | | | | | | collectInterferingVRegs will be the primary function for interference checks. llvm-svn: 137354
* Remove some dead code.Jakob Stoklund Olesen2011-08-111-19/+0
| | | | | | | | The InterferenceResult iterator turned out to be less important than we thought it would be. LiveIntervalUnion clients want higher level information, like the list of interfering virtual registers. llvm-svn: 137346
* Be more aggressive about following hints.Jakob Stoklund Olesen2011-07-081-5/+1
| | | | | | | | | | | | | | | | | | | | RAGreedy::tryAssign will now evict interference from the preferred register even when another register is free. To support this, add the EvictionCost struct that counts how many hints are broken by an eviction. We don't want to break one hint just to satisfy another. Rename canEvict to shouldEvict, and add the first bit of eviction policy that doesn't depend on spill weights: Always make room in the preferred register as long as the evictees can be split and aren't already assigned to their preferred register. Also make the CSR avoidance more accurate. When looking for a cheaper register it is OK to use a new volatile register. Only CSR aliases that have never been used before should be avoided. llvm-svn: 134735
* Speed up eviction by stopping collectInterferingVRegs as soon as the spillJakob Stoklund Olesen2011-04-111-3/+9
| | | | | | weight limit has been exceeded. llvm-svn: 129305
* Speed up LiveIntervalUnion::unify by handling end insertion specially.Jakob Stoklund Olesen2011-04-111-1/+9
| | | | | | This particularly helps with the initial transfer of fixed intervals. llvm-svn: 129277
* Add tags to live interval unions to avoid using stale queries.Jakob Stoklund Olesen2011-02-091-0/+2
| | | | | | | The tag is updated whenever the live interval union is changed, and it is tested before using cached information. llvm-svn: 125224
* Replace TargetRegisterInfo::printReg with a PrintReg class that also works ↵Jakob Stoklund Olesen2011-01-091-6/+5
| | | | | | | | | | without a TRI instance. Print virtual registers numbered from 0 instead of the arbitrary FirstVirtualRegister. The first virtual register is printed as %vreg0. TRI::NoRegister is printed as %noreg. llvm-svn: 123107
* Avoid dereferencing end() in collectInterferingVRegs() when there is noJakob Stoklund Olesen2010-12-171-1/+1
| | | | | | interference. llvm-svn: 122108
* Provide LiveIntervalUnion::Query::checkLoopInterference.Jakob Stoklund Olesen2010-12-171-0/+28
| | | | | | | | This is a three-way interval list intersection between a virtual register, a live interval union, and a loop. It will be used to identify interference-free loops for live range splitting. llvm-svn: 122034
* Start using SplitKit and MachineLoopRanges in RegAllocGreedy in preparation ofJakob Stoklund Olesen2010-12-151-2/+2
| | | | | | | | live range splitting around loops guided by register pressure. So far, trySplit() simply prints a lot of debug output. llvm-svn: 121918
* Add LiveIntervalUnion print methods, RegAllocGreedy::trySplit debug spew.Jakob Stoklund Olesen2010-12-141-3/+24
| | | | llvm-svn: 121783
* Use TRI::printReg instead of AbstractRegisterDescription when printingJakob Stoklund Olesen2010-12-141-13/+8
| | | | | | LiveIntervalUnions. llvm-svn: 121781
* Add a forgotten initializer for CheckedFirstInterference.Jakob Stoklund Olesen2010-12-091-0/+2
| | | | llvm-svn: 121410
* Added register reassignment prototype to RAGreedy. It's a simpleAndrew Trick2010-12-091-1/+4
| | | | | | | heuristic to reshuffle register assignments when we can't find an available reg. llvm-svn: 121388
* IntervalMap iterators are heavyweight, so avoid copying them around and useJakob Stoklund Olesen2010-12-091-3/+20
| | | | | | | | | | | references instead. Similarly, IntervalMap::begin() is almost as expensive as find(), so use find(x) instead of begin().advanceTo(x); This makes RegAllocBasic run another 5% faster. llvm-svn: 121344
* Properly deal with empty intervals when checking for interference.Jakob Stoklund Olesen2010-12-081-1/+2
| | | | llvm-svn: 121319
* Switch LiveIntervalUnion from std::set to IntervalMap.Jakob Stoklund Olesen2010-12-071-127/+58
| | | | | | | This speeds up RegAllocBasic by 20%, not counting releaseMemory which becomes way faster. llvm-svn: 121201
* Comment typo.Andrew Trick2010-11-301-1/+1
| | | | llvm-svn: 120504
* Coding style. No significant functionality. Abandon linear scan styleAndrew Trick2010-11-301-154/+178
| | | | | | | | 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
* RABasic is nearly functionally complete. There are a few remainingAndrew Trick2010-11-101-1/+71
| | | | | | | | | 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-5/+47
| | | | | | (retry now that the windows build is green) llvm-svn: 118630
* Reverting r118604. Windows build broke.Andrew Trick2010-11-091-46/+5
| | | | llvm-svn: 118613
* Adds RABasic verification and tracing.Andrew Trick2010-11-091-5/+46
| | | | llvm-svn: 118604
* Adds support for spilling previously allocated live intervals toAndrew Trick2010-11-081-41/+57
| | | | | | | | | 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
* Remove the vector of live vregs. I thought we would need to trackAndrew Trick2010-10-261-5/+0
| | | | | | | them, but hopefully we won't. And this is not the right data structure to do it anyway. llvm-svn: 117412
* Jakob's review of the basic register allocator.Andrew Trick2010-10-261-14/+16
| | | | llvm-svn: 117384
* Fix a likely bug in an assertion by adding parentheses around '||'. This bugChandler Carruth2010-10-231-1/+1
| | | | | | was found by a GCC warning. ;] llvm-svn: 117199
* This is a prototype of an experimental register allocationAndrew Trick2010-10-221-0/+167
framework. It's purpose is not to improve register allocation per se, but to make it easier to develop powerful live range splitting. I call it the basic allocator because it is as simple as a global allocator can be but provides the building blocks for sophisticated register allocation with live range splitting. A minimal implementation is provided that trivially spills whenever it runs out of registers. I'm checking in now to get high-level design and style feedback. I've only done minimal testing. The next step is implementing a "greedy" allocation algorithm that does some register reassignment and makes better splitting decisions. llvm-svn: 117174
OpenPOWER on IntegriCloud