summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* [NFC] fix trivial typos in commentsHiroshi Inoue2019-01-091-1/+1
| | | | llvm-svn: 350690
* [RegAllocGreedy] IMPLICIT_DEF values shouldn't prefer registersJohn Brawn2018-12-141-1/+4
| | | | | | | | | | | It costs nothing to spill an IMPLICIT_DEF value (the only spill code that's generated is a KILL of the value), so when creating split constraints if the live-out value is IMPLICIT_DEF the exit constraint should be DontCare instead of PrefReg. Differential Revision: https://reviews.llvm.org/D55652 llvm-svn: 349151
* [RegAllocGreedy] avoid using physreg candidates that cannot be correctly spilledDaniil Fukalov2018-09-251-9/+32
| | | | | | | | | | | | | | | | | | | For the AMDGPU target if a MBB contains exec mask restore preamble, SplitEditor may get state when it cannot insert a spill instruction. E.g. for a MIR bb.100: %1 = S_OR_SAVEEXEC_B64 %2, implicit-def $exec, implicit-def $scc, implicit $exec and if the regalloc will try to allocate a virtreg to the physreg already assigned to virtreg %1, it should insert spill instruction before the S_OR_SAVEEXEC_B64 instruction. But it is not possible since can generate incorrect code in terms of exec mask. The change makes regalloc to ignore such physreg candidates. Reviewed By: rampitec Differential Revision: https://reviews.llvm.org/D52052 llvm-svn: 343004
* [RegAllocGreedy] Fix crash in tryLocalSplitWalter Lee2018-09-201-1/+5
| | | | | | | | | | tryLocalSplit only handles a single use block, but an interval may have multiple use blocks. So don't crash in that case. This fixes PR38795. Differential revision: https://reviews.llvm.org/D52277 llvm-svn: 342682
* Remove FrameAccess struct from hasLoadFromStackSlotSander de Smalen2018-09-051-9/+8
| | | | | | | | | | | | | | This removes the FrameAccess struct that was added to the interface in D51537, since the PseudoValue from the MachineMemoryOperand can be safely casted to a FixedStackPseudoSourceValue. Reviewers: MatzeB, thegameg, javed.absar Reviewed By: thegameg Differential Revision: https://reviews.llvm.org/D51617 llvm-svn: 341454
* Extend hasStoreToStackSlot with list of FI accesses.Sander de Smalen2018-09-031-5/+11
| | | | | | | | | | | | | | | | | | For instructions that spill/fill to and from multiple frame-indices in a single instruction, hasStoreToStackSlot and hasLoadFromStackSlot should return an array of accesses, rather than just the first encounter of such an access. This better describes FI accesses for AArch64 (paired) LDP/STP instructions. Reviewers: t.p.northover, gberry, thegameg, rengolin, javed.absar, MatzeB Reviewed By: MatzeB Differential Revision: https://reviews.llvm.org/D51537 llvm-svn: 341301
* [RegAlloc][NFC] Fix the help string of the option "huge-size-for-split".Wei Mi2018-07-181-1/+2
| | | | llvm-svn: 337402
* [CodeGen] Fix inconsistent declaration parameter nameFangrui Song2018-07-161-1/+1
| | | | llvm-svn: 337200
* [RegAlloc] Skip global splitting if the live range is huge and its spill isWei Mi2018-07-161-0/+19
| | | | | | | | | | | | | | | | | | | | | | | trivially rematerializable. We run into a case where machineLICM hoists a large number of live ranges outside of a big loop because it thinks those live ranges are trivially rematerializable. In regalloc, global splitting is tried out first for those live ranges before they are spilled and rematerialized. Because the global splitting algorithm is quadratic, increasing a lot of global splitting candidates causes huge compile time increase (50s to 1400s on my local machine when compiling a module). However, we think for live ranges which are very large and are trivially rematerialiable, it is better to just skip global splitting so as to save compile time with little chance of sacrificing performance. We uses the segment size of live range to indirectly evaluate whether the global splitting of the live range can introduce high cost, and use an option as a knob to adjust the size limit threshold. Differential Revision: https://reviews.llvm.org/D49353 llvm-svn: 337186
* [NFC] fix trivial typos in commentsHiroshi Inoue2018-06-201-9/+9
| | | | llvm-svn: 335096
* [RegAllocGreedy] Use simpler map class for EvicteeInfo. NFCI.Nirav Dave2018-06-051-1/+1
| | | | | | | | RegAlloc keeps a insertion-time ordered map of evictee information, but we only use membership. Replace MapVector with contextually equivalent DenseMap which is smaller and faster. llvm-svn: 333981
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-94/+102
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-11/+11
| | | | | | | | | | | | | | | | We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
* Take into account the cost of local intervals when selecting split candidate.Marina Yatsina2018-01-311-12/+70
| | | | | | | | | | | | | When selecting a split candidate for region splitting, the register allocator tries to predict which candidate will have the cheapest spill cost. Global splitting may cause the creation of local intervals, and they might spill. This patch makes RA take into account the spill cost of local split intervals in use blocks (we already take into account the spill cost in through blocks). A flag ("-condsider-local-interval-cost") controls weather we do this advanced cost calculation (it's on by default for X86 target, off for the rest). Differential Revision: https://reviews.llvm.org/D41585 Change-Id: Icccb8ad2dbf13124f5d97a18c67d95aa6be0d14d llvm-svn: 323870
* [NFC] fix trivial typos in commentsHiroshi Inoue2018-01-171-2/+2
| | | | | | "the the" -> "the" llvm-svn: 322636
* LiveStacks: Rename LiveStack.{h|cpp} to LiveStacks.{h|cpp}; NFCMatthias Braun2017-12-181-1/+1
| | | | | | Filenames should match the name of the class they contain. llvm-svn: 321037
* MachineFunction: Return reference from getFunction(); NFCMatthias Braun2017-12-151-1/+1
| | | | | | The Function can never be nullptr so we can return a reference. llvm-svn: 320884
* Rename LiveIntervalAnalysis.h to LiveIntervals.hMatthias Braun2017-12-131-1/+1
| | | | | | | | | | Headers/Implementation files should be named after the class they declare/define. Also eliminated an `#include "llvm/CodeGen/LiveIntervalAnalysis.h"` in favor of `class LiveIntarvals;` llvm-svn: 320546
* [CodeGen] Unify MBB reference format in both MIR and debug outputFrancis Visoiu Mistrih2017-12-041-1/+1
| | | | | | | | | | | | | | | | As part of the unification of the debug format and the MIR format, print MBB references as '%bb.5'. The MIR printer prints the IR name of a MBB only for block definitions. * find . \( -name "*.mir" -o -name "*.cpp" -o -name "*.h" -o -name "*.ll" \) -type f -print0 | xargs -0 sed -i '' -E 's/BB#" << ([a-zA-Z0-9_]+)->getNumber\(\)/" << printMBBReference(*\1)/g' * find . \( -name "*.mir" -o -name "*.cpp" -o -name "*.h" -o -name "*.ll" \) -type f -print0 | xargs -0 sed -i '' -E 's/BB#" << ([a-zA-Z0-9_]+)\.getNumber\(\)/" << printMBBReference(\1)/g' * find . \( -name "*.txt" -o -name "*.s" -o -name "*.mir" -o -name "*.cpp" -o -name "*.h" -o -name "*.ll" \) -type f -print0 | xargs -0 sed -i '' -E 's/BB#([0-9]+)/%bb.\1/g' * grep -nr 'BB#' and fix Differential Revision: https://reviews.llvm.org/D40422 llvm-svn: 319665
* Mark all library options as hidden.Zachary Turner2017-12-011-4/+5
| | | | | | | | | | | | | | | | | These command line options are not intended for public use, and often don't even make sense in the context of a particular tool anyway. About 90% of them are already hidden, but when people add new options they forget to hide them, so if you were to make a brand new tool today, link against one of LLVM's libraries, and run tool -help you would get a bunch of junk that doesn't make sense for the tool you're writing. This patch hides these options. The real solution is to not have libraries defining command line options, but that's a much larger effort and not something I'm prepared to take on. Differential Revision: https://reviews.llvm.org/D40674 llvm-svn: 319505
* [CodeGen] Print "%vreg0" as "%0" in both MIR and debug outputFrancis Visoiu Mistrih2017-11-301-15/+15
| | | | | | | | | | | | | | | | | As part of the unification of the debug format and the MIR format, avoid printing "vreg" for virtual registers (which is one of the current MIR possibilities). Basically: * find . \( -name "*.mir" -o -name "*.cpp" -o -name "*.h" -o -name "*.ll" \) -type f -print0 | xargs -0 sed -i '' -E "s/%vreg([0-9]+)/%\1/g" * grep -nr '%vreg' . and fix if needed * find . \( -name "*.mir" -o -name "*.cpp" -o -name "*.h" -o -name "*.ll" \) -type f -print0 | xargs -0 sed -i '' -E "s/ vreg([0-9]+)/ %\1/g" * grep -nr 'vreg[0-9]\+' . and fix if needed Differential Revision: https://reviews.llvm.org/D40420 llvm-svn: 319427
* [CodeGen] Rename functions PrintReg* to printReg*Francis Visoiu Mistrih2017-11-281-19/+19
| | | | | | | | | | | LLVM Coding Standards: Function names should be verb phrases (as they represent actions), and command-like function should be imperative. The name should be camel case, and start with a lower case letter (e.g. openFile() or isFoo()). Differential Revision: https://reviews.llvm.org/D40416 llvm-svn: 319168
* Fix a bunch more layering of CodeGen headers that are in TargetDavid Blaikie2017-11-171-2/+2
| | | | | | | | All these headers already depend on CodeGen headers so moving them into CodeGen fixes the layering (since CodeGen depends on Target, not the other way around). llvm-svn: 318490
* Target/TargetInstrInfo.h -> CodeGen/TargetInstrInfo.h to match layeringDavid Blaikie2017-11-081-1/+1
| | | | | | | | This header includes CodeGen headers, and is not, itself, included by any Target headers, so move it into CodeGen to match the layering of its implementation. llvm-svn: 317647
* Add logic to greedy reg alloc to avoid bad eviction chainsMarina Yatsina2017-10-221-9/+347
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This fixes bugzilla 26810 https://bugs.llvm.org/show_bug.cgi?id=26810 This is intended to prevent sequences like: movl %ebp, 8(%esp) # 4-byte Spill movl %ecx, %ebp movl %ebx, %ecx movl %edi, %ebx movl %edx, %edi cltd idivl %esi movl %edi, %edx movl %ebx, %edi movl %ecx, %ebx movl %ebp, %ecx movl 16(%esp), %ebp # 4 - byte Reload Such sequences are created in 2 scenarios: Scenario #1: vreg0 is evicted from physreg0 by vreg1 Evictee vreg0 is intended for region splitting with split candidate physreg0 (the reg vreg0 was evicted from) Region splitting creates a local interval because of interference with the evictor vreg1 (normally region spliiting creates 2 interval, the "by reg" and "by stack" intervals. Local interval created when interference occurs.) one of the split intervals ends up evicting vreg2 from physreg1 Evictee vreg2 is intended for region splitting with split candidate physreg1 one of the split intervals ends up evicting vreg3 from physreg2 etc.. until someone spills Scenario #2 vreg0 is evicted from physreg0 by vreg1 vreg2 is evicted from physreg2 by vreg3 etc Evictee vreg0 is intended for region splitting with split candidate physreg1 Region splitting creates a local interval because of interference with the evictor vreg1 one of the split intervals ends up evicting back original evictor vreg1 from physreg0 (the reg vreg0 was evicted from) Another evictee vreg2 is intended for region splitting with split candidate physreg1 one of the split intervals ends up evicting vreg3 from physreg2 etc.. until someone spills As compile time was a concern, I've added a flag to control weather we do cost calculations for local intervals we expect to be created (it's on by default for X86 target, off for the rest). Differential Revision: https://reviews.llvm.org/D35816 Change-Id: Id9411ff7bbb845463d289ba2ae97737a1ee7cc39 llvm-svn: 316295
* [NFC] Convert OptimizationRemarkEmitter old emit() calls to new closureVivek Pandya2017-10-111-11/+14
| | | | | | | | | | | | | | parameterized emit() calls Summary: This is not functional change to adopt new emit() API added in r313691. Reviewed By: anemet Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D38285 llvm-svn: 315476
* Rename OptimizationDiagnosticInfo.* to OptimizationRemarkEmitter.*Adam Nemet2017-10-091-1/+1
| | | | | | | Sync it up with the name of the class actually defined here. This has been bothering me for a while... llvm-svn: 315249
* [RegAllocGreedy]: Allow recoloring of done register if it's non-tiedMikael Holmen2017-09-281-2/+14
| | | | | | | | | | | | | | | | | | | | | Summary: If we have a non-allocated register, we allow us to try recoloring of an already allocated and "Done" register, even if they are of the same register class, if the non-allocated register has at least one tied def and the allocated one has none. It should be easier to recolor the non-tied register than the tied one, so it might be an improvement even if they use the same regclasses. Reviewers: qcolombet Reviewed By: qcolombet Subscribers: llvm-commits, MatzeB Differential Revision: https://reviews.llvm.org/D38309 llvm-svn: 314388
* [RegAllocGreedy] Fix spelling error, "inteference" -> "interference", NFCMikael Holmen2017-09-271-3/+3
| | | | llvm-svn: 314299
* Recommit "[RegAlloc] Make sure live-ranges reflect the state of the IR whenJonas Paulsson2017-09-151-1/+4
| | | | | | | | | | | | | removing them" This was temporarily reverted, but now that the fix has been commited (r313197) it should be put back in place. https://bugs.llvm.org/show_bug.cgi?id=34502 This reverts commit 9ef93d9dc4c51568e858cf8203cd2c5ce8dca796. llvm-svn: 313349
* Revert "[RegAlloc] Make sure live-ranges reflect the state of the IR when ↵Jonas Paulsson2017-09-071-4/+1
| | | | | | | | | | removing them" This temporarily reverts commit 463fa38 (r311401). See https://bugs.llvm.org/show_bug.cgi?id=34502 llvm-svn: 312708
* [RegAlloc] Make sure live-ranges reflect the state of the IR when removing themQuentin Colombet2017-08-211-1/+4
| | | | | | | | | | | When removing a live-range we used to not touch them making debug prints harder to read because the IR was not matching what the live-ranges information was saying. This only affects debug printing and allows to put stronger asserts in the code (see r308906 for instance). llvm-svn: 311401
* fix typos in comments and error messages; NFCHiroshi Inoue2017-07-101-1/+1
| | | | llvm-svn: 307533
* fix trivial typo, NFCHiroshi Inoue2017-06-291-1/+1
| | | | llvm-svn: 306716
* [CodeGen] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-06-061-37/+59
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 304839
* BitVector: add iterators for set bitsFrancis Visoiu Mistrih2017-05-171-7/+4
| | | | | | Differential revision: https://reviews.llvm.org/D32060 llvm-svn: 303227
* RegAllocGreedy: Follow-up to r296722Matthias Braun2017-03-031-1/+5
| | | | | | | | | We can now end up in situations where we initiate LiveIntervalUnion queries with different SubRanges against the same register unit, so the assert() no longer holds in all cases. Just recalculate now when we know the cache is out of date. llvm-svn: 296928
* LIU:::Query: Query LiveRange instead of LiveInterval; NFCMatthias Braun2017-03-011-1/+1
| | | | | | | | | - We only need the information from the base class, not the additional details in the LiveInterval class. - Spread more `const` - Some code cleanup llvm-svn: 296684
* New OptimizationRemarkEmitter pass for MIRAdam Nemet2017-01-251-0/+84
| | | | | | | | | | | | | | | | | This allows MIR passes to emit optimization remarks with the same level of functionality that is available to IR passes. It also hooks up the greedy register allocator to report spills. This allows for interesting use cases like increasing interleaving on a loop until spilling of registers is observed. I still need to experiment whether reporting every spill scales but this demonstrates for now that the functionality works from llc using -pass-remarks*=<pass>. Differential Revision: https://reviews.llvm.org/D29004 llvm-svn: 293110
* Timer: Track name and description.Matthias Braun2016-11-181-4/+8
| | | | | | | | | | | | | The previously used "names" are rather descriptions (they use multiple words and contain spaces), use short programming language identifier like strings for the "names" which should be used when exporting to machine parseable formats. Also removed a unused TimerGroup from Hexxagon. Differential Revision: https://reviews.llvm.org/D25583 llvm-svn: 287369
* [RegAllocGreedy] Record missed hint for late recoloring.Quentin Colombet2016-11-161-0/+3
| | | | | | | | | | | | | | | In https://reviews.llvm.org/D25347, Geoff noticed that we still have useless copy that we can eliminate after register allocation. At the time the allocation is chosen for those copies, they are not useless but, because of changes in the surrounding code, later on they might become useless. The Greedy allocator already has a mechanism to deal with such cases with a late recoloring. However, we missed to record the some of the missed hints. This commit fixes that. llvm-svn: 287070
* RegAllocGreedy: Properly initialize this pass, so that -run-pass will workTom Stellard2016-11-141-13/+18
| | | | | | | | | | Reviewers: qcolombet, MatzeB Subscribers: wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D26572 llvm-svn: 286895
* [RegAllocGreedy] Another fix about NewVRegs for last chance recoloring after ↵Wei Mi2016-11-081-8/+5
| | | | | | | | | | | | | | | | | | r281783. About when we should move a vreg from CurrentNewVRegs to NewVRegs, if the vreg in CurrentNewVRegs was added into RecoloringCandidate and was evicted, it shouldn't be added to NewVRegs because its physical register will be restored at the end of tryLastChanceRecoloring after the recoloring failed. If the vreg in CurrentNewVRegs was not in RecoloringCandidate, i.e. it was evicted in selectOrSplitImpl inside tryRecoloringCandidates, its physical register will not be restored even if the recoloring failed. In that case, we need to add the vreg to NewVRegs. Same as r281783, the problem was seen on out-of-tree target and we didn't have a test case that reproduce the problem with in-tree targets. llvm-svn: 286259
* [RAGreedy] Empty live-ranges always succeed in last chance recoloring.Quentin Colombet2016-10-131-1/+12
| | | | | | | | | | | Relax the constraint for empty live-ranges while doing last chance recoloring. Indeed, those live-ranges do not need an actual color to be fond for the recoloring to work. Empty live-range may happen as a result of splitting/spilling. Unfortunately no test case for in-tree targets. llvm-svn: 284152
* [RegAllocGreedy] Attempt to split unspillable live intervalsDylan McKay2016-10-111-6/+8
| | | | | | | | | | | | | | | | | | | | | | | Summary: Previously, when allocating unspillable live ranges, we would never attempt to split. We would always bail out and try last ditch graph recoloring. This patch changes this by attempting to split all live intervals before performing recoloring. This fixes LLVM bug PR14879. I can't add test cases for any backends other than AVR because none of them have small enough register classes to trigger the bug. Reviewers: qcolombet Subscribers: MatzeB Differential Revision: https://reviews.llvm.org/D25070 llvm-svn: 283838
* Turn cl::values() (for enum) from a vararg function to using C++ variadic ↵Mehdi Amini2016-10-081-2/+1
| | | | | | | | | | | | | | | template The core of the change is supposed to be NFC, however it also fixes what I believe was an undefined behavior when calling: va_start(ValueArgs, Desc); with Desc being a StringRef. Differential Revision: https://reviews.llvm.org/D25342 llvm-svn: 283671
* Use StringRef in Pass/PassManager APIs (NFC)Mehdi Amini2016-10-011-3/+1
| | | | llvm-svn: 283004
* Revert "[RegAllocGreedy] Attempt to split unspillable live intervals"Dylan McKay2016-09-301-8/+6
| | | | | | It was accidentally committed. llvm-svn: 282855
* [RegAllocGreedy] Attempt to split unspillable live intervalsDylan McKay2016-09-301-6/+8
| | | | | | | | | | | | | | | | | | | | | | | Summary: Previously, when allocating unspillable live ranges, we would never attempt to split. We would always bail out and try last ditch graph recoloring. This patch changes this by attempting to split all live intervals before performing recoloring. This fixes LLVM bug PR14879. I can't add test cases for any backends other than AVR because none of them have small enough register classes to trigger the bug. Reviewers: qcolombet Subscribers: MatzeB Differential Revision: https://reviews.llvm.org/D25070 llvm-svn: 282852
OpenPOWER on IntegriCloud