summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Implement initial support for PHI translation in memdep. This means thatChris Lattner2008-12-151-39/+166
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | memdep keeps track of how PHIs affect the pointer in dep queries, which allows it to eliminate the load in cases like rle-phi-translate.ll, which basically end up being: BB1: X = load P br BB3 BB2: Y = load Q br BB3 BB3: R = phi [P] [Q] load R turning "load R" into a phi of X/Y. In addition to additional exposed opportunities, this makes memdep safe in many cases that it wasn't before (which is required for load PRE) and also makes it substantially more efficient. For example, consider: bb1: // has many predecessors. P = some_operator() load P In this example, previously memdep would scan all the predecessors of BB1 to see if they had something that would mustalias P. In some cases (e.g. test/Transforms/GVN/rle-must-alias.ll) it would actually find them and end up eliminating something. In many other cases though, it would scan and not find anything useful. MemDep now stops at a block if the pointer is defined in that block and cannot be phi translated to predecessors. This causes it to miss the (rare) cases like rle-must-alias.ll, but makes it faster by not scanning tons of stuff that is unlikely to be useful. For example, this speeds up GVN as a whole from 3.928s to 2.448s (60%)!. IMO, scalar GVN should be enhanced to simplify the rle-must-alias pointer base anyway, which would allow the loads to be eliminated. In the future, this should be enhanced to phi translate through geps and bitcasts as well (as indicated by FIXMEs) making memdep even more powerful. llvm-svn: 61022
* Don't dereference the end() iterator. This wasDuncan Sands2008-12-101-2/+3
| | | | | | | causing a bunch of failures when running "make ENABLE_EXPENSIVE_CHECKS=1 check". llvm-svn: 60832
* loosen up an assertion that isn't valid when called fromChris Lattner2008-12-091-1/+1
| | | | | | | invalidateCachedPointerInfo. Thanks to Bill for sending me a testcase. llvm-svn: 60805
* Teach GVN to invalidate some memdep information when it does an RAUWChris Lattner2008-12-091-1/+15
| | | | | | | | | | | | | | | | | | | | | | | | of a pointer. This allows is to catch more equivalencies. For example, the type_lists_compatible_p function used to require two iterations of the gvn pass (!) to delete its 18 redundant loads because the first pass would CSE all the addressing computation cruft, which would unblock the second memdep/gvn passes from recognizing them. This change allows memdep/gvn to catch all 18 when run just once on the function (as is typical :) instead of just 3. On all of 403.gcc, this bumps up the # reundandancies found from: 63 gvn - Number of instructions PRE'd 153991 gvn - Number of instructions deleted 50069 gvn - Number of loads deleted to: 63 gvn - Number of instructions PRE'd 154137 gvn - Number of instructions deleted 50185 gvn - Number of loads deleted +120 loads deleted isn't bad. llvm-svn: 60799
* Teach BasicAA::getModRefInfo(CallSite, CallSite) someChris Lattner2008-12-091-17/+32
| | | | | | | | | | | | | | | | | | | | | | tricks based on readnone/readonly functions. Teach memdep to look past readonly calls when analyzing deps for a readonly call. This allows elimination of a few more calls from 403.gcc: before: 63 gvn - Number of instructions PRE'd 153986 gvn - Number of instructions deleted 50069 gvn - Number of loads deleted after: 63 gvn - Number of instructions PRE'd 153991 gvn - Number of instructions deleted 50069 gvn - Number of loads deleted 5 calls isn't much, but this adds plumbing for the next change. llvm-svn: 60794
* Fix a fixme: allow memdep to see past read-only calls when doingChris Lattner2008-12-091-4/+13
| | | | | | | | | | | | | load dependence queries. This allows GVN to eliminate a few more instructions on 403.gcc: 152598 gvn - Number of instructions deleted 49240 gvn - Number of loads deleted after: 153986 gvn - Number of instructions deleted 50069 gvn - Number of loads deleted llvm-svn: 60786
* rename getNonLocalDependency -> getNonLocalCallDependency, and removeChris Lattner2008-12-091-48/+22
| | | | | | pointer stuff from it, simplifying the code a bit. llvm-svn: 60783
* fix typos gabor noticedChris Lattner2008-12-091-1/+1
| | | | llvm-svn: 60754
* restructure the top level non-local ptr dep query to handle Chris Lattner2008-12-091-19/+26
| | | | | | | | the first block of a query specially. This makes the "complete query caching" subsystem more effective, avoiding predecessor queries. This speeds up GVN another 4%. llvm-svn: 60752
* rename getNonLocalPointerDepInternal -> getNonLocalPointerDepFromBBChris Lattner2008-12-091-65/+83
| | | | | | | and split its inner loop out into a new GetNonLocalInfoForBlock function. No functionality change. llvm-svn: 60751
* if we have two elements, insert both, don't use std::sort.Chris Lattner2008-12-091-3/+16
| | | | | | This speeds up the new GVN by another 3% llvm-svn: 60747
* If we're only adding one new element to 'Cache', insert it into its knownChris Lattner2008-12-091-1/+12
| | | | | | | position instead of using a full sort. This speeds up GVN by ~4% with the new memdep stuff. llvm-svn: 60746
* convert a couple other places that use pred_iterator to use the cachingChris Lattner2008-12-091-2/+4
| | | | | | pred iterator. llvm-svn: 60745
* use hte new pred cache to speed up the new non-local memdepChris Lattner2008-12-091-4/+24
| | | | | | | queries. This speeds up GVN using the new queries (not yet checked in) by just over 10%. llvm-svn: 60743
* add another level of caching for non-local pointer queries, keepingChris Lattner2008-12-081-7/+32
| | | | | | | | | track of whether the CachedNonLocalPointerInfo for a block is specific to a block. If so, just return it without any pred scanning. This is good for a 6% speedup on GVN (when it uses this lookup method, which it doesn't right now). llvm-svn: 60695
* add an assert. the cast<> below would catch this but a message is moreChris Lattner2008-12-071-0/+2
| | | | | | useful. llvm-svn: 60674
* factor some code better.Chris Lattner2008-12-071-17/+17
| | | | llvm-svn: 60673
* factor some code, fixing some fixme's.Chris Lattner2008-12-071-32/+23
| | | | llvm-svn: 60672
* add support for caching pointer dependence queries. Nothing uses this yetChris Lattner2008-12-071-17/+211
| | | | | | so it "can't" break anything. That said, it does appear to work. llvm-svn: 60654
* Some internal refactoring to make it easier to cache results.Chris Lattner2008-12-071-17/+26
| | | | llvm-svn: 60650
* Introduce a new MemDep::getNonLocalPointerDependencyChris Lattner2008-12-071-13/+82
| | | | | | | | | method. This will eventually take over load/store dep queries from getNonLocalDependency. For now it works fine, but is incredibly slow because it does no caching. Lets not switch GVN to use it until that is fixed :) llvm-svn: 60649
* push the "pointer case" up the analysis stack a bit. This causes Chris Lattner2008-12-071-47/+83
| | | | | | | duplication of logic (in 2 places) to determine what pointer a load/store touches. This will be addressed in a future commit. llvm-svn: 60648
* make clients have to know how to call getCallSiteDependencyFromChris Lattner2008-12-071-2/+13
| | | | | | instead of making getDependencyFrom do it. llvm-svn: 60647
* rename some variables for consistencyChris Lattner2008-12-071-6/+6
| | | | llvm-svn: 60644
* I love how using out of scope variables is not an error with GCC, no really ↵Chris Lattner2008-12-071-3/+3
| | | | | | I do. llvm-svn: 60643
* Rename getCallSiteDependency -> getCallSiteDependencyFrom toChris Lattner2008-12-071-4/+5
| | | | | | | | emphasize the scanning and make it more similar to getDependencyFrom llvm-svn: 60642
* a memdep query on a volatile load/store will always returnChris Lattner2008-12-071-11/+10
| | | | | | | | | clobber with the current implementation. Instead of returning a "precise clobber" just return a fuzzy one. This doesn't matter to any clients anyway and should speed up analysis time very very slightly. llvm-svn: 60641
* remove the ability to get memdep info for vaarg. I don't think theChris Lattner2008-12-071-6/+9
| | | | | | original impl was correct and noone actually makes the query anyway. llvm-svn: 60639
* Make a few major changes to memdep and its clients:Chris Lattner2008-12-051-35/+55
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Make it illegal to call getDependency* on non-memory instructionsChris Lattner2008-12-051-3/+4
| | | | | | like binary operators. llvm-svn: 60600
* Reimplement the non-local dependency data structure in terms of a sortedChris Lattner2008-12-011-50/+82
| | | | | | | | | | | | | | | | | | | 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
* Eliminate the DepResultTy abstraction. It is now completely Chris Lattner2008-11-301-48/+43
| | | | | | redundant with MemDepResult, and MemDepResult has a nicer interface. llvm-svn: 60308
* Cache TargetData/AliasAnalysis in the pass instead of callingChris Lattner2008-11-301-18/+18
| | | | | | | getAnalysis<>. getAnalysis<> is apparently extremely expensive. Doing this speeds up GVN on 403.gcc by 16%! llvm-svn: 60304
* Two changes: Make getDependency remove QueryInst for a dirty record'sChris Lattner2008-11-301-18/+26
| | | | | | | | | | | ReverseLocalDeps when we update it. This fixes a regression test failure from my last commit. Second, for each non-local cached information structure, keep a bit that indicates whether it is dirty or not. This saves us a scan over the whole thing in the common case when it isn't dirty. llvm-svn: 60274
* introduce a typedef, no functionality change.Chris Lattner2008-11-301-16/+15
| | | | llvm-svn: 60272
* Change NonLocalDeps to be a densemap of pointers to densemapChris Lattner2008-11-301-30/+52
| | | | | | | | | | | | instead of containing them by value. This increases the density (!) of NonLocalDeps as well as making the reallocation case faster. This speeds up gvn on 403.gcc by 2% and makes room for future improvements. I'm not super thrilled with having to explicitly manage the new/delete of the map, but it is necesary for the next change. llvm-svn: 60271
* calls never depend on allocations.Chris Lattner2008-11-301-12/+5
| | | | llvm-svn: 60268
* Fix a fixme by making memdep's handling of allocations more logical.Chris Lattner2008-11-301-20/+10
| | | | | | | | 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
* implement a fixme by introducing a new getDependencyFromInternalChris Lattner2008-11-301-24/+19
| | | | | | | method that returns its result as a DepResultTy instead of as a MemDepResult. This reduces conversion back and forth. llvm-svn: 60266
* Move the getNonLocalDependency method to a more logical place inChris Lattner2008-11-301-90/+89
| | | | | | the file, no functionality change. llvm-svn: 60265
* REmove an old fixme, resolve another fixme by adding liberalChris Lattner2008-11-301-2/+0
| | | | | | comments about what this class does. llvm-svn: 60264
* remove a bit of incorrect code that tried to be tricky about speeding up Chris Lattner2008-11-301-49/+24
| | | | | | | | | | | | | | | | | | | | | | | | | dependencies. The basic situation was this: consider if we had: store1 ... store2 ... store3 Where memdep thinks that store3 depends on store2 and store2 depends on store1. The problem happens when we delete store2: The code in question was updating dep info for store3 to be store1. This is a spiffy optimization, but is not safe at all, because aliasing isn't transitive. This bug isn't exposed today with DSE because DSE will only zap store2 if it is identifical to store 3, and in this case, it is safe to update it to depend on store1. However, memcpyopt is not so fortunate, which is presumably why the "dropInstruction" code used to exist. Since this doesn't actually provide a speedup in practice, just rip the code out. llvm-svn: 60263
* Eliminate the dropInstruction method, which is not needed any more.Chris Lattner2008-11-291-77/+33
| | | | | | Fix a subtle iterator invalidation bug I introduced in the last commit. llvm-svn: 60258
* implement some fixme's: when deleting an instruction withChris Lattner2008-11-291-14/+62
| | | | | | | | | | | | | an entry in the nonlocal deps map, don't reset entries referencing that instruction to [dirty, null], instead, set them to [dirty,next] where next is the instruction after the deleted one. Use this information in the non-local deps code to avoid rescanning entire blocks. This speeds up GVN slightly by avoiding pointless work. On 403.gcc this makes GVN 1.5% faster. llvm-svn: 60256
* Change MemDep::getNonLocalDependency to return its results asChris Lattner2008-11-291-7/+6
| | | | | | | a smallvector instead of a DenseMap. This speeds up GVN by 5% on 403.gcc. llvm-svn: 60255
* move MemoryDependenceAnalysis::verifyRemoved to the end of the file,Chris Lattner2008-11-291-32/+32
| | | | | | no functionality/code change. llvm-svn: 60254
* reimplement getNonLocalDependency with a simpler worklistChris Lattner2008-11-291-136/+73
| | | | | | | formulation that is faster and doesn't require nonLazyHelper. Much less code. llvm-svn: 60253
* rename some maps.Chris Lattner2008-11-291-35/+35
| | | | llvm-svn: 60242
* rename some variables.Chris Lattner2008-11-291-21/+21
| | | | llvm-svn: 60241
* eliminate a bunch of code in favor of using AliasAnalysis::getModRefInfo.Chris Lattner2008-11-291-47/+45
| | | | | | | Put a some code back to handle buggy behavior that GVN expects: it wants loads to depend on each other, and accesses to depend on their allocations. llvm-svn: 60240
OpenPOWER on IntegriCloud