aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/DataStructure
AgeCommit message (Collapse)Author
2005-03-25remove a debugging timer.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20827 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-25Two changes here:Chris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20826 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-25Make the spliceFrom case where one graph is completely empty be constant time.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20825 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-24add a new DSGraph::spliceFrom method, which violently takes the content ofChris Lattner
one graph and plops it into another, without breaking a sweat. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20824 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-24This replaces the correct but slow code with a more aggressive scc-finderChris Lattner
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 :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20820 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-24only look at successors of globals. This gets us down to "only" 22s in theChris Lattner
bu pass for 176.gcc git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20818 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-24Unfortunately, a previous patch was not safe. Revert it, reimplementChris Lattner
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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20817 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-24don't bother |'ing in 0'sChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20815 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-24be more aggressive about incompleteness markingChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20814 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-24Fix a crash while promoting a value out of a loop from a global variableChris Lattner
when using ds-aa git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20802 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-24teach ds-aa about mod/ref for external function calls.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20801 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-23a hack to allow count-aa to work with ds-aa :(Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20791 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-23turn a dead conditional into an assert.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20787 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-23Totally gut mergeInGraph. There is absolutely no reason to be mergingChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20786 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-23wrap a long lineChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20785 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-23Make -steens-aa more conservative (aka correct) by making sure to obeyChris Lattner
incompleteness flags. Make it more aggressive by taking field sensitive information into account. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20781 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-23implement Analysis/DSGraph/field-sensitive.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20779 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22Several changes here:Chris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20775 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22Mark external globals incomplete in the BU Globals graph, fixingChris Lattner
Analysis/DSGraph/2005-03-22-IncompleteGlobal.ll git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20773 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22Remove an iteration pass over the entire scalarmap for each function createdChris Lattner
by not allowing integer constants to get into the scalar map in the first place. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20764 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22When making a clone of a DSGraph from the BU pass, make sure to remember thatChris Lattner
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*. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20763 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22Don't use operator[], use the new method instead, which is faster. This speedsChris Lattner
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 :( git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20762 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22Now that the dead ctor is gone, nothing uses the old node mapping exported byChris Lattner
cloneInto: make it an internally used mapping. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20760 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22remove a dead ctorChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20759 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22now that the second argument is always this->ReturnNodes, don't bother ↵Chris Lattner
passing it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20758 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22instead of using a local RetValMap, just use the graph we are cloning intoChris Lattner
for the return node map. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20757 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22now that the valuemapping is always the local scalar map, we can eliminateChris Lattner
this identity merge. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20755 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22remove the second argument to cloneIntoChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20754 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22add some timers, don't clone aux nodesChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20752 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22move this out of lineChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20751 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-22don't generate temporary scalarmaps.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20749 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-21allow passing clone flags down to cloneIntoChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20748 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-21Enhance the TD pass to build composite graphs when we have indirect callChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20743 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-21make this const correctChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20741 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-21Fix a major problem where we didn't add call graph edges for call sites withChris Lattner
more than 1 callee. This fixes Analysis/DSGraph/FunctionPointerTable-const.ll git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20740 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-21Ugh, for some reason, I can't call this unless the reference is const!?!?!?Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20732 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-21The reachability cloner should add arguments to merged calls when the RHS ofChris Lattner
the merge has more operands than the LHS. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20731 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-21'note to self'Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20727 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-21Change the way that the TD pass inlines graphs. Instead of inlining eachChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20723 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20Don't strip modref bits when inlining down the call graph. This fixesChris Lattner
the DSGraph/2003-06-30-TopDownResolve.ll regression from last night. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20717 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20Remove the ability to keep track of inlined globals, which is always dead.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20716 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20This call is always a noop, remove it.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20714 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20remove some pointless assertsChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20713 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20-steens doesn't use the inlined globals facility.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20712 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20Build EC's for globals twice. The first is after constructing the initialChris Lattner
Globals Graph for the local pass, the second is after all of the locals graphs have been constructed. This allows for many additional global EC's to be recognized that weren't before. This speeds up analysis of programs like 177.mesa, where it changes DSA from taking 0.712s to 0.4018s. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20711 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20Add a new DSNode::removeGlobal method.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20710 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20Transform BU pass to not use the horrible DSCallSiteIterator class.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20708 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20Implement new methods for dealing with DSNode global lists, rename uses ofChris Lattner
old methods. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20707 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20use simpler methods.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20706 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20method was renamed.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20705 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-01 16:56:21 +0000