summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Change Pass::print to take a raw ostream instead of std::ostream,Chris Lattner2009-08-231-2/+1
| | | | | | update all code that this affects. llvm-svn: 79830
* 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. ;-) llvm-svn: 79813
* remove a dead class.Chris Lattner2009-08-231-5/+0
| | | | llvm-svn: 79795
* Convert DOUT to DEBUG(errs()...).Bill Wendling2009-08-221-50/+76
| | | | llvm-svn: 79752
* 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. llvm-svn: 78620
* Turn some insert_subreg, extract_subreg, subreg_to_reg into implicit_defs.Evan Cheng2009-08-051-5/+27
| | | | llvm-svn: 78151
* Re-apply LiveInterval index dumping patch, with fixes suggested by BillDavid Greene2009-08-031-0/+6
| | | | | | and others. llvm-svn: 78003
* Use setPreservesAll and setPreservesCFG in CodeGen passes.Dan Gohman2009-07-311-0/+1
| | | | llvm-svn: 77754
* 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. llvm-svn: 77019
* Move to raw_ostream.Daniel Dunbar2009-07-241-2/+2
| | | | llvm-svn: 76963
* Constify the key in Mi2IndexMap.David Greene2009-07-221-1/+1
| | | | llvm-svn: 76801
* revert r76602, 76603, and r76615, pending design discussions.Chris Lattner2009-07-211-2/+9
| | | | llvm-svn: 76646
* 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. llvm-svn: 76615
* 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. llvm-svn: 76223
* Changed my mind. We now allow remat of instructions whose defs have subreg ↵Evan Cheng2009-07-161-5/+0
| | | | | | indices. llvm-svn: 76100
* 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. llvm-svn: 75900
* 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"). llvm-svn: 75640
* 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. llvm-svn: 75379
* Convert more assert(0)+abort() -> LLVM_UNREACHABLE,Torok Edwin2009-07-111-4/+8
| | | | | | and abort()/exit() -> llvm_report_error(). llvm-svn: 75363
* Avoid compiler warnings if assertions turned off.Duncan Sands2009-07-101-0/+2
| | | | llvm-svn: 75267
* 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. llvm-svn: 75097
* 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. llvm-svn: 74601
* 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. llvm-svn: 74580
* 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. llvm-svn: 74518
* When doing remat, don't consider uses of non-allocatable physregs. Patch Chris Lattner2009-06-271-0/+4
| | | | | | by Evan. llvm-svn: 74370
* More VNInfo tweaking, plus a little progress on intra-block splitting.Lang Hames2009-06-191-2/+4
| | | | llvm-svn: 73750
* Improved PHI def marking, replaced some gotos with breaks.Lang Hames2009-06-181-5/+7
| | | | llvm-svn: 73727
* VNInfo cleanup.Lang Hames2009-06-171-26/+27
| | | | llvm-svn: 73634
* Move register allocation preference (or hint) from LiveInterval to ↵Evan Cheng2009-06-141-1/+1
| | | | | | MachineRegisterInfo. This allows more passes to set them. llvm-svn: 73346
* Update to in-place spilling framework. Includes live interval scaling and ↵Lang Hames2009-06-021-0/+44
| | | | | | trivial rewriter. llvm-svn: 72729
* 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. llvm-svn: 72426
* 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. llvm-svn: 70787
* Fix PR4076. Correctly create live interval of physical register with ↵Evan Cheng2009-04-271-10/+20
| | | | | | two-address update. llvm-svn: 70245
* 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. llvm-svn: 70213
* 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. llvm-svn: 69743
* 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. llvm-svn: 69585
* Don't abort on an aliasing physical register that does not haveDan Gohman2009-04-131-1/+1
| | | | | | a live interval. This is needed for some upcoming subreg changes. llvm-svn: 68956
* Fix pr3954. The register scavenger asserts for inline assembly withBob Wilson2009-04-091-1/+1
| | | | | | | | | | | | 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). llvm-svn: 68714
* Implement support for using modeling implicit-zero-extension on x86-64Dan Gohman2009-04-081-1/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 68576
* Don't assign a new stack slot if the pre-alloc splitter already assigned one.Owen Anderson2009-03-261-2/+9
| | | | llvm-svn: 67764
* Fix PR3391 and PR3864. Reg allocator infinite looping.Evan Cheng2009-03-231-4/+8
| | | | llvm-svn: 67544
* Model inline asm constraint which ties an input to an output register as ↵Evan Cheng2009-03-231-4/+6
| | | | | | 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. llvm-svn: 67512
* Fix the Win32 VS2008 build:Sebastian Redl2009-03-191-1/+1
| | | | | | | | | | - Make type declarations match the struct/class keyword of the definition. - Move AddSignalHandler into the namespace where it belongs. - Correctly call functions from template base. - Some other small changes. With this patch, LLVM and Clang should build properly and with far less noise under VS2008. llvm-svn: 67347
* Added MachineInstr::isRegTiedToDefOperand to check for two-addressness.Evan Cheng2009-03-191-6/+2
| | | | llvm-svn: 67335
* Fix how livein live intervals are handled. Previously it could end at MBB ↵Evan Cheng2009-03-051-4/+9
| | | | | | start. Sorry, no small test case possible. llvm-svn: 66129
* Fix PR3486. Fix a bug in code that manually patch physical register live ↵Evan Cheng2009-02-081-2/+9
| | | | | | interval after its sub-register is coalesced with a virtual register. llvm-svn: 64082
* Exit with nice warnings when register allocator run out of registers.Evan Cheng2009-01-291-1/+13
| | | | llvm-svn: 63267
* Change TargetInstrInfo::isMoveInstr to return source and destination ↵Evan Cheng2009-01-201-10/+10
| | | | | | sub-register indices as well. llvm-svn: 62600
* The coalescer does not coalesce a virtual register to a physical register if ↵Evan Cheng2009-01-071-3/+49
| | | | | | | | | | | | | | any of the physical register's sub-register live intervals overlaps with the virtual register. This is overly conservative. It prevents a extract_subreg from being coalesced away: v1024 = EDI // not killed = = EDI One possible solution is for the coalescer to examine the sub-register live intervals in the same manner as the physical register. Another possibility is to examine defs and uses (when needed) of sub-registers. Both solutions are too expensive. For now, look for "short virtual intervals" and scan instructions to look for conflict instead. This is a small win on x86-64. e.g. It shaves 403.gcc by ~80 instructions. llvm-svn: 61847
* Fix PR3149. If an early clobber def is a physical register and it is tied to ↵Evan Cheng2008-12-191-7/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | an input operand, it effectively extends the live range of the physical register. Currently we do not have a good way to represent this. 172 %ECX<def> = MOV32rr %reg1039<kill> 180 INLINEASM <es:subl $5,$1 sbbl $3,$0>, 10, %EAX<def>, 14, %ECX<earlyclobber,def>, 9, %EAX<kill>, 36, <fi#0>, 1, %reg0, 0, 9, %ECX<kill>, 36, <fi#1>, 1, %reg0, 0 188 %EAX<def> = MOV32rr %EAX<kill> 196 %ECX<def> = MOV32rr %ECX<kill> 204 %ECX<def> = MOV32rr %ECX<kill> 212 %EAX<def> = MOV32rr %EAX<kill> 220 %EAX<def> = MOV32rr %EAX 228 %reg1039<def> = MOV32rr %ECX<kill> The early clobber operand ties ECX input to the ECX def. The live interval of ECX is represented as this: %reg20,inf = [46,47:1)[174,230:0) 0@174-(230) 1@46-(47) The right way to represent this is something like %reg20,inf = [46,47:2)[174,182:1)[181:230:0) 0@174-(182) 1@181-230 @2@46-(47) Of course that won't work since that means overlapping live ranges defined by two val#. The workaround for now is to add a bit to val# which says the val# is redefined by a early clobber def somewhere. This prevents the move at 228 from being optimized away by SimpleRegisterCoalescing::AdjustCopiesBackFrom. llvm-svn: 61259
OpenPOWER on IntegriCloud