summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* simplify some code and rename some variables. Reduce nesting.Chris Lattner2008-11-291-64/+64
| | | | | | | Use getTypeStoreSize instead of ABITypeSize for in-memory size in a couple places. llvm-svn: 60238
* Split getDependency into getDependency and getDependencyFrom, the Chris Lattner2008-11-291-124/+80
| | | | | | | former does caching, the later doesn't. This dramatically simplifies the logic in getDependency and getDependencyFrom. llvm-svn: 60234
* Now that DepType is private, we can start cleaning up some of its uses:Chris Lattner2008-11-291-73/+61
| | | | | | | | | | | | | | Document the Dirty value more precisely, use it for the uninitialized DepResultTy value. Change reverse mappings to be from an instruction* instead of DepResultTy, and stop tracking other forms. This makes it more clear that we only care about the instruction cases. Eliminate a DepResultTy,bool pair by using Dirty in the local case as well, shrinking the map and simplifying the code. This speeds up GVN by ~3% on 403.gcc. llvm-svn: 60232
* Introduce and use a new MemDepResult class to hold the results of a memdepChris Lattner2008-11-291-41/+40
| | | | | | | | | | | 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-114/+110
| | | | | | | | | | | | | | | 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 PR3141 by ensuring that MemoryDependenceAnalysis::removeInstructionChris Lattner2008-11-281-12/+28
| | | | | | | properly updates the reverse dependency map when it installs updated dependencies for instructions that depend on the removed instruction. llvm-svn: 60222
* more cleanups for MemoryDependenceAnalysis::removeInstruction,Chris Lattner2008-11-281-38/+42
| | | | | | no functionality change. llvm-svn: 60219
* random cleanups, no functionality change.Chris Lattner2008-11-281-29/+28
| | | | llvm-svn: 60218
* Run verifyRemoved from removeInstruction when -debug is specified.Chris Lattner2008-11-281-10/+14
| | | | | | This shows the root problem behind PR3141. llvm-svn: 60216
* rename "ping" to "verifyRemoved". I don't know why 'ping' what chosen,Chris Lattner2008-11-281-12/+13
| | | | | | | | but it doesn't make any sense at all. Also make the method const, private, and fit in 80 cols while we're at it. llvm-svn: 60215
* remove mysterious escaped newlines.Chris Lattner2008-11-281-5/+5
| | | | llvm-svn: 60211
OpenPOWER on IntegriCloud