summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocLinearScan.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Change errs() to dbgs().David Greene2010-01-051-32/+32
| | | | llvm-svn: 92583
* Fix a bunch of little errors that Clang complains about when its being pedanticDouglas Gregor2009-12-191-1/+1
| | | | llvm-svn: 91764
* Moved spill weight calculation out of SimpleRegisterCoalescing and into its ↵Lang Hames2009-12-141-0/+2
| | | | | | own pass: CalculateSpillWeights. llvm-svn: 91273
* Also attempt trivial coalescing for live intervals that end in a copy.Jakob Stoklund Olesen2009-12-101-44/+54
| | | | | | | | | | | | | | | The coalescer is supposed to clean these up, but when setting up parameters for a function call, there may be copies to physregs. If the defining instruction has been LICM'ed far away, the coalescer won't touch it. The register allocation hint does not always work - when the register allocator is backtracking, it clears the hints. This patch is more conservative than r90502, and does not break 483.xalancbmk/i686. It still breaks the PowerPC bootstrap, so it is disabled by default, and can be enabled with the -trivial-coalesce-ends option. llvm-svn: 91049
* Added a new "splitting" spiller.Lang Hames2009-12-091-9/+6
| | | | | | | | | | | | | When a call is placed to spill an interval this spiller will first try to break the interval up into its component values. Single value intervals and intervals which have already been split (or are the result of previous splits) are spilled by the default spiller. Splitting intervals as described above may improve the performance of generated code in some circumstances. This work is experimental however, and it still miscompiles many benchmarks. It's not recommended for general use yet. llvm-svn: 90951
* Temporarily revert r90502. It was causing the llvm-gcc bootstrap on PPC to fail.Bill Wendling2009-12-051-48/+44
| | | | llvm-svn: 90653
* Also attempt trivial coalescing for live intervals that end in a copy.Jakob Stoklund Olesen2009-12-041-44/+48
| | | | | | | | | | | | | The coalescer is supposed to clean these up, but when setting up parameters for a function call, there may be copies to physregs. If the defining instruction has been LICM'ed far away, the coalescer won't touch it. The register allocation hint does not always work - when the register allocator is backtracking, it clears the hints. This patch takes care of a few more cases that r90163 missed. llvm-svn: 90502
* Cleanups.David Greene2009-11-201-3/+6
| | | | | | Make things a little more efficient as suggested by Evan. llvm-svn: 89489
* Removed references to LiveStacks from Spiller.* . They're no longer needed.Lang Hames2009-11-201-1/+1
| | | | llvm-svn: 89422
* Fix a small bug.David Greene2009-11-191-1/+1
| | | | | | | Fix one case we missed to make sure we reserve registers from allocation. llvm-svn: 89376
* Add support for spreading register allocation.David Greene2009-11-191-7/+60
| | | | | | | | | | | | | Add a -linearscan-skip-count argument (default to 0) that tells the allocator to remember the last N registers it allocated and skip them when looking for a register candidate. This tends to spread out register usage and free up post-allocation scheduling at the cost of slightly more register pressure. The primary benefit is the ability to backschedule reloads. This is turned off by default. llvm-svn: 89356
* Added a new Spiller implementation which wraps ↵Lang Hames2009-11-191-18/+3
| | | | | | | | | | LiveIntervals::addIntervalsForSpills. All spiller calls in RegAllocLinearScan now go through the new Spiller interface. The "-new-spill-framework" command line option has been removed. To use the trivial in-place spiller you should now pass "-spiller=trivial -rewriter=trivial". (Note the trivial spiller/rewriter are only meant to serve as examples of the new in-place modification work. Enabling them will yield terrible, though hopefully functional, code). llvm-svn: 89311
* The Indexes Patch.Lang Hames2009-11-031-23/+32
| | | | | | | | | | | | | | | | This introduces a new pass, SlotIndexes, which is responsible for numbering instructions for register allocation (and other clients). SlotIndexes numbering is designed to match the existing scheme, so this patch should not cause any changes in the generated code. For consistency, and to avoid naming confusion, LiveIndex has been renamed SlotIndex. The processImplicitDefs method of the LiveIntervals analysis has been moved into its own pass so that it can be run prior to SlotIndexes. This was necessary to match the existing numbering scheme. llvm-svn: 85979
* Remove includes of Support/Compiler.h that are no longer needed after theNick Lewycky2009-10-251-1/+0
| | | | | | VISIBILITY_HIDDEN removal. llvm-svn: 85043
* Remove VISIBILITY_HIDDEN from class/struct found inside anonymous namespaces.Nick Lewycky2009-10-251-1/+1
| | | | | | | Chris claims we should never have visibility_hidden inside any .cpp file but that's still not true even after this commit. llvm-svn: 85042
* Renamed MachineInstrIndex to LiveIndex.Lang Hames2009-10-031-12/+12
| | | | llvm-svn: 83254
* Simplify a few more uses of reg_iterator.Dan Gohman2009-09-251-3/+3
| | | | llvm-svn: 82812
* Replaces uses of unsigned for indexes in LiveInterval and VNInfo withLang Hames2009-09-041-22/+25
| | | | | | | | 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. llvm-svn: 81040
* Kill off more cerr/cout uses and prune includes a bit.Benjamin Kramer2009-08-231-1/+1
| | | | llvm-svn: 79852
* Convert DOUT to DEBUG(errs()...).Bill Wendling2009-08-221-55/+67
| | | | llvm-svn: 79756
* 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-1/+3
| | | | | | | | | | - 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
* 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
* Removed some junk code that snuck in to an earlier commit.Lang Hames2009-07-131-5/+0
| | | | llvm-svn: 75450
* Convert more assert(0)+abort() -> LLVM_UNREACHABLE,Torok Edwin2009-07-111-3/+4
| | | | | | and abort()/exit() -> llvm_report_error(). llvm-svn: 75363
* Handle IMPLICIT_DEF with isUndef operand marker, part 2. This patch moves ↵Evan Cheng2009-07-011-31/+0
| | | | | | 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-0/+11
| | | | | | | | | | 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
* - Update register allocation hint after coalescing. This is done by the ↵Evan Cheng2009-06-181-2/+8
| | | | | | | | | target since the hint is target dependent. This is important for ARM register pair hints. - Register allocator should resolve the second part of the hint (register number) before passing it to the target since it knows virtual register to physical register mapping. - More fixes to get ARM load / store double word working. llvm-svn: 73671
* VNInfo cleanup.Lang Hames2009-06-171-3/+3
| | | | llvm-svn: 73634
* Part 1.Evan Cheng2009-06-151-12/+13
| | | | | | | | | | | | | | | | | | | | | - Change register allocation hint to a pair of unsigned integers. The hint type is zero (which means prefer the register specified as second part of the pair) or entirely target dependent. - Allow targets to specify alternative register allocation orders based on allocation hint. Part 2. - Use the register allocation hint system to implement more aggressive load / store multiple formation. - Aggressively form LDRD / STRD. These are formed *before* register allocation. It has to be done this way to shorten live interval of base and offset registers. e.g. v1025 = LDR v1024, 0 v1026 = LDR v1024, 0 => v1025,v1026 = LDRD v1024, 0 If this transformation isn't done before allocation, v1024 will overlap v1025 which means it more difficult to allocate a register pair. - Even with the register allocation hint, it may not be possible to get the desired allocation. In that case, the post-allocation load / store multiple pass must fix the ldrd / strd instructions. They can either become ldm / stm instructions or back to a pair of ldr / str instructions. This is work in progress, not yet enabled. llvm-svn: 73381
* 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
OpenPOWER on IntegriCloud