summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/DataStructure/TopDownClosure.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Remove trailing whitespaceMisha Brukman2005-04-211-8/+8
| | | | llvm-svn: 21416
* fix some VC compilation problems, thanks to Jeff C for pointing this out!Chris Lattner2005-04-021-4/+3
| | | | llvm-svn: 21044
* use a callee_iterator typedef.Chris Lattner2005-04-021-3/+2
| | | | llvm-svn: 21038
* Change the ActualCallees callgraph from hash_multimap<Instruction,Function>Chris Lattner2005-04-021-32/+23
| | | | | | | | | to std::set<std::pair<Inst,Func>> to avoid duplicate entries. This speeds up the CompleteBU pass from 1.99s to .15s on povray and the eqgraph passes from 1.5s to .16s on the same. llvm-svn: 21031
* Fix a crash while promoting a value out of a loop from a global variableChris Lattner2005-03-241-1/+10
| | | | | | when using ds-aa llvm-svn: 20802
* 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
* add some timers, don't clone aux nodesChris Lattner2005-03-221-2/+29
| | | | llvm-svn: 20752
* 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
* '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
* Don't strip modref bits when inlining down the call graph. This fixesChris Lattner2005-03-201-1/+1
| | | | | | the DSGraph/2003-06-30-TopDownResolve.ll regression from last night. llvm-svn: 20717
* This call is always a noop, remove it.Chris Lattner2005-03-201-9/+0
| | | | llvm-svn: 20714
* Make use of simpler DSNode methods.Chris Lattner2005-03-201-5/+3
| | | | llvm-svn: 20702
* Create an equivalence class of global variables that DSA will never be ableChris Lattner2005-03-191-3/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 20696
* Start using retnodes_* for iteration.Chris Lattner2005-03-151-4/+3
| | | | llvm-svn: 20618
* Fix the Regression/Transforms/DSAnalysis/recursion.ll regression.Chris Lattner2005-02-041-4/+3
| | | | llvm-svn: 20031
* Fix some scary bugs that VC++ detected.Chris Lattner2005-01-311-1/+1
| | | | llvm-svn: 19941
* * Make some methods more const correct.Chris Lattner2005-01-301-18/+14
| | | | | | | | | | | | | | | | * Change the FunctionCalls and AuxFunctionCalls vectors into std::lists. This makes many operations on these lists much more natural, and avoids *exteremely* expensive copying of DSCallSites (e.g. moving nodes around between lists, erasing a node from not the end of the vector, etc). With a profile build of analyze, this speeds up BU DS from 25.14s to 12.59s on 176.gcc. I expect that it would help TD even more, but I don't have data for it. This effectively eliminates removeIdenticalCalls and children from the profile, going from 6.53 to 0.27s. llvm-svn: 19939
* Make -ds-aa more useful, allowing it to be updated as xforms hack on the ↵Chris Lattner2005-01-241-0/+53
| | | | | | program. llvm-svn: 19818
* 'Pass' should now not be derived from by clients. Instead, they should deriveChris Lattner2004-09-201-1/+1
| | | | | | | from ModulePass. Instead of implementing Pass::run, then should implement ModulePass::runOnModule. llvm-svn: 16436
* Changes For Bug 352Reid Spencer2004-09-011-2/+2
| | | | | | | | Move include/Config and include/Support into include/llvm/Config, include/llvm/ADT and include/llvm/Support. From here on out, all LLVM public header files must be under include/llvm/. llvm-svn: 16137
* Move all of the DSA headers into the Analysis/DataStructure subdir.Chris Lattner2004-07-071-2/+2
| | | | llvm-svn: 14663
* Wrapped code and comments at 80 cols; doxygenified some comments.Misha Brukman2004-04-291-2/+3
| | | | llvm-svn: 13264
* Instead of callign removeTriviallyDeadNodes on the global graph every timeChris Lattner2004-02-081-0/+2
| | | | | | | | | removeDeadNodes is called, only call it at the end of the pass being run. This saves 1.3 seconds running DSA on 177.mesa (5.3->4.0s), which is pretty big. This is only possible because of the automatic garbage collection done on forwarding nodes. llvm-svn: 11178
* Remove another unneeded call.Chris Lattner2004-02-081-1/+0
| | | | llvm-svn: 11177
* In the TD pass, iterate over globals directly instead of through the whole ↵Chris Lattner2004-01-281-9/+8
| | | | | | | | scalar map. This saves 5s in the TD pass, from 22->17s on perlbmk llvm-svn: 10998
* In the TD pass, don't iterate over the scalar map to find the globals, ↵Chris Lattner2004-01-281-3/+2
| | | | | | | | | iterate over the globals directly. This doesn't save any substantial time, however, because the globals graph only contains globals! llvm-svn: 10997
* Rewrite to use the reachability cloner interface. Also, make this much moreChris Lattner2004-01-271-58/+39
| | | | | | | | efficient in the case where a function calls into the same graph multiple times (ie, it either contains multiple calls to the same function, or multiple calls to functions in the same SCC graph) llvm-svn: 10986
* Eliminated the CompletedNodes argument to the cloneReachable* methods. ThisChris Lattner2004-01-221-2/+1
| | | | | | | | map was only used to implement a marginal GlobalsGraph optimization, and it actually slows the analysis down (due to the overhead of keeping it), so just eliminate it entirely. llvm-svn: 10955
* Fine-grainify namespaces for this libraryChris Lattner2003-11-121-4/+1
| | | | llvm-svn: 9948
* Put all LLVM code into the llvm namespace, as per bug 109.Brian Gaeke2003-11-111-0/+3
| | | | llvm-svn: 9903
* This doesn't use DSCallSiteIteratorChris Lattner2003-11-081-1/+1
| | | | llvm-svn: 9809
* Added LLVM project notice to the top of every C++ source file.John Criswell2003-10-201-0/+7
| | | | | | Header files will be on the way. llvm-svn: 9298
* Functions reachable from the arguments of unresolvable call nodes shouldChris Lattner2003-09-201-1/+13
| | | | | | not have their arguments marked complete llvm-svn: 8639
* Do not mark incoming arguments to functions complete if the function is ↵Chris Lattner2003-09-201-10/+30
| | | | | | pointed to by a global in the globals graph llvm-svn: 8637
* Switch from using CallInst's to represent call sites to using the LLVMChris Lattner2003-09-201-2/+4
| | | | | | | CallSite class. Now we can represent function calls by invoke instructions too! llvm-svn: 8629
* DEBUG got moved to Support/Debug.hChris Lattner2003-08-011-0/+1
| | | | llvm-svn: 7492
* (1) Rematerialize nodes from the globals graph into the current graphVikram S. Adve2003-07-161-57/+84
| | | | | | | | | | | | after all callers are inlined into the current graph. (2) Optimize the way a graph is inlined into its callees in the TD phase: (a) Use DSGraph::cloneReachableSubgraph to clone only a subgraph at each call site, for faster inlining. (b) Clone separately for the same callee at different call sites, since only the reachable subgraph is being cloned, not the entire caller graph. llvm-svn: 7188
* Remove space at end of lineChris Lattner2003-07-021-1/+1
| | | | llvm-svn: 7084
* Fix how we are handling unreachable functions. This DRAMATICALLY improves ↵Chris Lattner2003-07-021-36/+35
| | | | | | efficiency llvm-svn: 7082
* Try using trivially dead deletionChris Lattner2003-07-021-0/+1
| | | | llvm-svn: 7075
* Complete rewrite of td passChris Lattner2003-07-021-103/+101
| | | | llvm-svn: 7064
* Rework TD pass to work with the precise call graph constructed by the BU phaseChris Lattner2003-07-011-113/+147
| | | | llvm-svn: 7031
* Remove dead methodChris Lattner2003-06-301-27/+0
| | | | llvm-svn: 6999
* Do not multiply delete graphs if functions are sharing graphsChris Lattner2003-06-301-4/+6
| | | | llvm-svn: 6997
* Revamp DSGraphs so that they can support multiple functions in the sameChris Lattner2003-06-301-4/+8
| | | | | | DSGraph at one time llvm-svn: 6994
* Abstract out the predicate which decides whether a function gets completeChris Lattner2003-06-291-13/+23
| | | | | | arguments or not... llvm-svn: 6987
* Propagate globals graph from the local to bu to td globals graphs. ThisChris Lattner2003-06-281-2/+2
| | | | | | fixes bug: DSGraph/buglobals.ll llvm-svn: 6947
* Remove support for the MultiObject flag, which was fundamentally brokenChris Lattner2003-06-221-0/+1
| | | | llvm-svn: 6840
* Implement a "union-findy" version of DS-Analysis, which eliminates theChris Lattner2003-02-111-9/+3
| | | | | | Referrers list on DSNodes. llvm-svn: 5536
OpenPOWER on IntegriCloud