summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveInterval.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Rename SlotIndexes to match how they are used.Jakob Stoklund Olesen2011-11-131-1/+1
| | | | | | | | | | | | | | | | | | | | The old naming scheme (load/use/def/store) can be traced back to an old linear scan article, but the names don't match how slots are actually used. The load and store slots are not needed after the deferred spill code insertion framework was deleted. The use and def slots don't make any sense because we are using half-open intervals as is customary in C code, but the names suggest closed intervals. In reality, these slots were used to distinguish early-clobber defs from normal defs. The new naming scheme also has 4 slots, but the names match how the slots are really used. This is a purely mechanical renaming, but some of the code makes a lot more sense now. llvm-svn: 144503
* Leave hasPHIKill flags alone in LiveInterval::RenumberValues.Jakob Stoklund Olesen2011-09-151-21/+0
| | | | | | | | | | | It is conservatively correct to keep the hasPHIKill flags, even after deleting PHI-defs. The calculation can be very expensive after taildup has created a quadratic number of indirectbr edges in the CFG, and the hasPHIKill flag isn't used for anything after RenumberValues(). llvm-svn: 139780
* Switch extendInBlock() to take a kill slot instead of the last use slot.Jakob Stoklund Olesen2011-09-131-7/+7
| | | | | | | Three out of four clients prefer this interface which is consistent with extendIntervalEndTo() and LiveRangeCalc::extend(). llvm-svn: 139604
* Replace a broken LiveInterval::MergeValueInAsValue() with something simpler.Jakob Stoklund Olesen2011-03-191-46/+5
| | | | llvm-svn: 127960
* Rewrite instructions as part of ConnectedVNInfoEqClasses::Distribute.Jakob Stoklund Olesen2011-03-171-16/+33
| | | | llvm-svn: 127779
* That's it, I am declaring this a failure of the C++03 STL.Jakob Stoklund Olesen2011-03-121-119/+15
| | | | | | | | | | | | | | There are too many compatibility problems with using mixed types in std::upper_bound, and I don't want to spend 110 lines of boilerplate setting up a call to a 10-line function. Binary search is not /that/ hard to implement correctly. I tried terminating the binary search with a linear search, but that actually made the algorithm slower against my expectation. Most live intervals have less than 4 segments. The early test against endIndex() does pay, and this version is 25% faster than plain std::upper_bound(). llvm-svn: 127522
* Fix use of CompEnd predicate to be standards conformingJohn Wiegley2011-03-111-9/+111
| | | | | | | | | | | | | The existing CompEnd predicate does not define a strict weak order as required by the C++03 standard; therefore, its use as a predicate to std::upper_bound is invalid. For a discussion of this issue, see http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270 This patch replaces the asymmetrical comparison with an iterator adaptor that achieves the same effect while being strictly standard-conforming by ensuring an apples-to-apples comparison. llvm-svn: 127462
* Fix the build for MSVC 9 whose upper_bound() wants to compare elements in ↵Jakob Stoklund Olesen2011-03-081-0/+3
| | | | | | | | the sorted array. Patch by Olaf Krzikalla! llvm-svn: 127264
* Revert "Make a comparator's argument `const'. This fixes the build forOscar Fuentes2011-03-081-1/+1
| | | | | | | | | | MSVC 9." The "fix" was meaningless. This reverts commit r127245. llvm-svn: 127260
* Make a comparator's argument `const'. This fixes the build for MSVC 9.Oscar Fuentes2011-03-081-1/+1
| | | | llvm-svn: 127245
* Avoid comparing invalid slot indexes.Jakob Stoklund Olesen2011-03-031-4/+6
| | | | llvm-svn: 126922
* Move LiveIntervalMap::extendTo into LiveInterval itself.Jakob Stoklund Olesen2011-03-021-0/+16
| | | | | | | This method could probably be used by LiveIntervalAnalysis::shrinkToUses, and now it can use extendIntervalEndTo() which coalesces ranges. llvm-svn: 126803
* Implement RAGreedy::splitAroundRegion and remove loop splitting.Jakob Stoklund Olesen2011-01-191-1/+3
| | | | | | | | | | | | | | Region splitting includes loop splitting as a subset, and it is more generic. The splitting heuristics for variables that are live in more than one block are now: 1. Try to create a region that covers multiple basic blocks. 2. Try to create a new live range for each block with multiple uses. 3. Spill. Steps 2 and 3 are similar to what the standard spiller is doing. llvm-svn: 123853
* Teach TargetRegisterInfo how to cram stack slot indexes in with the virtual andJakob Stoklund Olesen2011-01-091-6/+1
| | | | | | | | | | | | | physical register numbers. This makes the hack used in LiveInterval official, and lets LiveInterval be oblivious of stack slots. The isPhysicalRegister() and isVirtualRegister() predicates don't know about this, so when a variable may contain a stack slot, isStackSlot() should always be tested first. llvm-svn: 123128
* Replace TargetRegisterInfo::printReg with a PrintReg class that also works ↵Jakob Stoklund Olesen2011-01-091-3/+1
| | | | | | | | | | without a TRI instance. Print virtual registers numbered from 0 instead of the arbitrary FirstVirtualRegister. The first virtual register is printed as %vreg0. TRI::NoRegister is printed as %noreg. llvm-svn: 123107
* Use IntEqClasses to compute connected components of live intervals.Jakob Stoklund Olesen2010-12-211-49/+9
| | | | llvm-svn: 122296
* Fix PR8815 by checking for an explicit clobber def tied to a use operand inCameron Zwarich2010-12-191-0/+8
| | | | | | ConnectedVNInfoEqClasses::Classify(). llvm-svn: 122202
* Teach ConnectedVNInfoEqClasses::Classify to deal with unused values.Jakob Stoklund Olesen2010-10-291-1/+15
| | | | | | | | We don't want unused values forming their own equivalence classes, so we lump them all together in one class, and then merge them with the class of the last used value. llvm-svn: 117670
* Fix broken equivalence class calculation. We could probably also useJakob Stoklund Olesen2010-10-291-11/+8
| | | | | | | EquvivalenceClasses.h except it looks like overkill when elements are continuous integers. llvm-svn: 117631
* Silence compiler warning.Benjamin Kramer2010-10-091-1/+1
| | | | llvm-svn: 116156
* Classify value numbers into connected components in linear time.Jakob Stoklund Olesen2010-10-081-23/+15
| | | | llvm-svn: 116105
* After splitting, the remaining LiveInterval may be fragmented into multipleJakob Stoklund Olesen2010-10-071-0/+110
| | | | | | | | | | | | | connected components. These components should be allocated different virtual registers because there is no reason for them to be allocated together. Add the ConnectedVNInfoEqClasses class to calculate the connected components, and move values to new LiveIntervals. Use it from SplitKit::rewrite by creating new virtual registers for the components. llvm-svn: 116006
* Tweak VNInfo printing.Jakob Stoklund Olesen2010-10-051-0/+2
| | | | llvm-svn: 115650
* Add assert for valid slot indexes.Jakob Stoklund Olesen2010-10-051-0/+1
| | | | llvm-svn: 115649
* When RemoveCopyByCommutingDef is creating additional identity copies, just useJakob Stoklund Olesen2010-10-011-0/+3
| | | | | | | | | | | LiveInterval::MergeValueNumberInto instead of trying to extend LiveRanges and getting it wrong. This fixed PR8249 where a valno with a multi-segment live range was defined by an identity copy created by RemoveCopyByCommutingDef. Some of the live segments disappeared. llvm-svn: 115385
* Removed VNInfo::isDefAccurate(). Def "accuracy" can be checked by testing ↵Lang Hames2010-09-251-4/+1
| | | | | | whether LiveIntervals::getInstructionFromIndex(def) returns NULL. llvm-svn: 114791
* Refix MSVC9 and upper_bound. It actually needs a fully symmetric comparator.Jakob Stoklund Olesen2010-09-211-7/+5
| | | | llvm-svn: 114469
* Don't pollute the global namespace.Jakob Stoklund Olesen2010-09-211-0/+2
| | | | llvm-svn: 114459
* MSVC9 does not support upper_bound with an asymmetric comparator.Jakob Stoklund Olesen2010-09-211-6/+10
| | | | llvm-svn: 114455
* Add LiveInterval::find and use it for most LiveRange searching operationsJakob Stoklund Olesen2010-09-211-68/+8
| | | | | | | | | | | | instead of calling lower_bound or upper_bound directly. This cleans up the search logic a bit because {lower,upper}_bound compare LR->start by default, and it is usually simpler to search LR->end. Funnelling all searches through one function also makes it possible to replace the search algorithm with something faster than binary search. llvm-svn: 114448
* Remove dead method.Jakob Stoklund Olesen2010-09-211-21/+0
| | | | llvm-svn: 114447
* Remove dead code.Jakob Stoklund Olesen2010-09-081-11/+0
| | | | llvm-svn: 113386
* Remove dead code.Jakob Stoklund Olesen2010-09-041-97/+0
| | | | | | | Clobber ranges are no longer used when joining physical registers. Instead, all aliases are checked for interference. llvm-svn: 113084
* Also recompute HasPHIKill flags in LiveInterval::RenumberValues.Jakob Stoklund Olesen2010-08-121-1/+22
| | | | | | | If a phi-def value were removed from the interval, the phi-kill flags are no longer valid. llvm-svn: 110949
* Remove trailing whitespace.Jakob Stoklund Olesen2010-08-121-22/+22
| | | | llvm-svn: 110944
* Transpose the calculation of spill weights such that we are calculating oneJakob Stoklund Olesen2010-08-101-12/+0
| | | | | | | | | | | | | | register at a time. This turns out to be slightly faster than iterating over instructions, but more importantly, it allows us to compute spill weights for new registers created after the spill weight pass has run. Also compute the allocation hint at the same time as the spill weight. This allows us to use the spill weight as a cost metric for copies, and choose the most profitable hint if there is more than one possibility. The new hints provide a very small (< 0.1%) but universal code size improvement. llvm-svn: 110631
* Add LiveInterval::RenumberValues - Garbage collection for VNInfos.Jakob Stoklund Olesen2010-08-061-0/+15
| | | | | | | After heavy editing of a live interval, it is much easier to simply renumber the live values instead of trying to keep track of the unused ones. llvm-svn: 110463
* Prefix `next' iterator operation with `llvm::'.Oscar Fuentes2010-08-021-5/+5
| | | | | | | | Fixes potential ambiguity problems on VS 2010. Patch by nobled! llvm-svn: 110029
* Factored out a bit of common code to mark VNInfos for deletion.Lang Hames2010-07-261-40/+22
| | | | llvm-svn: 109388
* Print VNInfo flags.Jakob Stoklund Olesen2010-07-131-0/+4
| | | | llvm-svn: 108277
* Add an assertion to make PR7542 fail consistently.Jakob Stoklund Olesen2010-07-131-0/+1
| | | | | | | | | | LiveInterval::overlapsFrom dereferences end() if it is called on an empty interval. It would be reasonable to just return false - an empty interval doesn't overlap anything, but I want to know who is doing it first. llvm-svn: 108264
OpenPOWER on IntegriCloud