aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/MemoryDependenceAnalysis.cpp
AgeCommit message (Collapse)Author
2013-05-06Fix unchecked uses of DominatorTree in MemoryDependenceAnalysis.Matt Arsenault
Use unknown results for places where it would be needed git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181176 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-17A limit of 500 was still a bit too high for some tests.Bill Wendling
PR15000 has a testcase where the time to compile was bordering on 30s. When I dropped the limit value to 100, it became a much more managable 6s. The compile time seems to increase in a roughly linear fashion based on increasing the limit value. (See the runtimes below.) So, let's lower the limit to 100 so that they can get a more reasonable compile time. Limit Value Time ----------- ---- 10 0.9744s 20 1.8035s 30 2.3618s 40 2.9814s 50 3.6988s 60 4.5486s 70 4.9314s 80 5.8012s 90 6.4246s 100 7.0852s 110 7.6634s 120 8.3553s 130 9.0552s 140 9.6820s 150 9.8804s 160 10.8901s 170 10.9855s 180 12.0114s 190 12.6816s 200 13.2754s 210 13.9942s 220 13.8097s 230 14.3272s 240 15.7753s 250 15.6673s 260 16.0541s 270 16.7625s 280 17.3823s 290 18.8213s 300 18.6120s 310 20.0333s 320 19.5165s 330 20.2505s 340 20.7068s 350 21.1833s 360 22.9216s 370 22.2152s 380 23.9390s 390 23.4609s 400 24.0426s 410 24.6410s 420 26.5208s 430 27.7155s 440 26.4142s 450 28.5646s 460 27.3494s 470 29.7255s 480 29.4646s 490 30.5001s git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179713 91177308-0d34-0410-b5e6-96231b3b80d8
2013-03-29Fix loop styleMatt Arsenault
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@178355 91177308-0d34-0410-b5e6-96231b3b80d8
2013-03-20Remove 'else' after 'return'.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@177607 91177308-0d34-0410-b5e6-96231b3b80d8
2013-03-20Remove trailing spaces.Jakub Staszak
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@177584 91177308-0d34-0410-b5e6-96231b3b80d8
2013-03-06Memory Dependence Analysis (not mem-dep test) take advantage of ↵Shuxin Yang
"invariant.load" metadata. The "invariant.load" metadata indicates the memory unit being accessed is immutable. A load annotated with this metadata can be moved across any store. As I am not sure if it is legal to move such loads across barrier/fence, this change dose not allow such transformation. rdar://11311484 Thank Arnold for code review. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176562 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-26Unify clang/llvm attributes for asan/tsan/msan (LLVM part)Kostya Serebryany
These are two related changes (one in llvm, one in clang). LLVM: - rename address_safety => sanitize_address (the enum value is the same, so we preserve binary compatibility with old bitcode) - rename thread_safety => sanitize_thread - rename no_uninitialized_checks -> sanitize_memory CLANG: - add __attribute__((no_sanitize_address)) as a synonym for __attribute__((no_address_safety_analysis)) - add __attribute__((no_sanitize_thread)) - add __attribute__((no_sanitize_memory)) for S in address thread memory If -fsanitize=S is present and __attribute__((no_sanitize_S)) is not set llvm attribute sanitize_S git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176075 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-13[tsan] disable load widening in ThreadSanitizer modeKostya Serebryany
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175034 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-31Change GetPointerBaseWithConstantOffset's DataLayout argument from aDan Gohman
reference to a pointer, so that it can handle the case where DataLayout is not available and behave conservatively. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174024 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-02Move all of the header files which are involved in modelling the LLVM IRChandler Carruth
into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171366 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-30Remove the Function::getFnAttributes method in favor of using the AttributeSetBill Wendling
directly. This is in preparation for removing the use of the 'Attribute' class as a collection of attributes. That will shift to the AttributeSet class instead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171253 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-19Rename the 'Attributes' class to 'Attribute'. It's going to represent a ↵Bill Wendling
single attribute in the future. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@170502 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-03Use the new script to sort the includes of every file under lib.Chandler Carruth
Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-23Ignore unreachable blocks when doing memory dependence analysis on non-localBill Wendling
loads. It's not really profitable and may result in GVN going into an infinite loop when it hits constructs like this: %x = gep %some.type %x, ... Found via an LTO build of LLVM. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166490 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-09Create enums for the different attributes.Bill Wendling
We use the enums to query whether an Attributes object has that attribute. The opaque layer is responsible for knowing where that specific attribute is stored. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165488 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-08Move TargetData to DataLayout.Micah Villmow
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165402 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-26Remove the `hasFnAttr' method from Function.Bill Wendling
The hasFnAttr method has been replaced by querying the Attributes explicitly. No intended functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164725 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-04Be conservative about allocations that may alias the accessed pointer.Bob Wilson
If an allocation has a must-alias relation to the access pointer, we treat it as a Def. Otherwise, without this check, the code here was just skipping over the allocation call and ignoring it. I noticed this by inspection and don't have a specific testcase that it breaks, but it seems like we need to treat a may-alias allocation as a Clobber. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163127 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-03Fix more fallout from r158919, similar to PR13547.Bob Wilson
This code used to only handle malloc-like calls, which do not read memory. r158919 changed it to check isNoAliasFn(), which includes strdup-like and realloc-like calls, but it was not checking for dependencies on the memory read by those calls. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163106 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-29Make MemoryBuiltins aware of TargetLibraryInfo.Benjamin Kramer
This disables malloc-specific optimization when -fno-builtin (or -ffreestanding) is specified. This has been a problem for a long time but became more severe with the recent memory builtin improvements. Since the memory builtin functions are used everywhere, this required passing TLI in many places. This means that functions that now have an optional TLI argument, like RecursivelyDeleteTriviallyDeadFunctions, won't remove dead mallocs anymore if the TLI argument is missing. I've updated most passes to do the right thing. Fixes PR13694 and probably others. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162841 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-13MemoryDependenceAnalysis attempts to find the first memory dependency for ↵Nadav Rotem
function calls. Currently, if GetLocation reports that it did not find a valid pointer (this is the case for volatile load/stores), we ignore the result. This patch adds code to handle the cases where we did not obtain a valid pointer. rdar://11872864 PR12899 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161802 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-21refactor the MemoryBuiltin analysis:Nuno Lopes
- provide more extensive set of functions to detect library allocation functions (e.g., malloc, calloc, strdup, etc) - provide an API to compute the size and offset of an object pointed by Move a few clients (GVN, AA, instcombine, ...) to the new API. This implementation is a lot more aggressive than each of the custom implementations being replaced. Patch reviewed by Nick Lewycky and Chandler Carruth, thanks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158919 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-02Fix typos found by http://github.com/lyda/misspell-checkBenjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157885 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-14Move the capture analysis from MemoryDependencyAnalysis to a more general placeChad Rosier
so that it can be reused in MemCpyOptimizer. This analysis is needed to remove an unnecessary memcpy when returning a struct into a local variable. rdar://11341081 PR12686 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156776 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-12Hoist simpler checks above llvm::PointerMayBeCaptured. No functional change ↵Chad Rosier
intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156687 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-26Don't call dominates on unreachable instructions. Should fix the dragoneggRafael Espindola
build. Testcase is still reducing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151474 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-06The patch resolves the conflict between AddressSanitizer and load widening ↵Kostya Serebryany
(GVN). The problem initially reported by Mozilla folks (http://code.google.com/p/address-sanitizer/issues/detail?id=20), but it also prevents us from enabling LLVM bootstrap with AddressSanitizer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149925 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-20More dead code removal (using -Wunreachable-code)David Blaikie
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148578 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-28Change CaptureTracking to pass a Use* instead of a Value* when a value isNick Lewycky
captured. This allows the tracker to look at the specific use, which may be especially interesting for function calls. Use this to fix 'nocapture' deduction in FunctionAttrs. The existing one does not iterate until a fixpoint and does not guarantee that it produces the same result regardless of iteration order. The new implementation builds up a graph of how arguments are passed from function to function, and uses a bottom-up walk on the argument-SCCs to assign nocapture. This gets us nocapture more often, and does so rather efficiently and independent of iteration order. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147327 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-21Fix crasher in GVN due to my recent capture tracking changes.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145047 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-20Less template, more virtual! Refactoring suggested by Chris in code review.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145014 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-20Refactor code to use new attribute getters on CallSite for NoCapture and ByVal.Nick Lewycky
Suggested in code review by Eli. That code in InstCombine looks kinda suspicious. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145013 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-14Refactor capture tracking (which already had a couple flags for whether returnsNick Lewycky
and stores capture) to permit the caller to see each capture point and decide whether to continue looking. Use this inside memdep to do an analysis that basicaa won't do. This lets us solve another devirtualization case, fixing PR8908! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144580 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-13Enhance the memdep interface so that users can tell the difference between a ↵Eli Friedman
dependency which cannot be calculated and a path reaching the entry point of the function. This patch introduces isNonFuncLocal, which replaces isUnknown in some cases. Patch by Xiaoyi Guo. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141896 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-15Misc analysis passes that need to be aware of atomic load/store.Eli Friedman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137650 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-18land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135375 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-15Add a limit to the number of instructions memdep will scan in a single ↵Eli Friedman
block. This prevents (at least in some cases) O(N^2) runtime in passes like DSE. The limit in this patch is probably too high, but it is enough to stop DSE from going completely insane on a testcase I have (which has a single block with around 50,000 non-aliasing stores in it). rdar://9471075 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133111 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-15Add "unknown" results for memdep, which mean "I don't know whether a ↵Eli Friedman
dependence for the given instruction exists in the given block". This cleans up all the existing hacks in memdep which represent this concept by returning clobber with various unrelated instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133031 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-04Disable the main feature of 130180, the elimination of loads that areDan Gohman
redundant with partially-aliasing loads. When computing what portion of a clobbering load value is needed, it doesn't consider phi-translation which may have occurred between the clobbing load and the redundant load. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132631 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-02When marking a block as being unanalyzable, use "Clobber" on the terminator ↵Eli Friedman
instead of the first instruction in the block. This is a bit of a hack; "Clobber" isn't really the right marking in the first place. memdep doesn't really have any way of properly expressing "unanalyzable" at the moment. Using it on the terminator is much less ambiguous than using it on an arbitrary instruction, though. In the given testcase, the "Clobber" was pointing to a load, and GVN was incorrectly assuming that meant that the "Clobber" load overlapped the load being analyzed (when they are actually unrelated). The included testcase tests both this commit and r132434. Part two of rdar://9429882. (r132434 was mislabeled.) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132442 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-01In MemoryDependenceAnalysis::getNonLocalPointerDepFromBB, if a given block ↵Eli Friedman
is is deemed unanalyzable (and we execute one of the "goto PredTranslationFailure" statements), make sure we don't put information about the predecessors of that block into the returned data structures; this can lead to, among other things, extraneous results (which will confuse passes using memdep). Fixes an assert in GVN compiling ruby. Part of rdar://problem/9521954 . Testcase coming up soon. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132434 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-17@llvm.lifetime.begin acts as a load, not @llvm.lifetime.end.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131437 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-28teach GVN to widen integer loads when they are overaligned, when doing an Chris Lattner
wider load would allow elimination of subsequent loads, and when the wider load is still a native integer type. This eliminates a ton of loads on various benchmarks involving struct fields, though it is somewhat hobbled by clang not being very aggressive about field alignment. This is yet another step along the way towards resolving PR6627. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130390 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-26Enhance memdep to return clobber relation between noalias loads whenChris Lattner
an earlier load could be widened to encompass a later load. For example, if we see: X = load i8* P, align 4 Y = load i8* (P+3), align 1 and we have a 32-bit native integer type, we can widen the former load to i32 which then makes the second load redundant. GVN can't actually do anything with this load/load relation yet, so this isn't testable, but it is the next step to resolving PR6627, and a fairly general class of "merge neighboring loads" missed optimizations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130250 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-26use AA::isMustAlias to simplify some calls.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130248 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-26remove support for llvm.invariant.end from memdep. It is a Chris Lattner
work-in-progress that is not progressing, and it has issues. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130247 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-26Enhance MemDep: When alias analysis returns a partial alias result,Chris Lattner
return it as a clobber. This allows GVN to do smart things. Enhance GVN to be smart about the case when a small load is clobbered by a larger overlapping load. In this case, forward the value. This allows us to compile stuff like this: int test(void *P) { int tmp = *(unsigned int*)P; return tmp+*((unsigned char*)P+1); } into: _test: ## @test movl (%rdi), %ecx movzbl %ch, %eax addl %ecx, %eax ret which has one load. We already handled the case where the smaller load was from a must-aliased base pointer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130180 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-24Give GetUnderlyingObject a TargetData, to keep it in syncDan Gohman
with BasicAA's DecomposeGEPExpression, which recently began using a TargetData. This fixes PR8968, though the testcase is awkward to reduce. Also, update several off GetUnderlyingObject's users which happen to have a TargetData handy to pass it in. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124134 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-11Revert r123207: "Turn on memdep's verifyRemoved() in an attempt to smoke out ↵Jakob Stoklund Olesen
the cause of our gcc bootstrap miscompare." It didn't. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123215 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-11Turn on memdep's verifyRemoved() in an attempt to smoke out the cause of our ↵Jakob Stoklund Olesen
gcc bootstrap miscompare. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123207 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-26 16:43:55 +0000