summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/DataStructure
Commit message (Collapse)AuthorAgeFilesLines
* remove ...Chris Lattner2005-03-271-2/+2
| | | | llvm-svn: 20883
* speed up steens by using spliceFrom, improve its precision by realizing thatChris Lattner2005-03-271-5/+10
| | | | | | an incomplete node cannot alias a complete node. llvm-svn: 20882
* Don't give up completely, maybe other AA can say something about this.Chris Lattner2005-03-271-1/+2
| | | | llvm-svn: 20873
* Cache mapping information for a call site after computing it for a mod/refChris Lattner2005-03-261-27/+81
| | | | | | | | | query. If the next mod/ref query happens to be for the same call site (which is extremely likely), use the cache instead of recomputing the callee/caller mapping. This makes -aa-eval ***MUCH*** faster with ds-aa llvm-svn: 20871
* Remove more long dead code: dsa doesn't provide must alias infoChris Lattner2005-03-261-32/+0
| | | | llvm-svn: 20870
* remove some unsafe code that has long been deadChris Lattner2005-03-261-24/+0
| | | | llvm-svn: 20869
* slightly improve mod/ref for DSAA by checking the globals graph for fallbackChris Lattner2005-03-261-0/+12
| | | | llvm-svn: 20868
* Teach steens-aa two things about mod/ref information:Chris Lattner2005-03-261-3/+33
| | | | | | | | | 1. If memory never escapes the program, it cannot be mod/ref'd by external functions. 2. If memory is global never mod/ref'd in the program, it cannot be mod/ref'd by any call. llvm-svn: 20867
* no really, don't double count these nodes either!Chris Lattner2005-03-251-14/+19
| | | | llvm-svn: 20837
* Don't count all of the nodes in the SCC once for each function in the SCC.Chris Lattner2005-03-251-4/+9
| | | | llvm-svn: 20836
* Grow the EQ classes for globals at the end of the BU pass. This shrinksChris Lattner2005-03-251-0/+93
| | | | | | memory usage in the TD pass for 254.gap from 31.3MB to 3.9MB. llvm-svn: 20834
* remove a debugging timer.Chris Lattner2005-03-251-4/+1
| | | | llvm-svn: 20827
* Two changes here:Chris Lattner2005-03-251-47/+41
| | | | | | | | | | | 1. Instead of copying Local graphs to the BU graphs to start with, use spliceFrom to do the job (which is constant time in this case). On 176.gcc, this chops off .17s from the bu pass. 2. When building SCC graphs, simplify the logic and use spliceFrom to do the heavy lifting, instead of cloneInto/delete. This slices another .14s off 176.gcc. llvm-svn: 20826
* Make the spliceFrom case where one graph is completely empty be constant time.Chris Lattner2005-03-251-2/+6
| | | | llvm-svn: 20825
* add a new DSGraph::spliceFrom method, which violently takes the content ofChris Lattner2005-03-241-0/+41
| | | | | | one graph and plops it into another, without breaking a sweat. llvm-svn: 20824
* This replaces the correct but slow code with a more aggressive scc-finderChris Lattner2005-03-241-54/+97
| | | | | | | | based approach to find globals and call sites that need to be copied. This speeds up the BU pass on 176.gcc from 22s back up to 2.3s. Not as good as 1.5s, but at least it's correct :) llvm-svn: 20820
* only look at successors of globals. This gets us down to "only" 22s in theChris Lattner2005-03-241-4/+9
| | | | | | bu pass for 176.gcc llvm-svn: 20818
* Unfortunately, a previous patch was not safe. Revert it, reimplementChris Lattner2005-03-241-40/+93
| | | | | | | something correct. Unfortunately this takes 176.gcc's BU phase back up to 29s from 1.5. This fixes DSGraph/2005-03-24-Global-Arg-Alias.ll llvm-svn: 20817
* don't bother |'ing in 0'sChris Lattner2005-03-243-4/+2
| | | | llvm-svn: 20815
* be more aggressive about incompleteness markingChris Lattner2005-03-241-3/+2
| | | | llvm-svn: 20814
* Fix a crash while promoting a value out of a loop from a global variableChris Lattner2005-03-242-2/+20
| | | | | | when using ds-aa llvm-svn: 20802
* teach ds-aa about mod/ref for external function calls.Chris Lattner2005-03-241-1/+25
| | | | llvm-svn: 20801
* a hack to allow count-aa to work with ds-aa :(Chris Lattner2005-03-231-1/+1
| | | | llvm-svn: 20791
* turn a dead conditional into an assert.Chris Lattner2005-03-231-9/+5
| | | | llvm-svn: 20787
* Totally gut mergeInGraph. There is absolutely no reason to be mergingChris Lattner2005-03-231-73/+47
| | | | | | | | | | | global roots in from callees to callers. The BU graphs do not have accurate globals information and all of the clients know it. Instead, just make sure the GG is up-to-date, and they will be perfectly satiated. This speeds up the BU pass on 176.gcc from 5.5s to 1.5s, and Loc+BU+TD from 7s to 2.7s. llvm-svn: 20786
* wrap a long lineChris Lattner2005-03-231-1/+2
| | | | llvm-svn: 20785
* Make -steens-aa more conservative (aka correct) by making sure to obeyChris Lattner2005-03-231-8/+18
| | | | | | | | | incompleteness flags. Make it more aggressive by taking field sensitive information into account. llvm-svn: 20781
* implement Analysis/DSGraph/field-sensitive.llChris Lattner2005-03-231-3/+2
| | | | llvm-svn: 20779
* Several changes here:Chris Lattner2005-03-221-19/+42
| | | | | | | | | | | | 1. Increase max node size from 64->256 to avoid collapsing an important structure in 181.mcf 2. If we have multiple calls to an indirect call node with an indirect callee, fold these call nodes together, to avoid DSA turning apoc into a flaming fireball of death when analyzing 176.gcc. With this change, 176.gcc now takes ~7s to analyze for loc+bu+td, with 5.7s of that in the BU pass. llvm-svn: 20775
* Mark external globals incomplete in the BU Globals graph, fixingChris Lattner2005-03-221-0/+3
| | | | | | Analysis/DSGraph/2005-03-22-IncompleteGlobal.ll llvm-svn: 20773
* Remove an iteration pass over the entire scalarmap for each function createdChris Lattner2005-03-221-15/+8
| | | | | | | by not allowing integer constants to get into the scalar map in the first place. llvm-svn: 20764
* When making a clone of a DSGraph from the BU pass, make sure to remember thatChris Lattner2005-03-221-1/+8
| | | | | | | | | | this clone is supposed to be used for *ALL* of the functions in the SCC. This fixes the memory explosion problem the TD pass was having, reducing the memory growth from 24MB -> 3.5MB on povray and 270MB ->8.3MB on perlbmk! This obviously also speeds up the TD pass *a lot*. llvm-svn: 20763
* Don't use operator[], use the new method instead, which is faster. This speedsChris Lattner2005-03-221-1/+1
| | | | | | | up the TD pass about 30% for povray and perlbmk. It's still not clear why copying a 5MB set of graphs turns into a 25MB set of graphs though :( llvm-svn: 20762
* Now that the dead ctor is gone, nothing uses the old node mapping exported byChris Lattner2005-03-225-25/+12
| | | | | | cloneInto: make it an internally used mapping. llvm-svn: 20760
* remove a dead ctorChris Lattner2005-03-221-7/+0
| | | | llvm-svn: 20759
* now that the second argument is always this->ReturnNodes, don't bother ↵Chris Lattner2005-03-225-16/+18
| | | | | | passing it. llvm-svn: 20758
* instead of using a local RetValMap, just use the graph we are cloning intoChris Lattner2005-03-221-8/+5
| | | | | | for the return node map. llvm-svn: 20757
* now that the valuemapping is always the local scalar map, we can eliminateChris Lattner2005-03-221-4/+0
| | | | | | this identity merge. llvm-svn: 20755
* remove the second argument to cloneIntoChris Lattner2005-03-225-19/+14
| | | | llvm-svn: 20754
* add some timers, don't clone aux nodesChris Lattner2005-03-221-2/+29
| | | | llvm-svn: 20752
* move this out of lineChris Lattner2005-03-221-0/+28
| | | | llvm-svn: 20751
* don't generate temporary scalarmaps.Chris Lattner2005-03-221-17/+5
| | | | llvm-svn: 20749
* allow passing clone flags down to cloneIntoChris Lattner2005-03-211-2/+3
| | | | llvm-svn: 20748
* Enhance the TD pass to build composite graphs when we have indirect callChris Lattner2005-03-211-17/+108
| | | | | | | | | | sites that target multiple callees. If we have a function table, for example, with N callees, and M callers call through it, we used to have to perform O(M*N) graph inlinings. Now we perform O(M+N) inlinings. This speeds up the td pass on perlbmk from 36.26s to 25.75s. llvm-svn: 20743
* make this const correctChris Lattner2005-03-211-2/+2
| | | | llvm-svn: 20741
* Fix a major problem where we didn't add call graph edges for call sites withChris Lattner2005-03-211-6/+10
| | | | | | more than 1 callee. This fixes Analysis/DSGraph/FunctionPointerTable-const.ll llvm-svn: 20740
* Ugh, for some reason, I can't call this unless the reference is const!?!?!?Chris Lattner2005-03-211-2/+2
| | | | llvm-svn: 20732
* The reachability cloner should add arguments to merged calls when the RHS ofChris Lattner2005-03-211-1/+4
| | | | | | the merge has more operands than the LHS. llvm-svn: 20731
* 'note to self'Chris Lattner2005-03-211-2/+5
| | | | llvm-svn: 20727
* Change the way that the TD pass inlines graphs. Instead of inlining eachChris Lattner2005-03-211-72/+87
| | | | | | | | | | | | | | | | | | | | graph into all of the functions it calls when we visit a graph, change it so that the graph visitor inlines all of the callers of a graph into the current graph when it visits it. While we're at it, inline global information from the GG instead of from each of the callers. The GG contains a superset of the info that the callers do anyway, and this way we only need to do it one time (not one for each caller). This speeds up the TD pass substantially on several programs, and there is still room for improvement. For example, the TD pass used to take 147s on perlbmk, it now takes 36s. On povray, we went from about 5s to 1.97s. 134.perl is down from ~1s for Loc+BU+TD to .6s. The TD pass needs a lot of improvement though, which will occur with later patches. llvm-svn: 20723
OpenPOWER on IntegriCloud