summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocLinearScan.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Move register allocation preference (or hint) from LiveInterval to ↵Evan Cheng2009-06-141-13/+17
| | | | | | MachineRegisterInfo. This allows more passes to set them. llvm-svn: 73346
* RALinScan::attemptTrivialCoalescing() was returning a virtual register ↵Evan Cheng2009-06-041-3/+9
| | | | | | instead of the physical register it is allocated to. This resulted in virtual register(s) being added the live-in sets. llvm-svn: 72890
* A value defined by an implicit_def can be liven to a use BB. This is ↵Evan Cheng2009-06-041-0/+18
| | | | | | unfortunate. But register allocator still has to add it to the live-in set of the use BB. llvm-svn: 72889
* Remove a #include of <iostream>.Dan Gohman2009-06-041-1/+0
| | | | llvm-svn: 72828
* Removed more testing code that snuck in earlier.Lang Hames2009-06-041-20/+2
| | | | llvm-svn: 72825
* Fixed warning, removed some temporary validation code that snuck in during ↵Lang Hames2009-06-021-91/+0
| | | | | | my last commit. llvm-svn: 72735
* Update to in-place spilling framework. Includes live interval scaling and ↵Lang Hames2009-06-021-9/+132
| | | | | | trivial rewriter. llvm-svn: 72729
* New Spiller interface and trivial implementation.Lang Hames2009-05-181-2/+24
| | | | llvm-svn: 72030
* Teach TransferDeadness to delete truly dead instructions if they do not ↵Evan Cheng2009-05-121-8/+23
| | | | | | produce side effects. llvm-svn: 71606
* Renamed Spiller classes (plus uses and related files) to VirtRegRewriter.Lang Hames2009-05-061-4/+4
| | | | llvm-svn: 71057
* In some rare cases, the register allocator can spill registers but end up ↵Evan Cheng2009-05-031-17/+35
| | | | | | | | | | 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
* Code clean up. Bye bye PhysRegTracker.Evan Cheng2009-05-011-26/+83
| | | | llvm-svn: 70524
* spillPhysRegAroundRegDefsUses() may have invalidated iterators stored in ↵Evan Cheng2009-04-291-0/+9
| | | | | | fixed_ IntervalPtrs. Reset them. llvm-svn: 70378
* Determine allocation 'preference' with right register class. I haven't seen ↵Evan Cheng2009-04-291-8/+10
| | | | | | this changing codegen so no test case. llvm-svn: 70351
* It has finally happened. Spiller is now using live interval info.Evan Cheng2009-04-211-1/+1
| | | | | | 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
* - Remove an arbitrary spill weight tweak that should not have been there.Evan Cheng2009-04-201-5/+26
| | | | | | - Find more reloads from SS. llvm-svn: 69606
* Added a linearscan register allocation optimization. When the register ↵Evan Cheng2009-04-201-56/+189
| | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Fix a bug in spill weight computation. If the alias is a super-register, and ↵Evan Cheng2009-03-231-7/+34
| | | | | | | | | | | the super-register is in the register class we are trying to allocate. Then add the weight to all sub-registers of the super-register even if they are not aliases. e.g. allocating for GR32, bh is not used, updating bl spill weight. bl should get the same spill weight otherwise it will be choosen as a spill candidate since spilling bh doesn't make ebx available. This fix PR2866. llvm-svn: 67574
* Fix PR3391 and PR3864. Reg allocator infinite looping.Evan Cheng2009-03-231-2/+6
| | | | llvm-svn: 67544
* Convert VirtRegMap to a MachineFunctionPass.Owen Anderson2009-03-131-3/+4
| | | | llvm-svn: 66870
* Reorganization: Move the Spiller out of VirtRegMap.cpp into its own files. ↵Owen Anderson2009-03-111-0/+1
| | | | | | No (intended) functionality change. llvm-svn: 66720
* Change TargetInstrInfo::isMoveInstr to return source and destination ↵Evan Cheng2009-01-201-4/+6
| | | | | | sub-register indices as well. llvm-svn: 62600
* Make linear scan's trivial coalescer slightly more aggressive.Evan Cheng2009-01-201-6/+6
| | | | llvm-svn: 62547
* Tidy up #includes, deleting a bunch of unnecessary #includes.Dan Gohman2009-01-051-0/+1
| | | | llvm-svn: 61715
* - More pre-split fixes: spill slot live interval computation bug; restore ↵Evan Cheng2008-10-291-1/+1
| | | | | | | | point bug. - If a def is spilt, remember its spill index to allow its reuse. llvm-svn: 58375
* - Rewrite code that update register live interval that's split.Evan Cheng2008-10-291-1/+1
| | | | | | | - Create and update spill slot live intervals. - Lots of bug fixes. llvm-svn: 58367
* Committing a good chunk of the pre-register allocation live interval ↵Evan Cheng2008-10-231-0/+7
| | | | | | splitting pass. It's handling simple cases and appear to do good things. Next: avoid splitting an interval multiple times; renumber registers when possible; record stack slot live intervals for coloring; rematerialize defs when possible. llvm-svn: 58044
* Fix command-line option printing to print two spaces where needed,Dan Gohman2008-10-141-1/+1
| | | | | | | | | instead of requiring all "short description" strings to begin with two spaces. This makes these strings less mysterious, and it fixes some cases where short description strings mistakenly did not begin with two spaces. llvm-svn: 57521
* Add an option to enable StrongPHIElimination, for ease of testing.Owen Anderson2008-10-071-0/+3
| | | | llvm-svn: 57259
* Re-apply 56835 along with header file changes.Evan Cheng2008-09-301-2/+3
| | | | llvm-svn: 56848
* Revert commit 56835 since it breaks the build.Duncan Sands2008-09-301-3/+2
| | | | | | | | | | "If a re-materializable instruction has a register operand, the spiller will change the register operand's spill weight to HUGE_VAL to avoid it being spilled. However, if the operand is already in the queue ready to be spilled, avoid re-materializing it". llvm-svn: 56837
* If a re-materializable instruction has a register operand, the spiller will ↵Evan Cheng2008-09-301-2/+3
| | | | | | change the register operand's spill weight to HUGE_VAL to avoid it being spilled. However, if the operand is already in the queue ready to be spilled, avoid re-materializing it. llvm-svn: 56835
* Next round of earlyclobber handling. Approach theDale Johannesen2008-09-241-95/+4
| | | | | | | | | | RA problem by expanding the live interval of an earlyclobber def back one slot. Remove overlap-earlyclobber throughout. Remove earlyclobber bits and their handling from live internals. llvm-svn: 56539
* Teach coalescer about earlyclobber bits.Dale Johannesen2008-09-201-2/+5
| | | | | | Check bits for preferred register. llvm-svn: 56384
* Fix PR2808. When regalloc runs out of register, it spill a physical register ↵Evan Cheng2008-09-201-1/+4
| | | | | | around the live interval being allocated. Do not continue to try to spill another register, just grab the physical register and move on. llvm-svn: 56381
* Make earlyclobber stuff work when virtual regsDale Johannesen2008-09-191-8/+26
| | | | | | have previously been assigned conflicting physreg. llvm-svn: 56364
* Remove AsmThatEarlyClobber etc. from LiveIntervalAnalysisDale Johannesen2008-09-191-2/+71
| | | | | | | and redo as linked list walk. Logic moved into RA. Per review feedback. llvm-svn: 56326
* Somehow RegAllocLinearScan is keeping two pointers to MachineRegisterInfo.Evan Cheng2008-09-181-8/+6
| | | | llvm-svn: 56314
* Add a bit to mark operands of asm's that conflictDale Johannesen2008-09-171-2/+4
| | | | | | | | | with an earlyclobber operand elsewhere. Propagate this bit and the earlyclobber bit through SDISel. Change linear-scan RA not to allocate regs in a way that conflicts with an earlyclobber. See also comments. llvm-svn: 56290
* Fix PR2757. Ignore liveinterval register allocation preference if the ↵Evan Cheng2008-09-091-1/+1
| | | | | | preference register is not in the right register class. This can happen due to sub-register coalescing. llvm-svn: 56006
* Tidy up several unbeseeming casts from pointer to intptr_t.Dan Gohman2008-09-041-1/+1
| | | | llvm-svn: 55779
* Convert several std::vectors over to SmallVector, and use reserve() as ↵Owen Anderson2008-08-151-2/+4
| | | | | | appropriate for cases where std::vector is still used. llvm-svn: 54820
* Get rid of a use of std::map.Owen Anderson2008-08-131-2/+2
| | | | llvm-svn: 54770
* Make the allocation of LiveIntervals explicit, rather than holding them in ↵Owen Anderson2008-08-131-6/+6
| | | | | | | | the r2iMap_ by value. This will prevent references to them from being invalidated if the map is changed. llvm-svn: 54763
* Fix a compile-time regression introduced by my heuristic-changing patch. I ↵Owen Anderson2008-07-231-1/+1
| | | | | | | | | forgot to multiply the instruction count by a constant factor in a few places, which caused the register allocator to require many more iterations. llvm-svn: 53959
* Change the heuristics used in the coalescer, register allocator, and withinOwen Anderson2008-07-221-1/+2
| | | | | | | live intervals itself to use an instruction count approximation that is not affected by inserting empty indices. llvm-svn: 53937
* A brief survey of priority_queue usage in the tree turned this upDan Gohman2008-06-231-1/+1
| | | | | | as a questionable case, but the code isn't actually needed. llvm-svn: 52657
* Enhanced heuristic to determine the *best* register to spill. Instead of ↵Evan Cheng2008-06-201-66/+176
| | | | | | | | picking the register with the lowest spill weight. Consider (up to) 2 additional registers with spill weights that are close to the lowest spill weight. The one with fewest defs and uses that conflicts with the current interval (weighted by loop depth) is the spill candidate. This is not always a win, but there are much more wins than loses and wins tend to be more noticeable. llvm-svn: 52554
* Refine stack slot interval weight computation.Evan Cheng2008-06-061-8/+13
| | | | llvm-svn: 52040
* Add a stack slot coloring pass. Not yet enabled.Evan Cheng2008-06-041-1/+32
| | | | llvm-svn: 51934
OpenPOWER on IntegriCloud