summaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegisterCoalescer.cpp
Commit message (Collapse)AuthorAge
* Merging r168837: into the 3.2 release branch.Pawel Wodnicki2012-11-29
| | | | | | | | | | | Avoid rewriting instructions twice. This could cause miscompilations in targets where sub-register composition is not always idempotent (ARM). <rdar://problem/12758887> git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_32@168849 91177308-0d34-0410-b5e6-96231b3b80d8
* Exploit the new identity composition in composeSubRegIndices().Jakob Stoklund Olesen2012-11-01
| | | | | | | The static compose() function in RegisterCoalescer was doing the exact same thing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167198 91177308-0d34-0410-b5e6-96231b3b80d8
* Completely disallow partial copies in adjustCopiesBackFrom().Jakob Stoklund Olesen2012-10-29
| | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166944 91177308-0d34-0410-b5e6-96231b3b80d8
* Never attempt to join an early-clobber def with a regular kill.Jakob Stoklund Olesen2012-10-27
| | | | | | This fixes PR14194. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166880 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't crash when the Assignments vector is empty.Jakob Stoklund Olesen2012-10-21
| | | | | | Reported by Vincent Lejeune using an out-of-tree target. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166398 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert r166046 "Switch back to the old coalescer for now to fix the 32 bit bit"Jakob Stoklund Olesen2012-10-16
| | | | | | A fix for PR14098, including the test case is in the next commit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166067 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch back to the old coalescer for now to fix the 32 bit bitRafael Espindola2012-10-16
| | | | | | llvm+clang+compiler-rt bootstrap. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166046 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove RegisterClassInfo::isReserved() and isAllocatable().Jakob Stoklund Olesen2012-10-15
| | | | | | Clients can use the equivalent functions in MRI. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165990 91177308-0d34-0410-b5e6-96231b3b80d8
* Drop <def,dead> flags when merging into an unused lane.Jakob Stoklund Olesen2012-10-13
| | | | | | | | | | | | The new coalescer can merge a dead def into an unused lane of an otherwise live vector register. Clear the <dead> flag when that happens since the flag refers to the full virtual register which is still live after the partial dead def. This fixes PR14079. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165877 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix coalescing with IMPLICIT_DEF values.Jakob Stoklund Olesen2012-10-12
| | | | | | | | | | | | | | | | PHIElimination inserts IMPLICIT_DEF instructions to guarantee that all PHI predecessors have a live-out value. These IMPLICIT_DEF values are not considered to be real interference when coalescing virtual registers: %vreg1 = IMPLICIT_DEF %vreg2 = MOV32r0 When joining %vreg1 and %vreg2, the IMPLICIT_DEF instruction and its value number should simply be erased since the %vreg2 value number now provides a live-out value for the PHI predecesor block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165813 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove the old coalescer algorithm.Jakob Stoklund Olesen2012-10-02
| | | | | | | The new algorithm has been enabled by default for almost a week now and seems to be stable. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165062 91177308-0d34-0410-b5e6-96231b3b80d8
* Make sure the whole live range is covered when values are pruned twice.Jakob Stoklund Olesen2012-10-02
| | | | | | | | | | | | | | | | | | | | | | | | JoinVals::pruneValues() calls LIS->pruneValue() to avoid conflicts when overlapping two different values. This produces a set of live range end points that are used to reconstruct the live range (with SSA update) after joining the two registers. When a value is pruned twice, the set of end points was insufficient: v1 = DEF v1 = REPLACE1 v1 = REPLACE2 KILL v1 The end point at KILL would only reconstruct the live range from REPLACE2 to KILL, leaving the range REPLACE1-REPLACE2 dead. Add REPLACE2 as an end point in this case so the full live range is reconstructed. This fixes PR13999. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165056 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove <def,read-undef> flags from partial redefinitions.Jakob Stoklund Olesen2012-09-27
| | | | | | | | | The new coalescer can turn a full virtual register definition into a partial redef by merging another value into an unused vector lane. Make sure to clear the <read-undef> flag on such defs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164807 91177308-0d34-0410-b5e6-96231b3b80d8
* Enable the new coalescer algorithm by default.Jakob Stoklund Olesen2012-09-27
| | | | | | | The new coalescer is better at merging values into unused vector lanes, improving NEON code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164794 91177308-0d34-0410-b5e6-96231b3b80d8
* Ignore PHI-defs for -new-coalescer interference checks.Jakob Stoklund Olesen2012-09-20
| | | | | | | | A PHI can't create interference on its own. If two live ranges interfere at a PHI, they must also interfere when leaving one of the PHI predecessors. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164330 91177308-0d34-0410-b5e6-96231b3b80d8
* Extend -new-coalescer SSA update to handle mapped values as well.Jakob Stoklund Olesen2012-09-20
| | | | | | | | | | | | | The old-fashioned many-to-one value mapping doesn't always work when merging vector lanes. A value can map to multiple different values, and it can even be necessary to insert new PHIs. When a value number is defined by a copy from a value number that required SSa update, include the live range of the copied value number in the SSA update as well. It is not necessarily a copy of the original value number any longer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164329 91177308-0d34-0410-b5e6-96231b3b80d8
* Resolve conflicts involving dead vector lanes for -new-coalescer.Jakob Stoklund Olesen2012-09-19
| | | | | | | | | | | | | | | | | | | | | A common coalescing conflict in vector code is lane insertion: %dst = FOO %src = BAR %dst:ssub0 = COPY %src The live range of %src interferes with the ssub0 lane of %dst, but that lane is never read after %src would have clobbered it. That makes it safe to merge the live ranges and eliminate the COPY: %dst = FOO %dst:ssub0 = BAR This patch teaches the new coalescer to resolve conflicts where dead vector lanes would be clobbered, at least as long as the clobbered vector lanes don't escape the basic block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164250 91177308-0d34-0410-b5e6-96231b3b80d8
* Merge into undefined lanes under -new-coalescer.Jakob Stoklund Olesen2012-09-17
| | | | | | | | | | | | | | | | | Add LIS::pruneValue() and extendToIndices(). These two functions are used by the register coalescer when merging two live ranges requires more than a trivial value mapping as supported by LiveInterval::join(). The pruneValue() function can remove the part of a value number that is going to conflict in join(). Afterwards, extendToIndices can restore the live range, using any new dominating value numbers and updating the SSA form. Use this complex value mapping to support merging a register into a vector lane that has a conflicting value, but the clobbered lane is undef. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164074 91177308-0d34-0410-b5e6-96231b3b80d8
* Add alternative coalescing algorithm under a flag.Jakob Stoklund Olesen2012-09-16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The live range of an SSA value forms a sub-tree of the dominator tree. That means the live ranges of two values overlap if and only if the def of one value lies within the live range of the other. This can be used to simplify the interference checking a bit: Visit each def in the two registers about to be joined. Check for interference against the value that is live in the other register at the def point only. It is not necessary to scan the set of overlapping live ranges, this interference check can be done while computing the value mapping required for the final live range join. The new algorithm is prepared to handle more complicated conflict resolution - We can allow overlapping live ranges with different values as long as the differing lanes are undef or unused in the other register. The implementation in this patch doesn't do that yet, it creates code that is nearly identical to the old algorithm's, except: - The new stripCopies() function sees through multiple copies while the old RegistersDefinedFromSameValue() only can handle one. - There are a few rare cases where the new algorithm can erase an IMPLICIT_DEF instuction that RegistersDefinedFromSameValue() couldn't handle. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163991 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't depend on kill flags in removeCopyByCommutingDef().Jakob Stoklund Olesen2012-09-15
| | | | | | | Kill flags are removed more and more aggressively during the register allocation passes, it is better to get information from LiveIntervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163972 91177308-0d34-0410-b5e6-96231b3b80d8
* Tidy up a few more uses of MF.getFunction()->getName().David Blaikie2012-08-22
| | | | | | | | Based on CR feedback from r162301 and Craig Topper's refactoring in r162347 here are a few other places that could use the same API (& in one instance drop a Function.h dependency). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162367 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a getName function to MachineFunction. Use it in places that previously ↵Craig Topper2012-08-22
| | | | | | did getFunction()->getName(). Remove includes of Function.h that are no longer needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162347 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete merged physreg copies in joinReservedPhysReg().Jakob Stoklund Olesen2012-08-03
| | | | | | | Previously, the identity copy would survive through register allocation before it was removed by the rewriter. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161269 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate the VNInfo::hasPHIKill() flag.Jakob Stoklund Olesen2012-08-03
| | | | | | | | | | The only real user of the flag was removeCopyByCommutingDef(), and it has been switched to LiveIntervals::hasPHIKill(). All the code changed by this patch was only concerned with computing and propagating the flag. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161255 91177308-0d34-0410-b5e6-96231b3b80d8
* Make the hasPHIKills flag a computed property.Jakob Stoklund Olesen2012-08-03
| | | | | | | | | | | | | The VNInfo::HAS_PHI_KILL is only half supported. We precompute it in LiveIntervalAnalysis, but it isn't properly updated by live range splitting and functions like shrinkToUses(). It is only used in one place: RegisterCoalescer::removeCopyByCommutingDef(). This patch changes that function to use a new LiveIntervals::hasPHIKill() function that computes the flag for a given value number. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161254 91177308-0d34-0410-b5e6-96231b3b80d8
* Clear kill flags in removeCopyByCommutingDef().Jakob Stoklund Olesen2012-07-31
| | | | | | | | | We are extending live ranges, so kill flags are not accurate. They aren't needed until they are recomputed after RA anyway. <rdar://problem/11950722> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161023 91177308-0d34-0410-b5e6-96231b3b80d8
* Now that RegistersDefinedFromSameValue handles one instruction being anRafael Espindola2012-07-01
| | | | | | | | | implicit_def, the other instruction can be anything, including instructions that define multiple values. Be careful about that and don't assume what operand 0 is. Fixes pr13249. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159509 91177308-0d34-0410-b5e6-96231b3b80d8
* Handle implicit_defs in the register coalescer. I am still trying to produceRafael Espindola2012-06-30
| | | | | | a reduced testcase, but this fixes pr13209. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159479 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a crash in --debug code.Jakob Stoklund Olesen2012-06-22
| | | | | | Don't try to print out the live range of a physreg. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159021 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove some redundant LIS->hasInterval() checks.Jakob Stoklund Olesen2012-06-22
| | | | | | | These functions only operate on virtual registers now, and they all have live ranges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159015 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove LiveIntervals::trackingRegUnits().Jakob Stoklund Olesen2012-06-22
| | | | | | | | | With regunit liveness permanently enabled, this function would always return true. Also remove now obsolete code for checking physreg interference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159006 91177308-0d34-0410-b5e6-96231b3b80d8
* Update regunits in RegisterCoalescer::reMaterializeTrivialDef.Jakob Stoklund Olesen2012-06-21
| | | | | | Old code would only update physreg live intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158881 91177308-0d34-0410-b5e6-96231b3b80d8
* Use regunit liveness in RegisterCoalescer when it is available.Jakob Stoklund Olesen2012-06-15
| | | | | | | We only do very limited physreg coalescing now, but we still merge virtual registers into reserved registers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158526 91177308-0d34-0410-b5e6-96231b3b80d8
* Move RegisterClassInfo.h.Andrew Trick2012-06-06
| | | | | | | Allow targets to access this API. It's required for RegisterPressure. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158102 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unused private fields found by clang's new -Wunused-private-field.Benjamin Kramer2012-06-06
| | | | | | | | There are some that I didn't remove this round because they looked like obvious stubs. There are dead variables in gtest too, they should be fixed upstream. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158090 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify LiveInterval::print().Jakob Stoklund Olesen2012-06-05
| | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158031 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch all register list clients to the new MC*Iterator interface.Jakob Stoklund Olesen2012-06-01
| | | | | | | | | | | | | 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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157854 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove physreg support from adjustCopiesBackFrom and removeCopyByCommutingDef.Jakob Stoklund Olesen2012-06-01
| | | | | | | After physreg coalescing was disabled, these functions can't do anything useful with physregs anyway. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157849 91177308-0d34-0410-b5e6-96231b3b80d8
* Correctly deal with identity copies in RegisterCoalescer.Jakob Stoklund Olesen2012-05-23
| | | | | | | | | | | | | | | | | Now that the coalescer keeps live intervals and machine code in sync at all times, it needs to deal with identity copies differently. When merging two virtual registers, all identity copies are removed right away. This means that other identity copies must come from somewhere else, and they are going to have a value number. Deal with such copies by merging the value numbers before erasing the copy instruction. Otherwise, we leave dangling value numbers in the live interval. This fixes PR12927. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157340 91177308-0d34-0410-b5e6-96231b3b80d8
* Clear kill flags on the fly when joining intervals.Jakob Stoklund Olesen2012-05-20
| | | | | | | | | | | With physreg joining out of the way, it is easy to recognize the instructions that need their kill flags cleared while testing for interference. This allows us to skip the final scan of all instructions for an 11% speedup of the coalescer pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157169 91177308-0d34-0410-b5e6-96231b3b80d8
* Missed a push_back in r157147.Jakob Stoklund Olesen2012-05-20
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157148 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid deleting extra copies when RegistersDefinedFromSameValue is true.Jakob Stoklund Olesen2012-05-20
| | | | | | | This function adds copies to be erased to DupCopies, avoid also adding them to DeadCopies. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157147 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix build bots.Jakob Stoklund Olesen2012-05-20
| | | | | | Avoid looking at the operands of a potentially erased instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157146 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate some uses of struct LiveRange.Jakob Stoklund Olesen2012-05-20
| | | | | | That struct ought to be a LiveInterval implementation detail. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157143 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify overlap check.Jakob Stoklund Olesen2012-05-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157137 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix 12892.Jakob Stoklund Olesen2012-05-19
| | | | | | | | | | | | Dead code elimination during coalescing could cause a virtual register to be split into connected components. The following rewriting would be confused about the already joined copies present in the code, but without a corresponding value number in the live range. Erase all joined copies instantly when joining intervals such that the MI and LiveInterval representations are always in sync. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157135 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove the late DCE in RegisterCoalescer.Jakob Stoklund Olesen2012-05-19
| | | | | | | | | | | Dead code and joined copies are now eliminated on the fly, and there is no need for a post pass. This makes the coalescer work like other modern register allocator passes: Code is changed on the fly, there is no pending list of changes to be committed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157132 91177308-0d34-0410-b5e6-96231b3b80d8
* Erase joined copies immediately.Jakob Stoklund Olesen2012-05-19
| | | | | | | | | The late dead code elimination is no longer necessary. The test changes are cause by a register hint that can be either %rdi or %rax. The choice depends on the use list order, which this patch changes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157131 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix an ancient bug in removeCopyByCommutingDef().Jakob Stoklund Olesen2012-05-19
| | | | | | | | | | | | | | | Before rewriting uses of one value in A to register B, check that there are no tied uses. That would require multiple A values to be rewritten. This bug can't bite in the current version of the code for a fairly subtle reason: A tied use would have caused 2-addr to insert a copy before the use. If the copy has been coalesced, it will be found by the same loop changed by this patch, and the optimization is aborted. This was exposed by 400.perlbench and lua after applying a patch that deletes joined copies aggressively. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157130 91177308-0d34-0410-b5e6-96231b3b80d8
* Collect inflatable virtual registers on the fly.Jakob Stoklund Olesen2012-05-19
| | | | | | | There is no reason to defer the collection of virtual registers whose register class may be replaced with a larger class. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157125 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-05 12:44:28 +0000