summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Memory dependence analysis was incorrectly stopping to scan for stores to a ↵Victor Hernandez2009-10-131-10/+5
| | | | | | | | pointer at bitcast uses of a malloc call. It should continue scanning until the malloc call, and this patch fixes that. llvm-svn: 83931
* Revert r82404, it is causing a bootstrap miscompile. This is very very Chris Lattner2009-09-201-14/+1
| | | | | | scary, as it indicates a lurking bug. yay. llvm-svn: 82411
* improve memdep to eliminate bitcasts (and aliases, and noop geps) Chris Lattner2009-09-201-1/+14
| | | | | | | early for the stated reasons: this allows it to find more equivalences and depend less on code layout. llvm-svn: 82404
* Enhance analysis passes so that they apply the same analysis to malloc calls ↵Victor Hernandez2009-09-181-0/+10
| | | | | | | | as to MallocInst. Reviewed by Eli Friedman. llvm-svn: 82281
* Make TargetData optional in MemoryDependenceAnalysis.Dan Gohman2009-07-311-10/+7
| | | | llvm-svn: 77727
* Remove an unnecessary header.Dan Gohman2009-07-311-1/+0
| | | | llvm-svn: 77725
* factor the 'optimized sort' code out into a static helper functionChris Lattner2009-07-131-28/+38
| | | | | | and use it from one more place. Patch by Jakub Staszak! llvm-svn: 75478
* Move the re-sort of invalidated NonLocalPointerDeps cache earlierChris Lattner2009-07-131-14/+14
| | | | | | | | | | | so that all code paths get it. PR4256 was about a case where the phi translation loop would find all preds in the Visited cache, so it could get by without re-sorting the NonLocalPointerDeps cache. Fix this by resorting it earlier, there is no reason not to do this. This patch inspired by Jakub Staszak's patch. llvm-svn: 75476
* make memdep use the getModRefInfo method for stores instead of theChris Lattner2009-05-251-1/+9
| | | | | | | low-level alias() method, allowing it to reason more aggressively about pointers into constant memory. PR4189 llvm-svn: 72403
* now that you can put a PointerIntPair in a SmallPtrSet, remove someChris Lattner2009-03-291-17/+15
| | | | | | hackish workarounds from memdep llvm-svn: 67971
* Debug intriniscs should be skipped when lookingDale Johannesen2009-03-111-1/+1
| | | | | | for a dependency, not terminate the search. llvm-svn: 66709
* Ignore debug intrinsics when computing dependences.Owen Anderson2009-03-091-0/+6
| | | | llvm-svn: 66399
* Remove this as dbginfo intrinsics has been defined asZhou Sheng2009-03-061-5/+0
| | | | | | IntrNoMem. llvm-svn: 66256
* Ignore the debug info intrinsics when looking for dependency through basic ↵Zhou Sheng2009-03-051-0/+5
| | | | | | block. llvm-svn: 66119
* fix two more cases where we could let the NLPDI cache get unsorted.Chris Lattner2009-01-231-5/+14
| | | | | | With this, sqlite3 now passes. llvm-svn: 62839
* Unconditionally reset 'cache' to zero, even if we don't need to resort it.Chris Lattner2009-01-231-5/+4
| | | | | | | | | This avoids using a dangling pointer. Reset NumSortedEntries after restoring Cache to avoid extraneous sorts. This fixes the reduced sqlite3 testcase, but apparently not the whole app. llvm-svn: 62838
* a minor tweak to my previous patch, handle the invalidation caseChris Lattner2009-01-231-3/+4
| | | | | | when there are multiple iterations of the loop. This fixes PR3375. llvm-svn: 62822
* Fix PR3358, a really nasty bug where recursive phi translated Chris Lattner2009-01-221-3/+36
| | | | | | | | analyses could be run without the caches properly sorted. This can fix all sorts of weirdness. Many thanks to Bill for coming up with the 'issorted' verification idea. llvm-svn: 62757
* fix PR3217: fully cached queries need to be verified against the Chris Lattner2008-12-161-1/+21
| | | | | | | | visited set before they are used. If used, their blocks need to be added to the visited set so that subsequent queries don't use conflicting pointer values in the cache result blocks. llvm-svn: 61080
* if we have a phi translation failure of the start block,Chris Lattner2008-12-151-0/+1
| | | | | | | return *just* a clobber of the start block, not other random stuff as well. llvm-svn: 61026
* 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
OpenPOWER on IntegriCloud