aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/LiveIntervalAnalysis.cpp
AgeCommit message (Collapse)Author
2013-03-08Rewrite the physreg part of findLastUseBefore().Jakob Stoklund Olesen
To find the last use of a register unit, start from the bottom and scan upwards until a user is found. <rdar://problem/13353090> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176706 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-23Make some fixes for LiveInterval repair with debug info. Debug valueCameron Zwarich
MachineInstrs don't have a slot index. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175961 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-20Find anchoring end points for repairIntervalsInRange and repairIndexesInRangeCameron Zwarich
automatically. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175673 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-20Make repairIntervalsInRange() more robust. There are now no longer any liveness-Cameron Zwarich
related failures when running 'make check' without LiveVariables with the verifier enabled. Some of the remaining failures elsewhere may still be fallout from incorrect updating of LiveIntervals or the few missing cases left in the two-address pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175672 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-20Add support to the two-address pass for updating LiveIntervals in many of theCameron Zwarich
common transformations. This includes updating repairIntervalsInRange() to handle more cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175604 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-20Add SlotIndexes::repairIndexesInRange(), which repairs SlotIndexes after addingCameron Zwarich
and removing instructions. The implementation seems more complicated than it needs to be, but I couldn't find something simpler that dealt with all of the corner cases. Also add a call to repairIndexesInRange() from repairIntervalsInRange(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175601 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-17Remove use of reverse iterators in repairIntervalsInRange(). While they wereCameron Zwarich
arguably better than forward iterators for this use case, they are confusing and there are some implementation problems with reverse iterators and MI bundles. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175393 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-17Use ArrayRef instead of a reference to a SmallVectorImpl.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175385 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-17Add support for updating the LiveIntervals of registers used by 'exotic'Cameron Zwarich
terminators that actually have register uses when splitting critical edges. This commit also introduces a method repairIntervalsInRange() on LiveIntervals, which allows for repairing LiveIntervals in a small range after an arbitrary target hook modifies, inserts, and removes instructions. It's pretty limited right now, but I hope to extend it to support all of the things that are done by the convertToThreeAddress() target hooks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175382 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-09Remove the old liveness algorithm.Jakob Stoklund Olesen
This is part of the plan to delete LiveVariables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174783 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-08Turn on -new-live-intervals by default.Jakob Stoklund Olesen
This uses a liveness algorithm that does not depend on data from the LiveVariables analysis, it is the first step towards removing LiveVariables completely. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174774 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-02Move all of the header files which are involved in modelling the LLVM IRChandler Carruth
into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171366 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-03Use the new script to sort the includes of every file under lib.Chandler Carruth
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. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-01misched: Fix LiveInterval update to better handle DebugVal.Andrew Trick
Assertion failed: (itr != mi2iMap.end() && "Instruction not found in maps.") rdar://12777252. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169070 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-28Make the LiveRegMatrix analysis available to targets.Jakob Stoklund Olesen
No functional change, just moved header files. Targets can inject custom passes between register allocation and rewriting. This makes it possible to tweak the register allocation before rewriting, using the full global interference checking available from LiveRegMatrix. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168806 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-09Fix assertions in updateRegMaskSlots().Jakob Stoklund Olesen
The RegMaskSlots contains 'r' slots while NewIdx and OldIdx are 'B' slots. This broke the checks in the assertions. This fixes PR14302. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167625 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-16misched: Added handleMove support for updating all kill flags, not just for ↵Andrew Trick
allocatable regs. This is a medium term workaround until we have a more robust solution in the form of a register liveness utility for postRA passes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166001 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-15Remove LIS::isAllocatable() and isReserved() helpers.Jakob Stoklund Olesen
All callers can simply use the corresponding MRI functions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165985 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-13Allow for loops in LiveIntervals::pruneValue().Jakob Stoklund Olesen
It is possible that the live range of the value being pruned loops back into the kill MBB where the search started. When that happens, make sure that the beginning of KillMBB is also pruned. Instead of starting a DFS at KillMBB and skipping the root of the search, start a DFS at each KillMBB successor, and allow the search to loop back to KillMBB. This fixes PR14078. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165872 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-12Use a transposed algorithm for handleMove().Jakob Stoklund Olesen
Completely update one interval at a time instead of collecting live range fragments to be updated. This avoids building data structures, except for a single SmallPtrSet of updated intervals. Also share code between handleMove() and handleMoveIntoBundle(). Add support for moving dead defs across other live values in the interval. The MI scheduler can do that. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165824 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-02Handle reserved registers more accurately in handleMove().Jakob Stoklund Olesen
Reserved register live ranges look like a set of dead defs - any uses of reserved registers are ignored. Instead of skipping the updating of reserved register operands entirely, just ignore the use operands and treat the def operands normally. No test case, handleMove() is not commonly used yet. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165060 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-20Extend -new-coalescer SSA update to handle mapped values as well.Jakob Stoklund Olesen
The old-fashioned many-to-one value mapping doesn't always work when merging vector lanes. A value can map to multiple different values, and it can even be necessary to insert new PHIs. When a value number is defined by a copy from a value number that required SSa update, include the live range of the copied value number in the SSA update as well. It is not necessarily a copy of the original value number any longer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164329 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-17Merge into undefined lanes under -new-coalescer.Jakob Stoklund Olesen
Add LIS::pruneValue() and extendToIndices(). These two functions are used by the register coalescer when merging two live ranges requires more than a trivial value mapping as supported by LiveInterval::join(). The pruneValue() function can remove the part of a value number that is going to conflict in join(). Afterwards, extendToIndices can restore the live range, using any new dominating value numbers and updating the SSA form. Use this complex value mapping to support merging a register into a vector lane that has a conflicting value, but the clobbered lane is undef. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164074 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-12Make findLastUseBefore handle reg-unit liveness.Lang Hames
findLastUseBefore was previous considering virtreg liveness only, leading to incorrect live intervals for reg units when instrs with physreg operands were moved up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163685 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-11Release build: guard dump functions withManman Ren
"#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163339. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163653 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-10Remove redundant semicolons which are null statements.Dmitri Gribenko
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163547 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-06Release build: guard dump functions with "ifndef NDEBUG"Manman Ren
No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163339 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-06Handle overlapping regunit intervals in LiveIntervals::addKillFlags().Jakob Stoklund Olesen
We will soon allow virtual register live ranges to overlap regunit live ranges when the physreg is defined as a copy of the virtreg: %EAX = COPY %vreg5 FOO %vreg5 BAR %EAX<kill> There is no real interference since %vreg5 and %EAX have the same value where they overlap. This patch prevents addKillFlags from adding virtreg kill flags to FOO where the assigned physreg is overlapping the virtual register live range. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163335 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-03When updating live range endpoints, make sure to preserve the early clobber bit.Lang Hames
Fixs PR13719. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163107 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-22Tidy up a few more uses of MF.getFunction()->getName().David Blaikie
Based on CR feedback from r162301 and Craig Topper's refactoring in r162347 here are a few other places that could use the same API (& in one instance drop a Function.h dependency). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162367 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-03Add an experimental -early-live-intervals option.Jakob Stoklund Olesen
This option runs LiveIntervals before TwoAddressInstructionPass which will eventually learn to exploit and update the analysis. Eventually, LiveIntervals will run before PHIElimination, and we can get rid of LiveVariables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161270 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-08-03Make the hasPHIKills flag a computed property.Jakob Stoklund Olesen
The VNInfo::HAS_PHI_KILL is only half supported. We precompute it in LiveIntervalAnalysis, but it isn't properly updated by live range splitting and functions like shrinkToUses(). It is only used in one place: RegisterCoalescer::removeCopyByCommutingDef(). This patch changes that function to use a new LiveIntervals::hasPHIKill() function that computes the flag for a given value number. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161254 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-27Also compute register mask lists under -new-live-intervals.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160898 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-27Add a -new-live-intervals experimental option.Jakob Stoklund Olesen
This option replaces the existing live interval computation with one based on LiveRangeCalc.cpp. The new algorithm does not depend on LiveVariables, and it can be run at any time, before or after leaving SSA form. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160892 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-22Delete a boring statistic.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159030 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-22Store live intervals in an IndexedMap.Jakob Stoklund Olesen
It is both smaller and faster than DenseMap. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159029 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-22Simplify handleMove() a bit.Jakob Stoklund Olesen
There is no need to check for physreg live ranges. They don't exist any more. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159019 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-22Stop computing physreg live ranges.Jakob Stoklund Olesen
Everyone is using on-demand regunit ranges now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159018 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-22Remove LiveIntervals::trackingRegUnits().Jakob Stoklund Olesen
With regunit liveness permanently enabled, this function would always return true. Also remove now obsolete code for checking physreg interference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159006 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-20Remove the -live-regunits command line option.Jakob Stoklund Olesen
Register allocators depend on it being permanently enabled now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158873 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-20Fix some more LiveInterval enumerations.Jakob Stoklund Olesen
Deterministically enumerate the virtual registers instead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158872 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-20Enable register unit liveness by default.Jakob Stoklund Olesen
Soon we won't need to compute live intervals for physical registers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158865 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-20Only update regunit live ranges that have been precomputed.Jakob Stoklund Olesen
Regunit live ranges are computed on demand, so when mi-sched calls handleMove, some regunits may not have live ranges yet. That makes updating them easier: Just skip the non-existing ranges. They will be computed correctly from the rescheduled machine code when they are needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158831 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-20Delete dead code.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158827 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-19Add regunit liveness support to LiveIntervals::handleMove().Jakob Stoklund Olesen
When LiveIntervals is tracking fixed interference in regunits, make sure to update those intervals as well. Currently guarded by -live-regunits. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158766 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-1980 col.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158755 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-06Remove dead debug option -disable-rematerialization.Jakob Stoklund Olesen
Remat has been stable for years, and it isn't done by LiveIntervalAnalysis any longer. (See LiveRangeEdit). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158079 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-28 05:38:36 +0000