summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/GVN.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Complete the NumberTable --> LeaderTable rename.Owen Anderson2011-01-041-12/+12
| | | | llvm-svn: 122828
* Fix typo in a comment.Owen Anderson2011-01-041-1/+1
| | | | llvm-svn: 122827
* Prune #include's.Owen Anderson2011-01-041-10/+0
| | | | llvm-svn: 122826
* Clarify terminology, settling on referring to what was the "number table" as ↵Owen Anderson2011-01-041-32/+32
| | | | | | | | the "leader table", and rename methods to make it much more clear what they're doing. llvm-svn: 122823
* When removing a value from GVN's leaders list, don't drop the Next pointer ↵Owen Anderson2011-01-041-1/+2
| | | | | | in a corner case. llvm-svn: 122822
* Branch instructions don't produce values, so there's no need to generate a ↵Owen Anderson2011-01-041-5/+3
| | | | | | | | | value number for them. This avoids adding them to the various value numbering tables, resulting in a minor (~3%) speedup for GVN on 40.gcc. llvm-svn: 122819
* Remove commented out code.Owen Anderson2011-01-041-4/+0
| | | | llvm-svn: 122817
* Use the new addEscapingValue callback to update GlobalsModRef when GVN adds ↵Owen Anderson2011-01-031-2/+19
| | | | | | | | PHIs of GEPs. For the moment, have GlobalsModRef handle this conservatively by simply removing the value from its maps. llvm-svn: 122787
* Simplify GVN's value expression structure, allowing the elimination of a lot of Owen Anderson2011-01-031-260/+26
| | | | | | almost-but-not-quite-identical code. No intended functionality change. llvm-svn: 122760
* split dom frontier handling stuff out to its own DominanceFrontier header,Chris Lattner2011-01-021-0/+1
| | | | | | so that Dominators.h is *just* domtree. Also prune #includes a bit. llvm-svn: 122714
* Give GVN back the ability to perform simple conditional propagation on ↵Owen Anderson2010-12-211-52/+82
| | | | | | | | | conditional branch values. I still think that LVI should be handling this, but that capability is some ways off in the future, and this matters for some significant benchmarks. llvm-svn: 122378
* Remove dead code.Owen Anderson2010-12-211-9/+0
| | | | llvm-svn: 122371
* GVN's Expression is not POD-like (it contains a SmallVector). Simplify code ↵Benjamin Kramer2010-12-211-13/+3
| | | | | | while at it. llvm-svn: 122362
* tidy upChris Lattner2010-12-191-18/+17
| | | | llvm-svn: 122190
* Preserve TBAA tags when doing load PRE.Dan Gohman2010-12-151-3/+8
| | | | llvm-svn: 121921
* Move Value::getUnderlyingObject to be a standaloneDan Gohman2010-12-151-1/+1
| | | | | | | function so that it can live in Analysis instead of VMCore. llvm-svn: 121885
* move GetPointerBaseWithConstantOffset out of GVN into ValueTracking.hChris Lattner2010-11-301-58/+12
| | | | llvm-svn: 120476
* remove a fixed fixmeChris Lattner2010-11-301-2/+0
| | | | llvm-svn: 120474
* Document the new GVN number table structure.Owen Anderson2010-11-191-0/+12
| | | | llvm-svn: 119865
* Completely rework the datastructure GVN uses to represent the value number ↵Owen Anderson2010-11-181-72/+86
| | | | | | | | | | | | | | | | | | | | | | | to leader mapping. Previously, this was a tree of hashtables, and a query recursed into the table for the immediate dominator ad infinitum if the initial lookup failed. This led to really bad performance on tall, narrow CFGs. We can instead replace it with what is conceptually a multimap of value numbers to leaders (actually represented by a hashtable with a list of Value*'s as the value type), and then determine which leader from that set to use very cheaply thanks to the DFS numberings maintained by DominatorTree. Because there are typically few duplicates of a given value, this scan tends to be quite fast. Additionally, we use a custom linked list and BumpPtr allocation to avoid any unnecessary allocation in representing the value-side of the multimap. This change brings with it a 15% (!) improvement in the total running time of GVN on 403.gcc, which I think is pretty good considering that includes all the "real work" being done by MemDep as well. The one downside to this approach is that we can no longer use GVN to perform simple conditional progation, but that seems like an acceptable loss since we now have LVI and CorrelatedValuePropagation to pick up the slack. If you see conditional propagation that's not happening, please file bugs against LVI or CVP. llvm-svn: 119714
* Remove dead code in GVN: now that SimplifyInstruction is calledDuncan Sands2010-11-171-43/+2
| | | | | | | | | | systematically, CollapsePhi will always return null here. Note that CollapsePhi did an extra check, isSafeReplacement, which the SimplifyInstruction logic does not do. I think that check was bogus - I guess we will soon find out! (It was originally added in commit 41998 without a testcase). llvm-svn: 119456
* If dom tree information is available, make it possible to passDuncan Sands2010-11-141-1/+1
| | | | | | it to get better phi node simplification. llvm-svn: 119055
* Have GVN simplify instructions as it goes. For example, considerDuncan Sands2010-11-121-18/+20
| | | | | | | | | | | | | | | "%z = %x and %y". If GVN can prove that %y equals %x, then it turns this into "%z = %x and %x". With the new code, %z will be replaced with %x everywhere (and then deleted). Previously %z would be value numbered too, which is a waste of time. Also, while a clever value numbering algorithm would give %z the same value number as %x, our current one doesn't do so (at least I don't think it does). The new logic has an essentially equivalent effect to what you would get if %z was given the same value number as %x, i.e. it should make value numbering smarter. While there, get hold of target data once at the start rather than a gazillion times all over the place. llvm-svn: 118923
* Add helper functions for computing the Location of load, store,Dan Gohman2010-11-111-5/+2
| | | | | | and vaarg instructions. llvm-svn: 118845
* Enhance GVN to do more precise alias queries for non-local memoryDan Gohman2010-11-101-2/+4
| | | | | | | | | | | | | | | references. For example, this allows gvn to eliminate the load in this example: void foo(int n, int* p, int *q) { p[0] = 0; p[1] = 1; if (n) { *q = p[0]; } } llvm-svn: 118714
* Use getValueOperand() and getPointerOperand() on load and storeDan Gohman2010-11-101-12/+13
| | | | | | instructions instead of hard-coding operand numbers. llvm-svn: 118698
* 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/+5
| | | | | | | | | 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 the profitable bits of EnableFullLoadPRE have been enabled by ↵Owen Anderson2010-10-011-8/+6
| | | | | | | | | default, rip out the remainder. Anyone interested in more general PRE would be better served by implementing it separately, to get real anticipation calculation, etc. llvm-svn: 115337
* We do want to allow LoadPRE to perform LICM-like transformations: we already ↵Owen Anderson2010-09-301-13/+0
| | | | | | | | | consider PHI nodes to be negligible for code size (making this transform code size neutral), and it allows us to hoist values out of loops, which is always a good thing. llvm-svn: 115205
* LoadPRE was not properly checking that the load it was PRE'ing ↵Owen Anderson2010-09-251-1/+7
| | | | | | | | | | | | | | post-dominated the block it was being hoisted to. Splitting critical edges at the merge point only addressed part of the issue; it is also possible for non-post-domination to occur when the path from the load to the merge has branches in it. Unfortunately, full anticipation analysis is time-consuming, so for now approximate it. This is strictly more conservative than real anticipation, so we will miss some cases that real PRE would allow, but we also no longer insert loads into paths where they didn't exist before. :-) This is a very slight net positive on SPEC for me (0.5% on average). Most of the benchmarks are largely unaffected, but when it pays off it pays off decently: 181.mcf improves by 4.5% on my machine. llvm-svn: 114785
* zap dead code.Chris Lattner2010-09-041-3/+2
| | | | llvm-svn: 113073
* Reapply commit 112699, speculatively reverted by echristo, sinceDuncan Sands2010-09-021-1/+1
| | | | | | | | | I'm sure it is harmless. Original commit message: If PrototypeValue is erased in the middle of using the SSAUpdator then the SSAUpdator may access freed memory. Instead, simply pass in the type and name explicitly, which is all that was used anyway. llvm-svn: 112810
* Speculatively revert 112699 and 112702, they seem to be causingEric Christopher2010-09-011-1/+1
| | | | | | self host errors on clang-x86-64. llvm-svn: 112719
* If PrototypeValue is erased in the middle of using the SSAUpdatorDuncan Sands2010-09-011-1/+1
| | | | | | | then the SSAUpdator may access freed memory. Instead, simply pass in the type and name explicitly, which is all that was used anyway. llvm-svn: 112699
* remove dead protoChris Lattner2010-08-291-1/+0
| | | | llvm-svn: 112408
* Don't attempt the PRE inline asm calls, since we don't value number them ↵Owen Anderson2010-08-071-0/+5
| | | | | | yet. Fixes PR7835. llvm-svn: 110489
* Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson2010-08-061-1/+1
| | | | llvm-svn: 110460
* Revert r110396 to fix buildbots.Owen Anderson2010-08-061-1/+1
| | | | llvm-svn: 110410
* Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson2010-08-051-1/+1
| | | | | | | | address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. llvm-svn: 110396
* mass elimination of reliance on automatic iterator dereferencingGabor Greif2010-07-221-1/+1
| | | | llvm-svn: 109103
* Fix batch of converting RegisterPass<> to INTIALIZE_PASS().Owen Anderson2010-07-211-2/+1
| | | | llvm-svn: 109045
* cache result of operator* (found by inspection)Gabor Greif2010-07-091-2/+4
| | | | llvm-svn: 107971
* cache result of operator*Gabor Greif2010-07-091-6/+7
| | | | llvm-svn: 107969
* use getNumArgOperands instead of getNumOperandsGabor Greif2010-06-301-2/+2
| | | | llvm-svn: 107272
* use ArgOperand APIGabor Greif2010-06-241-6/+6
| | | | llvm-svn: 106730
* use callsite to obtain all argumentsGabor Greif2010-06-241-1/+2
| | | | llvm-svn: 106729
* Use pre-increment instead of post-increment when the result is not used.Dan Gohman2010-06-221-11/+11
| | | | llvm-svn: 106542
* Move FindAvailableLoadedValue isSafeToLoadUnconditionally out ofDan Gohman2010-05-281-0/+1
| | | | | | | lib/Transforms/Utils and into lib/Analysis so that Analysis passes can use them. llvm-svn: 104949
OpenPOWER on IntegriCloud