aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/LiveIntervalAnalysis.cpp
AgeCommit message (Collapse)Author
2009-09-21Fix PR4986. "r1024 = insert_subreg r1024, undef, 2" cannot be turned in an ↵Evan Cheng
implicit_def. Instead, it's an identity copy so it should be eliminated. Also make sure to update livevariable kill information. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82436 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-20When computing live intervals for earlyclobber operands,Dale Johannesen
we pushed the beginning of the interval back 1, so the interval would overlap with inputs that die. We were also pushing the end of the interval back 1, though, which means the earlyclobber didn't overlap with other output operands. Don't do this. PR 4964. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82342 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-15Fix -Asserts warning.Daniel Dunbar
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81909 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-15Another try at early partial coalescing. Identity phi source copies (their ↵Evan Cheng
sources are defined by phi join def) are coalesced. And the phi join copy is backward copy propagated into the other copies. Still miscompiling some tests. :-( git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81849 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-14Add early coalescing to liveintervals. This is work in progress and is known ↵Evan Cheng
to miscompute some tests. Read it at your own rish, I have aged 10 year while writing this. The gist of this is if source of some of the copies that feed into a phi join is defined by the phi join, we'd like to eliminate them. However, if any of the non-identity source overlaps the live interval of the phi join then the coalescer won't be able to coalesce them. The early coalescer's job is to eliminate the identity copies by partially-coalescing the two live intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81796 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-12Moved some more index operations over to LiveIntervals.Lang Hames
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81605 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-1280 col violations.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81598 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-04Replaces uses of unsigned for indexes in LiveInterval and VNInfo withLang Hames
a new class, MachineInstrIndex, which hides arithmetic details from most clients. This is a step towards allowing the register allocator to update/insert code during allocation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81040 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-23Change Pass::print to take a raw ostream instead of std::ostream,Chris Lattner
update all code that this affects. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79830 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-23remove various std::ostream version of printing methods fromChris Lattner
MachineInstr and MachineOperand. This required eliminating a bunch of stuff that was using DOUT, I hope that bill doesn't mind me stealing his fun. ;-) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79813 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-23remove a dead class.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79795 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-22Convert DOUT to DEBUG(errs()...).Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79752 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-10Modified VNInfo. The "copy" member is now a union which holds the copy for a ↵Lang Hames
register interval, or the defining register for a stack interval. Access is via getCopy/setCopy and getReg/setReg. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78620 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-05Turn some insert_subreg, extract_subreg, subreg_to_reg into implicit_defs.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78151 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-03Re-apply LiveInterval index dumping patch, with fixes suggested by BillDavid Greene
and others. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78003 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-31Use setPreservesAll and setPreservesCFG in CodeGen passes.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77754 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-25More migration to raw_ostream, the water has dried up around the iostream hole.Daniel Dunbar
- Some clients which used DOUT have moved to DEBUG. We are deprecating the "magic" DOUT behavior which avoided calling printing functions when the statement was disabled. In addition to being unnecessary magic, it had the downside of leaving code in -Asserts builds, and of hiding potentially unnecessary computations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77019 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-24Move to raw_ostream.Daniel Dunbar
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76963 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-22Constify the key in Mi2IndexMap.David Greene
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76801 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-21revert r76602, 76603, and r76615, pending design discussions.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76646 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-21Prefix IR dumps with LiveInterval indices when possible. This turnsDavid Greene
this: %ESI<def> = MOV32rr %EDI<kill> ADJCALLSTACKDOWN64 0, %RSP<imp-def>, %EFLAGS<imp-def,dead>, %RSP<imp-use> %reg1027<def> = MOVZX64rr32 %ESI %reg1027<def> = ADD64ri8 %reg1027, 15, %EFLAGS<imp-def,dead> %reg1027<def> = AND64ri8 %reg1027, -16, %EFLAGS<imp-def,dead> %RDI<def> = MOV64rr %RSP %RDI<def> = SUB64rr %RDI, %reg1027<kill>, %EFLAGS<imp-def,dead> %RSP<def> = MOV64rr %RDI into this: 4 %reg1024<def> = MOV32rr %EDI<kill> 12 ADJCALLSTACKDOWN64 0, %RSP<imp-def>, %EFLAGS<imp-def,dead>, %RSP<imp-use> 20 %reg1025<def> = MOVZX64rr32 %reg1024 28 %reg1026<def> = MOV64rr %reg1025<kill> 36 %reg1026<def> = ADD64ri8 %reg1026, 15, %EFLAGS<imp-def,dead> 44 %reg1027<def> = MOV64rr %reg1026<kill> 52 %reg1027<def> = AND64ri8 %reg1027, -16, %EFLAGS<imp-def,dead> 60 %reg1028<def> = MOV64rr %RSP 68 %reg1029<def> = MOV64rr %reg1028<kill> 76 %reg1029<def> = SUB64rr %reg1029, %reg1027<kill>, %EFLAGS<imp-def,dead> 84 %RSP<def> = MOV64rr %reg1029 This helps greatly when debugging register allocation and coalescing problems. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76615 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-17Simplify the coalescer (finally!) by making ↵Evan Cheng
LiveIntervals::processImplicitDefs a little more aggressive and teaching liveintervals to make use of isUndef marker on MachineOperands. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76223 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-16Changed my mind. We now allow remat of instructions whose defs have subreg ↵Evan Cheng
indices. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76100 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-16Let callers decide the sub-register index on the def operand of ↵Evan Cheng
rematerialized instructions. Avoid remat'ing instructions whose def have sub-register indices for now. It's just really really hard to get all the cases right. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75900 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-14llvm_unreachable->llvm_unreachable(0), LLVM_UNREACHABLE->llvm_unreachable.Torok Edwin
This adds location info for all llvm_unreachable calls (which is a macro now) in !NDEBUG builds. In NDEBUG builds location info and the message is off (it only prints "UREACHABLE executed"). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75640 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-11assert(0) -> LLVM_UNREACHABLE.Torok Edwin
Make llvm_unreachable take an optional string, thus moving the cerr<< out of line. LLVM_UNREACHABLE is now a simple wrapper that makes the message go away for NDEBUG builds. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75379 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-11Convert more assert(0)+abort() -> LLVM_UNREACHABLE,Torok Edwin
and abort()/exit() -> llvm_report_error(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75363 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-10Avoid compiler warnings if assertions turned off.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75267 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-09Improved tracking of value number kills. VN kills are now representedLang Hames
as an (index,bool) pair. The bool flag records whether the kill is a PHI kill or not. This code will be used to enable splitting of live intervals containing PHI-kills. A slight change to live interval weights introduced an extra spill into lsr-code-insertion (outside the critical sections). The test condition has been updated to reflect this. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75097 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-01Remove special handling of implicit_def. Fix a couple more bugs in ↵Evan Cheng
liveintervalanalysis and coalescer handling of implicit_def. Note, isUndef marker must be placed even on implicit_def def operand or else the scavenger will not ignore it. This is necessary because -O0 path does not use liveintervalanalysis, it treats implicit_def just like any other def. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74601 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-01Handle IMPLICIT_DEF with isUndef operand marker, part 2. This patch moves ↵Evan Cheng
the code to annotate machineoperands to LiveIntervalAnalysis. It also add markers for implicit_def that define physical registers. The rest, is just a lot of details. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74580 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-30Add a bit IsUndef to MachineOperand. This indicates the def / use register ↵Evan Cheng
operand is defined by an implicit_def. That means it can def / use any register and passes (e.g. register scavenger) can feel free to ignore them. The register allocator, when it allocates a register to a virtual register defined by an implicit_def, can allocate any physical register without worrying about overlapping live ranges. It should mark all of operands of the said virtual register so later passes will do the right thing. This is not the best solution. But it should be a lot less fragile to having the scavenger try to track what is defined by implicit_def. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74518 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-27When doing remat, don't consider uses of non-allocatable physregs. Patch Chris Lattner
by Evan. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74370 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-19More VNInfo tweaking, plus a little progress on intra-block splitting.Lang Hames
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73750 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-18Improved PHI def marking, replaced some gotos with breaks.Lang Hames
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73727 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-17VNInfo cleanup.Lang Hames
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73634 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-14Move register allocation preference (or hint) from LiveInterval to ↵Evan Cheng
MachineRegisterInfo. This allows more passes to set them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73346 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-02Update to in-place spilling framework. Includes live interval scaling and ↵Lang Hames
trivial rewriter. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72729 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-26LiveVariables::VarInfo contains an AliveBlocks BitVector, which has as manyJeffrey Yasskin
entries as there are basic blocks in the function. LiveVariables::getVarInfo creates a VarInfo struct for every register in the function, leading to quadratic space use. This patch changes the BitVector to a SparseBitVector, which doesn't help the worst-case memory use but does reduce the actual use in very long functions with short-lived variables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72426 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-03In some rare cases, the register allocator can spill registers but end up ↵Evan Cheng
not utilizing registers at all. The fundamental problem is linearscan's backtracking can end up freeing more than one allocated registers. However, reloads and restores might be folded into uses / defs and freed registers might not be used at all. VirtRegMap keeps track of allocations so it knows what's not used. As a horrible hack, the stack coloring can color spill slots with *free* registers. That is, it replace reload and spills with copies from and to the free register. It unfold instructions that load and store the spill slot and replace them with register using variants. Not yet enabled. This is part 1. More coming. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70787 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-27Fix PR4076. Correctly create live interval of physical register with ↵Evan Cheng
two-address update. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70245 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-27Fix PR4056. It's possible a physical register def is dead if its implicit ↵Evan Cheng
use is deleted by two-address pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70213 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-21It has finally happened. Spiller is now using live interval info.Evan Cheng
This fixes a very subtle bug. vr defined by an implicit_def is allowed overlap with any register since it doesn't actually modify anything. However, if it's used as a two-address use, its live range can be extended and it can be spilled. The spiller must take care not to emit a reload for the vn number that's defined by the implicit_def. This is both a correctness and performance issue. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69743 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-20Added a linearscan register allocation optimization. When the register ↵Evan Cheng
allocator spill an interval with multiple uses in the same basic block, it creates a different virtual register for each of the reloads. e.g. %reg1498<def> = MOV32rm %reg1024, 1, %reg0, 12, %reg0, Mem:LD(4,4) [sunkaddr39 + 0] %reg1506<def> = MOV32rm %reg1024, 1, %reg0, 8, %reg0, Mem:LD(4,4) [sunkaddr42 + 0] %reg1486<def> = MOV32rr %reg1506 %reg1486<def> = XOR32rr %reg1486, %reg1498, %EFLAGS<imp-def,dead> %reg1510<def> = MOV32rm %reg1024, 1, %reg0, 4, %reg0, Mem:LD(4,4) [sunkaddr45 + 0] => %reg1498<def> = MOV32rm %reg2036, 1, %reg0, 12, %reg0, Mem:LD(4,4) [sunkaddr39 + 0] %reg1506<def> = MOV32rm %reg2037, 1, %reg0, 8, %reg0, Mem:LD(4,4) [sunkaddr42 + 0] %reg1486<def> = MOV32rr %reg1506 %reg1486<def> = XOR32rr %reg1486, %reg1498, %EFLAGS<imp-def,dead> %reg1510<def> = MOV32rm %reg2038, 1, %reg0, 4, %reg0, Mem:LD(4,4) [sunkaddr45 + 0] From linearscan's point of view, each of reg2036, 2037, and 2038 are separate registers, each is "killed" after a single use. The reloaded register is available and it's often clobbered right away. e.g. In thise case reg1498 is allocated EAX while reg2036 is allocated RAX. This means we end up with multiple reloads from the same stack slot in the same basic block. Now linearscan recognize there are other reloads from same SS in the same BB. So it'll "downgrade" RAX (and its aliases) after reg2036 is allocated until the next reload (reg2037) is done. This greatly increase the likihood reloads from SS are reused. This speeds up sha1 from OpenSSL by 5.8%. It is also an across the board win for SPEC2000 and 2006. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69585 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-13Don't abort on an aliasing physical register that does not haveDan Gohman
a live interval. This is needed for some upcoming subreg changes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@68956 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-09Fix pr3954. The register scavenger asserts for inline assembly withBob Wilson
register destinations that are tied to source operands. The TargetInstrDescr::findTiedToSrcOperand method silently fails for inline assembly. The existing MachineInstr::isRegReDefinedByTwoAddr was very close to doing what is needed, so this revision makes a few changes to that method and also renames it to isRegTiedToUseOperand (for consistency with the very similar isRegTiedToDefOperand and because it handles both two-address instructions and inline assembly with tied registers). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@68714 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-08Implement support for using modeling implicit-zero-extension on x86-64Dan Gohman
with SUBREG_TO_REG, teach SimpleRegisterCoalescing to coalesce SUBREG_TO_REG instructions (which are similar to INSERT_SUBREG instructions), and teach the DAGCombiner to take advantage of this on targets which support it. This eliminates many redundant zero-extension operations on x86-64. This adds a new TargetLowering hook, isZExtFree. It's similar to isTruncateFree, except it only applies to actual definitions, and not no-op truncates which may not zero the high bits. Also, this adds a new optimization to SimplifyDemandedBits: transform operations like x+y into (zext (add (trunc x), (trunc y))) on targets where all the casts are no-ops. In contexts where the high part of the add is explicitly masked off, this allows the mask operation to be eliminated. Fix the DAGCombiner to avoid undoing these transformations to eliminate casts on targets where the casts are no-ops. Also, this adds a new two-address lowering heuristic. Since two-address lowering runs before coalescing, it helps to be able to look through copies when deciding whether commuting and/or three-address conversion are profitable. Also, fix a bug in LiveInterval::MergeInClobberRanges. It didn't handle the case that a clobber range extended both before and beyond an existing live range. In that case, multiple live ranges need to be added. This was exposed by the new subreg coalescing code. Remove 2008-05-06-SpillerBug.ll. It was bugpoint-reduced, and the spiller behavior it was looking for no longer occurrs with the new instruction selection. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@68576 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-26Don't assign a new stack slot if the pre-alloc splitter already assigned one.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@67764 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-23Fix PR3391 and PR3864. Reg allocator infinite looping.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@67544 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-23Model inline asm constraint which ties an input to an output register as ↵Evan Cheng
machine operand TIED_TO constraint. This eliminated the need to pre-allocate registers for these. This also allows register allocator can eliminate the unneeded copies. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@67512 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-01 20:04:22 +0000