summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [RegAllocGreedy] Introduce a late pass to repair broken hints.Quentin Colombet2015-01-081-2/+207
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [PBQP] Tweak spill costs and coalescing benefitsArnaud A. de Grandmaison2014-11-041-3/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch improves how the different costs (register, interference, spill and coalescing) relates together. The assumption is now that: - coalescing (or any other "side effect" of reg alloc) is negative, and instead of being derived from a spill cost, they use the block frequency info. - spill costs are in the [MinSpillCost:+inf( range - register or interference costs are in [0.0:MinSpillCost( or +inf The current MinSpillCost is set to 10.0, which is a random value high enough that the current constraint builders do not need to worry about when settings costs. It would however be worth adding a normalization step for register and interference costs as the last step in the constraint builder chain to ensure they are not greater than SpillMinCost (unless this has some sense for some architectures). This would work well with the current builder pipeline, where all costs are tweaked relatively to each others, but could grow above MinSpillCost if the pipeline is deep enough. The current heuristic is tuned to depend rather on the number of uses of a live interval rather than a density of uses, as used by the greedy allocator. This heuristic provides a few percent improvement on a number of benchmarks (eembc, spec, ...) and will definitely need to change once spill placement is implemented: the current spill placement is really ineficient, so making the cost proportionnal to the number of use is a clear win. llvm-svn: 221292
* Grab the subtarget and subtarget dependent variables off ofEric Christopher2014-10-141-4/+4
| | | | | | MachineFunction rather than TargetMachine. llvm-svn: 219671
* Revert 202433 - Provide a target override for the latest regalloc heuristicRenato Golin2014-10-031-1/+1
| | | | | | | | | | | That commit was introduced in order to help investigate a problem in ARM codegen breaking from commit 202304 (Add a limit to the heuristic that register allocates instructions in local order). Recent analisys indicated that the problem no longer exists, so I'm reverting this change. See PR18996. llvm-svn: 218981
* Simplify creation of a bunch of ArrayRefs by using None, makeArrayRef or ↵Craig Topper2014-08-271-5/+3
| | | | | | just letting them be implicitly created. llvm-svn: 216525
* Remove the TargetMachine forwards for TargetSubtargetInfo basedEric Christopher2014-08-041-2/+2
| | | | | | information and update all callers. No functional change. llvm-svn: 214781
* Remove uses of the redundant ".reset(nullptr)" of unique_ptr, in favor of ↵David Blaikie2014-07-191-1/+1
| | | | | | | | | | | ".reset()" It's also possible to just write "= nullptr", but there's some question of whether that's as readable, so I leave it up to authors to pick which they prefer for now. If we want to discuss standardizing on one or the other, we can do that at some point in the future. llvm-svn: 213438
* [RegAllocGreedy] Provide a subtarget hook to disable the local reassignmentQuentin Colombet2014-07-021-4/+14
| | | | | | | | | | | | heuristic. By default, no functionality change. This is a follow-up of r212099. This hook provides a finer grain to control the optimization. <rdar://problem/17444599> llvm-svn: 212204
* [RegAllocGreedy] Provide a flag to disable the local reassignment heuristic.Quentin Colombet2014-07-011-1/+7
| | | | | | | | | | | | | | | | | | | | | | By default, no functionality change. Before evicting a local variable, this heuristic tries to find another (set of) local(s) that can be reassigned to a free color. In some extreme cases (large basic blocks with tons of local variables), the compilation time is dominated by the local interference checks that this heuristic must perform, with no code gen gain. E.g., the motivating example takes 4 minutes to compile with this heuristic, 12 seconds without. Improving the situation will likely require to make drastic changes to the register allocator and/or the interference check framework. For now, provide this flag to better understand the impact of that heuristic. <rdar://problem/17444599> llvm-svn: 212099
* [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
* [RegAllocGreedy][Last Chance Recoloring] Change the name of the exhaustive ↵Quentin Colombet2014-04-111-1/+1
| | | | | | | | | | | search option. fexhaustive-register-search => exhaustive-register-search 'f' is a Clang thing! This is related to PR18747. llvm-svn: 206075
* [RegAllocGreedy][Last Chance Recoloring] Addition ofQuentin Colombet2014-04-111-6/+14
| | | | | | | | | | | -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>. llvm-svn: 206072
* RegAlloc: Account for a variable entry block frequencyDuncan P. N. Exon Smith2014-04-081-9/+36
| | | | | | | | | | | | | | | | | | | | 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> llvm-svn: 205789
* [RegAllocGreedy][Last Chance Recoloring] Emit diagnostics when last chanceQuentin Colombet2014-04-041-1/+35
| | | | | | | | | | recoloring cut-offs are encountered and register allocation failed. This is related to PR18747 Patch by MAYUR PANDEY <mayur.p@samsung.com>. llvm-svn: 205601
* Revert r205599, the commit was not intended to have so many changesQuentin Colombet2014-04-041-35/+1
| | | | llvm-svn: 205600
* [RegAllocGreedy][Last Chance Recoloring] Emit diagnostics when last chanceQuentin Colombet2014-04-041-1/+35
| | | | | | | | | | recoloring cut-offs are hit. This is related to PR18747. Patch by MAYUR PANDEY <mayur.p@samsung.com> llvm-svn: 205599
* Provide a target override for the cost of using a callee-saved registerManman Ren2014-03-271-2/+6
| | | | | | | | | for the first time. Thanks Andy for the discussion. rdar://16162005 llvm-svn: 204979
* Register Allocator: refactoring and add comments.Manman Ren2014-03-271-35/+58
| | | | | | | | No functionality change. Thanks Andy for reviewing. rdar://16162005 llvm-svn: 204962
* Add comments. Addressing review comments from Evan on r204690.Manman Ren2014-03-261-0/+5
| | | | llvm-svn: 204864
* Register Allocator: check other options before using a CSR for the first time.Manman Ren2014-03-251-6/+57
| | | | | | | | | | | | | | | | | | | 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 llvm-svn: 204690
* Register Allocator: refactoring (no functionality change).Manman Ren2014-03-241-6/+30
| | | | | | | | | Factor out two functions calculateRegionSplitCost and doRegionSplit from tryRegionSplit. These two functions will be used in coming patches. rdar://16162005 llvm-svn: 204684
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-071-12/+11
| | | | | | class. llvm-svn: 203220
* Replace OwningPtr<T> with std::unique_ptr<T>.Ahmed Charles2014-03-061-3/+3
| | | | | | | | | | 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
* [C++11] Use std::tie to simplify compare operators.Benjamin Kramer2014-03-031-3/+2
| | | | | | No functionality change. llvm-svn: 202751
* [C++11] Expand and eliminate the LLVM_ENUM_INT_TYPE() macroAlp Toker2014-03-021-1/+1
| | | | llvm-svn: 202607
* Provide a target override for the latest regalloc heuristic.Andrew Trick2014-02-271-1/+1
| | | | | | | This is a temporary workaround for native arm linux builds: PR18996: Changing regalloc order breaks "lencod" on native arm linux builds. llvm-svn: 202433
* Add a limit to the heuristic that register allocates instructions in local ↵Andrew Trick2014-02-261-2/+8
| | | | | | | | | | | | 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. llvm-svn: 202304
* Remove outdated comments.Manman Ren2014-02-251-1/+1
| | | | llvm-svn: 202186
* Fix typosAlp Toker2014-02-251-1/+1
| | | | llvm-svn: 202107
* [RegAlloc] Fix the assertion in the last chance recoloring to match theQuentin Colombet2014-02-131-1/+1
| | | | | | condition at the call site. llvm-svn: 201296
* [RegAlloc] Add a last chance recoloring mechanism when everything else failed toQuentin Colombet2014-02-051-8/+263
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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> llvm-svn: 200883
* RegAllocGreedy.cpp: Use more simple value as Hysteresis, to suppress ↵NAKAMURA Takumi2014-02-041-1/+1
| | | | | | -mfpmath-dependent behavior. llvm-svn: 200738
* [RegAlloc] Make tryInstructionSplit less aggressive.Quentin Colombet2014-01-021-3/+37
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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> llvm-svn: 198369
* [block-freq] Rename getEntryFrequency() -> getEntryFreq() to match ↵Michael Gottesman2013-12-141-1/+1
| | | | | | getBlockFreq() in all *BlockFrequencyInfo*. llvm-svn: 197304
* [block-freq] Update MachineBlockPlacement and RegAllocGreedy to use the new ↵Michael Gottesman2013-12-141-4/+7
| | | | | | MachineBlockFrequencyInfo methods. llvm-svn: 197290
* Add TargetRegisterInfo::reverseLocalAssignment hook.Andrew Trick2013-12-111-1/+8
| | | | | | | | | | | | | | 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. llvm-svn: 197001
* Check hint registers for interference only once before evictionsAditya Nandakumar2013-12-051-1/+1
| | | | llvm-svn: 196536
* Reverse the order of eviction checks for possible compile time savings. No ↵Andrew Trick2013-11-291-3/+3
| | | | | | functionality. llvm-svn: 195969
* DEBUG shouldEvict decisionsAndrew Trick2013-11-221-1/+5
| | | | llvm-svn: 195490
* Minor cleanup. EvictionCost ctor was confusing relative to the other costs ↵Andrew Trick2013-11-221-3/+9
| | | | | | floating around in the code. llvm-svn: 195489
* Fixed an extra for(typo) in the commentsAditya Nandakumar2013-11-191-1/+1
| | | | llvm-svn: 195171
* Replacing HUGE_VALF with llvm::huge_valf in order to work around a warning ↵Aaron Ballman2013-11-131-3/+3
| | | | | | | | triggered in MSVC 12. Patch reviewed by Reid Kleckner and Jim Grosbach. llvm-svn: 194533
* CalcSpillWeights: give a better describing name to calculateSpillWeightsArnaud A. de Grandmaison2013-11-111-1/+1
| | | | | | | | Besides, this relates it more obviously to the VirtRegAuxInfo::calculateSpillWeightAndHint. No functionnal change. llvm-svn: 194404
* CalculateSpillWeights does not need to be a passArnaud A. de Grandmaison2013-11-101-2/+2
| | | | | | | | | | 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. llvm-svn: 194356
* Revert "CalculateSpillWeights does not need to be a pass"Arnaud A. de Grandmaison2013-11-081-2/+2
| | | | | | Temporarily revert my previous commit until I understand why it breaks 3 target tests. llvm-svn: 194272
* CalculateSpillWeights does not need to be a passArnaud A. de Grandmaison2013-11-081-2/+2
| | | | | | | | | | 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. llvm-svn: 194269
* Represent RegUnit liveness with LiveRange instanceMatthias Braun2013-10-101-3/+3
| | | | | | | Previously LiveInterval has been used, but having a spill weight and register number is unnecessary for a register unit. llvm-svn: 192397
* Explicitly request unsigned enum types when desiredReid Kleckner2013-10-081-1/+1
| | | | | | | This fixes repeated -Wmicrosoft warnings when self-hosting clang on Windows, and gets us real unsigned enum types with MSVC. llvm-svn: 192227
OpenPOWER on IntegriCloud