summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveInterval.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Pass LiveQueryResult by valueMatthias Braun2013-10-101-1/+1
| | | | | | | This makes the API a bit more natural to use and makes it easier to make LiveRanges implementation details private. llvm-svn: 192394
* Refactor LiveInterval: introduce new LiveRange classMatthias Braun2013-10-101-98/+92
| | | | | | | | | | LiveRange just manages a list of segments and a list of value numbers now as LiveInterval did previously, but without having details like spill weight or a fixed register number. LiveInterval is now a subclass of LiveRange and simply adds the spill weight and the register number. llvm-svn: 192393
* Rename LiveRange to LiveInterval::SegmentMatthias Braun2013-10-101-112/+110
| | | | | | | | The Segment struct contains a single interval; multiple instances of this struct are used to construct a live range, but the struct is not a live range by itself. llvm-svn: 192392
* avoid unnecessary direct access to LiveInterval::rangesMatthias Braun2013-09-061-24/+23
| | | | llvm-svn: 190170
* remove unused argument from LiveRanges::join()Matthias Braun2013-09-061-2/+1
| | | | llvm-svn: 190169
* Remove unnecessary parameter to RenumberValues.Jakob Stoklund Olesen2013-08-141-1/+1
| | | | | | Patch by Matthias Braun! llvm-svn: 188393
* Use SmallVectorImpl& instead of SmallVector to avoid repeating small vector ↵Craig Topper2013-07-111-1/+1
| | | | | | size. llvm-svn: 186098
* Fix PR16110: Handle DBG_VALUE in ConnectedVNInfoEqClasses::Distribute().Jakob Stoklund Olesen2013-05-231-2/+10
| | | | | | | | | | | | Now that the LiveDebugVariables pass is running *after* register coalescing, the ConnectedVNInfoEqClasses class needs to deal with DBG_VALUE instructions. This only comes up when rematerialization during coalescing causes the remaining live range of a virtual register to separate into two connected components. llvm-svn: 182592
* Don't allocate memory in LiveInterval::join().Jakob Stoklund Olesen2013-02-201-10/+7
| | | | | | | Rewrite value numbers directly in the 'Other' LiveInterval which is moribund anyway. This avoids allocating the OtherAssignments vector. llvm-svn: 175690
* Use LiveRangeUpdater instead of mergeIntervalRanges.Jakob Stoklund Olesen2013-02-201-140/+11
| | | | | | | Performance is the same, but LiveRangeUpdater has a more flexible interface. llvm-svn: 175645
* Add a LiveRangeUpdater class.Jakob Stoklund Olesen2013-02-201-0/+200
| | | | | | | | | | | | | | | | | | Adding new segments to large LiveIntervals can be expensive because the LiveRange objects after the insertion point may need to be moved left or right. This can cause quadratic behavior when adding a large number of segments to a live range. The LiveRangeUpdater class allows the LIveInterval to be in a temporary invalid state while segments are being added. It maintains an internal gap in the LiveInterval when it is shrinking, and it has a spill area for new segments when the LiveInterval is growing. The behavior is similar to the existing mergeIntervalRanges() function, except it allocates less memory for the spill area, and the algorithm is turned inside out so the loop is driven by the clients. llvm-svn: 175644
OpenPOWER on IntegriCloud