summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Fix comment typo.Duncan Sands2008-09-111-1/+1
| | | | llvm-svn: 56116
* Fix a subtle bug when removing instructions from memdep. In very specific Owen Anderson2008-07-281-0/+4
| | | | | | | | circumstances we could end up remapping a dependee to the same instruction that we're trying to remove. Handle this properly by just falling back to a conservative solution. llvm-svn: 54132
* A better fix for PR2503 that doesn't pessimize GVN in the presence of ↵Owen Anderson2008-07-021-13/+0
| | | | | | unreachable blocks. llvm-svn: 53032
* Properly handle cases where a predecessor of the block being queried on is ↵Owen Anderson2008-07-011-0/+13
| | | | | | | | unreachable. This fixes PR2503, though we should also fix other passes not to emit this kind of code. llvm-svn: 52946
* Remember to update the reverse non-local cache when cleaning up dirty ↵Owen Anderson2008-06-011-0/+5
| | | | | | entries. This fixes PR2397. llvm-svn: 51846
* Make ping more aggressive in finding nonlocal caching errors.Owen Anderson2008-06-011-0/+3
| | | | llvm-svn: 51845
* Fix memdep's handling of invokes when finding the dependency of another callOwen Anderson2008-05-131-1/+1
| | | | | | instruction. This fixes some Ada miscompiles reported in PR2324. llvm-svn: 51069
* Clean up the use of static and anonymous namespaces. This turned upDan Gohman2008-05-131-8/+6
| | | | | | | several things that were neither in an anonymous namespace nor static but not intended to be global. llvm-svn: 51017
* Make several variable declarations static.Dan Gohman2008-05-061-1/+1
| | | | llvm-svn: 50696
* Make GVN able to remove unnecessary calls to read-only functions again.Owen Anderson2008-04-171-2/+1
| | | | llvm-svn: 49842
* Fix a typo in a comment.Dan Gohman2008-04-101-1/+1
| | | | llvm-svn: 49504
* Fix for PR2190. Memdep's non-local caching was checking dirtied blocks in theOwen Anderson2008-04-101-2/+4
| | | | | | wrong order. llvm-svn: 49499
* Set blockBegin to point to the beginning of the block,Dan Gohman2008-03-311-2/+2
| | | | | | not the end. llvm-svn: 48999
* Restore isCFGOnly property of various analysis passes.Devang Patel2008-03-201-1/+1
| | | | llvm-svn: 48579
* PassInfo keep tracks whether a pass is an analysis pass or not.Devang Patel2008-03-191-1/+1
| | | | llvm-svn: 48554
* Re-apply the patch to improve the optimizations of memcpy's, with severalOwen Anderson2008-02-121-1/+41
| | | | | | bugs fixed. This now passes PPC bootstrap. llvm-svn: 47026
* Throttle the non-local dependence analysis for basic blocks with more than ↵Tanya Lattner2008-02-061-7/+20
| | | | | | 50 predecessors. Added command line option to play with this threshold. llvm-svn: 46790
* Fix an obscure read-after-free bug that Duncan found.Owen Anderson2008-02-051-10/+20
| | | | llvm-svn: 46738
* Fix an issue where, under very specific circumstances, memdep could end up ↵Owen Anderson2008-01-301-2/+2
| | | | | | | | dereferencing the end of one of its internal maps. llvm-svn: 46541
* Remove attribution from file headers, per discussion on llvmdev.Chris Lattner2007-12-291-2/+2
| | | | llvm-svn: 45418
* Fix several cache coherence bugs in MemDep/GVN that were found. Also add ↵Owen Anderson2007-12-081-23/+67
| | | | | | | | some (disabled) debugging code to make such problems easier to diagnose in the future, written by Duncan Sands. llvm-svn: 44695
* Integrate the readonly/readnone logic more deeplyDuncan Sands2007-12-011-4/+2
| | | | | | | | | | | | | | | into alias analysis. This meant updating the API which now has versions of the getModRefBehavior, doesNotAccessMemory and onlyReadsMemory methods which take a callsite parameter. These should be used unless the callsite is not known, since in general they can do a better job than the versions that take a function. Also, users should no longer call the version of getModRefBehavior that takes both a function and a callsite. To reduce the chance of misuse it is now protected. llvm-svn: 44487
* Fix a silly bug that Nicholas noticed.Owen Anderson2007-11-261-1/+2
| | | | llvm-svn: 44324
* Allow GVN to eliminate read-only function calls when it can detect that they ↵Owen Anderson2007-11-261-4/+5
| | | | | | are redundant. llvm-svn: 44323
* Executive summary: getTypeSize -> getTypeStoreSize / getABITypeSize.Duncan Sands2007-11-011-11/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The meaning of getTypeSize was not clear - clarifying it is important now that we have x86 long double and arbitrary precision integers. The issue with long double is that it requires 80 bits, and this is not a multiple of its alignment. This gives a primitive type for which getTypeSize differed from getABITypeSize. For arbitrary precision integers it is even worse: there is the minimum number of bits needed to hold the type (eg: 36 for an i36), the maximum number of bits that will be overwriten when storing the type (40 bits for i36) and the ABI size (i.e. the storage size rounded up to a multiple of the alignment; 64 bits for i36). This patch removes getTypeSize (not really - it is still there but deprecated to allow for a gradual transition). Instead there is: (1) getTypeSizeInBits - a number of bits that suffices to hold all values of the type. For a primitive type, this is the minimum number of bits. For an i36 this is 36 bits. For x86 long double it is 80. This corresponds to gcc's TYPE_PRECISION. (2) getTypeStoreSizeInBits - the maximum number of bits that is written when storing the type (or read when reading it). For an i36 this is 40 bits, for an x86 long double it is 80 bits. This is the size alias analysis is interested in (getTypeStoreSize returns the number of bytes). There doesn't seem to be anything corresponding to this in gcc. (3) getABITypeSizeInBits - this is getTypeStoreSizeInBits rounded up to a multiple of the alignment. For an i36 this is 64, for an x86 long double this is 96 or 128 depending on the OS. This is the spacing between consecutive elements when you form an array out of this type (getABITypeSize returns the number of bytes). This is TYPE_SIZE in gcc. Since successive elements in a SequentialType (arrays, pointers and vectors) need to be aligned, the spacing between them will be given by getABITypeSize. This means that the size of an array is the length times the getABITypeSize. It also means that GEP computations need to use getABITypeSize when computing offsets. Furthermore, if an alloca allocates several elements at once then these too need to be aligned, so the size of the alloca has to be the number of elements multiplied by getABITypeSize. Logically speaking this doesn't have to be the case when allocating just one element, but it is simpler to also use getABITypeSize in this case. So alloca's and mallocs should use getABITypeSize. Finally, since gcc's only notion of size is that given by getABITypeSize, if you want to output assembler etc the same as gcc then getABITypeSize is the size you want. Since a store will overwrite no more than getTypeStoreSize bytes, and a read will read no more than that many bytes, this is the notion of size appropriate for alias analysis calculations. In this patch I have corrected all type size uses except some of those in ScalarReplAggregates, lib/Codegen, lib/Target (the hard cases). I will get around to auditing these too at some point, but I could do with some help. Finally, I made one change which I think wise but others might consider pointless and suboptimal: in an unpacked struct the amount of space allocated for a field is now given by the ABI size rather than getTypeStoreSize. I did this because every other place that reserves memory for a type (eg: alloca) now uses getABITypeSize, and I didn't want to make an exception for unpacked structs, i.e. I did it to make things more uniform. This only effects structs containing long doubles and arbitrary precision integers. If someone wants to pack these types more tightly they can always use a packed struct. llvm-svn: 43620
* Add partial caching of non-local memory dependence queries. This provides a ↵Owen Anderson2007-09-211-2/+33
| | | | | | | | modest speedup for GVN. llvm-svn: 42185
* Add a flag to mark a dirty cache entry. This is not yet used, but will ↵Owen Anderson2007-09-191-0/+1
| | | | | | | | eventually help non-local memdep caching. llvm-svn: 42137
* Fix a typo in memdep, which was causing PR1648.Owen Anderson2007-09-111-1/+1
| | | | llvm-svn: 41833
* Remove an un-needed dependence query. This improves compile time marginally ↵Owen Anderson2007-09-091-9/+10
| | | | | | on 401.bzip2. llvm-svn: 41792
OpenPOWER on IntegriCloud