summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/StrongPHIElimination.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Remove the now unused strong phi elimination pass.Rafael Espindola2013-10-141-825/+0
| | | | llvm-svn: 192604
* Rename LiveRange to LiveInterval::SegmentMatthias Braun2013-10-101-21/+21
| | | | | | | | The Segment struct contains a single interval; multiple instances of this struct are used to construct a live range, but the struct is not a live range by itself. llvm-svn: 192392
* avoid unnecessary direct access to LiveInterval::rangesMatthias Braun2013-09-061-1/+1
| | | | llvm-svn: 190170
* Auto-compute live intervals on demand.Mark Lacey2013-08-141-2/+2
| | | | | | | | | | | | | | | When new virtual registers are created during splitting/spilling, defer creation of the live interval until we need to use the live interval. Along with the recent commits to notify LiveRangeEdit when new virtual registers are created, this makes it possible for functions like TargetInstrInfo::loadRegFromStackSlot() and TargetInstrInfo::storeRegToStackSlot() to create multiple virtual registers as part of the process of generating loads/stores for different register classes, and then have the live intervals for those new registers computed when they are needed. llvm-svn: 188437
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-4/+4
| | | | | | | | | | | | | | | | | 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. =] llvm-svn: 169131
* Reduce duplicated hash map lookups.Benjamin Kramer2012-08-221-5/+6
| | | | llvm-svn: 162362
* Silence unused variable warning in -asserts buildMatt Beaumont-Gay2012-08-031-0/+1
| | | | llvm-svn: 161256
* Eliminate the VNInfo::hasPHIKill() flag.Jakob Stoklund Olesen2012-08-031-1/+0
| | | | | | | | | | 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. llvm-svn: 161255
* Eliminate the IS_PHI_DEF flag and VNInfo::setIsPHIDef().Jakob Stoklund Olesen2012-07-271-2/+0
| | | | | | | | 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. llvm-svn: 160893
* Remove dead code. Improve llvm_unreachable text. Simplify some control flow.Ahmed Charles2012-02-191-1/+0
| | | | llvm-svn: 150918
* Don't explicitly renumber slot indices.Jakob Stoklund Olesen2012-02-061-2/+0
| | | | | | We have automatic local renumbering now. llvm-svn: 149920
* Don't store COPY pointers in VNInfo.Jakob Stoklund Olesen2012-02-041-1/+0
| | | | | | | | | | 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%. llvm-svn: 149763
* Rename SlotIndexes to match how they are used.Jakob Stoklund Olesen2011-11-131-7/+7
| | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 144503
* Use an existing method.Cameron Zwarich2011-10-131-1/+1
| | | | llvm-svn: 141855
* To find the exiting VN of a LiveInterval from a block, use the previous slotCameron Zwarich2011-10-121-1/+1
| | | | | | | | | | | 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. llvm-svn: 141812
* Trim an unneeded header.Jakob Stoklund Olesen2011-08-091-0/+1
| | | | llvm-svn: 137184
* Fix a ton of comment typos found by codespell. Patch byChris Lattner2011-04-151-1/+1
| | | | | | Luis Felipe Strano Moraes! llvm-svn: 129558
* Add some statistics to StrongPHIElimination.Cameron Zwarich2011-02-141-0/+8
| | | | llvm-svn: 125477
* Eliminate some extra hash table lookups.Cameron Zwarich2011-01-091-7/+10
| | | | llvm-svn: 123115
* Add an informative comment.Cameron Zwarich2011-01-091-1/+9
| | | | llvm-svn: 123114
* Fix coding style.Cameron Zwarich2011-01-081-64/+64
| | | | llvm-svn: 123093
* Switch to path halving from path compression for a small speedup. This alsoCameron Zwarich2011-01-041-6/+12
| | | | | | makes getLeader() nonrecursive. llvm-svn: 122811
* Eliminate repeated allocation of a per-BB DenseMap for a 4.6% reduction of timeCameron Zwarich2011-01-041-6/+5
| | | | | | spent in StrongPHIElimination on 403.gcc. llvm-svn: 122803
* Use getVRegDef() instead of def_iterator. This leads to fewer defs being addedCameron Zwarich2010-12-301-4/+3
| | | | | | | with 2-address instructions, for about a 3.5% speedup of StrongPHIElimination on 403.gcc. llvm-svn: 122635
* Instead of processing every instruction when splitting interferences, onlyCameron Zwarich2010-12-291-27/+61
| | | | | | | process those instructions that define phi sources. This is a 47% speedup of StrongPHIElimination compile time on 403.gcc. llvm-svn: 122627
* Add text explaining an assertion.Cameron Zwarich2010-12-291-1/+3
| | | | llvm-svn: 122617
* Revert the optimization in r122596. It is correct for all current targets, butCameron Zwarich2010-12-281-1/+8
| | | | | | it relies on assumptions that may not be true in the future. llvm-svn: 122608
* Avoid iterating every operand of an instruction in StrongPHIElimination, sinceCameron Zwarich2010-12-281-4/+3
| | | | | | | | we are only interested in the defs when discovering interferences. This is a 28% speedup running StrongPHIElimination on 403.gcc. llvm-svn: 122596
* Change an assertion to assert what the code actually relies upon.Cameron Zwarich2010-12-271-1/+1
| | | | llvm-svn: 122586
* Land a first cut at StrongPHIElimination. There are only 5 new test failuresCameron Zwarich2010-12-271-64/+590
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 122582
* Simplify a check for implicit defs and remove a FIXME.Cameron Zwarich2010-12-241-8/+6
| | | | llvm-svn: 122537
* Incremental progress towards a new implementation of StrongPHIElimination. MostCameron Zwarich2010-12-211-3/+186
| | | | | | | | | | | | 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). llvm-svn: 122321
* Some cleanup before I start committing some incremental progress onCameron Zwarich2010-12-051-21/+22
| | | | | | StrongPHIElimination. llvm-svn: 120961
* Delete the StrongPHIElimination pass, leaving only a shell.Jakob Stoklund Olesen2010-12-031-1018/+22
| | | | | | | | | | 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. llvm-svn: 120830
* Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson2010-10-191-1/+3
| | | | | | | | | | | | | | | | | 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. llvm-svn: 116820
* Begin adding static dependence information to passes, which will allow us toOwen Anderson2010-10-121-1/+6
| | | | | | | | | 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. llvm-svn: 116334
* Now with fewer extraneous semicolons!Owen Anderson2010-10-071-1/+1
| | | | llvm-svn: 115996
* Now that PassInfo and Pass::ID have been separated, move the rest of the ↵Owen Anderson2010-08-231-3/+2
| | | | | | passes over to the new registration API. llvm-svn: 111815
* Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson2010-08-061-2/+2
| | | | llvm-svn: 110460
* Revert r110396 to fix buildbots.Owen Anderson2010-08-061-2/+2
| | | | llvm-svn: 110410
* Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson2010-08-051-2/+2
| | | | | | | | address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. llvm-svn: 110396
* Replace copyRegToReg with COPY everywhere in lib/CodeGen except for FastISel.Jakob Stoklund Olesen2010-07-101-10/+9
| | | | llvm-svn: 108062
* Don't track kills in VNInfo. Use interval ends instead.Jakob Stoklund Olesen2010-06-251-3/+0
| | | | | | | | | | | | 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
* Add a DebugLoc argument to TargetInstrInfo::copyRegToReg, so that itDan Gohman2010-05-061-4/+4
| | | | | | doesn't have to guess. llvm-svn: 103194
* Fix "the the" and similar typos.Dan Gohman2010-02-101-1/+1
| | | | llvm-svn: 95781
* move target-independent opcodes out of TargetInstrInfoChris Lattner2010-02-091-7/+6
| | | | | | | | | 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. llvm-svn: 95687
* Change errs() to dbgs().David Greene2010-01-051-6/+6
| | | | llvm-svn: 92596
* Revert accidental commit.Bill Wendling2009-12-171-1/+1
| | | | llvm-svn: 91635
* Turn off critical edge splitting for landing pads. The introduction of aBill Wendling2009-12-171-1/+1
| | | | | | | | | | 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. llvm-svn: 91634
* The Indexes Patch.Lang Hames2009-11-031-27/+28
| | | | | | | | | | | | | | | | 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
OpenPOWER on IntegriCloud