aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/StrongPHIElimination.cpp
AgeCommit message (Collapse)Author
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-08-22Reduce duplicated hash map lookups.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162362 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-03Silence unused variable warning in -asserts buildMatt Beaumont-Gay
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161256 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-02-19Remove dead code. Improve llvm_unreachable text. Simplify some control flow.Ahmed Charles
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150918 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-06Don't explicitly renumber slot indices.Jakob Stoklund Olesen
We have automatic local renumbering now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149920 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
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-10-13Use an existing method.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141855 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-12To find the exiting VN of a LiveInterval from a block, use the previous slotCameron Zwarich
rather than the previous index. If a block has a single instruction, the previous index may be in a different basic block. I have no clue how this used to work on all of test-suite, because now this failure is seen quite often when trying to compile code with -strong-phi-elim. This fixes PR10252. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141812 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-09Trim an unneeded header.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137184 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-15Fix a ton of comment typos found by codespell. Patch byChris Lattner
Luis Felipe Strano Moraes! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129558 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-14Add some statistics to StrongPHIElimination.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125477 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-09Eliminate some extra hash table lookups.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123115 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-09Add an informative comment.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123114 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-08Fix coding style.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123093 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-04Switch to path halving from path compression for a small speedup. This alsoCameron Zwarich
makes getLeader() nonrecursive. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122811 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-04Eliminate repeated allocation of a per-BB DenseMap for a 4.6% reduction of timeCameron Zwarich
spent in StrongPHIElimination on 403.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122803 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-30Use getVRegDef() instead of def_iterator. This leads to fewer defs being addedCameron Zwarich
with 2-address instructions, for about a 3.5% speedup of StrongPHIElimination on 403.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122635 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-29Instead of processing every instruction when splitting interferences, onlyCameron Zwarich
process those instructions that define phi sources. This is a 47% speedup of StrongPHIElimination compile time on 403.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122627 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-29Add text explaining an assertion.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122617 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-28Revert the optimization in r122596. It is correct for all current targets, butCameron Zwarich
it relies on assumptions that may not be true in the future. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122608 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-28Avoid iterating every operand of an instruction in StrongPHIElimination, sinceCameron Zwarich
we are only interested in the defs when discovering interferences. This is a 28% speedup running StrongPHIElimination on 403.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122596 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-27Change an assertion to assert what the code actually relies upon.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122586 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-27Land a first cut at StrongPHIElimination. There are only 5 new test failuresCameron Zwarich
when running without the verifier, and I have not yet checked them to see if the new results are still correct. There are more verifier failures, but they all seem to be additional occurrences of verifier failures that occur with the existing PHIElimination pass. There are a few obvious issues with the code: 1) It doesn't properly update the register equivalence classes during copy insertion, and instead recomputes them before merging live intervals and renaming registers. I wanted to keep this first patch simple for debugging purposes, but it shouldn't be very hard to do this. 2) It doesn't mix the renaming and live interval merging with the copy insertion process, which leads to a lot of virtual register churn. Virtual registers and live intervals are created, only to later be merged into others. The code should be smarter and only create a new virtual register if there is no existing register in the same congruence class. 3) In one place the code uses a DenseMap per basic block, which is unnecessary heap allocation. There should be an inline storage version of DenseMap. I did a quick compile-time test of running llc on 403.gcc with and without StrongPHIElimination. It is slightly slower with StrongPHIElimination, because the small decrease in the coalescer runtime can't beat the increase in phi elimination runtime. Perhaps fixing the above performance issues will narrow the gap. I also haven't yet run any tests of the quality of the generated code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122582 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-24Simplify a check for implicit defs and remove a FIXME.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122537 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-21Incremental progress towards a new implementation of StrongPHIElimination. MostCameron Zwarich
of the problems with my last attempt were in the updating of LiveIntervals rather than the coalescing itself. Therefore, I decided to get that right first by essentially reimplementing the existing PHIElimination using LiveIntervals. It works correctly, with only a few tests failing (which may not be legitimate failures) and no new verifier failures (at least as far as I can tell, I didn't count the number per file). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122321 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-05Some cleanup before I start committing some incremental progress onCameron Zwarich
StrongPHIElimination. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120961 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-03Delete the StrongPHIElimination pass, leaving only a shell.Jakob Stoklund Olesen
The StrongPHIElimination pass did not work, and nobody has worked on it for two years. A rewrite is underway, so I am leaving this shell pass instead of deleting it completely. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120830 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-19Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson
exposes an initializeMyPassFunction(), which must be called in the pass's constructor. This function uses static dependency declarations to recursively initialize the pass's dependencies. Clients that only create passes through the createFooPass() APIs will require no changes. Clients that want to use the CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h before parsing commandline arguments. I have tested this with all standard configurations of clang and llvm-gcc on Darwin. It is possible that there are problems with the static dependencies that will only be visible with non-standard options. If you encounter any crash in pass registration/creation, please send the testcase to me directly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116820 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-12Begin adding static dependence information to passes, which will allow us toOwen Anderson
perform initialization without static constructors AND without explicit initialization by the client. For the moment, passes are required to initialize both their (potential) dependencies and any passes they preserve. I hope to be able to relax the latter requirement in the future. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116334 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-07Now with fewer extraneous semicolons!Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@115996 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-23Now that PassInfo and Pass::ID have been separated, move the rest of the ↵Owen Anderson
passes over to the new registration API. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111815 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-06Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110460 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-06Revert r110396 to fix buildbots.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110410 91177308-0d34-0410-b5e6-96231b3b80d8
2010-08-05Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson
address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110396 91177308-0d34-0410-b5e6-96231b3b80d8
2010-07-10Replace copyRegToReg with COPY everywhere in lib/CodeGen except for FastISel.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108062 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-05-06Add a DebugLoc argument to TargetInstrInfo::copyRegToReg, so that itDan Gohman
doesn't have to guess. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103194 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-10Fix "the the" and similar typos.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95781 91177308-0d34-0410-b5e6-96231b3b80d8
2010-02-09move target-independent opcodes out of TargetInstrInfoChris Lattner
into TargetOpcodes.h. #include the new TargetOpcodes.h into MachineInstr. Add new inline accessors (like isPHI()) to MachineInstr, and start using them throughout the codebase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95687 91177308-0d34-0410-b5e6-96231b3b80d8
2010-01-05Change errs() to dbgs().David Greene
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92596 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-17Revert accidental commit.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91635 91177308-0d34-0410-b5e6-96231b3b80d8
2009-12-17Turn off critical edge splitting for landing pads. The introduction of aBill Wendling
non-landing pad basic block as the successor to a block that ends in an unconditional jump will cause block folding to remove the added block as a successor. Thus eventually removing it AND the landing pad entirely. Critical edge splitting is an optimization, so we can safely turn it off when dealing with landing pads. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91634 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-25Remove includes of Support/Compiler.h that are no longer needed after theNick Lewycky
VISIBILITY_HIDDEN removal. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85043 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-25Remove VISIBILITY_HIDDEN from class/struct found inside anonymous namespaces.Nick Lewycky
Chris claims we should never have visibility_hidden inside any .cpp file but that's still not true even after this commit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85042 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
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-04 07:33:36 +0000