aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Analysis/DataStructure/DataStructure.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Only clone global nodes between graphs if both graphs have the global.Chris Lattner2004-02-271-13/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11928 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix typoChris Lattner2004-02-261-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11864 91177308-0d34-0410-b5e6-96231b3b80d8
* The node doesn't have to be _no_ node flags, it just has to be complete andChris Lattner2004-02-261-2/+3
| | | | | | | not have any globals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11863 91177308-0d34-0410-b5e6-96231b3b80d8
* Two changes:Chris Lattner2004-02-251-1/+4
| | | | | | | | | | | | | | 1. Functions do not make things incomplete, only variables 2. Constant global variables no longer need to be marked incomplete, because we are guaranteed that the initializer for the global will be in the graph we are hacking on now. This makes resolution of indirect calls happen a lot more in the bu pass, supports things like vtables and the C counterparts (giant constant arrays of function pointers), etc... Testcase here: test/Regression/Analysis/DSGraph/constant_globals.ll git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11852 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify the dead node elimination stuffChris Lattner2004-02-251-10/+12
| | | | | | | | | | | Make the incompleteness marker faster by looping directly over the globals instead of over the scalars to find the globals Fix a bug where we didn't mark a global incomplete if it didn't have any outgoing edges. This wouldn't break any current clients but is still wrong. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11848 91177308-0d34-0410-b5e6-96231b3b80d8
* Use isNull instead of getNode() to test for existence of a node, this is ↵Chris Lattner2004-02-221-6/+11
| | | | | | | | | | cheaper. FIX MAJOR BUG, whereby we didn't merge null edges correctly. Correcting this fixes poolallocation on 175.vpr, and possibly others. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11695 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix an iterator invalidation problem which was causing some nodes to not beChris Lattner2004-02-211-20/+19
| | | | | | | correctly merged over! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11693 91177308-0d34-0410-b5e6-96231b3b80d8
* Adjust to the changed StructType interface. In particular, ↵Chris Lattner2004-02-091-6/+6
| | | | | | getElementTypes() is gone. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11228 91177308-0d34-0410-b5e6-96231b3b80d8
* Instead of callign removeTriviallyDeadNodes on the global graph every timeChris Lattner2004-02-081-8/+9
| | | | | | | | | | 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
* Substantially improve the DSA code by removing 'forwarding' nodes fromChris Lattner2004-02-081-1/+5
| | | | | | | | | | 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
* Bugfix for ilist conversion. The ilist wants to make an 'end' node which hasChris Lattner2004-02-081-1/+1
| | | | | | | G == 0 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11174 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch the Nodes list from being an std::vector<DSNode*> to an ilist<DSNode>Chris Lattner2004-02-081-19/+17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11173 91177308-0d34-0410-b5e6-96231b3b80d8
* Change to use node_iterators instead of direct access to NodesChris Lattner2004-02-081-34/+43
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11171 91177308-0d34-0410-b5e6-96231b3b80d8
* getNodes() is gone, use node_begin/end insteadChris Lattner2004-02-071-5/+7
| | | | | | | | 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
* There is no need to clone over nodes that are going to be dead anywayChris Lattner2004-02-071-3/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11157 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bug aflicting 265.gapChris Lattner2004-01-291-4/+18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11006 91177308-0d34-0410-b5e6-96231b3b80d8
* Minor bugfixesChris Lattner2004-01-291-8/+12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11005 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename DSGraph::ScalarMapTy -> DSScalarMapChris Lattner2004-01-281-6/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11001 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bugChris Lattner2004-01-281-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11000 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate the call to removeTriviallyDeadNodes from updateFromGlobals graph,Chris Lattner2004-01-281-4/+1
| | | | | | | | 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
* In updateFromGlobalsGraph, instead of iterating over all of the scalars in theChris Lattner2004-01-281-8/+7
| | | | | | | | | 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
* Minor tweaks, eliminate useless integer pruning optimziation, turn onChris Lattner2004-01-281-4/+6
| | | | | | | timers by default git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10993 91177308-0d34-0410-b5e6-96231b3b80d8
* Further reduce the number of nodes cloned with getClonedNH, using merge instead.Chris Lattner2004-01-281-1/+1
| | | | | | | | | 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
* Add a timer, fix a minor bug.Chris Lattner2004-01-281-4/+12
| | | | | | | 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
* Another bugfix, disable "spurious" output.Chris Lattner2004-01-281-1/+4
| | | | | | | You gotta love spurious git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10990 91177308-0d34-0410-b5e6-96231b3b80d8
* fix bug in previous checkinChris Lattner2004-01-271-1/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10989 91177308-0d34-0410-b5e6-96231b3b80d8
* * Add a new commandline argument to control the "global roots hack". DefaultChris Lattner2004-01-271-454/+407
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Initial support for implementing clonePartiallyInto in terms of ↵Chris Lattner2004-01-231-57/+122
| | | | | | cloneReachableSubgraph, though this support is currently disabled. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10970 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminated the CompletedNodes argument to the cloneReachable* methods. ThisChris Lattner2004-01-221-41/+20
| | | | | | | | | 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
* Ok, I'm tired of pulling out all my timers to check stuff in, just do it.Chris Lattner2004-01-221-0/+18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10954 91177308-0d34-0410-b5e6-96231b3b80d8
* Bug fix: X.mergeWith(Y) was not updating Y if Y was a null node handle!Chris Lattner2004-01-221-2/+9
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10953 91177308-0d34-0410-b5e6-96231b3b80d8
* Start implementing DSGraph::clonePartiallyInto and implement mergeInGraphChris Lattner2004-01-221-66/+176
| | | | | | | | | | | | 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
* Fine-grainify namespaces for this libraryChris Lattner2003-11-121-4/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9948 91177308-0d34-0410-b5e6-96231b3b80d8
* Add new argument to disable checkingChris Lattner2003-11-121-3/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9922 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't crash if no ggChris Lattner2003-11-121-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9913 91177308-0d34-0410-b5e6-96231b3b80d8
* Put all LLVM code into the llvm namespace, as per bug 109.Brian Gaeke2003-11-111-2/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9903 91177308-0d34-0410-b5e6-96231b3b80d8
* Compute node offsets correctlyChris Lattner2003-11-111-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9895 91177308-0d34-0410-b5e6-96231b3b80d8
* Add new method for computing node mappings. This is used by the pool allocatorChris Lattner2003-11-111-0/+31
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9880 91177308-0d34-0410-b5e6-96231b3b80d8
* All DSGraphs keep a reference to the targetdata they are created with. This isChris Lattner2003-11-021-9/+14
| | | | | | | | | 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
* Fix bug: test/Regression/Analysis/DSGraph/2003-11-02-NodeCollapsing.llChris Lattner2003-11-021-6/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9658 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9298 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove trivially dead nodes was not removing nodes that were dead due to ↵Chris Lattner2003-09-201-0/+14
| | | | | | forwarding! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8634 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch from using CallInst's to represent call sites to using the LLVMChris Lattner2003-09-201-2/+2
| | | | | | | | 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
* Fixed spelling and grammar.Misha Brukman2003-09-111-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8478 91177308-0d34-0410-b5e6-96231b3b80d8
* Add more verbose commentChris Lattner2003-08-051-10/+9
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7610 91177308-0d34-0410-b5e6-96231b3b80d8
* Added function mergeInGlobalsGraph which merges in the entire globals graph ↵Sumant Kowshik2003-08-051-0/+29
| | | | | | with the graph of a function git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7606 91177308-0d34-0410-b5e6-96231b3b80d8
* DEBUG got moved to Support/Debug.hChris Lattner2003-08-011-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7492 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix comment.Vikram S. Adve2003-07-221-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7227 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement 2 important changes: (1) rematerialization from the globals graph,Vikram S. Adve2003-07-161-65/+250
| | | | | | | | | | | | | | | | | | | | | | | | 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
* Remove globals more aggressively from graphs.Chris Lattner2003-07-031-11/+32
| | | | | | | 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
generated by cgit v1.1 at 2025-11-29 17:17:48 +0000