summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegisterCoalescer.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-2/+2
| | | | | | Remove the old functions. llvm-svn: 202636
* ReMat: fix overly cavalier attitude to sub-register indicesTim Northover2014-01-161-24/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | There are two attempted optimisations in reMaterializeTrivialDef, trying to avoid promoting the size of a register too much when rematerializing. Unfortunately, both appear to be flawed. First, we see if the original register would have worked, but this is inadequate. Consider: v1 = SOMETHING (v1 is QQ) v2:Q0 = COPY v1:Q1 (v1, v2 are QQ) ... uses of v2 In this case even though v2 *could* be used directly as the output of SOMETHING, this would set the wrong bits of the QQ register involved. The correct rematerialization must be: v2:Q0_Q1 = SOMETHING (v2 promoted to QQQ) ... uses of v2:Q1_Q2 For the second optimisation, if the correct remat is "v2:idx = SOMETHING" then we can't necessarily expect v2 itself to be valid for SOMETHING, but we do try to hunt for a class between v1 and v2 that works. Unfortunately, this is also wrong: v1 = SOMETHING (v1 is QQ) v2:Q0_Q1 = COPY v1 (v1 is QQ, v2 is QQQ) ... uses of v2 as a QQQ The canonical rematerialization here is "v2:Q0_Q1 = SOMETHING". However current logic would decide that v2 could be a QQ (no interest is taken in later uses). This patch, therefore, always accepts the widened register class without trying to be clever. Generally there is no penalty to this (e.g. in the common GR32 < GR64 case, expanding the width doesn't matter because it's not like you were going to do anything else with the high bits of a GR32 register). It can increase register pressure in cases like the ARM VFP regs though (multiple non-overlapping but equivalent subregisters). This situation can be spotted by the fact that both source and destination in the not-quite-coalesced pair have a sub-register index and rematerialisation is skipped in that situation. Unfortunately, no in-tree targets actually expose this as far as I can tell (there are so few isAsCheapAsAMove instructions for it to trigger on) so I've been unable to produce a test. It was exposed in our ARM64 SPEC tests though, and I will be adding a test there that we should be able to contribute soon(TM). rdar://problem/15775279 llvm-svn: 199376
* Fix valgrind warning for gcc builds.Patrik Hagglund2014-01-141-5/+4
| | | | | | | | Sorry, I don't understand why the warning is generated (a gcc bug?). Anyhow, the change should improve readablity. No functionality change intended. llvm-svn: 199214
* Revert "ReMat: fix overly cavalier attitude to sub-register indices"Tim Northover2014-01-131-4/+24
| | | | | | | | | | Very sorry, this was a premature patch that I still need to investigate and finish off (for some reason beyond me at the moment it doesn't actually fix the issue in all cases). This reverts commit r199091. llvm-svn: 199093
* ReMat: fix overly cavalier attitude to sub-register indicesTim Northover2014-01-131-24/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | There are two attempted optimisations in reMaterializeTrivialDef, trying to avoid promoting the size of a register too much when rematerializing. Unfortunately, both appear to be flawed. First, we see if the original register would have worked, but this is inadequate. Consider: v1 = SOMETHING (v1 is QQ) v2:Q0 = COPY v1:Q1 (v1, v2 are QQ) ... uses of v2 In this case even though v2 *could* be used directly as the output of SOMETHING, this would set the wrong bits of the QQ register involved. The correct rematerialization must be: v2:Q0_Q1 = SOMETHING (v2 promoted to QQQ) ... uses of v2:Q1_Q2 For the second optimisation, if the correct remat is "v2:idx = SOMETHING" then we can't necessarily expect v2 itself to be valid for SOMETHING, but we do try to hunt for a class between v1 and v2 that works. Unfortunately, this is also wrong: v1 = SOMETHING (v1 is QQ) v2:Q0_Q1 = COPY v1 (v1 is QQ, v2 is QQQ) ... uses of v2 as a QQQ The canonical rematerialization here is "v2:Q0_Q1 = SOMETHING". However current logic would decide that v2 could be a QQ (no interest is taken in later uses). This patch, therefore, always accepts the widened register class without trying to be clever. Generally there is no penalty to this (e.g. in the common GR32 < GR64 case, expanding the width doesn't matter because it's not like you were going to do anything else with the high bits of a GR32 register). It can increase register pressure in cases like the ARM VFP regs though (multiple non-overlapping but equivalent subregisters). Hopefully this situation is rare enough that it won't matter. Unfortunately, no in-tree targets actually expose this as far as I can tell (there are so few isAsCheapAsAMove instructions for it to trigger on) so I've been unable to produce a test. It was exposed in our ARM64 SPEC tests though, and I will be adding a test there that we should be able to contribute soon(TM). llvm-svn: 199091
* Print register in LiveInterval::print()Matthias Braun2013-10-101-7/+8
| | | | llvm-svn: 192398
* Represent RegUnit liveness with LiveRange instanceMatthias Braun2013-10-101-2/+2
| | | | | | | Previously LiveInterval has been used, but having a spill weight and register number is unnecessary for a register unit. llvm-svn: 192397
* Work on LiveRange instead of LiveInterval where possibleMatthias Braun2013-10-101-1/+1
| | | | | | | Also change some pointer arguments to references at some places where 0-pointers are not allowed. llvm-svn: 192396
* Pass LiveQueryResult by valueMatthias Braun2013-10-101-6/+6
| | | | | | | This makes the API a bit more natural to use and makes it easier to make LiveRanges implementation details private. llvm-svn: 192394
* Rename LiveRange to LiveInterval::SegmentMatthias Braun2013-10-101-34/+35
| | | | | | | | The Segment struct contains a single interval; multiple instances of this struct are used to construct a live range, but the struct is not a live range by itself. llvm-svn: 192392
* Fix commentMatthias Braun2013-10-041-1/+1
| | | | llvm-svn: 191966
* Added temp flag -misched-bench for staging in default changes.Andrew Trick2013-09-261-1/+1
| | | | llvm-svn: 191423
* Provide basic type safety for array_pod_sort comparators.Benjamin Kramer2013-09-221-3/+2
| | | | | | | | This makes using array_pod_sort significantly safer. The implementation relies on function pointer casting but that should be safe as we're dealing with void* here. llvm-svn: 191175
* avoid unnecessary direct access to LiveInterval::rangesMatthias Braun2013-09-061-6/+6
| | | | llvm-svn: 190170
* remove unused argument from LiveRanges::join()Matthias Braun2013-09-061-2/+1
| | | | llvm-svn: 190169
* remove pointless assertMatthias Braun2013-09-061-2/+0
| | | | | | The if above it ensures the property anyway. llvm-svn: 190168
* fix commentMatthias Braun2013-09-061-1/+1
| | | | | | There's no 'B3' in the example. llvm-svn: 190167
* 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
* Use modern API to avoid exposing LiveInterval internals.Jakob Stoklund Olesen2013-07-051-5/+3
| | | | | | No functional change intended. llvm-svn: 185733
* Fix a -join-globalcopies bug; handle undef operands.Andrew Trick2013-06-211-0/+3
| | | | llvm-svn: 184569
* Modify the -join-globalcopies option (off by default).Andrew Trick2013-06-211-2/+2
| | | | | | | Always coalesce in forward order to propagate rematerialization. I'm fixing this option so I can enable it by default soon. llvm-svn: 184568
* Make rematerialization in the coalescer less sensitive to LRG order.Andrew Trick2013-06-211-4/+15
| | | | llvm-svn: 184567
* Mark rematerialized super/sub registers as dead.Tim Northover2013-06-141-0/+1
| | | | | | | | | | | | | When we're rematerializing into a not-quite-right register we already add the real definition as an imp-def, but we should also be marking the "official" register as dead, since nothing else is going to use it as a result of this remat. Not doing this can affect pressure tracking. rdar://problem/14158833 llvm-svn: 184002
* Fix rematerialization into physical registers.Tim Northover2013-05-301-2/+3
| | | | | | | | | | | | | | | | | r182872 introduced a bug in how the register-coalescer's rematerialization handled defining a physical register. It relied on the output of the coalescer's setRegisters method to determine whether the replacement instruction needed an implicit-def. However, this value isn't necessarily the same as the CopyMI's actual destination register which is what the rest of the basic-block expects us to be defining. The commit changes the rematerializer to use the actual register attached to CopyMI in its decision. This will be tested soon by an X86 patch which moves everything to using MOV32r0 instead of other sizes. llvm-svn: 182925
* Teach ReMaterialization to be more cunning about subregistersTim Northover2013-05-291-18/+65
| | | | | | | | | | | | | | | | This allows rematerialization during register coalescing to handle more cases involving operations like SUBREG_TO_REG which might need to be rematerialized using sub-register indices. For example, code like: v1(GPR64):sub_32 = MOVZ something v2(GPR64) = COPY v1(GPR64) should be convertable to: v2(GPR64):sub_32 = MOVZ something but previously we just gave up in places like this llvm-svn: 182872
* Remove unused #includes.Bill Wendling2013-03-051-1/+0
| | | | llvm-svn: 176467
* RegisterCoalescer::reMaterializeTrivialDef() can constrain the destinationCameron Zwarich2013-02-141-1/+1
| | | | | | register class to match the defining instruction. llvm-svn: 175130
* Fix RegisterCoalescer::rematerializeTrivialDef() so that it works on flippedCameron Zwarich2013-02-141-10/+10
| | | | | | | CoalescerPairs. Also, make it take a CoalescerPair directly like other methods of RegisterCoalescer. llvm-svn: 175123
* Fix some issues with rematerialization in RegisterCoalescer when the destinationCameron Zwarich2013-02-141-0/+10
| | | | | | | | | | | | of the copy is a subregister def. The current code assumes that it can do a full def of the destination register, but it is not checking that the def operand is read-undef. It also doesn't clear the subregister index of the destination in the new instruction to reflect the full subregister def. These issues were found running 'make check' with my next commit that enables rematerialization in more cases. llvm-svn: 175122
* Debug Info: LiveDebugVarible can remove DBG_VALUEs, make sure we emit them back.Manman Ren2013-02-131-10/+0
| | | | | | | | | | | | | | RegisterCoalescer used to depend on LiveDebugVariable. LDV removes DBG_VALUEs without emitting them at the end. We fix this by removing LDV from RegisterCoalescer. Also add an assertion to make sure we call emitDebugValues if DBG_VALUEs are removed at runOnMachineFunction. rdar://problem/13183203 Reviewed by Andy & Jakob llvm-svn: 175023
* Fix PR14732 by handling all kinds of IMPLICIT_DEF live ranges.Jakob Stoklund Olesen2013-01-031-8/+37
| | | | | | | | | | | | | | | | Most IMPLICIT_DEF instructions are removed by the ProcessImplicitDefs pass, and a few are reinserted by PHIElimination when a PHI argument is <undef>. RegisterCoalescer was assuming that all IMPLICIT_DEF live ranges look like those created by PHIElimination, and that their live range never leaves the basic block. The PR14732 test case does tricks with PHI nodes that causes a longer IMPLICIT_DEF live range to appear. This happens very rarely, but RegisterCoalescer should be able to handle it. llvm-svn: 171435
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-1/+1
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-3/+2
| | | | | | | | | | | | | | | | | 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
* Avoid rewriting instructions twice.Jakob Stoklund Olesen2012-11-291-0/+9
| | | | | | | | | This could cause miscompilations in targets where sub-register composition is not always idempotent (ARM). <rdar://problem/12758887> llvm-svn: 168837
* 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 duplicated #includes.Jakub Staszak2012-11-271-4/+0
| | | | llvm-svn: 168712
* Use array_pod_sort instead of std::sort.Andrew Trick2012-11-161-41/+36
| | | | llvm-svn: 168203
* Fix an obvious merge bug in -join-globalcopies (disabled).Andrew Trick2012-11-151-1/+3
| | | | | | | | Jakub Staszak spotted this in review. I don't notice these things until I manually rerun benchmarks. But reducing unit tests is a very high priority. llvm-svn: 168021
* Use reserve() to avoid vector reallocation.Jakub Staszak2012-11-141-0/+1
| | | | llvm-svn: 167991
* canJoinPhys method doesn't modify CoalescerPair. Make it const.Jakub Staszak2012-11-141-2/+2
| | | | llvm-svn: 167972
* Revert -join-splitedges to a boolean cmd line option.Andrew Trick2012-11-131-3/+2
| | | | llvm-svn: 167880
* The MachineScheduler does not currently require JoinSplitEdges.Andrew Trick2012-11-131-4/+4
| | | | | | | This option will eventually either be enabled unconditionally or replaced by a more general live range splitting optimization. llvm-svn: 167879
* Fix -join-splitedges: my previous "cleanup" broke it.Andrew Trick2012-11-131-1/+1
| | | | | | | Working on reducing unit tests. This won't be enabled unless a subtarget enables misched. llvm-svn: 167851
* misched: Allow subtargets to enable misched and dependent options.Andrew Trick2012-11-131-10/+34
| | | | | | | | | | | | This allows me to begin enabling (or backing out) misched by default for one subtarget at a time. To run misched we typically want to: - Disable SelectionDAG scheduling (use the source order scheduler) - Enable more aggressive coalescing (until we decide to always run the coalescer this way) - Enable MachineScheduler pass itself. Disabling PostRA sched may follow for some subtargets. llvm-svn: 167826
* Added RegisterCoalescer support for joining global copies first.Andrew Trick2012-11-131-20/+80
| | | | | | | | | | | | This adds the -join-globalcopies option which can be enabled by default once misched is also enabled. Ideally, the register coalescer would be able to split local live ranges in a way that produces copies that can be easily resolved by the scheduler. Until then, this heuristic should be good enough to at least allow the scheduler to run after coalescing. llvm-svn: 167825
* Cleanup the main RegisterCoalescer loop.Andrew Trick2012-11-131-23/+10
| | | | | | Block priorities still apply outside loops. llvm-svn: 167793
* Cleanup -join-splitedges. Make the loop more obvious.Andrew Trick2012-11-121-5/+2
| | | | llvm-svn: 167785
* Added a temporary option to avoid critical edges splitting.Andrew Trick2012-11-121-16/+55
| | | | | | | | | This teaches the register coalescer to be less prone to split critical edges. I am currently benchmarking this with the new (post-coalescer) scheduler. I plan to enable this by default and remove the option as soon as misched is enabled. llvm-svn: 167758
* Exploit the new identity composition in composeSubRegIndices().Jakob Stoklund Olesen2012-11-011-12/+8
| | | | | | | The static compose() function in RegisterCoalescer was doing the exact same thing. llvm-svn: 167198
* Completely disallow partial copies in adjustCopiesBackFrom().Jakob Stoklund Olesen2012-10-291-1/+2
| | | | | | | | | | | | Partial copies can show up even when CoalescerPair.isPartial() returns false. For example: %vreg24:dsub_0<def> = COPY %vreg31:dsub_0; QPR:%vreg24,%vreg31 Such a partial-partial copy is not good enough for the transformation adjustCopiesBackFrom() needs to do. llvm-svn: 166944
OpenPOWER on IntegriCloud