summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* [RegAllocGreedy] Fix the list of NewVRegs for last chance recoloring.Quentin Colombet2016-09-161-2/+22
| | | | | | | | | | | | | | | | | When trying to recolor a register we may split live-ranges in the process. When we create new live-ranges we will have to process them, but when we move a register from Assign to Split, the allocation is not changed until the whole recoloring session is successful. Therefore, only push the live-ranges that changed from Assign to Split when the recoloring is successful. Same as the previous commit, I was not able to produce a test case that reproduce the problem with in-tree targets. Note: The bug has been here since the recoloring scheme has been added back in r200883 (Feb 2014). llvm-svn: 281783
* [RegAllocGreedy] Fix an assertion and condition when last chance recoloring ↵Quentin Colombet2016-09-161-2/+3
| | | | | | | | | | | | | | | | is used. When last chance recoloring is used, the list of NewVRegs may not be empty when calling selectOrSplitImpl. Indeed, another coloring may have taken place with splitting/spilling in the same recoloring session. Relax an assertion to take this into account and adapt a condition to act as if the NewVRegs were local to this selectOrSplitImpl instance. Unfortunately I am unable to produce a test case for this, I was only able to reproduce the conditions on an out-of-tree target. llvm-svn: 281782
* MachineFunction: Introduce NoPHIs propertyMatthias Braun2016-08-231-0/+5
| | | | | | | | | | | | | I want to compute the SSA property of .mir files automatically in upcoming patches. The problem with this is that some inputs will be reported as static single assignment with some passes claiming not to support SSA form. In reality though those passes do not support PHI instructions => Track the presence of PHI instructions separate from the SSA property. Differential Revision: https://reviews.llvm.org/D22719 llvm-svn: 279573
* Allow dead insts to be kept in DeadRemat only when they are rematerializable.Wei Mi2016-07-081-1/+3
| | | | | | | | | | | | | | | Because isReallyTriviallyReMaterializableGeneric puts many limits on rematerializable instructions, this fix can prevent instructions with tied virtual operands and instructions with virtual register uses from being kept in DeadRemat, so as to workaround the live interval consistency problem for the dummy instructions kept in DeadRemat. But we still need to fix the live interval consistency problem. This patch is just a short time relieve. PR28464 has been filed as a reminder. Differential Revision: http://reviews.llvm.org/D19486 llvm-svn: 274928
* Recommit r265547, and r265610,r265639,r265657 on top of it, plusWei Mi2016-04-131-14/+17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | two fixes with one about error verify-regalloc reported, and another about live range update of phi after rematerialization. r265547: Replace analyzeSiblingValues with new algorithm to fix its compile time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Patches on top of r265547: r265610 "Fix the compare-clang diff error introduced by r265547." r265639 "Fix the sanitizer bootstrap error in r265547." r265657 "InlineSpiller.cpp: Escap \@ in r265547. [-Wdocumentation]" Differential Revision: http://reviews.llvm.org/D15302 Differential Revision: http://reviews.llvm.org/D18934 Differential Revision: http://reviews.llvm.org/D18935 Differential Revision: http://reviews.llvm.org/D18936 llvm-svn: 266162
* Revert r265547 "Recommit r265309 after fixed an invalid memory reference bug ↵Hans Wennborg2016-04-081-17/+14
| | | | | | | | | | | | | happened" It caused PR27275: "ARM: Bad machine code: Using an undefined physical register" Also reverting the following commits that were landed on top: r265610 "Fix the compare-clang diff error introduced by r265547." r265639 "Fix the sanitizer bootstrap error in r265547." r265657 "InlineSpiller.cpp: Escap \@ in r265547. [-Wdocumentation]" llvm-svn: 265790
* Recommit r265309 after fixed an invalid memory reference bug happenedWei Mi2016-04-061-14/+17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | when DenseMap growed and moved memory. I verified it fixed the bootstrap problem on x86_64-linux-gnu but I cannot verify whether it fixes the bootstrap error on clang-ppc64be-linux. I will watch the build-bot result closely. Replace analyzeSiblingValues with new algorithm to fix its compile time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Differential Revision: http://reviews.llvm.org/D15302 llvm-svn: 265547
OpenPOWER on IntegriCloud