summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveInterval.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [LiveInterval] Allow updating subranges with slightly out-dated IRQuentin Colombet2019-11-131-5/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | During register coalescing, we update the live-intervals on-the-fly. To do that we are in this strange mode where the live-intervals can be slightly out-of-sync (more precisely they are forward looking) compared to what the IR actually represents. This happens because the register coalescer only updates the IR when it is done with updating the live-intervals and it has to do it this way because updating the IR on-the-fly would actually clobber some information on how the live-ranges that are being updated look like. This is problematic for updates that rely on the IR to accurately represents the state of the live-ranges. Right now, we have only one of those: stripValuesNotDefiningMask. To reconcile this need of out-of-sync IR, this patch introduces a new argument to LiveInterval::refineSubRanges that allows the code doing the live range updates to reason about how the code should look like after the coalescer will have rewritten the registers. Essentially this captures how a subregister index with be offseted to match its position in a new register class. E.g., let say we want to merge: V1.sub1:<2 x s32> = COPY V2.sub3:<4 x s32> We do that by choosing a class where sub1:<2 x s32> and sub3:<4 x s32> overlap, i.e., by choosing a class where we can find "offset + 1 == 3". Put differently we align V2's sub3 with V1's sub1: V2: sub0 sub1 sub2 sub3 V1: <offset> sub0 sub1 This offset will look like a composed subregidx in the the class: V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32> => V1.(composed sub2 with sub1):<4 x s32> = COPY V2.sub3:<4 x s32> Now if we didn't rewrite the uses and def of V1, all the checks for V1 need to account for this offset to match what the live intervals intend to capture. Prior to this patch, we would fail to recognize the uses and def of V1 and would end up with machine verifier errors: No live segment at def. This could lead to miscompile as we would drop some live-ranges and thus, miss some interferences. For this problem to trigger, we need to reach stripValuesNotDefiningMask while having a mismatch between the IR and the live-ranges (i.e., we have to apply a subreg offset to the IR.) This requires the following three conditions: 1. An update of overlapping subreg lanes: e.g., dsub0 == <ssub0, ssub1> 2. An update with Tuple registers with a possibility to coalesce the subreg index: e.g., v1.dsub_1 == v2.dsub_3 3. Subreg liveness enabled. looking at the IR to decide what is alive and what is not, i.e., calling stripValuesNotDefiningMask. coalescer maintains for the live-ranges information. None of the targets that currently use subreg liveness (i.e., the targets that fulfill #3, Hexagon, AMDGPU, PowerPC, and SystemZ IIRC) expose #1 and and #2, so this patch also artificial enables subreg liveness for ARM, so that a nice test case can be attached.
* LiveIntervals: Remove assertionMatt Arsenault2019-09-121-1/+2
| | | | | | | | | | | | | This testcase is invalid, and caught by the verifier. For the verifier to catch it, the live interval computation needs to complete. Remove the assert so the verifier catches this, which is less confusing. In this testcase there is an undefined use of a subregister, and lanes which aren't used or defined. An equivalent testcase with the super-register shrunk to have no untouched lanes already hit this verifier error. llvm-svn: 371792
* Finish moving TargetRegisterInfo::isVirtualRegister() and friends to ↵Daniel Sanders2019-08-011-2/+2
| | | | | | llvm::Register as started by r367614. NFC llvm-svn: 367633
* Use llvm::upper_bound. NFCFangrui Song2019-04-121-3/+1
| | | | llvm-svn: 358277
* [LiveRange] Reset the VNIs when splitting subrangesQuentin Colombet2019-03-261-2/+51
| | | | | | | | | | | | | | | When splitting a subrange we end up with two different subranges covering two different, non overlapping, lanes. As part of this splitting the VNIs of the original live-range need to be dispatched to the subranges according to which lanes they are actually defining. Prior to this patch we were assuming that all values were defining all lanes. This was wrong as demonstrated by llvm.org/PR40835. Differential Revision: https://reviews.llvm.org/D59731 llvm-svn: 357032
* 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
* Update DBG_VALUE register operand during LiveInterval operationsYury Delendik2018-08-211-11/+11
| | | | | | | | | | | | | | | | | | | Summary: Handling of DBG_VALUE in ConnectedVNInfoEqClasses::Distribute() was fixed in PR16110. However DBG_VALUE register operands are not getting updated. This patch properly resolves the value location. Reviewers: MatzeB, vsk Reviewed By: MatzeB Subscribers: kparzysz, thegameg, vsk, MatzeB, dschuff, sbc100, jgravelle-google, aheejin, sunfish, llvm-commits Tags: #debug-info Differential Revision: https://reviews.llvm.org/D48994 llvm-svn: 340310
* IWYU for llvm-config.h in llvm, additions.Nico Weber2018-04-301-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | See r331124 for how I made a list of files missing the include. I then ran this Python script: for f in open('filelist.txt'): f = f.strip() fl = open(f).readlines() found = False for i in xrange(len(fl)): p = '#include "llvm/' if not fl[i].startswith(p): continue if fl[i][len(p):] > 'Config': fl.insert(i, '#include "llvm/Config/llvm-config.h"\n') found = True break if not found: print 'not found', f else: open(f, 'w').write(''.join(fl)) and then looked through everything with `svn diff | diffstat -l | xargs -n 1000 gvim -p` and tried to fix include ordering and whatnot. No intended behavior change. llvm-svn: 331184
* LiveInterval: Print weight in print() function.Matthias Braun2018-01-291-0/+1
| | | | llvm-svn: 323702
* 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] Rename functions PrintReg* to printReg*Francis Visoiu Mistrih2017-11-281-1/+1
| | | | | | | | | | | 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-1/+1
| | | | | | | | 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
* Reverting r315590; it did not include changes for llvm-tblgen, which is ↵Aaron Ballman2017-10-151-3/+3
| | | | | | | | causing link errors for several people. Error LNK2019 unresolved external symbol "public: void __cdecl `anonymous namespace'::MatchableInfo::dump(void)const " (?dump@MatchableInfo@?A0xf4f1c304@@QEBAXXZ) referenced in function "public: void __cdecl `anonymous namespace'::AsmMatcherEmitter::run(class llvm::raw_ostream &)" (?run@AsmMatcherEmitter@?A0xf4f1c304@@QEAAXAEAVraw_ostream@llvm@@@Z) llvm-tblgen D:\llvm\2017\utils\TableGen\AsmMatcherEmitter.obj 1 llvm-svn: 315854
* [dump] Remove NDEBUG from test to enable dump methods [NFC]Don Hinton2017-10-121-3/+3
| | | | | | | | | | | | | | | Summary: Add LLVM_FORCE_ENABLE_DUMP cmake option, and use it along with LLVM_ENABLE_ASSERTIONS to set LLVM_ENABLE_DUMP. Remove NDEBUG and only use LLVM_ENABLE_DUMP to enable dump methods. Move definition of LLVM_ENABLE_DUMP from config.h to llvm-config.h so it'll be picked up by public headers. Differential Revision: https://reviews.llvm.org/D38406 llvm-svn: 315590
* [CodeGen] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-08-241-16/+30
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 311703
* RegisterCoalescer: Simplify subrange splitting code; NFCMatthias Braun2017-03-031-0/+31
| | | | | | - Use slightly better variable names / compute in a more direct way. llvm-svn: 296905
* Cleanup dump() functions.Matthias Braun2017-01-281-0/+2
| | | | | | | | | | | | | | | | | | 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
* Implement LaneBitmask::any(), use it to replace !none(), NFCIKrzysztof Parzyszek2016-12-161-2/+2
| | | | llvm-svn: 289974
* Extract LaneBitmask into a separate typeKrzysztof Parzyszek2016-12-151-6/+7
| | | | | | | | | | | | 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
* Create subranges for new intervals resulting from live interval splittingKrzysztof Parzyszek2016-08-241-12/+82
| | | | | | | | | | | | | | | | | | | 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
* Use the range variant of remove_if instead of unpacking begin/endDavid Majnemer2016-08-121-1/+1
| | | | | | No functionality change is intended. llvm-svn: 278475
* Add print/dump routines to LiveInterval::SubRangeKrzysztof Parzyszek2016-07-121-10/+18
| | | | llvm-svn: 275194
* CodeGen: Refactor renameDisconnectedComponents() as a passMatthias Braun2016-05-311-266/+1
| | | | | | | | | | | | | | | | | | 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: Rework constructMainRangeFromSubranges()Matthias Braun2016-05-201-245/+12
| | | | | | | | | | | | | | | | | | | | | 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-7/+57
| | | | | | | | | | | | | | 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-20/+245
| | | | | | | | 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-245/+20
| | | | | | | | | | | | | | | | | | 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
* LiveInterval: Avoid unnecessary auto, add const; NFCMatthias Braun2016-05-101-3/+3
| | | | llvm-svn: 269015
* [NFC] Header cleanupMehdi Amini2016-04-181-1/+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
* LiveInterval: Fix Distribute() failing on liveranges with unused VNInfosMatthias Braun2016-03-241-8/+13
| | | | | | This fixes http://llvm.org/PR26991 llvm-svn: 264345
* CodeGen: Take MachineInstr& in SlotIndexes and LiveIntervals, NFCDuncan P. N. Exon Smith2016-02-271-6/+6
| | | | | | | | | | | | | | 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
* Remove uses of builtin comma operator.Richard Trieu2016-02-181-3/+5
| | | | | | Cleanup for upcoming Clang warning -Wcomma. No functionality change intended. llvm-svn: 261270
* [regalloc][WinEH] Do not mark intervals as not spillable if they contain a ↵Andrew Kaylor2016-02-081-0/+34
| | | | | | | | regmask Differential Revision: http://reviews.llvm.org/D16831 llvm-svn: 260164
* Annotate dump() methods with LLVM_DUMP_METHOD, addressing Richard Smith ↵Yaron Keren2016-01-291-5/+4
| | | | | | | | r259192 post commit comment. clang part in r259232, this is the LLVM part of the patch. llvm-svn: 259240
* LiveInterval: Add utility class to rename independent subregister usageMatthias Braun2016-01-201-0/+183
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-5/+5
| | | | llvm-svn: 257129
* 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-4/+4
| | | | | | apropriate; NFC llvm-svn: 248623
* Fix typoMatt Arsenault2015-09-241-1/+1
| | | | llvm-svn: 248549
* LiveInterval: Distribute subregister liveranges to new intervals in ↵Matthias Braun2015-09-221-29/+65
| | | | | | | | | | | | | | | | ConnectedVNInfoEqClasses::Distribute() This improves ConnectedVNInfoEqClasses::Distribute() to distribute the segments and value numbers in the subranges instead of conservatively clearing all subregister info. No separate test here, just clearing the subrange instead of properly distributing them would however break my upcoming fix regarding dead super register definitions. Differential Revision: http://reviews.llvm.org/D13075 llvm-svn: 248334
* LiveIntervalAnalysis: Factor common code into splitSeparateComponents; NFCMatthias Braun2015-09-221-9/+7
| | | | llvm-svn: 248241
* LiveInterval: Document and enforce rules about empty subranges.Matthias Braun2015-07-161-0/+2
| | | | | | | | | Empty subranges are not allowed in a LiveInterval and must be removed instead: Check this in the verifiers, put a reminder for this in the comment of the shrinkToUses variant for a single lane and make it automatic for the shrinkToUses variant for a LiveInterval. llvm-svn: 242431
* Oops, didn't mean to commit my debug fprintfsMatthias Braun2015-04-081-4/+1
| | | | llvm-svn: 234385
* LiveInterval: Fix computeFromMainRange() producing adjacent segments with ↵Matthias Braun2015-04-081-14/+45
| | | | | | | | | | | | | | | same valno If two livesegments from different subranges happened to have the same definition they could possibly end up as two adjacent segments in the main liverange with the same value number which is not allowed. Detect such cases and fix them in the 2nd pass of computeFromMainRange() if necessary. No testcase as there is only an out-of-tree target where I can sensibly come up with one. llvm-svn: 234382
* Move private classes into anonymous namespacesBenjamin Kramer2015-03-231-0/+2
| | | | | | NFC. llvm-svn: 232944
* Recommit r231168: unique_ptrify LiveRange::segmentSetDavid Blaikie2015-03-041-1/+0
| | | | | | | | | | | | | | | | | | | | | | | GCC 4.7's libstdc++ doesn't have std::map::emplace, but it does have std::unordered_map::emplace, and the use case here doesn't appear to need ordering. The container has been changed in a separate/precursor patch, and now this patch should hopefully build cleanly even with GCC 4.7. & then I realized the order of the container did matter, so extra handling of ordering was added in r231189. Original commit message: This makes LiveRange non-copyable, and LiveInterval is already non-movable (due to the explicit dtor), so now it's non-copyable and non-movable. Fix the one case where we were relying on the (deprecated in C++11) implicit copy ctor of LiveInterval (which happened to work because the ctor created an object with a null segmentSet, so double-deleting the null pointer was fine). llvm-svn: 231192
* Revert "unique_ptrify LiveRange::segmentSet"David Blaikie2015-03-041-0/+1
| | | | | | | | Apparently something does care about ordering of LiveIntervals... so revert all that stuff (r231175, r231176, r231177) & take some time to re-evaluate. llvm-svn: 231184
* Recommit r231168: unique_ptrify LiveRange::segmentSetDavid Blaikie2015-03-031-1/+0
| | | | | | | | | | | | | | | | | | | | GCC 4.7's libstdc++ doesn't have std::map::emplace, but it does have std::unordered_map::emplace, and the use case here doesn't appear to need ordering. The container has been changed in a separate/precursor patch, and now this patch should hopefully build cleanly even with GCC 4.7. Original commit message: This makes LiveRange non-copyable, and LiveInterval is already non-movable (due to the explicit dtor), so now it's non-copyable and non-movable. Fix the one case where we were relying on the (deprecated in C++11) implicit copy ctor of LiveInterval (which happened to work because the ctor created an object with a null segmentSet, so double-deleting the null pointer was fine). llvm-svn: 231176
* Revert "unique_ptrify LiveRange::segmentSet"David Blaikie2015-03-031-0/+1
| | | | | | | | GCC 4.7 *shakes fist* (doesn't have std::map::emplace... ) This reverts commit r231168. llvm-svn: 231173
* unique_ptrify LiveRange::segmentSetDavid Blaikie2015-03-031-1/+0
| | | | | | | | | | | | | This makes LiveRange non-copyable, and LiveInterval is already non-movable (due to the explicit dtor), so now it's non-copyable and non-movable. Fix the one case where we were relying on the (deprecated in C++11) implicit copy ctor of LiveInterval (which happened to work because the ctor created an object with a null segmentSet, so double-deleting the null pointer was fine). llvm-svn: 231168
OpenPOWER on IntegriCloud