summaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAge
* [Modules] Remove potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-22
| | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206837 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-14
| | | | | | instead of comparing to nullptr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206142 91177308-0d34-0410-b5e6-96231b3b80d8
* [RegAllocGreedy][Last Chance Recoloring] Change the name of the exhaustive ↵Quentin Colombet2014-04-11
| | | | | | | | | | | | search option. fexhaustive-register-search => exhaustive-register-search 'f' is a Clang thing! This is related to PR18747. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206075 91177308-0d34-0410-b5e6-96231b3b80d8
* [RegAllocGreedy][Last Chance Recoloring] Addition ofQuentin Colombet2014-04-11
| | | | | | | | | | | | -fexhaustive-register-search option to allow an exhaustive search during last chance recoloring. This is related to PR18747 Patch by MAYUR PANDEY <mayur.p@samsung.com>. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206072 91177308-0d34-0410-b5e6-96231b3b80d8
* RegAlloc: Account for a variable entry block frequencyDuncan P. N. Exon Smith2014-04-08
| | | | | | | | | | | | | | | | | | | | Until r197284, the entry frequency was constant -- i.e., set to 2^14. Although current ToT still has a constant entry frequency, since r197284 that has been an implementation detail (which is soon going to change). - r204690 made the wrong assumption for the CSRCost metric. Adjust callee-saved register cost based on entry frequency. - r185393 made the wrong assumption (although it was valid at the time). Update SpillPlacement.cpp::Threshold to be relative to the entry frequency. Since ToT still has 2^14 entry frequency, this should have no observable functionality change. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@205789 91177308-0d34-0410-b5e6-96231b3b80d8
* [RegAllocGreedy][Last Chance Recoloring] Emit diagnostics when last chanceQuentin Colombet2014-04-04
| | | | | | | | | | | recoloring cut-offs are encountered and register allocation failed. This is related to PR18747 Patch by MAYUR PANDEY <mayur.p@samsung.com>. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@205601 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert r205599, the commit was not intended to have so many changesQuentin Colombet2014-04-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@205600 91177308-0d34-0410-b5e6-96231b3b80d8
* [RegAllocGreedy][Last Chance Recoloring] Emit diagnostics when last chanceQuentin Colombet2014-04-04
| | | | | | | | | | | recoloring cut-offs are hit. This is related to PR18747. Patch by MAYUR PANDEY <mayur.p@samsung.com> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@205599 91177308-0d34-0410-b5e6-96231b3b80d8
* Provide a target override for the cost of using a callee-saved registerManman Ren2014-03-27
| | | | | | | | | | for the first time. Thanks Andy for the discussion. rdar://16162005 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@204979 91177308-0d34-0410-b5e6-96231b3b80d8
* Register Allocator: refactoring and add comments.Manman Ren2014-03-27
| | | | | | | | | No functionality change. Thanks Andy for reviewing. rdar://16162005 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@204962 91177308-0d34-0410-b5e6-96231b3b80d8
* Add comments. Addressing review comments from Evan on r204690.Manman Ren2014-03-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@204864 91177308-0d34-0410-b5e6-96231b3b80d8
* Register Allocator: check other options before using a CSR for the first time.Manman Ren2014-03-25
| | | | | | | | | | | | | | | | | | | | When register allocator's stage is RS_Spill, we choose spill over using the CSR for the first time, if the spill cost is lower than CSRCost. When register allocator's stage is < RS_Split, we choose pre-splitting over using the CSR for the first time, if the cost of splitting is lower than CSRCost. CSRCost is set with command-line option "regalloc-csr-first-time-cost". The default value is 0 to generate the same codes as before this commit. With a value of 15 (1 << 14 is the entry frequency), I measured performance gain of 3% on 253.perlbmk and 1.7% on 197.parser, with instrumented PGO, on an arm device. rdar://16162005 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@204690 91177308-0d34-0410-b5e6-96231b3b80d8
* Register Allocator: refactoring (no functionality change).Manman Ren2014-03-24
| | | | | | | | | | Factor out two functions calculateRegionSplitCost and doRegionSplit from tryRegionSplit. These two functions will be used in coming patches. rdar://16162005 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@204684 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-07
| | | | | | class. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@203220 91177308-0d34-0410-b5e6-96231b3b80d8
* Replace OwningPtr<T> with std::unique_ptr<T>.Ahmed Charles2014-03-06
| | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@203083 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Use std::tie to simplify compare operators.Benjamin Kramer2014-03-03
| | | | | | No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202751 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Expand and eliminate the LLVM_ENUM_INT_TYPE() macroAlp Toker2014-03-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202607 91177308-0d34-0410-b5e6-96231b3b80d8
* Provide a target override for the latest regalloc heuristic.Andrew Trick2014-02-27
| | | | | | | This is a temporary workaround for native arm linux builds: PR18996: Changing regalloc order breaks "lencod" on native arm linux builds. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202433 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a limit to the heuristic that register allocates instructions in local ↵Andrew Trick2014-02-26
| | | | | | | | | | | | order. This handles pathological cases in which we see 2x increase in spill code for large blocks (~50k instructions). I don't have a unit test for this behavior. Fixes rdar://16072279. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202304 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove outdated comments.Manman Ren2014-02-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202186 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix typosAlp Toker2014-02-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202107 91177308-0d34-0410-b5e6-96231b3b80d8
* [RegAlloc] Fix the assertion in the last chance recoloring to match theQuentin Colombet2014-02-13
| | | | | | | condition at the call site. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201296 91177308-0d34-0410-b5e6-96231b3b80d8
* [RegAlloc] Add a last chance recoloring mechanism when everything else failed toQuentin Colombet2014-02-05
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | find a register. The idea is to choose a color for the variable that cannot be allocated and recolor its interferences around. Unlike the current register allocation scheme, it is allowed to change the color of an already assigned (but maybe not splittable or spillable) live interval while propagating this change to its neighbors. In other word, there are two things that may help finding an available color: - Already assigned variables (RS_Done) can be recolored to different color. - The recoloring allows to catch solutions that needs to touch more that just the neighbors of the current allocated variable. E.g., vA can use {R1, R2 } vB can use { R2, R3} vC can use {R1 } Where vA, vB, and vC cannot be split anymore (they are reloads for instance) and they all interfere. vA is assigned R1 vB is assigned R2 vC tries to evict vA but vA is already done. => Regular register allocation heuristic fails. Last chance recoloring kicks in: vC does as if vA was evicted => vC uses R1. vC is marked as fixed. vA needs to find a color. None are available. vA cannot evict vC: vC is a fixed virtual register now. vA does as if vB was evicted => vA uses R2. vB needs to find a color. R3 is available. Recoloring => vC = R1, vA = R2, vB = R3. <rdar://problem/15947839> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@200883 91177308-0d34-0410-b5e6-96231b3b80d8
* RegAllocGreedy.cpp: Use more simple value as Hysteresis, to suppress ↵NAKAMURA Takumi2014-02-04
| | | | | | -mfpmath-dependent behavior. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@200738 91177308-0d34-0410-b5e6-96231b3b80d8
* [RegAlloc] Make tryInstructionSplit less aggressive.Quentin Colombet2014-01-02
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The greedy register allocator tries to split a live-range around each instruction where it is used or defined to relax the constraints on the entire live-range (this is a last chance split before falling back to spill). The goal is to have a big live-range that is unconstrained (i.e., that can use the largest legal register class) and several small local live-range that carry the constraints implied by each instruction. E.g., Let csti be the constraints on operation i. V1= op1 V1(cst1) op2 V1(cst2) V1 live-range is constrained on the intersection of cst1 and cst2. tryInstructionSplit relaxes those constraints by aggressively splitting each def/use point: V1= V2 = V1 V3 = V2 op1 V3(cst1) V4 = V2 op2 V4(cst2) Because of how the coalescer infrastructure works, each new variable (V3, V4) that is alive at the same time as V1 (or its copy, here V2) interfere with V1. Thus, we end up with an uncoalescable copy for each split point. To make tryInstructionSplit less aggressive, we check if the split point actually relaxes the constraints on the whole live-range. If it does not, we do not insert it. Indeed, it will not help the global allocation problem: - V1 will have the same constraints. - V1 will have the same interference + possibly the newly added split variable VS. - VS will produce an uncoalesceable copy if alive at the same time as V1. <rdar://problem/15570057> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@198369 91177308-0d34-0410-b5e6-96231b3b80d8
* [block-freq] Rename getEntryFrequency() -> getEntryFreq() to match ↵Michael Gottesman2013-12-14
| | | | | | getBlockFreq() in all *BlockFrequencyInfo*. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@197304 91177308-0d34-0410-b5e6-96231b3b80d8
* [block-freq] Update MachineBlockPlacement and RegAllocGreedy to use the new ↵Michael Gottesman2013-12-14
| | | | | | MachineBlockFrequencyInfo methods. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@197290 91177308-0d34-0410-b5e6-96231b3b80d8
* Add TargetRegisterInfo::reverseLocalAssignment hook.Andrew Trick2013-12-11
| | | | | | | | | | | | | | This hook reverses the order of assignment for local live ranges. This will generally allocate shorter local live ranges first. For targets with many registers, this could reduce regalloc compile time by a large factor. It should still achieve optimal coloring; however, it can change register eviction decisions. It is disabled by default for two reasons: (1) Top-down allocation is simpler and easier to debug for targets that don't benefit from reversing the order. (2) Bottom-up allocation could result in poor evicition decisions on some targets affecting the performance of compiled code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@197001 91177308-0d34-0410-b5e6-96231b3b80d8
* Check hint registers for interference only once before evictionsAditya Nandakumar2013-12-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@196536 91177308-0d34-0410-b5e6-96231b3b80d8
* Reverse the order of eviction checks for possible compile time savings. No ↵Andrew Trick2013-11-29
| | | | | | functionality. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@195969 91177308-0d34-0410-b5e6-96231b3b80d8
* DEBUG shouldEvict decisionsAndrew Trick2013-11-22
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@195490 91177308-0d34-0410-b5e6-96231b3b80d8
* Minor cleanup. EvictionCost ctor was confusing relative to the other costs ↵Andrew Trick2013-11-22
| | | | | | floating around in the code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@195489 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixed an extra for(typo) in the commentsAditya Nandakumar2013-11-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@195171 91177308-0d34-0410-b5e6-96231b3b80d8
* Replacing HUGE_VALF with llvm::huge_valf in order to work around a warning ↵Aaron Ballman2013-11-13
| | | | | | | | triggered in MSVC 12. Patch reviewed by Reid Kleckner and Jim Grosbach. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194533 91177308-0d34-0410-b5e6-96231b3b80d8
* CalcSpillWeights: give a better describing name to calculateSpillWeightsArnaud A. de Grandmaison2013-11-11
| | | | | | | | Besides, this relates it more obviously to the VirtRegAuxInfo::calculateSpillWeightAndHint. No functionnal change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194404 91177308-0d34-0410-b5e6-96231b3b80d8
* CalculateSpillWeights does not need to be a passArnaud A. de Grandmaison2013-11-10
| | | | | | | | | | Based on discussions with Lang Hames and Jakob Stoklund Olesen at the hacker's lab, and in the light of upcoming work on the PBQP register allocator, it was though that CalcSpillWeights does not need to be a pass. This change will enable to customize / tune the spill weight computation depending on the allocator. Update the documentation style while there. No functionnal change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194356 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "CalculateSpillWeights does not need to be a pass"Arnaud A. de Grandmaison2013-11-08
| | | | | | Temporarily revert my previous commit until I understand why it breaks 3 target tests. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194272 91177308-0d34-0410-b5e6-96231b3b80d8
* CalculateSpillWeights does not need to be a passArnaud A. de Grandmaison2013-11-08
| | | | | | | | | | Based on discussions with Lang Hames and Jakob Stoklund Olesen at the hacker's lab, and in the light of upcoming work on the PBQP register allocator, it was though that CalcSpillWeights does not need to be a pass. This change will enable to customize / tune the spill weight computation depending on the allocator. Update the documentation style while there. No functionnal change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194269 91177308-0d34-0410-b5e6-96231b3b80d8
* Represent RegUnit liveness with LiveRange instanceMatthias Braun2013-10-10
| | | | | | | Previously LiveInterval has been used, but having a spill weight and register number is unnecessary for a register unit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192397 91177308-0d34-0410-b5e6-96231b3b80d8
* Explicitly request unsigned enum types when desiredReid Kleckner2013-10-08
| | | | | | | This fixes repeated -Wmicrosoft warnings when self-hosting clang on Windows, and gets us real unsigned enum types with MSVC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192227 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix unused variables.Eli Friedman2013-09-10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190448 91177308-0d34-0410-b5e6-96231b3b80d8
* Track new virtual registers by register number.Mark Lacey2013-08-14
| | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188434 91177308-0d34-0410-b5e6-96231b3b80d8
* Down-scale slot index distance to save bits.Andrew Trick2013-07-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187438 91177308-0d34-0410-b5e6-96231b3b80d8
* RegAllocGreedy comment.Andrew Trick2013-07-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187141 91177308-0d34-0410-b5e6-96231b3b80d8
* Evict local live ranges if they can be reassigned.Andrew Trick2013-07-25
| | | | | | | | | | | | | | | | The previous change to local live range allocation also suppressed eviction of local ranges. In rare cases, this could result in more expensive register choices. This commit actually revives a feature that I added long ago: check if live ranges can be reassigned before eviction. But now it only happens in rare cases of evicting a local live range because another local live range wants a cheaper register. The benefit is improved code size for some benchmarks on x86 and armv7. I measured no significant compile time increase and performance changes are noise. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187140 91177308-0d34-0410-b5e6-96231b3b80d8
* Allocate local registers in order for optimal coloring.Andrew Trick2013-07-25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Also avoid locals evicting locals just because they want a cheaper register. Problem: MI Sched knows exactly how many registers we have and assumes they can be colored. In cases where we have large blocks, usually from unrolled loops, greedy coloring fails. This is a source of "regressions" from the MI Scheduler on x86. I noticed this issue on x86 where we have long chains of two-address defs in the same live range. It's easy to see this in matrix multiplication benchmarks like IRSmk and even the unit test misched-matmul.ll. A fundamental difference between the LLVM register allocator and conventional graph coloring is that in our model a live range can't discover its neighbors, it can only verify its neighbors. That's why we initially went for greedy coloring and added eviction to deal with the hard cases. However, for singly defined and two-address live ranges, we can optimally color without visiting neighbors simply by processing the live ranges in instruction order. Other beneficial side effects: It is much easier to understand and debug regalloc for large blocks when the live ranges are allocated in order. Yes, global allocation is still very confusing, but it's nice to be able to comprehend what happened locally. Heuristics could be added to bias register assignment based on instruction locality (think late register pairing, banks...). Intuituvely this will make some test cases that are on the threshold of register pressure more stable. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187139 91177308-0d34-0410-b5e6-96231b3b80d8
* Dump LIS before regalloc. MI sched changes them.Andrew Trick2013-07-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187107 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove floats from live range splitting costs.Jakob Stoklund Olesen2013-07-16
| | | | | | | | | | These floats all represented block frequencies anyway, so just use the BlockFrequency class directly. Some floating point computations remain in tryLocalSplit(). They are estimating spill weights which are still floats. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186435 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.Benjamin Kramer2013-06-17
| | | | | | | | | | | | | | | | | | The main advantages here are way better heuristics, taking into account not just loop depth but also __builtin_expect and other static heuristics and will eventually learn how to use profile info. Most of the work in this patch is pushing the MachineBlockFrequencyInfo analysis into the right places. This is good for a 5% speedup on zlib's deflate (x86_64), there were some very unfortunate spilling decisions in its hottest loop in longest_match(). Other benchmarks I tried were mostly neutral. This changes register allocation in subtle ways, update the tests for it. 2012-02-20-MachineCPBug.ll was deleted as it's very fragile and the instruction it looked for was gone already (but the FileCheck pattern picked up unrelated stuff). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@184105 91177308-0d34-0410-b5e6-96231b3b80d8
* Use only explicit bool conversion operatorsDavid Blaikie2013-05-15
| | | | | | | | | | | | | | | | | | | | | | | BitVector/SmallBitVector::reference::operator bool remain implicit since they model more exactly a bool, rather than something else that can be boolean tested. The most common (non-buggy) case are where such objects are used as return expressions in bool-returning functions or as boolean function arguments. In those cases I've used (& added if necessary) a named function to provide the equivalent (or sometimes negative, depending on convenient wording) test. One behavior change (YAMLParser) was made, though no test case is included as I'm not sure how to reach that code path. Essentially any comparison of llvm::yaml::document_iterators would be invalid if neither iterator was at the end. This helped uncover a couple of bugs in Clang - test cases provided for those in a separate commit along with similar changes to `operator bool` instances in Clang. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181868 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-28 21:47:12 +0000