aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/GVN.cpp
AgeCommit message (Collapse)Author
2008-12-01pull the predMap densemap out of the inner loop of performPRE, soChris Lattner
that it isn't reallocated all the time. This is a tiny speedup for GVN: 3.90->3.88s git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60338 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-01Make GVN be more intelligent about redundant load Chris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60314 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-01Reimplement the non-local dependency data structure in terms of a sortedChris Lattner
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 :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60313 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-01Cache analyses in ivars and add some useful DEBUG output.Chris Lattner
This speeds up GVN from 4.0386s to 3.9376s. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60310 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-30improve indentation, do cheap checks before expensive ones,Chris Lattner
remove some fixme's. This speeds up GVN very slightly on 403.gcc (4.06->4.03s) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60309 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-30Fix a fixme by making memdep's handling of allocations more logical.Chris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60267 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-29Change MemDep::getNonLocalDependency to return its results asChris Lattner
a smallvector instead of a DenseMap. This speeds up GVN by 5% on 403.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60255 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-29reimplement getNonLocalDependency with a simpler worklistChris Lattner
formulation that is faster and doesn't require nonLazyHelper. Much less code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60253 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-29Split getDependency into getDependency and getDependencyFrom, the Chris Lattner
former does caching, the later doesn't. This dramatically simplifies the logic in getDependency and getDependencyFrom. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60234 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-29Introduce and use a new MemDepResult class to hold the results of a memdepChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60231 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-29Reimplement the internal abstraction used by MemDep in termsChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60230 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-10fix memleak by cleaning the global sets on pass exitNuno Lopes
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@57353 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-08Add <cstdio> include where needed by gcc-4.4.Duncan Sands
Patch by Samuel Tardieu. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@57291 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-01Factorize code: remove variants of "strip offDuncan Sands
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56922 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-04Tidy up several unbeseeming casts from pointer to intptr_t.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55779 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-03Fix a bug that prevented PRE from applying in some cases.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55744 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-26Put a heuristic in place to prevent GVN from falling into bad cases with ↵Owen Anderson
massively complicated CFGs. This speeds up a particular testcase from 12+ hours to 5 seconds with little perceptible loss of quality. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55391 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-22consolidate DenseMapInfo implementations, and add one for std::pair.Chris Lattner
Patch contributed by m-s. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55167 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-18Supress a gcc-4.3 warning.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53771 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-18Make PRE actually handle critical edges (by splitting them). Confirmed that ↵Owen Anderson
bootstrap passes with this change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53762 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-17Enable PRE. My last batch of changes fixed the miscompile.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53730 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-17Factor MergeBlockIntoPredecessor out into BasicBlockUtils.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53705 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-16There's no need to iterate block merging and PRE. In fact, iterating the latterOwen Anderson
could cause problems for memdep when it breaks critical edges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53691 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-15Revert this, as it seems to still be broken.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53627 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-15Enable local PRE by default.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53616 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-15Have GVN do a pre-pass over the CFG that folds away unconditional branches ↵Owen Anderson
where possible. This allows local PRE to be more aggressive. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53615 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-11Don't call lookupNumber more than we have to.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53470 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-03Use information already present in the ValueTable to fast-fail when we know ↵Owen Anderson
there won't be a value number match. This speeds up GVN on a case where there are very few redundancies by ~25%. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53108 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-02Avoid a redundant call.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53040 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-02A better fix for PR2503 that doesn't pessimize GVN in the presence of ↵Owen Anderson
unreachable blocks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53032 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-23Disable PRE. It's breaking bootstrapping.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52643 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-23Tighten the conditions under which we do PRE, remove some unneeded code, and ↵Owen Anderson
correct our preserved analyses list, since we do now change the CFG by splitting critical edges during PRE. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52631 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-21Enable PRE.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52574 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-20Really disable PRE.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52531 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-20Change around the data structures used to store availability sets, resulting ↵Owen Anderson
in a GVN+PRE that is faster that GVN alone was before. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52521 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-20Disable PRE for now. It seems to be breaking llvm-gcc bootstrapping.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52518 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-19Add a hidden -disable-pre flag for testing purposes. This should be removedOwen Anderson
once benchmarking is completed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52506 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-19PRE requires that critical edges be split.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52505 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-19Be sure to remove values from the value numbering table after we delete them.Owen Anderson
This fixes a failure on povray. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52499 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-19Revert support for insertvalue and extractvalue instructions for the moment.Owen Anderson
GVN expects that all inputs which to an instruction fall somewhere in the value hierarchy, which isn't true for these. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52496 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-18Add support for extractvalue and insertvalue instructions in GVN.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52472 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-18Add local PRE to GVN. This only operates in cases where it would not ↵Owen Anderson
increase code size, namely when the instantiated expression would only need to be created in one predecessor. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52471 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-17We don't want to find dependencies within the same block in this case. It ↵Owen Anderson
leads to incorrect results because we're detecting something at or after the call we're querying on. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52433 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-12Switch GVN to use ScopedHashTable.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52242 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-05Update comments and documentation to reflect that GCSE and ValueNumbering areMatthijs Kooijman
deprecated by the GVN and GVNPRE passes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51983 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-04Remove unneeded #include.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51955 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-18Teach GVN to not assert on vector comparisonsNate Begeman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51230 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-13Fix Analysis/BasicAA/pure-const-dce.ll. This turned out to be a correctnessOwen Anderson
bug as well as a missed optimization. We weren't properly checking for local dependencies before moving on to non-local ones when doing non-local read-only call CSE. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51082 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-13Make the non-local CSE safety checks slightly more thorough.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51035 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-13Add support for non-local CSE of read-only calls.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51024 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-17 00:05:12 +0000