aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/CodeGen/LiveInterval.cpp
AgeCommit message (Collapse)AuthorFilesLines
2011-03-19Replace a broken LiveInterval::MergeValueInAsValue() with something simpler.Jakob Stoklund Olesen1-46/+5
llvm-svn: 127960
2011-03-17Rewrite instructions as part of ConnectedVNInfoEqClasses::Distribute.Jakob Stoklund Olesen1-16/+33
llvm-svn: 127779
2011-03-12That's it, I am declaring this a failure of the C++03 STL.Jakob Stoklund Olesen1-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
2011-03-11Fix use of CompEnd predicate to be standards conformingJohn Wiegley1-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
2011-03-08Fix the build for MSVC 9 whose upper_bound() wants to compare elements in ↵Jakob Stoklund Olesen1-0/+3
the sorted array. Patch by Olaf Krzikalla! llvm-svn: 127264
2011-03-08Revert "Make a comparator's argument `const'. This fixes the build forOscar Fuentes1-1/+1
MSVC 9." The "fix" was meaningless. This reverts commit r127245. llvm-svn: 127260
2011-03-08Make a comparator's argument `const'. This fixes the build for MSVC 9.Oscar Fuentes1-1/+1
llvm-svn: 127245
2011-03-03Avoid comparing invalid slot indexes.Jakob Stoklund Olesen1-4/+6
llvm-svn: 126922
2011-03-02Move LiveIntervalMap::extendTo into LiveInterval itself.Jakob Stoklund Olesen1-0/+16
This method could probably be used by LiveIntervalAnalysis::shrinkToUses, and now it can use extendIntervalEndTo() which coalesces ranges. llvm-svn: 126803
2011-01-19Implement RAGreedy::splitAroundRegion and remove loop splitting.Jakob Stoklund Olesen1-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
2011-01-09Teach TargetRegisterInfo how to cram stack slot indexes in with the virtual andJakob Stoklund Olesen1-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
2011-01-09Replace TargetRegisterInfo::printReg with a PrintReg class that also works ↵Jakob Stoklund Olesen1-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
2010-12-21Use IntEqClasses to compute connected components of live intervals.Jakob Stoklund Olesen1-49/+9
llvm-svn: 122296
2010-12-19Fix PR8815 by checking for an explicit clobber def tied to a use operand inCameron Zwarich1-0/+8
ConnectedVNInfoEqClasses::Classify(). llvm-svn: 122202
2010-10-29Teach ConnectedVNInfoEqClasses::Classify to deal with unused values.Jakob Stoklund Olesen1-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
2010-10-29Fix broken equivalence class calculation. We could probably also useJakob Stoklund Olesen1-11/+8
EquvivalenceClasses.h except it looks like overkill when elements are continuous integers. llvm-svn: 117631
2010-10-09Silence compiler warning.Benjamin Kramer1-1/+1
llvm-svn: 116156
2010-10-08Classify value numbers into connected components in linear time.Jakob Stoklund Olesen1-23/+15
llvm-svn: 116105
2010-10-07After splitting, the remaining LiveInterval may be fragmented into multipleJakob Stoklund Olesen1-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
2010-10-05Tweak VNInfo printing.Jakob Stoklund Olesen1-0/+2
llvm-svn: 115650
2010-10-05Add assert for valid slot indexes.Jakob Stoklund Olesen1-0/+1
llvm-svn: 115649
2010-10-01When RemoveCopyByCommutingDef is creating additional identity copies, just useJakob Stoklund Olesen1-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
2010-09-25Removed VNInfo::isDefAccurate(). Def "accuracy" can be checked by testing ↵Lang Hames1-4/+1
whether LiveIntervals::getInstructionFromIndex(def) returns NULL. llvm-svn: 114791
2010-09-21Refix MSVC9 and upper_bound. It actually needs a fully symmetric comparator.Jakob Stoklund Olesen1-7/+5
llvm-svn: 114469
2010-09-21Don't pollute the global namespace.Jakob Stoklund Olesen1-0/+2
llvm-svn: 114459
2010-09-21MSVC9 does not support upper_bound with an asymmetric comparator.Jakob Stoklund Olesen1-6/+10
llvm-svn: 114455
2010-09-21Add LiveInterval::find and use it for most LiveRange searching operationsJakob Stoklund Olesen1-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
2010-09-21Remove dead method.Jakob Stoklund Olesen1-21/+0
llvm-svn: 114447
2010-09-08Remove dead code.Jakob Stoklund Olesen1-11/+0
llvm-svn: 113386
2010-09-04Remove dead code.Jakob Stoklund Olesen1-97/+0
Clobber ranges are no longer used when joining physical registers. Instead, all aliases are checked for interference. llvm-svn: 113084
2010-08-12Also recompute HasPHIKill flags in LiveInterval::RenumberValues.Jakob Stoklund Olesen1-1/+22
If a phi-def value were removed from the interval, the phi-kill flags are no longer valid. llvm-svn: 110949
2010-08-12Remove trailing whitespace.Jakob Stoklund Olesen1-22/+22
llvm-svn: 110944
2010-08-10Transpose the calculation of spill weights such that we are calculating oneJakob Stoklund Olesen1-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
2010-08-06Add LiveInterval::RenumberValues - Garbage collection for VNInfos.Jakob Stoklund Olesen1-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
2010-08-02Prefix `next' iterator operation with `llvm::'.Oscar Fuentes1-5/+5
Fixes potential ambiguity problems on VS 2010. Patch by nobled! llvm-svn: 110029
2010-07-26Factored out a bit of common code to mark VNInfos for deletion.Lang Hames1-40/+22
llvm-svn: 109388
2010-07-13Print VNInfo flags.Jakob Stoklund Olesen1-0/+4
llvm-svn: 108277
2010-07-13Add an assertion to make PR7542 fail consistently.Jakob Stoklund Olesen1-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
2010-07-13Fix LiveInterval::overlaps so it doesn't claim touching intervals overlap.Jakob Stoklund Olesen1-10/+2
Also, one binary search is enough. llvm-svn: 108261
2010-06-29Remove initialized but otherwise unused variables.Duncan Sands1-1/+0
llvm-svn: 107127
2010-06-25Don't track kills in VNInfo. Use interval ends instead.Jakob Stoklund Olesen1-27/+33
The VNInfo.kills vector was almost unused except for all the code keeping it updated. The few places using it were easily rewritten to check for interval ends instead. The two new methods LiveInterval::killedAt and killedInRange are replacements. This brings us down to 3 independent data structures tracking kills. llvm-svn: 106905
2010-06-24Make sure all eliminated kills are removed from VNInfo lists.Jakob Stoklund Olesen1-0/+2
This fixes PR7479 and PR7485. The test cases from those PRs are big, so not included. However, PR7485 comes from self hosting on FreeBSD, so we will surely hear about any regression. llvm-svn: 106811
2010-06-23Add a few VNInfo data structure checks.Jakob Stoklund Olesen1-2/+5
llvm-svn: 106627
2010-03-30Introduce SpecificBumpPtrAllocator, a wrapper for BumpPtrAllocator which allowsBenjamin Kramer1-3/+3
only a single type of object to be allocated. Use it to make VNInfo destruction typesafe. llvm-svn: 99919
2010-03-30Fix -Asserts warning.Daniel Dunbar1-4/+0
llvm-svn: 99895
2010-03-30Reapply r99881 with some fixes: only call destructor in releaseMemory!Torok Edwin1-5/+0
llvm-svn: 99883
2010-01-12Fix a comment typo.Bob Wilson1-1/+1
llvm-svn: 93261
2010-01-04Change errs() to dbgs().David Greene1-2/+3
llvm-svn: 92528
2009-12-09Added a new "splitting" spiller.Lang Hames1-1/+1
When a call is placed to spill an interval this spiller will first try to break the interval up into its component values. Single value intervals and intervals which have already been split (or are the result of previous splits) are spilled by the default spiller. Splitting intervals as described above may improve the performance of generated code in some circumstances. This work is experimental however, and it still miscompiles many benchmarks. It's not recommended for general use yet. llvm-svn: 90951
2009-11-03The Indexes Patch.Lang Hames1-58/+31
This introduces a new pass, SlotIndexes, which is responsible for numbering instructions for register allocation (and other clients). SlotIndexes numbering is designed to match the existing scheme, so this patch should not cause any changes in the generated code. For consistency, and to avoid naming confusion, LiveIndex has been renamed SlotIndex. The processImplicitDefs method of the LiveIntervals analysis has been moved into its own pass so that it can be run prior to SlotIndexes. This was necessary to match the existing numbering scheme. llvm-svn: 85979
generated by cgit v1.1 at 2025-11-02 05:41:53 +0000