aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Analysis/DataStructure/DataStructure.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* INCLUDE_PARENT_GRAPH is required!Chris Lattner2003-07-021-21/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7088 91177308-0d34-0410-b5e6-96231b3b80d8
* Add support for ParentGraph only when building in debug modeChris Lattner2003-07-021-8/+48
| | | | | | | 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
* Rework TD pass to work with the precise call graph constructed by the BU phaseChris Lattner2003-07-011-0/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7031 91177308-0d34-0410-b5e6-96231b3b80d8
* Add new methodChris Lattner2003-06-301-0/+17
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7007 91177308-0d34-0410-b5e6-96231b3b80d8
* Be more const-correctChris Lattner2003-06-301-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7005 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix bug in last checkinChris Lattner2003-06-301-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7003 91177308-0d34-0410-b5e6-96231b3b80d8
* Handle the case where OldNodeMap == &ScalarMap correctlyChris Lattner2003-06-301-12/+7
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7000 91177308-0d34-0410-b5e6-96231b3b80d8
* Move usages of explicit hash_* datastructures to use typedefsChris Lattner2003-06-301-7/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6996 91177308-0d34-0410-b5e6-96231b3b80d8
* Revamp DSGraphs so that they can support multiple functions in the sameChris Lattner2003-06-301-40/+50
| | | | | | | DSGraph at one time git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6994 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix minor bug in previous checkinChris Lattner2003-06-291-3/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6986 91177308-0d34-0410-b5e6-96231b3b80d8
* Add support for "physical subtyping", which fixes:Chris Lattner2003-06-291-5/+140
| | | | | | | DSGraph/2003-06-29-NodeCollapsing2.ll & DSGraph/PhysicalSubtyping.ll git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6982 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid double negativesChris Lattner2003-06-281-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6945 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove support for the MultiObject flag, which was fundamentally brokenChris Lattner2003-06-221-11/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6840 91177308-0d34-0410-b5e6-96231b3b80d8
* * Changes to make NodeType be private to DSNode.Chris Lattner2003-06-191-32/+41
| | | | | | | | | * Add new MultiObject flag to DSNode which keeps track of whether or not multiple objects have been merged into the node, allowing must-alias info to be tracked. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6794 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove bogus assertion: a node with no referrers could be collapsed if ↵Chris Lattner2003-06-161-2/+0
| | | | | | field-sensitivity was disabled git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6695 91177308-0d34-0410-b5e6-96231b3b80d8
* s/convertable/convertible/gMisha Brukman2003-05-201-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6248 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't apply type information to load instructions if it will cause collapsingChris Lattner2003-03-031-5/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5684 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix resolution of indirect function calls... whoopsChris Lattner2003-02-141-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5576 91177308-0d34-0410-b5e6-96231b3b80d8
* - Eliminate provably non-pointer nodes from graphs.Chris Lattner2003-02-141-5/+22
| | | | | | | | | | | | | | | This helps a lot of testcases, for example: New Time New #Nodes Old Time Old #Nodes 254.gap: 91.1024 21605 91.1397 22657 povray31: 2.7807 8613 3.0152 10338 255.vortex: 1.2034 8153 1.2172 8822 moria: .6756 3150 .7054 3877 300.twolf: .1652 2010 .1851 3270 Typically, testcases which use long and ulong integers a lot get better, f.e. povray above. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5566 91177308-0d34-0410-b5e6-96231b3b80d8
* Move node forwarding code from being inlined to being out-of-line.Chris Lattner2003-02-131-0/+21
| | | | | | | This brings a 11.6% speedup to steens, and a 3.6 overall speedup to ds-aa git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5552 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement a "union-findy" version of DS-Analysis, which eliminates theChris Lattner2003-02-111-227/+120
| | | | | | | Referrers list on DSNodes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5536 91177308-0d34-0410-b5e6-96231b3b80d8
* Modest speedup which seems to help steens quite a bit on large graphsChris Lattner2003-02-101-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5532 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix problem breaking GAP, use hasNoReferrers moreChris Lattner2003-02-101-4/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5530 91177308-0d34-0410-b5e6-96231b3b80d8
* * Fix a bug where global incompleteness marking would not mark the globalChris Lattner2003-02-091-8/+5
| | | | | | | | | itself incomplete! * Allow incompleteness callers to specify they don't want globals to be considered sources of incompleteness. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5513 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a special case for main because we know it's incoming arguments don't aliasChris Lattner2003-02-081-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5511 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix an assertion failureChris Lattner2003-02-061-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5496 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement optimization for direct function call case. This dramaticallyChris Lattner2003-02-051-11/+25
| | | | | | | | reduces the number of function nodes created and speeds up analysis by about 10% overall. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5495 91177308-0d34-0410-b5e6-96231b3b80d8
* Add sanity checkChris Lattner2003-02-041-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5489 91177308-0d34-0410-b5e6-96231b3b80d8
* * Fix a bug introduced in the last checkin wrt Stack markersChris Lattner2003-02-031-8/+6
| | | | | | | * Make cloning more efficient in the process... git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5479 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement the globals graph!Chris Lattner2003-02-031-128/+163
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5477 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bug where we would delete neccesary calls in bu passChris Lattner2003-02-011-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5465 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a bug where we would incorrectly delete globals which had edges to alive ↵Chris Lattner2003-02-011-3/+0
| | | | | | | | | | nodes in a graph in the t-d pass. This slows down the TD pass by quite a bit (1/3), but is needed for correctness. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5464 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete nodes more efficientlyChris Lattner2003-02-011-6/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5463 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove dead nodes more efficientlyChris Lattner2003-02-011-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5462 91177308-0d34-0410-b5e6-96231b3b80d8
* Improve efficiency of aliveness traversal codeChris Lattner2003-02-011-21/+19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5461 91177308-0d34-0410-b5e6-96231b3b80d8
* Change DSGraph stuff to use hash_(set|map) instead of std::(set|map)Chris Lattner2003-02-011-29/+26
| | | | | | | This change provides a small (3%) but consistent speedup git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5460 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove using declarationsChris Lattner2003-02-011-14/+12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5456 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove globals on the bottom up pass which do not contain any informationChris Lattner2003-01-311-3/+22
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5451 91177308-0d34-0410-b5e6-96231b3b80d8
* Use and implement API for graph traversalsChris Lattner2003-01-291-24/+25
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5431 91177308-0d34-0410-b5e6-96231b3b80d8
* * Eliminate boolean arguments in favor of using enumsChris Lattner2003-01-231-6/+7
| | | | | | | * T-D pass now eliminates unreachable globals git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5419 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix analysis of the Burg programChris Lattner2003-01-221-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5401 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix several related bugs in DSNode::mergeWith() caused by theVikram S. Adve2002-12-061-90/+102
| | | | | | | | | | fact that the incoming nodes may be merged away at intermediate steps. Use an extra level of indirection via DSNodeHandles to track the nodes being merged. All this now happens in a static helper function MergeNodes(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4947 91177308-0d34-0410-b5e6-96231b3b80d8
* Cute bug fix: when moving links from N to this, some links could haveVikram S. Adve2002-12-051-14/+23
| | | | | | | | been missed if node *this got merged away due to recursive merging! Also, links were not moved correctly if a node is collapsed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4933 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix logical error in TD pass: we should clear Mod/Ref bits of each callerVikram S. Adve2002-11-271-2/+7
| | | | | | | | before inlining their graphs into a function. To support this, added flags to CloneFlags to strip/keep Mod/Ref bits. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4836 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2025-11-12 01:40:53 +0000