summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [CodeGen] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-05-241-17/+32
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 303820
* Fix subreg value numbers in handleMoveUpStanislav Mekhanoshin2017-03-111-1/+3
| | | | | | | | | | | The problem can occur in presence of subregs. If we are swapping two instructions defining different subregs of the same register we will get a new liveout from a block. We need to preserve value number for block's liveout for successor block's livein to match. Differential Revision: https://reviews.llvm.org/D30558 llvm-svn: 297534
* Cleanup dump() functions.Matthias Braun2017-01-281-1/+1
| | | | | | | | | | | | | | | | | | We had various variants of defining dump() functions in LLVM. Normalize them (this should just consistently implement the things discussed in http://lists.llvm.org/pipermail/cfe-dev/2014-January/034323.html For reference: - Public headers should just declare the dump() method but not use LLVM_DUMP_METHOD or #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) - The definition of a dump method should look like this: #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) LLVM_DUMP_METHOD void MyClass::dump() { // print stuff to dbgs()... } #endif llvm-svn: 293359
* LiveIntervalAnalysis: Calculate liveness even if a superreg is reserved.Matthias Braun2017-01-241-6/+13
| | | | | | | | | | | | | | | | | A register unit may be allocatable and non-reserved but some of the register(tuples) built with it are reserved. We still need to calculate liveness in this case. Note to out of tree targets: If you start seeing machine verifier errors with this commit, it probably means that you do not properly mark super registers of reserved register as reserved. See for example r292836 or r292870 for example on how to fix that. rdar://29996737 Differential Revision: https://reviews.llvm.org/D28881 llvm-svn: 292871
* LiveIntervalAnalysis: Cleanup; NFCMatthias Braun2017-01-191-81/+64
| | | | | | | | - Fix doxygen comments: Do not repeat name, remove duplicated doxygen comment (on declaration + implementation), etc. - Use more range based for llvm-svn: 292455
* Implement LaneBitmask::any(), use it to replace !none(), NFCIKrzysztof Parzyszek2016-12-161-3/+3
| | | | llvm-svn: 289974
* Extract LaneBitmask into a separate typeKrzysztof Parzyszek2016-12-151-11/+11
| | | | | | | | | | | | Specifically avoid implicit conversions from/to integral types to avoid potential errors when changing the underlying type. For example, a typical initialization of a "full" mask was "LaneMask = ~0u", which would result in a value of 0x00000000FFFFFFFF if the type was extended to uint64_t. Differential Revision: https://reviews.llvm.org/D27454 llvm-svn: 289820
* Modify df_iterator to support post-order actionsDavid Callahan2016-10-051-1/+1
| | | | | | | | | | | | Summary: This makes a change to the state used to maintain visited information for depth first iterator. We know assume a method "completed(...)" which is called after all children of a node have been visited. In all existing cases, this method does nothing so this patch has no functional changes. It will however allow a client to distinguish back from cross edges in a DFS tree. Reviewers: nadav, mehdi_amini, dberlin Subscribers: MatzeB, mzolotukhin, twoh, freik, llvm-commits Differential Revision: https://reviews.llvm.org/D25191 llvm-svn: 283391
* Do not consider subreg defs as reads when computing subrange livenessKrzysztof Parzyszek2016-09-021-5/+4
| | | | | | | | | | Subregister definitions are considered uses for the purpose of tracking liveness of the whole register. At the same time, when calculating live interval subranges, subregister defs should not be treated as uses. Differential Revision: https://reviews.llvm.org/D24190 llvm-svn: 280532
* Add an optional parameter with a list of undefs to extendToIndicesKrzysztof Parzyszek2016-09-011-2/+3
| | | | | | Reapply r280268, hopefully in a version that MSVC likes. llvm-svn: 280358
* Revert "Add an optional parameter with a list of undefs to extendToIndices"Reid Kleckner2016-08-311-3/+2
| | | | | | | | | | | | This reverts commit r280268, it causes all MSVC 2013 to ICE. This appears to have been fixed in a later MSVC 2013 update, because I cannot reproduce it locally. That said, all upstream LLVM bots are broken right now, so I am reverting. Also reverts dependent change r280275, "[Hexagon] Deal with undefs when extending live intervals". llvm-svn: 280301
* Add an optional parameter with a list of undefs to extendToIndicesKrzysztof Parzyszek2016-08-311-2/+3
| | | | llvm-svn: 280268
* MachineRegisterInfo/MIR: Initialize tracksSubRegLiveness early, do not ↵Matthias Braun2016-08-241-7/+0
| | | | | | | | | | | | | print/parser it tracksSubRegLiveness only depends on the Subtarget and a cl::opt, there is not need to change it or save/parse it in a .mir file. Make the field const and move the initialization LiveIntervalAnalysis to the MachineRegisterInfo constructor. Also cleanup some code and fix some instances which better use MachineRegisterInfo::subRegLivenessEnabled() instead of TargetSubtargetInfo::enableSubRegLiveness(). llvm-svn: 279676
* Create subranges for new intervals resulting from live interval splittingKrzysztof Parzyszek2016-08-241-10/+16
| | | | | | | | | | | | | | | | | | | The register allocator can split a live interval of a register into a set of smaller intervals. After the allocation of registers is complete, the rewriter will modify the IR to replace virtual registers with the corres- ponding physical registers. At this stage, if a register corresponding to a subregister of a virtual register is used, the rewriter will check if that subregister is undefined, and if so, it will add the <undef> flag to the machine operand. The function verifying liveness of the subregis- ter would assume that it is undefined, unless any of the subranges of the live interval proves otherwise. The problem is that the live intervals created during splitting do not have any subranges, even if the original parent interval did. This could result in the <undef> flag placed on a register that is actually defined. Differential Revision: http://reviews.llvm.org/D21189 llvm-svn: 279625
* LiveIntervalAnalysis: fix a crash in repairOldRegInRangeNicolai Haehnle2016-08-101-0/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: See the new test case for one that was (non-deterministically) crashing on trunk and deterministically hit the assertion that I added in D23302. Basically, the machine function contains a sequence DS_WRITE_B32 %vreg4, %vreg14:sub0, ... DS_WRITE_B32 %vreg4, %vreg14:sub0, ... %vreg14:sub1<def> = COPY %vreg14:sub0 and SILoadStoreOptimizer::mergeWrite2Pair merges the two DS_WRITE_B32 instructions into one before calling repairIntervalsInRange. Now repairIntervalsInRange wants to repair %vreg14, in particular, and ends up trying to repair %vreg14:sub1 as well, but that only becomes active _after_ the range that is to be repaired, hence the crash due to LR.find(...) == LR.begin() at the start of repairOldRegInRange. I believe that just skipping those subrange is fine, but again, not too familiar with that code. Reviewers: MatzeB, kparzysz, tstellarAMD Subscribers: llvm-commits, MatzeB Differential Revision: https://reviews.llvm.org/D23303 llvm-svn: 278268
* LiveIntervalAnalysis: Fix handleMoveDown() problemMatthias Braun2016-07-261-0/+2
| | | | | | | | | | | | If we move a last-use register read to a later position we may skip intermediate segments. This may require us to not only extend the segment before the NewIdx, but also extend the segment live-in to OldIdx. This switches LiveIntervalTest to use AMDGPU so we can test subregister liveness. llvm-svn: 276724
* Fix printing of debugging information in LiveIntervals::shrinkToUsesKrzysztof Parzyszek2016-07-121-1/+1
| | | | | | | Print VNI->def before calling VNI->markUnused(), since markUnused makes the def invalid. llvm-svn: 275196
* LiveIntervalAnalysis: findLastUseBefore() must ignore undef uses.Matthias Braun2016-06-111-1/+3
| | | | | | | | | | undef uses are no real uses of a register and must be ignored by findLastUseBefore() so that handleMove() does not produce invalid live intervals in some cases. This fixed http://llvm.org/PR28083 llvm-svn: 272446
* CodeGen: Refactor renameDisconnectedComponents() as a passMatthias Braun2016-05-311-16/+0
| | | | | | | | | | | | | | | | | | Refactor LiveIntervals::renameDisconnectedComponents() to be a pass. Also change the name to "RenameIndependentSubregs": - renameDisconnectedComponents() worked on a MachineFunction at a time so it is a natural candidate for a machine function pass. - The algorithm is testable with a .mir test now. - This also fixes a problem where the lazy renaming as part of the MachineScheduler introduced IMPLICIT_DEF instructions after the number of a nodes in a region were counted leading to a mismatch. Differential Revision: http://reviews.llvm.org/D20507 llvm-svn: 271345
* LiveIntervalAnalysis: Fix handleMove() re-using the wrong value numberMatthias Braun2016-05-241-7/+3
| | | | | | This fixes http://llvm.org/PR27856 llvm-svn: 270619
* [LiveIntervalAnalysis] Don't dereference an end iterator in ↵Hal Finkel2016-05-211-1/+1
| | | | | | | | | | | | | | | | repairIntervalsInRange This fixes a bug introduced in: r262115 - CodeGen: Take MachineInstr& in SlotIndexes and LiveIntervals, NFC The iterator End here might == MBB->end(), and so we can't unconditionally dereference it. This often goes unnoticed (I don't have a test case that always crashes, and ASAN does not catch it either) because the function call arguments are turned right back into iterators. MachineInstrBundleIterator's constructor, however, does have an assert which might randomly fire. llvm-svn: 270323
* LiveIntervalAnalysis: Rework constructMainRangeFromSubranges()Matthias Braun2016-05-201-0/+6
| | | | | | | | | | | | | | | | | | | | | We now use LiveRangeCalc::extendToUses() instead of a specially designed algorithm in constructMainRangeFromSubranges(): - The original motivation for constructMainRangeFromSubranges() were differences between the main liverange and subranges because of hidden dead definitions. This case however cannot happen anymore with the DetectDeadLaneMasks pass in place. - It simplifies the code. - This fixes a longstanding bug where we did not properly create new SSA values on merging control flow (the MachineVerifier missed most of these cases). - Move constructMainRangeFromSubranges() to LiveIntervalAnalysis and LiveRangeCalc to better match the implementation/available helper functions. This re-applies r269016. The fixes from r270290 and r270259 should avoid the machine verifier problems this time. llvm-svn: 270291
* LiveIntervalAnalysis: Fix missing defs in renameDisconnectedComponents().Matthias Braun2016-05-201-1/+1
| | | | | | | | | | | | | | Fix renameDisconnectedComponents() creating vreg uses that can be reached from function begin withouthaving a definition (or explicit live-in). Fix this by inserting IMPLICIT_DEF instruction before control-flow joins as necessary. Removes an assert from MachineScheduler because we may now get additional IMPLICIT_DEF when preparing the scheduling policy. This fixes the underlying problem of http://llvm.org/PR27705 llvm-svn: 270259
* Revert "LiveIntervalAnalysis: Rework constructMainRangeFromSubranges()"Tom Stellard2016-05-121-6/+0
| | | | | | | | This reverts commit r269016 and also the follow-up commit r269020. This patch caused PR27705. llvm-svn: 269344
* LiveIntervalAnalysis: Rework constructMainRangeFromSubranges()Matthias Braun2016-05-101-0/+6
| | | | | | | | | | | | | | | | | | We now use LiveRangeCalc::extendToUses() instead of a specially designed algorithm in constructMainRangeFromSubranges(): - The original motivation for constructMainRangeFromSubranges() were differences between the main liverange and subranges because of hidden dead definitions. This case however cannot happen anymore with the DetectDeadLaneMasks pass in place. - It simplifies the code. - This fixes a longstanding bug where we did not properly create new SSA values on merging control flow (the MachineVerifier missed most of these cases). - Move constructMainRangeFromSubranges() to LiveIntervalAnalysis and LiveRangeCalc to better match the implementation/available helper functions. llvm-svn: 269016
* LiveIntervalAnalysis: Fix handleMove() extending liverange for undef inputsMatthias Braun2016-05-061-3/+6
| | | | | | | Fix handleMove() incorrectly extending liveranges when an undef input of a vreg was moved past the (current) end of the liverange. llvm-svn: 268805
* LiveIntervalAnalysis: Remove LiveVariables requirementMatthias Braun2016-04-281-7/+1
| | | | | | | | | | | | This requirement was a huge hack to keep LiveVariables alive because it was optionally used by TwoAddressInstructionPass and PHIElimination. However we have AnalysisUsage::addUsedIfAvailable() which we can use in those passes. This re-applies r260806 with LiveVariables manually added to PowerPC to hopefully not break the stage 2 bots this time. llvm-svn: 267954
* LiveIntervalAnalysis: No need to deal with dead subregister defs anymore.Matthias Braun2016-04-281-20/+3
| | | | | | | | The DetectDeadLaneMask already ensures that we have no dead subregister definitions making the special handling in LiveIntervalAnalysis unnecessary. This reverts most of r248335. llvm-svn: 267937
* LiveIntervalAnalysis: Fix handleMove() using wrong value numbersMatthias Braun2016-04-281-2/+1
| | | | | | | | | | handleMove() was incorrectly swapping two value numbers. This was missed before because the problem only occured when moving subregister definitions and needed -verify-machineinstrs to be detected. I cannot add a testcase as long as I cannot reapply r260905/r260806. llvm-svn: 267840
* [NFC] Header cleanupMehdi Amini2016-04-181-2/+0
| | | | | | | | | | | | | | Removed some unused headers, replaced some headers with forward class declarations. Found using simple scripts like this one: clear && ack --cpp -l '#include "llvm/ADT/IndexedMap.h"' | xargs grep -L 'IndexedMap[<]' | xargs grep -n --color=auto 'IndexedMap' Patch by Eugene Kosov <claprix@yandex.ru> Differential Revision: http://reviews.llvm.org/D19219 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 266595
* CodeGen: Update LiveIntervalAnalysis API to use MachineInstr&, NFCDuncan P. N. Exon Smith2016-02-271-27/+28
| | | | | | These parameters aren't expected to be null, so take them by reference. llvm-svn: 262151
* WIP: CodeGen: Use MachineInstr& in MachineInstrBundle.h, NFCDuncan P. N. Exon Smith2016-02-271-2/+2
| | | | | | | | Update APIs in MachineInstrBundle.h to take and return MachineInstr& instead of MachineInstr* when the instruction cannot be null. Besides being a nice cleanup, this is tacking toward a fix for PR26753. llvm-svn: 262141
* CodeGen: Take MachineInstr& in SlotIndexes and LiveIntervals, NFCDuncan P. N. Exon Smith2016-02-271-23/+22
| | | | | | | | | | | | | | Take MachineInstr by reference instead of by pointer in SlotIndexes and the SlotIndex wrappers in LiveIntervals. The MachineInstrs here are never null, so this cleans up the API a bit. It also incidentally removes a few implicit conversions from MachineInstrBundleIterator to MachineInstr* (see PR26753). At a couple of call sites it was convenient to convert to a range-based for loop over MachineBasicBlock::instr_begin/instr_end, so I added MachineBasicBlock::instrs. llvm-svn: 262115
* [WinEH] Fix funclet return block clobber mask placementReid Kleckner2016-02-261-2/+6
| | | | | | | | | | | | | | | | | | MBB slot index intervals are half open, not closed. getMBBEndIndex() returns the slot index of the start of the next block in layout order. Placing a register mask there is incorrect if the successor of the funclet return is not laid out after the return. Clang generates IR for catch bodies before generating the following normal code, so we never noticed this issue until the D frontend authors filed a bug about it. Instead, we can put the clobber mask on the last instruction of the funclet return block. We still aren't using a register mask operand on the CATCHRET instruction because it would cause PEI to spill all CSRs, including XMM regs, in the prologue. Fixes PR26679. llvm-svn: 262035
* Revert "LiveIntervalAnalysis: Remove LiveVariables requirement" and ↵Matthias Braun2016-02-181-1/+7
| | | | | | | | | | | | | | | | | | | LiveIntervalTest The commit breaks stage2 compilation on PowerPC. Reverting for now while this is analyzed. I also have to revert the LiveIntervalTest for now as that depends on this commit. Revert "LiveIntervalAnalysis: Remove LiveVariables requirement" This reverts commit r260806. Revert "Remove an unnecessary std::move to fix -Wpessimizing-move warning." This reverts commit r260931. Revert "Fix typo in LiveIntervalTest" This reverts commit r260907. Revert "Add unittest for LiveIntervalAnalysis::handleMove()" This reverts commit r260905. llvm-svn: 261189
* LiveIntervalAnalysis: Support moving of subregister defs in handleMoveMatthias Braun2016-02-151-34/+153
| | | | | | | | | | | | | | | | | | | This is an updated version which fixes a bug that happened with uses tied to an earlyclobber operand which end at an unusual slotindex. If two definitions write to independent subregisters then they can be put in any order. LiveIntervalAnalysis::handleMove() did not support this previously because it looks like moving a definition of a vreg past another one. This is a modified version of a patch proposed (two years ago) by Vincent Lejeune! This version does not touch the read-undef flags and is extended for the case of moving a subregister def behind all uses - this can happen for subregister defs that are completely unused. Differential Revision: http://reviews.llvm.org/D9067 llvm-svn: 260906
* LiveIntervalAnalysis: Remove LiveVariables requirementMatthias Braun2016-02-131-7/+1
| | | | | | | | | This requirement was a huge hack to keep LiveVariables alive because it was optionally used by TwoAddressInstructionPass and PHIElimination. However we have AnalysisUsage::addUsedIfAvailable() which we can use in those passes. llvm-svn: 260806
* Revert "LiveIntervalAnalysis: Support moving of subregister defs in handleMove"Matthias Braun2016-02-111-152/+34
| | | | | | | | | | | | This is broke a bot: http://lab.llvm.org:8011/builders/clang-cmake-aarch64-quick/builds/4703/steps/test-suite/logs/test.log Reverting while I investigate. This reverts commit r260565. llvm-svn: 260586
* LiveIntervalAnalysis: Support moving of subregister defs in handleMoveMatthias Braun2016-02-111-34/+152
| | | | | | | | | | | | | | | | If two definitions write to independent subregisters then they can be put in any order. LiveIntervalAnalysis::handleMove() did not support this previously because it looks like moving a definition of a vreg past another one. This is a modified version of a patch proposed (two years ago) by Vincent Lejeune! This version does not touch the read-undef flags and is extended for the case of moving a subregister def behind all uses - this can happen for subregister defs that are completely unused. Differential Revision: http://reviews.llvm.org/D9067 llvm-svn: 260565
* LiveIntervalAnalysis: Improve some commentsMatthias Braun2016-01-261-4/+4
| | | | | | As recommended by Justin. llvm-svn: 258771
* LiveIntervalAnalysis: Cleanup handleMove{Down|Up}() functions, NFCMatthias Braun2016-01-261-131/+141
| | | | | | | | | | | | | | | | | | | | | | These two functions are hard to reason about. This commit makes the code more comprehensible: - Use four distinct variables (OldIdxIn, OldIdxOut, NewIdxIn, NewIdxOut) with a fixed value instead of a changing iterator I that points to different things during the function. - Remove the early explanation before the function in favor of more detailed comments inside the function. Should have more/clearer comments now stating which conditions are tested and which invariants hold at different points in the functions. The behaviour of the code was not changed. I hope that this will make it easier to review the changes in http://reviews.llvm.org/D9067 which I will adapt next. Differential Revision: http://reviews.llvm.org/D16379 llvm-svn: 258756
* LiveInterval: Add utility class to rename independent subregister usageMatthias Braun2016-01-201-0/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This renaming is necessary to avoid a subregister aware scheduler accidentally creating liveness "holes" which are rejected by the MachineVerifier. Explanation as found in this patch: Helper class that can divide MachineOperands of a virtual register into equivalence classes of connected components. MachineOperands belong to the same equivalence class when they are part of the same SubRange segment or adjacent segments (adjacent in control flow); Different subranges affected by the same MachineOperand belong to the same equivalence class. Example: vreg0:sub0 = ... vreg0:sub1 = ... vreg0:sub2 = ... ... xxx = op vreg0:sub1 vreg0:sub1 = ... store vreg0:sub0_sub1 The example contains 3 different equivalence classes: - One for the (dead) vreg0:sub2 definition - One containing the first vreg0:sub1 definition and its use, but not the second definition! - The remaining class contains all other operands involving vreg0. We provide a utility function here to rename disjunct classes to different virtual registers. Differential Revision: http://reviews.llvm.org/D16126 llvm-svn: 258257
* LiveInterval: A LiveRange is enough for ConnectedVNInfoEqClasses::Classify()Matthias Braun2016-01-081-1/+1
| | | | llvm-svn: 257129
* MachineInstr: addRegisterDefReadUndef() => setRegisterDefReadUndef()Matthias Braun2015-11-111-1/+1
| | | | | | This way we can not only add but also remove read undef flags. llvm-svn: 252678
* [WinEH] Mark funclet entries and exits as clobbering all registersReid Kleckner2015-11-061-0/+14
| | | | | | | | | | | | | | | | | Summary: In this implementation, LiveIntervalAnalysis invents a few register masks on basic block boundaries that preserve no registers. The nice thing about this is that it prevents the prologue inserter from thinking it needs to spill all XMM CSRs, because it doesn't see any explicit physreg defs in the MI. Reviewers: MatzeB, qcolombet, JosephTremoulet, majnemer Subscribers: MatzeB, llvm-commits Differential Revision: http://reviews.llvm.org/D14407 llvm-svn: 252318
* Range-for some LiveIntervals code under reviewReid Kleckner2015-11-061-9/+7
| | | | llvm-svn: 252267
* CodeGen: Remove more ilist iterator implicit conversions, NFCDuncan P. N. Exon Smith2015-10-091-2/+2
| | | | llvm-svn: 249879
* TargetRegisterInfo: Introduce PrintLaneMask.Matthias Braun2015-09-251-2/+1
| | | | | | | This makes it more convenient to print lane masks and lead to more uniform printing. llvm-svn: 248624
* TargetRegisterInfo: Add typedef unsigned LaneBitmask and use it where ↵Matthias Braun2015-09-251-10/+10
| | | | | | apropriate; NFC llvm-svn: 248623
* LiveIntervalAnalysis: Avoid multiple connected liveness componentsMatthias Braun2015-09-221-8/+26
| | | | | | | | | | | | | We may have subregister defs which are unused but not discovered and cleaned up prior to liveness analysis. This creates multiple connected components in the resulting live range which are forbidden in the MachineVerifier because they would unnecesarily constrain the register allocator. Rewrite those dead definitions to define a newly created virtual register. Differential Revision: http://reviews.llvm.org/D13035 llvm-svn: 248335
OpenPOWER on IntegriCloud