aboutsummaryrefslogtreecommitdiffstats
path: root/include/llvm/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Extract source location info from DebugInfo.Devang Patel2009-01-051-9/+31
| | | | | | | Add methods to add source location info in a DIE. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61761 91177308-0d34-0410-b5e6-96231b3b80d8
* Add classof() methods so that dwarf writer can decide what DIDescriptor is ↵Devang Patel2009-01-051-2/+17
| | | | | | in its hand. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61740 91177308-0d34-0410-b5e6-96231b3b80d8
* Construct stuct field DIEs.Devang Patel2009-01-051-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61729 91177308-0d34-0410-b5e6-96231b3b80d8
* Construct enumerator DIE using DebugInfo.Devang Patel2009-01-051-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61726 91177308-0d34-0410-b5e6-96231b3b80d8
* Construct array/vector type DIEs using DebugInfo.Devang Patel2009-01-051-10/+12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61724 91177308-0d34-0410-b5e6-96231b3b80d8
* Now, getTag() is used by DwarfWriter.Devang Patel2009-01-051-3/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61718 91177308-0d34-0410-b5e6-96231b3b80d8
* Tidy up #includes, deleting a bunch of unnecessary #includes.Dan Gohman2009-01-059-17/+11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61715 91177308-0d34-0410-b5e6-96231b3b80d8
* Today the front-ends (llvm-gcc and clang) generate multiple ↵Devang Patel2008-12-171-9/+33
| | | | | | | | | | llvm.dbg.compile_units to identify source file for various debug entities. Each llvm.dbg.compile_unit matches one file on the disk. However, the backend only supports one DW_TAG_compile_unit per .o file. The backend selects first compile_unit from the vector to construct DW_TAG_compile_unit entry, which is not correct in all cases. First step to resolve this is, record file name and directory directly in debug info for various debug entities. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61164 91177308-0d34-0410-b5e6-96231b3b80d8
* Add -print-dbginfo pass that prints LLVM IR with comments inserted to showTorok Edwin2008-12-161-0/+3
| | | | | | | | which source/line a certain BB/instruction comes from, original variable names, and original (unmangled) C++ name of functions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61085 91177308-0d34-0410-b5e6-96231b3b80d8
* Add utility functions to search for DbgStopPointInst corresponding to anTorok Edwin2008-12-161-1/+14
| | | | | | | | instruction or BasicBlock, and to search for DbgDeclareInst corresponding to a variable. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61084 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement initial support for PHI translation in memdep. This means thatChris Lattner2008-12-151-5/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Fix getFieldAs() to use the parameter instead of 6.Torok Edwin2008-12-131-1/+1
| | | | | | | Add missing DIType constructor, needed by DIVariable::getType(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60976 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach GVN to invalidate some memdep information when it does an RAUWChris Lattner2008-12-091-1/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Teach BasicAA::getModRefInfo(CallSite, CallSite) someChris Lattner2008-12-091-1/+1
| | | | | | | | | | | | | | | | | | | | | | | 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
* rename getNonLocalDependency -> getNonLocalCallDependency, and removeChris Lattner2008-12-091-3/+3
| | | | | | | 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
* rename getNonLocalPointerDepInternal -> getNonLocalPointerDepFromBBChris Lattner2008-12-091-6/+10
| | | | | | | | 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
* use hte new pred cache to speed up the new non-local memdepChris Lattner2008-12-091-10/+7
| | | | | | | | 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
* add another level of caching for non-local pointer queries, keepingChris Lattner2008-12-081-1/+2
| | | | | | | | | | | 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
* Use bool instead of int, now that it no longer evokes a warning.Dan Gohman2008-12-071-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60678 91177308-0d34-0410-b5e6-96231b3b80d8
* fix a typo duncan noticed!Chris Lattner2008-12-071-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60671 91177308-0d34-0410-b5e6-96231b3b80d8
* add support for caching pointer dependence queries. Nothing uses this yetChris Lattner2008-12-071-8/+22
| | | | | | | 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
* Some internal refactoring to make it easier to cache results.Chris Lattner2008-12-071-4/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60650 91177308-0d34-0410-b5e6-96231b3b80d8
* Introduce a new MemDep::getNonLocalPointerDependencyChris Lattner2008-12-071-0/+12
| | | | | | | | | | 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 :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60649 91177308-0d34-0410-b5e6-96231b3b80d8
* push the "pointer case" up the analysis stack a bit. This causes Chris Lattner2008-12-071-4/+6
| | | | | | | | duplication of logic (in 2 places) to determine what pointer a load/store touches. This will be addressed in a future commit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60648 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename getCallSiteDependency -> getCallSiteDependencyFrom toChris Lattner2008-12-071-5/+3
| | | | | | | | | emphasize the scanning and make it more similar to getDependencyFrom git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60642 91177308-0d34-0410-b5e6-96231b3b80d8
* make getDependencyFrom private.Chris Lattner2008-12-071-10/+10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60637 91177308-0d34-0410-b5e6-96231b3b80d8
* Make a few major changes to memdep and its clients:Chris Lattner2008-12-051-22/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60607 91177308-0d34-0410-b5e6-96231b3b80d8
* Make it illegal to call getDependency* on non-memory instructionsChris Lattner2008-12-051-1/+2
| | | | | | | like binary operators. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60600 91177308-0d34-0410-b5e6-96231b3b80d8
* Update comments. There is no getArgumentAccesses.Dan Gohman2008-12-051-4/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60585 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a new SCEV representing signed division.Nick Lewycky2008-12-023-1/+55
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60407 91177308-0d34-0410-b5e6-96231b3b80d8
* cleanups suggested by duncan, thanks!Chris Lattner2008-12-011-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60353 91177308-0d34-0410-b5e6-96231b3b80d8
* Reimplement the non-local dependency data structure in terms of a sortedChris Lattner2008-12-011-15/+21
| | | | | | | | | | | | | | | | | | | | | 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 :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60313 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate the DepResultTy abstraction. It is now completely Chris Lattner2008-11-301-59/+42
| | | | | | | | redundant with MemDepResult, and MemDepResult has a nicer interface. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60308 91177308-0d34-0410-b5e6-96231b3b80d8
* Cache TargetData/AliasAnalysis in the pass instead of callingChris Lattner2008-11-301-3/+7
| | | | | | | | getAnalysis<>. getAnalysis<> is apparently extremely expensive. Doing this speeds up GVN on 403.gcc by 16%! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60304 91177308-0d34-0410-b5e6-96231b3b80d8
* Two changes: Make getDependency remove QueryInst for a dirty record'sChris Lattner2008-11-301-4/+7
| | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60274 91177308-0d34-0410-b5e6-96231b3b80d8
* introduce a typedef, no functionality change.Chris Lattner2008-11-301-1/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60272 91177308-0d34-0410-b5e6-96231b3b80d8
* Change NonLocalDeps to be a densemap of pointers to densemapChris Lattner2008-11-301-5/+8
| | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60271 91177308-0d34-0410-b5e6-96231b3b80d8
* implement a fixme by introducing a new getDependencyFromInternalChris Lattner2008-11-301-12/+13
| | | | | | | | method that returns its result as a DepResultTy instead of as a MemDepResult. This reduces conversion back and forth. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60266 91177308-0d34-0410-b5e6-96231b3b80d8
* REmove an old fixme, resolve another fixme by adding liberalChris Lattner2008-11-301-1/+12
| | | | | | | comments about what this class does. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60264 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate the dropInstruction method, which is not needed any more.Chris Lattner2008-11-291-5/+0
| | | | | | | | Fix a subtle iterator invalidation bug I introduced in the last commit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60258 91177308-0d34-0410-b5e6-96231b3b80d8
* implement some fixme's: when deleting an instruction withChris Lattner2008-11-291-9/+5
| | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60256 91177308-0d34-0410-b5e6-96231b3b80d8
* Change MemDep::getNonLocalDependency to return its results asChris Lattner2008-11-291-1/+2
| | | | | | | | a smallvector instead of a DenseMap. This speeds up GVN by 5% on 403.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60255 91177308-0d34-0410-b5e6-96231b3b80d8
* reimplement getNonLocalDependency with a simpler worklistChris Lattner2008-11-291-8/+10
| | | | | | | | formulation that is faster and doesn't require nonLazyHelper. Much less code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60253 91177308-0d34-0410-b5e6-96231b3b80d8
* tidy up some variable names.Chris Lattner2008-11-291-5/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60243 91177308-0d34-0410-b5e6-96231b3b80d8
* rename some maps.Chris Lattner2008-11-291-8/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60242 91177308-0d34-0410-b5e6-96231b3b80d8
* Split getDependency into getDependency and getDependencyFrom, the Chris Lattner2008-11-291-5/+12
| | | | | | | | former does caching, the later doesn't. This dramatically simplifies the logic in getDependency and getDependencyFrom. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60234 91177308-0d34-0410-b5e6-96231b3b80d8
* Now that DepType is private, we can start cleaning up some of its uses:Chris Lattner2008-11-291-11/+20
| | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60232 91177308-0d34-0410-b5e6-96231b3b80d8
* Introduce and use a new MemDepResult class to hold the results of a memdepChris Lattner2008-11-291-8/+77
| | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60231 91177308-0d34-0410-b5e6-96231b3b80d8
* Reimplement the internal abstraction used by MemDep in termsChris Lattner2008-11-291-24/+41
| | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60230 91177308-0d34-0410-b5e6-96231b3b80d8
* comment cleanups.Chris Lattner2008-11-281-4/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60220 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2025-08-06 09:29:12 +0000