summaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAge
* Replacing HUGE_VALF with llvm::huge_valf in order to work around a warning ↵Aaron Ballman2013-11-13
| | | | | | | | triggered in MSVC 12. Patch reviewed by Reid Kleckner and Jim Grosbach. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194533 91177308-0d34-0410-b5e6-96231b3b80d8
* CalcSpillWeights: give a better describing name to calculateSpillWeightsArnaud A. de Grandmaison2013-11-11
| | | | | | | | Besides, this relates it more obviously to the VirtRegAuxInfo::calculateSpillWeightAndHint. No functionnal change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194404 91177308-0d34-0410-b5e6-96231b3b80d8
* CalculateSpillWeights does not need to be a passArnaud A. de Grandmaison2013-11-10
| | | | | | | | | | Based on discussions with Lang Hames and Jakob Stoklund Olesen at the hacker's lab, and in the light of upcoming work on the PBQP register allocator, it was though that CalcSpillWeights does not need to be a pass. This change will enable to customize / tune the spill weight computation depending on the allocator. Update the documentation style while there. No functionnal change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194356 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "CalculateSpillWeights does not need to be a pass"Arnaud A. de Grandmaison2013-11-08
| | | | | | Temporarily revert my previous commit until I understand why it breaks 3 target tests. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194272 91177308-0d34-0410-b5e6-96231b3b80d8
* CalculateSpillWeights does not need to be a passArnaud A. de Grandmaison2013-11-08
| | | | | | | | | | Based on discussions with Lang Hames and Jakob Stoklund Olesen at the hacker's lab, and in the light of upcoming work on the PBQP register allocator, it was though that CalcSpillWeights does not need to be a pass. This change will enable to customize / tune the spill weight computation depending on the allocator. Update the documentation style while there. No functionnal change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194269 91177308-0d34-0410-b5e6-96231b3b80d8
* Represent RegUnit liveness with LiveRange instanceMatthias Braun2013-10-10
| | | | | | | Previously LiveInterval has been used, but having a spill weight and register number is unnecessary for a register unit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192397 91177308-0d34-0410-b5e6-96231b3b80d8
* Explicitly request unsigned enum types when desiredReid Kleckner2013-10-08
| | | | | | | This fixes repeated -Wmicrosoft warnings when self-hosting clang on Windows, and gets us real unsigned enum types with MSVC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192227 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix unused variables.Eli Friedman2013-09-10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190448 91177308-0d34-0410-b5e6-96231b3b80d8
* Track new virtual registers by register number.Mark Lacey2013-08-14
| | | | | | | | | | Track new virtual registers by register number, rather than by the live interval created for them. This is the first step in separating the creation of new virtual registers and new live intervals. Eventually live intervals will be created and populated on demand after the virtual registers have been created and used in instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188434 91177308-0d34-0410-b5e6-96231b3b80d8
* Down-scale slot index distance to save bits.Andrew Trick2013-07-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187438 91177308-0d34-0410-b5e6-96231b3b80d8
* RegAllocGreedy comment.Andrew Trick2013-07-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187141 91177308-0d34-0410-b5e6-96231b3b80d8
* Evict local live ranges if they can be reassigned.Andrew Trick2013-07-25
| | | | | | | | | | | | | | | | The previous change to local live range allocation also suppressed eviction of local ranges. In rare cases, this could result in more expensive register choices. This commit actually revives a feature that I added long ago: check if live ranges can be reassigned before eviction. But now it only happens in rare cases of evicting a local live range because another local live range wants a cheaper register. The benefit is improved code size for some benchmarks on x86 and armv7. I measured no significant compile time increase and performance changes are noise. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187140 91177308-0d34-0410-b5e6-96231b3b80d8
* Allocate local registers in order for optimal coloring.Andrew Trick2013-07-25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Also avoid locals evicting locals just because they want a cheaper register. Problem: MI Sched knows exactly how many registers we have and assumes they can be colored. In cases where we have large blocks, usually from unrolled loops, greedy coloring fails. This is a source of "regressions" from the MI Scheduler on x86. I noticed this issue on x86 where we have long chains of two-address defs in the same live range. It's easy to see this in matrix multiplication benchmarks like IRSmk and even the unit test misched-matmul.ll. A fundamental difference between the LLVM register allocator and conventional graph coloring is that in our model a live range can't discover its neighbors, it can only verify its neighbors. That's why we initially went for greedy coloring and added eviction to deal with the hard cases. However, for singly defined and two-address live ranges, we can optimally color without visiting neighbors simply by processing the live ranges in instruction order. Other beneficial side effects: It is much easier to understand and debug regalloc for large blocks when the live ranges are allocated in order. Yes, global allocation is still very confusing, but it's nice to be able to comprehend what happened locally. Heuristics could be added to bias register assignment based on instruction locality (think late register pairing, banks...). Intuituvely this will make some test cases that are on the threshold of register pressure more stable. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187139 91177308-0d34-0410-b5e6-96231b3b80d8
* Dump LIS before regalloc. MI sched changes them.Andrew Trick2013-07-25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187107 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove floats from live range splitting costs.Jakob Stoklund Olesen2013-07-16
| | | | | | | | | | These floats all represented block frequencies anyway, so just use the BlockFrequency class directly. Some floating point computations remain in tryLocalSplit(). They are estimating spill weights which are still floats. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186435 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.Benjamin Kramer2013-06-17
| | | | | | | | | | | | | | | | | | 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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@184105 91177308-0d34-0410-b5e6-96231b3b80d8
* Use only explicit bool conversion operatorsDavid Blaikie2013-05-15
| | | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181868 91177308-0d34-0410-b5e6-96231b3b80d8
* Replace uses of the deprecated std::auto_ptr with OwningPtr.Andy Gibbs2013-04-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179373 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unused #includes.Bill Wendling2013-03-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176467 91177308-0d34-0410-b5e6-96231b3b80d8
* Limit the search space in RAGreedy::tryEvict().Jakob Stoklund Olesen2013-01-12
| | | | | | | When tryEvict() is looking for a cheaper register in the allocation order, skip the tail of too expensive registers when possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172281 91177308-0d34-0410-b5e6-96231b3b80d8
* Speed up the AllocationOrder class a bit.Jakob Stoklund Olesen2012-12-04
| | | | | | | Allow the central functions to be inlined, and use the argumentless isHint() function when possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169319 91177308-0d34-0410-b5e6-96231b3b80d8
* Add VirtRegMap::hasKnownPreference().Jakob Stoklund Olesen2012-12-03
| | | | | | | | Virtual registers with a known preferred register are prioritized by RAGreedy. This function makes the condition explicit without depending on getRegAllocPref(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169179 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-03
| | | | | | | | | | | | | | | | | 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. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
* Make the LiveRegMatrix analysis available to targets.Jakob Stoklund Olesen2012-11-28
| | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168806 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a significant recent(?) regression. StackSlotColoring no longer did anythingEvan Cheng2012-09-21
| | | | | | | | | | because LiveStackAnalysis was not preserved by VirtRegWriter. This caused big stack usage regression in some cases. rdar://12340383 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164408 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a couple of Doxygen comment issues pointed out by -Wdocumentation.Dmitri Gribenko2012-09-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163721 91177308-0d34-0410-b5e6-96231b3b80d8
* Tidy up a few more uses of MF.getFunction()->getName().David Blaikie2012-08-22
| | | | | | | | 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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162367 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a getName function to MachineFunction. Use it in places that previously ↵Craig Topper2012-08-22
| | | | | | did getFunction()->getName(). Remove includes of Function.h that are no longer needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162347 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unnecessary cast that was also unnecessarily casting away constness.David Blaikie2012-08-21
| | | | | | | | | | 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)? git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162301 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove LiveIntervalUnions from RegAllocBase.Jakob Stoklund Olesen2012-06-20
| | | | | | They are living in LiveRegMatrix now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158868 91177308-0d34-0410-b5e6-96231b3b80d8
* Convert RAGreedy to LiveRegMatrix interference checking.Jakob Stoklund Olesen2012-06-20
| | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158867 91177308-0d34-0410-b5e6-96231b3b80d8
* Also compute MBB live-in lists in the new rewriter pass.Jakob Stoklund Olesen2012-06-09
| | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158249 91177308-0d34-0410-b5e6-96231b3b80d8
* Reintroduce VirtRegRewriter.Jakob Stoklund Olesen2012-06-08
| | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158244 91177308-0d34-0410-b5e6-96231b3b80d8
* Round 2 of dead private variable removal.Benjamin Kramer2012-06-06
| | | | | | | | LLVM is now -Wunused-private-field clean except for - lib/MC/MCDisassembler/Disassembler.h. Not sure why it keeps all those unaccessible fields. - gtest. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158096 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch all register list clients to the new MC*Iterator interface.Jakob Stoklund Olesen2012-06-01
| | | | | | | | | | | | | 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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157854 91177308-0d34-0410-b5e6-96231b3b80d8
* Prioritize smaller register classes for urgent evictions.Jakob Stoklund Olesen2012-05-30
| | | | | | | | | | | | | | 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> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157715 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a last resort tryInstructionSplit() to RAGreedy.Jakob Stoklund Olesen2012-05-23
| | | | | | | | | | | | | 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> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157354 91177308-0d34-0410-b5e6-96231b3b80d8
* Allow LiveRangeEdit to be created with a NULL parent.Jakob Stoklund Olesen2012-05-19
| | | | | | The dead code elimination with callbacks is still useful. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157100 91177308-0d34-0410-b5e6-96231b3b80d8
* Moved LiveRangeEdit.h so that it can be called from other parts of the ↵Pete Cooper2012-04-02
| | | | | | backend, not just libCodeGen git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153906 91177308-0d34-0410-b5e6-96231b3b80d8
* Allocate virtual registers in ascending order.Jakob Stoklund Olesen2012-04-02
| | | | | | | | | This is just the fallback tie-breaker ordering, the main allocation order is still descending size. Patch by Shamil Kurmangaleev! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153904 91177308-0d34-0410-b5e6-96231b3b80d8
* Refactored the LiveRangeEdit interface so that MachineFunction, ↵Pete Cooper2012-04-02
| | | | | | TargetInstrInfo, MachineRegisterInfo, LiveIntervals, and VirtRegMap are all passed into the constructor and stored as members instead of passed in to each method. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153903 91177308-0d34-0410-b5e6-96231b3b80d8
* Use uint16_t to store register overlaps to reduce static data.Craig Topper2012-03-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152001 91177308-0d34-0410-b5e6-96231b3b80d8
* Clear virtual registers after they are no longer referenced.Andrew Trick2012-02-21
| | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151032 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix details in local live range splitting with regmasks.Jakob Stoklund Olesen2012-02-14
| | | | | | | Perform all comparisons at instruction granularity, and make sure register masks on uses count in both gaps. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150530 91177308-0d34-0410-b5e6-96231b3b80d8
* Handle register masks in local live range splitting.Jakob Stoklund Olesen2012-02-11
| | | | | | | Again the goal is to produce identical assembly with register mask operands enabled. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150287 91177308-0d34-0410-b5e6-96231b3b80d8
* Add register mask support to InterferenceCache.Jakob Stoklund Olesen2012-02-10
| | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150259 91177308-0d34-0410-b5e6-96231b3b80d8
* RegAlloc superpass: includes phi elimination, coalescing, and scheduling.Andrew Trick2012-02-10
| | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150226 91177308-0d34-0410-b5e6-96231b3b80d8
* Add register mask support to RAGreedy.Jakob Stoklund Olesen2012-02-09
| | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150191 91177308-0d34-0410-b5e6-96231b3b80d8
* Renamed MachineScheduler to ScheduleTopDownLive.Andrew Trick2012-01-17
| | | | | | Responding to code review. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148290 91177308-0d34-0410-b5e6-96231b3b80d8
* Moving options declarations around.Andrew Trick2012-01-17
| | | | | | More short term hackery until we have a way to configure passes that work on LiveIntervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148289 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-14 13:02:16 +0000