summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Simplify using the new leaveIntvBefore()Jakob Stoklund Olesen2011-02-091-13/+2
| | | | llvm-svn: 125238
* Move calcLiveBlockInfo() and the BlockInfo struct into SplitAnalysis.Jakob Stoklund Olesen2011-02-091-143/+20
| | | | | | No functional changes intended. llvm-svn: 125231
* Evict a lighter single interference before attempting to split a live range.Jakob Stoklund Olesen2011-02-091-29/+41
| | | | | | | | | | | | | | Registers are not allocated strictly in spill weight order when live range splitting and spilling has created new shorter intervals with higher spill weights. When one of the new heavy intervals conflicts with a single lighter interval, simply evict the old interval instead of trying to split the heavy one. The lighter interval is a better candidate for splitting, it has a smaller use density. llvm-svn: 125151
* Fix one more case of splitting after the last split point.Jakob Stoklund Olesen2011-02-081-8/+10
| | | | llvm-svn: 125137
* Reorganize interference code to check LastSplitPoint first.Jakob Stoklund Olesen2011-02-081-29/+43
| | | | | | | The last split point can be anywhere in the block, so it interferes with the strictly monotonic requirements of advanceTo(). llvm-svn: 125132
* Also handle the situation where an indirect branch is the first (and last)Jakob Stoklund Olesen2011-02-081-6/+8
| | | | | | instruction in a basic block. llvm-svn: 125116
* Add LiveIntervals::addKillFlags() to recompute kill flags after register ↵Jakob Stoklund Olesen2011-02-081-0/+1
| | | | | | | | | allocation. This is a lot easier than trying to get kill flags right during live range splitting and rematerialization. llvm-svn: 125113
* Trim debug spewJakob Stoklund Olesen2011-02-081-1/+0
| | | | llvm-svn: 125109
* Add SplitEditor::overlapIntv() to create small ranges where both registers ↵Jakob Stoklund Olesen2011-02-081-2/+25
| | | | | | | | | | | | | | | | | | | | | | are live. If a live range is used by a terminator instruction, and that live range needs to leave the block on the stack or in a different register, it can be necessary to have both sides of the split live at the terminator instruction. Example: %vreg2 = COPY %vreg1 JMP %vreg1 Becomes after spilling %vreg2: SPILL %vreg1 JMP %vreg1 The spill doesn't kill the register as is normally the case. llvm-svn: 125102
* Be more strict about the first/last interference-free use.Jakob Stoklund Olesen2011-02-051-4/+25
| | | | | | If the interference overlaps the instruction, we cannot separate it. llvm-svn: 124918
* Add assertions to verify that the new interval is clear of the interference.Jakob Stoklund Olesen2011-02-051-7/+14
| | | | | | | If these inequalities don't hold, we are creating a live range split that won't allocate. llvm-svn: 124917
* Be more accurate about live range splitting at the end of blocks.Jakob Stoklund Olesen2011-02-041-4/+17
| | | | | | | | | | | If interference reaches the last split point, it is effectively live out and should be marked as 'MustSpill'. This can make a difference when the terminator uses a register. There is no way that register can be reused in the outgoing CFG bundle, even if it isn't live out. llvm-svn: 124900
* Verify that one of the ranges produced by region splitting is allocatable.Jakob Stoklund Olesen2011-02-041-1/+15
| | | | | | | We should not be attempting a region split if it won't lead to at least one directly allocatable interval. That could cause infinite splitting loops. llvm-svn: 124893
* Also compute interference intervals for blocks with no uses.Jakob Stoklund Olesen2011-02-041-3/+1
| | | | | | | | When the live range is live through a block that doesn't use the register, but that has interference, region splitting wants to split at the top and bottom of the basic block. llvm-svn: 124839
* Ensure that the computed interference intervals actually overlap their basic ↵Jakob Stoklund Olesen2011-02-031-3/+12
| | | | | | blocks. llvm-svn: 124815
* Return live range end points from SplitEditor::enter*/leave*.Jakob Stoklund Olesen2011-02-031-12/+8
| | | | | | | These end points come from the inserted copies, and can be passed directly to useIntv. This simplifies the coloring code. llvm-svn: 124799
* Reapply this.Eric Christopher2011-02-031-12/+3
| | | | llvm-svn: 124779
* Temporarily revert 124765 in an attempt to find the cycle breaking bootstrap.Eric Christopher2011-02-031-3/+12
| | | | llvm-svn: 124778
* Defer SplitKit value mapping until all defs are available.Jakob Stoklund Olesen2011-02-031-12/+3
| | | | | | | | | | | | | | | | | | | The greedy register allocator revealed some problems with the value mapping in SplitKit. We would sometimes start mapping values before all defs were known, and that could change a value from a simple 1-1 mapping to a multi-def mapping that requires ssa update. The new approach collects all defs and register assignments first without filling in any live intervals. Only when finish() is called, do we compute liveness and mapped values. At this time we know with certainty which values map to multiple values in a split range. This also has the advantage that we can compute live ranges based on the remaining uses after rematerializing at split points. The current implementation has many opportunities for compile time optimization. llvm-svn: 124765
* SplitKit requires that all defs are in place before calling useIntv().Jakob Stoklund Olesen2011-01-201-10/+22
| | | | | | | | | | | The value mapping gets confused about which original values have multiple new definitions so they may need phi insertions. This could probably be simplified by letting enterIntvBefore() take a live range to be added following the instruction. As long as the range stays inside the same basic block, value mapping shouldn't be a problem. llvm-svn: 123926
* Don't accidentally leave small gaps in the live ranges when leaving the activeJakob Stoklund Olesen2011-01-191-2/+3
| | | | | | | | | | interval after an instruction. The leaveIntvAfter() method only adds liveness from the instruction's boundary index to the inserted copy. Ideally, SplitKit should be smarter about this, perhaps by combining useIntv() and leaveIntvAfter() into one method that guarantees continuity. llvm-svn: 123858
* Implement RAGreedy::splitAroundRegion and remove loop splitting.Jakob Stoklund Olesen2011-01-191-98/+290
| | | | | | | | | | | | | | Region splitting includes loop splitting as a subset, and it is more generic. The splitting heuristics for variables that are live in more than one block are now: 1. Try to create a region that covers multiple basic blocks. 2. Try to create a new live range for each block with multiple uses. 3. Spill. Steps 2 and 3 are similar to what the standard spiller is doing. llvm-svn: 123853
* Add RAGreedy methods for splitting live ranges around regions.Jakob Stoklund Olesen2011-01-181-0/+340
| | | | | | | | | | Analyze the live range's behavior entering and leaving basic blocks. Compute an interference pattern for each allocation candidate, and use SpillPlacement to find an optimal region where that register can be live. This code is still not enabled. llvm-svn: 123774
* Pacify the compiler. BestWeight cannot in fact be used uninitializedDuncan Sands2010-12-281-1/+1
| | | | | | | in this function, but the compiler was warning that it might be when doing a release build. llvm-svn: 122595
* When RegAllocGreedy decides to spill the interferences of the current register,Jakob Stoklund Olesen2010-12-221-37/+89
| | | | | | pick the victim with the lowest total spill weight. llvm-svn: 122445
* Tweak debug spew.Jakob Stoklund Olesen2010-12-181-2/+4
| | | | llvm-svn: 122132
* Fix GCC warning:Nick Lewycky2010-12-181-0/+1
| | | | | | lib/CodeGen/RegAllocGreedy.cpp:311: error: unused variable 'PhysReg' [-Wunused-variable] llvm-svn: 122122
* Pass a Banner argument to the machine code verifier both fromJakob Stoklund Olesen2010-12-181-2/+2
| | | | | | | | createMachineVerifierPass and MachineFunction::verify. The banner is printed before the machine code dump, just like the printer pass. llvm-svn: 122113
* Make the -verify-regalloc command line option available to base classes asJakob Stoklund Olesen2010-12-171-0/+6
| | | | | | | | RegAllocBase::VerifyEnabled. Run the machine code verifier in a few interesting places during RegAllocGreedy. llvm-svn: 122107
* Enable loop splitting in RegAllocGreedy.Jakob Stoklund Olesen2010-12-171-23/+64
| | | | | | | The heuristics split around the largest loop where the current register may be allocated without interference. llvm-svn: 122106
* Start using SplitKit and MachineLoopRanges in RegAllocGreedy in preparation ofJakob Stoklund Olesen2010-12-151-9/+37
| | | | | | | | live range splitting around loops guided by register pressure. So far, trySplit() simply prints a lot of debug output. llvm-svn: 121918
* Simplify RegAllocGreedy's use of register aliases.Jakob Stoklund Olesen2010-12-141-17/+4
| | | | llvm-svn: 121807
* Move debugging code entirely within DEBUG(). Silences an unused variableMatt Beaumont-Gay2010-12-141-8/+8
| | | | | | warning in the opt build. llvm-svn: 121791
* Add LiveIntervalUnion print methods, RegAllocGreedy::trySplit debug spew.Jakob Stoklund Olesen2010-12-141-0/+8
| | | | llvm-svn: 121783
* Q.seenAllInterferences() must be called after Q.collectInterferingVRegs().Jakob Stoklund Olesen2010-12-141-2/+4
| | | | llvm-svn: 121774
* Remove unused vector.Jakob Stoklund Olesen2010-12-141-1/+1
| | | | llvm-svn: 121741
* Try reassigning all virtual register interferences, not just those with lowerJakob Stoklund Olesen2010-12-141-49/+71
| | | | | | | | spill weight. Filter out fixed registers instead. Add support for reassigning an interference that was assigned to an alias. llvm-svn: 121737
* Add stub for RAGreedy::trySplit.Jakob Stoklund Olesen2010-12-141-0/+16
| | | | llvm-svn: 121736
* Add named timer groups for the different stages of register allocation.Jakob Stoklund Olesen2010-12-111-9/+15
| | | | llvm-svn: 121604
* Move MRI into RegAllocBase. Clean up debug output a bit.Jakob Stoklund Olesen2010-12-101-14/+1
| | | | llvm-svn: 121599
* Remove extraneous close parenthesis.Nick Lewycky2010-12-101-1/+1
| | | | | | Fix build breakage. llvm-svn: 121596
* Move variable that's unused in an NDEBUG build inside the DEBUG() macro, fixingNick Lewycky2010-12-101-3/+4
| | | | | | lib/CodeGen/RegAllocGreedy.cpp:233: error: unused variable 'TRC' [-Wunused-variable] llvm-svn: 121594
* Force the greedy register allocator to always use the inline spiller.Jakob Stoklund Olesen2010-12-101-1/+1
| | | | | | | Soon, RegAllocGreedy will start splitting live ranges, and then deferred spilling won't work anyway. llvm-svn: 121591
* Use AllocationOrder in RegAllocGreedy, fix a bug in the hint calculation.Jakob Stoklund Olesen2010-12-101-21/+6
| | | | llvm-svn: 121584
* Fix miscompilation caused by trivial logic error in the reassignVReg()Jakob Stoklund Olesen2010-12-101-10/+16
| | | | | | interference check. llvm-svn: 121519
* Remember to filter out reserved rergisters from the allocation order.Jakob Stoklund Olesen2010-12-091-1/+1
| | | | llvm-svn: 121411
* Added register reassignment prototype to RAGreedy. It's a simpleAndrew Trick2010-12-091-9/+108
| | | | | | | heuristic to reshuffle register assignments when we can't find an available reg. llvm-svn: 121388
* Properly deal with empty intervals when checking for interference.Jakob Stoklund Olesen2010-12-081-0/+1
| | | | llvm-svn: 121319
* Implement very primitive hinting support in RegAllocGreedy.Jakob Stoklund Olesen2010-12-081-1/+25
| | | | | | | The hint is simply tried first and then forgotten if it couldn't be allocated immediately. llvm-svn: 121306
* Store (priority,regnum) pairs in the priority queue instead of providing anJakob Stoklund Olesen2010-12-081-0/+2
| | | | | | | | | | | | | | | | | | | | | | | abstract priority queue interface in subclasses that want to override the priority calculations. Subclasses must provide a getPriority() implementation instead. This approach requires less code as long as priorities are expressable as simple floats, and it avoids the dangers of defining potentially expensive priority comparison functions. It also should speed up priority_queue operations since they no longer have to chase pointers when comparing registers. This is not measurable, though. Preferably, we shouldn't use floats to guide code generation. The use of floats here is derived from the use of floats for spill weights. Spill weights have a dynamic range that doesn't lend itself easily to a fixpoint implementation. When someone invents a stable spill weight representation, it can be reused for allocation priorities. llvm-svn: 121294
OpenPOWER on IntegriCloud