aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegAllocGreedy.cpp
AgeCommit message (Collapse)Author
2011-02-19Separate timers for local and global splitting.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126001 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-18Add VirtRegMap::rewrite() and use it in the new register allocators.Jakob Stoklund Olesen
The rewriter works almost identically to -rewriter=trivial, except it also eliminates any identity copies. This makes the new register allocators independent of VirtRegRewriter.cpp which will be going away at the same time as RegAllocLinearScan. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125967 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-17Add basic register allocator statistics.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125789 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-17Split local live ranges.Jakob Stoklund Olesen
A local live range is live in a single basic block. If such a range fails to allocate, try to find a sub-range that would get a larger spill weight than its interference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125764 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-09Simplify using the new leaveIntvBefore()Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125238 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-09Move calcLiveBlockInfo() and the BlockInfo struct into SplitAnalysis.Jakob Stoklund Olesen
No functional changes intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125231 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-09Evict a lighter single interference before attempting to split a live range.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125151 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-08Fix one more case of splitting after the last split point.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125137 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-08Reorganize interference code to check LastSplitPoint first.Jakob Stoklund Olesen
The last split point can be anywhere in the block, so it interferes with the strictly monotonic requirements of advanceTo(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125132 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-08Also handle the situation where an indirect branch is the first (and last)Jakob Stoklund Olesen
instruction in a basic block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125116 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-08Add LiveIntervals::addKillFlags() to recompute kill flags after register ↵Jakob Stoklund Olesen
allocation. This is a lot easier than trying to get kill flags right during live range splitting and rematerialization. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125113 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-08Trim debug spewJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125109 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-08Add SplitEditor::overlapIntv() to create small ranges where both registers ↵Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125102 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-05Be more strict about the first/last interference-free use.Jakob Stoklund Olesen
If the interference overlaps the instruction, we cannot separate it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124918 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-05Add assertions to verify that the new interval is clear of the interference.Jakob Stoklund Olesen
If these inequalities don't hold, we are creating a live range split that won't allocate. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124917 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-04Be more accurate about live range splitting at the end of blocks.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124900 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-04Verify that one of the ranges produced by region splitting is allocatable.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124893 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-04Also compute interference intervals for blocks with no uses.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124839 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Ensure that the computed interference intervals actually overlap their basic ↵Jakob Stoklund Olesen
blocks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124815 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Return live range end points from SplitEditor::enter*/leave*.Jakob Stoklund Olesen
These end points come from the inserted copies, and can be passed directly to useIntv. This simplifies the coloring code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124799 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Reapply this.Eric Christopher
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124779 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Temporarily revert 124765 in an attempt to find the cycle breaking bootstrap.Eric Christopher
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124778 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Defer SplitKit value mapping until all defs are available.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124765 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-20SplitKit requires that all defs are in place before calling useIntv().Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123926 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-19Don't accidentally leave small gaps in the live ranges when leaving the activeJakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123858 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-19Implement RAGreedy::splitAroundRegion and remove loop splitting.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123853 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-18Add RAGreedy methods for splitting live ranges around regions.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123774 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-28Pacify the compiler. BestWeight cannot in fact be used uninitializedDuncan Sands
in this function, but the compiler was warning that it might be when doing a release build. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122595 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-22When RegAllocGreedy decides to spill the interferences of the current register,Jakob Stoklund Olesen
pick the victim with the lowest total spill weight. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122445 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-18Tweak debug spew.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122132 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-18Fix GCC warning:Nick Lewycky
lib/CodeGen/RegAllocGreedy.cpp:311: error: unused variable 'PhysReg' [-Wunused-variable] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122122 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-18Pass a Banner argument to the machine code verifier both fromJakob Stoklund Olesen
createMachineVerifierPass and MachineFunction::verify. The banner is printed before the machine code dump, just like the printer pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122113 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-17Make the -verify-regalloc command line option available to base classes asJakob Stoklund Olesen
RegAllocBase::VerifyEnabled. Run the machine code verifier in a few interesting places during RegAllocGreedy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122107 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-17Enable loop splitting in RegAllocGreedy.Jakob Stoklund Olesen
The heuristics split around the largest loop where the current register may be allocated without interference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122106 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-15Start using SplitKit and MachineLoopRanges in RegAllocGreedy in preparation ofJakob Stoklund Olesen
live range splitting around loops guided by register pressure. So far, trySplit() simply prints a lot of debug output. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121918 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-14Simplify RegAllocGreedy's use of register aliases.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121807 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-14Move debugging code entirely within DEBUG(). Silences an unused variableMatt Beaumont-Gay
warning in the opt build. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121791 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-14Add LiveIntervalUnion print methods, RegAllocGreedy::trySplit debug spew.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121783 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-14Q.seenAllInterferences() must be called after Q.collectInterferingVRegs().Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121774 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-14Remove unused vector.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121741 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-14Try reassigning all virtual register interferences, not just those with lowerJakob Stoklund Olesen
spill weight. Filter out fixed registers instead. Add support for reassigning an interference that was assigned to an alias. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121737 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-14Add stub for RAGreedy::trySplit.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121736 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-11Add named timer groups for the different stages of register allocation.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121604 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-10Move MRI into RegAllocBase. Clean up debug output a bit.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121599 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-10Remove extraneous close parenthesis.Nick Lewycky
Fix build breakage. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121596 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-10Move variable that's unused in an NDEBUG build inside the DEBUG() macro, fixingNick Lewycky
lib/CodeGen/RegAllocGreedy.cpp:233: error: unused variable 'TRC' [-Wunused-variable] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121594 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-10Force the greedy register allocator to always use the inline spiller.Jakob Stoklund Olesen
Soon, RegAllocGreedy will start splitting live ranges, and then deferred spilling won't work anyway. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121591 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-10Use AllocationOrder in RegAllocGreedy, fix a bug in the hint calculation.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121584 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-10Fix miscompilation caused by trivial logic error in the reassignVReg()Jakob Stoklund Olesen
interference check. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121519 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-09Remember to filter out reserved rergisters from the allocation order.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121411 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-30 04:28:27 +0000