aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/LiveIntervalAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Oops. Renamed remaining MachineInstrIndex references.Lang Hames2009-10-031-8/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83255 91177308-0d34-0410-b5e6-96231b3b80d8
* Renamed MachineInstrIndex to LiveIndex.Lang Hames2009-10-031-92/+92
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83254 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unused variable.Daniel Dunbar2009-09-251-2/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82821 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify a few more uses of reg_iterator.Dan Gohman2009-09-251-4/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82812 91177308-0d34-0410-b5e6-96231b3b80d8
* Improve MachineMemOperand handling.Dan Gohman2009-09-251-5/+6
| | | | | | | | | | | | | | | | | | | | | | - Allocate MachineMemOperands and MachineMemOperand lists in MachineFunctions. This eliminates MachineInstr's std::list member and allows the data to be created by isel and live for the remainder of codegen, avoiding a lot of copying and unnecessary translation. This also shrinks MemSDNode. - Delete MemOperandSDNode. Introduce MachineSDNode which has dedicated fields for MachineMemOperands. - Change MemSDNode to have a MachineMemOperand member instead of its own fields with the same information. This introduces some redundancy, but it's more consistent with what MachineInstr will eventually want. - Ignore alignment when searching for redundant loads for CSE, but remember the greatest alignment. Target-specific code which previously used MemOperandSDNodes with generic SDNodes now use MemIntrinsicSDNodes, with opcodes in a designated range so that the SelectionDAG framework knows that MachineMemOperand information is available. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82794 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix PR5024. LiveVariables physical register defs should *commit* only after allEvan Cheng2009-09-231-0/+4
| | | | | | | | | of the defs are processed. Also fix a implicit_def propagation bug: a implicit_def of a physical register should be applied to uses of the sub-registers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82616 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix PR4986. "r1024 = insert_subreg r1024, undef, 2" cannot be turned in an ↵Evan Cheng2009-09-211-10/+23
| | | | | | 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
* When computing live intervals for earlyclobber operands,Dale Johannesen2009-09-201-3/+16
| | | | | | | | | | | | 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
* Fix -Asserts warning.Daniel Dunbar2009-09-151-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81909 91177308-0d34-0410-b5e6-96231b3b80d8
* Another try at early partial coalescing. Identity phi source copies (their ↵Evan Cheng2009-09-151-58/+56
| | | | | | | | | 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
* Add early coalescing to liveintervals. This is work in progress and is known ↵Evan Cheng2009-09-141-24/+164
| | | | | | | | | 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
* Moved some more index operations over to LiveIntervals.Lang Hames2009-09-121-50/+50
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81605 91177308-0d34-0410-b5e6-96231b3b80d8
* 80 col violations.Evan Cheng2009-09-121-5/+9
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81598 91177308-0d34-0410-b5e6-96231b3b80d8
* Replaces uses of unsigned for indexes in LiveInterval and VNInfo withLang Hames2009-09-041-163/+186
| | | | | | | | | 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
* Change Pass::print to take a raw ostream instead of std::ostream,Chris Lattner2009-08-231-2/+1
| | | | | | | update all code that this affects. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79830 91177308-0d34-0410-b5e6-96231b3b80d8
* remove various std::ostream version of printing methods fromChris Lattner2009-08-231-6/+8
| | | | | | | | | 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
* remove a dead class.Chris Lattner2009-08-231-5/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79795 91177308-0d34-0410-b5e6-96231b3b80d8
* Convert DOUT to DEBUG(errs()...).Bill Wendling2009-08-221-50/+76
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79752 91177308-0d34-0410-b5e6-96231b3b80d8
* Modified VNInfo. The "copy" member is now a union which holds the copy for a ↵Lang Hames2009-08-101-10/+10
| | | | | | 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
* Turn some insert_subreg, extract_subreg, subreg_to_reg into implicit_defs.Evan Cheng2009-08-051-5/+27
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78151 91177308-0d34-0410-b5e6-96231b3b80d8
* Re-apply LiveInterval index dumping patch, with fixes suggested by BillDavid Greene2009-08-031-0/+6
| | | | | | | and others. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78003 91177308-0d34-0410-b5e6-96231b3b80d8
* Use setPreservesAll and setPreservesCFG in CodeGen passes.Dan Gohman2009-07-311-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77754 91177308-0d34-0410-b5e6-96231b3b80d8
* More migration to raw_ostream, the water has dried up around the iostream hole.Daniel Dunbar2009-07-251-5/+5
| | | | | | | | | | | - 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
* Move to raw_ostream.Daniel Dunbar2009-07-241-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76963 91177308-0d34-0410-b5e6-96231b3b80d8
* Constify the key in Mi2IndexMap.David Greene2009-07-221-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76801 91177308-0d34-0410-b5e6-96231b3b80d8
* revert r76602, 76603, and r76615, pending design discussions.Chris Lattner2009-07-211-2/+9
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76646 91177308-0d34-0410-b5e6-96231b3b80d8
* Prefix IR dumps with LiveInterval indices when possible. This turnsDavid Greene2009-07-211-9/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Simplify the coalescer (finally!) by making ↵Evan Cheng2009-07-171-33/+44
| | | | | | 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
* Changed my mind. We now allow remat of instructions whose defs have subreg ↵Evan Cheng2009-07-161-5/+0
| | | | | | indices. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76100 91177308-0d34-0410-b5e6-96231b3b80d8
* Let callers decide the sub-register index on the def operand of ↵Evan Cheng2009-07-161-1/+6
| | | | | | | | | 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
* llvm_unreachable->llvm_unreachable(0), LLVM_UNREACHABLE->llvm_unreachable.Torok Edwin2009-07-141-1/+1
| | | | | | | | | | 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
* assert(0) -> LLVM_UNREACHABLE.Torok Edwin2009-07-111-1/+1
| | | | | | | | | | 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
* Convert more assert(0)+abort() -> LLVM_UNREACHABLE,Torok Edwin2009-07-111-4/+8
| | | | | | | and abort()/exit() -> llvm_report_error(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75363 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid compiler warnings if assertions turned off.Duncan Sands2009-07-101-0/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75267 91177308-0d34-0410-b5e6-96231b3b80d8
* Improved tracking of value number kills. VN kills are now representedLang Hames2009-07-091-18/+76
| | | | | | | | | | | | | | 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
* Remove special handling of implicit_def. Fix a couple more bugs in ↵Evan Cheng2009-07-011-24/+51
| | | | | | | | | 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
* Handle IMPLICIT_DEF with isUndef operand marker, part 2. This patch moves ↵Evan Cheng2009-07-011-2/+91
| | | | | | 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
* Add a bit IsUndef to MachineOperand. This indicates the def / use register ↵Evan Cheng2009-06-301-1/+5
| | | | | | | | | | | 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
* When doing remat, don't consider uses of non-allocatable physregs. Patch Chris Lattner2009-06-271-0/+4
| | | | | | | by Evan. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74370 91177308-0d34-0410-b5e6-96231b3b80d8
* More VNInfo tweaking, plus a little progress on intra-block splitting.Lang Hames2009-06-191-2/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73750 91177308-0d34-0410-b5e6-96231b3b80d8
* Improved PHI def marking, replaced some gotos with breaks.Lang Hames2009-06-181-5/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73727 91177308-0d34-0410-b5e6-96231b3b80d8
* VNInfo cleanup.Lang Hames2009-06-171-26/+27
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73634 91177308-0d34-0410-b5e6-96231b3b80d8
* Move register allocation preference (or hint) from LiveInterval to ↵Evan Cheng2009-06-141-1/+1
| | | | | | 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
* Update to in-place spilling framework. Includes live interval scaling and ↵Lang Hames2009-06-021-0/+44
| | | | | | trivial rewriter. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72729 91177308-0d34-0410-b5e6-96231b3b80d8
* LiveVariables::VarInfo contains an AliveBlocks BitVector, which has as manyJeffrey Yasskin2009-05-261-5/+5
| | | | | | | | | | | 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
* In some rare cases, the register allocator can spill registers but end up ↵Evan Cheng2009-05-031-48/+10
| | | | | | | | | | | 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
* Fix PR4076. Correctly create live interval of physical register with ↵Evan Cheng2009-04-271-10/+20
| | | | | | two-address update. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70245 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix PR4056. It's possible a physical register def is dead if its implicit ↵Evan Cheng2009-04-271-2/+2
| | | | | | use is deleted by two-address pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70213 91177308-0d34-0410-b5e6-96231b3b80d8
* It has finally happened. Spiller is now using live interval info.Evan Cheng2009-04-211-3/+3
| | | | | | | 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
* Added a linearscan register allocation optimization. When the register ↵Evan Cheng2009-04-201-11/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-15 12:10:25 +0000