summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.Benjamin Kramer2013-06-171-1/+6
| | | | | | | | | | | | | | | | | | The main advantages here are way better heuristics, taking into account not just loop depth but also __builtin_expect and other static heuristics and will eventually learn how to use profile info. Most of the work in this patch is pushing the MachineBlockFrequencyInfo analysis into the right places. This is good for a 5% speedup on zlib's deflate (x86_64), there were some very unfortunate spilling decisions in its hottest loop in longest_match(). Other benchmarks I tried were mostly neutral. This changes register allocation in subtle ways, update the tests for it. 2012-02-20-MachineCPBug.ll was deleted as it's very fragile and the instruction it looked for was gone already (but the FileCheck pattern picked up unrelated stuff). llvm-svn: 184105
* Use only explicit bool conversion operatorsDavid Blaikie2013-05-151-1/+1
| | | | | | | | | | | | | | | | | | | | | | | BitVector/SmallBitVector::reference::operator bool remain implicit since they model more exactly a bool, rather than something else that can be boolean tested. The most common (non-buggy) case are where such objects are used as return expressions in bool-returning functions or as boolean function arguments. In those cases I've used (& added if necessary) a named function to provide the equivalent (or sometimes negative, depending on convenient wording) test. One behavior change (YAMLParser) was made, though no test case is included as I'm not sure how to reach that code path. Essentially any comparison of llvm::yaml::document_iterators would be invalid if neither iterator was at the end. This helped uncover a couple of bugs in Clang - test cases provided for those in a separate commit along with similar changes to `operator bool` instances in Clang. llvm-svn: 181868
* Replace uses of the deprecated std::auto_ptr with OwningPtr.Andy Gibbs2013-04-121-3/+3
| | | | llvm-svn: 179373
* Remove unused #includes.Bill Wendling2013-03-051-1/+0
| | | | llvm-svn: 176467
* Limit the search space in RAGreedy::tryEvict().Jakob Stoklund Olesen2013-01-121-1/+18
| | | | | | | When tryEvict() is looking for a cheaper register in the allocation order, skip the tail of too expensive registers when possible. llvm-svn: 172281
* Speed up the AllocationOrder class a bit.Jakob Stoklund Olesen2012-12-041-2/+2
| | | | | | | Allow the central functions to be inlined, and use the argumentless isHint() function when possible. llvm-svn: 169319
* Add VirtRegMap::hasKnownPreference().Jakob Stoklund Olesen2012-12-031-1/+1
| | | | | | | | Virtual registers with a known preferred register are prioritized by RAGreedy. This function makes the condition explicit without depending on getRegAllocPref(). llvm-svn: 169179
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-7/+6
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Make the LiveRegMatrix analysis available to targets.Jakob Stoklund Olesen2012-11-281-2/+2
| | | | | | | | | | | No functional change, just moved header files. Targets can inject custom passes between register allocation and rewriting. This makes it possible to tweak the register allocation before rewriting, using the full global interference checking available from LiveRegMatrix. llvm-svn: 168806
* Fix a significant recent(?) regression. StackSlotColoring no longer did anythingEvan Cheng2012-09-211-1/+1
| | | | | | | | | because LiveStackAnalysis was not preserved by VirtRegWriter. This caused big stack usage regression in some cases. rdar://12340383 llvm-svn: 164408
* Fix a couple of Doxygen comment issues pointed out by -Wdocumentation.Dmitri Gribenko2012-09-121-1/+1
| | | | llvm-svn: 163721
* Tidy up a few more uses of MF.getFunction()->getName().David Blaikie2012-08-221-2/+1
| | | | | | | | Based on CR feedback from r162301 and Craig Topper's refactoring in r162347 here are a few other places that could use the same API (& in one instance drop a Function.h dependency). llvm-svn: 162367
* Add a getName function to MachineFunction. Use it in places that previously ↵Craig Topper2012-08-221-2/+1
| | | | | | did getFunction()->getName(). Remove includes of Function.h that are no longer needed. llvm-svn: 162347
* Remove unnecessary cast that was also unnecessarily casting away constness.David Blaikie2012-08-211-1/+1
| | | | | | | | | | Even looking at the revision history I couldn't quite piece together why this cast was ever written in the first place, but I assume it was because of some change in the inheritance, perhaps this function was reimplemented in a derived type & this caller was meant to get the base version (& it wasn't virtual)? llvm-svn: 162301
* Remove LiveIntervalUnions from RegAllocBase.Jakob Stoklund Olesen2012-06-201-3/+3
| | | | | | They are living in LiveRegMatrix now. llvm-svn: 158868
* Convert RAGreedy to LiveRegMatrix interference checking.Jakob Stoklund Olesen2012-06-201-55/+75
| | | | | | | | | | | | | | | | | Stop depending on the LiveIntervalUnions in RegAllocBase, they are about to be removed. The changes are mostly replacing register alias iterators with regunit iterators, and querying LiveRegMatrix instrad of RegAllocBase. InterferenceCache is converted to work with per-regunit LiveIntervalUnions, and it checks fixed regunit interference separately, using the fixed live intervals provided by LiveIntervalAnalysis. The local splitting helper calcGapWeights() is also considering fixed regunit interference which is kept on the side now. llvm-svn: 158867
* Also compute MBB live-in lists in the new rewriter pass.Jakob Stoklund Olesen2012-06-091-1/+0
| | | | | | | | | This deduplicates some code from the optimizing register allocators, and it means that it is now possible to change the register allocators' solutions simply by editing the VirtRegMap between the register allocator pass and the rewriter. llvm-svn: 158249
* Reintroduce VirtRegRewriter.Jakob Stoklund Olesen2012-06-081-19/+1
| | | | | | | | | | | | | | | | | | OK, not really. We don't want to reintroduce the old rewriter hacks. This patch extracts virtual register rewriting as a separate pass that runs after the register allocator. This is possible now that CodeGen/Passes.cpp can configure the full optimizing register allocator pipeline. The rewriter pass uses register assignments in VirtRegMap to rewrite virtual registers to physical registers, and it inserts kill flags based on live intervals. These finalization steps are the same for the optimizing register allocators: RABasic, RAGreedy, and PBQP. llvm-svn: 158244
* Round 2 of dead private variable removal.Benjamin Kramer2012-06-061-1/+0
| | | | | | | | LLVM is now -Wunused-private-field clean except for - lib/MC/MCDisassembler/Disassembler.h. Not sure why it keeps all those unaccessible fields. - gtest. llvm-svn: 158096
* Switch all register list clients to the new MC*Iterator interface.Jakob Stoklund Olesen2012-06-011-5/+5
| | | | | | | | | | | | | No functional change intended. Sorry for the churn. The iterator classes are supposed to help avoid giant commits like this one in the future. The TableGen-produced register lists are getting quite large, and it may be necessary to change the table representation. This makes it possible to do so without changing all clients (again). llvm-svn: 157854
* Prioritize smaller register classes for urgent evictions.Jakob Stoklund Olesen2012-05-301-1/+7
| | | | | | | | | | | | | | It helps compile exotic inline asm. In the test case, normal GR32 virtual registers use up eax-edx so the final GR32_ABCD live range has no registers left. Since all the live ranges were tiny, we had no way of prioritizing the smaller register class. This patch allows tiny unspillable live ranges to be evicted by tiny unspillable live ranges from a smaller register class. <rdar://problem/11542429> llvm-svn: 157715
* Add a last resort tryInstructionSplit() to RAGreedy.Jakob Stoklund Olesen2012-05-231-1/+65
| | | | | | | | | | | | | Live ranges with a constrained register class may benefit from splitting around individual uses. It allows the remaining live range to use a larger register class where it may allocate. This is like spilling to a different register class. This is only attempted on constrained register classes. <rdar://problem/11438902> llvm-svn: 157354
* 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
OpenPOWER on IntegriCloud