summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveInterval.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Fix a bug where I didn't test for an empty range before inspecting theChandler Carruth2012-07-101-1/+2
| | | | | | | | | | | | | | | back of it. I don't have anything even remotely close to a test case for this. It only broke two build bots, both of them doing bootstrap builds, one of them a dragonegg bootstrap. It doesn't break for me when I bootstrap either. It doesn't reproduce every time or on many machines during the bootstrap. Many thanks to Duncan Sands who got the exact command (and stage of the bootstrap) which failed on the dragonegg bootstrap and managed to get it to trigger under valgrind with debug symbols. The fix was then found by inspection. llvm-svn: 159993
* Add an efficient merge operation to LiveInterval and use it to avoidChandler Carruth2012-07-101-32/+132
| | | | | | | | | | | quadratic behavior when performing pathological merges. Fixes the core element of PR12652. There is only one user of addRangeFrom left: join. I'm hoping to refactor further in a future patch and have join use this merge operation as well. llvm-svn: 159982
* Teach LiveIntervals how to verify themselves and start using it in someChandler Carruth2012-07-101-0/+33
| | | | | | | | | | of the trick merge routines. This adds a layer of testing that was necessary when implementing more efficient (and complex) merge logic for this datastructure. No functionality changed here. llvm-svn: 159981
* Optimize extendIntervalEndTo a tiny bit by saving one call through theChandler Carruth2012-07-051-7/+7
| | | | | | vector erase. No functionality changed. llvm-svn: 159746
* Simplify LiveInterval::print().Jakob Stoklund Olesen2012-06-051-7/+2
| | | | | | | | | | Don't print out the register number and spill weight, making the TRI argument unnecessary. This allows callers to interpret the reg field. It can currently be a virtual register, a physical register, a spill slot, or a register unit. llvm-svn: 158031
* Implement LiveRangeCalc::extendToUses() and createDeadDefs().Jakob Stoklund Olesen2012-06-051-0/+20
| | | | | | | These LiveRangeCalc methods are to be used when computing a live range from scratch. llvm-svn: 158027
* Run proper recursive dead code elimination during coalescing.Jakob Stoklund Olesen2012-05-191-1/+4
| | | | | | | | | | | | | | | Dead copies cause problems because they are trivial to coalesce, but removing them gived the live range a dangling end point. This patch enables full dead code elimination which trims live ranges to their uses so end points don't dangle. DCE may erase multiple instructions. Put the pointers in an ErasedInstrs set so we never risk visiting erased instructions in the work list. There isn't supposed to be any dead copies entering RegisterCoalescer, but they do slip by as evidenced by test/CodeGen/X86/coalescer-dce.ll. llvm-svn: 157101
* Don't update spill weights when joining intervals.Jakob Stoklund Olesen2012-04-281-25/+0
| | | | | | We don't compute spill weights until after coalescing anyway. llvm-svn: 155766
* Spring cleaning - Delete dead code.Jakob Stoklund Olesen2012-04-281-12/+0
| | | | llvm-svn: 155765
* Drop the REDEF_BY_EC VNInfo flag.Jakob Stoklund Olesen2012-02-041-2/+0
| | | | | | | | | | A live range that has an early clobber tied redef now looks like a normal tied redef, except the early clobber def uses the early clobber slot. This is enough to handle any strange interference problems. llvm-svn: 149769
* Break as soon as the MustMapCurValNos flag is set - no need to reiterate.Lang Hames2012-02-021-1/+3
| | | | llvm-svn: 149596
* PR11868. The previous loop in LiveIntervals::join would sometimes fall over ifLang Hames2012-02-021-11/+12
| | | | | | | more than two adjacent ranges needed to be merged. The new version should be able to handle an arbitrary sequence of adjancent ranges. llvm-svn: 149588
* Use getVNInfoBefore() when it makes sense.Jakob Stoklund Olesen2011-11-141-3/+2
| | | | llvm-svn: 144517
OpenPOWER on IntegriCloud