summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/DataStructure/DataStructure.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Silence VC++ warnings.Chris Lattner2005-01-121-11/+13
| | | | llvm-svn: 19506
* Move method out of line for better ICC supportChris Lattner2004-12-081-0/+11
| | | | | | Add some ifdefs for some stuff I like to be able to toggle easily llvm-svn: 18665
* Improve commentChris Lattner2004-10-311-2/+4
| | | | llvm-svn: 17375
* Add more paranoid assertions :)Chris Lattner2004-10-311-0/+12
| | | | llvm-svn: 17367
* Fix three bugs:Chris Lattner2004-10-301-9/+12
| | | | | | | | | | | | | | | | 1. Calls to external global VARIABLES should not be treated as a call to an external function 2. Efficiently deleting an element from a vector by using std::swap with the back, then pop_back is NOT a good way to keep the vector sorted. 3. Our hope of having stuff get deleted by making them redundant just won't work. In particular, if we have three calls in sequence that should be merged: A, B, C first we unify B into A. To be sure that they appeared identical (so B would be erased) we set B = A. On the next step, we unified C into A and set C = A. Unfortunately, this is no guarantee that C = B, so we would fail to delete the dead call. Switch to a more explicit scheme. llvm-svn: 17357
* * Add a methodChris Lattner2004-10-301-16/+28
| | | | | | | | | * change some uses of NH.getNode() in a bool context to use !NH.isNull() * Fix a bunch of places where we depended on the (undefined) order of evaluation of arguments to function calls to ensure that getNode() was called before getOffset(). In practice, this was NOT happening. llvm-svn: 17354
* Changes For Bug 352Reid Spencer2004-09-011-6/+6
| | | | | | | | 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
* Fix #includes of i*.h => Instructions.h as per PR403.Misha Brukman2004-07-291-1/+1
| | | | llvm-svn: 15334
* Disable some code that isn't helping mattersChris Lattner2004-07-081-1/+6
| | | | llvm-svn: 14682
* Move all of the DSA headers into the Analysis/DataStructure subdir.Chris Lattner2004-07-071-1/+1
| | | | llvm-svn: 14663
* As much as I hate to say it, the whole setNode interface for DSNodeHandlesChris Lattner2004-07-071-9/+6
| | | | | | | | | | | | is HOPELESSLY broken. The problem is that the embedded getNode call can change the offset of the node handle in unpredictable ways. As it turns out, all of the clients of this method really want to set both the node and the offset, thus it is more efficient (and less buggy) to just do both of them in one method call. This fixes some obscure bugs handling non-forwarded node handles. llvm-svn: 14660
* Fix merging of nodes whose incoming offset is not zero. This unbreaks DSA onChris Lattner2004-06-231-2/+1
| | | | | | several mallocbench programs, including perl. llvm-svn: 14342
* Rename Type::PrimitiveID to TypeId and ::getPrimitiveID() to ::getTypeID()Chris Lattner2004-06-171-2/+2
| | | | llvm-svn: 14201
* Wrapped code and comments at 80 cols; doxygenified some comments.Misha Brukman2004-04-291-16/+17
| | | | llvm-svn: 13264
* Fix a tiny bug that caused an incorrect assertion failure poolallocatingChris Lattner2004-03-131-4/+6
| | | | | | boxed-sim. llvm-svn: 12358
* implement new methodChris Lattner2004-03-091-0/+24
| | | | llvm-svn: 12264
* Fix a bug handling globals that are constants, but are still externalChris Lattner2004-03-081-1/+1
| | | | llvm-svn: 12208
* Implement a FIXME, improving the efficiency of DSA on povray.Chris Lattner2004-03-041-2/+16
| | | | | | | This reduces CBU time from 145s -> 122s (debug build), reduces # allocated nodes from 129420 to 116477. llvm-svn: 12125
* Fix BU datastructures with povray!Chris Lattner2004-03-041-11/+25
| | | | | | | | The problem was that we were merging a field of a node with a value that was deleted. Thanks to bugpoint for reducing povray to a nice small 3 function example. :) llvm-svn: 12116
* Only clone nodes that are needed in the caller, don't clone ALL aux calls. ↵Chris Lattner2004-03-041-20/+48
| | | | | | | | This improves povray from having ~600K nodes and 300K call nodes to 65K nodes and 25K call nodes. llvm-svn: 12109
* Fix a DSA bug that caused DSA to generate incredibly huge graphs and take ↵Chris Lattner2004-03-031-1/+34
| | | | | | | | | | forever to do it on povray. The problem is that we were not copying globals from callees to callers unless the existed in both graphs. We should have copied them in the case where the global pointed to a node that was copied as well. llvm-svn: 12104
* Deinline methods, add fast exitChris Lattner2004-03-031-0/+27
| | | | llvm-svn: 12102
* Fix a node mapping problem that was causing the pool allocator to locally ↵Chris Lattner2004-03-031-0/+3
| | | | | | | | allocate nodes that were globally live, thus breaking programs. llvm-svn: 12094
* Only clone global nodes between graphs if both graphs have the global.Chris Lattner2004-02-271-13/+6
| | | | llvm-svn: 11928
* Fix typoChris Lattner2004-02-261-1/+1
| | | | llvm-svn: 11864
* 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. llvm-svn: 11863
* 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 llvm-svn: 11852
* 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. llvm-svn: 11848
* 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. llvm-svn: 11695
* Fix an iterator invalidation problem which was causing some nodes to not beChris Lattner2004-02-211-20/+19
| | | | | | correctly merged over! llvm-svn: 11693
* Adjust to the changed StructType interface. In particular, ↵Chris Lattner2004-02-091-6/+6
| | | | | | getElementTypes() is gone. llvm-svn: 11228
* 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. llvm-svn: 11178
* 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. llvm-svn: 11175
* Bugfix for ilist conversion. The ilist wants to make an 'end' node which hasChris Lattner2004-02-081-1/+1
| | | | | | G == 0 llvm-svn: 11174
* Switch the Nodes list from being an std::vector<DSNode*> to an ilist<DSNode>Chris Lattner2004-02-081-19/+17
| | | | llvm-svn: 11173
* Change to use node_iterators instead of direct access to NodesChris Lattner2004-02-081-34/+43
| | | | llvm-svn: 11171
* getNodes() is gone, use node_begin/end insteadChris Lattner2004-02-071-5/+7
| | | | | | | Rename stats from dsnode -> dsa Add a new stat llvm-svn: 11167
* There is no need to clone over nodes that are going to be dead anywayChris Lattner2004-02-071-3/+5
| | | | llvm-svn: 11157
* Fix a bug aflicting 265.gapChris Lattner2004-01-291-4/+18
| | | | llvm-svn: 11006
* Minor bugfixesChris Lattner2004-01-291-8/+12
| | | | llvm-svn: 11005
* Rename DSGraph::ScalarMapTy -> DSScalarMapChris Lattner2004-01-281-6/+6
| | | | llvm-svn: 11001
* Fix a bugChris Lattner2004-01-281-1/+1
| | | | llvm-svn: 11000
* 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 llvm-svn: 10999
* 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. llvm-svn: 10996
* Minor tweaks, eliminate useless integer pruning optimziation, turn onChris Lattner2004-01-281-4/+6
| | | | | | timers by default llvm-svn: 10993
* 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 :( llvm-svn: 10992
* 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. llvm-svn: 10991
* Another bugfix, disable "spurious" output.Chris Lattner2004-01-281-1/+4
| | | | | | You gotta love spurious llvm-svn: 10990
* fix bug in previous checkinChris Lattner2004-01-271-1/+0
| | | | llvm-svn: 10989
* * 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 llvm-svn: 10987
OpenPOWER on IntegriCloud