summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveInterval.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Revert "Remove the explicit SDNodeIterator::operator= in favor of the ↵David Blaikie2015-03-031-0/+1
| | | | | | | | | | | implicit default" Accidentally committed a few more of these cleanup changes than intended. Still breaking these out & tidying them up. This reverts commit r231135. llvm-svn: 231136
* Remove the explicit SDNodeIterator::operator= in favor of the implicit defaultDavid Blaikie2015-03-031-1/+0
| | | | | | | | | | There doesn't seem to be any need to assert that iterator assignment is between iterators over the same node - if you want to reuse an iterator variable to iterate another node, that's perfectly acceptable. Just don't mix comparisons between iterators into disjoint sequences, as usual. llvm-svn: 231135
* LiveRange: Replace a creative vector erase loop with std::remove_if.Benjamin Kramer2015-02-281-7/+3
| | | | | | | I didn't see this so far because it scans backwards, but that doesn't make it any less quadratic. NFC. llvm-svn: 230863
* LiveRangeCalc: Rename some parameters from kill to use, NFC.Matthias Braun2015-02-181-4/+4
| | | | | | Those parameters did not necessarily describe kill points but just uses. llvm-svn: 229601
* [LiveIntervalAnalysis] Speed up creation of live ranges for physical registersQuentin Colombet2015-02-061-142/+303
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | by using a segment set. The patch addresses a compile-time performance regression in the LiveIntervals analysis pass (see http://llvm.org/bugs/show_bug.cgi?id=18580). This regression is especially critical when compiling long functions. Our analysis had shown that the most of time is taken for generation of live intervals for physical registers. Insertions in the middle of the array of live ranges cause quadratic algorithmic complexity, which is apparently the main reason for the slow-down. Overview of changes: - The patch introduces an additional std::set<Segment>* member in LiveRange for storing segments in the phase of initial creation. The set is used if this member is not NULL, otherwise everything works the old way. - The set of operations on LiveRange used during initial creation (i.e. used by createDeadDefs and extendToUses) have been reimplemented to use the segment set if it is available. - After a live range is created the contents of the set are flushed to the segment vector, because the set is not as efficient as the vector for the later uses of the live range. After the flushing, the set is deleted and cannot be used again. - The set is only for live ranges computed in LiveIntervalAnalysis::computeLiveInRegUnits() and getRegUnit() but not in computeVirtRegs(), because I did not bring any performance benefits to computeVirtRegs() and for some examples even brought a slow down. Patch by Vaidas Gasiunas <vaidas.gasiunas@sap.com> Differential Revision: http://reviews.llvm.org/D6013 llvm-svn: 228421
* LiveInterval: Fix SubRange memory leak.Matthias Braun2015-02-061-1/+16
| | | | llvm-svn: 228405
* LiveInterval: Implement feedback by Quentin Colombet.Matthias Braun2015-01-071-25/+32
| | | | llvm-svn: 225413
* LiveInterval: Remove accidentally committed debug code.Matthias Braun2014-12-241-10/+0
| | | | llvm-svn: 224807
* LiveInterval: Introduce createMainRangeFromSubranges().Matthias Braun2014-12-241-0/+214
| | | | | | | | | | | | | | | | | | | | This function constructs the main liverange by merging all subranges if subregister liveness tracking is available. This should be slightly faster to compute instead of performing the liveness calculation again for the main range. More importantly it avoids cases where the main liverange would cover positions where no subrange was live. These cases happened for partial definitions where the actual defined part was dead and only the undefined parts used later. The register coalescing requires that every part covered by the main live range has at least one subrange live. I also expect this function to become usefull later for places where the subranges are modified in a way that it is hard to correctly fix the main liverange in the machine scheduler, we can simply reconstruct it from subranges then. llvm-svn: 224806
* LiveInterval: Use range based for loops for subregister ranges.Matthias Braun2014-12-111-9/+7
| | | | llvm-svn: 223991
* LiveInterval: Use more range based for loops for value numbers and segments.Matthias Braun2014-12-101-28/+26
| | | | llvm-svn: 223978
* LiveInterval: Add removeEmptySubRanges().Matthias Braun2014-12-101-0/+17
| | | | llvm-svn: 223887
* LiveInterval: Add support to track liveness of subregisters.Matthias Braun2014-12-101-0/+29
| | | | | | This code adds the required data structures. Algorithms to compute it follow. llvm-svn: 223877
* LiveInterval: Add a 'covers' operation to LiveRange.Matthias Braun2014-12-101-0/+21
| | | | llvm-svn: 223876
* Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie2014-11-191-1/+1
| | | | | | | | | | | | | pair<iterator, bool> This is to be consistent with StringSet and ultimately with the standard library's associative container insert function. This lead to updating SmallSet::insert to return pair<iterator, bool>, and then to update SmallPtrSet::insert to return pair<iterator, bool>, and then to update all the existing users of those functions... llvm-svn: 222334
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-141-6/+6
| | | | | | instead of comparing to nullptr. llvm-svn: 206142
* Phase 2 of the great MachineRegisterInfo cleanup. This time, we're changingOwen Anderson2014-03-131-2/+2
| | | | | | | | | | operator* on the by-operand iterators to return a MachineOperand& rather than a MachineInstr&. At this point they almost behave like normal iterators! Again, this requires making some existing loops more verbose, but should pave the way for the big range-based for-loop cleanups in the future. llvm-svn: 203865
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-11/+11
| | | | | | Remove the old functions. llvm-svn: 202636
* Print register in LiveInterval::print()Matthias Braun2013-10-101-0/+9
| | | | llvm-svn: 192398
OpenPOWER on IntegriCloud