aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/MemoryDependenceAnalysis.cpp
AgeCommit message (Collapse)Author
2009-11-26factor some code out into some helper functions.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@89975 91177308-0d34-0410-b5e6-96231b3b80d8
2009-11-22Remove dead code. While there, also turn a few 'T* ' into 'T *' to match theNick Lewycky
rest of the file. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@89577 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-28Treat lifetime begin/end markers as allocations/frees respectively for theOwen Anderson
purposes for GVN/DSE. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85383 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-28Be more careful about invariance reasoning on "store" queries. Stores still ↵Owen Anderson
need to depend on Ref and ModRef calls within the invariant region. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85380 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-28Add trivial support for the invariance intrinsics to memdep. This logic isOwen Anderson
purely local for now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85378 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-27Rename MallocFreeHelper as MemoryBuiltinsVictor Hernandez
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85286 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-26Rename MallocHelper as MallocFreeHelper, since it now also identifies calls ↵Victor Hernandez
to free() git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85181 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-26Remove FreeInst.Victor Hernandez
Remove LowerAllocations pass. Update some more passes to treate free calls just like they were treating FreeInst. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85176 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-24Auto-upgrade free instructions to calls to the builtin free function.Victor Hernandez
Update all analysis passes and transforms to treat free calls just like FreeInst. Remove RaiseAllocations and all its tests since FreeInst no longer needs to be raised. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84987 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-23Remove AllocationInst. Since MallocInst went away, AllocaInst is the only ↵Victor Hernandez
subclass of AllocationInst, so it no longer is necessary. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84969 91177308-0d34-0410-b5e6-96231b3b80d8
2009-10-13Memory dependence analysis was incorrectly stopping to scan for stores to a ↵Victor Hernandez
pointer at bitcast uses of a malloc call. It should continue scanning until the malloc call, and this patch fixes that. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83931 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-20Revert r82404, it is causing a bootstrap miscompile. This is very very Chris Lattner
scary, as it indicates a lurking bug. yay. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82411 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-20improve memdep to eliminate bitcasts (and aliases, and noop geps) Chris Lattner
early for the stated reasons: this allows it to find more equivalences and depend less on code layout. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82404 91177308-0d34-0410-b5e6-96231b3b80d8
2009-09-18Enhance analysis passes so that they apply the same analysis to malloc calls ↵Victor Hernandez
as to MallocInst. Reviewed by Eli Friedman. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82281 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-31Make TargetData optional in MemoryDependenceAnalysis.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77727 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-31Remove an unnecessary header.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77725 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-13factor the 'optimized sort' code out into a static helper functionChris Lattner
and use it from one more place. Patch by Jakub Staszak! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75478 91177308-0d34-0410-b5e6-96231b3b80d8
2009-07-13Move the re-sort of invalidated NonLocalPointerDeps cache earlierChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75476 91177308-0d34-0410-b5e6-96231b3b80d8
2009-05-25make memdep use the getModRefInfo method for stores instead of theChris Lattner
low-level alias() method, allowing it to reason more aggressively about pointers into constant memory. PR4189 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72403 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-29now that you can put a PointerIntPair in a SmallPtrSet, remove someChris Lattner
hackish workarounds from memdep git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@67971 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-11Debug intriniscs should be skipped when lookingDale Johannesen
for a dependency, not terminate the search. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@66709 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-09Ignore debug intrinsics when computing dependences.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@66399 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-06Remove this as dbginfo intrinsics has been defined asZhou Sheng
IntrNoMem. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@66256 91177308-0d34-0410-b5e6-96231b3b80d8
2009-03-05Ignore the debug info intrinsics when looking for dependency through basic ↵Zhou Sheng
block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@66119 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-23fix two more cases where we could let the NLPDI cache get unsorted.Chris Lattner
With this, sqlite3 now passes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62839 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-23Unconditionally reset 'cache' to zero, even if we don't need to resort it.Chris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62838 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-23a minor tweak to my previous patch, handle the invalidation caseChris Lattner
when there are multiple iterations of the loop. This fixes PR3375. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62822 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-22Fix PR3358, a really nasty bug where recursive phi translated Chris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62757 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-16fix PR3217: fully cached queries need to be verified against the Chris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61080 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-15if we have a phi translation failure of the start block,Chris Lattner
return *just* a clobber of the start block, not other random stuff as well. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61026 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-15Implement initial support for PHI translation in memdep. This means thatChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61022 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-10Don't dereference the end() iterator. This wasDuncan Sands
causing a bunch of failures when running "make ENABLE_EXPENSIVE_CHECKS=1 check". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60832 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09loosen up an assertion that isn't valid when called fromChris Lattner
invalidateCachedPointerInfo. Thanks to Bill for sending me a testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60805 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09Teach GVN to invalidate some memdep information when it does an RAUWChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60799 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09Teach BasicAA::getModRefInfo(CallSite, CallSite) someChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60794 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09Fix a fixme: allow memdep to see past read-only calls when doingChris Lattner
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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60786 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09rename getNonLocalDependency -> getNonLocalCallDependency, and removeChris Lattner
pointer stuff from it, simplifying the code a bit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60783 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09fix typos gabor noticedChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60754 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09restructure the top level non-local ptr dep query to handle Chris Lattner
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%. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60752 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09rename getNonLocalPointerDepInternal -> getNonLocalPointerDepFromBBChris Lattner
and split its inner loop out into a new GetNonLocalInfoForBlock function. No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60751 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09if we have two elements, insert both, don't use std::sort.Chris Lattner
This speeds up the new GVN by another 3% git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60747 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09If we're only adding one new element to 'Cache', insert it into its knownChris Lattner
position instead of using a full sort. This speeds up GVN by ~4% with the new memdep stuff. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60746 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09convert a couple other places that use pred_iterator to use the cachingChris Lattner
pred iterator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60745 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09use hte new pred cache to speed up the new non-local memdepChris Lattner
queries. This speeds up GVN using the new queries (not yet checked in) by just over 10%. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60743 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-08add another level of caching for non-local pointer queries, keepingChris Lattner
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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60695 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-07add an assert. the cast<> below would catch this but a message is moreChris Lattner
useful. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60674 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-07factor some code better.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60673 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-07factor some code, fixing some fixme's.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60672 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-07add support for caching pointer dependence queries. Nothing uses this yetChris Lattner
so it "can't" break anything. That said, it does appear to work. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60654 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-07Some internal refactoring to make it easier to cache results.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60650 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-29 05:21:01 +0000