aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/CodeGen/LiveInterval.h
AgeCommit message (Collapse)Author
2013-04-24MI Sched: eliminate local vreg copies.Andrew Trick
For now, we just reschedule instructions that use the copied vregs and let regalloc elliminate it. I would really like to eliminate the copies on-the-fly during scheduling, but we need a complete implementation of repairIntervalsInRange() first. The general strategy is for the register coalescer to eliminate as many global copies as possible and shrink live ranges to be extended-basic-block local. The coalescer should not have to worry about resolving local copies (e.g. it shouldn't attemp to reorder instructions). The scheduler is a much better place to deal with local interference. The coalescer side of this equation needs work. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@180193 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-20Use LiveRangeUpdater instead of mergeIntervalRanges.Jakob Stoklund Olesen
Performance is the same, but LiveRangeUpdater has a more flexible interface. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175645 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-20Add a LiveRangeUpdater class.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175644 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-20Add a default constructor for LiveRange.Jakob Stoklund Olesen
It is useful to be able to create temporary LiveRange object whose members are filled in later. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175639 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-20Modify LiveInterval::addRange() to match the comment about what it returns.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175602 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-03Sort the #include lines for the include/... tree with the script.Chandler Carruth
AKA: Recompile *ALL* the source code! This one went much better. No manual edits here. I spot-checked for silliness and grep-checked for really broken edits and everything seemed good. It all still compiles. Yell if you see something that looks goofy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169133 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-17Mark unimplemented copy constructors and copy assignment operators as ↵Craig Topper
LLVM_DELETED_FUNCTION. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164016 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-16Fix problem when using LiveRangeQuery with block entries.Jakob Stoklund Olesen
A value that is live in to a basic block should be returned by valueIn() in LiveRangeQuery(getMBBStartIdx(MBB)), unless it is a PHI-def which should be returned by valueDefined() instead. Current code isn't using this functionality. Future code will. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163990 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-15Make LiveRangeQuery work for PHIDefs as well.Jakob Stoklund Olesen
If a PHI value happens to be live out from the layout predecessor of its def block, the def slot index will be in the middle of the segment: %vreg11 = [192r,240B:0)[352r,416B:2)[416B,496r:1) 0@192r 1@480B-phi %2@352r A LiveRangeQuery for 480 should return NULL from valueIn() since the PHI value is defined at the block entry, not live in to the block. No test case, future code depends on this functionality. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163971 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-12Delete dead code.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163735 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-06Allow overlaps between virtreg and physreg live ranges.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163336 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-03Completely eliminate VNInfo flags.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161258 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-03Eliminate the VNInfo::hasPHIKill() flag.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161255 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-27Eliminate the IS_PHI_DEF flag and VNInfo::setIsPHIDef().Jakob Stoklund Olesen
A value number is a PHI def if and only if it begins at a block boundary. This can be derived from the def slot, a separate flag is not necessary. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160893 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-10Teach the LiveInterval::join function to use the fast merge algorithm,Chandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160026 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-10Add an efficient merge operation to LiveInterval and use it to avoidChandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159982 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-10Teach LiveIntervals how to verify themselves and start using it in someChandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159981 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-05Simplify LiveInterval::print().Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158031 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-05Implement LiveRangeCalc::extendToUses() and createDeadDefs().Jakob Stoklund Olesen
These LiveRangeCalc methods are to be used when computing a live range from scratch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158027 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-20Add a LiveRangeQuery class.Jakob Stoklund Olesen
This class is meant to be the primary interface for examining a live range in the vicinity on a given instruction. It avoids all the messy dealings with iterators and early clobbers. This is a more abstract interface to live ranges, hiding the implementation as a vector of segments. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157141 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-28Don't update spill weights when joining intervals.Jakob Stoklund Olesen
We don't compute spill weights until after coalescing anyway. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155766 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-28Spring cleaning - Delete dead code.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155765 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-04Drop the REDEF_BY_EC VNInfo flag.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149769 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-04Don't store COPY pointers in VNInfo.Jakob Stoklund Olesen
If a value is defined by a COPY, that instuction can easily and cheaply be found by getInstructionFromIndex(VNI->def). This reduces the size of VNInfo from 24 to 16 bytes, and improves llc compile time by 3%. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149763 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-19Added methods to get the live range immediately before a given slot. ↵Lang Hames
Intended to parallel the getVNInfoBefore method. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148453 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-05comment cleanupAndrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147585 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-13Rename SlotIndexes to match how they are used.Jakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144503 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-15Use getPrevSlot() instead of getPrevIndex().Jakob Stoklund Olesen
The getPrevIndex() function moves to the same slot in the previous instruction. For getVNInfoBefore(), we just need the previous slot in the same instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139793 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-15Stop verifying hasPHIKill() flags.Jakob Stoklund Olesen
There is only one legitimate use remaining, in addIntervalsForSpills(). All other calls to hasPHIKill() are only used to update PHIKill flags. The addIntervalsForSpills() function is part of the old spilling framework, only used by linearscan. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139783 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-15Leave hasPHIKill flags alone in LiveInterval::RenumberValues.Jakob Stoklund Olesen
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(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139780 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-15[regcoalescing] bug fix for RegistersDefinedFromSameValue.Andrew Trick
An improper SlotIndex->VNInfo lookup was leading to unsafe copy removal. Fixes PR10920 401.bzip2 miscompile with no IV rewrite. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139765 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-13Switch extendInBlock() to take a kill slot instead of the last use slot.Jakob Stoklund Olesen
Three out of four clients prefer this interface which is consistent with extendIntervalEndTo() and LiveRangeCalc::extend(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139604 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-16Teach LiveInterval::isZeroLength about null SlotIndexes.Jakob Stoklund Olesen
When instructions are deleted, they leave tombstone SlotIndex entries. The isZeroLength method should ignore these null indexes. This causes RABasic to sometimes spill a callee-saved register in the abi-isel.ll test, so don't run that test with -regalloc=basic. Prioritizing register allocation according to spill weight can cause more registers to be used. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131436 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-30Avoid using stale entries form the sibling value map.Jakob Stoklund Olesen
This could happen when trying to use a value that had been eliminated after dead code elimination and folding loads. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130597 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-17Rewrite instructions as part of ConnectedVNInfoEqClasses::Distribute.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127779 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-02Move LiveIntervalMap::extendTo into LiveInterval itself.Jakob Stoklund Olesen
This method could probably be used by LiveIntervalAnalysis::shrinkToUses, and now it can use extendIntervalEndTo() which coalesces ranges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126803 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Reapply this.Eric Christopher
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124779 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Temporarily revert 124765 in an attempt to find the cycle breaking bootstrap.Eric Christopher
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124778 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Defer SplitKit value mapping until all defs are available.Jakob Stoklund Olesen
The greedy register allocator revealed some problems with the value mapping in SplitKit. We would sometimes start mapping values before all defs were known, and that could change a value from a simple 1-1 mapping to a multi-def mapping that requires ssa update. The new approach collects all defs and register assignments first without filling in any live intervals. Only when finish() is called, do we compute liveness and mapped values. At this time we know with certainty which values map to multiple values in a split range. This also has the advantage that we can compute live ranges based on the remaining uses after rematerializing at split points. The current implementation has many opportunities for compile time optimization. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124765 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-09Teach TargetRegisterInfo how to cram stack slot indexes in with the virtual andJakob Stoklund Olesen
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123128 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-21Use IntEqClasses to compute connected components of live intervals.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122296 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-17Avoid dereferencing end() in collectInterferingVRegs() when there is noJakob Stoklund Olesen
interference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122108 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-29Print out the connected components in the verifier after complaining about theirJakob Stoklund Olesen
multiplicity. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117630 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-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-25Avoid using VNInfo::getCopy as much as possible. I want to get rid of it.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114794 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-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-08Rearrange for better alignment and less paddingJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113445 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-28 10:16:58 +0000