summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/StrongPHIElimination.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Remove includes of Support/Compiler.h that are no longer needed after theNick Lewycky2009-10-251-1/+0
| | | | | | VISIBILITY_HIDDEN removal. llvm-svn: 85043
* Remove VISIBILITY_HIDDEN from class/struct found inside anonymous namespaces.Nick Lewycky2009-10-251-1/+1
| | | | | | | Chris claims we should never have visibility_hidden inside any .cpp file but that's still not true even after this commit. llvm-svn: 85042
* Oops. Renamed remaining MachineInstrIndex references.Lang Hames2009-10-031-1/+1
| | | | llvm-svn: 83255
* Renamed MachineInstrIndex to LiveIndex.Lang Hames2009-10-031-9/+9
| | | | llvm-svn: 83254
* Removed static qualifier from a few index related methods. These methods may ↵Lang Hames2009-09-091-9/+8
| | | | | | require a LiveIntervals instance in future. llvm-svn: 81374
* Replaces uses of unsigned for indexes in LiveInterval and VNInfo withLang Hames2009-09-041-16/+15
| | | | | | | | 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. llvm-svn: 81040
* remove a few DOUTs here and there.Chris Lattner2009-08-231-9/+11
| | | | llvm-svn: 79832
* Modified VNInfo. The "copy" member is now a union which holds the copy for a ↵Lang Hames2009-08-101-2/+2
| | | | | | register interval, or the defining register for a stack interval. Access is via getCopy/setCopy and getReg/setReg. llvm-svn: 78620
* Use setPreservesAll and setPreservesCFG in CodeGen passes.Dan Gohman2009-07-311-0/+1
| | | | llvm-svn: 77754
* Improved tracking of value number kills. VN kills are now representedLang Hames2009-07-091-2/+2
| | | | | | | | | | | | 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. llvm-svn: 75097
* VNInfo cleanup.Lang Hames2009-06-171-7/+4
| | | | llvm-svn: 73634
* Update to in-place spilling framework. Includes live interval scaling and ↵Lang Hames2009-06-021-1/+1
| | | | | | trivial rewriter. llvm-svn: 72729
* Fix a bug in live-in detection that caused lost-copy problems to show up.Owen Anderson2008-10-121-1/+1
| | | | llvm-svn: 57424
* Fix compilation error on MSVC.Argyrios Kyrtzidis2008-10-041-1/+1
| | | | llvm-svn: 57046
* Switch the MachineOperand accessors back to the short names likeDan Gohman2008-10-031-1/+1
| | | | | | isReg, etc., from isRegister, etc. llvm-svn: 57006
* Use a multimap rather than a map for holding the list of copies to insert, ↵Owen Anderson2008-10-021-12/+19
| | | | | | | | | | so we don't lose copies when two of them have the same source. I don't know what I was thinking when I wrote this originally. Note: There's probably a more efficient way to do this, but I need to think about it some more, and about what determinism guarantees need to be present. llvm-svn: 56964
* Mark merged-in VNInfo's as being PHIKilled.Owen Anderson2008-09-301-0/+5
| | | | llvm-svn: 56893
OpenPOWER on IntegriCloud