aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/LiveInterval.cpp
AgeCommit message (Collapse)Author
2010-10-29Teach ConnectedVNInfoEqClasses::Classify to deal with unused values.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117670 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-29Fix broken equivalence class calculation. We could probably also useJakob Stoklund Olesen
EquvivalenceClasses.h except it looks like overkill when elements are continuous integers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117631 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-09Silence compiler warning.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116156 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-08Classify value numbers into connected components in linear time.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116105 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-07After splitting, the remaining LiveInterval may be fragmented into multipleJakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116006 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-05Tweak VNInfo printing.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115650 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-05Add assert for valid slot indexes.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115649 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-01When RemoveCopyByCommutingDef is creating additional identity copies, just useJakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115385 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-25Removed VNInfo::isDefAccurate(). Def "accuracy" can be checked by testing ↵Lang Hames
whether LiveIntervals::getInstructionFromIndex(def) returns NULL. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114791 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-21Refix MSVC9 and upper_bound. It actually needs a fully symmetric comparator.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114469 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-21Don't pollute the global namespace.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114459 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-21MSVC9 does not support upper_bound with an asymmetric comparator.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114455 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-21Add LiveInterval::find and use it for most LiveRange searching operationsJakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114448 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-21Remove dead method.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114447 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-08Remove dead code.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113386 91177308-0d34-0410-b5e6-96231b3b80d8
2010-09-04Remove dead code.Jakob Stoklund Olesen
Clobber ranges are no longer used when joining physical registers. Instead, all aliases are checked for interference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113084 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-12Also recompute HasPHIKill flags in LiveInterval::RenumberValues.Jakob Stoklund Olesen
If a phi-def value were removed from the interval, the phi-kill flags are no longer valid. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110949 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-12Remove trailing whitespace.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110944 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-10Transpose the calculation of spill weights such that we are calculating oneJakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110631 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-06Add LiveInterval::RenumberValues - Garbage collection for VNInfos.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110463 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-02Prefix `next' iterator operation with `llvm::'.Oscar Fuentes
Fixes potential ambiguity problems on VS 2010. Patch by nobled! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110029 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-26Factored out a bit of common code to mark VNInfos for deletion.Lang Hames
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109388 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-13Print VNInfo flags.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108277 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-13Add an assertion to make PR7542 fail consistently.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108264 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-13Fix LiveInterval::overlaps so it doesn't claim touching intervals overlap.Jakob Stoklund Olesen
Also, one binary search is enough. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108261 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-29Remove initialized but otherwise unused variables.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@107127 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-25Don't track kills in VNInfo. Use interval ends instead.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106905 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-24Make sure all eliminated kills are removed from VNInfo lists.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106811 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-23Add a few VNInfo data structure checks.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106627 91177308-0d34-0410-b5e6-96231b3b80d8
2010-03-30Introduce SpecificBumpPtrAllocator, a wrapper for BumpPtrAllocator which allowsBenjamin Kramer
only a single type of object to be allocated. Use it to make VNInfo destruction typesafe. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@99919 91177308-0d34-0410-b5e6-96231b3b80d8
2010-03-30Fix -Asserts warning.Daniel Dunbar
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@99895 91177308-0d34-0410-b5e6-96231b3b80d8
2010-03-30Reapply r99881 with some fixes: only call destructor in releaseMemory!Torok Edwin
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@99883 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-12Fix a comment typo.Bob Wilson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@93261 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-04Change errs() to dbgs().David Greene
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92528 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-09Added a new "splitting" spiller.Lang Hames
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@90951 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-03The Indexes Patch.Lang Hames
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85979 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-03Oops. Renamed remaining MachineInstrIndex references.Lang Hames
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83255 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-03Renamed MachineInstrIndex to LiveIndex.Lang Hames
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83254 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-12Moved some more index operations over to LiveIntervals.Lang Hames
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81605 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-04Replaces uses of unsigned for indexes in LiveInterval and VNInfo withLang Hames
a new class, MachineInstrIndex, which hides arithmetic details from most clients. This is a step towards allowing the register allocator to update/insert code during allocation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@81040 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-23shoot a few more std::ostream print methods in the head.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@79814 91177308-0d34-0410-b5e6-96231b3b80d8
2009-08-10Modified VNInfo. The "copy" member is now a union which holds the copy for a ↵Lang Hames
register interval, or the defining register for a stack interval. Access is via getCopy/setCopy and getReg/setReg. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78620 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-24More move to raw_ostream.Daniel Dunbar
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76966 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-24Move more to raw_ostream, provide support for writing MachineBasicBlock,Daniel Dunbar
LiveInterval, etc to raw_ostream. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76965 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-22Reorder if-else branches as suggested by Bill.David Greene
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76808 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-22Make some changes suggested by Bill and Evan.David Greene
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76775 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-21Add some support for iterative coalescers to calculate a joined liveDavid Greene
range's weight properly. This is turned off right now in the sense that you'll get an assert if you get into a situation that can only be caused by an iterative coalescer. All other code paths operate exactly as before so there is no functional change with this patch. The asserts should be disabled if/when an iterative coalescer gets added to trunk. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76680 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-09Improved tracking of value number kills. VN kills are now representedLang Hames
as an (index,bool) pair. The bool flag records whether the kill is a PHI kill or not. This code will be used to enable splitting of live intervals containing PHI-kills. A slight change to live interval weights introduced an extra spill into lsr-code-insertion (outside the critical sections). The test condition has been updated to reflect this. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75097 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-24Fixed a bug in LiveInterval scaling (failure to scale VNI defs correctly), ↵Lang Hames
removed old TODO comments. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74054 91177308-0d34-0410-b5e6-96231b3b80d8
2009-06-17VNInfo cleanup.Lang Hames
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73634 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-01 15:50:20 +0000