summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Allow LiveRangeEdit to be created with a NULL parent.Jakob Stoklund Olesen2012-05-191-4/+4
| | | | | | The dead code elimination with callbacks is still useful. llvm-svn: 157100
* Moved LiveRangeEdit.h so that it can be called from other parts of the ↵Pete Cooper2012-04-021-1/+1
| | | | | | backend, not just libCodeGen llvm-svn: 153906
* Allocate virtual registers in ascending order.Jakob Stoklund Olesen2012-04-021-2/+2
| | | | | | | | | This is just the fallback tie-breaker ordering, the main allocation order is still descending size. Patch by Shamil Kurmangaleev! llvm-svn: 153904
* Refactored the LiveRangeEdit interface so that MachineFunction, ↵Pete Cooper2012-04-021-4/+4
| | | | | | TargetInstrInfo, MachineRegisterInfo, LiveIntervals, and VirtRegMap are all passed into the constructor and stored as members instead of passed in to each method. llvm-svn: 153903
* Use uint16_t to store register overlaps to reduce static data.Craig Topper2012-03-041-3/+3
| | | | llvm-svn: 152001
* Clear virtual registers after they are no longer referenced.Andrew Trick2012-02-211-1/+4
| | | | | | | | | | | | | Passes after RegAlloc should be able to rely on MRI->getNumVirtRegs() == 0. This makes sharing code for pre/postRA passes more robust. Now, to check if a pass is running before the RA pipeline begins, use MRI->isSSA(). To check if a pass is running after the RA pipeline ends, use !MRI->getNumVirtRegs(). PEI resets virtual regs when it's done scavenging. PTX will either have to provide its own PEI pass or assign physregs. llvm-svn: 151032
* Fix details in local live range splitting with regmasks.Jakob Stoklund Olesen2012-02-141-6/+16
| | | | | | | Perform all comparisons at instruction granularity, and make sure register masks on uses count in both gaps. llvm-svn: 150530
* Handle register masks in local live range splitting.Jakob Stoklund Olesen2012-02-111-0/+25
| | | | | | | Again the goal is to produce identical assembly with register mask operands enabled. llvm-svn: 150287
* Add register mask support to InterferenceCache.Jakob Stoklund Olesen2012-02-101-1/+1
| | | | | | | | | | | | | | | | This makes global live range splitting behave identically with and without register mask operands. This is not necessarily the best way of using register masks for live range splitting. It would be more efficient to first split global live ranges around calls (i.e., register masks), and reserve the fine grained per-physreg interference guidance for global live ranges that do not cross calls. For now the goal is to produce identical assembly when enabling register masks. llvm-svn: 150259
* RegAlloc superpass: includes phi elimination, coalescing, and scheduling.Andrew Trick2012-02-101-13/+0
| | | | | | | | | | | | | | | | Creates a configurable regalloc pipeline. Ensure specific llc options do what they say and nothing more: -reglloc=... has no effect other than selecting the allocator pass itself. This patch introduces a new umbrella flag, "-optimize-regalloc", to enable/disable the optimizing regalloc "superpass". This allows for example testing coalscing and scheduling under -O0 or vice-versa. When a CodeGen pass requires the MachineFunction to have a particular property, we need to explicitly define that property so it can be directly queried rather than naming a specific Pass. For example, to check for SSA, use MRI->isSSA, not addRequired<PHIElimination>. CodeGen transformation passes are never "required" as an analysis ProcessImplicitDefs does not require LiveVariables. We have a plan to massively simplify some of the early passes within the regalloc superpass. llvm-svn: 150226
* Add register mask support to RAGreedy.Jakob Stoklund Olesen2012-02-091-2/+25
| | | | | | | | This only adds the interference checks required for correctness. We still need to take advantage of register masks for the interference driven live range splitting. llvm-svn: 150191
* Renamed MachineScheduler to ScheduleTopDownLive.Andrew Trick2012-01-171-2/+2
| | | | | | Responding to code review. llvm-svn: 148290
* Moving options declarations around.Andrew Trick2012-01-171-0/+7
| | | | | | More short term hackery until we have a way to configure passes that work on LiveIntervals. llvm-svn: 148289
* Added the MachineSchedulerPass skeleton.Andrew Trick2012-01-131-0/+3
| | | | llvm-svn: 148105
* Make SplitAnalysis::UseSlots private.Jakob Stoklund Olesen2012-01-121-3/+3
| | | | llvm-svn: 148031
* Make data structures private.Jakob Stoklund Olesen2012-01-111-2/+2
| | | | llvm-svn: 147979
* Stop tracking spill slot uses in VirtRegMap.Jakob Stoklund Olesen2011-11-131-6/+0
| | | | | | | Nobody cared, StackSlotColoring scans the instructions to find used stack slots. llvm-svn: 144485
* Update split candidate correctly when interference cache is full.Jakob Stoklund Olesen2011-11-011-0/+2
| | | | | | No test case, spotted by inspection. llvm-svn: 143407
* Ignore the cloning of unknown registers.Jakob Stoklund Olesen2011-09-141-0/+4
| | | | | | | | THe LRE_DidCloneVirtReg callback may be called with vitual registers that RAGreedy doesn't even know about yet. In that case, there are no data structures to update. llvm-svn: 139702
* Remove the -compact-regions flag.Jakob Stoklund Olesen2011-09-121-11/+5
| | | | | | | It has been enabled by default for a while, it was only there to allow performance comparisons. llvm-svn: 139501
* Add an interface for SplitKit complement spill modes.Jakob Stoklund Olesen2011-09-121-2/+11
| | | | | | | | | | | | | | | | | | | | | | | | | SplitKit always computes a complement live range to cover the places where the original live range was live, but no explicit region has been allocated. Currently, the complement live range is created to be as small as possible - it never overlaps any of the regions. This minimizes register pressure, but if the complement is going to be spilled anyway, that is not very important. The spiller will eliminate redundant spills, and hoist others by making the spill slot live range overlap some of the regions created by splitting. Stack slots are cheap. This patch adds the interface to enable spill modes in SplitKit. In spill mode, SplitKit will assume that the complement is going to spill, so it will allow it to overlap regions in order to avoid back-copies. By doing some of the spiller's work early, the complement live range becomes simpler. In some cases, it can become much simpler because no extra PHI-defs are required. This will speed up both splitting and spilling. This is only the interface to enable spill modes, no implementation yet. llvm-svn: 139500
* Make a bunch of symbols private.Benjamin Kramer2011-08-191-1/+1
| | | | llvm-svn: 138025
* Refer to the RegisterCoalescer pass by ID.Jakob Stoklund Olesen2011-08-091-2/+1
| | | | | | | A public interface is no longer needed since RegisterCoalescer is not an analysis any more. llvm-svn: 137082
* Fix typo. Thanks, Andy!Jakob Stoklund Olesen2011-08-061-1/+1
| | | | llvm-svn: 137023
* Reject RS_Spill ranges from local splitting as well.Jakob Stoklund Olesen2011-08-051-4/+4
| | | | | | | All new local ranges are marked as RS_New now, so there is no need to attempt splitting of RS_Spill ranges any more. llvm-svn: 137002
* Only mark remainder intervals as RS_Spill after per-block splitting.Jakob Stoklund Olesen2011-08-051-2/+12
| | | | | | | | | | The local ranges created get to stay in the RS_New stage, just like for local and region splitting. This gives tryLocalSplit a bit more freedom the first time it sees one of these new local ranges. llvm-svn: 137001
* Remember to update LiveDebugVariables after per-block splitting.Jakob Stoklund Olesen2011-08-051-1/+5
| | | | llvm-svn: 136996
* Extract per-block splitting into its own method.Jakob Stoklund Olesen2011-08-051-23/+36
| | | | | | No functional change. llvm-svn: 136994
* Also use shouldSplitSingleBlock() in the fallback splitting mode.Jakob Stoklund Olesen2011-08-051-8/+18
| | | | | | | Drop the use of SplitAnalysis::getMultiUseBlocks, there is no need to go through a SmallPtrSet any more. llvm-svn: 136992
* Split around single instructions to enable register class inflation.Jakob Stoklund Olesen2011-08-051-1/+7
| | | | | | | | | | | | | Normally, we don't create a live range for a single instruction in a basic block, the spiller does that anyway. However, when splitting a live range that belongs to a proper register sub-class, inserting these extra COPY instructions completely remove the constraints from the remainder interval, and it may be allocated from the larger super-class. The spiller will mop up these small live ranges if we end up spilling anyway. It calls them snippets. llvm-svn: 136989
* Enable compact region splitting by default.Jakob Stoklund Olesen2011-08-031-1/+1
| | | | | | | | | | | This helps generate better code in functions with high register pressure. The previous version of compact region splitting caused regressions because the regions were a bit too large. A stronger negative bias applied in r136832 fixed this problem. llvm-svn: 136836
* Be more conservative when forming compact regions.Jakob Stoklund Olesen2011-08-031-1/+3
| | | | | | | | | | | | | | | Apply twice the negative bias on transparent blocks when computing the compact regions. This excludes loop backedges from the region when only one of the loop blocks uses the register. Previously, we would include the backedge in the region if the loop preheader and the loop latch both used the register, but the loop header didn't. When both the header and latch blocks use the register, we still keep it live on the backedge. llvm-svn: 136832
* Fix some warnings from Clang in release builds:Chandler Carruth2011-08-031-0/+2
| | | | | | | | | | | lib/CodeGen/RegAllocGreedy.cpp:1176:18: warning: unused variable 'B' [-Wunused-variable] if (unsigned B = Cand.getBundles(BundleCand, BestCand)) { ^ lib/CodeGen/RegAllocGreedy.cpp:1188:18: warning: unused variable 'B' [-Wunused-variable] if (unsigned B = Cand.getBundles(BundleCand, 0)) { ^ llvm-svn: 136831
* Use the precomputed def presence in RAGreedy::calcSpillCost.Jakob Stoklund Olesen2011-08-021-11/+2
| | | | llvm-svn: 136742
* Inform SpillPlacement about blocks with defs.Jakob Stoklund Olesen2011-08-021-0/+1
| | | | | | This information is not used for anything yet. llvm-svn: 136741
* Rename {First,Last}Use to {First,Last}Instr.Jakob Stoklund Olesen2011-08-021-10/+12
| | | | | | | With a 'FirstDef' field right there, it is very confusing that FirstUse refers to an instruction that may be a def. llvm-svn: 136739
* Time the emission of debug values.Jakob Stoklund Olesen2011-07-311-1/+4
| | | | llvm-svn: 136584
* Revert r136528 "Enable compact region splitting by default."Jakob Stoklund Olesen2011-07-301-1/+1
| | | | | | | While this generally helped x86-64, there was some large regressions for i386. llvm-svn: 136571
* Enable compact region splitting by default.Jakob Stoklund Olesen2011-07-291-1/+1
| | | | | | | This helps generate better code in functions with high register pressure. llvm-svn: 136528
* Reverse order of RS_Split live ranges under -compact-regions.Jakob Stoklund Olesen2011-07-281-3/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | There are two conflicting strategies in play: - Under high register pressure, we want to assign large live ranges first. Smaller live ranges are easier to place afterwards. - Live range splitting is guided by interference, so splitting should be deferred until interference is as realistic as possible. With the recent changes to the live range stages, and with compact regions enabled, it is less traumatic to split a live range too early. If some of the split products were too big, they can often be split again. By reversing the RS_Split order, we get this queue order: 1. Normal live ranges, large to small. 2. RS_Split live ranges, large to small. The large-to-small order improves RAGreedy's puzzle solving skills under high register pressure. It may cause a bit more iterated splitting, but we handle that better now. With this change, -compact-regions is mostly an improvement on SPEC. llvm-svn: 136388
* Add support for multi-way live range splitting.Jakob Stoklund Olesen2011-07-261-64/+165
| | | | | | | | | | | | | | | | | | | | | When splitting global live ranges, it is now possible to split for multiple destination intervals at once. Previously, we only had the main and stack intervals. Each edge bundle is assigned to a split candidate, and splitAroundRegion will insert copies between the candidate intervals and the stack interval as needed. The multi-way splitting is used to split around compact regions when enabled with -compact-regions. The best candidate register still gets all the bundles it wants, but everything outside the main interval is first split around compact regions before we create single-block intervals. Compact region splitting still causes some regressions, so it is not enabled by default. llvm-svn: 136186
* Revert to RA_Assign when a virtreg separates into components.Jakob Stoklund Olesen2011-07-261-1/+3
| | | | | | | | | | | | | When dead code elimination deletes a PHI value, the virtual register may split into multiple connected components. In that case, revert each component to the RS_Assign stage. The new components are guaranteed to be smaller (the original value numbers are distributed among the components), so this will always be making progress. The components are now allowed to evict other live ranges or be split again. llvm-svn: 136034
* Add an RS_Split2 stage used for loop prevention.Jakob Stoklund Olesen2011-07-251-15/+24
| | | | | | | | | | | | | | | | This mechanism already exists, but the RS_Split2 stage makes it clearer. When live range splitting creates ranges that may not be making progress, they are marked RS_Split2 instead of RS_New. These ranges may be split again, but only in a way that can be proven to make progress. For local ranges, that means they must be split into ranges used by strictly fewer instructions. For global ranges, region splitting is bypassed and the RS_Split2 ranges go straight to per-block splitting. llvm-svn: 135912
* Rename live range stages to better reflect how they are used.Jakob Stoklund Olesen2011-07-251-32/+40
| | | | | | | | | | | | The stage is used to control where a live range is going, not where it is coming from. Live ranges created by splitting will usually be marked RS_New, but some are marked RS_Spill to avoid wasting time trying to split them again. The old RS_Global and RS_Local stages are merged - they are really the same thing for local and global live ranges. llvm-svn: 135911
* Add RAGreedy::calcCompactRegion.Jakob Stoklund Olesen2011-07-231-0/+46
| | | | | | | | | | | | | | | | This method computes the edge bundles that should be live when splitting around a compact region. This is independent of interference. The function returns false if the live range was already a compact region, or the compact region doesn't have any live bundles - it would be the same as splitting around basic blocks. Compact regions are computed using the normal spill placement code. We pretend there is interference in all live-through blocks that don't use the live range. This removes all edges from the Hopfield network used for spill placement, so it converges instantly. llvm-svn: 135847
* Prepare RAGreedy::growRegion for compact regions.Jakob Stoklund Olesen2011-07-231-1/+8
| | | | | | | | | | | | | | | A split candidate can have a null PhysReg which means that it doesn't map to a real interference pattern. Instead, pretend that all through blocks have interference. This makes it possible to generate compact regions where the live range doesn't go through blocks that don't use it. The live range will still be live between directly connected blocks with uses. Splitting around a compact region tends to produce a live range with a high spill weight, so it may evict a less dense live range. llvm-svn: 135845
* Migrate LLVM and Clang to use the new makeArrayRef(...) functions where ↵Frits van Bommel2011-07-181-4/+3
| | | | | | | | previously explicit non-default constructors were used. Mostly mechanical with some manual reformatting. llvm-svn: 135390
* Remove unused LoopRanges from RegAllocGreedy.Jakub Staszak2011-07-161-6/+0
| | | | llvm-svn: 135354
* Extract parts of RAGreedy::splitAroundRegion as SplitKit methods.Jakob Stoklund Olesen2011-07-151-299/+13
| | | | | | | | | | | This gets rid of some of the gory splitting details in RAGreedy and makes them available to future SplitKit clients. Slightly generalize the functionality to support multi-way splitting. Specifically, SplitEditor::splitLiveThroughBlock() supports switching between different register intervals in a block. llvm-svn: 135307
* Reapply r135121 with a fixed copy constructor.Jakob Stoklund Olesen2011-07-141-5/+16
| | | | | | | | | | | | | | | | | | | | | Original commit message: Count references to interference cache entries. Each InterferenceCache::Cursor instance references a cache entry. A non-zero reference count guarantees that the entry won't be reused for a new register. This makes it possible to have multiple live cursors examining interference for different physregs. The total number of live cursors into a cache must be kept below InterferenceCache::getMaxCursors(). Code generation should be unaffected by this change, and it doesn't seem to affect the cache replacement strategy either. llvm-svn: 135130
OpenPOWER on IntegriCloud