summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveInterval.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Fully qualify llvm::next to avoid ambiguity when building as C++11.David Blaikie2013-02-201-1/+1
| | | | llvm-svn: 175608
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-4/+4
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Handle mixed normal and early-clobber defs on inline asm.Jakob Stoklund Olesen2012-11-191-2/+10
| | | | | | PR14376. llvm-svn: 168320
* Don't dereference begin() on an empty vector.Jakob Stoklund Olesen2012-09-271-1/+1
| | | | | | | | The fix is obvious and the only test case I have is horrible, so I am not including it. The problem shows up when self-hosting clang on i386 with -new-coalescer enabled. llvm-svn: 164793
* Delete dead code.Jakob Stoklund Olesen2012-09-121-36/+0
| | | | llvm-svn: 163735
* Release build: guard dump functions withManman Ren2012-09-111-2/+2
| | | | | | | | "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163339. llvm-svn: 163653
* Release build: guard dump functions with "ifndef NDEBUG"Manman Ren2012-09-061-0/+4
| | | | | | No functional change. llvm-svn: 163339
* Allow overlaps between virtreg and physreg live ranges.Jakob Stoklund Olesen2012-09-061-0/+43
| | | | | | | | | | | | | | | | | The RegisterCoalescer understands overlapping live ranges where one register is defined as a copy of the other. With this change, register allocators using LiveRegMatrix can do the same, at least for copies between physical and virtual registers. When a physreg is defined by a copy from a virtreg, allow those live ranges to overlap: %CL<def> = COPY %vreg11:sub_8bit; GR32_ABCD:%vreg11 %vreg13<def,tied1> = SAR32rCL %vreg13<tied0>, %CL<imp-use,kill> We can assign %vreg11 to %ECX, overlapping the live range of %CL. llvm-svn: 163336
* Completely eliminate VNInfo flags.Jakob Stoklund Olesen2012-08-031-4/+1
| | | | | | | | The 'unused' state of a value number can be represented as an invalid def SlotIndex. This also exposed code that shouldn't have been looking at unused value VNInfos. llvm-svn: 161258
* Eliminate the VNInfo::hasPHIKill() flag.Jakob Stoklund Olesen2012-08-031-3/+1
| | | | | | | | | | The only real user of the flag was removeCopyByCommutingDef(), and it has been switched to LiveIntervals::hasPHIKill(). All the code changed by this patch was only concerned with computing and propagating the flag. llvm-svn: 161255
* Preserve 2-addr constraints in ConnectedVNInfoEqClasses.Jakob Stoklund Olesen2012-07-251-7/+4
| | | | | | | | | | | | | | | | | | | | When a live range splits into multiple connected components, we would arbitrarily assign <undef> uses to component 0. This is wrong when the use is tied to a def that gets assigned to a different component: %vreg69<def> = ADD8ri %vreg68<undef>, 1 The use and def must get the same virtual register. Fix this by assigning <undef> uses to the same component as the value defined by the instruction, if any: %vreg69<def> = ADD8ri %vreg69<undef>, 1 This fixes PR13402. The PR has a test case which I am not including because it is unlikely to keep exposing this behavior in the future. llvm-svn: 160739
* Teach the LiveInterval::join function to use the fast merge algorithm,Chandler Carruth2012-07-101-14/+17
| | | | | | | | | | | generalizing its implementation sufficiently to support this value number scenario as well. This cuts out another significant performance hit in large functions (over 10k basic blocks, etc), especially those with "natural" CFG structures. llvm-svn: 160026
OpenPOWER on IntegriCloud