summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Clarify some comments.Dan Gohman2008-12-081-2/+2
| | | | llvm-svn: 60683
* Reason #3 from 60595 doesn't hold true. If we can fold a PIC load from ↵Evan Cheng2008-12-051-9/+11
| | | | | | constpool into a use, the rewrite happens at time of spill (not in VirtRegMap). Later on, if the GlobalBaseReg is spilled, the spiller can see the use uses GlobalBaseReg and do the right thing. llvm-svn: 60596
* Fix comment.Evan Cheng2008-12-051-1/+1
| | | | llvm-svn: 60592
* Drop the reg argument to isRegReDefinedByTwoAddr, which was redundant.Dan Gohman2008-12-051-1/+1
| | | | llvm-svn: 60586
* Rename isSimpleLoad to canFoldAsLoad, to better reflect its meaning.Dan Gohman2008-12-031-3/+3
| | | | llvm-svn: 60487
* LiveRanges are represented as half-open ranges. Fix the findLiveInMBBs codeDan Gohman2008-11-261-1/+1
| | | | | | | and the LiveInterval.h top-level comment and accordingly. This fixes blocks having spurious live-in registers in boundary cases. llvm-svn: 60092
* Silence unused variable warnings.Devang Patel2008-11-211-0/+1
| | | | llvm-svn: 59841
* Use find_first/find_next to iterate through all the set bits in aDan Gohman2008-11-131-8/+7
| | | | | | BitVector, instead of manually testing each bit. llvm-svn: 59246
* Remove some debugging code made redundant by the change to doDan Gohman2008-11-121-8/+0
| | | | | | | coalescing as a separate pass rather than inside of LiveIntervalAnalysis. llvm-svn: 59146
* - Rewrite code that update register live interval that's split.Evan Cheng2008-10-291-3/+24
| | | | | | | - Create and update spill slot live intervals. - Lots of bug fixes. llvm-svn: 58367
* Fix PR2634. Create new virtual registers from spills early so that weDavid Greene2008-10-271-8/+19
| | | | | | | can give it the same stack slot as the spilled interval if it is folded. This prevents the fold/unfold code from pointing to the wrong register. llvm-svn: 58255
* Avoid splitting an interval multiple times; avoid splitting ↵Evan Cheng2008-10-241-0/+9
| | | | | | re-materializable val# (for now). llvm-svn: 58068
* By min, I mean max.Evan Cheng2008-10-181-1/+1
| | | | llvm-svn: 57766
OpenPOWER on IntegriCloud