aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/DataStructure/DataStructure.cpp
AgeCommit message (Collapse)Author
2004-02-09Adjust to the changed StructType interface. In particular, ↵Chris Lattner
getElementTypes() is gone. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11228 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-08Instead of callign removeTriviallyDeadNodes on the global graph every timeChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11178 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-08Substantially improve the DSA code by removing 'forwarding' nodes fromChris Lattner
DSGraphs while they are forwarding. When the last reference to the forwarding node is dropped, the forwarding node is autodeleted. This should simplify removeTriviallyDead nodes, and is only (efficiently) possible because we are using an ilist of dsnodes now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11175 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-08Bugfix for ilist conversion. The ilist wants to make an 'end' node which hasChris Lattner
G == 0 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11174 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-08Switch the Nodes list from being an std::vector<DSNode*> to an ilist<DSNode>Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11173 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-08Change to use node_iterators instead of direct access to NodesChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11171 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-07getNodes() is gone, use node_begin/end insteadChris Lattner
Rename stats from dsnode -> dsa Add a new stat git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11167 91177308-0d34-0410-b5e6-96231b3b80d8
2004-02-07There is no need to clone over nodes that are going to be dead anywayChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11157 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-29Fix a bug aflicting 265.gapChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11006 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-29Minor bugfixesChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11005 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-28Rename DSGraph::ScalarMapTy -> DSScalarMapChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11001 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-28Fix a bugChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11000 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-28Eliminate the call to removeTriviallyDeadNodes from updateFromGlobals graph,Chris Lattner
moving it to the start of removeDeadNodes. This speeds up DSA by 2s on perlbmk from 41s git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10999 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-28In updateFromGlobalsGraph, instead of iterating over all of the scalars in theChris Lattner
function to find the globals, iterate over all of the globals directly. This speeds the function up from 14s to 6.3s on perlbmk, reducing DSA time from 53->46s. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10996 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-28Minor tweaks, eliminate useless integer pruning optimziation, turn onChris Lattner
timers by default git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10993 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-28Further reduce the number of nodes cloned with getClonedNH, using merge instead.Chris Lattner
This reduces the number of nodes allocated, then immediately merged and DNE'd from 2193852 to 1298049. unfortunately this only speeds DSA up by ~1.5s (of 53s), because it's spending most of its time waddling through the scalar map :( git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10992 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-28Add a timer, fix a minor bug.Chris Lattner
Also, use RC::merge when possible, reducing the number of nodes allocated, then immediately merged away from 2985444 to 2193852 on perlbmk. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10991 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-28Another bugfix, disable "spurious" output.Chris Lattner
You gotta love spurious git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10990 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-27fix bug in previous checkinChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10989 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-27* Add a new commandline argument to control the "global roots hack". DefaultChris Lattner
it to be off. If it looks like it's completely unnecessary after testing, I will remove it completely (which is the hope). * Callers of the DSNode "copy ctor" can not choose to not copy links. * Make node collapsing not create a garbage node in some cases, avoiding a memory allocation, and a subsequent DNE. * When merging types, allow two functions of different types to be merged without collapsing. * Use DSNodeHandle::isNull more often instead of DSNodeHandle::getNode() == 0, as it is much more efficient. *** Implement the new, more efficient reachability cloner class In addition to only cloning nodes that are reachable from interesting roots, this also fixes the huge inefficiency we had where we cloned lots of nodes, only to merge them away immediately after they were cloned. Now we only actually allocate a node if there isn't one to merge it into. * Eliminate the now-obsolete cloneReachable* and clonePartiallyInto methods * Rewrite updateFromGlobalsGraph to use the reachability cloner * Rewrite mergeInGraph to use the reachability cloner * Disable the scalar map scanning code in removeTriviallyDeadNodes. In large SCC's, this is extremely expensive. We need a better data structure for the scalar map, because we really want to scan the unique node handles, not ALL of the scalars. * Remove the incorrect SANER_CODE_FOR_CHECKING_IF_ALL_REFERRERS_ARE_FROM_SCALARMAP code. * Move the code for eliminating integer nodes from the trivially dead eliminator to the dead node eliminator. * removeDeadNodes no longer uses removeTriviallyDeadNodes, as it contains a superset of the node removal power. * Only futz around with the globals graph in removeDeadNodes if it is modified git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10987 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-23Initial support for implementing clonePartiallyInto in terms of ↵Chris Lattner
cloneReachableSubgraph, though this support is currently disabled. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10970 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-22Eliminated the CompletedNodes argument to the cloneReachable* methods. ThisChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10955 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-22Ok, I'm tired of pulling out all my timers to check stuff in, just do it.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10954 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-22Bug fix: X.mergeWith(Y) was not updating Y if Y was a null node handle!Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10953 91177308-0d34-0410-b5e6-96231b3b80d8
2004-01-22Start implementing DSGraph::clonePartiallyInto and implement mergeInGraphChris Lattner
in terms of it. Though clonePartiallyInto is not cloning partial graphs yet, this change dramatically speeds up inlining of graphs with many scalars. For example, this change speeds up the BU pass on 253.perlbmk from 69s to 36s, because it avoids iteration over the scalar map, which can get pretty large. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10951 91177308-0d34-0410-b5e6-96231b3b80d8
2003-11-12Fine-grainify namespaces for this libraryChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9948 91177308-0d34-0410-b5e6-96231b3b80d8
2003-11-12Add new argument to disable checkingChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9922 91177308-0d34-0410-b5e6-96231b3b80d8
2003-11-12Don't crash if no ggChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9913 91177308-0d34-0410-b5e6-96231b3b80d8
2003-11-11Put all LLVM code into the llvm namespace, as per bug 109.Brian Gaeke
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9903 91177308-0d34-0410-b5e6-96231b3b80d8
2003-11-11Compute node offsets correctlyChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9895 91177308-0d34-0410-b5e6-96231b3b80d8
2003-11-11Add new method for computing node mappings. This is used by the pool allocatorChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9880 91177308-0d34-0410-b5e6-96231b3b80d8
2003-11-02All DSGraphs keep a reference to the targetdata they are created with. This isChris Lattner
used to eliminate the hard coded, hacked in, sparc specific, global TargetData. Changing the TargetData used to actually match the code fixes problems, and eliminates a crash. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9659 91177308-0d34-0410-b5e6-96231b3b80d8
2003-11-02Fix bug: test/Regression/Analysis/DSGraph/2003-11-02-NodeCollapsing.llChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9658 91177308-0d34-0410-b5e6-96231b3b80d8
2003-10-20Added LLVM project notice to the top of every C++ source file.John Criswell
Header files will be on the way. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9298 91177308-0d34-0410-b5e6-96231b3b80d8
2003-09-20Remove trivially dead nodes was not removing nodes that were dead due to ↵Chris Lattner
forwarding! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8634 91177308-0d34-0410-b5e6-96231b3b80d8
2003-09-20Switch from using CallInst's to represent call sites to using the LLVMChris Lattner
CallSite class. Now we can represent function calls by invoke instructions too! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8629 91177308-0d34-0410-b5e6-96231b3b80d8
2003-09-11Fixed spelling and grammar.Misha Brukman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8478 91177308-0d34-0410-b5e6-96231b3b80d8
2003-08-05Add more verbose commentChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7610 91177308-0d34-0410-b5e6-96231b3b80d8
2003-08-05Added function mergeInGlobalsGraph which merges in the entire globals graph ↵Sumant Kowshik
with the graph of a function git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7606 91177308-0d34-0410-b5e6-96231b3b80d8
2003-08-01DEBUG got moved to Support/Debug.hChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7492 91177308-0d34-0410-b5e6-96231b3b80d8
2003-07-22Fix comment.Vikram S. Adve
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7227 91177308-0d34-0410-b5e6-96231b3b80d8
2003-07-16Implement 2 important changes: (1) rematerialization from the globals graph,Vikram S. Adve
and (2) faster inlining by cloning only reachable nodes. In particular: (1) Added DSGraph::cloneReachableSubgraph and DSGraph::cloneReachableNodes to clone the subgraph reachable from a set of root nodes, into the current graph, merging the global nodes into thos in the current graph. The TD pass now uses this for faster inlining, and so does the next function. (2) Added DSGraph::updateFromGlobalGraph() to rematerialize nodes from the globals graph into the current graph in both BU and TD passes. (3) `I' flags are removed from all nodes in the globals graph, because they are difficult to maintain correctly and are not needed anyway. (4) Aux. function calls are only removed to the globals graph if they will never be resovled. (This is what fixed gap.) The immediate reason is that if we took these out of a function (and moved them to the globals graph) we would need to rematerialize these nodes into the function graph for every function in the BU pass. The longer term problem is that we would need to find a way to remove them from the globals graph iff they have been resolved on all paths through the call graph. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7187 91177308-0d34-0410-b5e6-96231b3b80d8
2003-07-03Remove globals more aggressively from graphs.Chris Lattner
Fix a bug where we removed nodes that were marked U. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7090 91177308-0d34-0410-b5e6-96231b3b80d8
2003-07-02INCLUDE_PARENT_GRAPH is required!Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7088 91177308-0d34-0410-b5e6-96231b3b80d8
2003-07-02Add support for ParentGraph only when building in debug modeChris Lattner
Minor cleanups, reenable folding of call nodes to external functions git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7061 91177308-0d34-0410-b5e6-96231b3b80d8
2003-07-01Rework TD pass to work with the precise call graph constructed by the BU phaseChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7031 91177308-0d34-0410-b5e6-96231b3b80d8
2003-06-30Add new methodChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7007 91177308-0d34-0410-b5e6-96231b3b80d8
2003-06-30Be more const-correctChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7005 91177308-0d34-0410-b5e6-96231b3b80d8
2003-06-30Fix bug in last checkinChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7003 91177308-0d34-0410-b5e6-96231b3b80d8
2003-06-30Handle the case where OldNodeMap == &ScalarMap correctlyChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7000 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-30 14:38:03 +0000