summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/GVN.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* random cleanups, no functionality change.Chris Lattner2008-12-091-14/+26
| | | | llvm-svn: 60779
* Make a few major changes to memdep and its clients:Chris Lattner2008-12-051-108/+63
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 1. Merge the 'None' result into 'Normal', making loads and stores return their dependencies on allocations as Normal. 2. Split the 'Normal' result into 'Clobber' and 'Def' to distinguish between the cases when memdep knows the value is produced from when we just know if may be changed. 3. Move some of the logic for determining whether readonly calls are CSEs into memdep instead of it being in GVN. This still leaves verification that the arguments are hte same to GVN to let it know about value equivalences in different contexts. 4. Change memdep's call/call dependency analysis to use getModRefInfo(CallSite,CallSite) instead of doing something very weak. This only really matters for things like DSA, but someday maybe we'll have some other decent context sensitive analyses :) 5. This reimplements the guts of memdep to handle the new results. 6. This simplifies GVN significantly: a) readonly call CSE is slightly simpler b) I eliminated the "getDependencyFrom" chaining for load elimination and load CSE doesn't have to worry about volatile (they are always clobbers) anymore. c) GVN no longer does any 'lastLoad' caching, leaving it to memdep. 7. The logic in DSE is simplified a bit and sped up. A potentially unsafe case was eliminated. llvm-svn: 60607
* Revert invalid r60393. It causes llvm-gcc bootstrap fails in release builds.Anton Korobeynikov2008-12-051-7/+2
| | | | | | See PR3160 for details llvm-svn: 60604
* Fix test/Transforms/GVN/pre-load.llChris Lattner2008-12-051-1/+1
| | | | llvm-svn: 60594
* Make IsValueFullyAvailableInBlock safe.Chris Lattner2008-12-051-14/+60
| | | | llvm-svn: 60588
* Implement PRE of loads in the GVN pass with a pretty cheap and Chris Lattner2008-12-021-54/+193
| | | | | | | | | | | | | | | | | | | | | | | straight-forward implementation. This does not require any extra alias analysis queries beyond what we already do for non-local loads. Some programs really really like load PRE. For example, SPASS triggers this ~1000 times, ~300 times in 255.vortex, and ~1500 times on 403.gcc. The biggest limitation to the implementation is that it does not split critical edges. This is a huge killer on many programs and should be addressed after the initial patch is enabled by default. The implementation of this should incidentally speed up rejection of non-local loads because it avoids creating the repl densemap in cases when it won't be used for fully redundant loads. This is currently disabled by default. Before I turn this on, I need to fix a couple of miscompilations in the testsuite, look at compile time performance numbers, and look at perf impact. This is pretty close to ready though. llvm-svn: 60408
* Fix an issue that Chris noticed, where local PRE was not properly instantiatingOwen Anderson2008-12-021-2/+7
| | | | | | | a new value numbering set after splitting a critical edge. This increases the number of instances of PRE on 403.gcc from ~60 to ~570. llvm-svn: 60393
* Rename some variables, only increment BI once at the start of the loop ↵Chris Lattner2008-12-011-38/+30
| | | | | | instead of throughout it. llvm-svn: 60339
* pull the predMap densemap out of the inner loop of performPRE, soChris Lattner2008-12-011-2/+4
| | | | | | | that it isn't reallocated all the time. This is a tiny speedup for GVN: 3.90->3.88s llvm-svn: 60338
* Make GVN be more intelligent about redundant load Chris Lattner2008-12-011-2/+19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | elimination: when finding dependent load/stores, realize that they are the same if aliasing claims must alias instead of relying on the pointers to be exactly equal. This makes load elimination more aggressive. For example, on 403.gcc, we had: < 68 gvn - Number of instructions PRE'd < 152718 gvn - Number of instructions deleted < 49699 gvn - Number of loads deleted < 6153 memdep - Number of dirty cached non-local responses < 169336 memdep - Number of fully cached non-local responses < 162428 memdep - Number of uncached non-local responses now we have: > 64 gvn - Number of instructions PRE'd > 153623 gvn - Number of instructions deleted > 49856 gvn - Number of loads deleted > 5022 memdep - Number of dirty cached non-local responses > 159030 memdep - Number of fully cached non-local responses > 162443 memdep - Number of uncached non-local responses That's an extra 157 loads deleted and extra 905 other instructions nuked. This slows down GVN very slightly, from 3.91 to 3.96s. llvm-svn: 60314
* Reimplement the non-local dependency data structure in terms of a sortedChris Lattner2008-12-011-22/+34
| | | | | | | | | | | | | | | | | | | vector instead of a densemap. This shrinks the memory usage of this thing substantially (the high water mark) as well as making operations like scanning it faster. This speeds up memdep slightly, gvn goes from 3.9376 to 3.9118s on 403.gcc This also splits out the statistics for the cached non-local case to differentiate between the dirty and clean cached case. Here's the stats for 403.gcc: 6153 memdep - Number of dirty cached non-local responses 169336 memdep - Number of fully cached non-local responses 162428 memdep - Number of uncached non-local responses yay for caching :) llvm-svn: 60313
* Cache analyses in ivars and add some useful DEBUG output.Chris Lattner2008-12-011-37/+30
| | | | | | This speeds up GVN from 4.0386s to 3.9376s. llvm-svn: 60310
* improve indentation, do cheap checks before expensive ones,Chris Lattner2008-11-301-52/+51
| | | | | | | remove some fixme's. This speeds up GVN very slightly on 403.gcc (4.06->4.03s) llvm-svn: 60309
* Fix a fixme by making memdep's handling of allocations more logical.Chris Lattner2008-11-301-15/+12
| | | | | | | | If we see that a load depends on the allocation of its memory with no intervening stores, we now return a 'None' depedency instead of "Normal". This tweaks GVN to do its optimization with the new result. llvm-svn: 60267
* Change MemDep::getNonLocalDependency to return its results asChris Lattner2008-11-291-5/+5
| | | | | | | a smallvector instead of a DenseMap. This speeds up GVN by 5% on 403.gcc. llvm-svn: 60255
* reimplement getNonLocalDependency with a simpler worklistChris Lattner2008-11-291-4/+21
| | | | | | | formulation that is faster and doesn't require nonLazyHelper. Much less code. llvm-svn: 60253
* Split getDependency into getDependency and getDependencyFrom, the Chris Lattner2008-11-291-1/+1
| | | | | | | former does caching, the later doesn't. This dramatically simplifies the logic in getDependency and getDependencyFrom. llvm-svn: 60234
* Introduce and use a new MemDepResult class to hold the results of a memdepChris Lattner2008-11-291-28/+28
| | | | | | | | | | | query. This makes it crystal clear what cases can escape from MemDep that the clients have to handle. This also gives the clients a nice simplified interface to it that is easy to poke at. This patch also makes DepResultTy and MemoryDependenceAnalysis::DepType private, yay. llvm-svn: 60231
* Reimplement the internal abstraction used by MemDep in termsChris Lattner2008-11-291-30/+33
| | | | | | | | | | | | | | | of a pointer/int pair instead of a manually bitmangled pointer. This forces clients to think a little more about checking the appropriate pieces and will be useful for internal implementation improvements later. I'm not particularly happy with this. After going through this I don't think that the clients of memdep should be exposed to the internal type at all. I'll fix this in a subsequent commit. This has no functionality change. llvm-svn: 60230
* fix memleak by cleaning the global sets on pass exitNuno Lopes2008-10-101-11/+17
| | | | llvm-svn: 57353
* Add <cstdio> include where needed by gcc-4.4.Duncan Sands2008-10-081-0/+1
| | | | | | Patch by Samuel Tardieu. llvm-svn: 57291
* Factorize code: remove variants of "strip offDuncan Sands2008-10-011-10/+1
| | | | | | | | | | | pointer bitcasts and GEP's", and centralize the logic in Value::getUnderlyingObject. The difference with stripPointerCasts is that stripPointerCasts only strips GEPs if all indices are zero, while getUnderlyingObject strips GEPs no matter what the indices are. llvm-svn: 56922
* Tidy up several unbeseeming casts from pointer to intptr_t.Dan Gohman2008-09-041-1/+1
| | | | llvm-svn: 55779
* Fix a bug that prevented PRE from applying in some cases.Owen Anderson2008-09-031-3/+5
| | | | llvm-svn: 55744
* Put a heuristic in place to prevent GVN from falling into bad cases with ↵Owen Anderson2008-08-261-0/+6
| | | | | | | | massively complicated CFGs. This speeds up a particular testcase from 12+ hours to 5 seconds with little perceptible loss of quality. llvm-svn: 55391
* consolidate DenseMapInfo implementations, and add one for std::pair.Chris Lattner2008-08-221-12/+0
| | | | | | Patch contributed by m-s. llvm-svn: 55167
* Supress a gcc-4.3 warning.Duncan Sands2008-07-181-1/+1
| | | | llvm-svn: 53771
* Make PRE actually handle critical edges (by splitting them). Confirmed that ↵Owen Anderson2008-07-181-3/+6
| | | | | | bootstrap passes with this change. llvm-svn: 53762
* Enable PRE. My last batch of changes fixed the miscompile.Owen Anderson2008-07-171-1/+1
| | | | llvm-svn: 53730
* Factor MergeBlockIntoPredecessor out into BasicBlockUtils.Owen Anderson2008-07-171-51/+4
| | | | llvm-svn: 53705
* There's no need to iterate block merging and PRE. In fact, iterating the latterOwen Anderson2008-07-161-14/+12
| | | | | | could cause problems for memdep when it breaks critical edges. llvm-svn: 53691
* Revert this, as it seems to still be broken.Owen Anderson2008-07-151-1/+1
| | | | llvm-svn: 53627
* Enable local PRE by default.Owen Anderson2008-07-151-1/+1
| | | | llvm-svn: 53616
* Have GVN do a pre-pass over the CFG that folds away unconditional branches ↵Owen Anderson2008-07-151-2/+63
| | | | | | where possible. This allows local PRE to be more aggressive. llvm-svn: 53615
* Don't call lookupNumber more than we have to.Owen Anderson2008-07-111-5/+8
| | | | llvm-svn: 53470
* Use information already present in the ValueTable to fast-fail when we know ↵Owen Anderson2008-07-031-2/+11
| | | | | | there won't be a value number match. This speeds up GVN on a case where there are very few redundancies by ~25%. llvm-svn: 53108
* Avoid a redundant call.Owen Anderson2008-07-021-4/+4
| | | | llvm-svn: 53040
* A better fix for PR2503 that doesn't pessimize GVN in the presence of ↵Owen Anderson2008-07-021-0/+5
| | | | | | unreachable blocks. llvm-svn: 53032
* Disable PRE. It's breaking bootstrapping.Evan Cheng2008-06-231-1/+1
| | | | llvm-svn: 52643
* Tighten the conditions under which we do PRE, remove some unneeded code, and ↵Owen Anderson2008-06-231-12/+10
| | | | | | | | correct our preserved analyses list, since we do now change the CFG by splitting critical edges during PRE. llvm-svn: 52631
* Enable PRE.Evan Cheng2008-06-211-1/+1
| | | | llvm-svn: 52574
* Really disable PRE.Owen Anderson2008-06-201-1/+1
| | | | llvm-svn: 52531
* Change around the data structures used to store availability sets, resulting ↵Owen Anderson2008-06-201-26/+64
| | | | | | in a GVN+PRE that is faster that GVN alone was before. llvm-svn: 52521
* Disable PRE for now. It seems to be breaking llvm-gcc bootstrapping.Evan Cheng2008-06-201-2/+2
| | | | llvm-svn: 52518
* Add a hidden -disable-pre flag for testing purposes. This should be removedOwen Anderson2008-06-191-2/+8
| | | | | | once benchmarking is completed. llvm-svn: 52506
* PRE requires that critical edges be split.Owen Anderson2008-06-191-0/+24
| | | | llvm-svn: 52505
* Be sure to remove values from the value numbering table after we delete them.Owen Anderson2008-06-191-0/+1
| | | | | | This fixes a failure on povray. llvm-svn: 52499
* Revert support for insertvalue and extractvalue instructions for the moment.Owen Anderson2008-06-191-63/+1
| | | | | | | GVN expects that all inputs which to an instruction fall somewhere in the value hierarchy, which isn't true for these. llvm-svn: 52496
* Add support for extractvalue and insertvalue instructions in GVN.Owen Anderson2008-06-181-1/+63
| | | | llvm-svn: 52472
* Add local PRE to GVN. This only operates in cases where it would not ↵Owen Anderson2008-06-181-30/+168
| | | | | | | | increase code size, namely when the instantiated expression would only need to be created in one predecessor. llvm-svn: 52471
OpenPOWER on IntegriCloud