aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/DataStructure
AgeCommit message (Collapse)Author
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
2005-03-20print out equiv class info.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20704 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20some methods got renamedChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20703 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20Make use of simpler DSNode methods.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20702 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20#ifdef out a function only used by #ifdef'd code.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20700 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-20comment cleanupChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20699 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-19Create an equivalence class of global variables that DSA will never be ableChris Lattner
to tell apart anyway, and only track the leader for of these equivalence classes in our graphs. This dramatically reduces the number of GlobalValue*'s that appear in scalar maps, which A) reduces memory usage, by eliminating many many scalarmap entries and B) reduces time for operations that need to execute an operation for each global in the scalar map. As an example, this reduces the memory used to analyze 176.gcc from 1GB to 511MB, which (while it's still way too much) is better because it doesn't hit swap anymore. On eon, this shrinks the local graphs from 14MB to 6.8MB, shrinks the bu+td graphs of povray from 50M to 40M, shrinks the TD graphs of 130.li from 8.8M to 3.6M, etc. This change also speeds up DSA on large programs where this makes a big difference. For example, 130.li goes from 1.17s -> 0.56s, 134.perl goes from 2.14 -> 0.93s, povray goes from 15.63s->7.99s (!!!). This also apparently either fixes the problem that caused DSA to crash on perlbmk and gcc, or it hides it, because DSA now works on these. These both take entirely too much time in the TD pass (147s for perl, 538s for gcc, vs 7.67/5.9s in the bu pass for either one), but this is a known problem that I'll deal with later. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20696 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-19Switch to use the new interface for the EquivalenceClasses class, and fixChris Lattner
a bug involving SCC's who have multiple members that are part of an EC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20678 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-18do not bother inlining nullary functions without return values. The onlyChris Lattner
effect these calls can have is due to global variables, and these passes all use the globals graph to capture their effect anyway. This speeds up the BU pass very slightly on perlbmk, reducing the number of dsnodes allocated from 98913 to 96423. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20676 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-18fix a bogus assertionChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20675 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-18another fastpathChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20674 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-18remove a bogus optimization. This only works if there are no globals in theChris Lattner
graph, and the combination of a function that does not reference globals, takes not arguments and returns no value is pretty rare. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20670 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-18Rewrite DSAA::getModRefInfo to compute the mapping between caller and calleeChris Lattner
to determine mod/ref behavior, instead of creating a *copy* of the caller graph and inlining the callee graph into the copy. This speeds up aa-eval on Ptrdist/yacr2 from 109.13s to 3.98s, and gives identical results. The speedup is similar on other programs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20669 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-17implement a new method.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20668 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-17add some possibly bogus assertions.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20665 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-17simplify this function a bit, allow DS-AA to build on/improve the mod/refChris Lattner
results returned by AA, not just use one or the other. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20662 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-17Clean up some code, handle null pointer specially to avoid an assertionChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20660 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-17Two changes:Chris Lattner
1. Chain to the parent implementation of M/R analysis if we can't find any information. It has some heuristics that often do well. 2. Do not clear all flags, this can make invalid nodes by turning nodes that used to be collapsed into non-collapsed nodes (fixing crashes) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20659 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-17Fix the missing symbols problem Bill was hitting. Patch contributed byChris Lattner
Bill Wendling!! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20649 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-17Do not create ridiculously huge DSNodes, as described in the comments.Chris Lattner
This speeds up the BU pass on 172.mgrid from 62.3 -> 0.1242s. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20648 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-16remove use of compat_iterator.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20643 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-15make sure to mark nodes in the globals graph incomplete after computing itChris Lattner
so that external globals (and whatever they point to) are marked incomplete. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20628 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-15fix crashes when we only have a prototype for main.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20627 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-15Fix a crash that happens when mapping something like this:Chris Lattner
{ short, short } to short where the second short maps onto the second field of the first struct. In this case, the struct index is not aligned, so we should avoid calling getLink(2), which asserts out. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20626 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-15Make computeGGToGMapping compute an invnodemapChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20622 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-15Finally fix (the right way) the problem where functions like this:Chris Lattner
void foo() { G = 1; } would have an empty DSGraph even though G (a global) is directly used in the function. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20619 91177308-0d34-0410-b5e6-96231b3b80d8
2005-03-15Start using retnodes_* for iteration.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20618 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-11 11:11:49 +0000